[llvm-bugs] [Bug 38514] New: [LICM][MustExecute] MustExecute analysis is fundamentally broken

[via llvm-bugs]

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

            Bug ID: 38514
           Summary: [LICM][MustExecute] MustExecute analysis is
                    fundamentally broken
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: Windows NT
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: max.kazantsev at azul.com
                CC: llvm-bugs at lists.llvm.org

I have submitted some tests that show what MustExecute analysis is wrong. See
https://reviews.llvm.org/rL339417.

Given the example:

define void @test_impossible_exit_in_untaken_block(i32 %a, i32 %b, i32* %p) {
entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  br i1 false, label %never_taken, label %backedge

never_taken:
  %div = sdiv i32 %a, %b
  store i32 %div, i32* %p
  br i1 true, label %backedge, label %exit

backedge:
  %iv.next = add i32 %iv, 1
  br label %loop

exit:
  ret void
}

As we seem block "never_taken" is never entered. Even more, block "exit" would
not be reached even if it was taken. So the instruction %div (which is
potentially dangerous if b == 0) is never executed. However MustExecute
incorrectly says that the block "never_taken" will always be executed basing on
fact that it dominates all loop exits.

Basing on that, LICM manages to hoist %div into the entry block, introducing UB
to a program that did not contain it before the optimization. It ends up with
the following:

define void @test_impossible_exit_in_untaken_block(i32 %a, i32 %b, i32* %p) {
entry:
  %div = sdiv i32 %a, %b
  br label %loop

loop:                                             ; preds = %backedge, %entry
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  br i1 false, label %never_taken, label %backedge

never_taken:                                      ; preds = %loop
  br i1 true, label %backedge, label %exit

backedge:                                         ; preds = %never_taken, %loop
  %iv.next = add i32 %iv, 1
  br label %loop

exit:                                             ; preds = %never_taken
  store i32 %div, i32* %p, align 4
  ret void
}

The reason of that is that because implementation of isGuaranteedToExecute does
not correspond to its specification. The comment to this function says:

/// Returns true if the instruction in a loop is guaranteed to execute at least
/// once (under the assumption that the loop is entered).

However the last piece of code after this comment:

  // Note: There are two styles of reasoning intermixed below for
  // implementation efficiency reasons.  They are:
  // 1) If we can prove that the instruction dominates all exit blocks, then we
  // know the instruction must have executed on *some* iteration before we
  // exit.  We do not prove *which* iteration the instruction must execute on.
  // 2) If we can prove that the instruction dominates the latch and all exits
  // which might be taken on the first iteration, we know the instruction must
  // execute on the first iteration.  This second style allows a conditional
  // exit before the instruction of interest which is provably not taken on the
  // first iteration.  This is a quite common case for range check like
  // patterns.  TODO: support loops with multiple latches.

Does the different thing. If you take a closer look into this description, this
logic returns true if the instruction is proved executed under assumption that
the loop was EXITED, not ENTERED. So it solves the different problem for loops
which will effectively be not exited. The attempt to return false for loops
that do not have exit blocks is insufficient, because infinite loops may have
any number of exit blocks.

-- 
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/20180810/61d03681/attachment.html>