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
|
//===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass implements a simple loop unroller. It works best when loops have
// been canonicalized by the -indvars pass, allowing it to determine the trip
// counts of loops easily.
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "loop-unroll"
#include "llvm/IntrinsicInst.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/InlineCost.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include <climits>
using namespace llvm;
static cl::opt<unsigned>
UnrollThreshold("unroll-threshold", cl::init(200), cl::Hidden,
cl::desc("The cut-off point for automatic loop unrolling"));
static cl::opt<unsigned>
UnrollCount("unroll-count", cl::init(0), cl::Hidden,
cl::desc("Use this unroll count for all loops, for testing purposes"));
static cl::opt<bool>
UnrollAllowPartial("unroll-allow-partial", cl::init(false), cl::Hidden,
cl::desc("Allows loops to be partially unrolled until "
"-unroll-threshold loop size is reached."));
namespace {
class LoopUnroll : public LoopPass {
public:
static char ID; // Pass ID, replacement for typeid
LoopUnroll() : LoopPass(&ID) {}
/// A magic value for use with the Threshold parameter to indicate
/// that the loop unroll should be performed regardless of how much
/// code expansion would result.
static const unsigned NoThreshold = UINT_MAX;
bool runOnLoop(Loop *L, LPPassManager &LPM);
/// This transformation requires natural loop information & requires that
/// loop preheaders be inserted into the CFG...
///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<LoopInfo>();
AU.addPreserved<LoopInfo>();
AU.addRequiredID(LoopSimplifyID);
AU.addPreservedID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addPreservedID(LCSSAID);
// FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info.
// If loop unroll does not preserve dom info then LCSSA pass on next
// loop will receive invalid dom info.
// For now, recreate dom info, if loop is unrolled.
AU.addPreserved<DominatorTree>();
AU.addPreserved<DominanceFrontier>();
AU.addPreserved<ScalarEvolution>();
}
};
}
char LoopUnroll::ID = 0;
INITIALIZE_PASS(LoopUnroll, "loop-unroll", "Unroll loops", false, false);
Pass *llvm::createLoopUnrollPass() { return new LoopUnroll(); }
/// ApproximateLoopSize - Approximate the size of the loop.
static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls) {
CodeMetrics Metrics;
for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
I != E; ++I)
Metrics.analyzeBasicBlock(*I);
NumCalls = Metrics.NumCalls;
return Metrics.NumInsts;
}
bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) {
LoopInfo *LI = &getAnalysis<LoopInfo>();
BasicBlock *Header = L->getHeader();
DEBUG(dbgs() << "Loop Unroll: F[" << Header->getParent()->getName()
<< "] Loop %" << Header->getName() << "\n");
(void)Header;
// Find trip count
unsigned TripCount = L->getSmallConstantTripCount();
unsigned Count = UnrollCount;
// Automatically select an unroll count.
if (Count == 0) {
// Conservative heuristic: if we know the trip count, see if we can
// completely unroll (subject to the threshold, checked below); otherwise
// try to find greatest modulo of the trip count which is still under
// threshold value.
if (TripCount == 0)
return false;
Count = TripCount;
}
// Enforce the threshold.
if (UnrollThreshold != NoThreshold) {
unsigned NumCalls;
unsigned LoopSize = ApproximateLoopSize(L, NumCalls);
DEBUG(dbgs() << " Loop Size = " << LoopSize << "\n");
if (NumCalls != 0) {
DEBUG(dbgs() << " Not unrolling loop with function calls.\n");
return false;
}
uint64_t Size = (uint64_t)LoopSize*Count;
if (TripCount != 1 && Size > UnrollThreshold) {
DEBUG(dbgs() << " Too large to fully unroll with count: " << Count
<< " because size: " << Size << ">" << UnrollThreshold << "\n");
if (!UnrollAllowPartial) {
DEBUG(dbgs() << " will not try to unroll partially because "
<< "-unroll-allow-partial not given\n");
return false;
}
// Reduce unroll count to be modulo of TripCount for partial unrolling
Count = UnrollThreshold / LoopSize;
while (Count != 0 && TripCount%Count != 0) {
Count--;
}
if (Count < 2) {
DEBUG(dbgs() << " could not unroll partially\n");
return false;
}
DEBUG(dbgs() << " partially unrolling with count: " << Count << "\n");
}
}
// Unroll the loop.
Function *F = L->getHeader()->getParent();
if (!UnrollLoop(L, Count, LI, &LPM))
return false;
// FIXME: Reconstruct dom info, because it is not preserved properly.
DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>();
if (DT) {
DT->runOnFunction(*F);
DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>();
if (DF)
DF->runOnFunction(*F);
}
return true;
}
|
