Allow unsigned comparisons

[jdoerfert]

Summary

We will now optimistically assume that the result of an unsigned comparison
is the same as the result of the same comparison interpreted as signed. To
this end we will simply assume that both operands are non-negative.

[Meinersbur]

lib/Analysis/ScopInfo.cpp

1323–1326

I assume that RTCs checks will always be signed therefor this will check whether the MSB is not 1. Could you add a comment for that?

test/ScopInfo/simple_loop_unsigned.ll

3–7

This has no unsigned comparison. Can you make it represent the IR below? Eg.

for (i = 0; (uint64_t)i < (uint64_t)N; ++i)

%i is of type i64, so I suggest to declare i as int64_t

13

Why is this significant for the test case?

test/ScopInfo/simple_loop_unsigned_2.ll

36

Since i is unsigned, why does it have a nsw flag?

[jdoerfert]

lib/Analysis/ScopInfo.cpp

1323–1326

Will do.

test/ScopInfo/simple_loop_unsigned.ll

3–7

Ok.

13

Idk. Most of the check lines are not. Is this a problem now?

test/ScopInfo/simple_loop_unsigned_2.ll

36

that wasn't me (I think). Is it really important if it has this flag or not?

[Meinersbur]

test/ScopInfo/simple_loop_unsigned.ll

13

Not a problem, but makes it harder to understand what's the point of the test.

I could understand why checking the Statement because of its domain, but I don't know why checking the accessed array and its size should be relevant.

test/ScopInfo/simple_loop_unsigned_2.ll

36

This is a brand new test case, so who else could have added it?

The problem I see is that the commented C-code does not accurately represent the IR, hence does a disfavor when trying to understand the code. If you do not intend to keep the C-representation in-sync with the IR, you can just remove it.

[jdoerfert]

test/ScopInfo/simple_loop_unsigned.ll

13

Personally, I think this is overkill to argue about 3 trivial check lines of a test case that has 12 lines of IR. Anyway, you seem to care a lot about it and I will remove them.

test/ScopInfo/simple_loop_unsigned_2.ll

36

This is a brand new test case, so who else could have added it?

Clang? One of our preparation passes? Somebody else and I just copied an existing test case as a basis for this one?

The problem I see is that the commented C-code does not accurately represent the IR, hence does a disfavor when trying to understand the code. If you do not intend to keep the C-representation in-sync with the IR, you can just remove it.

Did you actually compile the code to IR? The nsw you seem to care about is always there. Regarding the mismatch of C and IR, your comment seems rather odd. We surely can just drop all the C code but I think it helps people to understand the structure of the test case, even though it is/cannot always represent the IR exactly. In general I think this is again a discussion that is out of place and if you care about it I would suggest you move it to the mailinglist.

[jdoerfert]

Commited in r267559.

include/polly/ScopDetectionDiagnostic.h

enum RejectReasonKind {
   rrkCondition,
   rrkLastCFG,
   rrkIrreducibleRegion,
 
   // Non-Affinity
   rrkAffFunc,
   rrkUndefCond,
   rrkInvalidCond,
-  rrkUnsignedCond,
   rrkUndefOperand,
   rrkNonAffBranch,
   rrkNoBasePtr,
   rrkUndefBasePtr,
   rrkVariantBasePtr,
   rrkNonAffineAccess,
   rrkDifferentElementSize,
   rrkLastAffFunc,
public:
 
   /// @name RejectReason interface
   //@{
   virtual std::string getMessage() const override;
   //@}
 };
 
 //===----------------------------------------------------------------------===//
