1f2a634c44
Motivating example: https://godbolt.org/z/eb97zrxhx Here we have 2 induction variables in the loop: one is corresponding to i variable (add rdx, 4), the other - to res (add rax, 2). The second induction variable can be removed by rewriteLoopExitValues() method (final value of res at loop exit is unroll_iter * -2); however, this doesn't happen because we have duplicated LCSSA phi nodes at loop exit: ``` ; Preheader: for.body.preheader.new: ; preds = %for.body.preheader %unroll_iter = and i64 %N, -4 br label %for.body ; Loop: for.body: ; preds = %for.body, %for.body.preheader.new %lsr.iv = phi i64 [ %lsr.iv.next, %for.body ], [ 0, %for.body.preheader.new ] %i.07 = phi i64 [ 0, %for.body.preheader.new ], [ %inc.3, %for.body ] %inc.3 = add nuw i64 %i.07, 4 %lsr.iv.next = add nsw i64 %lsr.iv, -2 %niter.ncmp.3.not = icmp eq i64 %unroll_iter, %inc.3 br i1 %niter.ncmp.3.not, label %for.end.loopexit.unr-lcssa.loopexit, label %for.body, !llvm.loop !7 ; Exit blocks for.end.loopexit.unr-lcssa.loopexit: ; preds = %for.body %inc.3.lcssa = phi i64 [ %inc.3, %for.body ] %lsr.iv.next.lcssa11 = phi i64 [ %lsr.iv.next, %for.body ] %lsr.iv.next.lcssa = phi i64 [ %lsr.iv.next, %for.body ] br label %for.end.loopexit.unr-lcssa ``` rewriteLoopExitValues requires %lsr.iv.next value to have only 2 uses: one in LCSSA phi node, the other - in induction phi node. Here we have 3 uses of this value because of duplicated lcssa nodes, so the transform doesn't apply and leads to an extra add operation inside the loop. The proposed solution is to accumulate inserted instructions that will require LCSSA form update into SetVector and then call formLCSSAForInstructions for this SetVector once, so the same instructions don't process twice. Reland fixes the issue with preserve-lcssa.ll test: it fails in the situation when x86_64-unknown-linux-gnu target is unavailable in opt. The changes are moved into separate duplicated-phis.ll test with explicit x86 target requirement to fix bots which are not building this target.
141 lines
4.3 KiB
LLVM
141 lines
4.3 KiB
LLVM
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
|
|
; RUN: opt -loop-reduce -S < %s | FileCheck %s
|
|
;
|
|
; Test LSR's use of SplitCriticalEdge during phi rewriting.
|
|
|
|
target triple = "x86_64-apple-darwin"
|
|
|
|
; Provide legal integer types.
|
|
target datalayout = "n8:16:32:64"
|
|
|
|
; Verify that identical edges are merged. rdar://problem/6453893
|
|
|
|
define ptr @test1() {
|
|
;
|
|
; CHECK-LABEL: @test1(
|
|
; CHECK-NEXT: entry:
|
|
; CHECK-NEXT: br label [[LOOP:%.*]]
|
|
; CHECK: loop:
|
|
; CHECK-NEXT: [[LSR_IV:%.*]] = phi ptr [ [[SCEVGEP:%.*]], [[LOOP]] ], [ null, [[ENTRY:%.*]] ]
|
|
; CHECK-NEXT: [[SCEVGEP]] = getelementptr i8, ptr [[LSR_IV]], i64 1
|
|
; CHECK-NEXT: br i1 false, label [[LOOP]], label [[LOOPEXIT:%.*]]
|
|
; CHECK: loopexit:
|
|
; CHECK-NEXT: [[SCEVGEP_LCSSA:%.*]] = phi ptr [ [[SCEVGEP]], [[LOOP]] ]
|
|
; CHECK-NEXT: br i1 false, label [[BBA:%.*]], label [[BBB:%.*]]
|
|
; CHECK: bbA:
|
|
; CHECK-NEXT: switch i32 0, label [[BBA_BB89_CRIT_EDGE:%.*]] [
|
|
; CHECK-NEXT: i32 47, label [[BBA_BB89_CRIT_EDGE]]
|
|
; CHECK-NEXT: i32 58, label [[BBA_BB89_CRIT_EDGE]]
|
|
; CHECK-NEXT: ]
|
|
; CHECK: bbA.bb89_crit_edge:
|
|
; CHECK-NEXT: br label [[BB89:%.*]]
|
|
; CHECK: bbB:
|
|
; CHECK-NEXT: switch i8 0, label [[BBB_BB89_CRIT_EDGE:%.*]] [
|
|
; CHECK-NEXT: i8 47, label [[BBB_BB89_CRIT_EDGE]]
|
|
; CHECK-NEXT: i8 58, label [[BBB_BB89_CRIT_EDGE]]
|
|
; CHECK-NEXT: ]
|
|
; CHECK: bbB.bb89_crit_edge:
|
|
; CHECK-NEXT: br label [[BB89]]
|
|
; CHECK: bb89:
|
|
; CHECK-NEXT: [[TMP75PHI:%.*]] = phi ptr [ [[SCEVGEP_LCSSA]], [[BBA_BB89_CRIT_EDGE]] ], [ [[SCEVGEP_LCSSA]], [[BBB_BB89_CRIT_EDGE]] ]
|
|
; CHECK-NEXT: br label [[EXIT:%.*]]
|
|
; CHECK: exit:
|
|
; CHECK-NEXT: ret ptr [[TMP75PHI]]
|
|
;
|
|
entry:
|
|
br label %loop
|
|
|
|
loop:
|
|
%rec = phi i32 [ %next, %loop ], [ 0, %entry ]
|
|
%next = add i32 %rec, 1
|
|
%tmp75 = getelementptr i8, ptr null, i32 %next
|
|
br i1 false, label %loop, label %loopexit
|
|
|
|
loopexit:
|
|
br i1 false, label %bbA, label %bbB
|
|
|
|
bbA:
|
|
switch i32 0, label %bb89 [
|
|
i32 47, label %bb89
|
|
i32 58, label %bb89
|
|
]
|
|
|
|
bbB:
|
|
switch i8 0, label %bb89 [
|
|
i8 47, label %bb89
|
|
i8 58, label %bb89
|
|
]
|
|
|
|
bb89:
|
|
%tmp75phi = phi ptr [ %tmp75, %bbA ], [ %tmp75, %bbA ], [ %tmp75, %bbA ], [ %tmp75, %bbB ], [ %tmp75, %bbB ], [ %tmp75, %bbB ]
|
|
br label %exit
|
|
|
|
exit:
|
|
ret ptr %tmp75phi
|
|
}
|
|
|
|
; Handle single-predecessor phis: PR13756
|
|
define ptr @test2() {
|
|
;
|
|
; CHECK-LABEL: @test2(
|
|
; CHECK-NEXT: entry:
|
|
; CHECK-NEXT: br label [[LOOP:%.*]]
|
|
; CHECK: loop:
|
|
; CHECK-NEXT: [[LSR_IV:%.*]] = phi ptr [ [[SCEVGEP:%.*]], [[LOOP]] ], [ null, [[ENTRY:%.*]] ]
|
|
; CHECK-NEXT: [[SCEVGEP]] = getelementptr i8, ptr [[LSR_IV]], i64 1
|
|
; CHECK-NEXT: br i1 false, label [[LOOP]], label [[LOOPEXIT:%.*]]
|
|
; CHECK: loopexit:
|
|
; CHECK-NEXT: [[SCEVGEP_LCSSA:%.*]] = phi ptr [ [[SCEVGEP]], [[LOOP]] ]
|
|
; CHECK-NEXT: br i1 false, label [[BBA:%.*]], label [[BBB:%.*]]
|
|
; CHECK: bbA:
|
|
; CHECK-NEXT: switch i32 0, label [[BB89:%.*]] [
|
|
; CHECK-NEXT: i32 47, label [[BB89]]
|
|
; CHECK-NEXT: i32 58, label [[BB89]]
|
|
; CHECK-NEXT: ]
|
|
; CHECK: bbB:
|
|
; CHECK-NEXT: switch i8 0, label [[BBB_EXIT_CRIT_EDGE:%.*]] [
|
|
; CHECK-NEXT: i8 47, label [[BBB_EXIT_CRIT_EDGE]]
|
|
; CHECK-NEXT: i8 58, label [[BBB_EXIT_CRIT_EDGE]]
|
|
; CHECK-NEXT: ]
|
|
; CHECK: bbB.exit_crit_edge:
|
|
; CHECK-NEXT: br label [[EXIT:%.*]]
|
|
; CHECK: bb89:
|
|
; CHECK-NEXT: [[TMP75PHI:%.*]] = phi ptr [ [[SCEVGEP_LCSSA]], [[BBA]] ], [ [[SCEVGEP_LCSSA]], [[BBA]] ], [ [[SCEVGEP_LCSSA]], [[BBA]] ]
|
|
; CHECK-NEXT: br label [[EXIT]]
|
|
; CHECK: exit:
|
|
; CHECK-NEXT: [[RESULT:%.*]] = phi ptr [ [[TMP75PHI]], [[BB89]] ], [ [[SCEVGEP_LCSSA]], [[BBB_EXIT_CRIT_EDGE]] ]
|
|
; CHECK-NEXT: ret ptr [[RESULT]]
|
|
;
|
|
entry:
|
|
br label %loop
|
|
|
|
loop:
|
|
%rec = phi i32 [ %next, %loop ], [ 0, %entry ]
|
|
%next = add i32 %rec, 1
|
|
%tmp75 = getelementptr i8, ptr null, i32 %next
|
|
br i1 false, label %loop, label %loopexit
|
|
|
|
loopexit:
|
|
br i1 false, label %bbA, label %bbB
|
|
|
|
bbA:
|
|
switch i32 0, label %bb89 [
|
|
i32 47, label %bb89
|
|
i32 58, label %bb89
|
|
]
|
|
|
|
bbB:
|
|
switch i8 0, label %exit [
|
|
i8 47, label %exit
|
|
i8 58, label %exit
|
|
]
|
|
|
|
bb89:
|
|
%tmp75phi = phi ptr [ %tmp75, %bbA ], [ %tmp75, %bbA ], [ %tmp75, %bbA ]
|
|
br label %exit
|
|
|
|
exit:
|
|
%result = phi ptr [ %tmp75phi, %bb89 ], [ %tmp75, %bbB ], [ %tmp75, %bbB ], [ %tmp75, %bbB ]
|
|
ret ptr %result
|
|
}
|