[Polly][ScopInfo] Add support for wrap-around of integers in unsigned comparisons

[annanay25]

Summary

This is one possible solution to implement wrap-arounds for integers in unsigned icmp operations. For example,

store i32 -1, i32* %A_addr
%0 = load i32, i32* %A_addr
%1 = icmp ult i32 %0, 0

%1 should hold false, because under the assumption of unsigned integers, -1 should wrap around to 2^32-1. However, previously. it was assumed that the MSB (Most Significant Bit - aka the Sign bit) was never set for integers in unsigned operations.

This patch modifies the buildConditionSets function in ScopInfo.cpp to give better information about the integers in these unsigned comparisons.

[annanay25]

List of failing tests:

Failing Tests (12):
    Polly :: Isl/CodeGen/20101103-signmissmatch.ll
    Polly :: Isl/CodeGen/ptrtoint_as_parameter.ll
    Polly :: Isl/CodeGen/two-scops-in-row-invalidate-scevs.ll
    Polly :: ScopInfo/complex_domain_binary_condition.ll
    Polly :: ScopInfo/long-compile-time-alias-analysis.ll
    Polly :: ScopInfo/run-time-check-many-array-disjuncts.ll
    Polly :: ScopInfo/simple_loop_unsigned.ll
    Polly :: ScopInfo/simple_loop_unsigned_2.ll
    Polly :: ScopInfo/simple_loop_unsigned_3.ll
    Polly :: ScopInfo/unsigned-condition.ll
    Polly :: ScopInfo/zero_ext_of_truncate.ll
    Polly :: ScopInfo/zero_ext_of_truncate_2.ll

  Expected Passes    : 885
  Expected Failures  : 11
  Unsupported Tests  : 43
  Unexpected Failures: 12

[annanay25]

Update: isl object handling.

Now-

Failing Tests (8):
    Polly :: Isl/CodeGen/20101103-signmissmatch.ll
    Polly :: Isl/CodeGen/ptrtoint_as_parameter.ll
    Polly :: ScopInfo/long-compile-time-alias-analysis.ll
    Polly :: ScopInfo/run-time-check-many-array-disjuncts.ll
    Polly :: ScopInfo/simple_loop_unsigned.ll
    Polly :: ScopInfo/simple_loop_unsigned_3.ll
    Polly :: ScopInfo/zero_ext_of_truncate.ll
    Polly :: ScopInfo/zero_ext_of_truncate_2.ll

  Expected Passes    : 890
  Expected Failures  : 11
  Unsupported Tests  : 43
  Unexpected Failures: 8

[annanay25]

lib/Analysis/ScopInfo.cpp

1602 ↗

