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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [df-core.c] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Allocation for dataflow support routines.
2
   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3
   2008, 2009, 2010, 2011 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
static void df_clear_bb_info (struct dataflow *, unsigned int);
403
#ifdef DF_DEBUG_CFG
404
static void df_set_clean_cfg (void);
405
#endif
406
 
407
/* An obstack for bitmap not related to specific dataflow problems.
408
   This obstack should e.g. be used for bitmaps with a short life time
409
   such as temporary bitmaps.  */
410
 
411
bitmap_obstack df_bitmap_obstack;
412
 
413
 
414
/*----------------------------------------------------------------------------
415
  Functions to create, destroy and manipulate an instance of df.
416
----------------------------------------------------------------------------*/
417
 
418
struct df_d *df;
419
 
420
/* Add PROBLEM (and any dependent problems) to the DF instance.  */
421
 
422
void
423
df_add_problem (struct df_problem *problem)
424
{
425
  struct dataflow *dflow;
426
  int i;
427
 
428
  /* First try to add the dependent problem. */
429
  if (problem->dependent_problem)
430
    df_add_problem (problem->dependent_problem);
431
 
432
  /* Check to see if this problem has already been defined.  If it
433
     has, just return that instance, if not, add it to the end of the
434
     vector.  */
435
  dflow = df->problems_by_index[problem->id];
436
  if (dflow)
437
    return;
438
 
439
  /* Make a new one and add it to the end.  */
440
  dflow = XCNEW (struct dataflow);
441
  dflow->problem = problem;
442
  dflow->computed = false;
443
  dflow->solutions_dirty = true;
444
  df->problems_by_index[dflow->problem->id] = dflow;
445
 
446
  /* Keep the defined problems ordered by index.  This solves the
447
     problem that RI will use the information from UREC if UREC has
448
     been defined, or from LIVE if LIVE is defined and otherwise LR.
449
     However for this to work, the computation of RI must be pushed
450
     after which ever of those problems is defined, but we do not
451
     require any of those except for LR to have actually been
452
     defined.  */
453
  df->num_problems_defined++;
454
  for (i = df->num_problems_defined - 2; i >= 0; i--)
455
    {
456
      if (problem->id < df->problems_in_order[i]->problem->id)
457
        df->problems_in_order[i+1] = df->problems_in_order[i];
458
      else
459
        {
460
          df->problems_in_order[i+1] = dflow;
461
          return;
462
        }
463
    }
464
  df->problems_in_order[0] = dflow;
465
}
466
 
467
 
468
/* Set the MASK flags in the DFLOW problem.  The old flags are
469
   returned.  If a flag is not allowed to be changed this will fail if
470
   checking is enabled.  */
471
int
472
df_set_flags (int changeable_flags)
473
{
474
  int old_flags = df->changeable_flags;
475
  df->changeable_flags |= changeable_flags;
476
  return old_flags;
477
}
478
 
479
 
480
/* Clear the MASK flags in the DFLOW problem.  The old flags are
481
   returned.  If a flag is not allowed to be changed this will fail if
482
   checking is enabled.  */
483
int
484
df_clear_flags (int changeable_flags)
485
{
486
  int old_flags = df->changeable_flags;
487
  df->changeable_flags &= ~changeable_flags;
488
  return old_flags;
489
}
490
 
491
 
492
/* Set the blocks that are to be considered for analysis.  If this is
493
   not called or is called with null, the entire function in
494
   analyzed.  */
495
 
496
void
497
df_set_blocks (bitmap blocks)
498
{
499
  if (blocks)
500
    {
501
      if (dump_file)
502
        bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n");
503
      if (df->blocks_to_analyze)
504
        {
505
          /* This block is called to change the focus from one subset
506
             to another.  */
507
          int p;
508
          bitmap_head diff;
509
          bitmap_initialize (&diff, &df_bitmap_obstack);
510
          bitmap_and_compl (&diff, df->blocks_to_analyze, blocks);
511
          for (p = 0; p < df->num_problems_defined; p++)
512
            {
513
              struct dataflow *dflow = df->problems_in_order[p];
514
              if (dflow->optional_p && dflow->problem->reset_fun)
515
                dflow->problem->reset_fun (df->blocks_to_analyze);
516
              else if (dflow->problem->free_blocks_on_set_blocks)
517
                {
518
                  bitmap_iterator bi;
519
                  unsigned int bb_index;
520
 
521
                  EXECUTE_IF_SET_IN_BITMAP (&diff, 0, bb_index, bi)
522
                    {
523
                      basic_block bb = BASIC_BLOCK (bb_index);
524
                      if (bb)
525
                        {
526
                          void *bb_info = df_get_bb_info (dflow, bb_index);
527
                          dflow->problem->free_bb_fun (bb, bb_info);
528
                          df_clear_bb_info (dflow, bb_index);
529
                        }
530
                    }
531
                }
532
            }
533
 
534
           bitmap_clear (&diff);
535
        }
536
      else
537
        {
538
          /* This block of code is executed to change the focus from
539
             the entire function to a subset.  */
540
          bitmap_head blocks_to_reset;
541
          bool initialized = false;
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 (!initialized)
549
                    {
550
                      basic_block bb;
551
                      bitmap_initialize (&blocks_to_reset, &df_bitmap_obstack);
552
                      FOR_ALL_BB(bb)
553
                        {
554
                          bitmap_set_bit (&blocks_to_reset, bb->index);
555
                        }
556
                    }
557
                  dflow->problem->reset_fun (&blocks_to_reset);
558
                }
559
            }
560
          if (initialized)
561
            bitmap_clear (&blocks_to_reset);
562
 
563
          df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack);
564
        }
565
      bitmap_copy (df->blocks_to_analyze, blocks);
566
      df->analyze_subset = true;
567
    }
568
  else
569
    {
570
      /* This block is executed to reset the focus to the entire
571
         function.  */
572
      if (dump_file)
573
        fprintf (dump_file, "clearing blocks_to_analyze\n");
574
      if (df->blocks_to_analyze)
575
        {
576
          BITMAP_FREE (df->blocks_to_analyze);
577
          df->blocks_to_analyze = NULL;
578
        }
579
      df->analyze_subset = false;
580
    }
581
 
582
  /* Setting the blocks causes the refs to be unorganized since only
583
     the refs in the blocks are seen.  */
584
  df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
585
  df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
586
  df_mark_solutions_dirty ();
587
}
588
 
589
 
590
/* Delete a DFLOW problem (and any problems that depend on this
591
   problem).  */
592
 
593
void
594
df_remove_problem (struct dataflow *dflow)
595
{
596
  struct df_problem *problem;
597
  int i;
598
 
599
  if (!dflow)
600
    return;
601
 
602
  problem = dflow->problem;
603
  gcc_assert (problem->remove_problem_fun);
604
 
605
  /* Delete any problems that depended on this problem first.  */
606
  for (i = 0; i < df->num_problems_defined; i++)
607
    if (df->problems_in_order[i]->problem->dependent_problem == problem)
608
      df_remove_problem (df->problems_in_order[i]);
609
 
610
  /* Now remove this problem.  */
611
  for (i = 0; i < df->num_problems_defined; i++)
612
    if (df->problems_in_order[i] == dflow)
613
      {
614
        int j;
615
        for (j = i + 1; j < df->num_problems_defined; j++)
616
          df->problems_in_order[j-1] = df->problems_in_order[j];
617
        df->problems_in_order[j-1] = NULL;
618
        df->num_problems_defined--;
619
        break;
620
      }
621
 
622
  (problem->remove_problem_fun) ();
623
  df->problems_by_index[problem->id] = NULL;
624
}
625
 
626
 
