//=- 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<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(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<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;

  /// 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, 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<Value *> &Values,

                              SetVector<const Loop *> &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<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 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 &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);

  void createUserVector(__isl_take isl_ast_node *User,

                        std::vector<Value *> &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