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.

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
IDToScopArrayInfoTy *	IDToSAI = 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
Scop &	S

llvm::Value *	OverflowState
	Flag that will be set if an overflow occurred at runtime.

PollyIRBuilder &	Builder

IDToValueTy &	IDToValue

ValueMapT &	GlobalMap

const llvm::DataLayout &	DL

llvm::ScalarEvolution &	SE

llvm::DominatorTree &	DT

llvm::LoopInfo &	LI

llvm::BasicBlock *	StartBlock

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:

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.

Definition at line 81 of file IslExprBuilder.h.

Member Typedef Documentation

◆ IDToScopArrayInfoTy

typedef llvm::MapVector<isl_id *, const ScopArrayInfo *> polly::IslExprBuilder::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

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.
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.
GlobalMap	A mapping from llvm::Values used in the original scop region to a new set of llvm::Values.
DL	DataLayout for the current Module.
SE	ScalarEvolution analysis for the current function.
DT	DominatorTree analysis for the current function.
LI	LoopInfo analysis for the current function.
StartBlock	The 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 )

Create LLVM-IR for an isl_ast_expr[ession].

Parameters

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

Returns: The llvm::Value* containing the result of the computation.

Definition at line 768 of file IslExprBuilder.cpp.

References createId(), createInt(), createOp(), isl_ast_expr_error, isl_ast_expr_get_type(), isl_ast_expr_id, isl_ast_expr_int, isl_ast_expr_op, and polly::Value.

◆ 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

Expr	The 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 235 of file IslExprBuilder.cpp.

References assert, Builder, create(), createAdd(), polly::RuntimeDebugBuilder::createCPUPrinter(), createMul(), DL, polly::expandCodeFor(), 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

LHS	The left operand.
RHS	The right operand.
Name	The (base) name of the new IR operations.

Returns: A value that represents the result of the addition.

Definition at line 152 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

OpC	The binary operation that should be performed [Add/Sub/Mul].
LHS	The left operand.
RHS	The right operand.
Name	The (base) name of the new IR operations.

Returns: A value that represents the result of the binary operation.

Definition at line 99 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

Definition at line 710 of file IslExprBuilder.cpp.

References assert, Builder, DL, getType(), IDToValue, isl_ast_expr_free(), isl_ast_expr_get_id(), isl_ast_expr_get_type(), isl_ast_expr_id, isl_id_free(), and polly::Value.

Referenced by create().

◆ createInt()

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

private

Definition at line 744 of file IslExprBuilder.cpp.

References polly::APIntFromVal(), assert, Builder, getType(), isl_ast_expr_free(), isl_ast_expr_get_type(), isl_ast_expr_get_val(), isl_ast_expr_int, and polly::Value.

Referenced by create().

◆ createMul()

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

private

Create a multiplication and track overflows if requested.

Parameters

LHS	The left operand.
RHS	The right operand.
Name	The (base) name of the new IR operations.

Returns: A value that represents the result of the multiplication.

Definition at line 160 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 339 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

Definition at line 692 of file IslExprBuilder.cpp.

References assert, createAccessAddress(), isl_ast_expr_free(), 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, and polly::Value.

Referenced by createOp().

◆ createOpBin()

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

private

Definition at line 346 of file IslExprBuilder.cpp.

References assert, Builder, create(), createAdd(), createMul(), createSub(), getType(), getWidestType(), isl_ast_expr_free(), 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_add, isl_ast_op_div, isl_ast_op_fdiv_q, isl_ast_op_mul, isl_ast_op_pdiv_q, isl_ast_op_pdiv_r, isl_ast_op_sub, isl_ast_op_type, isl_ast_op_zdiv_r, Res, and polly::Value.

Referenced by createOp().

◆ createOpBoolean()

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

private

Definition at line 540 of file IslExprBuilder.cpp.

References assert, Builder, create(), isl_ast_expr_free(), isl_ast_expr_get_op_arg(), isl_ast_expr_get_op_type(), isl_ast_expr_get_type(), isl_ast_expr_op, isl_ast_op_and, isl_ast_op_or, isl_ast_op_type, Res, and polly::Value.

Referenced by createOp().

◆ createOpBooleanConditional()

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

private

Definition at line 588 of file IslExprBuilder.cpp.

References assert, Builder, create(), DT, Function, isl_ast_expr_free(), isl_ast_expr_get_op_arg(), isl_ast_expr_get_op_type(), isl_ast_expr_get_type(), isl_ast_expr_op, isl_ast_op_and, isl_ast_op_and_then, isl_ast_op_or_else, isl_ast_op_type, LI, polly::PHI, and polly::Value.

Referenced by createOp().

◆ createOpICmp()

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