-/// @brief Captures an condition on unsigned values
-///
-/// We do not yet allow conditions on unsigend values
-class ReportUnsignedCond : public ReportAffFunc {
-  //===--------------------------------------------------------------------===//
-
-  // The BasicBlock we found the broken condition in.
-  BasicBlock *BB;
-
-public:
-  ReportUnsignedCond(const Instruction *Inst, BasicBlock *BB)
-      : ReportAffFunc(rrkUnsignedCond, Inst), BB(BB) {}
-
-  /// @name LLVM-RTTI interface
-  //@{
-  static bool classof(const RejectReason *RR);
-  //@}
-
-  /// @name RejectReason interface
-  //@{
-  virtual std::string getMessage() const override;
-  virtual std::string getEndUserMessage() const override;
-  //@}
-};
-
-//===----------------------------------------------------------------------===//
 /// @brief Captures an undefined operand.
 class ReportUndefOperand : public ReportAffFunc {
   //===--------------------------------------------------------------------===//
 
   // The BasicBlock we found the undefined operand in.
   BasicBlock *BB;
 
 public:

lib/Analysis/ScopDetection.cpp

static cl::opt<bool> AllowNonAffineSubRegions(
     cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool>
     AllowNonAffineSubLoops("polly-allow-nonaffine-loops",
                            cl::desc("Allow non affine conditions for loops"),
                            cl::Hidden, cl::init(false), cl::ZeroOrMore,
                            cl::cat(PollyCategory));
 
-static cl::opt<bool> AllowUnsigned("polly-allow-unsigned",
-                                   cl::desc("Allow unsigned expressions"),
-                                   cl::Hidden, cl::init(false), cl::ZeroOrMore,
-                                   cl::cat(PollyCategory));
-
 static cl::opt<bool, true>
     TrackFailures("polly-detect-track-failures",
                   cl::desc("Track failure strings in detecting scop regions"),
                   cl::location(PollyTrackFailures), cl::Hidden, cl::ZeroOrMore,
                   cl::init(true), cl::cat(PollyCategory));
 
 static cl::opt<bool> KeepGoing("polly-detect-keep-going",
                                cl::desc("Do not fail on the first error."),
bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
   if (!isa<ICmpInst>(Condition)) {
     if (!IsLoopBranch && AllowNonAffineSubRegions &&
         addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
       return true;
     return invalid<ReportInvalidCond>(Context, /*Assert=*/true, BI, &BB);
   }
 
   ICmpInst *ICmp = cast<ICmpInst>(Condition);
-  // Unsigned comparisons are not allowed. They trigger overflow problems
-  // in the code generation.
-  //
-  // TODO: This is not sufficient and just hides bugs. However it does pretty
-  //       well.
-  if (ICmp->isUnsigned() && !AllowUnsigned)
-    return invalid<ReportUnsignedCond>(Context, /*Assert=*/true, BI, &BB);
 
   // Are both operands of the ICmp affine?
   if (isa<UndefValue>(ICmp->getOperand(0)) ||
       isa<UndefValue>(ICmp->getOperand(1)))
     return invalid<ReportUndefOperand>(Context, /*Assert=*/true, &BB, ICmp);
 
   Loop *L = LI->getLoopFor(ICmp->getParent());
   const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L);

lib/Analysis/ScopDetectionDiagnostic.cpp

return ("Condition in BB '" + BB->getName()).str() +
          "' neither constant nor an icmp instruction";
 }
 
 bool ReportInvalidCond::classof(const RejectReason *RR) {
   return RR->getKind() == rrkInvalidCond;
 }
 
 //===----------------------------------------------------------------------===//
-// ReportUnsignedCond.
-
-std::string ReportUnsignedCond::getMessage() const {
-  return ("Condition in BB '" + BB->getName()).str() +
-         "' performs a comparision on (not yet supported) unsigned integers.";
-}
-
-std::string ReportUnsignedCond::getEndUserMessage() const {
-  return "Unsupported comparision on unsigned integers encountered";
-}
-
-bool ReportUnsignedCond::classof(const RejectReason *RR) {
-  return RR->getKind() == rrkUnsignedCond;
-}
-
-//===----------------------------------------------------------------------===//
 // ReportUndefOperand.
 
 std::string ReportUndefOperand::getMessage() const {
   return ("undef operand in branch at BB: " + BB->getName()).str();
 }
 
 bool ReportUndefOperand::classof(const RejectReason *RR) {
   return RR->getKind() == rrkUndefOperand;

lib/Analysis/ScopInfo.cpp

if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
     auto *ICond = dyn_cast<ICmpInst>(Condition);
     assert(ICond &&
            "Condition of exiting branch was neither constant nor ICmp!");
 
     ScalarEvolution &SE = *S.getSE();
     isl_pw_aff *LHS, *RHS;
     LHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L));
     RHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L));
+
+    if (ICond->isUnsigned()) {
+      auto *BB = Stmt.getEntryBlock();
+      S.recordAssumption(UNSIGNED, isl_pw_aff_nonneg_set(isl_pw_aff_copy(LHS)),
+                         TI->getDebugLoc(), AS_ASSUMPTION, BB);
+      S.recordAssumption(UNSIGNED, isl_pw_aff_nonneg_set(isl_pw_aff_copy(RHS)),
+                         TI->getDebugLoc(), AS_ASSUMPTION, BB);
+    }
+
     ConsequenceCondSet =
         buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
   }
 
   // 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);

test/ScopInfo/simple_loop_unsigned.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+
+; void f(int a[], int N) {
+;   int i;
+;   for (i = 0; i < N; ++i)
+;     a[i] = i;
+; }
+
+; CHECK:      Assumed Context:
+; CHECK-NEXT: [N] -> {  : N >= 0 }
+;
+; CHECK:      Arrays {
+; CHECK-NEXT:     i64 MemRef_a[*]; // Element size 8
+; CHECK-NEXT: }
+;
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_bb
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] : 0 <= i0 < N; Stmt_bb[0] : N <= 0 };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] -> [i0] : i0 < N; Stmt_bb[0] -> [0] : N <= 0 };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] -> MemRef_a[i0] };
+; CHECK-NEXT: }
+
+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
+  %i = phi i64 [ 0, %entry ], [ %i.inc, %bb ]
+  %scevgep = getelementptr inbounds i64, i64* %a, i64 %i
+  store i64 %i, i64* %scevgep
+  %i.inc = add nsw i64 %i, 1
+  %exitcond = icmp uge i64 %i.inc, %N
+  br i1 %exitcond, label %return, label %bb
+
+return:                                           ; preds = %bb, %entry
+  ret void
+}

