1 /**
2 * Copyright (c) 2021-2022 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 panda::compiler {
AddEdge(unsigned a,unsigned b)24 bool GraphMatrix::AddEdge(unsigned a, unsigned b)
25 {
26 auto it = matrix_.begin() + FindEdge(a, b);
27 bool old_val = *it;
28 *it = true;
29 return old_val;
30 }
31
AddAffinityEdge(unsigned a,unsigned b)32 bool GraphMatrix::AddAffinityEdge(unsigned a, unsigned b)
33 {
34 auto it = matrix_.begin() + FindAffinityEdge(a, b);
35 bool old_val = *it;
36 *it = true;
37 return old_val;
38 }
39
40 // -------------------------------------------------------
41
AllocNode()42 ColorNode *InterferenceGraph::AllocNode()
43 {
44 unsigned cur = nodes_.size();
45 nodes_.emplace_back(cur, nodes_.get_allocator());
46
47 // Check matrix capacity
48 ASSERT(nodes_.size() <= matrix_.GetCapacity());
49
50 return &nodes_.back();
51 }
52
Reserve(size_t count)53 void InterferenceGraph::Reserve(size_t count)
54 {
55 nodes_.clear();
56 nodes_.reserve(count);
57 matrix_.SetCapacity(count);
58 biases_.clear();
59 }
60
AddEdge(unsigned a,unsigned b)61 void InterferenceGraph::AddEdge(unsigned a, unsigned b)
62 {
63 matrix_.AddEdge(a, b);
64 }
65
HasEdge(unsigned a,unsigned b) const66 bool InterferenceGraph::HasEdge(unsigned a, unsigned b) const
67 {
68 return matrix_.HasEdge(a, b);
69 }
70
AddAffinityEdge(unsigned a,unsigned b)71 void InterferenceGraph::AddAffinityEdge(unsigned a, unsigned b)
72 {
73 matrix_.AddAffinityEdge(a, b);
74 }
75
HasAffinityEdge(unsigned a,unsigned b) const76 bool InterferenceGraph::HasAffinityEdge(unsigned a, unsigned b) const
77 {
78 return matrix_.HasAffinityEdge(a, b);
79 }
80
81 namespace {
82 constexpr size_t MIN_SIMPLITIAL_NODES = 3;
83 constexpr size_t DEFAULT_BOUNDARY_STACK = 16;
84 } // namespace
85
LexBFS() const86 ArenaVector<unsigned> InterferenceGraph::LexBFS() const
87 {
88 // Initialize out to sequentaly from 0
89 unsigned num = nodes_.size();
90 ArenaVector<unsigned> out(num, nodes_.get_allocator());
91 std::iota(out.begin(), out.end(), 0);
92
93 // Less then 3 are all simplicial
94 if (out.size() < MIN_SIMPLITIAL_NODES) {
95 return out;
96 }
97
98 // Control sub-sequences boundaries in stack maner
99 SmallVector<unsigned, DEFAULT_BOUNDARY_STACK> boundary_stack;
100 boundary_stack.reserve(num);
101 boundary_stack.push_back(num); // Sentinel
102 unsigned pos = 0; // Initialy we have set S of all elements
103
104 while (true) {
105 ASSERT(pos < out.size());
106 auto id = out[pos];
107 pos++;
108
109 // Check for boundaries colapse
110 ASSERT(!boundary_stack.empty());
111 auto prev_end = boundary_stack.back();
112 ASSERT(pos <= prev_end);
113 if (pos == prev_end) {
114 if (pos == num) {
115 break;
116 }
117 boundary_stack.resize(boundary_stack.size() - 1);
118 ASSERT(!boundary_stack.empty());
119 prev_end = boundary_stack.back();
120 }
121
122 // Partition on 2 groups: adjacent and not adjacent(last)
123 ASSERT(pos <= prev_end);
124 auto it = std::stable_partition(out.begin() + pos, out.begin() + prev_end,
125 [id, &out, this](unsigned val) { return HasEdge(id, out[val]); });
126 auto pivot = static_cast<unsigned>(std::distance(out.begin(), it));
127
128 // Split group if needed
129 if (pivot > pos && pivot != prev_end) {
130 boundary_stack.push_back(pivot);
131 }
132 }
133
134 return out;
135 }
136
137 namespace {
138 constexpr size_t DEFAULT_VECTOR_SIZE = 64;
139 } // namespace
140
IsChordal() const141 bool InterferenceGraph::IsChordal() const
142 {
143 const auto &peo = LexBFS();
144 SmallVector<Register, DEFAULT_VECTOR_SIZE> processed_nbr;
145
146 for (size_t i = 0; i < peo.size(); i++) {
147 processed_nbr.clear();
148
149 // Collect processed neighbors
150 for (size_t j = 0; j < i; j++) {
151 if (HasEdge(peo[i], peo[j])) {
152 processed_nbr.push_back(j);
153 }
154 }
155
156 // Check that all processed neighbors in clique
157 for (auto nbr1 : processed_nbr) {
158 for (auto nbr2 : processed_nbr) {
159 if (nbr1 != nbr2 && !HasEdge(peo[nbr1], peo[nbr2])) {
160 return false;
161 }
162 }
163 }
164 }
165
166 return true;
167 }
168
169 namespace {
GetNodeShape(const InterferenceGraph & ig,unsigned i)170 const char *GetNodeShape(const InterferenceGraph &ig, unsigned i)
171 {
172 const char *shape = "ellipse";
173 if (ig.GetNode(i).IsPhysical()) {
174 shape = "box";
175 } else {
176 for (unsigned j = 0; j < ig.Size(); j++) {
177 if (i != j && ig.HasEdge(i, j) && ig.GetNode(j).IsPhysical()) {
178 shape = "hexagon";
179 break;
180 }
181 }
182 }
183 return shape;
184 }
185 } // namespace
186
Dump(const std::string & name,bool skip_physical,std::ostream & out) const187 void InterferenceGraph::Dump(const std::string &name, bool skip_physical, std::ostream &out) const
188 {
189 auto transformed_name = name;
190 std::replace(transformed_name.begin(), transformed_name.end(), ':', '_');
191 out << "Nodes: " << Size() << "\n\n"
192 << "\ngraph " << transformed_name << " {\nnode [colorscheme=spectral9]\n";
193 auto size = Size();
194 if (size == 0) {
195 out << "}\n";
196 return;
197 }
198
199 // Map to colors
200 std::array<Register, std::numeric_limits<Register>::max()> colors {};
201 colors.fill(INVALID_REG);
202 Register cur_color = 0;
203
204 for (auto &node : GetNodes()) {
205 if (!(skip_physical && node.IsPhysical()) && colors[node.GetColor()] == INVALID_REG) {
206 colors[node.GetColor()] = cur_color;
207 cur_color++;
208 }
209 }
210
211 // Print header
212 for (unsigned i = 0; i < size; i++) {
213 if (skip_physical && GetNode(i).IsPhysical()) {
214 continue;
215 }
216 auto color = GetNode(i).GetColor();
217 out << i << " [color=" << unsigned(colors[color]) << ", xlabel=\"";
218 out << unsigned(color) << "\", tooltip=\"" << GetNode(i).GetLifeIntervals()->ToString<true>();
219 out << "\", shape=\"" << GetNodeShape(*this, i) << "\"]\n";
220 }
221
222 auto edge_printer = [this, &out, skip_physical](auto node_num) {
223 for (unsigned j = 0; j < node_num; j++) {
224 if (!(skip_physical && GetNode(j).IsPhysical()) && HasEdge(node_num, j)) {
225 if (GetNode(node_num).GetColor() == GetNode(j).GetColor() &&
226 GetNode(node_num).GetColor() != INVALID_REG) {
227 out << "Error: Same color\n";
228 }
229 out << node_num << "--" << j << "\n";
230 }
231 }
232 };
233
234 // Print edges
235 for (unsigned i = 1; i < size; i++) {
236 if (skip_physical && GetNode(i).IsPhysical()) {
237 continue;
238 }
239 edge_printer(i);
240 }
241
242 out << "}\n";
243 }
244 } // namespace panda::compiler
245