Local.cpp revision 200581
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" 16193323Sed#include "llvm/Constants.h" 17194612Sed#include "llvm/GlobalAlias.h" 18193323Sed#include "llvm/GlobalVariable.h" 19193323Sed#include "llvm/DerivedTypes.h" 20193323Sed#include "llvm/Instructions.h" 21193323Sed#include "llvm/Intrinsics.h" 22193323Sed#include "llvm/IntrinsicInst.h" 23198090Srdivacky#include "llvm/LLVMContext.h" 24193323Sed#include "llvm/ADT/SmallPtrSet.h" 25193323Sed#include "llvm/Analysis/ConstantFolding.h" 26193323Sed#include "llvm/Analysis/DebugInfo.h" 27199481Srdivacky#include "llvm/Analysis/InstructionSimplify.h" 28198090Srdivacky#include "llvm/Analysis/ProfileInfo.h" 29193323Sed#include "llvm/Target/TargetData.h" 30199481Srdivacky#include "llvm/Support/CFG.h" 31199481Srdivacky#include "llvm/Support/Debug.h" 32193323Sed#include "llvm/Support/GetElementPtrTypeIterator.h" 33193323Sed#include "llvm/Support/MathExtras.h" 34199481Srdivacky#include "llvm/Support/raw_ostream.h" 35193323Sedusing namespace llvm; 36193323Sed 37193323Sed//===----------------------------------------------------------------------===// 38194612Sed// Local analysis. 39194612Sed// 40194612Sed 41194612Sed/// isSafeToLoadUnconditionally - Return true if we know that executing a load 42194612Sed/// from this value cannot trap. If it is not obviously safe to load from the 43194612Sed/// specified pointer, we do a quick local scan of the basic block containing 44194612Sed/// ScanFrom, to determine if the address is already accessed. 45194612Sedbool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) { 46194612Sed // If it is an alloca it is always safe to load from. 47194612Sed if (isa<AllocaInst>(V)) return true; 48194612Sed 49194612Sed // If it is a global variable it is mostly safe to load from. 50194612Sed if (const GlobalValue *GV = dyn_cast<GlobalVariable>(V)) 51194612Sed // Don't try to evaluate aliases. External weak GV can be null. 52194612Sed return !isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage(); 53194612Sed 54194612Sed // Otherwise, be a little bit agressive by scanning the local block where we 55194612Sed // want to check to see if the pointer is already being loaded or stored 56194612Sed // from/to. If so, the previous load or store would have already trapped, 57194612Sed // so there is no harm doing an extra load (also, CSE will later eliminate 58194612Sed // the load entirely). 59194612Sed BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin(); 60194612Sed 61194612Sed while (BBI != E) { 62194612Sed --BBI; 63194612Sed 64194612Sed // If we see a free or a call which may write to memory (i.e. which might do 65194612Sed // a free) the pointer could be marked invalid. 66198892Srdivacky if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() && 67198892Srdivacky !isa<DbgInfoIntrinsic>(BBI)) 68194612Sed return false; 69194612Sed 70194612Sed if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 71194612Sed if (LI->getOperand(0) == V) return true; 72194612Sed } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 73194612Sed if (SI->getOperand(1) == V) return true; 74194612Sed } 75194612Sed } 76194612Sed return false; 77194612Sed} 78194612Sed 79194612Sed 80194612Sed//===----------------------------------------------------------------------===// 81193323Sed// Local constant propagation. 82193323Sed// 83193323Sed 84193323Sed// ConstantFoldTerminator - If a terminator instruction is predicated on a 85193323Sed// constant value, convert it into an unconditional branch to the constant 86193323Sed// destination. 87193323Sed// 88193323Sedbool llvm::ConstantFoldTerminator(BasicBlock *BB) { 89193323Sed TerminatorInst *T = BB->getTerminator(); 90193323Sed 91193323Sed // Branch - See if we are conditional jumping on constant 92193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 93193323Sed if (BI->isUnconditional()) return false; // Can't optimize uncond branch 94193323Sed BasicBlock *Dest1 = BI->getSuccessor(0); 95193323Sed BasicBlock *Dest2 = BI->getSuccessor(1); 96193323Sed 97193323Sed if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 98193323Sed // Are we branching on constant? 99193323Sed // YES. Change to unconditional branch... 100193323Sed BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 101193323Sed BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 102193323Sed 103193323Sed //cerr << "Function: " << T->getParent()->getParent() 104193323Sed // << "\nRemoving branch from " << T->getParent() 105193323Sed // << "\n\nTo: " << OldDest << endl; 106193323Sed 107193323Sed // Let the basic block know that we are letting go of it. Based on this, 108193323Sed // it will adjust it's PHI nodes. 109193323Sed assert(BI->getParent() && "Terminator not inserted in block!"); 110193323Sed OldDest->removePredecessor(BI->getParent()); 111193323Sed 112193323Sed // Set the unconditional destination, and change the insn to be an 113193323Sed // unconditional branch. 114193323Sed BI->setUnconditionalDest(Destination); 115193323Sed return true; 116198892Srdivacky } 117198892Srdivacky 118198892Srdivacky if (Dest2 == Dest1) { // Conditional branch to same location? 119193323Sed // This branch matches something like this: 120193323Sed // br bool %cond, label %Dest, label %Dest 121193323Sed // and changes it into: br label %Dest 122193323Sed 123193323Sed // Let the basic block know that we are letting go of one copy of it. 124193323Sed assert(BI->getParent() && "Terminator not inserted in block!"); 125193323Sed Dest1->removePredecessor(BI->getParent()); 126193323Sed 127193323Sed // Change a conditional branch to unconditional. 128193323Sed BI->setUnconditionalDest(Dest1); 129193323Sed return true; 130193323Sed } 131198892Srdivacky return false; 132198892Srdivacky } 133198892Srdivacky 134198892Srdivacky if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 135193323Sed // If we are switching on a constant, we can convert the switch into a 136193323Sed // single branch instruction! 137193323Sed ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 138193323Sed BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 139193323Sed BasicBlock *DefaultDest = TheOnlyDest; 140193323Sed assert(TheOnlyDest == SI->getDefaultDest() && 141193323Sed "Default destination is not successor #0?"); 142193323Sed 143198892Srdivacky // Figure out which case it goes to. 144193323Sed for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 145193323Sed // Found case matching a constant operand? 146193323Sed if (SI->getSuccessorValue(i) == CI) { 147193323Sed TheOnlyDest = SI->getSuccessor(i); 148193323Sed break; 149193323Sed } 150193323Sed 151193323Sed // Check to see if this branch is going to the same place as the default 152193323Sed // dest. If so, eliminate it as an explicit compare. 153193323Sed if (SI->getSuccessor(i) == DefaultDest) { 154198892Srdivacky // Remove this entry. 155193323Sed DefaultDest->removePredecessor(SI->getParent()); 156193323Sed SI->removeCase(i); 157193323Sed --i; --e; // Don't skip an entry... 158193323Sed continue; 159193323Sed } 160193323Sed 161193323Sed // Otherwise, check to see if the switch only branches to one destination. 162193323Sed // We do this by reseting "TheOnlyDest" to null when we find two non-equal 163193323Sed // destinations. 164193323Sed if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 165193323Sed } 166193323Sed 167193323Sed if (CI && !TheOnlyDest) { 168193323Sed // Branching on a constant, but not any of the cases, go to the default 169193323Sed // successor. 170193323Sed TheOnlyDest = SI->getDefaultDest(); 171193323Sed } 172193323Sed 173193323Sed // If we found a single destination that we can fold the switch into, do so 174193323Sed // now. 175193323Sed if (TheOnlyDest) { 176198892Srdivacky // Insert the new branch. 177193323Sed BranchInst::Create(TheOnlyDest, SI); 178193323Sed BasicBlock *BB = SI->getParent(); 179193323Sed 180193323Sed // Remove entries from PHI nodes which we no longer branch to... 181193323Sed for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 182193323Sed // Found case matching a constant operand? 183193323Sed BasicBlock *Succ = SI->getSuccessor(i); 184193323Sed if (Succ == TheOnlyDest) 185193323Sed TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 186193323Sed else 187193323Sed Succ->removePredecessor(BB); 188193323Sed } 189193323Sed 190198892Srdivacky // Delete the old switch. 191193323Sed BB->getInstList().erase(SI); 192193323Sed return true; 193198892Srdivacky } 194198892Srdivacky 195198892Srdivacky if (SI->getNumSuccessors() == 2) { 196193323Sed // Otherwise, we can fold this switch into a conditional branch 197193323Sed // instruction if it has only one non-default destination. 198198090Srdivacky Value *Cond = new ICmpInst(SI, ICmpInst::ICMP_EQ, SI->getCondition(), 199198090Srdivacky SI->getSuccessorValue(1), "cond"); 200198892Srdivacky // Insert the new branch. 201193323Sed BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 202193323Sed 203198892Srdivacky // Delete the old switch. 204193323Sed SI->eraseFromParent(); 205193323Sed return true; 206193323Sed } 207198892Srdivacky return false; 208193323Sed } 209198892Srdivacky 210198892Srdivacky if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { 211198892Srdivacky // indirectbr blockaddress(@F, @BB) -> br label @BB 212198892Srdivacky if (BlockAddress *BA = 213198892Srdivacky dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 214198892Srdivacky BasicBlock *TheOnlyDest = BA->getBasicBlock(); 215198892Srdivacky // Insert the new branch. 216198892Srdivacky BranchInst::Create(TheOnlyDest, IBI); 217198892Srdivacky 218198892Srdivacky for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 219198892Srdivacky if (IBI->getDestination(i) == TheOnlyDest) 220198892Srdivacky TheOnlyDest = 0; 221198892Srdivacky else 222198892Srdivacky IBI->getDestination(i)->removePredecessor(IBI->getParent()); 223198892Srdivacky } 224198892Srdivacky IBI->eraseFromParent(); 225198892Srdivacky 226198892Srdivacky // If we didn't find our destination in the IBI successor list, then we 227198892Srdivacky // have undefined behavior. Replace the unconditional branch with an 228198892Srdivacky // 'unreachable' instruction. 229198892Srdivacky if (TheOnlyDest) { 230198892Srdivacky BB->getTerminator()->eraseFromParent(); 231198892Srdivacky new UnreachableInst(BB->getContext(), BB); 232198892Srdivacky } 233198892Srdivacky 234198892Srdivacky return true; 235198892Srdivacky } 236198892Srdivacky } 237198892Srdivacky 238193323Sed return false; 239193323Sed} 240193323Sed 241193323Sed 242193323Sed//===----------------------------------------------------------------------===// 243199481Srdivacky// Local dead code elimination. 244193323Sed// 245193323Sed 246193323Sed/// isInstructionTriviallyDead - Return true if the result produced by the 247193323Sed/// instruction is not used, and the instruction has no side effects. 248193323Sed/// 249193323Sedbool llvm::isInstructionTriviallyDead(Instruction *I) { 250193323Sed if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 251193323Sed 252193323Sed // We don't want debug info removed by anything this general. 253193323Sed if (isa<DbgInfoIntrinsic>(I)) return false; 254193323Sed 255199481Srdivacky // Likewise for memory use markers. 256199481Srdivacky if (isa<MemoryUseIntrinsic>(I)) return false; 257199481Srdivacky 258193323Sed if (!I->mayHaveSideEffects()) return true; 259193323Sed 260193323Sed // Special case intrinsics that "may have side effects" but can be deleted 261193323Sed // when dead. 262193323Sed if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 263193323Sed // Safe to delete llvm.stacksave if dead. 264193323Sed if (II->getIntrinsicID() == Intrinsic::stacksave) 265193323Sed return true; 266193323Sed return false; 267193323Sed} 268193323Sed 269193323Sed/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 270193323Sed/// trivially dead instruction, delete it. If that makes any of its operands 271193323Sed/// trivially dead, delete them too, recursively. 272193323Sedvoid llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { 273193323Sed Instruction *I = dyn_cast<Instruction>(V); 274193323Sed if (!I || !I->use_empty() || !isInstructionTriviallyDead(I)) 275193323Sed return; 276193323Sed 277193323Sed SmallVector<Instruction*, 16> DeadInsts; 278193323Sed DeadInsts.push_back(I); 279193323Sed 280193323Sed while (!DeadInsts.empty()) { 281193323Sed I = DeadInsts.pop_back_val(); 282193323Sed 283193323Sed // Null out all of the instruction's operands to see if any operand becomes 284193323Sed // dead as we go. 285193323Sed for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 286193323Sed Value *OpV = I->getOperand(i); 287193323Sed I->setOperand(i, 0); 288193323Sed 289193323Sed if (!OpV->use_empty()) continue; 290193323Sed 291193323Sed // If the operand is an instruction that became dead as we nulled out the 292193323Sed // operand, and if it is 'trivially' dead, delete it in a future loop 293193323Sed // iteration. 294193323Sed if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 295193323Sed if (isInstructionTriviallyDead(OpI)) 296193323Sed DeadInsts.push_back(OpI); 297193323Sed } 298193323Sed 299193323Sed I->eraseFromParent(); 300193323Sed } 301193323Sed} 302193323Sed 303193323Sed/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 304193323Sed/// dead PHI node, due to being a def-use chain of single-use nodes that 305193323Sed/// either forms a cycle or is terminated by a trivially dead instruction, 306193323Sed/// delete it. If that makes any of its operands trivially dead, delete them 307193323Sed/// too, recursively. 308193323Sedvoid 309193323Sedllvm::RecursivelyDeleteDeadPHINode(PHINode *PN) { 310193323Sed // We can remove a PHI if it is on a cycle in the def-use graph 311193323Sed // where each node in the cycle has degree one, i.e. only one use, 312193323Sed // and is an instruction with no side effects. 313193323Sed if (!PN->hasOneUse()) 314193323Sed return; 315193323Sed 316193323Sed SmallPtrSet<PHINode *, 4> PHIs; 317193323Sed PHIs.insert(PN); 318193323Sed for (Instruction *J = cast<Instruction>(*PN->use_begin()); 319193323Sed J->hasOneUse() && !J->mayHaveSideEffects(); 320193323Sed J = cast<Instruction>(*J->use_begin())) 321193323Sed // If we find a PHI more than once, we're on a cycle that 322193323Sed // won't prove fruitful. 323193323Sed if (PHINode *JP = dyn_cast<PHINode>(J)) 324193323Sed if (!PHIs.insert(cast<PHINode>(JP))) { 325193323Sed // Break the cycle and delete the PHI and its operands. 326193323Sed JP->replaceAllUsesWith(UndefValue::get(JP->getType())); 327193323Sed RecursivelyDeleteTriviallyDeadInstructions(JP); 328193323Sed break; 329193323Sed } 330193323Sed} 331193323Sed 332193323Sed//===----------------------------------------------------------------------===// 333199481Srdivacky// Control Flow Graph Restructuring. 334193323Sed// 335193323Sed 336199481Srdivacky 337199481Srdivacky/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 338199481Srdivacky/// method is called when we're about to delete Pred as a predecessor of BB. If 339199481Srdivacky/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 340199481Srdivacky/// 341199481Srdivacky/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 342199481Srdivacky/// nodes that collapse into identity values. For example, if we have: 343199481Srdivacky/// x = phi(1, 0, 0, 0) 344199481Srdivacky/// y = and x, z 345199481Srdivacky/// 346199481Srdivacky/// .. and delete the predecessor corresponding to the '1', this will attempt to 347199481Srdivacky/// recursively fold the and to 0. 348199481Srdivackyvoid llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 349199481Srdivacky TargetData *TD) { 350199481Srdivacky // This only adjusts blocks with PHI nodes. 351199481Srdivacky if (!isa<PHINode>(BB->begin())) 352199481Srdivacky return; 353199481Srdivacky 354199481Srdivacky // Remove the entries for Pred from the PHI nodes in BB, but do not simplify 355199481Srdivacky // them down. This will leave us with single entry phi nodes and other phis 356199481Srdivacky // that can be removed. 357199481Srdivacky BB->removePredecessor(Pred, true); 358199481Srdivacky 359199481Srdivacky WeakVH PhiIt = &BB->front(); 360199481Srdivacky while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) { 361199481Srdivacky PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt)); 362199481Srdivacky 363199481Srdivacky Value *PNV = PN->hasConstantValue(); 364199481Srdivacky if (PNV == 0) continue; 365199481Srdivacky 366199481Srdivacky // If we're able to simplify the phi to a single value, substitute the new 367199481Srdivacky // value into all of its uses. 368199481Srdivacky assert(PNV != PN && "hasConstantValue broken"); 369199481Srdivacky 370199481Srdivacky ReplaceAndSimplifyAllUses(PN, PNV, TD); 371199481Srdivacky 372199481Srdivacky // If recursive simplification ended up deleting the next PHI node we would 373199481Srdivacky // iterate to, then our iterator is invalid, restart scanning from the top 374199481Srdivacky // of the block. 375199481Srdivacky if (PhiIt == 0) PhiIt = &BB->front(); 376199481Srdivacky } 377199481Srdivacky} 378199481Srdivacky 379199481Srdivacky 380193323Sed/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 381193323Sed/// predecessor is known to have one successor (DestBB!). Eliminate the edge 382193323Sed/// between them, moving the instructions in the predecessor into DestBB and 383193323Sed/// deleting the predecessor block. 384193323Sed/// 385198090Srdivackyvoid llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { 386193323Sed // If BB has single-entry PHI nodes, fold them. 387193323Sed while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 388193323Sed Value *NewVal = PN->getIncomingValue(0); 389193323Sed // Replace self referencing PHI with undef, it must be dead. 390193323Sed if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 391193323Sed PN->replaceAllUsesWith(NewVal); 392193323Sed PN->eraseFromParent(); 393193323Sed } 394193323Sed 395193323Sed BasicBlock *PredBB = DestBB->getSinglePredecessor(); 396193323Sed assert(PredBB && "Block doesn't have a single predecessor!"); 397193323Sed 398193323Sed // Splice all the instructions from PredBB to DestBB. 399193323Sed PredBB->getTerminator()->eraseFromParent(); 400193323Sed DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 401193323Sed 402193323Sed // Anything that branched to PredBB now branches to DestBB. 403193323Sed PredBB->replaceAllUsesWith(DestBB); 404193323Sed 405198090Srdivacky if (P) { 406198090Srdivacky ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); 407198090Srdivacky if (PI) { 408198090Srdivacky PI->replaceAllUses(PredBB, DestBB); 409198090Srdivacky PI->removeEdge(ProfileInfo::getEdge(PredBB, DestBB)); 410198090Srdivacky } 411198090Srdivacky } 412193323Sed // Nuke BB. 413193323Sed PredBB->eraseFromParent(); 414193323Sed} 415193323Sed 416199481Srdivacky/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 417199481Srdivacky/// almost-empty BB ending in an unconditional branch to Succ, into succ. 418199481Srdivacky/// 419199481Srdivacky/// Assumption: Succ is the single successor for BB. 420199481Srdivacky/// 421199481Srdivackystatic bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 422199481Srdivacky assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 423199481Srdivacky 424199481Srdivacky DEBUG(errs() << "Looking to fold " << BB->getName() << " into " 425199481Srdivacky << Succ->getName() << "\n"); 426199481Srdivacky // Shortcut, if there is only a single predecessor it must be BB and merging 427199481Srdivacky // is always safe 428199481Srdivacky if (Succ->getSinglePredecessor()) return true; 429199481Srdivacky 430199481Srdivacky // Make a list of the predecessors of BB 431199481Srdivacky typedef SmallPtrSet<BasicBlock*, 16> BlockSet; 432199481Srdivacky BlockSet BBPreds(pred_begin(BB), pred_end(BB)); 433199481Srdivacky 434199481Srdivacky // Use that list to make another list of common predecessors of BB and Succ 435199481Srdivacky BlockSet CommonPreds; 436199481Srdivacky for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); 437199481Srdivacky PI != PE; ++PI) 438199481Srdivacky if (BBPreds.count(*PI)) 439199481Srdivacky CommonPreds.insert(*PI); 440199481Srdivacky 441199481Srdivacky // Shortcut, if there are no common predecessors, merging is always safe 442199481Srdivacky if (CommonPreds.empty()) 443199481Srdivacky return true; 444199481Srdivacky 445199481Srdivacky // Look at all the phi nodes in Succ, to see if they present a conflict when 446199481Srdivacky // merging these blocks 447199481Srdivacky for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 448199481Srdivacky PHINode *PN = cast<PHINode>(I); 449199481Srdivacky 450199481Srdivacky // If the incoming value from BB is again a PHINode in 451199481Srdivacky // BB which has the same incoming value for *PI as PN does, we can 452199481Srdivacky // merge the phi nodes and then the blocks can still be merged 453199481Srdivacky PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 454199481Srdivacky if (BBPN && BBPN->getParent() == BB) { 455199481Srdivacky for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); 456199481Srdivacky PI != PE; PI++) { 457199481Srdivacky if (BBPN->getIncomingValueForBlock(*PI) 458199481Srdivacky != PN->getIncomingValueForBlock(*PI)) { 459199481Srdivacky DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " 460199481Srdivacky << Succ->getName() << " is conflicting with " 461199481Srdivacky << BBPN->getName() << " with regard to common predecessor " 462199481Srdivacky << (*PI)->getName() << "\n"); 463199481Srdivacky return false; 464199481Srdivacky } 465199481Srdivacky } 466199481Srdivacky } else { 467199481Srdivacky Value* Val = PN->getIncomingValueForBlock(BB); 468199481Srdivacky for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); 469199481Srdivacky PI != PE; PI++) { 470199481Srdivacky // See if the incoming value for the common predecessor is equal to the 471199481Srdivacky // one for BB, in which case this phi node will not prevent the merging 472199481Srdivacky // of the block. 473199481Srdivacky if (Val != PN->getIncomingValueForBlock(*PI)) { 474199481Srdivacky DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " 475199481Srdivacky << Succ->getName() << " is conflicting with regard to common " 476199481Srdivacky << "predecessor " << (*PI)->getName() << "\n"); 477199481Srdivacky return false; 478199481Srdivacky } 479199481Srdivacky } 480199481Srdivacky } 481199481Srdivacky } 482199481Srdivacky 483199481Srdivacky return true; 484199481Srdivacky} 485199481Srdivacky 486199481Srdivacky/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 487199481Srdivacky/// unconditional branch, and contains no instructions other than PHI nodes, 488199481Srdivacky/// potential debug intrinsics and the branch. If possible, eliminate BB by 489199481Srdivacky/// rewriting all the predecessors to branch to the successor block and return 490199481Srdivacky/// true. If we can't transform, return false. 491199481Srdivackybool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { 492199481Srdivacky // We can't eliminate infinite loops. 493199481Srdivacky BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 494199481Srdivacky if (BB == Succ) return false; 495199481Srdivacky 496199481Srdivacky // Check to see if merging these blocks would cause conflicts for any of the 497199481Srdivacky // phi nodes in BB or Succ. If not, we can safely merge. 498199481Srdivacky if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 499199481Srdivacky 500199481Srdivacky // Check for cases where Succ has multiple predecessors and a PHI node in BB 501199481Srdivacky // has uses which will not disappear when the PHI nodes are merged. It is 502199481Srdivacky // possible to handle such cases, but difficult: it requires checking whether 503199481Srdivacky // BB dominates Succ, which is non-trivial to calculate in the case where 504199481Srdivacky // Succ has multiple predecessors. Also, it requires checking whether 505199481Srdivacky // constructing the necessary self-referential PHI node doesn't intoduce any 506199481Srdivacky // conflicts; this isn't too difficult, but the previous code for doing this 507199481Srdivacky // was incorrect. 508199481Srdivacky // 509199481Srdivacky // Note that if this check finds a live use, BB dominates Succ, so BB is 510199481Srdivacky // something like a loop pre-header (or rarely, a part of an irreducible CFG); 511199481Srdivacky // folding the branch isn't profitable in that case anyway. 512199481Srdivacky if (!Succ->getSinglePredecessor()) { 513199481Srdivacky BasicBlock::iterator BBI = BB->begin(); 514199481Srdivacky while (isa<PHINode>(*BBI)) { 515199481Srdivacky for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 516199481Srdivacky UI != E; ++UI) { 517199481Srdivacky if (PHINode* PN = dyn_cast<PHINode>(*UI)) { 518199481Srdivacky if (PN->getIncomingBlock(UI) != BB) 519199481Srdivacky return false; 520199481Srdivacky } else { 521199481Srdivacky return false; 522199481Srdivacky } 523199481Srdivacky } 524199481Srdivacky ++BBI; 525199481Srdivacky } 526199481Srdivacky } 527199481Srdivacky 528199481Srdivacky DEBUG(errs() << "Killing Trivial BB: \n" << *BB); 529199481Srdivacky 530199481Srdivacky if (isa<PHINode>(Succ->begin())) { 531199481Srdivacky // If there is more than one pred of succ, and there are PHI nodes in 532199481Srdivacky // the successor, then we need to add incoming edges for the PHI nodes 533199481Srdivacky // 534199481Srdivacky const SmallVector<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 535199481Srdivacky 536199481Srdivacky // Loop over all of the PHI nodes in the successor of BB. 537199481Srdivacky for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 538199481Srdivacky PHINode *PN = cast<PHINode>(I); 539199481Srdivacky Value *OldVal = PN->removeIncomingValue(BB, false); 540199481Srdivacky assert(OldVal && "No entry in PHI for Pred BB!"); 541199481Srdivacky 542199481Srdivacky // If this incoming value is one of the PHI nodes in BB, the new entries 543199481Srdivacky // in the PHI node are the entries from the old PHI. 544199481Srdivacky if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 545199481Srdivacky PHINode *OldValPN = cast<PHINode>(OldVal); 546199481Srdivacky for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 547199481Srdivacky // Note that, since we are merging phi nodes and BB and Succ might 548199481Srdivacky // have common predecessors, we could end up with a phi node with 549199481Srdivacky // identical incoming branches. This will be cleaned up later (and 550199481Srdivacky // will trigger asserts if we try to clean it up now, without also 551199481Srdivacky // simplifying the corresponding conditional branch). 552199481Srdivacky PN->addIncoming(OldValPN->getIncomingValue(i), 553199481Srdivacky OldValPN->getIncomingBlock(i)); 554199481Srdivacky } else { 555199481Srdivacky // Add an incoming value for each of the new incoming values. 556199481Srdivacky for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) 557199481Srdivacky PN->addIncoming(OldVal, BBPreds[i]); 558199481Srdivacky } 559199481Srdivacky } 560199481Srdivacky } 561199481Srdivacky 562199481Srdivacky while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 563199481Srdivacky if (Succ->getSinglePredecessor()) { 564199481Srdivacky // BB is the only predecessor of Succ, so Succ will end up with exactly 565199481Srdivacky // the same predecessors BB had. 566199481Srdivacky Succ->getInstList().splice(Succ->begin(), 567199481Srdivacky BB->getInstList(), BB->begin()); 568199481Srdivacky } else { 569199481Srdivacky // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 570199481Srdivacky assert(PN->use_empty() && "There shouldn't be any uses here!"); 571199481Srdivacky PN->eraseFromParent(); 572199481Srdivacky } 573199481Srdivacky } 574199481Srdivacky 575199481Srdivacky // Everything that jumped to BB now goes to Succ. 576199481Srdivacky BB->replaceAllUsesWith(Succ); 577199481Srdivacky if (!Succ->hasName()) Succ->takeName(BB); 578199481Srdivacky BB->eraseFromParent(); // Delete the old basic block. 579199481Srdivacky return true; 580199481Srdivacky} 581199481Srdivacky 582199481Srdivacky 583199481Srdivacky 584193323Sed/// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used 585193323Sed/// by DbgIntrinsics. If DbgInUses is specified then the vector is filled 586193323Sed/// with the DbgInfoIntrinsic that use the instruction I. 587193323Sedbool llvm::OnlyUsedByDbgInfoIntrinsics(Instruction *I, 588193323Sed SmallVectorImpl<DbgInfoIntrinsic *> *DbgInUses) { 589193323Sed if (DbgInUses) 590193323Sed DbgInUses->clear(); 591193323Sed 592193323Sed for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; 593193323Sed ++UI) { 594193323Sed if (DbgInfoIntrinsic *DI = dyn_cast<DbgInfoIntrinsic>(*UI)) { 595193323Sed if (DbgInUses) 596193323Sed DbgInUses->push_back(DI); 597193323Sed } else { 598193323Sed if (DbgInUses) 599193323Sed DbgInUses->clear(); 600193323Sed return false; 601193323Sed } 602193323Sed } 603193323Sed return true; 604193323Sed} 605193323Sed 606200581Srdivacky/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 607200581Srdivacky/// nodes in this block. This doesn't try to be clever about PHI nodes 608200581Srdivacky/// which differ only in the order of the incoming values, but instcombine 609200581Srdivacky/// orders them so it usually won't matter. 610200581Srdivacky/// 611200581Srdivackybool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 612200581Srdivacky bool Changed = false; 613200581Srdivacky 614200581Srdivacky // This implementation doesn't currently consider undef operands 615200581Srdivacky // specially. Theroetically, two phis which are identical except for 616200581Srdivacky // one having an undef where the other doesn't could be collapsed. 617200581Srdivacky 618200581Srdivacky // Map from PHI hash values to PHI nodes. If multiple PHIs have 619200581Srdivacky // the same hash value, the element is the first PHI in the 620200581Srdivacky // linked list in CollisionMap. 621200581Srdivacky DenseMap<uintptr_t, PHINode *> HashMap; 622200581Srdivacky 623200581Srdivacky // Maintain linked lists of PHI nodes with common hash values. 624200581Srdivacky DenseMap<PHINode *, PHINode *> CollisionMap; 625200581Srdivacky 626200581Srdivacky // Examine each PHI. 627200581Srdivacky for (BasicBlock::iterator I = BB->begin(); 628200581Srdivacky PHINode *PN = dyn_cast<PHINode>(I++); ) { 629200581Srdivacky // Compute a hash value on the operands. Instcombine will likely have sorted 630200581Srdivacky // them, which helps expose duplicates, but we have to check all the 631200581Srdivacky // operands to be safe in case instcombine hasn't run. 632200581Srdivacky uintptr_t Hash = 0; 633200581Srdivacky for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { 634200581Srdivacky // This hash algorithm is quite weak as hash functions go, but it seems 635200581Srdivacky // to do a good enough job for this particular purpose, and is very quick. 636200581Srdivacky Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I)); 637200581Srdivacky Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 638200581Srdivacky } 639200581Srdivacky // If we've never seen this hash value before, it's a unique PHI. 640200581Srdivacky std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair = 641200581Srdivacky HashMap.insert(std::make_pair(Hash, PN)); 642200581Srdivacky if (Pair.second) continue; 643200581Srdivacky // Otherwise it's either a duplicate or a hash collision. 644200581Srdivacky for (PHINode *OtherPN = Pair.first->second; ; ) { 645200581Srdivacky if (OtherPN->isIdenticalTo(PN)) { 646200581Srdivacky // A duplicate. Replace this PHI with its duplicate. 647200581Srdivacky PN->replaceAllUsesWith(OtherPN); 648200581Srdivacky PN->eraseFromParent(); 649200581Srdivacky Changed = true; 650200581Srdivacky break; 651200581Srdivacky } 652200581Srdivacky // A non-duplicate hash collision. 653200581Srdivacky DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN); 654200581Srdivacky if (I == CollisionMap.end()) { 655200581Srdivacky // Set this PHI to be the head of the linked list of colliding PHIs. 656200581Srdivacky PHINode *Old = Pair.first->second; 657200581Srdivacky Pair.first->second = PN; 658200581Srdivacky CollisionMap[PN] = Old; 659200581Srdivacky break; 660200581Srdivacky } 661200581Srdivacky // Procede to the next PHI in the list. 662200581Srdivacky OtherPN = I->second; 663200581Srdivacky } 664200581Srdivacky } 665200581Srdivacky 666200581Srdivacky return Changed; 667200581Srdivacky} 668