1 /*
2 * Copyright (c) 2021-2024 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 "interference_graph.h"
17 #include <array>
18 #include <iterator>
19 #include <numeric>
20 #include "optimizer/analysis/liveness_analyzer.h"
21 #include "utils/small_vector.h"
22
23 namespace ark::compiler {
24
AllocNode()25 ColorNode *InterferenceGraph::AllocNode()
26 {
27 unsigned cur = nodes_.size();
28 nodes_.emplace_back(cur, nodes_.get_allocator());
29
30 // Check matrix capacity
31 ASSERT(nodes_.size() <= matrix_.GetCapacity());
32
33 return &nodes_.back();
34 }
35
Reserve(size_t count)36 void InterferenceGraph::Reserve(size_t count)
37 {
38 nodes_.clear();
39 nodes_.reserve(count);
40 matrix_.SetCapacity(count);
41 biases_.clear();
42 }
43
AddEdge(unsigned a,unsigned b)44 void InterferenceGraph::AddEdge(unsigned a, unsigned b)
45 {
46 matrix_.AddEdge(a, b);
47 }
48
HasEdge(unsigned a,unsigned b) const49 bool InterferenceGraph::HasEdge(unsigned a, unsigned b) const
50 {
51 return matrix_.HasEdge(a, b);
52 }
53
AddAffinityEdge(unsigned a,unsigned b)54 void InterferenceGraph::AddAffinityEdge(unsigned a, unsigned b)
55 {
56 matrix_.AddAffinityEdge(a, b);
57 }
58
HasAffinityEdge(unsigned a,unsigned b) const59 bool InterferenceGraph::HasAffinityEdge(unsigned a, unsigned b) const
60 {
61 return matrix_.HasAffinityEdge(a, b);
62 }
63
64 namespace {
65 constexpr size_t MIN_SIMPLITIAL_NODES = 3;
66 constexpr size_t DEFAULT_BOUNDARY_STACK = 16;
67 } // namespace
68
LexBFS() const69 ArenaVector<unsigned> InterferenceGraph::LexBFS() const
70 {
71 // Initialize out to sequentaly from 0
72 unsigned num = nodes_.size();
73 ArenaVector<unsigned> out(num, nodes_.get_allocator());
74 std::iota(out.begin(), out.end(), 0);
75
76 // Less then 3 are all simplicial
77 if (out.size() < MIN_SIMPLITIAL_NODES) {
78 return out;
79 }
80
81 // Control sub-sequences boundaries in stack maner
82 SmallVector<unsigned, DEFAULT_BOUNDARY_STACK> boundaryStack;
83 boundaryStack.reserve(num);
84 boundaryStack.push_back(num); // Sentinel
85 unsigned pos = 0; // Initialy we have set S of all elements
86
87 while (true) {
88 ASSERT(pos < out.size());
89 auto id = out[pos];
90 pos++;
91
92 // Check for boundaries colapse
93 ASSERT(!boundaryStack.empty());
94 auto prevEnd = boundaryStack.back();
95 ASSERT(pos <= prevEnd);
96 if (pos == prevEnd) {
97 if (pos == num) {
98 break;
99 }
100 boundaryStack.resize(boundaryStack.size() - 1);
101 ASSERT(!boundaryStack.empty());
102 prevEnd = boundaryStack.back();
103 }
104
105 // Partition on 2 groups: adjacent and not adjacent(last)
106 ASSERT(pos <= prevEnd);
107 auto it = std::stable_partition(out.begin() + pos, out.begin() + prevEnd,
108 [id, &out, this](unsigned val) { return HasEdge(id, out[val]); });
109 auto pivot = static_cast<unsigned>(std::distance(out.begin(), it));
110 // Split group if needed
111 if (pivot > pos && pivot != prevEnd) {
112 boundaryStack.push_back(pivot);
113 }
114 }
115
116 return out;
117 }
118
GetOrderedNodesIds() const119 ArenaVector<unsigned> InterferenceGraph::GetOrderedNodesIds() const
120 {
121 // Initialize out to sequentaly from 0
122 unsigned num = nodes_.size();
123 ArenaVector<unsigned> out(num, nodes_.get_allocator());
124 std::iota(out.begin(), out.end(), 0);
125 // If spill weights were counted, prefer nodes with higher weight, to increase their chances to be colored
126 if (IsUsedSpillWeight()) {
127 std::sort(out.begin(), out.end(), [&](unsigned lhsId, unsigned rhsId) {
128 return GetNode(lhsId).GetSpillWeight() > GetNode(rhsId).GetSpillWeight();
129 });
130 }
131 return out;
132 }
133
134 namespace {
135 constexpr size_t DEFAULT_VECTOR_SIZE = 64;
136 } // namespace
137
138 template <>
CheckNeighborsInClique(const ArenaVector<unsigned> & peo,SmallVector<Register,DEFAULT_VECTOR_SIZE> & processedNbr) const139 bool InterferenceGraph::CheckNeighborsInClique(const ArenaVector<unsigned> &peo,
140 SmallVector<Register, DEFAULT_VECTOR_SIZE> &processedNbr) const
141 {
142 for (auto nbr1 : processedNbr) {
143 for (auto nbr2 : processedNbr) {
144 if (nbr1 != nbr2 && !HasEdge(peo[nbr1], peo[nbr2])) {
145 return false;
146 }
147 }
148 }
149 return true;
150 }
151
IsChordal() const152 bool InterferenceGraph::IsChordal() const
153 {
154 const auto &peo = LexBFS();
155 SmallVector<Register, DEFAULT_VECTOR_SIZE> processedNbr;
156
157 for (size_t i = 0; i < peo.size(); i++) {
158 processedNbr.clear();
159
160 // Collect processed neighbors
161 for (size_t j = 0; j < i; j++) {
162 if (HasEdge(peo[i], peo[j])) {
163 processedNbr.push_back(j);
164 }
165 }
166
167 // Check that all processed neighbors in clique
168 if (!CheckNeighborsInClique(peo, processedNbr)) {
169 return false;
170 }
171 }
172
173 return true;
174 }
175
176 namespace {
GetNodeShape(const InterferenceGraph & ig,unsigned i)177 const char *GetNodeShape(const InterferenceGraph &ig, unsigned i)
178 {
179 const char *shape = "ellipse";
180 if (ig.GetNode(i).IsPhysical()) {
181 shape = "box";
182 } else {
183 auto size = ig.Size();
184 for (unsigned j = 0; j < size; j++) {
185 if (i != j && ig.HasEdge(i, j) && ig.GetNode(j).IsPhysical()) {
186 shape = "hexagon";
187 break;
188 }
189 }
190 }
191 return shape;
192 }
193 } // namespace
194
Dump(const std::string & name,bool skipPhysical,std::ostream & out) const195 void InterferenceGraph::Dump(const std::string &name, bool skipPhysical, std::ostream &out) const
196 {
197 auto transformedName = name;
198 std::replace(transformedName.begin(), transformedName.end(), ':', '_');
199 out << "Nodes: " << Size() << "\n\n"
200 << "\ngraph " << transformedName << " {\nnode [colorscheme=spectral9]\n";
201 auto size = Size();
202 if (size == 0) {
203 out << "}\n";
204 return;
205 }
206
207 // Map to colors
208 std::array<Register, std::numeric_limits<Register>::max()> colors {};
209 colors.fill(GetInvalidReg());
210 Register curColor = 0;
211
212 for (auto &node : GetNodes()) {
213 if (!(skipPhysical && node.IsPhysical()) && colors[node.GetColor()] == GetInvalidReg()) {
214 colors[node.GetColor()] = curColor;
215 curColor++;
216 }
217 }
218
219 // Print header
220 for (unsigned i = 0; i < size; i++) {
221 if (skipPhysical && GetNode(i).IsPhysical()) {
222 continue;
223 }
224 auto color = GetNode(i).GetColor();
225 out << i << " [color=" << unsigned(colors[color]) << ", xlabel=\"";
226 out << unsigned(color) << "\", tooltip=\"" << GetNode(i).GetLifeIntervals()->ToString<true>();
227 out << "\", shape=\"" << GetNodeShape(*this, i) << "\"]\n";
228 }
229
230 auto edgePrinter = [this, &out, skipPhysical](auto nodeNum) {
231 for (unsigned j = 0; j < nodeNum; j++) {
232 bool check = !(skipPhysical && GetNode(j).IsPhysical()) && HasEdge(nodeNum, j);
233 if (!check) {
234 continue;
235 }
236 if (GetNode(nodeNum).GetColor() == GetNode(j).GetColor() &&
237 GetNode(nodeNum).GetColor() != GetInvalidReg()) {
238 out << "Error: Same color\n";
239 }
240 out << nodeNum << "--" << j << "\n";
241 }
242 };
243
244 // Print edges
245 for (unsigned i = 1; i < size; i++) {
246 if (skipPhysical && GetNode(i).IsPhysical()) {
247 continue;
248 }
249 edgePrinter(i);
250 }
251
252 out << "}\n";
253 }
254 } // namespace ark::compiler
255