1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
//===- PiNodeInsertion.cpp - Insert Pi nodes into a program ---------------===//
//
// PiNodeInsertion - This pass inserts single entry Phi nodes into basic blocks
// that are preceeded by a conditional branch, where the branch gives
// information about the operands of the condition. For example, this C code:
// if (x == 0) { ... = x + 4;
// becomes:
// if (x == 0) {
// x2 = phi(x); // Node that can hold data flow information about X
// ... = x2 + 4;
//
// Since the direction of the condition branch gives information about X itself
// (whether or not it is zero), some passes (like value numbering or ABCD) can
// use the inserted Phi/Pi nodes as a place to attach information, in this case
// saying that X has a value of 0 in this scope. The power of this analysis
// information is that "in the scope" translates to "for all uses of x2".
//
// This special form of Phi node is refered to as a Pi node, following the
// terminology defined in the "Array Bounds Checks on Demand" paper.
//
// As a really trivial example of what the Pi nodes are good for, this pass
// replaces values compared for equality with direct constants with the constant
// itself in the branch it's equal to the constant. In the case above, it would
// change the body to be "... = 0 + 4;" Real value numbering can do much more.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Pass.h"
#include "llvm/Function.h"
#include "llvm/iTerminators.h"
#include "llvm/iOperators.h"
#include "llvm/iPHINode.h"
#include "llvm/Support/CFG.h"
#include "Support/Statistic.h"
namespace {
Statistic<> NumInserted("pinodes", "Number of Pi nodes inserted");
struct PiNodeInserter : public FunctionPass {
virtual bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<DominatorSet>();
}
// insertPiNodeFor - Insert a Pi node for V in the successors of BB if our
// conditions hold. If Rep is not null, fill in a value of 'Rep' instead of
// creating a new Pi node itself because we know that the value is a simple
// constant.
//
bool insertPiNodeFor(Value *V, BasicBlock *BB, Value *Rep = 0);
};
RegisterOpt<PiNodeInserter> X("pinodes", "Pi Node Insertion");
}
Pass *createPiNodeInsertionPass() { return new PiNodeInserter(); }
bool PiNodeInserter::runOnFunction(Function &F) {
bool Changed = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
TerminatorInst *TI = I->getTerminator();
// FIXME: Insert PI nodes for switch statements too
// Look for conditional branch instructions... that branch on a setcc test
if (BranchInst *BI = dyn_cast<BranchInst>(TI))
if (BI->isConditional())
// TODO: we could in theory support logical operations here too...
if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) {
// Calculate replacement values if this is an obvious constant == or
// != comparison...
Value *TrueRep = 0, *FalseRep = 0;
// Make sure the the constant is the second operand if there is one...
// This fits with our cannonicalization patterns used elsewhere in the
// compiler, without depending on instcombine running before us.
//
if (isa<Constant>(SCI->getOperand(0)) &&
!isa<Constant>(SCI->getOperand(1))) {
SCI->swapOperands();
Changed = true;
}
if (isa<Constant>(SCI->getOperand(1))) {
if (SCI->getOpcode() == Instruction::SetEQ)
TrueRep = SCI->getOperand(1);
else if (SCI->getOpcode() == Instruction::SetNE)
FalseRep = SCI->getOperand(1);
}
BasicBlock *TB = BI->getSuccessor(0); // True block
BasicBlock *FB = BI->getSuccessor(1); // False block
// Insert the Pi nodes for the first operand to the comparison...
Changed |= insertPiNodeFor(SCI->getOperand(0), TB, TrueRep);
Changed |= insertPiNodeFor(SCI->getOperand(0), FB, FalseRep);
// Insert the Pi nodes for the second operand to the comparison...
Changed |= insertPiNodeFor(SCI->getOperand(1), TB);
Changed |= insertPiNodeFor(SCI->getOperand(1), FB);
}
}
return Changed;
}
// alreadyHasPiNodeFor - Return true if there is already a Pi node in BB for V.
static bool alreadyHasPiNodeFor(Value *V, BasicBlock *BB) {
for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
if (PHINode *PN = dyn_cast<PHINode>(*I))
if (PN->getParent() == BB)
return true;
return false;
}
// insertPiNodeFor - Insert a Pi node for V in the successors of BB if our
// conditions hold. If Rep is not null, fill in a value of 'Rep' instead of
// creating a new Pi node itself because we know that the value is a simple
// constant.
//
bool PiNodeInserter::insertPiNodeFor(Value *V, BasicBlock *Succ, Value *Rep) {
// Do not insert Pi nodes for constants!
if (isa<Constant>(V)) return false;
// Check to make sure that there is not already a PI node inserted...
if (alreadyHasPiNodeFor(V, Succ) && Rep == 0)
return false;
// Insert Pi nodes only into successors that the conditional branch dominates.
// In this simple case, we know that BB dominates a successor as long there
// are no other incoming edges to the successor.
//
// Check to make sure that the successor only has a single predecessor...
pred_iterator PI = pred_begin(Succ);
BasicBlock *Pred = *PI;
if (++PI != pred_end(Succ)) return false; // Multiple predecessor? Bail...
// It seems to be safe to insert the Pi node. Do so now...
// Create the Pi node...
Value *Pi = Rep;
if (Rep == 0) // Insert the Pi node in the successor basic block...
Pi = new PHINode(V->getType(), V->getName() + ".pi", Succ->begin());
// Loop over all of the uses of V, replacing ones that the Pi node
// dominates with references to the Pi node itself.
//
DominatorSet &DS = getAnalysis<DominatorSet>();
for (unsigned i = 0; i < V->use_size(); ) {
if (Instruction *U = dyn_cast<Instruction>(*(V->use_begin()+i)))
if (U->getParent()->getParent() == Succ->getParent() &&
DS.dominates(Succ, U->getParent())) {
// This instruction is dominated by the Pi node, replace reference to V
// with a reference to the Pi node.
//
U->replaceUsesOfWith(V, Pi);
continue; // Do not skip the next use...
}
// This use is not dominated by the Pi node, skip it...
++i;
}
// Set up the incoming value for the Pi node... do this after uses have been
// replaced, because we don't want the Pi node to refer to itself.
//
if (Rep == 0)
cast<PHINode>(Pi)->addIncoming(V, Pred);
++NumInserted;
return true;
}
|
