Local.cpp revision 25b8390bf23ed35640664d244951d684c5a7b132
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 } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 61 if (Function *F = CI->getCalledFunction()) 62 if (canConstantFoldCallTo(F)) { 63 std::vector<Constant*> Args; 64 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) 65 if (Constant *Op = dyn_cast<Constant>(CI->getOperand(i))) 66 Args.push_back(Op); 67 else 68 return 0; 69 return ConstantFoldCall(F, Args); 70 } 71 return 0; 72 } 73 74 Constant *Op0 = 0, *Op1 = 0; 75 switch (I->getNumOperands()) { 76 default: 77 case 2: 78 Op1 = dyn_cast<Constant>(I->getOperand(1)); 79 if (Op1 == 0) return 0; // Not a constant?, can't fold 80 case 1: 81 Op0 = dyn_cast<Constant>(I->getOperand(0)); 82 if (Op0 == 0) return 0; // Not a constant?, can't fold 83 break; 84 case 0: return 0; 85 } 86 87 if (isa<BinaryOperator>(I) || isa<ShiftInst>(I)) 88 return ConstantExpr::get(I->getOpcode(), Op0, Op1); 89 90 switch (I->getOpcode()) { 91 default: return 0; 92 case Instruction::Cast: 93 return ConstantExpr::getCast(Op0, I->getType()); 94 case Instruction::Select: 95 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2))) 96 return ConstantExpr::getSelect(Op0, Op1, Op2); 97 return 0; 98 case Instruction::GetElementPtr: 99 std::vector<Constant*> IdxList; 100 IdxList.reserve(I->getNumOperands()-1); 101 if (Op1) IdxList.push_back(Op1); 102 for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i) 103 if (Constant *C = dyn_cast<Constant>(I->getOperand(i))) 104 IdxList.push_back(C); 105 else 106 return 0; // Non-constant operand 107 return ConstantExpr::getGetElementPtr(Op0, IdxList); 108 } 109} 110 111// ConstantFoldTerminator - If a terminator instruction is predicated on a 112// constant value, convert it into an unconditional branch to the constant 113// destination. 114// 115bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 116 TerminatorInst *T = BB->getTerminator(); 117 118 // Branch - See if we are conditional jumping on constant 119 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 120 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 121 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 122 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 123 124 if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) { 125 // Are we branching on constant? 126 // YES. Change to unconditional branch... 127 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; 128 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; 129 130 //cerr << "Function: " << T->getParent()->getParent() 131 // << "\nRemoving branch from " << T->getParent() 132 // << "\n\nTo: " << OldDest << endl; 133 134 // Let the basic block know that we are letting go of it. Based on this, 135 // it will adjust it's PHI nodes. 136 assert(BI->getParent() && "Terminator not inserted in block!"); 137 OldDest->removePredecessor(BI->getParent()); 138 139 // Set the unconditional destination, and change the insn to be an 140 // unconditional branch. 141 BI->setUnconditionalDest(Destination); 142 return true; 143 } else if (Dest2 == Dest1) { // Conditional branch to same location? 144 // This branch matches something like this: 145 // br bool %cond, label %Dest, label %Dest 146 // and changes it into: br label %Dest 147 148 // Let the basic block know that we are letting go of one copy of it. 149 assert(BI->getParent() && "Terminator not inserted in block!"); 150 Dest1->removePredecessor(BI->getParent()); 151 152 // Change a conditional branch to unconditional. 153 BI->setUnconditionalDest(Dest1); 154 return true; 155 } 156 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 157 // If we are switching on a constant, we can convert the switch into a 158 // single branch instruction! 159 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 160 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 161 BasicBlock *DefaultDest = TheOnlyDest; 162 assert(TheOnlyDest == SI->getDefaultDest() && 163 "Default destination is not successor #0?"); 164 165 // Figure out which case it goes to... 166 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 167 // Found case matching a constant operand? 168 if (SI->getSuccessorValue(i) == CI) { 169 TheOnlyDest = SI->getSuccessor(i); 170 break; 171 } 172 173 // Check to see if this branch is going to the same place as the default 174 // dest. If so, eliminate it as an explicit compare. 175 if (SI->getSuccessor(i) == DefaultDest) { 176 // Remove this entry... 177 DefaultDest->removePredecessor(SI->getParent()); 178 SI->removeCase(i); 179 --i; --e; // Don't skip an entry... 180 continue; 181 } 182 183 // Otherwise, check to see if the switch only branches to one destination. 184 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 185 // destinations. 186 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 187 } 188 189 if (CI && !TheOnlyDest) { 190 // Branching on a constant, but not any of the cases, go to the default 191 // successor. 192 TheOnlyDest = SI->getDefaultDest(); 193 } 194 195 // If we found a single destination that we can fold the switch into, do so 196 // now. 197 if (TheOnlyDest) { 198 // Insert the new branch.. 199 new BranchInst(TheOnlyDest, SI); 200 BasicBlock *BB = SI->getParent(); 201 202 // Remove entries from PHI nodes which we no longer branch to... 203 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 204 // Found case matching a constant operand? 205 BasicBlock *Succ = SI->getSuccessor(i); 206 if (Succ == TheOnlyDest) 207 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 208 else 209 Succ->removePredecessor(BB); 210 } 211 212 // Delete the old switch... 213 BB->getInstList().erase(SI); 214 return true; 215 } else if (SI->getNumSuccessors() == 2) { 216 // Otherwise, we can fold this switch into a conditional branch 217 // instruction if it has only one non-default destination. 218 Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(), 219 SI->getSuccessorValue(1), "cond", SI); 220 // Insert the new branch... 221 new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 222 223 // Delete the old switch... 224 SI->getParent()->getInstList().erase(SI); 225 return true; 226 } 227 } 228 return false; 229} 230 231/// canConstantFoldCallTo - Return true if its even possible to fold a call to 232/// the specified function. 233bool llvm::canConstantFoldCallTo(Function *F) { 234 const std::string &Name = F->getName(); 235 return Name == "sin" || Name == "cos" || Name == "tan" || Name == "sqrt"; 236} 237 238/// ConstantFoldCall - Attempt to constant fold a call to the specified function 239/// with the specified arguments, returning null if unsuccessful. 240Constant *llvm::ConstantFoldCall(Function *F, 241 const std::vector<Constant*> &Operands) { 242 const std::string &Name = F->getName(); 243 const Type *Ty = F->getReturnType(); 244 245 if (Name == "sin") { 246 if (Operands.size() == 1) 247 if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0])) 248 return ConstantFP::get(Ty, sin(CFP->getValue())); 249 250 } else if (Name == "cos") { 251 if (Operands.size() == 1) 252 if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0])) 253 return ConstantFP::get(Ty, cos(CFP->getValue())); 254 255 } else if (Name == "tan") { 256 if (Operands.size() == 1) 257 if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0])) 258 return ConstantFP::get(Ty, tan(CFP->getValue())); 259 260 } else if (Name == "sqrt") { 261 if (Operands.size() == 1) 262 if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0])) 263 if (CFP->getValue() >= 0) 264 return ConstantFP::get(Ty, sqrt(CFP->getValue())); 265 } 266 return 0; 267} 268 269 270 271 272//===----------------------------------------------------------------------===// 273// Local dead code elimination... 274// 275 276bool llvm::isInstructionTriviallyDead(Instruction *I) { 277 return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I); 278} 279 280// dceInstruction - Inspect the instruction at *BBI and figure out if it's 281// [trivially] dead. If so, remove the instruction and update the iterator 282// to point to the instruction that immediately succeeded the original 283// instruction. 284// 285bool llvm::dceInstruction(BasicBlock::iterator &BBI) { 286 // Look for un"used" definitions... 287 if (isInstructionTriviallyDead(BBI)) { 288 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye 289 return true; 290 } 291 return false; 292} 293 294//===----------------------------------------------------------------------===// 295// PHI Instruction Simplification 296// 297 298/// hasConstantValue - If the specified PHI node always merges together the same 299/// value, return the value, otherwise return null. 300/// 301Value *llvm::hasConstantValue(PHINode *PN) { 302 // If the PHI node only has one incoming value, eliminate the PHI node... 303 if (PN->getNumIncomingValues() == 1) 304 return PN->getIncomingValue(0); 305 306 // Otherwise if all of the incoming values are the same for the PHI, replace 307 // the PHI node with the incoming value. 308 // 309 Value *InVal = 0; 310 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 311 if (PN->getIncomingValue(i) != PN) // Not the PHI node itself... 312 if (InVal && PN->getIncomingValue(i) != InVal) 313 return 0; // Not the same, bail out. 314 else 315 InVal = PN->getIncomingValue(i); 316 317 // The only case that could cause InVal to be null is if we have a PHI node 318 // that only has entries for itself. In this case, there is no entry into the 319 // loop, so kill the PHI. 320 // 321 if (InVal == 0) InVal = Constant::getNullValue(PN->getType()); 322 323 // All of the incoming values are the same, return the value now. 324 return InVal; 325} 326