627
/* Remove all of the problems that are not permanent.  Scanning, LR
628
   and (at -O2 or higher) LIVE are permanent, the rest are removable.
629
   Also clear all of the changeable_flags.  */
630
 
631
void
632
df_finish_pass (bool verify ATTRIBUTE_UNUSED)
633
{
634
  int i;
635
  int removed = 0;
636
 
637
#ifdef ENABLE_DF_CHECKING
638
  int saved_flags;
639
#endif
640
 
641
  if (!df)
642
    return;
643
 
644
  df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE);
645
  df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE);
646
 
647
#ifdef ENABLE_DF_CHECKING
648
  saved_flags = df->changeable_flags;
649
#endif
650
 
651
  for (i = 0; i < df->num_problems_defined; i++)
652
    {
653
      struct dataflow *dflow = df->problems_in_order[i];
654
      struct df_problem *problem = dflow->problem;
655
 
656
      if (dflow->optional_p)
657
        {
658
          gcc_assert (problem->remove_problem_fun);
659
          (problem->remove_problem_fun) ();
660
          df->problems_in_order[i] = NULL;
661
          df->problems_by_index[problem->id] = NULL;
662
          removed++;
663
        }
664
    }
665
  df->num_problems_defined -= removed;
666
 
667
  /* Clear all of the flags.  */
668
  df->changeable_flags = 0;
669
  df_process_deferred_rescans ();
670
 
671
  /* Set the focus back to the whole function.  */
672
  if (df->blocks_to_analyze)
673
    {
674
      BITMAP_FREE (df->blocks_to_analyze);
675
      df->blocks_to_analyze = NULL;
676
      df_mark_solutions_dirty ();
677
      df->analyze_subset = false;
678
    }
679
 
680
#ifdef ENABLE_DF_CHECKING
681
  /* Verification will fail in DF_NO_INSN_RESCAN.  */
682
  if (!(saved_flags & DF_NO_INSN_RESCAN))
683
    {
684
      df_lr_verify_transfer_functions ();
685
      if (df_live)
686
        df_live_verify_transfer_functions ();
687
    }
688
 
689
#ifdef DF_DEBUG_CFG
690
  df_set_clean_cfg ();
691
#endif
692
#endif
693
 
694
#ifdef ENABLE_CHECKING
695
  if (verify)
696
    df->changeable_flags |= DF_VERIFY_SCHEDULED;
697
#endif
698
}
699
 
700
 
701
/* Set up the dataflow instance for the entire back end.  */
702
 
703
static unsigned int
704
rest_of_handle_df_initialize (void)
705
{
706
  gcc_assert (!df);
707
  df = XCNEW (struct df_d);
708
  df->changeable_flags = 0;
709
 
710
  bitmap_obstack_initialize (&df_bitmap_obstack);
711
 
712
  /* Set this to a conservative value.  Stack_ptr_mod will compute it
713
     correctly later.  */
714
  current_function_sp_is_unchanging = 0;
715
 
716
  df_scan_add_problem ();
717
  df_scan_alloc (NULL);
718
 
719
  /* These three problems are permanent.  */
720
  df_lr_add_problem ();
721
  if (optimize > 1)
722
    df_live_add_problem ();
723
 
724
  df->postorder = XNEWVEC (int, last_basic_block);
725
  df->postorder_inverted = XNEWVEC (int, last_basic_block);
726
  df->n_blocks = post_order_compute (df->postorder, true, true);
727
  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
728
  gcc_assert (df->n_blocks == df->n_blocks_inverted);
729
 
730
  df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
731
  memset (df->hard_regs_live_count, 0,
732
          sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);
733
 
734
  df_hard_reg_init ();
735
  /* After reload, some ports add certain bits to regs_ever_live so
736
     this cannot be reset.  */
737
  df_compute_regs_ever_live (true);
738
  df_scan_blocks ();
739
  df_compute_regs_ever_live (false);
740
  return 0;
741
}
742
 
743
 
744
static bool
745
gate_opt (void)
746
{
747
  return optimize > 0;
748
}
749
 
750
 
751
struct rtl_opt_pass pass_df_initialize_opt =
752
{
753
 {
754
  RTL_PASS,
755
  "dfinit",                             /* name */
756
  gate_opt,                             /* gate */
757
  rest_of_handle_df_initialize,         /* execute */
758
  NULL,                                 /* sub */
759
  NULL,                                 /* next */
760
  0,                                    /* static_pass_number */
761
  TV_DF_SCAN,                           /* tv_id */
762
  0,                                    /* properties_required */
763
  0,                                    /* properties_provided */
764
  0,                                    /* properties_destroyed */
765
  0,                                    /* todo_flags_start */
766
 
767
 }
768
};
769
 
770
 
771
static bool
772
gate_no_opt (void)
773
{
774
  return optimize == 0;
775
}
776
 
777
 
778
struct rtl_opt_pass pass_df_initialize_no_opt =
779
{
780
 {
781
  RTL_PASS,
782
  "no-opt dfinit",                      /* name */
783
  gate_no_opt,                          /* gate */
784
  rest_of_handle_df_initialize,         /* execute */
785
  NULL,                                 /* sub */
786
  NULL,                                 /* next */
787
  0,                                    /* static_pass_number */
788
  TV_DF_SCAN,                           /* tv_id */
789
  0,                                    /* properties_required */
790
  0,                                    /* properties_provided */
791
  0,                                    /* properties_destroyed */
792
  0,                                    /* todo_flags_start */
793
 
794
 }
795
};
796
 
797
 
798
/* Free all the dataflow info and the DF structure.  This should be
799
   called from the df_finish macro which also NULLs the parm.  */
800
 
801
static unsigned int
802
rest_of_handle_df_finish (void)
803
{
804
  int i;
805
 
806
  gcc_assert (df);
807
 
808
  for (i = 0; i < df->num_problems_defined; i++)
809
    {
810
      struct dataflow *dflow = df->problems_in_order[i];
811
      dflow->problem->free_fun ();
812
    }
813
 
814
  free (df->postorder);
815
  free (df->postorder_inverted);
816
  free (df->hard_regs_live_count);
817
  free (df);
818
  df = NULL;
819
 
820
  bitmap_obstack_release (&df_bitmap_obstack);
821
  return 0;
822
}
823
 
824
 
825
struct rtl_opt_pass pass_df_finish =
826
{
827
 {
828
  RTL_PASS,
829
  "dfinish",                            /* name */
830
  NULL,                                 /* gate */
831
  rest_of_handle_df_finish,             /* execute */
832
  NULL,                                 /* sub */
833
  NULL,                                 /* next */
834
  0,                                    /* static_pass_number */
835
  TV_NONE,                              /* tv_id */
836
  0,                                    /* properties_required */
837
  0,                                    /* properties_provided */
838
  0,                                    /* properties_destroyed */
839
  0,                                    /* todo_flags_start */
840
 
841
 }
842
};
843
 
844
 
845
 
846
 
847
 
848
/*----------------------------------------------------------------------------
849
   The general data flow analysis engine.
850
----------------------------------------------------------------------------*/
851
 
852
/* Return time BB when it was visited for last time.  */
853
#define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux)
854
 
855
/* Helper function for df_worklist_dataflow.
856
   Propagate the dataflow forward.
857
   Given a BB_INDEX, do the dataflow propagation
858
   and set bits on for successors in PENDING
859
   if the out set of the dataflow has changed.
860
 
861
   AGE specify time when BB was visited last time.
862
   AGE of 0 means we are visiting for first time and need to
863
   compute transfer function to initialize datastructures.
864
   Otherwise we re-do transfer function only if something change
865
   while computing confluence functions.
866
   We need to compute confluence only of basic block that are younger
867
   then last visit of the BB.
868
 
869
   Return true if BB info has changed.  This is always the case
870
   in the first visit.  */
