This is an archive of the discontinued LLVM Phabricator instance.

Differential D106851

[SCEV] Add two tests showing the bug in SCEV getAddExpr
AbandonedPublic

Authored by skatkov on Jul 27 2021, 12:26 AM.

Details

Reviewers
reames
nikic
efriedma
fhahn
mkazantsev
Summary

getAddExpr utility uses computed flags from AddRec plus loop invariants
in AddRec.Start + loop invariants basing on the an assumption that
0th iteration of the loop exists. However the loop might be dead
(runtime or compile time), in this case the propagation of the flag becomes
invalid.

One of the test shows the incorrect behavior of IndVarSimplify pass
in case of nested loops.
The second test shows incorrect SCEV computation of sibling loops.

In both cases the right loop is runtime dead and incorrect SCEV is computes
for alive left loop.

Diff Detail

Unit TestsFailed

TimeTest
3,240 msx64 debian > libarcher.barrier::barrier.c
3,060 msx64 debian > libarcher.critical::critical.c
3,620 msx64 debian > libarcher.parallel::parallel-simple2.c
3,620 msx64 debian > libarcher.races::critical-unrelated.c
3,530 msx64 debian > libarcher.races::lock-nested-unrelated.c
View Full Test Results (18 Failed)

Event Timeline

skatkov created this revision.Jul 27 2021, 12:26 AM
Herald added a subscriber: javed.absar. · View Herald TranscriptJul 27 2021, 12:26 AM
skatkov requested review of this revision.Jul 27 2021, 12:26 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 27 2021, 12:26 AM
skatkov added a child revision: D106852: [SCEV] Fix getAddExpr for adding loop invariants into start of some AddRec.Jul 27 2021, 12:29 AM
Harbormaster completed remote builds in B116356: Diff 361921.Jul 27 2021, 1:05 AM
mkazantsev accepted this revision.Sep 10 2021, 1:24 AM

It makes sense to file a bug (if not already) and describe what the bug is, and then rename the test file into pr<ID>.ll.
Do you really need an approval to check in the tests? :)

This revision is now accepted and ready to land.Sep 10 2021, 1:24 AM
reames added a comment.Sep 15 2021, 1:01 PM

FYI, I landed some tests for this in 248e430f37. Not sure if these are worth keeping or not.

skatkov abandoned this revision.Sep 15 2021, 8:11 PM

Abandon in favor of Philip's tests.

Revision Contents

PathSize
llvm/
test/
Analysis/
ScalarEvolution/
90 lines
52 lines

Diff 361921

