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