Skip to content

Commit 1ee9324

Browse files
fhahnfhahn
committed
[LoopInterchange] Only skip PHIs with incoming values from the inner loop.
Currently we have limited support for outer loops with multiple basic blocks after the inner loop exit. But the current checks for creating PHIs for loop exit values only assumes the header and latches of the outer loop. It is better to just skip incoming values defined in the original inner loops. Those are handled earlier. Reviewers: efriedma, mcrosier Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D70059
1 parent ec4c96d commit 1ee9324

File tree

2 files changed

+157
-7
lines changed

2 files changed

+157
-7
lines changed

‎llvm/lib/Transforms/Scalar/LoopInterchange.cpp

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1339,7 +1339,8 @@ static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
13391339
// Move Lcssa PHIs to the right place.
13401340
static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
13411341
BasicBlock *InnerLatch, BasicBlock *OuterHeader,
1342-
BasicBlock *OuterLatch, BasicBlock *OuterExit) {
1342+
BasicBlock *OuterLatch, BasicBlock *OuterExit,
1343+
Loop *InnerLoop, LoopInfo *LI) {
13431344

13441345
// Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
13451346
// defined either in the header or latch. Those blocks will become header and
@@ -1394,19 +1395,17 @@ static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
13941395
P->moveBefore(InnerExit->getFirstNonPHI());
13951396

13961397
// Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
1397-
// incoming values from the outer latch or header, we have to add a new PHI
1398+
// incoming values defined in the outer loop, we have to add a new PHI
13981399
// in the inner loop latch, which became the exit block of the outer loop,
13991400
// after interchanging.
14001401
if (OuterExit) {
14011402
for (PHINode &P : OuterExit->phis()) {
14021403
if (P.getNumIncomingValues() != 1)
14031404
continue;
1404-
// Skip Phis with incoming values not defined in the outer loop's header
1405-
// and latch. Also skip incoming phis defined in the latch. Those should
1405+
// Skip Phis with incoming values defined in the inner loop. Those should
14061406
// already have been updated.
14071407
auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
1408-
if (!I || ((I->getParent() != OuterLatch || isa<PHINode>(I)) &&
1409-
I->getParent() != OuterHeader))
1408+
if (!I || LI->getLoopFor(I->getParent()) == InnerLoop)
14101409
continue;
14111410

14121411
PHINode *NewPhi = dyn_cast<PHINode>(P.clone());
@@ -1520,7 +1519,8 @@ bool LoopInterchangeTransform::adjustLoopBranches() {
15201519
OuterLoopPreHeader);
15211520

15221521
moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,
1523-
OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock());
1522+
OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(),
1523+
InnerLoop, LI);
15241524
// For PHIs in the exit block of the outer loop, outer's latch has been
15251525
// replaced by Inners'.
15261526
OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);

