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
| //===- IslAst.h - Interface to the isl code generator -----------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// The isl code generator interface takes a Scop and generates a isl_ast. This
// ist_ast can either be returned directly or it can be pretty printed to
// stdout.
//
// A typical isl_ast output looks like this:
//
// for (c2 = max(0, ceild(n + m, 2); c2 <= min(511, floord(5 * n, 3)); c2++) {
// bb2(c2);
// }
//
//===----------------------------------------------------------------------===//
#ifndef POLLY_ISLAST_H
#define POLLY_ISLAST_H
#include "polly/ScopPass.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/IR/PassManager.h"
#include "isl/ctx.h"
namespace polly {
struct Dependences;
class IslAst {
public:
IslAst(const IslAst &) = delete;
IslAst &operator=(const IslAst &) = delete;
IslAst(IslAst &&);
IslAst &operator=(IslAst &&) = delete;
~IslAst();
static IslAst create(Scop &Scop, const Dependences &D);
/// Print a source code representation of the program.
void pprint(raw_ostream &OS);
__isl_give isl_ast_node *getAst();
const std::shared_ptr<isl_ctx> getSharedIslCtx() const { return Ctx; }
/// Get the run-time conditions for the Scop.
__isl_give isl_ast_expr *getRunCondition();
/// Build run-time condition for scop.
///
/// @param S The scop to build the condition for.
/// @param Build The isl_build object to use to build the condition.
///
/// @returns An ast expression that describes the necessary run-time check.
static isl_ast_expr *buildRunCondition(Scop &S,
__isl_keep isl_ast_build *Build);
private:
Scop &S;
isl_ast_node *Root = nullptr;
isl_ast_expr *RunCondition = nullptr;
std::shared_ptr<isl_ctx> Ctx;
IslAst(Scop &Scop);
void init(const Dependences &D);
};
class IslAstInfo {
public:
using MemoryAccessSet = SmallPtrSet<MemoryAccess *, 4>;
/// Payload information used to annotate an AST node.
struct IslAstUserPayload {
/// Construct and initialize the payload.
IslAstUserPayload() = default;
/// Cleanup all isl structs on destruction.
~IslAstUserPayload();
/// Does the dependence analysis determine that there are no loop-carried
/// dependencies?
bool IsParallel = false;
/// Flag to mark innermost loops.
bool IsInnermost = false;
/// Flag to mark innermost parallel loops.
bool IsInnermostParallel = false;
/// Flag to mark outermost parallel loops.
bool IsOutermostParallel = false;
/// Flag to mark parallel loops which break reductions.
bool IsReductionParallel = false;
/// The minimal dependence distance for non parallel loops.
isl::pw_aff MinimalDependenceDistance;
/// The build environment at the time this node was constructed.
isl_ast_build *Build = nullptr;
/// Set of accesses which break reduction dependences.
MemoryAccessSet BrokenReductions;
};
private:
Scop &S;
IslAst Ast;
public:
IslAstInfo(Scop &S, const Dependences &D) : S(S), Ast(IslAst::create(S, D)) {}
/// Return the isl AST computed by this IslAstInfo.
IslAst &getIslAst() { return Ast; }
/// Return a copy of the AST root node.
__isl_give isl_ast_node *getAst();
/// Get the run condition.
///
/// Only if the run condition evaluates at run-time to a non-zero value, the
/// assumptions that have been taken hold. If the run condition evaluates to
/// zero/false some assumptions do not hold and the original code needs to
/// be executed.
__isl_give isl_ast_expr *getRunCondition();
void print(raw_ostream &O);
/// @name Extract information attached to an isl ast (for) node.
///
///{
/// Get the complete payload attached to @p Node.
static IslAstUserPayload *getNodePayload(__isl_keep isl_ast_node *Node);
/// Is this loop an innermost loop?
static bool isInnermost(__isl_keep isl_ast_node *Node);
/// Is this loop a parallel loop?
static bool isParallel(__isl_keep isl_ast_node *Node);
/// Is this loop an outermost parallel loop?
static bool isOutermostParallel(__isl_keep isl_ast_node *Node);
/// Is this loop an innermost parallel loop?
static bool isInnermostParallel(__isl_keep isl_ast_node *Node);
/// Is this loop a reduction parallel loop?
static bool isReductionParallel(__isl_keep isl_ast_node *Node);
/// Will the loop be run as thread parallel?
static bool isExecutedInParallel(__isl_keep isl_ast_node *Node);
/// Get the nodes schedule or a nullptr if not available.
static __isl_give isl_union_map *getSchedule(__isl_keep isl_ast_node *Node);
/// Get minimal dependence distance or nullptr if not available.
static __isl_give isl_pw_aff *
getMinimalDependenceDistance(__isl_keep isl_ast_node *Node);
/// Get the nodes broken reductions or a nullptr if not available.
static MemoryAccessSet *getBrokenReductions(__isl_keep isl_ast_node *Node);
/// Get the nodes build context or a nullptr if not available.
static __isl_give isl_ast_build *getBuild(__isl_keep isl_ast_node *Node);
///}
};
struct IslAstAnalysis : public AnalysisInfoMixin<IslAstAnalysis> {
static AnalysisKey Key;
using Result = IslAstInfo;
IslAstInfo run(Scop &S, ScopAnalysisManager &SAM,
ScopStandardAnalysisResults &SAR);
};
class IslAstInfoWrapperPass : public ScopPass {
std::unique_ptr<IslAstInfo> Ast;
public:
static char ID;
IslAstInfoWrapperPass() : ScopPass(ID) {}
IslAstInfo &getAI() { return *Ast; }
const IslAstInfo &getAI() const { return *Ast; }
/// Build the AST for the given SCoP @p S.
bool runOnScop(Scop &S) override;
/// Register all analyses and transformation required.
void getAnalysisUsage(AnalysisUsage &AU) const override;
/// Release the internal memory.
void releaseMemory() override;
/// Print a source code representation of the program.
void printScop(raw_ostream &OS, Scop &S) const override;
};
struct IslAstPrinterPass : public PassInfoMixin<IslAstPrinterPass> {
IslAstPrinterPass(raw_ostream &OS) : OS(OS) {}
PreservedAnalyses run(Scop &S, ScopAnalysisManager &SAM,
ScopStandardAnalysisResults &, SPMUpdater &U);
raw_ostream &OS;
};
} // namespace polly
#endif // POLLY_ISLAST_H
|