Mercurial > hg > CbC > CbC_gcc
annotate gcc/ddg.c @ 142:c83ff0b5a2ed
merge
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 22 Nov 2018 19:45:33 +0900 |
parents | 84e7813d76e9 |
children | 1830386684a0 |
rev | line source |
---|---|
0 | 1 /* DDG - Data Dependence Graph implementation. |
131 | 2 Copyright (C) 2004-2018 Free Software Foundation, Inc. |
0 | 3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com> |
4 | |
5 This file is part of GCC. | |
6 | |
7 GCC is free software; you can redistribute it and/or modify it under | |
8 the terms of the GNU General Public License as published by the Free | |
9 Software Foundation; either version 3, or (at your option) any later | |
10 version. | |
11 | |
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
18 along with GCC; see the file COPYING3. If not see | |
19 <http://www.gnu.org/licenses/>. */ | |
20 | |
21 | |
22 #include "config.h" | |
23 #include "system.h" | |
24 #include "coretypes.h" | |
111 | 25 #include "backend.h" |
0 | 26 #include "rtl.h" |
111 | 27 #include "df.h" |
0 | 28 #include "insn-attr.h" |
29 #include "sched-int.h" | |
30 #include "ddg.h" | |
111 | 31 #include "rtl-iter.h" |
0 | 32 |
33 #ifdef INSN_SCHEDULING | |
34 | |
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); | |
42 static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr, | |
43 ddg_node_ptr, dep_t); | |
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 | |
50 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */ | |
51 static bool mem_ref_p; | |
52 | |
53 /* Auxiliary function for mem_read_insn_p. */ | |
111 | 54 static void |
55 mark_mem_use (rtx *x, void *) | |
0 | 56 { |
111 | 57 subrtx_iterator::array_type array; |
58 FOR_EACH_SUBRTX (iter, array, *x, NONCONST) | |
59 if (MEM_P (*iter)) | |
60 { | |
61 mem_ref_p = true; | |
62 break; | |
63 } | |
0 | 64 } |
65 | |
66 /* Returns nonzero if INSN reads from memory. */ | |
67 static bool | |
111 | 68 mem_read_insn_p (rtx_insn *insn) |
0 | 69 { |
70 mem_ref_p = false; | |
111 | 71 note_uses (&PATTERN (insn), mark_mem_use, NULL); |
0 | 72 return mem_ref_p; |
73 } | |
74 | |
75 static void | |
76 mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) | |
77 { | |
78 if (MEM_P (loc)) | |
79 mem_ref_p = true; | |
80 } | |
81 | |
82 /* Returns nonzero if INSN writes to memory. */ | |
83 static bool | |
111 | 84 mem_write_insn_p (rtx_insn *insn) |
0 | 85 { |
86 mem_ref_p = false; | |
87 note_stores (PATTERN (insn), mark_mem_store, NULL); | |
88 return mem_ref_p; | |
89 } | |
90 | |
91 /* Returns nonzero if X has access to memory. */ | |
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 | |
102 if (MEM_P (x)) | |
103 return true; | |
104 | |
105 code = GET_CODE (x); | |
106 fmt = GET_RTX_FORMAT (code); | |
107 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
108 { | |
109 if (fmt[i] == 'e') | |
110 { | |
111 if (rtx_mem_access_p (XEXP (x, i))) | |
112 return true; | |
113 } | |
114 else if (fmt[i] == 'E') | |
115 for (j = 0; j < XVECLEN (x, i); j++) | |
116 { | |
117 if (rtx_mem_access_p (XVECEXP (x, i, j))) | |
118 return true; | |
119 } | |
120 } | |
121 return false; | |
122 } | |
123 | |
124 /* Returns nonzero if INSN reads to or writes from memory. */ | |
125 static bool | |
111 | 126 mem_access_insn_p (rtx_insn *insn) |
0 | 127 { |
128 return rtx_mem_access_p (PATTERN (insn)); | |
129 } | |
130 | |
111 | 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 | |
140 autoinc_var_is_used_p (rtx_insn *def_insn, rtx_insn *use_insn) | |
141 { | |
142 rtx note; | |
143 | |
144 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1)) | |
145 if (REG_NOTE_KIND (note) == REG_INC | |
146 && reg_referenced_p (XEXP (note, 0), PATTERN (use_insn))) | |
147 return true; | |
148 | |
149 return false; | |
150 } | |
151 | |
152 /* Return true if one of the definitions in INSN has MODE_CC. Otherwise | |
153 return false. */ | |
154 static bool | |
155 def_has_ccmode_p (rtx_insn *insn) | |
156 { | |
157 df_ref def; | |
158 | |
159 FOR_EACH_INSN_DEF (def, insn) | |
160 { | |
161 machine_mode mode = GET_MODE (DF_REF_REG (def)); | |
162 | |
163 if (GET_MODE_CLASS (mode) == MODE_CC) | |
164 return true; | |
165 } | |
166 | |
167 return false; | |
168 } | |
169 | |
0 | 170 /* Computes the dependence parameters (latency, distance etc.), creates |
171 a ddg_edge and adds it to the given DDG. */ | |
172 static void | |
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) | |
175 { | |
176 ddg_edge_ptr e; | |
177 int latency, distance = 0; | |
178 dep_type t = TRUE_DEP; | |
179 dep_data_type dt = (mem_access_insn_p (src_node->insn) | |
180 && mem_access_insn_p (dest_node->insn) ? MEM_DEP | |
181 : REG_DEP); | |
182 gcc_assert (src_node->cuid < dest_node->cuid); | |
183 gcc_assert (link); | |
184 | |
185 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */ | |
186 if (DEP_TYPE (link) == REG_DEP_ANTI) | |
187 t = ANTI_DEP; | |
188 else if (DEP_TYPE (link) == REG_DEP_OUTPUT) | |
189 t = OUTPUT_DEP; | |
190 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
191 gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
192 gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
193 |
0 | 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 | |
111 | 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 | |
0 | 203 whose register has multiple defs in the loop. */ |
111 | 204 if (flag_modulo_sched_allow_regmoves |
205 && (t == ANTI_DEP && dt == REG_DEP) | |
206 && !def_has_ccmode_p (dest_node->insn) | |
207 && !autoinc_var_is_used_p (dest_node->insn, src_node->insn)) | |
0 | 208 { |
209 rtx set; | |
210 | |
211 set = single_set (dest_node->insn); | |
212 /* TODO: Handle registers that REG_P is not true for them, i.e. | |
213 subregs and special registers. */ | |
214 if (set && REG_P (SET_DEST (set))) | |
215 { | |
216 int regno = REGNO (SET_DEST (set)); | |
217 df_ref first_def; | |
218 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); | |
219 | |
220 first_def = df_bb_regno_first_def_find (g->bb, regno); | |
221 gcc_assert (first_def); | |
222 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
223 if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def))) |
0 | 224 return; |
225 } | |
226 } | |
227 | |
228 latency = dep_cost (link); | |
229 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance); | |
230 add_edge_to_ddg (g, e); | |
231 } | |
232 | |
233 /* The same as the above function, but it doesn't require a link parameter. */ | |
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; | |
240 enum reg_note dep_kind; | |
241 struct _dep _dep, *dep = &_dep; | |
242 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
243 gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
244 gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
245 |
0 | 246 if (d_t == ANTI_DEP) |
247 dep_kind = REG_DEP_ANTI; | |
248 else if (d_t == OUTPUT_DEP) | |
249 dep_kind = REG_DEP_OUTPUT; | |
250 else | |
251 { | |
252 gcc_assert (d_t == TRUE_DEP); | |
253 | |
254 dep_kind = REG_DEP_TRUE; | |
255 } | |
256 | |
257 init_dep (dep, from->insn, to->insn, dep_kind); | |
258 | |
259 l = dep_cost (dep); | |
260 | |
261 e = create_ddg_edge (from, to, d_t, d_dt, l, distance); | |
262 if (distance > 0) | |
263 add_backarc_to_ddg (g, e); | |
264 else | |
265 add_edge_to_ddg (g, e); | |
266 } | |
267 | |
268 | |
269 /* Given a downwards exposed register def LAST_DEF (which is the last | |
270 definition of that register in the bb), add inter-loop true dependences | |
271 to all its uses in the next iteration, an output dependence to the | |
272 first def of the same register (possibly itself) in the next iteration | |
273 and anti-dependences from its uses in the current iteration to the | |
274 first definition in the next iteration. */ | |
275 static void | |
276 add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def) | |
277 { | |
278 int regno = DF_REF_REGNO (last_def); | |
279 struct df_link *r_use; | |
280 int has_use_in_bb_p = false; | |
111 | 281 rtx_insn *def_insn = DF_REF_INSN (last_def); |
0 | 282 ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn); |
283 ddg_node_ptr use_node; | |
284 df_ref first_def = df_bb_regno_first_def_find (g->bb, regno); | |
285 | |
286 gcc_assert (last_def_node); | |
287 gcc_assert (first_def); | |
288 | |
111 | 289 if (flag_checking && DF_REF_ID (last_def) != DF_REF_ID (first_def)) |
290 { | |
291 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); | |
292 gcc_assert (!bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def))); | |
293 } | |
0 | 294 |
295 /* Create inter-loop true dependences and anti dependences. */ | |
296 for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next) | |
297 { | |
131 | 298 if (DF_REF_BB (r_use->ref) != g->bb) |
299 continue; | |
0 | 300 |
131 | 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); | |
0 | 305 |
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. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
315 create_ddg_dep_no_link (g, last_def_node, use_node, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
316 DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP, |
0 | 317 REG_DEP, 1); |
318 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
319 else if (!DEBUG_INSN_P (use_insn)) |
0 | 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, | |
328 DF_REF_INSN (first_def)); | |
329 | |
330 gcc_assert (first_def_node); | |
331 | |
111 | 332 /* Always create the edge if the use node is a branch in |
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. */ | |
0 | 337 if (DF_REF_ID (last_def) != DF_REF_ID (first_def) |
111 | 338 || !flag_modulo_sched_allow_regmoves |
339 || JUMP_P (use_node->insn) | |
340 || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn) | |
341 || def_has_ccmode_p (DF_REF_INSN (last_def))) | |
0 | 342 create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP, |
343 REG_DEP, 1); | |
344 | |
345 } | |
346 } | |
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) | |
355 { | |
356 ddg_node_ptr dest_node; | |
357 | |
358 if (DF_REF_ID (last_def) == DF_REF_ID (first_def)) | |
359 return; | |
360 | |
361 dest_node = get_node_of_insn (g, DF_REF_INSN (first_def)); | |
362 gcc_assert (dest_node); | |
363 create_ddg_dep_no_link (g, last_def_node, dest_node, | |
364 OUTPUT_DEP, REG_DEP, 1); | |
365 } | |
366 } | |
367 /* Build inter-loop dependencies, by looking at DF analysis backwards. */ | |
368 static void | |
369 build_inter_loop_deps (ddg_ptr g) | |
370 { | |
371 unsigned rd_num; | |
372 struct df_rd_bb_info *rd_bb_info; | |
373 bitmap_iterator bi; | |
374 | |
375 rd_bb_info = DF_RD_BB_INFO (g->bb); | |
376 | |
377 /* Find inter-loop register output, true and anti deps. */ | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
378 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi) |
0 | 379 { |
380 df_ref rd = DF_DEFS_GET (rd_num); | |
381 | |
382 add_cross_iteration_register_deps (g, rd); | |
383 } | |
384 } | |
385 | |
386 | |
111 | 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) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
391 { |
111 | 392 subrtx_iterator::array_type array1; |
393 subrtx_iterator::array_type array2; | |
394 FOR_EACH_SUBRTX (iter1, array1, PATTERN (insn1), NONCONST) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
395 { |
111 | 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 } | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
404 } |
111 | 405 return false; |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
406 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
407 |
111 | 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) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
412 { |
111 | 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; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
419 |
111 | 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); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
430 } |
111 | 431 else if (!mem_read_insn_p (to->insn)) |
432 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 0); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
433 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
434 |
0 | 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 { | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
440 if (!insns_may_alias_p (from->insn, to->insn)) |
0 | 441 /* Do not create edge if memory references have disjoint alias sets. */ |
442 return; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
443 |
0 | 444 if (mem_write_insn_p (from->insn)) |
445 { | |
446 if (mem_read_insn_p (to->insn)) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
447 create_ddg_dep_no_link (g, from, to, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
448 DEBUG_INSN_P (to->insn) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
449 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1); |
0 | 450 else if (from->cuid != to->cuid) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
451 create_ddg_dep_no_link (g, from, to, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
452 DEBUG_INSN_P (to->insn) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
453 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1); |
0 | 454 } |
455 else | |
456 { | |
457 if (mem_read_insn_p (to->insn)) | |
458 return; | |
459 else if (from->cuid != to->cuid) | |
460 { | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
461 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
462 if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
463 create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
464 else |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
465 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1); |
0 | 466 } |
467 } | |
468 | |
469 } | |
470 | |
471 /* Perform intra-block Data Dependency analysis and connect the nodes in | |
472 the DDG. We assume the loop has a single basic block. */ | |
473 static void | |
474 build_intra_loop_deps (ddg_ptr g) | |
475 { | |
476 int i; | |
477 /* Hold the dependency analysis state during dependency calculations. */ | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
478 struct deps_desc tmp_deps; |
111 | 479 rtx_insn *head, *tail; |
0 | 480 |
481 /* Build the dependence information, using the sched_analyze function. */ | |
482 init_deps_global (); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
483 init_deps (&tmp_deps, false); |
0 | 484 |
485 /* Do the intra-block data dependence analysis for the given block. */ | |
486 get_ebb_head_tail (g->bb, g->bb, &head, &tail); | |
487 sched_analyze (&tmp_deps, head, tail); | |
488 | |
489 /* Build intra-loop data dependencies using the scheduler dependency | |
490 analysis. */ | |
491 for (i = 0; i < g->num_nodes; i++) | |
492 { | |
493 ddg_node_ptr dest_node = &g->nodes[i]; | |
494 sd_iterator_def sd_it; | |
495 dep_t dep; | |
496 | |
497 if (! INSN_P (dest_node->insn)) | |
498 continue; | |
499 | |
500 FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep) | |
501 { | |
111 | 502 rtx_insn *src_insn = DEP_PRO (dep); |
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); | |
0 | 511 |
512 if (!src_node) | |
513 continue; | |
514 | |
515 create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep); | |
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]; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
527 if (DEBUG_INSN_P (j_node->insn)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
528 continue; |
0 | 529 if (mem_access_insn_p (j_node->insn)) |
111 | 530 { |
531 /* Don't bother calculating inter-loop dep if an intra-loop dep | |
532 already exists. */ | |
533 if (! bitmap_bit_p (dest_node->successors, j)) | |
0 | 534 add_inter_loop_mem_dep (g, dest_node, j_node); |
111 | 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 | |
543 && !bitmap_bit_p (dest_node->predecessors, j)) | |
544 add_intra_loop_mem_dep (g, j_node, dest_node); | |
545 } | |
0 | 546 } |
547 } | |
548 } | |
549 | |
550 /* Free the INSN_LISTs. */ | |
551 finish_deps_global (); | |
552 free_deps (&tmp_deps); | |
553 | |
554 /* Free dependencies. */ | |
555 sched_free_deps (head, tail, false); | |
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 | |
563 create_ddg (basic_block bb, int closing_branch_deps) | |
564 { | |
565 ddg_ptr g; | |
111 | 566 rtx_insn *insn, *first_note; |
0 | 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 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
582 if (DEBUG_INSN_P (insn)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
583 g->num_debug++; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
584 else |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
585 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
586 if (mem_read_insn_p (insn)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
587 g->num_loads++; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
588 if (mem_write_insn_p (insn)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
589 g->num_stores++; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
590 } |
0 | 591 num_nodes++; |
592 } | |
593 | |
594 /* There is nothing to do for this BB. */ | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
595 if ((num_nodes - g->num_debug) <= 1) |
0 | 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; | |
111 | 606 first_note = NULL; |
0 | 607 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); |
608 insn = NEXT_INSN (insn)) | |
609 { | |
610 if (! INSN_P (insn)) | |
611 { | |
612 if (! first_note && NOTE_P (insn) | |
613 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK) | |
614 first_note = insn; | |
615 continue; | |
616 } | |
617 if (JUMP_P (insn)) | |
618 { | |
619 gcc_assert (!g->closing_branch); | |
620 g->closing_branch = &g->nodes[i]; | |
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); | |
111 | 631 bitmap_clear (g->nodes[i].successors); |
0 | 632 g->nodes[i].predecessors = sbitmap_alloc (num_nodes); |
111 | 633 bitmap_clear (g->nodes[i].predecessors); |
0 | 634 g->nodes[i].first_note = (first_note ? first_note : insn); |
635 g->nodes[i++].insn = insn; | |
111 | 636 first_note = NULL; |
0 | 637 } |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
638 |
0 | 639 /* We must have found a branch in DDG. */ |
640 gcc_assert (g->closing_branch); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
641 |
0 | 642 |
643 /* Build the data dependency graph. */ | |
644 build_intra_loop_deps (g); | |
645 build_inter_loop_deps (g); | |
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 | |
679 print_ddg_edge (FILE *file, ddg_edge_ptr e) | |
680 { | |
681 char dep_c; | |
682 | |
683 switch (e->type) | |
684 { | |
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'; | |
693 } | |
694 | |
695 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn), | |
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 | |
701 print_ddg (FILE *file, ddg_ptr g) | |
702 { | |
703 int i; | |
704 | |
705 for (i = 0; i < g->num_nodes; i++) | |
706 { | |
707 ddg_edge_ptr e; | |
708 | |
709 fprintf (file, "Node num: %d\n", g->nodes[i].cuid); | |
710 print_rtl_single (file, g->nodes[i].insn); | |
711 fprintf (file, "OUT ARCS: "); | |
712 for (e = g->nodes[i].out; e; e = e->next_out) | |
713 print_ddg_edge (file, e); | |
714 | |
715 fprintf (file, "\nIN ARCS: "); | |
716 for (e = g->nodes[i].in; e; e = e->next_in) | |
717 print_ddg_edge (file, e); | |
718 | |
719 fprintf (file, "\n"); | |
720 } | |
721 } | |
722 | |
723 /* Print the given DDG in VCG format. */ | |
111 | 724 DEBUG_FUNCTION void |
0 | 725 vcg_print_ddg (FILE *file, ddg_ptr g) |
726 { | |
727 int src_cuid; | |
728 | |
729 fprintf (file, "graph: {\n"); | |
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 | |
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"); | |
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) | |
745 fprintf (file, "backedge: {color: red "); | |
746 else | |
747 fprintf (file, "edge: { "); | |
748 | |
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); | |
752 } | |
753 } | |
754 fprintf (file, "}\n"); | |
755 } | |
756 | |
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); | |
111 | 772 EXECUTE_IF_SET_IN_BITMAP (sccs->sccs[i]->nodes, 0, u, sbi) |
0 | 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 | |
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 | |
806 /* Should have allocated the sbitmaps. */ | |
807 gcc_assert (src->successors && dest->predecessors); | |
808 | |
111 | 809 bitmap_set_bit (src->successors, dest->cuid); |
810 bitmap_set_bit (dest->predecessors, src->cuid); | |
0 | 811 e->next_in = dest->in; |
812 dest->in = e; | |
813 e->next_out = src->out; | |
814 src->out = e; | |
815 } | |
816 | |
817 | |
818 | |
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; | |
854 unsigned int u = 0; | |
855 sbitmap_iterator sbi; | |
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); | |
111 | 861 bitmap_copy (scc->nodes, nodes); |
0 | 862 |
863 /* Mark the backarcs that belong to this SCC. */ | |
111 | 864 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi) |
0 | 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) | |
111 | 870 if (bitmap_bit_p (nodes, e->dest->cuid)) |
0 | 871 { |
872 e->aux.count = IN_SCC; | |
873 if (e->distance > 0) | |
874 add_backarc_to_scc (scc, e); | |
875 } | |
876 } | |
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 | |
111 | 929 get_node_of_insn (ddg_ptr g, rtx_insn *insn) |
0 | 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 { | |
945 unsigned int i = 0; | |
946 sbitmap_iterator sbi; | |
947 | |
111 | 948 EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi) |
0 | 949 { |
950 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]); | |
111 | 951 bitmap_ior (succ, succ, node_succ); |
0 | 952 }; |
953 | |
954 /* We want those that are not in ops. */ | |
111 | 955 bitmap_and_compl (succ, succ, ops); |
0 | 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 { | |
964 unsigned int i = 0; | |
965 sbitmap_iterator sbi; | |
966 | |
111 | 967 EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi) |
0 | 968 { |
969 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]); | |
111 | 970 bitmap_ior (preds, preds, node_preds); |
0 | 971 }; |
972 | |
973 /* We want those that are not in ops. */ | |
111 | 974 bitmap_and_compl (preds, preds, ops); |
0 | 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 { | |
983 const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
984 const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length; |
0 | 985 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1)); |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
986 |
0 | 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 | |
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; | |
111 | 1003 auto_sbitmap tmp (num_nodes); |
0 | 1004 |
111 | 1005 bitmap_clear (tmp); |
0 | 1006 for (i = 0; i < sccs->num_sccs; i++) |
1007 { | |
111 | 1008 gcc_assert (!bitmap_empty_p (sccs->sccs[i]->nodes)); |
0 | 1009 /* Verify that every node in sccs is in exactly one strongly |
1010 connected component. */ | |
111 | 1011 gcc_assert (!bitmap_intersect_p (tmp, sccs->sccs[i]->nodes)); |
1012 bitmap_ior (tmp, tmp, sccs->sccs[i]->nodes); | |
0 | 1013 } |
1014 } | |
1015 | |
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; | |
111 | 1023 auto_sbitmap from (num_nodes); |
1024 auto_sbitmap to (num_nodes); | |
1025 auto_sbitmap scc_nodes (num_nodes); | |
0 | 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 | |
111 | 1044 bitmap_clear (scc_nodes); |
1045 bitmap_clear (from); | |
1046 bitmap_clear (to); | |
1047 bitmap_set_bit (from, dest->cuid); | |
1048 bitmap_set_bit (to, src->cuid); | |
0 | 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); | |
111 | 1057 |
1058 if (flag_checking) | |
1059 check_sccs (sccs, num_nodes); | |
1060 | |
0 | 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 | |
111 | 1076 free (all_sccs->sccs); |
0 | 1077 free (all_sccs); |
1078 } | |
1079 | |
1080 | |
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 | |
1083 nodes from FROM and TO). Return nonzero if nodes exist. */ | |
1084 int | |
1085 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) | |
1086 { | |
1087 int change; | |
1088 unsigned int u = 0; | |
1089 int num_nodes = g->num_nodes; | |
1090 sbitmap_iterator sbi; | |
1091 | |
111 | 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); | |
0 | 1096 |
111 | 1097 bitmap_copy (reachable_from, from); |
1098 bitmap_copy (tmp, from); | |
0 | 1099 |
1100 change = 1; | |
1101 while (change) | |
1102 { | |
1103 change = 0; | |
111 | 1104 bitmap_copy (workset, tmp); |
1105 bitmap_clear (tmp); | |
1106 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) | |
0 | 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 | |
111 | 1116 if (!bitmap_bit_p (reachable_from, v)) |
0 | 1117 { |
111 | 1118 bitmap_set_bit (reachable_from, v); |
1119 bitmap_set_bit (tmp, v); | |
0 | 1120 change = 1; |
1121 } | |
1122 } | |
1123 } | |
1124 } | |
1125 | |
111 | 1126 bitmap_copy (reach_to, to); |
1127 bitmap_copy (tmp, to); | |
0 | 1128 |
1129 change = 1; | |
1130 while (change) | |
1131 { | |
1132 change = 0; | |
111 | 1133 bitmap_copy (workset, tmp); |
1134 bitmap_clear (tmp); | |
1135 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) | |
0 | 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 | |
111 | 1145 if (!bitmap_bit_p (reach_to, v)) |
0 | 1146 { |
111 | 1147 bitmap_set_bit (reach_to, v); |
1148 bitmap_set_bit (tmp, v); | |
0 | 1149 change = 1; |
1150 } | |
1151 } | |
1152 } | |
1153 } | |
1154 | |
111 | 1155 return bitmap_and (result, reachable_from, reach_to); |
0 | 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). | |
1162 Returns nonzero if any count was changed. */ | |
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 | |
111 | 1174 if (bitmap_bit_p (nodes, v) |
0 | 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; | |
111 | 1179 bitmap_set_bit (tmp, v); |
0 | 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 { | |
1192 int i; | |
1193 unsigned int u = 0; | |
1194 int change = 1; | |
1195 int num_nodes = g->num_nodes; | |
111 | 1196 auto_sbitmap workset (num_nodes); |
1197 auto_sbitmap tmp (num_nodes); | |
0 | 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 | |
111 | 1206 bitmap_clear (tmp); |
1207 bitmap_set_bit (tmp, src); | |
0 | 1208 |
1209 while (change) | |
1210 { | |
1211 sbitmap_iterator sbi; | |
1212 | |
1213 change = 0; | |
111 | 1214 bitmap_copy (workset, tmp); |
1215 bitmap_clear (tmp); | |
1216 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) | |
0 | 1217 { |
1218 ddg_node_ptr u_node = &g->nodes[u]; | |
1219 | |
1220 change |= update_dist_to_successors (u_node, nodes, tmp); | |
1221 } | |
1222 } | |
111 | 1223 return g->nodes[dest].aux.count; |
0 | 1224 } |
1225 | |
1226 #endif /* INSN_SCHEDULING */ |