‎llvm/test/Transforms/LoopInterchange/pr43797-lcssa-for-multiple-outer-loop-blocks.ll

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2+
; RUN: opt -loop-interchange -verify-loop-lcssa -S %s | FileCheck %s
3+
4+
; Tests for PR43797.
5+
6+
@wdtdr = external dso_local global [5 x [5 x double]], align 16
7+
8+
define void @test1() {
9+
; CHECK-LABEL: @test1(
10+
; CHECK-NEXT: entry:
11+
; CHECK-NEXT: br label [[INNER_HEADER_PREHEADER:%.*]]
12+
; CHECK: outer.header.preheader:
13+
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
14+
; CHECK: outer.header:
15+
; CHECK-NEXT: [[OUTER_IDX:%.*]] = phi i64 [ [[OUTER_IDX_INC:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[OUTER_HEADER_PREHEADER:%.*]] ]
16+
; CHECK-NEXT: [[ARRAYIDX8:%.*]] = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 [[OUTER_IDX]]
17+
; CHECK-NEXT: br label [[INNER_HEADER_SPLIT:%.*]]
18+
; CHECK: inner.header.preheader:
19+
; CHECK-NEXT: br label [[INNER_HEADER:%.*]]
20+
; CHECK: inner.header:
21+
; CHECK-NEXT: [[INNER_IDX:%.*]] = phi i64 [ [[TMP3:%.*]], [[INNER_LATCH_SPLIT:%.*]] ], [ 0, [[INNER_HEADER_PREHEADER]] ]
22+
; CHECK-NEXT: br label [[OUTER_HEADER_PREHEADER]]
23+
; CHECK: inner.header.split:
24+
; CHECK-NEXT: [[TMP0:%.*]] = load double, double* [[ARRAYIDX8]], align 8
25+
; CHECK-NEXT: store double undef, double* [[ARRAYIDX8]], align 8
26+
; CHECK-NEXT: br label [[INNER_LATCH:%.*]]
27+
; CHECK: inner.latch:
28+
; CHECK-NEXT: [[INNER_IDX_INC:%.*]] = add nsw i64 [[INNER_IDX]], 1
29+
; CHECK-NEXT: br label [[INNER_EXIT:%.*]]
30+
; CHECK: inner.latch.split:
31+
; CHECK-NEXT: [[TMP1:%.*]] = phi i64 [ [[OUTER_V:%.*]], [[OUTER_LATCH]] ]
32+
; CHECK-NEXT: [[TMP2:%.*]] = phi i64 [ [[OUTER_IDX_INC]], [[OUTER_LATCH]] ]
33+
; CHECK-NEXT: [[TMP3]] = add nsw i64 [[INNER_IDX]], 1
34+
; CHECK-NEXT: br i1 false, label [[INNER_HEADER]], label [[OUTER_EXIT:%.*]]
35+
; CHECK: inner.exit:
36+
; CHECK-NEXT: [[OUTER_V]] = add nsw i64 [[OUTER_IDX]], 1
37+
; CHECK-NEXT: br label [[OUTER_LATCH]]
38+
; CHECK: outer.latch:
39+
; CHECK-NEXT: [[OUTER_IDX_INC]] = add nsw i64 [[OUTER_IDX]], 1
40+
; CHECK-NEXT: br i1 false, label [[OUTER_HEADER]], label [[INNER_LATCH_SPLIT]]
41+
; CHECK: outer.exit:
42+
; CHECK-NEXT: [[EXIT1_LCSSA:%.*]] = phi i64 [ [[TMP1]], [[INNER_LATCH_SPLIT]] ]
43+
; CHECK-NEXT: [[EXIT2_LCSSA:%.*]] = phi i64 [ [[TMP2]], [[INNER_LATCH_SPLIT]] ]
44+
; CHECK-NEXT: ret void
45+
;
46+
entry:
47+
br label %outer.header
48+
49+
outer.header: ; preds = %for.inc27, %entry
50+
%outer.idx = phi i64 [ 0, %entry ], [ %outer.idx.inc, %outer.latch ]
51+
%arrayidx8 = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 %outer.idx
52+
br label %inner.header
53+
54+
inner.header: ; preds = %for.inc, %for.body
55+
%inner.idx = phi i64 [ 0, %outer.header ], [ %inner.idx.inc, %inner.latch]
56+
%0 = load double, double* %arrayidx8, align 8
57+
store double undef, double* %arrayidx8, align 8
58+
br label %inner.latch
59+
60+
inner.latch: ; preds = %for.body6
61+
%inner.idx.inc = add nsw i64 %inner.idx, 1
62+
br i1 undef, label %inner.header, label %inner.exit
63+
64+
inner.exit: ; preds = %for.inc
65+
%outer.v = add nsw i64 %outer.idx, 1
66+
br label %outer.latch
67+
68+
outer.latch: ; preds = %for.end
69+
%outer.idx.inc = add nsw i64 %outer.idx, 1
70+
br i1 undef, label %outer.header, label %outer.exit
71+
72+
outer.exit: ; preds = %for.inc27
73+
%exit1.lcssa = phi i64 [ %outer.v, %outer.latch ]
74+
%exit2.lcssa = phi i64 [ %outer.idx.inc, %outer.latch ]
75+
ret void
76+
}
77+
78+
define void @test2(i1 %cond) {
79+
; CHECK-LABEL: @test2(
80+
; CHECK-NEXT: entry:
81+
; CHECK-NEXT: br i1 [[COND:%.*]], label [[INNER_HEADER_PREHEADER:%.*]], label [[OUTER_EXIT:%.*]]
82+
; CHECK: outer.header.preheader:
83+
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
84+
; CHECK: outer.header:
85+
; CHECK-NEXT: [[OUTER_IDX:%.*]] = phi i64 [ [[OUTER_IDX_INC:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[OUTER_HEADER_PREHEADER:%.*]] ]
86+
; CHECK-NEXT: [[ARRAYIDX8:%.*]] = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 [[OUTER_IDX]]
87+
; CHECK-NEXT: br label [[INNER_HEADER_SPLIT:%.*]]
88+
; CHECK: inner.header.preheader:
89+
; CHECK-NEXT: br label [[INNER_HEADER:%.*]]
90+
; CHECK: inner.header:
91+
; CHECK-NEXT: [[INNER_IDX:%.*]] = phi i64 [ [[TMP3:%.*]], [[INNER_LATCH_SPLIT:%.*]] ], [ 0, [[INNER_HEADER_PREHEADER]] ]
92+
; CHECK-NEXT: br label [[OUTER_HEADER_PREHEADER]]
93+
; CHECK: inner.header.split:
94+
; CHECK-NEXT: [[TMP0:%.*]] = load double, double* [[ARRAYIDX8]], align 8
95+
; CHECK-NEXT: store double undef, double* [[ARRAYIDX8]], align 8
96+
; CHECK-NEXT: br label [[INNER_LATCH:%.*]]
97+
; CHECK: inner.latch:
98+
; CHECK-NEXT: [[INNER_IDX_INC:%.*]] = add nsw i64 [[INNER_IDX]], 1
99+
; CHECK-NEXT: br label [[INNER_EXIT:%.*]]
100+
; CHECK: inner.latch.split:
101+
; CHECK-NEXT: [[TMP1:%.*]] = phi i64 [ [[OUTER_IDX_INC]], [[OUTER_LATCH]] ]
102+
; CHECK-NEXT: [[TMP2:%.*]] = phi i64 [ [[OUTER_V:%.*]], [[OUTER_LATCH]] ]
103+
; CHECK-NEXT: [[TMP3]] = add nsw i64 [[INNER_IDX]], 1
104+
; CHECK-NEXT: br i1 false, label [[INNER_HEADER]], label [[OUTER_EXIT_LOOPEXIT:%.*]]
105+
; CHECK: inner.exit:
106+
; CHECK-NEXT: [[OUTER_V]] = add nsw i64 [[OUTER_IDX]], 1
107+
; CHECK-NEXT: br label [[OUTER_LATCH]]
108+
; CHECK: outer.latch:
109+
; CHECK-NEXT: [[OUTER_IDX_INC]] = add nsw i64 [[OUTER_IDX]], 1
110+
; CHECK-NEXT: br i1 false, label [[OUTER_HEADER]], label [[INNER_LATCH_SPLIT]]
111+
; CHECK: outer.exit.loopexit:
112+
; CHECK-NEXT: [[OUTER_IDX_INC_LCSSA:%.*]] = phi i64 [ [[TMP1]], [[INNER_LATCH_SPLIT]] ]
113+
; CHECK-NEXT: [[OUTER_V_LCSSA:%.*]] = phi i64 [ [[TMP2]], [[INNER_LATCH_SPLIT]] ]
114+
; CHECK-NEXT: br label [[OUTER_EXIT]]
115+
; CHECK: outer.exit:
116+
; CHECK-NEXT: [[EXIT1_LCSSA:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_V_LCSSA]], [[OUTER_EXIT_LOOPEXIT]] ]
117+
; CHECK-NEXT: [[EXIT2_LCSSA:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[OUTER_IDX_INC_LCSSA]], [[OUTER_EXIT_LOOPEXIT]] ]
118+
; CHECK-NEXT: ret void
119+
;
120+
entry:
121+
br i1 %cond, label %outer.header, label %outer.exit
122+
123+
outer.header: ; preds = %for.inc27, %entry
124+
%outer.idx = phi i64 [ 0, %entry ], [ %outer.idx.inc, %outer.latch ]
125+
%arrayidx8 = getelementptr inbounds [5 x [5 x double]], [5 x [5 x double]]* @wdtdr, i64 0, i64 0, i64 %outer.idx
126+
br label %inner.header
127+
128+
inner.header: ; preds = %for.inc, %for.body
129+
%inner.idx = phi i64 [ 0, %outer.header ], [ %inner.idx.inc, %inner.latch]
130+
%0 = load double, double* %arrayidx8, align 8
131+
store double undef, double* %arrayidx8, align 8
132+
br label %inner.latch
133+
134+
inner.latch: ; preds = %for.body6
135+
%inner.idx.inc = add nsw i64 %inner.idx , 1
136+
br i1 undef, label %inner.header, label %inner.exit
137+
138+
inner.exit: ; preds = %for.inc
139+
%outer.v = add nsw i64 %outer.idx, 1
140+
br label %outer.latch
141+
142+
outer.latch: ; preds = %for.end
143+
%outer.idx.inc = add nsw i64 %outer.idx, 1
144+
br i1 undef, label %outer.header, label %outer.exit
145+
146+
outer.exit: ; preds = %for.inc27
147+
%exit1.lcssa = phi i64 [ 0, %entry ], [ %outer.v, %outer.latch ]
148+
%exit2.lcssa = phi i64 [ 0, %entry ], [ %outer.idx.inc, %outer.latch ]
149+
ret void
150+
}

0 commit comments

Comments
 (0)