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 | |
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 | mark_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. */ |
64 | static bool |
65 | mem_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 | |
72 | static void |
73 | mark_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. */ |
80 | static bool |
81 | mem_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. */ |
89 | static bool |
90 | rtx_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. */ |
122 | static bool |
123 | mem_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. */ |
136 | bool |
137 | autoinc_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. */ |
151 | static bool |
152 | def_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. */ |
169 | static void |
170 | 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 | 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. */ |
228 | static void |
229 | 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 | 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. */ |
266 | static void |
267 | add_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. */ |
346 | static void |
347 | build_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. */ |
367 | static bool |
368 | insns_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. */ |
388 | static void |
389 | add_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. */ |
411 | static void |
412 | add_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. */ |
439 | static void |
440 | build_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. */ |
517 | ddg_ptr |
518 | create_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. */ |
610 | void |
611 | free_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 | |
639 | void |
640 | print_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. */ |
661 | void |
662 | print_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. */ |
685 | DEBUG_FUNCTION void |
686 | vcg_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. */ |
719 | void |
720 | print_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. */ |
743 | static ddg_edge_ptr |
744 | 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 | 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. */ |
761 | static void |
762 | add_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. */ |
783 | static void |
784 | set_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. */ |
808 | static ddg_scc_ptr |
809 | create_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. */ |
843 | static void |
844 | free_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. */ |
857 | static void |
858 | add_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. */ |
868 | static void |
869 | add_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. */ |
878 | static void |
879 | add_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. */ |
888 | ddg_node_ptr |
889 | get_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. */ |
902 | void |
903 | find_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. */ |
921 | void |
922 | find_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. */ |
940 | static int |
941 | compare_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. */ |
950 | static void |
951 | order_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. */ |
959 | static void |
960 | check_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. */ |
978 | ddg_all_sccs_ptr |
979 | create_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. */ |
1067 | void |
1068 | free_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. */ |
1086 | int |
1087 | find_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 | |