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 struct Dependences; 33 34 class IslAst { 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 /// Print a source code representation of the program. 44 void pprint(raw_ostream &OS); 45 46 isl::ast_node getAst(); 47 getSharedIslCtx()48 const std::shared_ptr<isl_ctx> getSharedIslCtx() const { return Ctx; } 49 50 /// Get the run-time conditions for the Scop. 51 isl::ast_expr getRunCondition(); 52 53 /// Build run-time condition for scop. 54 /// 55 /// @param S The scop to build the condition for. 56 /// @param Build The isl_build object to use to build the condition. 57 /// 58 /// @returns An ast expression that describes the necessary run-time check. 59 static isl::ast_expr buildRunCondition(Scop &S, const isl::ast_build &Build); 60 61 private: 62 Scop &S; 63 std::shared_ptr<isl_ctx> Ctx; 64 isl::ast_expr RunCondition; 65 isl::ast_node Root; 66 67 IslAst(Scop &Scop); 68 69 void init(const Dependences &D); 70 }; 71 72 class IslAstInfo { 73 public: 74 using MemoryAccessSet = SmallPtrSet<MemoryAccess *, 4>; 75 76 /// Payload information used to annotate an AST node. 77 struct IslAstUserPayload { 78 /// Construct and initialize the payload. 79 IslAstUserPayload() = default; 80 81 /// Does the dependence analysis determine that there are no loop-carried 82 /// dependencies? 83 bool IsParallel = false; 84 85 /// Flag to mark innermost loops. 86 bool IsInnermost = false; 87 88 /// Flag to mark innermost parallel loops. 89 bool IsInnermostParallel = false; 90 91 /// Flag to mark outermost parallel loops. 92 bool IsOutermostParallel = false; 93 94 /// Flag to mark parallel loops which break reductions. 95 bool IsReductionParallel = false; 96 97 /// The minimal dependence distance for non parallel loops. 98 isl::pw_aff MinimalDependenceDistance; 99 100 /// The build environment at the time this node was constructed. 101 isl::ast_build Build; 102 103 /// Set of accesses which break reduction dependences. 104 MemoryAccessSet BrokenReductions; 105 }; 106 107 private: 108 Scop &S; 109 IslAst Ast; 110 111 public: IslAstInfo(Scop & S,const Dependences & D)112 IslAstInfo(Scop &S, const Dependences &D) : S(S), Ast(IslAst::create(S, D)) {} 113 114 /// Return the isl AST computed by this IslAstInfo. getIslAst()115 IslAst &getIslAst() { return Ast; } 116 117 /// Return a copy of the AST root node. 118 isl::ast_node getAst(); 119 120 /// Get the run condition. 121 /// 122 /// Only if the run condition evaluates at run-time to a non-zero value, the 123 /// assumptions that have been taken hold. If the run condition evaluates to 124 /// zero/false some assumptions do not hold and the original code needs to 125 /// be executed. 126 isl::ast_expr getRunCondition(); 127 128 void print(raw_ostream &O); 129 130 /// @name Extract information attached to an isl ast (for) node. 131 /// 132 ///{ 133 /// Get the complete payload attached to @p Node. 134 static IslAstUserPayload *getNodePayload(const isl::ast_node &Node); 135 136 /// Is this loop an innermost loop? 137 static bool isInnermost(const isl::ast_node &Node); 138 139 /// Is this loop a parallel loop? 140 static bool isParallel(const isl::ast_node &Node); 141 142 /// Is this loop an outermost parallel loop? 143 static bool isOutermostParallel(const isl::ast_node &Node); 144 145 /// Is this loop an innermost parallel loop? 146 static bool isInnermostParallel(const isl::ast_node &Node); 147 148 /// Is this loop a reduction parallel loop? 149 static bool isReductionParallel(const isl::ast_node &Node); 150 151 /// Will the loop be run as thread parallel? 152 static bool isExecutedInParallel(const isl::ast_node &Node); 153 154 /// Get the nodes schedule or a nullptr if not available. 155 static isl::union_map getSchedule(const isl::ast_node &Node); 156 157 /// Get minimal dependence distance or nullptr if not available. 158 static isl::pw_aff getMinimalDependenceDistance(const isl::ast_node &Node); 159 160 /// Get the nodes broken reductions or a nullptr if not available. 161 static MemoryAccessSet *getBrokenReductions(const isl::ast_node &Node); 162 163 /// Get the nodes build context or a nullptr if not available. 164 static isl::ast_build getBuild(const isl::ast_node &Node); 165 166 ///} 167 }; 168 169 struct IslAstAnalysis : public AnalysisInfoMixin<IslAstAnalysis> { 170 static AnalysisKey Key; 171 172 using Result = IslAstInfo; 173 174 IslAstInfo run(Scop &S, ScopAnalysisManager &SAM, 175 ScopStandardAnalysisResults &SAR); 176 }; 177 178 class IslAstInfoWrapperPass : public ScopPass { 179 std::unique_ptr<IslAstInfo> Ast; 180 181 public: 182 static char ID; 183 IslAstInfoWrapperPass()184 IslAstInfoWrapperPass() : ScopPass(ID) {} 185 getAI()186 IslAstInfo &getAI() { return *Ast; } getAI()187 const IslAstInfo &getAI() const { return *Ast; } 188 189 /// Build the AST for the given SCoP @p S. 190 bool runOnScop(Scop &S) override; 191 192 /// Register all analyses and transformation required. 193 void getAnalysisUsage(AnalysisUsage &AU) const override; 194 195 /// Release the internal memory. 196 void releaseMemory() override; 197 198 /// Print a source code representation of the program. 199 void printScop(raw_ostream &OS, Scop &S) const override; 200 }; 201 202 struct IslAstPrinterPass : public PassInfoMixin<IslAstPrinterPass> { IslAstPrinterPassIslAstPrinterPass203 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 #endif // POLLY_ISLAST_H 213