Branch data Line data Source code
1 : : /* DDG - Data Dependence Graph implementation.
2 : : Copyright (C) 2004-2025 Free Software Foundation, Inc.
3 : : Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it under
8 : : the terms of the GNU General Public License as published by the Free
9 : : Software Foundation; either version 3, or (at your option) any later
10 : : version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : : 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 : :
22 : : #include "config.h"
23 : : #include "system.h"
24 : : #include "coretypes.h"
25 : : #include "backend.h"
26 : : #include "rtl.h"
27 : : #include "df.h"
28 : : #include "insn-attr.h"
29 : : #include "sched-int.h"
30 : : #include "ddg.h"
31 : : #include "rtl-iter.h"
32 : :
33 : : #ifdef INSN_SCHEDULING
34 : :
35 : : /* Forward declarations. */
36 : : static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
37 : : static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
38 : : static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr);
39 : : static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr,
40 : : ddg_node_ptr, dep_t);
41 : : static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr,
42 : : dep_type, dep_data_type, int);
43 : : static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type,
44 : : dep_data_type, int, int);
45 : : static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr);
46 : :
47 : : /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
48 : : static bool mem_ref_p;
49 : :
50 : : /* Auxiliary function for mem_read_insn_p. */
51 : : static void
52 : 0 : mark_mem_use (rtx *x, void *)
53 : : {
54 : 0 : subrtx_iterator::array_type array;
55 : 0 : FOR_EACH_SUBRTX (iter, array, *x, NONCONST)
56 : 0 : if (MEM_P (*iter))
57 : : {
58 : 0 : mem_ref_p = true;
59 : 0 : break;
60 : : }
61 : 0 : }
62 : :
63 : : /* Returns nonzero if INSN reads from memory. */
64 : : static bool
65 : 0 : mem_read_insn_p (rtx_insn *insn)
66 : : {
67 : 0 : mem_ref_p = false;
68 : 0 : note_uses (&PATTERN (insn), mark_mem_use, NULL);
69 : 0 : return mem_ref_p;
70 : : }
71 : :
72 : : static void
73 : 0 : mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
74 : : {
75 : 0 : if (MEM_P (loc))
76 : 0 : mem_ref_p = true;
77 : 0 : }
78 : :
79 : : /* Returns nonzero if INSN writes to memory. */
80 : : static bool
81 : 0 : mem_write_insn_p (rtx_insn *insn)
82 : : {
83 : 0 : mem_ref_p = false;
84 : 0 : note_stores (insn, mark_mem_store, NULL);
85 : 0 : return mem_ref_p;
86 : : }
87 : :
88 : : /* Returns nonzero if X has access to memory. */
89 : : static bool
90 : 0 : rtx_mem_access_p (rtx x)
91 : : {
92 : 0 : int i, j;
93 : 0 : const char *fmt;
94 : 0 : enum rtx_code code;
95 : :
96 : 0 : if (x == 0)
97 : : return false;
98 : :
99 : 0 : if (MEM_P (x))
100 : : return true;
101 : :
102 : 0 : code = GET_CODE (x);
103 : 0 : fmt = GET_RTX_FORMAT (code);
104 : 0 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
105 : : {
106 : 0 : if (fmt[i] == 'e')
107 : : {
108 : 0 : if (rtx_mem_access_p (XEXP (x, i)))
109 : : return true;
110 : : }
111 : 0 : else if (fmt[i] == 'E')
112 : 0 : for (j = 0; j < XVECLEN (x, i); j++)
113 : : {
114 : 0 : if (rtx_mem_access_p (XVECEXP (x, i, j)))
115 : : return true;
116 : : }
117 : : }
118 : : return false;
119 : : }
120 : :
121 : : /* Returns nonzero if INSN reads to or writes from memory. */
122 : : static bool
123 : 0 : mem_access_insn_p (rtx_insn *insn)
124 : : {
125 : 0 : return rtx_mem_access_p (PATTERN (insn));
126 : : }
127 : :
128 : : /* Return true if DEF_INSN contains address being auto-inc or auto-dec
129 : : which is used in USE_INSN. Otherwise return false. The result is
130 : : being used to decide whether to remove the edge between def_insn and
131 : : use_insn when -fmodulo-sched-allow-regmoves is set. This function
132 : : doesn't need to consider the specific address register; no reg_moves
133 : : will be allowed for any life range defined by def_insn and used
134 : : by use_insn, if use_insn uses an address register auto-inc'ed by
135 : : def_insn. */
136 : : bool
137 : 0 : autoinc_var_is_used_p (rtx_insn *def_insn, rtx_insn *use_insn)
138 : : {
139 : 0 : rtx note;
140 : :
141 : 0 : for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
142 : 0 : if (REG_NOTE_KIND (note) == REG_INC
143 : 0 : && reg_referenced_p (XEXP (note, 0), PATTERN (use_insn)))
144 : : return true;
145 : :
146 : : return false;
147 : : }
148 : :
149 : : /* Return true if one of the definitions in INSN has MODE_CC. Otherwise
150 : : return false. */
151 : : static bool
152 : 0 : def_has_ccmode_p (rtx_insn *insn)
153 : : {
154 : 0 : df_ref def;
155 : :
156 : 0 : FOR_EACH_INSN_DEF (def, insn)
157 : : {
158 : 0 : machine_mode mode = GET_MODE (DF_REF_REG (def));
159 : :
160 : 0 : if (GET_MODE_CLASS (mode) == MODE_CC)
161 : : return true;
162 : : }
163 : :
164 : : return false;
165 : : }
166 : :
167 : : /* Computes the dependence parameters (latency, distance etc.), creates
168 : : a ddg_edge and adds it to the given DDG. */
169 : : static void
170 : 0 : create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node,
171 : : ddg_node_ptr dest_node, dep_t link)
172 : : {
173 : 0 : ddg_edge_ptr e;
174 : 0 : int latency, distance = 0;
175 : 0 : dep_type t = TRUE_DEP;
176 : 0 : dep_data_type dt = (mem_access_insn_p (src_node->insn)
177 : 0 : && mem_access_insn_p (dest_node->insn) ? MEM_DEP
178 : 0 : : REG_DEP);
179 : 0 : gcc_assert (src_node->cuid < dest_node->cuid);
180 : 0 : gcc_assert (link);
181 : :
182 : : /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
183 : 0 : if (DEP_TYPE (link) == REG_DEP_ANTI)
184 : : t = ANTI_DEP;
185 : 0 : else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
186 : 0 : t = OUTPUT_DEP;
187 : :
188 : : /* We currently choose not to create certain anti-deps edges and
189 : : compensate for that by generating reg-moves based on the life-range
190 : : analysis. The anti-deps that will be deleted are the ones which
191 : : have true-deps edges in the opposite direction (in other words
192 : : the kernel has only one def of the relevant register).
193 : : If the address that is being auto-inc or auto-dec in DEST_NODE
194 : : is used in SRC_NODE then do not remove the edge to make sure
195 : : reg-moves will not be created for this address.
196 : : TODO: support the removal of all anti-deps edges, i.e. including those
197 : : whose register has multiple defs in the loop. */
198 : 0 : if (flag_modulo_sched_allow_regmoves
199 : 0 : && (t == ANTI_DEP && dt == REG_DEP)
200 : 0 : && !def_has_ccmode_p (dest_node->insn)
201 : 0 : && !autoinc_var_is_used_p (dest_node->insn, src_node->insn))
202 : : {
203 : 0 : rtx set;
204 : :
205 : 0 : set = single_set (dest_node->insn);
206 : : /* TODO: Handle registers that REG_P is not true for them, i.e.
207 : : subregs and special registers. */
208 : 0 : if (set && REG_P (SET_DEST (set)))
209 : : {
210 : 0 : int regno = REGNO (SET_DEST (set));
211 : 0 : df_ref first_def;
212 : 0 : class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
213 : :
214 : 0 : first_def = df_bb_regno_first_def_find (g->bb, regno);
215 : 0 : gcc_assert (first_def);
216 : :
217 : 0 : if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)))
218 : : return;
219 : : }
220 : : }
221 : :
222 : 0 : latency = dep_cost (link);
223 : 0 : e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
224 : 0 : add_edge_to_ddg (g, e);
225 : : }
226 : :
227 : : /* The same as the above function, but it doesn't require a link parameter. */
228 : : static void
229 : 0 : create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
230 : : dep_type d_t, dep_data_type d_dt, int distance)
231 : : {
232 : 0 : ddg_edge_ptr e;
233 : 0 : int l;
234 : 0 : enum reg_note dep_kind;
235 : 0 : struct _dep _dep, *dep = &_dep;
236 : :
237 : 0 : if (d_t == ANTI_DEP)
238 : : dep_kind = REG_DEP_ANTI;
239 : : else if (d_t == OUTPUT_DEP)
240 : : dep_kind = REG_DEP_OUTPUT;
241 : : else
242 : : {
243 : 0 : gcc_assert (d_t == TRUE_DEP);
244 : :
245 : : dep_kind = REG_DEP_TRUE;
246 : : }
247 : :
248 : 0 : init_dep (dep, from->insn, to->insn, dep_kind);
249 : :
250 : 0 : l = dep_cost (dep);
251 : :
252 : 0 : e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
253 : 0 : if (distance > 0)
254 : 0 : add_backarc_to_ddg (g, e);
255 : : else
256 : 0 : add_edge_to_ddg (g, e);
257 : 0 : }
258 : :
259 : :
260 : : /* Given a downwards exposed register def LAST_DEF (which is the last
261 : : definition of that register in the bb), add inter-loop true dependences
262 : : to all its uses in the next iteration, an output dependence to the
263 : : first def of the same register (possibly itself) in the next iteration
264 : : and anti-dependences from its uses in the current iteration to the
265 : : first definition in the next iteration. */
266 : : static void
267 : 0 : add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
268 : : {
269 : 0 : struct df_link *r_use;
270 : 0 : int has_use_in_bb_p = false;
271 : 0 : int regno = DF_REF_REGNO (last_def);
272 : 0 : ddg_node_ptr last_def_node = get_node_of_insn (g, DF_REF_INSN (last_def));
273 : 0 : df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
274 : 0 : ddg_node_ptr first_def_node = get_node_of_insn (g, DF_REF_INSN (first_def));
275 : 0 : ddg_node_ptr use_node;
276 : :
277 : 0 : gcc_assert (last_def_node && first_def && first_def_node);
278 : :
279 : 0 : if (flag_checking && DF_REF_ID (last_def) != DF_REF_ID (first_def))
280 : : {
281 : 0 : class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
282 : 0 : gcc_assert (!bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)));
283 : : }
284 : :
285 : : /* Create inter-loop true dependences and anti dependences. */
286 : 0 : for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
287 : : {
288 : 0 : if (DF_REF_BB (r_use->ref) != g->bb)
289 : 0 : continue;
290 : :
291 : 0 : gcc_assert (!DF_REF_IS_ARTIFICIAL (r_use->ref)
292 : : && DF_REF_INSN_INFO (r_use->ref) != NULL);
293 : :
294 : 0 : rtx_insn *use_insn = DF_REF_INSN (r_use->ref);
295 : :
296 : 0 : if (DEBUG_INSN_P (use_insn))
297 : 0 : continue;
298 : :
299 : : /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
300 : 0 : use_node = get_node_of_insn (g, use_insn);
301 : 0 : gcc_assert (use_node);
302 : 0 : has_use_in_bb_p = true;
303 : 0 : if (use_node->cuid <= last_def_node->cuid)
304 : : {
305 : : /* Add true deps from last_def to it's uses in the next
306 : : iteration. Any such upwards exposed use appears before
307 : : the last_def def. */
308 : 0 : create_ddg_dep_no_link (g, last_def_node, use_node,
309 : : TRUE_DEP, REG_DEP, 1);
310 : : }
311 : : else
312 : : {
313 : : /* Add anti deps from last_def's uses in the current iteration
314 : : to the first def in the next iteration. We do not add ANTI
315 : : dep when there is an intra-loop TRUE dep in the opposite
316 : : direction, but use regmoves to fix such disregarded ANTI
317 : : deps when broken. If the first_def reaches the USE then
318 : : there is such a dep.
319 : : Always create the edge if the use node is a branch in
320 : : order to prevent the creation of reg-moves.
321 : : If the address that is being auto-inc or auto-dec in LAST_DEF
322 : : is used in USE_INSN then do not remove the edge to make sure
323 : : reg-moves will not be created for that address. */
324 : 0 : if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
325 : 0 : || !flag_modulo_sched_allow_regmoves
326 : 0 : || JUMP_P (use_node->insn)
327 : 0 : || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn)
328 : 0 : || def_has_ccmode_p (DF_REF_INSN (last_def)))
329 : 0 : create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
330 : : REG_DEP, 1);
331 : : }
332 : : }
333 : : /* Create an inter-loop output dependence between LAST_DEF (which is the
334 : : last def in its block, being downwards exposed) and the first def in
335 : : its block. Avoid creating a self output dependence. Avoid creating
336 : : an output dependence if there is a dependence path between the two
337 : : defs starting with a true dependence to a use which can be in the
338 : : next iteration; followed by an anti dependence of that use to the
339 : : first def (i.e. if there is a use between the two defs.) */
340 : 0 : if (!has_use_in_bb_p && DF_REF_ID (last_def) != DF_REF_ID (first_def))
341 : 0 : create_ddg_dep_no_link (g, last_def_node, first_def_node,
342 : : OUTPUT_DEP, REG_DEP, 1);
343 : 0 : }
344 : :
345 : : /* Build inter-loop dependencies, by looking at DF analysis backwards. */
346 : : static void
347 : 0 : build_inter_loop_deps (ddg_ptr g)
348 : : {
349 : 0 : unsigned rd_num;
350 : 0 : class df_rd_bb_info *rd_bb_info;
351 : 0 : bitmap_iterator bi;
352 : :
353 : 0 : rd_bb_info = DF_RD_BB_INFO (g->bb);
354 : :
355 : : /* Find inter-loop register output, true and anti deps. */
356 : 0 : EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi)
357 : : {
358 : 0 : df_ref rd = DF_DEFS_GET (rd_num);
359 : :
360 : 0 : add_cross_iteration_register_deps (g, rd);
361 : : }
362 : 0 : }
363 : :
364 : :
365 : : /* Return true if two specified instructions have mem expr with conflict
366 : : alias sets. */
367 : : static bool
368 : 0 : insns_may_alias_p (rtx_insn *insn1, rtx_insn *insn2)
369 : : {
370 : 0 : subrtx_iterator::array_type array1;
371 : 0 : subrtx_iterator::array_type array2;
372 : 0 : FOR_EACH_SUBRTX (iter1, array1, PATTERN (insn1), NONCONST)
373 : : {
374 : 0 : const_rtx x1 = *iter1;
375 : 0 : if (MEM_P (x1))
376 : 0 : FOR_EACH_SUBRTX (iter2, array2, PATTERN (insn2), NONCONST)
377 : : {
378 : 0 : const_rtx x2 = *iter2;
379 : 0 : if (MEM_P (x2) && may_alias_p (x2, x1))
380 : 0 : return true;
381 : : }
382 : : }
383 : 0 : return false;
384 : 0 : }
385 : :
386 : : /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
387 : : to ddg G. */
388 : : static void
389 : 0 : add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
390 : : {
391 : :
392 : 0 : if ((from->cuid == to->cuid)
393 : 0 : || !insns_may_alias_p (from->insn, to->insn))
394 : : /* Do not create edge if memory references have disjoint alias sets
395 : : or 'to' and 'from' are the same instruction. */
396 : 0 : return;
397 : :
398 : 0 : if (mem_write_insn_p (from->insn))
399 : : {
400 : 0 : if (mem_read_insn_p (to->insn))
401 : 0 : create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 0);
402 : : else
403 : 0 : create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 0);
404 : : }
405 : 0 : else if (!mem_read_insn_p (to->insn))
406 : 0 : create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 0);
407 : : }
408 : :
409 : : /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
410 : : to ddg G. */
411 : : static void
412 : 0 : add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
413 : : {
414 : 0 : if (!insns_may_alias_p (from->insn, to->insn))
415 : : /* Do not create edge if memory references have disjoint alias sets. */
416 : : return;
417 : :
418 : 0 : if (mem_write_insn_p (from->insn))
419 : : {
420 : 0 : if (mem_read_insn_p (to->insn))
421 : 0 : create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
422 : 0 : else if (from->cuid != to->cuid)
423 : 0 : create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
424 : : }
425 : : else
426 : : {
427 : 0 : if (mem_read_insn_p (to->insn))
428 : : return;
429 : 0 : else if (from->cuid != to->cuid)
430 : : {
431 : 0 : create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
432 : 0 : create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
433 : : }
434 : : }
435 : : }
436 : :
437 : : /* Perform intra-block Data Dependency analysis and connect the nodes in
438 : : the DDG. We assume the loop has a single basic block. */
439 : : static void
440 : 0 : build_intra_loop_deps (ddg_ptr g)
441 : : {
442 : 0 : int i;
443 : : /* Hold the dependency analysis state during dependency calculations. */
444 : 0 : class deps_desc tmp_deps;
445 : 0 : rtx_insn *head, *tail;
446 : :
447 : : /* Build the dependence information, using the sched_analyze function. */
448 : 0 : init_deps_global ();
449 : 0 : init_deps (&tmp_deps, false);
450 : :
451 : : /* Do the intra-block data dependence analysis for the given block. */
452 : 0 : get_ebb_head_tail (g->bb, g->bb, &head, &tail);
453 : 0 : sched_analyze (&tmp_deps, head, tail);
454 : :
455 : : /* Build intra-loop data dependencies using the scheduler dependency
456 : : analysis. */
457 : 0 : for (i = 0; i < g->num_nodes; i++)
458 : : {
459 : 0 : ddg_node_ptr dest_node = &g->nodes[i];
460 : 0 : sd_iterator_def sd_it;
461 : 0 : dep_t dep;
462 : :
463 : 0 : FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
464 : : {
465 : 0 : rtx_insn *src_insn = DEP_PRO (dep);
466 : 0 : ddg_node_ptr src_node = get_node_of_insn (g, src_insn);
467 : :
468 : 0 : if (!src_node)
469 : 0 : continue;
470 : :
471 : 0 : create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
472 : : }
473 : :
474 : : /* If this insn modifies memory, add an edge to all insns that access
475 : : memory. */
476 : 0 : if (mem_access_insn_p (dest_node->insn))
477 : : {
478 : : int j;
479 : :
480 : 0 : for (j = 0; j <= i; j++)
481 : : {
482 : 0 : ddg_node_ptr j_node = &g->nodes[j];
483 : :
484 : 0 : if (mem_access_insn_p (j_node->insn))
485 : : {
486 : : /* Don't bother calculating inter-loop dep if an intra-loop dep
487 : : already exists. */
488 : 0 : if (! bitmap_bit_p (dest_node->successors, j))
489 : 0 : add_inter_loop_mem_dep (g, dest_node, j_node);
490 : : /* If -fmodulo-sched-allow-regmoves
491 : : is set certain anti-dep edges are not created.
492 : : It might be that these anti-dep edges are on the
493 : : path from one memory instruction to another such that
494 : : removing these edges could cause a violation of the
495 : : memory dependencies. Thus we add intra edges between
496 : : every two memory instructions in this case. */
497 : 0 : if (flag_modulo_sched_allow_regmoves
498 : 0 : && !bitmap_bit_p (dest_node->predecessors, j))
499 : 0 : add_intra_loop_mem_dep (g, j_node, dest_node);
500 : : }
501 : : }
502 : : }
503 : : }
504 : :
505 : : /* Free the INSN_LISTs. */
506 : 0 : finish_deps_global ();
507 : 0 : free_deps (&tmp_deps);
508 : :
509 : : /* Free dependencies. */
510 : 0 : sched_free_deps (head, tail, false);
511 : 0 : }
512 : :
513 : :
514 : : /* Given a basic block, create its DDG and return a pointer to a variable
515 : : of ddg type that represents it.
516 : : Initialize the ddg structure fields to the appropriate values. */
517 : : ddg_ptr
518 : 0 : create_ddg (basic_block bb, int closing_branch_deps)
519 : : {
520 : 0 : ddg_ptr g;
521 : 0 : rtx_insn *insn, *first_note;
522 : 0 : int i, j;
523 : 0 : int num_nodes = 0;
524 : :
525 : 0 : g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
526 : :
527 : 0 : g->bb = bb;
528 : 0 : g->closing_branch_deps = closing_branch_deps;
529 : :
530 : : /* Count the number of insns in the BB. */
531 : 0 : for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
532 : 0 : insn = NEXT_INSN (insn))
533 : : {
534 : 0 : if (!INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
535 : 0 : continue;
536 : :
537 : 0 : if (NONDEBUG_INSN_P (insn))
538 : : {
539 : 0 : if (mem_read_insn_p (insn))
540 : 0 : g->num_loads++;
541 : 0 : if (mem_write_insn_p (insn))
542 : 0 : g->num_stores++;
543 : 0 : num_nodes++;
544 : : }
545 : : }
546 : :
547 : : /* There is nothing to do for this BB. */
548 : 0 : if (num_nodes <= 1)
549 : : {
550 : 0 : free (g);
551 : 0 : return NULL;
552 : : }
553 : :
554 : : /* Allocate the nodes array, and initialize the nodes. */
555 : 0 : g->num_nodes = num_nodes;
556 : 0 : g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
557 : 0 : g->closing_branch = NULL;
558 : 0 : i = 0;
559 : 0 : first_note = NULL;
560 : 0 : for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
561 : 0 : insn = NEXT_INSN (insn))
562 : : {
563 : 0 : if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
564 : 0 : continue;
565 : :
566 : 0 : if (!first_note && (INSN_P (insn) || NOTE_P (insn)))
567 : 0 : first_note = insn;
568 : :
569 : 0 : if (!INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
570 : 0 : continue;
571 : :
572 : 0 : if (JUMP_P (insn))
573 : : {
574 : 0 : gcc_assert (!g->closing_branch);
575 : 0 : g->closing_branch = &g->nodes[i];
576 : : }
577 : :
578 : 0 : if (NONDEBUG_INSN_P (insn))
579 : : {
580 : 0 : g->nodes[i].cuid = i;
581 : 0 : g->nodes[i].successors = sbitmap_alloc (num_nodes);
582 : 0 : bitmap_clear (g->nodes[i].successors);
583 : 0 : g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
584 : 0 : bitmap_clear (g->nodes[i].predecessors);
585 : :
586 : 0 : gcc_checking_assert (first_note);
587 : 0 : g->nodes[i].first_note = first_note;
588 : :
589 : 0 : g->nodes[i].aux.count = -1;
590 : 0 : g->nodes[i].max_dist = XCNEWVEC (int, num_nodes);
591 : 0 : for (j = 0; j < num_nodes; j++)
592 : 0 : g->nodes[i].max_dist[j] = -1;
593 : :
594 : 0 : g->nodes[i++].insn = insn;
595 : : }
596 : : first_note = NULL;
597 : : }
598 : :
599 : : /* We must have found a branch in DDG. */
600 : 0 : gcc_assert (g->closing_branch);
601 : :
602 : :
603 : : /* Build the data dependency graph. */
604 : 0 : build_intra_loop_deps (g);
605 : 0 : build_inter_loop_deps (g);
606 : 0 : return g;
607 : : }
608 : :
609 : : /* Free all the memory allocated for the DDG. */
610 : : void
611 : 0 : free_ddg (ddg_ptr g)
612 : : {
613 : 0 : int i;
614 : :
615 : 0 : if (!g)
616 : : return;
617 : :
618 : 0 : for (i = 0; i < g->num_nodes; i++)
619 : : {
620 : 0 : ddg_edge_ptr e = g->nodes[i].out;
621 : :
622 : 0 : while (e)
623 : : {
624 : 0 : ddg_edge_ptr next = e->next_out;
625 : :
626 : 0 : free (e);
627 : 0 : e = next;
628 : : }
629 : 0 : sbitmap_free (g->nodes[i].successors);
630 : 0 : sbitmap_free (g->nodes[i].predecessors);
631 : 0 : free (g->nodes[i].max_dist);
632 : : }
633 : 0 : if (g->num_backarcs > 0)
634 : 0 : free (g->backarcs);
635 : 0 : free (g->nodes);
636 : 0 : free (g);
637 : : }
638 : :
639 : : void
640 : 0 : print_ddg_edge (FILE *file, ddg_edge_ptr e)
641 : : {
642 : 0 : char dep_c;
643 : :
644 : 0 : switch (e->type)
645 : : {
646 : : case OUTPUT_DEP :
647 : : dep_c = 'O';
648 : : break;
649 : 0 : case ANTI_DEP :
650 : 0 : dep_c = 'A';
651 : 0 : break;
652 : 0 : default:
653 : 0 : dep_c = 'T';
654 : : }
655 : :
656 : 0 : fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
657 : 0 : dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
658 : 0 : }
659 : :
660 : : /* Print the DDG nodes with there in/out edges to the dump file. */
661 : : void
662 : 0 : print_ddg (FILE *file, ddg_ptr g)
663 : : {
664 : 0 : int i;
665 : :
666 : 0 : for (i = 0; i < g->num_nodes; i++)
667 : : {
668 : 0 : ddg_edge_ptr e;
669 : :
670 : 0 : fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
671 : 0 : print_rtl_single (file, g->nodes[i].insn);
672 : 0 : fprintf (file, "OUT ARCS: ");
673 : 0 : for (e = g->nodes[i].out; e; e = e->next_out)
674 : 0 : print_ddg_edge (file, e);
675 : :
676 : 0 : fprintf (file, "\nIN ARCS: ");
677 : 0 : for (e = g->nodes[i].in; e; e = e->next_in)
678 : 0 : print_ddg_edge (file, e);
679 : :
680 : 0 : fprintf (file, "\n");
681 : : }
682 : 0 : }
683 : :
684 : : /* Print the given DDG in VCG format. */
685 : : DEBUG_FUNCTION void
686 : 0 : vcg_print_ddg (FILE *file, ddg_ptr g)
687 : : {
688 : 0 : int src_cuid;
689 : :
690 : 0 : fprintf (file, "graph: {\n");
691 : 0 : for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
692 : : {
693 : 0 : ddg_edge_ptr e;
694 : 0 : int src_uid = INSN_UID (g->nodes[src_cuid].insn);
695 : :
696 : 0 : fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
697 : 0 : print_rtl_single (file, g->nodes[src_cuid].insn);
698 : 0 : fprintf (file, "\"}\n");
699 : 0 : for (e = g->nodes[src_cuid].out; e; e = e->next_out)
700 : : {
701 : 0 : int dst_uid = INSN_UID (e->dest->insn);
702 : 0 : int dst_cuid = e->dest->cuid;
703 : :
704 : : /* Give the backarcs a different color. */
705 : 0 : if (e->distance > 0)
706 : 0 : fprintf (file, "backedge: {color: red ");
707 : : else
708 : 0 : fprintf (file, "edge: { ");
709 : :
710 : 0 : fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
711 : 0 : fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
712 : 0 : fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
713 : : }
714 : : }
715 : 0 : fprintf (file, "}\n");
716 : 0 : }
717 : :
718 : : /* Dump the sccs in SCCS. */
719 : : void
720 : 0 : print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
721 : : {
722 : 0 : unsigned int u = 0;
723 : 0 : sbitmap_iterator sbi;
724 : 0 : int i;
725 : :
726 : 0 : if (!file)
727 : 0 : return;
728 : :
729 : 0 : fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
730 : 0 : for (i = 0; i < sccs->num_sccs; i++)
731 : : {
732 : 0 : fprintf (file, "SCC number: %d\n", i);
733 : 0 : EXECUTE_IF_SET_IN_BITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
734 : : {
735 : 0 : fprintf (file, "insn num %d\n", u);
736 : 0 : print_rtl_single (file, g->nodes[u].insn);
737 : : }
738 : : }
739 : 0 : fprintf (file, "\n");
740 : : }
741 : :
742 : : /* Create an edge and initialize it with given values. */
743 : : static ddg_edge_ptr
744 : 0 : create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
745 : : dep_type t, dep_data_type dt, int l, int d)
746 : : {
747 : 0 : ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
748 : :
749 : 0 : e->src = src;
750 : 0 : e->dest = dest;
751 : 0 : e->type = t;
752 : 0 : e->data_type = dt;
753 : 0 : e->latency = l;
754 : 0 : e->distance = d;
755 : 0 : e->next_in = e->next_out = NULL;
756 : 0 : e->in_scc = false;
757 : 0 : return e;
758 : : }
759 : :
760 : : /* Add the given edge to the in/out linked lists of the DDG nodes. */
761 : : static void
762 : 0 : add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
763 : : {
764 : 0 : ddg_node_ptr src = e->src;
765 : 0 : ddg_node_ptr dest = e->dest;
766 : :
767 : : /* Should have allocated the sbitmaps. */
768 : 0 : gcc_assert (src->successors && dest->predecessors);
769 : :
770 : 0 : bitmap_set_bit (src->successors, dest->cuid);
771 : 0 : bitmap_set_bit (dest->predecessors, src->cuid);
772 : 0 : e->next_in = dest->in;
773 : 0 : dest->in = e;
774 : 0 : e->next_out = src->out;
775 : 0 : src->out = e;
776 : 0 : }
777 : :
778 : :
779 : :
780 : : /* Algorithm for computing the recurrence_length of an scc. We assume at
781 : : for now that cycles in the data dependence graph contain a single backarc.
782 : : This simplifies the algorithm, and can be generalized later. */
783 : : static void
784 : 0 : set_recurrence_length (ddg_scc_ptr scc)
785 : : {
786 : 0 : int j;
787 : 0 : int result = -1;
788 : :
789 : 0 : for (j = 0; j < scc->num_backarcs; j++)
790 : : {
791 : 0 : ddg_edge_ptr backarc = scc->backarcs[j];
792 : 0 : int distance = backarc->distance;
793 : 0 : ddg_node_ptr src = backarc->dest;
794 : 0 : ddg_node_ptr dest = backarc->src;
795 : 0 : int length = src->max_dist[dest->cuid];
796 : :
797 : 0 : if (length < 0)
798 : 0 : continue;
799 : :
800 : 0 : length += backarc->latency;
801 : 0 : result = MAX (result, (length / distance));
802 : : }
803 : 0 : scc->recurrence_length = result;
804 : 0 : }
805 : :
806 : : /* Create a new SCC given the set of its nodes. Compute its recurrence_length
807 : : and mark edges that belong to this scc. */
808 : : static ddg_scc_ptr
809 : 0 : create_scc (ddg_ptr g, sbitmap nodes, int id)
810 : : {
811 : 0 : ddg_scc_ptr scc;
812 : 0 : unsigned int u = 0;
813 : 0 : sbitmap_iterator sbi;
814 : :
815 : 0 : scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
816 : 0 : scc->backarcs = NULL;
817 : 0 : scc->num_backarcs = 0;
818 : 0 : scc->nodes = sbitmap_alloc (g->num_nodes);
819 : 0 : bitmap_copy (scc->nodes, nodes);
820 : :
821 : : /* Mark the backarcs that belong to this SCC. */
822 : 0 : EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
823 : : {
824 : 0 : ddg_edge_ptr e;
825 : 0 : ddg_node_ptr n = &g->nodes[u];
826 : :
827 : 0 : gcc_assert (n->aux.count == -1);
828 : 0 : n->aux.count = id;
829 : :
830 : 0 : for (e = n->out; e; e = e->next_out)
831 : 0 : if (bitmap_bit_p (nodes, e->dest->cuid))
832 : : {
833 : 0 : e->in_scc = true;
834 : 0 : if (e->distance > 0)
835 : 0 : add_backarc_to_scc (scc, e);
836 : : }
837 : : }
838 : :
839 : 0 : return scc;
840 : : }
841 : :
842 : : /* Cleans the memory allocation of a given SCC. */
843 : : static void
844 : 0 : free_scc (ddg_scc_ptr scc)
845 : : {
846 : 0 : if (!scc)
847 : : return;
848 : :
849 : 0 : sbitmap_free (scc->nodes);
850 : 0 : if (scc->num_backarcs > 0)
851 : 0 : free (scc->backarcs);
852 : 0 : free (scc);
853 : : }
854 : :
855 : :
856 : : /* Add a given edge known to be a backarc to the given DDG. */
857 : : static void
858 : 0 : add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
859 : : {
860 : 0 : int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
861 : :
862 : 0 : add_edge_to_ddg (g, e);
863 : 0 : g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
864 : 0 : g->backarcs[g->num_backarcs++] = e;
865 : 0 : }
866 : :
867 : : /* Add backarc to an SCC. */
868 : : static void
869 : 0 : add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
870 : : {
871 : 0 : int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
872 : :
873 : 0 : scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
874 : 0 : scc->backarcs[scc->num_backarcs++] = e;
875 : 0 : }
876 : :
877 : : /* Add the given SCC to the DDG. */
878 : : static void
879 : 0 : add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
880 : : {
881 : 0 : int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
882 : :
883 : 0 : g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
884 : 0 : g->sccs[g->num_sccs++] = scc;
885 : 0 : }
886 : :
887 : : /* Given the instruction INSN return the node that represents it. */
888 : : ddg_node_ptr
889 : 0 : get_node_of_insn (ddg_ptr g, rtx_insn *insn)
890 : : {
891 : 0 : int i;
892 : :
893 : 0 : for (i = 0; i < g->num_nodes; i++)
894 : 0 : if (insn == g->nodes[i].insn)
895 : : return &g->nodes[i];
896 : : return NULL;
897 : : }
898 : :
899 : : /* Given a set OPS of nodes in the DDG, find the set of their successors
900 : : which are not in OPS, and set their bits in SUCC. Bits corresponding to
901 : : OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
902 : : void
903 : 0 : find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
904 : : {
905 : 0 : unsigned int i = 0;
906 : 0 : sbitmap_iterator sbi;
907 : :
908 : 0 : EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi)
909 : : {
910 : 0 : const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
911 : 0 : bitmap_ior (succ, succ, node_succ);
912 : 0 : };
913 : :
914 : : /* We want those that are not in ops. */
915 : 0 : bitmap_and_compl (succ, succ, ops);
916 : 0 : }
917 : :
918 : : /* Given a set OPS of nodes in the DDG, find the set of their predecessors
919 : : which are not in OPS, and set their bits in PREDS. Bits corresponding to
920 : : OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
921 : : void
922 : 0 : find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
923 : : {
924 : 0 : unsigned int i = 0;
925 : 0 : sbitmap_iterator sbi;
926 : :
927 : 0 : EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi)
928 : : {
929 : 0 : const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
930 : 0 : bitmap_ior (preds, preds, node_preds);
931 : 0 : };
932 : :
933 : : /* We want those that are not in ops. */
934 : 0 : bitmap_and_compl (preds, preds, ops);
935 : 0 : }
936 : :
937 : :
938 : : /* Compare function to be passed to qsort to order the backarcs in descending
939 : : recMII order. */
940 : : static int
941 : 0 : compare_sccs (const void *s1, const void *s2)
942 : : {
943 : 0 : const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
944 : 0 : const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
945 : 0 : return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
946 : :
947 : : }
948 : :
949 : : /* Order the backarcs in descending recMII order using compare_sccs. */
950 : : static void
951 : 0 : order_sccs (ddg_all_sccs_ptr g)
952 : : {
953 : 0 : qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
954 : : (int (*) (const void *, const void *)) compare_sccs);
955 : 0 : }
956 : :
957 : : /* Check that every node in SCCS belongs to exactly one strongly connected
958 : : component and that no element of SCCS is empty. */
959 : : static void
960 : 0 : check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
961 : : {
962 : 0 : int i = 0;
963 : 0 : auto_sbitmap tmp (num_nodes);
964 : :
965 : 0 : bitmap_clear (tmp);
966 : 0 : for (i = 0; i < sccs->num_sccs; i++)
967 : : {
968 : 0 : gcc_assert (!bitmap_empty_p (sccs->sccs[i]->nodes));
969 : : /* Verify that every node in sccs is in exactly one strongly
970 : : connected component. */
971 : 0 : gcc_assert (!bitmap_intersect_p (tmp, sccs->sccs[i]->nodes));
972 : 0 : bitmap_ior (tmp, tmp, sccs->sccs[i]->nodes);
973 : : }
974 : 0 : }
975 : :
976 : : /* Perform the Strongly Connected Components decomposing algorithm on the
977 : : DDG and return DDG_ALL_SCCS structure that contains them. */
978 : : ddg_all_sccs_ptr
979 : 0 : create_ddg_all_sccs (ddg_ptr g)
980 : : {
981 : 0 : int i, j, k, scc, way;
982 : 0 : int num_nodes = g->num_nodes;
983 : 0 : auto_sbitmap from (num_nodes);
984 : 0 : auto_sbitmap to (num_nodes);
985 : 0 : auto_sbitmap scc_nodes (num_nodes);
986 : 0 : ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
987 : 0 : xmalloc (sizeof (struct ddg_all_sccs));
988 : :
989 : 0 : sccs->ddg = g;
990 : 0 : sccs->sccs = NULL;
991 : 0 : sccs->num_sccs = 0;
992 : :
993 : 0 : for (i = 0; i < g->num_backarcs; i++)
994 : : {
995 : 0 : ddg_scc_ptr scc;
996 : 0 : ddg_edge_ptr backarc = g->backarcs[i];
997 : 0 : ddg_node_ptr src = backarc->src;
998 : 0 : ddg_node_ptr dest = backarc->dest;
999 : :
1000 : : /* If the backarc already belongs to an SCC, continue. */
1001 : 0 : if (backarc->in_scc)
1002 : 0 : continue;
1003 : :
1004 : 0 : bitmap_clear (scc_nodes);
1005 : 0 : bitmap_clear (from);
1006 : 0 : bitmap_clear (to);
1007 : 0 : bitmap_set_bit (from, dest->cuid);
1008 : 0 : bitmap_set_bit (to, src->cuid);
1009 : :
1010 : 0 : if (find_nodes_on_paths (scc_nodes, g, from, to))
1011 : : {
1012 : 0 : scc = create_scc (g, scc_nodes, sccs->num_sccs);
1013 : 0 : add_scc_to_ddg (sccs, scc);
1014 : : }
1015 : : }
1016 : :
1017 : : /* Init max_dist arrays for Floyd–Warshall-like
1018 : : longest patch calculation algorithm. */
1019 : 0 : for (k = 0; k < num_nodes; k++)
1020 : : {
1021 : 0 : ddg_edge_ptr e;
1022 : 0 : ddg_node_ptr n = &g->nodes[k];
1023 : :
1024 : 0 : if (n->aux.count == -1)
1025 : 0 : continue;
1026 : :
1027 : 0 : n->max_dist[k] = 0;
1028 : 0 : for (e = n->out; e; e = e->next_out)
1029 : 0 : if (e->distance == 0 && g->nodes[e->dest->cuid].aux.count == n->aux.count)
1030 : 0 : n->max_dist[e->dest->cuid] = e->latency;
1031 : : }
1032 : :
1033 : : /* Run main Floid-Warshall loop. We use only non-backarc edges
1034 : : inside each scc. */
1035 : 0 : for (k = 0; k < num_nodes; k++)
1036 : : {
1037 : 0 : scc = g->nodes[k].aux.count;
1038 : 0 : if (scc != -1)
1039 : : {
1040 : 0 : for (i = 0; i < num_nodes; i++)
1041 : 0 : if (g->nodes[i].aux.count == scc)
1042 : 0 : for (j = 0; j < num_nodes; j++)
1043 : 0 : if (g->nodes[j].aux.count == scc
1044 : 0 : && g->nodes[i].max_dist[k] >= 0
1045 : 0 : && g->nodes[k].max_dist[j] >= 0)
1046 : : {
1047 : 0 : way = g->nodes[i].max_dist[k] + g->nodes[k].max_dist[j];
1048 : 0 : if (g->nodes[i].max_dist[j] < way)
1049 : 0 : g->nodes[i].max_dist[j] = way;
1050 : : }
1051 : : }
1052 : : }
1053 : :
1054 : : /* Calculate recurrence_length using max_dist info. */
1055 : 0 : for (i = 0; i < sccs->num_sccs; i++)
1056 : 0 : set_recurrence_length (sccs->sccs[i]);
1057 : :
1058 : 0 : order_sccs (sccs);
1059 : :
1060 : 0 : if (flag_checking)
1061 : 0 : check_sccs (sccs, num_nodes);
1062 : :
1063 : 0 : return sccs;
1064 : 0 : }
1065 : :
1066 : : /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1067 : : void
1068 : 0 : free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
1069 : : {
1070 : 0 : int i;
1071 : :
1072 : 0 : if (!all_sccs)
1073 : : return;
1074 : :
1075 : 0 : for (i = 0; i < all_sccs->num_sccs; i++)
1076 : 0 : free_scc (all_sccs->sccs[i]);
1077 : :
1078 : 0 : free (all_sccs->sccs);
1079 : 0 : free (all_sccs);
1080 : : }
1081 : :
1082 : :
1083 : : /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1084 : : nodes - find all nodes that lie on paths from FROM to TO (not excluding
1085 : : nodes from FROM and TO). Return nonzero if nodes exist. */
1086 : : int
1087 : 0 : find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
1088 : : {
1089 : 0 : int change;
1090 : 0 : unsigned int u = 0;
1091 : 0 : int num_nodes = g->num_nodes;
1092 : 0 : sbitmap_iterator sbi;
1093 : :
1094 : 0 : auto_sbitmap workset (num_nodes);
1095 : 0 : auto_sbitmap reachable_from (num_nodes);
1096 : 0 : auto_sbitmap reach_to (num_nodes);
1097 : 0 : auto_sbitmap tmp (num_nodes);
1098 : :
1099 : 0 : bitmap_copy (reachable_from, from);
1100 : 0 : bitmap_copy (tmp, from);
1101 : :
1102 : 0 : change = 1;
1103 : 0 : while (change)
1104 : : {
1105 : 0 : change = 0;
1106 : 0 : bitmap_copy (workset, tmp);
1107 : 0 : bitmap_clear (tmp);
1108 : 0 : EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
1109 : : {
1110 : 0 : ddg_edge_ptr e;
1111 : 0 : ddg_node_ptr u_node = &g->nodes[u];
1112 : :
1113 : 0 : for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
1114 : : {
1115 : 0 : ddg_node_ptr v_node = e->dest;
1116 : 0 : int v = v_node->cuid;
1117 : :
1118 : 0 : if (!bitmap_bit_p (reachable_from, v))
1119 : : {
1120 : 0 : bitmap_set_bit (reachable_from, v);
1121 : 0 : bitmap_set_bit (tmp, v);
1122 : 0 : change = 1;
1123 : : }
1124 : : }
1125 : : }
1126 : : }
1127 : :
1128 : 0 : bitmap_copy (reach_to, to);
1129 : 0 : bitmap_copy (tmp, to);
1130 : :
1131 : 0 : change = 1;
1132 : 0 : while (change)
1133 : : {
1134 : 0 : change = 0;
1135 : 0 : bitmap_copy (workset, tmp);
1136 : 0 : bitmap_clear (tmp);
1137 : 0 : EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
1138 : : {
1139 : 0 : ddg_edge_ptr e;
1140 : 0 : ddg_node_ptr u_node = &g->nodes[u];
1141 : :
1142 : 0 : for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1143 : : {
1144 : 0 : ddg_node_ptr v_node = e->src;
1145 : 0 : int v = v_node->cuid;
1146 : :
1147 : 0 : if (!bitmap_bit_p (reach_to, v))
1148 : : {
1149 : 0 : bitmap_set_bit (reach_to, v);
1150 : 0 : bitmap_set_bit (tmp, v);
1151 : 0 : change = 1;
1152 : : }
1153 : : }
1154 : : }
1155 : : }
1156 : :
1157 : 0 : return bitmap_and (result, reachable_from, reach_to);
1158 : 0 : }
1159 : :
1160 : : #endif /* INSN_SCHEDULING */
|
