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 using namespace llvm;
  22
  23 namespace {
  24   class ValuePropagation : public FunctionPass {
  25     LazyValueInfo *LVI;
  26
  27     bool processSelect(SelectInst *SI);
  28     bool processPHI(PHINode *P);
  29
  30   public:
  31     static char ID;
  32     ValuePropagation(): FunctionPass(ID) { }
  33
  34     bool runOnFunction(Function &F);
  35
  36     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  37       AU.addRequired<LazyValueInfo>();
  38     }
  39   };
  40 }
  41
  42 char ValuePropagation::ID = 0;
  43 INITIALIZE_PASS(ValuePropagation, "value-propagation",
  44                 "Value Propagation", false, false);
  45
  46 // Public interface to the Value Propagation pass
  47 Pass *llvm::createValuePropagationPass() {
  48   return new ValuePropagation();
  49 }
  50
  51 bool ValuePropagation::processSelect(SelectInst *S) {
  52   Constant *C = LVI->getConstant(S->getOperand(0), S->getParent());
  53   if (!C) return false;
  54
  55   ConstantInt *CI = dyn_cast<ConstantInt>(C);
  56   if (!CI) return false;
  57
  58   if (CI->isZero()) {
  59     S->replaceAllUsesWith(S->getOperand(2));
  60     S->eraseFromParent();
  61   } else if (CI->isOne()) {
  62     S->replaceAllUsesWith(S->getOperand(1));
  63     S->eraseFromParent();
  64   } else {
  65     assert(0 && "Select on constant is neither 0 nor 1?");
  66   }
  67
  68   return true;
  69 }
  70
  71 bool ValuePropagation::processPHI(PHINode *P) {
  72   bool changed = false;
  73
  74   BasicBlock *BB = P->getParent();
  75   for (unsigned i = 0; i < P->getNumIncomingValues(); ++i) {
  76     Constant *C = LVI->getConstantOnEdge(P->getIncomingValue(i),
  77                                          P->getIncomingBlock(i),
  78                                          BB);
  79     if (!C || C == P->getIncomingValue(i)) continue;
  80
  81     P->setIncomingValue(i, C);
  82     changed = true;
  83   }
  84
  85   if (Value *ConstVal = P->hasConstantValue()) {
  86     P->replaceAllUsesWith(ConstVal);
  87     P->eraseFromParent();
  88     changed = true;
  89   }
  90
  91   return changed;
  92 }
  93
  94 bool ValuePropagation::runOnFunction(Function &F) {
  95   LVI = &getAnalysis<LazyValueInfo>();
  96
  97   bool changed = false;
  98
  99   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
 100     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
 101       Instruction *II = BI++;
 102       if (SelectInst *SI = dyn_cast<SelectInst>(II))
 103         changed |= processSelect(SI);
 104       else if (PHINode *P = dyn_cast<PHINode>(II))
 105         changed |= processPHI(P);
 106     }
 107
 108   if (changed)
 109     for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
 110       SimplifyInstructionsInBlock(FI);
 111
 112   return changed;
 113 }