]>
Commit | Line | Data |
---|---|---|
d397e8c6 | 1 | /* DDG - Data Dependence Graph implementation. |
8d9254fc | 2 | Copyright (C) 2004-2020 Free Software Foundation, Inc. |
d397e8c6 MH |
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 | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
d397e8c6 MH |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
d397e8c6 MH |
20 | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
c7131fb2 | 25 | #include "backend.h" |
d397e8c6 | 26 | #include "rtl.h" |
c7131fb2 | 27 | #include "df.h" |
d397e8c6 | 28 | #include "insn-attr.h" |
d397e8c6 | 29 | #include "sched-int.h" |
d397e8c6 | 30 | #include "ddg.h" |
fbf3fc0f | 31 | #include "rtl-iter.h" |
d397e8c6 | 32 | |
a750daa2 MK |
33 | #ifdef INSN_SCHEDULING |
34 | ||
d397e8c6 MH |
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); | |
517d76fa VY |
39 | static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr, |
40 | ddg_node_ptr, dep_t); | |
d397e8c6 MH |
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 | \f | |
47 | /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */ | |
48 | static bool mem_ref_p; | |
49 | ||
d397e8c6 MH |
50 | /* Auxiliary function for mem_read_insn_p. */ |
51 | static void | |
fbf3fc0f | 52 | mark_mem_use (rtx *x, void *) |
d397e8c6 | 53 | { |
fbf3fc0f RS |
54 | subrtx_iterator::array_type array; |
55 | FOR_EACH_SUBRTX (iter, array, *x, NONCONST) | |
cc75dc89 | 56 | if (MEM_P (*iter)) |
fbf3fc0f RS |
57 | { |
58 | mem_ref_p = true; | |
59 | break; | |
60 | } | |
d397e8c6 MH |
61 | } |
62 | ||
1ea7e6ad | 63 | /* Returns nonzero if INSN reads from memory. */ |
d397e8c6 | 64 | static bool |
9774f20d | 65 | mem_read_insn_p (rtx_insn *insn) |
d397e8c6 MH |
66 | { |
67 | mem_ref_p = false; | |
fbf3fc0f | 68 | note_uses (&PATTERN (insn), mark_mem_use, NULL); |
d397e8c6 MH |
69 | return mem_ref_p; |
70 | } | |
71 | ||
72 | static void | |
7bc980e1 | 73 | mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) |
d397e8c6 | 74 | { |
d9c4ef55 | 75 | if (MEM_P (loc)) |
d397e8c6 MH |
76 | mem_ref_p = true; |
77 | } | |
78 | ||
1ea7e6ad | 79 | /* Returns nonzero if INSN writes to memory. */ |
d397e8c6 | 80 | static bool |
9774f20d | 81 | mem_write_insn_p (rtx_insn *insn) |
d397e8c6 MH |
82 | { |
83 | mem_ref_p = false; | |
e8448ba5 | 84 | note_stores (insn, mark_mem_store, NULL); |
d397e8c6 MH |
85 | return mem_ref_p; |
86 | } | |
87 | ||
1ea7e6ad | 88 | /* Returns nonzero if X has access to memory. */ |
d397e8c6 MH |
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 | ||
d9c4ef55 | 99 | if (MEM_P (x)) |
d397e8c6 MH |
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 | ||
1ea7e6ad | 121 | /* Returns nonzero if INSN reads to or writes from memory. */ |
d397e8c6 | 122 | static bool |
9774f20d | 123 | mem_access_insn_p (rtx_insn *insn) |
d397e8c6 MH |
124 | { |
125 | return rtx_mem_access_p (PATTERN (insn)); | |
126 | } | |
127 | ||
d8edf83d RE |
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 | |
9774f20d | 137 | autoinc_var_is_used_p (rtx_insn *def_insn, rtx_insn *use_insn) |
d8edf83d RE |
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 (use_insn))) | |
144 | return true; | |
145 | ||
146 | return false; | |
147 | } | |
148 | ||
8b61e863 RE |
149 | /* Return true if one of the definitions in INSN has MODE_CC. Otherwise |
150 | return false. */ | |
151 | static bool | |
9774f20d | 152 | def_has_ccmode_p (rtx_insn *insn) |
8b61e863 | 153 | { |
bfac633a | 154 | df_ref def; |
8b61e863 | 155 | |
bfac633a | 156 | FOR_EACH_INSN_DEF (def, insn) |
8b61e863 | 157 | { |
ef4bddc2 | 158 | machine_mode mode = GET_MODE (DF_REF_REG (def)); |
8b61e863 RE |
159 | |
160 | if (GET_MODE_CLASS (mode) == MODE_CC) | |
161 | return true; | |
162 | } | |
163 | ||
164 | return false; | |
165 | } | |
166 | ||
d397e8c6 MH |
167 | /* Computes the dependence parameters (latency, distance etc.), creates |
168 | a ddg_edge and adds it to the given DDG. */ | |
169 | static void | |
517d76fa VY |
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) | |
d397e8c6 MH |
172 | { |
173 | ddg_edge_ptr e; | |
174 | int latency, distance = 0; | |
d397e8c6 MH |
175 | dep_type t = TRUE_DEP; |
176 | dep_data_type dt = (mem_access_insn_p (src_node->insn) | |
177 | && mem_access_insn_p (dest_node->insn) ? MEM_DEP | |
178 | : REG_DEP); | |
517d76fa | 179 | gcc_assert (src_node->cuid < dest_node->cuid); |
ced3f397 | 180 | gcc_assert (link); |
d397e8c6 MH |
181 | |
182 | /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */ | |
e2f6ff94 | 183 | if (DEP_TYPE (link) == REG_DEP_ANTI) |
d397e8c6 | 184 | t = ANTI_DEP; |
e2f6ff94 | 185 | else if (DEP_TYPE (link) == REG_DEP_OUTPUT) |
d397e8c6 | 186 | t = OUTPUT_DEP; |
d397e8c6 | 187 | |
b5b8b0ac | 188 | gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP); |
f49b295a | 189 | gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP); |
b5b8b0ac | 190 | |
517d76fa VY |
191 | /* We currently choose not to create certain anti-deps edges and |
192 | compensate for that by generating reg-moves based on the life-range | |
193 | analysis. The anti-deps that will be deleted are the ones which | |
194 | have true-deps edges in the opposite direction (in other words | |
d8edf83d RE |
195 | the kernel has only one def of the relevant register). |
196 | If the address that is being auto-inc or auto-dec in DEST_NODE | |
197 | is used in SRC_NODE then do not remove the edge to make sure | |
198 | reg-moves will not be created for this address. | |
199 | TODO: support the removal of all anti-deps edges, i.e. including those | |
517d76fa | 200 | whose register has multiple defs in the loop. */ |
d8edf83d RE |
201 | if (flag_modulo_sched_allow_regmoves |
202 | && (t == ANTI_DEP && dt == REG_DEP) | |
8b61e863 | 203 | && !def_has_ccmode_p (dest_node->insn) |
d8edf83d | 204 | && !autoinc_var_is_used_p (dest_node->insn, src_node->insn)) |
d397e8c6 | 205 | { |
517d76fa VY |
206 | rtx set; |
207 | ||
208 | set = single_set (dest_node->insn); | |
46dc0789 MN |
209 | /* TODO: Handle registers that REG_P is not true for them, i.e. |
210 | subregs and special registers. */ | |
211 | if (set && REG_P (SET_DEST (set))) | |
517d76fa VY |
212 | { |
213 | int regno = REGNO (SET_DEST (set)); | |
57512f53 | 214 | df_ref first_def; |
99b1c316 | 215 | class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); |
517d76fa | 216 | |
46dc0789 MN |
217 | first_def = df_bb_regno_first_def_find (g->bb, regno); |
218 | gcc_assert (first_def); | |
219 | ||
b33a91c9 | 220 | if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def))) |
517d76fa VY |
221 | return; |
222 | } | |
d397e8c6 | 223 | } |
517d76fa VY |
224 | |
225 | latency = dep_cost (link); | |
226 | e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance); | |
227 | add_edge_to_ddg (g, e); | |
d397e8c6 MH |
228 | } |
229 | ||
230 | /* The same as the above function, but it doesn't require a link parameter. */ | |
231 | static void | |
232 | create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, | |
233 | dep_type d_t, dep_data_type d_dt, int distance) | |
234 | { | |
235 | ddg_edge_ptr e; | |
236 | int l; | |
b198261f MK |
237 | enum reg_note dep_kind; |
238 | struct _dep _dep, *dep = &_dep; | |
d397e8c6 | 239 | |
b5b8b0ac | 240 | gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP); |
f49b295a | 241 | gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP); |
b5b8b0ac | 242 | |
d397e8c6 | 243 | if (d_t == ANTI_DEP) |
b198261f | 244 | dep_kind = REG_DEP_ANTI; |
d397e8c6 | 245 | else if (d_t == OUTPUT_DEP) |
b198261f MK |
246 | dep_kind = REG_DEP_OUTPUT; |
247 | else | |
248 | { | |
249 | gcc_assert (d_t == TRUE_DEP); | |
250 | ||
251 | dep_kind = REG_DEP_TRUE; | |
252 | } | |
253 | ||
254 | init_dep (dep, from->insn, to->insn, dep_kind); | |
d397e8c6 | 255 | |
b198261f | 256 | l = dep_cost (dep); |
d397e8c6 MH |
257 | |
258 | e = create_ddg_edge (from, to, d_t, d_dt, l, distance); | |
259 | if (distance > 0) | |
260 | add_backarc_to_ddg (g, e); | |
261 | else | |
262 | add_edge_to_ddg (g, e); | |
263 | } | |
264 | ||
e0ab232e RE |
265 | |
266 | /* Given a downwards exposed register def LAST_DEF (which is the last | |
267 | definition of that register in the bb), add inter-loop true dependences | |
268 | to all its uses in the next iteration, an output dependence to the | |
269 | first def of the same register (possibly itself) in the next iteration | |
270 | and anti-dependences from its uses in the current iteration to the | |
271 | first definition in the next iteration. */ | |
d397e8c6 | 272 | static void |
57512f53 | 273 | add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def) |
d397e8c6 | 274 | { |
e0ab232e | 275 | int regno = DF_REF_REGNO (last_def); |
d397e8c6 | 276 | struct df_link *r_use; |
e0ab232e | 277 | int has_use_in_bb_p = false; |
9774f20d | 278 | rtx_insn *def_insn = DF_REF_INSN (last_def); |
e0ab232e RE |
279 | ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn); |
280 | ddg_node_ptr use_node; | |
57512f53 | 281 | df_ref first_def = df_bb_regno_first_def_find (g->bb, regno); |
d397e8c6 | 282 | |
e0ab232e RE |
283 | gcc_assert (last_def_node); |
284 | gcc_assert (first_def); | |
285 | ||
b2b29377 MM |
286 | if (flag_checking && DF_REF_ID (last_def) != DF_REF_ID (first_def)) |
287 | { | |
99b1c316 | 288 | class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); |
b2b29377 MM |
289 | gcc_assert (!bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def))); |
290 | } | |
517d76fa | 291 | |
e0ab232e RE |
292 | /* Create inter-loop true dependences and anti dependences. */ |
293 | for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next) | |
d397e8c6 | 294 | { |
8c760464 | 295 | if (DF_REF_BB (r_use->ref) != g->bb) |
e0ab232e | 296 | continue; |
d397e8c6 | 297 | |
8c760464 PB |
298 | gcc_assert (!DF_REF_IS_ARTIFICIAL (r_use->ref) |
299 | && DF_REF_INSN_INFO (r_use->ref) != NULL); | |
300 | ||
301 | rtx_insn *use_insn = DF_REF_INSN (r_use->ref); | |
302 | ||
e0ab232e RE |
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. */ | |
b5b8b0ac AO |
312 | create_ddg_dep_no_link (g, last_def_node, use_node, |
313 | DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP, | |
d397e8c6 MH |
314 | REG_DEP, 1); |
315 | } | |
b5b8b0ac | 316 | else if (!DEBUG_INSN_P (use_insn)) |
e0ab232e RE |
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, | |
50e94c7e | 325 | DF_REF_INSN (first_def)); |
e0ab232e RE |
326 | |
327 | gcc_assert (first_def_node); | |
328 | ||
dcaac07d | 329 | /* Always create the edge if the use node is a branch in |
d8edf83d RE |
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. */ | |
57512f53 | 334 | if (DF_REF_ID (last_def) != DF_REF_ID (first_def) |
dcaac07d | 335 | || !flag_modulo_sched_allow_regmoves |
d8edf83d | 336 | || JUMP_P (use_node->insn) |
8b61e863 RE |
337 | || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn) |
338 | || def_has_ccmode_p (DF_REF_INSN (last_def))) | |
517d76fa VY |
339 | create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP, |
340 | REG_DEP, 1); | |
341 | ||
e0ab232e | 342 | } |
d397e8c6 | 343 | } |
e0ab232e RE |
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) | |
d397e8c6 | 352 | { |
d397e8c6 MH |
353 | ddg_node_ptr dest_node; |
354 | ||
57512f53 | 355 | if (DF_REF_ID (last_def) == DF_REF_ID (first_def)) |
d397e8c6 MH |
356 | return; |
357 | ||
50e94c7e | 358 | dest_node = get_node_of_insn (g, DF_REF_INSN (first_def)); |
e0ab232e RE |
359 | gcc_assert (dest_node); |
360 | create_ddg_dep_no_link (g, last_def_node, dest_node, | |
361 | OUTPUT_DEP, REG_DEP, 1); | |
d397e8c6 MH |
362 | } |
363 | } | |
d397e8c6 MH |
364 | /* Build inter-loop dependencies, by looking at DF analysis backwards. */ |
365 | static void | |
6fb5fa3c | 366 | build_inter_loop_deps (ddg_ptr g) |
d397e8c6 | 367 | { |
e0ab232e | 368 | unsigned rd_num; |
99b1c316 | 369 | class df_rd_bb_info *rd_bb_info; |
87c476a2 | 370 | bitmap_iterator bi; |
d397e8c6 | 371 | |
6fb5fa3c | 372 | rd_bb_info = DF_RD_BB_INFO (g->bb); |
d397e8c6 | 373 | |
e0ab232e | 374 | /* Find inter-loop register output, true and anti deps. */ |
b33a91c9 | 375 | EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi) |
e0ab232e | 376 | { |
57512f53 | 377 | df_ref rd = DF_DEFS_GET (rd_num); |
4d779342 | 378 | |
e0ab232e RE |
379 | add_cross_iteration_register_deps (g, rd); |
380 | } | |
d397e8c6 MH |
381 | } |
382 | ||
e0ab232e | 383 | |
a3aa0813 RS |
384 | /* Return true if two specified instructions have mem expr with conflict |
385 | alias sets. */ | |
386 | static bool | |
387 | insns_may_alias_p (rtx_insn *insn1, rtx_insn *insn2) | |
c6ea834c | 388 | { |
a3aa0813 RS |
389 | subrtx_iterator::array_type array1; |
390 | subrtx_iterator::array_type array2; | |
391 | FOR_EACH_SUBRTX (iter1, array1, PATTERN (insn1), NONCONST) | |
c6ea834c | 392 | { |
a3aa0813 RS |
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 | } | |
c6ea834c | 401 | } |
a3aa0813 | 402 | return false; |
c6ea834c BM |
403 | } |
404 | ||
d24dc7b3 RE |
405 | /* Given two nodes, analyze their RTL insns and add intra-loop mem deps |
406 | to ddg G. */ | |
407 | static void | |
408 | add_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 | ||
d397e8c6 MH |
432 | /* Given two nodes, analyze their RTL insns and add inter-loop mem deps |
433 | to ddg G. */ | |
434 | static void | |
435 | add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) | |
436 | { | |
c6ea834c | 437 | if (!insns_may_alias_p (from->insn, to->insn)) |
71a6fe66 BM |
438 | /* Do not create edge if memory references have disjoint alias sets. */ |
439 | return; | |
b8698a0f | 440 | |
d397e8c6 MH |
441 | if (mem_write_insn_p (from->insn)) |
442 | { | |
443 | if (mem_read_insn_p (to->insn)) | |
aec4e50c JJ |
444 | create_ddg_dep_no_link (g, from, to, |
445 | DEBUG_INSN_P (to->insn) | |
446 | ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1); | |
d397e8c6 | 447 | else if (from->cuid != to->cuid) |
aec4e50c JJ |
448 | create_ddg_dep_no_link (g, from, to, |
449 | DEBUG_INSN_P (to->insn) | |
450 | ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1); | |
d397e8c6 MH |
451 | } |
452 | else | |
453 | { | |
454 | if (mem_read_insn_p (to->insn)) | |
455 | return; | |
456 | else if (from->cuid != to->cuid) | |
457 | { | |
aec4e50c JJ |
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); | |
d397e8c6 MH |
463 | } |
464 | } | |
465 | ||
466 | } | |
467 | ||
468 | /* Perform intra-block Data Dependency analysis and connect the nodes in | |
9cf737f8 | 469 | the DDG. We assume the loop has a single basic block. */ |
d397e8c6 MH |
470 | static void |
471 | build_intra_loop_deps (ddg_ptr g) | |
472 | { | |
473 | int i; | |
474 | /* Hold the dependency analysis state during dependency calculations. */ | |
99b1c316 | 475 | class deps_desc tmp_deps; |
52d251b5 | 476 | rtx_insn *head, *tail; |
d397e8c6 MH |
477 | |
478 | /* Build the dependence information, using the sched_analyze function. */ | |
479 | init_deps_global (); | |
bcf33775 | 480 | init_deps (&tmp_deps, false); |
d397e8c6 MH |
481 | |
482 | /* Do the intra-block data dependence analysis for the given block. */ | |
496d7bb0 | 483 | get_ebb_head_tail (g->bb, g->bb, &head, &tail); |
d397e8c6 MH |
484 | sched_analyze (&tmp_deps, head, tail); |
485 | ||
61ada8ae | 486 | /* Build intra-loop data dependencies using the scheduler dependency |
d397e8c6 MH |
487 | analysis. */ |
488 | for (i = 0; i < g->num_nodes; i++) | |
489 | { | |
490 | ddg_node_ptr dest_node = &g->nodes[i]; | |
e2f6ff94 MK |
491 | sd_iterator_def sd_it; |
492 | dep_t dep; | |
d397e8c6 MH |
493 | |
494 | if (! INSN_P (dest_node->insn)) | |
495 | continue; | |
496 | ||
e2f6ff94 | 497 | FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep) |
d397e8c6 | 498 | { |
9774f20d | 499 | rtx_insn *src_insn = DEP_PRO (dep); |
1ca63357 AO |
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); | |
d397e8c6 MH |
508 | |
509 | if (!src_node) | |
510 | continue; | |
511 | ||
517d76fa | 512 | create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep); |
d397e8c6 MH |
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]; | |
b5b8b0ac AO |
524 | if (DEBUG_INSN_P (j_node->insn)) |
525 | continue; | |
d397e8c6 | 526 | if (mem_access_insn_p (j_node->insn)) |
d24dc7b3 RE |
527 | { |
528 | /* Don't bother calculating inter-loop dep if an intra-loop dep | |
529 | already exists. */ | |
d7c028c0 | 530 | if (! bitmap_bit_p (dest_node->successors, j)) |
d397e8c6 | 531 | add_inter_loop_mem_dep (g, dest_node, j_node); |
d24dc7b3 RE |
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 | |
d7c028c0 | 540 | && !bitmap_bit_p (dest_node->predecessors, j)) |
d24dc7b3 RE |
541 | add_intra_loop_mem_dep (g, j_node, dest_node); |
542 | } | |
d397e8c6 MH |
543 | } |
544 | } | |
545 | } | |
546 | ||
547 | /* Free the INSN_LISTs. */ | |
548 | finish_deps_global (); | |
549 | free_deps (&tmp_deps); | |
e2f6ff94 MK |
550 | |
551 | /* Free dependencies. */ | |
552 | sched_free_deps (head, tail, false); | |
d397e8c6 MH |
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. */ | |
559 | ddg_ptr | |
6fb5fa3c | 560 | create_ddg (basic_block bb, int closing_branch_deps) |
d397e8c6 MH |
561 | { |
562 | ddg_ptr g; | |
9774f20d | 563 | rtx_insn *insn, *first_note; |
728c2e5e | 564 | int i, j; |
d397e8c6 MH |
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 | ||
b5b8b0ac AO |
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 | } | |
d397e8c6 MH |
588 | num_nodes++; |
589 | } | |
590 | ||
591 | /* There is nothing to do for this BB. */ | |
0be955e7 | 592 | if ((num_nodes - g->num_debug) <= 1) |
d397e8c6 MH |
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; | |
9774f20d | 603 | first_note = NULL; |
d397e8c6 MH |
604 | for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); |
605 | insn = NEXT_INSN (insn)) | |
606 | { | |
607 | if (! INSN_P (insn)) | |
608 | { | |
4b4bf941 | 609 | if (! first_note && NOTE_P (insn) |
a38e7aa5 | 610 | && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK) |
d397e8c6 MH |
611 | first_note = insn; |
612 | continue; | |
613 | } | |
4b4bf941 | 614 | if (JUMP_P (insn)) |
d397e8c6 | 615 | { |
ced3f397 NS |
616 | gcc_assert (!g->closing_branch); |
617 | g->closing_branch = &g->nodes[i]; | |
d397e8c6 MH |
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); | |
f61e445a | 628 | bitmap_clear (g->nodes[i].successors); |
d397e8c6 | 629 | g->nodes[i].predecessors = sbitmap_alloc (num_nodes); |
f61e445a | 630 | bitmap_clear (g->nodes[i].predecessors); |
d397e8c6 | 631 | g->nodes[i].first_note = (first_note ? first_note : insn); |
728c2e5e RZ |
632 | |
633 | g->nodes[i].aux.count = -1; | |
634 | g->nodes[i].max_dist = XCNEWVEC (int, num_nodes); | |
635 | for (j = 0; j < num_nodes; j++) | |
90b5ebd7 | 636 | g->nodes[i].max_dist[j] = -1; |
728c2e5e | 637 | |
d397e8c6 | 638 | g->nodes[i++].insn = insn; |
9774f20d | 639 | first_note = NULL; |
d397e8c6 | 640 | } |
b8698a0f | 641 | |
ced3f397 NS |
642 | /* We must have found a branch in DDG. */ |
643 | gcc_assert (g->closing_branch); | |
b8698a0f | 644 | |
d397e8c6 | 645 | |
61ada8ae | 646 | /* Build the data dependency graph. */ |
d397e8c6 | 647 | build_intra_loop_deps (g); |
6fb5fa3c | 648 | build_inter_loop_deps (g); |
d397e8c6 MH |
649 | return g; |
650 | } | |
651 | ||
652 | /* Free all the memory allocated for the DDG. */ | |
653 | void | |
654 | free_ddg (ddg_ptr g) | |
655 | { | |
656 | int i; | |
657 | ||
658 | if (!g) | |
659 | return; | |
660 | ||
661 | for (i = 0; i < g->num_nodes; i++) | |
662 | { | |
663 | ddg_edge_ptr e = g->nodes[i].out; | |
664 | ||
665 | while (e) | |
666 | { | |
667 | ddg_edge_ptr next = e->next_out; | |
668 | ||
669 | free (e); | |
670 | e = next; | |
671 | } | |
672 | sbitmap_free (g->nodes[i].successors); | |
673 | sbitmap_free (g->nodes[i].predecessors); | |
728c2e5e | 674 | free (g->nodes[i].max_dist); |
d397e8c6 MH |
675 | } |
676 | if (g->num_backarcs > 0) | |
677 | free (g->backarcs); | |
678 | free (g->nodes); | |
679 | free (g); | |
680 | } | |
681 | ||
682 | void | |
10d22567 | 683 | print_ddg_edge (FILE *file, ddg_edge_ptr e) |
d397e8c6 MH |
684 | { |
685 | char dep_c; | |
686 | ||
428aba16 RS |
687 | switch (e->type) |
688 | { | |
d397e8c6 MH |
689 | case OUTPUT_DEP : |
690 | dep_c = 'O'; | |
691 | break; | |
692 | case ANTI_DEP : | |
693 | dep_c = 'A'; | |
694 | break; | |
695 | default: | |
696 | dep_c = 'T'; | |
428aba16 | 697 | } |
d397e8c6 | 698 | |
10d22567 | 699 | fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn), |
d397e8c6 MH |
700 | dep_c, e->latency, e->distance, INSN_UID (e->dest->insn)); |
701 | } | |
702 | ||
703 | /* Print the DDG nodes with there in/out edges to the dump file. */ | |
704 | void | |
10d22567 | 705 | print_ddg (FILE *file, ddg_ptr g) |
d397e8c6 MH |
706 | { |
707 | int i; | |
708 | ||
709 | for (i = 0; i < g->num_nodes; i++) | |
710 | { | |
711 | ddg_edge_ptr e; | |
712 | ||
76b4f0f7 | 713 | fprintf (file, "Node num: %d\n", g->nodes[i].cuid); |
10d22567 ZD |
714 | print_rtl_single (file, g->nodes[i].insn); |
715 | fprintf (file, "OUT ARCS: "); | |
d397e8c6 | 716 | for (e = g->nodes[i].out; e; e = e->next_out) |
10d22567 | 717 | print_ddg_edge (file, e); |
d397e8c6 | 718 | |
10d22567 | 719 | fprintf (file, "\nIN ARCS: "); |
d397e8c6 | 720 | for (e = g->nodes[i].in; e; e = e->next_in) |
10d22567 | 721 | print_ddg_edge (file, e); |
d397e8c6 | 722 | |
10d22567 | 723 | fprintf (file, "\n"); |
d397e8c6 MH |
724 | } |
725 | } | |
726 | ||
727 | /* Print the given DDG in VCG format. */ | |
a27a5de9 | 728 | DEBUG_FUNCTION void |
10d22567 | 729 | vcg_print_ddg (FILE *file, ddg_ptr g) |
d397e8c6 MH |
730 | { |
731 | int src_cuid; | |
732 | ||
10d22567 | 733 | fprintf (file, "graph: {\n"); |
d397e8c6 MH |
734 | for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++) |
735 | { | |
736 | ddg_edge_ptr e; | |
737 | int src_uid = INSN_UID (g->nodes[src_cuid].insn); | |
738 | ||
10d22567 ZD |
739 | fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid); |
740 | print_rtl_single (file, g->nodes[src_cuid].insn); | |
741 | fprintf (file, "\"}\n"); | |
d397e8c6 MH |
742 | for (e = g->nodes[src_cuid].out; e; e = e->next_out) |
743 | { | |
744 | int dst_uid = INSN_UID (e->dest->insn); | |
745 | int dst_cuid = e->dest->cuid; | |
746 | ||
747 | /* Give the backarcs a different color. */ | |
748 | if (e->distance > 0) | |
10d22567 | 749 | fprintf (file, "backedge: {color: red "); |
d397e8c6 | 750 | else |
10d22567 | 751 | fprintf (file, "edge: { "); |
d397e8c6 | 752 | |
10d22567 ZD |
753 | fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid); |
754 | fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid); | |
755 | fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance); | |
d397e8c6 MH |
756 | } |
757 | } | |
10d22567 | 758 | fprintf (file, "}\n"); |
d397e8c6 MH |
759 | } |
760 | ||
8cec1624 RE |
761 | /* Dump the sccs in SCCS. */ |
762 | void | |
763 | print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g) | |
764 | { | |
765 | unsigned int u = 0; | |
766 | sbitmap_iterator sbi; | |
767 | int i; | |
768 | ||
769 | if (!file) | |
770 | return; | |
771 | ||
772 | fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs); | |
773 | for (i = 0; i < sccs->num_sccs; i++) | |
774 | { | |
775 | fprintf (file, "SCC number: %d\n", i); | |
d4ac4ce2 | 776 | EXECUTE_IF_SET_IN_BITMAP (sccs->sccs[i]->nodes, 0, u, sbi) |
8cec1624 RE |
777 | { |
778 | fprintf (file, "insn num %d\n", u); | |
779 | print_rtl_single (file, g->nodes[u].insn); | |
780 | } | |
781 | } | |
782 | fprintf (file, "\n"); | |
783 | } | |
784 | ||
d397e8c6 MH |
785 | /* Create an edge and initialize it with given values. */ |
786 | static ddg_edge_ptr | |
787 | create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, | |
788 | dep_type t, dep_data_type dt, int l, int d) | |
789 | { | |
790 | ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge)); | |
791 | ||
792 | e->src = src; | |
793 | e->dest = dest; | |
794 | e->type = t; | |
795 | e->data_type = dt; | |
796 | e->latency = l; | |
797 | e->distance = d; | |
798 | e->next_in = e->next_out = NULL; | |
728c2e5e | 799 | e->in_scc = false; |
d397e8c6 MH |
800 | return e; |
801 | } | |
802 | ||
803 | /* Add the given edge to the in/out linked lists of the DDG nodes. */ | |
804 | static void | |
805 | add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e) | |
806 | { | |
807 | ddg_node_ptr src = e->src; | |
808 | ddg_node_ptr dest = e->dest; | |
809 | ||
ced3f397 NS |
810 | /* Should have allocated the sbitmaps. */ |
811 | gcc_assert (src->successors && dest->predecessors); | |
d397e8c6 | 812 | |
d7c028c0 LC |
813 | bitmap_set_bit (src->successors, dest->cuid); |
814 | bitmap_set_bit (dest->predecessors, src->cuid); | |
d397e8c6 MH |
815 | e->next_in = dest->in; |
816 | dest->in = e; | |
817 | e->next_out = src->out; | |
818 | src->out = e; | |
819 | } | |
820 | ||
821 | ||
822 | \f | |
823 | /* Algorithm for computing the recurrence_length of an scc. We assume at | |
824 | for now that cycles in the data dependence graph contain a single backarc. | |
825 | This simplifies the algorithm, and can be generalized later. */ | |
826 | static void | |
728c2e5e | 827 | set_recurrence_length (ddg_scc_ptr scc) |
d397e8c6 MH |
828 | { |
829 | int j; | |
830 | int result = -1; | |
831 | ||
832 | for (j = 0; j < scc->num_backarcs; j++) | |
833 | { | |
834 | ddg_edge_ptr backarc = scc->backarcs[j]; | |
d397e8c6 MH |
835 | int distance = backarc->distance; |
836 | ddg_node_ptr src = backarc->dest; | |
837 | ddg_node_ptr dest = backarc->src; | |
728c2e5e RZ |
838 | int length = src->max_dist[dest->cuid]; |
839 | ||
840 | if (length < 0) | |
90b5ebd7 | 841 | continue; |
d397e8c6 | 842 | |
d397e8c6 MH |
843 | length += backarc->latency; |
844 | result = MAX (result, (length / distance)); | |
845 | } | |
846 | scc->recurrence_length = result; | |
847 | } | |
848 | ||
849 | /* Create a new SCC given the set of its nodes. Compute its recurrence_length | |
728c2e5e | 850 | and mark edges that belong to this scc. */ |
d397e8c6 | 851 | static ddg_scc_ptr |
728c2e5e | 852 | create_scc (ddg_ptr g, sbitmap nodes, int id) |
d397e8c6 MH |
853 | { |
854 | ddg_scc_ptr scc; | |
dfea6c85 | 855 | unsigned int u = 0; |
b6e7e9af | 856 | sbitmap_iterator sbi; |
d397e8c6 MH |
857 | |
858 | scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc)); | |
859 | scc->backarcs = NULL; | |
860 | scc->num_backarcs = 0; | |
861 | scc->nodes = sbitmap_alloc (g->num_nodes); | |
f61e445a | 862 | bitmap_copy (scc->nodes, nodes); |
d397e8c6 MH |
863 | |
864 | /* Mark the backarcs that belong to this SCC. */ | |
d4ac4ce2 | 865 | EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi) |
d397e8c6 MH |
866 | { |
867 | ddg_edge_ptr e; | |
868 | ddg_node_ptr n = &g->nodes[u]; | |
869 | ||
728c2e5e RZ |
870 | gcc_assert (n->aux.count == -1); |
871 | n->aux.count = id; | |
872 | ||
d397e8c6 | 873 | for (e = n->out; e; e = e->next_out) |
d7c028c0 | 874 | if (bitmap_bit_p (nodes, e->dest->cuid)) |
d397e8c6 | 875 | { |
728c2e5e | 876 | e->in_scc = true; |
d397e8c6 MH |
877 | if (e->distance > 0) |
878 | add_backarc_to_scc (scc, e); | |
879 | } | |
b6e7e9af | 880 | } |
d397e8c6 | 881 | |
d397e8c6 MH |
882 | return scc; |
883 | } | |
884 | ||
885 | /* Cleans the memory allocation of a given SCC. */ | |
886 | static void | |
887 | free_scc (ddg_scc_ptr scc) | |
888 | { | |
889 | if (!scc) | |
890 | return; | |
891 | ||
892 | sbitmap_free (scc->nodes); | |
893 | if (scc->num_backarcs > 0) | |
894 | free (scc->backarcs); | |
895 | free (scc); | |
896 | } | |
897 | ||
898 | ||
899 | /* Add a given edge known to be a backarc to the given DDG. */ | |
900 | static void | |
901 | add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e) | |
902 | { | |
903 | int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr); | |
904 | ||
905 | add_edge_to_ddg (g, e); | |
906 | g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size); | |
907 | g->backarcs[g->num_backarcs++] = e; | |
908 | } | |
909 | ||
910 | /* Add backarc to an SCC. */ | |
911 | static void | |
912 | add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e) | |
913 | { | |
914 | int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr); | |
915 | ||
916 | scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size); | |
917 | scc->backarcs[scc->num_backarcs++] = e; | |
918 | } | |
919 | ||
920 | /* Add the given SCC to the DDG. */ | |
921 | static void | |
922 | add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc) | |
923 | { | |
924 | int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr); | |
925 | ||
926 | g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size); | |
927 | g->sccs[g->num_sccs++] = scc; | |
928 | } | |
929 | ||
930 | /* Given the instruction INSN return the node that represents it. */ | |
931 | ddg_node_ptr | |
9774f20d | 932 | get_node_of_insn (ddg_ptr g, rtx_insn *insn) |
d397e8c6 MH |
933 | { |
934 | int i; | |
935 | ||
936 | for (i = 0; i < g->num_nodes; i++) | |
937 | if (insn == g->nodes[i].insn) | |
938 | return &g->nodes[i]; | |
939 | return NULL; | |
940 | } | |
941 | ||
942 | /* Given a set OPS of nodes in the DDG, find the set of their successors | |
943 | which are not in OPS, and set their bits in SUCC. Bits corresponding to | |
944 | OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */ | |
945 | void | |
946 | find_successors (sbitmap succ, ddg_ptr g, sbitmap ops) | |
947 | { | |
dfea6c85 | 948 | unsigned int i = 0; |
b6e7e9af | 949 | sbitmap_iterator sbi; |
d397e8c6 | 950 | |
d4ac4ce2 | 951 | EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi) |
d397e8c6 MH |
952 | { |
953 | const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]); | |
f61e445a | 954 | bitmap_ior (succ, succ, node_succ); |
b6e7e9af | 955 | }; |
d397e8c6 MH |
956 | |
957 | /* We want those that are not in ops. */ | |
f61e445a | 958 | bitmap_and_compl (succ, succ, ops); |
d397e8c6 MH |
959 | } |
960 | ||
961 | /* Given a set OPS of nodes in the DDG, find the set of their predecessors | |
962 | which are not in OPS, and set their bits in PREDS. Bits corresponding to | |
963 | OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */ | |
964 | void | |
965 | find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops) | |
966 | { | |
dfea6c85 | 967 | unsigned int i = 0; |
b6e7e9af | 968 | sbitmap_iterator sbi; |
d397e8c6 | 969 | |
d4ac4ce2 | 970 | EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi) |
d397e8c6 MH |
971 | { |
972 | const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]); | |
f61e445a | 973 | bitmap_ior (preds, preds, node_preds); |
b6e7e9af | 974 | }; |
d397e8c6 MH |
975 | |
976 | /* We want those that are not in ops. */ | |
f61e445a | 977 | bitmap_and_compl (preds, preds, ops); |
d397e8c6 MH |
978 | } |
979 | ||
980 | ||
981 | /* Compare function to be passed to qsort to order the backarcs in descending | |
982 | recMII order. */ | |
983 | static int | |
984 | compare_sccs (const void *s1, const void *s2) | |
985 | { | |
5f754896 | 986 | const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length; |
b8698a0f | 987 | const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length; |
d397e8c6 | 988 | return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1)); |
b8698a0f | 989 | |
d397e8c6 MH |
990 | } |
991 | ||
992 | /* Order the backarcs in descending recMII order using compare_sccs. */ | |
993 | static void | |
994 | order_sccs (ddg_all_sccs_ptr g) | |
995 | { | |
996 | qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr), | |
997 | (int (*) (const void *, const void *)) compare_sccs); | |
998 | } | |
999 | ||
8cec1624 RE |
1000 | /* Check that every node in SCCS belongs to exactly one strongly connected |
1001 | component and that no element of SCCS is empty. */ | |
1002 | static void | |
1003 | check_sccs (ddg_all_sccs_ptr sccs, int num_nodes) | |
1004 | { | |
1005 | int i = 0; | |
7ba9e72d | 1006 | auto_sbitmap tmp (num_nodes); |
8cec1624 | 1007 | |
f61e445a | 1008 | bitmap_clear (tmp); |
8cec1624 RE |
1009 | for (i = 0; i < sccs->num_sccs; i++) |
1010 | { | |
f61e445a | 1011 | gcc_assert (!bitmap_empty_p (sccs->sccs[i]->nodes)); |
8cec1624 RE |
1012 | /* Verify that every node in sccs is in exactly one strongly |
1013 | connected component. */ | |
f61e445a LC |
1014 | gcc_assert (!bitmap_intersect_p (tmp, sccs->sccs[i]->nodes)); |
1015 | bitmap_ior (tmp, tmp, sccs->sccs[i]->nodes); | |
8cec1624 | 1016 | } |
8cec1624 | 1017 | } |
8cec1624 | 1018 | |
d397e8c6 MH |
1019 | /* Perform the Strongly Connected Components decomposing algorithm on the |
1020 | DDG and return DDG_ALL_SCCS structure that contains them. */ | |
1021 | ddg_all_sccs_ptr | |
1022 | create_ddg_all_sccs (ddg_ptr g) | |
1023 | { | |
728c2e5e | 1024 | int i, j, k, scc, way; |
d397e8c6 | 1025 | int num_nodes = g->num_nodes; |
7ba9e72d TS |
1026 | auto_sbitmap from (num_nodes); |
1027 | auto_sbitmap to (num_nodes); | |
1028 | auto_sbitmap scc_nodes (num_nodes); | |
d397e8c6 MH |
1029 | ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr) |
1030 | xmalloc (sizeof (struct ddg_all_sccs)); | |
1031 | ||
1032 | sccs->ddg = g; | |
1033 | sccs->sccs = NULL; | |
1034 | sccs->num_sccs = 0; | |
1035 | ||
1036 | for (i = 0; i < g->num_backarcs; i++) | |
1037 | { | |
1038 | ddg_scc_ptr scc; | |
1039 | ddg_edge_ptr backarc = g->backarcs[i]; | |
1040 | ddg_node_ptr src = backarc->src; | |
1041 | ddg_node_ptr dest = backarc->dest; | |
1042 | ||
1043 | /* If the backarc already belongs to an SCC, continue. */ | |
728c2e5e | 1044 | if (backarc->in_scc) |
d397e8c6 MH |
1045 | continue; |
1046 | ||
f61e445a LC |
1047 | bitmap_clear (scc_nodes); |
1048 | bitmap_clear (from); | |
1049 | bitmap_clear (to); | |
d7c028c0 LC |
1050 | bitmap_set_bit (from, dest->cuid); |
1051 | bitmap_set_bit (to, src->cuid); | |
d397e8c6 MH |
1052 | |
1053 | if (find_nodes_on_paths (scc_nodes, g, from, to)) | |
1054 | { | |
728c2e5e | 1055 | scc = create_scc (g, scc_nodes, sccs->num_sccs); |
d397e8c6 MH |
1056 | add_scc_to_ddg (sccs, scc); |
1057 | } | |
1058 | } | |
728c2e5e RZ |
1059 | |
1060 | /* Init max_dist arrays for Floyd–Warshall-like | |
1061 | longest patch calculation algorithm. */ | |
1062 | for (k = 0; k < num_nodes; k++) | |
1063 | { | |
1064 | ddg_edge_ptr e; | |
1065 | ddg_node_ptr n = &g->nodes[k]; | |
1066 | ||
1067 | if (n->aux.count == -1) | |
1068 | continue; | |
1069 | ||
1070 | n->max_dist[k] = 0; | |
1071 | for (e = n->out; e; e = e->next_out) | |
90b5ebd7 RZ |
1072 | if (e->distance == 0 && g->nodes[e->dest->cuid].aux.count == n->aux.count) |
1073 | n->max_dist[e->dest->cuid] = e->latency; | |
728c2e5e RZ |
1074 | } |
1075 | ||
1076 | /* Run main Floid-Warshall loop. We use only non-backarc edges | |
1077 | inside each scc. */ | |
1078 | for (k = 0; k < num_nodes; k++) | |
1079 | { | |
1080 | scc = g->nodes[k].aux.count; | |
1081 | if (scc != -1) | |
90b5ebd7 RZ |
1082 | { |
1083 | for (i = 0; i < num_nodes; i++) | |
1084 | if (g->nodes[i].aux.count == scc) | |
1085 | for (j = 0; j < num_nodes; j++) | |
1086 | if (g->nodes[j].aux.count == scc | |
1087 | && g->nodes[i].max_dist[k] >= 0 | |
1088 | && g->nodes[k].max_dist[j] >= 0) | |
1089 | { | |
1090 | way = g->nodes[i].max_dist[k] + g->nodes[k].max_dist[j]; | |
1091 | if (g->nodes[i].max_dist[j] < way) | |
1092 | g->nodes[i].max_dist[j] = way; | |
1093 | } | |
1094 | } | |
728c2e5e RZ |
1095 | } |
1096 | ||
1097 | /* Calculate recurrence_length using max_dist info. */ | |
1098 | for (i = 0; i < sccs->num_sccs; i++) | |
1099 | set_recurrence_length (sccs->sccs[i]); | |
1100 | ||
d397e8c6 | 1101 | order_sccs (sccs); |
b2b29377 MM |
1102 | |
1103 | if (flag_checking) | |
1104 | check_sccs (sccs, num_nodes); | |
1105 | ||
d397e8c6 MH |
1106 | return sccs; |
1107 | } | |
1108 | ||
1109 | /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */ | |
1110 | void | |
1111 | free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) | |
1112 | { | |
1113 | int i; | |
1114 | ||
1115 | if (!all_sccs) | |
1116 | return; | |
1117 | ||
1118 | for (i = 0; i < all_sccs->num_sccs; i++) | |
1119 | free_scc (all_sccs->sccs[i]); | |
1120 | ||
54333b7c | 1121 | free (all_sccs->sccs); |
d397e8c6 MH |
1122 | free (all_sccs); |
1123 | } | |
1124 | ||
1125 | \f | |
1126 | /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination | |
1127 | nodes - find all nodes that lie on paths from FROM to TO (not excluding | |
b01d837f | 1128 | nodes from FROM and TO). Return nonzero if nodes exist. */ |
d397e8c6 MH |
1129 | int |
1130 | find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) | |
1131 | { | |
b6e7e9af | 1132 | int change; |
dfea6c85 | 1133 | unsigned int u = 0; |
d397e8c6 | 1134 | int num_nodes = g->num_nodes; |
b6e7e9af KH |
1135 | sbitmap_iterator sbi; |
1136 | ||
8f48c622 TS |
1137 | auto_sbitmap workset (num_nodes); |
1138 | auto_sbitmap reachable_from (num_nodes); | |
1139 | auto_sbitmap reach_to (num_nodes); | |
1140 | auto_sbitmap tmp (num_nodes); | |
d397e8c6 | 1141 | |
f61e445a LC |
1142 | bitmap_copy (reachable_from, from); |
1143 | bitmap_copy (tmp, from); | |
d397e8c6 MH |
1144 | |
1145 | change = 1; | |
1146 | while (change) | |
1147 | { | |
1148 | change = 0; | |
f61e445a LC |
1149 | bitmap_copy (workset, tmp); |
1150 | bitmap_clear (tmp); | |
d4ac4ce2 | 1151 | EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) |
d397e8c6 MH |
1152 | { |
1153 | ddg_edge_ptr e; | |
1154 | ddg_node_ptr u_node = &g->nodes[u]; | |
1155 | ||
1156 | for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out) | |
1157 | { | |
1158 | ddg_node_ptr v_node = e->dest; | |
1159 | int v = v_node->cuid; | |
1160 | ||
d7c028c0 | 1161 | if (!bitmap_bit_p (reachable_from, v)) |
d397e8c6 | 1162 | { |
d7c028c0 LC |
1163 | bitmap_set_bit (reachable_from, v); |
1164 | bitmap_set_bit (tmp, v); | |
d397e8c6 MH |
1165 | change = 1; |
1166 | } | |
1167 | } | |
b6e7e9af | 1168 | } |
d397e8c6 MH |
1169 | } |
1170 | ||
f61e445a LC |
1171 | bitmap_copy (reach_to, to); |
1172 | bitmap_copy (tmp, to); | |
d397e8c6 MH |
1173 | |
1174 | change = 1; | |
1175 | while (change) | |
1176 | { | |
1177 | change = 0; | |
f61e445a LC |
1178 | bitmap_copy (workset, tmp); |
1179 | bitmap_clear (tmp); | |
d4ac4ce2 | 1180 | EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) |
d397e8c6 MH |
1181 | { |
1182 | ddg_edge_ptr e; | |
1183 | ddg_node_ptr u_node = &g->nodes[u]; | |
1184 | ||
1185 | for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in) | |
1186 | { | |
1187 | ddg_node_ptr v_node = e->src; | |
1188 | int v = v_node->cuid; | |
1189 | ||
d7c028c0 | 1190 | if (!bitmap_bit_p (reach_to, v)) |
d397e8c6 | 1191 | { |
d7c028c0 LC |
1192 | bitmap_set_bit (reach_to, v); |
1193 | bitmap_set_bit (tmp, v); | |
d397e8c6 MH |
1194 | change = 1; |
1195 | } | |
1196 | } | |
b6e7e9af | 1197 | } |
d397e8c6 MH |
1198 | } |
1199 | ||
8f48c622 | 1200 | return bitmap_and (result, reachable_from, reach_to); |
d397e8c6 MH |
1201 | } |
1202 | ||
a750daa2 | 1203 | #endif /* INSN_SCHEDULING */ |