[llvm-bugs] [Bug 44058] New: LCSSA corrupts SCEV

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=44058

            Bug ID: 44058
           Summary: LCSSA corrupts SCEV
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: suc-daniil at yandex.ru
                CC: llvm-bugs at lists.llvm.org

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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20191119/db420b17/attachment.html>