871
 
872
static bool
873
df_worklist_propagate_forward (struct dataflow *dataflow,
874
                               unsigned bb_index,
875
                               unsigned *bbindex_to_postorder,
876
                               bitmap pending,
877
                               sbitmap considered,
878
                               ptrdiff_t age)
879
{
880
  edge e;
881
  edge_iterator ei;
882
  basic_block bb = BASIC_BLOCK (bb_index);
883
  bool changed = !age;
884
 
885
  /*  Calculate <conf_op> of incoming edges.  */
886
  if (EDGE_COUNT (bb->preds) > 0)
887
    FOR_EACH_EDGE (e, ei, bb->preds)
888
      {
889
        if (age <= BB_LAST_CHANGE_AGE (e->src)
890
            && TEST_BIT (considered, e->src->index))
891
          changed |= dataflow->problem->con_fun_n (e);
892
      }
893
  else if (dataflow->problem->con_fun_0)
894
    dataflow->problem->con_fun_0 (bb);
895
 
896
  if (changed
897
      && dataflow->problem->trans_fun (bb_index))
898
    {
899
      /* The out set of this block has changed.
900
         Propagate to the outgoing blocks.  */
901
      FOR_EACH_EDGE (e, ei, bb->succs)
902
        {
903
          unsigned ob_index = e->dest->index;
904
 
905
          if (TEST_BIT (considered, ob_index))
906
            bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
907
        }
908
      return true;
909
    }
910
  return false;
911
}
912
 
913
 
914
/* Helper function for df_worklist_dataflow.
915
   Propagate the dataflow backward.  */
916
 
917
static bool
918
df_worklist_propagate_backward (struct dataflow *dataflow,
919
                                unsigned bb_index,
920
                                unsigned *bbindex_to_postorder,
921
                                bitmap pending,
922
                                sbitmap considered,
923
                                ptrdiff_t age)
924
{
925
  edge e;
926
  edge_iterator ei;
927
  basic_block bb = BASIC_BLOCK (bb_index);
928
  bool changed = !age;
929
 
930
  /*  Calculate <conf_op> of incoming edges.  */
931
  if (EDGE_COUNT (bb->succs) > 0)
932
    FOR_EACH_EDGE (e, ei, bb->succs)
933
      {
934
        if (age <= BB_LAST_CHANGE_AGE (e->dest)
935
            && TEST_BIT (considered, e->dest->index))
936
          changed |= dataflow->problem->con_fun_n (e);
937
      }
938
  else if (dataflow->problem->con_fun_0)
939
    dataflow->problem->con_fun_0 (bb);
940
 
941
  if (changed
942
      && dataflow->problem->trans_fun (bb_index))
943
    {
944
      /* The out set of this block has changed.
945
         Propagate to the outgoing blocks.  */
946
      FOR_EACH_EDGE (e, ei, bb->preds)
947
        {
948
          unsigned ob_index = e->src->index;
949
 
950
          if (TEST_BIT (considered, ob_index))
951
            bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
952
        }
953
      return true;
954
    }
955
  return false;
956
}
957
 
958
/* Main dataflow solver loop.
959
 
960
   DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we
961
   need to visit.
962
   BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and
963
   BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder possition.
964
   PENDING will be freed.
965
 
966
   The worklists are bitmaps indexed by postorder positions.
967
 
968
   The function implements standard algorithm for dataflow solving with two
969
   worklists (we are processing WORKLIST and storing new BBs to visit in
970
   PENDING).
971
 
972
   As an optimization we maintain ages when BB was changed (stored in bb->aux)
973
   and when it was last visited (stored in last_visit_age).  This avoids need
974
   to re-do confluence function for edges to basic blocks whose source
975
   did not change since destination was visited last time.  */
976
 
977
static void
978
df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
979
                                  bitmap pending,
980
                                  sbitmap considered,
981
                                  int *blocks_in_postorder,
982
                                  unsigned *bbindex_to_postorder,
983
                                  int n_blocks)
984
{
985
  enum df_flow_dir dir = dataflow->problem->dir;
986
  int dcount = 0;
987
  bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
988
  int age = 0;
989
  bool changed;
990
  VEC(int, heap) *last_visit_age = NULL;
991
  int prev_age;
992
  basic_block bb;
993
  int i;
994
 
995
  VEC_safe_grow_cleared (int, heap, last_visit_age, n_blocks);
996
 
997
  /* Double-queueing. Worklist is for the current iteration,
998
     and pending is for the next. */
999
  while (!bitmap_empty_p (pending))
1000
    {
1001
      bitmap_iterator bi;
1002
      unsigned int index;
1003
 
1004
      /* Swap pending and worklist. */
1005
      bitmap temp = worklist;
1006
      worklist = pending;
1007
      pending = temp;
1008
 
1009
      EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi)
1010
        {
1011
          unsigned bb_index;
1012
          dcount++;
1013
 
1014
          bitmap_clear_bit (pending, index);
1015
          bb_index = blocks_in_postorder[index];
1016
          bb = BASIC_BLOCK (bb_index);
1017
          prev_age = VEC_index (int, last_visit_age, index);
1018
          if (dir == DF_FORWARD)
1019
            changed = df_worklist_propagate_forward (dataflow, bb_index,
1020
                                                     bbindex_to_postorder,
1021
                                                     pending, considered,
1022
                                                     prev_age);
1023
          else
1024
            changed = df_worklist_propagate_backward (dataflow, bb_index,
1025
                                                      bbindex_to_postorder,
1026
                                                      pending, considered,
1027
                                                      prev_age);
1028
          VEC_replace (int, last_visit_age, index, ++age);
1029
          if (changed)
1030
            bb->aux = (void *)(ptrdiff_t)age;
1031
        }
1032
      bitmap_clear (worklist);
1033
    }
1034
  for (i = 0; i < n_blocks; i++)
1035
    BASIC_BLOCK (blocks_in_postorder[i])->aux = NULL;
1036
 
1037
  BITMAP_FREE (worklist);
1038
  BITMAP_FREE (pending);
1039
  VEC_free (int, heap, last_visit_age);
1040
 
1041
  /* Dump statistics. */
1042
  if (dump_file)
1043
    fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
1044
             "n_basic_blocks %d n_edges %d"
1045
             " count %d (%5.2g)\n",
1046
             n_basic_blocks, n_edges,
1047
             dcount, dcount / (float)n_basic_blocks);
1048
}
1049
 
1050
/* Worklist-based dataflow solver. It uses sbitmap as a worklist,
1051
   with "n"-th bit representing the n-th block in the reverse-postorder order.
1052
   The solver is a double-queue algorithm similar to the "double stack" solver
1053
   from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited".
1054
   The only significant difference is that the worklist in this implementation
1055
   is always sorted in RPO of the CFG visiting direction.  */
1056
 
1057
void
1058
df_worklist_dataflow (struct dataflow *dataflow,
1059
                      bitmap blocks_to_consider,
1060
                      int *blocks_in_postorder,
1061
                      int n_blocks)
