Index: include/polly/CodeGen/IslExprBuilder.h =================================================================== --- include/polly/CodeGen/IslExprBuilder.h +++ include/polly/CodeGen/IslExprBuilder.h @@ -116,6 +116,9 @@ /// @return The largest of the two types. llvm::Type *getWidestType(llvm::Type *T1, llvm::Type *T2); + /// @brief Cast @p V to an integer if it is a pointer, otherwise return @p V. + llvm::Value *ensureIntegerType(llvm::Value *V); + /// @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 Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -368,12 +368,6 @@ isa(ICmp->getOperand(1))) return invalid(Context, /*Assert=*/true, &BB, ICmp); - // TODO: FIXME: IslExprBuilder is not capable of producing valid code - // for arbitrary pointer expressions at the moment. Until - // this is fixed we disallow pointer expressions completely. - if (ICmp->getOperand(0)->getType()->isPointerTy()) - return false; - Loop *L = LI->getLoopFor(ICmp->getParent()); const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L); const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L); Index: lib/CodeGen/IslExprBuilder.cpp =================================================================== --- lib/CodeGen/IslExprBuilder.cpp +++ lib/CodeGen/IslExprBuilder.cpp @@ -37,7 +37,7 @@ assert(MaxType->isIntegerTy() && "Unary expressions can only be created for integer types"); - V = create(isl_ast_expr_get_op_arg(Expr, 0)); + V = ensureIntegerType(create(isl_ast_expr_get_op_arg(Expr, 0))); MaxType = getWidestType(MaxType, V->getType()); if (MaxType != V->getType()) @@ -199,65 +199,11 @@ LOp = isl_ast_expr_get_op_arg(Expr, 0); ROp = isl_ast_expr_get_op_arg(Expr, 1); - // Catch the special case ((-) + ) which is for - // isl the same as ( - ). We have to treat it here because - // there is no valid semantics for the (-) expression, hence in - // createOpUnary such an expression will trigger a crash. - // FIXME: The same problem can now be triggered by a subexpression of the LHS, - // however it is much less likely. - if (OpType == isl_ast_op_add && - isl_ast_expr_get_type(LOp) == isl_ast_expr_op && - isl_ast_expr_get_op_type(LOp) == isl_ast_op_minus) { - // Change the binary addition to a substraction. - OpType = isl_ast_op_sub; - - // Extract the unary operand of the LHS. - auto *LOpOp = isl_ast_expr_get_op_arg(LOp, 0); - isl_ast_expr_free(LOp); - - // Swap the unary operand of the LHS and the RHS. - LOp = ROp; - ROp = LOpOp; - } - - LHS = create(LOp); - RHS = create(ROp); - + LHS = ensureIntegerType(create(LOp)); Type *LHSType = LHS->getType(); + RHS = ensureIntegerType(create(ROp)); Type *RHSType = RHS->getType(); - // Handle - - if (LHSType->isPointerTy() && RHSType->isPointerTy()) { - isl_ast_expr_free(Expr); - assert(OpType == isl_ast_op_sub && "Substraction is the only valid binary " - "pointer <-> pointer operation."); - - return Builder.CreatePtrDiff(LHS, RHS); - } - - // Handle +/- and +/- - if (LHSType->isPointerTy() || RHSType->isPointerTy()) { - isl_ast_expr_free(Expr); - - assert((LHSType->isIntegerTy() || RHSType->isIntegerTy()) && - "Arithmetic operations might only performed on one but not two " - "pointer types."); - - if (LHSType->isIntegerTy()) - std::swap(LHS, RHS); - - switch (OpType) { - default: - llvm_unreachable( - "Only additive binary operations are allowed on pointer types."); - case isl_ast_op_sub: - RHS = Builder.CreateNeg(RHS); - // Fall through - case isl_ast_op_add: - return Builder.CreateGEP(LHS, RHS); - } - } - MaxType = getWidestType(LHSType, RHSType); // Take the result into account when calculating the widest type. @@ -647,6 +593,15 @@ return V; } +Value *IslExprBuilder::ensureIntegerType(Value *V) { + Type *VType = V->getType(); + if (VType->isPointerTy()) { + Type *IType = Builder.getIntNTy(DL.getPointerTypeSizeInBits(VType)); + V = Builder.CreatePtrToInt(V, IType); + } + return V; +} + Value *IslExprBuilder::create(__isl_take isl_ast_expr *Expr) { switch (isl_ast_expr_get_type(Expr)) { case isl_ast_expr_error: Index: lib/Support/SCEVValidator.cpp =================================================================== --- lib/Support/SCEVValidator.cpp +++ lib/Support/SCEVValidator.cpp @@ -378,16 +378,8 @@ ValidatorResult visitUnknown(const SCEVUnknown *Expr) { Value *V = Expr->getValue(); - // TODO: FIXME: IslExprBuilder is not capable of producing valid code - // for arbitrary pointer expressions at the moment. Until - // this is fixed we disallow pointer expressions completely. - if (Expr->getType()->isPointerTy()) { - DEBUG(dbgs() << "INVALID: UnknownExpr is a pointer type [FIXME]"); - return ValidatorResult(SCEVType::INVALID); - } - - if (!Expr->getType()->isIntegerTy()) { - DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer"); + if (!(Expr->getType()->isIntegerTy() || Expr->getType()->isPointerTy())) { + DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer type"); return ValidatorResult(SCEVType::INVALID); } Index: test/Isl/CodeGen/20120316-InvalidCast.ll =================================================================== --- test/Isl/CodeGen/20120316-InvalidCast.ll +++ test/Isl/CodeGen/20120316-InvalidCast.ll @@ -1,10 +1,5 @@ ; RUN: opt %loadPolly -S -polly-codegen < %s | FileCheck %s -; TODO: FIXME: IslExprBuilder is not capable of producing valid code -; for arbitrary pointer expressions at the moment. Until -; this is fixed we disallow pointer expressions completely. -; XFAIL: * - ; CHECK: polly.start target datalayout = "e-p:32:32:32-i64:64:64-i32:32:32-i16:16:16-i1:32:32-f64:64:64-f32:32:32-a0:0-n32" Index: test/Isl/CodeGen/MemAccess/different_types.ll =================================================================== --- test/Isl/CodeGen/MemAccess/different_types.ll +++ test/Isl/CodeGen/MemAccess/different_types.ll @@ -10,10 +10,11 @@ ; } ; CHECK: %polly.access.cast.A14 = bitcast float* %A to i32* -; CHECK: %5 = sub nsw i64 99, %polly.indvar11 -; CHECK: %polly.access.A15 = getelementptr i32, i32* %polly.access.cast.A14, i64 %5 -; CHECK: %6 = bitcast i32* %polly.access.A15 to float* -; CHECK: %tmp14_p_scalar_ = load float, float* %6, align 4, !alias.scope !3, !noalias !4 +; CHECK: %6 = sub nsw i64 0, %polly.indvar11 +; CHECK: %7 = add nsw i64 %6, 99 +; CHECK: %polly.access.A15 = getelementptr i32, i32* %polly.access.cast.A14, i64 %7 +; CHECK: %8 = bitcast i32* %polly.access.A15 to float* +; CHECK: %tmp14_p_scalar_ = load float, float* %8, align 4, !alias.scope !3, !noalias !4 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: test/Isl/CodeGen/pointer-type-expressions-2.ll =================================================================== --- test/Isl/CodeGen/pointer-type-expressions-2.ll +++ test/Isl/CodeGen/pointer-type-expressions-2.ll @@ -2,11 +2,6 @@ ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s -check-prefix=CODEGEN target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" -; TODO: FIXME: IslExprBuilder is not capable of producing valid code -; for arbitrary pointer expressions at the moment. Until -; this is fixed we disallow pointer expressions completely. -; XFAIL: * - define void @foo(i8* %start, i8* %end) { entry: %A = alloca i32 @@ -28,7 +23,11 @@ ; Check that we transform this into a pointer difference. -; CODEGEN: %[[r0:[._a-zA-Z0-9]]] = ptrtoint i8* %end to i64 -; CODEGEN: %[[r1:[._a-zA-Z0-9]]] = ptrtoint i8* %start to i64 -; CODEGEN: %[[r2:[._a-zA-Z0-9]]] = sub i64 %[[r0]], %[[r1]] +; CODEGEN: ptrtoint i8* %start to i64 +; CODEGEN: %[[R0:[0-9]*]] = ptrtoint i8* %start to i64 +; CODEGEN: %[[R1:[0-9]*]] = sub nsw i64 0, %[[R0]] +; CODEGEN: %[[R2:[0-9]*]] = ptrtoint i8* %end to i64 +; CODEGEN: %[[R3:[0-9]*]] = add nsw i64 %[[R1]], %[[R2]] +; CODEGEN: %polly.adjust_ub = sub i64 %[[R3]], 1 +; CODEGEN: %polly.loop_cond = icmp slt i64 %polly.indvar, %polly.adjust_ub Index: test/Isl/CodeGen/pointer-type-expressions-3.ll =================================================================== --- /dev/null +++ test/Isl/CodeGen/pointer-type-expressions-3.ll @@ -0,0 +1,38 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-ast -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen -S < %s | FileCheck %s -check-prefix=CODEGEN +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @foo(i32* %start, i32* %end) { +entry: + %A = alloca i32 + br label %body + +body: + %ptr = phi i32* [ %start, %entry ], [ %ptr2, %body ] + %ptr2 = getelementptr inbounds i32, i32* %ptr, i64 1 + %cmp = icmp eq i32* %ptr2, %end + store i32 42, i32* %A + br i1 %cmp, label %exit, label %body + +exit: + ret void +} + +; CHECK: if ((start - end) % 4 == 0) +; CHECK: for (int c0 = 0; c0 < (-start + end) / 4; c0 += 1) +; CHECK: Stmt_body(c0); + +; Check that we transform this into a pointer difference. + +; CODEGEN: ptrtoint i32* %start to i64 +; CODEGEN: ptrtoint i32* %start to i64 +; CODEGEN: %[[R0:[0-9]*]] = ptrtoint i32* %start to i64 +; CODEGEN: %[[R1:[0-9]*]] = sub nsw i64 0, %[[R0]] +; CODEGEN: %[[R2:[0-9]*]] = ptrtoint i32* %end to i64 +; CODEGEN: %[[R3:[0-9]*]] = add nsw i64 %[[R1]], %[[R2]] +; CODEGEN: %[[R4:[_.a-zA-Z0-9]*]] = sdiv exact i64 %[[R3]], 4 + +; CODEGEN: %polly.adjust_ub = sub i64 %[[R4]], 1 +; CODEGEN: %polly.loop_cond = icmp slt i64 %polly.indvar, %polly.adjust_ub + + Index: test/Isl/CodeGen/pointer-type-expressions.ll =================================================================== --- test/Isl/CodeGen/pointer-type-expressions.ll +++ test/Isl/CodeGen/pointer-type-expressions.ll @@ -1,11 +1,6 @@ ; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s -check-prefix=CODEGEN -; TODO: FIXME: IslExprBuilder is not capable of producing valid code -; for arbitrary pointer expressions at the moment. Until -; this is fixed we disallow pointer expressions completely. -; XFAIL: * - ; void f(int a[], int N, float *P) { ; int i; ; for (i = 0; i < N; ++i) @@ -47,6 +42,7 @@ ; CHECK: } ; CODEGEN: %[[R0:[0-9]*]] = bitcast float* %P to i8* +; CODEGEN-NEXT: icmp ule i8* %[[R0]], inttoptr (i64 -1 to i8*) ; CODEGEN: %[[R1:[0-9]*]] = bitcast float* %P to i8* -; CODEGEN-NEXT: icmp ule i8* %[[R1]], inttoptr (i64 -1 to i8*) +; CODEGEN-NEXT: icmp uge i8* %[[R1]], inttoptr (i64 1 to i8*) Index: test/Isl/CodeGen/pointer-type-pointer-type-comparison.ll =================================================================== --- test/Isl/CodeGen/pointer-type-pointer-type-comparison.ll +++ test/Isl/CodeGen/pointer-type-pointer-type-comparison.ll @@ -1,11 +1,6 @@ ; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s -check-prefix=CODEGEN ; -; TODO: FIXME: IslExprBuilder is not capable of producing valid code -; for arbitrary pointer expressions at the moment. Until -; this is fixed we disallow pointer expressions completely. -; XFAIL: * - ; void f(int a[], int N, float *P, float *Q) { ; int i; ; for (i = 0; i < N; ++i) @@ -46,7 +41,13 @@ ; CHECK: Stmt_store(c0); ; CHECK: } -; CODEGEN: %[[Pinc:[_a-zA-Z0-9]+]] = getelementptr float, float* %P, i64 1 -; CODEGEN-NEXT: icmp uge float* %Q, %[[Pinc]] -; CODEGEN: %[[Qinc:[_a-zA-Z0-9]+]] = getelementptr float, float* %Q, i64 1 -; CODEGEN-NEXT: icmp uge float* %P, %[[Qinc]] +; CODEGEN: %[[Pint:[_a-zA-Z0-9]+]] = ptrtoint float* %P to i64 +; CODEGEN-NEXT: %[[Pinc:[_a-zA-Z0-9]+]] = add nsw i64 %[[Pint]], 1 +; CODEGEN-NEXT: %[[Pincvptr:[_a-zA-Z0-9]+]] = inttoptr i64 %[[Pinc]] to i8* +; CODEGEN-NEXT: %[[Qvptr:[_a-zA-Z0-9]+]] = bitcast float* %Q to i8* +; CODEGEN-NEXT: icmp uge i8* %[[Qvptr]], %[[Pincvptr]] +; CODEGEN: %[[Qint:[_a-zA-Z0-9]+]] = ptrtoint float* %Q to i64 +; CODEGEN-NEXT: %[[Qinc:[_a-zA-Z0-9]+]] = add nsw i64 %[[Qint]], 1 +; CODEGEN-NEXT: %[[Qincvptr:[_a-zA-Z0-9]+]] = inttoptr i64 %[[Qinc]] to i8* +; CODEGEN-NEXT: %[[Pvptr:[_a-zA-Z0-9]+]] = bitcast float* %P to i8* +; CODEGEN-NEXT: icmp uge i8* %[[Pvptr]], %[[Qincvptr]] Index: test/ScopInfo/pointer-comparison-no-nsw.ll =================================================================== --- /dev/null +++ test/ScopInfo/pointer-comparison-no-nsw.ll @@ -0,0 +1,40 @@ +; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s +; +; void f(int *A, int *B) { +; while (A != B) { +; *A = *A + 1; +; A++; +; } +; } +; +; CHECK: Assumed Context: +; CHECK-NEXT: [A, B] -> { : exists (e0 = floor((-A + B)/4): 4e0 = -A + B and B >= A) } +; +; CHECK: Domain := +; CHECK: [A, B] -> { Stmt_while_body[i0] : exists (e0 = floor((A - B)/4): 4e0 = A - B and i0 >= 0 and 4i0 <= -1 - A + B and B >= A) }; +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32* %B) { +entry: + br label %entry.split + +entry.split: + store i32 0, i32* %A, align 4 + br i1 true, label %while.cond, label %while.end + +while.cond: ; preds = %while.body, %entry + %A.addr.0 = phi i32* [ %A, %entry.split ], [ %incdec.ptr, %while.body ] + %cmp = icmp eq i32* %A.addr.0, %B + br i1 %cmp, label %while.end, label %while.body + +while.body: ; preds = %while.cond + %tmp = load i32, i32* %A.addr.0, align 4 + %add = add i32 %tmp, 1 + store i32 %add, i32* %A.addr.0, align 4 + %incdec.ptr = getelementptr i32, i32* %A.addr.0, i64 1 + br label %while.cond + +while.end: ; preds = %while.cond + ret void +} Index: test/ScopInfo/pointer-comparison.ll =================================================================== --- /dev/null +++ test/ScopInfo/pointer-comparison.ll @@ -0,0 +1,33 @@ +; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s +; +; void f(int *A, int *B) { +; while (A != B) { +; *A = *A + 1; +; A++; +; } +; } +; +; CHECK: Domain := +; CHECK: [A, B] -> { Stmt_while_body[i0] : exists (e0 = floor((A - B)/4): 4e0 = A - B and i0 >= 0 and 4i0 <= -1 - A + B and B >= A) }; +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32* %B) { +entry: + br label %while.cond + +while.cond: ; preds = %while.body, %entry + %A.addr.0 = phi i32* [ %A, %entry ], [ %incdec.ptr, %while.body ] + %cmp = icmp eq i32* %A.addr.0, %B + br i1 %cmp, label %while.end, label %while.body + +while.body: ; preds = %while.cond + %tmp = load i32, i32* %A.addr.0, align 4 + %add = add nsw i32 %tmp, 1 + store i32 %add, i32* %A.addr.0, align 4 + %incdec.ptr = getelementptr inbounds i32, i32* %A.addr.0, i64 1 + br label %while.cond + +while.end: ; preds = %while.cond + ret void +} Index: test/ScopInfo/pointer-type-expressions.ll =================================================================== --- test/ScopInfo/pointer-type-expressions.ll +++ test/ScopInfo/pointer-type-expressions.ll @@ -1,10 +1,5 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s -; TODO: FIXME: IslExprBuilder is not capable of producing valid code -; for arbitrary pointer expressions at the moment. Until -; this is fixed we disallow pointer expressions completely. -; XFAIL: * - ; void f(int a[], int N, float *P) { ; int i; ; for (i = 0; i < N; ++i)