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/Transforms/Utils/Local.h" 00016 #include "llvm/Constants.h" 00017 #include "llvm/DerivedTypes.h" 00018 #include "llvm/Instructions.h" 00019 #include "llvm/Intrinsics.h" 00020 #include "llvm/Analysis/ConstantFolding.h" 00021 #include "llvm/Support/GetElementPtrTypeIterator.h" 00022 #include "llvm/Support/MathExtras.h" 00023 #include <cerrno> 00024 #include <cmath> 00025 using namespace llvm; 00026 00027 //===----------------------------------------------------------------------===// 00028 // Local constant propagation... 00029 // 00030 00031 /// doConstantPropagation - If an instruction references constants, try to fold 00032 /// them together... 00033 /// 00034 bool llvm::doConstantPropagation(BasicBlock::iterator &II) { 00035 if (Constant *C = ConstantFoldInstruction(II)) { 00036 // Replaces all of the uses of a variable with uses of the constant. 00037 II->replaceAllUsesWith(C); 00038 00039 // Remove the instruction from the basic block... 00040 II = II->getParent()->getInstList().erase(II); 00041 return true; 00042 } 00043 00044 return false; 00045 } 00046 00047 /// ConstantFoldInstruction - Attempt to constant fold the specified 00048 /// instruction. If successful, the constant result is returned, if not, null 00049 /// is returned. Note that this function can only fail when attempting to fold 00050 /// instructions like loads and stores, which have no constant expression form. 00051 /// 00052 Constant *llvm::ConstantFoldInstruction(Instruction *I) { 00053 if (PHINode *PN = dyn_cast<PHINode>(I)) { 00054 if (PN->getNumIncomingValues() == 0) 00055 return Constant::getNullValue(PN->getType()); 00056 00057 Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0)); 00058 if (Result == 0) return 0; 00059 00060 // Handle PHI nodes specially here... 00061 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 00062 if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN) 00063 return 0; // Not all the same incoming constants... 00064 00065 // If we reach here, all incoming values are the same constant. 00066 return Result; 00067 } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 00068 if (Function *F = CI->getCalledFunction()) 00069 if (canConstantFoldCallTo(F)) { 00070 std::vector<Constant*> Args; 00071 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) 00072 if (Constant *Op = dyn_cast<Constant>(CI->getOperand(i))) 00073 Args.push_back(Op); 00074 else 00075 return 0; 00076 return ConstantFoldCall(F, Args); 00077 } 00078 return 0; 00079 } 00080 00081 Constant *Op0 = 0, *Op1 = 0; 00082 switch (I->getNumOperands()) { 00083 default: 00084 case 2: 00085 Op1 = dyn_cast<Constant>(I->getOperand(1)); 00086 if (Op1 == 0) return 0; // Not a constant?, can't fold 00087 case 1: 00088 Op0 = dyn_cast<Constant>(I->getOperand(0)); 00089 if (Op0 == 0) return 0; // Not a constant?, can't fold 00090 break; 00091 case 0: return 0; 00092 } 00093 00094 if (isa<BinaryOperator>(I) || isa<ShiftInst>(I)) 00095 return ConstantExpr::get(I->getOpcode(), Op0, Op1); 00096 00097 switch (I->getOpcode()) { 00098 default: return 0; 00099 case Instruction::Cast: 00100 return ConstantExpr::getCast(Op0, I->getType()); 00101 case Instruction::Select: 00102 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2))) 00103 return ConstantExpr::getSelect(Op0, Op1, Op2); 00104 return 0; 00105 case Instruction::ExtractElement: 00106 return ConstantExpr::getExtractElement(Op0, Op1); 00107 case Instruction::InsertElement: 00108 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2))) 00109 return ConstantExpr::getInsertElement(Op0, Op1, Op2); 00110 return 0; 00111 case Instruction::ShuffleVector: 00112 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2))) 00113 return ConstantExpr::getShuffleVector(Op0, Op1, Op2); 00114 return 0; 00115 case Instruction::GetElementPtr: 00116 std::vector<Constant*> IdxList; 00117 IdxList.reserve(I->getNumOperands()-1); 00118 if (Op1) IdxList.push_back(Op1); 00119 for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i) 00120 if (Constant *C = dyn_cast<Constant>(I->getOperand(i))) 00121 IdxList.push_back(C); 00122 else 00123 return 0; // Non-constant operand 00124 return ConstantExpr::getGetElementPtr(Op0, IdxList); 00125 } 00126 } 00127 00128 // ConstantFoldTerminator - If a terminator instruction is predicated on a 00129 // constant value, convert it into an unconditional branch to the constant 00130 // destination. 00131 // 00132 bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 00133 TerminatorInst *T = BB->getTerminator(); 00134 00135 // Branch - See if we are conditional jumping on constant 00136 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 00137 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 00138 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 00139 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 00140 00141 if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) { 00142 // Are we branching on constant? 00143 // YES. Change to unconditional branch... 00144 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; 00145 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; 00146 00147 //cerr << "Function: " << T->getParent()->getParent() 00148 // << "\nRemoving branch from " << T->getParent() 00149 // << "\n\nTo: " << OldDest << endl; 00150 00151 // Let the basic block know that we are letting go of it. Based on this, 00152 // it will adjust it's PHI nodes. 00153 assert(BI->getParent() && "Terminator not inserted in block!"); 00154 OldDest->removePredecessor(BI->getParent()); 00155 00156 // Set the unconditional destination, and change the insn to be an 00157 // unconditional branch. 00158 BI->setUnconditionalDest(Destination); 00159 return true; 00160 } else if (Dest2 == Dest1) { // Conditional branch to same location? 00161 // This branch matches something like this: 00162 // br bool %cond, label %Dest, label %Dest 00163 // and changes it into: br label %Dest 00164 00165 // Let the basic block know that we are letting go of one copy of it. 00166 assert(BI->getParent() && "Terminator not inserted in block!"); 00167 Dest1->removePredecessor(BI->getParent()); 00168 00169 // Change a conditional branch to unconditional. 00170 BI->setUnconditionalDest(Dest1); 00171 return true; 00172 } 00173 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 00174 // If we are switching on a constant, we can convert the switch into a 00175 // single branch instruction! 00176 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 00177 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 00178 BasicBlock *DefaultDest = TheOnlyDest; 00179 assert(TheOnlyDest == SI->getDefaultDest() && 00180 "Default destination is not successor #0?"); 00181 00182 // Figure out which case it goes to... 00183 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 00184 // Found case matching a constant operand? 00185 if (SI->getSuccessorValue(i) == CI) { 00186 TheOnlyDest = SI->getSuccessor(i); 00187 break; 00188 } 00189 00190 // Check to see if this branch is going to the same place as the default 00191 // dest. If so, eliminate it as an explicit compare. 00192 if (SI->getSuccessor(i) == DefaultDest) { 00193 // Remove this entry... 00194 DefaultDest->removePredecessor(SI->getParent()); 00195 SI->removeCase(i); 00196 --i; --e; // Don't skip an entry... 00197 continue; 00198 } 00199 00200 // Otherwise, check to see if the switch only branches to one destination. 00201 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 00202 // destinations. 00203 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 00204 } 00205 00206 if (CI && !TheOnlyDest) { 00207 // Branching on a constant, but not any of the cases, go to the default 00208 // successor. 00209 TheOnlyDest = SI->getDefaultDest(); 00210 } 00211 00212 // If we found a single destination that we can fold the switch into, do so 00213 // now. 00214 if (TheOnlyDest) { 00215 // Insert the new branch.. 00216 new BranchInst(TheOnlyDest, SI); 00217 BasicBlock *BB = SI->getParent(); 00218 00219 // Remove entries from PHI nodes which we no longer branch to... 00220 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 00221 // Found case matching a constant operand? 00222 BasicBlock *Succ = SI->getSuccessor(i); 00223 if (Succ == TheOnlyDest) 00224 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 00225 else 00226 Succ->removePredecessor(BB); 00227 } 00228 00229 // Delete the old switch... 00230 BB->getInstList().erase(SI); 00231 return true; 00232 } else if (SI->getNumSuccessors() == 2) { 00233 // Otherwise, we can fold this switch into a conditional branch 00234 // instruction if it has only one non-default destination. 00235 Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(), 00236 SI->getSuccessorValue(1), "cond", SI); 00237 // Insert the new branch... 00238 new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 00239 00240 // Delete the old switch... 00241 SI->getParent()->getInstList().erase(SI); 00242 return true; 00243 } 00244 } 00245 return false; 00246 } 00247 00248 /// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a 00249 /// getelementptr constantexpr, return the constant value being addressed by the 00250 /// constant expression, or null if something is funny and we can't decide. 00251 Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 00252 ConstantExpr *CE) { 00253 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 00254 return 0; // Do not allow stepping over the value! 00255 00256 // Loop over all of the operands, tracking down which value we are 00257 // addressing... 00258 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 00259 for (++I; I != E; ++I) 00260 if (const StructType *STy = dyn_cast<StructType>(*I)) { 00261 ConstantUInt *CU = cast<ConstantUInt>(I.getOperand()); 00262 assert(CU->getValue() < STy->getNumElements() && 00263 "Struct index out of range!"); 00264 unsigned El = (unsigned)CU->getValue(); 00265 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 00266 C = CS->getOperand(El); 00267 } else if (isa<ConstantAggregateZero>(C)) { 00268 C = Constant::getNullValue(STy->getElementType(El)); 00269 } else if (isa<UndefValue>(C)) { 00270 C = UndefValue::get(STy->getElementType(El)); 00271 } else { 00272 return 0; 00273 } 00274 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 00275 if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) { 00276 if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) return 0; 00277 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 00278 C = CA->getOperand((unsigned)CI->getRawValue()); 00279 else if (isa<ConstantAggregateZero>(C)) 00280 C = Constant::getNullValue(ATy->getElementType()); 00281 else if (isa<UndefValue>(C)) 00282 C = UndefValue::get(ATy->getElementType()); 00283 else 00284 return 0; 00285 } else if (const PackedType *PTy = dyn_cast<PackedType>(*I)) { 00286 if ((uint64_t)CI->getRawValue() >= PTy->getNumElements()) return 0; 00287 if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) 00288 C = CP->getOperand((unsigned)CI->getRawValue()); 00289 else if (isa<ConstantAggregateZero>(C)) 00290 C = Constant::getNullValue(PTy->getElementType()); 00291 else if (isa<UndefValue>(C)) 00292 C = UndefValue::get(PTy->getElementType()); 00293 else 00294 return 0; 00295 } else { 00296 return 0; 00297 } 00298 } else { 00299 return 0; 00300 } 00301 return C; 00302 } 00303 00304 00305 //===----------------------------------------------------------------------===// 00306 // Local dead code elimination... 00307 // 00308 00309 bool llvm::isInstructionTriviallyDead(Instruction *I) { 00310 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 00311 00312 if (!I->mayWriteToMemory()) return true; 00313 00314 if (CallInst *CI = dyn_cast<CallInst>(I)) 00315 if (Function *F = CI->getCalledFunction()) { 00316 unsigned IntrinsicID = F->getIntrinsicID(); 00317 #define GET_SIDE_EFFECT_INFO 00318 #include "llvm/Intrinsics.gen" 00319 #undef GET_SIDE_EFFECT_INFO 00320 } 00321 return false; 00322 } 00323 00324 // dceInstruction - Inspect the instruction at *BBI and figure out if it's 00325 // [trivially] dead. If so, remove the instruction and update the iterator 00326 // to point to the instruction that immediately succeeded the original 00327 // instruction. 00328 // 00329 bool llvm::dceInstruction(BasicBlock::iterator &BBI) { 00330 // Look for un"used" definitions... 00331 if (isInstructionTriviallyDead(BBI)) { 00332 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye 00333 return true; 00334 } 00335 return false; 00336 }