//=- IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST -*- C++ -*-=// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file contains the IslNodeBuilder, a class to translate an isl AST into // a LLVM-IR AST. // //===----------------------------------------------------------------------===// #ifndef POLLY_ISLNODEBUILDER_H #define POLLY_ISLNODEBUILDER_H #include "polly/CodeGen/BlockGenerators.h" #include "polly/CodeGen/IslExprBuilder.h" #include "polly/ScopDetectionDiagnostic.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallSet.h" #include "llvm/IR/InstrTypes.h" #include "isl/ctx.h" #include "isl/isl-noexceptions.h" using namespace llvm; using namespace polly; namespace polly { struct InvariantEquivClassTy; } // namespace polly struct SubtreeReferences { LoopInfo &LI; ScalarEvolution &SE; Scop &S; ValueMapT &GlobalMap; SetVector &Values; SetVector &SCEVs; BlockGenerator &BlockGen; // In case an (optional) parameter space location is provided, parameter space // information is collected as well. isl::space *ParamSpace; }; /// Extract the out-of-scop values and SCEVs referenced from a ScopStmt. /// /// This includes the SCEVUnknowns referenced by the SCEVs used in the /// statement and the base pointers of the memory accesses. For scalar /// statements we force the generation of alloca memory locations and list /// these locations in the set of out-of-scop values as well. /// /// We also collect an isl::space that includes all parameter dimensions /// used in the statement's memory accesses, in case the ParamSpace pointer /// is non-null. /// /// @param Stmt The statement for which to extract the information. /// @param UserPtr A void pointer that can be casted to a /// SubtreeReferences structure. /// @param CreateScalarRefs Should the result include allocas of scalar /// references? void addReferencesFromStmt(const ScopStmt *Stmt, void *UserPtr, bool CreateScalarRefs = true); class IslNodeBuilder { public: IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, Scop &S, BasicBlock *StartBlock) : S(S), Builder(Builder), Annotator(Annotator), ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI, StartBlock), BlockGen(Builder, LI, SE, DT, ScalarMap, EscapeMap, ValueMap, &ExprBuilder, StartBlock), RegionGen(BlockGen), DL(DL), LI(LI), SE(SE), DT(DT), StartBlock(StartBlock) {} virtual ~IslNodeBuilder() = default; void addParameters(__isl_take isl_set *Context); /// Create Values which hold the sizes of the outermost dimension of all /// Fortran arrays in the current scop. /// /// @returns False, if a problem occurred and a Fortran array was not /// materialized. True otherwise. bool materializeFortranArrayOutermostDimension(); /// Generate code that evaluates @p Condition at run-time. /// /// This function is typically called to generate the LLVM-IR for the /// run-time condition of the scop, that verifies that all the optimistic /// assumptions we have taken during scop modeling and transformation /// hold at run-time. /// /// @param Condition The condition to evaluate /// /// @result An llvm::Value that is true if the condition holds and false /// otherwise. Value *createRTC(isl_ast_expr *Condition); void create(__isl_take isl_ast_node *Node); /// Allocate memory for all new arrays created by Polly. void allocateNewArrays(BBPair StartExitBlocks); /// Preload all memory loads that are invariant. bool preloadInvariantLoads(); /// Finalize code generation. /// /// @see BlockGenerator::finalizeSCoP(Scop &S) virtual void finalize() { BlockGen.finalizeSCoP(S); } IslExprBuilder &getExprBuilder() { return ExprBuilder; } /// Get the associated block generator. /// /// @return A reference to the associated block generator. BlockGenerator &getBlockGenerator() { return BlockGen; } /// Return the parallel subfunctions that have been created. const ArrayRef getParallelSubfunctions() const { return ParallelSubfunctions; } protected: Scop &S; PollyIRBuilder &Builder; ScopAnnotator &Annotator; IslExprBuilder ExprBuilder; /// Maps used by the block and region generator to demote scalars. /// ///@{ /// See BlockGenerator::ScalarMap. BlockGenerator::AllocaMapTy ScalarMap; /// See BlockGenerator::EscapeMap. BlockGenerator::EscapeUsersAllocaMapTy EscapeMap; ///@} /// The generator used to copy a basic block. BlockGenerator BlockGen; /// The generator used to copy a non-affine region. RegionGenerator RegionGen; const DataLayout &DL; LoopInfo &LI; ScalarEvolution &SE; DominatorTree &DT; BasicBlock *StartBlock; /// The current iteration of out-of-scop loops /// /// This map provides for a given loop a llvm::Value that contains the current /// loop iteration. MapVector OutsideLoopIterations; // This maps an isl_id* to the Value* it has in the generated program. For now // on, the only isl_ids that are stored here are the newly calculated loop // ivs. IslExprBuilder::IDToValueTy IDToValue; /// A collection of all parallel subfunctions that have been created. SmallVector ParallelSubfunctions; /// Generate code for a given SCEV* /// /// This function generates code for a given SCEV expression. It generated /// code is emitted at the end of the basic block our Builder currently /// points to and the resulting value is returned. /// /// @param Expr The expression to code generate. Value *generateSCEV(const SCEV *Expr); /// A set of Value -> Value remappings to apply when generating new code. /// /// When generating new code for a ScopStmt this map is used to map certain /// llvm::Values to new llvm::Values. ValueMapT ValueMap; /// Materialize code for @p Id if it was not done before. /// /// @returns False, iff a problem occurred and the value was not materialized. bool materializeValue(__isl_take isl_id *Id); /// Materialize parameters of @p Set. /// /// @returns False, iff a problem occurred and the value was not materialized. bool materializeParameters(__isl_take isl_set *Set); /// Materialize all parameters in the current scop. /// /// @returns False, iff a problem occurred and the value was not materialized. bool materializeParameters(); // Extract the upper bound of this loop // // The isl code generation can generate arbitrary expressions to check if the // upper bound of a loop is reached, but it provides an option to enforce // 'atomic' upper bounds. An 'atomic upper bound is always of the form // iv <= expr, where expr is an (arbitrary) expression not containing iv. // // This function extracts 'atomic' upper bounds. Polly, in general, requires // atomic upper bounds for the following reasons: // // 1. An atomic upper bound is loop invariant // // It must not be calculated at each loop iteration and can often even be // hoisted out further by the loop invariant code motion. // // 2. OpenMP needs a loop invariant upper bound to calculate the number // of loop iterations. // // 3. With the existing code, upper bounds have been easier to implement. isl::ast_expr getUpperBound(isl::ast_node For, CmpInst::Predicate &Predicate); /// Return non-negative number of iterations in case of the following form /// of a loop and -1 otherwise. /// /// for (i = 0; i <= NumIter; i++) { /// loop body; /// } /// /// NumIter is a non-negative integer value. Condition can have /// isl_ast_op_lt type. int getNumberOfIterations(isl::ast_node For); /// Compute the values and loops referenced in this subtree. /// /// This function looks at all ScopStmts scheduled below the provided For node /// and finds the llvm::Value[s] and llvm::Loops[s] which are referenced but /// not locally defined. /// /// Values that can be synthesized or that are available as globals are /// considered locally defined. /// /// Loops that contain the scop or that are part of the scop are considered /// locally defined. Loops that are before the scop, but do not contain the /// scop itself are considered not locally defined. /// /// @param For The node defining the subtree. /// @param Values A vector that will be filled with the Values referenced in /// this subtree. /// @param Loops A vector that will be filled with the Loops referenced in /// this subtree. void getReferencesInSubtree(__isl_keep isl_ast_node *For, SetVector &Values, SetVector &Loops); /// Change the llvm::Value(s) used for code generation. /// /// When generating code certain values (e.g., references to induction /// variables or array base pointers) in the original code may be replaced by /// new values. This function allows to (partially) update the set of values /// used. A typical use case for this function is the case when we continue /// code generation in a subfunction/kernel function and need to explicitly /// pass down certain values. /// /// @param NewValues A map that maps certain llvm::Values to new llvm::Values. void updateValues(ValueMapT &NewValues); /// Return the most up-to-date version of the llvm::Value for code generation. /// @param Original The Value to check for an up to date version. /// @returns A remapped `Value` from ValueMap, or `Original` if no mapping /// exists. /// @see IslNodeBuilder::updateValues /// @see IslNodeBuilder::ValueMap Value *getLatestValue(Value *Original) const; /// Generate code for a marker now. /// /// For mark nodes with an unknown name, we just forward the code generation /// to its child. This is currently the only behavior implemented, as there is /// currently not special handling for marker nodes implemented. /// /// @param Mark The node we generate code for. virtual void createMark(__isl_take isl_ast_node *Marker); virtual void createFor(__isl_take isl_ast_node *For); /// Set to remember materialized invariant loads. /// /// An invariant load is identified by its pointer (the SCEV) and its type. SmallSet, 16> PreloadedPtrs; /// Preload the memory access at @p AccessRange with @p Build. /// /// @returns The preloaded value casted to type @p Ty Value *preloadUnconditionally(__isl_take isl_set *AccessRange, isl_ast_build *Build, Instruction *AccInst); /// Preload the memory load access @p MA. /// /// If @p MA is not always executed it will be conditionally loaded and /// merged with undef from the same type. Hence, if @p MA is executed only /// under condition C then the preload code will look like this: /// /// MA_preload = undef; /// if (C) /// MA_preload = load MA; /// use MA_preload Value *preloadInvariantLoad(const MemoryAccess &MA, __isl_take isl_set *Domain); /// Preload the invariant access equivalence class @p IAClass /// /// This function will preload the representing load from @p IAClass and /// map all members of @p IAClass to that preloaded value, potentially casted /// to the required type. /// /// @returns False, iff a problem occurred and the load was not preloaded. bool preloadInvariantEquivClass(InvariantEquivClassTy &IAClass); void createForVector(__isl_take isl_ast_node *For, int VectorWidth); void createForSequential(isl::ast_node For, bool MarkParallel); /// Create LLVM-IR that executes a for node thread parallel. /// /// @param For The FOR isl_ast_node for which code is generated. void createForParallel(__isl_take isl_ast_node *For); /// Create new access functions for modified memory accesses. /// /// In case the access function of one of the memory references in the Stmt /// has been modified, we generate a new isl_ast_expr that reflects the /// newly modified access function and return a map that maps from the /// individual memory references in the statement (identified by their id) /// to these newly generated ast expressions. /// /// @param Stmt The statement for which to (possibly) generate new access /// functions. /// @param Node The ast node corresponding to the statement for us to extract /// the local schedule from. /// @return A new hash table that contains remappings from memory ids to new /// access expressions. __isl_give isl_id_to_ast_expr * createNewAccesses(ScopStmt *Stmt, __isl_keep isl_ast_node *Node); /// Generate LLVM-IR that computes the values of the original induction /// variables in function of the newly generated loop induction variables. /// /// Example: /// /// // Original /// for i /// for j /// S(i) /// /// Schedule: [i,j] -> [i+j, j] /// /// // New /// for c0 /// for c1 /// S(c0 - c1, c1) /// /// Assuming the original code consists of two loops which are /// transformed according to a schedule [i,j] -> [c0=i+j,c1=j]. The resulting /// ast models the original statement as a call expression where each argument /// is an expression that computes the old induction variables from the new /// ones, ordered such that the first argument computes the value of induction /// variable that was outermost in the original code. /// /// @param Expr The call expression that represents the statement. /// @param Stmt The statement that is called. /// @param LTS The loop to SCEV map in which the mapping from the original /// loop to a SCEV representing the new loop iv is added. This /// mapping does not require an explicit induction variable. /// Instead, we think in terms of an implicit induction variable /// that counts the number of times a loop is executed. For each /// original loop this count, expressed in function of the new /// induction variables, is added to the LTS map. void createSubstitutions(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt, LoopToScevMapT <S); void createSubstitutionsVector(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt, std::vector &VLTS, std::vector &IVS, __isl_take isl_id *IteratorID); virtual void createIf(__isl_take isl_ast_node *If); void createUserVector(__isl_take isl_ast_node *User, std::vector &IVS, __isl_take isl_id *IteratorID, __isl_take isl_union_map *Schedule); virtual void createUser(__isl_take isl_ast_node *User); virtual void createBlock(__isl_take isl_ast_node *Block); /// Get the schedule for a given AST node. /// /// This information is used to reason about parallelism of loops or the /// locality of memory accesses under a given schedule. /// /// @param Node The node we want to obtain the schedule for. /// @return Return an isl_union_map that maps from the statements executed /// below this ast node to the scheduling vectors used to enumerate /// them. /// virtual __isl_give isl_union_map * getScheduleForAstNode(__isl_take isl_ast_node *Node); private: /// Create code for a copy statement. /// /// A copy statement is expected to have one read memory access and one write /// memory access (in this very order). Data is loaded from the location /// described by the read memory access and written to the location described /// by the write memory access. @p NewAccesses contains for each access /// the isl ast expression that describes the location accessed. /// /// @param Stmt The copy statement that contains the accesses. /// @param NewAccesses The hash table that contains remappings from memory /// ids to new access expressions. void generateCopyStmt(ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses); /// Materialize a canonical loop induction variable for `L`, which is a loop /// that is *not* present in the Scop. /// /// Note that this is materialized at the point where the `Builder` is /// currently pointing. /// We also populate the `OutsideLoopIterations` map with `L`s SCEV to keep /// track of the induction variable. /// See [Code generation of induction variables of loops outside Scops] Value *materializeNonScopLoopInductionVariable(const Loop *L); }; #endif // POLLY_ISLNODEBUILDER_H