From 13c5c64b5d6f7eef57821ab2c87ced0c93183f02 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Tue, 29 Jul 2014 21:06:08 +0000 Subject: [PATCH] [Refactor] Expose the IslExprBuilder (missing files) llvm-svn: 214220 --- polly/include/polly/CodeGen/IslExprBuilder.h | 133 +++++++++ polly/lib/CodeGen/IslExprBuilder.cpp | 395 +++++++++++++++++++++++++++ 2 files changed, 528 insertions(+) create mode 100644 polly/include/polly/CodeGen/IslExprBuilder.h create mode 100644 polly/lib/CodeGen/IslExprBuilder.cpp diff --git a/polly/include/polly/CodeGen/IslExprBuilder.h b/polly/include/polly/CodeGen/IslExprBuilder.h new file mode 100644 index 0000000..f8eb6fa --- /dev/null +++ b/polly/include/polly/CodeGen/IslExprBuilder.h @@ -0,0 +1,133 @@ +//===-IslExprBuilder.h - Helper to generate code for isl AST expressions --===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +//===----------------------------------------------------------------------===// + +#ifndef POLLY_ISL_EXPR_BUILDER_H +#define POLLY_ISL_EXPR_BUILDER_H + +#include "polly/CodeGen/IRBuilder.h" + +#include "isl/ast.h" + +#include + +namespace polly { + +/// @brief 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. +/// +/// FIXME: Hardcoding sizes can cause issues: +/// +/// a) Certain run-time checks that we may want to generate can involve the +/// size of the data types the computation is performed on. When code +/// generating these run-time checks to isl_ast_expr[essions], the +/// resulting computation may require more than 64 bit. +/// +/// b) 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. +/// +/// 2) We always flag computations with 'nsw' +/// +/// As isl_ast_expr[essions] assume arbitrary precision, no wrapping should +/// ever occur in the generated LLVM-IR (assuming the data type chosen is large +/// enough). +class IslExprBuilder { +public: + /// @brief 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. + IslExprBuilder(PollyIRBuilder &Builder, + std::map &IDToValue) + : Builder(Builder), IDToValue(IDToValue) {} + + /// @brief 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); + + /// @brief 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); + + /// @brief 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); + +private: + PollyIRBuilder &Builder; + std::map &IDToValue; + + llvm::Value *createOp(__isl_take isl_ast_expr *Expr); + llvm::Value *createOpUnary(__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 *createId(__isl_take isl_ast_expr *Expr); + llvm::Value *createInt(__isl_take isl_ast_expr *Expr); +}; +} + +#endif diff --git a/polly/lib/CodeGen/IslExprBuilder.cpp b/polly/lib/CodeGen/IslExprBuilder.cpp new file mode 100644 index 0000000..6275c14 --- /dev/null +++ b/polly/lib/CodeGen/IslExprBuilder.cpp @@ -0,0 +1,395 @@ +//===------ IslExprBuilder.cpp ----- Code generate isl AST expressions ----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +//===----------------------------------------------------------------------===// + +#include "polly/CodeGen/IslExprBuilder.h" + +#include "polly/Support/GICHelper.h" + +#include "llvm/Support/Debug.h" + +using namespace llvm; +using namespace polly; + +Type *IslExprBuilder::getWidestType(Type *T1, Type *T2) { + assert(isa(T1) && isa(T2)); + + if (T1->getPrimitiveSizeInBits() < T2->getPrimitiveSizeInBits()) + return T2; + else + return T1; +} + +Value *IslExprBuilder::createOpUnary(__isl_take isl_ast_expr *Expr) { + assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_minus && + "Unsupported unary operation"); + + Value *V; + Type *MaxType = getType(Expr); + + V = create(isl_ast_expr_get_op_arg(Expr, 0)); + MaxType = getWidestType(MaxType, V->getType()); + + if (MaxType != V->getType()) + V = Builder.CreateSExt(V, MaxType); + + isl_ast_expr_free(Expr); + return Builder.CreateNSWNeg(V); +} + +Value *IslExprBuilder::createOpNAry(__isl_take isl_ast_expr *Expr) { + assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && + "isl ast expression not of type isl_ast_op"); + assert(isl_ast_expr_get_op_n_arg(Expr) >= 2 && + "We need at least two operands in an n-ary operation"); + + Value *V; + + V = create(isl_ast_expr_get_op_arg(Expr, 0)); + + for (int i = 0; i < isl_ast_expr_get_op_n_arg(Expr); ++i) { + Value *OpV; + OpV = create(isl_ast_expr_get_op_arg(Expr, i)); + + Type *Ty = getWidestType(V->getType(), OpV->getType()); + + if (Ty != OpV->getType()) + OpV = Builder.CreateSExt(OpV, Ty); + + if (Ty != V->getType()) + V = Builder.CreateSExt(V, Ty); + + switch (isl_ast_expr_get_op_type(Expr)) { + default: + llvm_unreachable("This is no n-ary isl ast expression"); + + case isl_ast_op_max: { + Value *Cmp = Builder.CreateICmpSGT(V, OpV); + V = Builder.CreateSelect(Cmp, V, OpV); + continue; + } + case isl_ast_op_min: { + Value *Cmp = Builder.CreateICmpSLT(V, OpV); + V = Builder.CreateSelect(Cmp, V, OpV); + continue; + } + } + } + + // TODO: We can truncate the result, if it fits into a smaller type. This can + // help in cases where we have larger operands (e.g. i67) but the result is + // known to fit into i64. Without the truncation, the larger i67 type may + // force all subsequent operations to be performed on a non-native type. + isl_ast_expr_free(Expr); + return V; +} + +Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) { + Value *LHS, *RHS, *Res; + Type *MaxType; + isl_ast_op_type OpType; + + assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && + "isl ast expression not of type isl_ast_op"); + assert(isl_ast_expr_get_op_n_arg(Expr) == 2 && + "not a binary isl ast expression"); + + OpType = isl_ast_expr_get_op_type(Expr); + + LHS = create(isl_ast_expr_get_op_arg(Expr, 0)); + RHS = create(isl_ast_expr_get_op_arg(Expr, 1)); + + MaxType = LHS->getType(); + MaxType = getWidestType(MaxType, RHS->getType()); + + // Take the result into account when calculating the widest type. + // + // For operations such as '+' the result may require a type larger than + // the type of the individual operands. For other operations such as '/', the + // result type cannot be larger than the type of the individual operand. isl + // does not calculate correct types for these operations and we consequently + // exclude those operations here. + switch (OpType) { + case isl_ast_op_pdiv_q: + case isl_ast_op_pdiv_r: + case isl_ast_op_div: + case isl_ast_op_fdiv_q: + // Do nothing + break; + case isl_ast_op_add: + case isl_ast_op_sub: + case isl_ast_op_mul: + MaxType = getWidestType(MaxType, getType(Expr)); + break; + default: + llvm_unreachable("This is no binary isl ast expression"); + } + + if (MaxType != RHS->getType()) + RHS = Builder.CreateSExt(RHS, MaxType); + + if (MaxType != LHS->getType()) + LHS = Builder.CreateSExt(LHS, MaxType); + + switch (OpType) { + default: + llvm_unreachable("This is no binary isl ast expression"); + case isl_ast_op_add: + Res = Builder.CreateNSWAdd(LHS, RHS); + break; + case isl_ast_op_sub: + Res = Builder.CreateNSWSub(LHS, RHS); + break; + case isl_ast_op_mul: + Res = Builder.CreateNSWMul(LHS, RHS); + break; + case isl_ast_op_div: + case isl_ast_op_pdiv_q: // Dividend is non-negative + Res = Builder.CreateSDiv(LHS, RHS); + break; + case isl_ast_op_fdiv_q: { // Round towards -infty + // TODO: Review code and check that this calculation does not yield + // incorrect overflow in some bordercases. + // + // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d + Value *One = ConstantInt::get(MaxType, 1); + Value *Zero = ConstantInt::get(MaxType, 0); + Value *Sum1 = Builder.CreateSub(LHS, RHS); + Value *Sum2 = Builder.CreateAdd(Sum1, One); + Value *isNegative = Builder.CreateICmpSLT(LHS, Zero); + Value *Dividend = Builder.CreateSelect(isNegative, Sum2, LHS); + Res = Builder.CreateSDiv(Dividend, RHS); + break; + } + case isl_ast_op_pdiv_r: // Dividend is non-negative + Res = Builder.CreateSRem(LHS, RHS); + break; + } + + // TODO: We can truncate the result, if it fits into a smaller type. This can + // help in cases where we have larger operands (e.g. i67) but the result is + // known to fit into i64. Without the truncation, the larger i67 type may + // force all subsequent operations to be performed on a non-native type. + isl_ast_expr_free(Expr); + return Res; +} + +Value *IslExprBuilder::createOpSelect(__isl_take isl_ast_expr *Expr) { + assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_select && + "Unsupported unary isl ast expression"); + Value *LHS, *RHS, *Cond; + Type *MaxType = getType(Expr); + + Cond = create(isl_ast_expr_get_op_arg(Expr, 0)); + + LHS = create(isl_ast_expr_get_op_arg(Expr, 1)); + RHS = create(isl_ast_expr_get_op_arg(Expr, 2)); + + MaxType = getWidestType(MaxType, LHS->getType()); + MaxType = getWidestType(MaxType, RHS->getType()); + + if (MaxType != RHS->getType()) + RHS = Builder.CreateSExt(RHS, MaxType); + + if (MaxType != LHS->getType()) + LHS = Builder.CreateSExt(LHS, MaxType); + + // TODO: Do we want to truncate the result? + isl_ast_expr_free(Expr); + return Builder.CreateSelect(Cond, LHS, RHS); +} + +Value *IslExprBuilder::createOpICmp(__isl_take isl_ast_expr *Expr) { + assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && + "Expected an isl_ast_expr_op expression"); + + Value *LHS, *RHS, *Res; + + LHS = create(isl_ast_expr_get_op_arg(Expr, 0)); + RHS = create(isl_ast_expr_get_op_arg(Expr, 1)); + + Type *MaxType = LHS->getType(); + MaxType = getWidestType(MaxType, RHS->getType()); + + if (MaxType != RHS->getType()) + RHS = Builder.CreateSExt(RHS, MaxType); + + if (MaxType != LHS->getType()) + LHS = Builder.CreateSExt(LHS, MaxType); + + switch (isl_ast_expr_get_op_type(Expr)) { + default: + llvm_unreachable("Unsupported ICmp isl ast expression"); + case isl_ast_op_eq: + Res = Builder.CreateICmpEQ(LHS, RHS); + break; + case isl_ast_op_le: + Res = Builder.CreateICmpSLE(LHS, RHS); + break; + case isl_ast_op_lt: + Res = Builder.CreateICmpSLT(LHS, RHS); + break; + case isl_ast_op_ge: + Res = Builder.CreateICmpSGE(LHS, RHS); + break; + case isl_ast_op_gt: + Res = Builder.CreateICmpSGT(LHS, RHS); + break; + } + + isl_ast_expr_free(Expr); + return Res; +} + +Value *IslExprBuilder::createOpBoolean(__isl_take isl_ast_expr *Expr) { + assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && + "Expected an isl_ast_expr_op expression"); + + Value *LHS, *RHS, *Res; + isl_ast_op_type OpType; + + OpType = isl_ast_expr_get_op_type(Expr); + + assert((OpType == isl_ast_op_and || OpType == isl_ast_op_or) && + "Unsupported isl_ast_op_type"); + + LHS = create(isl_ast_expr_get_op_arg(Expr, 0)); + RHS = create(isl_ast_expr_get_op_arg(Expr, 1)); + + // Even though the isl pretty printer prints the expressions as 'exp && exp' + // or 'exp || exp', we actually code generate the bitwise expressions + // 'exp & exp' or 'exp | exp'. This forces the evaluation of both branches, + // but it is, due to the use of i1 types, otherwise equivalent. The reason + // to go for bitwise operations is, that we assume the reduced control flow + // will outweight the overhead introduced by evaluating unneeded expressions. + // The isl code generation currently does not take advantage of the fact that + // the expression after an '||' or '&&' is in some cases not evaluated. + // Evaluating it anyways does not cause any undefined behaviour. + // + // TODO: Document in isl itself, that the unconditionally evaluating the + // second part of '||' or '&&' expressions is safe. + assert(LHS->getType() == Builder.getInt1Ty() && "Expected i1 type"); + assert(RHS->getType() == Builder.getInt1Ty() && "Expected i1 type"); + + switch (OpType) { + default: + llvm_unreachable("Unsupported boolean expression"); + case isl_ast_op_and: + Res = Builder.CreateAnd(LHS, RHS); + break; + case isl_ast_op_or: + Res = Builder.CreateOr(LHS, RHS); + break; + } + + isl_ast_expr_free(Expr); + return Res; +} + +Value *IslExprBuilder::createOp(__isl_take isl_ast_expr *Expr) { + assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && + "Expression not of type isl_ast_expr_op"); + switch (isl_ast_expr_get_op_type(Expr)) { + case isl_ast_op_error: + case isl_ast_op_cond: + case isl_ast_op_and_then: + case isl_ast_op_or_else: + case isl_ast_op_call: + case isl_ast_op_member: + case isl_ast_op_access: + llvm_unreachable("Unsupported isl ast expression"); + case isl_ast_op_max: + case isl_ast_op_min: + return createOpNAry(Expr); + case isl_ast_op_add: + case isl_ast_op_sub: + case isl_ast_op_mul: + case isl_ast_op_div: + case isl_ast_op_fdiv_q: // Round towards -infty + case isl_ast_op_pdiv_q: // Dividend is non-negative + case isl_ast_op_pdiv_r: // Dividend is non-negative + return createOpBin(Expr); + case isl_ast_op_minus: + return createOpUnary(Expr); + case isl_ast_op_select: + return createOpSelect(Expr); + case isl_ast_op_and: + case isl_ast_op_or: + return createOpBoolean(Expr); + case isl_ast_op_eq: + case isl_ast_op_le: + case isl_ast_op_lt: + case isl_ast_op_ge: + case isl_ast_op_gt: + return createOpICmp(Expr); + } + + llvm_unreachable("Unsupported isl_ast_expr_op kind."); +} + +Value *IslExprBuilder::createId(__isl_take isl_ast_expr *Expr) { + assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_id && + "Expression not of type isl_ast_expr_ident"); + + isl_id *Id; + Value *V; + + Id = isl_ast_expr_get_id(Expr); + + assert(IDToValue.count(Id) && "Identifier not found"); + + V = IDToValue[Id]; + + isl_id_free(Id); + isl_ast_expr_free(Expr); + + return V; +} + +IntegerType *IslExprBuilder::getType(__isl_keep isl_ast_expr *Expr) { + // XXX: We assume i64 is large enough. This is often true, but in general + // incorrect. Also, on 32bit architectures, it would be beneficial to + // use a smaller type. We can and should directly derive this information + // during code generation. + return IntegerType::get(Builder.getContext(), 64); +} + +Value *IslExprBuilder::createInt(__isl_take isl_ast_expr *Expr) { + assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_int && + "Expression not of type isl_ast_expr_int"); + isl_val *Val; + Value *V; + APInt APValue; + IntegerType *T; + + Val = isl_ast_expr_get_val(Expr); + APValue = APIntFromVal(Val); + T = getType(Expr); + APValue = APValue.sextOrSelf(T->getBitWidth()); + V = ConstantInt::get(T, APValue); + + isl_ast_expr_free(Expr); + return V; +} + +Value *IslExprBuilder::create(__isl_take isl_ast_expr *Expr) { + switch (isl_ast_expr_get_type(Expr)) { + case isl_ast_expr_error: + llvm_unreachable("Code generation error"); + case isl_ast_expr_op: + return createOp(Expr); + case isl_ast_expr_id: + return createId(Expr); + case isl_ast_expr_int: + return createInt(Expr); + } + + llvm_unreachable("Unexpected enum value"); +} -- 2.7.4