1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===-- Local.cpp - Functions to perform local transformations ------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This family of functions perform various local transformations to the 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// program. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/Local.h" 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Constants.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/GlobalAlias.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/GlobalVariable.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/DerivedTypes.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Instructions.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Intrinsics.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/IntrinsicInst.h" 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Metadata.h" 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Operator.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DenseMap.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallPtrSet.h" 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/DebugInfo.h" 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/DIBuilder.h" 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/Dominators.h" 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/InstructionSimplify.h" 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/ProfileInfo.h" 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/ValueTracking.h" 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetData.h" 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/CFG.h" 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/GetElementPtrTypeIterator.h" 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/IRBuilder.h" 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/MathExtras.h" 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/ValueHandle.h" 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Local constant propagation. 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ConstantFoldTerminator - If a terminator instruction is predicated on a 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// constant value, convert it into an unconditional branch to the constant 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// destination. This is a nontrivial operation because the successors of this 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// basic block must have their PHI nodes updated. 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// conditions and indirectbr addresses this might make dead if 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// DeleteDeadConditions is true. 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions) { 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TerminatorInst *T = BB->getTerminator(); 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IRBuilder<> Builder(T); 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Branch - See if we are conditional jumping on constant 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BI->isUnconditional()) return false; // Can't optimize uncond branch 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Dest1 = BI->getSuccessor(0); 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Dest2 = BI->getSuccessor(1); 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Are we branching on constant? 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // YES. Change to unconditional branch... 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //cerr << "Function: " << T->getParent()->getParent() 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // << "\nRemoving branch from " << T->getParent() 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // << "\n\nTo: " << OldDest << endl; 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Let the basic block know that we are letting go of it. Based on this, 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // it will adjust it's PHI nodes. 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OldDest->removePredecessor(BB); 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Replace the conditional branch with an unconditional one. 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Builder.CreateBr(Destination); 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BI->eraseFromParent(); 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Dest2 == Dest1) { // Conditional branch to same location? 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This branch matches something like this: 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // br bool %cond, label %Dest, label %Dest 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and changes it into: br label %Dest 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Let the basic block know that we are letting go of one copy of it. 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(BI->getParent() && "Terminator not inserted in block!"); 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Dest1->removePredecessor(BI->getParent()); 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Replace the conditional branch with an unconditional one. 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Builder.CreateBr(Dest1); 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *Cond = BI->getCondition(); 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BI->eraseFromParent(); 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DeleteDeadConditions) 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RecursivelyDeleteTriviallyDeadInstructions(Cond); 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we are switching on a constant, we can convert the switch into a 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // single branch instruction! 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *DefaultDest = TheOnlyDest; 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(TheOnlyDest == SI->getDefaultDest() && 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Default destination is not successor #0?"); 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Figure out which case it goes to. 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Found case matching a constant operand? 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SI->getSuccessorValue(i) == CI) { 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheOnlyDest = SI->getSuccessor(i); 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if this branch is going to the same place as the default 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // dest. If so, eliminate it as an explicit compare. 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SI->getSuccessor(i) == DefaultDest) { 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove this entry. 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DefaultDest->removePredecessor(SI->getParent()); 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SI->removeCase(i); 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --i; --e; // Don't skip an entry... 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, check to see if the switch only branches to one destination. 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We do this by reseting "TheOnlyDest" to null when we find two non-equal 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // destinations. 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CI && !TheOnlyDest) { 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Branching on a constant, but not any of the cases, go to the default 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // successor. 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheOnlyDest = SI->getDefaultDest(); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we found a single destination that we can fold the switch into, do so 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // now. 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TheOnlyDest) { 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert the new branch. 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Builder.CreateBr(TheOnlyDest); 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *BB = SI->getParent(); 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove entries from PHI nodes which we no longer branch to... 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Found case matching a constant operand? 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Succ = SI->getSuccessor(i); 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Succ == TheOnlyDest) 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Succ->removePredecessor(BB); 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Delete the old switch. 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *Cond = SI->getCondition(); 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SI->eraseFromParent(); 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DeleteDeadConditions) 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RecursivelyDeleteTriviallyDeadInstructions(Cond); 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SI->getNumSuccessors() == 2) { 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, we can fold this switch into a conditional branch 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instruction if it has only one non-default destination. 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SI->getSuccessorValue(1), "cond"); 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert the new branch. 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Builder.CreateCondBr(Cond, SI->getSuccessor(1), SI->getSuccessor(0)); 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Delete the old switch. 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SI->eraseFromParent(); 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // indirectbr blockaddress(@F, @BB) -> br label @BB 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BlockAddress *BA = 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *TheOnlyDest = BA->getBasicBlock(); 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert the new branch. 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Builder.CreateBr(TheOnlyDest); 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (IBI->getDestination(i) == TheOnlyDest) 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheOnlyDest = 0; 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman IBI->getDestination(i)->removePredecessor(IBI->getParent()); 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *Address = IBI->getAddress(); 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman IBI->eraseFromParent(); 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DeleteDeadConditions) 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RecursivelyDeleteTriviallyDeadInstructions(Address); 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we didn't find our destination in the IBI successor list, then we 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // have undefined behavior. Replace the unconditional branch with an 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 'unreachable' instruction. 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TheOnlyDest) { 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->getTerminator()->eraseFromParent(); 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new UnreachableInst(BB->getContext(), BB); 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Local dead code elimination. 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// isInstructionTriviallyDead - Return true if the result produced by the 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// instruction is not used, and the instruction has no side effects. 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool llvm::isInstructionTriviallyDead(Instruction *I) { 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We don't want the landingpad instruction removed by anything this general. 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<LandingPadInst>(I)) 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We don't want debug info removed by anything this general, unless 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // debug info is empty. 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DDI->getAddress()) 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 23919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DVI->getValue()) 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 24419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!I->mayHaveSideEffects()) return true; 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Special case intrinsics that "may have side effects" but can be deleted 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // when dead. 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Safe to delete llvm.stacksave if dead. 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (II->getIntrinsicID() == Intrinsic::stacksave) 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Lifetime intrinsics are dead when their right-hand is undef. 25619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (II->getIntrinsicID() == Intrinsic::lifetime_start || 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman II->getIntrinsicID() == Intrinsic::lifetime_end) 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return isa<UndefValue>(II->getArgOperand(1)); 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// trivially dead instruction, delete it. If that makes any of its operands 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// trivially dead, delete them too, recursively. Return true if any 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// instructions were deleted. 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *I = dyn_cast<Instruction>(V); 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!I || !I->use_empty() || !isInstructionTriviallyDead(I)) 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<Instruction*, 16> DeadInsts; 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DeadInsts.push_back(I); 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I = DeadInsts.pop_back_val(); 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Null out all of the instruction's operands to see if any operand becomes 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // dead as we go. 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *OpV = I->getOperand(i); 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setOperand(i, 0); 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!OpV->use_empty()) continue; 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the operand is an instruction that became dead as we nulled out the 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // operand, and if it is 'trivially' dead, delete it in a future loop 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // iteration. 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isInstructionTriviallyDead(OpI)) 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DeadInsts.push_back(OpI); 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->eraseFromParent(); 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while (!DeadInsts.empty()); 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// areAllUsesEqual - Check whether the uses of a value are all the same. 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// This is similar to Instruction::hasOneUse() except this will also return 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// true when there are no uses or multiple uses that all refer to the same 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// value. 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic bool areAllUsesEqual(Instruction *I) { 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value::use_iterator UI = I->use_begin(); 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value::use_iterator UE = I->use_end(); 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UI == UE) 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman User *TheUse = *UI; 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (++UI; UI != UE; ++UI) { 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (*UI != TheUse) 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// dead PHI node, due to being a def-use chain of single-use nodes that 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// either forms a cycle or is terminated by a trivially dead instruction, 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// delete it. If that makes any of its operands trivially dead, delete them 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// too, recursively. Return true if a change was made. 32319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) { 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<Instruction*, 4> Visited; 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I = cast<Instruction>(*I->use_begin())) { 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->use_empty()) 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return RecursivelyDeleteTriviallyDeadInstructions(I); 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we find an instruction more than once, we're on a cycle that 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // won't prove fruitful. 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Visited.insert(I)) { 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Break the cycle and delete the instruction and its operands. 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I->replaceAllUsesWith(UndefValue::get(I->getType())); 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)RecursivelyDeleteTriviallyDeadInstructions(I); 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// simplify any instructions in it and recursively delete dead instructions. 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// This returns true if it changed the code, note that it can delete 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// instructions in other blocks as well in this block. 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const TargetData *TD) { 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MadeChange = false; 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *Inst = BI++; 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Value *V = SimplifyInstruction(Inst, TD)) { 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman WeakVH BIHandle(BI); 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ReplaceAndSimplifyAllUses(Inst, V, TD); 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange = true; 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BIHandle != BI) 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BI = BB->begin(); 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 36019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Inst->isTerminator()) 36219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 36319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 36419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman WeakVH BIHandle(BI); 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst); 36619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BIHandle != BI) 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BI = BB->begin(); 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MadeChange; 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Control Flow Graph Restructuring. 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// method is called when we're about to delete Pred as a predecessor of BB. If 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// nodes that collapse into identity values. For example, if we have: 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// x = phi(1, 0, 0, 0) 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// y = and x, z 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// .. and delete the predecessor corresponding to the '1', this will attempt to 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// recursively fold the and to 0. 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TargetData *TD) { 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This only adjusts blocks with PHI nodes. 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isa<PHINode>(BB->begin())) 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove the entries for Pred from the PHI nodes in BB, but do not simplify 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // them down. This will leave us with single entry phi nodes and other phis 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // that can be removed. 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->removePredecessor(Pred, true); 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman WeakVH PhiIt = &BB->front(); 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) { 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt)); 40219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *PNV = SimplifyInstruction(PN, TD); 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PNV == 0) continue; 40519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we're able to simplify the phi to a single value, substitute the new 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // value into all of its uses. 40819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(PNV != PN && "SimplifyInstruction broken!"); 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *OldPhiIt = PhiIt; 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ReplaceAndSimplifyAllUses(PN, PNV, TD); 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If recursive simplification ended up deleting the next PHI node we would 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // iterate to, then our iterator is invalid, restart scanning from the top 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // of the block. 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PhiIt != OldPhiIt) PhiIt = &BB->front(); 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// predecessor is known to have one successor (DestBB!). Eliminate the edge 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// between them, moving the instructions in the predecessor into DestBB and 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// deleting the predecessor block. 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If BB has single-entry PHI nodes, fold them. 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *NewVal = PN->getIncomingValue(0); 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Replace self referencing PHI with undef, it must be dead. 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->replaceAllUsesWith(NewVal); 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->eraseFromParent(); 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *PredBB = DestBB->getSinglePredecessor(); 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(PredBB && "Block doesn't have a single predecessor!"); 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Zap anything that took the address of DestBB. Not doing this will give the 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // address an invalid value. 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DestBB->hasAddressTaken()) { 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockAddress *BA = BlockAddress::get(DestBB); 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Constant *Replacement = 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1); 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BA->getType())); 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BA->destroyConstant(); 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Anything that branched to PredBB now branches to DestBB. 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PredBB->replaceAllUsesWith(DestBB); 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 45319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Splice all the instructions from PredBB to DestBB. 45419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PredBB->getTerminator()->eraseFromParent(); 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (P) { 45819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); 45919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DT) { 46019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); 46119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DT->changeImmediateDominator(DestBB, PredBBIDom); 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DT->eraseNode(PredBB); 46319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PI) { 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PI->replaceAllUses(PredBB, DestBB); 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PI->removeEdge(ProfileInfo::getEdge(PredBB, DestBB)); 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Nuke BB. 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PredBB->eraseFromParent(); 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// almost-empty BB ending in an unconditional branch to Succ, into succ. 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Assumption: Succ is the single successor for BB. 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << Succ->getName() << "\n"); 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Shortcut, if there is only a single predecessor it must be BB and merging 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // is always safe 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Succ->getSinglePredecessor()) return true; 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make a list of the predecessors of BB 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef SmallPtrSet<BasicBlock*, 16> BlockSet; 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockSet BBPreds(pred_begin(BB), pred_end(BB)); 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Use that list to make another list of common predecessors of BB and Succ 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockSet CommonPreds; 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PI != PE; ++PI) { 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *P = *PI; 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BBPreds.count(P)) 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CommonPreds.insert(P); 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Shortcut, if there are no common predecessors, merging is always safe 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CommonPreds.empty()) 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Look at all the phi nodes in Succ, to see if they present a conflict when 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // merging these blocks 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *PN = cast<PHINode>(I); 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the incoming value from BB is again a PHINode in 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // BB which has the same incoming value for *PI as PN does, we can 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // merge the phi nodes and then the blocks can still be merged 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BBPN && BBPN->getParent() == BB) { 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PI != PE; PI++) { 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BBPN->getIncomingValueForBlock(*PI) 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman != PN->getIncomingValueForBlock(*PI)) { 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << Succ->getName() << " is conflicting with " 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << BBPN->getName() << " with regard to common predecessor " 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << (*PI)->getName() << "\n"); 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value* Val = PN->getIncomingValueForBlock(BB); 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PI != PE; PI++) { 530894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // See if the incoming value for the common predecessor is equal to the 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // one for BB, in which case this phi node will not prevent the merging 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // of the block. 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Val != PN->getIncomingValueForBlock(*PI)) { 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << Succ->getName() << " is conflicting with regard to common " 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << "predecessor " << (*PI)->getName() << "\n"); 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 542894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 543894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 545894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// unconditional branch, and contains no instructions other than PHI nodes, 54819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// potential side-effect free intrinsics and the branch. If possible, 54919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// eliminate BB by rewriting all the predecessors to branch to the successor 55019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// block and return true. If we can't transform, return false. 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { 55219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(BB != &BB->getParent()->getEntryBlock() && 55319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); 55419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 555894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We can't eliminate infinite loops. 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BB == Succ) return false; 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if merging these blocks would cause conflicts for any of the 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // phi nodes in BB or Succ. If not, we can safely merge. 561894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check for cases where Succ has multiple predecessors and a PHI node in BB 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // has uses which will not disappear when the PHI nodes are merged. It is 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // possible to handle such cases, but difficult: it requires checking whether 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // BB dominates Succ, which is non-trivial to calculate in the case where 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Succ has multiple predecessors. Also, it requires checking whether 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // constructing the necessary self-referential PHI node doesn't intoduce any 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // conflicts; this isn't too difficult, but the previous code for doing this 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // was incorrect. 571894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that if this check finds a live use, BB dominates Succ, so BB is 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // something like a loop pre-header (or rarely, a part of an irreducible CFG); 574894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // folding the branch isn't profitable in that case anyway. 575894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Succ->getSinglePredecessor()) { 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock::iterator BBI = BB->begin(); 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (isa<PHINode>(*BBI)) { 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ++UI) { 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PHINode* PN = dyn_cast<PHINode>(*UI)) { 581894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PN->getIncomingBlock(UI) != BB) 582894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 583894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 586894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++BBI; 588894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 589894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 590894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 591894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); 592894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 593894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<PHINode>(Succ->begin())) { 594894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If there is more than one pred of succ, and there are PHI nodes in 595894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the successor, then we need to add incoming edges for the PHI nodes 596894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 597894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SmallVector<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 598894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 599894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Loop over all of the PHI nodes in the successor of BB. 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 601894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *PN = cast<PHINode>(I); 602894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *OldVal = PN->removeIncomingValue(BB, false); 603894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(OldVal && "No entry in PHI for Pred BB!"); 604894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 605894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this incoming value is one of the PHI nodes in BB, the new entries 606894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // in the PHI node are the entries from the old PHI. 607894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 608894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *OldValPN = cast<PHINode>(OldVal); 609894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 610894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that, since we are merging phi nodes and BB and Succ might 611894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // have common predecessors, we could end up with a phi node with 612894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // identical incoming branches. This will be cleaned up later (and 613894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // will trigger asserts if we try to clean it up now, without also 614894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // simplifying the corresponding conditional branch). 615894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->addIncoming(OldValPN->getIncomingValue(i), 616894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OldValPN->getIncomingBlock(i)); 617894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 618894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add an incoming value for each of the new incoming values. 619894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) 620894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->addIncoming(OldVal, BBPreds[i]); 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Succ->getSinglePredecessor()) { 62619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // BB is the only predecessor of Succ, so Succ will end up with exactly 62719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the same predecessors BB had. 62819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 62919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Copy over any phi, debug or lifetime instruction. 63019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BB->getTerminator()->eraseFromParent(); 63119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList()); 63219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 63319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 634894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(PN->use_empty() && "There shouldn't be any uses here!"); 636894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->eraseFromParent(); 637894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 638894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 639894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Everything that jumped to BB now goes to Succ. 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->replaceAllUsesWith(Succ); 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Succ->hasName()) Succ->takeName(BB); 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BB->eraseFromParent(); // Delete the old basic block. 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 646894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 647894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 648894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// nodes in this block. This doesn't try to be clever about PHI nodes 649894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// which differ only in the order of the incoming values, but instcombine 650894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// orders them so it usually won't matter. 651894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 653894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Changed = false; 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This implementation doesn't currently consider undef operands 65619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // specially. Theoretically, two phis which are identical except for 657894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // one having an undef where the other doesn't could be collapsed. 658894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 659894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Map from PHI hash values to PHI nodes. If multiple PHIs have 660894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the same hash value, the element is the first PHI in the 661894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // linked list in CollisionMap. 662894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<uintptr_t, PHINode *> HashMap; 663894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 664894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Maintain linked lists of PHI nodes with common hash values. 665894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<PHINode *, PHINode *> CollisionMap; 666894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 667894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Examine each PHI. 668894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BasicBlock::iterator I = BB->begin(); 669894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *PN = dyn_cast<PHINode>(I++); ) { 670894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compute a hash value on the operands. Instcombine will likely have sorted 671894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // them, which helps expose duplicates, but we have to check all the 672894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // operands to be safe in case instcombine hasn't run. 673894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman uintptr_t Hash = 0; 67419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This hash algorithm is quite weak as hash functions go, but it seems 67519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // to do a good enough job for this particular purpose, and is very quick. 676894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { 677894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I)); 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 68019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end(); 68119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I != E; ++I) { 68219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I)); 68319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 68419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 68519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Avoid colliding with the DenseMap sentinels ~0 and ~0-1. 68619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Hash >>= 1; 687894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we've never seen this hash value before, it's a unique PHI. 688894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair = 689894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman HashMap.insert(std::make_pair(Hash, PN)); 690894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Pair.second) continue; 691894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise it's either a duplicate or a hash collision. 692894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (PHINode *OtherPN = Pair.first->second; ; ) { 693894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (OtherPN->isIdenticalTo(PN)) { 694894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A duplicate. Replace this PHI with its duplicate. 695894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->replaceAllUsesWith(OtherPN); 696894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->eraseFromParent(); 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 699894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 700894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A non-duplicate hash collision. 701894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN); 702894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I == CollisionMap.end()) { 703894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Set this PHI to be the head of the linked list of colliding PHIs. 704894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PHINode *Old = Pair.first->second; 705894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Pair.first->second = PN; 706894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CollisionMap[PN] = Old; 707894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 708894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 709894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Procede to the next PHI in the list. 710894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OtherPN = I->second; 711894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 712894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 713894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 714894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Changed; 715894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 71619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 71719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// enforceKnownAlignment - If the specified pointer points to an object that 71819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// we control, modify the object's alignment to PrefAlign. This isn't 71919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// often possible though. If alignment is important, a more reliable approach 72019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// is to simply align all global variables and allocation instructions to 72119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// their preferred alignment from the beginning. 72219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 72319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic unsigned enforceKnownAlignment(Value *V, unsigned Align, 72419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned PrefAlign, const TargetData *TD) { 72519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = V->stripPointerCasts(); 72619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 72719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 72819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the preferred alignment is greater than the natural stack alignment 72919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // then don't round up. This avoids dynamic stack realignment. 73019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TD && TD->exceedsNaturalStackAlignment(PrefAlign)) 73119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Align; 73219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If there is a requested alignment and if this is an alloca, round up. 73319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AI->getAlignment() >= PrefAlign) 73419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return AI->getAlignment(); 73519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AI->setAlignment(PrefAlign); 73619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return PrefAlign; 73719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 73819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 73919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 74019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If there is a large requested alignment and we can, bump up the alignment 74119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // of the global. 74219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GV->isDeclaration()) return Align; 74319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 74419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (GV->getAlignment() >= PrefAlign) 74519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return GV->getAlignment(); 74619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We can only increase the alignment of the global if it has no alignment 74719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // specified or if it is not assigned a section. If it is assigned a 74819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // section, the global could be densely packed with other objects in the 74919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // section, increasing the alignment could cause padding issues. 75019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!GV->hasSection() || GV->getAlignment() == 0) 75119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman GV->setAlignment(PrefAlign); 75219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return GV->getAlignment(); 75319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 75419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 75519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Align; 75619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 75719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 75819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 75919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// we can determine, return it, otherwise return 0. If PrefAlign is specified, 76019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// and it is more than the alignment of the ultimate object, see if we can 76119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// increase the alignment of the ultimate object, making this check succeed. 76219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanunsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 76319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetData *TD) { 76419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(V->getType()->isPointerTy() && 76519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "getOrEnforceKnownAlignment expects a pointer!"); 76619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned BitWidth = TD ? TD->getPointerSizeInBits() : 64; 76719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman APInt Mask = APInt::getAllOnesValue(BitWidth); 76819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 76919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD); 77019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned TrailZ = KnownZero.countTrailingOnes(); 77119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 77219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Avoid trouble with rediculously large TrailZ values, such as 77319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // those computed from a null pointer. 77419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 77519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 77619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Align = 1u << std::min(BitWidth - 1, TrailZ); 77719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 77819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // LLVM doesn't support alignments larger than this currently. 77919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Align = std::min(Align, +Value::MaximumAlignment); 78019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 78119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PrefAlign > Align) 78219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Align = enforceKnownAlignment(V, Align, PrefAlign, TD); 78319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 78419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We don't need to make any adjustment. 78519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Align; 78619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 78719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 78819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman///===---------------------------------------------------------------------===// 78919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Dbg Intrinsic utilities 79019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 79119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 79219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value 79319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// that has an associated llvm.dbg.decl intrinsic. 79419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 79519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman StoreInst *SI, DIBuilder &Builder) { 79619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DIVariable DIVar(DDI->getVariable()); 79719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DIVar.Verify()) 79819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 79919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 80019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *DbgVal = NULL; 80119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If an argument is zero extended then use argument directly. The ZExt 80219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // may be zapped by an optimization pass in future. 80319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Argument *ExtendedArg = NULL; 80419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0))) 80519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0)); 80619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0))) 80719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0)); 80819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ExtendedArg) 80919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, SI); 81019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 81119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, SI); 81219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 81319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Propagate any debug metadata from the store onto the dbg.value. 81419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DebugLoc SIDL = SI->getDebugLoc(); 81519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!SIDL.isUnknown()) 81619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgVal->setDebugLoc(SIDL); 81719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise propagate debug metadata from dbg.declare. 81819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 81919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgVal->setDebugLoc(DDI->getDebugLoc()); 82019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 82119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 82219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 82319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value 82419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// that has an associated llvm.dbg.decl intrinsic. 82519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 82619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoadInst *LI, DIBuilder &Builder) { 82719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DIVariable DIVar(DDI->getVariable()); 82819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DIVar.Verify()) 82919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 83019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 83119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *DbgVal = 83219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, 83319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DIVar, LI); 83419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 83519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Propagate any debug metadata from the store onto the dbg.value. 83619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DebugLoc LIDL = LI->getDebugLoc(); 83719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LIDL.isUnknown()) 83819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgVal->setDebugLoc(LIDL); 83919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise propagate debug metadata from dbg.declare. 84019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 84119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgVal->setDebugLoc(DDI->getDebugLoc()); 84219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 84319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 84419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 84519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 84619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// of llvm.dbg.value intrinsics. 84719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool llvm::LowerDbgDeclare(Function &F) { 84819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DIBuilder DIB(*F.getParent()); 84919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<DbgDeclareInst *, 4> Dbgs; 85019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 85119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) { 85219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(BI)) 85319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Dbgs.push_back(DDI); 85419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 85519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Dbgs.empty()) 85619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 85719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 85819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SmallVector<DbgDeclareInst *, 4>::iterator I = Dbgs.begin(), 85919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = Dbgs.end(); I != E; ++I) { 86019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DbgDeclareInst *DDI = *I; 86119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress())) { 86219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool RemoveDDI = true; 86319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 86419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UI != E; ++UI) 86519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 86619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 86719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) 86819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ConvertDebugDeclareToDebugValue(DDI, LI, DIB); 86919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 87019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RemoveDDI = false; 87119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (RemoveDDI) 87219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DDI->eraseFromParent(); 87319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 87419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 87519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 87619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 87719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 87819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the 87919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// alloca 'V', if any. 88019bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanDbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) { 88119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), V)) 88219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Value::use_iterator UI = DebugNode->use_begin(), 88319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = DebugNode->use_end(); UI != E; ++UI) 88419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(*UI)) 88519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DDI; 88619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 88719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return 0; 88819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 889