1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include <utility>
17 #include <algorithm>
18 #include "unit_test.h"
19 #include "optimizer/optimizations/regalloc/interference_graph.h"
20
21 namespace panda::compiler {
22 class RegAllocInterferenceTest : public GraphTest {
23 };
24
25 namespace {
26 constexpr unsigned DEFAULT_CAPACITY1 = 10;
27 unsigned test_edges1[2][2] = {{0, 1}, {7, 4}};
__anon92a0531b0202(unsigned a, unsigned b) 28 auto IsInSet = [](unsigned a, unsigned b) {
29 for (int i = 0; i < 2; i++) {
30 if ((a == test_edges1[i][0] && b == test_edges1[i][1]) || (b == test_edges1[i][0] && a == test_edges1[i][1])) {
31 return true;
32 }
33 }
34 return false;
35 };
36 } // namespace
37
TEST_F(RegAllocInterferenceTest,Basic)38 TEST_F(RegAllocInterferenceTest, Basic)
39 {
40 GraphMatrix matrix(GetLocalAllocator());
41 matrix.SetCapacity(DEFAULT_CAPACITY1);
42 EXPECT_FALSE(matrix.AddEdge(0, 1));
43 EXPECT_FALSE(matrix.AddEdge(7, 4));
44 for (unsigned i = 0; i < DEFAULT_CAPACITY1; i++) {
45 for (unsigned j = 0; j < DEFAULT_CAPACITY1; j++) {
46 ASSERT_EQ(matrix.HasEdge(i, j), IsInSet(i, j));
47 }
48 }
49 EXPECT_GE(matrix.GetCapacity(), DEFAULT_CAPACITY1);
50 }
51
TEST_F(RegAllocInterferenceTest,BasicAfinity)52 TEST_F(RegAllocInterferenceTest, BasicAfinity)
53 {
54 GraphMatrix matrix(GetLocalAllocator());
55 matrix.SetCapacity(DEFAULT_CAPACITY1);
56 EXPECT_FALSE(matrix.AddAffinityEdge(0, 1));
57 EXPECT_FALSE(matrix.AddAffinityEdge(7, 4));
58 for (unsigned i = 0; i < DEFAULT_CAPACITY1; i++) {
59 for (unsigned j = 0; j < DEFAULT_CAPACITY1; j++) {
60 EXPECT_EQ(matrix.HasAffinityEdge(i, j), IsInSet(i, j));
61 }
62 }
63 EXPECT_GE(matrix.GetCapacity(), DEFAULT_CAPACITY1);
64 }
65
TEST_F(RegAllocInterferenceTest,BasicGraph)66 TEST_F(RegAllocInterferenceTest, BasicGraph)
67 {
68 InterferenceGraph gr(GetLocalAllocator());
69 gr.Reserve(DEFAULT_CAPACITY1);
70
71 EXPECT_EQ(gr.Size(), 0);
72 auto *node1 = gr.AllocNode();
73 EXPECT_EQ(gr.Size(), 1);
74 EXPECT_EQ(node1->GetNumber(), 0);
75
76 auto *node2 = gr.AllocNode();
77 EXPECT_EQ(gr.Size(), 2);
78 EXPECT_EQ(node2->GetNumber(), 1);
79 EXPECT_NE(node1, node2);
80 }
81
TEST_F(RegAllocInterferenceTest,GraphChordal)82 TEST_F(RegAllocInterferenceTest, GraphChordal)
83 {
84 InterferenceGraph gr(GetLocalAllocator());
85 gr.Reserve(DEFAULT_CAPACITY1);
86
87 EXPECT_TRUE(gr.IsChordal());
88
89 gr.AllocNode();
90 EXPECT_TRUE(gr.IsChordal());
91
92 gr.AllocNode();
93 EXPECT_TRUE(gr.IsChordal());
94
95 gr.AllocNode();
96 EXPECT_TRUE(gr.IsChordal());
97
98 gr.AddEdge(0, 1);
99 EXPECT_TRUE(gr.IsChordal());
100
101 gr.AddEdge(1, 2);
102 EXPECT_TRUE(gr.IsChordal());
103
104 gr.AddEdge(0, 2);
105 EXPECT_TRUE(gr.IsChordal());
106
107 // Make nonchordal
108 gr.AllocNode();
109 gr.AllocNode();
110 gr.AddEdge(3, 2);
111 gr.AddEdge(3, 4);
112 gr.AddEdge(0, 4);
113 EXPECT_FALSE(gr.IsChordal());
114 }
115
116 namespace {
117 const unsigned DEFAULT_CAPACITY2 = 5;
118 const unsigned DEFAULT_EDGES2 = 6;
119 ::std::pair<unsigned, unsigned> test_edges2[DEFAULT_EDGES2] = {{0, 1}, {1, 2}, {2, 0}, {0, 3}, {2, 3}, {3, 4}};
120
121 // To prevent adding "remove edge" interfaces to main code, edge removing is simulated via building new graph without
122 // it.
BuildSubgraph(InterferenceGraph & orig_gr,ArenaAllocator * alloc,::std::pair<unsigned,unsigned> * edges,unsigned count,ArenaVector<unsigned> & peo,unsigned peo_count)123 InterferenceGraph BuildSubgraph(InterferenceGraph &orig_gr, ArenaAllocator *alloc,
124 ::std::pair<unsigned, unsigned> *edges, unsigned count, ArenaVector<unsigned> &peo,
125 unsigned peo_count)
126 {
127 InterferenceGraph gr(alloc);
128 gr.Reserve(orig_gr.Size());
129
130 for (unsigned i = 0; i < count; i++) {
131 auto x = edges[i].first;
132 auto y = edges[i].second;
133 for (unsigned j = 0; j < peo_count; j++) {
134 if (x == peo[j] || y == peo[j]) {
135 continue;
136 }
137 }
138 gr.AddEdge(x, y);
139 }
140
141 return gr;
142 }
143 } // namespace
144
TEST_F(RegAllocInterferenceTest,LexBFSSimple)145 TEST_F(RegAllocInterferenceTest, LexBFSSimple)
146 {
147 InterferenceGraph gr(GetLocalAllocator());
148 gr.Reserve(2);
149
150 gr.AllocNode();
151 gr.AllocNode();
152 gr.AddEdge(0, 1);
153
154 auto peo = gr.LexBFS();
155 EXPECT_EQ(peo.size(), 2);
156 EXPECT_EQ(peo[0], 0);
157 EXPECT_EQ(peo[1], 1);
158 }
159
TEST_F(RegAllocInterferenceTest,LexBFS)160 TEST_F(RegAllocInterferenceTest, LexBFS)
161 {
162 InterferenceGraph gr(GetLocalAllocator());
163 gr.Reserve(DEFAULT_CAPACITY2);
164
165 gr.AllocNode();
166 gr.AllocNode();
167 gr.AllocNode();
168 gr.AllocNode();
169 gr.AllocNode();
170 for (unsigned i = 0; i < DEFAULT_EDGES2; i++) {
171 auto x = test_edges2[i].first;
172 auto y = test_edges2[i].second;
173 gr.AddEdge(x, y);
174 }
175
176 auto peo = gr.LexBFS();
177 EXPECT_EQ(peo.size(), DEFAULT_CAPACITY2);
178 std::reverse(peo.begin(), peo.end());
179
180 for (unsigned i = 0; i < (DEFAULT_CAPACITY2 - 1); i++) {
181 auto gr2 = BuildSubgraph(gr, GetLocalAllocator(), test_edges2, DEFAULT_EDGES2, peo, i);
182 EXPECT_TRUE(gr2.IsChordal());
183 }
184 }
185
TEST_F(RegAllocInterferenceTest,AssignColorsSimple)186 TEST_F(RegAllocInterferenceTest, AssignColorsSimple)
187 {
188 InterferenceGraph gr(GetLocalAllocator());
189 gr.Reserve(DEFAULT_CAPACITY2);
190
191 auto *nd0 = gr.AllocNode();
192 auto *nd1 = gr.AllocNode();
193 auto *nd2 = gr.AllocNode();
194 auto *nd3 = gr.AllocNode();
195 auto *nd4 = gr.AllocNode();
196 for (unsigned i = 0; i < DEFAULT_EDGES2; i++) {
197 auto x = test_edges2[i].first;
198 auto y = test_edges2[i].second;
199 gr.AddEdge(x, y);
200 }
201
202 EXPECT_EQ(gr.AssignColors<32>(3, 0), 3);
203 EXPECT_NE(nd0->GetColor(), nd1->GetColor());
204 EXPECT_NE(nd0->GetColor(), nd2->GetColor());
205 EXPECT_NE(nd0->GetColor(), nd3->GetColor());
206
207 EXPECT_NE(nd2->GetColor(), nd1->GetColor());
208 EXPECT_NE(nd2->GetColor(), nd3->GetColor());
209
210 EXPECT_NE(nd4->GetColor(), nd3->GetColor());
211 }
212
TEST_F(RegAllocInterferenceTest,AssignColors)213 TEST_F(RegAllocInterferenceTest, AssignColors)
214 {
215 const unsigned DEFAULT_CAPACITY = 11;
216 const unsigned DEFAULT_EDGES = 12;
217 const unsigned DEFAULT_AEDGES = 4;
218 ::std::pair<unsigned, unsigned> test_edges[DEFAULT_EDGES] = {{0, 1}, {1, 2}, {2, 0}, {0, 3}, {2, 3}, {3, 4},
219 {6, 5}, {5, 7}, {6, 7}, {9, 8}, {9, 10}, {8, 10}};
220 ::std::pair<unsigned, unsigned> test_aedges[DEFAULT_AEDGES] = {{3, 6}, {6, 9}, {2, 5}, {7, 8}};
221
222 InterferenceGraph gr(GetLocalAllocator());
223 gr.Reserve(DEFAULT_CAPACITY);
224
225 auto *nd0 = gr.AllocNode();
226 auto *nd1 = gr.AllocNode();
227 auto *nd2 = gr.AllocNode();
228 auto *nd3 = gr.AllocNode();
229 auto *nd4 = gr.AllocNode();
230 auto *nd5 = gr.AllocNode();
231 auto *nd6 = gr.AllocNode();
232 auto *nd7 = gr.AllocNode();
233 auto *nd8 = gr.AllocNode();
234 auto *nd9 = gr.AllocNode();
235 auto *nd10 = gr.AllocNode();
236
237 for (unsigned i = 0; i < DEFAULT_EDGES; i++) {
238 auto x = test_edges[i].first;
239 auto y = test_edges[i].second;
240 gr.AddEdge(x, y);
241 }
242 for (unsigned i = 0; i < DEFAULT_AEDGES; i++) {
243 auto x = test_aedges[i].first;
244 auto y = test_aedges[i].second;
245 gr.AddAffinityEdge(x, y);
246 }
247 auto &bias0 = gr.AddBias();
248 auto &bias1 = gr.AddBias();
249 auto &bias2 = gr.AddBias();
250
251 nd3->SetBias(0);
252 nd6->SetBias(0);
253 nd9->SetBias(0);
254 nd2->SetBias(1);
255 nd5->SetBias(1);
256 nd7->SetBias(2);
257 nd8->SetBias(2);
258
259 EXPECT_EQ(gr.AssignColors<32>(3, 0), 3);
260
261 // Check nodes inequality
262 EXPECT_NE(nd0->GetColor(), nd1->GetColor());
263 EXPECT_NE(nd0->GetColor(), nd2->GetColor());
264 EXPECT_NE(nd0->GetColor(), nd3->GetColor());
265
266 EXPECT_NE(nd2->GetColor(), nd1->GetColor());
267 EXPECT_NE(nd2->GetColor(), nd3->GetColor());
268
269 EXPECT_NE(nd4->GetColor(), nd3->GetColor());
270
271 EXPECT_NE(nd5->GetColor(), nd6->GetColor());
272 EXPECT_NE(nd7->GetColor(), nd6->GetColor());
273 EXPECT_NE(nd5->GetColor(), nd7->GetColor());
274
275 EXPECT_NE(nd8->GetColor(), nd9->GetColor());
276 EXPECT_NE(nd8->GetColor(), nd10->GetColor());
277 EXPECT_NE(nd9->GetColor(), nd10->GetColor());
278
279 // Check biases work
280 EXPECT_EQ(nd3->GetColor(), nd6->GetColor());
281 EXPECT_EQ(nd9->GetColor(), nd6->GetColor());
282
283 EXPECT_EQ(nd2->GetColor(), nd5->GetColor());
284 EXPECT_EQ(nd7->GetColor(), nd8->GetColor());
285
286 // Check biases values
287 EXPECT_NE(bias0.color, bias1.color);
288 EXPECT_NE(bias0.color, bias2.color);
289 }
290 } // namespace panda::compiler
291