1062
{
1063
  bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
1064
  sbitmap considered = sbitmap_alloc (last_basic_block);
1065
  bitmap_iterator bi;
1066
  unsigned int *bbindex_to_postorder;
1067
  int i;
1068
  unsigned int index;
1069
  enum df_flow_dir dir = dataflow->problem->dir;
1070
 
1071
  gcc_assert (dir != DF_NONE);
1072
 
1073
  /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder.  */
1074
  bbindex_to_postorder =
1075
    (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
1076
 
1077
  /* Initialize the array to an out-of-bound value.  */
1078
  for (i = 0; i < last_basic_block; i++)
1079
    bbindex_to_postorder[i] = last_basic_block;
1080
 
1081
  /* Initialize the considered map.  */
1082
  sbitmap_zero (considered);
1083
  EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
1084
    {
1085
      SET_BIT (considered, index);
1086
    }
1087
 
1088
  /* Initialize the mapping of block index to postorder.  */
1089
  for (i = 0; i < n_blocks; i++)
1090
    {
1091
      bbindex_to_postorder[blocks_in_postorder[i]] = i;
1092
      /* Add all blocks to the worklist.  */
1093
      bitmap_set_bit (pending, i);
1094
    }
1095
 
1096
  /* Initialize the problem. */
1097
  if (dataflow->problem->init_fun)
1098
    dataflow->problem->init_fun (blocks_to_consider);
1099
 
1100
  /* Solve it.  */
1101
  df_worklist_dataflow_doublequeue (dataflow, pending, considered,
1102
                                    blocks_in_postorder,
1103
                                    bbindex_to_postorder,
1104
                                    n_blocks);
1105
  sbitmap_free (considered);
1106
  free (bbindex_to_postorder);
1107
}
1108
 
1109
 
1110
/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
1111
   the order of the remaining entries.  Returns the length of the resulting
1112
   list.  */
1113
 
1114
static unsigned
1115
df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
1116
{
1117
  unsigned act, last;
1118
 
1119
  for (act = 0, last = 0; act < len; act++)
1120
    if (bitmap_bit_p (blocks, list[act]))
1121
      list[last++] = list[act];
1122
 
1123
  return last;
1124
}
1125
 
1126
 
1127
/* Execute dataflow analysis on a single dataflow problem.
1128
 
1129
   BLOCKS_TO_CONSIDER are the blocks whose solution can either be
1130
   examined or will be computed.  For calls from DF_ANALYZE, this is
1131
   the set of blocks that has been passed to DF_SET_BLOCKS.
1132
*/
1133
 
1134
void
1135
df_analyze_problem (struct dataflow *dflow,
1136
                    bitmap blocks_to_consider,
1137
                    int *postorder, int n_blocks)
1138
{
1139
  timevar_push (dflow->problem->tv_id);
1140
 
1141
  /* (Re)Allocate the datastructures necessary to solve the problem.  */
1142
  if (dflow->problem->alloc_fun)
1143
    dflow->problem->alloc_fun (blocks_to_consider);
1144
 
1145
#ifdef ENABLE_DF_CHECKING
1146
  if (dflow->problem->verify_start_fun)
1147
    dflow->problem->verify_start_fun ();
1148
#endif
1149
 
1150
  /* Set up the problem and compute the local information.  */
1151
  if (dflow->problem->local_compute_fun)
1152
    dflow->problem->local_compute_fun (blocks_to_consider);
1153
 
1154
  /* Solve the equations.  */
1155
  if (dflow->problem->dataflow_fun)
1156
    dflow->problem->dataflow_fun (dflow, blocks_to_consider,
1157
                                  postorder, n_blocks);
1158
 
1159
  /* Massage the solution.  */
1160
  if (dflow->problem->finalize_fun)
1161
    dflow->problem->finalize_fun (blocks_to_consider);
1162
 
1163
#ifdef ENABLE_DF_CHECKING
1164
  if (dflow->problem->verify_end_fun)
1165
    dflow->problem->verify_end_fun ();
1166
#endif
1167
 
1168
  timevar_pop (dflow->problem->tv_id);
1169
 
1170
  dflow->computed = true;
1171
}
1172
 
1173
 
1174
/* Analyze dataflow info for the basic blocks specified by the bitmap
1175
   BLOCKS, or for the whole CFG if BLOCKS is zero.  */
1176
 
1177
void
1178
df_analyze (void)
1179
{
1180
  bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
1181
  bool everything;
1182
  int i;
1183
 
1184
  free (df->postorder);
1185
  free (df->postorder_inverted);
1186
  df->postorder = XNEWVEC (int, last_basic_block);
1187
  df->postorder_inverted = XNEWVEC (int, last_basic_block);
1188
  df->n_blocks = post_order_compute (df->postorder, true, true);
1189
  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
1190
 
1191
  /* These should be the same.  */
1192
  gcc_assert (df->n_blocks == df->n_blocks_inverted);
1193
 
1194
  /* We need to do this before the df_verify_all because this is
1195
     not kept incrementally up to date.  */
1196
  df_compute_regs_ever_live (false);
1197
  df_process_deferred_rescans ();
1198
 
1199
  if (dump_file)
1200
    fprintf (dump_file, "df_analyze called\n");
1201
 
1202
#ifndef ENABLE_DF_CHECKING
1203
  if (df->changeable_flags & DF_VERIFY_SCHEDULED)
1204
#endif
1205
    df_verify ();
1206
 
1207
  for (i = 0; i < df->n_blocks; i++)
1208
    bitmap_set_bit (current_all_blocks, df->postorder[i]);
1209
 
1210
#ifdef ENABLE_CHECKING
1211
  /* Verify that POSTORDER_INVERTED only contains blocks reachable from
1212
     the ENTRY block.  */
1213
  for (i = 0; i < df->n_blocks_inverted; i++)
1214
    gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
1215
#endif
1216
 
1217
  /* Make sure that we have pruned any unreachable blocks from these
1218
     sets.  */
1219
  if (df->analyze_subset)
1220
    {
1221
      everything = false;
1222
      bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
1223
      df->n_blocks = df_prune_to_subcfg (df->postorder,
1224
                                         df->n_blocks, df->blocks_to_analyze);
1225
      df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
1226
                                                  df->n_blocks_inverted,
1227
                                                  df->blocks_to_analyze);
1228
      BITMAP_FREE (current_all_blocks);
1229
    }
1230
  else
1231
    {
1232
      everything = true;
1233
      df->blocks_to_analyze = current_all_blocks;
1234
      current_all_blocks = NULL;
1235
    }
1236
 
1237
  /* Skip over the DF_SCAN problem. */
1238
  for (i = 1; i < df->num_problems_defined; i++)
1239
    {
1240
      struct dataflow *dflow = df->problems_in_order[i];
1241
      if (dflow->solutions_dirty)
1242
        {
1243
          if (dflow->problem->dir == DF_FORWARD)
1244
            df_analyze_problem (dflow,
1245
                                df->blocks_to_analyze,
1246
                                df->postorder_inverted,
1247
                                df->n_blocks_inverted);
1248
          else
1249
            df_analyze_problem (dflow,
1250
                                df->blocks_to_analyze,
1251
                                df->postorder,
1252
                                df->n_blocks);
1253
        }
1254
    }
1255
 
1256
  if (everything)
1257
    {
1258
      BITMAP_FREE (df->blocks_to_analyze);
1259
      df->blocks_to_analyze = NULL;
1260
    }
1261
 
1262
#ifdef DF_DEBUG_CFG
1263
  df_set_clean_cfg ();
1264
#endif
1265
}
1266
 
1267
 
1268
/* Return the number of basic blocks from the last call to df_analyze.  */
1269
 
1270
int
1271
df_get_n_blocks (enum df_flow_dir dir)
1272
{
1273
  gcc_assert (dir != DF_NONE);
1274
 
1275
  if (dir == DF_FORWARD)
1276
    {
1277
      gcc_assert (df->postorder_inverted);
1278
      return df->n_blocks_inverted;
1279
    }
1280
 
1281
  gcc_assert (df->postorder);
1282
  return df->n_blocks;
1283
}
1284
 
1285
 
1286
/* Return a pointer to the array of basic blocks in the reverse postorder.
1287
   Depending on the direction of the dataflow problem,
1288
   it returns either the usual reverse postorder array
1289
   or the reverse postorder of inverted traversal. */
