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 "cfg_mst.h"
17 #include "cgbb.h"
18 #include "instrument.h"
19 namespace maple {
20 template <class Edge, class BB>
BuildEdges(BB * commonEntry,BB * commonExit)21 void CFGMST<Edge, BB>::BuildEdges(BB *commonEntry, BB *commonExit)
22 {
23 for (auto *curbb = commonEntry; curbb != nullptr; curbb = curbb->GetNext()) {
24 bbGroups[curbb->GetId()] = curbb->GetId();
25 if (curbb == commonExit) {
26 continue;
27 }
28 totalBB++;
29 for (auto *succBB : curbb->GetSuccs()) {
30 // exitBB incoming edge allocate high weight
31 if (succBB->GetKind() == BB::BBKind::kBBReturn) {
32 AddEdge(curbb, succBB, kExitEdgeWeight);
33 continue;
34 }
35 if (IsCritialEdge(curbb, succBB)) {
36 AddEdge(curbb, succBB, kCriticalEdgeWeight, true);
37 continue;
38 }
39 AddEdge(curbb, succBB, kNormalEdgeWeight);
40 }
41 }
42 ASSERT_NOT_NULL(commonExit);
43 for (BB *bb : commonExit->GetPreds()) {
44 AddEdge(bb, commonExit, kFakeExitEdgeWeight, false, true);
45 }
46 bbGroups[commonExit->GetId()] = commonExit->GetId();
47 // insert fake edge to keep consistent
48 AddEdge(commonExit, commonEntry, UINT64_MAX, false, true);
49 }
50
51 template <class Edge, class BB>
ComputeMST(BB * commonEntry,BB * commonExit)52 void CFGMST<Edge, BB>::ComputeMST(BB *commonEntry, BB *commonExit)
53 {
54 BuildEdges(commonEntry, commonExit);
55 SortEdges();
56 /* only one edge means only one bb */
57 if (allEdges.size() == 1) {
58 LogInfo::MapleLogger() << "only one edge find " << std::endl;
59 return;
60 }
61 // first,put all critial edge,with destBB is eh-handle
62 // in mst,because current doesn't support split that edge
63 for (auto &e : allEdges) {
64 if (UnionGroups(e->GetSrcBB()->GetId(), e->GetDestBB()->GetId())) {
65 e->SetInMST();
66 }
67 }
68 }
69
70 template <class Edge, class BB>
AddEdge(BB * src,BB * dest,uint64 w,bool isCritical,bool isFake)71 void CFGMST<Edge, BB>::AddEdge(BB *src, BB *dest, uint64 w, bool isCritical, bool isFake)
72 {
73 if (src == nullptr || dest == nullptr) {
74 return;
75 }
76 bool found = false;
77 for (auto &edge : allEdges) {
78 if (edge->GetSrcBB() == src && edge->GetDestBB() == dest) {
79 uint64 weight = edge->GetWeight();
80 weight++;
81 edge->SetWeight(weight);
82 found = true;
83 }
84 }
85 if (!found) {
86 (void)allEdges.emplace_back(mp->New<Edge>(src, dest, w, isCritical, isFake));
87 }
88 }
89
90 template <class Edge, class BB>
SortEdges()91 void CFGMST<Edge, BB>::SortEdges()
92 {
93 std::stable_sort(allEdges.begin(), allEdges.end(),
94 [](const Edge *edge1, const Edge *edge2) { return edge1->GetWeight() > edge2->GetWeight(); });
95 }
96
97 template <class Edge, class BB>
FindGroup(uint32 bbId)98 uint32 CFGMST<Edge, BB>::FindGroup(uint32 bbId)
99 {
100 CHECK_FATAL(bbGroups.count(bbId) != 0, "unRegister bb");
101 if (bbGroups[bbId] != bbId) {
102 bbGroups[bbId] = FindGroup(bbGroups[bbId]);
103 }
104 return bbGroups[bbId];
105 }
106
107 template <class Edge, class BB>
UnionGroups(uint32 srcId,uint32 destId)108 bool CFGMST<Edge, BB>::UnionGroups(uint32 srcId, uint32 destId)
109 {
110 uint32 srcGroupId = FindGroup(srcId);
111 uint32 destGroupId = FindGroup(destId);
112 if (srcGroupId == destGroupId) {
113 return false;
114 }
115 bbGroups[srcGroupId] = destGroupId;
116 return true;
117 }
118 template <class Edge, class BB>
DumpEdgesInfo() const119 void CFGMST<Edge, BB>::DumpEdgesInfo() const
120 {
121 for (auto &edge : allEdges) {
122 BB *src = edge->GetSrcBB();
123 BB *dest = edge->GetDestBB();
124 LogInfo::MapleLogger() << "BB" << src->GetId() << "->"
125 << "BB" << dest->GetId() << " weight " << edge->GetWeight();
126 if (edge->IsInMST()) {
127 LogInfo::MapleLogger() << " in Mst\n";
128 } else {
129 LogInfo::MapleLogger() << " not in Mst\n";
130 }
131 }
132 }
133
134 template class CFGMST<maple::BBEdge<maplebe::BB>, maplebe::BB>;
135 template class CFGMST<maple::BBUseEdge<maplebe::BB>, maplebe::BB>;
136 } // namespace maple
137