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