LLVM API Documentation
00001 //===-- Local.cpp - Functions to perform local transformations ------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This family of functions perform various local transformations to the 00011 // program. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Support/MathExtras.h" 00016 #include "llvm/Transforms/Utils/Local.h" 00017 #include "llvm/Constants.h" 00018 #include "llvm/Instructions.h" 00019 #include "llvm/Intrinsics.h" 00020 #include <cerrno> 00021 #include <cmath> 00022 using namespace llvm; 00023 00024 //===----------------------------------------------------------------------===// 00025 // Local constant propagation... 00026 // 00027 00028 /// doConstantPropagation - If an instruction references constants, try to fold 00029 /// them together... 00030 /// 00031 bool llvm::doConstantPropagation(BasicBlock::iterator &II) { 00032 if (Constant *C = ConstantFoldInstruction(II)) { 00033 // Replaces all of the uses of a variable with uses of the constant. 00034 II->replaceAllUsesWith(C); 00035 00036 // Remove the instruction from the basic block... 00037 II = II->getParent()->getInstList().erase(II); 00038 return true; 00039 } 00040 00041 return false; 00042 } 00043 00044 /// ConstantFoldInstruction - Attempt to constant fold the specified 00045 /// instruction. If successful, the constant result is returned, if not, null 00046 /// is returned. Note that this function can only fail when attempting to fold 00047 /// instructions like loads and stores, which have no constant expression form. 00048 /// 00049 Constant *llvm::ConstantFoldInstruction(Instruction *I) { 00050 if (PHINode *PN = dyn_cast<PHINode>(I)) { 00051 if (PN->getNumIncomingValues() == 0) 00052 return Constant::getNullValue(PN->getType()); 00053 00054 Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0)); 00055 if (Result == 0) return 0; 00056 00057 // Handle PHI nodes specially here... 00058 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 00059 if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN) 00060 return 0; // Not all the same incoming constants... 00061 00062 // If we reach here, all incoming values are the same constant. 00063 return Result; 00064 } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 00065 if (Function *F = CI->getCalledFunction()) 00066 if (canConstantFoldCallTo(F)) { 00067 std::vector<Constant*> Args; 00068 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) 00069 if (Constant *Op = dyn_cast<Constant>(CI->getOperand(i))) 00070 Args.push_back(Op); 00071 else 00072 return 0; 00073 return ConstantFoldCall(F, Args); 00074 } 00075 return 0; 00076 } 00077 00078 Constant *Op0 = 0, *Op1 = 0; 00079 switch (I->getNumOperands()) { 00080 default: 00081 case 2: 00082 Op1 = dyn_cast<Constant>(I->getOperand(1)); 00083 if (Op1 == 0) return 0; // Not a constant?, can't fold 00084 case 1: 00085 Op0 = dyn_cast<Constant>(I->getOperand(0)); 00086 if (Op0 == 0) return 0; // Not a constant?, can't fold 00087 break; 00088 case 0: return 0; 00089 } 00090 00091 if (isa<BinaryOperator>(I) || isa<ShiftInst>(I)) 00092 return ConstantExpr::get(I->getOpcode(), Op0, Op1); 00093 00094 switch (I->getOpcode()) { 00095 default: return 0; 00096 case Instruction::Cast: 00097 return ConstantExpr::getCast(Op0, I->getType()); 00098 case Instruction::Select: 00099 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2))) 00100 return ConstantExpr::getSelect(Op0, Op1, Op2); 00101 return 0; 00102 case Instruction::GetElementPtr: 00103 std::vector<Constant*> IdxList; 00104 IdxList.reserve(I->getNumOperands()-1); 00105 if (Op1) IdxList.push_back(Op1); 00106 for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i) 00107 if (Constant *C = dyn_cast<Constant>(I->getOperand(i))) 00108 IdxList.push_back(C); 00109 else 00110 return 0; // Non-constant operand 00111 return ConstantExpr::getGetElementPtr(Op0, IdxList); 00112 } 00113 } 00114 00115 // ConstantFoldTerminator - If a terminator instruction is predicated on a 00116 // constant value, convert it into an unconditional branch to the constant 00117 // destination. 00118 // 00119 bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 00120 TerminatorInst *T = BB->getTerminator(); 00121 00122 // Branch - See if we are conditional jumping on constant 00123 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 00124 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 00125 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 00126 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 00127 00128 if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) { 00129 // Are we branching on constant? 00130 // YES. Change to unconditional branch... 00131 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; 00132 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; 00133 00134 //cerr << "Function: " << T->getParent()->getParent() 00135 // << "\nRemoving branch from " << T->getParent() 00136 // << "\n\nTo: " << OldDest << endl; 00137 00138 // Let the basic block know that we are letting go of it. Based on this, 00139 // it will adjust it's PHI nodes. 00140 assert(BI->getParent() && "Terminator not inserted in block!"); 00141 OldDest->removePredecessor(BI->getParent()); 00142 00143 // Set the unconditional destination, and change the insn to be an 00144 // unconditional branch. 00145 BI->setUnconditionalDest(Destination); 00146 return true; 00147 } else if (Dest2 == Dest1) { // Conditional branch to same location? 00148 // This branch matches something like this: 00149 // br bool %cond, label %Dest, label %Dest 00150 // and changes it into: br label %Dest 00151 00152 // Let the basic block know that we are letting go of one copy of it. 00153 assert(BI->getParent() && "Terminator not inserted in block!"); 00154 Dest1->removePredecessor(BI->getParent()); 00155 00156 // Change a conditional branch to unconditional. 00157 BI->setUnconditionalDest(Dest1); 00158 return true; 00159 } 00160 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 00161 // If we are switching on a constant, we can convert the switch into a 00162 // single branch instruction! 00163 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 00164 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 00165 BasicBlock *DefaultDest = TheOnlyDest; 00166 assert(TheOnlyDest == SI->getDefaultDest() && 00167 "Default destination is not successor #0?"); 00168 00169 // Figure out which case it goes to... 00170 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 00171 // Found case matching a constant operand? 00172 if (SI->getSuccessorValue(i) == CI) { 00173 TheOnlyDest = SI->getSuccessor(i); 00174 break; 00175 } 00176 00177 // Check to see if this branch is going to the same place as the default 00178 // dest. If so, eliminate it as an explicit compare. 00179 if (SI->getSuccessor(i) == DefaultDest) { 00180 // Remove this entry... 00181 DefaultDest->removePredecessor(SI->getParent()); 00182 SI->removeCase(i); 00183 --i; --e; // Don't skip an entry... 00184 continue; 00185 } 00186 00187 // Otherwise, check to see if the switch only branches to one destination. 00188 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 00189 // destinations. 00190 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 00191 } 00192 00193 if (CI && !TheOnlyDest) { 00194 // Branching on a constant, but not any of the cases, go to the default 00195 // successor. 00196 TheOnlyDest = SI->getDefaultDest(); 00197 } 00198 00199 // If we found a single destination that we can fold the switch into, do so 00200 // now. 00201 if (TheOnlyDest) { 00202 // Insert the new branch.. 00203 new BranchInst(TheOnlyDest, SI); 00204 BasicBlock *BB = SI->getParent(); 00205 00206 // Remove entries from PHI nodes which we no longer branch to... 00207 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 00208 // Found case matching a constant operand? 00209 BasicBlock *Succ = SI->getSuccessor(i); 00210 if (Succ == TheOnlyDest) 00211 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 00212 else 00213 Succ->removePredecessor(BB); 00214 } 00215 00216 // Delete the old switch... 00217 BB->getInstList().erase(SI); 00218 return true; 00219 } else if (SI->getNumSuccessors() == 2) { 00220 // Otherwise, we can fold this switch into a conditional branch 00221 // instruction if it has only one non-default destination. 00222 Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(), 00223 SI->getSuccessorValue(1), "cond", SI); 00224 // Insert the new branch... 00225 new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 00226 00227 // Delete the old switch... 00228 SI->getParent()->getInstList().erase(SI); 00229 return true; 00230 } 00231 } 00232 return false; 00233 } 00234 00235 /// canConstantFoldCallTo - Return true if its even possible to fold a call to 00236 /// the specified function. 00237 bool llvm::canConstantFoldCallTo(Function *F) { 00238 const std::string &Name = F->getName(); 00239 00240 switch (F->getIntrinsicID()) { 00241 case Intrinsic::isunordered: return true; 00242 default: break; 00243 } 00244 00245 return Name == "sin" || Name == "cos" || Name == "tan" || Name == "sqrt" || 00246 Name == "log" || Name == "log10" || Name == "exp" || Name == "pow" || 00247 Name == "acos" || Name == "asin" || Name == "atan" || Name == "fmod"; 00248 } 00249 00250 static Constant *ConstantFoldFP(double (*NativeFP)(double), double V, 00251 const Type *Ty) { 00252 errno = 0; 00253 V = NativeFP(V); 00254 if (errno == 0) 00255 return ConstantFP::get(Ty, V); 00256 return 0; 00257 } 00258 00259 /// ConstantFoldCall - Attempt to constant fold a call to the specified function 00260 /// with the specified arguments, returning null if unsuccessful. 00261 Constant *llvm::ConstantFoldCall(Function *F, 00262 const std::vector<Constant*> &Operands) { 00263 const std::string &Name = F->getName(); 00264 const Type *Ty = F->getReturnType(); 00265 00266 if (Operands.size() == 1) { 00267 if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) { 00268 double V = Op->getValue(); 00269 if (Name == "sin") 00270 return ConstantFP::get(Ty, sin(V)); 00271 else if (Name == "cos") 00272 return ConstantFP::get(Ty, cos(V)); 00273 else if (Name == "tan") 00274 return ConstantFP::get(Ty, tan(V)); 00275 else if (Name == "sqrt" && V >= 0) 00276 return ConstantFP::get(Ty, sqrt(V)); 00277 else if (Name == "exp") 00278 return ConstantFP::get(Ty, exp(V)); 00279 else if (Name == "log" && V > 0) 00280 return ConstantFP::get(Ty, log(V)); 00281 else if (Name == "log10") 00282 return ConstantFoldFP(log10, V, Ty); 00283 else if (Name == "acos") 00284 return ConstantFoldFP(acos, V, Ty); 00285 else if (Name == "asin") 00286 return ConstantFoldFP(asin, V, Ty); 00287 else if (Name == "atan") 00288 return ConstantFP::get(Ty, atan(V)); 00289 } 00290 } else if (Operands.size() == 2) { 00291 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) 00292 if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) { 00293 double Op1V = Op1->getValue(), Op2V = Op2->getValue(); 00294 00295 if (Name == "llvm.isunordered") 00296 return ConstantBool::get(IsNAN(Op1V) || IsNAN(Op2V)); 00297 else 00298 if (Name == "pow") { 00299 errno = 0; 00300 double V = pow(Op1V, Op2V); 00301 if (errno == 0) 00302 return ConstantFP::get(Ty, V); 00303 } else if (Name == "fmod") { 00304 errno = 0; 00305 double V = fmod(Op1V, Op2V); 00306 if (errno == 0) 00307 return ConstantFP::get(Ty, V); 00308 } 00309 } 00310 } 00311 return 0; 00312 } 00313 00314 00315 00316 00317 //===----------------------------------------------------------------------===// 00318 // Local dead code elimination... 00319 // 00320 00321 bool llvm::isInstructionTriviallyDead(Instruction *I) { 00322 return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I); 00323 } 00324 00325 // dceInstruction - Inspect the instruction at *BBI and figure out if it's 00326 // [trivially] dead. If so, remove the instruction and update the iterator 00327 // to point to the instruction that immediately succeeded the original 00328 // instruction. 00329 // 00330 bool llvm::dceInstruction(BasicBlock::iterator &BBI) { 00331 // Look for un"used" definitions... 00332 if (isInstructionTriviallyDead(BBI)) { 00333 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye 00334 return true; 00335 } 00336 return false; 00337 } 00338 00339 //===----------------------------------------------------------------------===// 00340 // PHI Instruction Simplification 00341 // 00342 00343 /// hasConstantValue - If the specified PHI node always merges together the same 00344 /// value, return the value, otherwise return null. 00345 /// 00346 Value *llvm::hasConstantValue(PHINode *PN) { 00347 // If the PHI node only has one incoming value, eliminate the PHI node... 00348 if (PN->getNumIncomingValues() == 1) 00349 return PN->getIncomingValue(0); 00350 00351 // Otherwise if all of the incoming values are the same for the PHI, replace 00352 // the PHI node with the incoming value. 00353 // 00354 Value *InVal = 0; 00355 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00356 if (PN->getIncomingValue(i) != PN && // Not the PHI node itself... 00357 !isa<UndefValue>(PN->getIncomingValue(i))) 00358 if (InVal && PN->getIncomingValue(i) != InVal) 00359 return 0; // Not the same, bail out. 00360 else 00361 InVal = PN->getIncomingValue(i); 00362 00363 // The only case that could cause InVal to be null is if we have a PHI node 00364 // that only has entries for itself. In this case, there is no entry into the 00365 // loop, so kill the PHI. 00366 // 00367 if (InVal == 0) InVal = UndefValue::get(PN->getType()); 00368 00369 // All of the incoming values are the same, return the value now. 00370 return InVal; 00371 }