[DA] Insufficient validation of delinearization results

[kasuga-fj]

Input:

define void @f(ptr %a, i64 %k) {
entry:
  %cmp = icmp eq i64 %k, 0
  br i1 %cmp, label %exit, label %loop

loop:
  %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
  %i.next = add i64 %i, 1
  %subscript.0 = mul i64 %i, %k
  %subscript.1 = mul i64 %i.next, %k
  %idx.0 = getelementptr i8, ptr %a, i64 %subscript.0
  %idx.1 = getelementptr i8, ptr %a, i64 %subscript.1
  store i8 42, ptr %idx.0
  store i8 42, ptr %idx.1
  %cond.exit = icmp eq i64 %i.next, 10000
  br i1 %cond.exit, label %exit, label %loop

exit:
  ret void
}

Result:

$ opt -passes='print<da>' -disable-output test.ll
Printing analysis 'Dependence Analysis' for function 'f':
Src:  store i8 42, ptr %idx.0, align 1 --> Dst:  store i8 42, ptr %idx.0, align 1
  da analyze - none!
Src:  store i8 42, ptr %idx.0, align 1 --> Dst:  store i8 42, ptr %idx.1, align 1
  da analyze - consistent output [-1]!
Src:  store i8 42, ptr %idx.1, align 1 --> Dst:  store i8 42, ptr %idx.1, align 1
  da analyze - none!

godbolt: https://godbolt.org/z/8Pc4Ev565

The dependencies between the two stores are reported as [-1], which is incorrect if %k is negative, as it should be [1]. I think the delinearization check is insufficient .Executing opt --pass='print<delinearization>' yields the following output:

Delinearization on function f:

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

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

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

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

godbolt: https://godbolt.org/z/9W6YWcMsG

The line ArrayDecl[UnknownSize][%k] ... indicates the estimated array size. Maybe we should reject such a result in DA if we cannot prove %k is non-negative.