1290
int *
1291
df_get_postorder (enum df_flow_dir dir)
1292
{
1293
  gcc_assert (dir != DF_NONE);
1294
 
1295
  if (dir == DF_FORWARD)
1296
    {
1297
      gcc_assert (df->postorder_inverted);
1298
      return df->postorder_inverted;
1299
    }
1300
  gcc_assert (df->postorder);
1301
  return df->postorder;
1302
}
1303
 
1304
static struct df_problem user_problem;
1305
static struct dataflow user_dflow;
1306
 
1307
/* Interface for calling iterative dataflow with user defined
1308
   confluence and transfer functions.  All that is necessary is to
1309
   supply DIR, a direction, CONF_FUN_0, a confluence function for
1310
   blocks with no logical preds (or NULL), CONF_FUN_N, the normal
1311
   confluence function, TRANS_FUN, the basic block transfer function,
1312
   and BLOCKS, the set of blocks to examine, POSTORDER the blocks in
1313
   postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
1314
 
1315
void
1316
df_simple_dataflow (enum df_flow_dir dir,
1317
                    df_init_function init_fun,
1318
                    df_confluence_function_0 con_fun_0,
1319
                    df_confluence_function_n con_fun_n,
1320
                    df_transfer_function trans_fun,
1321
                    bitmap blocks, int * postorder, int n_blocks)
1322
{
1323
  memset (&user_problem, 0, sizeof (struct df_problem));
1324
  user_problem.dir = dir;
1325
  user_problem.init_fun = init_fun;
1326
  user_problem.con_fun_0 = con_fun_0;
1327
  user_problem.con_fun_n = con_fun_n;
1328
  user_problem.trans_fun = trans_fun;
1329
  user_dflow.problem = &user_problem;
1330
  df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
1331
}
1332
 
1333
 
1334
 
1335
/*----------------------------------------------------------------------------
1336
   Functions to support limited incremental change.
1337
----------------------------------------------------------------------------*/
1338
 
1339
 
1340
/* Get basic block info.  */
1341
 
1342
static void *
1343
df_get_bb_info (struct dataflow *dflow, unsigned int index)
1344
{
1345
  if (dflow->block_info == NULL)
1346
    return NULL;
1347
  if (index >= dflow->block_info_size)
1348
    return NULL;
1349
  return (void *)((char *)dflow->block_info
1350
                  + index * dflow->problem->block_info_elt_size);
1351
}
1352
 
1353
 
1354
/* Set basic block info.  */
1355
 
1356
static void
1357
df_set_bb_info (struct dataflow *dflow, unsigned int index,
1358
                void *bb_info)
1359
{
1360
  gcc_assert (dflow->block_info);
1361
  memcpy ((char *)dflow->block_info
1362
          + index * dflow->problem->block_info_elt_size,
1363
          bb_info, dflow->problem->block_info_elt_size);
1364
}
1365
 
1366
 
1367
/* Clear basic block info.  */
1368
 
1369
static void
1370
df_clear_bb_info (struct dataflow *dflow, unsigned int index)
1371
{
1372
  gcc_assert (dflow->block_info);
1373
  gcc_assert (dflow->block_info_size > index);
1374
  memset ((char *)dflow->block_info
1375
          + index * dflow->problem->block_info_elt_size,
1376
          0, dflow->problem->block_info_elt_size);
1377
}
1378
 
1379
 
1380
/* Mark the solutions as being out of date.  */
1381
 
1382
void
1383
df_mark_solutions_dirty (void)
1384
{
1385
  if (df)
1386
    {
1387
      int p;
1388
      for (p = 1; p < df->num_problems_defined; p++)
1389
        df->problems_in_order[p]->solutions_dirty = true;
1390
    }
1391
}
1392
 
1393
 
1394
/* Return true if BB needs it's transfer functions recomputed.  */
1395
 
1396
bool
1397
df_get_bb_dirty (basic_block bb)
1398
{
1399
  return bitmap_bit_p ((df_live
1400
                        ? df_live : df_lr)->out_of_date_transfer_functions,
1401
                       bb->index);
1402
}
1403
 
1404
 
1405
/* Mark BB as needing it's transfer functions as being out of
1406
   date.  */
1407
 
1408
void
1409
df_set_bb_dirty (basic_block bb)
1410
{
1411
  bb->flags |= BB_MODIFIED;
1412
  if (df)
1413
    {
1414
      int p;
1415
      for (p = 1; p < df->num_problems_defined; p++)
1416
        {
1417
          struct dataflow *dflow = df->problems_in_order[p];
1418
          if (dflow->out_of_date_transfer_functions)
1419
            bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index);
1420
        }
1421
      df_mark_solutions_dirty ();
1422
    }
1423
}
1424
 
1425
 
1426
/* Grow the bb_info array.  */
1427
 
1428
void
1429
df_grow_bb_info (struct dataflow *dflow)
1430
{
1431
  unsigned int new_size = last_basic_block + 1;
1432
  if (dflow->block_info_size < new_size)
1433
    {
1434
      new_size += new_size / 4;
1435
      dflow->block_info
1436
         = (void *)XRESIZEVEC (char, (char *)dflow->block_info,
1437
                               new_size
1438
                               * dflow->problem->block_info_elt_size);
1439
      memset ((char *)dflow->block_info
1440
              + dflow->block_info_size
1441
              * dflow->problem->block_info_elt_size,
1442
              0,
1443
              (new_size - dflow->block_info_size)
1444
              * dflow->problem->block_info_elt_size);
1445
      dflow->block_info_size = new_size;
1446
    }
1447
}
1448
 
1449
 
1450
/* Clear the dirty bits.  This is called from places that delete
1451
   blocks.  */
1452
static void
1453
df_clear_bb_dirty (basic_block bb)
1454
{
1455
  int p;
1456
  for (p = 1; p < df->num_problems_defined; p++)
1457
    {
1458
      struct dataflow *dflow = df->problems_in_order[p];
1459
      if (dflow->out_of_date_transfer_functions)
1460
        bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index);
1461
    }
1462
}
1463
 
1464
/* Called from the rtl_compact_blocks to reorganize the problems basic
1465
   block info.  */
1466
 
