//===-IslExprBuilder.h - Helper to generate code for isl AST expressions --===//

//

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

//

//===----------------------------------------------------------------------===//

//

//===----------------------------------------------------------------------===//

#ifndef POLLY_ISL_EXPR_BUILDER_H

#define POLLY_ISL_EXPR_BUILDER_H

#include "polly/CodeGen/IRBuilder.h"

#include "polly/Support/ScopHelper.h"

#include "isl/isl-noexceptions.h"

namespace llvm {

// Provide PointerLikeTypeTraits for isl_id.

template <> struct PointerLikeTypeTraits<isl_id *> {

public:

  static inline const void *getAsVoidPointer(isl_id *P) { return (void *)P; }

  static inline const Region *getFromVoidPointer(void *P) {

    return (Region *)P;

  }

  enum { NumLowBitsAvailable = 0 };

};

} // namespace llvm

namespace polly {

class ScopArrayInfo;

/// LLVM-IR generator for isl_ast_expr[essions]

///

/// This generator generates LLVM-IR that performs the computation described by

/// an isl_ast_expr[ession].

///

/// Example:

///

///   An isl_ast_expr[ession] can look like this:

///

///     (N + M) + 10

///

///   The IslExprBuilder could create the following LLVM-IR:

///

///     %tmp1 = add nsw i64 %N

///     %tmp2 = add nsw i64 %tmp1, %M

///     %tmp3 = add nsw i64 %tmp2, 10

///

/// The implementation of this class is mostly a mapping from isl_ast_expr

/// constructs to the corresponding LLVM-IR constructs.

///

/// The following decisions may need some explanation:

///

/// 1) Which data-type to choose

///

/// isl_ast_expr[essions] are untyped expressions that assume arbitrary

/// precision integer computations. LLVM-IR instead has fixed size integers.

/// When lowering to LLVM-IR we need to chose both the size of the data type and

/// the sign of the operations we use.

///

/// At the moment, we hardcode i64 bit signed computations. Our experience has

/// shown that 64 bit are generally large enough for the loop bounds that appear

/// in the wild. Signed computations are needed, as loop bounds may become

/// negative.

///

/// It is possible to track overflows that occurred in the generated IR. See the

/// description of @see OverflowState for more information.

///

/// FIXME: Hardcoding sizes can cause issues:

///

///   -  On embedded systems and especially for high-level-synthesis 64 bit

///      computations are very costly.

///

///   The right approach is to compute the minimal necessary bitwidth and

///   signedness for each subexpression during in the isl AST generation and

///   to use this information in our IslAstGenerator. Preliminary patches are

///   available, but have not been committed yet.

///

class IslExprBuilder {

public:

  /// A map from isl_ids to llvm::Values.

  typedef llvm::MapVector<isl_id *, llvm::AssertingVH<llvm::Value>> IDToValueTy;

  typedef llvm::MapVector<isl_id *, const ScopArrayInfo *> IDToScopArrayInfoTy;

  /// A map from isl_ids to ScopArrayInfo objects.

  ///

  /// This map is used to obtain ScopArrayInfo objects for isl_ids which do not

  /// carry a ScopArrayInfo object in their user pointer. This is useful if the

  /// construction of ScopArrayInfo objects happens only after references (e.g.

  /// in an AST) to an isl_id are generated and the user pointer of the isl_id

  /// can not be changed any more.

  ///

  /// This is useful for external users who just use the IslExprBuilder for

  /// code generation.

  IDToScopArrayInfoTy *IDToSAI = nullptr;

  /// Set the isl_id to ScopArrayInfo map.

  ///

  /// @param NewIDToSAI The new isl_id to ScopArrayInfo map to use.

  void setIDToSAI(IDToScopArrayInfoTy *NewIDToSAI) { IDToSAI = NewIDToSAI; }

  /// Construct an IslExprBuilder.

  ///

  /// @param Builder     The IRBuilder used to construct the

  ///                    isl_ast_expr[ession]. The insert location of this

  ///                    IRBuilder defines WHERE the  corresponding LLVM-IR

  ///                    is generated.

  /// @param IDToValue   The isl_ast_expr[ession] may reference parameters or

  ///                    variables (identified by an isl_id). The IDTOValue map

  ///                    specifies the LLVM-IR Values that correspond to these

  ///                    parameters and variables.

  /// @param GlobalMap   A mapping from llvm::Values used in the original scop

  ///                    region to a new set of llvm::Values.

  /// @param DL          DataLayout for the current Module.

  /// @param SE          ScalarEvolution analysis for the current function.

  /// @param DT          DominatorTree analysis for the current function.

  /// @param LI          LoopInfo analysis for the current function.

  /// @param StartBlock The first basic block after the RTC.

  IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue,

                 ValueMapT &GlobalMap, const llvm::DataLayout &DL,

                 llvm::ScalarEvolution &SE, llvm::DominatorTree &DT,

                 llvm::LoopInfo &LI, llvm::BasicBlock *StartBlock);

  /// Create LLVM-IR for an isl_ast_expr[ession].

  ///

  /// @param Expr The ast expression for which we generate LLVM-IR.

  ///

  /// @return The llvm::Value* containing the result of the computation.

