1 //===- IslAst.h - Interface to the isl code generator -----------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // The isl code generator interface takes a Scop and generates a isl_ast. This
10 // ist_ast can either be returned directly or it can be pretty printed to
11 // stdout.
12 //
13 // A typical isl_ast output looks like this:
14 //
15 // for (c2 = max(0, ceild(n + m, 2); c2 <= min(511, floord(5 * n, 3)); c2++) {
16 //   bb2(c2);
17 // }
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #ifndef POLLY_ISLAST_H
22 #define POLLY_ISLAST_H
23 
24 #include "polly/ScopPass.h"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/IR/PassManager.h"
27 #include "isl/ctx.h"
28 
29 namespace polly {
30 using llvm::SmallPtrSet;
31 
32 class Dependences;
33 
34 class IslAst final {
35 public:
36   IslAst(const IslAst &) = delete;
37   IslAst &operator=(const IslAst &) = delete;
38   IslAst(IslAst &&);
39   IslAst &operator=(IslAst &&) = delete;
40 
41   static IslAst create(Scop &Scop, const Dependences &D);
42 
43   isl::ast_node getAst();
44 
getSharedIslCtx()45   const std::shared_ptr<isl_ctx> getSharedIslCtx() const { return Ctx; }
46 
47   /// Get the run-time conditions for the Scop.
48   isl::ast_expr getRunCondition();
49 
50   /// Build run-time condition for scop.
51   ///
52   /// @param S     The scop to build the condition for.
53   /// @param Build The isl_build object to use to build the condition.
54   ///
55   /// @returns An ast expression that describes the necessary run-time check.
56   static isl::ast_expr buildRunCondition(Scop &S, const isl::ast_build &Build);
57 
58 private:
59   Scop &S;
60   std::shared_ptr<isl_ctx> Ctx;
61   isl::ast_expr RunCondition;
62   isl::ast_node Root;
63 
64   IslAst(Scop &Scop);
65 
66   void init(const Dependences &D);
67 };
68 
69 class IslAstInfo {
70 public:
71   using MemoryAccessSet = SmallPtrSet<MemoryAccess *, 4>;
72 
73   /// Payload information used to annotate an AST node.
74   struct IslAstUserPayload {
75     /// Construct and initialize the payload.
76     IslAstUserPayload() = default;
77 
78     /// Does the dependence analysis determine that there are no loop-carried
79     /// dependencies?
80     bool IsParallel = false;
81 
82     /// Flag to mark innermost loops.
83     bool IsInnermost = false;
84 
85     /// Flag to mark innermost parallel loops.
86     bool IsInnermostParallel = false;
87 
88     /// Flag to mark outermost parallel loops.
89     bool IsOutermostParallel = false;
90 
91     /// Flag to mark parallel loops which break reductions.
92     bool IsReductionParallel = false;
93 
94     /// The minimal dependence distance for non parallel loops.
95     isl::pw_aff MinimalDependenceDistance;
96 
97     /// The build environment at the time this node was constructed.
98     isl::ast_build Build;
99 
100     /// Set of accesses which break reduction dependences.
101     MemoryAccessSet BrokenReductions;
102   };
103 
104 private:
105   Scop &S;
106   IslAst Ast;
107 
108 public:
IslAstInfo(Scop & S,const Dependences & D)109   IslAstInfo(Scop &S, const Dependences &D) : S(S), Ast(IslAst::create(S, D)) {}
110 
111   /// Return the isl AST computed by this IslAstInfo.
getIslAst()112   IslAst &getIslAst() { return Ast; }
113 
114   /// Return a copy of the AST root node.
115   isl::ast_node getAst();
116 
117   /// Get the run condition.
118   ///
119   /// Only if the run condition evaluates at run-time to a non-zero value, the
120   /// assumptions that have been taken hold. If the run condition evaluates to
121   /// zero/false some assumptions do not hold and the original code needs to
122   /// be executed.
123   isl::ast_expr getRunCondition();
124 
125   void print(raw_ostream &O);
126 
127   /// @name Extract information attached to an isl ast (for) node.
128   ///
129   ///{
130   /// Get the complete payload attached to @p Node.
131   static IslAstUserPayload *getNodePayload(const isl::ast_node &Node);
132 
133   /// Is this loop an innermost loop?
134   static bool isInnermost(const isl::ast_node &Node);
135 
136   /// Is this loop a parallel loop?
137   static bool isParallel(const isl::ast_node &Node);
138 
139   /// Is this loop an outermost parallel loop?
140   static bool isOutermostParallel(const isl::ast_node &Node);
141 
142   /// Is this loop an innermost parallel loop?
143   static bool isInnermostParallel(const isl::ast_node &Node);
144 
145   /// Is this loop a reduction parallel loop?
146   static bool isReductionParallel(const isl::ast_node &Node);
147 
148   /// Will the loop be run as thread parallel?
149   static bool isExecutedInParallel(const isl::ast_node &Node);
150 
151   /// Get the nodes schedule or a nullptr if not available.
152   static isl::union_map getSchedule(const isl::ast_node &Node);
153 
154   /// Get minimal dependence distance or nullptr if not available.
155   static isl::pw_aff getMinimalDependenceDistance(const isl::ast_node &Node);
156 
157   /// Get the nodes broken reductions or a nullptr if not available.
158   static MemoryAccessSet *getBrokenReductions(const isl::ast_node &Node);
159 
160   /// Get the nodes build context or a nullptr if not available.
161   static isl::ast_build getBuild(const isl::ast_node &Node);
162 
163   ///}
164 };
165 
166 struct IslAstAnalysis : AnalysisInfoMixin<IslAstAnalysis> {
167   static AnalysisKey Key;
168 
169   using Result = IslAstInfo;
170 
171   IslAstInfo run(Scop &S, ScopAnalysisManager &SAM,
172                  ScopStandardAnalysisResults &SAR);
173 };
174 
175 class IslAstInfoWrapperPass final : public ScopPass {
176   std::unique_ptr<IslAstInfo> Ast;
177 
178 public:
179   static char ID;
180 
IslAstInfoWrapperPass()181   IslAstInfoWrapperPass() : ScopPass(ID) {}
182 
getAI()183   IslAstInfo &getAI() { return *Ast; }
getAI()184   const IslAstInfo &getAI() const { return *Ast; }
185 
186   /// Build the AST for the given SCoP @p S.
187   bool runOnScop(Scop &S) override;
188 
189   /// Register all analyses and transformation required.
190   void getAnalysisUsage(AnalysisUsage &AU) const override;
191 
192   /// Release the internal memory.
193   void releaseMemory() override;
194 
195   /// Print a source code representation of the program.
196   void printScop(raw_ostream &OS, Scop &S) const override;
197 };
198 
199 llvm::Pass *createIslAstInfoWrapperPassPass();
200 llvm::Pass *createIslAstInfoPrinterLegacyPass(llvm::raw_ostream &OS);
201 
202 struct IslAstPrinterPass final : PassInfoMixin<IslAstPrinterPass> {
IslAstPrinterPassfinal203   IslAstPrinterPass(raw_ostream &OS) : OS(OS) {}
204 
205   PreservedAnalyses run(Scop &S, ScopAnalysisManager &SAM,
206                         ScopStandardAnalysisResults &, SPMUpdater &U);
207 
208   raw_ostream &OS;
209 };
210 } // namespace polly
211 
212 namespace llvm {
213 void initializeIslAstInfoWrapperPassPass(llvm::PassRegistry &);
214 void initializeIslAstInfoPrinterLegacyPassPass(llvm::PassRegistry &);
215 } // namespace llvm
216 
217 #endif // POLLY_ISLAST_H
218