LLVM API Documentation
00001 //===- LevelRaise.cpp - Code to change LLVM to higher level ---------------===// 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 file implements the 'raising' part of the LevelChange API. This is 00011 // useful because, in general, it makes the LLVM code terser and easier to 00012 // analyze. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #include "llvm/Transforms/Scalar.h" 00017 #include "llvm/Transforms/Utils/Local.h" 00018 #include "TransformInternals.h" 00019 #include "llvm/Instructions.h" 00020 #include "llvm/Pass.h" 00021 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00022 #include "llvm/Support/CommandLine.h" 00023 #include "llvm/Support/Debug.h" 00024 #include "llvm/ADT/Statistic.h" 00025 #include "llvm/ADT/STLExtras.h" 00026 #include <algorithm> 00027 #include <iostream> 00028 using namespace llvm; 00029 00030 // StartInst - This enables the -raise-start-inst=foo option to cause the level 00031 // raising pass to start at instruction "foo", which is immensely useful for 00032 // debugging! 00033 // 00034 static cl::opt<std::string> 00035 StartInst("raise-start-inst", cl::Hidden, cl::value_desc("inst name"), 00036 cl::desc("Start raise pass at the instruction with the specified name")); 00037 00038 static Statistic<> 00039 NumLoadStorePeepholes("raise", "Number of load/store peepholes"); 00040 00041 static Statistic<> 00042 NumGEPInstFormed("raise", "Number of other getelementptr's formed"); 00043 00044 static Statistic<> 00045 NumExprTreesConv("raise", "Number of expression trees converted"); 00046 00047 static Statistic<> 00048 NumCastOfCast("raise", "Number of cast-of-self removed"); 00049 00050 static Statistic<> 00051 NumDCEorCP("raise", "Number of insts DCEd or constprop'd"); 00052 00053 static Statistic<> 00054 NumVarargCallChanges("raise", "Number of vararg call peepholes"); 00055 00056 #define PRINT_PEEPHOLE(ID, NUM, I) \ 00057 DEBUG(std::cerr << "Inst P/H " << ID << "[" << NUM << "] " << I) 00058 00059 #define PRINT_PEEPHOLE1(ID, I1) do { PRINT_PEEPHOLE(ID, 0, I1); } while (0) 00060 #define PRINT_PEEPHOLE2(ID, I1, I2) \ 00061 do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); } while (0) 00062 #define PRINT_PEEPHOLE3(ID, I1, I2, I3) \ 00063 do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \ 00064 PRINT_PEEPHOLE(ID, 2, I3); } while (0) 00065 #define PRINT_PEEPHOLE4(ID, I1, I2, I3, I4) \ 00066 do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \ 00067 PRINT_PEEPHOLE(ID, 2, I3); PRINT_PEEPHOLE(ID, 3, I4); } while (0) 00068 00069 namespace { 00070 struct RPR : public FunctionPass { 00071 virtual bool runOnFunction(Function &F); 00072 00073 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00074 AU.setPreservesCFG(); 00075 AU.addRequired<TargetData>(); 00076 } 00077 00078 private: 00079 bool DoRaisePass(Function &F); 00080 bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI); 00081 }; 00082 00083 RegisterOpt<RPR> X("raise", "Raise Pointer References"); 00084 } 00085 00086 00087 FunctionPass *llvm::createRaisePointerReferencesPass() { 00088 return new RPR(); 00089 } 00090 00091 00092 // isReinterpretingCast - Return true if the cast instruction specified will 00093 // cause the operand to be "reinterpreted". A value is reinterpreted if the 00094 // cast instruction would cause the underlying bits to change. 00095 // 00096 static inline bool isReinterpretingCast(const CastInst *CI) { 00097 return!CI->getOperand(0)->getType()->isLosslesslyConvertibleTo(CI->getType()); 00098 } 00099 00100 bool RPR::PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) { 00101 Instruction *I = BI; 00102 const TargetData &TD = getAnalysis<TargetData>(); 00103 00104 if (CastInst *CI = dyn_cast<CastInst>(I)) { 00105 Value *Src = CI->getOperand(0); 00106 const Type *DestTy = CI->getType(); 00107 00108 // Peephole optimize the following instruction: 00109 // %V2 = cast <ty> %V to <ty> 00110 // 00111 // Into: <nothing> 00112 // 00113 if (DestTy == Src->getType()) { // Check for a cast to same type as src!! 00114 PRINT_PEEPHOLE1("cast-of-self-ty", *CI); 00115 CI->replaceAllUsesWith(Src); 00116 if (!Src->hasName() && CI->hasName()) { 00117 std::string Name = CI->getName(); 00118 CI->setName(""); 00119 Src->setName(Name); 00120 } 00121 00122 // DCE the instruction now, to avoid having the iterative version of DCE 00123 // have to worry about it. 00124 // 00125 BI = BB->getInstList().erase(BI); 00126 00127 ++NumCastOfCast; 00128 return true; 00129 } 00130 00131 // Check to see if it's a cast of an instruction that does not depend on the 00132 // specific type of the operands to do it's job. 00133 if (!isReinterpretingCast(CI)) { 00134 ValueTypeCache ConvertedTypes; 00135 00136 // Check to see if we can convert the source of the cast to match the 00137 // destination type of the cast... 00138 // 00139 ConvertedTypes[CI] = CI->getType(); // Make sure the cast doesn't change 00140 if (ExpressionConvertibleToType(Src, DestTy, ConvertedTypes, TD)) { 00141 PRINT_PEEPHOLE3("CAST-SRC-EXPR-CONV:in ", *Src, *CI, *BB->getParent()); 00142 00143 DEBUG(std::cerr << "\nCONVERTING SRC EXPR TYPE:\n"); 00144 { // ValueMap must be destroyed before function verified! 00145 ValueMapCache ValueMap; 00146 Value *E = ConvertExpressionToType(Src, DestTy, ValueMap, TD); 00147 00148 if (Constant *CPV = dyn_cast<Constant>(E)) 00149 CI->replaceAllUsesWith(CPV); 00150 00151 PRINT_PEEPHOLE1("CAST-SRC-EXPR-CONV:out", *E); 00152 DEBUG(std::cerr << "DONE CONVERTING SRC EXPR TYPE: \n" 00153 << *BB->getParent()); 00154 } 00155 00156 BI = BB->begin(); // Rescan basic block. BI might be invalidated. 00157 ++NumExprTreesConv; 00158 return true; 00159 } 00160 00161 // Check to see if we can convert the users of the cast value to match the 00162 // source type of the cast... 00163 // 00164 ConvertedTypes.clear(); 00165 // Make sure the source doesn't change type 00166 ConvertedTypes[Src] = Src->getType(); 00167 if (ValueConvertibleToType(CI, Src->getType(), ConvertedTypes, TD)) { 00168 //PRINT_PEEPHOLE3("CAST-DEST-EXPR-CONV:in ", *Src, *CI, 00169 // *BB->getParent()); 00170 00171 DEBUG(std::cerr << "\nCONVERTING EXPR TYPE:\n"); 00172 { // ValueMap must be destroyed before function verified! 00173 ValueMapCache ValueMap; 00174 ConvertValueToNewType(CI, Src, ValueMap, TD); // This will delete CI! 00175 } 00176 00177 PRINT_PEEPHOLE1("CAST-DEST-EXPR-CONV:out", *Src); 00178 DEBUG(std::cerr << "DONE CONVERTING EXPR TYPE: \n\n" << 00179 *BB->getParent()); 00180 00181 BI = BB->begin(); // Rescan basic block. BI might be invalidated. 00182 ++NumExprTreesConv; 00183 return true; 00184 } 00185 } 00186 00187 // Check to see if we are casting from a structure pointer to a pointer to 00188 // the first element of the structure... to avoid munching other peepholes, 00189 // we only let this happen if there are no add uses of the cast. 00190 // 00191 // Peephole optimize the following instructions: 00192 // %t1 = cast {<...>} * %StructPtr to <ty> * 00193 // 00194 // Into: %t2 = getelementptr {<...>} * %StructPtr, <0, 0, 0, ...> 00195 // %t1 = cast <eltype> * %t1 to <ty> * 00196 // 00197 if (const CompositeType *CTy = getPointedToComposite(Src->getType())) 00198 if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) { 00199 00200 // Loop over uses of the cast, checking for add instructions. If an add 00201 // exists, this is probably a part of a more complex GEP, so we don't 00202 // want to mess around with the cast. 00203 // 00204 bool HasAddUse = false; 00205 for (Value::use_iterator I = CI->use_begin(), E = CI->use_end(); 00206 I != E; ++I) 00207 if (isa<Instruction>(*I) && 00208 cast<Instruction>(*I)->getOpcode() == Instruction::Add) { 00209 HasAddUse = true; break; 00210 } 00211 00212 // If it doesn't have an add use, check to see if the dest type is 00213 // losslessly convertible to one of the types in the start of the struct 00214 // type. 00215 // 00216 if (!HasAddUse) { 00217 const Type *DestPointedTy = DestPTy->getElementType(); 00218 unsigned Depth = 1; 00219 const CompositeType *CurCTy = CTy; 00220 const Type *ElTy = 0; 00221 00222 // Build the index vector, full of all zeros 00223 std::vector<Value*> Indices; 00224 00225 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00226 while (CurCTy && !isa<PointerType>(CurCTy)) { 00227 if (const StructType *CurSTy = dyn_cast<StructType>(CurCTy)) { 00228 // Check for a zero element struct type... if we have one, bail. 00229 if (CurSTy->getNumElements() == 0) break; 00230 00231 // Grab the first element of the struct type, which must lie at 00232 // offset zero in the struct. 00233 // 00234 ElTy = CurSTy->getElementType(0); 00235 } else { 00236 ElTy = cast<SequentialType>(CurCTy)->getElementType(); 00237 } 00238 00239 // Insert a zero to index through this type... 00240 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00241 00242 // Did we find what we're looking for? 00243 if (ElTy->isLosslesslyConvertibleTo(DestPointedTy)) break; 00244 00245 // Nope, go a level deeper. 00246 ++Depth; 00247 CurCTy = dyn_cast<CompositeType>(ElTy); 00248 ElTy = 0; 00249 } 00250 00251 // Did we find what we were looking for? If so, do the transformation 00252 if (ElTy) { 00253 PRINT_PEEPHOLE1("cast-for-first:in", *CI); 00254 00255 std::string Name = CI->getName(); CI->setName(""); 00256 00257 // Insert the new T cast instruction... stealing old T's name 00258 GetElementPtrInst *GEP = new GetElementPtrInst(Src, Indices, 00259 Name, BI); 00260 00261 // Make the old cast instruction reference the new GEP instead of 00262 // the old src value. 00263 // 00264 CI->setOperand(0, GEP); 00265 00266 PRINT_PEEPHOLE2("cast-for-first:out", *GEP, *CI); 00267 ++NumGEPInstFormed; 00268 return true; 00269 } 00270 } 00271 } 00272 00273 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00274 Value *Val = SI->getOperand(0); 00275 Value *Pointer = SI->getPointerOperand(); 00276 00277 // Peephole optimize the following instructions: 00278 // %t = cast <T1>* %P to <T2> * ;; If T1 is losslessly convertible to T2 00279 // store <T2> %V, <T2>* %t 00280 // 00281 // Into: 00282 // %t = cast <T2> %V to <T1> 00283 // store <T1> %t2, <T1>* %P 00284 // 00285 // Note: This is not taken care of by expr conversion because there might 00286 // not be a cast available for the store to convert the incoming value of. 00287 // This code is basically here to make sure that pointers don't have casts 00288 // if possible. 00289 // 00290 if (CastInst *CI = dyn_cast<CastInst>(Pointer)) 00291 if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType 00292 if (const PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType())) 00293 // convertible types? 00294 if (Val->getType()->isLosslesslyConvertibleTo(CSPT->getElementType())) { 00295 PRINT_PEEPHOLE3("st-src-cast:in ", *Pointer, *Val, *SI); 00296 00297 // Insert the new T cast instruction... stealing old T's name 00298 std::string Name(CI->getName()); CI->setName(""); 00299 CastInst *NCI = new CastInst(Val, CSPT->getElementType(), 00300 Name, BI); 00301 00302 // Replace the old store with a new one! 00303 ReplaceInstWithInst(BB->getInstList(), BI, 00304 SI = new StoreInst(NCI, CastSrc)); 00305 PRINT_PEEPHOLE3("st-src-cast:out", *NCI, *CastSrc, *SI); 00306 ++NumLoadStorePeepholes; 00307 return true; 00308 } 00309 00310 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00311 Value *Pointer = LI->getOperand(0); 00312 const Type *PtrElType = 00313 cast<PointerType>(Pointer->getType())->getElementType(); 00314 00315 // Peephole optimize the following instructions: 00316 // %Val = cast <T1>* to <T2>* ;; If T1 is losslessly convertible to T2 00317 // %t = load <T2>* %P 00318 // 00319 // Into: 00320 // %t = load <T1>* %P 00321 // %Val = cast <T1> to <T2> 00322 // 00323 // Note: This is not taken care of by expr conversion because there might 00324 // not be a cast available for the store to convert the incoming value of. 00325 // This code is basically here to make sure that pointers don't have casts 00326 // if possible. 00327 // 00328 if (CastInst *CI = dyn_cast<CastInst>(Pointer)) 00329 if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType 00330 if (const PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType())) 00331 // convertible types? 00332 if (PtrElType->isLosslesslyConvertibleTo(CSPT->getElementType())) { 00333 PRINT_PEEPHOLE2("load-src-cast:in ", *Pointer, *LI); 00334 00335 // Create the new load instruction... loading the pre-casted value 00336 LoadInst *NewLI = new LoadInst(CastSrc, LI->getName(), BI); 00337 00338 // Insert the new T cast instruction... stealing old T's name 00339 CastInst *NCI = new CastInst(NewLI, LI->getType(), CI->getName()); 00340 00341 // Replace the old store with a new one! 00342 ReplaceInstWithInst(BB->getInstList(), BI, NCI); 00343 PRINT_PEEPHOLE3("load-src-cast:out", *NCI, *CastSrc, *NewLI); 00344 ++NumLoadStorePeepholes; 00345 return true; 00346 } 00347 00348 } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 00349 // If we have a call with all varargs arguments, convert the call to use the 00350 // actual argument types present... 00351 // 00352 const PointerType *PTy = cast<PointerType>(CI->getCalledValue()->getType()); 00353 const FunctionType *FTy = cast<FunctionType>(PTy->getElementType()); 00354 00355 // Is the call to a vararg variable with no real parameters? 00356 if (FTy->isVarArg() && FTy->getNumParams() == 0 && 00357 !CI->getCalledFunction()) { 00358 // If so, insert a new cast instruction, casting it to a function type 00359 // that matches the current arguments... 00360 // 00361 std::vector<const Type *> Params; // Parameter types... 00362 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) 00363 Params.push_back(CI->getOperand(i)->getType()); 00364 00365 FunctionType *NewFT = FunctionType::get(FTy->getReturnType(), 00366 Params, false); 00367 PointerType *NewPFunTy = PointerType::get(NewFT); 00368 00369 // Create a new cast, inserting it right before the function call... 00370 Value *NewCast; 00371 Constant *ConstantCallSrc = 0; 00372 if (Constant *CS = dyn_cast<Constant>(CI->getCalledValue())) 00373 ConstantCallSrc = CS; 00374 00375 if (ConstantCallSrc) 00376 NewCast = ConstantExpr::getCast(ConstantCallSrc, NewPFunTy); 00377 else 00378 NewCast = new CastInst(CI->getCalledValue(), NewPFunTy, 00379 CI->getCalledValue()->getName()+"_c",CI); 00380 00381 // Create a new call instruction... 00382 CallInst *NewCall = new CallInst(NewCast, 00383 std::vector<Value*>(CI->op_begin()+1, CI->op_end())); 00384 if (CI->isTailCall()) NewCall->setTailCall(); 00385 NewCall->setCallingConv(CI->getCallingConv()); 00386 ++BI; 00387 ReplaceInstWithInst(CI, NewCall); 00388 00389 ++NumVarargCallChanges; 00390 return true; 00391 } 00392 00393 } 00394 00395 return false; 00396 } 00397 00398 00399 00400 00401 bool RPR::DoRaisePass(Function &F) { 00402 bool Changed = false; 00403 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) 00404 for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) { 00405 DEBUG(std::cerr << "LevelRaising: " << *BI); 00406 if (dceInstruction(BI) || doConstantPropagation(BI)) { 00407 Changed = true; 00408 ++NumDCEorCP; 00409 DEBUG(std::cerr << "***\t\t^^-- Dead code eliminated!\n"); 00410 } else if (PeepholeOptimize(BB, BI)) { 00411 Changed = true; 00412 } else { 00413 ++BI; 00414 } 00415 } 00416 00417 return Changed; 00418 } 00419 00420 00421 // runOnFunction - Raise a function representation to a higher level. 00422 bool RPR::runOnFunction(Function &F) { 00423 DEBUG(std::cerr << "\n\n\nStarting to work on Function '" << F.getName() 00424 << "'\n"); 00425 00426 // Insert casts for all incoming pointer pointer values that are treated as 00427 // arrays... 00428 // 00429 bool Changed = false, LocalChange; 00430 00431 // If the StartInst option was specified, then Peephole optimize that 00432 // instruction first if it occurs in this function. 00433 // 00434 if (!StartInst.empty()) { 00435 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) 00436 for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) 00437 if (BI->getName() == StartInst) { 00438 bool SavedDebug = DebugFlag; // Save the DEBUG() controlling flag. 00439 DebugFlag = true; // Turn on DEBUG's 00440 Changed |= PeepholeOptimize(BB, BI); 00441 DebugFlag = SavedDebug; // Restore DebugFlag to previous state 00442 } 00443 } 00444 00445 do { 00446 DEBUG(std::cerr << "Looping: \n" << F); 00447 00448 // Iterate over the function, refining it, until it converges on a stable 00449 // state 00450 LocalChange = false; 00451 while (DoRaisePass(F)) LocalChange = true; 00452 Changed |= LocalChange; 00453 00454 } while (LocalChange); 00455 00456 return Changed; 00457 } 00458