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

source code of gcc/ddg.cc