LLVM API Documentation

IPConstantPropagation.cpp
Go to the documentation of this file.
00001 //===-- IPConstantPropagation.cpp - Propagate constants through calls -----===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass implements an _extremely_ simple interprocedural constant
00011 // propagation pass.  It could certainly be improved in many different ways,
00012 // like using a worklist.  This pass makes arguments dead, but does not remove
00013 // them.  The existing dead argument elimination pass should be run after this
00014 // to clean up the mess.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #include "llvm/Transforms/IPO.h"
00019 #include "llvm/ADT/SmallVector.h"
00020 #include "llvm/ADT/Statistic.h"
00021 #include "llvm/Analysis/ValueTracking.h"
00022 #include "llvm/IR/CallSite.h"
00023 #include "llvm/IR/Constants.h"
00024 #include "llvm/IR/Instructions.h"
00025 #include "llvm/IR/Module.h"
00026 #include "llvm/Pass.h"
00027 using namespace llvm;
00028 
00029 #define DEBUG_TYPE "ipconstprop"
00030 
00031 STATISTIC(NumArgumentsProped, "Number of args turned into constants");
00032 STATISTIC(NumReturnValProped, "Number of return values turned into constants");
00033 
00034 namespace {
00035   /// IPCP - The interprocedural constant propagation pass
00036   ///
00037   struct IPCP : public ModulePass {
00038     static char ID; // Pass identification, replacement for typeid
00039     IPCP() : ModulePass(ID) {
00040       initializeIPCPPass(*PassRegistry::getPassRegistry());
00041     }
00042 
00043     bool runOnModule(Module &M) override;
00044   private:
00045     bool PropagateConstantsIntoArguments(Function &F);
00046     bool PropagateConstantReturn(Function &F);
00047   };
00048 }
00049 
00050 char IPCP::ID = 0;
00051 INITIALIZE_PASS(IPCP, "ipconstprop",
00052                 "Interprocedural constant propagation", false, false)
00053 
00054 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
00055 
00056 bool IPCP::runOnModule(Module &M) {
00057   bool Changed = false;
00058   bool LocalChange = true;
00059 
00060   // FIXME: instead of using smart algorithms, we just iterate until we stop
00061   // making changes.
00062   while (LocalChange) {
00063     LocalChange = false;
00064     for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00065       if (!I->isDeclaration()) {
00066         // Delete any klingons.
00067         I->removeDeadConstantUsers();
00068         if (I->hasLocalLinkage())
00069           LocalChange |= PropagateConstantsIntoArguments(*I);
00070         Changed |= PropagateConstantReturn(*I);
00071       }
00072     Changed |= LocalChange;
00073   }
00074   return Changed;
00075 }
00076 
00077 /// PropagateConstantsIntoArguments - Look at all uses of the specified
00078 /// function.  If all uses are direct call sites, and all pass a particular
00079 /// constant in for an argument, propagate that constant in as the argument.
00080 ///
00081 bool IPCP::PropagateConstantsIntoArguments(Function &F) {
00082   if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
00083 
00084   // For each argument, keep track of its constant value and whether it is a
00085   // constant or not.  The bool is driven to true when found to be non-constant.
00086   SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
00087   ArgumentConstants.resize(F.arg_size());
00088 
00089   unsigned NumNonconstant = 0;
00090   for (Use &U : F.uses()) {
00091     User *UR = U.getUser();
00092     // Ignore blockaddress uses.
00093     if (isa<BlockAddress>(UR)) continue;
00094     
00095     // Used by a non-instruction, or not the callee of a function, do not
00096     // transform.
00097     if (!isa<CallInst>(UR) && !isa<InvokeInst>(UR))
00098       return false;
00099     
00100     CallSite CS(cast<Instruction>(UR));
00101     if (!CS.isCallee(&U))
00102       return false;
00103 
00104     // Check out all of the potentially constant arguments.  Note that we don't
00105     // inspect varargs here.
00106     CallSite::arg_iterator AI = CS.arg_begin();
00107     Function::arg_iterator Arg = F.arg_begin();
00108     for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
00109          ++i, ++AI, ++Arg) {
00110       
00111       // If this argument is known non-constant, ignore it.
00112       if (ArgumentConstants[i].second)
00113         continue;
00114       
00115       Constant *C = dyn_cast<Constant>(*AI);
00116       if (C && ArgumentConstants[i].first == 0) {
00117         ArgumentConstants[i].first = C;   // First constant seen.
00118       } else if (C && ArgumentConstants[i].first == C) {
00119         // Still the constant value we think it is.
00120       } else if (*AI == &*Arg) {
00121         // Ignore recursive calls passing argument down.
00122       } else {
00123         // Argument became non-constant.  If all arguments are non-constant now,
00124         // give up on this function.
00125         if (++NumNonconstant == ArgumentConstants.size())
00126           return false;
00127         ArgumentConstants[i].second = true;
00128       }
00129     }
00130   }
00131 
00132   // If we got to this point, there is a constant argument!
00133   assert(NumNonconstant != ArgumentConstants.size());
00134   bool MadeChange = false;
00135   Function::arg_iterator AI = F.arg_begin();
00136   for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
00137     // Do we have a constant argument?
00138     if (ArgumentConstants[i].second || AI->use_empty() ||
00139         AI->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory()))
00140       continue;
00141   
00142     Value *V = ArgumentConstants[i].first;
00143     if (V == 0) V = UndefValue::get(AI->getType());
00144     AI->replaceAllUsesWith(V);
00145     ++NumArgumentsProped;
00146     MadeChange = true;
00147   }
00148   return MadeChange;
00149 }
00150 
00151 
00152 // Check to see if this function returns one or more constants. If so, replace
00153 // all callers that use those return values with the constant value. This will
00154 // leave in the actual return values and instructions, but deadargelim will
00155 // clean that up.
00156 //
00157 // Additionally if a function always returns one of its arguments directly,
00158 // callers will be updated to use the value they pass in directly instead of
00159 // using the return value.
00160 bool IPCP::PropagateConstantReturn(Function &F) {
00161   if (F.getReturnType()->isVoidTy())
00162     return false; // No return value.
00163 
00164   // If this function could be overridden later in the link stage, we can't
00165   // propagate information about its results into callers.
00166   if (F.mayBeOverridden())
00167     return false;
00168     
00169   // Check to see if this function returns a constant.
00170   SmallVector<Value *,4> RetVals;
00171   StructType *STy = dyn_cast<StructType>(F.getReturnType());
00172   if (STy)
00173     for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) 
00174       RetVals.push_back(UndefValue::get(STy->getElementType(i)));
00175   else
00176     RetVals.push_back(UndefValue::get(F.getReturnType()));
00177 
00178   unsigned NumNonConstant = 0;
00179   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00180     if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
00181       for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
00182         // Already found conflicting return values?
00183         Value *RV = RetVals[i];
00184         if (!RV)
00185           continue;
00186 
00187         // Find the returned value
00188         Value *V;
00189         if (!STy)
00190           V = RI->getOperand(0);
00191         else
00192           V = FindInsertedValue(RI->getOperand(0), i);
00193 
00194         if (V) {
00195           // Ignore undefs, we can change them into anything
00196           if (isa<UndefValue>(V))
00197             continue;
00198           
00199           // Try to see if all the rets return the same constant or argument.
00200           if (isa<Constant>(V) || isa<Argument>(V)) {
00201             if (isa<UndefValue>(RV)) {
00202               // No value found yet? Try the current one.
00203               RetVals[i] = V;
00204               continue;
00205             }
00206             // Returning the same value? Good.
00207             if (RV == V)
00208               continue;
00209           }
00210         }
00211         // Different or no known return value? Don't propagate this return
00212         // value.
00213         RetVals[i] = 0;
00214         // All values non-constant? Stop looking.
00215         if (++NumNonConstant == RetVals.size())
00216           return false;
00217       }
00218     }
00219 
00220   // If we got here, the function returns at least one constant value.  Loop
00221   // over all users, replacing any uses of the return value with the returned
00222   // constant.
00223   bool MadeChange = false;
00224   for (Use &U : F.uses()) {
00225     CallSite CS(U.getUser());
00226     Instruction* Call = CS.getInstruction();
00227 
00228     // Not a call instruction or a call instruction that's not calling F
00229     // directly?
00230     if (!Call || !CS.isCallee(&U))
00231       continue;
00232     
00233     // Call result not used?
00234     if (Call->use_empty())
00235       continue;
00236 
00237     MadeChange = true;
00238 
00239     if (STy == 0) {
00240       Value* New = RetVals[0];
00241       if (Argument *A = dyn_cast<Argument>(New))
00242         // Was an argument returned? Then find the corresponding argument in
00243         // the call instruction and use that.
00244         New = CS.getArgument(A->getArgNo());
00245       Call->replaceAllUsesWith(New);
00246       continue;
00247     }
00248 
00249     for (auto I = Call->user_begin(), E = Call->user_end(); I != E;) {
00250       Instruction *Ins = cast<Instruction>(*I);
00251 
00252       // Increment now, so we can remove the use
00253       ++I;
00254 
00255       // Find the index of the retval to replace with
00256       int index = -1;
00257       if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
00258         if (EV->hasIndices())
00259           index = *EV->idx_begin();
00260 
00261       // If this use uses a specific return value, and we have a replacement,
00262       // replace it.
00263       if (index != -1) {
00264         Value *New = RetVals[index];
00265         if (New) {
00266           if (Argument *A = dyn_cast<Argument>(New))
00267             // Was an argument returned? Then find the corresponding argument in
00268             // the call instruction and use that.
00269             New = CS.getArgument(A->getArgNo());
00270           Ins->replaceAllUsesWith(New);
00271           Ins->eraseFromParent();
00272         }
00273       }
00274     }
00275   }
00276 
00277   if (MadeChange) ++NumReturnValProped;
00278   return MadeChange;
00279 }