llvm/test/Analysis/ScalarEvolution/nuw-add-nested-loops.ll

  • This file was added.
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --force-update
; RUN: opt < %s -indvars -S | FileCheck %s
; RUN: opt -S -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s --check-prefix=CHECK-ANALYSIS
; At the time test is written it shows that SCEV incorrectly computes flags
; for expression corresponding to outer_header loop and indvars does an
; incorrect transformation.
; CHECK-ANALYSIS: %r.ivi.next = add nuw nsw i32 %r.ivi, 1
; CHECK-ANALYSIS-NEXT: --> {{{{}}-399,+,1}<nuw><nsw><%outer_header>,+,1}<nuw><nsw><%right_header>
; CHECK-ANALYSIS: %l.ivi.next = add nsw i32 %l.ivi, 1
; CHECK-ANALYSIS-NEXT: --> {{{{}}-399,+,1}<nuw><nsw><%outer_header>,+,1}<nsw><%left_header>
define void @test(i1 %c) {
; CHECK-LABEL: @test(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
; CHECK: outer_header:
; CHECK-NEXT: [[IVO:%.*]] = phi i32 [ -400, [[ENTRY:%.*]] ], [ [[IVO_NEXT:%.*]], [[OUTER_BACKEDGE:%.*]] ]
; CHECK-NEXT: br i1 [[C:%.*]], label [[LEFT_HEADER_PREHEADER:%.*]], label [[RIGHT_HEADER_PREHEADER:%.*]]
; CHECK: right_header.preheader:
; CHECK-NEXT: br label [[RIGHT_HEADER:%.*]]
; CHECK: left_header.preheader:
; CHECK-NEXT: br label [[LEFT_HEADER:%.*]]
; CHECK: right_header:
; CHECK-NEXT: [[R_IVI:%.*]] = phi i32 [ [[R_IVI_NEXT:%.*]], [[RIGHT_HEADER]] ], [ [[IVO]], [[RIGHT_HEADER_PREHEADER]] ]
; CHECK-NEXT: [[R_IVI_NEXT]] = add nuw nsw i32 [[R_IVI]], 1
; CHECK-NEXT: [[R_IVI_NEXT_SDIV:%.*]] = sdiv i32 -1, [[R_IVI_NEXT]]
; CHECK-NEXT: [[R_IVI_NEXT_ZEXT:%.*]] = zext i32 [[R_IVI_NEXT_SDIV]] to i64
; CHECK-NEXT: call void @bar(i64 [[R_IVI_NEXT_ZEXT]])
; CHECK-NEXT: br i1 false, label [[OUTER_BACKEDGE_LOOPEXIT1:%.*]], label [[RIGHT_HEADER]]
; CHECK: left_header:
; CHECK-NEXT: br i1 false, label [[LEFT_BACKEDGE:%.*]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]]
; CHECK: left_backedge:
; CHECK-NEXT: br i1 false, label [[LEFT_EXIT:%.*]], label [[LEFT_HEADER]]
; CHECK: left_exit:
; CHECK-NEXT: call void @foo()
; CHECK-NEXT: br label [[OUTER_BACKEDGE]]
; CHECK: outer_backedge.loopexit:
; CHECK-NEXT: br label [[OUTER_BACKEDGE]]
; CHECK: outer_backedge.loopexit1:
; CHECK-NEXT: br label [[OUTER_BACKEDGE]]
; CHECK: outer_backedge:
; CHECK-NEXT: [[IVO_NEXT]] = add nuw nsw i32 [[IVO]], 1
; CHECK-NEXT: [[C_2:%.*]] = icmp sgt i32 [[IVO]], -2
; CHECK-NEXT: br i1 [[C_2]], label [[EXIT:%.*]], label [[OUTER_HEADER]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry:
br label %outer_header
outer_header:
%ivo = phi i32 [-400, %entry], [%ivo.next, %outer_backedge]
br i1 %c, label %left_header, label %right_header
right_header:
%r.ivi = phi i32 [%ivo, %outer_header], [%r.ivi.next, %right_header]
%r.ivi.next = add nsw nuw i32 %r.ivi, 1
; This instruction is required for SCEV to beleive that previous instruction is really nuw.
%r.ivi.next.sdiv = sdiv i32 -1, %r.ivi.next
%r.ivi.next.zext = zext i32 %r.ivi.next.sdiv to i64
call void @bar(i64 %r.ivi.next.zext)
%r.c = icmp sgt i32 %r.ivi.next, 1
br i1 %r.c, label %outer_backedge, label %right_header
left_header:
%l.ivi = phi i32 [%ivo, %outer_header], [%l.ivi.next, %left_backedge]
%l.ivi.next = add nsw i32 %l.ivi, 1
%l.c = icmp ult i32 %l.ivi.next, 400
br i1 %l.c, label %left_backedge, label %outer_backedge
left_backedge:
%l.c.2 = icmp sgt i32 %l.ivi, 1
br i1 %l.c.2, label %left_exit, label %left_header
left_exit:
call void @foo()
br label %outer_backedge
outer_backedge:
%ivo.next = add nuw nsw i32 %ivo, 1
%c.2 = icmp sgt i32 %ivo, -2
br i1 %c.2, label %exit, label %outer_header
exit:
ret void
}
declare void @foo() willreturn nounwind
declare void @bar(i64) willreturn nounwind

llvm/test/Analysis/ScalarEvolution/nuw-add-sibling-loops.ll

  • This file was added.
; RUN: opt -S -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s --check-prefix=CHECK-ANALYSIS
; At the time test is written it shows that SCEV incorrectly computes flags
; for expression corresponding to outer_header loop.
; CHECK-ANALYSIS: %r.ivi.next = add nuw nsw i32 %r.ivi, 1
; CHECK-ANALYSIS-NEXT: {{{{}}-399,+,1}<nuw><nsw><%outer_header>,+,1}<nuw><nsw><%right_header>
; CHECK-ANALYSIS: %l.ivi.next = add nsw i32 %l.ivi, 1
; CHECK-ANALYSIS-NEXT: {{{{}}-399,+,1}<nuw><nsw><%outer_header>,+,1}<nw><%left_header>
define void @test(i1 %c) {
entry:
br label %outer_header
outer_header:
%ivo = phi i32 [-400, %entry], [%ivo.next, %outer_header]
%ivo.next = add nuw nsw i32 %ivo, 1
%c.2 = icmp sgt i32 %ivo, -2
br i1 %c.2, label %outer_exit, label %outer_header
outer_exit:
br i1 %c, label %left_header, label %right_header
right_header:
%r.ivi = phi i32 [%ivo, %outer_exit], [%r.ivi.next, %right_header]
%r.ivi.next = add nsw nuw i32 %r.ivi, 1
; This instruction is required for SCEV to beleive that previous instruction is really nuw.
%r.ivi.next.sdiv = sdiv i32 -1, %r.ivi.next
%r.ivi.next.zext = zext i32 %r.ivi.next.sdiv to i64
call void @bar(i64 %r.ivi.next.zext)
%r.c = icmp sgt i32 %r.ivi.next, 1
br i1 %r.c, label %exit, label %right_header
left_header:
%l.ivi = phi i32 [%ivo, %outer_exit], [%l.ivi.next, %left_backedge], [%l.ivi.next, %left_exit]
%l.ivi.next = add nsw i32 %l.ivi, 1
%l.c = icmp ult i32 %l.ivi, 400
br i1 %l.c, label %left_backedge, label %left_exit
left_backedge:
%l.c.2 = icmp sgt i32 %l.ivi, 1
br i1 %l.c.2, label %exit, label %left_header
left_exit:
call void @foo()
br label %left_header
exit:
ret void
}
declare void @foo() willreturn nounwind
declare void @bar(i64) willreturn nounwind