CorrelatedValuePropagation.cpp revision 562b84b3aea359d1f918184e355da82bf05eb290 
1//===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
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 Correlated Value Propagation pass.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "correlated-value-propagation"
15#include "llvm/Transforms/Scalar.h"
16#include "llvm/Constants.h"
17#include "llvm/Function.h"
18#include "llvm/Instructions.h"
19#include "llvm/Pass.h"
20#include "llvm/Analysis/InstructionSimplify.h"
21#include "llvm/Analysis/LazyValueInfo.h"
22#include "llvm/Support/CFG.h"
23#include "llvm/Transforms/Utils/Local.h"
24#include "llvm/ADT/Statistic.h"
25using namespace llvm;
26
27STATISTIC(NumPhis,      "Number of phis propagated");
28STATISTIC(NumSelects,   "Number of selects propagated");
29STATISTIC(NumMemAccess, "Number of memory access targets propagated");
30STATISTIC(NumCmps,      "Number of comparisons propagated");
31
32namespace {
33  class CorrelatedValuePropagation : public FunctionPass {
34    LazyValueInfo *LVI;
35
36    bool processSelect(SelectInst *SI);
37    bool processPHI(PHINode *P);
38    bool processMemAccess(Instruction *I);
39    bool processCmp(CmpInst *C);
40
41  public:
42    static char ID;
43    CorrelatedValuePropagation(): FunctionPass(ID) {
44     initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
45    }
46
47    bool runOnFunction(Function &F);
48
49    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
50      AU.addRequired<LazyValueInfo>();
51    }
52  };
53}
54
55char CorrelatedValuePropagation::ID = 0;
56INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
57                "Value Propagation", false, false)
58INITIALIZE_PASS_DEPENDENCY(LazyValueInfo)
59INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
60                "Value Propagation", false, false)
61
62// Public interface to the Value Propagation pass
63Pass *llvm::createCorrelatedValuePropagationPass() {
64  return new CorrelatedValuePropagation();
65}
66
67bool CorrelatedValuePropagation::processSelect(SelectInst *S) {
68  if (S->getType()->isVectorTy()) return false;
69  if (isa<Constant>(S->getOperand(0))) return false;
70
71  Constant *C = LVI->getConstant(S->getOperand(0), S->getParent());
72  if (!C) return false;
73
74  ConstantInt *CI = dyn_cast<ConstantInt>(C);
75  if (!CI) return false;
76
77  Value *ReplaceWith = S->getOperand(1);
78  Value *Other = S->getOperand(2);
79  if (!CI->isOne()) std::swap(ReplaceWith, Other);
80  if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());
81
82  S->replaceAllUsesWith(ReplaceWith);
83  S->eraseFromParent();
84
85  ++NumSelects;
86
87  return true;
88}
89
90bool CorrelatedValuePropagation::processPHI(PHINode *P) {
91  bool Changed = false;
92
93  BasicBlock *BB = P->getParent();
94  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
95    Value *Incoming = P->getIncomingValue(i);
96    if (isa<Constant>(Incoming)) continue;
97
98    Constant *C = LVI->getConstantOnEdge(P->getIncomingValue(i),
99                                         P->getIncomingBlock(i),
100                                         BB);
101    if (!C) continue;
102
103    P->setIncomingValue(i, C);
104    Changed = true;
105  }
106
107  if (Value *V = SimplifyInstruction(P)) {
108    P->replaceAllUsesWith(V);
109    P->eraseFromParent();
110    Changed = true;
111  }
112
113  ++NumPhis;
114
115  return Changed;
116}
117
118bool CorrelatedValuePropagation::processMemAccess(Instruction *I) {
119  Value *Pointer = 0;
120  if (LoadInst *L = dyn_cast<LoadInst>(I))
121    Pointer = L->getPointerOperand();
122  else
123    Pointer = cast<StoreInst>(I)->getPointerOperand();
124
125  if (isa<Constant>(Pointer)) return false;
126
127  Constant *C = LVI->getConstant(Pointer, I->getParent());
128  if (!C) return false;
129
130  ++NumMemAccess;
131  I->replaceUsesOfWith(Pointer, C);
132  return true;
133}
134
135/// processCmp - If the value of this comparison could be determined locally,
136/// constant propagation would already have figured it out.  Instead, walk
137/// the predecessors and statically evaluate the comparison based on information
138/// available on that edge.  If a given static evaluation is true on ALL
139/// incoming edges, then it's true universally and we can simplify the compare.
140bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
141  Value *Op0 = C->getOperand(0);
142  if (isa<Instruction>(Op0) &&
143      cast<Instruction>(Op0)->getParent() == C->getParent())
144    return false;
145
146  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
147  if (!Op1) return false;
148
149  pred_iterator PI = pred_begin(C->getParent()), PE = pred_end(C->getParent());
150  if (PI == PE) return false;
151
152  LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(),
153                                    C->getOperand(0), Op1, *PI, C->getParent());
154  if (Result == LazyValueInfo::Unknown) return false;
155
156  ++PI;
157  while (PI != PE) {
158    LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(),
159                                    C->getOperand(0), Op1, *PI, C->getParent());
160    if (Res != Result) return false;
161    ++PI;
162  }
163
164  ++NumCmps;
165
166  if (Result == LazyValueInfo::True)
167    C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext()));
168  else
169    C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext()));
170
171  C->eraseFromParent();
172
173  return true;
174}
175
176bool CorrelatedValuePropagation::runOnFunction(Function &F) {
177  LVI = &getAnalysis<LazyValueInfo>();
178
179  bool FnChanged = false;
180
181  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
182    bool BBChanged = false;
183    for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
184      Instruction *II = BI++;
185      switch (II->getOpcode()) {
186      case Instruction::Select:
187        BBChanged |= processSelect(cast<SelectInst>(II));
188        break;
189      case Instruction::PHI:
190        BBChanged |= processPHI(cast<PHINode>(II));
191        break;
192      case Instruction::ICmp:
193      case Instruction::FCmp:
194        BBChanged |= processCmp(cast<CmpInst>(II));
195        break;
196      case Instruction::Load:
197      case Instruction::Store:
198        BBChanged |= processMemAccess(II);
199        break;
200      }
201    }
202
203    FnChanged |= BBChanged;
204  }
205
206  return FnChanged;
207}
208