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