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     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