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 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 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/Constants.h"
00020 #include "llvm/Instructions.h"
00021 #include "llvm/Module.h"
00022 #include "llvm/Pass.h"
00023 #include "llvm/Support/CallSite.h"
00024 #include "llvm/ADT/Statistic.h"
00025 using namespace llvm;
00026 
00027 namespace {
00028   Statistic<> NumArgumentsProped("ipconstprop",
00029                                  "Number of args turned into constants");
00030   Statistic<> NumReturnValProped("ipconstprop",
00031                                  "Number of return values turned into constants");
00032 
00033   /// IPCP - The interprocedural constant propagation pass
00034   ///
00035   struct IPCP : public ModulePass {
00036     bool runOnModule(Module &M);
00037   private:
00038     bool PropagateConstantsIntoArguments(Function &F);
00039     bool PropagateConstantReturn(Function &F);
00040   };
00041   RegisterOpt<IPCP> X("ipconstprop", "Interprocedural constant propagation");
00042 }
00043 
00044 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
00045 
00046 bool IPCP::runOnModule(Module &M) {
00047   bool Changed = false;
00048   bool LocalChange = true;
00049 
00050   // FIXME: instead of using smart algorithms, we just iterate until we stop
00051   // making changes.
00052   while (LocalChange) {
00053     LocalChange = false;
00054     for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00055       if (!I->isExternal()) {
00056         // Delete any klingons.
00057         I->removeDeadConstantUsers();
00058         if (I->hasInternalLinkage())
00059           LocalChange |= PropagateConstantsIntoArguments(*I);
00060         Changed |= PropagateConstantReturn(*I);
00061       }
00062     Changed |= LocalChange;
00063   }
00064   return Changed;
00065 }
00066 
00067 /// PropagateConstantsIntoArguments - Look at all uses of the specified
00068 /// function.  If all uses are direct call sites, and all pass a particular
00069 /// constant in for an argument, propagate that constant in as the argument.
00070 ///
00071 bool IPCP::PropagateConstantsIntoArguments(Function &F) {
00072   if (F.arg_empty() || F.use_empty()) return false;  // No arguments?  Early exit.
00073 
00074   std::vector<std::pair<Constant*, bool> > ArgumentConstants;
00075   ArgumentConstants.resize(F.arg_size());
00076 
00077   unsigned NumNonconstant = 0;
00078 
00079   for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I)
00080     if (!isa<Instruction>(*I))
00081       return false;  // Used by a non-instruction, do not transform
00082     else {
00083       CallSite CS = CallSite::get(cast<Instruction>(*I));
00084       if (CS.getInstruction() == 0 ||
00085           CS.getCalledFunction() != &F)
00086         return false;  // Not a direct call site?
00087 
00088       // Check out all of the potentially constant arguments
00089       CallSite::arg_iterator AI = CS.arg_begin();
00090       Function::arg_iterator Arg = F.arg_begin();
00091       for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
00092            ++i, ++AI, ++Arg) {
00093         if (*AI == &F) return false;  // Passes the function into itself
00094 
00095         if (!ArgumentConstants[i].second) {
00096           if (Constant *C = dyn_cast<Constant>(*AI)) {
00097             if (!ArgumentConstants[i].first)
00098               ArgumentConstants[i].first = C;
00099             else if (ArgumentConstants[i].first != C) {
00100               // Became non-constant
00101               ArgumentConstants[i].second = true;
00102               ++NumNonconstant;
00103               if (NumNonconstant == ArgumentConstants.size()) return false;
00104             }
00105           } else if (*AI != &*Arg) {    // Ignore recursive calls with same arg
00106             // This is not a constant argument.  Mark the argument as
00107             // non-constant.
00108             ArgumentConstants[i].second = true;
00109             ++NumNonconstant;
00110             if (NumNonconstant == ArgumentConstants.size()) return false;
00111           }
00112         }
00113       }
00114     }
00115 
00116   // If we got to this point, there is a constant argument!
00117   assert(NumNonconstant != ArgumentConstants.size());
00118   Function::arg_iterator AI = F.arg_begin();
00119   bool MadeChange = false;
00120   for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI)
00121     // Do we have a constant argument!?
00122     if (!ArgumentConstants[i].second && !AI->use_empty()) {
00123       Value *V = ArgumentConstants[i].first;
00124       if (V == 0) V = UndefValue::get(AI->getType());
00125       AI->replaceAllUsesWith(V);
00126       ++NumArgumentsProped;
00127       MadeChange = true;
00128     }
00129   return MadeChange;
00130 }
00131 
00132 
00133 // Check to see if this function returns a constant.  If so, replace all callers
00134 // that user the return value with the returned valued.  If we can replace ALL
00135 // callers,
00136 bool IPCP::PropagateConstantReturn(Function &F) {
00137   if (F.getReturnType() == Type::VoidTy)
00138     return false; // No return value.
00139 
00140   // Check to see if this function returns a constant.
00141   Value *RetVal = 0;
00142   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00143     if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
00144       if (isa<UndefValue>(RI->getOperand(0))) {
00145         // Ignore.
00146       } else if (Constant *C = dyn_cast<Constant>(RI->getOperand(0))) {
00147         if (RetVal == 0)
00148           RetVal = C;
00149         else if (RetVal != C)
00150           return false;  // Does not return the same constant.
00151       } else {
00152         return false;  // Does not return a constant.
00153       }
00154 
00155   if (RetVal == 0) RetVal = UndefValue::get(F.getReturnType());
00156 
00157   // If we got here, the function returns a constant value.  Loop over all
00158   // users, replacing any uses of the return value with the returned constant.
00159   bool ReplacedAllUsers = true;
00160   bool MadeChange = false;
00161   for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I)
00162     if (!isa<Instruction>(*I))
00163       ReplacedAllUsers = false;
00164     else {
00165       CallSite CS = CallSite::get(cast<Instruction>(*I));
00166       if (CS.getInstruction() == 0 ||
00167           CS.getCalledFunction() != &F) {
00168         ReplacedAllUsers = false;
00169       } else {
00170         if (!CS.getInstruction()->use_empty()) {
00171           CS.getInstruction()->replaceAllUsesWith(RetVal);
00172           MadeChange = true;
00173         }
00174       }
00175     }
00176 
00177   // If we replace all users with the returned constant, and there can be no
00178   // other callers of the function, replace the constant being returned in the
00179   // function with an undef value.
00180   if (ReplacedAllUsers && F.hasInternalLinkage() && !isa<UndefValue>(RetVal)) {
00181     Value *RV = UndefValue::get(RetVal->getType());
00182     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00183       if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
00184         if (RI->getOperand(0) != RV) {
00185           RI->setOperand(0, RV);
00186           MadeChange = true;
00187         }
00188       }
00189   }
00190 
00191   if (MadeChange) ++NumReturnValProped;
00192   return MadeChange;
00193 }