lib/Transforms/Scalar/ValuePropagation.cpp

   1 //===- ValuePropagation.cpp - Propagate information derived control flow --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the Value Propagation pass.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "value-propagation"
  15 #include "llvm/Transforms/Scalar.h"
  16 #include "llvm/Function.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/Pass.h"
  19 #include "llvm/Analysis/LazyValueInfo.h"
  20 #include "llvm/Transforms/Utils/Local.h"
  21 #include "llvm/ADT/Statistic.h"
  22 using namespace llvm;
  23
  24 STATISTIC(NumPhis,    "Number of phis propagated");
  25 STATISTIC(NumSelects, "Number of selects propagated");
  26
  27 namespace {
  28   class ValuePropagation : public FunctionPass {
  29     LazyValueInfo *LVI;
  30
  31     bool processSelect(SelectInst *SI);
  32     bool processPHI(PHINode *P);
  33
  34   public:
  35     static char ID;
  36     ValuePropagation(): FunctionPass(ID) { }
  37
  38     bool runOnFunction(Function &F);
  39
  40     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  41       AU.addRequired<LazyValueInfo>();
  42     }
  43   };
  44 }
  45
  46 char ValuePropagation::ID = 0;
  47 INITIALIZE_PASS(ValuePropagation, "value-propagation",
  48                 "Value Propagation", false, false);
  49
  50 // Public interface to the Value Propagation pass
  51 Pass *llvm::createValuePropagationPass() {
  52   return new ValuePropagation();
  53 }
  54
  55 bool ValuePropagation::processSelect(SelectInst *S) {
  56   Constant *C = LVI->getConstant(S->getOperand(0), S->getParent());
  57   if (!C) return false;
  58
  59   ConstantInt *CI = dyn_cast<ConstantInt>(C);
  60   if (!CI) return false;
  61
  62   if (CI->isZero()) {
  63     S->replaceAllUsesWith(S->getOperand(2));
  64     S->eraseFromParent();
  65   } else if (CI->isOne()) {
  66     S->replaceAllUsesWith(S->getOperand(1));
  67     S->eraseFromParent();
  68   } else {
  69     assert(0 && "Select on constant is neither 0 nor 1?");
  70   }
  71
  72   ++NumSelects;
  73
  74   return true;
  75 }
  76
  77 bool ValuePropagation::processPHI(PHINode *P) {
  78   bool changed = false;
  79
  80   BasicBlock *BB = P->getParent();
  81   for (unsigned i = 0; i < P->getNumIncomingValues(); ++i) {
  82     Constant *C = LVI->getConstantOnEdge(P->getIncomingValue(i),
  83                                          P->getIncomingBlock(i),
  84                                          BB);
  85     if (!C || C == P->getIncomingValue(i)) continue;
  86
  87     P->setIncomingValue(i, C);
  88     changed = true;
  89   }
  90
  91   if (Value *ConstVal = P->hasConstantValue()) {
  92     P->replaceAllUsesWith(ConstVal);
  93     P->eraseFromParent();
  94     changed = true;
  95   }
  96
  97   ++NumPhis;
  98
  99   return changed;
 100 }
 101
 102 bool ValuePropagation::runOnFunction(Function &F) {
 103   LVI = &getAnalysis<LazyValueInfo>();
 104
 105   bool changed = false;
 106
 107   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
 108     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
 109       Instruction *II = BI++;
 110       if (SelectInst *SI = dyn_cast<SelectInst>(II))
 111         changed |= processSelect(SI);
 112       else if (PHINode *P = dyn_cast<PHINode>(II))
 113         changed |= processPHI(P);
 114     }
 115
 116   if (changed)
 117     for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
 118       SimplifyInstructionsInBlock(FI);
 119
 120   return changed;
 121 }