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 Instruction *SrcI = dyn_cast<Instruction>(Src); // Nonnull if instr source 00107 const Type *DestTy = CI->getType(); 00108 00109 // Peephole optimize the following instruction: 00110 // %V2 = cast <ty> %V to <ty> 00111 // 00112 // Into: <nothing> 00113 // 00114 if (DestTy == Src->getType()) { // Check for a cast to same type as src!! 00115 PRINT_PEEPHOLE1("cast-of-self-ty", *CI); 00116 CI->replaceAllUsesWith(Src); 00117 if (!Src->hasName() && CI->hasName()) { 00118 std::string Name = CI->getName(); 00119 CI->setName(""); 00120 Src->setName(Name); 00121 } 00122 00123 // DCE the instruction now, to avoid having the iterative version of DCE 00124 // have to worry about it. 00125 // 00126 BI = BB->getInstList().erase(BI); 00127 00128 ++NumCastOfCast; 00129 return true; 00130 } 00131 00132 // Check to see if it's a cast of an instruction that does not depend on the 00133 // specific type of the operands to do it's job. 00134 if (!isReinterpretingCast(CI)) { 00135 ValueTypeCache ConvertedTypes; 00136 00137 // Check to see if we can convert the source of the cast to match the 00138 // destination type of the cast... 00139 // 00140 ConvertedTypes[CI] = CI->getType(); // Make sure the cast doesn't change 00141 if (ExpressionConvertibleToType(Src, DestTy, ConvertedTypes, TD)) { 00142 PRINT_PEEPHOLE3("CAST-SRC-EXPR-CONV:in ", *Src, *CI, *BB->getParent()); 00143 00144 DEBUG(std::cerr << "\nCONVERTING SRC EXPR TYPE:\n"); 00145 { // ValueMap must be destroyed before function verified! 00146 ValueMapCache ValueMap; 00147 Value *E = ConvertExpressionToType(Src, DestTy, ValueMap, TD); 00148 00149 if (Constant *CPV = dyn_cast<Constant>(E)) 00150 CI->replaceAllUsesWith(CPV); 00151 00152 PRINT_PEEPHOLE1("CAST-SRC-EXPR-CONV:out", *E); 00153 DEBUG(std::cerr << "DONE CONVERTING SRC EXPR TYPE: \n" 00154 << *BB->getParent()); 00155 } 00156 00157 BI = BB->begin(); // Rescan basic block. BI might be invalidated. 00158 ++NumExprTreesConv; 00159 return true; 00160 } 00161 00162 // Check to see if we can convert the users of the cast value to match the 00163 // source type of the cast... 00164 // 00165 ConvertedTypes.clear(); 00166 // Make sure the source doesn't change type 00167 ConvertedTypes[Src] = Src->getType(); 00168 if (ValueConvertibleToType(CI, Src->getType(), ConvertedTypes, TD)) { 00169 //PRINT_PEEPHOLE3("CAST-DEST-EXPR-CONV:in ", *Src, *CI, 00170 // *BB->getParent()); 00171 00172 DEBUG(std::cerr << "\nCONVERTING EXPR TYPE:\n"); 00173 { // ValueMap must be destroyed before function verified! 00174 ValueMapCache ValueMap; 00175 ConvertValueToNewType(CI, Src, ValueMap, TD); // This will delete CI! 00176 } 00177 00178 PRINT_PEEPHOLE1("CAST-DEST-EXPR-CONV:out", *Src); 00179 DEBUG(std::cerr << "DONE CONVERTING EXPR TYPE: \n\n" << 00180 *BB->getParent()); 00181 00182 BI = BB->begin(); // Rescan basic block. BI might be invalidated. 00183 ++NumExprTreesConv; 00184 return true; 00185 } 00186 } 00187 00188 // Check to see if we are casting from a structure pointer to a pointer to 00189 // the first element of the structure... to avoid munching other peepholes, 00190 // we only let this happen if there are no add uses of the cast. 00191 // 00192 // Peephole optimize the following instructions: 00193 // %t1 = cast {<...>} * %StructPtr to <ty> * 00194 // 00195 // Into: %t2 = getelementptr {<...>} * %StructPtr, <0, 0, 0, ...> 00196 // %t1 = cast <eltype> * %t1 to <ty> * 00197 // 00198 if (const CompositeType *CTy = getPointedToComposite(Src->getType())) 00199 if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) { 00200 00201 // Loop over uses of the cast, checking for add instructions. If an add 00202 // exists, this is probably a part of a more complex GEP, so we don't 00203 // want to mess around with the cast. 00204 // 00205 bool HasAddUse = false; 00206 for (Value::use_iterator I = CI->use_begin(), E = CI->use_end(); 00207 I != E; ++I) 00208 if (isa<Instruction>(*I) && 00209 cast<Instruction>(*I)->getOpcode() == Instruction::Add) { 00210 HasAddUse = true; break; 00211 } 00212 00213 // If it doesn't have an add use, check to see if the dest type is 00214 // losslessly convertible to one of the types in the start of the struct 00215 // type. 00216 // 00217 if (!HasAddUse) { 00218 const Type *DestPointedTy = DestPTy->getElementType(); 00219 unsigned Depth = 1; 00220 const CompositeType *CurCTy = CTy; 00221 const Type *ElTy = 0; 00222 00223 // Build the index vector, full of all zeros 00224 std::vector<Value*> Indices; 00225 00226 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00227 while (CurCTy && !isa<PointerType>(CurCTy)) { 00228 if (const StructType *CurSTy = dyn_cast<StructType>(CurCTy)) { 00229 // Check for a zero element struct type... if we have one, bail. 00230 if (CurSTy->getNumElements() == 0) break; 00231 00232 // Grab the first element of the struct type, which must lie at 00233 // offset zero in the struct. 00234 // 00235 ElTy = CurSTy->getElementType(0); 00236 } else { 00237 ElTy = cast<SequentialType>(CurCTy)->getElementType(); 00238 } 00239 00240 // Insert a zero to index through this type... 00241 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00242 00243 // Did we find what we're looking for? 00244 if (ElTy->isLosslesslyConvertibleTo(DestPointedTy)) break; 00245 00246 // Nope, go a level deeper. 00247 ++Depth; 00248 CurCTy = dyn_cast<CompositeType>(ElTy); 00249 ElTy = 0; 00250 } 00251 00252 // Did we find what we were looking for? If so, do the transformation 00253 if (ElTy) { 00254 PRINT_PEEPHOLE1("cast-for-first:in", *CI); 00255 00256 std::string Name = CI->getName(); CI->setName(""); 00257 00258 // Insert the new T cast instruction... stealing old T's name 00259 GetElementPtrInst *GEP = new GetElementPtrInst(Src, Indices, 00260 Name, BI); 00261 00262 // Make the old cast instruction reference the new GEP instead of 00263 // the old src value. 00264 // 00265 CI->setOperand(0, GEP); 00266 00267 PRINT_PEEPHOLE2("cast-for-first:out", *GEP, *CI); 00268 ++NumGEPInstFormed; 00269 return true; 00270 } 00271 } 00272 } 00273 00274 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00275 Value *Val = SI->getOperand(0); 00276 Value *Pointer = SI->getPointerOperand(); 00277 00278 // Peephole optimize the following instructions: 00279 // %t = cast <T1>* %P to <T2> * ;; If T1 is losslessly convertible to T2 00280 // store <T2> %V, <T2>* %t 00281 // 00282 // Into: 00283 // %t = cast <T2> %V to <T1> 00284 // store <T1> %t2, <T1>* %P 00285 // 00286 // Note: This is not taken care of by expr conversion because there might 00287 // not be a cast available for the store to convert the incoming value of. 00288 // This code is basically here to make sure that pointers don't have casts 00289 // if possible. 00290 // 00291 if (CastInst *CI = dyn_cast<CastInst>(Pointer)) 00292 if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType 00293 if (const PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType())) 00294 // convertible types? 00295 if (Val->getType()->isLosslesslyConvertibleTo(CSPT->getElementType())) { 00296 PRINT_PEEPHOLE3("st-src-cast:in ", *Pointer, *Val, *SI); 00297 00298 // Insert the new T cast instruction... stealing old T's name 00299 std::string Name(CI->getName()); CI->setName(""); 00300 CastInst *NCI = new CastInst(Val, CSPT->getElementType(), 00301 Name, BI); 00302 00303 // Replace the old store with a new one! 00304 ReplaceInstWithInst(BB->getInstList(), BI, 00305 SI = new StoreInst(NCI, CastSrc)); 00306 PRINT_PEEPHOLE3("st-src-cast:out", *NCI, *CastSrc, *SI); 00307 ++NumLoadStorePeepholes; 00308 return true; 00309 } 00310 00311 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00312 Value *Pointer = LI->getOperand(0); 00313 const Type *PtrElType = 00314 cast<PointerType>(Pointer->getType())->getElementType(); 00315 00316 // Peephole optimize the following instructions: 00317 // %Val = cast <T1>* to <T2>* ;; If T1 is losslessly convertible to T2 00318 // %t = load <T2>* %P 00319 // 00320 // Into: 00321 // %t = load <T1>* %P 00322 // %Val = cast <T1> to <T2> 00323 // 00324 // Note: This is not taken care of by expr conversion because there might 00325 // not be a cast available for the store to convert the incoming value of. 00326 // This code is basically here to make sure that pointers don't have casts 00327 // if possible. 00328 // 00329 if (CastInst *CI = dyn_cast<CastInst>(Pointer)) 00330 if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType 00331 if (const PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType())) 00332 // convertible types? 00333 if (PtrElType->isLosslesslyConvertibleTo(CSPT->getElementType())) { 00334 PRINT_PEEPHOLE2("load-src-cast:in ", *Pointer, *LI); 00335 00336 // Create the new load instruction... loading the pre-casted value 00337 LoadInst *NewLI = new LoadInst(CastSrc, LI->getName(), BI); 00338 00339 // Insert the new T cast instruction... stealing old T's name 00340 CastInst *NCI = new CastInst(NewLI, LI->getType(), CI->getName()); 00341 00342 // Replace the old store with a new one! 00343 ReplaceInstWithInst(BB->getInstList(), BI, NCI); 00344 PRINT_PEEPHOLE3("load-src-cast:out", *NCI, *CastSrc, *NewLI); 00345 ++NumLoadStorePeepholes; 00346 return true; 00347 } 00348 00349 } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 00350 // If we have a call with all varargs arguments, convert the call to use the 00351 // actual argument types present... 00352 // 00353 const PointerType *PTy = cast<PointerType>(CI->getCalledValue()->getType()); 00354 const FunctionType *FTy = cast<FunctionType>(PTy->getElementType()); 00355 00356 // Is the call to a vararg variable with no real parameters? 00357 if (FTy->isVarArg() && FTy->getNumParams() == 0 && 00358 !CI->getCalledFunction()) { 00359 // If so, insert a new cast instruction, casting it to a function type 00360 // that matches the current arguments... 00361 // 00362 std::vector<const Type *> Params; // Parameter types... 00363 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) 00364 Params.push_back(CI->getOperand(i)->getType()); 00365 00366 FunctionType *NewFT = FunctionType::get(FTy->getReturnType(), 00367 Params, false); 00368 PointerType *NewPFunTy = PointerType::get(NewFT); 00369 00370 // Create a new cast, inserting it right before the function call... 00371 Value *NewCast; 00372 Constant *ConstantCallSrc = 0; 00373 if (Constant *CS = dyn_cast<Constant>(CI->getCalledValue())) 00374 ConstantCallSrc = CS; 00375 00376 if (ConstantCallSrc) 00377 NewCast = ConstantExpr::getCast(ConstantCallSrc, NewPFunTy); 00378 else 00379 NewCast = new CastInst(CI->getCalledValue(), NewPFunTy, 00380 CI->getCalledValue()->getName()+"_c",CI); 00381 00382 // Create a new call instruction... 00383 CallInst *NewCall = new CallInst(NewCast, 00384 std::vector<Value*>(CI->op_begin()+1, CI->op_end())); 00385 if (CI->isTailCall()) NewCall->setTailCall(); 00386 NewCall->setCallingConv(CI->getCallingConv()); 00387 ++BI; 00388 ReplaceInstWithInst(CI, NewCall); 00389 00390 ++NumVarargCallChanges; 00391 return true; 00392 } 00393 00394 } 00395 00396 return false; 00397 } 00398 00399 00400 00401 00402 bool RPR::DoRaisePass(Function &F) { 00403 bool Changed = false; 00404 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) 00405 for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) { 00406 DEBUG(std::cerr << "LevelRaising: " << *BI); 00407 if (dceInstruction(BI) || doConstantPropagation(BI)) { 00408 Changed = true; 00409 ++NumDCEorCP; 00410 DEBUG(std::cerr << "***\t\t^^-- Dead code eliminated!\n"); 00411 } else if (PeepholeOptimize(BB, BI)) { 00412 Changed = true; 00413 } else { 00414 ++BI; 00415 } 00416 } 00417 00418 return Changed; 00419 } 00420 00421 00422 // runOnFunction - Raise a function representation to a higher level. 00423 bool RPR::runOnFunction(Function &F) { 00424 DEBUG(std::cerr << "\n\n\nStarting to work on Function '" << F.getName() 00425 << "'\n"); 00426 00427 // Insert casts for all incoming pointer pointer values that are treated as 00428 // arrays... 00429 // 00430 bool Changed = false, LocalChange; 00431 00432 // If the StartInst option was specified, then Peephole optimize that 00433 // instruction first if it occurs in this function. 00434 // 00435 if (!StartInst.empty()) { 00436 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) 00437 for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) 00438 if (BI->getName() == StartInst) { 00439 bool SavedDebug = DebugFlag; // Save the DEBUG() controlling flag. 00440 DebugFlag = true; // Turn on DEBUG's 00441 Changed |= PeepholeOptimize(BB, BI); 00442 DebugFlag = SavedDebug; // Restore DebugFlag to previous state 00443 } 00444 } 00445 00446 do { 00447 DEBUG(std::cerr << "Looping: \n" << F); 00448 00449 // Iterate over the function, refining it, until it converges on a stable 00450 // state 00451 LocalChange = false; 00452 while (DoRaisePass(F)) LocalChange = true; 00453 Changed |= LocalChange; 00454 00455 } while (LocalChange); 00456 00457 return Changed; 00458 } 00459