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
|
//===---- CodePreparation.cpp - Code preparation for Scop Detection -------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// The Polly code preparation pass is executed before SCoP detection. Its only
// use is to translate all PHI nodes that can not be expressed by the code
// generator into explicit memory dependences. Depending of the code generation
// strategy different PHI nodes are translated:
//
// - indvars based code generation:
//
// The indvars based code generation requires explicit canonical induction
// variables. Such variables are generated before scop detection and
// also before the code preparation pass. All PHI nodes that are not canonical
// induction variables are not supported by the indvars based code generation
// and are consequently translated into explict memory accesses.
//
// - scev based code generation:
//
// The scev based code generation can code generate all PHI nodes that do not
// reference parameters within the scop. As the code preparation pass is run
// before scop detection, we can not check this condition, because without
// a detected scop, we do not know SCEVUnknowns that appear in the SCEV of
// a PHI node may later be within or outside of the SCoP. Hence, we follow a
// heuristic and translate all PHI nodes that are either directly SCEVUnknown
// or SCEVCouldNotCompute. This will hopefully get most of the PHI nodes that
// are introduced due to conditional control flow, but not the ones that are
// referencing loop counters.
//
// XXX: In the future, we should remove the need for this pass entirely and
// instead add support for scalar dependences to ScopInfo and code generation.
//
//===----------------------------------------------------------------------===//
#include "polly/LinkAllPasses.h"
#include "polly/CodeGen/BlockGenerators.h"
#include "polly/Support/ScopHelper.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
using namespace polly;
namespace {
/// @brief Prepare the IR for the scop detection.
///
class CodePreparation : public FunctionPass {
// DO NOT IMPLEMENT.
CodePreparation(const CodePreparation &);
// DO NOT IMPLEMENT.
const CodePreparation &operator=(const CodePreparation &);
LoopInfo *LI;
ScalarEvolution *SE;
void clear();
bool eliminatePHINodes(Function &F);
public:
static char ID;
explicit CodePreparation() : FunctionPass(ID) {}
~CodePreparation();
/// @name FunctionPass interface.
//@{
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
virtual void releaseMemory();
virtual bool runOnFunction(Function &F);
virtual void print(raw_ostream &OS, const Module *) const;
//@}
};
}
void CodePreparation::clear() {}
CodePreparation::~CodePreparation() { clear(); }
bool CodePreparation::eliminatePHINodes(Function &F) {
// The PHINodes that will be deleted.
std::vector<PHINode *> PNtoDelete;
// The PHINodes that will be preserved.
std::vector<PHINode *> PreservedPNs;
// Scan the PHINodes in this function.
for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI)
for (BasicBlock::iterator II = BI->begin(), IE = BI->getFirstNonPHI();
II != IE; ++II) {
PHINode *PN = cast<PHINode>(II);
if (SCEVCodegen) {
if (SE->isSCEVable(PN->getType())) {
const SCEV *S = SE->getSCEV(PN);
if (!isa<SCEVUnknown>(S) && !isa<SCEVCouldNotCompute>(S)) {
PreservedPNs.push_back(PN);
continue;
}
}
} else {
if (Loop *L = LI->getLoopFor(BI)) {
// Induction variables will be preserved.
if (L->getCanonicalInductionVariable() == PN) {
PreservedPNs.push_back(PN);
continue;
}
}
}
// As DemotePHIToStack does not support invoke edges, we preserve
// PHINodes that have invoke edges.
if (hasInvokeEdge(PN))
PreservedPNs.push_back(PN);
else
PNtoDelete.push_back(PN);
}
if (PNtoDelete.empty())
return false;
while (!PNtoDelete.empty()) {
PHINode *PN = PNtoDelete.back();
PNtoDelete.pop_back();
DemotePHIToStack(PN);
}
// Move preserved PHINodes to the beginning of the BasicBlock.
while (!PreservedPNs.empty()) {
PHINode *PN = PreservedPNs.back();
PreservedPNs.pop_back();
BasicBlock *BB = PN->getParent();
if (PN == BB->begin())
continue;
PN->moveBefore(BB->begin());
}
return true;
}
void CodePreparation::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<LoopInfo>();
AU.addRequired<ScalarEvolution>();
AU.addPreserved<LoopInfo>();
AU.addPreserved<RegionInfo>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<DominanceFrontier>();
}
bool CodePreparation::runOnFunction(Function &F) {
LI = &getAnalysis<LoopInfo>();
SE = &getAnalysis<ScalarEvolution>();
splitEntryBlockForAlloca(&F.getEntryBlock(), this);
eliminatePHINodes(F);
return false;
}
void CodePreparation::releaseMemory() { clear(); }
void CodePreparation::print(raw_ostream &OS, const Module *) const {}
char CodePreparation::ID = 0;
char &polly::CodePreparationID = CodePreparation::ID;
Pass *polly::createCodePreparationPass() { return new CodePreparation(); }
INITIALIZE_PASS_BEGIN(CodePreparation, "polly-prepare",
"Polly - Prepare code for polly", false, false);
INITIALIZE_PASS_DEPENDENCY(LoopInfo);
INITIALIZE_PASS_END(CodePreparation, "polly-prepare",
"Polly - Prepare code for polly", false, false)
|
