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/ADT/Statistic.h"
  26 using namespace llvm;
  27
  28 STATISTIC(NumArgumentsProped, "Number of args turned into constants");
  29 STATISTIC(NumReturnValProped, "Number of return values turned into constants");
  30
  31 namespace {
  32   /// IPCP - The interprocedural constant propagation pass
  33   ///
  34   struct IPCP : public ModulePass {
  35     bool runOnModule(Module &M);
  36   private:
  37     bool PropagateConstantsIntoArguments(Function &F);
  38     bool PropagateConstantReturn(Function &F);
  39   };
  40   RegisterPass<IPCP> X("ipconstprop", "Interprocedural constant propagation");
  41 }
  42
  43 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
  44
  45 bool IPCP::runOnModule(Module &M) {
  46   bool Changed = false;
  47   bool LocalChange = true;
  48
  49   // FIXME: instead of using smart algorithms, we just iterate until we stop
  50   // making changes.
  51   while (LocalChange) {
  52     LocalChange = false;
  53     for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  54       if (!I->isDeclaration()) {
  55         // Delete any klingons.
  56         I->removeDeadConstantUsers();
  57         if (I->hasInternalLinkage())
  58           LocalChange |= PropagateConstantsIntoArguments(*I);
  59         Changed |= PropagateConstantReturn(*I);
  60       }
  61     Changed |= LocalChange;
  62   }
  63   return Changed;
  64 }
  65
  66 /// PropagateConstantsIntoArguments - Look at all uses of the specified
  67 /// function.  If all uses are direct call sites, and all pass a particular
  68 /// constant in for an argument, propagate that constant in as the argument.
  69 ///
  70 bool IPCP::PropagateConstantsIntoArguments(Function &F) {
  71   if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
  72
  73   std::vector<std::pair<Constant*, bool> > ArgumentConstants;
  74   ArgumentConstants.resize(F.arg_size());
  75
  76   unsigned NumNonconstant = 0;
  77
  78   for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I)
  79     if (!isa<Instruction>(*I))
  80       return false;  // Used by a non-instruction, do not transform
  81     else {
  82       CallSite CS = CallSite::get(cast<Instruction>(*I));
  83       if (CS.getInstruction() == 0 ||
  84           CS.getCalledFunction() != &F)
  85         return false;  // Not a direct call site?
  86
  87       // Check out all of the potentially constant arguments
  88       CallSite::arg_iterator AI = CS.arg_begin();
  89       Function::arg_iterator Arg = F.arg_begin();
  90       for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
  91            ++i, ++AI, ++Arg) {
  92         if (*AI == &F) return false;  // Passes the function into itself
  93
  94         if (!ArgumentConstants[i].second) {
  95           if (Constant *C = dyn_cast<Constant>(*AI)) {
  96             if (!ArgumentConstants[i].first)
  97               ArgumentConstants[i].first = C;
  98             else if (ArgumentConstants[i].first != C) {
  99               // Became non-constant
 100               ArgumentConstants[i].second = true;
 101               ++NumNonconstant;
 102               if (NumNonconstant == ArgumentConstants.size()) return false;
 103             }
 104           } else if (*AI != &*Arg) {    // Ignore recursive calls with same arg
 105             // This is not a constant argument.  Mark the argument as
 106             // non-constant.
 107             ArgumentConstants[i].second = true;
 108             ++NumNonconstant;
 109             if (NumNonconstant == ArgumentConstants.size()) return false;
 110           }
 111         }
 112       }
 113     }
 114
 115   // If we got to this point, there is a constant argument!
 116   assert(NumNonconstant != ArgumentConstants.size());
 117   Function::arg_iterator AI = F.arg_begin();
 118   bool MadeChange = false;
 119   for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI)
 120     // Do we have a constant argument!?
 121     if (!ArgumentConstants[i].second && !AI->use_empty()) {
 122       Value *V = ArgumentConstants[i].first;
 123       if (V == 0) V = UndefValue::get(AI->getType());
 124       AI->replaceAllUsesWith(V);
 125       ++NumArgumentsProped;
 126       MadeChange = true;
 127     }
 128   return MadeChange;
 129 }
 130
 131
 132 // Check to see if this function returns a constant.  If so, replace all callers
 133 // that user the return value with the returned valued.  If we can replace ALL
 134 // callers,
 135 bool IPCP::PropagateConstantReturn(Function &F) {
 136   if (F.getReturnType() == Type::VoidTy)
 137     return false; // No return value.
 138
 139   // Check to see if this function returns a constant.
 140   Value *RetVal = 0;
 141   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 142     if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
 143       if (isa<UndefValue>(RI->getOperand(0))) {
 144         // Ignore.
 145       } else if (Constant *C = dyn_cast<Constant>(RI->getOperand(0))) {
 146         if (RetVal == 0)
 147           RetVal = C;
 148         else if (RetVal != C)
 149           return false;  // Does not return the same constant.
 150       } else {
 151         return false;  // Does not return a constant.
 152       }
 153
 154   if (RetVal == 0) RetVal = UndefValue::get(F.getReturnType());
 155
 156   // If we got here, the function returns a constant value.  Loop over all
 157   // users, replacing any uses of the return value with the returned constant.
 158   bool ReplacedAllUsers = true;
 159   bool MadeChange = false;
 160   for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I)
 161     if (!isa<Instruction>(*I))
 162       ReplacedAllUsers = false;
 163     else {
 164       CallSite CS = CallSite::get(cast<Instruction>(*I));
 165       if (CS.getInstruction() == 0 ||
 166           CS.getCalledFunction() != &F) {
 167         ReplacedAllUsers = false;
 168       } else {
 169         if (!CS.getInstruction()->use_empty()) {
 170           CS.getInstruction()->replaceAllUsesWith(RetVal);
 171           MadeChange = true;
 172         }
 173       }
 174     }
 175
 176   // If we replace all users with the returned constant, and there can be no
 177   // other callers of the function, replace the constant being returned in the
 178   // function with an undef value.
 179   if (ReplacedAllUsers && F.hasInternalLinkage() && !isa<UndefValue>(RetVal)) {
 180     Value *RV = UndefValue::get(RetVal->getType());
 181     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 182       if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
 183         if (RI->getOperand(0) != RV) {
 184           RI->setOperand(0, RV);
 185           MadeChange = true;
 186         }
 187       }
 188   }
 189
 190   if (MadeChange) ++NumReturnValProped;
 191   return MadeChange;
 192 }