Skip to content

Commit dfa8741

Browse files
hiradityahiraditya
committedSep 13, 2017
[GVNHoist] Factor out reachability to search for anticipable instructions quickly
Factor out the reachability such that multiple queries to find reachability of values are fast. This is based on finding the ANTIC points in the CFG which do not change during hoisting. The ANTIC points are basically the dominance-frontiers in the inverse graph. So we introduce a data structure (CHI nodes) to keep track of values flowing out of a basic block. We only do this for values with multiple occurrences in the function as they are the potential hoistable candidates. This patch allows us to hoist instructions to a basic block with >2 successors, as well as deal with infinite loops in a trivial way. Relevant test cases are added to show the functionality as well as regression fixes from PR32821. Regression from previous GVNHoist: We do not hoist fully redundant expressions because fully redundant expressions are already handled by NewGVN Differential Revision: https://reviews.llvm.org/D35918 Reviewers: dberlin, sebpop, gberry, llvm-svn: 313116
1 parent d9d2a89 commit dfa8741

10 files changed

+952
-400
lines changed
 

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

+418-288
Large diffs are not rendered by default.

‎llvm/test/Transforms/GVNHoist/hoist-more-than-two-branches.ll

+31
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
; RUN: opt -gvn-hoist -S < %s | FileCheck %s
2+
3+
; CHECK: store
4+
; CHECK-NOT: store
5+
6+
; Check that an instruction can be hoisted to a basic block
7+
; with more than two successors.
8+
9+
@G = external global i32, align 4
10+
11+
define void @foo(i32 %c1) {
12+
entry:
13+
switch i32 %c1, label %exit1 [
14+
i32 0, label %sw0
15+
i32 1, label %sw1
16+
]
17+
18+
sw0:
19+
store i32 1, i32* @G
20+
br label %exit
21+
22+
sw1:
23+
store i32 1, i32* @G
24+
br label %exit
25+
26+
exit1:
27+
store i32 1, i32* @G
28+
ret void
29+
exit:
30+
ret void
31+
}

‎llvm/test/Transforms/GVNHoist/hoist-mssa.ll

+1-1
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
; RUN: opt -S -gvn-hoist < %s | FileCheck %s
1+
; RUN: opt -S -gvn-hoist -newgvn < %s | FileCheck %s
22

33
; Check that store hoisting works: there should be only one store left.
44
; CHECK-LABEL: @getopt

‎llvm/test/Transforms/GVNHoist/hoist-newgvn.ll

+105
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
; RUN: opt -gvn-hoist -newgvn -S < %s | FileCheck %s
2+
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
3+
target triple = "x86_64-unknown-linux-gnu"
4+
5+
@GlobalVar = internal global float 1.000000e+00
6+
7+
; Check that we hoist load and scalar expressions in dominator.
8+
; CHECK-LABEL: @dominatorHoisting
9+
; CHECK: load
10+
; CHECK: load
11+
; CHECK: fsub
12+
; CHECK: fmul
13+
; CHECK: load
14+
; CHECK: fsub
15+
; CHECK: fmul
16+
; CHECK-NOT: load
17+
; CHECK-NOT: fmul
18+
; CHECK-NOT: fsub
19+
define float @dominatorHoisting(float %d, float* %min, float* %max, float* %a) {
20+
entry:
21+
%div = fdiv float 1.000000e+00, %d
22+
%0 = load float, float* %min, align 4
23+
%1 = load float, float* %a, align 4
24+
%sub = fsub float %0, %1
25+
%mul = fmul float %sub, %div
26+
%2 = load float, float* %max, align 4
27+
%sub1 = fsub float %2, %1
28+
%mul2 = fmul float %sub1, %div
29+
%cmp = fcmp oge float %div, 0.000000e+00
30+
br i1 %cmp, label %if.then, label %if.end
31+
32+
if.then: ; preds = %entry
33+
%3 = load float, float* %max, align 4
34+
%4 = load float, float* %a, align 4
35+
%sub3 = fsub float %3, %4
36+
%mul4 = fmul float %sub3, %div
37+
%5 = load float, float* %min, align 4
38+
%sub5 = fsub float %5, %4
39+
%mul6 = fmul float %sub5, %div
40+
br label %if.end
41+
42+
if.end: ; preds = %entry
43+
%p1 = phi float [ %mul4, %if.then ], [ 0.000000e+00, %entry ]
44+
%p2 = phi float [ %mul6, %if.then ], [ 0.000000e+00, %entry ]
45+
46+
%x = fadd float %p1, %mul2
47+
%y = fadd float %p2, %mul
48+
%z = fadd float %x, %y
49+
ret float %z
50+
}
51+
52+
; Check that we hoist load and scalar expressions in dominator.
53+
; CHECK-LABEL: @domHoisting
54+
; CHECK: load
55+
; CHECK: load
56+
; CHECK: fsub
57+
; CHECK: fmul
58+
; CHECK: load
59+
; CHECK: fsub
60+
; CHECK: fmul
61+
; CHECK-NOT: load
62+
; CHECK-NOT: fmul
63+
; CHECK-NOT: fsub
64+
define float @domHoisting(float %d, float* %min, float* %max, float* %a) {
65+
entry:
66+
%div = fdiv float 1.000000e+00, %d
67+
%0 = load float, float* %min, align 4
68+
%1 = load float, float* %a, align 4
69+
%sub = fsub float %0, %1
70+
%mul = fmul float %sub, %div
71+
%2 = load float, float* %max, align 4
72+
%sub1 = fsub float %2, %1
73+
%mul2 = fmul float %sub1, %div
74+
%cmp = fcmp oge float %div, 0.000000e+00
75+
br i1 %cmp, label %if.then, label %if.else
76+
77+
if.then:
78+
%3 = load float, float* %max, align 4
79+
%4 = load float, float* %a, align 4
80+
%sub3 = fsub float %3, %4
81+
%mul4 = fmul float %sub3, %div
82+
%5 = load float, float* %min, align 4
83+
%sub5 = fsub float %5, %4
84+
%mul6 = fmul float %sub5, %div
85+
br label %if.end
86+
87+
if.else:
88+
%6 = load float, float* %max, align 4
89+
%7 = load float, float* %a, align 4
90+
%sub9 = fsub float %6, %7
91+
%mul10 = fmul float %sub9, %div
92+
%8 = load float, float* %min, align 4
93+
%sub12 = fsub float %8, %7
94+
%mul13 = fmul float %sub12, %div
95+
br label %if.end
96+
97+
if.end:
98+
%p1 = phi float [ %mul4, %if.then ], [ %mul10, %if.else ]
99+
%p2 = phi float [ %mul6, %if.then ], [ %mul13, %if.else ]
100+
101+
%x = fadd float %p1, %mul2
102+
%y = fadd float %p2, %mul
103+
%z = fadd float %x, %y
104+
ret float %z
105+
}

