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" 19263508Sdim#include "llvm/ADT/Statistic.h" 20218893Sdim#include "llvm/Analysis/Dominators.h" 21199481Srdivacky#include "llvm/Analysis/InstructionSimplify.h" 22234353Sdim#include "llvm/Analysis/MemoryBuiltins.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 46263508SdimSTATISTIC(NumRemoved, "Number of unreachable basic blocks removed"); 47263508Sdim 48193323Sed//===----------------------------------------------------------------------===// 49193323Sed// Local constant propagation. 50193323Sed// 51193323Sed 52223017Sdim/// ConstantFoldTerminator - If a terminator instruction is predicated on a 53223017Sdim/// constant value, convert it into an unconditional branch to the constant 54223017Sdim/// destination. This is a nontrivial operation because the successors of this 55223017Sdim/// basic block must have their PHI nodes updated. 56223017Sdim/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 57223017Sdim/// conditions and indirectbr addresses this might make dead if 58223017Sdim/// DeleteDeadConditions is true. 59243830Sdimbool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, 60243830Sdim const TargetLibraryInfo *TLI) { 61193323Sed TerminatorInst *T = BB->getTerminator(); 62223017Sdim IRBuilder<> Builder(T); 63193323Sed 64193323Sed // Branch - See if we are conditional jumping on constant 65193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 66193323Sed if (BI->isUnconditional()) return false; // Can't optimize uncond branch 67193323Sed BasicBlock *Dest1 = BI->getSuccessor(0); 68193323Sed BasicBlock *Dest2 = BI->getSuccessor(1); 69193323Sed 70193323Sed if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 71193323Sed // Are we branching on constant? 72193323Sed // YES. Change to unconditional branch... 73193323Sed BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 74193323Sed BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 75193323Sed 76193323Sed //cerr << "Function: " << T->getParent()->getParent() 77193323Sed // << "\nRemoving branch from " << T->getParent() 78193323Sed // << "\n\nTo: " << OldDest << endl; 79193323Sed 80193323Sed // Let the basic block know that we are letting go of it. Based on this, 81193323Sed // it will adjust it's PHI nodes. 82221345Sdim OldDest->removePredecessor(BB); 83193323Sed 84218893Sdim // Replace the conditional branch with an unconditional one. 85223017Sdim Builder.CreateBr(Destination); 86218893Sdim BI->eraseFromParent(); 87193323Sed return true; 88198892Srdivacky } 89263508Sdim 90198892Srdivacky if (Dest2 == Dest1) { // Conditional branch to same location? 91193323Sed // This branch matches something like this: 92193323Sed // br bool %cond, label %Dest, label %Dest 93193323Sed // and changes it into: br label %Dest 94193323Sed 95193323Sed // Let the basic block know that we are letting go of one copy of it. 96193323Sed assert(BI->getParent() && "Terminator not inserted in block!"); 97193323Sed Dest1->removePredecessor(BI->getParent()); 98193323Sed 99218893Sdim // Replace the conditional branch with an unconditional one. 100223017Sdim Builder.CreateBr(Dest1); 101223017Sdim Value *Cond = BI->getCondition(); 102218893Sdim BI->eraseFromParent(); 103223017Sdim if (DeleteDeadConditions) 104243830Sdim RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 105193323Sed return true; 106193323Sed } 107198892Srdivacky return false; 108198892Srdivacky } 109263508Sdim 110198892Srdivacky if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 111193323Sed // If we are switching on a constant, we can convert the switch into a 112193323Sed // single branch instruction! 113193323Sed ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 114234353Sdim BasicBlock *TheOnlyDest = SI->getDefaultDest(); 115193323Sed BasicBlock *DefaultDest = TheOnlyDest; 116193323Sed 117198892Srdivacky // Figure out which case it goes to. 118234353Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 119234353Sdim i != e; ++i) { 120193323Sed // Found case matching a constant operand? 121234353Sdim if (i.getCaseValue() == CI) { 122234353Sdim TheOnlyDest = i.getCaseSuccessor(); 123193323Sed break; 124193323Sed } 125193323Sed 126193323Sed // Check to see if this branch is going to the same place as the default 127193323Sed // dest. If so, eliminate it as an explicit compare. 128234353Sdim if (i.getCaseSuccessor() == DefaultDest) { 129243830Sdim MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); 130243830Sdim // MD should have 2 + NumCases operands. 131243830Sdim if (MD && MD->getNumOperands() == 2 + SI->getNumCases()) { 132243830Sdim // Collect branch weights into a vector. 133243830Sdim SmallVector<uint32_t, 8> Weights; 134243830Sdim for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 135243830Sdim ++MD_i) { 136243830Sdim ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(MD_i)); 137243830Sdim assert(CI); 138243830Sdim Weights.push_back(CI->getValue().getZExtValue()); 139243830Sdim } 140243830Sdim // Merge weight of this case to the default weight. 141243830Sdim unsigned idx = i.getCaseIndex(); 142243830Sdim Weights[0] += Weights[idx+1]; 143243830Sdim // Remove weight for this case. 144243830Sdim std::swap(Weights[idx+1], Weights.back()); 145243830Sdim Weights.pop_back(); 146243830Sdim SI->setMetadata(LLVMContext::MD_prof, 147243830Sdim MDBuilder(BB->getContext()). 148243830Sdim createBranchWeights(Weights)); 149243830Sdim } 150198892Srdivacky // Remove this entry. 151193323Sed DefaultDest->removePredecessor(SI->getParent()); 152193323Sed SI->removeCase(i); 153234353Sdim --i; --e; 154193323Sed continue; 155193323Sed } 156193323Sed 157193323Sed // Otherwise, check to see if the switch only branches to one destination. 158193323Sed // We do this by reseting "TheOnlyDest" to null when we find two non-equal 159193323Sed // destinations. 160234353Sdim if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = 0; 161193323Sed } 162193323Sed 163193323Sed if (CI && !TheOnlyDest) { 164193323Sed // Branching on a constant, but not any of the cases, go to the default 165193323Sed // successor. 166193323Sed TheOnlyDest = SI->getDefaultDest(); 167193323Sed } 168193323Sed 169193323Sed // If we found a single destination that we can fold the switch into, do so 170193323Sed // now. 171193323Sed if (TheOnlyDest) { 172198892Srdivacky // Insert the new branch. 173223017Sdim Builder.CreateBr(TheOnlyDest); 174193323Sed BasicBlock *BB = SI->getParent(); 175193323Sed 176193323Sed // Remove entries from PHI nodes which we no longer branch to... 177193323Sed for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 178193323Sed // Found case matching a constant operand? 179193323Sed BasicBlock *Succ = SI->getSuccessor(i); 180193323Sed if (Succ == TheOnlyDest) 181193323Sed TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 182193323Sed else 183193323Sed Succ->removePredecessor(BB); 184193323Sed } 185193323Sed 186198892Srdivacky // Delete the old switch. 187223017Sdim Value *Cond = SI->getCondition(); 188223017Sdim SI->eraseFromParent(); 189223017Sdim if (DeleteDeadConditions) 190243830Sdim RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 191193323Sed return true; 192198892Srdivacky } 193263508Sdim 194234353Sdim if (SI->getNumCases() == 1) { 195193323Sed // Otherwise, we can fold this switch into a conditional branch 196193323Sed // instruction if it has only one non-default destination. 197234353Sdim SwitchInst::CaseIt FirstCase = SI->case_begin(); 198263508Sdim Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), 199263508Sdim FirstCase.getCaseValue(), "cond"); 200223017Sdim 201263508Sdim // Insert the new branch. 202263508Sdim BranchInst *NewBr = Builder.CreateCondBr(Cond, 203263508Sdim FirstCase.getCaseSuccessor(), 204263508Sdim SI->getDefaultDest()); 205263508Sdim MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); 206263508Sdim if (MD && MD->getNumOperands() == 3) { 207263508Sdim ConstantInt *SICase = dyn_cast<ConstantInt>(MD->getOperand(2)); 208263508Sdim ConstantInt *SIDef = dyn_cast<ConstantInt>(MD->getOperand(1)); 209263508Sdim assert(SICase && SIDef); 210263508Sdim // The TrueWeight should be the weight for the single case of SI. 211263508Sdim NewBr->setMetadata(LLVMContext::MD_prof, 212263508Sdim MDBuilder(BB->getContext()). 213263508Sdim createBranchWeights(SICase->getValue().getZExtValue(), 214263508Sdim SIDef->getValue().getZExtValue())); 215263508Sdim } 216193323Sed 217263508Sdim // Delete the old switch. 218263508Sdim SI->eraseFromParent(); 219263508Sdim return true; 220193323Sed } 221198892Srdivacky return false; 222193323Sed } 223198892Srdivacky 224198892Srdivacky if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { 225198892Srdivacky // indirectbr blockaddress(@F, @BB) -> br label @BB 226198892Srdivacky if (BlockAddress *BA = 227198892Srdivacky dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 228198892Srdivacky BasicBlock *TheOnlyDest = BA->getBasicBlock(); 229198892Srdivacky // Insert the new branch. 230223017Sdim Builder.CreateBr(TheOnlyDest); 231263508Sdim 232198892Srdivacky for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 233198892Srdivacky if (IBI->getDestination(i) == TheOnlyDest) 234198892Srdivacky TheOnlyDest = 0; 235198892Srdivacky else 236198892Srdivacky IBI->getDestination(i)->removePredecessor(IBI->getParent()); 237198892Srdivacky } 238223017Sdim Value *Address = IBI->getAddress(); 239198892Srdivacky IBI->eraseFromParent(); 240223017Sdim if (DeleteDeadConditions) 241243830Sdim RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); 242263508Sdim 243198892Srdivacky // If we didn't find our destination in the IBI successor list, then we 244198892Srdivacky // have undefined behavior. Replace the unconditional branch with an 245198892Srdivacky // 'unreachable' instruction. 246198892Srdivacky if (TheOnlyDest) { 247198892Srdivacky BB->getTerminator()->eraseFromParent(); 248198892Srdivacky new UnreachableInst(BB->getContext(), BB); 249198892Srdivacky } 250263508Sdim 251198892Srdivacky return true; 252198892Srdivacky } 253198892Srdivacky } 254263508Sdim 255193323Sed return false; 256193323Sed} 257193323Sed 258193323Sed 259193323Sed//===----------------------------------------------------------------------===// 260199481Srdivacky// Local dead code elimination. 261193323Sed// 262193323Sed 263193323Sed/// isInstructionTriviallyDead - Return true if the result produced by the 264193323Sed/// instruction is not used, and the instruction has no side effects. 265193323Sed/// 266243830Sdimbool llvm::isInstructionTriviallyDead(Instruction *I, 267243830Sdim const TargetLibraryInfo *TLI) { 268193323Sed if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 269193323Sed 270226633Sdim // We don't want the landingpad instruction removed by anything this general. 271226633Sdim if (isa<LandingPadInst>(I)) 272226633Sdim return false; 273226633Sdim 274221345Sdim // We don't want debug info removed by anything this general, unless 275221345Sdim // debug info is empty. 276221345Sdim if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { 277226633Sdim if (DDI->getAddress()) 278221345Sdim return false; 279221345Sdim return true; 280226633Sdim } 281221345Sdim if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { 282221345Sdim if (DVI->getValue()) 283221345Sdim return false; 284221345Sdim return true; 285221345Sdim } 286193323Sed 287193323Sed if (!I->mayHaveSideEffects()) return true; 288193323Sed 289193323Sed // Special case intrinsics that "may have side effects" but can be deleted 290193323Sed // when dead. 291226633Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 292193323Sed // Safe to delete llvm.stacksave if dead. 293193323Sed if (II->getIntrinsicID() == Intrinsic::stacksave) 294193323Sed return true; 295226633Sdim 296226633Sdim // Lifetime intrinsics are dead when their right-hand is undef. 297226633Sdim if (II->getIntrinsicID() == Intrinsic::lifetime_start || 298226633Sdim II->getIntrinsicID() == Intrinsic::lifetime_end) 299226633Sdim return isa<UndefValue>(II->getArgOperand(1)); 300226633Sdim } 301234353Sdim 302243830Sdim if (isAllocLikeFn(I, TLI)) return true; 303234353Sdim 304243830Sdim if (CallInst *CI = isFreeCall(I, TLI)) 305234353Sdim if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0))) 306234353Sdim return C->isNullValue() || isa<UndefValue>(C); 307234353Sdim 308193323Sed return false; 309193323Sed} 310193323Sed 311193323Sed/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 312193323Sed/// trivially dead instruction, delete it. If that makes any of its operands 313202375Srdivacky/// trivially dead, delete them too, recursively. Return true if any 314202375Srdivacky/// instructions were deleted. 315243830Sdimbool 316243830Sdimllvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, 317243830Sdim const TargetLibraryInfo *TLI) { 318193323Sed Instruction *I = dyn_cast<Instruction>(V); 319243830Sdim if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI)) 320202375Srdivacky return false; 321263508Sdim 322193323Sed SmallVector<Instruction*, 16> DeadInsts; 323193323Sed DeadInsts.push_back(I); 324263508Sdim 325202375Srdivacky do { 326193323Sed I = DeadInsts.pop_back_val(); 327193323Sed 328193323Sed // Null out all of the instruction's operands to see if any operand becomes 329193323Sed // dead as we go. 330193323Sed for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 331193323Sed Value *OpV = I->getOperand(i); 332193323Sed I->setOperand(i, 0); 333263508Sdim 334193323Sed if (!OpV->use_empty()) continue; 335263508Sdim 336193323Sed // If the operand is an instruction that became dead as we nulled out the 337193323Sed // operand, and if it is 'trivially' dead, delete it in a future loop 338193323Sed // iteration. 339193323Sed if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 340243830Sdim if (isInstructionTriviallyDead(OpI, TLI)) 341193323Sed DeadInsts.push_back(OpI); 342193323Sed } 343263508Sdim 344193323Sed I->eraseFromParent(); 345202375Srdivacky } while (!DeadInsts.empty()); 346202375Srdivacky 347202375Srdivacky return true; 348193323Sed} 349193323Sed 350218893Sdim/// areAllUsesEqual - Check whether the uses of a value are all the same. 351218893Sdim/// This is similar to Instruction::hasOneUse() except this will also return 352219077Sdim/// true when there are no uses or multiple uses that all refer to the same 353219077Sdim/// value. 354218893Sdimstatic bool areAllUsesEqual(Instruction *I) { 355218893Sdim Value::use_iterator UI = I->use_begin(); 356218893Sdim Value::use_iterator UE = I->use_end(); 357218893Sdim if (UI == UE) 358219077Sdim return true; 359218893Sdim 360218893Sdim User *TheUse = *UI; 361218893Sdim for (++UI; UI != UE; ++UI) { 362218893Sdim if (*UI != TheUse) 363218893Sdim return false; 364218893Sdim } 365218893Sdim return true; 366218893Sdim} 367218893Sdim 368193323Sed/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 369193323Sed/// dead PHI node, due to being a def-use chain of single-use nodes that 370193323Sed/// either forms a cycle or is terminated by a trivially dead instruction, 371193323Sed/// delete it. If that makes any of its operands trivially dead, delete them 372219077Sdim/// too, recursively. Return true if a change was made. 373243830Sdimbool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, 374243830Sdim const TargetLibraryInfo *TLI) { 375219077Sdim SmallPtrSet<Instruction*, 4> Visited; 376219077Sdim for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); 377219077Sdim I = cast<Instruction>(*I->use_begin())) { 378219077Sdim if (I->use_empty()) 379243830Sdim return RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 380193323Sed 381219077Sdim // If we find an instruction more than once, we're on a cycle that 382193323Sed // won't prove fruitful. 383219077Sdim if (!Visited.insert(I)) { 384219077Sdim // Break the cycle and delete the instruction and its operands. 385219077Sdim I->replaceAllUsesWith(UndefValue::get(I->getType())); 386243830Sdim (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 387219077Sdim return true; 388219077Sdim } 389219077Sdim } 390219077Sdim return false; 391193323Sed} 392193323Sed 393202375Srdivacky/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 394202375Srdivacky/// simplify any instructions in it and recursively delete dead instructions. 395202375Srdivacky/// 396202375Srdivacky/// This returns true if it changed the code, note that it can delete 397202375Srdivacky/// instructions in other blocks as well in this block. 398243830Sdimbool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD, 399243830Sdim const TargetLibraryInfo *TLI) { 400202375Srdivacky bool MadeChange = false; 401234353Sdim 402234353Sdim#ifndef NDEBUG 403234353Sdim // In debug builds, ensure that the terminator of the block is never replaced 404234353Sdim // or deleted by these simplifications. The idea of simplification is that it 405234353Sdim // cannot introduce new instructions, and there is no way to replace the 406234353Sdim // terminator of a block without introducing a new instruction. 407234353Sdim AssertingVH<Instruction> TerminatorVH(--BB->end()); 408234353Sdim#endif 409234353Sdim 410234353Sdim for (BasicBlock::iterator BI = BB->begin(), E = --BB->end(); BI != E; ) { 411234353Sdim assert(!BI->isTerminator()); 412202375Srdivacky Instruction *Inst = BI++; 413234353Sdim 414234353Sdim WeakVH BIHandle(BI); 415263508Sdim if (recursivelySimplifyInstruction(Inst, TD, TLI)) { 416202375Srdivacky MadeChange = true; 417210299Sed if (BIHandle != BI) 418202375Srdivacky BI = BB->begin(); 419202375Srdivacky continue; 420202375Srdivacky } 421221345Sdim 422243830Sdim MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI); 423221345Sdim if (BIHandle != BI) 424221345Sdim BI = BB->begin(); 425202375Srdivacky } 426202375Srdivacky return MadeChange; 427202375Srdivacky} 428202375Srdivacky 429193323Sed//===----------------------------------------------------------------------===// 430199481Srdivacky// Control Flow Graph Restructuring. 431193323Sed// 432193323Sed 433199481Srdivacky 434199481Srdivacky/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 435199481Srdivacky/// method is called when we're about to delete Pred as a predecessor of BB. If 436199481Srdivacky/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 437199481Srdivacky/// 438199481Srdivacky/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 439199481Srdivacky/// nodes that collapse into identity values. For example, if we have: 440199481Srdivacky/// x = phi(1, 0, 0, 0) 441199481Srdivacky/// y = and x, z 442199481Srdivacky/// 443199481Srdivacky/// .. and delete the predecessor corresponding to the '1', this will attempt to 444199481Srdivacky/// recursively fold the and to 0. 445199481Srdivackyvoid llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 446243830Sdim DataLayout *TD) { 447199481Srdivacky // This only adjusts blocks with PHI nodes. 448199481Srdivacky if (!isa<PHINode>(BB->begin())) 449199481Srdivacky return; 450263508Sdim 451199481Srdivacky // Remove the entries for Pred from the PHI nodes in BB, but do not simplify 452199481Srdivacky // them down. This will leave us with single entry phi nodes and other phis 453199481Srdivacky // that can be removed. 454199481Srdivacky BB->removePredecessor(Pred, true); 455263508Sdim 456199481Srdivacky WeakVH PhiIt = &BB->front(); 457199481Srdivacky while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) { 458199481Srdivacky PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt)); 459234353Sdim Value *OldPhiIt = PhiIt; 460218893Sdim 461234353Sdim if (!recursivelySimplifyInstruction(PN, TD)) 462234353Sdim continue; 463218893Sdim 464199481Srdivacky // If recursive simplification ended up deleting the next PHI node we would 465199481Srdivacky // iterate to, then our iterator is invalid, restart scanning from the top 466199481Srdivacky // of the block. 467210299Sed if (PhiIt != OldPhiIt) PhiIt = &BB->front(); 468199481Srdivacky } 469199481Srdivacky} 470199481Srdivacky 471199481Srdivacky 472193323Sed/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 473193323Sed/// predecessor is known to have one successor (DestBB!). Eliminate the edge 474193323Sed/// between them, moving the instructions in the predecessor into DestBB and 475193323Sed/// deleting the predecessor block. 476193323Sed/// 477198090Srdivackyvoid llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { 478193323Sed // If BB has single-entry PHI nodes, fold them. 479193323Sed while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 480193323Sed Value *NewVal = PN->getIncomingValue(0); 481193323Sed // Replace self referencing PHI with undef, it must be dead. 482193323Sed if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 483193323Sed PN->replaceAllUsesWith(NewVal); 484193323Sed PN->eraseFromParent(); 485193323Sed } 486263508Sdim 487193323Sed BasicBlock *PredBB = DestBB->getSinglePredecessor(); 488193323Sed assert(PredBB && "Block doesn't have a single predecessor!"); 489263508Sdim 490203954Srdivacky // Zap anything that took the address of DestBB. Not doing this will give the 491203954Srdivacky // address an invalid value. 492203954Srdivacky if (DestBB->hasAddressTaken()) { 493203954Srdivacky BlockAddress *BA = BlockAddress::get(DestBB); 494203954Srdivacky Constant *Replacement = 495203954Srdivacky ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1); 496203954Srdivacky BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 497203954Srdivacky BA->getType())); 498203954Srdivacky BA->destroyConstant(); 499203954Srdivacky } 500263508Sdim 501193323Sed // Anything that branched to PredBB now branches to DestBB. 502193323Sed PredBB->replaceAllUsesWith(DestBB); 503263508Sdim 504224145Sdim // Splice all the instructions from PredBB to DestBB. 505224145Sdim PredBB->getTerminator()->eraseFromParent(); 506224145Sdim DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 507224145Sdim 508198090Srdivacky if (P) { 509218893Sdim DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); 510218893Sdim if (DT) { 511218893Sdim BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); 512218893Sdim DT->changeImmediateDominator(DestBB, PredBBIDom); 513218893Sdim DT->eraseNode(PredBB); 514218893Sdim } 515198090Srdivacky } 516193323Sed // Nuke BB. 517193323Sed PredBB->eraseFromParent(); 518193323Sed} 519193323Sed 520263508Sdim/// CanMergeValues - Return true if we can choose one of these values to use 521263508Sdim/// in place of the other. Note that we will always choose the non-undef 522263508Sdim/// value to keep. 523263508Sdimstatic bool CanMergeValues(Value *First, Value *Second) { 524263508Sdim return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second); 525263508Sdim} 526263508Sdim 527199481Srdivacky/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 528263508Sdim/// almost-empty BB ending in an unconditional branch to Succ, into Succ. 529199481Srdivacky/// 530199481Srdivacky/// Assumption: Succ is the single successor for BB. 531199481Srdivacky/// 532199481Srdivackystatic bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 533199481Srdivacky assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 534199481Srdivacky 535263508Sdim DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " 536199481Srdivacky << Succ->getName() << "\n"); 537199481Srdivacky // Shortcut, if there is only a single predecessor it must be BB and merging 538199481Srdivacky // is always safe 539199481Srdivacky if (Succ->getSinglePredecessor()) return true; 540199481Srdivacky 541199481Srdivacky // Make a list of the predecessors of BB 542234353Sdim SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 543199481Srdivacky 544199481Srdivacky // Look at all the phi nodes in Succ, to see if they present a conflict when 545199481Srdivacky // merging these blocks 546199481Srdivacky for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 547199481Srdivacky PHINode *PN = cast<PHINode>(I); 548199481Srdivacky 549199481Srdivacky // If the incoming value from BB is again a PHINode in 550199481Srdivacky // BB which has the same incoming value for *PI as PN does, we can 551199481Srdivacky // merge the phi nodes and then the blocks can still be merged 552199481Srdivacky PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 553199481Srdivacky if (BBPN && BBPN->getParent() == BB) { 554234353Sdim for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 555234353Sdim BasicBlock *IBB = PN->getIncomingBlock(PI); 556234353Sdim if (BBPreds.count(IBB) && 557263508Sdim !CanMergeValues(BBPN->getIncomingValueForBlock(IBB), 558263508Sdim PN->getIncomingValue(PI))) { 559263508Sdim DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 560263508Sdim << 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); 573263508Sdim if (BBPreds.count(IBB) && 574263508Sdim !CanMergeValues(Val, PN->getIncomingValue(PI))) { 575263508Sdim DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 576199481Srdivacky << Succ->getName() << " is conflicting with regard to common " 577234353Sdim << "predecessor " << IBB->getName() << "\n"); 578199481Srdivacky return false; 579199481Srdivacky } 580199481Srdivacky } 581199481Srdivacky } 582199481Srdivacky } 583199481Srdivacky 584199481Srdivacky return true; 585199481Srdivacky} 586199481Srdivacky 587263508Sdimtypedef SmallVector<BasicBlock *, 16> PredBlockVector; 588263508Sdimtypedef DenseMap<BasicBlock *, Value *> IncomingValueMap; 589263508Sdim 590263508Sdim/// \brief Determines the value to use as the phi node input for a block. 591263508Sdim/// 592263508Sdim/// Select between \p OldVal any value that we know flows from \p BB 593263508Sdim/// to a particular phi on the basis of which one (if either) is not 594263508Sdim/// undef. Update IncomingValues based on the selected value. 595263508Sdim/// 596263508Sdim/// \param OldVal The value we are considering selecting. 597263508Sdim/// \param BB The block that the value flows in from. 598263508Sdim/// \param IncomingValues A map from block-to-value for other phi inputs 599263508Sdim/// that we have examined. 600263508Sdim/// 601263508Sdim/// \returns the selected value. 602263508Sdimstatic Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, 603263508Sdim IncomingValueMap &IncomingValues) { 604263508Sdim if (!isa<UndefValue>(OldVal)) { 605263508Sdim assert((!IncomingValues.count(BB) || 606263508Sdim IncomingValues.find(BB)->second == OldVal) && 607263508Sdim "Expected OldVal to match incoming value from BB!"); 608263508Sdim 609263508Sdim IncomingValues.insert(std::make_pair(BB, OldVal)); 610263508Sdim return OldVal; 611263508Sdim } 612263508Sdim 613263508Sdim IncomingValueMap::const_iterator It = IncomingValues.find(BB); 614263508Sdim if (It != IncomingValues.end()) return It->second; 615263508Sdim 616263508Sdim return OldVal; 617263508Sdim} 618263508Sdim 619263508Sdim/// \brief Create a map from block to value for the operands of a 620263508Sdim/// given phi. 621263508Sdim/// 622263508Sdim/// Create a map from block to value for each non-undef value flowing 623263508Sdim/// into \p PN. 624263508Sdim/// 625263508Sdim/// \param PN The phi we are collecting the map for. 626263508Sdim/// \param IncomingValues [out] The map from block to value for this phi. 627263508Sdimstatic void gatherIncomingValuesToPhi(PHINode *PN, 628263508Sdim IncomingValueMap &IncomingValues) { 629263508Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 630263508Sdim BasicBlock *BB = PN->getIncomingBlock(i); 631263508Sdim Value *V = PN->getIncomingValue(i); 632263508Sdim 633263508Sdim if (!isa<UndefValue>(V)) 634263508Sdim IncomingValues.insert(std::make_pair(BB, V)); 635263508Sdim } 636263508Sdim} 637263508Sdim 638263508Sdim/// \brief Replace the incoming undef values to a phi with the values 639263508Sdim/// from a block-to-value map. 640263508Sdim/// 641263508Sdim/// \param PN The phi we are replacing the undefs in. 642263508Sdim/// \param IncomingValues A map from block to value. 643263508Sdimstatic void replaceUndefValuesInPhi(PHINode *PN, 644263508Sdim const IncomingValueMap &IncomingValues) { 645263508Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 646263508Sdim Value *V = PN->getIncomingValue(i); 647263508Sdim 648263508Sdim if (!isa<UndefValue>(V)) continue; 649263508Sdim 650263508Sdim BasicBlock *BB = PN->getIncomingBlock(i); 651263508Sdim IncomingValueMap::const_iterator It = IncomingValues.find(BB); 652263508Sdim if (It == IncomingValues.end()) continue; 653263508Sdim 654263508Sdim PN->setIncomingValue(i, It->second); 655263508Sdim } 656263508Sdim} 657263508Sdim 658263508Sdim/// \brief Replace a value flowing from a block to a phi with 659263508Sdim/// potentially multiple instances of that value flowing from the 660263508Sdim/// block's predecessors to the phi. 661263508Sdim/// 662263508Sdim/// \param BB The block with the value flowing into the phi. 663263508Sdim/// \param BBPreds The predecessors of BB. 664263508Sdim/// \param PN The phi that we are updating. 665263508Sdimstatic void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, 666263508Sdim const PredBlockVector &BBPreds, 667263508Sdim PHINode *PN) { 668263508Sdim Value *OldVal = PN->removeIncomingValue(BB, false); 669263508Sdim assert(OldVal && "No entry in PHI for Pred BB!"); 670263508Sdim 671263508Sdim IncomingValueMap IncomingValues; 672263508Sdim 673263508Sdim // We are merging two blocks - BB, and the block containing PN - and 674263508Sdim // as a result we need to redirect edges from the predecessors of BB 675263508Sdim // to go to the block containing PN, and update PN 676263508Sdim // accordingly. Since we allow merging blocks in the case where the 677263508Sdim // predecessor and successor blocks both share some predecessors, 678263508Sdim // and where some of those common predecessors might have undef 679263508Sdim // values flowing into PN, we want to rewrite those values to be 680263508Sdim // consistent with the non-undef values. 681263508Sdim 682263508Sdim gatherIncomingValuesToPhi(PN, IncomingValues); 683263508Sdim 684263508Sdim // If this incoming value is one of the PHI nodes in BB, the new entries 685263508Sdim // in the PHI node are the entries from the old PHI. 686263508Sdim if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 687263508Sdim PHINode *OldValPN = cast<PHINode>(OldVal); 688263508Sdim for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) { 689263508Sdim // Note that, since we are merging phi nodes and BB and Succ might 690263508Sdim // have common predecessors, we could end up with a phi node with 691263508Sdim // identical incoming branches. This will be cleaned up later (and 692263508Sdim // will trigger asserts if we try to clean it up now, without also 693263508Sdim // simplifying the corresponding conditional branch). 694263508Sdim BasicBlock *PredBB = OldValPN->getIncomingBlock(i); 695263508Sdim Value *PredVal = OldValPN->getIncomingValue(i); 696263508Sdim Value *Selected = selectIncomingValueForBlock(PredVal, PredBB, 697263508Sdim IncomingValues); 698263508Sdim 699263508Sdim // And add a new incoming value for this predecessor for the 700263508Sdim // newly retargeted branch. 701263508Sdim PN->addIncoming(Selected, PredBB); 702263508Sdim } 703263508Sdim } else { 704263508Sdim for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) { 705263508Sdim // Update existing incoming values in PN for this 706263508Sdim // predecessor of BB. 707263508Sdim BasicBlock *PredBB = BBPreds[i]; 708263508Sdim Value *Selected = selectIncomingValueForBlock(OldVal, PredBB, 709263508Sdim IncomingValues); 710263508Sdim 711263508Sdim // And add a new incoming value for this predecessor for the 712263508Sdim // newly retargeted branch. 713263508Sdim PN->addIncoming(Selected, PredBB); 714263508Sdim } 715263508Sdim } 716263508Sdim 717263508Sdim replaceUndefValuesInPhi(PN, IncomingValues); 718263508Sdim} 719263508Sdim 720199481Srdivacky/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 721199481Srdivacky/// unconditional branch, and contains no instructions other than PHI nodes, 722224145Sdim/// potential side-effect free intrinsics and the branch. If possible, 723224145Sdim/// eliminate BB by rewriting all the predecessors to branch to the successor 724224145Sdim/// block and return true. If we can't transform, return false. 725199481Srdivackybool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { 726212904Sdim assert(BB != &BB->getParent()->getEntryBlock() && 727212904Sdim "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); 728212904Sdim 729199481Srdivacky // We can't eliminate infinite loops. 730199481Srdivacky BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 731199481Srdivacky if (BB == Succ) return false; 732263508Sdim 733199481Srdivacky // Check to see if merging these blocks would cause conflicts for any of the 734199481Srdivacky // phi nodes in BB or Succ. If not, we can safely merge. 735199481Srdivacky if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 736199481Srdivacky 737199481Srdivacky // Check for cases where Succ has multiple predecessors and a PHI node in BB 738199481Srdivacky // has uses which will not disappear when the PHI nodes are merged. It is 739199481Srdivacky // possible to handle such cases, but difficult: it requires checking whether 740199481Srdivacky // BB dominates Succ, which is non-trivial to calculate in the case where 741199481Srdivacky // Succ has multiple predecessors. Also, it requires checking whether 742249423Sdim // constructing the necessary self-referential PHI node doesn't introduce any 743199481Srdivacky // conflicts; this isn't too difficult, but the previous code for doing this 744199481Srdivacky // was incorrect. 745199481Srdivacky // 746199481Srdivacky // Note that if this check finds a live use, BB dominates Succ, so BB is 747199481Srdivacky // something like a loop pre-header (or rarely, a part of an irreducible CFG); 748199481Srdivacky // folding the branch isn't profitable in that case anyway. 749199481Srdivacky if (!Succ->getSinglePredecessor()) { 750199481Srdivacky BasicBlock::iterator BBI = BB->begin(); 751199481Srdivacky while (isa<PHINode>(*BBI)) { 752199481Srdivacky for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 753199481Srdivacky UI != E; ++UI) { 754199481Srdivacky if (PHINode* PN = dyn_cast<PHINode>(*UI)) { 755199481Srdivacky if (PN->getIncomingBlock(UI) != BB) 756199481Srdivacky return false; 757199481Srdivacky } else { 758199481Srdivacky return false; 759199481Srdivacky } 760199481Srdivacky } 761199481Srdivacky ++BBI; 762199481Srdivacky } 763199481Srdivacky } 764199481Srdivacky 765202375Srdivacky DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); 766263508Sdim 767199481Srdivacky if (isa<PHINode>(Succ->begin())) { 768199481Srdivacky // If there is more than one pred of succ, and there are PHI nodes in 769199481Srdivacky // the successor, then we need to add incoming edges for the PHI nodes 770199481Srdivacky // 771263508Sdim const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); 772263508Sdim 773199481Srdivacky // Loop over all of the PHI nodes in the successor of BB. 774199481Srdivacky for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 775199481Srdivacky PHINode *PN = cast<PHINode>(I); 776263508Sdim 777263508Sdim redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); 778199481Srdivacky } 779199481Srdivacky } 780263508Sdim 781224145Sdim if (Succ->getSinglePredecessor()) { 782224145Sdim // BB is the only predecessor of Succ, so Succ will end up with exactly 783224145Sdim // the same predecessors BB had. 784224145Sdim 785224145Sdim // Copy over any phi, debug or lifetime instruction. 786224145Sdim BB->getTerminator()->eraseFromParent(); 787224145Sdim Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList()); 788224145Sdim } else { 789224145Sdim while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 790199481Srdivacky // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 791199481Srdivacky assert(PN->use_empty() && "There shouldn't be any uses here!"); 792199481Srdivacky PN->eraseFromParent(); 793199481Srdivacky } 794199481Srdivacky } 795263508Sdim 796199481Srdivacky // Everything that jumped to BB now goes to Succ. 797199481Srdivacky BB->replaceAllUsesWith(Succ); 798199481Srdivacky if (!Succ->hasName()) Succ->takeName(BB); 799199481Srdivacky BB->eraseFromParent(); // Delete the old basic block. 800199481Srdivacky return true; 801199481Srdivacky} 802199481Srdivacky 803200581Srdivacky/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 804200581Srdivacky/// nodes in this block. This doesn't try to be clever about PHI nodes 805200581Srdivacky/// which differ only in the order of the incoming values, but instcombine 806200581Srdivacky/// orders them so it usually won't matter. 807200581Srdivacky/// 808200581Srdivackybool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 809200581Srdivacky bool Changed = false; 810200581Srdivacky 811200581Srdivacky // This implementation doesn't currently consider undef operands 812224145Sdim // specially. Theoretically, two phis which are identical except for 813200581Srdivacky // one having an undef where the other doesn't could be collapsed. 814200581Srdivacky 815200581Srdivacky // Map from PHI hash values to PHI nodes. If multiple PHIs have 816200581Srdivacky // the same hash value, the element is the first PHI in the 817200581Srdivacky // linked list in CollisionMap. 818200581Srdivacky DenseMap<uintptr_t, PHINode *> HashMap; 819200581Srdivacky 820200581Srdivacky // Maintain linked lists of PHI nodes with common hash values. 821200581Srdivacky DenseMap<PHINode *, PHINode *> CollisionMap; 822200581Srdivacky 823200581Srdivacky // Examine each PHI. 824200581Srdivacky for (BasicBlock::iterator I = BB->begin(); 825200581Srdivacky PHINode *PN = dyn_cast<PHINode>(I++); ) { 826200581Srdivacky // Compute a hash value on the operands. Instcombine will likely have sorted 827200581Srdivacky // them, which helps expose duplicates, but we have to check all the 828200581Srdivacky // operands to be safe in case instcombine hasn't run. 829200581Srdivacky uintptr_t Hash = 0; 830224145Sdim // This hash algorithm is quite weak as hash functions go, but it seems 831224145Sdim // to do a good enough job for this particular purpose, and is very quick. 832200581Srdivacky for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { 833200581Srdivacky Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I)); 834200581Srdivacky Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 835200581Srdivacky } 836224145Sdim for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end(); 837224145Sdim I != E; ++I) { 838224145Sdim Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I)); 839224145Sdim Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 840224145Sdim } 841221345Sdim // Avoid colliding with the DenseMap sentinels ~0 and ~0-1. 842221345Sdim Hash >>= 1; 843200581Srdivacky // If we've never seen this hash value before, it's a unique PHI. 844200581Srdivacky std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair = 845200581Srdivacky HashMap.insert(std::make_pair(Hash, PN)); 846200581Srdivacky if (Pair.second) continue; 847200581Srdivacky // Otherwise it's either a duplicate or a hash collision. 848200581Srdivacky for (PHINode *OtherPN = Pair.first->second; ; ) { 849200581Srdivacky if (OtherPN->isIdenticalTo(PN)) { 850200581Srdivacky // A duplicate. Replace this PHI with its duplicate. 851200581Srdivacky PN->replaceAllUsesWith(OtherPN); 852200581Srdivacky PN->eraseFromParent(); 853200581Srdivacky Changed = true; 854200581Srdivacky break; 855200581Srdivacky } 856200581Srdivacky // A non-duplicate hash collision. 857200581Srdivacky DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN); 858200581Srdivacky if (I == CollisionMap.end()) { 859200581Srdivacky // Set this PHI to be the head of the linked list of colliding PHIs. 860200581Srdivacky PHINode *Old = Pair.first->second; 861200581Srdivacky Pair.first->second = PN; 862200581Srdivacky CollisionMap[PN] = Old; 863200581Srdivacky break; 864200581Srdivacky } 865239462Sdim // Proceed to the next PHI in the list. 866200581Srdivacky OtherPN = I->second; 867200581Srdivacky } 868200581Srdivacky } 869200581Srdivacky 870200581Srdivacky return Changed; 871200581Srdivacky} 872218893Sdim 873218893Sdim/// enforceKnownAlignment - If the specified pointer points to an object that 874218893Sdim/// we control, modify the object's alignment to PrefAlign. This isn't 875218893Sdim/// often possible though. If alignment is important, a more reliable approach 876218893Sdim/// is to simply align all global variables and allocation instructions to 877218893Sdim/// their preferred alignment from the beginning. 878218893Sdim/// 879218893Sdimstatic unsigned enforceKnownAlignment(Value *V, unsigned Align, 880243830Sdim unsigned PrefAlign, const DataLayout *TD) { 881224145Sdim V = V->stripPointerCasts(); 882218893Sdim 883224145Sdim if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 884226633Sdim // If the preferred alignment is greater than the natural stack alignment 885226633Sdim // then don't round up. This avoids dynamic stack realignment. 886226633Sdim if (TD && TD->exceedsNaturalStackAlignment(PrefAlign)) 887226633Sdim return Align; 888218893Sdim // If there is a requested alignment and if this is an alloca, round up. 889218893Sdim if (AI->getAlignment() >= PrefAlign) 890218893Sdim return AI->getAlignment(); 891218893Sdim AI->setAlignment(PrefAlign); 892218893Sdim return PrefAlign; 893218893Sdim } 894218893Sdim 895218893Sdim if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 896218893Sdim // If there is a large requested alignment and we can, bump up the alignment 897218893Sdim // of the global. 898218893Sdim if (GV->isDeclaration()) return Align; 899234353Sdim // If the memory we set aside for the global may not be the memory used by 900234353Sdim // the final program then it is impossible for us to reliably enforce the 901234353Sdim // preferred alignment. 902234353Sdim if (GV->isWeakForLinker()) return Align; 903263508Sdim 904218893Sdim if (GV->getAlignment() >= PrefAlign) 905218893Sdim return GV->getAlignment(); 906218893Sdim // We can only increase the alignment of the global if it has no alignment 907218893Sdim // specified or if it is not assigned a section. If it is assigned a 908218893Sdim // section, the global could be densely packed with other objects in the 909218893Sdim // section, increasing the alignment could cause padding issues. 910218893Sdim if (!GV->hasSection() || GV->getAlignment() == 0) 911218893Sdim GV->setAlignment(PrefAlign); 912218893Sdim return GV->getAlignment(); 913218893Sdim } 914218893Sdim 915218893Sdim return Align; 916218893Sdim} 917218893Sdim 918218893Sdim/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 919218893Sdim/// we can determine, return it, otherwise return 0. If PrefAlign is specified, 920218893Sdim/// and it is more than the alignment of the ultimate object, see if we can 921218893Sdim/// increase the alignment of the ultimate object, making this check succeed. 922218893Sdimunsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 923263508Sdim const DataLayout *DL) { 924218893Sdim assert(V->getType()->isPointerTy() && 925218893Sdim "getOrEnforceKnownAlignment expects a pointer!"); 926263508Sdim unsigned BitWidth = DL ? DL->getPointerTypeSizeInBits(V->getType()) : 64; 927263508Sdim 928218893Sdim APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 929263508Sdim ComputeMaskedBits(V, KnownZero, KnownOne, DL); 930218893Sdim unsigned TrailZ = KnownZero.countTrailingOnes(); 931263508Sdim 932263508Sdim // Avoid trouble with ridiculously large TrailZ values, such as 933218893Sdim // those computed from a null pointer. 934218893Sdim TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 935263508Sdim 936218893Sdim unsigned Align = 1u << std::min(BitWidth - 1, TrailZ); 937263508Sdim 938218893Sdim // LLVM doesn't support alignments larger than this currently. 939218893Sdim Align = std::min(Align, +Value::MaximumAlignment); 940263508Sdim 941218893Sdim if (PrefAlign > Align) 942263508Sdim Align = enforceKnownAlignment(V, Align, PrefAlign, DL); 943263508Sdim 944218893Sdim // We don't need to make any adjustment. 945218893Sdim return Align; 946218893Sdim} 947218893Sdim 948221345Sdim///===---------------------------------------------------------------------===// 949221345Sdim/// Dbg Intrinsic utilities 950221345Sdim/// 951221345Sdim 952251662Sdim/// See if there is a dbg.value intrinsic for DIVar before I. 953251662Sdimstatic bool LdStHasDebugValue(DIVariable &DIVar, Instruction *I) { 954251662Sdim // Since we can't guarantee that the original dbg.declare instrinsic 955251662Sdim // is removed by LowerDbgDeclare(), we need to make sure that we are 956251662Sdim // not inserting the same dbg.value intrinsic over and over. 957251662Sdim llvm::BasicBlock::InstListType::iterator PrevI(I); 958251662Sdim if (PrevI != I->getParent()->getInstList().begin()) { 959251662Sdim --PrevI; 960251662Sdim if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI)) 961251662Sdim if (DVI->getValue() == I->getOperand(0) && 962251662Sdim DVI->getOffset() == 0 && 963251662Sdim DVI->getVariable() == DIVar) 964251662Sdim return true; 965251662Sdim } 966251662Sdim return false; 967251662Sdim} 968251662Sdim 969251662Sdim/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 970221345Sdim/// that has an associated llvm.dbg.decl intrinsic. 971221345Sdimbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 972221345Sdim StoreInst *SI, DIBuilder &Builder) { 973221345Sdim DIVariable DIVar(DDI->getVariable()); 974263508Sdim assert((!DIVar || DIVar.isVariable()) && 975263508Sdim "Variable in DbgDeclareInst should be either null or a DIVariable."); 976263508Sdim if (!DIVar) 977221345Sdim return false; 978221345Sdim 979251662Sdim if (LdStHasDebugValue(DIVar, SI)) 980251662Sdim return true; 981251662Sdim 982223017Sdim Instruction *DbgVal = NULL; 983223017Sdim // If an argument is zero extended then use argument directly. The ZExt 984223017Sdim // may be zapped by an optimization pass in future. 985223017Sdim Argument *ExtendedArg = NULL; 986223017Sdim if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0))) 987223017Sdim ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0)); 988223017Sdim if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0))) 989223017Sdim ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0)); 990223017Sdim if (ExtendedArg) 991223017Sdim DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, SI); 992223017Sdim else 993223017Sdim DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, SI); 994223017Sdim 995221345Sdim // Propagate any debug metadata from the store onto the dbg.value. 996221345Sdim DebugLoc SIDL = SI->getDebugLoc(); 997221345Sdim if (!SIDL.isUnknown()) 998221345Sdim DbgVal->setDebugLoc(SIDL); 999221345Sdim // Otherwise propagate debug metadata from dbg.declare. 1000221345Sdim else 1001221345Sdim DbgVal->setDebugLoc(DDI->getDebugLoc()); 1002221345Sdim return true; 1003221345Sdim} 1004221345Sdim 1005251662Sdim/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 1006221345Sdim/// that has an associated llvm.dbg.decl intrinsic. 1007221345Sdimbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 1008221345Sdim LoadInst *LI, DIBuilder &Builder) { 1009221345Sdim DIVariable DIVar(DDI->getVariable()); 1010263508Sdim assert((!DIVar || DIVar.isVariable()) && 1011263508Sdim "Variable in DbgDeclareInst should be either null or a DIVariable."); 1012263508Sdim if (!DIVar) 1013221345Sdim return false; 1014221345Sdim 1015251662Sdim if (LdStHasDebugValue(DIVar, LI)) 1016251662Sdim return true; 1017251662Sdim 1018263508Sdim Instruction *DbgVal = 1019221345Sdim Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, 1020221345Sdim DIVar, LI); 1021263508Sdim 1022221345Sdim // Propagate any debug metadata from the store onto the dbg.value. 1023221345Sdim DebugLoc LIDL = LI->getDebugLoc(); 1024221345Sdim if (!LIDL.isUnknown()) 1025221345Sdim DbgVal->setDebugLoc(LIDL); 1026221345Sdim // Otherwise propagate debug metadata from dbg.declare. 1027221345Sdim else 1028221345Sdim DbgVal->setDebugLoc(DDI->getDebugLoc()); 1029221345Sdim return true; 1030221345Sdim} 1031221345Sdim 1032221345Sdim/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 1033221345Sdim/// of llvm.dbg.value intrinsics. 1034221345Sdimbool llvm::LowerDbgDeclare(Function &F) { 1035221345Sdim DIBuilder DIB(*F.getParent()); 1036221345Sdim SmallVector<DbgDeclareInst *, 4> Dbgs; 1037221345Sdim for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 1038221345Sdim for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) { 1039221345Sdim if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(BI)) 1040221345Sdim Dbgs.push_back(DDI); 1041221345Sdim } 1042221345Sdim if (Dbgs.empty()) 1043221345Sdim return false; 1044221345Sdim 1045263508Sdim for (SmallVectorImpl<DbgDeclareInst *>::iterator I = Dbgs.begin(), 1046221345Sdim E = Dbgs.end(); I != E; ++I) { 1047221345Sdim DbgDeclareInst *DDI = *I; 1048263508Sdim AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress()); 1049263508Sdim // If this is an alloca for a scalar variable, insert a dbg.value 1050263508Sdim // at each load and store to the alloca and erase the dbg.declare. 1051263508Sdim if (AI && !AI->isArrayAllocation()) { 1052263508Sdim 1053251662Sdim // We only remove the dbg.declare intrinsic if all uses are 1054251662Sdim // converted to dbg.value intrinsics. 1055221345Sdim bool RemoveDDI = true; 1056221345Sdim for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 1057221345Sdim UI != E; ++UI) 1058221345Sdim if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 1059221345Sdim ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 1060221345Sdim else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) 1061221345Sdim ConvertDebugDeclareToDebugValue(DDI, LI, DIB); 1062221345Sdim else 1063221345Sdim RemoveDDI = false; 1064221345Sdim if (RemoveDDI) 1065221345Sdim DDI->eraseFromParent(); 1066221345Sdim } 1067221345Sdim } 1068221345Sdim return true; 1069221345Sdim} 1070223017Sdim 1071223017Sdim/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the 1072223017Sdim/// alloca 'V', if any. 1073223017SdimDbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) { 1074223017Sdim if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), V)) 1075223017Sdim for (Value::use_iterator UI = DebugNode->use_begin(), 1076223017Sdim E = DebugNode->use_end(); UI != E; ++UI) 1077223017Sdim if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(*UI)) 1078223017Sdim return DDI; 1079223017Sdim 1080223017Sdim return 0; 1081223017Sdim} 1082249423Sdim 1083249423Sdimbool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 1084249423Sdim DIBuilder &Builder) { 1085249423Sdim DbgDeclareInst *DDI = FindAllocaDbgDeclare(AI); 1086249423Sdim if (!DDI) 1087249423Sdim return false; 1088249423Sdim DIVariable DIVar(DDI->getVariable()); 1089263508Sdim assert((!DIVar || DIVar.isVariable()) && 1090263508Sdim "Variable in DbgDeclareInst should be either null or a DIVariable."); 1091263508Sdim if (!DIVar) 1092249423Sdim return false; 1093249423Sdim 1094249423Sdim // Create a copy of the original DIDescriptor for user variable, appending 1095249423Sdim // "deref" operation to a list of address elements, as new llvm.dbg.declare 1096249423Sdim // will take a value storing address of the memory for variable, not 1097249423Sdim // alloca itself. 1098249423Sdim Type *Int64Ty = Type::getInt64Ty(AI->getContext()); 1099249423Sdim SmallVector<Value*, 4> NewDIVarAddress; 1100249423Sdim if (DIVar.hasComplexAddress()) { 1101249423Sdim for (unsigned i = 0, n = DIVar.getNumAddrElements(); i < n; ++i) { 1102249423Sdim NewDIVarAddress.push_back( 1103249423Sdim ConstantInt::get(Int64Ty, DIVar.getAddrElement(i))); 1104249423Sdim } 1105249423Sdim } 1106249423Sdim NewDIVarAddress.push_back(ConstantInt::get(Int64Ty, DIBuilder::OpDeref)); 1107249423Sdim DIVariable NewDIVar = Builder.createComplexVariable( 1108249423Sdim DIVar.getTag(), DIVar.getContext(), DIVar.getName(), 1109249423Sdim DIVar.getFile(), DIVar.getLineNumber(), DIVar.getType(), 1110249423Sdim NewDIVarAddress, DIVar.getArgNumber()); 1111249423Sdim 1112249423Sdim // Insert llvm.dbg.declare in the same basic block as the original alloca, 1113249423Sdim // and remove old llvm.dbg.declare. 1114249423Sdim BasicBlock *BB = AI->getParent(); 1115249423Sdim Builder.insertDeclare(NewAllocaAddress, NewDIVar, BB); 1116249423Sdim DDI->eraseFromParent(); 1117249423Sdim return true; 1118249423Sdim} 1119249423Sdim 1120263508Sdim/// changeToUnreachable - Insert an unreachable instruction before the specified 1121263508Sdim/// instruction, making it and the rest of the code in the block dead. 1122263508Sdimstatic void changeToUnreachable(Instruction *I, bool UseLLVMTrap) { 1123263508Sdim BasicBlock *BB = I->getParent(); 1124263508Sdim // Loop over all of the successors, removing BB's entry from any PHI 1125263508Sdim // nodes. 1126263508Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 1127263508Sdim (*SI)->removePredecessor(BB); 1128263508Sdim 1129263508Sdim // Insert a call to llvm.trap right before this. This turns the undefined 1130263508Sdim // behavior into a hard fail instead of falling through into random code. 1131263508Sdim if (UseLLVMTrap) { 1132263508Sdim Function *TrapFn = 1133263508Sdim Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); 1134263508Sdim CallInst *CallTrap = CallInst::Create(TrapFn, "", I); 1135263508Sdim CallTrap->setDebugLoc(I->getDebugLoc()); 1136263508Sdim } 1137263508Sdim new UnreachableInst(I->getContext(), I); 1138263508Sdim 1139263508Sdim // All instructions after this are dead. 1140263508Sdim BasicBlock::iterator BBI = I, BBE = BB->end(); 1141263508Sdim while (BBI != BBE) { 1142263508Sdim if (!BBI->use_empty()) 1143263508Sdim BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 1144263508Sdim BB->getInstList().erase(BBI++); 1145263508Sdim } 1146263508Sdim} 1147263508Sdim 1148263508Sdim/// changeToCall - Convert the specified invoke into a normal call. 1149263508Sdimstatic void changeToCall(InvokeInst *II) { 1150263508Sdim SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); 1151263508Sdim CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, "", II); 1152263508Sdim NewCall->takeName(II); 1153263508Sdim NewCall->setCallingConv(II->getCallingConv()); 1154263508Sdim NewCall->setAttributes(II->getAttributes()); 1155263508Sdim NewCall->setDebugLoc(II->getDebugLoc()); 1156263508Sdim II->replaceAllUsesWith(NewCall); 1157263508Sdim 1158263508Sdim // Follow the call by a branch to the normal destination. 1159263508Sdim BranchInst::Create(II->getNormalDest(), II); 1160263508Sdim 1161263508Sdim // Update PHI nodes in the unwind destination 1162263508Sdim II->getUnwindDest()->removePredecessor(II->getParent()); 1163263508Sdim II->eraseFromParent(); 1164263508Sdim} 1165263508Sdim 1166263508Sdimstatic bool markAliveBlocks(BasicBlock *BB, 1167263508Sdim SmallPtrSet<BasicBlock*, 128> &Reachable) { 1168263508Sdim 1169249423Sdim SmallVector<BasicBlock*, 128> Worklist; 1170263508Sdim Worklist.push_back(BB); 1171263508Sdim Reachable.insert(BB); 1172263508Sdim bool Changed = false; 1173249423Sdim do { 1174263508Sdim BB = Worklist.pop_back_val(); 1175263508Sdim 1176263508Sdim // Do a quick scan of the basic block, turning any obviously unreachable 1177263508Sdim // instructions into LLVM unreachable insts. The instruction combining pass 1178263508Sdim // canonicalizes unreachable insts into stores to null or undef. 1179263508Sdim for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ 1180263508Sdim if (CallInst *CI = dyn_cast<CallInst>(BBI)) { 1181263508Sdim if (CI->doesNotReturn()) { 1182263508Sdim // If we found a call to a no-return function, insert an unreachable 1183263508Sdim // instruction after it. Make sure there isn't *already* one there 1184263508Sdim // though. 1185263508Sdim ++BBI; 1186263508Sdim if (!isa<UnreachableInst>(BBI)) { 1187263508Sdim // Don't insert a call to llvm.trap right before the unreachable. 1188263508Sdim changeToUnreachable(BBI, false); 1189263508Sdim Changed = true; 1190263508Sdim } 1191263508Sdim break; 1192263508Sdim } 1193263508Sdim } 1194263508Sdim 1195263508Sdim // Store to undef and store to null are undefined and used to signal that 1196263508Sdim // they should be changed to unreachable by passes that can't modify the 1197263508Sdim // CFG. 1198263508Sdim if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 1199263508Sdim // Don't touch volatile stores. 1200263508Sdim if (SI->isVolatile()) continue; 1201263508Sdim 1202263508Sdim Value *Ptr = SI->getOperand(1); 1203263508Sdim 1204263508Sdim if (isa<UndefValue>(Ptr) || 1205263508Sdim (isa<ConstantPointerNull>(Ptr) && 1206263508Sdim SI->getPointerAddressSpace() == 0)) { 1207263508Sdim changeToUnreachable(SI, true); 1208263508Sdim Changed = true; 1209263508Sdim break; 1210263508Sdim } 1211263508Sdim } 1212263508Sdim } 1213263508Sdim 1214263508Sdim // Turn invokes that call 'nounwind' functions into ordinary calls. 1215263508Sdim if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) { 1216263508Sdim Value *Callee = II->getCalledValue(); 1217263508Sdim if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { 1218263508Sdim changeToUnreachable(II, true); 1219263508Sdim Changed = true; 1220263508Sdim } else if (II->doesNotThrow()) { 1221263508Sdim if (II->use_empty() && II->onlyReadsMemory()) { 1222263508Sdim // jump to the normal destination branch. 1223263508Sdim BranchInst::Create(II->getNormalDest(), II); 1224263508Sdim II->getUnwindDest()->removePredecessor(II->getParent()); 1225263508Sdim II->eraseFromParent(); 1226263508Sdim } else 1227263508Sdim changeToCall(II); 1228263508Sdim Changed = true; 1229263508Sdim } 1230263508Sdim } 1231263508Sdim 1232263508Sdim Changed |= ConstantFoldTerminator(BB, true); 1233249423Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 1234249423Sdim if (Reachable.insert(*SI)) 1235249423Sdim Worklist.push_back(*SI); 1236249423Sdim } while (!Worklist.empty()); 1237263508Sdim return Changed; 1238263508Sdim} 1239249423Sdim 1240263508Sdim/// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even 1241263508Sdim/// if they are in a dead cycle. Return true if a change was made, false 1242263508Sdim/// otherwise. 1243263508Sdimbool llvm::removeUnreachableBlocks(Function &F) { 1244263508Sdim SmallPtrSet<BasicBlock*, 128> Reachable; 1245263508Sdim bool Changed = markAliveBlocks(F.begin(), Reachable); 1246263508Sdim 1247263508Sdim // If there are unreachable blocks in the CFG... 1248249423Sdim if (Reachable.size() == F.size()) 1249263508Sdim return Changed; 1250249423Sdim 1251249423Sdim assert(Reachable.size() < F.size()); 1252263508Sdim NumRemoved += F.size()-Reachable.size(); 1253263508Sdim 1254263508Sdim // Loop over all of the basic blocks that are not reachable, dropping all of 1255263508Sdim // their internal references... 1256263508Sdim for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { 1257263508Sdim if (Reachable.count(BB)) 1258249423Sdim continue; 1259249423Sdim 1260263508Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 1261249423Sdim if (Reachable.count(*SI)) 1262263508Sdim (*SI)->removePredecessor(BB); 1263263508Sdim BB->dropAllReferences(); 1264249423Sdim } 1265249423Sdim 1266263508Sdim for (Function::iterator I = ++F.begin(); I != F.end();) 1267249423Sdim if (!Reachable.count(I)) 1268249423Sdim I = F.getBasicBlockList().erase(I); 1269249423Sdim else 1270249423Sdim ++I; 1271249423Sdim 1272249423Sdim return true; 1273249423Sdim} 1274