include/polly/CodeGen/IslNodeBuilder.h - llvm-project/polly - Git at Google

 //=- 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) {}

   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;

   /// 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);

   /// 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 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::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
	//=- 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) {}

	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;

	/// 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);

	/// 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 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::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