‎llvm/test/Transforms/GVNHoist/hoist-pr20242.ll

+4-1
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,7 @@
1-
; RUN: opt -gvn-hoist -S < %s | FileCheck %s
1+
; RUN: opt -gvn-hoist -newgvn -gvn-hoist -S < %s | FileCheck %s
2+
; Test to demonstrate that newgvn creates opportunities for
3+
; more gvn-hoist when sibling branches contain identical expressions.
4+
25
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
36
target triple = "x86_64-unknown-linux-gnu"
47

‎llvm/test/Transforms/GVNHoist/hoist-pr28933.ll

+1-2
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,8 @@
1-
; RUN: opt -S -gvn-hoist -verify-memoryssa < %s | FileCheck %s
1+
; RUN: opt -S -gvn-hoist -verify-memoryssa -newgvn < %s | FileCheck %s
22

33
; Check that we end up with one load and one store, in the right order
44
; CHECK-LABEL: define void @test_it(
55
; CHECK: store
6-
; CHECK-NEXT: load
76
; CHECK-NOT: store
87
; CHECK-NOT: load
98

‎llvm/test/Transforms/GVNHoist/hoist-recursive-geps.ll

+7-4
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,18 @@
1-
; RUN: opt -gvn-hoist -S < %s | FileCheck %s
1+
; RUN: opt -gvn-hoist -newgvn -gvn-hoist -S < %s | FileCheck %s
2+
3+
; Check that recursive GEPs are hoisted. Since hoisting creates
4+
; fully redundant instructions, newgvn is run to remove them which then
5+
; creates more opportunites for hoisting.
26

3-
; Check that recursive GEPs are hoisted.
47
; CHECK-LABEL: @fun
5-
; CHECK: fdiv
68
; CHECK: load
9+
; CHECK: fdiv
710
; CHECK: load
811
; CHECK: load
912
; CHECK: load
1013
; CHECK: fsub
11-
; CHECK: fsub
1214
; CHECK: fmul
15+
; CHECK: fsub
1316
; CHECK: fmul
1417
; CHECK-NOT: fsub
1518
; CHECK-NOT: fmul

‎llvm/test/Transforms/GVNHoist/hoist.ll

+4-104
Original file line numberDiff line numberDiff line change
@@ -8,8 +8,8 @@ target triple = "x86_64-unknown-linux-gnu"
88
;
99
; CHECK-LABEL: @scalarsHoisting
1010
; CHECK: fsub
11-
; CHECK: fsub
1211
; CHECK: fmul
12+
; CHECK: fsub
1313
; CHECK: fmul
1414
; CHECK-NOT: fmul
1515
; CHECK-NOT: fsub
@@ -48,8 +48,8 @@ if.end: ; preds = %if.else, %if.then
4848
; CHECK: load
4949
; CHECK: load
5050
; CHECK: fsub
51-
; CHECK: fsub
5251
; CHECK: fmul
52+
; CHECK: fsub
5353
; CHECK: fmul
5454
; CHECK-NOT: load
5555
; CHECK-NOT: fmul
@@ -148,8 +148,8 @@ if.end: ; preds = %if.else, %if.then
148148
; CHECK: load
149149
; CHECK: load
150150
; CHECK: fsub
151-
; CHECK: fsub
152151
; CHECK: fmul
152+
; CHECK: fsub
153153
; CHECK: fmul
154154
; CHECK-NOT: load
155155
; CHECK-NOT: fmul
@@ -265,8 +265,8 @@ if.end:
265265
; CHECK: load
266266
; CHECK: load
267267
; CHECK: fsub
268-
; CHECK: fsub
269268
; CHECK: fmul
269+
; CHECK: fsub
270270
; CHECK: fmul
271271
; CHECK-NOT: load
272272
; CHECK-NOT: fmul
@@ -304,106 +304,6 @@ if.end: ; preds = %entry
304304
ret float %z
305305
}
306306

