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