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