1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
; Check that the default heuristic use the local cse constraints.
; RUN: opt -S -passes=reassociate,early-cse %s -o - | FileCheck %s -check-prefix=LOCAL_CSE
; RUN: opt -S -passes=reassociate,early-cse %s -reassociate-use-cse-local=true -o - | FileCheck %s -check-prefix=LOCAL_CSE
; RUN: opt -S -passes=reassociate,early-cse %s -reassociate-use-cse-local=false -o - | FileCheck %s -check-prefix=CSE
; Check that when we use the heuristic to expose only local (to the first
; encountered block) CSE opportunities, we choose the right sub expression
; to expose.
;
; In these example we have three chains of expressions:
; chain a: inv1, val_bb2, inv2, inv4
; chain b: inv1, val_bb2, inv2, inv5
; chain c: inv1, val_bb2, inv3
;
; The CSE-able pairs with there respective occurrences are:
; inv1, val_bb2: 3
; inv1, inv2: 2
;
; val_bb2 is anchored in bb2 but inv1 and inv2 can start in bb1.
; With the local heuristic we will push inv1, inv2 at the beginning
; of chain_a and chain_b.
; With the non-local heuristic we will push inv1, val_bb2.
define void @chain_spanning_several_blocks(i64 %inv1, i64 %inv2, i64 %inv3, i64 %inv4, i64 %inv5) {
; LOCAL_CSE-LABEL: define void @chain_spanning_several_blocks
; LOCAL_CSE-SAME: (i64 [[INV1:%.*]], i64 [[INV2:%.*]], i64 [[INV3:%.*]], i64 [[INV4:%.*]], i64 [[INV5:%.*]]) {
; LOCAL_CSE-NEXT: bb1:
; LOCAL_CSE-NEXT: [[CHAIN_A0:%.*]] = add nuw i64 [[INV2]], [[INV1]]
; LOCAL_CSE-NEXT: br label [[BB2:%.*]]
; LOCAL_CSE: bb2:
; LOCAL_CSE-NEXT: [[VAL_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT: [[CHAIN_A1:%.*]] = add nuw i64 [[CHAIN_A0]], [[INV4]]
; LOCAL_CSE-NEXT: [[CHAIN_A2:%.*]] = add nuw i64 [[CHAIN_A1]], [[VAL_BB2]]
; LOCAL_CSE-NEXT: [[CHAIN_B1:%.*]] = add nuw i64 [[CHAIN_A0]], [[INV5]]
; LOCAL_CSE-NEXT: [[CHAIN_B2:%.*]] = add nuw i64 [[CHAIN_B1]], [[VAL_BB2]]
; LOCAL_CSE-NEXT: [[CHAIN_C0:%.*]] = add nuw i64 [[INV3]], [[INV1]]
; LOCAL_CSE-NEXT: [[CHAIN_C1:%.*]] = add nuw i64 [[CHAIN_C0]], [[VAL_BB2]]
; LOCAL_CSE-NEXT: call void @keep_alive(i64 [[CHAIN_A2]])
; LOCAL_CSE-NEXT: call void @keep_alive(i64 [[CHAIN_B2]])
; LOCAL_CSE-NEXT: call void @keep_alive(i64 [[CHAIN_C1]])
; LOCAL_CSE-NEXT: ret void
;
; CSE-LABEL: define void @chain_spanning_several_blocks
; CSE-SAME: (i64 [[INV1:%.*]], i64 [[INV2:%.*]], i64 [[INV3:%.*]], i64 [[INV4:%.*]], i64 [[INV5:%.*]]) {
; CSE-NEXT: bb1:
; CSE-NEXT: br label [[BB2:%.*]]
; CSE: bb2:
; CSE-NEXT: [[VAL_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT: [[CHAIN_A0:%.*]] = add nuw i64 [[VAL_BB2]], [[INV1]]
; CSE-NEXT: [[CHAIN_A1:%.*]] = add nuw i64 [[CHAIN_A0]], [[INV2]]
; CSE-NEXT: [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV4]]
; CSE-NEXT: [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV5]]
; CSE-NEXT: [[CHAIN_C1:%.*]] = add nuw i64 [[CHAIN_A0]], [[INV3]]
; CSE-NEXT: call void @keep_alive(i64 [[CHAIN_A2]])
; CSE-NEXT: call void @keep_alive(i64 [[CHAIN_B2]])
; CSE-NEXT: call void @keep_alive(i64 [[CHAIN_C1]])
; CSE-NEXT: ret void
;
bb1:
%chain_a0 = add nuw nsw i64 %inv1, %inv2
br label %bb2
bb2:
%val_bb2 = call i64 @get_val()
%chain_a1 = add nuw nsw i64 %chain_a0, %val_bb2
%chain_a2 = add nuw nsw i64 %chain_a1, %inv4
%chain_b0 = add nuw nsw i64 %val_bb2, %inv1
%chain_b1 = add nuw nsw i64 %chain_b0, %inv2
%chain_b2 = add nuw nsw i64 %chain_b1, %inv5
%chain_c0 = add nuw nsw i64 %val_bb2, %inv3
%chain_c1 = add nuw nsw i64 %chain_c0, %inv1
call void @keep_alive(i64 %chain_a2)
call void @keep_alive(i64 %chain_b2)
call void @keep_alive(i64 %chain_c1)
ret void
}
; Same as @chain_spanning_several_blocks, but with values that are all anchored
; on the non-entry block.
; I.e., same pair map as previous but with invX_bbY instead of invX.
; Note: Although %inv1_bb0 is anchored in the entry block, it doesn't constrain
; the sub expressions on the entry block because we need to see at least two
; values to be able to form a sub-expression and thus only the second one
; add a constraint.
define void @chain_spanning_several_blocks_no_entry_anchor() {
; LOCAL_CSE-LABEL: define void @chain_spanning_several_blocks_no_entry_anchor() {
; LOCAL_CSE-NEXT: bb0:
; LOCAL_CSE-NEXT: [[INV2_BB0:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT: br label [[BB1:%.*]]
; LOCAL_CSE: bb1:
; LOCAL_CSE-NEXT: [[INV1_BB1:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT: [[CHAIN_A0:%.*]] = add nuw i64 [[INV1_BB1]], [[INV2_BB0]]
; LOCAL_CSE-NEXT: br label [[BB2:%.*]]
; LOCAL_CSE: bb2:
; LOCAL_CSE-NEXT: [[INV3_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT: [[INV4_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT: [[INV5_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT: [[VAL_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT: [[CHAIN_A1:%.*]] = add nuw i64 [[CHAIN_A0]], [[INV4_BB2]]
; LOCAL_CSE-NEXT: [[CHAIN_A2:%.*]] = add nuw i64 [[CHAIN_A1]], [[VAL_BB2]]
; LOCAL_CSE-NEXT: [[CHAIN_B1:%.*]] = add nuw i64 [[CHAIN_A0]], [[INV5_BB2]]
; LOCAL_CSE-NEXT: [[CHAIN_B2:%.*]] = add nuw i64 [[CHAIN_B1]], [[VAL_BB2]]
; LOCAL_CSE-NEXT: [[CHAIN_C0:%.*]] = add nuw i64 [[VAL_BB2]], [[INV1_BB1]]
; LOCAL_CSE-NEXT: [[CHAIN_C1:%.*]] = add nuw i64 [[CHAIN_C0]], [[INV3_BB2]]
; LOCAL_CSE-NEXT: call void @keep_alive(i64 [[CHAIN_A2]])
; LOCAL_CSE-NEXT: call void @keep_alive(i64 [[CHAIN_B2]])
; LOCAL_CSE-NEXT: call void @keep_alive(i64 [[CHAIN_C1]])
; LOCAL_CSE-NEXT: ret void
;
; CSE-LABEL: define void @chain_spanning_several_blocks_no_entry_anchor() {
; CSE-NEXT: bb0:
; CSE-NEXT: [[INV2_BB0:%.*]] = call i64 @get_val()
; CSE-NEXT: br label [[BB1:%.*]]
; CSE: bb1:
; CSE-NEXT: [[INV1_BB1:%.*]] = call i64 @get_val()
; CSE-NEXT: br label [[BB2:%.*]]
; CSE: bb2:
; CSE-NEXT: [[INV3_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT: [[INV4_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT: [[INV5_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT: [[VAL_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT: [[CHAIN_A0:%.*]] = add nuw i64 [[VAL_BB2]], [[INV1_BB1]]
; CSE-NEXT: [[CHAIN_A1:%.*]] = add nuw i64 [[CHAIN_A0]], [[INV2_BB0]]
; CSE-NEXT: [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV4_BB2]]
; CSE-NEXT: [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV5_BB2]]
; CSE-NEXT: [[CHAIN_C1:%.*]] = add nuw i64 [[CHAIN_A0]], [[INV3_BB2]]
; CSE-NEXT: call void @keep_alive(i64 [[CHAIN_A2]])
; CSE-NEXT: call void @keep_alive(i64 [[CHAIN_B2]])
; CSE-NEXT: call void @keep_alive(i64 [[CHAIN_C1]])
; CSE-NEXT: ret void
;
bb0:
%inv2_bb0 = call i64 @get_val()
br label %bb1
bb1:
%inv1_bb1 = call i64 @get_val()
%chain_a0 = add nuw nsw i64 %inv1_bb1, %inv2_bb0
br label %bb2
bb2:
%inv3_bb2 = call i64 @get_val()
%inv4_bb2 = call i64 @get_val()
%inv5_bb2 = call i64 @get_val()
%val_bb2 = call i64 @get_val()
%chain_a1 = add nuw nsw i64 %chain_a0, %val_bb2
%chain_a2 = add nuw nsw i64 %chain_a1, %inv4_bb2
%chain_b0 = add nuw nsw i64 %val_bb2, %inv1_bb1
%chain_b1 = add nuw nsw i64 %chain_b0, %inv2_bb0
%chain_b2 = add nuw nsw i64 %chain_b1, %inv5_bb2
%chain_c0 = add nuw nsw i64 %val_bb2, %inv3_bb2
%chain_c1 = add nuw nsw i64 %chain_c0, %inv1_bb1
call void @keep_alive(i64 %chain_a2)
call void @keep_alive(i64 %chain_b2)
call void @keep_alive(i64 %chain_c1)
ret void
}
declare i64 @get_val()
declare void @keep_alive(i64)
|
