OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [df-core.c] - Blame information for rev 826

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.