LCSSAPass corrupts SCEV

[Quuxplusone]

Bugzilla Link	PR44058
Status	RESOLVED FIXED
Importance	P enhancement
Reported by	Daniil Suchkov (suc-daniil@yandex.ru)
Reported on	2019-11-19 03:47:00 -0800
Last modified on	2019-12-08 21:12:51 -0800
Version	trunk
Hardware	PC Linux
CC	florian_hahn@apple.com, listmail@philipreames.com, llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

Consider following IR:
define void @foo(i32* %arg, i32* %arg1, i1 %arg2) {
bb:
  br label %bb3

bb3:                                              ; preds = %bb13, %bb
  %tmp = load i32, i32* %arg
  %tmp4 = load i32, i32* %arg1
  %tmp5 = add i32 %tmp4, %tmp
  %tmp6 = icmp sgt i32 %tmp5, %tmp
  br i1 %tmp6, label %bb7, label %bb11

bb7:                                              ; preds = %bb3
  br i1 %arg2, label %bb10, label %bb8

bb8:                                              ; preds = %bb7
  %tmp9 = add nsw i32 %tmp, 1
  ret void

bb10:                                             ; preds = %bb7
  br label %bb11

bb11:                                             ; preds = %bb10, %bb3
  %tmp12 = phi i32 [ 0, %bb3 ], [ %tmp4, %bb10 ]
  br label %bb13

bb13:                                             ; preds = %bb13, %bb11
  %tmp14 = phi i32 [ %tmp15, %bb13 ], [ 0, %bb11 ]
  %tmp15 = add nuw nsw i32 %tmp14, 1
  %tmp16 = icmp slt i32 %tmp15, %tmp12
  br i1 %tmp16, label %bb13, label %bb3
}

SCEV of trip count for bb13 loop is `(-1 + (1 smax ((-1 * %tmp) + ((%tmp +
%tmp4) smax %tmp))))<nsw>`
LCSSA inserts following phi into bb8: %tmp.lcssa = phi i32 [ %tmp, %bb7 ]
When the phi is inserted, LCSSA calls ValueHandleBase::ValueIsRAUWd(%tmp,
%tmp.lcssa). Since %tmp is SCEVUnknown,
SCEVUnknown::allUsesReplacedWith(%tmp.lcssa) is called.
After that point SCEV of trip count for bb13 loop is `(-1 + (1 smax ((-1 *
%tmp.lcssa) + ((%tmp4 + %tmp.lcssa) smax %tmp.lcssa))))<nsw>`
Please note that %bb13 isn't reachable from %bb8, so this SCEV is incorrect.

With this patch applied: https://reviews.llvm.org/D70423
Following command:
   opt -passes="verify<scalar-evolution>,lcssa,verify<scalar-evolution>" -verify-scev-strict -S repro.ll
fails with following message:
    Trip Count for Loop at depth 2 containing: %bb13<header><latch><exiting>
     Changed!
    Old: (-1 + (1 smax ((-1 * %tmp.lcssa) + ((%tmp4 + %tmp.lcssa) smax %tmp.lcssa))))<nsw>
    New: (-1 + (1 smax ((-1 * %tmp) + ((%tmp + %tmp4) smax %tmp))))<nsw>
    Delta: ((-1 * (1 smax ((-1 * %tmp) + ((%tmp + %tmp4) smax %tmp))))<nsw> + (1 smax ((-1 * %tmp.lcssa) + ((%tmp4 + %tmp.lcssa) smax %tmp.lcssa))))

It is possible to reproduce the problem even without that patch, but it is less
convenient. With this command:
opt -passes="print<scalar-evolution>,lcssa,print<scalar-evolution>" -S repro.ll

The same problem is visible, but it requires manual checking (or parsing) of
the output.

Important note: both commands contain an extra pass before LCSSA (verify<scalar-
evolution> or print<scalar-evolution>). In both cases they are required to
query SCEV so that when LCSSA runs it has some cached values to corrupt.

In my opinion behavior of SCEVUnknown::allUsesReplacedWith is reasonable for
the case when *all* uses of the value are replaced, so the problem is that
LCSSA calls ValueHandleBase::ValueIsRAUWd when only some uses of the value are
replaced (hence the solution is to call something like SE->forgetValue
instead). But I'd like to hear others' opinions on this matter.

[Quuxplusone]

Here's an attempt to fix it: https://reviews.llvm.org/D70593

[Quuxplusone]

Fixed by https://reviews.llvm.org/rGc4d8c6319f576a7540017168db2f0440691914f4