Line data Source code
1 : /* DDG - Data Dependence Graph implementation.
2 : Copyright (C) 2004-2026 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 : : 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 */
|