  llvm::Value *create(__isl_take isl_ast_expr *Expr);

  /// Return the largest of two types.

  ///

  /// @param T1 The first type.

  /// @param T2 The second type.

  ///

  /// @return The largest of the two types.

  llvm::Type *getWidestType(llvm::Type *T1, llvm::Type *T2);

  /// Return the type with which this expression should be computed.

  ///

  /// The type needs to be large enough to hold all possible input and all

  /// possible output values.

  ///

  /// @param Expr The expression for which to find the type.

  /// @return The type with which the expression should be computed.

  llvm::IntegerType *getType(__isl_keep isl_ast_expr *Expr);

  /// Change if runtime overflows are tracked or not.

  ///

  /// @param Enable Flag to enable/disable the tracking.

  ///

  /// Note that this will reset the tracking state and that tracking is only

  /// allowed if the last tracked expression dominates the current insert point.

  void setTrackOverflow(bool Enable);

  /// Return the current overflow status or nullptr if it is not tracked.

  ///

  /// @return A nullptr if tracking is disabled or otherwise an i1 that has the

  ///         value of "0" if and only if no overflow happened since tracking

  ///         was enabled.

  llvm::Value *getOverflowState() const;

  /// Create LLVM-IR that computes the memory location of an access expression.

  ///

  /// For a given isl_ast_expr[ession] of type isl_ast_op_access this function

  /// creates IR that computes the address the access expression refers to.

  ///

  /// @param Expr The ast expression of type isl_ast_op_access

  ///             for which we generate LLVM-IR.

  ///

  /// @return The llvm::Value* containing the result of the computation.

  llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr);

  /// Check if an @p Expr contains integer constants larger than 64 bit.

  ///

  /// @param Expr The expression to check.

  ///

  /// @return True if the ast expression is larger than 64 bit.

  bool hasLargeInts(isl::ast_expr Expr);

private:

  Scop &S;

  /// Flag that will be set if an overflow occurred at runtime.

  ///

  /// Note that this flag is by default a nullptr and if it is a nullptr

  /// we will not record overflows but simply perform the computations.

  /// The intended usage is as follows:

  ///   - If overflows in [an] expression[s] should be tracked, call

  ///     the setTrackOverflow(true) function.

  ///   - Use create(...) for all expressions that should be checked.

  ///   - Call getOverflowState() to get the value representing the current

  ///     state of the overflow flag.

  ///   - To stop tracking call setTrackOverflow(false).

  llvm::Value *OverflowState;

  PollyIRBuilder &Builder;

  IDToValueTy &IDToValue;

  ValueMapT &GlobalMap;

  const llvm::DataLayout &DL;

  llvm::ScalarEvolution &SE;

  llvm::DominatorTree &DT;

  llvm::LoopInfo &LI;

  llvm::BasicBlock *StartBlock;

  llvm::Value *createOp(__isl_take isl_ast_expr *Expr);

  llvm::Value *createOpUnary(__isl_take isl_ast_expr *Expr);

  llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr);

  llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr);

  llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr);

  llvm::Value *createOpSelect(__isl_take isl_ast_expr *Expr);

  llvm::Value *createOpICmp(__isl_take isl_ast_expr *Expr);

  llvm::Value *createOpBoolean(__isl_take isl_ast_expr *Expr);

  llvm::Value *createOpBooleanConditional(__isl_take isl_ast_expr *Expr);

  llvm::Value *createId(__isl_take isl_ast_expr *Expr);

  llvm::Value *createInt(__isl_take isl_ast_expr *Expr);

  llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr);

  /// Create a binary operation @p Opc and track overflows if requested.

  ///

  /// @param OpC  The binary operation that should be performed [Add/Sub/Mul].

  /// @param LHS  The left operand.

  /// @param RHS  The right operand.

  /// @param Name The (base) name of the new IR operations.

  ///

  /// @return A value that represents the result of the binary operation.

  llvm::Value *createBinOp(llvm::BinaryOperator::BinaryOps Opc,

                           llvm::Value *LHS, llvm::Value *RHS,

                           const llvm::Twine &Name);

  /// Create an addition and track overflows if requested.

  ///

  /// @param LHS  The left operand.

  /// @param RHS  The right operand.

  /// @param Name The (base) name of the new IR operations.

  ///

  /// @return A value that represents the result of the addition.

  llvm::Value *createAdd(llvm::Value *LHS, llvm::Value *RHS,

                         const llvm::Twine &Name = "");

  /// Create a subtraction and track overflows if requested.

  ///

  /// @param LHS  The left operand.

  /// @param RHS  The right operand.

  /// @param Name The (base) name of the new IR operations.

  ///

  /// @return A value that represents the result of the subtraction.

  llvm::Value *createSub(llvm::Value *LHS, llvm::Value *RHS,

                         const llvm::Twine &Name = "");

  /// Create a multiplication and track overflows if requested.

  ///

  /// @param LHS  The left operand.

  /// @param RHS  The right operand.

  /// @param Name The (base) name of the new IR operations.

  ///

  /// @return A value that represents the result of the multiplication.

  llvm::Value *createMul(llvm::Value *LHS, llvm::Value *RHS,

                         const llvm::Twine &Name = "");

};

} // namespace polly

#endif