[Delinearization] Incorrect nsw/nuw flags

[kasuga-fj]

Consider the following silly IR:

; void f(char *a, unsigned long long d) {
;   if (d == UINT64_MAX)
;     for (unsigned long long i = 0; i != d; i++)
;       a[i * (d + 1)] = 42;
; }
define void @f(ptr %a, i64 %d) {
entry:
  %guard = icmp eq i64 %d, -1
  br i1 %guard, label %loop.preheader, label %exit

loop.preheader:
  %stride = add nsw i64 %d, 1  ; since %d is -1, %stride is 0
  br label %loop

loop:
  %i = phi i64 [ 0, %loop.preheader ], [ %i.next, %loop ]
  %offset = phi i64 [ 0, %loop.preheader ], [ %offset.next, %loop ]
  %idx = getelementptr inbounds i8, ptr %a, i64 %offset
  store i8 42, ptr %idx
  %i.next = add nuw i64 %i, 1
  %offset.next = add nsw nuw i64 %offset, %stride
  %cond = icmp eq i64 %i.next, %d
  br i1 %cond, label %exit, label %loop

exit:
  ret void
}

Running delinearization on this IR produces the following output (godbolt):

Delinearization on function f:

Inst:  %idx = getelementptr inbounds i8, ptr %a, i64 %offset
In Loop with Header: loop
AccessFunction: 0
failed to delinearize

Inst:  store i8 42, ptr %idx, align 1
In Loop with Header: loop
AccessFunction: {0,+,(1 + %d)}<nuw><nsw><%loop>
Base offset: %a
ArrayDecl[UnknownSize][%d] with elements of 1 bytes.
ArrayRef[{0,+,1}<nuw><nsw><%loop>][{0,+,1}<nuw><nsw><%loop>]

Since the back-edge taken count is 2^64 - 1, {0,+,1}<nuw><nsw><%loop> seems incorrect; we should drop the nsw.

The root cause appears to be that SCEVDivision propagates the no-wrap flags from the numerator to the quotient, which doesn't seem to hold in general.

llvm-project/llvm/lib/Analysis/ScalarEvolutionDivision.cpp

Lines 144 to 148 in f7c6c7c

	Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(),
	Numerator->getNoWrapFlags());
	Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(),
	Numerator->getNoWrapFlags());
	}

[kasuga-fj]

@nikic Sorry to bother you, but may I ask: is this a bug, or am I misunderstanding something?

[nikic]

@kasuga-fj I agree that it's a bug.

[kasuga-fj]

@nikic Thanks for your check! I will take a look (though I'm not confident that I can do it...).