[llvm-bugs] [Bug 48225] New: [SCEV] computeBackedgeTakenCount() returns incorrect BackedgeTakenInfo

[via llvm-bugs]

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

            Bug ID: 48225
           Summary: [SCEV] computeBackedgeTakenCount() returns incorrect
                    BackedgeTakenInfo
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: congzhecao at gmail.com
                CC: llvm-bugs at lists.llvm.org

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.

-- 
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/20201119/37790906/attachment-0001.html>