Local.cpp revision 7d6c24cdbf41522818ec9ae7b8d3b624660853c1
1//===-- Local.cpp - Functions to perform local transformations ------------===// 2// 3// This family of functions perform various local transformations to the 4// program. 5// 6//===----------------------------------------------------------------------===// 7 8#include "llvm/Transforms/Utils/Local.h" 9#include "llvm/iTerminators.h" 10#include "llvm/iOperators.h" 11#include "llvm/ConstantHandling.h" 12 13//===----------------------------------------------------------------------===// 14// Local constant propagation... 15// 16 17// ConstantFoldInstruction - If an instruction references constants, try to fold 18// them together... 19// 20bool doConstantPropagation(BasicBlock::iterator &II) { 21 if (Constant *C = ConstantFoldInstruction(II)) { 22 // Replaces all of the uses of a variable with uses of the constant. 23 II->replaceAllUsesWith(C); 24 25 // Remove the instruction from the basic block... 26 II = II->getParent()->getInstList().erase(II); 27 return true; 28 } 29 30 return false; 31} 32 33// ConstantFoldTerminator - If a terminator instruction is predicated on a 34// constant value, convert it into an unconditional branch to the constant 35// destination. 36// 37bool ConstantFoldTerminator(BasicBlock *BB) { 38 TerminatorInst *T = BB->getTerminator(); 39 40 // Branch - See if we are conditional jumping on constant 41 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 42 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 43 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 44 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 45 46 if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) { 47 // Are we branching on constant? 48 // YES. Change to unconditional branch... 49 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; 50 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; 51 52 //cerr << "Function: " << T->getParent()->getParent() 53 // << "\nRemoving branch from " << T->getParent() 54 // << "\n\nTo: " << OldDest << endl; 55 56 // Let the basic block know that we are letting go of it. Based on this, 57 // it will adjust it's PHI nodes. 58 assert(BI->getParent() && "Terminator not inserted in block!"); 59 OldDest->removePredecessor(BI->getParent()); 60 61 // Set the unconditional destination, and change the insn to be an 62 // unconditional branch. 63 BI->setUnconditionalDest(Destination); 64 return true; 65 } else if (Dest2 == Dest1) { // Conditional branch to same location? 66 // This branch matches something like this: 67 // br bool %cond, label %Dest, label %Dest 68 // and changes it into: br label %Dest 69 70 // Let the basic block know that we are letting go of one copy of it. 71 assert(BI->getParent() && "Terminator not inserted in block!"); 72 Dest1->removePredecessor(BI->getParent()); 73 74 // Change a conditional branch to unconditional. 75 BI->setUnconditionalDest(Dest1); 76 return true; 77 } 78 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 79 // If we are switching on a constant, we can convert the switch into a 80 // single branch instruction! 81 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 82 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 83 BasicBlock *DefaultDest = TheOnlyDest; 84 assert(TheOnlyDest == SI->getDefaultDest() && 85 "Default destination is not successor #0?"); 86 87 // Figure out which case it goes to... 88 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 89 // Found case matching a constant operand? 90 if (SI->getSuccessorValue(i) == CI) { 91 TheOnlyDest = SI->getSuccessor(i); 92 break; 93 } 94 95 // Check to see if this branch is going to the same place as the default 96 // dest. If so, eliminate it as an explicit compare. 97 if (SI->getSuccessor(i) == DefaultDest) { 98 // Remove this entry... 99 DefaultDest->removePredecessor(SI->getParent()); 100 SI->removeCase(i); 101 --i; --e; // Don't skip an entry... 102 continue; 103 } 104 105 // Otherwise, check to see if the switch only branches to one destination. 106 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 107 // destinations. 108 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 109 } 110 111 if (CI && !TheOnlyDest) { 112 // Branching on a constant, but not any of the cases, go to the default 113 // successor. 114 TheOnlyDest = SI->getDefaultDest(); 115 } 116 117 // If we found a single destination that we can fold the switch into, do so 118 // now. 119 if (TheOnlyDest) { 120 // Insert the new branch.. 121 new BranchInst(TheOnlyDest, SI); 122 BasicBlock *BB = SI->getParent(); 123 124 // Remove entries from PHI nodes which we no longer branch to... 125 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 126 // Found case matching a constant operand? 127 BasicBlock *Succ = SI->getSuccessor(i); 128 if (Succ == TheOnlyDest) 129 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 130 else 131 Succ->removePredecessor(BB); 132 } 133 134 // Delete the old switch... 135 BB->getInstList().erase(SI); 136 return true; 137 } else if (SI->getNumSuccessors() == 2) { 138 // Otherwise, we can fold this switch into a conditional branch 139 // instruction if it has only one non-default destination. 140 Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(), 141 SI->getSuccessorValue(1), "cond", SI); 142 // Insert the new branch... 143 new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 144 145 // Delete the old switch... 146 SI->getParent()->getInstList().erase(SI); 147 return true; 148 } 149 } 150 return false; 151} 152 153 154 155//===----------------------------------------------------------------------===// 156// Local dead code elimination... 157// 158 159bool isInstructionTriviallyDead(Instruction *I) { 160 return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I); 161} 162 163// dceInstruction - Inspect the instruction at *BBI and figure out if it's 164// [trivially] dead. If so, remove the instruction and update the iterator 165// to point to the instruction that immediately succeeded the original 166// instruction. 167// 168bool dceInstruction(BasicBlock::iterator &BBI) { 169 // Look for un"used" definitions... 170 if (isInstructionTriviallyDead(BBI)) { 171 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye 172 return true; 173 } 174 return false; 175} 176