Polly 20.0.0git
Public Types | Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | List of all members
polly::IslExprBuilder Class Referencefinal

LLVM-IR generator for isl_ast_expr[essions]. More...

#include <IslExprBuilder.h>

Public Types

typedef llvm::MapVector< isl_id *, llvm::AssertingVH< llvm::Value > > IDToValueTy
 A map from isl_ids to llvm::Values.
 
typedef llvm::MapVector< isl_id *, const ScopArrayInfo * > IDToScopArrayInfoTy
 

Public Member Functions

void setIDToSAI (IDToScopArrayInfoTy *NewIDToSAI)
 Set the isl_id to ScopArrayInfo map.
 
 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)
 Construct an IslExprBuilder.
 
void switchGeneratedFunc (llvm::Function *GenFn, llvm::DominatorTree *GenDT, llvm::LoopInfo *GenLI, llvm::ScalarEvolution *GenSE)
 Change the function that code is emitted into.
 
llvm::Value * create (__isl_take isl_ast_expr *Expr)
 Create LLVM-IR for an isl_ast_expr[ession].
 
llvm::Type * getWidestType (llvm::Type *T1, llvm::Type *T2)
 Return the largest of two types.
 
llvm::IntegerType * getType (__isl_keep isl_ast_expr *Expr)
 Return the type with which this expression should be computed.
 
void setTrackOverflow (bool Enable)
 Change if runtime overflows are tracked or not.
 
llvm::Value * getOverflowState () const
 Return the current overflow status or nullptr if it is not tracked.
 
std::pair< llvm::Value *, llvm::Type * > createAccessAddress (__isl_take isl_ast_expr *Expr)
 Create LLVM-IR that computes the memory location of an access expression.
 
bool hasLargeInts (isl::ast_expr Expr)
 Check if an Expr contains integer constants larger than 64 bit.
 

Public Attributes

IDToScopArrayInfoTyIDToSAI = nullptr
 A map from isl_ids to ScopArrayInfo objects.
 

Private Member Functions

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)
 
llvm::Value * createBinOp (llvm::BinaryOperator::BinaryOps Opc, llvm::Value *LHS, llvm::Value *RHS, const llvm::Twine &Name)
 Create a binary operation Opc and track overflows if requested.
 
llvm::Value * createAdd (llvm::Value *LHS, llvm::Value *RHS, const llvm::Twine &Name="")
 Create an addition and track overflows if requested.
 
llvm::Value * createSub (llvm::Value *LHS, llvm::Value *RHS, const llvm::Twine &Name="")
 Create a subtraction and track overflows if requested.
 
llvm::Value * createMul (llvm::Value *LHS, llvm::Value *RHS, const llvm::Twine &Name="")
 Create a multiplication and track overflows if requested.
 

Private Attributes

ScopS
 
llvm::Value * OverflowState
 Flag that will be set if an overflow occurred at runtime.
 
PollyIRBuilderBuilder
 
IDToValueTyIDToValue
 
ValueMapTGlobalMap
 
const llvm::DataLayout & DL
 
llvm::ScalarEvolution & SE
 
llvm::BasicBlock * StartBlock
 
llvm::DominatorTree * GenDT
 Relates to the region where the code is emitted into.
 
llvm::LoopInfo * GenLI
 
llvm::ScalarEvolution * GenSE
 

Detailed Description

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 also
OverflowState for more information.

FIXME: Hardcoding sizes can cause issues:

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.

Definition at line 81 of file IslExprBuilder.h.

Member Typedef Documentation

◆ IDToScopArrayInfoTy

Definition at line 86 of file IslExprBuilder.h.

◆ IDToValueTy

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

A map from isl_ids to llvm::Values.

Definition at line 84 of file IslExprBuilder.h.

Constructor & Destructor Documentation

◆ IslExprBuilder()

IslExprBuilder::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 
)

Construct an IslExprBuilder.

