1 //=- IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST -*- 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 // This file contains the IslNodeBuilder, a class to translate an isl AST into 10 // a LLVM-IR AST. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef POLLY_ISLNODEBUILDER_H 15 #define POLLY_ISLNODEBUILDER_H 16 17 #include "polly/CodeGen/BlockGenerators.h" 18 #include "polly/CodeGen/IslExprBuilder.h" 19 #include "polly/ScopDetectionDiagnostic.h" 20 #include "llvm/ADT/ArrayRef.h" 21 #include "llvm/ADT/SmallSet.h" 22 #include "llvm/IR/InstrTypes.h" 23 #include "isl/ctx.h" 24 #include "isl/isl-noexceptions.h" 25 26 namespace polly { 27 using llvm::LoopInfo; 28 using llvm::SmallSet; 29 30 struct InvariantEquivClassTy; 31 32 struct SubtreeReferences { 33 LoopInfo &LI; 34 ScalarEvolution &SE; 35 Scop &S; 36 ValueMapT &GlobalMap; 37 SetVector<Value *> &Values; 38 SetVector<const SCEV *> &SCEVs; 39 BlockGenerator &BlockGen; 40 // In case an (optional) parameter space location is provided, parameter space 41 // information is collected as well. 42 isl::space *ParamSpace; 43 }; 44 45 /// Extract the out-of-scop values and SCEVs referenced from a ScopStmt. 46 /// 47 /// This includes the SCEVUnknowns referenced by the SCEVs used in the 48 /// statement and the base pointers of the memory accesses. For scalar 49 /// statements we force the generation of alloca memory locations and list 50 /// these locations in the set of out-of-scop values as well. 51 /// 52 /// We also collect an isl::space that includes all parameter dimensions 53 /// used in the statement's memory accesses, in case the ParamSpace pointer 54 /// is non-null. 55 /// 56 /// @param Stmt The statement for which to extract the information. 57 /// @param UserPtr A void pointer that can be casted to a 58 /// SubtreeReferences structure. 59 /// @param CreateScalarRefs Should the result include allocas of scalar 60 /// references? 61 void addReferencesFromStmt(const ScopStmt *Stmt, void *UserPtr, 62 bool CreateScalarRefs = true); 63 64 class IslNodeBuilder { 65 public: IslNodeBuilder(PollyIRBuilder & Builder,ScopAnnotator & Annotator,const DataLayout & DL,LoopInfo & LI,ScalarEvolution & SE,DominatorTree & DT,Scop & S,BasicBlock * StartBlock)66 IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, 67 const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE, 68 DominatorTree &DT, Scop &S, BasicBlock *StartBlock) 69 : S(S), Builder(Builder), Annotator(Annotator), 70 ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI, 71 StartBlock), 72 BlockGen(Builder, LI, SE, DT, ScalarMap, EscapeMap, ValueMap, 73 &ExprBuilder, StartBlock), 74 RegionGen(BlockGen), DL(DL), LI(LI), SE(SE), DT(DT), 75 StartBlock(StartBlock) {} 76 77 virtual ~IslNodeBuilder() = default; 78 79 void addParameters(__isl_take isl_set *Context); 80 81 /// Create Values which hold the sizes of the outermost dimension of all 82 /// Fortran arrays in the current scop. 83 /// 84 /// @returns False, if a problem occurred and a Fortran array was not 85 /// materialized. True otherwise. 86 bool materializeFortranArrayOutermostDimension(); 87 88 /// Generate code that evaluates @p Condition at run-time. 89 /// 90 /// This function is typically called to generate the LLVM-IR for the 91 /// run-time condition of the scop, that verifies that all the optimistic 92 /// assumptions we have taken during scop modeling and transformation 93 /// hold at run-time. 94 /// 95 /// @param Condition The condition to evaluate 96 /// 97 /// @result An llvm::Value that is true if the condition holds and false 98 /// otherwise. 99 Value *createRTC(isl_ast_expr *Condition); 100 101 void create(__isl_take isl_ast_node *Node); 102 103 /// Allocate memory for all new arrays created by Polly. 104 void allocateNewArrays(BBPair StartExitBlocks); 105 106 /// Preload all memory loads that are invariant. 107 bool preloadInvariantLoads(); 108 109 /// Finalize code generation. 110 /// 111 /// @see BlockGenerator::finalizeSCoP(Scop &S) finalize()112 virtual void finalize() { BlockGen.finalizeSCoP(S); } 113 getExprBuilder()114 IslExprBuilder &getExprBuilder() { return ExprBuilder; } 115 116 /// Get the associated block generator. 117 /// 118 /// @return A reference to the associated block generator. getBlockGenerator()119 BlockGenerator &getBlockGenerator() { return BlockGen; } 120 121 /// Return the parallel subfunctions that have been created. getParallelSubfunctions()122 const ArrayRef<Function *> getParallelSubfunctions() const { 123 return ParallelSubfunctions; 124 } 125 126 protected: 127 Scop &S; 128 PollyIRBuilder &Builder; 129 ScopAnnotator &Annotator; 130 131 IslExprBuilder ExprBuilder; 132 133 /// Maps used by the block and region generator to demote scalars. 134 /// 135 ///@{ 136 137 /// See BlockGenerator::ScalarMap. 138 BlockGenerator::AllocaMapTy ScalarMap; 139 140 /// See BlockGenerator::EscapeMap. 141 BlockGenerator::EscapeUsersAllocaMapTy EscapeMap; 142 143 ///@} 144 145 /// The generator used to copy a basic block. 146 BlockGenerator BlockGen; 147 148 /// The generator used to copy a non-affine region. 149 RegionGenerator RegionGen; 150 151 const DataLayout &DL; 152 LoopInfo &LI; 153 ScalarEvolution &SE; 154 DominatorTree &DT; 155 BasicBlock *StartBlock; 156 157 /// The current iteration of out-of-scop loops 158 /// 159 /// This map provides for a given loop a llvm::Value that contains the current 160 /// loop iteration. 161 MapVector<const Loop *, const SCEV *> OutsideLoopIterations; 162 163 // This maps an isl_id* to the Value* it has in the generated program. For now 164 // on, the only isl_ids that are stored here are the newly calculated loop 165 // ivs. 166 IslExprBuilder::IDToValueTy IDToValue; 167 168 /// A collection of all parallel subfunctions that have been created. 169 SmallVector<Function *, 8> ParallelSubfunctions; 170 171 /// Generate code for a given SCEV* 172 /// 173 /// This function generates code for a given SCEV expression. It generated 174 /// code is emitted at the end of the basic block our Builder currently 175 /// points to and the resulting value is returned. 176 /// 177 /// @param Expr The expression to code generate. 178 Value *generateSCEV(const SCEV *Expr); 179 180 /// A set of Value -> Value remappings to apply when generating new code. 181 /// 182 /// When generating new code for a ScopStmt this map is used to map certain 183 /// llvm::Values to new llvm::Values. 184 ValueMapT ValueMap; 185 186 /// Materialize code for @p Id if it was not done before. 187 /// 188 /// @returns False, iff a problem occurred and the value was not materialized. 189 bool materializeValue(__isl_take isl_id *Id); 190 191 /// Materialize parameters of @p Set. 192 /// 193 /// @returns False, iff a problem occurred and the value was not materialized. 194 bool materializeParameters(__isl_take isl_set *Set); 195 196 /// Materialize all parameters in the current scop. 197 /// 198 /// @returns False, iff a problem occurred and the value was not materialized. 199 bool materializeParameters(); 200 201 // Extract the upper bound of this loop 202 // 203 // The isl code generation can generate arbitrary expressions to check if the 204 // upper bound of a loop is reached, but it provides an option to enforce 205 // 'atomic' upper bounds. An 'atomic upper bound is always of the form 206 // iv <= expr, where expr is an (arbitrary) expression not containing iv. 207 // 208 // This function extracts 'atomic' upper bounds. Polly, in general, requires 209 // atomic upper bounds for the following reasons: 210 // 211 // 1. An atomic upper bound is loop invariant 212 // 213 // It must not be calculated at each loop iteration and can often even be 214 // hoisted out further by the loop invariant code motion. 215 // 216 // 2. OpenMP needs a loop invariant upper bound to calculate the number 217 // of loop iterations. 218 // 219 // 3. With the existing code, upper bounds have been easier to implement. 220 isl::ast_expr getUpperBound(isl::ast_node For, CmpInst::Predicate &Predicate); 221 222 /// Return non-negative number of iterations in case of the following form 223 /// of a loop and -1 otherwise. 224 /// 225 /// for (i = 0; i <= NumIter; i++) { 226 /// loop body; 227 /// } 228 /// 229 /// NumIter is a non-negative integer value. Condition can have 230 /// isl_ast_op_lt type. 231 int getNumberOfIterations(isl::ast_node For); 232 233 /// Compute the values and loops referenced in this subtree. 234 /// 235 /// This function looks at all ScopStmts scheduled below the provided For node 236 /// and finds the llvm::Value[s] and llvm::Loops[s] which are referenced but 237 /// not locally defined. 238 /// 239 /// Values that can be synthesized or that are available as globals are 240 /// considered locally defined. 241 /// 242 /// Loops that contain the scop or that are part of the scop are considered 243 /// locally defined. Loops that are before the scop, but do not contain the 244 /// scop itself are considered not locally defined. 245 /// 246 /// @param For The node defining the subtree. 247 /// @param Values A vector that will be filled with the Values referenced in 248 /// this subtree. 249 /// @param Loops A vector that will be filled with the Loops referenced in 250 /// this subtree. 251 void getReferencesInSubtree(const isl::ast_node &For, 252 SetVector<Value *> &Values, 253 SetVector<const Loop *> &Loops); 254 255 /// Change the llvm::Value(s) used for code generation. 256 /// 257 /// When generating code certain values (e.g., references to induction 258 /// variables or array base pointers) in the original code may be replaced by 259 /// new values. This function allows to (partially) update the set of values 260 /// used. A typical use case for this function is the case when we continue 261 /// code generation in a subfunction/kernel function and need to explicitly 262 /// pass down certain values. 263 /// 264 /// @param NewValues A map that maps certain llvm::Values to new llvm::Values. 265 void updateValues(ValueMapT &NewValues); 266 267 /// Return the most up-to-date version of the llvm::Value for code generation. 268 /// @param Original The Value to check for an up to date version. 269 /// @returns A remapped `Value` from ValueMap, or `Original` if no mapping 270 /// exists. 271 /// @see IslNodeBuilder::updateValues 272 /// @see IslNodeBuilder::ValueMap 273 Value *getLatestValue(Value *Original) const; 274 275 /// Generate code for a marker now. 276 /// 277 /// For mark nodes with an unknown name, we just forward the code generation 278 /// to its child. This is currently the only behavior implemented, as there is 279 /// currently not special handling for marker nodes implemented. 280 /// 281 /// @param Mark The node we generate code for. 282 virtual void createMark(__isl_take isl_ast_node *Marker); 283 284 virtual void createFor(__isl_take isl_ast_node *For); 285 286 /// Set to remember materialized invariant loads. 287 /// 288 /// An invariant load is identified by its pointer (the SCEV) and its type. 289 SmallSet<std::pair<const SCEV *, Type *>, 16> PreloadedPtrs; 290 291 /// Preload the memory access at @p AccessRange with @p Build. 292 /// 293 /// @returns The preloaded value casted to type @p Ty 294 Value *preloadUnconditionally(__isl_take isl_set *AccessRange, 295 isl_ast_build *Build, Instruction *AccInst); 296 297 /// Preload the memory load access @p MA. 298 /// 299 /// If @p MA is not always executed it will be conditionally loaded and 300 /// merged with undef from the same type. Hence, if @p MA is executed only 301 /// under condition C then the preload code will look like this: 302 /// 303 /// MA_preload = undef; 304 /// if (C) 305 /// MA_preload = load MA; 306 /// use MA_preload 307 Value *preloadInvariantLoad(const MemoryAccess &MA, 308 __isl_take isl_set *Domain); 309 310 /// Preload the invariant access equivalence class @p IAClass 311 /// 312 /// This function will preload the representing load from @p IAClass and 313 /// map all members of @p IAClass to that preloaded value, potentially casted 314 /// to the required type. 315 /// 316 /// @returns False, iff a problem occurred and the load was not preloaded. 317 bool preloadInvariantEquivClass(InvariantEquivClassTy &IAClass); 318 319 void createForVector(__isl_take isl_ast_node *For, int VectorWidth); 320 void createForSequential(isl::ast_node For, bool MarkParallel); 321 322 /// Create LLVM-IR that executes a for node thread parallel. 323 /// 324 /// @param For The FOR isl_ast_node for which code is generated. 325 void createForParallel(__isl_take isl_ast_node *For); 326 327 /// Create new access functions for modified memory accesses. 328 /// 329 /// In case the access function of one of the memory references in the Stmt 330 /// has been modified, we generate a new isl_ast_expr that reflects the 331 /// newly modified access function and return a map that maps from the 332 /// individual memory references in the statement (identified by their id) 333 /// to these newly generated ast expressions. 334 /// 335 /// @param Stmt The statement for which to (possibly) generate new access 336 /// functions. 337 /// @param Node The ast node corresponding to the statement for us to extract 338 /// the local schedule from. 339 /// @return A new hash table that contains remappings from memory ids to new 340 /// access expressions. 341 __isl_give isl_id_to_ast_expr * 342 createNewAccesses(ScopStmt *Stmt, __isl_keep isl_ast_node *Node); 343 344 /// Generate LLVM-IR that computes the values of the original induction 345 /// variables in function of the newly generated loop induction variables. 346 /// 347 /// Example: 348 /// 349 /// // Original 350 /// for i 351 /// for j 352 /// S(i) 353 /// 354 /// Schedule: [i,j] -> [i+j, j] 355 /// 356 /// // New 357 /// for c0 358 /// for c1 359 /// S(c0 - c1, c1) 360 /// 361 /// Assuming the original code consists of two loops which are 362 /// transformed according to a schedule [i,j] -> [c0=i+j,c1=j]. The resulting 363 /// ast models the original statement as a call expression where each argument 364 /// is an expression that computes the old induction variables from the new 365 /// ones, ordered such that the first argument computes the value of induction 366 /// variable that was outermost in the original code. 367 /// 368 /// @param Expr The call expression that represents the statement. 369 /// @param Stmt The statement that is called. 370 /// @param LTS The loop to SCEV map in which the mapping from the original 371 /// loop to a SCEV representing the new loop iv is added. This 372 /// mapping does not require an explicit induction variable. 373 /// Instead, we think in terms of an implicit induction variable 374 /// that counts the number of times a loop is executed. For each 375 /// original loop this count, expressed in function of the new 376 /// induction variables, is added to the LTS map. 377 void createSubstitutions(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt, 378 LoopToScevMapT <S); 379 void createSubstitutionsVector(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt, 380 std::vector<LoopToScevMapT> &VLTS, 381 std::vector<Value *> &IVS, 382 __isl_take isl_id *IteratorID); 383 virtual void createIf(__isl_take isl_ast_node *If); 384 void createUserVector(__isl_take isl_ast_node *User, 385 std::vector<Value *> &IVS, 386 __isl_take isl_id *IteratorID, 387 __isl_take isl_union_map *Schedule); 388 virtual void createUser(__isl_take isl_ast_node *User); 389 virtual void createBlock(__isl_take isl_ast_node *Block); 390 391 /// Get the schedule for a given AST node. 392 /// 393 /// This information is used to reason about parallelism of loops or the 394 /// locality of memory accesses under a given schedule. 395 /// 396 /// @param Node The node we want to obtain the schedule for. 397 /// @return Return an isl_union_map that maps from the statements executed 398 /// below this ast node to the scheduling vectors used to enumerate 399 /// them. 400 /// 401 virtual isl::union_map getScheduleForAstNode(const isl::ast_node &Node); 402 403 private: 404 /// Create code for a copy statement. 405 /// 406 /// A copy statement is expected to have one read memory access and one write 407 /// memory access (in this very order). Data is loaded from the location 408 /// described by the read memory access and written to the location described 409 /// by the write memory access. @p NewAccesses contains for each access 410 /// the isl ast expression that describes the location accessed. 411 /// 412 /// @param Stmt The copy statement that contains the accesses. 413 /// @param NewAccesses The hash table that contains remappings from memory 414 /// ids to new access expressions. 415 void generateCopyStmt(ScopStmt *Stmt, 416 __isl_keep isl_id_to_ast_expr *NewAccesses); 417 418 /// Materialize a canonical loop induction variable for `L`, which is a loop 419 /// that is *not* present in the Scop. 420 /// 421 /// Note that this is materialized at the point where the `Builder` is 422 /// currently pointing. 423 /// We also populate the `OutsideLoopIterations` map with `L`s SCEV to keep 424 /// track of the induction variable. 425 /// See [Code generation of induction variables of loops outside Scops] 426 Value *materializeNonScopLoopInductionVariable(const Loop *L); 427 }; 428 429 } // namespace polly 430 431 #endif // POLLY_ISLNODEBUILDER_H 432