Line data Source code
1 : /* Sorting the nodes in the supergraph.
2 : Copyright (C) 2025-2026 Free Software Foundation, Inc.
3 : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it
8 : under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful, but
13 : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #define INCLUDE_SET
22 : #include "analyzer/common.h"
23 :
24 : #include "cgraph.h"
25 : #include "alloc-pool.h"
26 : #include "fibonacci_heap.h"
27 : #include "timevar.h"
28 :
29 : #include "analyzer/supergraph.h"
30 : #include "analyzer/analyzer-logging.h"
31 :
32 : #if ENABLE_ANALYZER
33 :
34 : namespace ana {
35 :
36 : /* Update m_nodes to be ORDERING.
37 : Update the m_id of all nodes to reflect the new orderding.
38 : This assumes that all nodes are in ORDERING; does not delete
39 : any underlying nodes. */
40 :
41 : void
42 3377 : supergraph::reorder_nodes_and_ids (const std::vector<supernode *> &ordering,
43 : logger *logger)
44 : {
45 3377 : LOG_SCOPE (logger);
46 :
47 3377 : m_nodes.truncate (0);
48 :
49 185466 : for (size_t new_id = 0; new_id < ordering.size (); ++new_id)
50 : {
51 182089 : supernode *snode = ordering[new_id];
52 182089 : if (logger)
53 : {
54 80 : if ((size_t)snode->m_id == new_id)
55 49 : logger->log ("SN %i is unchanged", snode->m_id);
56 : else
57 31 : logger->log ("old SN %i is now SN %li", snode->m_id, new_id);
58 : }
59 182089 : m_nodes.safe_push (snode);
60 182089 : snode->m_id = new_id;
61 : }
62 :
63 3377 : m_next_snode_id = m_nodes.length ();
64 3377 : }
65 :
66 : /* std::set::contains is C++20 onwards. */
67 : template <typename T>
68 : static bool
69 658495 : set_contains_p (const std::set<T> &s, T v)
70 : {
71 658495 : return s.find (v) != s.end ();
72 : }
73 :
74 : namespace {
75 :
76 : class sorting_worklist
77 : {
78 : public:
79 10201 : sorting_worklist ()
80 10201 : : m_queue (key_t (nullptr))
81 : {
82 10201 : }
83 :
84 : void add_node (supernode *n);
85 : supernode *take_next (logger *logger);
86 : bool contains_p (supernode *n) const;
87 :
88 : private:
89 : class key_t
90 : {
91 : public:
92 205024 : key_t (supernode *snode)
93 10201 : : m_snode (snode)
94 : {}
95 :
96 135989 : bool operator< (const key_t &other) const
97 : {
98 135989 : return cmp (*this, other) < 0;
99 : }
100 :
101 33010 : bool operator== (const key_t &other) const
102 : {
103 33010 : return cmp (*this, other) == 0;
104 : }
105 :
106 33010 : bool operator> (const key_t &other) const
107 : {
108 33010 : return !(*this == other || *this < other);
109 : }
110 :
111 : private:
112 : static int cmp (const key_t &ka, const key_t &kb);
113 : supernode *m_snode;
114 : };
115 :
116 : bool
117 : already_seen_all_predecessors_p (const supernode *n,
118 : logger *logger) const;
119 :
120 : std::set<supernode *> m_set_of_ordered_nodes;
121 : std::set<supernode *> m_set_of_queued_nodes;
122 : typedef fibonacci_heap<key_t, supernode> queue_t;
123 : queue_t m_queue;
124 : };
125 :
126 : void
127 194823 : sorting_worklist::add_node (supernode *n)
128 : {
129 194823 : m_queue.insert ({n}, n);
130 194823 : m_set_of_queued_nodes.insert (n);
131 194823 : }
132 :
133 : supernode *
134 192290 : sorting_worklist::take_next (logger *logger)
135 : {
136 192290 : if (m_queue.empty ())
137 : return nullptr;
138 :
139 182089 : std::vector<supernode *> rejected;
140 :
141 : /* First, try to find a node for which all predecessors
142 : have been ordered. */
143 194823 : while (!m_queue.empty ())
144 : {
145 193295 : supernode *candidate = m_queue.extract_min ();
146 :
147 : // n shouldn't be already within the ordering
148 193295 : gcc_assert (!set_contains_p (m_set_of_ordered_nodes, candidate));
149 :
150 193295 : if (logger)
151 85 : logger->log ("consider SN %i from worklist", candidate->m_id);
152 :
153 193295 : if (already_seen_all_predecessors_p (candidate, logger))
154 : {
155 180561 : if (logger)
156 76 : logger->log ("all predecessors of SN %i seen; using it",
157 : candidate->m_id);
158 191291 : for (auto r : rejected)
159 10730 : add_node (r);
160 180561 : m_set_of_ordered_nodes.insert (candidate);
161 180561 : m_set_of_queued_nodes.erase (candidate);
162 180561 : return candidate;
163 : }
164 : else
165 12734 : rejected.push_back (candidate);
166 : }
167 :
168 : /* Otherwise, simply use the first node. */
169 3532 : for (auto r : rejected)
170 2004 : add_node (r);
171 1528 : supernode *n = m_queue.extract_min ();
172 1528 : if (logger)
173 4 : logger->log ("using first in queue: SN %i", n->m_id);
174 1528 : m_set_of_ordered_nodes.insert (n);
175 1528 : m_set_of_queued_nodes.erase (n);
176 1528 : return n;
177 182089 : }
178 :
179 : bool
180 181929 : sorting_worklist::contains_p (supernode *n) const
181 : {
182 181929 : return (m_set_of_queued_nodes.find (n) != m_set_of_queued_nodes.end ()
183 181929 : || m_set_of_ordered_nodes.find (n) != m_set_of_ordered_nodes.end ());
184 : }
185 :
186 : int
187 168999 : sorting_worklist::key_t::cmp (const key_t &ka, const key_t &kb)
188 : {
189 168999 : const supernode *snode_a = ka.m_snode;
190 168999 : const supernode *snode_b = kb.m_snode;
191 :
192 : /* Sort by BB. */
193 168999 : if (int bb_cmp = snode_a->m_bb->index - snode_b->m_bb->index)
194 : return bb_cmp;
195 :
196 : /* Sort by existing id. */
197 44008 : return snode_a->m_id - snode_b->m_id;
198 : }
199 :
200 : bool
201 193295 : sorting_worklist::already_seen_all_predecessors_p (const supernode *n,
202 : logger *logger) const
203 : {
204 1011949 : for (auto e : n->m_preds)
205 465200 : if (!set_contains_p (m_set_of_ordered_nodes, e->m_src))
206 : {
207 12734 : if (logger)
208 9 : logger->log ("not yet ordered predecessor SN %i", e->m_src->m_id);
209 12734 : return false;
210 : }
211 : return true;
212 : }
213 :
214 : static std::vector<supernode *>
215 3377 : get_node_ordering (const supergraph &sg,
216 : logger *logger)
217 : {
218 3377 : LOG_SCOPE (logger);
219 :
220 3377 : std::vector<supernode *> ordering_vec;
221 :
222 3377 : cgraph_node *cgnode;
223 13578 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
224 : {
225 10201 : function *fun = cgnode->get_fun ();
226 :
227 10201 : sorting_worklist worklist;
228 :
229 10201 : supernode *start_node = sg.get_node_for_function_entry (*fun);
230 10201 : worklist.add_node (start_node);
231 :
232 : // Find the best node to add next in the ordering
233 192290 : while (supernode *next = worklist.take_next (logger))
234 : {
235 182089 : gcc_assert (next);
236 182089 : if (logger)
237 80 : logger->log ("next: SN: %i", next->m_id);
238 :
239 182089 : ordering_vec.push_back (next);
240 :
241 706094 : for (auto out_edge : next->m_succs)
242 : {
243 181929 : supernode *dest_node = out_edge->m_dest;
244 181929 : if (!worklist.contains_p (dest_node))
245 171888 : worklist.add_node (dest_node);
246 : }
247 182089 : }
248 10201 : }
249 :
250 6754 : return ordering_vec;
251 3377 : }
252 :
253 : } // anonymous namespace
254 :
255 : void
256 3377 : supergraph::sort_nodes (logger *logger)
257 : {
258 3377 : auto_timevar tv (TV_ANALYZER_SUPERGRAPH_SORTING);
259 3377 : LOG_SCOPE (logger);
260 :
261 3377 : const std::vector<supernode *> ordering = get_node_ordering (*this, logger);
262 3377 : reorder_nodes_and_ids (ordering, logger);
263 3377 : }
264 :
265 : } // namespace ana
266 :
267 : #endif /* #if ENABLE_ANALYZER */
|
