1 /* 2 * Copyright (c) 2024 Shenzhen Kaihong Digital Industry Development 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 * Copyright (c) 2024 Huawei Device Co., Ltd. 16 * Licensed under the Apache License, Version 2.0 (the "License"); 17 * you may not use this file except in compliance with the License. 18 * You may obtain a copy of the License at 19 20 * http://www.apache.org/licenses/LICENSE-2.0 21 * 22 * Unless required by applicable law or agreed to in writing, software 23 * distributed under the License is distributed on an "AS IS" BASIS, 24 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 25 * See the License for the specific language governing permissions and 26 * limitations under the License. 27 */ 28 29 #include <cstddef> 30 #include <gtest/gtest.h> 31 #include <sstream> 32 33 #include "graph_test.h" 34 #include "optimizer/analysis/liveness_analyzer.h" 35 #include "optimizer/ir/inst.h" 36 #include "optimizer/optimizations/regalloc/interference_graph.h" 37 38 using namespace testing::ext; 39 40 namespace panda::compiler { 41 class RegAllocInterferenceTest : public testing::Test { 42 public: SetUpTestCase(void)43 static void SetUpTestCase(void) {}; TearDownTestCase(void)44 static void TearDownTestCase(void) {}; SetUp()45 void SetUp() {}; TearDown()46 void TearDown() {}; 47 IsInSet(unsigned expect_edges[][2],size_t count,unsigned a,unsigned b)48 auto IsInSet(unsigned expect_edges[][2], size_t count, unsigned a, unsigned b) 49 { 50 ASSERT(expect_edges != nullptr); 51 for (size_t i = 0; i < count; i++) { 52 if ((a == expect_edges[i][0] && b == expect_edges[i][1]) || 53 (b == expect_edges[i][0] && a == expect_edges[i][1])) { 54 return true; 55 } 56 } 57 return false; 58 }; 59 60 // To prevent adding "remove edge" interfaces to main code, 61 // edge removing is simulated via building new graph without it. BuildSubgraph(InterferenceGraph & orig_ig,ArenaAllocator * alloc,std::pair<unsigned,unsigned> * edges,size_t count,ArenaVector<unsigned> & peo,size_t peo_count)62 InterferenceGraph BuildSubgraph(InterferenceGraph &orig_ig, ArenaAllocator *alloc, 63 std::pair<unsigned, unsigned> *edges, size_t count, 64 ArenaVector<unsigned> &peo, size_t peo_count) 65 { 66 InterferenceGraph ig(alloc); 67 ig.Reserve(orig_ig.Size()); 68 69 for (unsigned i = 0; i < count; i++) { 70 auto x = edges[i].first; 71 auto y = edges[i].second; 72 for (unsigned j = 0; j < peo_count; j++) { 73 if (x == peo[j] || y == peo[j]) { 74 continue; 75 } 76 } 77 ig.AddEdge(x, y); 78 } 79 80 return ig; 81 } 82 }; 83 84 /** 85 * @tc.name: reg_alloc_interference_test_001 86 * @tc.desc: Verify the AddEdge function of GraphMatrix. 87 * @tc.type: FUNC 88 * @tc.require: 89 */ 90 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_001, TestSize.Level1) 91 { 92 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 93 GraphMatrix matrix(&allocator); 94 matrix.SetCapacity(10); 95 96 unsigned test_edges[2][2] = {{0, 1}, {7, 4}}; 97 EXPECT_FALSE(matrix.AddEdge(0, 1)); 98 EXPECT_FALSE(matrix.AddEdge(7, 4)); 99 for (unsigned i = 0; i < 10; i++) { 100 for (unsigned j = 0; j < 10; j++) { 101 EXPECT_EQ(matrix.HasEdge(i, j), IsInSet(test_edges, 2, i, j)); 102 } 103 } 104 EXPECT_GE(matrix.GetCapacity(), 10); 105 } 106 107 /** 108 * @tc.name: reg_alloc_interference_test_002 109 * @tc.desc: Verify the AddAffinityEdge function of GraphMatrix. 110 * @tc.type: FUNC 111 * @tc.require: 112 */ 113 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_002, TestSize.Level1) 114 { 115 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 116 GraphMatrix matrix(&allocator); 117 matrix.SetCapacity(10); 118 119 unsigned test_edges[2][2] = {{0, 1}, {7, 4}}; 120 EXPECT_FALSE(matrix.AddAffinityEdge(0, 1)); 121 EXPECT_FALSE(matrix.AddAffinityEdge(7, 4)); 122 for (unsigned i = 0; i < 10; i++) { 123 for (unsigned j = 0; j < 10; j++) { 124 EXPECT_EQ(matrix.HasAffinityEdge(i, j), IsInSet(test_edges, 2, i, j)); 125 } 126 } 127 EXPECT_GE(matrix.GetCapacity(), 10); 128 } 129 130 /** 131 * @tc.name: reg_alloc_interference_test_003 132 * @tc.desc: Verify the GetNumber function of ColorNode. 133 * @tc.type: FUNC 134 * @tc.require: 135 */ 136 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_003, TestSize.Level1) 137 { 138 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 139 ColorNode node1(0, allocator.Adapter()); 140 EXPECT_EQ(node1.GetNumber(), 0); 141 ColorNode node2(1, allocator.Adapter()); 142 EXPECT_EQ(node2.GetNumber(), 1); 143 } 144 145 /** 146 * @tc.name: reg_alloc_interference_test_004 147 * @tc.desc: Verify the SetColor function of ColorNode. 148 * @tc.type: FUNC 149 * @tc.require: 150 */ 151 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_004, TestSize.Level1) 152 { 153 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 154 ColorNode node(0, allocator.Adapter()); 155 node.SetColor(0); 156 EXPECT_EQ(node.GetColor(), 0); 157 node.SetColor(1); 158 EXPECT_EQ(node.GetColor(), 1); 159 } 160 161 /** 162 * @tc.name: reg_alloc_interference_test_005 163 * @tc.desc: Verify the SetFixedColor function of ColorNode. 164 * @tc.type: FUNC 165 * @tc.require: 166 */ 167 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_005, TestSize.Level1) 168 { 169 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 170 ColorNode node(0, allocator.Adapter()); 171 node.SetFixedColor(1, true); 172 EXPECT_EQ(node.GetColor(), 1); 173 EXPECT_TRUE(node.IsFixedColor()); 174 EXPECT_TRUE(node.IsPhysical()); 175 node.SetFixedColor(2, false); 176 EXPECT_EQ(node.GetColor(), 2); 177 EXPECT_TRUE(node.IsFixedColor()); 178 EXPECT_FALSE(node.IsPhysical()); 179 } 180 181 /** 182 * @tc.name: reg_alloc_interference_test_006 183 * @tc.desc: Verify the SetBias function of ColorNode. 184 * @tc.type: FUNC 185 * @tc.require: 186 */ 187 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_006, TestSize.Level1) 188 { 189 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 190 ColorNode node(0, allocator.Adapter()); 191 node.SetBias(3); 192 EXPECT_EQ(node.GetBias(), 3); 193 EXPECT_TRUE(node.HasBias()); 194 node.SetBias(ColorNode::NO_BIAS); 195 EXPECT_EQ(node.GetBias(), ColorNode::NO_BIAS); 196 EXPECT_FALSE(node.HasBias()); 197 } 198 199 /** 200 * @tc.name: reg_alloc_interference_test_007 201 * @tc.desc: Verify the Assign function of ColorNode. 202 * @tc.type: FUNC 203 * @tc.require: 204 */ 205 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_007, TestSize.Level1) 206 { 207 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 208 LifeIntervals intervals(&allocator); 209 ColorNode node(0, allocator.Adapter()); 210 node.Assign(&intervals); 211 EXPECT_EQ(node.GetLifeIntervals(), &intervals); 212 } 213 214 /** 215 * @tc.name: reg_alloc_interference_test_008 216 * @tc.desc: Verify the AddCallsite function of ColorNode. 217 * @tc.type: FUNC 218 * @tc.require: 219 */ 220 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_008, TestSize.Level1) 221 { 222 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 223 ColorNode node(0, allocator.Adapter()); 224 EXPECT_EQ(node.GetCallsiteIntersectCount(), 0); 225 node.AddCallsite(2); 226 EXPECT_EQ(node.GetCallsiteIntersectCount(), 1); 227 node.AddCallsite(7); 228 EXPECT_EQ(node.GetCallsiteIntersectCount(), 2); 229 } 230 231 /** 232 * @tc.name: reg_alloc_interference_test_009 233 * @tc.desc: Verify the AllocNode function of InterferenceGraph. 234 * @tc.type: FUNC 235 * @tc.require: 236 */ 237 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_009, TestSize.Level1) 238 { 239 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 240 InterferenceGraph ig(&allocator); 241 ig.Reserve(10); 242 243 EXPECT_EQ(ig.Size(), 0); 244 auto *node1 = ig.AllocNode(); 245 EXPECT_EQ(ig.Size(), 1); 246 EXPECT_EQ(node1->GetNumber(), 0); 247 248 auto *node2 = ig.AllocNode(); 249 EXPECT_EQ(ig.Size(), 2); 250 EXPECT_EQ(node2->GetNumber(), 1); 251 EXPECT_NE(node1, node2); 252 } 253 254 /** 255 * @tc.name: reg_alloc_interference_test_010 256 * @tc.desc: Verify the AddBias function of InterferenceGraph. 257 * @tc.type: FUNC 258 * @tc.require: 259 */ 260 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_010, TestSize.Level1) 261 { 262 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 263 InterferenceGraph ig(&allocator); 264 EXPECT_EQ(ig.GetBiasCount(), 0); 265 ig.AddBias(); 266 EXPECT_EQ(ig.GetBiasCount(), 1); 267 ig.AddBias(); 268 EXPECT_EQ(ig.GetBiasCount(), 2); 269 } 270 271 /** 272 * @tc.name: reg_alloc_interference_test_011 273 * @tc.desc: Verify the LexBFS function of InterferenceGraph in simple case. 274 * @tc.type: FUNC 275 * @tc.require: 276 */ 277 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_011, TestSize.Level1) 278 { 279 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 280 InterferenceGraph ig(&allocator); 281 ig.Reserve(2); 282 283 ig.AllocNode(); 284 ig.AllocNode(); 285 ig.AddEdge(0, 1); 286 287 auto peo = ig.LexBFS(); 288 EXPECT_EQ(peo.size(), 2); 289 EXPECT_EQ(peo[0], 0); 290 EXPECT_EQ(peo[1], 1); 291 } 292 293 /** 294 * @tc.name: reg_alloc_interference_test_012 295 * @tc.desc: Verify the LexBFS function of InterferenceGraph. 296 * @tc.type: FUNC 297 * @tc.require: 298 */ 299 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_012, TestSize.Level1) 300 { 301 const size_t DEFAULT_CAPACITY = 5; 302 const size_t DEFAULT_EDGES = 6; 303 std::pair<unsigned, unsigned> test_edges[DEFAULT_EDGES] = {{0, 1}, {1, 2}, {2, 0}, {0, 3}, {2, 3}, {3, 4}}; 304 305 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 306 InterferenceGraph ig(&allocator); 307 ig.Reserve(DEFAULT_CAPACITY); 308 309 for (size_t i = 0; i < DEFAULT_CAPACITY; i++) { 310 ig.AllocNode(); 311 } 312 313 for (size_t i = 0; i < DEFAULT_CAPACITY; i++) { 314 auto x = test_edges[i].first; 315 auto y = test_edges[i].second; 316 ig.AddEdge(x, y); 317 } 318 319 auto peo = ig.LexBFS(); 320 EXPECT_EQ(peo.size(), DEFAULT_CAPACITY); 321 std::reverse(peo.begin(), peo.end()); 322 323 for (size_t i = 0; i < DEFAULT_CAPACITY - 1; i++) { 324 auto ig2 = BuildSubgraph(ig, &allocator, test_edges, DEFAULT_EDGES, peo, i); 325 EXPECT_TRUE(ig2.IsChordal()); 326 } 327 } 328 329 /** 330 * @tc.name: reg_alloc_interference_test_013 331 * @tc.desc: Verify the AssignColors function of InterferenceGraph. 332 * @tc.type: FUNC 333 * @tc.require: 334 */ 335 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_013, TestSize.Level1) 336 { 337 std::pair<unsigned, unsigned> test_edges[6] = {{0, 1}, {1, 2}, {2, 0}, {0, 3}, {2, 3}, {3, 4}}; 338 339 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 340 InterferenceGraph ig(&allocator); 341 ig.Reserve(5); 342 343 auto *nd0 = ig.AllocNode(); 344 auto *nd1 = ig.AllocNode(); 345 auto *nd2 = ig.AllocNode(); 346 auto *nd3 = ig.AllocNode(); 347 auto *nd4 = ig.AllocNode(); 348 349 for (size_t i = 0; i < 6; i++) { 350 auto x = test_edges[i].first; 351 auto y = test_edges[i].second; 352 ig.AddEdge(x, y); 353 } 354 355 EXPECT_EQ(ig.AssignColors<32>(3, 0), 3); 356 EXPECT_NE(nd0->GetColor(), nd1->GetColor()); 357 EXPECT_NE(nd0->GetColor(), nd2->GetColor()); 358 EXPECT_NE(nd0->GetColor(), nd3->GetColor()); 359 360 EXPECT_NE(nd2->GetColor(), nd1->GetColor()); 361 EXPECT_NE(nd2->GetColor(), nd3->GetColor()); 362 363 EXPECT_NE(nd4->GetColor(), nd3->GetColor()); 364 } 365 366 /** 367 * @tc.name: reg_alloc_interference_test_014 368 * @tc.desc: Verify the AssignColors function of InterferenceGraph. 369 * @tc.type: FUNC 370 * @tc.require: 371 */ 372 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_014, TestSize.Level1) 373 { 374 const size_t DEFAULT_CAPACITY = 11; 375 const size_t DEFAULT_EDGES = 12; 376 const size_t DEFAULT_AEDGES = 4; 377 std::pair<unsigned, unsigned> test_edges[DEFAULT_EDGES] = {{0, 1}, {1, 2}, {2, 0}, {0, 3}, {2, 3}, {3, 4}, 378 {6, 5}, {5, 7}, {6, 7}, {9, 8}, {9, 10}, {8, 10}}; 379 std::pair<unsigned, unsigned> test_aedges[DEFAULT_AEDGES] = {{3, 6}, {6, 9}, {2, 5}, {7, 8}}; 380 381 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 382 InterferenceGraph ig(&allocator); 383 ig.Reserve(DEFAULT_CAPACITY); 384 385 auto *nd0 = ig.AllocNode(); 386 auto *nd1 = ig.AllocNode(); 387 auto *nd2 = ig.AllocNode(); 388 auto *nd3 = ig.AllocNode(); 389 auto *nd4 = ig.AllocNode(); 390 auto *nd5 = ig.AllocNode(); 391 auto *nd6 = ig.AllocNode(); 392 auto *nd7 = ig.AllocNode(); 393 auto *nd8 = ig.AllocNode(); 394 auto *nd9 = ig.AllocNode(); 395 auto *nd10 = ig.AllocNode(); 396 397 for (size_t i = 0; i < DEFAULT_EDGES; i++) { 398 auto x = test_edges[i].first; 399 auto y = test_edges[i].second; 400 ig.AddEdge(x, y); 401 } 402 for (size_t i = 0; i < DEFAULT_AEDGES; i++) { 403 auto x = test_aedges[i].first; 404 auto y = test_aedges[i].second; 405 ig.AddAffinityEdge(x, y); 406 } 407 auto &bias0 = ig.AddBias(); 408 auto &bias1 = ig.AddBias(); 409 auto &bias2 = ig.AddBias(); 410 411 nd3->SetBias(0); 412 nd6->SetBias(0); 413 nd9->SetBias(0); 414 nd2->SetBias(1); 415 nd5->SetBias(1); 416 nd7->SetBias(2); 417 nd8->SetBias(2); 418 419 EXPECT_EQ(ig.AssignColors<32>(3, 0), 3); 420 421 // Check nodes inequality 422 EXPECT_NE(nd0->GetColor(), nd1->GetColor()); 423 EXPECT_NE(nd0->GetColor(), nd2->GetColor()); 424 EXPECT_NE(nd0->GetColor(), nd3->GetColor()); 425 426 EXPECT_NE(nd2->GetColor(), nd1->GetColor()); 427 EXPECT_NE(nd2->GetColor(), nd3->GetColor()); 428 429 EXPECT_NE(nd4->GetColor(), nd3->GetColor()); 430 431 EXPECT_NE(nd5->GetColor(), nd6->GetColor()); 432 EXPECT_NE(nd7->GetColor(), nd6->GetColor()); 433 EXPECT_NE(nd5->GetColor(), nd7->GetColor()); 434 435 EXPECT_NE(nd8->GetColor(), nd9->GetColor()); 436 EXPECT_NE(nd8->GetColor(), nd10->GetColor()); 437 EXPECT_NE(nd9->GetColor(), nd10->GetColor()); 438 439 // Check biases work 440 EXPECT_EQ(nd3->GetColor(), nd6->GetColor()); 441 EXPECT_EQ(nd9->GetColor(), nd6->GetColor()); 442 443 EXPECT_EQ(nd2->GetColor(), nd5->GetColor()); 444 EXPECT_EQ(nd7->GetColor(), nd8->GetColor()); 445 446 // Check biases values 447 EXPECT_NE(bias0.color, bias1.color); 448 EXPECT_NE(bias0.color, bias2.color); 449 } 450 451 /** 452 * @tc.name: reg_alloc_interference_test_015 453 * @tc.desc: Verify the Dump function of InterferenceGraph. 454 * @tc.type: FUNC 455 * @tc.require: 456 */ 457 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_015, TestSize.Level1) 458 { 459 const size_t DEFAULT_PHISICALS = 3; 460 const size_t DEFAULT_NONPHISICALS = 11; 461 462 const size_t DEFAULT_CAPACITY = DEFAULT_PHISICALS + DEFAULT_NONPHISICALS; 463 const size_t DEFAULT_EDGES = 14; 464 const size_t DEFAULT_AEDGES = 4; 465 const size_t DEFAULT_BIASES = 3; 466 std::pair<unsigned, unsigned> test_edges[DEFAULT_EDGES] = {{0, 1}, {1, 2}, {2, 0}, {0, 3}, {2, 3}, 467 {3, 4}, {6, 5}, {5, 7}, {6, 7}, {9, 8}, 468 {9, 10}, {8, 10}, {11, 12}, {12, 0}}; 469 std::pair<unsigned, unsigned> test_aedges[DEFAULT_AEDGES] = {{3, 6}, {6, 9}, {2, 5}, {7, 8}}; 470 471 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 472 InterferenceGraph ig(&allocator); 473 ig.Reserve(DEFAULT_CAPACITY); 474 475 for (size_t i = 0; i < DEFAULT_CAPACITY; i++) { 476 auto node = ig.AllocNode(); 477 478 auto inst = allocator.New<ConstantInst>(Opcode::Constant, 0); 479 inst->SetId(i); 480 481 LiveRange range(i, i); 482 auto intervals = allocator.New<LifeIntervals>(&allocator, inst, range); 483 484 node->Assign(intervals); 485 } 486 487 for (size_t i = DEFAULT_NONPHISICALS; i < DEFAULT_CAPACITY; i++) { 488 ig.GetNode(i).SetFixedColor(251 + i, true); 489 } 490 491 for (size_t i = 0; i < DEFAULT_EDGES; i++) { 492 auto x = test_edges[i].first; 493 auto y = test_edges[i].second; 494 ig.AddEdge(x, y); 495 } 496 497 for (size_t i = 0; i < DEFAULT_AEDGES; i++) { 498 auto x = test_aedges[i].first; 499 auto y = test_aedges[i].second; 500 ig.AddAffinityEdge(x, y); 501 } 502 503 for (size_t i = 0; i < DEFAULT_BIASES; i++) { 504 ig.AddBias(); 505 } 506 507 ig.GetNode(3).SetBias(0); 508 ig.GetNode(6).SetBias(0); 509 ig.GetNode(9).SetBias(0); 510 ig.GetNode(2).SetBias(1); 511 ig.GetNode(5).SetBias(1); 512 ig.GetNode(7).SetBias(2); 513 ig.GetNode(8).SetBias(2); 514 515 EXPECT_EQ(ig.AssignColors<32>(3, 0), 3); 516 517 std::stringstream out; 518 ig.Dump("ig_with_phisical", false, out); 519 std::string expect_str1 = "Nodes: 14\n" 520 "\n\n" 521 "graph ig_with_phisical {\n" 522 "node [colorscheme=spectral9]\n" 523 "0 [color=0, xlabel=\"0\", tooltip=\" {inst v0}\", shape=\"hexagon\"]\n" 524 "1 [color=1, xlabel=\"1\", tooltip=\"[1:1) {inst v1}\", shape=\"ellipse\"]\n" 525 "2 [color=2, xlabel=\"2\", tooltip=\"[2:2) {inst v2}\", shape=\"ellipse\"]\n" 526 "3 [color=1, xlabel=\"1\", tooltip=\"[3:3) {inst v3}\", shape=\"ellipse\"]\n" 527 "4 [color=0, xlabel=\"0\", tooltip=\"[4:4) {inst v4}\", shape=\"ellipse\"]\n" 528 "5 [color=2, xlabel=\"2\", tooltip=\"[5:5) {inst v5}\", shape=\"ellipse\"]\n" 529 "6 [color=1, xlabel=\"1\", tooltip=\"[6:6) {inst v6}\", shape=\"ellipse\"]\n" 530 "7 [color=0, xlabel=\"0\", tooltip=\"[7:7) {inst v7}\", shape=\"ellipse\"]\n" 531 "8 [color=0, xlabel=\"0\", tooltip=\"[8:8) {inst v8}\", shape=\"ellipse\"]\n" 532 "9 [color=1, xlabel=\"1\", tooltip=\"[9:9) {inst v9}\", shape=\"ellipse\"]\n" 533 "10 [color=2, xlabel=\"2\", tooltip=\"[10:10) {inst v10}\", shape=\"ellipse\"]\n" 534 "11 [color=3, xlabel=\"6\", tooltip=\"[11:11) {inst v11}\", shape=\"box\"]\n" 535 "12 [color=4, xlabel=\"7\", tooltip=\"[12:12) {inst v12}\", shape=\"box\"]\n" 536 "13 [color=5, xlabel=\"8\", tooltip=\"[13:13) {inst v13}\", shape=\"box\"]\n" 537 "1--0\n2--0\n2--1\n3--0\n3--2\n4--3\n6--5\n7--5\n7--6\n9--8\n10--8\n10--9\n" 538 "12--0\n12--11\n}\n"; 539 EXPECT_EQ(out.str(), expect_str1); 540 541 out.str(""); 542 ig.Dump("ig_without_phisical", true, out); 543 std::string expect_str2 = "Nodes: 14\n" 544 "\n\n" 545 "graph ig_without_phisical {\n" 546 "node [colorscheme=spectral9]\n" 547 "0 [color=0, xlabel=\"0\", tooltip=\" {inst v0}\", shape=\"hexagon\"]\n" 548 "1 [color=1, xlabel=\"1\", tooltip=\"[1:1) {inst v1}\", shape=\"ellipse\"]\n" 549 "2 [color=2, xlabel=\"2\", tooltip=\"[2:2) {inst v2}\", shape=\"ellipse\"]\n" 550 "3 [color=1, xlabel=\"1\", tooltip=\"[3:3) {inst v3}\", shape=\"ellipse\"]\n" 551 "4 [color=0, xlabel=\"0\", tooltip=\"[4:4) {inst v4}\", shape=\"ellipse\"]\n" 552 "5 [color=2, xlabel=\"2\", tooltip=\"[5:5) {inst v5}\", shape=\"ellipse\"]\n" 553 "6 [color=1, xlabel=\"1\", tooltip=\"[6:6) {inst v6}\", shape=\"ellipse\"]\n" 554 "7 [color=0, xlabel=\"0\", tooltip=\"[7:7) {inst v7}\", shape=\"ellipse\"]\n" 555 "8 [color=0, xlabel=\"0\", tooltip=\"[8:8) {inst v8}\", shape=\"ellipse\"]\n" 556 "9 [color=1, xlabel=\"1\", tooltip=\"[9:9) {inst v9}\", shape=\"ellipse\"]\n" 557 "10 [color=2, xlabel=\"2\", tooltip=\"[10:10) {inst v10}\", shape=\"ellipse\"]\n" 558 "1--0\n2--0\n2--1\n3--0\n3--2\n4--3\n6--5\n7--5\n7--6\n9--8\n10--8\n10--9\n}\n"; 559 EXPECT_EQ(out.str(), expect_str2); 560 } 561 562 /** 563 * @tc.name: reg_alloc_interference_test_016 564 * @tc.desc: Verify the Dump function with empty InterferenceGraph. 565 * @tc.type: FUNC 566 * @tc.require: 567 */ 568 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_016, TestSize.Level1) 569 { 570 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 571 InterferenceGraph ig(&allocator); 572 573 std::stringstream out; 574 ig.Dump("empty_ig", true, out); 575 std::string expect_str = "Nodes: 0\n" 576 "\n\n" 577 "graph empty_ig {\n" 578 "node [colorscheme=spectral9]\n" 579 "}\n"; 580 EXPECT_EQ(out.str(), expect_str); 581 } 582 583 /** 584 * @tc.name: reg_alloc_interference_test_017 585 * @tc.desc: Verify the Dump function with same color error. 586 * @tc.type: FUNC 587 * @tc.require: 588 */ 589 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_017, TestSize.Level1) 590 { 591 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 592 InterferenceGraph ig(&allocator); 593 ig.Reserve(2); 594 595 for (size_t i = 0; i < 2; i++) { 596 auto node = ig.AllocNode(); 597 598 auto inst = allocator.New<ConstantInst>(Opcode::Constant, i); 599 inst->SetId(i); 600 601 LiveRange range(i, i); 602 auto intervals = allocator.New<LifeIntervals>(&allocator, inst, range); 603 node->Assign(intervals); 604 605 // set same color 606 node->SetColor(3); 607 } 608 609 ig.AddEdge(0, 1); 610 611 std::stringstream out; 612 ig.Dump("same_color_error", false, out); 613 std::string expect_str = "Nodes: 2\n" 614 "\n\n" 615 "graph same_color_error {\n" 616 "node [colorscheme=spectral9]\n" 617 "0 [color=0, xlabel=\"3\", tooltip=\" {inst v0}\", shape=\"ellipse\"]\n" 618 "1 [color=0, xlabel=\"3\", tooltip=\"[1:1) {inst v1}\", shape=\"ellipse\"]\n" 619 "Error: Same color\n" 620 "1--0\n" 621 "}\n"; 622 EXPECT_EQ(out.str(), expect_str); 623 } 624 625 /** 626 * @tc.name: reg_alloc_interference_test_018 627 * @tc.desc: Verify the IsChordal function. 628 * @tc.type: FUNC 629 * @tc.require: 630 */ 631 HWTEST_F(RegAllocInterferenceTest, reg_alloc_interference_test_018, TestSize.Level1) 632 { 633 ArenaAllocator allocator {SpaceType::SPACE_TYPE_COMPILER}; 634 InterferenceGraph ig(&allocator); 635 ig.Reserve(5); 636 637 for (size_t i = 0; i < 5; i++) { 638 ig.AllocNode(); 639 EXPECT_TRUE(ig.IsChordal()); 640 } 641 ig.AddEdge(0, 1); 642 EXPECT_TRUE(ig.IsChordal()); 643 ig.AddEdge(1, 2); 644 EXPECT_TRUE(ig.IsChordal()); 645 ig.AddEdge(2, 0); 646 EXPECT_TRUE(ig.IsChordal()); 647 648 ig.AddEdge(3, 4); 649 ig.AddEdge(1, 3); 650 ig.AddEdge(2, 4); 651 EXPECT_FALSE(ig.IsChordal()); 652 653 ig.AddEdge(1, 4); 654 EXPECT_TRUE(ig.IsChordal()); 655 } 656 } // namespace panda::compiler 657