307-
; Check that we hoist load and scalar expressions in dominator.
308-
; CHECK-LABEL: @dominatorHoisting
309-
; CHECK: load
310-
; CHECK: load
311-
; CHECK: fsub
312-
; CHECK: fmul
313-
; CHECK: load
314-
; CHECK: fsub
315-
; CHECK: fmul
316-
; CHECK-NOT: load
317-
; CHECK-NOT: fmul
318-
; CHECK-NOT: fsub
319-
define float @dominatorHoisting(float %d, float* %min, float* %max, float* %a) {
320-
entry:
321-
%div = fdiv float 1.000000e+00, %d
322-
%0 = load float, float* %min, align 4
323-
%1 = load float, float* %a, align 4
324-
%sub = fsub float %0, %1
325-
%mul = fmul float %sub, %div
326-
%2 = load float, float* %max, align 4
327-
%sub1 = fsub float %2, %1
328-
%mul2 = fmul float %sub1, %div
329-
%cmp = fcmp oge float %div, 0.000000e+00
330-
br i1 %cmp, label %if.then, label %if.end
331-
332-
if.then: ; preds = %entry
333-
%3 = load float, float* %max, align 4
334-
%4 = load float, float* %a, align 4
335-
%sub3 = fsub float %3, %4
336-
%mul4 = fmul float %sub3, %div
337-
%5 = load float, float* %min, align 4
338-
%sub5 = fsub float %5, %4
339-
%mul6 = fmul float %sub5, %div
340-
br label %if.end
341-
342-
if.end: ; preds = %entry
343-
%p1 = phi float [ %mul4, %if.then ], [ 0.000000e+00, %entry ]
344-
%p2 = phi float [ %mul6, %if.then ], [ 0.000000e+00, %entry ]
345-
346-
%x = fadd float %p1, %mul2
347-
%y = fadd float %p2, %mul
348-
%z = fadd float %x, %y
349-
ret float %z
350-
}
351-
352-
; Check that we hoist load and scalar expressions in dominator.
353-
; CHECK-LABEL: @domHoisting
354-
; CHECK: load
355-
; CHECK: load
356-
; CHECK: fsub
357-
; CHECK: fmul
358-
; CHECK: load
359-
; CHECK: fsub
360-
; CHECK: fmul
361-
; CHECK-NOT: load
362-
; CHECK-NOT: fmul
363-
; CHECK-NOT: fsub
364-
define float @domHoisting(float %d, float* %min, float* %max, float* %a) {
365-
entry:
366-
%div = fdiv float 1.000000e+00, %d
367-
%0 = load float, float* %min, align 4
368-
%1 = load float, float* %a, align 4
369-
%sub = fsub float %0, %1
370-
%mul = fmul float %sub, %div
371-
%2 = load float, float* %max, align 4
372-
%sub1 = fsub float %2, %1
373-
%mul2 = fmul float %sub1, %div
374-
%cmp = fcmp oge float %div, 0.000000e+00
375-
br i1 %cmp, label %if.then, label %if.else
376-
377-
if.then:
378-
%3 = load float, float* %max, align 4
379-
%4 = load float, float* %a, align 4
380-
%sub3 = fsub float %3, %4
381-
%mul4 = fmul float %sub3, %div
382-
%5 = load float, float* %min, align 4
383-
%sub5 = fsub float %5, %4
384-
%mul6 = fmul float %sub5, %div
385-
br label %if.end
386-
387-
if.else:
388-
%6 = load float, float* %max, align 4
389-
%7 = load float, float* %a, align 4
390-
%sub9 = fsub float %6, %7
391-
%mul10 = fmul float %sub9, %div
392-
%8 = load float, float* %min, align 4
393-
%sub12 = fsub float %8, %7
394-
%mul13 = fmul float %sub12, %div
395-
br label %if.end
396-
397-
if.end:
398-
%p1 = phi float [ %mul4, %if.then ], [ %mul10, %if.else ]
399-
%p2 = phi float [ %mul6, %if.then ], [ %mul13, %if.else ]
400-
401-
%x = fadd float %p1, %mul2
402-
%y = fadd float %p2, %mul
403-
%z = fadd float %x, %y
404-
ret float %z
405-
}
406-
407307
; Check that we do not hoist loads past stores within a same basic block.
408308
; CHECK-LABEL: @noHoistInSingleBBWithStore
409309
; CHECK: load

0 commit comments

Comments
 (0)
Please sign in to comment.