lib/Transforms/IPO/IPConstantPropagation.cpp

   1 //===-- IPConstantPropagation.cpp - Propagate constants through calls -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass implements an _extremely_ simple interprocedural constant
  11 // propagation pass.  It could certainly be improved in many different ways,
  12 // like using a worklist.  This pass makes arguments dead, but does not remove
  13 // them.  The existing dead argument elimination pass should be run after this
  14 // to clean up the mess.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "ipconstprop"
  19 #include "llvm/Transforms/IPO.h"
  20 #include "llvm/Constants.h"
  21 #include "llvm/Instructions.h"
  22 #include "llvm/Module.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/CallSite.h"
  25 #include "llvm/Support/Compiler.h"
  26 #include "llvm/ADT/Statistic.h"
  27 using namespace llvm;
  28
  29 STATISTIC(NumArgumentsProped, "Number of args turned into constants");
  30 STATISTIC(NumReturnValProped, "Number of return values turned into constants");
  31
  32 namespace {
  33   /// IPCP - The interprocedural constant propagation pass
  34   ///
  35   struct VISIBILITY_HIDDEN IPCP : public ModulePass {
  36     static const char ID; // Pass identifcation, replacement for typeid
  37     IPCP() : ModulePass((intptr_t)&ID) {}
  38
  39     bool runOnModule(Module &M);
  40   private:
  41     bool PropagateConstantsIntoArguments(Function &F);
  42     bool PropagateConstantReturn(Function &F);
  43   };
  44   const char IPCP::ID = 0;
  45   RegisterPass<IPCP> X("ipconstprop", "Interprocedural constant propagation");
  46 }
  47
  48 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
  49
  50 bool IPCP::runOnModule(Module &M) {
  51   bool Changed = false;
  52   bool LocalChange = true;
  53
  54   // FIXME: instead of using smart algorithms, we just iterate until we stop
  55   // making changes.
  56   while (LocalChange) {
  57     LocalChange = false;
  58     for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  59       if (!I->isDeclaration()) {
  60         // Delete any klingons.
  61         I->removeDeadConstantUsers();
  62         if (I->hasInternalLinkage())
  63           LocalChange |= PropagateConstantsIntoArguments(*I);
  64         Changed |= PropagateConstantReturn(*I);
  65       }
  66     Changed |= LocalChange;
  67   }
  68   return Changed;
  69 }
  70
  71 /// PropagateConstantsIntoArguments - Look at all uses of the specified
  72 /// function.  If all uses are direct call sites, and all pass a particular
  73 /// constant in for an argument, propagate that constant in as the argument.
  74 ///
  75 bool IPCP::PropagateConstantsIntoArguments(Function &F) {
  76   if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
  77
  78   std::vector<std::pair<Constant*, bool> > ArgumentConstants;
  79   ArgumentConstants.resize(F.arg_size());
  80
  81   unsigned NumNonconstant = 0;
  82
  83   for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I)
  84     if (!isa<Instruction>(*I))
  85       return false;  // Used by a non-instruction, do not transform
  86     else {
  87       CallSite CS = CallSite::get(cast<Instruction>(*I));
  88       if (CS.getInstruction() == 0 ||
  89           CS.getCalledFunction() != &F)
  90         return false;  // Not a direct call site?
  91
  92       // Check out all of the potentially constant arguments
  93       CallSite::arg_iterator AI = CS.arg_begin();
  94       Function::arg_iterator Arg = F.arg_begin();
  95       for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
  96            ++i, ++AI, ++Arg) {
  97         if (*AI == &F) return false;  // Passes the function into itself
  98
  99         if (!ArgumentConstants[i].second) {
 100           if (Constant *C = dyn_cast<Constant>(*AI)) {
 101             if (!ArgumentConstants[i].first)
 102               ArgumentConstants[i].first = C;
 103             else if (ArgumentConstants[i].first != C) {
 104               // Became non-constant
 105               ArgumentConstants[i].second = true;
 106               ++NumNonconstant;
 107               if (NumNonconstant == ArgumentConstants.size()) return false;
 108             }
 109           } else if (*AI != &*Arg) {    // Ignore recursive calls with same arg
 110             // This is not a constant argument.  Mark the argument as
 111             // non-constant.
 112             ArgumentConstants[i].second = true;
 113             ++NumNonconstant;
 114             if (NumNonconstant == ArgumentConstants.size()) return false;
 115           }
 116         }
 117       }
 118     }
 119
 120   // If we got to this point, there is a constant argument!
 121   assert(NumNonconstant != ArgumentConstants.size());
 122   Function::arg_iterator AI = F.arg_begin();
 123   bool MadeChange = false;
 124   for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI)
 125     // Do we have a constant argument!?
 126     if (!ArgumentConstants[i].second && !AI->use_empty()) {
 127       Value *V = ArgumentConstants[i].first;
 128       if (V == 0) V = UndefValue::get(AI->getType());
 129       AI->replaceAllUsesWith(V);
 130       ++NumArgumentsProped;
 131       MadeChange = true;
 132     }
 133   return MadeChange;
 134 }
 135
 136
 137 // Check to see if this function returns a constant.  If so, replace all callers
 138 // that user the return value with the returned valued.  If we can replace ALL
 139 // callers,
 140 bool IPCP::PropagateConstantReturn(Function &F) {
 141   if (F.getReturnType() == Type::VoidTy)
 142     return false; // No return value.
 143
 144   // Check to see if this function returns a constant.
 145   Value *RetVal = 0;
 146   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 147     if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
 148       if (isa<UndefValue>(RI->getOperand(0))) {
 149         // Ignore.
 150       } else if (Constant *C = dyn_cast<Constant>(RI->getOperand(0))) {
 151         if (RetVal == 0)
 152           RetVal = C;
 153         else if (RetVal != C)
 154           return false;  // Does not return the same constant.
 155       } else {
 156         return false;  // Does not return a constant.
 157       }
 158
 159   if (RetVal == 0) RetVal = UndefValue::get(F.getReturnType());
 160
 161   // If we got here, the function returns a constant value.  Loop over all
 162   // users, replacing any uses of the return value with the returned constant.
 163   bool ReplacedAllUsers = true;
 164   bool MadeChange = false;
 165   for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I)
 166     if (!isa<Instruction>(*I))
 167       ReplacedAllUsers = false;
 168     else {
 169       CallSite CS = CallSite::get(cast<Instruction>(*I));
 170       if (CS.getInstruction() == 0 ||
 171           CS.getCalledFunction() != &F) {
 172         ReplacedAllUsers = false;
 173       } else {
 174         if (!CS.getInstruction()->use_empty()) {
 175           CS.getInstruction()->replaceAllUsesWith(RetVal);
 176           MadeChange = true;
 177         }
 178       }
 179     }
 180
 181   // If we replace all users with the returned constant, and there can be no
 182   // other callers of the function, replace the constant being returned in the
 183   // function with an undef value.
 184   if (ReplacedAllUsers && F.hasInternalLinkage() && !isa<UndefValue>(RetVal)) {
 185     Value *RV = UndefValue::get(RetVal->getType());
 186     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 187       if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
 188         if (RI->getOperand(0) != RV) {
 189           RI->setOperand(0, RV);
 190           MadeChange = true;
 191         }
 192       }
 193   }
 194
 195   if (MadeChange) ++NumReturnValProped;
 196   return MadeChange;
 197 }