1 //===-IslExprBuilder.h - Helper to generate code for isl AST expressions --===// 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 //===----------------------------------------------------------------------===// 10 11 #ifndef POLLY_ISL_EXPR_BUILDER_H 12 #define POLLY_ISL_EXPR_BUILDER_H 13 14 #include "polly/CodeGen/IRBuilder.h" 15 #include "polly/Support/ScopHelper.h" 16 #include "isl/isl-noexceptions.h" 17 18 namespace llvm { 19 // Provide PointerLikeTypeTraits for isl_id. 20 template <> struct PointerLikeTypeTraits<isl_id *> { 21 22 public: 23 static inline const void *getAsVoidPointer(isl_id *P) { return (void *)P; } 24 static inline const Region *getFromVoidPointer(void *P) { 25 return (Region *)P; 26 } 27 static constexpr int NumLowBitsAvailable = 0; 28 }; 29 } // namespace llvm 30 31 namespace polly { 32 class ScopArrayInfo; 33 34 /// LLVM-IR generator for isl_ast_expr[essions] 35 /// 36 /// This generator generates LLVM-IR that performs the computation described by 37 /// an isl_ast_expr[ession]. 38 /// 39 /// Example: 40 /// 41 /// An isl_ast_expr[ession] can look like this: 42 /// 43 /// (N + M) + 10 44 /// 45 /// The IslExprBuilder could create the following LLVM-IR: 46 /// 47 /// %tmp1 = add nsw i64 %N 48 /// %tmp2 = add nsw i64 %tmp1, %M 49 /// %tmp3 = add nsw i64 %tmp2, 10 50 /// 51 /// The implementation of this class is mostly a mapping from isl_ast_expr 52 /// constructs to the corresponding LLVM-IR constructs. 53 /// 54 /// The following decisions may need some explanation: 55 /// 56 /// 1) Which data-type to choose 57 /// 58 /// isl_ast_expr[essions] are untyped expressions that assume arbitrary 59 /// precision integer computations. LLVM-IR instead has fixed size integers. 60 /// When lowering to LLVM-IR we need to chose both the size of the data type and 61 /// the sign of the operations we use. 62 /// 63 /// At the moment, we hardcode i64 bit signed computations. Our experience has 64 /// shown that 64 bit are generally large enough for the loop bounds that appear 65 /// in the wild. Signed computations are needed, as loop bounds may become 66 /// negative. 67 /// 68 /// It is possible to track overflows that occurred in the generated IR. See the 69 /// description of @see OverflowState for more information. 70 /// 71 /// FIXME: Hardcoding sizes can cause issues: 72 /// 73 /// - On embedded systems and especially for high-level-synthesis 64 bit 74 /// computations are very costly. 75 /// 76 /// The right approach is to compute the minimal necessary bitwidth and 77 /// signedness for each subexpression during in the isl AST generation and 78 /// to use this information in our IslAstGenerator. Preliminary patches are 79 /// available, but have not been committed yet. 80 /// 81 class IslExprBuilder final { 82 public: 83 /// A map from isl_ids to llvm::Values. 84 typedef llvm::MapVector<isl_id *, llvm::AssertingVH<llvm::Value>> IDToValueTy; 85 86 typedef llvm::MapVector<isl_id *, const ScopArrayInfo *> IDToScopArrayInfoTy; 87 88 /// A map from isl_ids to ScopArrayInfo objects. 89 /// 90 /// This map is used to obtain ScopArrayInfo objects for isl_ids which do not 91 /// carry a ScopArrayInfo object in their user pointer. This is useful if the 92 /// construction of ScopArrayInfo objects happens only after references (e.g. 93 /// in an AST) to an isl_id are generated and the user pointer of the isl_id 94 /// can not be changed any more. 95 /// 96 /// This is useful for external users who just use the IslExprBuilder for 97 /// code generation. 98 IDToScopArrayInfoTy *IDToSAI = nullptr; 99 100 /// Set the isl_id to ScopArrayInfo map. 101 /// 102 /// @param NewIDToSAI The new isl_id to ScopArrayInfo map to use. 103 void setIDToSAI(IDToScopArrayInfoTy *NewIDToSAI) { IDToSAI = NewIDToSAI; } 104 105 /// Construct an IslExprBuilder. 106 /// 107 /// @param Builder The IRBuilder used to construct the 108 /// isl_ast_expr[ession]. The insert location of this 109 /// IRBuilder defines WHERE the corresponding LLVM-IR 110 /// is generated. 111 /// @param IDToValue The isl_ast_expr[ession] may reference parameters or 112 /// variables (identified by an isl_id). The IDTOValue map 113 /// specifies the LLVM-IR Values that correspond to these 114 /// parameters and variables. 115 /// @param GlobalMap A mapping from llvm::Values used in the original scop 116 /// region to a new set of llvm::Values. 117 /// @param DL DataLayout for the current Module. 118 /// @param SE ScalarEvolution analysis for the current function. 119 /// @param DT DominatorTree analysis for the current function. 120 /// @param LI LoopInfo analysis for the current function. 121 /// @param StartBlock The first basic block after the RTC. 122 IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue, 123 ValueMapT &GlobalMap, const llvm::DataLayout &DL, 124 llvm::ScalarEvolution &SE, llvm::DominatorTree &DT, 125 llvm::LoopInfo &LI, llvm::BasicBlock *StartBlock); 126 127 /// Create LLVM-IR for an isl_ast_expr[ession]. 128 /// 129 /// @param Expr The ast expression for which we generate LLVM-IR. 130 /// 131 /// @return The llvm::Value* containing the result of the computation. 132 llvm::Value *create(__isl_take isl_ast_expr *Expr); 133 134 /// Return the largest of two types. 135 /// 136 /// @param T1 The first type. 137 /// @param T2 The second type. 138 /// 139 /// @return The largest of the two types. 140 llvm::Type *getWidestType(llvm::Type *T1, llvm::Type *T2); 141 142 /// Return the type with which this expression should be computed. 143 /// 144 /// The type needs to be large enough to hold all possible input and all 145 /// possible output values. 146 /// 147 /// @param Expr The expression for which to find the type. 148 /// @return The type with which the expression should be computed. 149 llvm::IntegerType *getType(__isl_keep isl_ast_expr *Expr); 150 151 /// Change if runtime overflows are tracked or not. 152 /// 153 /// @param Enable Flag to enable/disable the tracking. 154 /// 155 /// Note that this will reset the tracking state and that tracking is only 156 /// allowed if the last tracked expression dominates the current insert point. 157 void setTrackOverflow(bool Enable); 158 159 /// Return the current overflow status or nullptr if it is not tracked. 160 /// 161 /// @return A nullptr if tracking is disabled or otherwise an i1 that has the 162 /// value of "0" if and only if no overflow happened since tracking 163 /// was enabled. 164 llvm::Value *getOverflowState() const; 165 166 /// Create LLVM-IR that computes the memory location of an access expression. 167 /// 168 /// For a given isl_ast_expr[ession] of type isl_ast_op_access this function 169 /// creates IR that computes the address the access expression refers to. 170 /// 171 /// @param Expr The ast expression of type isl_ast_op_access 172 /// for which we generate LLVM-IR. 173 /// 174 /// @return A pair of the llvm::Value* containing the result of the 175 /// computation and the llvm::Type* it points to. 176 std::pair<llvm::Value *, llvm::Type *> 177 createAccessAddress(__isl_take isl_ast_expr *Expr); 178 179 /// Check if an @p Expr contains integer constants larger than 64 bit. 180 /// 181 /// @param Expr The expression to check. 182 /// 183 /// @return True if the ast expression is larger than 64 bit. 184 bool hasLargeInts(isl::ast_expr Expr); 185 186 private: 187 Scop &S; 188 189 /// Flag that will be set if an overflow occurred at runtime. 190 /// 191 /// Note that this flag is by default a nullptr and if it is a nullptr 192 /// we will not record overflows but simply perform the computations. 193 /// The intended usage is as follows: 194 /// - If overflows in [an] expression[s] should be tracked, call 195 /// the setTrackOverflow(true) function. 196 /// - Use create(...) for all expressions that should be checked. 197 /// - Call getOverflowState() to get the value representing the current 198 /// state of the overflow flag. 199 /// - To stop tracking call setTrackOverflow(false). 200 llvm::Value *OverflowState; 201 202 PollyIRBuilder &Builder; 203 IDToValueTy &IDToValue; 204 ValueMapT &GlobalMap; 205 206 const llvm::DataLayout &DL; 207 llvm::ScalarEvolution &SE; 208 llvm::DominatorTree &DT; 209 llvm::LoopInfo &LI; 210 llvm::BasicBlock *StartBlock; 211 212 llvm::Value *createOp(__isl_take isl_ast_expr *Expr); 213 llvm::Value *createOpUnary(__isl_take isl_ast_expr *Expr); 214 llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr); 215 llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr); 216 llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr); 217 llvm::Value *createOpSelect(__isl_take isl_ast_expr *Expr); 218 llvm::Value *createOpICmp(__isl_take isl_ast_expr *Expr); 219 llvm::Value *createOpBoolean(__isl_take isl_ast_expr *Expr); 220 llvm::Value *createOpBooleanConditional(__isl_take isl_ast_expr *Expr); 221 llvm::Value *createId(__isl_take isl_ast_expr *Expr); 222 llvm::Value *createInt(__isl_take isl_ast_expr *Expr); 223 llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr); 224 225 /// Create a binary operation @p Opc and track overflows if requested. 226 /// 227 /// @param OpC The binary operation that should be performed [Add/Sub/Mul]. 228 /// @param LHS The left operand. 229 /// @param RHS The right operand. 230 /// @param Name The (base) name of the new IR operations. 231 /// 232 /// @return A value that represents the result of the binary operation. 233 llvm::Value *createBinOp(llvm::BinaryOperator::BinaryOps Opc, 234 llvm::Value *LHS, llvm::Value *RHS, 235 const llvm::Twine &Name); 236 237 /// Create an addition and track overflows if requested. 238 /// 239 /// @param LHS The left operand. 240 /// @param RHS The right operand. 241 /// @param Name The (base) name of the new IR operations. 242 /// 243 /// @return A value that represents the result of the addition. 244 llvm::Value *createAdd(llvm::Value *LHS, llvm::Value *RHS, 245 const llvm::Twine &Name = ""); 246 247 /// Create a subtraction and track overflows if requested. 248 /// 249 /// @param LHS The left operand. 250 /// @param RHS The right operand. 251 /// @param Name The (base) name of the new IR operations. 252 /// 253 /// @return A value that represents the result of the subtraction. 254 llvm::Value *createSub(llvm::Value *LHS, llvm::Value *RHS, 255 const llvm::Twine &Name = ""); 256 257 /// Create a multiplication and track overflows if requested. 258 /// 259 /// @param LHS The left operand. 260 /// @param RHS The right operand. 261 /// @param Name The (base) name of the new IR operations. 262 /// 263 /// @return A value that represents the result of the multiplication. 264 llvm::Value *createMul(llvm::Value *LHS, llvm::Value *RHS, 265 const llvm::Twine &Name = ""); 266 }; 267 } // namespace polly 268 269 #endif 270