CorrelatedValuePropagation.cpp revision 7aff1cd0389d922d752b57b9ccf942b457977955 
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"
22using namespace llvm;
23
24STATISTIC(NumPhis,    "Number of phis propagated");
25STATISTIC(NumSelects, "Number of selects propagated");
26
27namespace {
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
46char ValuePropagation::ID = 0;
47INITIALIZE_PASS(ValuePropagation, "value-propagation",
48                "Value Propagation", false, false);
49
50// Public interface to the Value Propagation pass
51Pass *llvm::createValuePropagationPass() {
52  return new ValuePropagation();
53}
54
55bool ValuePropagation::processSelect(SelectInst *S) {
56  if (S->getType()->isVectorTy()) return false;
57
58  Constant *C = LVI->getConstant(S->getOperand(0), S->getParent());
59  if (!C) return false;
60
61  ConstantInt *CI = dyn_cast<ConstantInt>(C);
62  if (!CI) return false;
63
64  S->replaceAllUsesWith(S->getOperand(CI->isOne() ? 1 : 2));
65  S->eraseFromParent();
66
67  ++NumSelects;
68
69  return true;
70}
71
72bool ValuePropagation::processPHI(PHINode *P) {
73  bool Changed = false;
74
75  BasicBlock *BB = P->getParent();
76  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
77    Value *Incoming = P->getIncomingValue(i);
78    if (isa<Constant>(Incoming)) continue;
79
80    Constant *C = LVI->getConstantOnEdge(P->getIncomingValue(i),
81                                         P->getIncomingBlock(i),
82                                         BB);
83    if (!C) continue;
84
85    P->setIncomingValue(i, C);
86    Changed = true;
87  }
88
89  if (Value *ConstVal = P->hasConstantValue()) {
90    P->replaceAllUsesWith(ConstVal);
91    P->eraseFromParent();
92    Changed = true;
93  }
94
95  ++NumPhis;
96
97  return Changed;
98}
99
100bool ValuePropagation::runOnFunction(Function &F) {
101  LVI = &getAnalysis<LazyValueInfo>();
102
103  bool Changed = false;
104
105  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
106    for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
107      Instruction *II = BI++;
108      if (SelectInst *SI = dyn_cast<SelectInst>(II))
109        Changed |= processSelect(SI);
110      else if (PHINode *P = dyn_cast<PHINode>(II))
111        Changed |= processPHI(P);
112    }
113
114  if (Changed)
115    for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
116      SimplifyInstructionsInBlock(FI);
117
118  return Changed;
119}
120