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