<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 - [SCEV] computeBackedgeTakenCount() returns incorrect BackedgeTakenInfo"
href="https://bugs.llvm.org/show_bug.cgi?id=48225">48225</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>[SCEV] computeBackedgeTakenCount() returns incorrect BackedgeTakenInfo
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Linux
</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>Scalar Optimizations
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>congzhecao@gmail.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>The IR that exposed this bug is the following.
; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-unknown-linux-gnu"
@a = common dso_local local_unnamed_addr global i32 0, align 4
@b = common dso_local local_unnamed_addr global i32 0, align 4
; Function Attrs: minsize nofree norecurse nounwind optsize
define dso_local i32 @main() local_unnamed_addr {
entry:
%0 = load i32, i32* @b, align 4
%cmp1 = icmp ne i32 %0, 0
%conv = zext i1 %cmp1 to i32
br label %for.cond
for.cond: ; preds = %for.body, %entry
%storemerge = phi i32 [ 0, %entry ], [ %inc, %for.body ]
%cmp = icmp ult i32 %storemerge, 2
br i1 %cmp, label %for.body, label %for.end
for.body: ; preds = %for.cond
%cmp2 = icmp eq i32 %storemerge, %conv
%tobool = icmp ne i32 %storemerge, 0
%or.cond = and i1 %tobool, %cmp2
%inc = add nuw nsw i32 %storemerge, 1
br i1 %or.cond, label %for.cond4.preheader, label %for.cond
for.cond4.preheader: ; preds = %for.body
%storemerge.lcssa6 = phi i32 [ %storemerge, %for.body ]
store i32 %storemerge.lcssa6, i32* @a, align 4
br label %for.cond4
for.cond4: ; preds =
%for.cond4.preheader, %for.cond4
br label %for.cond4
for.end: ; preds = %for.cond
%storemerge.lcssa = phi i32 [ %storemerge, %for.cond ]
store i32 %storemerge.lcssa, i32* @a, align 4
ret i32 0
}
For the IR above, the BackedgeTakenInfo returned from
ScalarEvolution::computeBackedgeTakenCount() is not correct. To be specific,
the field MaxAndComplete of BackedgeTakenInfo is incorrect. Dumping its value
using BackedgeTakenInfo.getMax()->dump() gives 1 meaning the computed backedge
count is 1. However the true value of backedge count should be 2.
Further investigation shows that the bug is in function
ScalarEvolution::computeExitLimitFromCondImpl(). When ExitCond is
Instruction::AND, this function computes two ExitLimit objects for the two
operands of AND, then does some post-processing and returns the result. In the
example, consider the ExitCond %or.cond of BB for.body, its two operands are:
%tobool = icmp ne i32 %storemerge, 0
%cmp2 = icmp eq i32 %storemerge, %conv
The ExitLimit.MaxNotTaken computed from %tobool is 1. The ExitLimit.MaxNotTaken
computed from %cmp2 is also 1. Therefore it determines that the MaxBECount for
BB for.body is 1.
However, it does not consider the fact that the two operands of AND are
sometimes not independent which results in the AND operator always evaluated to
false. This is exactly the case in the example above: %conv = zext i1 %cmp1 to
i32 so its range is [0,1] and at runtime it is actually 0. Thus %or.cond is
always false, meaning we always take the backedge when exiting BB for.body.
I think in this case the MaxBECount computed from
ScalarEvolution::computeExitLimitFromCondImpl() is supposed to be
CouldNotCompute.
Suggested fix:
in function ScalarEvolution::computeExitLimitFromCondImpl(), when ExitCond is
Instruction::AND, check if the two operands are independent. If not, then
directly return CouldNotCompute. To be specific, a simple check could consider
catching the following case:
operand 1: cmp eq %var1, %var2
operand 2: cmp ne %var1, %var3
where the range of %var2 is a subset of the range of %var3.
This simple check can be or needs be generalized, but that's a simple first fix
off the top of my head.</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>