private

Definition at line 480 of file IslExprBuilder.cpp.

References assert, Builder, create(), DL, getWidestType(), isl_ast_expr_free(), isl_ast_expr_get_op_arg(), isl_ast_expr_get_op_type(), isl_ast_expr_get_type(), isl_ast_expr_op, isl_ast_op_address_of, isl_ast_op_eq, isl_ast_op_gt, isl_ast_op_type, Res, and polly::Value.

Referenced by createOp().

◆ createOpNAry()

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

private

Definition at line 192 of file IslExprBuilder.cpp.

References assert, Builder, create(), getWidestType(), isl_ast_expr_free(), 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_max, isl_ast_op_min, and polly::Value.

Referenced by createOp().

◆ createOpSelect()

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

private

Definition at line 453 of file IslExprBuilder.cpp.

References assert, Builder, create(), getType(), getWidestType(), isl_ast_expr_free(), isl_ast_expr_get_op_arg(), isl_ast_expr_get_op_type(), isl_ast_op_select, and polly::Value.

Referenced by createOp().

◆ createOpUnary()

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

private

Definition at line 173 of file IslExprBuilder.cpp.

References assert, Builder, create(), createSub(), getType(), getWidestType(), isl_ast_expr_free(), isl_ast_expr_get_op_arg(), isl_ast_expr_get_op_type(), isl_ast_op_minus, and polly::Value.

Referenced by createOp().

◆ createSub()

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

private

Create a subtraction and track overflows if requested.

Parameters

LHS	The left operand.
RHS	The right operand.
Name	The (base) name of the new IR operations.

Returns: A value that represents the result of the subtraction.

Definition at line 156 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 64 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

Expr	The expression for which to find the type.

Returns: The type with which the expression should be computed.

Definition at line 736 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

T1	The first type.
T2	The second type.

Returns: The largest of the two types.

Definition at line 164 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

Expr	The expression to check.

Returns: True if the ast expression is larger than 64 bit.

Definition at line 73 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

NewIDToSAI The 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

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.

Definition at line 49 of file IslExprBuilder.cpp.

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

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

Member Data Documentation

◆ Builder

PollyIRBuilder& polly::IslExprBuilder::Builder

private

Definition at line 202 of file IslExprBuilder.h.

Referenced by createAccessAddress(), createBinOp(), createId(), createInt(), createOpAccess(), createOpBin(), createOpBoolean(), createOpBooleanConditional(), createOpICmp(), createOpNAry(), createOpSelect(), createOpUnary(), getOverflowState(), getType(), IslExprBuilder(), and setTrackOverflow().

◆ DL

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

private

Definition at line 206 of file IslExprBuilder.h.

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

◆ DT

llvm::DominatorTree& polly::IslExprBuilder::DT

private

Definition at line 208 of file IslExprBuilder.h.

Referenced by createOpBooleanConditional().

◆ GlobalMap

ValueMapT& polly::IslExprBuilder::GlobalMap

private

Definition at line 204 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 203 of file IslExprBuilder.h.

Referenced by createId().

◆ LI

llvm::LoopInfo& polly::IslExprBuilder::LI

private

Definition at line 209 of file IslExprBuilder.h.

Referenced by createOpBooleanConditional().

◆ 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 200 of file IslExprBuilder.h.

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

◆ S

Scop& polly::IslExprBuilder::S

private

Definition at line 187 of file IslExprBuilder.h.

◆ SE

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

private

Definition at line 207 of file IslExprBuilder.h.

Referenced by createAccessAddress().

◆ StartBlock

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

private

Definition at line 210 of file IslExprBuilder.h.

Referenced by createAccessAddress().

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

Public Types

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ IDToScopArrayInfoTy

◆ IDToValueTy

Constructor & Destructor Documentation

◆ IslExprBuilder()

Member Function Documentation

◆ create()

◆ createAccessAddress()

◆ createAdd()

◆ createBinOp()

◆ createId()

◆ createInt()

◆ createMul()

◆ createOp()

◆ createOpAccess()

◆ createOpAddressOf()

◆ createOpBin()

◆ createOpBoolean()

◆ createOpBooleanConditional()

◆ createOpICmp()

◆ createOpNAry()

◆ createOpSelect()

◆ createOpUnary()

◆ createSub()

◆ getOverflowState()

◆ getType()

◆ getWidestType()

◆ hasLargeInts()

◆ setIDToSAI()

◆ setTrackOverflow()

Member Data Documentation

◆ Builder

◆ DL

◆ DT

◆ GlobalMap

◆ IDToSAI

◆ IDToValue

◆ LI

◆ OverflowState

◆ S

◆ SE

◆ StartBlock