(On Diff #106833)

@Meinersbur ;

One bug that I did not consider. Since LHS can have multiple dimensions, I cannot assume a _unit_ dimension in isl_pw_aff_read_from_str() as the spaces would then be incompatible.

[annanay25]

lib/Analysis/ScopInfo.cpp

1602 ↗

(On Diff #106833)

Example:

isl_pw_aff_dump(LHS)
{ [i0, i1] -> [(28)] }

Crashes with:

polly/lib/External/isl/isl_map.c:3773: spaces don't match

[Meinersbur]

Thanks for the patch. This is what I had in mind. Tests still fail, though.

Can you make a test for all of the 4 cases? Shouldn't be difficult.

How did you make the diff? I cannot directly apply it because the tests are not marked as new files.

lib/Analysis/ScopInfo.cpp

1590 ↗

(On Diff #106833)

[Style] For that many if-cases, you case use a switch instead.

1598 ↗

(On Diff #106833)

[Style] In LLVM's coding style, local variable start with an upper case letter.

[Style] Use inline declarations

1602 ↗

(On Diff #106833)

[Serious] Do not create isl sets from string. You need the correct space: The one one LHS (isl_pw_aff_get_space). To create an pw_aff for 0, there is isl_pw_aff_zero_on_domain.

1613–1628 ↗

(On Diff #106833)

[Suggestion] Extract the common code into a function with parameter(s) for the case.

1622 ↗

(On Diff #106833)

[Style] We usually don have post-line comments, it makes the line longer with an already strict 80 column limit and clang-format doesn't make them look nice.

1678 ↗

(On Diff #106833)

Please avoid whitespace/unrelated changes.

test/ScopInfo/unsigned_wrap_ugt.ll

36 ↗

(On Diff #106833)

[Suggestion] Check for the domain of ifinbounds which should be something like 0 <= %j < 64.

Some comment in the test for what it is supposed to test would be nice.

[annanay25]

Addressed comments.

Currently -

Failing Tests (1):
    Polly :: ScopInfo/simple_loop_unsigned_3.ll

I think there is something fishy with this test case -

The exitcond in the test case is -

%exitcond = icmp ult i64 %sub, 0
br i1 %exitcond, label %bb, label %return

Which should essentially give an empty domain.

[Meinersbur]

simple_loop_unsigned_3.ll has one iteration only: It resembles a do-while loop, therefore is executed exactly once since the exit condition is a tautology.

The correct domain therefore is [N] -> { Stmt_bb[0] } as you code correctly returns.

The code in you summary:

store i32 -1, %0
%1 = icmp ult i32 %0, 0

does not make sense (cannot store to %0 which is not a pointer). Can you revise it?

lib/Analysis/ScopInfo.cpp

1538 ↗

(On Diff #107257)

[Style] We use @param for documenting parameters.

1543 ↗

(On Diff #107257)

[Serious] InvalidDomainMap was updated to use isl C++ bindings. It now should be DenseMap<BasicBlock *, isl::set>. Please update to the latest trunk version of Polly.

[Style] Try to use variable names that are more abstract than what they were used. "SCEV_RHS" is not necessarily the right-hand-side. IsGreaterThan is implementation-specific.
Suggestions:
LHS => TestVal
RHS => UpperBound
IsGreaterThan => IsStrictUpperBound

1546–1547 ↗

(On Diff #107257)

[Style] You can save the assert and use

auto *ICond = cast<ICmpInst>(Condition);

The cast never returns null and checks that with an assert.

1554 ↗

(On Diff #107257)

[Suggestion] It would be slightly less confusing if the comment was using the "ge" operator and the order LHS/RHS are used below: LHS >= 0. Alternatively, you case use isl_pw_aff_le_set.

1563 ↗

(On Diff #107257)

[Suggestion] RHS > LHS or use isl_pw_aff_lt_set

1566 ↗

(On Diff #107257)

[Suggestion] RHS >= LHS or use isl_pw_aff_le_set

1631 ↗

(On Diff #107257)

[Style] Store SE.getSCEVAtScope(ICond->getOperand(0), L) and SE.getSCEVAtScope(ICond->getOperand(1), L) in a variable before the swtich. It is used in all cases.

test/ScopInfo/simple_loop_unsigned.ll

13 ↗

(On Diff #107257)

This is a nice improvement.

[Meinersbur]

simple_loop_unsigned_3.ll has one iteration only: It resembles a do-while loop, therefore is executed exactly once since the exit condition is a tautology.

The correct domain therefore is [N] -> { Stmt_bb[0] } as you code correctly returns.

The code in you summary:

store i32 -1, %0
%1 = icmp ult i32 %0, 0

does not make sense (cannot store to %0 which is not a pointer). Can you revise it?

[annanay25]

Addressed comments.

@Meinersbur Please let me know of any changes to be made.

[Meinersbur]

Thank you.

polly/trunk/lib/Analysis/ScopInfo.cpp

buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
   ConditionSets[0] = setDimensionIds(
       Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion));
 
   isl_pw_aff_free(LHS);
 
   return true;
 }
 
+/// Build condition sets for unsigned ICmpInst(s).
+/// Special handling is required for unsigned operands to ensure that if
+/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
+/// it should wrap around.
+///
+/// @param IsStrictUpperBound holds information on the predicate relation
+/// between TestVal and UpperBound, i.e,
+/// TestVal < UpperBound  OR  TestVal <= UpperBound
+static __isl_give isl_set *
+buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
+                           __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
+                           const SCEV *SCEV_UpperBound,
+                           DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+                           bool IsStrictUpperBound) {
+
+  // Do not take NonNeg assumption on TestVal
+  // as it might have MSB (Sign bit) set.
+  isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false);
+  // Take NonNeg assumption on UpperBound.
+  isl_pw_aff *UpperBound =
+      getPwAff(S, BB, InvalidDomainMap, SCEV_UpperBound, true);
+
+  // 0 <= TestVal
+  isl_set *First =
+      isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space(
+                            isl_pw_aff_get_domain_space(TestVal))),
+                        isl_pw_aff_copy(TestVal));
+
+  isl_set *Second;
+  if (IsStrictUpperBound)
+    // TestVal < UpperBound
+    Second = isl_pw_aff_lt_set(TestVal, UpperBound);
+  else
+    // TestVal <= UpperBound
+    Second = isl_pw_aff_le_set(TestVal, UpperBound);
+
+  isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);
+  ConsequenceCondSet = setDimensionIds(Domain, ConsequenceCondSet);
+  return ConsequenceCondSet;
+}
+
 /// Build the conditions sets for the branch condition @p Condition in
 /// the @p Domain.
 ///
 /// This will fill @p ConditionSets with the conditions under which control
 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
 /// have as many elements as @p TI has successors. If @p TI is nullptr the
 /// context under which @p Condition is true/false will be returned as the
 /// new elements of @p ConditionSets.
assert(ICond &&
            "Condition of exiting branch was neither constant nor ICmp!");
 
     ScalarEvolution &SE = *S.getSE();
     isl_pw_aff *LHS, *RHS;
     // For unsigned comparisons we assumed the signed bit of neither operand
     // to be set. The comparison is equal to a signed comparison under this
     // assumption.
     bool NonNeg = ICond->isUnsigned();
-    LHS = getPwAff(S, BB, InvalidDomainMap,
-                   SE.getSCEVAtScope(ICond->getOperand(0), L), NonNeg);
-    RHS = getPwAff(S, BB, InvalidDomainMap,
-                   SE.getSCEVAtScope(ICond->getOperand(1), L), NonNeg);
+    const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
+               *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
+
+    switch (ICond->getPredicate()) {
+    case ICmpInst::ICMP_ULT:
+      ConsequenceCondSet =
+          buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
+                                     RightOperand, InvalidDomainMap, true);
+      break;
+    case ICmpInst::ICMP_ULE:
+      ConsequenceCondSet =
+          buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
+                                     RightOperand, InvalidDomainMap, false);
+      break;
+    case ICmpInst::ICMP_UGT:
+      ConsequenceCondSet =
+          buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
+                                     LeftOperand, InvalidDomainMap, true);
+      break;
+    case ICmpInst::ICMP_UGE:
+      ConsequenceCondSet =
+          buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
+                                     LeftOperand, InvalidDomainMap, false);
+      break;
+    default:
+      LHS = getPwAff(S, BB, InvalidDomainMap, LeftOperand, NonNeg);
+      RHS = getPwAff(S, BB, InvalidDomainMap, RightOperand, NonNeg);
       ConsequenceCondSet =
           buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
+      break;
+    }
   }
 
   // If no terminator was given we are only looking for parameter constraints
   // under which @p Condition is true/false.
   if (!TI)
     ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
   assert(ConsequenceCondSet);
   ConsequenceCondSet = isl_set_coalesce(

polly/trunk/test/ScopInfo/simple_loop_unsigned.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 
 ; void f(int a[], unsigned N) {
 ;   unsigned i;
 ;   do {
 ;     a[i] = i;
 ;   } while (++i <= N);
 ; }
 
 ; CHECK:      Assumed Context:
 ; CHECK-NEXT: [N] -> {  :  }
 ; CHECK-NEXT: Invalid Context:
-; CHECK-NEXT: [N] -> {  : N < 0 }
+; CHECK-NEXT: [N] -> {  : 1 = 0 }
 ;
 ; CHECK:              Domain :=
-; CHECK-NEXT:             [N] -> { Stmt_bb[i0] : 0 <= i0 < N; Stmt_bb[0] : N <= 0 };
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] : 0 <= i0 < N; Stmt_bb[0] : N = 0 };
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 
 define void @f(i64* nocapture %a, i64 %N) nounwind {
 entry:
   br label %bb
 
 bb:                                               ; preds = %bb, %entry

polly/trunk/test/ScopInfo/simple_loop_unsigned_3.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 
 ; CHECK:      Assumed Context:
 ; CHECK-NEXT: [N] -> { : }
 ;
 ; CHECK:              Domain :=
-; CHECK-NEXT:             [N] -> { Stmt_bb[i0] : 0 < i0 <= 1000 - N; Stmt_bb[0] };
+; CHECK-NEXT:             [N] -> { Stmt_bb[0] };
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 
 define void @f(i64* nocapture %a, i64 %N) nounwind {
 entry:
   br label %bb
 
 bb:                                               ; preds = %bb, %entry

polly/trunk/test/ScopInfo/unsigned_wrap_uge.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Unsigned wrap-around check.
+;
+; for (int i = -1; i < 65 ; i ++ )
+;   if ( 63 >= (unsigned)i )
+;     A[i] = 42;
+
+
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %for
+
+  for:
+  %j = phi i32 [-1, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, 65
+  br i1 %j.cmp, label %body, label %exit
+
+  body:
+  %inbounds = icmp uge i32 63, %j
+  br i1 %inbounds, label %ifinbounds, label %ifoutbounds
+
+  ifinbounds:
+  %A_idx = getelementptr inbounds double, double* %A, i32 %j
+  store double 42.0, double* %A_idx
+  br label %inc
+
+  ifoutbounds:
+  br label %inc
+
+  inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+  exit:
+  br label %return
+
+  return:
+  ret void
+}
+
+
+; CHECK: Region: %for---%return
+; CHECK:            Domain :=
+; CHECK-NEXT:                            { Stmt_ifinbounds[i0] : 0 < i0 <= 64 };
+

polly/trunk/test/ScopInfo/unsigned_wrap_ugt.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Unsigned wrap-around check.
+;
+; for (int i = -1; i < 65 ; i ++ )
+;   if ( 64 > (unsigned)i )
+;     A[i] = 42;
+
+
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %for
+
+  for:
+  %j = phi i32 [-1, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, 65
+  br i1 %j.cmp, label %body, label %exit
+
+  body:
+  %inbounds = icmp ugt i32 64, %j
+  br i1 %inbounds, label %ifinbounds, label %ifoutbounds
+
+  ifinbounds:
+  %A_idx = getelementptr inbounds double, double* %A, i32 %j
+  store double 42.0, double* %A_idx
+  br label %inc
+
+  ifoutbounds:
+  br label %inc
+
+  inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+  exit:
+  br label %return
+
+  return:
+  ret void
+}
+
+
+; CHECK: Region: %for---%return
+; CHECK:            Domain :=
+; CHECK-NEXT:                            { Stmt_ifinbounds[i0] : 0 < i0 <= 64 };
+

polly/trunk/test/ScopInfo/unsigned_wrap_ule.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Unsigned wrap-around check.
+;
+; for (int i = -1; i < 65 ; i ++ )
+;   if ( (unsigned)i <= 63 )
+;     A[i] = 42;
+
+
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %for
+
+  for:
+  %j = phi i32 [-1, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, 65
+  br i1 %j.cmp, label %body, label %exit
+
+  body:
+  %inbounds = icmp ule i32 %j, 63
+  br i1 %inbounds, label %ifinbounds, label %ifoutbounds
+
+  ifinbounds:
+  %A_idx = getelementptr inbounds double, double* %A, i32 %j
+  store double 42.0, double* %A_idx
+  br label %inc
+
+  ifoutbounds:
+  br label %inc
+
+  inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+  exit:
+  br label %return
+
+  return:
+  ret void
+}
+
+
+; CHECK: Region: %for---%return
+; CHECK:            Domain :=
+; CHECK-NEXT:                            { Stmt_ifinbounds[i0] : 0 < i0 <= 64 };
+

polly/trunk/test/ScopInfo/unsigned_wrap_ult.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Unsigned wrap-around check.
+;
+; for (int i = -1; i < 65 ; i ++ )
+;   if ( (unsigned)i < 64 )
+;     A[i] = 42;
+
+
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %for
+
+  for:
+  %j = phi i32 [-1, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, 65
+  br i1 %j.cmp, label %body, label %exit
+
+  body:
+  %inbounds = icmp ult i32 %j, 64
+  br i1 %inbounds, label %ifinbounds, label %ifoutbounds
+
+  ifinbounds:
+  %A_idx = getelementptr inbounds double, double* %A, i32 %j
+  store double 42.0, double* %A_idx
+  br label %inc
+
+  ifoutbounds:
+  br label %inc
+
+  inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+  exit:
+  br label %return
+
+  return:
+  ret void
+}
+
+
+; CHECK: Region: %for---%return
+; CHECK:            Domain :=
+; CHECK-NEXT:                            { Stmt_ifinbounds[i0] : 0 < i0 <= 64 };
+

polly/trunk/test/ScopInfo/zero_ext_of_truncate.ll

 ;
 ; FIXME: The truncated value should be a paramter.
 ; CHECK:         Assumed Context:
 ; CHECK-NEXT:    [N, tmp, M] -> { : }
 ; CHECK-NEXT:    Invalid Context:
 ; CHECK-NEXT:    [N, tmp, M] -> { : N < 0 or (N > 0 and tmp >= 128) or (N > 0 and tmp < 0) or (N > 0 and M < 0) }
 ;
 ; CHECK:         Domain :=
-; CHECK-NEXT:    [N, tmp, M] -> { Stmt_if_then[i0] : M > tmp and 0 <= i0 < N };
+; CHECK-NEXT:    [N, tmp, M] -> { Stmt_if_then[i0] : tmp >= 0 and M > tmp and 0 <= i0 < N };
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i32* noalias %I, i32* noalias %A, i32 %N, i32 %M) {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry

polly/trunk/test/ScopInfo/zero_ext_of_truncate_2.ll

 ;    }
 ;
 ; CHECK:         Assumed Context:
 ; CHECK-NEXT:    [N, tmp] -> { : }
 ; CHECK-NEXT:    Invalid Context:
 ; CHECK-NEXT:    [N, tmp] -> { : N > 0 and (tmp < 0 or tmp >= 2147483648) }
 ;
 ; CHECK:         Domain :=
-; CHECK-NEXT:    [N, tmp] -> { Stmt_if_then[i0] : i0 > tmp and 0 <= i0 < N };
+; CHECK-NEXT:    [N, tmp] -> { Stmt_if_then[i0] : tmp >= 0 and tmp < i0 < N };
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(i64* noalias %I, i32* noalias %A, i32 %N, i32 %M) {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry