]>
Commit | Line | Data |
---|---|---|
d397e8c6 | 1 | /* DDG - Data Dependence Graph implementation. |
4d779342 | 2 | Copyright (C) 2004, 2005, 2006 |
d397e8c6 MH |
3 | Free Software Foundation, Inc. |
4 | Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com> | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify it under | |
9 | the terms of the GNU General Public License as published by the Free | |
10 | Software Foundation; either version 2, or (at your option) any later | |
11 | version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
16 | for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING. If not, write to the Free | |
366ccddb KC |
20 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
21 | 02110-1301, USA. */ | |
d397e8c6 MH |
22 | |
23 | ||
24 | #include "config.h" | |
25 | #include "system.h" | |
26 | #include "coretypes.h" | |
27 | #include "tm.h" | |
28 | #include "toplev.h" | |
29 | #include "rtl.h" | |
30 | #include "tm_p.h" | |
31 | #include "hard-reg-set.h" | |
d397e8c6 MH |
32 | #include "regs.h" |
33 | #include "function.h" | |
34 | #include "flags.h" | |
35 | #include "insn-config.h" | |
36 | #include "insn-attr.h" | |
37 | #include "except.h" | |
38 | #include "recog.h" | |
39 | #include "sched-int.h" | |
40 | #include "target.h" | |
41 | #include "cfglayout.h" | |
42 | #include "cfgloop.h" | |
43 | #include "sbitmap.h" | |
44 | #include "expr.h" | |
45 | #include "bitmap.h" | |
46 | #include "df.h" | |
47 | #include "ddg.h" | |
48 | ||
49 | /* A flag indicating that a ddg edge belongs to an SCC or not. */ | |
50 | enum edge_flag {NOT_IN_SCC = 0, IN_SCC}; | |
51 | ||
52 | /* Forward declarations. */ | |
53 | static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr); | |
54 | static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr); | |
55 | static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr); | |
56 | static void create_ddg_dependence (ddg_ptr, ddg_node_ptr, ddg_node_ptr, rtx); | |
57 | static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr, | |
58 | dep_type, dep_data_type, int); | |
59 | static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type, | |
60 | dep_data_type, int, int); | |
61 | static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr); | |
62 | \f | |
63 | /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */ | |
64 | static bool mem_ref_p; | |
65 | ||
66 | /* Auxiliary function for mem_read_insn_p. */ | |
67 | static int | |
68 | mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED) | |
69 | { | |
d9c4ef55 | 70 | if (MEM_P (*x)) |
d397e8c6 MH |
71 | mem_ref_p = true; |
72 | return 0; | |
73 | } | |
74 | ||
75 | /* Auxiliary function for mem_read_insn_p. */ | |
76 | static void | |
77 | mark_mem_use_1 (rtx *x, void *data) | |
78 | { | |
79 | for_each_rtx (x, mark_mem_use, data); | |
80 | } | |
81 | ||
1ea7e6ad | 82 | /* Returns nonzero if INSN reads from memory. */ |
d397e8c6 MH |
83 | static bool |
84 | mem_read_insn_p (rtx insn) | |
85 | { | |
86 | mem_ref_p = false; | |
87 | note_uses (&PATTERN (insn), mark_mem_use_1, NULL); | |
88 | return mem_ref_p; | |
89 | } | |
90 | ||
91 | static void | |
92 | mark_mem_store (rtx loc, rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) | |
93 | { | |
d9c4ef55 | 94 | if (MEM_P (loc)) |
d397e8c6 MH |
95 | mem_ref_p = true; |
96 | } | |
97 | ||
1ea7e6ad | 98 | /* Returns nonzero if INSN writes to memory. */ |
d397e8c6 MH |
99 | static bool |
100 | mem_write_insn_p (rtx insn) | |
101 | { | |
102 | mem_ref_p = false; | |
103 | note_stores (PATTERN (insn), mark_mem_store, NULL); | |
104 | return mem_ref_p; | |
105 | } | |
106 | ||
1ea7e6ad | 107 | /* Returns nonzero if X has access to memory. */ |
d397e8c6 MH |
108 | static bool |
109 | rtx_mem_access_p (rtx x) | |
110 | { | |
111 | int i, j; | |
112 | const char *fmt; | |
113 | enum rtx_code code; | |
114 | ||
115 | if (x == 0) | |
116 | return false; | |
117 | ||
d9c4ef55 | 118 | if (MEM_P (x)) |
d397e8c6 MH |
119 | return true; |
120 | ||
121 | code = GET_CODE (x); | |
122 | fmt = GET_RTX_FORMAT (code); | |
123 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
124 | { | |
125 | if (fmt[i] == 'e') | |
126 | { | |
127 | if (rtx_mem_access_p (XEXP (x, i))) | |
128 | return true; | |
129 | } | |
130 | else if (fmt[i] == 'E') | |
131 | for (j = 0; j < XVECLEN (x, i); j++) | |
132 | { | |
133 | if (rtx_mem_access_p (XVECEXP (x, i, j))) | |
134 | return true; | |
135 | } | |
136 | } | |
137 | return false; | |
138 | } | |
139 | ||
1ea7e6ad | 140 | /* Returns nonzero if INSN reads to or writes from memory. */ |
d397e8c6 MH |
141 | static bool |
142 | mem_access_insn_p (rtx insn) | |
143 | { | |
144 | return rtx_mem_access_p (PATTERN (insn)); | |
145 | } | |
146 | ||
147 | /* Computes the dependence parameters (latency, distance etc.), creates | |
148 | a ddg_edge and adds it to the given DDG. */ | |
149 | static void | |
150 | create_ddg_dependence (ddg_ptr g, ddg_node_ptr src_node, | |
151 | ddg_node_ptr dest_node, rtx link) | |
152 | { | |
153 | ddg_edge_ptr e; | |
154 | int latency, distance = 0; | |
155 | int interloop = (src_node->cuid >= dest_node->cuid); | |
156 | dep_type t = TRUE_DEP; | |
157 | dep_data_type dt = (mem_access_insn_p (src_node->insn) | |
158 | && mem_access_insn_p (dest_node->insn) ? MEM_DEP | |
159 | : REG_DEP); | |
160 | ||
161 | /* For now we don't have an exact calculation of the distance, | |
162 | so assume 1 conservatively. */ | |
163 | if (interloop) | |
164 | distance = 1; | |
165 | ||
ced3f397 | 166 | gcc_assert (link); |
d397e8c6 MH |
167 | |
168 | /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */ | |
169 | if (REG_NOTE_KIND (link) == REG_DEP_ANTI) | |
170 | t = ANTI_DEP; | |
171 | else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) | |
172 | t = OUTPUT_DEP; | |
173 | latency = insn_cost (src_node->insn, link, dest_node->insn); | |
174 | ||
175 | e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance); | |
176 | ||
177 | if (interloop) | |
178 | { | |
179 | /* Some interloop dependencies are relaxed: | |
180 | 1. Every insn is output dependent on itself; ignore such deps. | |
181 | 2. Every true/flow dependence is an anti dependence in the | |
182 | opposite direction with distance 1; such register deps | |
183 | will be removed by renaming if broken --- ignore them. */ | |
184 | if (!(t == OUTPUT_DEP && src_node == dest_node) | |
185 | && !(t == ANTI_DEP && dt == REG_DEP)) | |
186 | add_backarc_to_ddg (g, e); | |
187 | else | |
188 | free (e); | |
189 | } | |
d331e204 MH |
190 | else if (t == ANTI_DEP && dt == REG_DEP) |
191 | free (e); /* We can fix broken anti register deps using reg-moves. */ | |
d397e8c6 MH |
192 | else |
193 | add_edge_to_ddg (g, e); | |
194 | } | |
195 | ||
196 | /* The same as the above function, but it doesn't require a link parameter. */ | |
197 | static void | |
198 | create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, | |
199 | dep_type d_t, dep_data_type d_dt, int distance) | |
200 | { | |
201 | ddg_edge_ptr e; | |
202 | int l; | |
203 | rtx link = alloc_INSN_LIST (to->insn, NULL_RTX); | |
204 | ||
205 | if (d_t == ANTI_DEP) | |
206 | PUT_REG_NOTE_KIND (link, REG_DEP_ANTI); | |
207 | else if (d_t == OUTPUT_DEP) | |
208 | PUT_REG_NOTE_KIND (link, REG_DEP_OUTPUT); | |
209 | ||
210 | l = insn_cost (from->insn, link, to->insn); | |
211 | free_INSN_LIST_node (link); | |
212 | ||
213 | e = create_ddg_edge (from, to, d_t, d_dt, l, distance); | |
214 | if (distance > 0) | |
215 | add_backarc_to_ddg (g, e); | |
216 | else | |
217 | add_edge_to_ddg (g, e); | |
218 | } | |
219 | ||
220 | \f | |
221 | /* Given a downwards exposed register def RD, add inter-loop true dependences | |
222 | for all its uses in the next iteration, and an output dependence to the | |
223 | first def of the next iteration. */ | |
224 | static void | |
4d779342 | 225 | add_deps_for_def (ddg_ptr g, struct df *df, struct df_ref *rd) |
d397e8c6 MH |
226 | { |
227 | int regno = DF_REF_REGNO (rd); | |
4d779342 | 228 | struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (df, g->bb); |
d397e8c6 MH |
229 | struct df_link *r_use; |
230 | int use_before_def = false; | |
231 | rtx def_insn = DF_REF_INSN (rd); | |
232 | ddg_node_ptr src_node = get_node_of_insn (g, def_insn); | |
233 | ||
234 | /* Create and inter-loop true dependence between RD and each of its uses | |
235 | that is upwards exposed in RD's block. */ | |
236 | for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next) | |
237 | { | |
4d779342 | 238 | if (bitmap_bit_p (bb_info->gen, r_use->ref->id)) |
d397e8c6 MH |
239 | { |
240 | rtx use_insn = DF_REF_INSN (r_use->ref); | |
241 | ddg_node_ptr dest_node = get_node_of_insn (g, use_insn); | |
242 | ||
ced3f397 | 243 | gcc_assert (src_node && dest_node); |
d397e8c6 MH |
244 | |
245 | /* Any such upwards exposed use appears before the rd def. */ | |
246 | use_before_def = true; | |
247 | create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP, | |
248 | REG_DEP, 1); | |
249 | } | |
250 | } | |
251 | ||
252 | /* Create an inter-loop output dependence between RD (which is the | |
253 | last def in its block, being downwards exposed) and the first def | |
254 | in its block. Avoid creating a self output dependence. Avoid creating | |
255 | an output dependence if there is a dependence path between the two defs | |
256 | starting with a true dependence followed by an anti dependence (i.e. if | |
257 | there is a use between the two defs. */ | |
258 | if (! use_before_def) | |
259 | { | |
4d779342 | 260 | struct df_ref *def = df_bb_regno_first_def_find (df, g->bb, regno); |
d397e8c6 MH |
261 | int i; |
262 | ddg_node_ptr dest_node; | |
263 | ||
264 | if (!def || rd->id == def->id) | |
265 | return; | |
266 | ||
267 | /* Check if there are uses after RD. */ | |
268 | for (i = src_node->cuid + 1; i < g->num_nodes; i++) | |
4d779342 | 269 | if (df_find_use (df, g->nodes[i].insn, rd->reg)) |
d397e8c6 MH |
270 | return; |
271 | ||
272 | dest_node = get_node_of_insn (g, def->insn); | |
273 | create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, REG_DEP, 1); | |
274 | } | |
275 | } | |
276 | ||
277 | /* Given a register USE, add an inter-loop anti dependence to the first | |
278 | (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed | |
279 | by a def in the block. */ | |
280 | static void | |
4d779342 | 281 | add_deps_for_use (ddg_ptr g, struct df *df, struct df_ref *use) |
d397e8c6 MH |
282 | { |
283 | int i; | |
284 | int regno = DF_REF_REGNO (use); | |
4d779342 | 285 | struct df_ref *first_def = df_bb_regno_first_def_find (df, g->bb, regno); |
d397e8c6 MH |
286 | ddg_node_ptr use_node; |
287 | ddg_node_ptr def_node; | |
4d779342 | 288 | struct df_rd_bb_info *bb_info; |
d397e8c6 | 289 | |
4d779342 | 290 | bb_info = DF_RD_BB_INFO (df, g->bb); |
d397e8c6 MH |
291 | |
292 | if (!first_def) | |
293 | return; | |
294 | ||
295 | use_node = get_node_of_insn (g, use->insn); | |
296 | def_node = get_node_of_insn (g, first_def->insn); | |
297 | ||
ced3f397 | 298 | gcc_assert (use_node && def_node); |
d397e8c6 MH |
299 | |
300 | /* Make sure there are no defs after USE. */ | |
301 | for (i = use_node->cuid + 1; i < g->num_nodes; i++) | |
302 | if (df_find_def (df, g->nodes[i].insn, use->reg)) | |
303 | return; | |
304 | /* We must not add ANTI dep when there is an intra-loop TRUE dep in | |
0fa2e4df | 305 | the opposite direction. If the first_def reaches the USE then there is |
9cf737f8 | 306 | such a dep. */ |
4d779342 | 307 | if (! bitmap_bit_p (bb_info->gen, first_def->id)) |
d397e8c6 MH |
308 | create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1); |
309 | } | |
310 | ||
311 | /* Build inter-loop dependencies, by looking at DF analysis backwards. */ | |
312 | static void | |
313 | build_inter_loop_deps (ddg_ptr g, struct df *df) | |
314 | { | |
3cd8c58a | 315 | unsigned rd_num, u_num; |
4d779342 DB |
316 | struct df_rd_bb_info *rd_bb_info; |
317 | struct df_ru_bb_info *ru_bb_info; | |
87c476a2 | 318 | bitmap_iterator bi; |
d397e8c6 | 319 | |
4d779342 | 320 | rd_bb_info = DF_RD_BB_INFO (df, g->bb); |
d397e8c6 MH |
321 | |
322 | /* Find inter-loop output and true deps by connecting downward exposed defs | |
323 | to the first def of the BB and to upwards exposed uses. */ | |
4d779342 | 324 | EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi) |
d397e8c6 | 325 | { |
4d779342 | 326 | struct df_ref *rd = DF_DEFS_GET (df, rd_num); |
d397e8c6 MH |
327 | |
328 | add_deps_for_def (g, df, rd); | |
87c476a2 | 329 | } |
d397e8c6 | 330 | |
4d779342 DB |
331 | ru_bb_info = DF_RU_BB_INFO (df, g->bb); |
332 | ||
d397e8c6 MH |
333 | /* Find inter-loop anti deps. We are interested in uses of the block that |
334 | appear below all defs; this implies that these uses are killed. */ | |
4d779342 | 335 | EXECUTE_IF_SET_IN_BITMAP (ru_bb_info->kill, 0, u_num, bi) |
d397e8c6 | 336 | { |
4d779342 | 337 | struct df_ref *use = DF_USES_GET (df, u_num); |
d397e8c6 MH |
338 | |
339 | /* We are interested in uses of this BB. */ | |
340 | if (BLOCK_FOR_INSN (use->insn) == g->bb) | |
341 | add_deps_for_use (g, df,use); | |
87c476a2 | 342 | } |
d397e8c6 MH |
343 | } |
344 | ||
345 | /* Given two nodes, analyze their RTL insns and add inter-loop mem deps | |
346 | to ddg G. */ | |
347 | static void | |
348 | add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) | |
349 | { | |
350 | if (mem_write_insn_p (from->insn)) | |
351 | { | |
352 | if (mem_read_insn_p (to->insn)) | |
353 | create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1); | |
354 | else if (from->cuid != to->cuid) | |
355 | create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1); | |
356 | } | |
357 | else | |
358 | { | |
359 | if (mem_read_insn_p (to->insn)) | |
360 | return; | |
361 | else if (from->cuid != to->cuid) | |
362 | { | |
363 | create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1); | |
364 | create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1); | |
365 | } | |
366 | } | |
367 | ||
368 | } | |
369 | ||
370 | /* Perform intra-block Data Dependency analysis and connect the nodes in | |
9cf737f8 | 371 | the DDG. We assume the loop has a single basic block. */ |
d397e8c6 MH |
372 | static void |
373 | build_intra_loop_deps (ddg_ptr g) | |
374 | { | |
375 | int i; | |
376 | /* Hold the dependency analysis state during dependency calculations. */ | |
377 | struct deps tmp_deps; | |
378 | rtx head, tail, link; | |
379 | ||
380 | /* Build the dependence information, using the sched_analyze function. */ | |
381 | init_deps_global (); | |
382 | init_deps (&tmp_deps); | |
383 | ||
384 | /* Do the intra-block data dependence analysis for the given block. */ | |
385 | get_block_head_tail (g->bb->index, &head, &tail); | |
386 | sched_analyze (&tmp_deps, head, tail); | |
387 | ||
61ada8ae | 388 | /* Build intra-loop data dependencies using the scheduler dependency |
d397e8c6 MH |
389 | analysis. */ |
390 | for (i = 0; i < g->num_nodes; i++) | |
391 | { | |
392 | ddg_node_ptr dest_node = &g->nodes[i]; | |
393 | ||
394 | if (! INSN_P (dest_node->insn)) | |
395 | continue; | |
396 | ||
397 | for (link = LOG_LINKS (dest_node->insn); link; link = XEXP (link, 1)) | |
398 | { | |
399 | ddg_node_ptr src_node = get_node_of_insn (g, XEXP (link, 0)); | |
400 | ||
401 | if (!src_node) | |
402 | continue; | |
403 | ||
404 | add_forward_dependence (XEXP (link, 0), dest_node->insn, | |
405 | REG_NOTE_KIND (link)); | |
406 | create_ddg_dependence (g, src_node, dest_node, | |
407 | INSN_DEPEND (src_node->insn)); | |
408 | } | |
409 | ||
410 | /* If this insn modifies memory, add an edge to all insns that access | |
411 | memory. */ | |
412 | if (mem_access_insn_p (dest_node->insn)) | |
413 | { | |
414 | int j; | |
415 | ||
416 | for (j = 0; j <= i; j++) | |
417 | { | |
418 | ddg_node_ptr j_node = &g->nodes[j]; | |
419 | if (mem_access_insn_p (j_node->insn)) | |
420 | /* Don't bother calculating inter-loop dep if an intra-loop dep | |
421 | already exists. */ | |
422 | if (! TEST_BIT (dest_node->successors, j)) | |
423 | add_inter_loop_mem_dep (g, dest_node, j_node); | |
424 | } | |
425 | } | |
426 | } | |
427 | ||
428 | /* Free the INSN_LISTs. */ | |
429 | finish_deps_global (); | |
430 | free_deps (&tmp_deps); | |
431 | } | |
432 | ||
433 | ||
434 | /* Given a basic block, create its DDG and return a pointer to a variable | |
435 | of ddg type that represents it. | |
436 | Initialize the ddg structure fields to the appropriate values. */ | |
437 | ddg_ptr | |
438 | create_ddg (basic_block bb, struct df *df, int closing_branch_deps) | |
439 | { | |
440 | ddg_ptr g; | |
441 | rtx insn, first_note; | |
442 | int i; | |
443 | int num_nodes = 0; | |
444 | ||
445 | g = (ddg_ptr) xcalloc (1, sizeof (struct ddg)); | |
446 | ||
447 | g->bb = bb; | |
448 | g->closing_branch_deps = closing_branch_deps; | |
449 | ||
450 | /* Count the number of insns in the BB. */ | |
451 | for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); | |
452 | insn = NEXT_INSN (insn)) | |
453 | { | |
454 | if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE) | |
455 | continue; | |
456 | ||
457 | if (mem_read_insn_p (insn)) | |
458 | g->num_loads++; | |
459 | if (mem_write_insn_p (insn)) | |
460 | g->num_stores++; | |
461 | num_nodes++; | |
462 | } | |
463 | ||
464 | /* There is nothing to do for this BB. */ | |
465 | if (num_nodes <= 1) | |
466 | { | |
467 | free (g); | |
468 | return NULL; | |
469 | } | |
470 | ||
471 | /* Allocate the nodes array, and initialize the nodes. */ | |
472 | g->num_nodes = num_nodes; | |
473 | g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node)); | |
474 | g->closing_branch = NULL; | |
475 | i = 0; | |
476 | first_note = NULL_RTX; | |
477 | for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); | |
478 | insn = NEXT_INSN (insn)) | |
479 | { | |
480 | if (! INSN_P (insn)) | |
481 | { | |
4b4bf941 | 482 | if (! first_note && NOTE_P (insn) |
d397e8c6 MH |
483 | && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK) |
484 | first_note = insn; | |
485 | continue; | |
486 | } | |
4b4bf941 | 487 | if (JUMP_P (insn)) |
d397e8c6 | 488 | { |
ced3f397 NS |
489 | gcc_assert (!g->closing_branch); |
490 | g->closing_branch = &g->nodes[i]; | |
d397e8c6 MH |
491 | } |
492 | else if (GET_CODE (PATTERN (insn)) == USE) | |
493 | { | |
494 | if (! first_note) | |
495 | first_note = insn; | |
496 | continue; | |
497 | } | |
498 | ||
499 | g->nodes[i].cuid = i; | |
500 | g->nodes[i].successors = sbitmap_alloc (num_nodes); | |
501 | sbitmap_zero (g->nodes[i].successors); | |
502 | g->nodes[i].predecessors = sbitmap_alloc (num_nodes); | |
503 | sbitmap_zero (g->nodes[i].predecessors); | |
504 | g->nodes[i].first_note = (first_note ? first_note : insn); | |
505 | g->nodes[i++].insn = insn; | |
506 | first_note = NULL_RTX; | |
507 | } | |
ced3f397 NS |
508 | |
509 | /* We must have found a branch in DDG. */ | |
510 | gcc_assert (g->closing_branch); | |
511 | ||
d397e8c6 | 512 | |
61ada8ae | 513 | /* Build the data dependency graph. */ |
d397e8c6 MH |
514 | build_intra_loop_deps (g); |
515 | build_inter_loop_deps (g, df); | |
516 | return g; | |
517 | } | |
518 | ||
519 | /* Free all the memory allocated for the DDG. */ | |
520 | void | |
521 | free_ddg (ddg_ptr g) | |
522 | { | |
523 | int i; | |
524 | ||
525 | if (!g) | |
526 | return; | |
527 | ||
528 | for (i = 0; i < g->num_nodes; i++) | |
529 | { | |
530 | ddg_edge_ptr e = g->nodes[i].out; | |
531 | ||
532 | while (e) | |
533 | { | |
534 | ddg_edge_ptr next = e->next_out; | |
535 | ||
536 | free (e); | |
537 | e = next; | |
538 | } | |
539 | sbitmap_free (g->nodes[i].successors); | |
540 | sbitmap_free (g->nodes[i].predecessors); | |
541 | } | |
542 | if (g->num_backarcs > 0) | |
543 | free (g->backarcs); | |
544 | free (g->nodes); | |
545 | free (g); | |
546 | } | |
547 | ||
548 | void | |
549 | print_ddg_edge (FILE *dump_file, ddg_edge_ptr e) | |
550 | { | |
551 | char dep_c; | |
552 | ||
553 | switch (e->type) { | |
554 | case OUTPUT_DEP : | |
555 | dep_c = 'O'; | |
556 | break; | |
557 | case ANTI_DEP : | |
558 | dep_c = 'A'; | |
559 | break; | |
560 | default: | |
561 | dep_c = 'T'; | |
562 | } | |
563 | ||
564 | fprintf (dump_file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn), | |
565 | dep_c, e->latency, e->distance, INSN_UID (e->dest->insn)); | |
566 | } | |
567 | ||
568 | /* Print the DDG nodes with there in/out edges to the dump file. */ | |
569 | void | |
570 | print_ddg (FILE *dump_file, ddg_ptr g) | |
571 | { | |
572 | int i; | |
573 | ||
574 | for (i = 0; i < g->num_nodes; i++) | |
575 | { | |
576 | ddg_edge_ptr e; | |
577 | ||
578 | print_rtl_single (dump_file, g->nodes[i].insn); | |
579 | fprintf (dump_file, "OUT ARCS: "); | |
580 | for (e = g->nodes[i].out; e; e = e->next_out) | |
581 | print_ddg_edge (dump_file, e); | |
582 | ||
583 | fprintf (dump_file, "\nIN ARCS: "); | |
584 | for (e = g->nodes[i].in; e; e = e->next_in) | |
585 | print_ddg_edge (dump_file, e); | |
586 | ||
587 | fprintf (dump_file, "\n"); | |
588 | } | |
589 | } | |
590 | ||
591 | /* Print the given DDG in VCG format. */ | |
592 | void | |
593 | vcg_print_ddg (FILE *dump_file, ddg_ptr g) | |
594 | { | |
595 | int src_cuid; | |
596 | ||
597 | fprintf (dump_file, "graph: {\n"); | |
598 | for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++) | |
599 | { | |
600 | ddg_edge_ptr e; | |
601 | int src_uid = INSN_UID (g->nodes[src_cuid].insn); | |
602 | ||
603 | fprintf (dump_file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid); | |
604 | print_rtl_single (dump_file, g->nodes[src_cuid].insn); | |
605 | fprintf (dump_file, "\"}\n"); | |
606 | for (e = g->nodes[src_cuid].out; e; e = e->next_out) | |
607 | { | |
608 | int dst_uid = INSN_UID (e->dest->insn); | |
609 | int dst_cuid = e->dest->cuid; | |
610 | ||
611 | /* Give the backarcs a different color. */ | |
612 | if (e->distance > 0) | |
613 | fprintf (dump_file, "backedge: {color: red "); | |
614 | else | |
615 | fprintf (dump_file, "edge: { "); | |
616 | ||
617 | fprintf (dump_file, "sourcename: \"%d_%d\" ", src_cuid, src_uid); | |
618 | fprintf (dump_file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid); | |
619 | fprintf (dump_file, "label: \"%d_%d\"}\n", e->latency, e->distance); | |
620 | } | |
621 | } | |
622 | fprintf (dump_file, "}\n"); | |
623 | } | |
624 | ||
625 | /* Create an edge and initialize it with given values. */ | |
626 | static ddg_edge_ptr | |
627 | create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, | |
628 | dep_type t, dep_data_type dt, int l, int d) | |
629 | { | |
630 | ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge)); | |
631 | ||
632 | e->src = src; | |
633 | e->dest = dest; | |
634 | e->type = t; | |
635 | e->data_type = dt; | |
636 | e->latency = l; | |
637 | e->distance = d; | |
638 | e->next_in = e->next_out = NULL; | |
639 | e->aux.info = 0; | |
640 | return e; | |
641 | } | |
642 | ||
643 | /* Add the given edge to the in/out linked lists of the DDG nodes. */ | |
644 | static void | |
645 | add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e) | |
646 | { | |
647 | ddg_node_ptr src = e->src; | |
648 | ddg_node_ptr dest = e->dest; | |
649 | ||
ced3f397 NS |
650 | /* Should have allocated the sbitmaps. */ |
651 | gcc_assert (src->successors && dest->predecessors); | |
d397e8c6 MH |
652 | |
653 | SET_BIT (src->successors, dest->cuid); | |
654 | SET_BIT (dest->predecessors, src->cuid); | |
655 | e->next_in = dest->in; | |
656 | dest->in = e; | |
657 | e->next_out = src->out; | |
658 | src->out = e; | |
659 | } | |
660 | ||
661 | ||
662 | \f | |
663 | /* Algorithm for computing the recurrence_length of an scc. We assume at | |
664 | for now that cycles in the data dependence graph contain a single backarc. | |
665 | This simplifies the algorithm, and can be generalized later. */ | |
666 | static void | |
667 | set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g) | |
668 | { | |
669 | int j; | |
670 | int result = -1; | |
671 | ||
672 | for (j = 0; j < scc->num_backarcs; j++) | |
673 | { | |
674 | ddg_edge_ptr backarc = scc->backarcs[j]; | |
675 | int length; | |
676 | int distance = backarc->distance; | |
677 | ddg_node_ptr src = backarc->dest; | |
678 | ddg_node_ptr dest = backarc->src; | |
679 | ||
680 | length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes); | |
681 | if (length < 0 ) | |
682 | { | |
683 | /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */ | |
684 | continue; | |
685 | } | |
686 | length += backarc->latency; | |
687 | result = MAX (result, (length / distance)); | |
688 | } | |
689 | scc->recurrence_length = result; | |
690 | } | |
691 | ||
692 | /* Create a new SCC given the set of its nodes. Compute its recurrence_length | |
693 | and mark edges that belong to this scc as IN_SCC. */ | |
694 | static ddg_scc_ptr | |
695 | create_scc (ddg_ptr g, sbitmap nodes) | |
696 | { | |
697 | ddg_scc_ptr scc; | |
dfea6c85 | 698 | unsigned int u = 0; |
b6e7e9af | 699 | sbitmap_iterator sbi; |
d397e8c6 MH |
700 | |
701 | scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc)); | |
702 | scc->backarcs = NULL; | |
703 | scc->num_backarcs = 0; | |
704 | scc->nodes = sbitmap_alloc (g->num_nodes); | |
705 | sbitmap_copy (scc->nodes, nodes); | |
706 | ||
707 | /* Mark the backarcs that belong to this SCC. */ | |
b6e7e9af | 708 | EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi) |
d397e8c6 MH |
709 | { |
710 | ddg_edge_ptr e; | |
711 | ddg_node_ptr n = &g->nodes[u]; | |
712 | ||
713 | for (e = n->out; e; e = e->next_out) | |
714 | if (TEST_BIT (nodes, e->dest->cuid)) | |
715 | { | |
716 | e->aux.count = IN_SCC; | |
717 | if (e->distance > 0) | |
718 | add_backarc_to_scc (scc, e); | |
719 | } | |
b6e7e9af | 720 | } |
d397e8c6 MH |
721 | |
722 | set_recurrence_length (scc, g); | |
723 | return scc; | |
724 | } | |
725 | ||
726 | /* Cleans the memory allocation of a given SCC. */ | |
727 | static void | |
728 | free_scc (ddg_scc_ptr scc) | |
729 | { | |
730 | if (!scc) | |
731 | return; | |
732 | ||
733 | sbitmap_free (scc->nodes); | |
734 | if (scc->num_backarcs > 0) | |
735 | free (scc->backarcs); | |
736 | free (scc); | |
737 | } | |
738 | ||
739 | ||
740 | /* Add a given edge known to be a backarc to the given DDG. */ | |
741 | static void | |
742 | add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e) | |
743 | { | |
744 | int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr); | |
745 | ||
746 | add_edge_to_ddg (g, e); | |
747 | g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size); | |
748 | g->backarcs[g->num_backarcs++] = e; | |
749 | } | |
750 | ||
751 | /* Add backarc to an SCC. */ | |
752 | static void | |
753 | add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e) | |
754 | { | |
755 | int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr); | |
756 | ||
757 | scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size); | |
758 | scc->backarcs[scc->num_backarcs++] = e; | |
759 | } | |
760 | ||
761 | /* Add the given SCC to the DDG. */ | |
762 | static void | |
763 | add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc) | |
764 | { | |
765 | int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr); | |
766 | ||
767 | g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size); | |
768 | g->sccs[g->num_sccs++] = scc; | |
769 | } | |
770 | ||
771 | /* Given the instruction INSN return the node that represents it. */ | |
772 | ddg_node_ptr | |
773 | get_node_of_insn (ddg_ptr g, rtx insn) | |
774 | { | |
775 | int i; | |
776 | ||
777 | for (i = 0; i < g->num_nodes; i++) | |
778 | if (insn == g->nodes[i].insn) | |
779 | return &g->nodes[i]; | |
780 | return NULL; | |
781 | } | |
782 | ||
783 | /* Given a set OPS of nodes in the DDG, find the set of their successors | |
784 | which are not in OPS, and set their bits in SUCC. Bits corresponding to | |
785 | OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */ | |
786 | void | |
787 | find_successors (sbitmap succ, ddg_ptr g, sbitmap ops) | |
788 | { | |
dfea6c85 | 789 | unsigned int i = 0; |
b6e7e9af | 790 | sbitmap_iterator sbi; |
d397e8c6 | 791 | |
b6e7e9af | 792 | EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi) |
d397e8c6 MH |
793 | { |
794 | const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]); | |
795 | sbitmap_a_or_b (succ, succ, node_succ); | |
b6e7e9af | 796 | }; |
d397e8c6 MH |
797 | |
798 | /* We want those that are not in ops. */ | |
799 | sbitmap_difference (succ, succ, ops); | |
800 | } | |
801 | ||
802 | /* Given a set OPS of nodes in the DDG, find the set of their predecessors | |
803 | which are not in OPS, and set their bits in PREDS. Bits corresponding to | |
804 | OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */ | |
805 | void | |
806 | find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops) | |
807 | { | |
dfea6c85 | 808 | unsigned int i = 0; |
b6e7e9af | 809 | sbitmap_iterator sbi; |
d397e8c6 | 810 | |
b6e7e9af | 811 | EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi) |
d397e8c6 MH |
812 | { |
813 | const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]); | |
814 | sbitmap_a_or_b (preds, preds, node_preds); | |
b6e7e9af | 815 | }; |
d397e8c6 MH |
816 | |
817 | /* We want those that are not in ops. */ | |
818 | sbitmap_difference (preds, preds, ops); | |
819 | } | |
820 | ||
821 | ||
822 | /* Compare function to be passed to qsort to order the backarcs in descending | |
823 | recMII order. */ | |
824 | static int | |
825 | compare_sccs (const void *s1, const void *s2) | |
826 | { | |
827 | int rec_l1 = (*(ddg_scc_ptr *)s1)->recurrence_length; | |
828 | int rec_l2 = (*(ddg_scc_ptr *)s2)->recurrence_length; | |
829 | return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1)); | |
830 | ||
831 | } | |
832 | ||
833 | /* Order the backarcs in descending recMII order using compare_sccs. */ | |
834 | static void | |
835 | order_sccs (ddg_all_sccs_ptr g) | |
836 | { | |
837 | qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr), | |
838 | (int (*) (const void *, const void *)) compare_sccs); | |
839 | } | |
840 | ||
841 | /* Perform the Strongly Connected Components decomposing algorithm on the | |
842 | DDG and return DDG_ALL_SCCS structure that contains them. */ | |
843 | ddg_all_sccs_ptr | |
844 | create_ddg_all_sccs (ddg_ptr g) | |
845 | { | |
846 | int i; | |
847 | int num_nodes = g->num_nodes; | |
848 | sbitmap from = sbitmap_alloc (num_nodes); | |
849 | sbitmap to = sbitmap_alloc (num_nodes); | |
850 | sbitmap scc_nodes = sbitmap_alloc (num_nodes); | |
851 | ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr) | |
852 | xmalloc (sizeof (struct ddg_all_sccs)); | |
853 | ||
854 | sccs->ddg = g; | |
855 | sccs->sccs = NULL; | |
856 | sccs->num_sccs = 0; | |
857 | ||
858 | for (i = 0; i < g->num_backarcs; i++) | |
859 | { | |
860 | ddg_scc_ptr scc; | |
861 | ddg_edge_ptr backarc = g->backarcs[i]; | |
862 | ddg_node_ptr src = backarc->src; | |
863 | ddg_node_ptr dest = backarc->dest; | |
864 | ||
865 | /* If the backarc already belongs to an SCC, continue. */ | |
866 | if (backarc->aux.count == IN_SCC) | |
867 | continue; | |
868 | ||
869 | sbitmap_zero (from); | |
870 | sbitmap_zero (to); | |
871 | SET_BIT (from, dest->cuid); | |
872 | SET_BIT (to, src->cuid); | |
873 | ||
874 | if (find_nodes_on_paths (scc_nodes, g, from, to)) | |
875 | { | |
876 | scc = create_scc (g, scc_nodes); | |
877 | add_scc_to_ddg (sccs, scc); | |
878 | } | |
879 | } | |
880 | order_sccs (sccs); | |
881 | sbitmap_free (from); | |
882 | sbitmap_free (to); | |
883 | sbitmap_free (scc_nodes); | |
884 | return sccs; | |
885 | } | |
886 | ||
887 | /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */ | |
888 | void | |
889 | free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) | |
890 | { | |
891 | int i; | |
892 | ||
893 | if (!all_sccs) | |
894 | return; | |
895 | ||
896 | for (i = 0; i < all_sccs->num_sccs; i++) | |
897 | free_scc (all_sccs->sccs[i]); | |
898 | ||
899 | free (all_sccs); | |
900 | } | |
901 | ||
902 | \f | |
903 | /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination | |
904 | nodes - find all nodes that lie on paths from FROM to TO (not excluding | |
b01d837f | 905 | nodes from FROM and TO). Return nonzero if nodes exist. */ |
d397e8c6 MH |
906 | int |
907 | find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) | |
908 | { | |
909 | int answer; | |
b6e7e9af | 910 | int change; |
dfea6c85 | 911 | unsigned int u = 0; |
d397e8c6 | 912 | int num_nodes = g->num_nodes; |
b6e7e9af KH |
913 | sbitmap_iterator sbi; |
914 | ||
d397e8c6 MH |
915 | sbitmap workset = sbitmap_alloc (num_nodes); |
916 | sbitmap reachable_from = sbitmap_alloc (num_nodes); | |
917 | sbitmap reach_to = sbitmap_alloc (num_nodes); | |
918 | sbitmap tmp = sbitmap_alloc (num_nodes); | |
919 | ||
920 | sbitmap_copy (reachable_from, from); | |
921 | sbitmap_copy (tmp, from); | |
922 | ||
923 | change = 1; | |
924 | while (change) | |
925 | { | |
926 | change = 0; | |
927 | sbitmap_copy (workset, tmp); | |
928 | sbitmap_zero (tmp); | |
b6e7e9af | 929 | EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) |
d397e8c6 MH |
930 | { |
931 | ddg_edge_ptr e; | |
932 | ddg_node_ptr u_node = &g->nodes[u]; | |
933 | ||
934 | for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out) | |
935 | { | |
936 | ddg_node_ptr v_node = e->dest; | |
937 | int v = v_node->cuid; | |
938 | ||
939 | if (!TEST_BIT (reachable_from, v)) | |
940 | { | |
941 | SET_BIT (reachable_from, v); | |
942 | SET_BIT (tmp, v); | |
943 | change = 1; | |
944 | } | |
945 | } | |
b6e7e9af | 946 | } |
d397e8c6 MH |
947 | } |
948 | ||
949 | sbitmap_copy (reach_to, to); | |
950 | sbitmap_copy (tmp, to); | |
951 | ||
952 | change = 1; | |
953 | while (change) | |
954 | { | |
955 | change = 0; | |
956 | sbitmap_copy (workset, tmp); | |
957 | sbitmap_zero (tmp); | |
b6e7e9af | 958 | EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) |
d397e8c6 MH |
959 | { |
960 | ddg_edge_ptr e; | |
961 | ddg_node_ptr u_node = &g->nodes[u]; | |
962 | ||
963 | for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in) | |
964 | { | |
965 | ddg_node_ptr v_node = e->src; | |
966 | int v = v_node->cuid; | |
967 | ||
968 | if (!TEST_BIT (reach_to, v)) | |
969 | { | |
970 | SET_BIT (reach_to, v); | |
971 | SET_BIT (tmp, v); | |
972 | change = 1; | |
973 | } | |
974 | } | |
b6e7e9af | 975 | } |
d397e8c6 MH |
976 | } |
977 | ||
978 | answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to); | |
979 | sbitmap_free (workset); | |
980 | sbitmap_free (reachable_from); | |
981 | sbitmap_free (reach_to); | |
982 | sbitmap_free (tmp); | |
983 | return answer; | |
984 | } | |
985 | ||
986 | ||
987 | /* Updates the counts of U_NODE's successors (that belong to NODES) to be | |
988 | at-least as large as the count of U_NODE plus the latency between them. | |
989 | Sets a bit in TMP for each successor whose count was changed (increased). | |
1ea7e6ad | 990 | Returns nonzero if any count was changed. */ |
d397e8c6 MH |
991 | static int |
992 | update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp) | |
993 | { | |
994 | ddg_edge_ptr e; | |
995 | int result = 0; | |
996 | ||
997 | for (e = u_node->out; e; e = e->next_out) | |
998 | { | |
999 | ddg_node_ptr v_node = e->dest; | |
1000 | int v = v_node->cuid; | |
1001 | ||
1002 | if (TEST_BIT (nodes, v) | |
1003 | && (e->distance == 0) | |
1004 | && (v_node->aux.count < u_node->aux.count + e->latency)) | |
1005 | { | |
1006 | v_node->aux.count = u_node->aux.count + e->latency; | |
1007 | SET_BIT (tmp, v); | |
1008 | result = 1; | |
1009 | } | |
1010 | } | |
1011 | return result; | |
1012 | } | |
1013 | ||
1014 | ||
1015 | /* Find the length of a longest path from SRC to DEST in G, | |
1016 | going only through NODES, and disregarding backarcs. */ | |
1017 | int | |
1018 | longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes) | |
1019 | { | |
b6e7e9af | 1020 | int i; |
dfea6c85 | 1021 | unsigned int u = 0; |
d397e8c6 MH |
1022 | int change = 1; |
1023 | int result; | |
1024 | int num_nodes = g->num_nodes; | |
1025 | sbitmap workset = sbitmap_alloc (num_nodes); | |
1026 | sbitmap tmp = sbitmap_alloc (num_nodes); | |
1027 | ||
1028 | ||
1029 | /* Data will hold the distance of the longest path found so far from | |
1030 | src to each node. Initialize to -1 = less than minimum. */ | |
1031 | for (i = 0; i < g->num_nodes; i++) | |
1032 | g->nodes[i].aux.count = -1; | |
1033 | g->nodes[src].aux.count = 0; | |
1034 | ||
1035 | sbitmap_zero (tmp); | |
1036 | SET_BIT (tmp, src); | |
1037 | ||
1038 | while (change) | |
1039 | { | |
b6e7e9af KH |
1040 | sbitmap_iterator sbi; |
1041 | ||
d397e8c6 MH |
1042 | change = 0; |
1043 | sbitmap_copy (workset, tmp); | |
1044 | sbitmap_zero (tmp); | |
b6e7e9af | 1045 | EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi) |
d397e8c6 MH |
1046 | { |
1047 | ddg_node_ptr u_node = &g->nodes[u]; | |
1048 | ||
1049 | change |= update_dist_to_successors (u_node, nodes, tmp); | |
b6e7e9af | 1050 | } |
d397e8c6 MH |
1051 | } |
1052 | result = g->nodes[dest].aux.count; | |
1053 | sbitmap_free (workset); | |
1054 | sbitmap_free (tmp); | |
1055 | return result; | |
1056 | } |