Parameters
BuilderThe IRBuilder used to construct the isl_ast_expr[ession]. The insert location of this IRBuilder defines WHERE the corresponding LLVM-IR is generated.
IDToValueThe 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.
GlobalMapA mapping from llvm::Values used in the original scop region to a new set of llvm::Values.
DLDataLayout for the current Module.
SEScalarEvolution analysis for the current function.
DTDominatorTree analysis for the current function.
LILoopInfo analysis for the current function.
StartBlockThe first basic block after the RTC.

Definition at line 39 of file IslExprBuilder.cpp.

References Builder, OT_ALWAYS, OTMode(), and OverflowState.

Member Function Documentation

◆ create()

Value * IslExprBuilder::create ( __isl_take isl_ast_expr Expr)

◆ createAccessAddress()

std::pair< Value *, Type * > IslExprBuilder::createAccessAddress ( __isl_take isl_ast_expr Expr)

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.

Parameters
ExprThe ast expression of type isl_ast_op_access for which we generate LLVM-IR.
Returns
A pair of the llvm::Value* containing the result of the computation and the llvm::Type* it points to.

Definition at line 248 of file IslExprBuilder.cpp.

References assert, Builder, create(), createAdd(), polly::RuntimeDebugBuilder::createCPUPrinter(), createMul(), DL, polly::expandCodeFor(), GenSE, polly::ScopArrayInfo::getBasePtr(), polly::ScopArrayInfo::getDimensionSize(), polly::ScopArrayInfo::getElementType(), polly::ScopArrayInfo::getFromId(), getWidestType(), GlobalMap, IDToSAI, isl_ast_expr_free(), isl_ast_expr_get_id(), isl_ast_expr_get_op_arg(), isl_ast_expr_get_op_n_arg(), isl_ast_expr_get_op_type(), isl_ast_expr_get_type(), isl_ast_expr_op, isl_ast_op_access, isl_id_free(), isl_id_get_name(), isl::manage(), PollyDebugPrinting, SE, StartBlock, and polly::Value.

Referenced by createOpAccess(), createOpAddressOf(), and polly::IslNodeBuilder::generateCopyStmt().

◆ createAdd()

Value * IslExprBuilder::createAdd ( llvm::Value *  LHS,
llvm::Value *  RHS,
const llvm::Twine &  Name = "" 
)
private

Create an addition and track overflows if requested.

Parameters
LHSThe left operand.
RHSThe right operand.
NameThe (base) name of the new IR operations.
Returns
A value that represents the result of the addition.

Definition at line 165 of file IslExprBuilder.cpp.

References createBinOp(), and polly::Value.

Referenced by createAccessAddress(), and createOpBin().

◆ createBinOp()

Value * IslExprBuilder::createBinOp ( llvm::BinaryOperator::BinaryOps  Opc,
llvm::Value *  LHS,
llvm::Value *  RHS,
const llvm::Twine &  Name 
)
private

Create a binary operation Opc and track overflows if requested.

Parameters
OpCThe binary operation that should be performed [Add/Sub/Mul].
LHSThe left operand.
RHSThe right operand.
NameThe (base) name of the new IR operations.
Returns
A value that represents the result of the binary operation.

Definition at line 112 of file IslExprBuilder.cpp.

References assert, Builder, Function, M(), Module, OT_ALWAYS, OTMode(), OverflowState, and polly::Value.

Referenced by createAdd(), createMul(), and createSub().

◆ createId()

Value * IslExprBuilder::createId ( __isl_take isl_ast_expr Expr)
private

◆ createInt()

Value * IslExprBuilder::createInt ( __isl_take isl_ast_expr Expr)
private

◆ createMul()

Value * IslExprBuilder::createMul ( llvm::Value *  LHS,
llvm::Value *  RHS,
const llvm::Twine &  Name = "" 
)
private

Create a multiplication and track overflows if requested.

Parameters
LHSThe left operand.
RHSThe right operand.
NameThe (base) name of the new IR operations.
Returns
A value that represents the result of the multiplication.

