Local.cpp revision 17fd273512037da9838240b522619f4a6d2792b7
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/Constants.h" 17#include "llvm/Instructions.h" 18using namespace llvm; 19 20//===----------------------------------------------------------------------===// 21// Local constant propagation... 22// 23 24/// doConstantPropagation - If an instruction references constants, try to fold 25/// them together... 26/// 27bool llvm::doConstantPropagation(BasicBlock::iterator &II) { 28 if (Constant *C = ConstantFoldInstruction(II)) { 29 // Replaces all of the uses of a variable with uses of the constant. 30 II->replaceAllUsesWith(C); 31 32 // Remove the instruction from the basic block... 33 II = II->getParent()->getInstList().erase(II); 34 return true; 35 } 36 37 return false; 38} 39 40/// ConstantFoldInstruction - Attempt to constant fold the specified 41/// instruction. If successful, the constant result is returned, if not, null 42/// is returned. Note that this function can only fail when attempting to fold 43/// instructions like loads and stores, which have no constant expression form. 44/// 45Constant *llvm::ConstantFoldInstruction(Instruction *I) { 46 if (PHINode *PN = dyn_cast<PHINode>(I)) { 47 if (PN->getNumIncomingValues() == 0) 48 return Constant::getNullValue(PN->getType()); 49 50 Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0)); 51 if (Result == 0) return 0; 52 53 // Handle PHI nodes specially here... 54 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 55 if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN) 56 return 0; // Not all the same incoming constants... 57 58 // If we reach here, all incoming values are the same constant. 59 return Result; 60 } 61 62 Constant *Op0 = 0, *Op1 = 0; 63 switch (I->getNumOperands()) { 64 default: 65 case 2: 66 Op1 = dyn_cast<Constant>(I->getOperand(1)); 67 if (Op1 == 0) return 0; // Not a constant?, can't fold 68 case 1: 69 Op0 = dyn_cast<Constant>(I->getOperand(0)); 70 if (Op0 == 0) return 0; // Not a constant?, can't fold 71 break; 72 case 0: return 0; 73 } 74 75 if (isa<BinaryOperator>(I) || isa<ShiftInst>(I)) 76 return ConstantExpr::get(I->getOpcode(), Op0, Op1); 77 78 switch (I->getOpcode()) { 79 default: return 0; 80 case Instruction::Cast: 81 return ConstantExpr::getCast(Op0, I->getType()); 82 case Instruction::Select: 83 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2))) 84 return ConstantExpr::getSelect(Op0, Op1, Op2); 85 return 0; 86 case Instruction::GetElementPtr: 87 std::vector<Constant*> IdxList; 88 IdxList.reserve(I->getNumOperands()-1); 89 if (Op1) IdxList.push_back(Op1); 90 for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i) 91 if (Constant *C = dyn_cast<Constant>(I->getOperand(i))) 92 IdxList.push_back(C); 93 else 94 return 0; // Non-constant operand 95 return ConstantExpr::getGetElementPtr(Op0, IdxList); 96 } 97} 98 99// ConstantFoldTerminator - If a terminator instruction is predicated on a 100// constant value, convert it into an unconditional branch to the constant 101// destination. 102// 103bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 104 TerminatorInst *T = BB->getTerminator(); 105 106 // Branch - See if we are conditional jumping on constant 107 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 108 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 109 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 110 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 111 112 if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) { 113 // Are we branching on constant? 114 // YES. Change to unconditional branch... 115 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; 116 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; 117 118 //cerr << "Function: " << T->getParent()->getParent() 119 // << "\nRemoving branch from " << T->getParent() 120 // << "\n\nTo: " << OldDest << endl; 121 122 // Let the basic block know that we are letting go of it. Based on this, 123 // it will adjust it's PHI nodes. 124 assert(BI->getParent() && "Terminator not inserted in block!"); 125 OldDest->removePredecessor(BI->getParent()); 126 127 // Set the unconditional destination, and change the insn to be an 128 // unconditional branch. 129 BI->setUnconditionalDest(Destination); 130 return true; 131 } else if (Dest2 == Dest1) { // Conditional branch to same location? 132 // This branch matches something like this: 133 // br bool %cond, label %Dest, label %Dest 134 // and changes it into: br label %Dest 135 136 // Let the basic block know that we are letting go of one copy of it. 137 assert(BI->getParent() && "Terminator not inserted in block!"); 138 Dest1->removePredecessor(BI->getParent()); 139 140 // Change a conditional branch to unconditional. 141 BI->setUnconditionalDest(Dest1); 142 return true; 143 } 144 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 145 // If we are switching on a constant, we can convert the switch into a 146 // single branch instruction! 147 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 148 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 149 BasicBlock *DefaultDest = TheOnlyDest; 150 assert(TheOnlyDest == SI->getDefaultDest() && 151 "Default destination is not successor #0?"); 152 153 // Figure out which case it goes to... 154 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 155 // Found case matching a constant operand? 156 if (SI->getSuccessorValue(i) == CI) { 157 TheOnlyDest = SI->getSuccessor(i); 158 break; 159 } 160 161 // Check to see if this branch is going to the same place as the default 162 // dest. If so, eliminate it as an explicit compare. 163 if (SI->getSuccessor(i) == DefaultDest) { 164 // Remove this entry... 165 DefaultDest->removePredecessor(SI->getParent()); 166 SI->removeCase(i); 167 --i; --e; // Don't skip an entry... 168 continue; 169 } 170 171 // Otherwise, check to see if the switch only branches to one destination. 172 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 173 // destinations. 174 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 175 } 176 177 if (CI && !TheOnlyDest) { 178 // Branching on a constant, but not any of the cases, go to the default 179 // successor. 180 TheOnlyDest = SI->getDefaultDest(); 181 } 182 183 // If we found a single destination that we can fold the switch into, do so 184 // now. 185 if (TheOnlyDest) { 186 // Insert the new branch.. 187 new BranchInst(TheOnlyDest, SI); 188 BasicBlock *BB = SI->getParent(); 189 190 // Remove entries from PHI nodes which we no longer branch to... 191 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 192 // Found case matching a constant operand? 193 BasicBlock *Succ = SI->getSuccessor(i); 194 if (Succ == TheOnlyDest) 195 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 196 else 197 Succ->removePredecessor(BB); 198 } 199 200 // Delete the old switch... 201 BB->getInstList().erase(SI); 202 return true; 203 } else if (SI->getNumSuccessors() == 2) { 204 // Otherwise, we can fold this switch into a conditional branch 205 // instruction if it has only one non-default destination. 206 Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(), 207 SI->getSuccessorValue(1), "cond", SI); 208 // Insert the new branch... 209 new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 210 211 // Delete the old switch... 212 SI->getParent()->getInstList().erase(SI); 213 return true; 214 } 215 } 216 return false; 217} 218 219 220 221//===----------------------------------------------------------------------===// 222// Local dead code elimination... 223// 224 225bool llvm::isInstructionTriviallyDead(Instruction *I) { 226 return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I); 227} 228 229// dceInstruction - Inspect the instruction at *BBI and figure out if it's 230// [trivially] dead. If so, remove the instruction and update the iterator 231// to point to the instruction that immediately succeeded the original 232// instruction. 233// 234bool llvm::dceInstruction(BasicBlock::iterator &BBI) { 235 // Look for un"used" definitions... 236 if (isInstructionTriviallyDead(BBI)) { 237 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye 238 return true; 239 } 240 return false; 241} 242 243//===----------------------------------------------------------------------===// 244// PHI Instruction Simplification 245// 246 247/// hasConstantValue - If the specified PHI node always merges together the same 248/// value, return the value, otherwise return null. 249/// 250Value *llvm::hasConstantValue(PHINode *PN) { 251 // If the PHI node only has one incoming value, eliminate the PHI node... 252 if (PN->getNumIncomingValues() == 1) 253 return PN->getIncomingValue(0); 254 255 // Otherwise if all of the incoming values are the same for the PHI, replace 256 // the PHI node with the incoming value. 257 // 258 Value *InVal = 0; 259 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 260 if (PN->getIncomingValue(i) != PN) // Not the PHI node itself... 261 if (InVal && PN->getIncomingValue(i) != InVal) 262 return 0; // Not the same, bail out. 263 else 264 InVal = PN->getIncomingValue(i); 265 266 // The only case that could cause InVal to be null is if we have a PHI node 267 // that only has entries for itself. In this case, there is no entry into the 268 // loop, so kill the PHI. 269 // 270 if (InVal == 0) InVal = Constant::getNullValue(PN->getType()); 271 272 // All of the incoming values are the same, return the value now. 273 return InVal; 274} 275