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 /// Change the function that code is emitted into. 128 void switchGeneratedFunc(llvm::Function *GenFn, llvm::DominatorTree *GenDT, 129 llvm::LoopInfo *GenLI, llvm::ScalarEvolution *GenSE); 130 131 /// Create LLVM-IR for an isl_ast_expr[ession]. 132 /// 133 /// @param Expr The ast expression for which we generate LLVM-IR. 134 /// 135 /// @return The llvm::Value* containing the result of the computation. 136 llvm::Value *create(__isl_take isl_ast_expr *Expr); 137 138 /// Return the largest of two types. 139 /// 140 /// @param T1 The first type. 141 /// @param T2 The second type. 142 /// 143 /// @return The largest of the two types. 144 llvm::Type *getWidestType(llvm::Type *T1, llvm::Type *T2); 145 146 /// Return the type with which this expression should be computed. 147 /// 148 /// The type needs to be large enough to hold all possible input and all 149 /// possible output values. 150 /// 151 /// @param Expr The expression for which to find the type. 152 /// @return The type with which the expression should be computed. 153 llvm::IntegerType *getType(__isl_keep isl_ast_expr *Expr); 154 155 /// Change if runtime overflows are tracked or not. 156 /// 157 /// @param Enable Flag to enable/disable the tracking. 158 /// 159 /// Note that this will reset the tracking state and that tracking is only 160 /// allowed if the last tracked expression dominates the current insert point. 161 void setTrackOverflow(bool Enable); 162 163 /// Return the current overflow status or nullptr if it is not tracked. 164 /// 165 /// @return A nullptr if tracking is disabled or otherwise an i1 that has the 166 /// value of "0" if and only if no overflow happened since tracking 167 /// was enabled. 168 llvm::Value *getOverflowState() const; 169 170 /// Create LLVM-IR that computes the memory location of an access expression. 171 /// 172 /// For a given isl_ast_expr[ession] of type isl_ast_op_access this function 173 /// creates IR that computes the address the access expression refers to. 174 /// 175 /// @param Expr The ast expression of type isl_ast_op_access 176 /// for which we generate LLVM-IR. 177 /// 178 /// @return A pair of the llvm::Value* containing the result of the 179 /// computation and the llvm::Type* it points to. 180 std::pair<llvm::Value *, llvm::Type *> 181 createAccessAddress(__isl_take isl_ast_expr *Expr); 182 183 /// Check if an @p Expr contains integer constants larger than 64 bit. 184 /// 185 /// @param Expr The expression to check. 186 /// 187 /// @return True if the ast expression is larger than 64 bit. 188 bool hasLargeInts(isl::ast_expr Expr); 189 190 private: 191 Scop &S; 192 193 /// Flag that will be set if an overflow occurred at runtime. 194 /// 195 /// Note that this flag is by default a nullptr and if it is a nullptr 196 /// we will not record overflows but simply perform the computations. 197 /// The intended usage is as follows: 198 /// - If overflows in [an] expression[s] should be tracked, call 199 /// the setTrackOverflow(true) function. 200 /// - Use create(...) for all expressions that should be checked. 201 /// - Call getOverflowState() to get the value representing the current 202 /// state of the overflow flag. 203 /// - To stop tracking call setTrackOverflow(false). 204 llvm::Value *OverflowState; 205 206 PollyIRBuilder &Builder; 207 IDToValueTy &IDToValue; 208 ValueMapT &GlobalMap; 209 210 const llvm::DataLayout &DL; 211 llvm::ScalarEvolution &SE; 212 llvm::BasicBlock *StartBlock; 213 214 /// Relates to the region where the code is emitted into. 215 /// @{ 216 llvm::DominatorTree *GenDT; 217 llvm::LoopInfo *GenLI; 218 llvm::ScalarEvolution *GenSE; 219 /// @} 220 221 llvm::Value *createOp(__isl_take isl_ast_expr *Expr); 222 llvm::Value *createOpUnary(__isl_take isl_ast_expr *Expr); 223 llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr); 224 llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr); 225 llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr); 226 llvm::Value *createOpSelect(__isl_take isl_ast_expr *Expr); 227 llvm::Value *createOpICmp(__isl_take isl_ast_expr *Expr); 228 llvm::Value *createOpBoolean(__isl_take isl_ast_expr *Expr); 229 llvm::Value *createOpBooleanConditional(__isl_take isl_ast_expr *Expr); 230 llvm::Value *createId(__isl_take isl_ast_expr *Expr); 231 llvm::Value *createInt(__isl_take isl_ast_expr *Expr); 232 llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr); 233 234 /// Create a binary operation @p Opc and track overflows if requested. 235 /// 236 /// @param OpC The binary operation that should be performed [Add/Sub/Mul]. 237 /// @param LHS The left operand. 238 /// @param RHS The right operand. 239 /// @param Name The (base) name of the new IR operations. 240 /// 241 /// @return A value that represents the result of the binary operation. 242 llvm::Value *createBinOp(llvm::BinaryOperator::BinaryOps Opc, 243 llvm::Value *LHS, llvm::Value *RHS, 244 const llvm::Twine &Name); 245 246 /// Create an addition and track overflows if requested. 247 /// 248 /// @param LHS The left operand. 249 /// @param RHS The right operand. 250 /// @param Name The (base) name of the new IR operations. 251 /// 252 /// @return A value that represents the result of the addition. 253 llvm::Value *createAdd(llvm::Value *LHS, llvm::Value *RHS, 254 const llvm::Twine &Name = ""); 255 256 /// Create a subtraction and track overflows if requested. 257 /// 258 /// @param LHS The left operand. 259 /// @param RHS The right operand. 260 /// @param Name The (base) name of the new IR operations. 261 /// 262 /// @return A value that represents the result of the subtraction. 263 llvm::Value *createSub(llvm::Value *LHS, llvm::Value *RHS, 264 const llvm::Twine &Name = ""); 265 266 /// Create a multiplication and track overflows if requested. 267 /// 268 /// @param LHS The left operand. 269 /// @param RHS The right operand. 270 /// @param Name The (base) name of the new IR operations. 271 /// 272 /// @return A value that represents the result of the multiplication. 273 llvm::Value *createMul(llvm::Value *LHS, llvm::Value *RHS, 274 const llvm::Twine &Name = ""); 275 }; 276 } // namespace polly 277 278 #endif 279