Definition at line 173 of file IslExprBuilder.cpp.

References createBinOp(), and polly::Value.

Referenced by createAccessAddress(), and createOpBin().

◆ createOp()

Value * IslExprBuilder::createOp ( __isl_take isl_ast_expr Expr)
private

◆ createOpAccess()

Value * IslExprBuilder::createOpAccess ( __isl_take isl_ast_expr Expr)
private

Definition at line 350 of file IslExprBuilder.cpp.

References assert, Builder, createAccessAddress(), and polly::Value.

Referenced by createOp().

◆ createOpAddressOf()

Value * IslExprBuilder::createOpAddressOf ( __isl_take isl_ast_expr Expr)
private

◆ createOpBin()

Value * IslExprBuilder::createOpBin ( __isl_take isl_ast_expr Expr)
private

◆ createOpBoolean()

Value * IslExprBuilder::createOpBoolean ( __isl_take isl_ast_expr Expr)
private

◆ createOpBooleanConditional()

Value * IslExprBuilder::createOpBooleanConditional ( __isl_take isl_ast_expr Expr)
private

◆ createOpICmp()

Value * IslExprBuilder::createOpICmp ( __isl_take isl_ast_expr Expr)
private

◆ createOpNAry()

Value * IslExprBuilder::createOpNAry ( __isl_take isl_ast_expr Expr)
private

◆ createOpSelect()

Value * IslExprBuilder::createOpSelect ( __isl_take isl_ast_expr Expr)
private

◆ createOpUnary()

Value * IslExprBuilder::createOpUnary ( __isl_take isl_ast_expr Expr)
private

◆ createSub()

Value * IslExprBuilder::createSub ( llvm::Value *  LHS,
llvm::Value *  RHS,
const llvm::Twine &  Name = "" 
)
private

Create a subtraction and track overflows if requested.

Parameters
LHSThe left operand.
RHSThe right operand.
NameThe (base) name of the new IR operations.
Returns
A value that represents the result of the subtraction.

Definition at line 169 of file IslExprBuilder.cpp.

References createBinOp(), and polly::Value.

Referenced by createOpBin(), and createOpUnary().

◆ getOverflowState()

Value * IslExprBuilder::getOverflowState ( ) const

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

Returns
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.

Definition at line 77 of file IslExprBuilder.cpp.

References Builder, OT_NEVER, OTMode(), OverflowState, and polly::Value.

Referenced by polly::IslNodeBuilder::createRTC(), and polly::IslNodeBuilder::preloadInvariantLoad().

◆ getType()

IntegerType * IslExprBuilder::getType ( __isl_keep isl_ast_expr Expr)

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.

Parameters
ExprThe expression for which to find the type.
Returns
The type with which the expression should be computed.

Definition at line 747 of file IslExprBuilder.cpp.

References Builder.

Referenced by polly::IslNodeBuilder::createForParallel(), polly::IslNodeBuilder::createForSequential(), createId(), createInt(), createOpBin(), createOpSelect(), and createOpUnary().

◆ getWidestType()

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

Return the largest of two types.

Parameters
T1The first type.
T2The second type.
Returns
The largest of the two types.

Definition at line 177 of file IslExprBuilder.cpp.

References assert.

Referenced by createAccessAddress(), polly::IslNodeBuilder::createForParallel(), polly::IslNodeBuilder::createForSequential(), createOpBin(), createOpICmp(), createOpNAry(), createOpSelect(), and createOpUnary().

◆ hasLargeInts()

bool IslExprBuilder::hasLargeInts ( isl::ast_expr  Expr)

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

Parameters
ExprThe expression to check.
Returns
True if the ast expression is larger than 64 bit.

Definition at line 86 of file IslExprBuilder.cpp.

References polly::APIntFromVal(), assert, isl::ast_expr::get(), isl::ast_expr::get_op_arg(), isl::ast_expr::get_val(), hasLargeInts(), isl_ast_expr_get_op_n_arg(), isl_ast_expr_get_type(), isl_ast_expr_id, isl_ast_expr_int, and isl_ast_expr_op.

