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