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 "cgbb.h"
17 #include "cgfunc.h"
18 
19 namespace maplebe {
20 constexpr uint32 kCondBrNum = 2;
21 constexpr uint32 kSwitchCaseNum = 5;
22 
23 const std::string BB::bbNames[BB::kBBLast] = {"BB_ft", "BB_if", "BB_goto", "BB_ret", "BB_noret", "BB_rangegoto"};
24 
InsertInsnBefore(Insn &existing, Insn &newInsn)25 Insn *BB::InsertInsnBefore(Insn &existing, Insn &newInsn)
26 {
27     Insn *pre = existing.GetPrev();
28     newInsn.SetPrev(pre);
29     newInsn.SetNext(&existing);
30     existing.SetPrev(&newInsn);
31     if (pre != nullptr) {
32         pre->SetNext(&newInsn);
33     }
34     if (&existing == firstInsn) {
35         firstInsn = &newInsn;
36     }
37     newInsn.SetBB(this);
38     return &newInsn;
39 }
40 
InsertInsnAfter(Insn &existing, Insn &newInsn)41 Insn *BB::InsertInsnAfter(Insn &existing, Insn &newInsn)
42 {
43     newInsn.SetPrev(&existing);
44     newInsn.SetNext(existing.GetNext());
45     existing.SetNext(&newInsn);
46     if (&existing == lastInsn) {
47         lastInsn = &newInsn;
48     } else if (newInsn.GetNext()) {
49         newInsn.GetNext()->SetPrev(&newInsn);
50     }
51     newInsn.SetBB(this);
52     internalFlag1++;
53     return &newInsn;
54 }
55 
ReplaceInsn(Insn &insn, Insn &newInsn)56 void BB::ReplaceInsn(Insn &insn, Insn &newInsn)
57 {
58     if (insn.IsAccessRefField()) {
59         newInsn.MarkAsAccessRefField(true);
60     }
61     if (insn.GetDoNotRemove()) {
62         newInsn.SetDoNotRemove(true);
63     }
64     newInsn.SetPrev(insn.GetPrev());
65     newInsn.SetNext(insn.GetNext());
66     if (&insn == lastInsn) {
67         lastInsn = &newInsn;
68     } else if (newInsn.GetNext() != nullptr) {
69         newInsn.GetNext()->SetPrev(&newInsn);
70     }
71     if (firstInsn == &insn) {
72         firstInsn = &newInsn;
73     } else if (newInsn.GetPrev() != nullptr) {
74         newInsn.GetPrev()->SetNext(&newInsn);
75     }
76     newInsn.SetComment(insn.GetComment());
77     newInsn.SetBB(this);
78 }
79 
RemoveInsn(Insn &insn)80 void BB::RemoveInsn(Insn &insn)
81 {
82     if ((firstInsn == &insn) && (lastInsn == &insn)) {
83         firstInsn = lastInsn = nullptr;
84     } else if (firstInsn == &insn) {
85         firstInsn = insn.GetNext();
86     } else if (lastInsn == &insn) {
87         lastInsn = insn.GetPrev();
88     }
89     /* remove insn from lir list */
90     Insn *prevInsn = insn.GetPrev();
91     Insn *nextInsn = insn.GetNext();
92     if (prevInsn != nullptr) {
93         prevInsn->SetNext(nextInsn);
94     }
95     if (nextInsn != nullptr) {
96         nextInsn->SetPrev(prevInsn);
97     }
98 }
99 
100 /* Remove insns in this bb from insn1 to insn2. */
RemoveInsnSequence(Insn &insn, const Insn &nextInsn)101 void BB::RemoveInsnSequence(Insn &insn, const Insn &nextInsn)
102 {
103     DEBUG_ASSERT(insn.GetBB() == this, "remove insn sequence in one bb");
104     DEBUG_ASSERT(nextInsn.GetBB() == this, "remove insn sequence in one bb");
105     if ((firstInsn == &insn) && (lastInsn == &nextInsn)) {
106         firstInsn = lastInsn = nullptr;
107     } else if (firstInsn == &insn) {
108         firstInsn = nextInsn.GetNext();
109     } else if (lastInsn == &nextInsn) {
110         lastInsn = insn.GetPrev();
111     }
112 
113     if (insn.GetPrev() != nullptr) {
114         insn.GetPrev()->SetNext(nextInsn.GetNext());
115     }
116     if (nextInsn.GetNext() != nullptr) {
117         nextInsn.GetNext()->SetPrev(insn.GetPrev());
118     }
119 }
120 
121 /* append all insns from bb into this bb */
AppendBBInsns(BB &bb)122 void BB::AppendBBInsns(BB &bb)
123 {
124     if (firstInsn == nullptr) {
125         firstInsn = bb.firstInsn;
126         lastInsn = bb.lastInsn;
127         if (firstInsn != nullptr) {
128             FOR_BB_INSNS(i, &bb)
129             {
130                 i->SetBB(this);
131             }
132         }
133         return;
134     }
135     if ((bb.firstInsn == nullptr) || (bb.lastInsn == nullptr)) {
136         return;
137     }
138     FOR_BB_INSNS_SAFE(insn, &bb, nextInsn)
139     {
140         AppendInsn(*insn);
141     }
142 }
143 
144 /* prepend all insns from bb into this bb */
InsertAtBeginning(BB &bb)145 void BB::InsertAtBeginning(BB &bb)
146 {
147     if (bb.firstInsn == nullptr) { /* nothing to add */
148         return;
149     }
150 
151     FOR_BB_INSNS(insn, &bb)
152     {
153         insn->SetBB(this);
154     }
155 
156     if (firstInsn == nullptr) {
157         firstInsn = bb.firstInsn;
158         lastInsn = bb.lastInsn;
159     } else {
160         bb.lastInsn->SetNext(firstInsn);
161         firstInsn->SetPrev(bb.lastInsn);
162         firstInsn = bb.firstInsn;
163     }
164     bb.firstInsn = bb.lastInsn = nullptr;
165 }
166 
167 /* append all insns from bb into this bb */
InsertAtEnd(BB &bb)168 void BB::InsertAtEnd(BB &bb)
169 {
170     if (bb.firstInsn == nullptr) { /* nothing to add */
171         return;
172     }
173 
174     FOR_BB_INSNS(insn, &bb)
175     {
176         insn->SetBB(this);
177     }
178 
179     if (firstInsn == nullptr) {
180         firstInsn = bb.firstInsn;
181         lastInsn = bb.lastInsn;
182     } else {
183         bb.firstInsn->SetPrev(lastInsn);
184         lastInsn->SetNext(bb.firstInsn);
185         lastInsn = bb.lastInsn;
186     }
187     bb.firstInsn = bb.lastInsn = nullptr;
188 }
189 
190 /* Number of instructions excluding DbgInsn and comments */
NumInsn() const191 int32 BB::NumInsn() const
192 {
193     int32 bbSize = 0;
194     FOR_BB_INSNS_CONST(i, this)
195     {
196         if (i->IsImmaterialInsn() || i->IsDbgInsn()) {
197             continue;
198         }
199         ++bbSize;
200     }
201     return bbSize;
202 }
203 
Dump() const204 void BB::Dump() const
205 {
206     LogInfo::MapleLogger() << "=== BB " << this << " <" << GetKindName();
207     if (labIdx) {
208         LogInfo::MapleLogger() << "[labeled with " << labIdx << "]";
209         if (labelTaken) {
210             LogInfo::MapleLogger() << " taken";
211         }
212     }
213     LogInfo::MapleLogger() << "> <" << id << "> ";
214     if (isCleanup) {
215         LogInfo::MapleLogger() << "[is_cleanup] ";
216     }
217     if (unreachable) {
218         LogInfo::MapleLogger() << "[unreachable] ";
219     }
220     LogInfo::MapleLogger() << "frequency:" << frequency << "===\n";
221 
222     Insn *insn = firstInsn;
223     while (insn != nullptr) {
224         insn->Dump();
225         insn = insn->GetNext();
226     }
227 }
228 
IsCommentBB() const229 bool BB::IsCommentBB() const
230 {
231     if (GetKind() != kBBFallthru) {
232         return false;
233     }
234     FOR_BB_INSNS_CONST(insn, this)
235     {
236         if (insn->IsMachineInstruction()) {
237             return false;
238         }
239     }
240     return true;
241 }
242 
243 /* return true if bb has no real insns. */
IsEmptyOrCommentOnly() const244 bool BB::IsEmptyOrCommentOnly() const
245 {
246     return (IsEmpty() || IsCommentBB());
247 }
248 
IsSoloGoto() const249 bool BB::IsSoloGoto() const
250 {
251     if (GetKind() != kBBGoto) {
252         return false;
253     }
254     if (GetHasCfi()) {
255         return false;
256     }
257     FOR_BB_INSNS_CONST(insn, this)
258     {
259         if (!insn->IsMachineInstruction()) {
260             continue;
261         }
262         return (insn->IsUnCondBranch());
263     }
264     return false;
265 }
266 
SeekCycles()267 void Bfs::SeekCycles()
268 {
269     MapleVector<bool> visited(cgfunc->NumBBs(), false, alloc.Adapter());
270     MapleVector<bool> onPath(cgfunc->NumBBs(), false, alloc.Adapter());
271     MapleStack<BB*> workStack(alloc.Adapter());
272 
273     // searhing workStack BBs cycle
274     auto seekCycles = [this, &visited, &onPath, &workStack]() {
275         while (!workStack.empty()) {
276             auto *bb = workStack.top();
277             if (visited[bb->GetId()]) {
278                 onPath[bb->GetId()] = false;
279                 workStack.pop();
280                 continue;
281             }
282 
283             visited[bb->GetId()] = true;
284             onPath[bb->GetId()] = true;
285             for (auto *succBB : bb->GetSuccs()) {
286                 if (!visited[succBB->GetId()]) {
287                     workStack.push(succBB);
288                 } else if (onPath[succBB->GetId()]) {
289                     (void)cycleSuccs[bb->GetId()].insert(succBB->GetId());
290                 }
291             }
292         }
293     };
294 
295     bool changed = false;
296     do {
297         changed = false;
298         FOR_ALL_BB(bb, cgfunc)
299         {
300             if (!visited[bb->GetId()]) {
301                 workStack.push(bb);
302                 seekCycles();
303                 changed = true;
304             }
305         }
306     } while (changed);
307 }
308 
AllPredBBVisited(const BB &bb, long &level) const309 bool Bfs::AllPredBBVisited(const BB &bb, long &level) const
310 {
311     // check pred bb is in cycle
312     auto predBBInCycle = [this](const BB &bb, const BB &predBB) {
313         for (auto bbId : cycleSuccs[predBB.GetId()]) {
314             if (bb.GetId() == bbId) {
315                 return true;
316             }
317         }
318         return false;
319     };
320 
321     bool isAllPredsVisited = true;
322     for (const auto *predBB : bb.GetPreds()) {
323         if (!predBBInCycle(bb, *predBB) && !visitedBBs[predBB->GetId()]) {
324             isAllPredsVisited = false;
325             break;
326         }
327         level = std::max(level, predBB->GetInternalFlag2());
328     }
329     return isAllPredsVisited;
330 }
331 
332 /*
333  * During live interval construction, bb has only one predecessor and/or one
334  * successor are stright line bb.  It can be considered to be a single large bb
335  * for the purpose of finding live interval.  This is to prevent extending live
336  * interval of registers unnecessarily when interleaving bb from other paths.
337  */
MarkStraightLineBBInBFS(BB *bb)338 BB *Bfs::MarkStraightLineBBInBFS(BB *bb)
339 {
340     while (true) {
341         if (bb->GetSuccs().size() != 1) {
342             break;
343         }
344         BB *sbb = bb->GetSuccs().front();
345         if (visitedBBs[sbb->GetId()]) {
346             break;
347         }
348         if (sbb->GetPreds().size() != 1) {
349             break;
350         }
351         sortedBBs.push_back(sbb);
352         visitedBBs[sbb->GetId()] = true;
353         sbb->SetInternalFlag2(bb->GetInternalFlag2() + 1);
354         bb = sbb;
355     }
356     return bb;
357 }
358 
SearchForStraightLineBBs(BB &bb)359 BB *Bfs::SearchForStraightLineBBs(BB &bb)
360 {
361     if ((bb.GetSuccs().size() != kCondBrNum)) {
362         return &bb;
363     }
364     BB *sbb1 = bb.GetSuccs().front();
365     BB *sbb2 = bb.GetSuccs().back();
366     size_t predSz1 = sbb1->GetPreds().size();
367     size_t predSz2 = sbb2->GetPreds().size();
368     BB *candidateBB = nullptr;
369     if ((predSz1 == 1) && (predSz2 > kSwitchCaseNum)) {
370         candidateBB = sbb1;
371     } else if ((predSz2 == 1) && (predSz1 > kSwitchCaseNum)) {
372         candidateBB = sbb2;
373     } else {
374         return &bb;
375     }
376     DEBUG_ASSERT(candidateBB->GetId() < visitedBBs.size(), "index out of range in RA::SearchForStraightLineBBs");
377     if (visitedBBs[candidateBB->GetId()]) {
378         return &bb;
379     }
380     if (candidateBB->GetSuccs().size() != 1) {
381         return &bb;
382     }
383 
384     sortedBBs.push_back(candidateBB);
385     visitedBBs[candidateBB->GetId()] = true;
386     return MarkStraightLineBBInBFS(candidateBB);
387 }
388 
BFS(BB &curBB)389 void Bfs::BFS(BB &curBB)
390 {
391     std::queue<BB *> workList;
392     workList.push(&curBB);
393     DEBUG_ASSERT(curBB.GetId() < cgfunc->NumBBs(), "RA::BFS visitedBBs overflow");
394     DEBUG_ASSERT(curBB.GetId() < visitedBBs.size(), "index out of range in RA::BFS");
395     visitedBBs[curBB.GetId()] = true;
396     do {
397         BB *bb = workList.front();
398         sortedBBs.push_back(bb);
399         DEBUG_ASSERT(bb->GetId() < cgfunc->NumBBs(), "RA::BFS visitedBBs overflow");
400         visitedBBs[bb->GetId()] = true;
401         workList.pop();
402         /* Look for straight line bb */
403         bb = MarkStraightLineBBInBFS(bb);
404         /* Look for an 'if' followed by some straight-line bb */
405         bb = SearchForStraightLineBBs(*bb);
406         for (auto *ibb : bb->GetSuccs()) {
407             /* See if there are unvisited predecessor */
408             if (visitedBBs[ibb->GetId()]) {
409                 continue;
410             }
411             long prevLevel = 0;
412             if (AllPredBBVisited(*ibb, prevLevel)) {
413                 ibb->SetInternalFlag2(prevLevel + 1);
414                 workList.push(ibb);
415                 DEBUG_ASSERT(ibb->GetId() < cgfunc->NumBBs(), "GCRA::BFS visitedBBs overflow");
416                 visitedBBs[ibb->GetId()] = true;
417             }
418         }
419     } while (!workList.empty());
420 }
421 
ComputeBlockOrder()422 void Bfs::ComputeBlockOrder()
423 {
424     cycleSuccs.assign(cgfunc->NumBBs(), MapleSet<BBID>(alloc.Adapter()));
425     SeekCycles();
426 
427     sortedBBs.clear();
428     visitedBBs.assign(cgfunc->NumBBs(), false);
429     BB *cleanupBB = nullptr;
430     FOR_ALL_BB(bb, cgfunc)
431     {
432         bb->SetInternalFlag1(0);
433         bb->SetInternalFlag2(1);
434         if (bb->IsCleanup()) {
435             DEBUG_ASSERT(cleanupBB == nullptr, "one cleanupBB in the function only");
436             cleanupBB = bb;
437         }
438     }
439     if (cleanupBB != nullptr) {
440         cleanupBB->SetInternalFlag1(1);
441     }
442 
443     bool changed;
444     size_t sortedCnt = 0;
445     bool done = false;
446     do {
447         changed = false;
448         FOR_ALL_BB(bb, cgfunc)
449         {
450             if (bb->GetInternalFlag1() == 1 || bb->IsUnreachable()) {
451                 continue;
452             }
453             if (visitedBBs[bb->GetId()]) {
454                 continue;
455             }
456             changed = true;
457             long prevLevel = 0;
458             if (AllPredBBVisited(*bb, prevLevel)) {
459                 bb->SetInternalFlag2(prevLevel + 1);
460                 BFS(*bb);
461             }
462         }
463         /* Make sure there is no infinite loop. */
464         if (sortedCnt == sortedBBs.size()) {
465             if (!done) {
466                 done = true;
467             } else {
468                 LogInfo::MapleLogger() << "Error: RA BFS loop " << sortedCnt
469                                        << " in func " << cgfunc->GetName() << "\n";
470                 CHECK_FATAL(false, "");
471             }
472         }
473         sortedCnt = sortedBBs.size();
474     } while (changed);
475 
476     if (cleanupBB != nullptr) {
477         sortedBBs.push_back(cleanupBB);
478     }
479 }
480 
GetAnalysisDependence(AnalysisDep &aDep) const481 void CgBBSort::GetAnalysisDependence(AnalysisDep &aDep) const
482 {
483 #if TARGX86_64
484     if (Triple::GetTriple().GetArch() == Triple::ArchType::x64) {
485         aDep.AddRequired<CgHandleCFG>();
486     }
487 #endif
488     aDep.SetPreservedAll();
489 }
490 
PhaseRun(CGFunc &f)491 bool CgBBSort::PhaseRun(CGFunc &f)
492 {
493     MemPool *memPool = GetPhaseMemPool();
494     bfs = memPool->New<Bfs>(f, *memPool);
495     CHECK_FATAL(bfs != nullptr, "NIY, ptr null check.");
496     bfs->ComputeBlockOrder();
497     return false;
498 }
499 MAPLE_ANALYSIS_PHASE_REGISTER(CgBBSort, bbsort)
500 } /* namespace maplebe */
501