Referenced by polly::IslNodeBuilder::createRTC(), and hasLargeInts().

◆ setIDToSAI()

void polly::IslExprBuilder::setIDToSAI ( IDToScopArrayInfoTy NewIDToSAI)
inline

Set the isl_id to ScopArrayInfo map.

Parameters
NewIDToSAIThe new isl_id to ScopArrayInfo map to use.

Definition at line 103 of file IslExprBuilder.h.

References IDToSAI.

◆ setTrackOverflow()

void IslExprBuilder::setTrackOverflow ( bool  Enable)

Change if runtime overflows are tracked or not.

Parameters
EnableFlag 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.

Definition at line 62 of file IslExprBuilder.cpp.

References Builder, OT_REQUEST, OTMode(), and OverflowState.

Referenced by polly::IslNodeBuilder::createRTC(), and polly::IslNodeBuilder::preloadInvariantLoad().

◆ switchGeneratedFunc()

void IslExprBuilder::switchGeneratedFunc ( llvm::Function *  GenFn,
llvm::DominatorTree *  GenDT,
llvm::LoopInfo *  GenLI,
llvm::ScalarEvolution *  GenSE 
)

Change the function that code is emitted into.

Definition at line 50 of file IslExprBuilder.cpp.

References assert, GenDT, GenLI, and GenSE.

Referenced by polly::IslNodeBuilder::createForParallel().

Member Data Documentation

◆ Builder

PollyIRBuilder& polly::IslExprBuilder::Builder
private

◆ DL

const llvm::DataLayout& polly::IslExprBuilder::DL
private

Definition at line 210 of file IslExprBuilder.h.

Referenced by createAccessAddress(), createId(), and createOpICmp().

◆ GenDT

llvm::DominatorTree* polly::IslExprBuilder::GenDT
private

Relates to the region where the code is emitted into.

Definition at line 216 of file IslExprBuilder.h.

Referenced by createOpBooleanConditional(), and switchGeneratedFunc().

◆ GenLI

llvm::LoopInfo* polly::IslExprBuilder::GenLI
private

Definition at line 217 of file IslExprBuilder.h.

Referenced by createOpBooleanConditional(), and switchGeneratedFunc().

◆ GenSE

llvm::ScalarEvolution* polly::IslExprBuilder::GenSE
private

Definition at line 218 of file IslExprBuilder.h.

Referenced by createAccessAddress(), and switchGeneratedFunc().

◆ GlobalMap

ValueMapT& polly::IslExprBuilder::GlobalMap
private

Definition at line 208 of file IslExprBuilder.h.

Referenced by createAccessAddress().

◆ IDToSAI

IDToScopArrayInfoTy* polly::IslExprBuilder::IDToSAI = nullptr

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.

Definition at line 98 of file IslExprBuilder.h.

Referenced by createAccessAddress(), and setIDToSAI().

◆ IDToValue

IDToValueTy& polly::IslExprBuilder::IDToValue
private

Definition at line 207 of file IslExprBuilder.h.

Referenced by createId().

◆ OverflowState

llvm::Value* polly::IslExprBuilder::OverflowState
private

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).

Definition at line 204 of file IslExprBuilder.h.

Referenced by createBinOp(), getOverflowState(), IslExprBuilder(), and setTrackOverflow().

◆ S

Scop& polly::IslExprBuilder::S
private

Definition at line 191 of file IslExprBuilder.h.

◆ SE

llvm::ScalarEvolution& polly::IslExprBuilder::SE
private

Definition at line 211 of file IslExprBuilder.h.

Referenced by createAccessAddress().

◆ StartBlock

llvm::BasicBlock* polly::IslExprBuilder::StartBlock
private

Definition at line 212 of file IslExprBuilder.h.

Referenced by createAccessAddress().


The documentation for this class was generated from the following files: