xref: /dflybsd-src/contrib/gcc-4.7/gcc/df-core.c (revision 04febcfb30580676d3e95f58a16c5137ee478b32)
1*e4b17023SJohn Marino /* Allocation for dataflow support routines.
2*e4b17023SJohn Marino    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3*e4b17023SJohn Marino    2008, 2009, 2010, 2011 Free Software Foundation, Inc.
4*e4b17023SJohn Marino    Originally contributed by Michael P. Hayes
5*e4b17023SJohn Marino              (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6*e4b17023SJohn Marino    Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7*e4b17023SJohn Marino              and Kenneth Zadeck (zadeck@naturalbridge.com).
8*e4b17023SJohn Marino 
9*e4b17023SJohn Marino This file is part of GCC.
10*e4b17023SJohn Marino 
11*e4b17023SJohn Marino GCC is free software; you can redistribute it and/or modify it under
12*e4b17023SJohn Marino the terms of the GNU General Public License as published by the Free
13*e4b17023SJohn Marino Software Foundation; either version 3, or (at your option) any later
14*e4b17023SJohn Marino version.
15*e4b17023SJohn Marino 
16*e4b17023SJohn Marino GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17*e4b17023SJohn Marino WARRANTY; without even the implied warranty of MERCHANTABILITY or
18*e4b17023SJohn Marino FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
19*e4b17023SJohn Marino for more details.
20*e4b17023SJohn Marino 
21*e4b17023SJohn Marino You should have received a copy of the GNU General Public License
22*e4b17023SJohn Marino along with GCC; see the file COPYING3.  If not see
23*e4b17023SJohn Marino <http://www.gnu.org/licenses/>.  */
24*e4b17023SJohn Marino 
25*e4b17023SJohn Marino /*
26*e4b17023SJohn Marino OVERVIEW:
27*e4b17023SJohn Marino 
28*e4b17023SJohn Marino The files in this collection (df*.c,df.h) provide a general framework
29*e4b17023SJohn Marino for solving dataflow problems.  The global dataflow is performed using
30*e4b17023SJohn Marino a good implementation of iterative dataflow analysis.
31*e4b17023SJohn Marino 
32*e4b17023SJohn Marino The file df-problems.c provides problem instance for the most common
33*e4b17023SJohn Marino dataflow problems: reaching defs, upward exposed uses, live variables,
34*e4b17023SJohn Marino uninitialized variables, def-use chains, and use-def chains.  However,
35*e4b17023SJohn Marino the interface allows other dataflow problems to be defined as well.
36*e4b17023SJohn Marino 
37*e4b17023SJohn Marino Dataflow analysis is available in most of the rtl backend (the parts
38*e4b17023SJohn Marino between pass_df_initialize and pass_df_finish).  It is quite likely
39*e4b17023SJohn Marino that these boundaries will be expanded in the future.  The only
40*e4b17023SJohn Marino requirement is that there be a correct control flow graph.
41*e4b17023SJohn Marino 
42*e4b17023SJohn Marino There are three variations of the live variable problem that are
43*e4b17023SJohn Marino available whenever dataflow is available.  The LR problem finds the
44*e4b17023SJohn Marino areas that can reach a use of a variable, the UR problems finds the
45*e4b17023SJohn Marino areas that can be reached from a definition of a variable.  The LIVE
46*e4b17023SJohn Marino problem finds the intersection of these two areas.
47*e4b17023SJohn Marino 
48*e4b17023SJohn Marino There are several optional problems.  These can be enabled when they
49*e4b17023SJohn Marino are needed and disabled when they are not needed.
50*e4b17023SJohn Marino 
51*e4b17023SJohn Marino Dataflow problems are generally solved in three layers.  The bottom
52*e4b17023SJohn Marino layer is called scanning where a data structure is built for each rtl
53*e4b17023SJohn Marino insn that describes the set of defs and uses of that insn.  Scanning
54*e4b17023SJohn Marino is generally kept up to date, i.e. as the insns changes, the scanned
55*e4b17023SJohn Marino version of that insn changes also.  There are various mechanisms for
56*e4b17023SJohn Marino making this happen and are described in the INCREMENTAL SCANNING
57*e4b17023SJohn Marino section.
58*e4b17023SJohn Marino 
59*e4b17023SJohn Marino In the middle layer, basic blocks are scanned to produce transfer
60*e4b17023SJohn Marino functions which describe the effects of that block on the global
61*e4b17023SJohn Marino dataflow solution.  The transfer functions are only rebuilt if the
62*e4b17023SJohn Marino some instruction within the block has changed.
63*e4b17023SJohn Marino 
64*e4b17023SJohn Marino The top layer is the dataflow solution itself.  The dataflow solution
65*e4b17023SJohn Marino is computed by using an efficient iterative solver and the transfer
66*e4b17023SJohn Marino functions.  The dataflow solution must be recomputed whenever the
67*e4b17023SJohn Marino control changes or if one of the transfer function changes.
68*e4b17023SJohn Marino 
69*e4b17023SJohn Marino 
70*e4b17023SJohn Marino USAGE:
71*e4b17023SJohn Marino 
72*e4b17023SJohn Marino Here is an example of using the dataflow routines.
73*e4b17023SJohn Marino 
74*e4b17023SJohn Marino       df_[chain,live,note,rd]_add_problem (flags);
75*e4b17023SJohn Marino 
76*e4b17023SJohn Marino       df_set_blocks (blocks);
77*e4b17023SJohn Marino 
78*e4b17023SJohn Marino       df_analyze ();
79*e4b17023SJohn Marino 
80*e4b17023SJohn Marino       df_dump (stderr);
81*e4b17023SJohn Marino 
82*e4b17023SJohn Marino       df_finish_pass (false);
83*e4b17023SJohn Marino 
84*e4b17023SJohn Marino DF_[chain,live,note,rd]_ADD_PROBLEM adds a problem, defined by an
85*e4b17023SJohn Marino instance to struct df_problem, to the set of problems solved in this
86*e4b17023SJohn Marino instance of df.  All calls to add a problem for a given instance of df
87*e4b17023SJohn Marino must occur before the first call to DF_ANALYZE.
88*e4b17023SJohn Marino 
89*e4b17023SJohn Marino Problems can be dependent on other problems.  For instance, solving
90*e4b17023SJohn Marino def-use or use-def chains is dependent on solving reaching
91*e4b17023SJohn Marino definitions. As long as these dependencies are listed in the problem
92*e4b17023SJohn Marino definition, the order of adding the problems is not material.
93*e4b17023SJohn Marino Otherwise, the problems will be solved in the order of calls to
94*e4b17023SJohn Marino df_add_problem.  Note that it is not necessary to have a problem.  In
95*e4b17023SJohn Marino that case, df will just be used to do the scanning.
96*e4b17023SJohn Marino 
97*e4b17023SJohn Marino 
98*e4b17023SJohn Marino 
99*e4b17023SJohn Marino DF_SET_BLOCKS is an optional call used to define a region of the
100*e4b17023SJohn Marino function on which the analysis will be performed.  The normal case is
101*e4b17023SJohn Marino to analyze the entire function and no call to df_set_blocks is made.
102*e4b17023SJohn Marino DF_SET_BLOCKS only effects the blocks that are effected when computing
103*e4b17023SJohn Marino the transfer functions and final solution.  The insn level information
104*e4b17023SJohn Marino is always kept up to date.
105*e4b17023SJohn Marino 
106*e4b17023SJohn Marino When a subset is given, the analysis behaves as if the function only
107*e4b17023SJohn Marino contains those blocks and any edges that occur directly between the
108*e4b17023SJohn Marino blocks in the set.  Care should be taken to call df_set_blocks right
109*e4b17023SJohn Marino before the call to analyze in order to eliminate the possibility that
110*e4b17023SJohn Marino optimizations that reorder blocks invalidate the bitvector.
111*e4b17023SJohn Marino 
112*e4b17023SJohn Marino DF_ANALYZE causes all of the defined problems to be (re)solved.  When
113*e4b17023SJohn Marino DF_ANALYZE is completes, the IN and OUT sets for each basic block
114*e4b17023SJohn Marino contain the computer information.  The DF_*_BB_INFO macros can be used
115*e4b17023SJohn Marino to access these bitvectors.  All deferred rescannings are down before
116*e4b17023SJohn Marino the transfer functions are recomputed.
117*e4b17023SJohn Marino 
118*e4b17023SJohn Marino DF_DUMP can then be called to dump the information produce to some
119*e4b17023SJohn Marino file.  This calls DF_DUMP_START, to print the information that is not
120*e4b17023SJohn Marino basic block specific, and then calls DF_DUMP_TOP and DF_DUMP_BOTTOM
121*e4b17023SJohn Marino for each block to print the basic specific information.  These parts
122*e4b17023SJohn Marino can all be called separately as part of a larger dump function.
123*e4b17023SJohn Marino 
124*e4b17023SJohn Marino 
125*e4b17023SJohn Marino DF_FINISH_PASS causes df_remove_problem to be called on all of the
126*e4b17023SJohn Marino optional problems.  It also causes any insns whose scanning has been
127*e4b17023SJohn Marino deferred to be rescanned as well as clears all of the changeable flags.
128*e4b17023SJohn Marino Setting the pass manager TODO_df_finish flag causes this function to
129*e4b17023SJohn Marino be run.  However, the pass manager will call df_finish_pass AFTER the
130*e4b17023SJohn Marino pass dumping has been done, so if you want to see the results of the
131*e4b17023SJohn Marino optional problems in the pass dumps, use the TODO flag rather than
132*e4b17023SJohn Marino calling the function yourself.
133*e4b17023SJohn Marino 
134*e4b17023SJohn Marino INCREMENTAL SCANNING
135*e4b17023SJohn Marino 
136*e4b17023SJohn Marino There are four ways of doing the incremental scanning:
137*e4b17023SJohn Marino 
138*e4b17023SJohn Marino 1) Immediate rescanning - Calls to df_insn_rescan, df_notes_rescan,
139*e4b17023SJohn Marino    df_bb_delete, df_insn_change_bb have been added to most of
140*e4b17023SJohn Marino    the low level service functions that maintain the cfg and change
141*e4b17023SJohn Marino    rtl.  Calling and of these routines many cause some number of insns
142*e4b17023SJohn Marino    to be rescanned.
143*e4b17023SJohn Marino 
144*e4b17023SJohn Marino    For most modern rtl passes, this is certainly the easiest way to
145*e4b17023SJohn Marino    manage rescanning the insns.  This technique also has the advantage
146*e4b17023SJohn Marino    that the scanning information is always correct and can be relied
147*e4b17023SJohn Marino    upon even after changes have been made to the instructions.  This
148*e4b17023SJohn Marino    technique is contra indicated in several cases:
149*e4b17023SJohn Marino 
150*e4b17023SJohn Marino    a) If def-use chains OR use-def chains (but not both) are built,
151*e4b17023SJohn Marino       using this is SIMPLY WRONG.  The problem is that when a ref is
152*e4b17023SJohn Marino       deleted that is the target of an edge, there is not enough
153*e4b17023SJohn Marino       information to efficiently find the source of the edge and
154*e4b17023SJohn Marino       delete the edge.  This leaves a dangling reference that may
155*e4b17023SJohn Marino       cause problems.
156*e4b17023SJohn Marino 
157*e4b17023SJohn Marino    b) If def-use chains AND use-def chains are built, this may
158*e4b17023SJohn Marino       produce unexpected results.  The problem is that the incremental
159*e4b17023SJohn Marino       scanning of an insn does not know how to repair the chains that
160*e4b17023SJohn Marino       point into an insn when the insn changes.  So the incremental
161*e4b17023SJohn Marino       scanning just deletes the chains that enter and exit the insn
162*e4b17023SJohn Marino       being changed.  The dangling reference issue in (a) is not a
163*e4b17023SJohn Marino       problem here, but if the pass is depending on the chains being
164*e4b17023SJohn Marino       maintained after insns have been modified, this technique will
165*e4b17023SJohn Marino       not do the correct thing.
166*e4b17023SJohn Marino 
167*e4b17023SJohn Marino    c) If the pass modifies insns several times, this incremental
168*e4b17023SJohn Marino       updating may be expensive.
169*e4b17023SJohn Marino 
170*e4b17023SJohn Marino    d) If the pass modifies all of the insns, as does register
171*e4b17023SJohn Marino       allocation, it is simply better to rescan the entire function.
172*e4b17023SJohn Marino 
173*e4b17023SJohn Marino 2) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and
174*e4b17023SJohn Marino    df_insn_delete do not immediately change the insn but instead make
175*e4b17023SJohn Marino    a note that the insn needs to be rescanned.  The next call to
176*e4b17023SJohn Marino    df_analyze, df_finish_pass, or df_process_deferred_rescans will
177*e4b17023SJohn Marino    cause all of the pending rescans to be processed.
178*e4b17023SJohn Marino 
179*e4b17023SJohn Marino    This is the technique of choice if either 1a, 1b, or 1c are issues
180*e4b17023SJohn Marino    in the pass.  In the case of 1a or 1b, a call to df_finish_pass
181*e4b17023SJohn Marino    (either manually or via TODO_df_finish) should be made before the
182*e4b17023SJohn Marino    next call to df_analyze or df_process_deferred_rescans.
183*e4b17023SJohn Marino 
184*e4b17023SJohn Marino    This mode is also used by a few passes that still rely on note_uses,
185*e4b17023SJohn Marino    note_stores and for_each_rtx instead of using the DF data.  This
186*e4b17023SJohn Marino    can be said to fall under case 1c.
187*e4b17023SJohn Marino 
188*e4b17023SJohn Marino    To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN).
189*e4b17023SJohn Marino    (This mode can be cleared by calling df_clear_flags
190*e4b17023SJohn Marino    (DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to
191*e4b17023SJohn Marino    be rescanned.
192*e4b17023SJohn Marino 
193*e4b17023SJohn Marino 3) Total rescanning - In this mode the rescanning is disabled.
194*e4b17023SJohn Marino    Only when insns are deleted is the df information associated with
195*e4b17023SJohn Marino    it also deleted.  At the end of the pass, a call must be made to
196*e4b17023SJohn Marino    df_insn_rescan_all.  This method is used by the register allocator
197*e4b17023SJohn Marino    since it generally changes each insn multiple times (once for each ref)
198*e4b17023SJohn Marino    and does not need to make use of the updated scanning information.
199*e4b17023SJohn Marino 
200*e4b17023SJohn Marino 4) Do it yourself - In this mechanism, the pass updates the insns
201*e4b17023SJohn Marino    itself using the low level df primitives.  Currently no pass does
202*e4b17023SJohn Marino    this, but it has the advantage that it is quite efficient given
203*e4b17023SJohn Marino    that the pass generally has exact knowledge of what it is changing.
204*e4b17023SJohn Marino 
205*e4b17023SJohn Marino DATA STRUCTURES
206*e4b17023SJohn Marino 
207*e4b17023SJohn Marino Scanning produces a `struct df_ref' data structure (ref) is allocated
208*e4b17023SJohn Marino for every register reference (def or use) and this records the insn
209*e4b17023SJohn Marino and bb the ref is found within.  The refs are linked together in
210*e4b17023SJohn Marino chains of uses and defs for each insn and for each register.  Each ref
211*e4b17023SJohn Marino also has a chain field that links all the use refs for a def or all
212*e4b17023SJohn Marino the def refs for a use.  This is used to create use-def or def-use
213*e4b17023SJohn Marino chains.
214*e4b17023SJohn Marino 
215*e4b17023SJohn Marino Different optimizations have different needs.  Ultimately, only
216*e4b17023SJohn Marino register allocation and schedulers should be using the bitmaps
217*e4b17023SJohn Marino produced for the live register and uninitialized register problems.
218*e4b17023SJohn Marino The rest of the backend should be upgraded to using and maintaining
219*e4b17023SJohn Marino the linked information such as def use or use def chains.
220*e4b17023SJohn Marino 
221*e4b17023SJohn Marino 
222*e4b17023SJohn Marino PHILOSOPHY:
223*e4b17023SJohn Marino 
224*e4b17023SJohn Marino While incremental bitmaps are not worthwhile to maintain, incremental
225*e4b17023SJohn Marino chains may be perfectly reasonable.  The fastest way to build chains
226*e4b17023SJohn Marino from scratch or after significant modifications is to build reaching
227*e4b17023SJohn Marino definitions (RD) and build the chains from this.
228*e4b17023SJohn Marino 
229*e4b17023SJohn Marino However, general algorithms for maintaining use-def or def-use chains
230*e4b17023SJohn Marino are not practical.  The amount of work to recompute the chain any
231*e4b17023SJohn Marino chain after an arbitrary change is large.  However, with a modest
232*e4b17023SJohn Marino amount of work it is generally possible to have the application that
233*e4b17023SJohn Marino uses the chains keep them up to date.  The high level knowledge of
234*e4b17023SJohn Marino what is really happening is essential to crafting efficient
235*e4b17023SJohn Marino incremental algorithms.
236*e4b17023SJohn Marino 
237*e4b17023SJohn Marino As for the bit vector problems, there is no interface to give a set of
238*e4b17023SJohn Marino blocks over with to resolve the iteration.  In general, restarting a
239*e4b17023SJohn Marino dataflow iteration is difficult and expensive.  Again, the best way to
240*e4b17023SJohn Marino keep the dataflow information up to data (if this is really what is
241*e4b17023SJohn Marino needed) it to formulate a problem specific solution.
242*e4b17023SJohn Marino 
243*e4b17023SJohn Marino There are fine grained calls for creating and deleting references from
244*e4b17023SJohn Marino instructions in df-scan.c.  However, these are not currently connected
245*e4b17023SJohn Marino to the engine that resolves the dataflow equations.
246*e4b17023SJohn Marino 
247*e4b17023SJohn Marino 
248*e4b17023SJohn Marino DATA STRUCTURES:
249*e4b17023SJohn Marino 
250*e4b17023SJohn Marino The basic object is a DF_REF (reference) and this may either be a
251*e4b17023SJohn Marino DEF (definition) or a USE of a register.
252*e4b17023SJohn Marino 
253*e4b17023SJohn Marino These are linked into a variety of lists; namely reg-def, reg-use,
254*e4b17023SJohn Marino insn-def, insn-use, def-use, and use-def lists.  For example, the
255*e4b17023SJohn Marino reg-def lists contain all the locations that define a given register
256*e4b17023SJohn Marino while the insn-use lists contain all the locations that use a
257*e4b17023SJohn Marino register.
258*e4b17023SJohn Marino 
259*e4b17023SJohn Marino Note that the reg-def and reg-use chains are generally short for
260*e4b17023SJohn Marino pseudos and long for the hard registers.
261*e4b17023SJohn Marino 
262*e4b17023SJohn Marino ACCESSING INSNS:
263*e4b17023SJohn Marino 
264*e4b17023SJohn Marino 1) The df insn information is kept in an array of DF_INSN_INFO objects.
265*e4b17023SJohn Marino    The array is indexed by insn uid, and every DF_REF points to the
266*e4b17023SJohn Marino    DF_INSN_INFO object of the insn that contains the reference.
267*e4b17023SJohn Marino 
268*e4b17023SJohn Marino 2) Each insn has three sets of refs, which are linked into one of three
269*e4b17023SJohn Marino    lists: The insn's defs list (accessed by the DF_INSN_INFO_DEFS,
270*e4b17023SJohn Marino    DF_INSN_DEFS, or DF_INSN_UID_DEFS macros), the insn's uses list
271*e4b17023SJohn Marino    (accessed by the DF_INSN_INFO_USES, DF_INSN_USES, or
272*e4b17023SJohn Marino    DF_INSN_UID_USES macros) or the insn's eq_uses list (accessed by the
273*e4b17023SJohn Marino    DF_INSN_INFO_EQ_USES, DF_INSN_EQ_USES or DF_INSN_UID_EQ_USES macros).
274*e4b17023SJohn Marino    The latter list are the list of references in REG_EQUAL or REG_EQUIV
275*e4b17023SJohn Marino    notes.  These macros produce a ref (or NULL), the rest of the list
276*e4b17023SJohn Marino    can be obtained by traversal of the NEXT_REF field (accessed by the
277*e4b17023SJohn Marino    DF_REF_NEXT_REF macro.)  There is no significance to the ordering of
278*e4b17023SJohn Marino    the uses or refs in an instruction.
279*e4b17023SJohn Marino 
280*e4b17023SJohn Marino 3) Each insn has a logical uid field (LUID) which is stored in the
281*e4b17023SJohn Marino    DF_INSN_INFO object for the insn.  The LUID field is accessed by
282*e4b17023SJohn Marino    the DF_INSN_INFO_LUID, DF_INSN_LUID, and DF_INSN_UID_LUID macros.
283*e4b17023SJohn Marino    When properly set, the LUID is an integer that numbers each insn in
284*e4b17023SJohn Marino    the basic block, in order from the start of the block.
285*e4b17023SJohn Marino    The numbers are only correct after a call to df_analyze.  They will
286*e4b17023SJohn Marino    rot after insns are added deleted or moved round.
287*e4b17023SJohn Marino 
288*e4b17023SJohn Marino ACCESSING REFS:
289*e4b17023SJohn Marino 
290*e4b17023SJohn Marino There are 4 ways to obtain access to refs:
291*e4b17023SJohn Marino 
292*e4b17023SJohn Marino 1) References are divided into two categories, REAL and ARTIFICIAL.
293*e4b17023SJohn Marino 
294*e4b17023SJohn Marino    REAL refs are associated with instructions.
295*e4b17023SJohn Marino 
296*e4b17023SJohn Marino    ARTIFICIAL refs are associated with basic blocks.  The heads of
297*e4b17023SJohn Marino    these lists can be accessed by calling df_get_artificial_defs or
298*e4b17023SJohn Marino    df_get_artificial_uses for the particular basic block.
299*e4b17023SJohn Marino 
300*e4b17023SJohn Marino    Artificial defs and uses occur both at the beginning and ends of blocks.
301*e4b17023SJohn Marino 
302*e4b17023SJohn Marino      For blocks that area at the destination of eh edges, the
303*e4b17023SJohn Marino      artificial uses and defs occur at the beginning.  The defs relate
304*e4b17023SJohn Marino      to the registers specified in EH_RETURN_DATA_REGNO and the uses
305*e4b17023SJohn Marino      relate to the registers specified in ED_USES.  Logically these
306*e4b17023SJohn Marino      defs and uses should really occur along the eh edge, but there is
307*e4b17023SJohn Marino      no convenient way to do this.  Artificial edges that occur at the
308*e4b17023SJohn Marino      beginning of the block have the DF_REF_AT_TOP flag set.
309*e4b17023SJohn Marino 
310*e4b17023SJohn Marino      Artificial uses occur at the end of all blocks.  These arise from
311*e4b17023SJohn Marino      the hard registers that are always live, such as the stack
312*e4b17023SJohn Marino      register and are put there to keep the code from forgetting about
313*e4b17023SJohn Marino      them.
314*e4b17023SJohn Marino 
315*e4b17023SJohn Marino      Artificial defs occur at the end of the entry block.  These arise
316*e4b17023SJohn Marino      from registers that are live at entry to the function.
317*e4b17023SJohn Marino 
318*e4b17023SJohn Marino 2) There are three types of refs: defs, uses and eq_uses.  (Eq_uses are
319*e4b17023SJohn Marino    uses that appear inside a REG_EQUAL or REG_EQUIV note.)
320*e4b17023SJohn Marino 
321*e4b17023SJohn Marino    All of the eq_uses, uses and defs associated with each pseudo or
322*e4b17023SJohn Marino    hard register may be linked in a bidirectional chain.  These are
323*e4b17023SJohn Marino    called reg-use or reg_def chains.  If the changeable flag
324*e4b17023SJohn Marino    DF_EQ_NOTES is set when the chains are built, the eq_uses will be
325*e4b17023SJohn Marino    treated like uses.  If it is not set they are ignored.
326*e4b17023SJohn Marino 
327*e4b17023SJohn Marino    The first use, eq_use or def for a register can be obtained using
328*e4b17023SJohn Marino    the DF_REG_USE_CHAIN, DF_REG_EQ_USE_CHAIN or DF_REG_DEF_CHAIN
329*e4b17023SJohn Marino    macros.  Subsequent uses for the same regno can be obtained by
330*e4b17023SJohn Marino    following the next_reg field of the ref.  The number of elements in
331*e4b17023SJohn Marino    each of the chains can be found by using the DF_REG_USE_COUNT,
332*e4b17023SJohn Marino    DF_REG_EQ_USE_COUNT or DF_REG_DEF_COUNT macros.
333*e4b17023SJohn Marino 
334*e4b17023SJohn Marino    In previous versions of this code, these chains were ordered.  It
335*e4b17023SJohn Marino    has not been practical to continue this practice.
336*e4b17023SJohn Marino 
337*e4b17023SJohn Marino 3) If def-use or use-def chains are built, these can be traversed to
338*e4b17023SJohn Marino    get to other refs.  If the flag DF_EQ_NOTES has been set, the chains
339*e4b17023SJohn Marino    include the eq_uses.  Otherwise these are ignored when building the
340*e4b17023SJohn Marino    chains.
341*e4b17023SJohn Marino 
342*e4b17023SJohn Marino 4) An array of all of the uses (and an array of all of the defs) can
343*e4b17023SJohn Marino    be built.  These arrays are indexed by the value in the id
344*e4b17023SJohn Marino    structure.  These arrays are only lazily kept up to date, and that
345*e4b17023SJohn Marino    process can be expensive.  To have these arrays built, call
346*e4b17023SJohn Marino    df_reorganize_defs or df_reorganize_uses.  If the flag DF_EQ_NOTES
347*e4b17023SJohn Marino    has been set the array will contain the eq_uses.  Otherwise these
348*e4b17023SJohn Marino    are ignored when building the array and assigning the ids.  Note
349*e4b17023SJohn Marino    that the values in the id field of a ref may change across calls to
350*e4b17023SJohn Marino    df_analyze or df_reorganize_defs or df_reorganize_uses.
351*e4b17023SJohn Marino 
352*e4b17023SJohn Marino    If the only use of this array is to find all of the refs, it is
353*e4b17023SJohn Marino    better to traverse all of the registers and then traverse all of
354*e4b17023SJohn Marino    reg-use or reg-def chains.
355*e4b17023SJohn Marino 
356*e4b17023SJohn Marino NOTES:
357*e4b17023SJohn Marino 
358*e4b17023SJohn Marino Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
359*e4b17023SJohn Marino both a use and a def.  These are both marked read/write to show that they
360*e4b17023SJohn Marino are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
361*e4b17023SJohn Marino will generate a use of reg 42 followed by a def of reg 42 (both marked
362*e4b17023SJohn Marino read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
363*e4b17023SJohn Marino generates a use of reg 41 then a def of reg 41 (both marked read/write),
364*e4b17023SJohn Marino even though reg 41 is decremented before it is used for the memory
365*e4b17023SJohn Marino address in this second example.
366*e4b17023SJohn Marino 
367*e4b17023SJohn Marino A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
368*e4b17023SJohn Marino for which the number of word_mode units covered by the outer mode is
369*e4b17023SJohn Marino smaller than that covered by the inner mode, invokes a read-modify-write
370*e4b17023SJohn Marino operation.  We generate both a use and a def and again mark them
371*e4b17023SJohn Marino read/write.
372*e4b17023SJohn Marino 
373*e4b17023SJohn Marino Paradoxical subreg writes do not leave a trace of the old content, so they
374*e4b17023SJohn Marino are write-only operations.
375*e4b17023SJohn Marino */
376*e4b17023SJohn Marino 
377*e4b17023SJohn Marino 
378*e4b17023SJohn Marino #include "config.h"
379*e4b17023SJohn Marino #include "system.h"
380*e4b17023SJohn Marino #include "coretypes.h"
381*e4b17023SJohn Marino #include "tm.h"
382*e4b17023SJohn Marino #include "rtl.h"
383*e4b17023SJohn Marino #include "tm_p.h"
384*e4b17023SJohn Marino #include "insn-config.h"
385*e4b17023SJohn Marino #include "recog.h"
386*e4b17023SJohn Marino #include "function.h"
387*e4b17023SJohn Marino #include "regs.h"
388*e4b17023SJohn Marino #include "output.h"
389*e4b17023SJohn Marino #include "alloc-pool.h"
390*e4b17023SJohn Marino #include "flags.h"
391*e4b17023SJohn Marino #include "hard-reg-set.h"
392*e4b17023SJohn Marino #include "basic-block.h"
393*e4b17023SJohn Marino #include "sbitmap.h"
394*e4b17023SJohn Marino #include "bitmap.h"
395*e4b17023SJohn Marino #include "timevar.h"
396*e4b17023SJohn Marino #include "df.h"
397*e4b17023SJohn Marino #include "tree-pass.h"
398*e4b17023SJohn Marino #include "params.h"
399*e4b17023SJohn Marino 
400*e4b17023SJohn Marino static void *df_get_bb_info (struct dataflow *, unsigned int);
401*e4b17023SJohn Marino static void df_set_bb_info (struct dataflow *, unsigned int, void *);
402*e4b17023SJohn Marino static void df_clear_bb_info (struct dataflow *, unsigned int);
403*e4b17023SJohn Marino #ifdef DF_DEBUG_CFG
404*e4b17023SJohn Marino static void df_set_clean_cfg (void);
405*e4b17023SJohn Marino #endif
406*e4b17023SJohn Marino 
407*e4b17023SJohn Marino /* An obstack for bitmap not related to specific dataflow problems.
408*e4b17023SJohn Marino    This obstack should e.g. be used for bitmaps with a short life time
409*e4b17023SJohn Marino    such as temporary bitmaps.  */
410*e4b17023SJohn Marino 
411*e4b17023SJohn Marino bitmap_obstack df_bitmap_obstack;
412*e4b17023SJohn Marino 
413*e4b17023SJohn Marino 
414*e4b17023SJohn Marino /*----------------------------------------------------------------------------
415*e4b17023SJohn Marino   Functions to create, destroy and manipulate an instance of df.
416*e4b17023SJohn Marino ----------------------------------------------------------------------------*/
417*e4b17023SJohn Marino 
418*e4b17023SJohn Marino struct df_d *df;
419*e4b17023SJohn Marino 
420*e4b17023SJohn Marino /* Add PROBLEM (and any dependent problems) to the DF instance.  */
421*e4b17023SJohn Marino 
422*e4b17023SJohn Marino void
df_add_problem(struct df_problem * problem)423*e4b17023SJohn Marino df_add_problem (struct df_problem *problem)
424*e4b17023SJohn Marino {
425*e4b17023SJohn Marino   struct dataflow *dflow;
426*e4b17023SJohn Marino   int i;
427*e4b17023SJohn Marino 
428*e4b17023SJohn Marino   /* First try to add the dependent problem. */
429*e4b17023SJohn Marino   if (problem->dependent_problem)
430*e4b17023SJohn Marino     df_add_problem (problem->dependent_problem);
431*e4b17023SJohn Marino 
432*e4b17023SJohn Marino   /* Check to see if this problem has already been defined.  If it
433*e4b17023SJohn Marino      has, just return that instance, if not, add it to the end of the
434*e4b17023SJohn Marino      vector.  */
435*e4b17023SJohn Marino   dflow = df->problems_by_index[problem->id];
436*e4b17023SJohn Marino   if (dflow)
437*e4b17023SJohn Marino     return;
438*e4b17023SJohn Marino 
439*e4b17023SJohn Marino   /* Make a new one and add it to the end.  */
440*e4b17023SJohn Marino   dflow = XCNEW (struct dataflow);
441*e4b17023SJohn Marino   dflow->problem = problem;
442*e4b17023SJohn Marino   dflow->computed = false;
443*e4b17023SJohn Marino   dflow->solutions_dirty = true;
444*e4b17023SJohn Marino   df->problems_by_index[dflow->problem->id] = dflow;
445*e4b17023SJohn Marino 
446*e4b17023SJohn Marino   /* Keep the defined problems ordered by index.  This solves the
447*e4b17023SJohn Marino      problem that RI will use the information from UREC if UREC has
448*e4b17023SJohn Marino      been defined, or from LIVE if LIVE is defined and otherwise LR.
449*e4b17023SJohn Marino      However for this to work, the computation of RI must be pushed
450*e4b17023SJohn Marino      after which ever of those problems is defined, but we do not
451*e4b17023SJohn Marino      require any of those except for LR to have actually been
452*e4b17023SJohn Marino      defined.  */
453*e4b17023SJohn Marino   df->num_problems_defined++;
454*e4b17023SJohn Marino   for (i = df->num_problems_defined - 2; i >= 0; i--)
455*e4b17023SJohn Marino     {
456*e4b17023SJohn Marino       if (problem->id < df->problems_in_order[i]->problem->id)
457*e4b17023SJohn Marino 	df->problems_in_order[i+1] = df->problems_in_order[i];
458*e4b17023SJohn Marino       else
459*e4b17023SJohn Marino 	{
460*e4b17023SJohn Marino 	  df->problems_in_order[i+1] = dflow;
461*e4b17023SJohn Marino 	  return;
462*e4b17023SJohn Marino 	}
463*e4b17023SJohn Marino     }
464*e4b17023SJohn Marino   df->problems_in_order[0] = dflow;
465*e4b17023SJohn Marino }
466*e4b17023SJohn Marino 
467*e4b17023SJohn Marino 
468*e4b17023SJohn Marino /* Set the MASK flags in the DFLOW problem.  The old flags are
469*e4b17023SJohn Marino    returned.  If a flag is not allowed to be changed this will fail if
470*e4b17023SJohn Marino    checking is enabled.  */
471*e4b17023SJohn Marino int
df_set_flags(int changeable_flags)472*e4b17023SJohn Marino df_set_flags (int changeable_flags)
473*e4b17023SJohn Marino {
474*e4b17023SJohn Marino   int old_flags = df->changeable_flags;
475*e4b17023SJohn Marino   df->changeable_flags |= changeable_flags;
476*e4b17023SJohn Marino   return old_flags;
477*e4b17023SJohn Marino }
478*e4b17023SJohn Marino 
479*e4b17023SJohn Marino 
480*e4b17023SJohn Marino /* Clear the MASK flags in the DFLOW problem.  The old flags are
481*e4b17023SJohn Marino    returned.  If a flag is not allowed to be changed this will fail if
482*e4b17023SJohn Marino    checking is enabled.  */
483*e4b17023SJohn Marino int
df_clear_flags(int changeable_flags)484*e4b17023SJohn Marino df_clear_flags (int changeable_flags)
485*e4b17023SJohn Marino {
486*e4b17023SJohn Marino   int old_flags = df->changeable_flags;
487*e4b17023SJohn Marino   df->changeable_flags &= ~changeable_flags;
488*e4b17023SJohn Marino   return old_flags;
489*e4b17023SJohn Marino }
490*e4b17023SJohn Marino 
491*e4b17023SJohn Marino 
492*e4b17023SJohn Marino /* Set the blocks that are to be considered for analysis.  If this is
493*e4b17023SJohn Marino    not called or is called with null, the entire function in
494*e4b17023SJohn Marino    analyzed.  */
495*e4b17023SJohn Marino 
496*e4b17023SJohn Marino void
df_set_blocks(bitmap blocks)497*e4b17023SJohn Marino df_set_blocks (bitmap blocks)
498*e4b17023SJohn Marino {
499*e4b17023SJohn Marino   if (blocks)
500*e4b17023SJohn Marino     {
501*e4b17023SJohn Marino       if (dump_file)
502*e4b17023SJohn Marino 	bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
503*e4b17023SJohn Marino       if (df->blocks_to_analyze)
504*e4b17023SJohn Marino 	{
505*e4b17023SJohn Marino 	  /* This block is called to change the focus from one subset
506*e4b17023SJohn Marino 	     to another.  */
507*e4b17023SJohn Marino 	  int p;
508*e4b17023SJohn Marino 	  bitmap_head diff;
509*e4b17023SJohn Marino 	  bitmap_initialize (&diff, &df_bitmap_obstack);
510*e4b17023SJohn Marino 	  bitmap_and_compl (&diff, df->blocks_to_analyze, blocks);
511*e4b17023SJohn Marino 	  for (p = 0; p < df->num_problems_defined; p++)
512*e4b17023SJohn Marino 	    {
513*e4b17023SJohn Marino 	      struct dataflow *dflow = df->problems_in_order[p];
514*e4b17023SJohn Marino 	      if (dflow->optional_p && dflow->problem->reset_fun)
515*e4b17023SJohn Marino 		dflow->problem->reset_fun (df->blocks_to_analyze);
516*e4b17023SJohn Marino 	      else if (dflow->problem->free_blocks_on_set_blocks)
517*e4b17023SJohn Marino 		{
518*e4b17023SJohn Marino 		  bitmap_iterator bi;
519*e4b17023SJohn Marino 		  unsigned int bb_index;
520*e4b17023SJohn Marino 
521*e4b17023SJohn Marino 		  EXECUTE_IF_SET_IN_BITMAP (&diff, 0, bb_index, bi)
522*e4b17023SJohn Marino 		    {
523*e4b17023SJohn Marino 		      basic_block bb = BASIC_BLOCK (bb_index);
524*e4b17023SJohn Marino 		      if (bb)
525*e4b17023SJohn Marino 			{
526*e4b17023SJohn Marino 			  void *bb_info = df_get_bb_info (dflow, bb_index);
527*e4b17023SJohn Marino 			  dflow->problem->free_bb_fun (bb, bb_info);
528*e4b17023SJohn Marino 			  df_clear_bb_info (dflow, bb_index);
529*e4b17023SJohn Marino 			}
530*e4b17023SJohn Marino 		    }
531*e4b17023SJohn Marino 		}
532*e4b17023SJohn Marino 	    }
533*e4b17023SJohn Marino 
534*e4b17023SJohn Marino 	   bitmap_clear (&diff);
535*e4b17023SJohn Marino 	}
536*e4b17023SJohn Marino       else
537*e4b17023SJohn Marino 	{
538*e4b17023SJohn Marino 	  /* This block of code is executed to change the focus from
539*e4b17023SJohn Marino 	     the entire function to a subset.  */
540*e4b17023SJohn Marino 	  bitmap_head blocks_to_reset;
541*e4b17023SJohn Marino 	  bool initialized = false;
542*e4b17023SJohn Marino 	  int p;
543*e4b17023SJohn Marino 	  for (p = 0; p < df->num_problems_defined; p++)
544*e4b17023SJohn Marino 	    {
545*e4b17023SJohn Marino 	      struct dataflow *dflow = df->problems_in_order[p];
546*e4b17023SJohn Marino 	      if (dflow->optional_p && dflow->problem->reset_fun)
547*e4b17023SJohn Marino 		{
548*e4b17023SJohn Marino 		  if (!initialized)
549*e4b17023SJohn Marino 		    {
550*e4b17023SJohn Marino 		      basic_block bb;
551*e4b17023SJohn Marino 		      bitmap_initialize (&blocks_to_reset, &df_bitmap_obstack);
552*e4b17023SJohn Marino 		      FOR_ALL_BB(bb)
553*e4b17023SJohn Marino 			{
554*e4b17023SJohn Marino 			  bitmap_set_bit (&blocks_to_reset, bb->index);
555*e4b17023SJohn Marino 			}
556*e4b17023SJohn Marino 		    }
557*e4b17023SJohn Marino 		  dflow->problem->reset_fun (&blocks_to_reset);
558*e4b17023SJohn Marino 		}
559*e4b17023SJohn Marino 	    }
560*e4b17023SJohn Marino 	  if (initialized)
561*e4b17023SJohn Marino 	    bitmap_clear (&blocks_to_reset);
562*e4b17023SJohn Marino 
563*e4b17023SJohn Marino 	  df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);
564*e4b17023SJohn Marino 	}
565*e4b17023SJohn Marino       bitmap_copy (df->blocks_to_analyze, blocks);
566*e4b17023SJohn Marino       df->analyze_subset = true;
567*e4b17023SJohn Marino     }
568*e4b17023SJohn Marino   else
569*e4b17023SJohn Marino     {
570*e4b17023SJohn Marino       /* This block is executed to reset the focus to the entire
571*e4b17023SJohn Marino 	 function.  */
572*e4b17023SJohn Marino       if (dump_file)
573*e4b17023SJohn Marino 	fprintf (dump_file, "clearing blocks_to_analyze\n");
574*e4b17023SJohn Marino       if (df->blocks_to_analyze)
575*e4b17023SJohn Marino 	{
576*e4b17023SJohn Marino 	  BITMAP_FREE (df->blocks_to_analyze);
577*e4b17023SJohn Marino 	  df->blocks_to_analyze = NULL;
578*e4b17023SJohn Marino 	}
579*e4b17023SJohn Marino       df->analyze_subset = false;
580*e4b17023SJohn Marino     }
581*e4b17023SJohn Marino 
582*e4b17023SJohn Marino   /* Setting the blocks causes the refs to be unorganized since only
583*e4b17023SJohn Marino      the refs in the blocks are seen.  */
584*e4b17023SJohn Marino   df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
585*e4b17023SJohn Marino   df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
586*e4b17023SJohn Marino   df_mark_solutions_dirty ();
587*e4b17023SJohn Marino }
588*e4b17023SJohn Marino 
589*e4b17023SJohn Marino 
590*e4b17023SJohn Marino /* Delete a DFLOW problem (and any problems that depend on this
591*e4b17023SJohn Marino    problem).  */
592*e4b17023SJohn Marino 
593*e4b17023SJohn Marino void
df_remove_problem(struct dataflow * dflow)594*e4b17023SJohn Marino df_remove_problem (struct dataflow *dflow)
595*e4b17023SJohn Marino {
596*e4b17023SJohn Marino   struct df_problem *problem;
597*e4b17023SJohn Marino   int i;
598*e4b17023SJohn Marino 
599*e4b17023SJohn Marino   if (!dflow)
600*e4b17023SJohn Marino     return;
601*e4b17023SJohn Marino 
602*e4b17023SJohn Marino   problem = dflow->problem;
603*e4b17023SJohn Marino   gcc_assert (problem->remove_problem_fun);
604*e4b17023SJohn Marino 
605*e4b17023SJohn Marino   /* Delete any problems that depended on this problem first.  */
606*e4b17023SJohn Marino   for (i = 0; i < df->num_problems_defined; i++)
607*e4b17023SJohn Marino     if (df->problems_in_order[i]->problem->dependent_problem == problem)
608*e4b17023SJohn Marino       df_remove_problem (df->problems_in_order[i]);
609*e4b17023SJohn Marino 
610*e4b17023SJohn Marino   /* Now remove this problem.  */
611*e4b17023SJohn Marino   for (i = 0; i < df->num_problems_defined; i++)
612*e4b17023SJohn Marino     if (df->problems_in_order[i] == dflow)
613*e4b17023SJohn Marino       {
614*e4b17023SJohn Marino 	int j;
615*e4b17023SJohn Marino 	for (j = i + 1; j < df->num_problems_defined; j++)
616*e4b17023SJohn Marino 	  df->problems_in_order[j-1] = df->problems_in_order[j];
617*e4b17023SJohn Marino 	df->problems_in_order[j-1] = NULL;
618*e4b17023SJohn Marino 	df->num_problems_defined--;
619*e4b17023SJohn Marino 	break;
620*e4b17023SJohn Marino       }
621*e4b17023SJohn Marino 
622*e4b17023SJohn Marino   (problem->remove_problem_fun) ();
623*e4b17023SJohn Marino   df->problems_by_index[problem->id] = NULL;
624*e4b17023SJohn Marino }
625*e4b17023SJohn Marino 
626*e4b17023SJohn Marino 
627*e4b17023SJohn Marino /* Remove all of the problems that are not permanent.  Scanning, LR
628*e4b17023SJohn Marino    and (at -O2 or higher) LIVE are permanent, the rest are removable.
629*e4b17023SJohn Marino    Also clear all of the changeable_flags.  */
630*e4b17023SJohn Marino 
631*e4b17023SJohn Marino void
df_finish_pass(bool verify ATTRIBUTE_UNUSED)632*e4b17023SJohn Marino df_finish_pass (bool verify ATTRIBUTE_UNUSED)
633*e4b17023SJohn Marino {
634*e4b17023SJohn Marino   int i;
635*e4b17023SJohn Marino   int removed = 0;
636*e4b17023SJohn Marino 
637*e4b17023SJohn Marino #ifdef ENABLE_DF_CHECKING
638*e4b17023SJohn Marino   int saved_flags;
639*e4b17023SJohn Marino #endif
640*e4b17023SJohn Marino 
641*e4b17023SJohn Marino   if (!df)
642*e4b17023SJohn Marino     return;
643*e4b17023SJohn Marino 
644*e4b17023SJohn Marino   df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
645*e4b17023SJohn Marino   df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
646*e4b17023SJohn Marino 
647*e4b17023SJohn Marino #ifdef ENABLE_DF_CHECKING
648*e4b17023SJohn Marino   saved_flags = df->changeable_flags;
649*e4b17023SJohn Marino #endif
650*e4b17023SJohn Marino 
651*e4b17023SJohn Marino   for (i = 0; i < df->num_problems_defined; i++)
652*e4b17023SJohn Marino     {
653*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[i];
654*e4b17023SJohn Marino       struct df_problem *problem = dflow->problem;
655*e4b17023SJohn Marino 
656*e4b17023SJohn Marino       if (dflow->optional_p)
657*e4b17023SJohn Marino 	{
658*e4b17023SJohn Marino 	  gcc_assert (problem->remove_problem_fun);
659*e4b17023SJohn Marino 	  (problem->remove_problem_fun) ();
660*e4b17023SJohn Marino 	  df->problems_in_order[i] = NULL;
661*e4b17023SJohn Marino 	  df->problems_by_index[problem->id] = NULL;
662*e4b17023SJohn Marino 	  removed++;
663*e4b17023SJohn Marino 	}
664*e4b17023SJohn Marino     }
665*e4b17023SJohn Marino   df->num_problems_defined -= removed;
666*e4b17023SJohn Marino 
667*e4b17023SJohn Marino   /* Clear all of the flags.  */
668*e4b17023SJohn Marino   df->changeable_flags = 0;
669*e4b17023SJohn Marino   df_process_deferred_rescans ();
670*e4b17023SJohn Marino 
671*e4b17023SJohn Marino   /* Set the focus back to the whole function.  */
672*e4b17023SJohn Marino   if (df->blocks_to_analyze)
673*e4b17023SJohn Marino     {
674*e4b17023SJohn Marino       BITMAP_FREE (df->blocks_to_analyze);
675*e4b17023SJohn Marino       df->blocks_to_analyze = NULL;
676*e4b17023SJohn Marino       df_mark_solutions_dirty ();
677*e4b17023SJohn Marino       df->analyze_subset = false;
678*e4b17023SJohn Marino     }
679*e4b17023SJohn Marino 
680*e4b17023SJohn Marino #ifdef ENABLE_DF_CHECKING
681*e4b17023SJohn Marino   /* Verification will fail in DF_NO_INSN_RESCAN.  */
682*e4b17023SJohn Marino   if (!(saved_flags & DF_NO_INSN_RESCAN))
683*e4b17023SJohn Marino     {
684*e4b17023SJohn Marino       df_lr_verify_transfer_functions ();
685*e4b17023SJohn Marino       if (df_live)
686*e4b17023SJohn Marino 	df_live_verify_transfer_functions ();
687*e4b17023SJohn Marino     }
688*e4b17023SJohn Marino 
689*e4b17023SJohn Marino #ifdef DF_DEBUG_CFG
690*e4b17023SJohn Marino   df_set_clean_cfg ();
691*e4b17023SJohn Marino #endif
692*e4b17023SJohn Marino #endif
693*e4b17023SJohn Marino 
694*e4b17023SJohn Marino #ifdef ENABLE_CHECKING
695*e4b17023SJohn Marino   if (verify)
696*e4b17023SJohn Marino     df->changeable_flags |= DF_VERIFY_SCHEDULED;
697*e4b17023SJohn Marino #endif
698*e4b17023SJohn Marino }
699*e4b17023SJohn Marino 
700*e4b17023SJohn Marino 
701*e4b17023SJohn Marino /* Set up the dataflow instance for the entire back end.  */
702*e4b17023SJohn Marino 
703*e4b17023SJohn Marino static unsigned int
rest_of_handle_df_initialize(void)704*e4b17023SJohn Marino rest_of_handle_df_initialize (void)
705*e4b17023SJohn Marino {
706*e4b17023SJohn Marino   gcc_assert (!df);
707*e4b17023SJohn Marino   df = XCNEW (struct df_d);
708*e4b17023SJohn Marino   df->changeable_flags = 0;
709*e4b17023SJohn Marino 
710*e4b17023SJohn Marino   bitmap_obstack_initialize (&df_bitmap_obstack);
711*e4b17023SJohn Marino 
712*e4b17023SJohn Marino   /* Set this to a conservative value.  Stack_ptr_mod will compute it
713*e4b17023SJohn Marino      correctly later.  */
714*e4b17023SJohn Marino   current_function_sp_is_unchanging = 0;
715*e4b17023SJohn Marino 
716*e4b17023SJohn Marino   df_scan_add_problem ();
717*e4b17023SJohn Marino   df_scan_alloc (NULL);
718*e4b17023SJohn Marino 
719*e4b17023SJohn Marino   /* These three problems are permanent.  */
720*e4b17023SJohn Marino   df_lr_add_problem ();
721*e4b17023SJohn Marino   if (optimize > 1)
722*e4b17023SJohn Marino     df_live_add_problem ();
723*e4b17023SJohn Marino 
724*e4b17023SJohn Marino   df->postorder = XNEWVEC (int, last_basic_block);
725*e4b17023SJohn Marino   df->postorder_inverted = XNEWVEC (int, last_basic_block);
726*e4b17023SJohn Marino   df->n_blocks = post_order_compute (df->postorder, true, true);
727*e4b17023SJohn Marino   df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
728*e4b17023SJohn Marino   gcc_assert (df->n_blocks == df->n_blocks_inverted);
729*e4b17023SJohn Marino 
730*e4b17023SJohn Marino   df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
731*e4b17023SJohn Marino   memset (df->hard_regs_live_count, 0,
732*e4b17023SJohn Marino 	  sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);
733*e4b17023SJohn Marino 
734*e4b17023SJohn Marino   df_hard_reg_init ();
735*e4b17023SJohn Marino   /* After reload, some ports add certain bits to regs_ever_live so
736*e4b17023SJohn Marino      this cannot be reset.  */
737*e4b17023SJohn Marino   df_compute_regs_ever_live (true);
738*e4b17023SJohn Marino   df_scan_blocks ();
739*e4b17023SJohn Marino   df_compute_regs_ever_live (false);
740*e4b17023SJohn Marino   return 0;
741*e4b17023SJohn Marino }
742*e4b17023SJohn Marino 
743*e4b17023SJohn Marino 
744*e4b17023SJohn Marino static bool
gate_opt(void)745*e4b17023SJohn Marino gate_opt (void)
746*e4b17023SJohn Marino {
747*e4b17023SJohn Marino   return optimize > 0;
748*e4b17023SJohn Marino }
749*e4b17023SJohn Marino 
750*e4b17023SJohn Marino 
751*e4b17023SJohn Marino struct rtl_opt_pass pass_df_initialize_opt =
752*e4b17023SJohn Marino {
753*e4b17023SJohn Marino  {
754*e4b17023SJohn Marino   RTL_PASS,
755*e4b17023SJohn Marino   "dfinit",                             /* name */
756*e4b17023SJohn Marino   gate_opt,                             /* gate */
757*e4b17023SJohn Marino   rest_of_handle_df_initialize,         /* execute */
758*e4b17023SJohn Marino   NULL,                                 /* sub */
759*e4b17023SJohn Marino   NULL,                                 /* next */
760*e4b17023SJohn Marino   0,                                    /* static_pass_number */
761*e4b17023SJohn Marino   TV_DF_SCAN,                           /* tv_id */
762*e4b17023SJohn Marino   0,                                    /* properties_required */
763*e4b17023SJohn Marino   0,                                    /* properties_provided */
764*e4b17023SJohn Marino   0,                                    /* properties_destroyed */
765*e4b17023SJohn Marino   0,                                    /* todo_flags_start */
766*e4b17023SJohn Marino   0                                     /* todo_flags_finish */
767*e4b17023SJohn Marino  }
768*e4b17023SJohn Marino };
769*e4b17023SJohn Marino 
770*e4b17023SJohn Marino 
771*e4b17023SJohn Marino static bool
gate_no_opt(void)772*e4b17023SJohn Marino gate_no_opt (void)
773*e4b17023SJohn Marino {
774*e4b17023SJohn Marino   return optimize == 0;
775*e4b17023SJohn Marino }
776*e4b17023SJohn Marino 
777*e4b17023SJohn Marino 
778*e4b17023SJohn Marino struct rtl_opt_pass pass_df_initialize_no_opt =
779*e4b17023SJohn Marino {
780*e4b17023SJohn Marino  {
781*e4b17023SJohn Marino   RTL_PASS,
782*e4b17023SJohn Marino   "no-opt dfinit",                      /* name */
783*e4b17023SJohn Marino   gate_no_opt,                          /* gate */
784*e4b17023SJohn Marino   rest_of_handle_df_initialize,         /* execute */
785*e4b17023SJohn Marino   NULL,                                 /* sub */
786*e4b17023SJohn Marino   NULL,                                 /* next */
787*e4b17023SJohn Marino   0,                                    /* static_pass_number */
788*e4b17023SJohn Marino   TV_DF_SCAN,                           /* tv_id */
789*e4b17023SJohn Marino   0,                                    /* properties_required */
790*e4b17023SJohn Marino   0,                                    /* properties_provided */
791*e4b17023SJohn Marino   0,                                    /* properties_destroyed */
792*e4b17023SJohn Marino   0,                                    /* todo_flags_start */
793*e4b17023SJohn Marino   0                                     /* todo_flags_finish */
794*e4b17023SJohn Marino  }
795*e4b17023SJohn Marino };
796*e4b17023SJohn Marino 
797*e4b17023SJohn Marino 
798*e4b17023SJohn Marino /* Free all the dataflow info and the DF structure.  This should be
799*e4b17023SJohn Marino    called from the df_finish macro which also NULLs the parm.  */
800*e4b17023SJohn Marino 
801*e4b17023SJohn Marino static unsigned int
rest_of_handle_df_finish(void)802*e4b17023SJohn Marino rest_of_handle_df_finish (void)
803*e4b17023SJohn Marino {
804*e4b17023SJohn Marino   int i;
805*e4b17023SJohn Marino 
806*e4b17023SJohn Marino   gcc_assert (df);
807*e4b17023SJohn Marino 
808*e4b17023SJohn Marino   for (i = 0; i < df->num_problems_defined; i++)
809*e4b17023SJohn Marino     {
810*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[i];
811*e4b17023SJohn Marino       dflow->problem->free_fun ();
812*e4b17023SJohn Marino     }
813*e4b17023SJohn Marino 
814*e4b17023SJohn Marino   free (df->postorder);
815*e4b17023SJohn Marino   free (df->postorder_inverted);
816*e4b17023SJohn Marino   free (df->hard_regs_live_count);
817*e4b17023SJohn Marino   free (df);
818*e4b17023SJohn Marino   df = NULL;
819*e4b17023SJohn Marino 
820*e4b17023SJohn Marino   bitmap_obstack_release (&df_bitmap_obstack);
821*e4b17023SJohn Marino   return 0;
822*e4b17023SJohn Marino }
823*e4b17023SJohn Marino 
824*e4b17023SJohn Marino 
825*e4b17023SJohn Marino struct rtl_opt_pass pass_df_finish =
826*e4b17023SJohn Marino {
827*e4b17023SJohn Marino  {
828*e4b17023SJohn Marino   RTL_PASS,
829*e4b17023SJohn Marino   "dfinish",                            /* name */
830*e4b17023SJohn Marino   NULL,					/* gate */
831*e4b17023SJohn Marino   rest_of_handle_df_finish,             /* execute */
832*e4b17023SJohn Marino   NULL,                                 /* sub */
833*e4b17023SJohn Marino   NULL,                                 /* next */
834*e4b17023SJohn Marino   0,                                    /* static_pass_number */
835*e4b17023SJohn Marino   TV_NONE,                              /* tv_id */
836*e4b17023SJohn Marino   0,                                    /* properties_required */
837*e4b17023SJohn Marino   0,                                    /* properties_provided */
838*e4b17023SJohn Marino   0,                                    /* properties_destroyed */
839*e4b17023SJohn Marino   0,                                    /* todo_flags_start */
840*e4b17023SJohn Marino   0                                     /* todo_flags_finish */
841*e4b17023SJohn Marino  }
842*e4b17023SJohn Marino };
843*e4b17023SJohn Marino 
844*e4b17023SJohn Marino 
845*e4b17023SJohn Marino 
846*e4b17023SJohn Marino 
847*e4b17023SJohn Marino 
848*e4b17023SJohn Marino /*----------------------------------------------------------------------------
849*e4b17023SJohn Marino    The general data flow analysis engine.
850*e4b17023SJohn Marino ----------------------------------------------------------------------------*/
851*e4b17023SJohn Marino 
852*e4b17023SJohn Marino /* Return time BB when it was visited for last time.  */
853*e4b17023SJohn Marino #define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux)
854*e4b17023SJohn Marino 
855*e4b17023SJohn Marino /* Helper function for df_worklist_dataflow.
856*e4b17023SJohn Marino    Propagate the dataflow forward.
857*e4b17023SJohn Marino    Given a BB_INDEX, do the dataflow propagation
858*e4b17023SJohn Marino    and set bits on for successors in PENDING
859*e4b17023SJohn Marino    if the out set of the dataflow has changed.
860*e4b17023SJohn Marino 
861*e4b17023SJohn Marino    AGE specify time when BB was visited last time.
862*e4b17023SJohn Marino    AGE of 0 means we are visiting for first time and need to
863*e4b17023SJohn Marino    compute transfer function to initialize datastructures.
864*e4b17023SJohn Marino    Otherwise we re-do transfer function only if something change
865*e4b17023SJohn Marino    while computing confluence functions.
866*e4b17023SJohn Marino    We need to compute confluence only of basic block that are younger
867*e4b17023SJohn Marino    then last visit of the BB.
868*e4b17023SJohn Marino 
869*e4b17023SJohn Marino    Return true if BB info has changed.  This is always the case
870*e4b17023SJohn Marino    in the first visit.  */
871*e4b17023SJohn Marino 
872*e4b17023SJohn Marino static bool
df_worklist_propagate_forward(struct dataflow * dataflow,unsigned bb_index,unsigned * bbindex_to_postorder,bitmap pending,sbitmap considered,ptrdiff_t age)873*e4b17023SJohn Marino df_worklist_propagate_forward (struct dataflow *dataflow,
874*e4b17023SJohn Marino                                unsigned bb_index,
875*e4b17023SJohn Marino                                unsigned *bbindex_to_postorder,
876*e4b17023SJohn Marino                                bitmap pending,
877*e4b17023SJohn Marino                                sbitmap considered,
878*e4b17023SJohn Marino 			       ptrdiff_t age)
879*e4b17023SJohn Marino {
880*e4b17023SJohn Marino   edge e;
881*e4b17023SJohn Marino   edge_iterator ei;
882*e4b17023SJohn Marino   basic_block bb = BASIC_BLOCK (bb_index);
883*e4b17023SJohn Marino   bool changed = !age;
884*e4b17023SJohn Marino 
885*e4b17023SJohn Marino   /*  Calculate <conf_op> of incoming edges.  */
886*e4b17023SJohn Marino   if (EDGE_COUNT (bb->preds) > 0)
887*e4b17023SJohn Marino     FOR_EACH_EDGE (e, ei, bb->preds)
888*e4b17023SJohn Marino       {
889*e4b17023SJohn Marino         if (age <= BB_LAST_CHANGE_AGE (e->src)
890*e4b17023SJohn Marino 	    && TEST_BIT (considered, e->src->index))
891*e4b17023SJohn Marino           changed |= dataflow->problem->con_fun_n (e);
892*e4b17023SJohn Marino       }
893*e4b17023SJohn Marino   else if (dataflow->problem->con_fun_0)
894*e4b17023SJohn Marino     dataflow->problem->con_fun_0 (bb);
895*e4b17023SJohn Marino 
896*e4b17023SJohn Marino   if (changed
897*e4b17023SJohn Marino       && dataflow->problem->trans_fun (bb_index))
898*e4b17023SJohn Marino     {
899*e4b17023SJohn Marino       /* The out set of this block has changed.
900*e4b17023SJohn Marino          Propagate to the outgoing blocks.  */
901*e4b17023SJohn Marino       FOR_EACH_EDGE (e, ei, bb->succs)
902*e4b17023SJohn Marino         {
903*e4b17023SJohn Marino           unsigned ob_index = e->dest->index;
904*e4b17023SJohn Marino 
905*e4b17023SJohn Marino           if (TEST_BIT (considered, ob_index))
906*e4b17023SJohn Marino             bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
907*e4b17023SJohn Marino         }
908*e4b17023SJohn Marino       return true;
909*e4b17023SJohn Marino     }
910*e4b17023SJohn Marino   return false;
911*e4b17023SJohn Marino }
912*e4b17023SJohn Marino 
913*e4b17023SJohn Marino 
914*e4b17023SJohn Marino /* Helper function for df_worklist_dataflow.
915*e4b17023SJohn Marino    Propagate the dataflow backward.  */
916*e4b17023SJohn Marino 
917*e4b17023SJohn Marino static bool
df_worklist_propagate_backward(struct dataflow * dataflow,unsigned bb_index,unsigned * bbindex_to_postorder,bitmap pending,sbitmap considered,ptrdiff_t age)918*e4b17023SJohn Marino df_worklist_propagate_backward (struct dataflow *dataflow,
919*e4b17023SJohn Marino                                 unsigned bb_index,
920*e4b17023SJohn Marino                                 unsigned *bbindex_to_postorder,
921*e4b17023SJohn Marino                                 bitmap pending,
922*e4b17023SJohn Marino                                 sbitmap considered,
923*e4b17023SJohn Marino 			        ptrdiff_t age)
924*e4b17023SJohn Marino {
925*e4b17023SJohn Marino   edge e;
926*e4b17023SJohn Marino   edge_iterator ei;
927*e4b17023SJohn Marino   basic_block bb = BASIC_BLOCK (bb_index);
928*e4b17023SJohn Marino   bool changed = !age;
929*e4b17023SJohn Marino 
930*e4b17023SJohn Marino   /*  Calculate <conf_op> of incoming edges.  */
931*e4b17023SJohn Marino   if (EDGE_COUNT (bb->succs) > 0)
932*e4b17023SJohn Marino     FOR_EACH_EDGE (e, ei, bb->succs)
933*e4b17023SJohn Marino       {
934*e4b17023SJohn Marino         if (age <= BB_LAST_CHANGE_AGE (e->dest)
935*e4b17023SJohn Marino 	    && TEST_BIT (considered, e->dest->index))
936*e4b17023SJohn Marino           changed |= dataflow->problem->con_fun_n (e);
937*e4b17023SJohn Marino       }
938*e4b17023SJohn Marino   else if (dataflow->problem->con_fun_0)
939*e4b17023SJohn Marino     dataflow->problem->con_fun_0 (bb);
940*e4b17023SJohn Marino 
941*e4b17023SJohn Marino   if (changed
942*e4b17023SJohn Marino       && dataflow->problem->trans_fun (bb_index))
943*e4b17023SJohn Marino     {
944*e4b17023SJohn Marino       /* The out set of this block has changed.
945*e4b17023SJohn Marino          Propagate to the outgoing blocks.  */
946*e4b17023SJohn Marino       FOR_EACH_EDGE (e, ei, bb->preds)
947*e4b17023SJohn Marino         {
948*e4b17023SJohn Marino           unsigned ob_index = e->src->index;
949*e4b17023SJohn Marino 
950*e4b17023SJohn Marino           if (TEST_BIT (considered, ob_index))
951*e4b17023SJohn Marino             bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
952*e4b17023SJohn Marino         }
953*e4b17023SJohn Marino       return true;
954*e4b17023SJohn Marino     }
955*e4b17023SJohn Marino   return false;
956*e4b17023SJohn Marino }
957*e4b17023SJohn Marino 
958*e4b17023SJohn Marino /* Main dataflow solver loop.
959*e4b17023SJohn Marino 
960*e4b17023SJohn Marino    DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we
961*e4b17023SJohn Marino    need to visit.
962*e4b17023SJohn Marino    BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and
963*e4b17023SJohn Marino    BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder possition.
964*e4b17023SJohn Marino    PENDING will be freed.
965*e4b17023SJohn Marino 
966*e4b17023SJohn Marino    The worklists are bitmaps indexed by postorder positions.
967*e4b17023SJohn Marino 
968*e4b17023SJohn Marino    The function implements standard algorithm for dataflow solving with two
969*e4b17023SJohn Marino    worklists (we are processing WORKLIST and storing new BBs to visit in
970*e4b17023SJohn Marino    PENDING).
971*e4b17023SJohn Marino 
972*e4b17023SJohn Marino    As an optimization we maintain ages when BB was changed (stored in bb->aux)
973*e4b17023SJohn Marino    and when it was last visited (stored in last_visit_age).  This avoids need
974*e4b17023SJohn Marino    to re-do confluence function for edges to basic blocks whose source
975*e4b17023SJohn Marino    did not change since destination was visited last time.  */
976*e4b17023SJohn Marino 
977*e4b17023SJohn Marino static void
df_worklist_dataflow_doublequeue(struct dataflow * dataflow,bitmap pending,sbitmap considered,int * blocks_in_postorder,unsigned * bbindex_to_postorder,int n_blocks)978*e4b17023SJohn Marino df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
979*e4b17023SJohn Marino 			  	  bitmap pending,
980*e4b17023SJohn Marino                                   sbitmap considered,
981*e4b17023SJohn Marino                                   int *blocks_in_postorder,
982*e4b17023SJohn Marino 				  unsigned *bbindex_to_postorder,
983*e4b17023SJohn Marino 				  int n_blocks)
984*e4b17023SJohn Marino {
985*e4b17023SJohn Marino   enum df_flow_dir dir = dataflow->problem->dir;
986*e4b17023SJohn Marino   int dcount = 0;
987*e4b17023SJohn Marino   bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
988*e4b17023SJohn Marino   int age = 0;
989*e4b17023SJohn Marino   bool changed;
990*e4b17023SJohn Marino   VEC(int, heap) *last_visit_age = NULL;
991*e4b17023SJohn Marino   int prev_age;
992*e4b17023SJohn Marino   basic_block bb;
993*e4b17023SJohn Marino   int i;
994*e4b17023SJohn Marino 
995*e4b17023SJohn Marino   VEC_safe_grow_cleared (int, heap, last_visit_age, n_blocks);
996*e4b17023SJohn Marino 
997*e4b17023SJohn Marino   /* Double-queueing. Worklist is for the current iteration,
998*e4b17023SJohn Marino      and pending is for the next. */
999*e4b17023SJohn Marino   while (!bitmap_empty_p (pending))
1000*e4b17023SJohn Marino     {
1001*e4b17023SJohn Marino       bitmap_iterator bi;
1002*e4b17023SJohn Marino       unsigned int index;
1003*e4b17023SJohn Marino 
1004*e4b17023SJohn Marino       /* Swap pending and worklist. */
1005*e4b17023SJohn Marino       bitmap temp = worklist;
1006*e4b17023SJohn Marino       worklist = pending;
1007*e4b17023SJohn Marino       pending = temp;
1008*e4b17023SJohn Marino 
1009*e4b17023SJohn Marino       EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi)
1010*e4b17023SJohn Marino 	{
1011*e4b17023SJohn Marino 	  unsigned bb_index;
1012*e4b17023SJohn Marino 	  dcount++;
1013*e4b17023SJohn Marino 
1014*e4b17023SJohn Marino 	  bitmap_clear_bit (pending, index);
1015*e4b17023SJohn Marino 	  bb_index = blocks_in_postorder[index];
1016*e4b17023SJohn Marino 	  bb = BASIC_BLOCK (bb_index);
1017*e4b17023SJohn Marino 	  prev_age = VEC_index (int, last_visit_age, index);
1018*e4b17023SJohn Marino 	  if (dir == DF_FORWARD)
1019*e4b17023SJohn Marino 	    changed = df_worklist_propagate_forward (dataflow, bb_index,
1020*e4b17023SJohn Marino 						     bbindex_to_postorder,
1021*e4b17023SJohn Marino 						     pending, considered,
1022*e4b17023SJohn Marino 						     prev_age);
1023*e4b17023SJohn Marino 	  else
1024*e4b17023SJohn Marino 	    changed = df_worklist_propagate_backward (dataflow, bb_index,
1025*e4b17023SJohn Marino 						      bbindex_to_postorder,
1026*e4b17023SJohn Marino 						      pending, considered,
1027*e4b17023SJohn Marino 						      prev_age);
1028*e4b17023SJohn Marino 	  VEC_replace (int, last_visit_age, index, ++age);
1029*e4b17023SJohn Marino 	  if (changed)
1030*e4b17023SJohn Marino 	    bb->aux = (void *)(ptrdiff_t)age;
1031*e4b17023SJohn Marino 	}
1032*e4b17023SJohn Marino       bitmap_clear (worklist);
1033*e4b17023SJohn Marino     }
1034*e4b17023SJohn Marino   for (i = 0; i < n_blocks; i++)
1035*e4b17023SJohn Marino     BASIC_BLOCK (blocks_in_postorder[i])->aux = NULL;
1036*e4b17023SJohn Marino 
1037*e4b17023SJohn Marino   BITMAP_FREE (worklist);
1038*e4b17023SJohn Marino   BITMAP_FREE (pending);
1039*e4b17023SJohn Marino   VEC_free (int, heap, last_visit_age);
1040*e4b17023SJohn Marino 
1041*e4b17023SJohn Marino   /* Dump statistics. */
1042*e4b17023SJohn Marino   if (dump_file)
1043*e4b17023SJohn Marino     fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
1044*e4b17023SJohn Marino 	     "n_basic_blocks %d n_edges %d"
1045*e4b17023SJohn Marino 	     " count %d (%5.2g)\n",
1046*e4b17023SJohn Marino 	     n_basic_blocks, n_edges,
1047*e4b17023SJohn Marino 	     dcount, dcount / (float)n_basic_blocks);
1048*e4b17023SJohn Marino }
1049*e4b17023SJohn Marino 
1050*e4b17023SJohn Marino /* Worklist-based dataflow solver. It uses sbitmap as a worklist,
1051*e4b17023SJohn Marino    with "n"-th bit representing the n-th block in the reverse-postorder order.
1052*e4b17023SJohn Marino    The solver is a double-queue algorithm similar to the "double stack" solver
1053*e4b17023SJohn Marino    from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
1054*e4b17023SJohn Marino    The only significant difference is that the worklist in this implementation
1055*e4b17023SJohn Marino    is always sorted in RPO of the CFG visiting direction.  */
1056*e4b17023SJohn Marino 
1057*e4b17023SJohn Marino void
df_worklist_dataflow(struct dataflow * dataflow,bitmap blocks_to_consider,int * blocks_in_postorder,int n_blocks)1058*e4b17023SJohn Marino df_worklist_dataflow (struct dataflow *dataflow,
1059*e4b17023SJohn Marino                       bitmap blocks_to_consider,
1060*e4b17023SJohn Marino                       int *blocks_in_postorder,
1061*e4b17023SJohn Marino                       int n_blocks)
1062*e4b17023SJohn Marino {
1063*e4b17023SJohn Marino   bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
1064*e4b17023SJohn Marino   sbitmap considered = sbitmap_alloc (last_basic_block);
1065*e4b17023SJohn Marino   bitmap_iterator bi;
1066*e4b17023SJohn Marino   unsigned int *bbindex_to_postorder;
1067*e4b17023SJohn Marino   int i;
1068*e4b17023SJohn Marino   unsigned int index;
1069*e4b17023SJohn Marino   enum df_flow_dir dir = dataflow->problem->dir;
1070*e4b17023SJohn Marino 
1071*e4b17023SJohn Marino   gcc_assert (dir != DF_NONE);
1072*e4b17023SJohn Marino 
1073*e4b17023SJohn Marino   /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder.  */
1074*e4b17023SJohn Marino   bbindex_to_postorder =
1075*e4b17023SJohn Marino     (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
1076*e4b17023SJohn Marino 
1077*e4b17023SJohn Marino   /* Initialize the array to an out-of-bound value.  */
1078*e4b17023SJohn Marino   for (i = 0; i < last_basic_block; i++)
1079*e4b17023SJohn Marino     bbindex_to_postorder[i] = last_basic_block;
1080*e4b17023SJohn Marino 
1081*e4b17023SJohn Marino   /* Initialize the considered map.  */
1082*e4b17023SJohn Marino   sbitmap_zero (considered);
1083*e4b17023SJohn Marino   EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
1084*e4b17023SJohn Marino     {
1085*e4b17023SJohn Marino       SET_BIT (considered, index);
1086*e4b17023SJohn Marino     }
1087*e4b17023SJohn Marino 
1088*e4b17023SJohn Marino   /* Initialize the mapping of block index to postorder.  */
1089*e4b17023SJohn Marino   for (i = 0; i < n_blocks; i++)
1090*e4b17023SJohn Marino     {
1091*e4b17023SJohn Marino       bbindex_to_postorder[blocks_in_postorder[i]] = i;
1092*e4b17023SJohn Marino       /* Add all blocks to the worklist.  */
1093*e4b17023SJohn Marino       bitmap_set_bit (pending, i);
1094*e4b17023SJohn Marino     }
1095*e4b17023SJohn Marino 
1096*e4b17023SJohn Marino   /* Initialize the problem. */
1097*e4b17023SJohn Marino   if (dataflow->problem->init_fun)
1098*e4b17023SJohn Marino     dataflow->problem->init_fun (blocks_to_consider);
1099*e4b17023SJohn Marino 
1100*e4b17023SJohn Marino   /* Solve it.  */
1101*e4b17023SJohn Marino   df_worklist_dataflow_doublequeue (dataflow, pending, considered,
1102*e4b17023SJohn Marino 				    blocks_in_postorder,
1103*e4b17023SJohn Marino 				    bbindex_to_postorder,
1104*e4b17023SJohn Marino 				    n_blocks);
1105*e4b17023SJohn Marino   sbitmap_free (considered);
1106*e4b17023SJohn Marino   free (bbindex_to_postorder);
1107*e4b17023SJohn Marino }
1108*e4b17023SJohn Marino 
1109*e4b17023SJohn Marino 
1110*e4b17023SJohn Marino /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1111*e4b17023SJohn Marino    the order of the remaining entries.  Returns the length of the resulting
1112*e4b17023SJohn Marino    list.  */
1113*e4b17023SJohn Marino 
1114*e4b17023SJohn Marino static unsigned
df_prune_to_subcfg(int list[],unsigned len,bitmap blocks)1115*e4b17023SJohn Marino df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
1116*e4b17023SJohn Marino {
1117*e4b17023SJohn Marino   unsigned act, last;
1118*e4b17023SJohn Marino 
1119*e4b17023SJohn Marino   for (act = 0, last = 0; act < len; act++)
1120*e4b17023SJohn Marino     if (bitmap_bit_p (blocks, list[act]))
1121*e4b17023SJohn Marino       list[last++] = list[act];
1122*e4b17023SJohn Marino 
1123*e4b17023SJohn Marino   return last;
1124*e4b17023SJohn Marino }
1125*e4b17023SJohn Marino 
1126*e4b17023SJohn Marino 
1127*e4b17023SJohn Marino /* Execute dataflow analysis on a single dataflow problem.
1128*e4b17023SJohn Marino 
1129*e4b17023SJohn Marino    BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1130*e4b17023SJohn Marino    examined or will be computed.  For calls from DF_ANALYZE, this is
1131*e4b17023SJohn Marino    the set of blocks that has been passed to DF_SET_BLOCKS.
1132*e4b17023SJohn Marino */
1133*e4b17023SJohn Marino 
1134*e4b17023SJohn Marino void
df_analyze_problem(struct dataflow * dflow,bitmap blocks_to_consider,int * postorder,int n_blocks)1135*e4b17023SJohn Marino df_analyze_problem (struct dataflow *dflow,
1136*e4b17023SJohn Marino 		    bitmap blocks_to_consider,
1137*e4b17023SJohn Marino 		    int *postorder, int n_blocks)
1138*e4b17023SJohn Marino {
1139*e4b17023SJohn Marino   timevar_push (dflow->problem->tv_id);
1140*e4b17023SJohn Marino 
1141*e4b17023SJohn Marino   /* (Re)Allocate the datastructures necessary to solve the problem.  */
1142*e4b17023SJohn Marino   if (dflow->problem->alloc_fun)
1143*e4b17023SJohn Marino     dflow->problem->alloc_fun (blocks_to_consider);
1144*e4b17023SJohn Marino 
1145*e4b17023SJohn Marino #ifdef ENABLE_DF_CHECKING
1146*e4b17023SJohn Marino   if (dflow->problem->verify_start_fun)
1147*e4b17023SJohn Marino     dflow->problem->verify_start_fun ();
1148*e4b17023SJohn Marino #endif
1149*e4b17023SJohn Marino 
1150*e4b17023SJohn Marino   /* Set up the problem and compute the local information.  */
1151*e4b17023SJohn Marino   if (dflow->problem->local_compute_fun)
1152*e4b17023SJohn Marino     dflow->problem->local_compute_fun (blocks_to_consider);
1153*e4b17023SJohn Marino 
1154*e4b17023SJohn Marino   /* Solve the equations.  */
1155*e4b17023SJohn Marino   if (dflow->problem->dataflow_fun)
1156*e4b17023SJohn Marino     dflow->problem->dataflow_fun (dflow, blocks_to_consider,
1157*e4b17023SJohn Marino 				  postorder, n_blocks);
1158*e4b17023SJohn Marino 
1159*e4b17023SJohn Marino   /* Massage the solution.  */
1160*e4b17023SJohn Marino   if (dflow->problem->finalize_fun)
1161*e4b17023SJohn Marino     dflow->problem->finalize_fun (blocks_to_consider);
1162*e4b17023SJohn Marino 
1163*e4b17023SJohn Marino #ifdef ENABLE_DF_CHECKING
1164*e4b17023SJohn Marino   if (dflow->problem->verify_end_fun)
1165*e4b17023SJohn Marino     dflow->problem->verify_end_fun ();
1166*e4b17023SJohn Marino #endif
1167*e4b17023SJohn Marino 
1168*e4b17023SJohn Marino   timevar_pop (dflow->problem->tv_id);
1169*e4b17023SJohn Marino 
1170*e4b17023SJohn Marino   dflow->computed = true;
1171*e4b17023SJohn Marino }
1172*e4b17023SJohn Marino 
1173*e4b17023SJohn Marino 
1174*e4b17023SJohn Marino /* Analyze dataflow info for the basic blocks specified by the bitmap
1175*e4b17023SJohn Marino    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
1176*e4b17023SJohn Marino 
1177*e4b17023SJohn Marino void
df_analyze(void)1178*e4b17023SJohn Marino df_analyze (void)
1179*e4b17023SJohn Marino {
1180*e4b17023SJohn Marino   bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
1181*e4b17023SJohn Marino   bool everything;
1182*e4b17023SJohn Marino   int i;
1183*e4b17023SJohn Marino 
1184*e4b17023SJohn Marino   free (df->postorder);
1185*e4b17023SJohn Marino   free (df->postorder_inverted);
1186*e4b17023SJohn Marino   df->postorder = XNEWVEC (int, last_basic_block);
1187*e4b17023SJohn Marino   df->postorder_inverted = XNEWVEC (int, last_basic_block);
1188*e4b17023SJohn Marino   df->n_blocks = post_order_compute (df->postorder, true, true);
1189*e4b17023SJohn Marino   df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
1190*e4b17023SJohn Marino 
1191*e4b17023SJohn Marino   /* These should be the same.  */
1192*e4b17023SJohn Marino   gcc_assert (df->n_blocks == df->n_blocks_inverted);
1193*e4b17023SJohn Marino 
1194*e4b17023SJohn Marino   /* We need to do this before the df_verify_all because this is
1195*e4b17023SJohn Marino      not kept incrementally up to date.  */
1196*e4b17023SJohn Marino   df_compute_regs_ever_live (false);
1197*e4b17023SJohn Marino   df_process_deferred_rescans ();
1198*e4b17023SJohn Marino 
1199*e4b17023SJohn Marino   if (dump_file)
1200*e4b17023SJohn Marino     fprintf (dump_file, "df_analyze called\n");
1201*e4b17023SJohn Marino 
1202*e4b17023SJohn Marino #ifndef ENABLE_DF_CHECKING
1203*e4b17023SJohn Marino   if (df->changeable_flags & DF_VERIFY_SCHEDULED)
1204*e4b17023SJohn Marino #endif
1205*e4b17023SJohn Marino     df_verify ();
1206*e4b17023SJohn Marino 
1207*e4b17023SJohn Marino   for (i = 0; i < df->n_blocks; i++)
1208*e4b17023SJohn Marino     bitmap_set_bit (current_all_blocks, df->postorder[i]);
1209*e4b17023SJohn Marino 
1210*e4b17023SJohn Marino #ifdef ENABLE_CHECKING
1211*e4b17023SJohn Marino   /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1212*e4b17023SJohn Marino      the ENTRY block.  */
1213*e4b17023SJohn Marino   for (i = 0; i < df->n_blocks_inverted; i++)
1214*e4b17023SJohn Marino     gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
1215*e4b17023SJohn Marino #endif
1216*e4b17023SJohn Marino 
1217*e4b17023SJohn Marino   /* Make sure that we have pruned any unreachable blocks from these
1218*e4b17023SJohn Marino      sets.  */
1219*e4b17023SJohn Marino   if (df->analyze_subset)
1220*e4b17023SJohn Marino     {
1221*e4b17023SJohn Marino       everything = false;
1222*e4b17023SJohn Marino       bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
1223*e4b17023SJohn Marino       df->n_blocks = df_prune_to_subcfg (df->postorder,
1224*e4b17023SJohn Marino 					 df->n_blocks, df->blocks_to_analyze);
1225*e4b17023SJohn Marino       df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
1226*e4b17023SJohn Marino 			                          df->n_blocks_inverted,
1227*e4b17023SJohn Marino                                                   df->blocks_to_analyze);
1228*e4b17023SJohn Marino       BITMAP_FREE (current_all_blocks);
1229*e4b17023SJohn Marino     }
1230*e4b17023SJohn Marino   else
1231*e4b17023SJohn Marino     {
1232*e4b17023SJohn Marino       everything = true;
1233*e4b17023SJohn Marino       df->blocks_to_analyze = current_all_blocks;
1234*e4b17023SJohn Marino       current_all_blocks = NULL;
1235*e4b17023SJohn Marino     }
1236*e4b17023SJohn Marino 
1237*e4b17023SJohn Marino   /* Skip over the DF_SCAN problem. */
1238*e4b17023SJohn Marino   for (i = 1; i < df->num_problems_defined; i++)
1239*e4b17023SJohn Marino     {
1240*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[i];
1241*e4b17023SJohn Marino       if (dflow->solutions_dirty)
1242*e4b17023SJohn Marino         {
1243*e4b17023SJohn Marino           if (dflow->problem->dir == DF_FORWARD)
1244*e4b17023SJohn Marino             df_analyze_problem (dflow,
1245*e4b17023SJohn Marino                                 df->blocks_to_analyze,
1246*e4b17023SJohn Marino                                 df->postorder_inverted,
1247*e4b17023SJohn Marino                                 df->n_blocks_inverted);
1248*e4b17023SJohn Marino           else
1249*e4b17023SJohn Marino             df_analyze_problem (dflow,
1250*e4b17023SJohn Marino                                 df->blocks_to_analyze,
1251*e4b17023SJohn Marino                                 df->postorder,
1252*e4b17023SJohn Marino                                 df->n_blocks);
1253*e4b17023SJohn Marino         }
1254*e4b17023SJohn Marino     }
1255*e4b17023SJohn Marino 
1256*e4b17023SJohn Marino   if (everything)
1257*e4b17023SJohn Marino     {
1258*e4b17023SJohn Marino       BITMAP_FREE (df->blocks_to_analyze);
1259*e4b17023SJohn Marino       df->blocks_to_analyze = NULL;
1260*e4b17023SJohn Marino     }
1261*e4b17023SJohn Marino 
1262*e4b17023SJohn Marino #ifdef DF_DEBUG_CFG
1263*e4b17023SJohn Marino   df_set_clean_cfg ();
1264*e4b17023SJohn Marino #endif
1265*e4b17023SJohn Marino }
1266*e4b17023SJohn Marino 
1267*e4b17023SJohn Marino 
1268*e4b17023SJohn Marino /* Return the number of basic blocks from the last call to df_analyze.  */
1269*e4b17023SJohn Marino 
1270*e4b17023SJohn Marino int
df_get_n_blocks(enum df_flow_dir dir)1271*e4b17023SJohn Marino df_get_n_blocks (enum df_flow_dir dir)
1272*e4b17023SJohn Marino {
1273*e4b17023SJohn Marino   gcc_assert (dir != DF_NONE);
1274*e4b17023SJohn Marino 
1275*e4b17023SJohn Marino   if (dir == DF_FORWARD)
1276*e4b17023SJohn Marino     {
1277*e4b17023SJohn Marino       gcc_assert (df->postorder_inverted);
1278*e4b17023SJohn Marino       return df->n_blocks_inverted;
1279*e4b17023SJohn Marino     }
1280*e4b17023SJohn Marino 
1281*e4b17023SJohn Marino   gcc_assert (df->postorder);
1282*e4b17023SJohn Marino   return df->n_blocks;
1283*e4b17023SJohn Marino }
1284*e4b17023SJohn Marino 
1285*e4b17023SJohn Marino 
1286*e4b17023SJohn Marino /* Return a pointer to the array of basic blocks in the reverse postorder.
1287*e4b17023SJohn Marino    Depending on the direction of the dataflow problem,
1288*e4b17023SJohn Marino    it returns either the usual reverse postorder array
1289*e4b17023SJohn Marino    or the reverse postorder of inverted traversal. */
1290*e4b17023SJohn Marino int *
df_get_postorder(enum df_flow_dir dir)1291*e4b17023SJohn Marino df_get_postorder (enum df_flow_dir dir)
1292*e4b17023SJohn Marino {
1293*e4b17023SJohn Marino   gcc_assert (dir != DF_NONE);
1294*e4b17023SJohn Marino 
1295*e4b17023SJohn Marino   if (dir == DF_FORWARD)
1296*e4b17023SJohn Marino     {
1297*e4b17023SJohn Marino       gcc_assert (df->postorder_inverted);
1298*e4b17023SJohn Marino       return df->postorder_inverted;
1299*e4b17023SJohn Marino     }
1300*e4b17023SJohn Marino   gcc_assert (df->postorder);
1301*e4b17023SJohn Marino   return df->postorder;
1302*e4b17023SJohn Marino }
1303*e4b17023SJohn Marino 
1304*e4b17023SJohn Marino static struct df_problem user_problem;
1305*e4b17023SJohn Marino static struct dataflow user_dflow;
1306*e4b17023SJohn Marino 
1307*e4b17023SJohn Marino /* Interface for calling iterative dataflow with user defined
1308*e4b17023SJohn Marino    confluence and transfer functions.  All that is necessary is to
1309*e4b17023SJohn Marino    supply DIR, a direction, CONF_FUN_0, a confluence function for
1310*e4b17023SJohn Marino    blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1311*e4b17023SJohn Marino    confluence function, TRANS_FUN, the basic block transfer function,
1312*e4b17023SJohn Marino    and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1313*e4b17023SJohn Marino    postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1314*e4b17023SJohn Marino 
1315*e4b17023SJohn Marino void
df_simple_dataflow(enum df_flow_dir dir,df_init_function init_fun,df_confluence_function_0 con_fun_0,df_confluence_function_n con_fun_n,df_transfer_function trans_fun,bitmap blocks,int * postorder,int n_blocks)1316*e4b17023SJohn Marino df_simple_dataflow (enum df_flow_dir dir,
1317*e4b17023SJohn Marino 		    df_init_function init_fun,
1318*e4b17023SJohn Marino 		    df_confluence_function_0 con_fun_0,
1319*e4b17023SJohn Marino 		    df_confluence_function_n con_fun_n,
1320*e4b17023SJohn Marino 		    df_transfer_function trans_fun,
1321*e4b17023SJohn Marino 		    bitmap blocks, int * postorder, int n_blocks)
1322*e4b17023SJohn Marino {
1323*e4b17023SJohn Marino   memset (&user_problem, 0, sizeof (struct df_problem));
1324*e4b17023SJohn Marino   user_problem.dir = dir;
1325*e4b17023SJohn Marino   user_problem.init_fun = init_fun;
1326*e4b17023SJohn Marino   user_problem.con_fun_0 = con_fun_0;
1327*e4b17023SJohn Marino   user_problem.con_fun_n = con_fun_n;
1328*e4b17023SJohn Marino   user_problem.trans_fun = trans_fun;
1329*e4b17023SJohn Marino   user_dflow.problem = &user_problem;
1330*e4b17023SJohn Marino   df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
1331*e4b17023SJohn Marino }
1332*e4b17023SJohn Marino 
1333*e4b17023SJohn Marino 
1334*e4b17023SJohn Marino 
1335*e4b17023SJohn Marino /*----------------------------------------------------------------------------
1336*e4b17023SJohn Marino    Functions to support limited incremental change.
1337*e4b17023SJohn Marino ----------------------------------------------------------------------------*/
1338*e4b17023SJohn Marino 
1339*e4b17023SJohn Marino 
1340*e4b17023SJohn Marino /* Get basic block info.  */
1341*e4b17023SJohn Marino 
1342*e4b17023SJohn Marino static void *
df_get_bb_info(struct dataflow * dflow,unsigned int index)1343*e4b17023SJohn Marino df_get_bb_info (struct dataflow *dflow, unsigned int index)
1344*e4b17023SJohn Marino {
1345*e4b17023SJohn Marino   if (dflow->block_info == NULL)
1346*e4b17023SJohn Marino     return NULL;
1347*e4b17023SJohn Marino   if (index >= dflow->block_info_size)
1348*e4b17023SJohn Marino     return NULL;
1349*e4b17023SJohn Marino   return (void *)((char *)dflow->block_info
1350*e4b17023SJohn Marino 		  + index * dflow->problem->block_info_elt_size);
1351*e4b17023SJohn Marino }
1352*e4b17023SJohn Marino 
1353*e4b17023SJohn Marino 
1354*e4b17023SJohn Marino /* Set basic block info.  */
1355*e4b17023SJohn Marino 
1356*e4b17023SJohn Marino static void
df_set_bb_info(struct dataflow * dflow,unsigned int index,void * bb_info)1357*e4b17023SJohn Marino df_set_bb_info (struct dataflow *dflow, unsigned int index,
1358*e4b17023SJohn Marino 		void *bb_info)
1359*e4b17023SJohn Marino {
1360*e4b17023SJohn Marino   gcc_assert (dflow->block_info);
1361*e4b17023SJohn Marino   memcpy ((char *)dflow->block_info
1362*e4b17023SJohn Marino 	  + index * dflow->problem->block_info_elt_size,
1363*e4b17023SJohn Marino 	  bb_info, dflow->problem->block_info_elt_size);
1364*e4b17023SJohn Marino }
1365*e4b17023SJohn Marino 
1366*e4b17023SJohn Marino 
1367*e4b17023SJohn Marino /* Clear basic block info.  */
1368*e4b17023SJohn Marino 
1369*e4b17023SJohn Marino static void
df_clear_bb_info(struct dataflow * dflow,unsigned int index)1370*e4b17023SJohn Marino df_clear_bb_info (struct dataflow *dflow, unsigned int index)
1371*e4b17023SJohn Marino {
1372*e4b17023SJohn Marino   gcc_assert (dflow->block_info);
1373*e4b17023SJohn Marino   gcc_assert (dflow->block_info_size > index);
1374*e4b17023SJohn Marino   memset ((char *)dflow->block_info
1375*e4b17023SJohn Marino 	  + index * dflow->problem->block_info_elt_size,
1376*e4b17023SJohn Marino 	  0, dflow->problem->block_info_elt_size);
1377*e4b17023SJohn Marino }
1378*e4b17023SJohn Marino 
1379*e4b17023SJohn Marino 
1380*e4b17023SJohn Marino /* Mark the solutions as being out of date.  */
1381*e4b17023SJohn Marino 
1382*e4b17023SJohn Marino void
df_mark_solutions_dirty(void)1383*e4b17023SJohn Marino df_mark_solutions_dirty (void)
1384*e4b17023SJohn Marino {
1385*e4b17023SJohn Marino   if (df)
1386*e4b17023SJohn Marino     {
1387*e4b17023SJohn Marino       int p;
1388*e4b17023SJohn Marino       for (p = 1; p < df->num_problems_defined; p++)
1389*e4b17023SJohn Marino 	df->problems_in_order[p]->solutions_dirty = true;
1390*e4b17023SJohn Marino     }
1391*e4b17023SJohn Marino }
1392*e4b17023SJohn Marino 
1393*e4b17023SJohn Marino 
1394*e4b17023SJohn Marino /* Return true if BB needs it's transfer functions recomputed.  */
1395*e4b17023SJohn Marino 
1396*e4b17023SJohn Marino bool
df_get_bb_dirty(basic_block bb)1397*e4b17023SJohn Marino df_get_bb_dirty (basic_block bb)
1398*e4b17023SJohn Marino {
1399*e4b17023SJohn Marino   return bitmap_bit_p ((df_live
1400*e4b17023SJohn Marino 			? df_live : df_lr)->out_of_date_transfer_functions,
1401*e4b17023SJohn Marino 		       bb->index);
1402*e4b17023SJohn Marino }
1403*e4b17023SJohn Marino 
1404*e4b17023SJohn Marino 
1405*e4b17023SJohn Marino /* Mark BB as needing it's transfer functions as being out of
1406*e4b17023SJohn Marino    date.  */
1407*e4b17023SJohn Marino 
1408*e4b17023SJohn Marino void
df_set_bb_dirty(basic_block bb)1409*e4b17023SJohn Marino df_set_bb_dirty (basic_block bb)
1410*e4b17023SJohn Marino {
1411*e4b17023SJohn Marino   bb->flags |= BB_MODIFIED;
1412*e4b17023SJohn Marino   if (df)
1413*e4b17023SJohn Marino     {
1414*e4b17023SJohn Marino       int p;
1415*e4b17023SJohn Marino       for (p = 1; p < df->num_problems_defined; p++)
1416*e4b17023SJohn Marino 	{
1417*e4b17023SJohn Marino 	  struct dataflow *dflow = df->problems_in_order[p];
1418*e4b17023SJohn Marino 	  if (dflow->out_of_date_transfer_functions)
1419*e4b17023SJohn Marino 	    bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1420*e4b17023SJohn Marino 	}
1421*e4b17023SJohn Marino       df_mark_solutions_dirty ();
1422*e4b17023SJohn Marino     }
1423*e4b17023SJohn Marino }
1424*e4b17023SJohn Marino 
1425*e4b17023SJohn Marino 
1426*e4b17023SJohn Marino /* Grow the bb_info array.  */
1427*e4b17023SJohn Marino 
1428*e4b17023SJohn Marino void
df_grow_bb_info(struct dataflow * dflow)1429*e4b17023SJohn Marino df_grow_bb_info (struct dataflow *dflow)
1430*e4b17023SJohn Marino {
1431*e4b17023SJohn Marino   unsigned int new_size = last_basic_block + 1;
1432*e4b17023SJohn Marino   if (dflow->block_info_size < new_size)
1433*e4b17023SJohn Marino     {
1434*e4b17023SJohn Marino       new_size += new_size / 4;
1435*e4b17023SJohn Marino       dflow->block_info
1436*e4b17023SJohn Marino          = (void *)XRESIZEVEC (char, (char *)dflow->block_info,
1437*e4b17023SJohn Marino 			       new_size
1438*e4b17023SJohn Marino 			       * dflow->problem->block_info_elt_size);
1439*e4b17023SJohn Marino       memset ((char *)dflow->block_info
1440*e4b17023SJohn Marino 	      + dflow->block_info_size
1441*e4b17023SJohn Marino 	      * dflow->problem->block_info_elt_size,
1442*e4b17023SJohn Marino 	      0,
1443*e4b17023SJohn Marino 	      (new_size - dflow->block_info_size)
1444*e4b17023SJohn Marino 	      * dflow->problem->block_info_elt_size);
1445*e4b17023SJohn Marino       dflow->block_info_size = new_size;
1446*e4b17023SJohn Marino     }
1447*e4b17023SJohn Marino }
1448*e4b17023SJohn Marino 
1449*e4b17023SJohn Marino 
1450*e4b17023SJohn Marino /* Clear the dirty bits.  This is called from places that delete
1451*e4b17023SJohn Marino    blocks.  */
1452*e4b17023SJohn Marino static void
df_clear_bb_dirty(basic_block bb)1453*e4b17023SJohn Marino df_clear_bb_dirty (basic_block bb)
1454*e4b17023SJohn Marino {
1455*e4b17023SJohn Marino   int p;
1456*e4b17023SJohn Marino   for (p = 1; p < df->num_problems_defined; p++)
1457*e4b17023SJohn Marino     {
1458*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[p];
1459*e4b17023SJohn Marino       if (dflow->out_of_date_transfer_functions)
1460*e4b17023SJohn Marino 	bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
1461*e4b17023SJohn Marino     }
1462*e4b17023SJohn Marino }
1463*e4b17023SJohn Marino 
1464*e4b17023SJohn Marino /* Called from the rtl_compact_blocks to reorganize the problems basic
1465*e4b17023SJohn Marino    block info.  */
1466*e4b17023SJohn Marino 
1467*e4b17023SJohn Marino void
df_compact_blocks(void)1468*e4b17023SJohn Marino df_compact_blocks (void)
1469*e4b17023SJohn Marino {
1470*e4b17023SJohn Marino   int i, p;
1471*e4b17023SJohn Marino   basic_block bb;
1472*e4b17023SJohn Marino   void *problem_temps;
1473*e4b17023SJohn Marino   bitmap_head tmp;
1474*e4b17023SJohn Marino 
1475*e4b17023SJohn Marino   bitmap_initialize (&tmp, &df_bitmap_obstack);
1476*e4b17023SJohn Marino   for (p = 0; p < df->num_problems_defined; p++)
1477*e4b17023SJohn Marino     {
1478*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[p];
1479*e4b17023SJohn Marino 
1480*e4b17023SJohn Marino       /* Need to reorganize the out_of_date_transfer_functions for the
1481*e4b17023SJohn Marino 	 dflow problem.  */
1482*e4b17023SJohn Marino       if (dflow->out_of_date_transfer_functions)
1483*e4b17023SJohn Marino 	{
1484*e4b17023SJohn Marino 	  bitmap_copy (&tmp, dflow->out_of_date_transfer_functions);
1485*e4b17023SJohn Marino 	  bitmap_clear (dflow->out_of_date_transfer_functions);
1486*e4b17023SJohn Marino 	  if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1487*e4b17023SJohn Marino 	    bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
1488*e4b17023SJohn Marino 	  if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1489*e4b17023SJohn Marino 	    bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
1490*e4b17023SJohn Marino 
1491*e4b17023SJohn Marino 	  i = NUM_FIXED_BLOCKS;
1492*e4b17023SJohn Marino 	  FOR_EACH_BB (bb)
1493*e4b17023SJohn Marino 	    {
1494*e4b17023SJohn Marino 	      if (bitmap_bit_p (&tmp, bb->index))
1495*e4b17023SJohn Marino 		bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
1496*e4b17023SJohn Marino 	      i++;
1497*e4b17023SJohn Marino 	    }
1498*e4b17023SJohn Marino 	}
1499*e4b17023SJohn Marino 
1500*e4b17023SJohn Marino       /* Now shuffle the block info for the problem.  */
1501*e4b17023SJohn Marino       if (dflow->problem->free_bb_fun)
1502*e4b17023SJohn Marino 	{
1503*e4b17023SJohn Marino 	  int size = last_basic_block * dflow->problem->block_info_elt_size;
1504*e4b17023SJohn Marino 	  problem_temps = XNEWVAR (char, size);
1505*e4b17023SJohn Marino 	  df_grow_bb_info (dflow);
1506*e4b17023SJohn Marino 	  memcpy (problem_temps, dflow->block_info, size);
1507*e4b17023SJohn Marino 
1508*e4b17023SJohn Marino 	  /* Copy the bb info from the problem tmps to the proper
1509*e4b17023SJohn Marino 	     place in the block_info vector.  Null out the copied
1510*e4b17023SJohn Marino 	     item.  The entry and exit blocks never move.  */
1511*e4b17023SJohn Marino 	  i = NUM_FIXED_BLOCKS;
1512*e4b17023SJohn Marino 	  FOR_EACH_BB (bb)
1513*e4b17023SJohn Marino 	    {
1514*e4b17023SJohn Marino 	      df_set_bb_info (dflow, i,
1515*e4b17023SJohn Marino 			      (char *)problem_temps
1516*e4b17023SJohn Marino 			      + bb->index * dflow->problem->block_info_elt_size);
1517*e4b17023SJohn Marino 	      i++;
1518*e4b17023SJohn Marino 	    }
1519*e4b17023SJohn Marino 	  memset ((char *)dflow->block_info
1520*e4b17023SJohn Marino 		  + i * dflow->problem->block_info_elt_size, 0,
1521*e4b17023SJohn Marino 		  (last_basic_block - i)
1522*e4b17023SJohn Marino 		  * dflow->problem->block_info_elt_size);
1523*e4b17023SJohn Marino 	  free (problem_temps);
1524*e4b17023SJohn Marino 	}
1525*e4b17023SJohn Marino     }
1526*e4b17023SJohn Marino 
1527*e4b17023SJohn Marino   /* Shuffle the bits in the basic_block indexed arrays.  */
1528*e4b17023SJohn Marino 
1529*e4b17023SJohn Marino   if (df->blocks_to_analyze)
1530*e4b17023SJohn Marino     {
1531*e4b17023SJohn Marino       if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1532*e4b17023SJohn Marino 	bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
1533*e4b17023SJohn Marino       if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1534*e4b17023SJohn Marino 	bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
1535*e4b17023SJohn Marino       bitmap_copy (&tmp, df->blocks_to_analyze);
1536*e4b17023SJohn Marino       bitmap_clear (df->blocks_to_analyze);
1537*e4b17023SJohn Marino       i = NUM_FIXED_BLOCKS;
1538*e4b17023SJohn Marino       FOR_EACH_BB (bb)
1539*e4b17023SJohn Marino 	{
1540*e4b17023SJohn Marino 	  if (bitmap_bit_p (&tmp, bb->index))
1541*e4b17023SJohn Marino 	    bitmap_set_bit (df->blocks_to_analyze, i);
1542*e4b17023SJohn Marino 	  i++;
1543*e4b17023SJohn Marino 	}
1544*e4b17023SJohn Marino     }
1545*e4b17023SJohn Marino 
1546*e4b17023SJohn Marino   bitmap_clear (&tmp);
1547*e4b17023SJohn Marino 
1548*e4b17023SJohn Marino   i = NUM_FIXED_BLOCKS;
1549*e4b17023SJohn Marino   FOR_EACH_BB (bb)
1550*e4b17023SJohn Marino     {
1551*e4b17023SJohn Marino       SET_BASIC_BLOCK (i, bb);
1552*e4b17023SJohn Marino       bb->index = i;
1553*e4b17023SJohn Marino       i++;
1554*e4b17023SJohn Marino     }
1555*e4b17023SJohn Marino 
1556*e4b17023SJohn Marino   gcc_assert (i == n_basic_blocks);
1557*e4b17023SJohn Marino 
1558*e4b17023SJohn Marino   for (; i < last_basic_block; i++)
1559*e4b17023SJohn Marino     SET_BASIC_BLOCK (i, NULL);
1560*e4b17023SJohn Marino 
1561*e4b17023SJohn Marino #ifdef DF_DEBUG_CFG
1562*e4b17023SJohn Marino   if (!df_lr->solutions_dirty)
1563*e4b17023SJohn Marino     df_set_clean_cfg ();
1564*e4b17023SJohn Marino #endif
1565*e4b17023SJohn Marino }
1566*e4b17023SJohn Marino 
1567*e4b17023SJohn Marino 
1568*e4b17023SJohn Marino /* Shove NEW_BLOCK in at OLD_INDEX.  Called from ifcvt to hack a
1569*e4b17023SJohn Marino    block.  There is no excuse for people to do this kind of thing.  */
1570*e4b17023SJohn Marino 
1571*e4b17023SJohn Marino void
df_bb_replace(int old_index,basic_block new_block)1572*e4b17023SJohn Marino df_bb_replace (int old_index, basic_block new_block)
1573*e4b17023SJohn Marino {
1574*e4b17023SJohn Marino   int new_block_index = new_block->index;
1575*e4b17023SJohn Marino   int p;
1576*e4b17023SJohn Marino 
1577*e4b17023SJohn Marino   if (dump_file)
1578*e4b17023SJohn Marino     fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
1579*e4b17023SJohn Marino 
1580*e4b17023SJohn Marino   gcc_assert (df);
1581*e4b17023SJohn Marino   gcc_assert (BASIC_BLOCK (old_index) == NULL);
1582*e4b17023SJohn Marino 
1583*e4b17023SJohn Marino   for (p = 0; p < df->num_problems_defined; p++)
1584*e4b17023SJohn Marino     {
1585*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[p];
1586*e4b17023SJohn Marino       if (dflow->block_info)
1587*e4b17023SJohn Marino 	{
1588*e4b17023SJohn Marino 	  df_grow_bb_info (dflow);
1589*e4b17023SJohn Marino 	  df_set_bb_info (dflow, old_index,
1590*e4b17023SJohn Marino 			  df_get_bb_info (dflow, new_block_index));
1591*e4b17023SJohn Marino 	}
1592*e4b17023SJohn Marino     }
1593*e4b17023SJohn Marino 
1594*e4b17023SJohn Marino   df_clear_bb_dirty (new_block);
1595*e4b17023SJohn Marino   SET_BASIC_BLOCK (old_index, new_block);
1596*e4b17023SJohn Marino   new_block->index = old_index;
1597*e4b17023SJohn Marino   df_set_bb_dirty (BASIC_BLOCK (old_index));
1598*e4b17023SJohn Marino   SET_BASIC_BLOCK (new_block_index, NULL);
1599*e4b17023SJohn Marino }
1600*e4b17023SJohn Marino 
1601*e4b17023SJohn Marino 
1602*e4b17023SJohn Marino /* Free all of the per basic block dataflow from all of the problems.
1603*e4b17023SJohn Marino    This is typically called before a basic block is deleted and the
1604*e4b17023SJohn Marino    problem will be reanalyzed.  */
1605*e4b17023SJohn Marino 
1606*e4b17023SJohn Marino void
df_bb_delete(int bb_index)1607*e4b17023SJohn Marino df_bb_delete (int bb_index)
1608*e4b17023SJohn Marino {
1609*e4b17023SJohn Marino   basic_block bb = BASIC_BLOCK (bb_index);
1610*e4b17023SJohn Marino   int i;
1611*e4b17023SJohn Marino 
1612*e4b17023SJohn Marino   if (!df)
1613*e4b17023SJohn Marino     return;
1614*e4b17023SJohn Marino 
1615*e4b17023SJohn Marino   for (i = 0; i < df->num_problems_defined; i++)
1616*e4b17023SJohn Marino     {
1617*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[i];
1618*e4b17023SJohn Marino       if (dflow->problem->free_bb_fun)
1619*e4b17023SJohn Marino 	{
1620*e4b17023SJohn Marino 	  void *bb_info = df_get_bb_info (dflow, bb_index);
1621*e4b17023SJohn Marino 	  if (bb_info)
1622*e4b17023SJohn Marino 	    {
1623*e4b17023SJohn Marino 	      dflow->problem->free_bb_fun (bb, bb_info);
1624*e4b17023SJohn Marino 	      df_clear_bb_info (dflow, bb_index);
1625*e4b17023SJohn Marino 	    }
1626*e4b17023SJohn Marino 	}
1627*e4b17023SJohn Marino     }
1628*e4b17023SJohn Marino   df_clear_bb_dirty (bb);
1629*e4b17023SJohn Marino   df_mark_solutions_dirty ();
1630*e4b17023SJohn Marino }
1631*e4b17023SJohn Marino 
1632*e4b17023SJohn Marino 
1633*e4b17023SJohn Marino /* Verify that there is a place for everything and everything is in
1634*e4b17023SJohn Marino    its place.  This is too expensive to run after every pass in the
1635*e4b17023SJohn Marino    mainline.  However this is an excellent debugging tool if the
1636*e4b17023SJohn Marino    dataflow information is not being updated properly.  You can just
1637*e4b17023SJohn Marino    sprinkle calls in until you find the place that is changing an
1638*e4b17023SJohn Marino    underlying structure without calling the proper updating
1639*e4b17023SJohn Marino    routine.  */
1640*e4b17023SJohn Marino 
1641*e4b17023SJohn Marino void
df_verify(void)1642*e4b17023SJohn Marino df_verify (void)
1643*e4b17023SJohn Marino {
1644*e4b17023SJohn Marino   df_scan_verify ();
1645*e4b17023SJohn Marino #ifdef ENABLE_DF_CHECKING
1646*e4b17023SJohn Marino   df_lr_verify_transfer_functions ();
1647*e4b17023SJohn Marino   if (df_live)
1648*e4b17023SJohn Marino     df_live_verify_transfer_functions ();
1649*e4b17023SJohn Marino #endif
1650*e4b17023SJohn Marino }
1651*e4b17023SJohn Marino 
1652*e4b17023SJohn Marino #ifdef DF_DEBUG_CFG
1653*e4b17023SJohn Marino 
1654*e4b17023SJohn Marino /* Compute an array of ints that describes the cfg.  This can be used
1655*e4b17023SJohn Marino    to discover places where the cfg is modified by the appropriate
1656*e4b17023SJohn Marino    calls have not been made to the keep df informed.  The internals of
1657*e4b17023SJohn Marino    this are unexciting, the key is that two instances of this can be
1658*e4b17023SJohn Marino    compared to see if any changes have been made to the cfg.  */
1659*e4b17023SJohn Marino 
1660*e4b17023SJohn Marino static int *
df_compute_cfg_image(void)1661*e4b17023SJohn Marino df_compute_cfg_image (void)
1662*e4b17023SJohn Marino {
1663*e4b17023SJohn Marino   basic_block bb;
1664*e4b17023SJohn Marino   int size = 2 + (2 * n_basic_blocks);
1665*e4b17023SJohn Marino   int i;
1666*e4b17023SJohn Marino   int * map;
1667*e4b17023SJohn Marino 
1668*e4b17023SJohn Marino   FOR_ALL_BB (bb)
1669*e4b17023SJohn Marino     {
1670*e4b17023SJohn Marino       size += EDGE_COUNT (bb->succs);
1671*e4b17023SJohn Marino     }
1672*e4b17023SJohn Marino 
1673*e4b17023SJohn Marino   map = XNEWVEC (int, size);
1674*e4b17023SJohn Marino   map[0] = size;
1675*e4b17023SJohn Marino   i = 1;
1676*e4b17023SJohn Marino   FOR_ALL_BB (bb)
1677*e4b17023SJohn Marino     {
1678*e4b17023SJohn Marino       edge_iterator ei;
1679*e4b17023SJohn Marino       edge e;
1680*e4b17023SJohn Marino 
1681*e4b17023SJohn Marino       map[i++] = bb->index;
1682*e4b17023SJohn Marino       FOR_EACH_EDGE (e, ei, bb->succs)
1683*e4b17023SJohn Marino 	map[i++] = e->dest->index;
1684*e4b17023SJohn Marino       map[i++] = -1;
1685*e4b17023SJohn Marino     }
1686*e4b17023SJohn Marino   map[i] = -1;
1687*e4b17023SJohn Marino   return map;
1688*e4b17023SJohn Marino }
1689*e4b17023SJohn Marino 
1690*e4b17023SJohn Marino static int *saved_cfg = NULL;
1691*e4b17023SJohn Marino 
1692*e4b17023SJohn Marino 
1693*e4b17023SJohn Marino /* This function compares the saved version of the cfg with the
1694*e4b17023SJohn Marino    current cfg and aborts if the two are identical.  The function
1695*e4b17023SJohn Marino    silently returns if the cfg has been marked as dirty or the two are
1696*e4b17023SJohn Marino    the same.  */
1697*e4b17023SJohn Marino 
1698*e4b17023SJohn Marino void
df_check_cfg_clean(void)1699*e4b17023SJohn Marino df_check_cfg_clean (void)
1700*e4b17023SJohn Marino {
1701*e4b17023SJohn Marino   int *new_map;
1702*e4b17023SJohn Marino 
1703*e4b17023SJohn Marino   if (!df)
1704*e4b17023SJohn Marino     return;
1705*e4b17023SJohn Marino 
1706*e4b17023SJohn Marino   if (df_lr->solutions_dirty)
1707*e4b17023SJohn Marino     return;
1708*e4b17023SJohn Marino 
1709*e4b17023SJohn Marino   if (saved_cfg == NULL)
1710*e4b17023SJohn Marino     return;
1711*e4b17023SJohn Marino 
1712*e4b17023SJohn Marino   new_map = df_compute_cfg_image ();
1713*e4b17023SJohn Marino   gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
1714*e4b17023SJohn Marino   free (new_map);
1715*e4b17023SJohn Marino }
1716*e4b17023SJohn Marino 
1717*e4b17023SJohn Marino 
1718*e4b17023SJohn Marino /* This function builds a cfg fingerprint and squirrels it away in
1719*e4b17023SJohn Marino    saved_cfg.  */
1720*e4b17023SJohn Marino 
1721*e4b17023SJohn Marino static void
df_set_clean_cfg(void)1722*e4b17023SJohn Marino df_set_clean_cfg (void)
1723*e4b17023SJohn Marino {
1724*e4b17023SJohn Marino   free (saved_cfg);
1725*e4b17023SJohn Marino   saved_cfg = df_compute_cfg_image ();
1726*e4b17023SJohn Marino }
1727*e4b17023SJohn Marino 
1728*e4b17023SJohn Marino #endif /* DF_DEBUG_CFG  */
1729*e4b17023SJohn Marino /*----------------------------------------------------------------------------
1730*e4b17023SJohn Marino    PUBLIC INTERFACES TO QUERY INFORMATION.
1731*e4b17023SJohn Marino ----------------------------------------------------------------------------*/
1732*e4b17023SJohn Marino 
1733*e4b17023SJohn Marino 
1734*e4b17023SJohn Marino /* Return first def of REGNO within BB.  */
1735*e4b17023SJohn Marino 
1736*e4b17023SJohn Marino df_ref
df_bb_regno_first_def_find(basic_block bb,unsigned int regno)1737*e4b17023SJohn Marino df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
1738*e4b17023SJohn Marino {
1739*e4b17023SJohn Marino   rtx insn;
1740*e4b17023SJohn Marino   df_ref *def_rec;
1741*e4b17023SJohn Marino   unsigned int uid;
1742*e4b17023SJohn Marino 
1743*e4b17023SJohn Marino   FOR_BB_INSNS (bb, insn)
1744*e4b17023SJohn Marino     {
1745*e4b17023SJohn Marino       if (!INSN_P (insn))
1746*e4b17023SJohn Marino 	continue;
1747*e4b17023SJohn Marino 
1748*e4b17023SJohn Marino       uid = INSN_UID (insn);
1749*e4b17023SJohn Marino       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1750*e4b17023SJohn Marino 	{
1751*e4b17023SJohn Marino 	  df_ref def = *def_rec;
1752*e4b17023SJohn Marino 	  if (DF_REF_REGNO (def) == regno)
1753*e4b17023SJohn Marino 	    return def;
1754*e4b17023SJohn Marino 	}
1755*e4b17023SJohn Marino     }
1756*e4b17023SJohn Marino   return NULL;
1757*e4b17023SJohn Marino }
1758*e4b17023SJohn Marino 
1759*e4b17023SJohn Marino 
1760*e4b17023SJohn Marino /* Return last def of REGNO within BB.  */
1761*e4b17023SJohn Marino 
1762*e4b17023SJohn Marino df_ref
df_bb_regno_last_def_find(basic_block bb,unsigned int regno)1763*e4b17023SJohn Marino df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
1764*e4b17023SJohn Marino {
1765*e4b17023SJohn Marino   rtx insn;
1766*e4b17023SJohn Marino   df_ref *def_rec;
1767*e4b17023SJohn Marino   unsigned int uid;
1768*e4b17023SJohn Marino 
1769*e4b17023SJohn Marino   FOR_BB_INSNS_REVERSE (bb, insn)
1770*e4b17023SJohn Marino     {
1771*e4b17023SJohn Marino       if (!INSN_P (insn))
1772*e4b17023SJohn Marino 	continue;
1773*e4b17023SJohn Marino 
1774*e4b17023SJohn Marino       uid = INSN_UID (insn);
1775*e4b17023SJohn Marino       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1776*e4b17023SJohn Marino 	{
1777*e4b17023SJohn Marino 	  df_ref def = *def_rec;
1778*e4b17023SJohn Marino 	  if (DF_REF_REGNO (def) == regno)
1779*e4b17023SJohn Marino 	    return def;
1780*e4b17023SJohn Marino 	}
1781*e4b17023SJohn Marino     }
1782*e4b17023SJohn Marino 
1783*e4b17023SJohn Marino   return NULL;
1784*e4b17023SJohn Marino }
1785*e4b17023SJohn Marino 
1786*e4b17023SJohn Marino /* Finds the reference corresponding to the definition of REG in INSN.
1787*e4b17023SJohn Marino    DF is the dataflow object.  */
1788*e4b17023SJohn Marino 
1789*e4b17023SJohn Marino df_ref
df_find_def(rtx insn,rtx reg)1790*e4b17023SJohn Marino df_find_def (rtx insn, rtx reg)
1791*e4b17023SJohn Marino {
1792*e4b17023SJohn Marino   unsigned int uid;
1793*e4b17023SJohn Marino   df_ref *def_rec;
1794*e4b17023SJohn Marino 
1795*e4b17023SJohn Marino   if (GET_CODE (reg) == SUBREG)
1796*e4b17023SJohn Marino     reg = SUBREG_REG (reg);
1797*e4b17023SJohn Marino   gcc_assert (REG_P (reg));
1798*e4b17023SJohn Marino 
1799*e4b17023SJohn Marino   uid = INSN_UID (insn);
1800*e4b17023SJohn Marino   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1801*e4b17023SJohn Marino     {
1802*e4b17023SJohn Marino       df_ref def = *def_rec;
1803*e4b17023SJohn Marino       if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
1804*e4b17023SJohn Marino 	return def;
1805*e4b17023SJohn Marino     }
1806*e4b17023SJohn Marino 
1807*e4b17023SJohn Marino   return NULL;
1808*e4b17023SJohn Marino }
1809*e4b17023SJohn Marino 
1810*e4b17023SJohn Marino 
1811*e4b17023SJohn Marino /* Return true if REG is defined in INSN, zero otherwise.  */
1812*e4b17023SJohn Marino 
1813*e4b17023SJohn Marino bool
df_reg_defined(rtx insn,rtx reg)1814*e4b17023SJohn Marino df_reg_defined (rtx insn, rtx reg)
1815*e4b17023SJohn Marino {
1816*e4b17023SJohn Marino   return df_find_def (insn, reg) != NULL;
1817*e4b17023SJohn Marino }
1818*e4b17023SJohn Marino 
1819*e4b17023SJohn Marino 
1820*e4b17023SJohn Marino /* Finds the reference corresponding to the use of REG in INSN.
1821*e4b17023SJohn Marino    DF is the dataflow object.  */
1822*e4b17023SJohn Marino 
1823*e4b17023SJohn Marino df_ref
df_find_use(rtx insn,rtx reg)1824*e4b17023SJohn Marino df_find_use (rtx insn, rtx reg)
1825*e4b17023SJohn Marino {
1826*e4b17023SJohn Marino   unsigned int uid;
1827*e4b17023SJohn Marino   df_ref *use_rec;
1828*e4b17023SJohn Marino 
1829*e4b17023SJohn Marino   if (GET_CODE (reg) == SUBREG)
1830*e4b17023SJohn Marino     reg = SUBREG_REG (reg);
1831*e4b17023SJohn Marino   gcc_assert (REG_P (reg));
1832*e4b17023SJohn Marino 
1833*e4b17023SJohn Marino   uid = INSN_UID (insn);
1834*e4b17023SJohn Marino   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1835*e4b17023SJohn Marino     {
1836*e4b17023SJohn Marino       df_ref use = *use_rec;
1837*e4b17023SJohn Marino       if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1838*e4b17023SJohn Marino 	return use;
1839*e4b17023SJohn Marino     }
1840*e4b17023SJohn Marino   if (df->changeable_flags & DF_EQ_NOTES)
1841*e4b17023SJohn Marino     for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1842*e4b17023SJohn Marino       {
1843*e4b17023SJohn Marino 	df_ref use = *use_rec;
1844*e4b17023SJohn Marino 	if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1845*e4b17023SJohn Marino 	  return use;
1846*e4b17023SJohn Marino       }
1847*e4b17023SJohn Marino   return NULL;
1848*e4b17023SJohn Marino }
1849*e4b17023SJohn Marino 
1850*e4b17023SJohn Marino 
1851*e4b17023SJohn Marino /* Return true if REG is referenced in INSN, zero otherwise.  */
1852*e4b17023SJohn Marino 
1853*e4b17023SJohn Marino bool
df_reg_used(rtx insn,rtx reg)1854*e4b17023SJohn Marino df_reg_used (rtx insn, rtx reg)
1855*e4b17023SJohn Marino {
1856*e4b17023SJohn Marino   return df_find_use (insn, reg) != NULL;
1857*e4b17023SJohn Marino }
1858*e4b17023SJohn Marino 
1859*e4b17023SJohn Marino 
1860*e4b17023SJohn Marino /*----------------------------------------------------------------------------
1861*e4b17023SJohn Marino    Debugging and printing functions.
1862*e4b17023SJohn Marino ----------------------------------------------------------------------------*/
1863*e4b17023SJohn Marino 
1864*e4b17023SJohn Marino 
1865*e4b17023SJohn Marino /* Write information about registers and basic blocks into FILE.
1866*e4b17023SJohn Marino    This is part of making a debugging dump.  */
1867*e4b17023SJohn Marino 
1868*e4b17023SJohn Marino void
df_print_regset(FILE * file,bitmap r)1869*e4b17023SJohn Marino df_print_regset (FILE *file, bitmap r)
1870*e4b17023SJohn Marino {
1871*e4b17023SJohn Marino   unsigned int i;
1872*e4b17023SJohn Marino   bitmap_iterator bi;
1873*e4b17023SJohn Marino 
1874*e4b17023SJohn Marino   if (r == NULL)
1875*e4b17023SJohn Marino     fputs (" (nil)", file);
1876*e4b17023SJohn Marino   else
1877*e4b17023SJohn Marino     {
1878*e4b17023SJohn Marino       EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
1879*e4b17023SJohn Marino 	{
1880*e4b17023SJohn Marino 	  fprintf (file, " %d", i);
1881*e4b17023SJohn Marino 	  if (i < FIRST_PSEUDO_REGISTER)
1882*e4b17023SJohn Marino 	    fprintf (file, " [%s]", reg_names[i]);
1883*e4b17023SJohn Marino 	}
1884*e4b17023SJohn Marino     }
1885*e4b17023SJohn Marino   fprintf (file, "\n");
1886*e4b17023SJohn Marino }
1887*e4b17023SJohn Marino 
1888*e4b17023SJohn Marino 
1889*e4b17023SJohn Marino /* Write information about registers and basic blocks into FILE.  The
1890*e4b17023SJohn Marino    bitmap is in the form used by df_byte_lr.  This is part of making a
1891*e4b17023SJohn Marino    debugging dump.  */
1892*e4b17023SJohn Marino 
1893*e4b17023SJohn Marino void
df_print_word_regset(FILE * file,bitmap r)1894*e4b17023SJohn Marino df_print_word_regset (FILE *file, bitmap r)
1895*e4b17023SJohn Marino {
1896*e4b17023SJohn Marino   unsigned int max_reg = max_reg_num ();
1897*e4b17023SJohn Marino 
1898*e4b17023SJohn Marino   if (r == NULL)
1899*e4b17023SJohn Marino     fputs (" (nil)", file);
1900*e4b17023SJohn Marino   else
1901*e4b17023SJohn Marino     {
1902*e4b17023SJohn Marino       unsigned int i;
1903*e4b17023SJohn Marino       for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++)
1904*e4b17023SJohn Marino 	{
1905*e4b17023SJohn Marino 	  bool found = (bitmap_bit_p (r, 2 * i)
1906*e4b17023SJohn Marino 			|| bitmap_bit_p (r, 2 * i + 1));
1907*e4b17023SJohn Marino 	  if (found)
1908*e4b17023SJohn Marino 	    {
1909*e4b17023SJohn Marino 	      int word;
1910*e4b17023SJohn Marino 	      const char * sep = "";
1911*e4b17023SJohn Marino 	      fprintf (file, " %d", i);
1912*e4b17023SJohn Marino 	      fprintf (file, "(");
1913*e4b17023SJohn Marino 	      for (word = 0; word < 2; word++)
1914*e4b17023SJohn Marino 		if (bitmap_bit_p (r, 2 * i + word))
1915*e4b17023SJohn Marino 		  {
1916*e4b17023SJohn Marino 		    fprintf (file, "%s%d", sep, word);
1917*e4b17023SJohn Marino 		    sep = ", ";
1918*e4b17023SJohn Marino 		  }
1919*e4b17023SJohn Marino 	      fprintf (file, ")");
1920*e4b17023SJohn Marino 	    }
1921*e4b17023SJohn Marino 	}
1922*e4b17023SJohn Marino     }
1923*e4b17023SJohn Marino   fprintf (file, "\n");
1924*e4b17023SJohn Marino }
1925*e4b17023SJohn Marino 
1926*e4b17023SJohn Marino 
1927*e4b17023SJohn Marino /* Dump dataflow info.  */
1928*e4b17023SJohn Marino 
1929*e4b17023SJohn Marino void
df_dump(FILE * file)1930*e4b17023SJohn Marino df_dump (FILE *file)
1931*e4b17023SJohn Marino {
1932*e4b17023SJohn Marino   basic_block bb;
1933*e4b17023SJohn Marino   df_dump_start (file);
1934*e4b17023SJohn Marino 
1935*e4b17023SJohn Marino   FOR_ALL_BB (bb)
1936*e4b17023SJohn Marino     {
1937*e4b17023SJohn Marino       df_print_bb_index (bb, file);
1938*e4b17023SJohn Marino       df_dump_top (bb, file);
1939*e4b17023SJohn Marino       df_dump_bottom (bb, file);
1940*e4b17023SJohn Marino     }
1941*e4b17023SJohn Marino 
1942*e4b17023SJohn Marino   fprintf (file, "\n");
1943*e4b17023SJohn Marino }
1944*e4b17023SJohn Marino 
1945*e4b17023SJohn Marino 
1946*e4b17023SJohn Marino /* Dump dataflow info for df->blocks_to_analyze.  */
1947*e4b17023SJohn Marino 
1948*e4b17023SJohn Marino void
df_dump_region(FILE * file)1949*e4b17023SJohn Marino df_dump_region (FILE *file)
1950*e4b17023SJohn Marino {
1951*e4b17023SJohn Marino   if (df->blocks_to_analyze)
1952*e4b17023SJohn Marino     {
1953*e4b17023SJohn Marino       bitmap_iterator bi;
1954*e4b17023SJohn Marino       unsigned int bb_index;
1955*e4b17023SJohn Marino 
1956*e4b17023SJohn Marino       fprintf (file, "\n\nstarting region dump\n");
1957*e4b17023SJohn Marino       df_dump_start (file);
1958*e4b17023SJohn Marino 
1959*e4b17023SJohn Marino       EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1960*e4b17023SJohn Marino 	{
1961*e4b17023SJohn Marino 	  basic_block bb = BASIC_BLOCK (bb_index);
1962*e4b17023SJohn Marino 
1963*e4b17023SJohn Marino 	  df_print_bb_index (bb, file);
1964*e4b17023SJohn Marino 	  df_dump_top (bb, file);
1965*e4b17023SJohn Marino 	  df_dump_bottom (bb, file);
1966*e4b17023SJohn Marino 	}
1967*e4b17023SJohn Marino       fprintf (file, "\n");
1968*e4b17023SJohn Marino     }
1969*e4b17023SJohn Marino   else
1970*e4b17023SJohn Marino     df_dump (file);
1971*e4b17023SJohn Marino }
1972*e4b17023SJohn Marino 
1973*e4b17023SJohn Marino 
1974*e4b17023SJohn Marino /* Dump the introductory information for each problem defined.  */
1975*e4b17023SJohn Marino 
1976*e4b17023SJohn Marino void
df_dump_start(FILE * file)1977*e4b17023SJohn Marino df_dump_start (FILE *file)
1978*e4b17023SJohn Marino {
1979*e4b17023SJohn Marino   int i;
1980*e4b17023SJohn Marino 
1981*e4b17023SJohn Marino   if (!df || !file)
1982*e4b17023SJohn Marino     return;
1983*e4b17023SJohn Marino 
1984*e4b17023SJohn Marino   fprintf (file, "\n\n%s\n", current_function_name ());
1985*e4b17023SJohn Marino   fprintf (file, "\nDataflow summary:\n");
1986*e4b17023SJohn Marino   if (df->blocks_to_analyze)
1987*e4b17023SJohn Marino     fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
1988*e4b17023SJohn Marino 	     DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
1989*e4b17023SJohn Marino 
1990*e4b17023SJohn Marino   for (i = 0; i < df->num_problems_defined; i++)
1991*e4b17023SJohn Marino     {
1992*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[i];
1993*e4b17023SJohn Marino       if (dflow->computed)
1994*e4b17023SJohn Marino 	{
1995*e4b17023SJohn Marino 	  df_dump_problem_function fun = dflow->problem->dump_start_fun;
1996*e4b17023SJohn Marino 	  if (fun)
1997*e4b17023SJohn Marino 	    fun(file);
1998*e4b17023SJohn Marino 	}
1999*e4b17023SJohn Marino     }
2000*e4b17023SJohn Marino }
2001*e4b17023SJohn Marino 
2002*e4b17023SJohn Marino 
2003*e4b17023SJohn Marino /* Dump the top of the block information for BB.  */
2004*e4b17023SJohn Marino 
2005*e4b17023SJohn Marino void
df_dump_top(basic_block bb,FILE * file)2006*e4b17023SJohn Marino df_dump_top (basic_block bb, FILE *file)
2007*e4b17023SJohn Marino {
2008*e4b17023SJohn Marino   int i;
2009*e4b17023SJohn Marino 
2010*e4b17023SJohn Marino   if (!df || !file)
2011*e4b17023SJohn Marino     return;
2012*e4b17023SJohn Marino 
2013*e4b17023SJohn Marino   for (i = 0; i < df->num_problems_defined; i++)
2014*e4b17023SJohn Marino     {
2015*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[i];
2016*e4b17023SJohn Marino       if (dflow->computed)
2017*e4b17023SJohn Marino 	{
2018*e4b17023SJohn Marino 	  df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
2019*e4b17023SJohn Marino 	  if (bbfun)
2020*e4b17023SJohn Marino 	    bbfun (bb, file);
2021*e4b17023SJohn Marino 	}
2022*e4b17023SJohn Marino     }
2023*e4b17023SJohn Marino }
2024*e4b17023SJohn Marino 
2025*e4b17023SJohn Marino 
2026*e4b17023SJohn Marino /* Dump the bottom of the block information for BB.  */
2027*e4b17023SJohn Marino 
2028*e4b17023SJohn Marino void
df_dump_bottom(basic_block bb,FILE * file)2029*e4b17023SJohn Marino df_dump_bottom (basic_block bb, FILE *file)
2030*e4b17023SJohn Marino {
2031*e4b17023SJohn Marino   int i;
2032*e4b17023SJohn Marino 
2033*e4b17023SJohn Marino   if (!df || !file)
2034*e4b17023SJohn Marino     return;
2035*e4b17023SJohn Marino 
2036*e4b17023SJohn Marino   for (i = 0; i < df->num_problems_defined; i++)
2037*e4b17023SJohn Marino     {
2038*e4b17023SJohn Marino       struct dataflow *dflow = df->problems_in_order[i];
2039*e4b17023SJohn Marino       if (dflow->computed)
2040*e4b17023SJohn Marino 	{
2041*e4b17023SJohn Marino 	  df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
2042*e4b17023SJohn Marino 	  if (bbfun)
2043*e4b17023SJohn Marino 	    bbfun (bb, file);
2044*e4b17023SJohn Marino 	}
2045*e4b17023SJohn Marino     }
2046*e4b17023SJohn Marino }
2047*e4b17023SJohn Marino 
2048*e4b17023SJohn Marino 
2049*e4b17023SJohn Marino static void
df_ref_dump(df_ref ref,FILE * file)2050*e4b17023SJohn Marino df_ref_dump (df_ref ref, FILE *file)
2051*e4b17023SJohn Marino {
2052*e4b17023SJohn Marino   fprintf (file, "%c%d(%d)",
2053*e4b17023SJohn Marino 	   DF_REF_REG_DEF_P (ref)
2054*e4b17023SJohn Marino 	   ? 'd'
2055*e4b17023SJohn Marino 	   : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
2056*e4b17023SJohn Marino 	   DF_REF_ID (ref),
2057*e4b17023SJohn Marino 	   DF_REF_REGNO (ref));
2058*e4b17023SJohn Marino }
2059*e4b17023SJohn Marino 
2060*e4b17023SJohn Marino void
df_refs_chain_dump(df_ref * ref_rec,bool follow_chain,FILE * file)2061*e4b17023SJohn Marino df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file)
2062*e4b17023SJohn Marino {
2063*e4b17023SJohn Marino   fprintf (file, "{ ");
2064*e4b17023SJohn Marino   while (*ref_rec)
2065*e4b17023SJohn Marino     {
2066*e4b17023SJohn Marino       df_ref ref = *ref_rec;
2067*e4b17023SJohn Marino       df_ref_dump (ref, file);
2068*e4b17023SJohn Marino       if (follow_chain)
2069*e4b17023SJohn Marino 	df_chain_dump (DF_REF_CHAIN (ref), file);
2070*e4b17023SJohn Marino       ref_rec++;
2071*e4b17023SJohn Marino     }
2072*e4b17023SJohn Marino   fprintf (file, "}");
2073*e4b17023SJohn Marino }
2074*e4b17023SJohn Marino 
2075*e4b17023SJohn Marino 
2076*e4b17023SJohn Marino /* Dump either a ref-def or reg-use chain.  */
2077*e4b17023SJohn Marino 
2078*e4b17023SJohn Marino void
df_regs_chain_dump(df_ref ref,FILE * file)2079*e4b17023SJohn Marino df_regs_chain_dump (df_ref ref,  FILE *file)
2080*e4b17023SJohn Marino {
2081*e4b17023SJohn Marino   fprintf (file, "{ ");
2082*e4b17023SJohn Marino   while (ref)
2083*e4b17023SJohn Marino     {
2084*e4b17023SJohn Marino       df_ref_dump (ref, file);
2085*e4b17023SJohn Marino       ref = DF_REF_NEXT_REG (ref);
2086*e4b17023SJohn Marino     }
2087*e4b17023SJohn Marino   fprintf (file, "}");
2088*e4b17023SJohn Marino }
2089*e4b17023SJohn Marino 
2090*e4b17023SJohn Marino 
2091*e4b17023SJohn Marino static void
df_mws_dump(struct df_mw_hardreg ** mws,FILE * file)2092*e4b17023SJohn Marino df_mws_dump (struct df_mw_hardreg **mws, FILE *file)
2093*e4b17023SJohn Marino {
2094*e4b17023SJohn Marino   while (*mws)
2095*e4b17023SJohn Marino     {
2096*e4b17023SJohn Marino       fprintf (file, "mw %c r[%d..%d]\n",
2097*e4b17023SJohn Marino 	       (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u',
2098*e4b17023SJohn Marino 	       (*mws)->start_regno, (*mws)->end_regno);
2099*e4b17023SJohn Marino       mws++;
2100*e4b17023SJohn Marino     }
2101*e4b17023SJohn Marino }
2102*e4b17023SJohn Marino 
2103*e4b17023SJohn Marino 
2104*e4b17023SJohn Marino static void
df_insn_uid_debug(unsigned int uid,bool follow_chain,FILE * file)2105*e4b17023SJohn Marino df_insn_uid_debug (unsigned int uid,
2106*e4b17023SJohn Marino 		   bool follow_chain, FILE *file)
2107*e4b17023SJohn Marino {
2108*e4b17023SJohn Marino   fprintf (file, "insn %d luid %d",
2109*e4b17023SJohn Marino 	   uid, DF_INSN_UID_LUID (uid));
2110*e4b17023SJohn Marino 
2111*e4b17023SJohn Marino   if (DF_INSN_UID_DEFS (uid))
2112*e4b17023SJohn Marino     {
2113*e4b17023SJohn Marino       fprintf (file, " defs ");
2114*e4b17023SJohn Marino       df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
2115*e4b17023SJohn Marino     }
2116*e4b17023SJohn Marino 
2117*e4b17023SJohn Marino   if (DF_INSN_UID_USES (uid))
2118*e4b17023SJohn Marino     {
2119*e4b17023SJohn Marino       fprintf (file, " uses ");
2120*e4b17023SJohn Marino       df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
2121*e4b17023SJohn Marino     }
2122*e4b17023SJohn Marino 
2123*e4b17023SJohn Marino   if (DF_INSN_UID_EQ_USES (uid))
2124*e4b17023SJohn Marino     {
2125*e4b17023SJohn Marino       fprintf (file, " eq uses ");
2126*e4b17023SJohn Marino       df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
2127*e4b17023SJohn Marino     }
2128*e4b17023SJohn Marino 
2129*e4b17023SJohn Marino   if (DF_INSN_UID_MWS (uid))
2130*e4b17023SJohn Marino     {
2131*e4b17023SJohn Marino       fprintf (file, " mws ");
2132*e4b17023SJohn Marino       df_mws_dump (DF_INSN_UID_MWS (uid), file);
2133*e4b17023SJohn Marino     }
2134*e4b17023SJohn Marino   fprintf (file, "\n");
2135*e4b17023SJohn Marino }
2136*e4b17023SJohn Marino 
2137*e4b17023SJohn Marino 
2138*e4b17023SJohn Marino DEBUG_FUNCTION void
df_insn_debug(rtx insn,bool follow_chain,FILE * file)2139*e4b17023SJohn Marino df_insn_debug (rtx insn, bool follow_chain, FILE *file)
2140*e4b17023SJohn Marino {
2141*e4b17023SJohn Marino   df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
2142*e4b17023SJohn Marino }
2143*e4b17023SJohn Marino 
2144*e4b17023SJohn Marino DEBUG_FUNCTION void
df_insn_debug_regno(rtx insn,FILE * file)2145*e4b17023SJohn Marino df_insn_debug_regno (rtx insn, FILE *file)
2146*e4b17023SJohn Marino {
2147*e4b17023SJohn Marino   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2148*e4b17023SJohn Marino 
2149*e4b17023SJohn Marino   fprintf (file, "insn %d bb %d luid %d defs ",
2150*e4b17023SJohn Marino 	   INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
2151*e4b17023SJohn Marino 	   DF_INSN_INFO_LUID (insn_info));
2152*e4b17023SJohn Marino   df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
2153*e4b17023SJohn Marino 
2154*e4b17023SJohn Marino   fprintf (file, " uses ");
2155*e4b17023SJohn Marino   df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
2156*e4b17023SJohn Marino 
2157*e4b17023SJohn Marino   fprintf (file, " eq_uses ");
2158*e4b17023SJohn Marino   df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
2159*e4b17023SJohn Marino   fprintf (file, "\n");
2160*e4b17023SJohn Marino }
2161*e4b17023SJohn Marino 
2162*e4b17023SJohn Marino DEBUG_FUNCTION void
df_regno_debug(unsigned int regno,FILE * file)2163*e4b17023SJohn Marino df_regno_debug (unsigned int regno, FILE *file)
2164*e4b17023SJohn Marino {
2165*e4b17023SJohn Marino   fprintf (file, "reg %d defs ", regno);
2166*e4b17023SJohn Marino   df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
2167*e4b17023SJohn Marino   fprintf (file, " uses ");
2168*e4b17023SJohn Marino   df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
2169*e4b17023SJohn Marino   fprintf (file, " eq_uses ");
2170*e4b17023SJohn Marino   df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
2171*e4b17023SJohn Marino   fprintf (file, "\n");
2172*e4b17023SJohn Marino }
2173*e4b17023SJohn Marino 
2174*e4b17023SJohn Marino 
2175*e4b17023SJohn Marino DEBUG_FUNCTION void
df_ref_debug(df_ref ref,FILE * file)2176*e4b17023SJohn Marino df_ref_debug (df_ref ref, FILE *file)
2177*e4b17023SJohn Marino {
2178*e4b17023SJohn Marino   fprintf (file, "%c%d ",
2179*e4b17023SJohn Marino 	   DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2180*e4b17023SJohn Marino 	   DF_REF_ID (ref));
2181*e4b17023SJohn Marino   fprintf (file, "reg %d bb %d insn %d flag %#x type %#x ",
2182*e4b17023SJohn Marino 	   DF_REF_REGNO (ref),
2183*e4b17023SJohn Marino 	   DF_REF_BBNO (ref),
2184*e4b17023SJohn Marino 	   DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
2185*e4b17023SJohn Marino 	   DF_REF_FLAGS (ref),
2186*e4b17023SJohn Marino 	   DF_REF_TYPE (ref));
2187*e4b17023SJohn Marino   if (DF_REF_LOC (ref))
2188*e4b17023SJohn Marino     {
2189*e4b17023SJohn Marino       if (flag_dump_noaddr)
2190*e4b17023SJohn Marino 	fprintf (file, "loc #(#) chain ");
2191*e4b17023SJohn Marino       else
2192*e4b17023SJohn Marino 	fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
2193*e4b17023SJohn Marino 		 (void *)*DF_REF_LOC (ref));
2194*e4b17023SJohn Marino     }
2195*e4b17023SJohn Marino   else
2196*e4b17023SJohn Marino     fprintf (file, "chain ");
2197*e4b17023SJohn Marino   df_chain_dump (DF_REF_CHAIN (ref), file);
2198*e4b17023SJohn Marino   fprintf (file, "\n");
2199*e4b17023SJohn Marino }
2200*e4b17023SJohn Marino 
2201*e4b17023SJohn Marino /* Functions for debugging from GDB.  */
2202*e4b17023SJohn Marino 
2203*e4b17023SJohn Marino DEBUG_FUNCTION void
debug_df_insn(rtx insn)2204*e4b17023SJohn Marino debug_df_insn (rtx insn)
2205*e4b17023SJohn Marino {
2206*e4b17023SJohn Marino   df_insn_debug (insn, true, stderr);
2207*e4b17023SJohn Marino   debug_rtx (insn);
2208*e4b17023SJohn Marino }
2209*e4b17023SJohn Marino 
2210*e4b17023SJohn Marino 
2211*e4b17023SJohn Marino DEBUG_FUNCTION void
debug_df_reg(rtx reg)2212*e4b17023SJohn Marino debug_df_reg (rtx reg)
2213*e4b17023SJohn Marino {
2214*e4b17023SJohn Marino   df_regno_debug (REGNO (reg), stderr);
2215*e4b17023SJohn Marino }
2216*e4b17023SJohn Marino 
2217*e4b17023SJohn Marino 
2218*e4b17023SJohn Marino DEBUG_FUNCTION void
debug_df_regno(unsigned int regno)2219*e4b17023SJohn Marino debug_df_regno (unsigned int regno)
2220*e4b17023SJohn Marino {
2221*e4b17023SJohn Marino   df_regno_debug (regno, stderr);
2222*e4b17023SJohn Marino }
2223*e4b17023SJohn Marino 
2224*e4b17023SJohn Marino 
2225*e4b17023SJohn Marino DEBUG_FUNCTION void
debug_df_ref(df_ref ref)2226*e4b17023SJohn Marino debug_df_ref (df_ref ref)
2227*e4b17023SJohn Marino {
2228*e4b17023SJohn Marino   df_ref_debug (ref, stderr);
2229*e4b17023SJohn Marino }
2230*e4b17023SJohn Marino 
2231*e4b17023SJohn Marino 
2232*e4b17023SJohn Marino DEBUG_FUNCTION void
debug_df_defno(unsigned int defno)2233*e4b17023SJohn Marino debug_df_defno (unsigned int defno)
2234*e4b17023SJohn Marino {
2235*e4b17023SJohn Marino   df_ref_debug (DF_DEFS_GET (defno), stderr);
2236*e4b17023SJohn Marino }
2237*e4b17023SJohn Marino 
2238*e4b17023SJohn Marino 
2239*e4b17023SJohn Marino DEBUG_FUNCTION void
debug_df_useno(unsigned int defno)2240*e4b17023SJohn Marino debug_df_useno (unsigned int defno)
2241*e4b17023SJohn Marino {
2242*e4b17023SJohn Marino   df_ref_debug (DF_USES_GET (defno), stderr);
2243*e4b17023SJohn Marino }
2244*e4b17023SJohn Marino 
2245*e4b17023SJohn Marino 
2246*e4b17023SJohn Marino DEBUG_FUNCTION void
debug_df_chain(struct df_link * link)2247*e4b17023SJohn Marino debug_df_chain (struct df_link *link)
2248*e4b17023SJohn Marino {
2249*e4b17023SJohn Marino   df_chain_dump (link, stderr);
2250*e4b17023SJohn Marino   fputc ('\n', stderr);
2251*e4b17023SJohn Marino }
2252