[DA] Incorrect DA results likely due to mishandling of signed/unsigned comparisons

[amehsan]

The issue was initially reported by @kasuga-fj during a discussion on PR 128782. For the loop in Example 1 (IR at the end) DA reports incorrect results (most notably it reports no dependency between two store instructions). It is easy to show that different variations of this loop have the same problem. See Example 2 for one of the cases.

Example 1:

; for (i = 0; i < 9223372036854775806; i++) {
;   if (i < 2147483640)
;     for (j = 0; j < 2147483640; j++)
;       a[i + j * 4294967296] = 0;
;
;   for (j = 0; j < 2147483640; j++)
;     a[j * 2] = 0;
; }
;

Example 2:

void foo2 (int *a ) {

  unsigned long long i;
  unsigned long long j;

  for (i = 0; i < 9223372036854775806; i++) {
    for (j = 0; j < 2147483640; j++) {
      a[i + j * 4294967296] = 0;
      a[j * 2] = 0;
    }
  }
}

IR for Example 1

define void @f(ptr %a) {
entry:
  br label %loop.i.header

loop.i.header:
  %i = phi i64 [ 0 , %entry ], [ %i.next, %loop.i.latch ]
  br label %loop.j.0.pr

loop.j.0.pr:
  %guard.j.0 = icmp slt i64 %i, 2147483640
  br i1 %guard.j.0, label %loop.j.0, label %loop.j.1

loop.j.0:
  %j.0 = phi i64 [ 0, %loop.j.0.pr ], [ %j.0.next, %loop.j.0 ]
  %val.0 = phi i64 [ %i, %loop.j.0.pr ], [ %val.0.next, %loop.j.0 ]
  %j.0.next = add nsw i64 %j.0, 1
  %idx.0 = getelementptr inbounds i8, ptr %a, i64 %val.0
  store i8 0, ptr %idx.0
  %val.0.next = add nsw i64 %val.0, 4294967296
  %exitcond.j.0 = icmp eq i64 %j.0.next, 2147483640
  br i1 %exitcond.j.0, label %loop.j.1, label %loop.j.0

loop.j.1:
  %j.1 = phi i64 [ 0, %loop.j.0 ], [ 0, %loop.j.0.pr ], [ %j.1.next, %loop.j.1 ]
  %val.1 = phi i64 [ 0, %loop.j.0 ], [ 0, %loop.j.0.pr ], [ %val.1.next, %loop.j.1 ]
  %idx.1 = getelementptr inbounds i8, ptr %a, i64 %val.1
  store i8 0, ptr %idx.1
  %j.1.next = add nsw i64 %j.1, 1
  %val.1.next = add nsw i64 %val.1, 2
  %exitcond.j.1 = icmp eq i64 %j.1.next, 2147483640
  br i1 %exitcond.j.1, label %loop.i.latch, label %loop.j.1

loop.i.latch:
  %i.next = add nsw i64 %i, 1
  %exitcond.i = icmp eq i64 %i.next, 9223372036854775806
  br i1 %exitcond.i, label %exit, label %loop.i.header

exit:
  ret void
}

[llvmbot]

@llvm/issue-subscribers-bug

Author: None (amehsan)

