1 /*
2 * Copyright (c) 2023 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 "loop.h"
17 #include "cg.h"
18 #include "optimize_common.h"
19
20 namespace maplebe {
21 #define LOOP_ANALYSIS_DUMP_NEWPM CG_DEBUG_FUNC(f)
22
PrintLoopInfo(const LoopHierarchy & loop)23 static void PrintLoopInfo(const LoopHierarchy &loop)
24 {
25 LogInfo::MapleLogger() << "header " << loop.GetHeader()->GetId();
26 if (loop.otherLoopEntries.size()) {
27 LogInfo::MapleLogger() << " multi-header ";
28 for (auto en : loop.otherLoopEntries) {
29 LogInfo::MapleLogger() << en->GetId() << " ";
30 }
31 }
32 if (loop.GetOuterLoop() != nullptr) {
33 LogInfo::MapleLogger() << " parent " << loop.GetOuterLoop()->GetHeader()->GetId();
34 }
35 LogInfo::MapleLogger() << " backedge ";
36 for (auto *bb : loop.GetBackedge()) {
37 LogInfo::MapleLogger() << bb->GetId() << " ";
38 }
39 LogInfo::MapleLogger() << "\n members ";
40 for (auto *bb : loop.GetLoopMembers()) {
41 LogInfo::MapleLogger() << bb->GetId() << " ";
42 }
43 if (!loop.GetInnerLoops().empty()) {
44 LogInfo::MapleLogger() << "\n inner_loop_headers ";
45 for (auto *inner : loop.GetInnerLoops()) {
46 LogInfo::MapleLogger() << inner->GetHeader()->GetId() << " ";
47 }
48 }
49 LogInfo::MapleLogger() << "\n";
50 }
51
PrintInner(const LoopHierarchy & loop,uint32 level)52 static void PrintInner(const LoopHierarchy &loop, uint32 level)
53 {
54 for (auto *inner : loop.GetInnerLoops()) {
55 LogInfo::MapleLogger() << "loop-level-" << level << "\n";
56 PrintLoopInfo(*inner);
57 PrintInner(*inner, level + 1);
58 }
59 }
60
PrintLoops(const std::string & name) const61 void LoopHierarchy::PrintLoops(const std::string &name) const
62 {
63 LogInfo::MapleLogger() << name << "\n";
64 for (const LoopHierarchy *loop = this; loop != nullptr; loop = loop->next) {
65 PrintLoopInfo(*loop);
66 }
67 for (const LoopHierarchy *loop = this; loop != nullptr; loop = loop->next) {
68 PrintInner(*loop, 1);
69 }
70 }
71
CheckOverlappingInnerLoops(const MapleVector<CGFuncLoops * > & iLoops,const MapleVector<BB * > & loopMem) const72 void CGFuncLoops::CheckOverlappingInnerLoops(const MapleVector<CGFuncLoops *> &iLoops,
73 const MapleVector<BB *> &loopMem) const
74 {
75 for (auto iloop : iLoops) {
76 CHECK_FATAL(iloop->loopMembers.size() > 0, "Empty loop");
77 for (auto bb : iloop->loopMembers) {
78 if (find(loopMem.begin(), loopMem.end(), bb) != loopMem.end()) {
79 LogInfo::MapleLogger() << "Error: inconsistent loop member";
80 CHECK_FATAL(0, "loop member overlap with inner loop");
81 }
82 }
83 CheckOverlappingInnerLoops(iloop->innerLoops, loopMem);
84 }
85 }
86
CheckLoops() const87 void CGFuncLoops::CheckLoops() const
88 {
89 // Make sure backedge -> header relationship holds
90 for (auto bEdge : backedge) {
91 if (find(bEdge->GetSuccs().begin(), bEdge->GetSuccs().end(), header) == bEdge->GetSuccs().end()) {
92 bool inOtherEntry = false;
93 for (auto entry : multiEntries) {
94 if (find(bEdge->GetSuccs().begin(), bEdge->GetSuccs().end(), entry) != bEdge->GetSuccs().end()) {
95 inOtherEntry = true;
96 break;
97 }
98 }
99 if (inOtherEntry == false) {
100 if (find(bEdge->GetEhSuccs().begin(), bEdge->GetEhSuccs().end(), header) == bEdge->GetEhSuccs().end()) {
101 LogInfo::MapleLogger() << "Error: inconsistent loop backedge";
102 CHECK_FATAL(0, "loop backedge does not go to loop header");
103 }
104 }
105 }
106 if (find(header->GetPreds().begin(), header->GetPreds().end(), bEdge) == header->GetPreds().end()) {
107 bool inOtherEntry = false;
108 for (auto entry : multiEntries) {
109 if (find(entry->GetPreds().begin(), entry->GetPreds().end(), bEdge) != entry->GetPreds().end()) {
110 inOtherEntry = true;
111 break;
112 }
113 }
114 if (inOtherEntry == false) {
115 if (find(header->GetEhPreds().begin(), header->GetEhPreds().end(), bEdge) ==
116 header->GetEhPreds().end()) {
117 LogInfo::MapleLogger() << "Error: inconsistent loop header";
118 CHECK_FATAL(0, "loop header does not have a backedge");
119 }
120 }
121 }
122 }
123
124 // Make sure containing loop members do not overlap
125 CheckOverlappingInnerLoops(innerLoops, loopMembers);
126
127 if (innerLoops.empty() == false) {
128 for (auto lp : innerLoops) {
129 lp->CheckLoops();
130 }
131 }
132 }
133
PrintLoops(const CGFuncLoops & funcLoop) const134 void CGFuncLoops::PrintLoops(const CGFuncLoops &funcLoop) const
135 {
136 LogInfo::MapleLogger() << "loop_level(" << funcLoop.loopLevel << ") ";
137 LogInfo::MapleLogger() << "header " << funcLoop.GetHeader()->GetId() << " ";
138 if (funcLoop.multiEntries.size()) {
139 LogInfo::MapleLogger() << "other-header ";
140 for (auto bb : funcLoop.multiEntries) {
141 LogInfo::MapleLogger() << bb->GetId() << " ";
142 }
143 }
144 if (funcLoop.GetOuterLoop() != nullptr) {
145 LogInfo::MapleLogger() << "parent " << funcLoop.GetOuterLoop()->GetHeader()->GetId() << " ";
146 }
147 LogInfo::MapleLogger() << "backedge ";
148 for (auto *bb : funcLoop.GetBackedge()) {
149 LogInfo::MapleLogger() << bb->GetId() << " ";
150 }
151 LogInfo::MapleLogger() << "\n members ";
152 for (auto *bb : funcLoop.GetLoopMembers()) {
153 LogInfo::MapleLogger() << bb->GetId() << " ";
154 }
155 LogInfo::MapleLogger() << "\n exits ";
156 for (auto *bb : funcLoop.GetExits()) {
157 LogInfo::MapleLogger() << bb->GetId() << " ";
158 }
159 LogInfo::MapleLogger() << "\n";
160 if (!funcLoop.GetInnerLoops().empty()) {
161 LogInfo::MapleLogger() << " inner_loop_headers ";
162 for (auto *inner : funcLoop.GetInnerLoops()) {
163 LogInfo::MapleLogger() << inner->GetHeader()->GetId() << " ";
164 }
165 LogInfo::MapleLogger() << "\n";
166 for (auto *inner : funcLoop.GetInnerLoops()) {
167 PrintLoops(*inner);
168 }
169 }
170 }
171
172 // partial loop body found with formLoop is NOT really needed in down stream
173 // It should be simplied later
formLoop(BB * headBB,BB * backBB)174 void LoopFinder::formLoop(BB *headBB, BB *backBB)
175 {
176 DEBUG_ASSERT(headBB != nullptr && backBB != nullptr, "headBB or backBB is nullptr");
177 LoopHierarchy *simple_loop = memPool->New<LoopHierarchy>(*memPool);
178
179 if (headBB != backBB) {
180 DEBUG_ASSERT(!dfsBBs.empty(), "dfsBBs is empty");
181 DEBUG_ASSERT(onPathBBs[headBB->GetId()], "headBB is not on execution path");
182 std::stack<BB *> tempStk;
183
184 tempStk.push(dfsBBs.top());
185 dfsBBs.pop();
186
187 while (tempStk.top() != headBB && !dfsBBs.empty()) {
188 tempStk.push(dfsBBs.top());
189 dfsBBs.pop();
190 }
191
192 while (!tempStk.empty()) {
193 BB *topBB = tempStk.top();
194 tempStk.pop();
195
196 if (onPathBBs[topBB->GetId()]) {
197 simple_loop->InsertLoopMembers(*topBB);
198 }
199 dfsBBs.push(topBB);
200 }
201 }
202 // Note: backBB is NOT on dfsBBs
203 simple_loop->InsertLoopMembers(*backBB);
204 simple_loop->SetHeader(*headBB);
205 simple_loop->InsertBackedge(*backBB);
206
207 if (loops) {
208 loops->SetPrev(simple_loop);
209 }
210 simple_loop->SetNext(loops);
211 loops = simple_loop;
212 }
213
seekBackEdge(BB * bb,MapleList<BB * > succs)214 void LoopFinder::seekBackEdge(BB *bb, MapleList<BB *> succs)
215 {
216 for (const auto succBB : succs) {
217 if (!visitedBBs[succBB->GetId()]) {
218 dfsBBs.push(succBB);
219 } else {
220 if (onPathBBs[succBB->GetId()]) {
221 formLoop(succBB, bb);
222 bb->PushBackLoopSuccs(*succBB);
223 succBB->PushBackLoopPreds(*bb);
224 }
225 }
226 }
227 }
228
seekCycles()229 void LoopFinder::seekCycles()
230 {
231 while (!dfsBBs.empty()) {
232 BB *bb = dfsBBs.top();
233 if (visitedBBs[bb->GetId()]) {
234 onPathBBs[bb->GetId()] = false;
235 dfsBBs.pop();
236 continue;
237 }
238
239 visitedBBs[bb->GetId()] = true;
240 onPathBBs[bb->GetId()] = true;
241 seekBackEdge(bb, bb->GetSuccs());
242 seekBackEdge(bb, bb->GetEhSuccs());
243 }
244 }
245
markExtraEntryAndEncl()246 void LoopFinder::markExtraEntryAndEncl()
247 {
248 DEBUG_ASSERT(dfsBBs.empty(), "dfsBBs is NOT empty");
249 std::vector<BB *> loopEnclosure;
250 loopEnclosure.resize(cgFunc->NumBBs());
251 std::vector<bool> startProcess;
252 startProcess.resize(cgFunc->NumBBs());
253 std::vector<BB *> origEntries;
254 origEntries.resize(cgFunc->NumBBs());
255 std::vector<BB *> newEntries;
256 newEntries.resize(cgFunc->NumBBs());
257
258 for (LoopHierarchy *loop = loops; loop != nullptr; loop = loop->GetNext()) {
259 fill(visitedBBs.begin(), visitedBBs.end(), false);
260 fill(loopEnclosure.begin(), loopEnclosure.end(), nullptr);
261 fill(startProcess.begin(), startProcess.end(), false);
262 fill(origEntries.begin(), origEntries.end(), nullptr);
263 fill(newEntries.begin(), newEntries.end(), nullptr);
264
265 for (auto *bb : loop->GetLoopMembers()) {
266 loopEnclosure[bb->GetId()] = bb;
267 }
268 origEntries[loop->GetHeader()->GetId()] = loop->GetHeader();
269
270 // Form loop closure from the primary entry. At end collect all other entries
271 bool changed = false;
272 dfsBBs.push(loop->GetHeader());
273 while (true) {
274 while (!dfsBBs.empty()) {
275 BB *bb = dfsBBs.top();
276 visitedBBs[bb->GetId()] = true;
277 if (startProcess[bb->GetId()]) {
278 dfsBBs.pop();
279 for (const auto succBB : bb->GetSuccs()) {
280 if (loopEnclosure[bb->GetId()] == nullptr && loopEnclosure[succBB->GetId()] != nullptr &&
281 succBB != loop->GetHeader()) {
282 changed = true;
283 loopEnclosure[bb->GetId()] = bb;
284 break;
285 }
286 }
287 continue;
288 } else {
289 startProcess[bb->GetId()] = true;
290 for (const auto succBB : bb->GetSuccs()) {
291 if (!visitedBBs[succBB->GetId()]) {
292 dfsBBs.push(succBB);
293 }
294 }
295 }
296 }
297
298 // Repeat till no new item is added in
299 if (changed) {
300 dfsBBs.push(loop->GetHeader());
301 changed = false;
302 fill(visitedBBs.begin(), visitedBBs.end(), false);
303 fill(startProcess.begin(), startProcess.end(), false);
304 continue;
305 }
306
307 // Collect all entries
308 bool foundNewEntry = false;
309 fill(visitedBBs.begin(), visitedBBs.end(), false);
310 FOR_ALL_BB(bb, cgFunc) {
311 if (!visitedBBs[bb->GetId()]) {
312 dfsBBs.push(bb);
313 visitedBBs[bb->GetId()] = true;
314 while (!dfsBBs.empty()) {
315 BB *currBB = dfsBBs.top();
316 visitedBBs[currBB->GetId()] = true;
317 dfsBBs.pop();
318 for (const auto succBB : currBB->GetSuccs()) {
319 // check if entering a loop.
320 if ((loopEnclosure[succBB->GetId()] != nullptr) &&
321 (loopEnclosure[currBB->GetId()] == nullptr)) {
322 newEntries[succBB->GetId()] = succBB;
323 if (origEntries[succBB->GetId()] == nullptr) {
324 foundNewEntry = true;
325 }
326 }
327 if (!visitedBBs[succBB->GetId()]) {
328 dfsBBs.push(succBB);
329 }
330 }
331 }
332 }
333 }
334 if (foundNewEntry) {
335 origEntries = newEntries;
336 for (const auto bb : newEntries) {
337 if (bb != nullptr) {
338 dfsBBs.push(bb);
339 }
340 }
341 fill(visitedBBs.begin(), visitedBBs.end(), false);
342 fill(startProcess.begin(), startProcess.end(), false);
343 fill(newEntries.begin(), newEntries.end(), nullptr);
344 } else {
345 break;
346 }
347 }
348
349 // Setup loop body
350 for (size_t id = 0; id < loopEnclosure.size(); id++) {
351 if (loopEnclosure[id] != nullptr) {
352 loop->InsertLoopMembers(*loopEnclosure[id]);
353 }
354 }
355
356 // Setup head and extra entries
357 for (const auto bb : newEntries) {
358 if (bb != nullptr) {
359 loop->otherLoopEntries.insert(bb);
360 }
361 }
362 loop->otherLoopEntries.erase(loop->GetHeader());
363 }
364 }
365
HasSameHeader(const LoopHierarchy * lp1,const LoopHierarchy * lp2)366 bool LoopFinder::HasSameHeader(const LoopHierarchy *lp1, const LoopHierarchy *lp2)
367 {
368 if (lp1->GetHeader() == lp2->GetHeader()) {
369 return true;
370 }
371 for (auto other1 : lp1->otherLoopEntries) {
372 if (lp2->GetHeader() == other1) {
373 return true;
374 }
375 for (auto other2 : lp2->otherLoopEntries) {
376 if (other2 == other1) {
377 return true;
378 }
379 }
380 }
381 return false;
382 }
383
MergeLoops()384 void LoopFinder::MergeLoops()
385 {
386 for (LoopHierarchy *loopHierarchy1 = loops; loopHierarchy1 != nullptr; loopHierarchy1 = loopHierarchy1->GetNext()) {
387 for (LoopHierarchy *loopHierarchy2 = loopHierarchy1->GetNext(); loopHierarchy2 != nullptr;
388 loopHierarchy2 = loopHierarchy2->GetNext()) {
389 // Different loop bodies imply different loops
390 bool sameLoop = true;
391 if (loopHierarchy1->GetLoopMembers().size() == loopHierarchy2->GetLoopMembers().size()) {
392 for (auto *bb : loopHierarchy2->GetLoopMembers()) {
393 if (find(loopHierarchy1->GetLoopMembers().begin(), loopHierarchy1->GetLoopMembers().end(), bb) ==
394 loopHierarchy1->GetLoopMembers().end()) {
395 sameLoop = false;
396 break;
397 }
398 }
399 if (sameLoop) {
400 for (auto *bb : loopHierarchy1->GetLoopMembers()) {
401 if (find(loopHierarchy2->GetLoopMembers().begin(), loopHierarchy2->GetLoopMembers().end(),
402 bb) == loopHierarchy2->GetLoopMembers().end()) {
403 sameLoop = false;
404 break;
405 }
406 }
407 }
408 if (sameLoop) {
409 loopHierarchy2->GetPrev()->SetNext(loopHierarchy2->GetNext());
410 if (loopHierarchy2->GetNext() != nullptr) {
411 loopHierarchy2->GetNext()->SetPrev(loopHierarchy2->GetPrev());
412 }
413 continue;
414 }
415 }
416 if (HasSameHeader(loopHierarchy1, loopHierarchy2) == false) {
417 continue;
418 }
419 for (auto *bb : loopHierarchy2->GetLoopMembers()) {
420 loopHierarchy1->InsertLoopMembers(*bb);
421 }
422 if (loopHierarchy1->GetHeader() != loopHierarchy2->GetHeader()) {
423 loopHierarchy1->otherLoopEntries.insert(loopHierarchy2->GetHeader());
424 }
425 for (auto bb : loopHierarchy2->otherLoopEntries) {
426 if (loopHierarchy1->GetHeader() != bb) {
427 loopHierarchy1->otherLoopEntries.insert(bb);
428 }
429 }
430 for (auto *bb : loopHierarchy2->GetBackedge()) {
431 loopHierarchy1->InsertBackedge(*bb);
432 }
433 loopHierarchy2->GetPrev()->SetNext(loopHierarchy2->GetNext());
434 if (loopHierarchy2->GetNext() != nullptr) {
435 loopHierarchy2->GetNext()->SetPrev(loopHierarchy2->GetPrev());
436 }
437 }
438 }
439 }
440
SortLoops()441 void LoopFinder::SortLoops()
442 {
443 LoopHierarchy *head = nullptr;
444 LoopHierarchy *next1 = nullptr;
445 LoopHierarchy *next2 = nullptr;
446 bool swapped;
447 do {
448 swapped = false;
449 for (LoopHierarchy *loopHierarchy1 = loops; loopHierarchy1 != nullptr;) {
450 /* remember loopHierarchy1's prev in case if loopHierarchy1 moved */
451 head = loopHierarchy1;
452 next1 = loopHierarchy1->GetNext();
453 for (LoopHierarchy *loopHierarchy2 = loopHierarchy1->GetNext(); loopHierarchy2 != nullptr;) {
454 next2 = loopHierarchy2->GetNext();
455
456 if (loopHierarchy1->GetLoopMembers().size() > loopHierarchy2->GetLoopMembers().size()) {
457 if (head->GetPrev() == nullptr) {
458 /* remove loopHierarchy2 from list */
459 loopHierarchy2->GetPrev()->SetNext(loopHierarchy2->GetNext());
460 if (loopHierarchy2->GetNext() != nullptr) {
461 loopHierarchy2->GetNext()->SetPrev(loopHierarchy2->GetPrev());
462 }
463 /* link loopHierarchy2 as head */
464 loops = loopHierarchy2;
465 loopHierarchy2->SetPrev(nullptr);
466 loopHierarchy2->SetNext(head);
467 head->SetPrev(loopHierarchy2);
468 } else {
469 loopHierarchy2->GetPrev()->SetNext(loopHierarchy2->GetNext());
470 if (loopHierarchy2->GetNext() != nullptr) {
471 loopHierarchy2->GetNext()->SetPrev(loopHierarchy2->GetPrev());
472 }
473 head->GetPrev()->SetNext(loopHierarchy2);
474 loopHierarchy2->SetPrev(head->GetPrev());
475 loopHierarchy2->SetNext(head);
476 head->SetPrev(loopHierarchy2);
477 }
478 head = loopHierarchy2;
479 swapped = true;
480 }
481 loopHierarchy2 = next2;
482 }
483 loopHierarchy1 = next1;
484 }
485 } while (swapped);
486 }
487
UpdateOuterForInnerLoop(BB * bb,LoopHierarchy * outer)488 void LoopFinder::UpdateOuterForInnerLoop(BB *bb, LoopHierarchy *outer)
489 {
490 if (outer == nullptr) {
491 return;
492 }
493 for (auto ito = outer->GetLoopMembers().begin(); ito != outer->GetLoopMembers().end();) {
494 if (*ito == bb) {
495 ito = outer->EraseLoopMembers(ito);
496 } else {
497 ++ito;
498 }
499 }
500 if (outer->GetOuterLoop() != nullptr) {
501 UpdateOuterForInnerLoop(bb, const_cast<LoopHierarchy *>(outer->GetOuterLoop()));
502 }
503 }
504
UpdateOuterLoop(const LoopHierarchy * loop)505 void LoopFinder::UpdateOuterLoop(const LoopHierarchy *loop)
506 {
507 for (auto inner : loop->GetInnerLoops()) {
508 UpdateOuterLoop(inner);
509 }
510 for (auto *bb : loop->GetLoopMembers()) {
511 UpdateOuterForInnerLoop(bb, const_cast<LoopHierarchy *>(loop->GetOuterLoop()));
512 }
513 }
514
CreateInnerLoop(LoopHierarchy & inner,LoopHierarchy & outer)515 void LoopFinder::CreateInnerLoop(LoopHierarchy &inner, LoopHierarchy &outer)
516 {
517 outer.InsertInnerLoops(inner);
518 inner.SetOuterLoop(outer);
519 if (loops == &inner) {
520 loops = inner.GetNext();
521 } else {
522 LoopHierarchy *prev = loops;
523 for (LoopHierarchy *loopHierarchy1 = loops->GetNext(); loopHierarchy1 != nullptr;
524 loopHierarchy1 = loopHierarchy1->GetNext()) {
525 if (loopHierarchy1 == &inner) {
526 prev->SetNext(prev->GetNext()->GetNext());
527 }
528 prev = loopHierarchy1;
529 }
530 }
531 }
532
FindLoopExits(LoopHierarchy * loop)533 static void FindLoopExits(LoopHierarchy *loop)
534 {
535 for (auto *bb : loop->GetLoopMembers()) {
536 for (auto succ : bb->GetSuccs()) {
537 if (find(loop->GetLoopMembers().begin(), loop->GetLoopMembers().end(), succ) ==
538 loop->GetLoopMembers().end()) {
539 loop->InsertExit(*bb);
540 }
541 }
542 }
543 for (auto *inner : loop->GetInnerLoops()) {
544 FindLoopExits(inner);
545 }
546 }
547
DetectInnerLoop()548 void LoopFinder::DetectInnerLoop()
549 {
550 for (LoopHierarchy *loop = loops; loop != nullptr; loop = loop->GetNext()) {
551 FindLoopExits(loop);
552 }
553 bool innerCreated;
554 do {
555 innerCreated = false;
556 for (LoopHierarchy *loopHierarchy1 = loops; loopHierarchy1 != nullptr;
557 loopHierarchy1 = loopHierarchy1->GetNext()) {
558 for (LoopHierarchy *loopHierarchy2 = loopHierarchy1->GetNext(); loopHierarchy2 != nullptr;
559 loopHierarchy2 = loopHierarchy2->GetNext()) {
560 if (loopHierarchy1->GetHeader() != loopHierarchy2->GetHeader()) {
561 auto &loopHierarchy2Members = loopHierarchy2->GetLoopMembers();
562 if (find(loopHierarchy2Members.begin(), loopHierarchy2Members.end(), loopHierarchy1->GetHeader()) !=
563 loopHierarchy2Members.end()) {
564 bool allin = true;
565 // Make sure body is included
566 for (auto *bb1 : loopHierarchy1->GetLoopMembers()) {
567 if (find(loopHierarchy2Members.begin(), loopHierarchy2Members.end(), bb1) ==
568 loopHierarchy2Members.end()) {
569 allin = false;
570 break;
571 }
572 }
573 if (allin) {
574 CreateInnerLoop(*loopHierarchy1, *loopHierarchy2);
575 innerCreated = true;
576 }
577 }
578 if (innerCreated) {
579 break;
580 }
581 }
582 }
583 if (innerCreated) {
584 break;
585 }
586 }
587 } while (innerCreated);
588
589 for (LoopHierarchy *outer = loops; outer != nullptr; outer = outer->GetNext()) {
590 UpdateOuterLoop(outer);
591 }
592 }
593
CopyLoopInfo(const LoopHierarchy * from,CGFuncLoops * to,CGFuncLoops * parent,MemPool * memPool)594 static void CopyLoopInfo(const LoopHierarchy *from, CGFuncLoops *to, CGFuncLoops *parent, MemPool *memPool)
595 {
596 to->SetHeader(*const_cast<BB *>(from->GetHeader()));
597 for (auto bb : from->otherLoopEntries) {
598 to->AddMultiEntries(*bb);
599 }
600 for (auto *bb : from->GetLoopMembers()) {
601 to->AddLoopMembers(*bb);
602 bb->SetLoop(*to);
603 }
604 for (auto *bb : from->GetBackedge()) {
605 to->AddBackedge(*bb);
606 }
607 for (auto *bb : from->GetExits()) {
608 to->AddExit(*bb);
609 }
610 if (!from->GetInnerLoops().empty()) {
611 for (auto *inner : from->GetInnerLoops()) {
612 CGFuncLoops *floop = memPool->New<CGFuncLoops>(*memPool);
613 to->AddInnerLoops(*floop);
614 floop->SetLoopLevel(to->GetLoopLevel() + 1);
615 CopyLoopInfo(inner, floop, to, memPool);
616 }
617 }
618 if (parent != nullptr) {
619 to->SetOuterLoop(*parent);
620 }
621 }
622
UpdateCGFunc()623 void LoopFinder::UpdateCGFunc()
624 {
625 for (LoopHierarchy *loop = loops; loop != nullptr; loop = loop->GetNext()) {
626 CGFuncLoops *floop = cgFunc->GetMemoryPool()->New<CGFuncLoops>(*cgFunc->GetMemoryPool());
627 cgFunc->PushBackLoops(*floop);
628 floop->SetLoopLevel(1); /* top level */
629 CopyLoopInfo(loop, floop, nullptr, cgFunc->GetMemoryPool());
630 }
631 }
632
FormLoopHierarchy()633 void LoopFinder::FormLoopHierarchy()
634 {
635 visitedBBs.clear();
636 visitedBBs.resize(cgFunc->NumBBs(), false);
637 sortedBBs.clear();
638 sortedBBs.resize(cgFunc->NumBBs(), nullptr);
639 onPathBBs.clear();
640 onPathBBs.resize(cgFunc->NumBBs(), false);
641
642 FOR_ALL_BB(bb, cgFunc) {
643 bb->SetLevel(0);
644 }
645 bool changed;
646 do {
647 changed = false;
648 FOR_ALL_BB(bb, cgFunc) {
649 if (!visitedBBs[bb->GetId()]) {
650 dfsBBs.push(bb);
651 seekCycles();
652 changed = true;
653 }
654 }
655 } while (changed);
656
657 markExtraEntryAndEncl();
658 /*
659 * FIX : Should merge the partial loops at the time of initial
660 * construction. And make the linked list as a sorted set,
661 * then the merge and sort phases below can go away.
662 *
663 * Start merging the loops with the same header
664 */
665 MergeLoops();
666 /* order loops from least number of members */
667 SortLoops();
668 DetectInnerLoop();
669 UpdateCGFunc();
670 }
671
PhaseRun(maplebe::CGFunc & f)672 bool CgLoopAnalysis::PhaseRun(maplebe::CGFunc &f)
673 {
674 f.ClearLoopInfo();
675 MemPool *loopMemPool = GetPhaseMemPool();
676 LoopFinder *loopFinder = loopMemPool->New<LoopFinder>(f, *loopMemPool);
677 loopFinder->FormLoopHierarchy();
678
679 if (LOOP_ANALYSIS_DUMP_NEWPM) {
680 /* do dot gen after detection so the loop backedge can be properly colored using the loop info */
681 DotGenerator::GenerateDot("buildloop", f, f.GetMirModule(), true, f.GetName());
682 }
683 #if DEBUG
684 for (const auto *lp : f.GetLoops()) {
685 lp->CheckLoops();
686 }
687 #endif
688 return false;
689 }
690 MAPLE_ANALYSIS_PHASE_REGISTER(CgLoopAnalysis, loopanalysis)
691 } /* namespace maplebe */
692