EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2026-05-10 08:48:11
0001 //===-IslExprBuilder.h - Helper to generate code for isl AST expressions --===// 0002 // 0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 0004 // See https://llvm.org/LICENSE.txt for license information. 0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 0006 // 0007 //===----------------------------------------------------------------------===// 0008 // 0009 //===----------------------------------------------------------------------===// 0010 0011 #ifndef POLLY_ISL_EXPR_BUILDER_H 0012 #define POLLY_ISL_EXPR_BUILDER_H 0013 0014 #include "polly/CodeGen/IRBuilder.h" 0015 #include "polly/Support/ScopHelper.h" 0016 #include "isl/isl-noexceptions.h" 0017 0018 namespace llvm { 0019 // Provide PointerLikeTypeTraits for isl_id. 0020 template <> struct PointerLikeTypeTraits<isl_id *> { 0021 0022 public: 0023 static inline const void *getAsVoidPointer(isl_id *P) { return (void *)P; } 0024 static inline const Region *getFromVoidPointer(void *P) { 0025 return (Region *)P; 0026 } 0027 static constexpr int NumLowBitsAvailable = 0; 0028 }; 0029 } // namespace llvm 0030 0031 namespace polly { 0032 class ScopArrayInfo; 0033 0034 /// LLVM-IR generator for isl_ast_expr[essions] 0035 /// 0036 /// This generator generates LLVM-IR that performs the computation described by 0037 /// an isl_ast_expr[ession]. 0038 /// 0039 /// Example: 0040 /// 0041 /// An isl_ast_expr[ession] can look like this: 0042 /// 0043 /// (N + M) + 10 0044 /// 0045 /// The IslExprBuilder could create the following LLVM-IR: 0046 /// 0047 /// %tmp1 = add nsw i64 %N 0048 /// %tmp2 = add nsw i64 %tmp1, %M 0049 /// %tmp3 = add nsw i64 %tmp2, 10 0050 /// 0051 /// The implementation of this class is mostly a mapping from isl_ast_expr 0052 /// constructs to the corresponding LLVM-IR constructs. 0053 /// 0054 /// The following decisions may need some explanation: 0055 /// 0056 /// 1) Which data-type to choose 0057 /// 0058 /// isl_ast_expr[essions] are untyped expressions that assume arbitrary 0059 /// precision integer computations. LLVM-IR instead has fixed size integers. 0060 /// When lowering to LLVM-IR we need to chose both the size of the data type and 0061 /// the sign of the operations we use. 0062 /// 0063 /// At the moment, we hardcode i64 bit signed computations. Our experience has 0064 /// shown that 64 bit are generally large enough for the loop bounds that appear 0065 /// in the wild. Signed computations are needed, as loop bounds may become 0066 /// negative. 0067 /// 0068 /// It is possible to track overflows that occurred in the generated IR. See the 0069 /// description of @see OverflowState for more information. 0070 /// 0071 /// FIXME: Hardcoding sizes can cause issues: 0072 /// 0073 /// - On embedded systems and especially for high-level-synthesis 64 bit 0074 /// computations are very costly. 0075 /// 0076 /// The right approach is to compute the minimal necessary bitwidth and 0077 /// signedness for each subexpression during in the isl AST generation and 0078 /// to use this information in our IslAstGenerator. Preliminary patches are 0079 /// available, but have not been committed yet. 0080 /// 0081 class IslExprBuilder final { 0082 public: 0083 /// A map from isl_ids to llvm::Values. 0084 typedef llvm::MapVector<isl_id *, llvm::AssertingVH<llvm::Value>> IDToValueTy; 0085 0086 typedef llvm::MapVector<isl_id *, const ScopArrayInfo *> IDToScopArrayInfoTy; 0087 0088 /// A map from isl_ids to ScopArrayInfo objects. 0089 /// 0090 /// This map is used to obtain ScopArrayInfo objects for isl_ids which do not 0091 /// carry a ScopArrayInfo object in their user pointer. This is useful if the 0092 /// construction of ScopArrayInfo objects happens only after references (e.g. 0093 /// in an AST) to an isl_id are generated and the user pointer of the isl_id 0094 /// can not be changed any more. 0095 /// 0096 /// This is useful for external users who just use the IslExprBuilder for 0097 /// code generation. 0098 IDToScopArrayInfoTy *IDToSAI = nullptr; 0099 0100 /// Set the isl_id to ScopArrayInfo map. 0101 /// 0102 /// @param NewIDToSAI The new isl_id to ScopArrayInfo map to use. 0103 void setIDToSAI(IDToScopArrayInfoTy *NewIDToSAI) { IDToSAI = NewIDToSAI; } 0104 0105 /// Construct an IslExprBuilder. 0106 /// 0107 /// @param Builder The IRBuilder used to construct the 0108 /// isl_ast_expr[ession]. The insert location of this 0109 /// IRBuilder defines WHERE the corresponding LLVM-IR 0110 /// is generated. 0111 /// @param IDToValue The isl_ast_expr[ession] may reference parameters or 0112 /// variables (identified by an isl_id). The IDTOValue map 0113 /// specifies the LLVM-IR Values that correspond to these 0114 /// parameters and variables. 0115 /// @param GlobalMap A mapping from llvm::Values used in the original scop 0116 /// region to a new set of llvm::Values. 0117 /// @param DL DataLayout for the current Module. 0118 /// @param SE ScalarEvolution analysis for the current function. 0119 /// @param DT DominatorTree analysis for the current function. 0120 /// @param LI LoopInfo analysis for the current function. 0121 /// @param StartBlock The first basic block after the RTC. 0122 IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue, 0123 ValueMapT &GlobalMap, const llvm::DataLayout &DL, 0124 llvm::ScalarEvolution &SE, llvm::DominatorTree &DT, 0125 llvm::LoopInfo &LI, llvm::BasicBlock *StartBlock); 0126 0127 /// Change the function that code is emitted into. 0128 void switchGeneratedFunc(llvm::Function *GenFn, llvm::DominatorTree *GenDT, 0129 llvm::LoopInfo *GenLI, llvm::ScalarEvolution *GenSE); 0130 0131 /// Create LLVM-IR for an isl_ast_expr[ession]. 0132 /// 0133 /// @param Expr The ast expression for which we generate LLVM-IR. 0134 /// 0135 /// @return The llvm::Value* containing the result of the computation. 0136 llvm::Value *create(__isl_take isl_ast_expr *Expr); 0137 0138 /// Create LLVM-IR for an isl_ast_expr[ession] and cast it to i1. 0139 llvm::Value *createBool(__isl_take isl_ast_expr *Expr); 0140 0141 /// Return the largest of two types. 0142 /// 0143 /// @param T1 The first type. 0144 /// @param T2 The second type. 0145 /// 0146 /// @return The largest of the two types. 0147 llvm::Type *getWidestType(llvm::Type *T1, llvm::Type *T2); 0148 0149 /// Return the type with which this expression should be computed. 0150 /// 0151 /// The type needs to be large enough to hold all possible input and all 0152 /// possible output values. 0153 /// 0154 /// @param Expr The expression for which to find the type. 0155 /// @return The type with which the expression should be computed. 0156 llvm::IntegerType *getType(__isl_keep isl_ast_expr *Expr); 0157 0158 /// Change if runtime overflows are tracked or not. 0159 /// 0160 /// @param Enable Flag to enable/disable the tracking. 0161 /// 0162 /// Note that this will reset the tracking state and that tracking is only 0163 /// allowed if the last tracked expression dominates the current insert point. 0164 void setTrackOverflow(bool Enable); 0165 0166 /// Return the current overflow status or nullptr if it is not tracked. 0167 /// 0168 /// @return A nullptr if tracking is disabled or otherwise an i1 that has the 0169 /// value of "0" if and only if no overflow happened since tracking 0170 /// was enabled. 0171 llvm::Value *getOverflowState() const; 0172 0173 /// Create LLVM-IR that computes the memory location of an access expression. 0174 /// 0175 /// For a given isl_ast_expr[ession] of type isl_ast_op_access this function 0176 /// creates IR that computes the address the access expression refers to. 0177 /// 0178 /// @param Expr The ast expression of type isl_ast_op_access 0179 /// for which we generate LLVM-IR. 0180 /// 0181 /// @return A pair of the llvm::Value* containing the result of the 0182 /// computation and the llvm::Type* it points to. 0183 std::pair<llvm::Value *, llvm::Type *> 0184 createAccessAddress(__isl_take isl_ast_expr *Expr); 0185 0186 /// Check if an @p Expr contains integer constants larger than 64 bit. 0187 /// 0188 /// @param Expr The expression to check. 0189 /// 0190 /// @return True if the ast expression is larger than 64 bit. 0191 bool hasLargeInts(isl::ast_expr Expr); 0192 0193 private: 0194 Scop &S; 0195 0196 /// Flag that will be set if an overflow occurred at runtime. 0197 /// 0198 /// Note that this flag is by default a nullptr and if it is a nullptr 0199 /// we will not record overflows but simply perform the computations. 0200 /// The intended usage is as follows: 0201 /// - If overflows in [an] expression[s] should be tracked, call 0202 /// the setTrackOverflow(true) function. 0203 /// - Use create(...) for all expressions that should be checked. 0204 /// - Call getOverflowState() to get the value representing the current 0205 /// state of the overflow flag. 0206 /// - To stop tracking call setTrackOverflow(false). 0207 llvm::Value *OverflowState; 0208 0209 PollyIRBuilder &Builder; 0210 IDToValueTy &IDToValue; 0211 ValueMapT &GlobalMap; 0212 0213 const llvm::DataLayout &DL; 0214 llvm::ScalarEvolution &SE; 0215 llvm::BasicBlock *StartBlock; 0216 0217 /// Relates to the region where the code is emitted into. 0218 /// @{ 0219 llvm::DominatorTree *GenDT; 0220 llvm::LoopInfo *GenLI; 0221 llvm::ScalarEvolution *GenSE; 0222 /// @} 0223 0224 llvm::Value *createOp(__isl_take isl_ast_expr *Expr); 0225 llvm::Value *createOpUnary(__isl_take isl_ast_expr *Expr); 0226 llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr); 0227 llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr); 0228 llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr); 0229 llvm::Value *createOpSelect(__isl_take isl_ast_expr *Expr); 0230 llvm::Value *createOpICmp(__isl_take isl_ast_expr *Expr); 0231 llvm::Value *createOpBoolean(__isl_take isl_ast_expr *Expr); 0232 llvm::Value *createOpBooleanConditional(__isl_take isl_ast_expr *Expr); 0233 llvm::Value *createId(__isl_take isl_ast_expr *Expr); 0234 llvm::Value *createInt(__isl_take isl_ast_expr *Expr); 0235 llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr); 0236 0237 /// Create a binary operation @p Opc and track overflows if requested. 0238 /// 0239 /// @param OpC The binary operation that should be performed [Add/Sub/Mul]. 0240 /// @param LHS The left operand. 0241 /// @param RHS The right operand. 0242 /// @param Name The (base) name of the new IR operations. 0243 /// 0244 /// @return A value that represents the result of the binary operation. 0245 llvm::Value *createBinOp(llvm::BinaryOperator::BinaryOps Opc, 0246 llvm::Value *LHS, llvm::Value *RHS, 0247 const llvm::Twine &Name); 0248 0249 /// Create an addition and track overflows if requested. 0250 /// 0251 /// @param LHS The left operand. 0252 /// @param RHS The right operand. 0253 /// @param Name The (base) name of the new IR operations. 0254 /// 0255 /// @return A value that represents the result of the addition. 0256 llvm::Value *createAdd(llvm::Value *LHS, llvm::Value *RHS, 0257 const llvm::Twine &Name = ""); 0258 0259 /// Create a subtraction and track overflows if requested. 0260 /// 0261 /// @param LHS The left operand. 0262 /// @param RHS The right operand. 0263 /// @param Name The (base) name of the new IR operations. 0264 /// 0265 /// @return A value that represents the result of the subtraction. 0266 llvm::Value *createSub(llvm::Value *LHS, llvm::Value *RHS, 0267 const llvm::Twine &Name = ""); 0268 0269 /// Create a multiplication and track overflows if requested. 0270 /// 0271 /// @param LHS The left operand. 0272 /// @param RHS The right operand. 0273 /// @param Name The (base) name of the new IR operations. 0274 /// 0275 /// @return A value that represents the result of the multiplication. 0276 llvm::Value *createMul(llvm::Value *LHS, llvm::Value *RHS, 0277 const llvm::Twine &Name = ""); 0278 }; 0279 } // namespace polly 0280 0281 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|