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