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