<html>
<head>
<base href="https://bugs.llvm.org/">
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - [LICM][MustExecute] MustExecute analysis is fundamentally broken"
href="https://bugs.llvm.org/show_bug.cgi?id=38514">38514</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>[LICM][MustExecute] MustExecute analysis is fundamentally broken
</td>
</tr>
<tr>
<th>Product</th>
<td>new-bugs
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Windows NT
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>new bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>max.kazantsev@azul.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>I have submitted some tests that show what MustExecute analysis is wrong. See
<a href="https://reviews.llvm.org/rL339417">https://reviews.llvm.org/rL339417</a>.
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.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>