1467
void
1468
df_compact_blocks (void)
1469
{
1470
  int i, p;
1471
  basic_block bb;
1472
  void *problem_temps;
1473
  bitmap_head tmp;
1474
 
1475
  bitmap_initialize (&tmp, &df_bitmap_obstack);
1476
  for (p = 0; p < df->num_problems_defined; p++)
1477
    {
1478
      struct dataflow *dflow = df->problems_in_order[p];
1479
 
1480
      /* Need to reorganize the out_of_date_transfer_functions for the
1481
         dflow problem.  */
1482
      if (dflow->out_of_date_transfer_functions)
1483
        {
1484
          bitmap_copy (&tmp, dflow->out_of_date_transfer_functions);
1485
          bitmap_clear (dflow->out_of_date_transfer_functions);
1486
          if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1487
            bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
1488
          if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1489
            bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
1490
 
1491
          i = NUM_FIXED_BLOCKS;
1492
          FOR_EACH_BB (bb)
1493
            {
1494
              if (bitmap_bit_p (&tmp, bb->index))
1495
                bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
1496
              i++;
1497
            }
1498
        }
1499
 
1500
      /* Now shuffle the block info for the problem.  */
1501
      if (dflow->problem->free_bb_fun)
1502
        {
1503
          int size = last_basic_block * dflow->problem->block_info_elt_size;
1504
          problem_temps = XNEWVAR (char, size);
1505
          df_grow_bb_info (dflow);
1506
          memcpy (problem_temps, dflow->block_info, size);
1507
 
1508
          /* Copy the bb info from the problem tmps to the proper
1509
             place in the block_info vector.  Null out the copied
1510
             item.  The entry and exit blocks never move.  */
1511
          i = NUM_FIXED_BLOCKS;
1512
          FOR_EACH_BB (bb)
1513
            {
1514
              df_set_bb_info (dflow, i,
1515
                              (char *)problem_temps
1516
                              + bb->index * dflow->problem->block_info_elt_size);
1517
              i++;
1518
            }
1519
          memset ((char *)dflow->block_info
1520
                  + i * dflow->problem->block_info_elt_size, 0,
1521
                  (last_basic_block - i)
1522
                  * dflow->problem->block_info_elt_size);
1523
          free (problem_temps);
1524
        }
1525
    }
1526
 
1527
  /* Shuffle the bits in the basic_block indexed arrays.  */
1528
 
1529
  if (df->blocks_to_analyze)
1530
    {
1531
      if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
1532
        bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
1533
      if (bitmap_bit_p (&tmp, EXIT_BLOCK))
1534
        bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
1535
      bitmap_copy (&tmp, df->blocks_to_analyze);
1536
      bitmap_clear (df->blocks_to_analyze);
1537
      i = NUM_FIXED_BLOCKS;
1538
      FOR_EACH_BB (bb)
1539
        {
1540
          if (bitmap_bit_p (&tmp, bb->index))
1541
            bitmap_set_bit (df->blocks_to_analyze, i);
1542
          i++;
1543
        }
1544
    }
1545
 
1546
  bitmap_clear (&tmp);
1547
 
1548
  i = NUM_FIXED_BLOCKS;
1549
  FOR_EACH_BB (bb)
1550
    {
1551
      SET_BASIC_BLOCK (i, bb);
1552
      bb->index = i;
1553
      i++;
1554
    }
1555
 
1556
  gcc_assert (i == n_basic_blocks);
1557
 
1558
  for (; i < last_basic_block; i++)
1559
    SET_BASIC_BLOCK (i, NULL);
1560
 
1561
#ifdef DF_DEBUG_CFG
1562
  if (!df_lr->solutions_dirty)
1563
    df_set_clean_cfg ();
1564
#endif
1565
}
1566
 
1567
 
1568
/* Shove NEW_BLOCK in at OLD_INDEX.  Called from ifcvt to hack a
1569
   block.  There is no excuse for people to do this kind of thing.  */
1570
 
1571
void
1572
df_bb_replace (int old_index, basic_block new_block)
1573
{
1574
  int new_block_index = new_block->index;
1575
  int p;
1576
 
1577
  if (dump_file)
1578
    fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index);
1579
 
1580
  gcc_assert (df);
1581
  gcc_assert (BASIC_BLOCK (old_index) == NULL);
1582
 
1583
  for (p = 0; p < df->num_problems_defined; p++)
1584
    {
1585
      struct dataflow *dflow = df->problems_in_order[p];
1586
      if (dflow->block_info)
1587
        {
1588
          df_grow_bb_info (dflow);
1589
          df_set_bb_info (dflow, old_index,
1590
                          df_get_bb_info (dflow, new_block_index));
1591
        }
1592
    }
1593
 
1594
  df_clear_bb_dirty (new_block);
1595
  SET_BASIC_BLOCK (old_index, new_block);
1596
  new_block->index = old_index;
1597
  df_set_bb_dirty (BASIC_BLOCK (old_index));
1598
  SET_BASIC_BLOCK (new_block_index, NULL);
1599
}
1600
 
1601
 
1602
/* Free all of the per basic block dataflow from all of the problems.
1603
   This is typically called before a basic block is deleted and the
1604
   problem will be reanalyzed.  */
1605
 
1606
void
1607
df_bb_delete (int bb_index)
1608
{
1609
  basic_block bb = BASIC_BLOCK (bb_index);
1610
  int i;
1611
 
1612
  if (!df)
1613
    return;
1614
 
1615
  for (i = 0; i < df->num_problems_defined; i++)
1616
    {
1617
      struct dataflow *dflow = df->problems_in_order[i];
1618
      if (dflow->problem->free_bb_fun)
1619
        {
1620
          void *bb_info = df_get_bb_info (dflow, bb_index);
1621
          if (bb_info)
1622
            {
1623
              dflow->problem->free_bb_fun (bb, bb_info);
1624
              df_clear_bb_info (dflow, bb_index);
1625
            }
1626
        }
1627
    }
1628
  df_clear_bb_dirty (bb);
1629
  df_mark_solutions_dirty ();
1630
}
1631
 
1632
 
1633
/* Verify that there is a place for everything and everything is in
1634
   its place.  This is too expensive to run after every pass in the
1635
   mainline.  However this is an excellent debugging tool if the
1636
   dataflow information is not being updated properly.  You can just
1637
   sprinkle calls in until you find the place that is changing an
1638
   underlying structure without calling the proper updating
1639
   routine.  */
1640
 
1641
void
1642
df_verify (void)
1643
{
1644
  df_scan_verify ();
1645
#ifdef ENABLE_DF_CHECKING
1646
  df_lr_verify_transfer_functions ();
1647
  if (df_live)
1648
    df_live_verify_transfer_functions ();
1649
#endif
1650
}
1651
 
1652
#ifdef DF_DEBUG_CFG
1653
 
1654
/* Compute an array of ints that describes the cfg.  This can be used
1655
   to discover places where the cfg is modified by the appropriate
1656
   calls have not been made to the keep df informed.  The internals of
1657
   this are unexciting, the key is that two instances of this can be
1658
   compared to see if any changes have been made to the cfg.  */
1659
 
1660
static int *
1661
df_compute_cfg_image (void)
1662
{
1663
  basic_block bb;
1664
  int size = 2 + (2 * n_basic_blocks);
1665
  int i;
1666
  int * map;
1667
 
1668
  FOR_ALL_BB (bb)
1669
    {
1670
      size += EDGE_COUNT (bb->succs);
1671
    }
1672
 
1673
  map = XNEWVEC (int, size);
1674
  map[0] = size;
1675
  i = 1;
1676
  FOR_ALL_BB (bb)
1677
    {
1678
      edge_iterator ei;
1679
      edge e;
1680
 
1681
      map[i++] = bb->index;
1682
      FOR_EACH_EDGE (e, ei, bb->succs)
1683
        map[i++] = e->dest->index;
1684
      map[i++] = -1;
1685
    }
1686
  map[i] = -1;
1687
  return map;
1688
}
1689
 
1690
static int *saved_cfg = NULL;
1691
 
1692
 
1693
/* This function compares the saved version of the cfg with the
1694
   current cfg and aborts if the two are identical.  The function
1695
   silently returns if the cfg has been marked as dirty or the two are
1696
   the same.  */
1697
 
1698
void
1699
df_check_cfg_clean (void)
1700
{
1701
  int *new_map;
1702
 
1703
  if (!df)
1704
    return;
1705
 
1706
  if (df_lr->solutions_dirty)
1707
    return;
1708
 
1709
  if (saved_cfg == NULL)
1710
    return;
1711
 
1712
  new_map = df_compute_cfg_image ();
1713
  gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0);
1714
  free (new_map);
1715
}
1716
 
1717
 
1718
/* This function builds a cfg fingerprint and squirrels it away in
1719
   saved_cfg.  */
1720
 
1721
static void
1722
df_set_clean_cfg (void)
1723
{
1724
  free (saved_cfg);
1725
  saved_cfg = df_compute_cfg_image ();
1726
}
1727
 
1728
#endif /* DF_DEBUG_CFG  */
1729
/*----------------------------------------------------------------------------
1730
   PUBLIC INTERFACES TO QUERY INFORMATION.
1731
----------------------------------------------------------------------------*/
1732
 
1733
 
1734
/* Return first def of REGNO within BB.  */
1735
 
