EIC code displayed by LXR master/​include/​polly/​CodeGen/​IslNodeBuilder.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:48:11

 //=- 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"
 
 namespace polly {
 using llvm::LoopInfo;
 using llvm::SmallSet;
 
 struct InvariantEquivClassTy;
 
 struct SubtreeReferences {
   LoopInfo &LI;
   ScalarEvolution &SE;
   Scop &S;
   ValueMapT &GlobalMap;
   SetVector<Value *> &Values;
   SetVector<const SCEV *> &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(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), GenDT(&DT), GenLI(&LI), GenSE(&SE) {}
 
   virtual ~IslNodeBuilder() = default;
 
   void addParameters(__isl_take isl_set *Context);
 
   /// 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<Function *> 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;
 
   /// Relates to the region where the code is emitted into.
   /// @{
   DominatorTree *GenDT;
   LoopInfo *GenLI;
   ScalarEvolution *GenSE;
   /// @}
 
   /// 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<const Loop *, const SCEV *> 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<Function *, 8> 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 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 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(const isl::ast_node &For,
                               SetVector<Value *> &Values,
                               SetVector<const Loop *> &Loops);
 
   /// 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<std::pair<const SCEV *, Type *>, 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 createForSequential(isl::ast_node_for 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 &LTS);
   void createSubstitutionsVector(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt,
                                  std::vector<LoopToScevMapT> &VLTS,
                                  std::vector<Value *> &IVS,
                                  __isl_take isl_id *IteratorID);
   virtual void createIf(__isl_take isl_ast_node *If);
   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::union_map getScheduleForAstNode(const 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);
 };
 
 } // namespace polly
 
 #endif // POLLY_ISLNODEBUILDER_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team