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