LLVM API Documentation

LevelRaise.cpp

Go to the documentation of this file.
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