test/ScopInfo/simple_loop_unsigned_2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+
+; void f(int a[], unsigned N) {
+;   unsigned i;
+;   for (i = N; i > 0; --i)
+;     a[i] = i;
+; }
+
+; CHECK:      Assumed Context:
+; CHECK-NEXT: [N] -> {  : N > 0 }
+;
+; CHECK:      Arrays {
+; CHECK-NEXT:     i64 MemRef_a[*]; // Element size 8
+; CHECK-NEXT: }
+;
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_bb
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] : 0 <= i0 < N; Stmt_bb[0] : N <= 0 };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] -> [i0] : i0 < N; Stmt_bb[0] -> [0] : N <= 0 };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] -> MemRef_a[N - i0] };
+; CHECK-NEXT: }
+
+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
+  %i = phi i64 [ %N, %entry ], [ %i.dec, %bb ]
+  %scevgep = getelementptr inbounds i64, i64* %a, i64 %i
+  store i64 %i, i64* %scevgep
+  %i.dec = add nsw i64 %i, -1
+  %exitcond = icmp ugt i64 %i.dec, 0
+  br i1 %exitcond, label %bb, label %return
+
+return:                                           ; preds = %bb, %entry
+  ret void
+}

test/ScopInfo/simple_loop_unsigned_3.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+
+; void f(int a[], unsigned N) {
+;   unsigned i;
+;   for (i = 1000; N - i < 0; --i)
+;     a[i] = i;
+; }
+
+; CHECK:      Assumed Context:
+; CHECK-NEXT: [N] -> { : }
+; CHECK:      Invalid Context:
+; CHECK-NEXT: [N] -> { : N <= -9223372036854774808 }
+;
+; CHECK:      Arrays {
+; CHECK-NEXT:     i64 MemRef_a[*]; // Element size 8
+; CHECK-NEXT: }
+;
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_bb
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] : 0 < i0 <= 1000 - N; Stmt_bb[0] };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] -> [i0] : 0 < i0 <= 1000 - N; Stmt_bb[0] -> [0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [N] -> { Stmt_bb[i0] -> MemRef_a[1000 - i0] };
+; CHECK-NEXT: }
+
+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
+  %i = phi i64 [ 1000, %entry ], [ %i.dec, %bb ]
+  %scevgep = getelementptr inbounds i64, i64* %a, i64 %i
+  store i64 %i, i64* %scevgep
+  %i.dec = add nsw i64 %i, -1
+  %sub = sub nsw i64 %N, %i
+  %exitcond = icmp ult i64 %sub, 0
+  br i1 %exitcond, label %bb, label %return
+
+return:                                           ; preds = %bb, %entry
+  ret void
+}

test/ScopInfo/unsigned-condition.ll

-; RUN: opt %loadPolly -polly-scops -analyze -polly-allow-unsigned < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 
 ; void f(int a[], int N, unsigned P) {
 ;   int i;
 ;   for (i = 0; i < N; ++i)
 ;     if (P > 42)
 ;       a[i] = i;
 ; }
 
+; The assumed context is the universe because the "signed-unsigned assumption"
+;   [P, N] -> {  : N > 0 and P >= 0 }
+; is implied by the execution domain. Thus if something is executed this
+; assumption will hold.
+
+; CHECK:      Assumed Context:
+; CHECK-NEXT: [P, N] -> {  :  }
+;
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_store
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [P, N] -> { Stmt_store[i0] : P >= 42 and 0 <= i0 < N };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [P, N] -> { Stmt_store[i0] -> [i0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [P, N] -> { Stmt_store[i0] -> MemRef_a[i0] };
+; CHECK-NEXT: }
+
 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, i64 %P) nounwind {
 entry:
   br label %bb
 
 bb:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %bb.backedge ]
   %brcond = icmp uge i64 %P, 42
   br i1 %brcond, label %store, label %bb.backedge
 
 store:
   %scevgep = getelementptr inbounds i64, i64* %a, i64 %i
   store i64 %i, i64* %scevgep
   br label %bb.backedge
 
 bb.backedge:
   %i.inc = add nsw i64 %i, 1
   %exitcond = icmp eq i64 %i.inc, %N
   br i1 %exitcond, label %return, label %bb
 
 return:
   ret void
 }
-
-
-; CHECK:      Assumed Context:
-; CHECK-NEXT: [P, N] -> {  :  }
-;
-; CHECK:      Statements {
-; CHECK-NEXT:     Stmt_store
-; CHECK-NEXT:         Domain :=
-; CHECK-NEXT:             [P, N] -> { Stmt_store[i0] : P >= 42 and 0 <= i0 < N };
-; CHECK-NEXT:         Schedule :=
-; CHECK-NEXT:             [P, N] -> { Stmt_store[i0] -> [i0] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
-; CHECK-NEXT:             [P, N] -> { Stmt_store[i0] -> MemRef_a[i0] };
-; CHECK-NEXT: }