1736
df_ref
1737
df_bb_regno_first_def_find (basic_block bb, unsigned int regno)
1738
{
1739
  rtx insn;
1740
  df_ref *def_rec;
1741
  unsigned int uid;
1742
 
1743
  FOR_BB_INSNS (bb, insn)
1744
    {
1745
      if (!INSN_P (insn))
1746
        continue;
1747
 
1748
      uid = INSN_UID (insn);
1749
      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1750
        {
1751
          df_ref def = *def_rec;
1752
          if (DF_REF_REGNO (def) == regno)
1753
            return def;
1754
        }
1755
    }
1756
  return NULL;
1757
}
1758
 
1759
 
1760
/* Return last def of REGNO within BB.  */
1761
 
1762
df_ref
1763
df_bb_regno_last_def_find (basic_block bb, unsigned int regno)
1764
{
1765
  rtx insn;
1766
  df_ref *def_rec;
1767
  unsigned int uid;
1768
 
1769
  FOR_BB_INSNS_REVERSE (bb, insn)
1770
    {
1771
      if (!INSN_P (insn))
1772
        continue;
1773
 
1774
      uid = INSN_UID (insn);
1775
      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1776
        {
1777
          df_ref def = *def_rec;
1778
          if (DF_REF_REGNO (def) == regno)
1779
            return def;
1780
        }
1781
    }
1782
 
1783
  return NULL;
1784
}
1785
 
1786
/* Finds the reference corresponding to the definition of REG in INSN.
1787
   DF is the dataflow object.  */
1788
 
1789
df_ref
1790
df_find_def (rtx insn, rtx reg)
1791
{
1792
  unsigned int uid;
1793
  df_ref *def_rec;
1794
 
1795
  if (GET_CODE (reg) == SUBREG)
1796
    reg = SUBREG_REG (reg);
1797
  gcc_assert (REG_P (reg));
1798
 
1799
  uid = INSN_UID (insn);
1800
  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1801
    {
1802
      df_ref def = *def_rec;
1803
      if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
1804
        return def;
1805
    }
1806
 
1807
  return NULL;
1808
}
1809
 
1810
 
1811
/* Return true if REG is defined in INSN, zero otherwise.  */
1812
 
1813
bool
1814
df_reg_defined (rtx insn, rtx reg)
1815
{
1816
  return df_find_def (insn, reg) != NULL;
1817
}
1818
 
1819
 
1820
/* Finds the reference corresponding to the use of REG in INSN.
1821
   DF is the dataflow object.  */
1822
 
1823
df_ref
1824
df_find_use (rtx insn, rtx reg)
1825
{
1826
  unsigned int uid;
1827
  df_ref *use_rec;
1828
 
1829
  if (GET_CODE (reg) == SUBREG)
1830
    reg = SUBREG_REG (reg);
1831
  gcc_assert (REG_P (reg));
1832
 
1833
  uid = INSN_UID (insn);
1834
  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1835
    {
1836
      df_ref use = *use_rec;
1837
      if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1838
        return use;
1839
    }
1840
  if (df->changeable_flags & DF_EQ_NOTES)
1841
    for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1842
      {
1843
        df_ref use = *use_rec;
1844
        if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1845
          return use;
1846
      }
1847
  return NULL;
1848
}
1849
 
1850
 
1851
/* Return true if REG is referenced in INSN, zero otherwise.  */
1852
 
1853
bool
1854
df_reg_used (rtx insn, rtx reg)
1855
{
1856
  return df_find_use (insn, reg) != NULL;
1857
}
1858
 
1859
 
1860
/*----------------------------------------------------------------------------
1861
   Debugging and printing functions.
1862
----------------------------------------------------------------------------*/
1863
 
1864
 
1865
/* Write information about registers and basic blocks into FILE.
1866
   This is part of making a debugging dump.  */
1867
 
1868
void
1869
df_print_regset (FILE *file, bitmap r)
1870
{
1871
  unsigned int i;
1872
  bitmap_iterator bi;
1873
 
1874
  if (r == NULL)
1875
    fputs (" (nil)", file);
1876
  else
1877
    {
1878
      EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi)
1879
        {
1880
          fprintf (file, " %d", i);
1881
          if (i < FIRST_PSEUDO_REGISTER)
1882
            fprintf (file, " [%s]", reg_names[i]);
1883
        }
1884
    }
1885
  fprintf (file, "\n");
1886
}
1887
 
1888
 
1889
/* Write information about registers and basic blocks into FILE.  The
1890
   bitmap is in the form used by df_byte_lr.  This is part of making a
1891
   debugging dump.  */
1892
 
1893
void
1894
df_print_word_regset (FILE *file, bitmap r)
1895
{
1896
  unsigned int max_reg = max_reg_num ();
1897
 
1898
  if (r == NULL)
1899
    fputs (" (nil)", file);
1900
  else
1901
    {
1902
      unsigned int i;
1903
      for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++)
1904
        {
1905
          bool found = (bitmap_bit_p (r, 2 * i)
1906
                        || bitmap_bit_p (r, 2 * i + 1));
1907
          if (found)
1908
            {
1909
              int word;
1910
              const char * sep = "";
1911
              fprintf (file, " %d", i);
1912
              fprintf (file, "(");
1913
              for (word = 0; word < 2; word++)
1914
                if (bitmap_bit_p (r, 2 * i + word))
1915
                  {
1916
                    fprintf (file, "%s%d", sep, word);
1917
                    sep = ", ";
1918
                  }
1919
              fprintf (file, ")");
1920
            }
1921
        }
1922
    }
1923
  fprintf (file, "\n");
1924
}
1925
 
1926
 
1927
/* Dump dataflow info.  */
1928
 
1929
void
1930
df_dump (FILE *file)
1931
{
1932
  basic_block bb;
1933
  df_dump_start (file);
1934
 
1935
  FOR_ALL_BB (bb)
1936
    {
1937
      df_print_bb_index (bb, file);
1938
      df_dump_top (bb, file);
1939
      df_dump_bottom (bb, file);
1940
    }
1941
 
1942
  fprintf (file, "\n");
1943
}
1944
 
1945
 
1946
/* Dump dataflow info for df->blocks_to_analyze.  */
1947
 
1948
void
1949
df_dump_region (FILE *file)
1950
{
1951
  if (df->blocks_to_analyze)
1952
    {
1953
      bitmap_iterator bi;
1954
      unsigned int bb_index;
1955
 
1956
      fprintf (file, "\n\nstarting region dump\n");
1957
      df_dump_start (file);
1958
 
1959
      EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1960
        {
1961
          basic_block bb = BASIC_BLOCK (bb_index);
1962
 
1963
          df_print_bb_index (bb, file);
1964
          df_dump_top (bb, file);
1965
          df_dump_bottom (bb, file);
1966
        }
1967
      fprintf (file, "\n");
1968
    }
1969
  else
1970
    df_dump (file);
1971
}
1972
 
1973
 
1974
/* Dump the introductory information for each problem defined.  */
1975
 
1976
void
1977
df_dump_start (FILE *file)
1978
{
1979
  int i;
1980
 
1981
  if (!df || !file)
1982
    return;
1983
 
1984
  fprintf (file, "\n\n%s\n", current_function_name ());
1985
  fprintf (file, "\nDataflow summary:\n");
1986
  if (df->blocks_to_analyze)
1987
    fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n",
1988
             DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ());
1989
 
1990
  for (i = 0; i < df->num_problems_defined; i++)
1991
    {
1992
      struct dataflow *dflow = df->problems_in_order[i];
1993
      if (dflow->computed)
1994
        {
1995
          df_dump_problem_function fun = dflow->problem->dump_start_fun;
1996
          if (fun)
1997
            fun(file);
1998
        }
1999
    }
2000
}
2001
 
2002
 
