1193323Sed//===-- Local.cpp - Functions to perform local transformations ------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This family of functions perform various local transformations to the 11193323Sed// program. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#include "llvm/Transforms/Utils/Local.h" 16201360Srdivacky#include "llvm/ADT/DenseMap.h" 17249423Sdim#include "llvm/ADT/STLExtras.h" 18193323Sed#include "llvm/ADT/SmallPtrSet.h" 19218893Sdim#include "llvm/Analysis/Dominators.h" 20199481Srdivacky#include "llvm/Analysis/InstructionSimplify.h" 21234353Sdim#include "llvm/Analysis/MemoryBuiltins.h" 22198090Srdivacky#include "llvm/Analysis/ProfileInfo.h" 23218893Sdim#include "llvm/Analysis/ValueTracking.h" 24249423Sdim#include "llvm/DIBuilder.h" 25249423Sdim#include "llvm/DebugInfo.h" 26249423Sdim#include "llvm/IR/Constants.h" 27249423Sdim#include "llvm/IR/DataLayout.h" 28249423Sdim#include "llvm/IR/DerivedTypes.h" 29249423Sdim#include "llvm/IR/GlobalAlias.h" 30249423Sdim#include "llvm/IR/GlobalVariable.h" 31249423Sdim#include "llvm/IR/IRBuilder.h" 32249423Sdim#include "llvm/IR/Instructions.h" 33249423Sdim#include "llvm/IR/IntrinsicInst.h" 34249423Sdim#include "llvm/IR/Intrinsics.h" 35249423Sdim#include "llvm/IR/MDBuilder.h" 36249423Sdim#include "llvm/IR/Metadata.h" 37249423Sdim#include "llvm/IR/Operator.h" 38199481Srdivacky#include "llvm/Support/CFG.h" 39199481Srdivacky#include "llvm/Support/Debug.h" 40193323Sed#include "llvm/Support/GetElementPtrTypeIterator.h" 41193323Sed#include "llvm/Support/MathExtras.h" 42201360Srdivacky#include "llvm/Support/ValueHandle.h" 43199481Srdivacky#include "llvm/Support/raw_ostream.h" 44193323Sedusing namespace llvm; 45193323Sed 46193323Sed//===----------------------------------------------------------------------===// 47193323Sed// Local constant propagation. 48193323Sed// 49193323Sed 50223017Sdim/// ConstantFoldTerminator - If a terminator instruction is predicated on a 51223017Sdim/// constant value, convert it into an unconditional branch to the constant 52223017Sdim/// destination. This is a nontrivial operation because the successors of this 53223017Sdim/// basic block must have their PHI nodes updated. 54223017Sdim/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 55223017Sdim/// conditions and indirectbr addresses this might make dead if 56223017Sdim/// DeleteDeadConditions is true. 57243830Sdimbool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, 58243830Sdim const TargetLibraryInfo *TLI) { 59193323Sed TerminatorInst *T = BB->getTerminator(); 60223017Sdim IRBuilder<> Builder(T); 61193323Sed 62193323Sed // Branch - See if we are conditional jumping on constant 63193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 64193323Sed if (BI->isUnconditional()) return false; // Can't optimize uncond branch 65193323Sed BasicBlock *Dest1 = BI->getSuccessor(0); 66193323Sed BasicBlock *Dest2 = BI->getSuccessor(1); 67193323Sed 68193323Sed if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 69193323Sed // Are we branching on constant? 70193323Sed // YES. Change to unconditional branch... 71193323Sed BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 72193323Sed BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 73193323Sed 74193323Sed //cerr << "Function: " << T->getParent()->getParent() 75193323Sed // << "\nRemoving branch from " << T->getParent() 76193323Sed // << "\n\nTo: " << OldDest << endl; 77193323Sed 78193323Sed // Let the basic block know that we are letting go of it. Based on this, 79193323Sed // it will adjust it's PHI nodes. 80221345Sdim OldDest->removePredecessor(BB); 81193323Sed 82218893Sdim // Replace the conditional branch with an unconditional one. 83223017Sdim Builder.CreateBr(Destination); 84218893Sdim BI->eraseFromParent(); 85193323Sed return true; 86198892Srdivacky } 87198892Srdivacky 88198892Srdivacky if (Dest2 == Dest1) { // Conditional branch to same location? 89193323Sed // This branch matches something like this: 90193323Sed // br bool %cond, label %Dest, label %Dest 91193323Sed // and changes it into: br label %Dest 92193323Sed 93193323Sed // Let the basic block know that we are letting go of one copy of it. 94193323Sed assert(BI->getParent() && "Terminator not inserted in block!"); 95193323Sed Dest1->removePredecessor(BI->getParent()); 96193323Sed 97218893Sdim // Replace the conditional branch with an unconditional one. 98223017Sdim Builder.CreateBr(Dest1); 99223017Sdim Value *Cond = BI->getCondition(); 100218893Sdim BI->eraseFromParent(); 101223017Sdim if (DeleteDeadConditions) 102243830Sdim RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 103193323Sed return true; 104193323Sed } 105198892Srdivacky return false; 106198892Srdivacky } 107198892Srdivacky 108198892Srdivacky if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 109193323Sed // If we are switching on a constant, we can convert the switch into a 110193323Sed // single branch instruction! 111193323Sed ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 112234353Sdim BasicBlock *TheOnlyDest = SI->getDefaultDest(); 113193323Sed BasicBlock *DefaultDest = TheOnlyDest; 114193323Sed 115198892Srdivacky // Figure out which case it goes to. 116234353Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 117234353Sdim i != e; ++i) { 118193323Sed // Found case matching a constant operand? 119234353Sdim if (i.getCaseValue() == CI) { 120234353Sdim TheOnlyDest = i.getCaseSuccessor(); 121193323Sed break; 122193323Sed } 123193323Sed 124193323Sed // Check to see if this branch is going to the same place as the default 125193323Sed // dest. If so, eliminate it as an explicit compare. 126234353Sdim if (i.getCaseSuccessor() == DefaultDest) { 127243830Sdim MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); 128243830Sdim // MD should have 2 + NumCases operands. 129243830Sdim if (MD && MD->getNumOperands() == 2 + SI->getNumCases()) { 130243830Sdim // Collect branch weights into a vector. 131243830Sdim SmallVector<uint32_t, 8> Weights; 132243830Sdim for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 133243830Sdim ++MD_i) { 134243830Sdim ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(MD_i)); 135243830Sdim assert(CI); 136243830Sdim Weights.push_back(CI->getValue().getZExtValue()); 137243830Sdim } 138243830Sdim // Merge weight of this case to the default weight. 139243830Sdim unsigned idx = i.getCaseIndex(); 140243830Sdim Weights[0] += Weights[idx+1]; 141243830Sdim // Remove weight for this case. 142243830Sdim std::swap(Weights[idx+1], Weights.back()); 143243830Sdim Weights.pop_back(); 144243830Sdim SI->setMetadata(LLVMContext::MD_prof, 145243830Sdim MDBuilder(BB->getContext()). 146243830Sdim createBranchWeights(Weights)); 147243830Sdim } 148198892Srdivacky // Remove this entry. 149193323Sed DefaultDest->removePredecessor(SI->getParent()); 150193323Sed SI->removeCase(i); 151234353Sdim --i; --e; 152193323Sed continue; 153193323Sed } 154193323Sed 155193323Sed // Otherwise, check to see if the switch only branches to one destination. 156193323Sed // We do this by reseting "TheOnlyDest" to null when we find two non-equal 157193323Sed // destinations. 158234353Sdim if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = 0; 159193323Sed } 160193323Sed 161193323Sed if (CI && !TheOnlyDest) { 162193323Sed // Branching on a constant, but not any of the cases, go to the default 163193323Sed // successor. 164193323Sed TheOnlyDest = SI->getDefaultDest(); 165193323Sed } 166193323Sed 167193323Sed // If we found a single destination that we can fold the switch into, do so 168193323Sed // now. 169193323Sed if (TheOnlyDest) { 170198892Srdivacky // Insert the new branch. 171223017Sdim Builder.CreateBr(TheOnlyDest); 172193323Sed BasicBlock *BB = SI->getParent(); 173193323Sed 174193323Sed // Remove entries from PHI nodes which we no longer branch to... 175193323Sed for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 176193323Sed // Found case matching a constant operand? 177193323Sed BasicBlock *Succ = SI->getSuccessor(i); 178193323Sed if (Succ == TheOnlyDest) 179193323Sed TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 180193323Sed else 181193323Sed Succ->removePredecessor(BB); 182193323Sed } 183193323Sed 184198892Srdivacky // Delete the old switch. 185223017Sdim Value *Cond = SI->getCondition(); 186223017Sdim SI->eraseFromParent(); 187223017Sdim if (DeleteDeadConditions) 188243830Sdim RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 189193323Sed return true; 190198892Srdivacky } 191198892Srdivacky 192234353Sdim if (SI->getNumCases() == 1) { 193193323Sed // Otherwise, we can fold this switch into a conditional branch 194193323Sed // instruction if it has only one non-default destination. 195234353Sdim SwitchInst::CaseIt FirstCase = SI->case_begin(); 196239462Sdim IntegersSubset& Case = FirstCase.getCaseValueEx(); 197239462Sdim if (Case.isSingleNumber()) { 198239462Sdim // FIXME: Currently work with ConstantInt based numbers. 199239462Sdim Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), 200239462Sdim Case.getSingleNumber(0).toConstantInt(), 201239462Sdim "cond"); 202223017Sdim 203239462Sdim // Insert the new branch. 204243830Sdim BranchInst *NewBr = Builder.CreateCondBr(Cond, 205243830Sdim FirstCase.getCaseSuccessor(), 206243830Sdim SI->getDefaultDest()); 207243830Sdim MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); 208243830Sdim if (MD && MD->getNumOperands() == 3) { 209243830Sdim ConstantInt *SICase = dyn_cast<ConstantInt>(MD->getOperand(2)); 210243830Sdim ConstantInt *SIDef = dyn_cast<ConstantInt>(MD->getOperand(1)); 211243830Sdim assert(SICase && SIDef); 212243830Sdim // The TrueWeight should be the weight for the single case of SI. 213243830Sdim NewBr->setMetadata(LLVMContext::MD_prof, 214243830Sdim MDBuilder(BB->getContext()). 215243830Sdim createBranchWeights(SICase->getValue().getZExtValue(), 216243830Sdim SIDef->getValue().getZExtValue())); 217243830Sdim } 218193323Sed 219239462Sdim // Delete the old switch. 220239462Sdim SI->eraseFromParent(); 221239462Sdim return true; 222239462Sdim } 223193323Sed } 224198892Srdivacky return false; 225193323Sed } 226198892Srdivacky 227198892Srdivacky if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { 228198892Srdivacky // indirectbr blockaddress(@F, @BB) -> br label @BB 229198892Srdivacky if (BlockAddress *BA = 230198892Srdivacky dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 231198892Srdivacky BasicBlock *TheOnlyDest = BA->getBasicBlock(); 232198892Srdivacky // Insert the new branch. 233223017Sdim Builder.CreateBr(TheOnlyDest); 234198892Srdivacky 235198892Srdivacky for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 236198892Srdivacky if (IBI->getDestination(i) == TheOnlyDest) 237198892Srdivacky TheOnlyDest = 0; 238198892Srdivacky else 239198892Srdivacky IBI->getDestination(i)->removePredecessor(IBI->getParent()); 240198892Srdivacky } 241223017Sdim Value *Address = IBI->getAddress(); 242198892Srdivacky IBI->eraseFromParent(); 243223017Sdim if (DeleteDeadConditions) 244243830Sdim RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); 245198892Srdivacky 246198892Srdivacky // If we didn't find our destination in the IBI successor list, then we 247198892Srdivacky // have undefined behavior. Replace the unconditional branch with an 248198892Srdivacky // 'unreachable' instruction. 249198892Srdivacky if (TheOnlyDest) { 250198892Srdivacky BB->getTerminator()->eraseFromParent(); 251198892Srdivacky new UnreachableInst(BB->getContext(), BB); 252198892Srdivacky } 253198892Srdivacky 254198892Srdivacky return true; 255198892Srdivacky } 256198892Srdivacky } 257198892Srdivacky 258193323Sed return false; 259193323Sed} 260193323Sed 261193323Sed 262193323Sed//===----------------------------------------------------------------------===// 263199481Srdivacky// Local dead code elimination. 264193323Sed// 265193323Sed 266193323Sed/// isInstructionTriviallyDead - Return true if the result produced by the 267193323Sed/// instruction is not used, and the instruction has no side effects. 268193323Sed/// 269243830Sdimbool llvm::isInstructionTriviallyDead(Instruction *I, 270243830Sdim const TargetLibraryInfo *TLI) { 271193323Sed if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 272193323Sed 273226633Sdim // We don't want the landingpad instruction removed by anything this general. 274226633Sdim if (isa<LandingPadInst>(I)) 275226633Sdim return false; 276226633Sdim 277221345Sdim // We don't want debug info removed by anything this general, unless 278221345Sdim // debug info is empty. 279221345Sdim if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { 280226633Sdim if (DDI->getAddress()) 281221345Sdim return false; 282221345Sdim return true; 283226633Sdim } 284221345Sdim if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { 285221345Sdim if (DVI->getValue()) 286221345Sdim return false; 287221345Sdim return true; 288221345Sdim } 289193323Sed 290193323Sed if (!I->mayHaveSideEffects()) return true; 291193323Sed 292193323Sed // Special case intrinsics that "may have side effects" but can be deleted 293193323Sed // when dead. 294226633Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 295193323Sed // Safe to delete llvm.stacksave if dead. 296193323Sed if (II->getIntrinsicID() == Intrinsic::stacksave) 297193323Sed return true; 298226633Sdim 299226633Sdim // Lifetime intrinsics are dead when their right-hand is undef. 300226633Sdim if (II->getIntrinsicID() == Intrinsic::lifetime_start || 301226633Sdim II->getIntrinsicID() == Intrinsic::lifetime_end) 302226633Sdim return isa<UndefValue>(II->getArgOperand(1)); 303226633Sdim } 304234353Sdim 305243830Sdim if (isAllocLikeFn(I, TLI)) return true; 306234353Sdim 307243830Sdim if (CallInst *CI = isFreeCall(I, TLI)) 308234353Sdim if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0))) 309234353Sdim return C->isNullValue() || isa<UndefValue>(C); 310234353Sdim 311193323Sed return false; 312193323Sed} 313193323Sed 314193323Sed/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 315193323Sed/// trivially dead instruction, delete it. If that makes any of its operands 316202375Srdivacky/// trivially dead, delete them too, recursively. Return true if any 317202375Srdivacky/// instructions were deleted. 318243830Sdimbool 319243830Sdimllvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, 320243830Sdim const TargetLibraryInfo *TLI) { 321193323Sed Instruction *I = dyn_cast<Instruction>(V); 322243830Sdim if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI)) 323202375Srdivacky return false; 324193323Sed 325193323Sed SmallVector<Instruction*, 16> DeadInsts; 326193323Sed DeadInsts.push_back(I); 327193323Sed 328202375Srdivacky do { 329193323Sed I = DeadInsts.pop_back_val(); 330193323Sed 331193323Sed // Null out all of the instruction's operands to see if any operand becomes 332193323Sed // dead as we go. 333193323Sed for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 334193323Sed Value *OpV = I->getOperand(i); 335193323Sed I->setOperand(i, 0); 336193323Sed 337193323Sed if (!OpV->use_empty()) continue; 338193323Sed 339193323Sed // If the operand is an instruction that became dead as we nulled out the 340193323Sed // operand, and if it is 'trivially' dead, delete it in a future loop 341193323Sed // iteration. 342193323Sed if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 343243830Sdim if (isInstructionTriviallyDead(OpI, TLI)) 344193323Sed DeadInsts.push_back(OpI); 345193323Sed } 346193323Sed 347193323Sed I->eraseFromParent(); 348202375Srdivacky } while (!DeadInsts.empty()); 349202375Srdivacky 350202375Srdivacky return true; 351193323Sed} 352193323Sed 353218893Sdim/// areAllUsesEqual - Check whether the uses of a value are all the same. 354218893Sdim/// This is similar to Instruction::hasOneUse() except this will also return 355219077Sdim/// true when there are no uses or multiple uses that all refer to the same 356219077Sdim/// value. 357218893Sdimstatic bool areAllUsesEqual(Instruction *I) { 358218893Sdim Value::use_iterator UI = I->use_begin(); 359218893Sdim Value::use_iterator UE = I->use_end(); 360218893Sdim if (UI == UE) 361219077Sdim return true; 362218893Sdim 363218893Sdim User *TheUse = *UI; 364218893Sdim for (++UI; UI != UE; ++UI) { 365218893Sdim if (*UI != TheUse) 366218893Sdim return false; 367218893Sdim } 368218893Sdim return true; 369218893Sdim} 370218893Sdim 371193323Sed/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 372193323Sed/// dead PHI node, due to being a def-use chain of single-use nodes that 373193323Sed/// either forms a cycle or is terminated by a trivially dead instruction, 374193323Sed/// delete it. If that makes any of its operands trivially dead, delete them 375219077Sdim/// too, recursively. Return true if a change was made. 376243830Sdimbool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, 377243830Sdim const TargetLibraryInfo *TLI) { 378219077Sdim SmallPtrSet<Instruction*, 4> Visited; 379219077Sdim for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); 380219077Sdim I = cast<Instruction>(*I->use_begin())) { 381219077Sdim if (I->use_empty()) 382243830Sdim return RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 383193323Sed 384219077Sdim // If we find an instruction more than once, we're on a cycle that 385193323Sed // won't prove fruitful. 386219077Sdim if (!Visited.insert(I)) { 387219077Sdim // Break the cycle and delete the instruction and its operands. 388219077Sdim I->replaceAllUsesWith(UndefValue::get(I->getType())); 389243830Sdim (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 390219077Sdim return true; 391219077Sdim } 392219077Sdim } 393219077Sdim return false; 394193323Sed} 395193323Sed 396202375Srdivacky/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 397202375Srdivacky/// simplify any instructions in it and recursively delete dead instructions. 398202375Srdivacky/// 399202375Srdivacky/// This returns true if it changed the code, note that it can delete 400202375Srdivacky/// instructions in other blocks as well in this block. 401243830Sdimbool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD, 402243830Sdim const TargetLibraryInfo *TLI) { 403202375Srdivacky bool MadeChange = false; 404234353Sdim 405234353Sdim#ifndef NDEBUG 406234353Sdim // In debug builds, ensure that the terminator of the block is never replaced 407234353Sdim // or deleted by these simplifications. The idea of simplification is that it 408234353Sdim // cannot introduce new instructions, and there is no way to replace the 409234353Sdim // terminator of a block without introducing a new instruction. 410234353Sdim AssertingVH<Instruction> TerminatorVH(--BB->end()); 411234353Sdim#endif 412234353Sdim 413234353Sdim for (BasicBlock::iterator BI = BB->begin(), E = --BB->end(); BI != E; ) { 414234353Sdim assert(!BI->isTerminator()); 415202375Srdivacky Instruction *Inst = BI++; 416234353Sdim 417234353Sdim WeakVH BIHandle(BI); 418234353Sdim if (recursivelySimplifyInstruction(Inst, TD)) { 419202375Srdivacky MadeChange = true; 420210299Sed if (BIHandle != BI) 421202375Srdivacky BI = BB->begin(); 422202375Srdivacky continue; 423202375Srdivacky } 424221345Sdim 425243830Sdim MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI); 426221345Sdim if (BIHandle != BI) 427221345Sdim BI = BB->begin(); 428202375Srdivacky } 429202375Srdivacky return MadeChange; 430202375Srdivacky} 431202375Srdivacky 432193323Sed//===----------------------------------------------------------------------===// 433199481Srdivacky// Control Flow Graph Restructuring. 434193323Sed// 435193323Sed 436199481Srdivacky 437199481Srdivacky/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 438199481Srdivacky/// method is called when we're about to delete Pred as a predecessor of BB. If 439199481Srdivacky/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 440199481Srdivacky/// 441199481Srdivacky/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 442199481Srdivacky/// nodes that collapse into identity values. For example, if we have: 443199481Srdivacky/// x = phi(1, 0, 0, 0) 444199481Srdivacky/// y = and x, z 445199481Srdivacky/// 446199481Srdivacky/// .. and delete the predecessor corresponding to the '1', this will attempt to 447199481Srdivacky/// recursively fold the and to 0. 448199481Srdivackyvoid llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 449243830Sdim DataLayout *TD) { 450199481Srdivacky // This only adjusts blocks with PHI nodes. 451199481Srdivacky if (!isa<PHINode>(BB->begin())) 452199481Srdivacky return; 453199481Srdivacky 454199481Srdivacky // Remove the entries for Pred from the PHI nodes in BB, but do not simplify 455199481Srdivacky // them down. This will leave us with single entry phi nodes and other phis 456199481Srdivacky // that can be removed. 457199481Srdivacky BB->removePredecessor(Pred, true); 458199481Srdivacky 459199481Srdivacky WeakVH PhiIt = &BB->front(); 460199481Srdivacky while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) { 461199481Srdivacky PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt)); 462234353Sdim Value *OldPhiIt = PhiIt; 463218893Sdim 464234353Sdim if (!recursivelySimplifyInstruction(PN, TD)) 465234353Sdim continue; 466218893Sdim 467199481Srdivacky // If recursive simplification ended up deleting the next PHI node we would 468199481Srdivacky // iterate to, then our iterator is invalid, restart scanning from the top 469199481Srdivacky // of the block. 470210299Sed if (PhiIt != OldPhiIt) PhiIt = &BB->front(); 471199481Srdivacky } 472199481Srdivacky} 473199481Srdivacky 474199481Srdivacky 475193323Sed/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 476193323Sed/// predecessor is known to have one successor (DestBB!). Eliminate the edge 477193323Sed/// between them, moving the instructions in the predecessor into DestBB and 478193323Sed/// deleting the predecessor block. 479193323Sed/// 480198090Srdivackyvoid llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { 481193323Sed // If BB has single-entry PHI nodes, fold them. 482193323Sed while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 483193323Sed Value *NewVal = PN->getIncomingValue(0); 484193323Sed // Replace self referencing PHI with undef, it must be dead. 485193323Sed if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 486193323Sed PN->replaceAllUsesWith(NewVal); 487193323Sed PN->eraseFromParent(); 488193323Sed } 489193323Sed 490193323Sed BasicBlock *PredBB = DestBB->getSinglePredecessor(); 491193323Sed assert(PredBB && "Block doesn't have a single predecessor!"); 492193323Sed 493203954Srdivacky // Zap anything that took the address of DestBB. Not doing this will give the 494203954Srdivacky // address an invalid value. 495203954Srdivacky if (DestBB->hasAddressTaken()) { 496203954Srdivacky BlockAddress *BA = BlockAddress::get(DestBB); 497203954Srdivacky Constant *Replacement = 498203954Srdivacky ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1); 499203954Srdivacky BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 500203954Srdivacky BA->getType())); 501203954Srdivacky BA->destroyConstant(); 502203954Srdivacky } 503193323Sed 504193323Sed // Anything that branched to PredBB now branches to DestBB. 505193323Sed PredBB->replaceAllUsesWith(DestBB); 506193323Sed 507224145Sdim // Splice all the instructions from PredBB to DestBB. 508224145Sdim PredBB->getTerminator()->eraseFromParent(); 509224145Sdim DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 510224145Sdim 511198090Srdivacky if (P) { 512218893Sdim DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); 513218893Sdim if (DT) { 514218893Sdim BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); 515218893Sdim DT->changeImmediateDominator(DestBB, PredBBIDom); 516218893Sdim DT->eraseNode(PredBB); 517218893Sdim } 518198090Srdivacky ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); 519198090Srdivacky if (PI) { 520198090Srdivacky PI->replaceAllUses(PredBB, DestBB); 521198090Srdivacky PI->removeEdge(ProfileInfo::getEdge(PredBB, DestBB)); 522198090Srdivacky } 523198090Srdivacky } 524193323Sed // Nuke BB. 525193323Sed PredBB->eraseFromParent(); 526193323Sed} 527193323Sed 528199481Srdivacky/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 529199481Srdivacky/// almost-empty BB ending in an unconditional branch to Succ, into succ. 530199481Srdivacky/// 531199481Srdivacky/// Assumption: Succ is the single successor for BB. 532199481Srdivacky/// 533199481Srdivackystatic bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 534199481Srdivacky assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 535199481Srdivacky 536202375Srdivacky DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " 537199481Srdivacky << Succ->getName() << "\n"); 538199481Srdivacky // Shortcut, if there is only a single predecessor it must be BB and merging 539199481Srdivacky // is always safe 540199481Srdivacky if (Succ->getSinglePredecessor()) return true; 541199481Srdivacky 542199481Srdivacky // Make a list of the predecessors of BB 543234353Sdim SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 544199481Srdivacky 545199481Srdivacky // Look at all the phi nodes in Succ, to see if they present a conflict when 546199481Srdivacky // merging these blocks 547199481Srdivacky for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 548199481Srdivacky PHINode *PN = cast<PHINode>(I); 549199481Srdivacky 550199481Srdivacky // If the incoming value from BB is again a PHINode in 551199481Srdivacky // BB which has the same incoming value for *PI as PN does, we can 552199481Srdivacky // merge the phi nodes and then the blocks can still be merged 553199481Srdivacky PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 554199481Srdivacky if (BBPN && BBPN->getParent() == BB) { 555234353Sdim for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 556234353Sdim BasicBlock *IBB = PN->getIncomingBlock(PI); 557234353Sdim if (BBPreds.count(IBB) && 558234353Sdim BBPN->getIncomingValueForBlock(IBB) != PN->getIncomingValue(PI)) { 559202375Srdivacky DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 560199481Srdivacky << Succ->getName() << " is conflicting with " 561199481Srdivacky << BBPN->getName() << " with regard to common predecessor " 562234353Sdim << IBB->getName() << "\n"); 563199481Srdivacky return false; 564199481Srdivacky } 565199481Srdivacky } 566199481Srdivacky } else { 567199481Srdivacky Value* Val = PN->getIncomingValueForBlock(BB); 568234353Sdim for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 569199481Srdivacky // See if the incoming value for the common predecessor is equal to the 570199481Srdivacky // one for BB, in which case this phi node will not prevent the merging 571199481Srdivacky // of the block. 572234353Sdim BasicBlock *IBB = PN->getIncomingBlock(PI); 573234353Sdim if (BBPreds.count(IBB) && Val != PN->getIncomingValue(PI)) { 574202375Srdivacky DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 575199481Srdivacky << Succ->getName() << " is conflicting with regard to common " 576234353Sdim << "predecessor " << IBB->getName() << "\n"); 577199481Srdivacky return false; 578199481Srdivacky } 579199481Srdivacky } 580199481Srdivacky } 581199481Srdivacky } 582199481Srdivacky 583199481Srdivacky return true; 584199481Srdivacky} 585199481Srdivacky 586199481Srdivacky/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 587199481Srdivacky/// unconditional branch, and contains no instructions other than PHI nodes, 588224145Sdim/// potential side-effect free intrinsics and the branch. If possible, 589224145Sdim/// eliminate BB by rewriting all the predecessors to branch to the successor 590224145Sdim/// block and return true. If we can't transform, return false. 591199481Srdivackybool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { 592212904Sdim assert(BB != &BB->getParent()->getEntryBlock() && 593212904Sdim "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); 594212904Sdim 595199481Srdivacky // We can't eliminate infinite loops. 596199481Srdivacky BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 597199481Srdivacky if (BB == Succ) return false; 598199481Srdivacky 599199481Srdivacky // Check to see if merging these blocks would cause conflicts for any of the 600199481Srdivacky // phi nodes in BB or Succ. If not, we can safely merge. 601199481Srdivacky if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 602199481Srdivacky 603199481Srdivacky // Check for cases where Succ has multiple predecessors and a PHI node in BB 604199481Srdivacky // has uses which will not disappear when the PHI nodes are merged. It is 605199481Srdivacky // possible to handle such cases, but difficult: it requires checking whether 606199481Srdivacky // BB dominates Succ, which is non-trivial to calculate in the case where 607199481Srdivacky // Succ has multiple predecessors. Also, it requires checking whether 608249423Sdim // constructing the necessary self-referential PHI node doesn't introduce any 609199481Srdivacky // conflicts; this isn't too difficult, but the previous code for doing this 610199481Srdivacky // was incorrect. 611199481Srdivacky // 612199481Srdivacky // Note that if this check finds a live use, BB dominates Succ, so BB is 613199481Srdivacky // something like a loop pre-header (or rarely, a part of an irreducible CFG); 614199481Srdivacky // folding the branch isn't profitable in that case anyway. 615199481Srdivacky if (!Succ->getSinglePredecessor()) { 616199481Srdivacky BasicBlock::iterator BBI = BB->begin(); 617199481Srdivacky while (isa<PHINode>(*BBI)) { 618199481Srdivacky for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 619199481Srdivacky UI != E; ++UI) { 620199481Srdivacky if (PHINode* PN = dyn_cast<PHINode>(*UI)) { 621199481Srdivacky if (PN->getIncomingBlock(UI) != BB) 622199481Srdivacky return false; 623199481Srdivacky } else { 624199481Srdivacky return false; 625199481Srdivacky } 626199481Srdivacky } 627199481Srdivacky ++BBI; 628199481Srdivacky } 629199481Srdivacky } 630199481Srdivacky 631202375Srdivacky DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); 632199481Srdivacky 633199481Srdivacky if (isa<PHINode>(Succ->begin())) { 634199481Srdivacky // If there is more than one pred of succ, and there are PHI nodes in 635199481Srdivacky // the successor, then we need to add incoming edges for the PHI nodes 636199481Srdivacky // 637199481Srdivacky const SmallVector<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 638199481Srdivacky 639199481Srdivacky // Loop over all of the PHI nodes in the successor of BB. 640199481Srdivacky for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 641199481Srdivacky PHINode *PN = cast<PHINode>(I); 642199481Srdivacky Value *OldVal = PN->removeIncomingValue(BB, false); 643199481Srdivacky assert(OldVal && "No entry in PHI for Pred BB!"); 644199481Srdivacky 645199481Srdivacky // If this incoming value is one of the PHI nodes in BB, the new entries 646199481Srdivacky // in the PHI node are the entries from the old PHI. 647199481Srdivacky if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 648199481Srdivacky PHINode *OldValPN = cast<PHINode>(OldVal); 649199481Srdivacky for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 650199481Srdivacky // Note that, since we are merging phi nodes and BB and Succ might 651199481Srdivacky // have common predecessors, we could end up with a phi node with 652199481Srdivacky // identical incoming branches. This will be cleaned up later (and 653199481Srdivacky // will trigger asserts if we try to clean it up now, without also 654199481Srdivacky // simplifying the corresponding conditional branch). 655199481Srdivacky PN->addIncoming(OldValPN->getIncomingValue(i), 656199481Srdivacky OldValPN->getIncomingBlock(i)); 657199481Srdivacky } else { 658199481Srdivacky // Add an incoming value for each of the new incoming values. 659199481Srdivacky for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) 660199481Srdivacky PN->addIncoming(OldVal, BBPreds[i]); 661199481Srdivacky } 662199481Srdivacky } 663199481Srdivacky } 664199481Srdivacky 665224145Sdim if (Succ->getSinglePredecessor()) { 666224145Sdim // BB is the only predecessor of Succ, so Succ will end up with exactly 667224145Sdim // the same predecessors BB had. 668224145Sdim 669224145Sdim // Copy over any phi, debug or lifetime instruction. 670224145Sdim BB->getTerminator()->eraseFromParent(); 671224145Sdim Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList()); 672224145Sdim } else { 673224145Sdim while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 674199481Srdivacky // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 675199481Srdivacky assert(PN->use_empty() && "There shouldn't be any uses here!"); 676199481Srdivacky PN->eraseFromParent(); 677199481Srdivacky } 678199481Srdivacky } 679199481Srdivacky 680199481Srdivacky // Everything that jumped to BB now goes to Succ. 681199481Srdivacky BB->replaceAllUsesWith(Succ); 682199481Srdivacky if (!Succ->hasName()) Succ->takeName(BB); 683199481Srdivacky BB->eraseFromParent(); // Delete the old basic block. 684199481Srdivacky return true; 685199481Srdivacky} 686199481Srdivacky 687200581Srdivacky/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 688200581Srdivacky/// nodes in this block. This doesn't try to be clever about PHI nodes 689200581Srdivacky/// which differ only in the order of the incoming values, but instcombine 690200581Srdivacky/// orders them so it usually won't matter. 691200581Srdivacky/// 692200581Srdivackybool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 693200581Srdivacky bool Changed = false; 694200581Srdivacky 695200581Srdivacky // This implementation doesn't currently consider undef operands 696224145Sdim // specially. Theoretically, two phis which are identical except for 697200581Srdivacky // one having an undef where the other doesn't could be collapsed. 698200581Srdivacky 699200581Srdivacky // Map from PHI hash values to PHI nodes. If multiple PHIs have 700200581Srdivacky // the same hash value, the element is the first PHI in the 701200581Srdivacky // linked list in CollisionMap. 702200581Srdivacky DenseMap<uintptr_t, PHINode *> HashMap; 703200581Srdivacky 704200581Srdivacky // Maintain linked lists of PHI nodes with common hash values. 705200581Srdivacky DenseMap<PHINode *, PHINode *> CollisionMap; 706200581Srdivacky 707200581Srdivacky // Examine each PHI. 708200581Srdivacky for (BasicBlock::iterator I = BB->begin(); 709200581Srdivacky PHINode *PN = dyn_cast<PHINode>(I++); ) { 710200581Srdivacky // Compute a hash value on the operands. Instcombine will likely have sorted 711200581Srdivacky // them, which helps expose duplicates, but we have to check all the 712200581Srdivacky // operands to be safe in case instcombine hasn't run. 713200581Srdivacky uintptr_t Hash = 0; 714224145Sdim // This hash algorithm is quite weak as hash functions go, but it seems 715224145Sdim // to do a good enough job for this particular purpose, and is very quick. 716200581Srdivacky for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { 717200581Srdivacky Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I)); 718200581Srdivacky Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 719200581Srdivacky } 720224145Sdim for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end(); 721224145Sdim I != E; ++I) { 722224145Sdim Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I)); 723224145Sdim Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 724224145Sdim } 725221345Sdim // Avoid colliding with the DenseMap sentinels ~0 and ~0-1. 726221345Sdim Hash >>= 1; 727200581Srdivacky // If we've never seen this hash value before, it's a unique PHI. 728200581Srdivacky std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair = 729200581Srdivacky HashMap.insert(std::make_pair(Hash, PN)); 730200581Srdivacky if (Pair.second) continue; 731200581Srdivacky // Otherwise it's either a duplicate or a hash collision. 732200581Srdivacky for (PHINode *OtherPN = Pair.first->second; ; ) { 733200581Srdivacky if (OtherPN->isIdenticalTo(PN)) { 734200581Srdivacky // A duplicate. Replace this PHI with its duplicate. 735200581Srdivacky PN->replaceAllUsesWith(OtherPN); 736200581Srdivacky PN->eraseFromParent(); 737200581Srdivacky Changed = true; 738200581Srdivacky break; 739200581Srdivacky } 740200581Srdivacky // A non-duplicate hash collision. 741200581Srdivacky DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN); 742200581Srdivacky if (I == CollisionMap.end()) { 743200581Srdivacky // Set this PHI to be the head of the linked list of colliding PHIs. 744200581Srdivacky PHINode *Old = Pair.first->second; 745200581Srdivacky Pair.first->second = PN; 746200581Srdivacky CollisionMap[PN] = Old; 747200581Srdivacky break; 748200581Srdivacky } 749239462Sdim // Proceed to the next PHI in the list. 750200581Srdivacky OtherPN = I->second; 751200581Srdivacky } 752200581Srdivacky } 753200581Srdivacky 754200581Srdivacky return Changed; 755200581Srdivacky} 756218893Sdim 757218893Sdim/// enforceKnownAlignment - If the specified pointer points to an object that 758218893Sdim/// we control, modify the object's alignment to PrefAlign. This isn't 759218893Sdim/// often possible though. If alignment is important, a more reliable approach 760218893Sdim/// is to simply align all global variables and allocation instructions to 761218893Sdim/// their preferred alignment from the beginning. 762218893Sdim/// 763218893Sdimstatic unsigned enforceKnownAlignment(Value *V, unsigned Align, 764243830Sdim unsigned PrefAlign, const DataLayout *TD) { 765224145Sdim V = V->stripPointerCasts(); 766218893Sdim 767224145Sdim if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 768226633Sdim // If the preferred alignment is greater than the natural stack alignment 769226633Sdim // then don't round up. This avoids dynamic stack realignment. 770226633Sdim if (TD && TD->exceedsNaturalStackAlignment(PrefAlign)) 771226633Sdim return Align; 772218893Sdim // If there is a requested alignment and if this is an alloca, round up. 773218893Sdim if (AI->getAlignment() >= PrefAlign) 774218893Sdim return AI->getAlignment(); 775218893Sdim AI->setAlignment(PrefAlign); 776218893Sdim return PrefAlign; 777218893Sdim } 778218893Sdim 779218893Sdim if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 780218893Sdim // If there is a large requested alignment and we can, bump up the alignment 781218893Sdim // of the global. 782218893Sdim if (GV->isDeclaration()) return Align; 783234353Sdim // If the memory we set aside for the global may not be the memory used by 784234353Sdim // the final program then it is impossible for us to reliably enforce the 785234353Sdim // preferred alignment. 786234353Sdim if (GV->isWeakForLinker()) return Align; 787218893Sdim 788218893Sdim if (GV->getAlignment() >= PrefAlign) 789218893Sdim return GV->getAlignment(); 790218893Sdim // We can only increase the alignment of the global if it has no alignment 791218893Sdim // specified or if it is not assigned a section. If it is assigned a 792218893Sdim // section, the global could be densely packed with other objects in the 793218893Sdim // section, increasing the alignment could cause padding issues. 794218893Sdim if (!GV->hasSection() || GV->getAlignment() == 0) 795218893Sdim GV->setAlignment(PrefAlign); 796218893Sdim return GV->getAlignment(); 797218893Sdim } 798218893Sdim 799218893Sdim return Align; 800218893Sdim} 801218893Sdim 802218893Sdim/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 803218893Sdim/// we can determine, return it, otherwise return 0. If PrefAlign is specified, 804218893Sdim/// and it is more than the alignment of the ultimate object, see if we can 805218893Sdim/// increase the alignment of the ultimate object, making this check succeed. 806218893Sdimunsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 807243830Sdim const DataLayout *TD) { 808218893Sdim assert(V->getType()->isPointerTy() && 809218893Sdim "getOrEnforceKnownAlignment expects a pointer!"); 810218893Sdim unsigned BitWidth = TD ? TD->getPointerSizeInBits() : 64; 811218893Sdim APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 812234353Sdim ComputeMaskedBits(V, KnownZero, KnownOne, TD); 813218893Sdim unsigned TrailZ = KnownZero.countTrailingOnes(); 814218893Sdim 815218893Sdim // Avoid trouble with rediculously large TrailZ values, such as 816218893Sdim // those computed from a null pointer. 817218893Sdim TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 818218893Sdim 819218893Sdim unsigned Align = 1u << std::min(BitWidth - 1, TrailZ); 820218893Sdim 821218893Sdim // LLVM doesn't support alignments larger than this currently. 822218893Sdim Align = std::min(Align, +Value::MaximumAlignment); 823218893Sdim 824218893Sdim if (PrefAlign > Align) 825226633Sdim Align = enforceKnownAlignment(V, Align, PrefAlign, TD); 826218893Sdim 827218893Sdim // We don't need to make any adjustment. 828218893Sdim return Align; 829218893Sdim} 830218893Sdim 831221345Sdim///===---------------------------------------------------------------------===// 832221345Sdim/// Dbg Intrinsic utilities 833221345Sdim/// 834221345Sdim 835251662Sdim/// See if there is a dbg.value intrinsic for DIVar before I. 836251662Sdimstatic bool LdStHasDebugValue(DIVariable &DIVar, Instruction *I) { 837251662Sdim // Since we can't guarantee that the original dbg.declare instrinsic 838251662Sdim // is removed by LowerDbgDeclare(), we need to make sure that we are 839251662Sdim // not inserting the same dbg.value intrinsic over and over. 840251662Sdim llvm::BasicBlock::InstListType::iterator PrevI(I); 841251662Sdim if (PrevI != I->getParent()->getInstList().begin()) { 842251662Sdim --PrevI; 843251662Sdim if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI)) 844251662Sdim if (DVI->getValue() == I->getOperand(0) && 845251662Sdim DVI->getOffset() == 0 && 846251662Sdim DVI->getVariable() == DIVar) 847251662Sdim return true; 848251662Sdim } 849251662Sdim return false; 850251662Sdim} 851251662Sdim 852251662Sdim/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 853221345Sdim/// that has an associated llvm.dbg.decl intrinsic. 854221345Sdimbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 855221345Sdim StoreInst *SI, DIBuilder &Builder) { 856221345Sdim DIVariable DIVar(DDI->getVariable()); 857221345Sdim if (!DIVar.Verify()) 858221345Sdim return false; 859221345Sdim 860251662Sdim if (LdStHasDebugValue(DIVar, SI)) 861251662Sdim return true; 862251662Sdim 863223017Sdim Instruction *DbgVal = NULL; 864223017Sdim // If an argument is zero extended then use argument directly. The ZExt 865223017Sdim // may be zapped by an optimization pass in future. 866223017Sdim Argument *ExtendedArg = NULL; 867223017Sdim if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0))) 868223017Sdim ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0)); 869223017Sdim if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0))) 870223017Sdim ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0)); 871223017Sdim if (ExtendedArg) 872223017Sdim DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, SI); 873223017Sdim else 874223017Sdim DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, SI); 875223017Sdim 876221345Sdim // Propagate any debug metadata from the store onto the dbg.value. 877221345Sdim DebugLoc SIDL = SI->getDebugLoc(); 878221345Sdim if (!SIDL.isUnknown()) 879221345Sdim DbgVal->setDebugLoc(SIDL); 880221345Sdim // Otherwise propagate debug metadata from dbg.declare. 881221345Sdim else 882221345Sdim DbgVal->setDebugLoc(DDI->getDebugLoc()); 883221345Sdim return true; 884221345Sdim} 885221345Sdim 886251662Sdim/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 887221345Sdim/// that has an associated llvm.dbg.decl intrinsic. 888221345Sdimbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 889221345Sdim LoadInst *LI, DIBuilder &Builder) { 890221345Sdim DIVariable DIVar(DDI->getVariable()); 891221345Sdim if (!DIVar.Verify()) 892221345Sdim return false; 893221345Sdim 894251662Sdim if (LdStHasDebugValue(DIVar, LI)) 895251662Sdim return true; 896251662Sdim 897221345Sdim Instruction *DbgVal = 898221345Sdim Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, 899221345Sdim DIVar, LI); 900221345Sdim 901221345Sdim // Propagate any debug metadata from the store onto the dbg.value. 902221345Sdim DebugLoc LIDL = LI->getDebugLoc(); 903221345Sdim if (!LIDL.isUnknown()) 904221345Sdim DbgVal->setDebugLoc(LIDL); 905221345Sdim // Otherwise propagate debug metadata from dbg.declare. 906221345Sdim else 907221345Sdim DbgVal->setDebugLoc(DDI->getDebugLoc()); 908221345Sdim return true; 909221345Sdim} 910221345Sdim 911221345Sdim/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 912221345Sdim/// of llvm.dbg.value intrinsics. 913221345Sdimbool llvm::LowerDbgDeclare(Function &F) { 914221345Sdim DIBuilder DIB(*F.getParent()); 915221345Sdim SmallVector<DbgDeclareInst *, 4> Dbgs; 916221345Sdim for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 917221345Sdim for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) { 918221345Sdim if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(BI)) 919221345Sdim Dbgs.push_back(DDI); 920221345Sdim } 921221345Sdim if (Dbgs.empty()) 922221345Sdim return false; 923221345Sdim 924221345Sdim for (SmallVector<DbgDeclareInst *, 4>::iterator I = Dbgs.begin(), 925221345Sdim E = Dbgs.end(); I != E; ++I) { 926221345Sdim DbgDeclareInst *DDI = *I; 927221345Sdim if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress())) { 928251662Sdim // We only remove the dbg.declare intrinsic if all uses are 929251662Sdim // converted to dbg.value intrinsics. 930221345Sdim bool RemoveDDI = true; 931221345Sdim for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 932221345Sdim UI != E; ++UI) 933221345Sdim if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 934221345Sdim ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 935221345Sdim else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) 936221345Sdim ConvertDebugDeclareToDebugValue(DDI, LI, DIB); 937221345Sdim else 938221345Sdim RemoveDDI = false; 939221345Sdim if (RemoveDDI) 940221345Sdim DDI->eraseFromParent(); 941221345Sdim } 942221345Sdim } 943221345Sdim return true; 944221345Sdim} 945223017Sdim 946223017Sdim/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the 947223017Sdim/// alloca 'V', if any. 948223017SdimDbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) { 949223017Sdim if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), V)) 950223017Sdim for (Value::use_iterator UI = DebugNode->use_begin(), 951223017Sdim E = DebugNode->use_end(); UI != E; ++UI) 952223017Sdim if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(*UI)) 953223017Sdim return DDI; 954223017Sdim 955223017Sdim return 0; 956223017Sdim} 957249423Sdim 958249423Sdimbool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 959249423Sdim DIBuilder &Builder) { 960249423Sdim DbgDeclareInst *DDI = FindAllocaDbgDeclare(AI); 961249423Sdim if (!DDI) 962249423Sdim return false; 963249423Sdim DIVariable DIVar(DDI->getVariable()); 964249423Sdim if (!DIVar.Verify()) 965249423Sdim return false; 966249423Sdim 967249423Sdim // Create a copy of the original DIDescriptor for user variable, appending 968249423Sdim // "deref" operation to a list of address elements, as new llvm.dbg.declare 969249423Sdim // will take a value storing address of the memory for variable, not 970249423Sdim // alloca itself. 971249423Sdim Type *Int64Ty = Type::getInt64Ty(AI->getContext()); 972249423Sdim SmallVector<Value*, 4> NewDIVarAddress; 973249423Sdim if (DIVar.hasComplexAddress()) { 974249423Sdim for (unsigned i = 0, n = DIVar.getNumAddrElements(); i < n; ++i) { 975249423Sdim NewDIVarAddress.push_back( 976249423Sdim ConstantInt::get(Int64Ty, DIVar.getAddrElement(i))); 977249423Sdim } 978249423Sdim } 979249423Sdim NewDIVarAddress.push_back(ConstantInt::get(Int64Ty, DIBuilder::OpDeref)); 980249423Sdim DIVariable NewDIVar = Builder.createComplexVariable( 981249423Sdim DIVar.getTag(), DIVar.getContext(), DIVar.getName(), 982249423Sdim DIVar.getFile(), DIVar.getLineNumber(), DIVar.getType(), 983249423Sdim NewDIVarAddress, DIVar.getArgNumber()); 984249423Sdim 985249423Sdim // Insert llvm.dbg.declare in the same basic block as the original alloca, 986249423Sdim // and remove old llvm.dbg.declare. 987249423Sdim BasicBlock *BB = AI->getParent(); 988249423Sdim Builder.insertDeclare(NewAllocaAddress, NewDIVar, BB); 989249423Sdim DDI->eraseFromParent(); 990249423Sdim return true; 991249423Sdim} 992249423Sdim 993249423Sdimbool llvm::removeUnreachableBlocks(Function &F) { 994249423Sdim SmallPtrSet<BasicBlock*, 16> Reachable; 995249423Sdim SmallVector<BasicBlock*, 128> Worklist; 996249423Sdim Worklist.push_back(&F.getEntryBlock()); 997249423Sdim Reachable.insert(&F.getEntryBlock()); 998249423Sdim do { 999249423Sdim BasicBlock *BB = Worklist.pop_back_val(); 1000249423Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 1001249423Sdim if (Reachable.insert(*SI)) 1002249423Sdim Worklist.push_back(*SI); 1003249423Sdim } while (!Worklist.empty()); 1004249423Sdim 1005249423Sdim if (Reachable.size() == F.size()) 1006249423Sdim return false; 1007249423Sdim 1008249423Sdim assert(Reachable.size() < F.size()); 1009249423Sdim for (Function::iterator I = llvm::next(F.begin()), E = F.end(); I != E; ++I) { 1010249423Sdim if (Reachable.count(I)) 1011249423Sdim continue; 1012249423Sdim 1013249423Sdim for (succ_iterator SI = succ_begin(I), SE = succ_end(I); SI != SE; ++SI) 1014249423Sdim if (Reachable.count(*SI)) 1015249423Sdim (*SI)->removePredecessor(I); 1016249423Sdim I->dropAllReferences(); 1017249423Sdim } 1018249423Sdim 1019249423Sdim for (Function::iterator I = llvm::next(F.begin()), E=F.end(); I != E;) 1020249423Sdim if (!Reachable.count(I)) 1021249423Sdim I = F.getBasicBlockList().erase(I); 1022249423Sdim else 1023249423Sdim ++I; 1024249423Sdim 1025249423Sdim return true; 1026249423Sdim} 1027