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