1
//===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This file implements the Correlated Value Propagation pass.
12
//===----------------------------------------------------------------------===//
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/Statistic.h"
25
STATISTIC(NumPhis, "Number of phis propagated");
26
STATISTIC(NumSelects, "Number of selects propagated");
27
STATISTIC(NumMemAccess, "Number of memory access targets propagated");
28
STATISTIC(NumCmps, "Number of comparisons propagated");
31
class CorrelatedValuePropagation : public FunctionPass {
34
bool processSelect(SelectInst *SI);
35
bool processPHI(PHINode *P);
36
bool processMemAccess(Instruction *I);
37
bool processCmp(CmpInst *C);
41
CorrelatedValuePropagation(): FunctionPass(ID) { }
43
bool runOnFunction(Function &F);
45
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
46
AU.addRequired<LazyValueInfo>();
51
char CorrelatedValuePropagation::ID = 0;
52
INITIALIZE_PASS(CorrelatedValuePropagation, "correlated-propagation",
53
"Value Propagation", false, false);
55
// Public interface to the Value Propagation pass
56
Pass *llvm::createCorrelatedValuePropagationPass() {
57
return new CorrelatedValuePropagation();
60
bool CorrelatedValuePropagation::processSelect(SelectInst *S) {
61
if (S->getType()->isVectorTy()) return false;
62
if (isa<Constant>(S->getOperand(0))) return false;
64
Constant *C = LVI->getConstant(S->getOperand(0), S->getParent());
67
ConstantInt *CI = dyn_cast<ConstantInt>(C);
68
if (!CI) return false;
70
S->replaceAllUsesWith(S->getOperand(CI->isOne() ? 1 : 2));
78
bool CorrelatedValuePropagation::processPHI(PHINode *P) {
81
BasicBlock *BB = P->getParent();
82
for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
83
Value *Incoming = P->getIncomingValue(i);
84
if (isa<Constant>(Incoming)) continue;
86
Constant *C = LVI->getConstantOnEdge(P->getIncomingValue(i),
87
P->getIncomingBlock(i),
91
P->setIncomingValue(i, C);
95
if (Value *ConstVal = P->hasConstantValue()) {
96
P->replaceAllUsesWith(ConstVal);
106
bool CorrelatedValuePropagation::processMemAccess(Instruction *I) {
108
if (LoadInst *L = dyn_cast<LoadInst>(I))
109
Pointer = L->getPointerOperand();
111
Pointer = cast<StoreInst>(I)->getPointerOperand();
113
if (isa<Constant>(Pointer)) return false;
115
Constant *C = LVI->getConstant(Pointer, I->getParent());
116
if (!C) return false;
119
I->replaceUsesOfWith(Pointer, C);
123
/// processCmp - If the value of this comparison could be determined locally,
124
/// constant propagation would already have figured it out. Instead, walk
125
/// the predecessors and statically evaluate the comparison based on information
126
/// available on that edge. If a given static evaluation is true on ALL
127
/// incoming edges, then it's true universally and we can simplify the compare.
128
bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
129
Value *Op0 = C->getOperand(0);
130
if (isa<Instruction>(Op0) &&
131
cast<Instruction>(Op0)->getParent() == C->getParent())
134
Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
135
if (!Op1) return false;
137
pred_iterator PI = pred_begin(C->getParent()), PE = pred_end(C->getParent());
138
if (PI == PE) return false;
140
LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(),
141
C->getOperand(0), Op1, *PI, C->getParent());
142
if (Result == LazyValueInfo::Unknown) return false;
146
LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(),
147
C->getOperand(0), Op1, *PI, C->getParent());
148
if (Res != Result) return false;
154
if (Result == LazyValueInfo::True)
155
C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext()));
157
C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext()));
159
C->eraseFromParent();
164
bool CorrelatedValuePropagation::runOnFunction(Function &F) {
165
LVI = &getAnalysis<LazyValueInfo>();
167
bool FnChanged = false;
169
for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
170
bool BBChanged = false;
171
for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
172
Instruction *II = BI++;
173
switch (II->getOpcode()) {
174
case Instruction::Select:
175
BBChanged |= processSelect(cast<SelectInst>(II));
177
case Instruction::PHI:
178
BBChanged |= processPHI(cast<PHINode>(II));
180
case Instruction::ICmp:
181
case Instruction::FCmp:
182
BBChanged |= processCmp(cast<CmpInst>(II));
184
case Instruction::Load:
185
case Instruction::Store:
186
BBChanged |= processMemAccess(II);
191
// Propagating correlated values might leave cruft around.
192
// Try to clean it up before we continue.
194
SimplifyInstructionsInBlock(FI);
196
FnChanged |= BBChanged;