2003
/* Dump the top of the block information for BB.  */
2004
 
2005
void
2006
df_dump_top (basic_block bb, FILE *file)
2007
{
2008
  int i;
2009
 
2010
  if (!df || !file)
2011
    return;
2012
 
2013
  for (i = 0; i < df->num_problems_defined; i++)
2014
    {
2015
      struct dataflow *dflow = df->problems_in_order[i];
2016
      if (dflow->computed)
2017
        {
2018
          df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
2019
          if (bbfun)
2020
            bbfun (bb, file);
2021
        }
2022
    }
2023
}
2024
 
2025
 
2026
/* Dump the bottom of the block information for BB.  */
2027
 
2028
void
2029
df_dump_bottom (basic_block bb, FILE *file)
2030
{
2031
  int i;
2032
 
2033
  if (!df || !file)
2034
    return;
2035
 
2036
  for (i = 0; i < df->num_problems_defined; i++)
2037
    {
2038
      struct dataflow *dflow = df->problems_in_order[i];
2039
      if (dflow->computed)
2040
        {
2041
          df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
2042
          if (bbfun)
2043
            bbfun (bb, file);
2044
        }
2045
    }
2046
}
2047
 
2048
 
2049
static void
2050
df_ref_dump (df_ref ref, FILE *file)
2051
{
2052
  fprintf (file, "%c%d(%d)",
2053
           DF_REF_REG_DEF_P (ref)
2054
           ? 'd'
2055
           : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
2056
           DF_REF_ID (ref),
2057
           DF_REF_REGNO (ref));
2058
}
2059
 
2060
void
2061
df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file)
2062
{
2063
  fprintf (file, "{ ");
2064
  while (*ref_rec)
2065
    {
2066
      df_ref ref = *ref_rec;
2067
      df_ref_dump (ref, file);
2068
      if (follow_chain)
2069
        df_chain_dump (DF_REF_CHAIN (ref), file);
2070
      ref_rec++;
2071
    }
2072
  fprintf (file, "}");
2073
}
2074
 
2075
 
2076
/* Dump either a ref-def or reg-use chain.  */
2077
 
2078
void
2079
df_regs_chain_dump (df_ref ref,  FILE *file)
2080
{
2081
  fprintf (file, "{ ");
2082
  while (ref)
2083
    {
2084
      df_ref_dump (ref, file);
2085
      ref = DF_REF_NEXT_REG (ref);
2086
    }
2087
  fprintf (file, "}");
2088
}
2089
 
2090
 
2091
static void
2092
df_mws_dump (struct df_mw_hardreg **mws, FILE *file)
2093
{
2094
  while (*mws)
2095
    {
2096
      fprintf (file, "mw %c r[%d..%d]\n",
2097
               (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u',
2098
               (*mws)->start_regno, (*mws)->end_regno);
2099
      mws++;
2100
    }
2101
}
2102
 
2103
 
2104
static void
2105
df_insn_uid_debug (unsigned int uid,
2106
                   bool follow_chain, FILE *file)
2107
{
2108
  fprintf (file, "insn %d luid %d",
2109
           uid, DF_INSN_UID_LUID (uid));
2110
 
2111
  if (DF_INSN_UID_DEFS (uid))
2112
    {
2113
      fprintf (file, " defs ");
2114
      df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file);
2115
    }
2116
 
2117
  if (DF_INSN_UID_USES (uid))
2118
    {
2119
      fprintf (file, " uses ");
2120
      df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file);
2121
    }
2122
 
2123
  if (DF_INSN_UID_EQ_USES (uid))
2124
    {
2125
      fprintf (file, " eq uses ");
2126
      df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file);
2127
    }
2128
 
2129
  if (DF_INSN_UID_MWS (uid))
2130
    {
2131
      fprintf (file, " mws ");
2132
      df_mws_dump (DF_INSN_UID_MWS (uid), file);
2133
    }
2134
  fprintf (file, "\n");
2135
}
2136
 
2137
 
2138
DEBUG_FUNCTION void
2139
df_insn_debug (rtx insn, bool follow_chain, FILE *file)
2140
{
2141
  df_insn_uid_debug (INSN_UID (insn), follow_chain, file);
2142
}
2143
 
2144
DEBUG_FUNCTION void
2145
df_insn_debug_regno (rtx insn, FILE *file)
2146
{
2147
  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2148
 
2149
  fprintf (file, "insn %d bb %d luid %d defs ",
2150
           INSN_UID (insn), BLOCK_FOR_INSN (insn)->index,
2151
           DF_INSN_INFO_LUID (insn_info));
2152
  df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file);
2153
 
2154
  fprintf (file, " uses ");
2155
  df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file);
2156
 
2157
  fprintf (file, " eq_uses ");
2158
  df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file);
2159
  fprintf (file, "\n");
2160
}
2161
 
2162
DEBUG_FUNCTION void
2163
df_regno_debug (unsigned int regno, FILE *file)
2164
{
2165
  fprintf (file, "reg %d defs ", regno);
2166
  df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file);
2167
  fprintf (file, " uses ");
2168
  df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file);
2169
  fprintf (file, " eq_uses ");
2170
  df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file);
2171
  fprintf (file, "\n");
2172
}
2173
 
2174
 
2175
DEBUG_FUNCTION void
2176
df_ref_debug (df_ref ref, FILE *file)
2177
{
2178
  fprintf (file, "%c%d ",
2179
           DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
2180
           DF_REF_ID (ref));
2181
  fprintf (file, "reg %d bb %d insn %d flag %#x type %#x ",
2182
           DF_REF_REGNO (ref),
2183
           DF_REF_BBNO (ref),
2184
           DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref),
2185
           DF_REF_FLAGS (ref),
2186
           DF_REF_TYPE (ref));
2187
  if (DF_REF_LOC (ref))
2188
    {
2189
      if (flag_dump_noaddr)
2190
        fprintf (file, "loc #(#) chain ");
2191
      else
2192
        fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref),
2193
                 (void *)*DF_REF_LOC (ref));
2194
    }
2195
  else
2196
    fprintf (file, "chain ");
2197
  df_chain_dump (DF_REF_CHAIN (ref), file);
2198
  fprintf (file, "\n");
2199
}
2200
 
2201
/* Functions for debugging from GDB.  */
2202
 
2203
DEBUG_FUNCTION void
2204
debug_df_insn (rtx insn)
2205
{
2206
  df_insn_debug (insn, true, stderr);
2207
  debug_rtx (insn);
2208
}
2209
 
2210
 
2211
DEBUG_FUNCTION void
2212
debug_df_reg (rtx reg)
2213
{
2214
  df_regno_debug (REGNO (reg), stderr);
2215
}
2216
 
2217
 
2218
DEBUG_FUNCTION void
2219
debug_df_regno (unsigned int regno)
2220
{
2221
  df_regno_debug (regno, stderr);
2222
}
2223
 
2224
 
2225
DEBUG_FUNCTION void
2226
debug_df_ref (df_ref ref)
2227
{
2228
  df_ref_debug (ref, stderr);
2229
}
2230
 
2231
 
2232
DEBUG_FUNCTION void
2233
debug_df_defno (unsigned int defno)
2234
{
2235
  df_ref_debug (DF_DEFS_GET (defno), stderr);
2236
}
2237
 
2238
 
2239
DEBUG_FUNCTION void
2240
debug_df_useno (unsigned int defno)
2241
{
2242
  df_ref_debug (DF_USES_GET (defno), stderr);
2243
}
2244
 
2245
 
2246
DEBUG_FUNCTION void
2247
debug_df_chain (struct df_link *link)
2248
{
2249
  df_chain_dump (link, stderr);
2250
  fputc ('\n', stderr);
2251
}

powered by: WebSVN 2.1.0

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