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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
//
// This pass is a simple loop invariant code motion pass.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/iOperators.h"
#include "llvm/iMemory.h"
#include "llvm/Support/InstVisitor.h"
#include "Support/STLExtras.h"
#include "Support/Statistic.h"
#include "llvm/Assembly/Writer.h"
#include <algorithm>
using std::string;
namespace {
Statistic<> NumHoisted("licm", "Number of instructions hoisted out of loop");
Statistic<> NumHoistedLoads("licm", "Number of load insts hoisted");
struct LICM : public FunctionPass, public InstVisitor<LICM> {
virtual bool runOnFunction(Function &F);
/// This transformation requires natural loop information & requires that
/// loop preheaders be inserted into the CFG...
///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequiredID(LoopPreheadersID);
AU.addRequired<LoopInfo>();
AU.addRequired<DominatorTree>();
AU.addRequired<AliasAnalysis>();
}
private:
Loop *CurLoop; // The current loop we are working on...
BasicBlock *Preheader; // The preheader block of the current loop...
bool Changed; // Set to true when we change anything.
AliasAnalysis *AA; // Currently AliasAnalysis information
/// visitLoop - Hoist expressions out of the specified loop...
///
void visitLoop(Loop *L);
/// HoistRegion - Walk the specified region of the CFG (defined by all
/// blocks dominated by the specified block, and that are in the current
/// loop) in depth first order w.r.t the DominatorTree. This allows us to
/// visit defintions before uses, allowing us to hoist a loop body in one
/// pass without iteration.
///
void HoistRegion(DominatorTree::Node *N);
/// inSubLoop - Little predicate that returns true if the specified basic
/// block is in a subloop of the current one, not the current one itself.
///
bool inSubLoop(BasicBlock *BB) {
assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
for (unsigned i = 0, e = CurLoop->getSubLoops().size(); i != e; ++i)
if (CurLoop->getSubLoops()[i]->contains(BB))
return true; // A subloop actually contains this block!
return false;
}
/// hoist - When an instruction is found to only use loop invariant operands
/// that is safe to hoist, this instruction is called to do the dirty work.
///
void hoist(Instruction &I);
/// pointerInvalidatedByLoop - Return true if the body of this loop may
/// store into the memory location pointed to by V.
///
bool pointerInvalidatedByLoop(Value *V);
/// isLoopInvariant - Return true if the specified value is loop invariant
///
inline bool isLoopInvariant(Value *V) {
if (Instruction *I = dyn_cast<Instruction>(V))
return !CurLoop->contains(I->getParent());
return true; // All non-instructions are loop invariant
}
/// Instruction visitation handlers... these basically control whether or
/// not the specified instruction types are hoisted.
///
friend class InstVisitor<LICM>;
void visitBinaryOperator(Instruction &I) {
if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1)))
hoist(I);
}
void visitCastInst(CastInst &CI) {
Instruction &I = (Instruction&)CI;
if (isLoopInvariant(I.getOperand(0))) hoist(I);
}
void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); }
void visitLoadInst(LoadInst &LI);
void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
Instruction &I = (Instruction&)GEPI;
for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
if (!isLoopInvariant(I.getOperand(i))) return;
hoist(I);
}
};
RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion");
}
Pass *createLICMPass() { return new LICM(); }
/// runOnFunction - For LICM, this simply traverses the loop structure of the
/// function, hoisting expressions out of loops if possible.
///
bool LICM::runOnFunction(Function &) {
// Get information about the top level loops in the function...
const std::vector<Loop*> &TopLevelLoops =
getAnalysis<LoopInfo>().getTopLevelLoops();
// Get our alias analysis information...
AA = &getAnalysis<AliasAnalysis>();
// Traverse loops in postorder, hoisting expressions out of the deepest loops
// first.
//
Changed = false;
std::for_each(TopLevelLoops.begin(), TopLevelLoops.end(),
bind_obj(this, &LICM::visitLoop));
return Changed;
}
/// visitLoop - Hoist expressions out of the specified loop...
///
void LICM::visitLoop(Loop *L) {
// Recurse through all subloops before we process this loop...
std::for_each(L->getSubLoops().begin(), L->getSubLoops().end(),
bind_obj(this, &LICM::visitLoop));
CurLoop = L;
// Get the preheader block to move instructions into...
Preheader = L->getLoopPreheader();
assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!");
// We want to visit all of the instructions in this loop... that are not parts
// of our subloops (they have already had their invariants hoisted out of
// their loop, into this loop, so there is no need to process the BODIES of
// the subloops).
//
// Traverse the body of the loop in depth first order on the dominator tree so
// that we are guaranteed to see definitions before we see uses. This allows
// us to perform the LICM transformation in one pass, without iteration.
//
HoistRegion(getAnalysis<DominatorTree>()[L->getHeader()]);
// Clear out loops state information for the next iteration
CurLoop = 0;
Preheader = 0;
}
/// HoistRegion - Walk the specified region of the CFG (defined by all blocks
/// dominated by the specified block, and that are in the current loop) in depth
/// first order w.r.t the DominatorTree. This allows us to visit defintions
/// before uses, allowing us to hoist a loop body in one pass without iteration.
///
void LICM::HoistRegion(DominatorTree::Node *N) {
assert(N != 0 && "Null dominator tree node?");
// If this subregion is not in the top level loop at all, exit.
if (!CurLoop->contains(N->getNode())) return;
// Only need to hoist the contents of this block if it is not part of a
// subloop (which would already have been hoisted)
if (!inSubLoop(N->getNode()))
visit(*N->getNode());
const std::vector<DominatorTree::Node*> &Children = N->getChildren();
for (unsigned i = 0, e = Children.size(); i != e; ++i)
HoistRegion(Children[i]);
}
/// hoist - When an instruction is found to only use loop invariant operands
/// that is safe to hoist, this instruction is called to do the dirty work.
///
void LICM::hoist(Instruction &Inst) {
DEBUG(std::cerr << "LICM hoisting to";
WriteAsOperand(std::cerr, Preheader, false);
std::cerr << ": " << Inst);
// Remove the instruction from its current basic block... but don't delete the
// instruction.
Inst.getParent()->getInstList().remove(&Inst);
// Insert the new node in Preheader, before the terminator.
Preheader->getInstList().insert(Preheader->getTerminator(), &Inst);
++NumHoisted;
Changed = true;
}
void LICM::visitLoadInst(LoadInst &LI) {
if (isLoopInvariant(LI.getOperand(0)) &&
!pointerInvalidatedByLoop(LI.getOperand(0))) {
hoist(LI);
++NumHoistedLoads;
}
}
/// pointerInvalidatedByLoop - Return true if the body of this loop may store
/// into the memory location pointed to by V.
///
bool LICM::pointerInvalidatedByLoop(Value *V) {
// Check to see if any of the basic blocks in CurLoop invalidate V.
for (unsigned i = 0, e = CurLoop->getBlocks().size(); i != e; ++i)
if (AA->canBasicBlockModify(*CurLoop->getBlocks()[i], V))
return true;
return false;
}
|
