[llvm-bugs] [Bug 44320] New: SSAUpdater corrupts SCEV

[via llvm-bugs]

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

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

Created attachment 22940
  --> https://bugs.llvm.org/attachment.cgi?id=22940&action=edit
CFG after loop unswitch

Consider following IR:
define void @foo(i32* %arg, i32* %arg1, i1 %cond1, i1 %cond2, i1 %cond3, i1
%cond4, i1 %cond5) {
bb:
  br label %bb3

bb2:                                              ; preds = %bb20
  br label %bb3

bb3:                                              ; preds = %bb2, %bb
  br i1 %cond1, label %bb4, label %bb24

bb4:                                              ; preds = %bb3
  %tmp = load i32, i32* %arg
  %tmp5 = load i32, i32* %arg1
  %tmp6 = add i32 %tmp5, %tmp
  %tmp7 = icmp sgt i32 %tmp6, %tmp
  br i1 %tmp7, label %bb8, label %bb17

bb8:                                              ; preds = %bb4
  %tmp9 = and i1 %cond2, %cond3
  br label %bb10

bb10:                                             ; preds = %bb15, %bb8
  %tmp11 = phi i32 [ %tmp12, %bb15 ], [ %tmp, %bb8 ]
  %tmp12 = add nsw i32 %tmp11, 1
  br i1 %tmp9, label %bb15, label %bb13

bb13:                                             ; preds = %bb10
  %tmp14 = phi i32 [ %tmp12, %bb10 ]
  ret void

bb15:                                             ; preds = %bb10
  br i1 %cond4, label %bb10, label %bb16

bb16:                                             ; preds = %bb15
  br label %bb17

bb17:                                             ; preds = %bb16, %bb4
  %tmp18 = phi i32 [ 0, %bb4 ], [ %tmp5, %bb16 ]
  br i1 %cond5, label %bb25, label %bb19

bb19:                                             ; preds = %bb17
  br label %bb20

bb20:                                             ; preds = %bb20, %bb19
  %tmp21 = phi i32 [ %tmp22, %bb20 ], [ 0, %bb19 ]
  %tmp22 = add nuw nsw i32 %tmp21, 1
  %tmp23 = icmp slt i32 %tmp22, %tmp18
  br i1 %tmp23, label %bb20, label %bb2

bb24:                                             ; preds = %bb3
  ret void

bb25:                                             ; preds = %bb17
  ret void
}

Following command:
opt
-passes="verify<scalar-evolution>,loop(unswitch<nontrivial>),verify<scalar-evolution>"
-S -o /dev/null -verify-scev-strict input.ll

completes with following error message:
Trip Count for Loop at depth 2 containing: %bb20<header><latch><exiting>
 Changed!
Old: (-1 + (1 smax ((-1 * %.us-phi) + ((%tmp5 + %.us-phi) smax
%.us-phi))))<nsw>
New: (-1 + (1 smax ((-1 * %tmp) + ((%tmp + %tmp5) smax %tmp))))<nsw>
Delta: ((-1 * (1 smax ((-1 * %tmp) + ((%tmp + %tmp5) smax %tmp))))<nsw> + (1
smax ((-1 * %.us-phi) + ((%tmp5 + %.us-phi) smax %.us-phi))))

(comment: %.us-phi is an alias of %tmp that doesn't dominate %bb20, %bb20 isn't
even reachable from the point where %.us-phi is defined; if that's unclear see
attached .svg CFG of the final IR)

Here's why:
To preserve LCSSA SimpleLoopUnswitch calls formLCSSA, which in some cases uses
SSAUpdater::RewriteUse. Even though SSAUpdater::RewriteUse rewrites only one
use, it calls ValueHandleBase::ValueIsRAUWd which in turn calls
CallbackVH::allUsesReplacedWith. SCEVUnknown::allUsesReplacedWith acts the way
that is correct if and only if all uses of the value are replaced (and given
the name of the method it makes complete sense), so it looks like
ValueHandleBase::ValueIsRAUWd shouldn't be called by SSAUpdater::RewriteUse at
all. Actually if I just remove the call to ValueHandleBase::ValueIsRAUWd the
bug goes away and `make check` completes successfully. Here's the catch: that
call was added by the following commit:
    commit 8d804520766b6772277fcc1d9b31da02f320bc12
    Author: Nadav Rotem <nrotem at apple.com>
    Date:   Mon Aug 13 23:06:54 2012 +0000

        LICM uses AliasSet information to hoist and sink instructions. However,
other passes, such as LoopRotate
        may invalidate its AliasSet because SSAUpdater does not update the
AliasSet properly.
        This patch teaches SSAUpdater to notify AliasSet that it made changes.
        The testcase in PR12901 is too big to be useful and I could not reduce
it to a normal size.

        rdar://11872059 PR12901

        llvm-svn: 161803


I.e. AliasSetTracker relies on SSAUpdater to (incorrectly) call
ValueHandleBase::ValueIsRAUWd for every new instruction it adds, so we can't
simply remove that call since it will (probably) cause new bugs.

One way to fix it is to remove that call and invalidate AliasSet everywhere
where SSAUpdater is used, either directly or indirectly, but it goes against
what many efforts were aimed for (compile time improvements).

Another way is to introduce a new method, say CallbackVH::UseIsReplacedWith,
and its counterpart ValueHandleBase::UsesOfValueReplaced and call it in such
cases instead of ValueHandleBase::ValueIsRAUWd. This option looks OK to me but
the scope of the work leaves me wonder if there is an easier solution.

I'd like to hear others opinions on how this issue can be resolved.

-- 
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/20191217/a9e638b2/attachment.html>