The issue was initially reported by @kasuga-fj during a discussion on [PR 128782](https://github.com//pull/128782). For the loop in Example 1 (IR at the end) DA reports incorrect results (most notably it reports no dependency between two store instructions). It is easy to show that different variations of this loop have the same problem. See Example 2 for one of the cases.

Example 1:

; for (i = 0; i < 9223372036854775806; i++) {
;   if (i < 2147483640)
;     for (j = 0; j < 2147483640; j++)
;       a[i + j * 4294967296] = 0;
;
;   for (j = 0; j < 2147483640; j++)
;     a[j * 2] = 0;
; }
;

Example 2:

void foo2 (int *a ) {

  unsigned long long i;
  unsigned long long j;

  for (i = 0; i < 9223372036854775806; i++) {
    for (j = 0; j < 2147483640; j++) {
      a[i + j * 4294967296] = 0;
      a[j * 2] = 0;
    }
  }
}

IR for Example 1

define void @<!-- -->f(ptr %a) {
entry:
  br label %loop.i.header

loop.i.header:
  %i = phi i64 [ 0 , %entry ], [ %i.next, %loop.i.latch ]
  br label %loop.j.0.pr

loop.j.0.pr:
  %guard.j.0 = icmp slt i64 %i, 2147483640
  br i1 %guard.j.0, label %loop.j.0, label %loop.j.1

loop.j.0:
  %j.0 = phi i64 [ 0, %loop.j.0.pr ], [ %j.0.next, %loop.j.0 ]
  %val.0 = phi i64 [ %i, %loop.j.0.pr ], [ %val.0.next, %loop.j.0 ]
  %j.0.next = add nsw i64 %j.0, 1
  %idx.0 = getelementptr inbounds i8, ptr %a, i64 %val.0
  store i8 0, ptr %idx.0
  %val.0.next = add nsw i64 %val.0, 4294967296
  %exitcond.j.0 = icmp eq i64 %j.0.next, 2147483640
  br i1 %exitcond.j.0, label %loop.j.1, label %loop.j.0

loop.j.1:
  %j.1 = phi i64 [ 0, %loop.j.0 ], [ 0, %loop.j.0.pr ], [ %j.1.next, %loop.j.1 ]
  %val.1 = phi i64 [ 0, %loop.j.0 ], [ 0, %loop.j.0.pr ], [ %val.1.next, %loop.j.1 ]
  %idx.1 = getelementptr inbounds i8, ptr %a, i64 %val.1
  store i8 0, ptr %idx.1
  %j.1.next = add nsw i64 %j.1, 1
  %val.1.next = add nsw i64 %val.1, 2
  %exitcond.j.1 = icmp eq i64 %j.1.next, 2147483640
  br i1 %exitcond.j.1, label %loop.i.latch, label %loop.j.1

loop.i.latch:
  %i.next = add nsw i64 %i, 1
  %exitcond.i = icmp eq i64 %i.next, 9223372036854775806
  br i1 %exitcond.i, label %exit, label %loop.i.header

exit:
  ret void
}

[amehsan]

@kasuga-fj

In example 1 above, you can change the condition of the loop guard to be something different and DA will still produce incorrect results. That helps to see why loop guard is not relevant to this bug in DA.

@1997alireza has looked at these cases. There is a problem with singned/unsigned comparison in different places in the code. We will add the information here soon and we are currently investigating the issue.

[1997alireza]

The bug shows up in DA tests SIV, RDIV, and MIV.

In Example 1, DA reports no dependency between a[i + j * 4294967296] and itself, and none between a[i + j * 4294967296] and a[j * 2], both incorrect. The root cause is a computation in findBoundsALL (used by banerjeeMIVtest) that multiplies the iteration count by another term and overflows.

Example 3:

for (i = 0; i < 9223372036854775806; i++) {
  for (j = 0; j < 2147483640; j++) {
    a[i] = 0;
    a[j] = 0;
  }
}

Here, DA again reports no dependency for a[i] vs itself, and none for a[i] vs a[j].

• For a[i] vs itself: DA uses Strong SIV, where an overflow happens in a multiplication on the loop iteration count. Switching the following comparison in the next line to an unsigned predicate fixes this specific case.

• For a[i] vs a[j]: in symbolicRDIVtest, computing A1N1 also overflows, similar to the previous cases.

[amehsan]

• For a[i] vs itself: DA uses Strong SIV, where an overflow happens in a multiplication on the loop iteration count. Switching the following comparison in the next line to an unsigned predicate fixes this specific case.

Could you explain why switching to unsigned comparison is appropriate fix for an overflow problem? (or maybe I misunderstood your comment?)

[1997alireza]

• For a[i] vs itself: DA uses Strong SIV, where an overflow happens in a multiplication on the loop iteration count. Switching the following comparison in the next line to an unsigned predicate fixes this specific case.

Could you explain why switching to unsigned comparison is appropriate fix for an overflow problem? (or maybe I misunderstood your comment?)

I am not suggesting the unsigned comparison as a solution. In general, we are not sure if the values are positive. But it makes it more clear about the reason of the bug by showing that if we have kept the values for this specific case in unsigned SCEVs, we could not have the overflow problem.

[kasuga-fj]

As far as I can tell, similar bugs (overflow during analysis) are occurring in many parts of DA. Recently I fixed one of them. Probably we should apply the similar fix in other places. The problem is a bit more complicated in these cases because we use SCEV instead of APInt.

• For a[i] vs itself: DA uses Strong SIV, where an overflow happens in a multiplication on the loop iteration count. Switching the following comparison in the next line to an unsigned predicate fixes this specific case.

Hm, considering the fact that we are using the absolute value of Delta and Coef¹, maybe it's okay to use unsigned here...

• For a[i] vs a[j]: in symbolicRDIVtest, computing A1N1 also overflows, similar to the previous cases.

A while ago, I tried to insert an overflow check using ScalarEvolution::willNotOverflow in symbolicRDIVtest, which resulted in almost all tests in SymbolicRDIV.ll failing. Hence, I stopped working on it and have left it as is. Of course, we could handle only the case of SCEVConstant, but doing just that wouldn't make much sense...

Footnotes

1. That aside, the absolute value calculation is probably incorrect, though... ↩