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

Subversion Repositories openrisc

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

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Standard problems for dataflow support routines.
2
   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
3
   2008, 2009 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
#include "config.h"
26
#include "system.h"
27
#include "coretypes.h"
28
#include "tm.h"
29
#include "rtl.h"
30
#include "tm_p.h"
31
#include "insn-config.h"
32
#include "recog.h"
33
#include "function.h"
34
#include "regs.h"
35
#include "output.h"
36
#include "alloc-pool.h"
37
#include "flags.h"
38
#include "hard-reg-set.h"
39
#include "basic-block.h"
40
#include "sbitmap.h"
41
#include "bitmap.h"
42
#include "timevar.h"
43
#include "df.h"
44
#include "except.h"
45
#include "dce.h"
46
#include "vecprim.h"
47
 
48
/* Note that turning REG_DEAD_DEBUGGING on will cause
49
   gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
50
   addresses in the dumps.  */
51
#if 0
52
#define REG_DEAD_DEBUGGING
53
#endif
54
 
55
#define DF_SPARSE_THRESHOLD 32
56
 
57
static bitmap seen_in_block = NULL;
58
static bitmap seen_in_insn = NULL;
59
 
60
 
61
/*----------------------------------------------------------------------------
62
   Public functions access functions for the dataflow problems.
63
----------------------------------------------------------------------------*/
64
/* Get the live at out set for BB no matter what problem happens to be
65
   defined.  This function is used by the register allocators who
66
   choose different dataflow problems depending on the optimization
67
   level.  */
68
 
69
bitmap
70
df_get_live_out (basic_block bb)
71
{
72
  gcc_assert (df_lr);
73
 
74
  if (df_live)
75
    return DF_LIVE_OUT (bb);
76
  else
77
    return DF_LR_OUT (bb);
78
}
79
 
80
/* Get the live at in set for BB no matter what problem happens to be
81
   defined.  This function is used by the register allocators who
82
   choose different dataflow problems depending on the optimization
83
   level.  */
84
 
85
bitmap
86
df_get_live_in (basic_block bb)
87
{
88
  gcc_assert (df_lr);
89
 
90
  if (df_live)
91
    return DF_LIVE_IN (bb);
92
  else
93
    return DF_LR_IN (bb);
94
}
95
 
96
/*----------------------------------------------------------------------------
97
   Utility functions.
98
----------------------------------------------------------------------------*/
99
 
100
/* Generic versions to get the void* version of the block info.  Only
101
   used inside the problem instance vectors.  */
102
 
103
/* Grow the bb_info array.  */
104
 
105
void
106
df_grow_bb_info (struct dataflow *dflow)
107
{
108
  unsigned int new_size = last_basic_block + 1;
109
  if (dflow->block_info_size < new_size)
110
    {
111
      new_size += new_size / 4;
112
      dflow->block_info = XRESIZEVEC (void *, dflow->block_info, new_size);
113
      memset (dflow->block_info + dflow->block_info_size, 0,
114
              (new_size - dflow->block_info_size) *sizeof (void *));
115
      dflow->block_info_size = new_size;
116
    }
117
}
118
 
119
/* Dump a def-use or use-def chain for REF to FILE.  */
120
 
121
void
122
df_chain_dump (struct df_link *link, FILE *file)
123
{
124
  fprintf (file, "{ ");
125
  for (; link; link = link->next)
126
    {
127
      fprintf (file, "%c%d(bb %d insn %d) ",
128
               DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
129
               DF_REF_ID (link->ref),
130
               DF_REF_BBNO (link->ref),
131
               DF_REF_IS_ARTIFICIAL (link->ref) ? -1 : DF_REF_INSN_UID (link->ref));
132
    }
133
  fprintf (file, "}");
134
}
135
 
136
 
137
/* Print some basic block info as part of df_dump.  */
138
 
139
void
140
df_print_bb_index (basic_block bb, FILE *file)
141
{
142
  edge e;
143
  edge_iterator ei;
144
 
145
  fprintf (file, "\n( ");
146
    FOR_EACH_EDGE (e, ei, bb->preds)
147
    {
148
      basic_block pred = e->src;
149
      fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
150
    }
151
  fprintf (file, ")->[%d]->( ", bb->index);
152
  FOR_EACH_EDGE (e, ei, bb->succs)
153
    {
154
      basic_block succ = e->dest;
155
      fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
156
    }
157
  fprintf (file, ")\n");
158
}
159
 
160
 
161
/*----------------------------------------------------------------------------
162
   REACHING DEFINITIONS
163
 
164
   Find the locations in the function where each definition site for a
165
   pseudo reaches.  In and out bitvectors are built for each basic
166
   block.  The id field in the ref is used to index into these sets.
167
   See df.h for details.
168
   ----------------------------------------------------------------------------*/
169
 
170
/* This problem plays a large number of games for the sake of
171
   efficiency.
172
 
173
   1) The order of the bits in the bitvectors.  After the scanning
174
   phase, all of the defs are sorted.  All of the defs for the reg 0
175
   are first, followed by all defs for reg 1 and so on.
176
 
177
   2) There are two kill sets, one if the number of defs is less or
178
   equal to DF_SPARSE_THRESHOLD and another if the number of defs is
179
   greater.
180
 
181
   <= : Data is built directly in the kill set.
182
 
183
   > : One level of indirection is used to keep from generating long
184
   strings of 1 bits in the kill sets.  Bitvectors that are indexed
185
   by the regnum are used to represent that there is a killing def
186
   for the register.  The confluence and transfer functions use
187
   these along with the bitmap_clear_range call to remove ranges of
188
   bits without actually generating a knockout vector.
189
 
190
   The kill and sparse_kill and the dense_invalidated_by_call and
191
   sparse_invalidated_by_call both play this game.  */
192
 
193
/* Private data used to compute the solution for this problem.  These
194
   data structures are not accessible outside of this module.  */
195
struct df_rd_problem_data
196
{
197
  /* The set of defs to regs invalidated by call.  */
198
  bitmap sparse_invalidated_by_call;
199
  /* The set of defs to regs invalidate by call for rd.  */
200
  bitmap dense_invalidated_by_call;
201
  /* An obstack for the bitmaps we need for this problem.  */
202
  bitmap_obstack rd_bitmaps;
203
};
204
 
205
/* Set basic block info.  */
206
 
207
static void
208
df_rd_set_bb_info (unsigned int index,
209
                   struct df_rd_bb_info *bb_info)
210
{
211
  gcc_assert (df_rd);
212
  gcc_assert (index < df_rd->block_info_size);
213
  df_rd->block_info[index] = bb_info;
214
}
215
 
216
 
217
/* Free basic block info.  */
218
 
219
static void
220
df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
221
                    void *vbb_info)
222
{
223
  struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
224
  if (bb_info)
225
    {
226
      BITMAP_FREE (bb_info->kill);
227
      BITMAP_FREE (bb_info->sparse_kill);
228
      BITMAP_FREE (bb_info->gen);
229
      BITMAP_FREE (bb_info->in);
230
      BITMAP_FREE (bb_info->out);
231
      pool_free (df_rd->block_pool, bb_info);
232
    }
233
}
234
 
235
 
236
/* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
237
   not touched unless the block is new.  */
238
 
239
static void
240
df_rd_alloc (bitmap all_blocks)
241
{
242
  unsigned int bb_index;
243
  bitmap_iterator bi;
244
  struct df_rd_problem_data *problem_data;
245
 
246
  if (!df_rd->block_pool)
247
    df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
248
                                           sizeof (struct df_rd_bb_info), 50);
249
 
250
  if (df_rd->problem_data)
251
    {
252
      problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
253
      bitmap_clear (problem_data->sparse_invalidated_by_call);
254
      bitmap_clear (problem_data->dense_invalidated_by_call);
255
    }
256
  else
257
    {
258
      problem_data = XNEW (struct df_rd_problem_data);
259
      df_rd->problem_data = problem_data;
260
 
261
      bitmap_obstack_initialize (&problem_data->rd_bitmaps);
262
      problem_data->sparse_invalidated_by_call
263
        = BITMAP_ALLOC (&problem_data->rd_bitmaps);
264
      problem_data->dense_invalidated_by_call
265
        = BITMAP_ALLOC (&problem_data->rd_bitmaps);
266
    }
267
 
268
  df_grow_bb_info (df_rd);
269
 
270
  /* Because of the clustering of all use sites for the same pseudo,
271
     we have to process all of the blocks before doing the
272
     analysis.  */
273
 
274
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
275
    {
276
      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
277
      if (bb_info)
278
        {
279
          bitmap_clear (bb_info->kill);
280
          bitmap_clear (bb_info->sparse_kill);
281
          bitmap_clear (bb_info->gen);
282
        }
283
      else
284
        {
285
          bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
286
          df_rd_set_bb_info (bb_index, bb_info);
287
          bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
288
          bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
289
          bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
290
          bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
291
          bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
292
        }
293
    }
294
  df_rd->optional_p = true;
295
}
296
 
297
 
298
/* Add the effect of the top artificial defs of BB to the reaching definitions
299
   bitmap LOCAL_RD.  */
300
 
301
void
302
df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
303
{
304
  int bb_index = bb->index;
305
  df_ref *def_rec;
306
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
307
    {
308
      df_ref def = *def_rec;
309
      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
310
        {
311
          unsigned int dregno = DF_REF_REGNO (def);
312
          if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
313
            bitmap_clear_range (local_rd,
314
                                DF_DEFS_BEGIN (dregno),
315
                                DF_DEFS_COUNT (dregno));
316
          bitmap_set_bit (local_rd, DF_REF_ID (def));
317
        }
318
    }
319
}
320
 
321
/* Add the effect of the defs of INSN to the reaching definitions bitmap
322
   LOCAL_RD.  */
323
 
324
void
325
df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
326
                         bitmap local_rd)
327
{
328
  unsigned uid = INSN_UID (insn);
329
  df_ref *def_rec;
330
 
331
  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
332
    {
333
      df_ref def = *def_rec;
334
      unsigned int dregno = DF_REF_REGNO (def);
335
      if ((!(df->changeable_flags & DF_NO_HARD_REGS))
336
          || (dregno >= FIRST_PSEUDO_REGISTER))
337
        {
338
          if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
339
            bitmap_clear_range (local_rd,
340
                                DF_DEFS_BEGIN (dregno),
341
                                DF_DEFS_COUNT (dregno));
342
          if (!(DF_REF_FLAGS (def)
343
                & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
344
            bitmap_set_bit (local_rd, DF_REF_ID (def));
345
        }
346
    }
347
}
348
 
349
/* Process a list of DEFs for df_rd_bb_local_compute.  This is a bit
350
   more complicated than just simulating, because we must produce the
351
   gen and kill sets and hence deal with the two possible representations
352
   of kill sets.   */
353
 
354
static void
355
df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
356
                                    df_ref *def_rec,
357
                                    int top_flag)
358
{
359
  while (*def_rec)
360
    {
361
      df_ref def = *def_rec;
362
      if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
363
        {
364
          unsigned int regno = DF_REF_REGNO (def);
365
          unsigned int begin = DF_DEFS_BEGIN (regno);
366
          unsigned int n_defs = DF_DEFS_COUNT (regno);
367
 
368
          if ((!(df->changeable_flags & DF_NO_HARD_REGS))
369
              || (regno >= FIRST_PSEUDO_REGISTER))
370
            {
371
              /* Only the last def(s) for a regno in the block has any
372
                 effect.  */
373
              if (!bitmap_bit_p (seen_in_block, regno))
374
                {
375
                  /* The first def for regno in insn gets to knock out the
376
                     defs from other instructions.  */
377
                  if ((!bitmap_bit_p (seen_in_insn, regno))
378
                      /* If the def is to only part of the reg, it does
379
                         not kill the other defs that reach here.  */
380
                      && (!(DF_REF_FLAGS (def) &
381
                            (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
382
                    {
383
                      if (n_defs > DF_SPARSE_THRESHOLD)
384
                        {
385
                          bitmap_set_bit (bb_info->sparse_kill, regno);
386
                          bitmap_clear_range(bb_info->gen, begin, n_defs);
387
                        }
388
                      else
389
                        {
390
                          bitmap_set_range (bb_info->kill, begin, n_defs);
391
                          bitmap_clear_range (bb_info->gen, begin, n_defs);
392
                        }
393
                    }
394
 
395
                  bitmap_set_bit (seen_in_insn, regno);
396
                  /* All defs for regno in the instruction may be put into
397
                     the gen set.  */
398
                  if (!(DF_REF_FLAGS (def)
399
                        & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
400
                    bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
401
                }
402
            }
403
        }
404
      def_rec++;
405
    }
406
}
407
 
408
/* Compute local reaching def info for basic block BB.  */
409
 
410
static void
411
df_rd_bb_local_compute (unsigned int bb_index)
412
{
413
  basic_block bb = BASIC_BLOCK (bb_index);
414
  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
415
  rtx insn;
416
 
417
  bitmap_clear (seen_in_block);
418
  bitmap_clear (seen_in_insn);
419
 
420
  /* Artificials are only hard regs.  */
421
  if (!(df->changeable_flags & DF_NO_HARD_REGS))
422
    df_rd_bb_local_compute_process_def (bb_info,
423
                                        df_get_artificial_defs (bb_index),
424
                                        0);
425
 
426
  FOR_BB_INSNS_REVERSE (bb, insn)
427
    {
428
      unsigned int uid = INSN_UID (insn);
429
 
430
      if (!INSN_P (insn))
431
        continue;
432
 
433
      df_rd_bb_local_compute_process_def (bb_info,
434
                                          DF_INSN_UID_DEFS (uid), 0);
435
 
436
      /* This complex dance with the two bitmaps is required because
437
         instructions can assign twice to the same pseudo.  This
438
         generally happens with calls that will have one def for the
439
         result and another def for the clobber.  If only one vector
440
         is used and the clobber goes first, the result will be
441
         lost.  */
442
      bitmap_ior_into (seen_in_block, seen_in_insn);
443
      bitmap_clear (seen_in_insn);
444
    }
445
 
446
  /* Process the artificial defs at the top of the block last since we
447
     are going backwards through the block and these are logically at
448
     the start.  */
449
  if (!(df->changeable_flags & DF_NO_HARD_REGS))
450
    df_rd_bb_local_compute_process_def (bb_info,
451
                                        df_get_artificial_defs (bb_index),
452
                                        DF_REF_AT_TOP);
453
}
454
 
455
 
456
/* Compute local reaching def info for each basic block within BLOCKS.  */
457
 
458
static void
459
df_rd_local_compute (bitmap all_blocks)
460
{
461
  unsigned int bb_index;
462
  bitmap_iterator bi;
463
  unsigned int regno;
464
  struct df_rd_problem_data *problem_data
465
    = (struct df_rd_problem_data *) df_rd->problem_data;
466
  bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
467
  bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
468
 
469
  seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
470
  seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
471
 
472
  df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
473
 
474
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
475
    {
476
      df_rd_bb_local_compute (bb_index);
477
    }
478
 
479
  /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
480
  EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)
481
    {
482
      if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
483
        bitmap_set_bit (sparse_invalidated, regno);
484
      else
485
        bitmap_set_range (dense_invalidated,
486
                          DF_DEFS_BEGIN (regno),
487
                          DF_DEFS_COUNT (regno));
488
    }
489
 
490
  BITMAP_FREE (seen_in_block);
491
  BITMAP_FREE (seen_in_insn);
492
}
493
 
494
 
495
/* Initialize the solution bit vectors for problem.  */
496
 
497
static void
498
df_rd_init_solution (bitmap all_blocks)
499
{
500
  unsigned int bb_index;
501
  bitmap_iterator bi;
502
 
503
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
504
    {
505
      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
506
 
507
      bitmap_copy (bb_info->out, bb_info->gen);
508
      bitmap_clear (bb_info->in);
509
    }
510
}
511
 
512
/* In of target gets or of out of source.  */
513
 
514
static void
515
df_rd_confluence_n (edge e)
516
{
517
  bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
518
  bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
519
 
520
  if (e->flags & EDGE_FAKE)
521
    return;
522
 
523
  if (e->flags & EDGE_EH)
524
    {
525
      struct df_rd_problem_data *problem_data
526
        = (struct df_rd_problem_data *) df_rd->problem_data;
527
      bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
528
      bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
529
      bitmap_iterator bi;
530
      unsigned int regno;
531
      bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
532
 
533
      bitmap_copy (tmp, op2);
534
      bitmap_and_compl_into (tmp, dense_invalidated);
535
 
536
      EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
537
        {
538
          bitmap_clear_range (tmp,
539
                              DF_DEFS_BEGIN (regno),
540
                              DF_DEFS_COUNT (regno));
541
        }
542
      bitmap_ior_into (op1, tmp);
543
      BITMAP_FREE (tmp);
544
    }
545
  else
546
    bitmap_ior_into (op1, op2);
547
}
548
 
549
 
550
/* Transfer function.  */
551
 
552
static bool
553
df_rd_transfer_function (int bb_index)
554
{
555
  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
556
  unsigned int regno;
557
  bitmap_iterator bi;
558
  bitmap in = bb_info->in;
559
  bitmap out = bb_info->out;
560
  bitmap gen = bb_info->gen;
561
  bitmap kill = bb_info->kill;
562
  bitmap sparse_kill = bb_info->sparse_kill;
563
 
564
  if (bitmap_empty_p (sparse_kill))
565
    return  bitmap_ior_and_compl (out, gen, in, kill);
566
  else
567
    {
568
      struct df_rd_problem_data *problem_data;
569
      bool changed = false;
570
      bitmap tmp;
571
 
572
      /* Note that TMP is _not_ a temporary bitmap if we end up replacing
573
         OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
574
      problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
575
      tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
576
 
577
      bitmap_copy (tmp, in);
578
      EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
579
        {
580
          bitmap_clear_range (tmp,
581
                              DF_DEFS_BEGIN (regno),
582
                              DF_DEFS_COUNT (regno));
583
        }
584
      bitmap_and_compl_into (tmp, kill);
585
      bitmap_ior_into (tmp, gen);
586
      changed = !bitmap_equal_p (tmp, out);
587
      if (changed)
588
        {
589
          BITMAP_FREE (out);
590
          bb_info->out = tmp;
591
        }
592
      else
593
          BITMAP_FREE (tmp);
594
      return changed;
595
    }
596
}
597
 
598
 
599
/* Free all storage associated with the problem.  */
600
 
601
static void
602
df_rd_free (void)
603
{
604
  struct df_rd_problem_data *problem_data
605
    = (struct df_rd_problem_data *) df_rd->problem_data;
606
 
607
  if (problem_data)
608
    {
609
      free_alloc_pool (df_rd->block_pool);
610
      bitmap_obstack_release (&problem_data->rd_bitmaps);
611
 
612
      df_rd->block_info_size = 0;
613
      free (df_rd->block_info);
614
      free (df_rd->problem_data);
615
    }
616
  free (df_rd);
617
}
618
 
619
 
620
/* Debugging info.  */
621
 
622
static void
623
df_rd_start_dump (FILE *file)
624
{
625
  struct df_rd_problem_data *problem_data
626
    = (struct df_rd_problem_data *) df_rd->problem_data;
627
  unsigned int m = DF_REG_SIZE(df);
628
  unsigned int regno;
629
 
630
  if (!df_rd->block_info)
631
    return;
632
 
633
  fprintf (file, ";; Reaching defs:\n\n");
634
 
635
  fprintf (file, "  sparse invalidated \t");
636
  dump_bitmap (file, problem_data->sparse_invalidated_by_call);
637
  fprintf (file, "  dense invalidated \t");
638
  dump_bitmap (file, problem_data->dense_invalidated_by_call);
639
 
640
  for (regno = 0; regno < m; regno++)
641
    if (DF_DEFS_COUNT (regno))
642
      fprintf (file, "%d[%d,%d] ", regno,
643
               DF_DEFS_BEGIN (regno),
644
               DF_DEFS_COUNT (regno));
645
  fprintf (file, "\n");
646
 
647
}
648
 
649
 
650
/* Debugging info at top of bb.  */
651
 
652
static void
653
df_rd_top_dump (basic_block bb, FILE *file)
654
{
655
  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
656
  if (!bb_info || !bb_info->in)
657
    return;
658
 
659
  fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
660
  dump_bitmap (file, bb_info->in);
661
  fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
662
  dump_bitmap (file, bb_info->gen);
663
  fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
664
  dump_bitmap (file, bb_info->kill);
665
}
666
 
667
 
668
/* Debugging info at top of bb.  */
669
 
670
static void
671
df_rd_bottom_dump (basic_block bb, FILE *file)
672
{
673
  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
674
  if (!bb_info || !bb_info->out)
675
    return;
676
 
677
  fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
678
  dump_bitmap (file, bb_info->out);
679
}
680
 
681
/* All of the information associated with every instance of the problem.  */
682
 
683
static struct df_problem problem_RD =
684
{
685
  DF_RD,                      /* Problem id.  */
686
  DF_FORWARD,                 /* Direction.  */
687
  df_rd_alloc,                /* Allocate the problem specific data.  */
688
  NULL,                       /* Reset global information.  */
689
  df_rd_free_bb_info,         /* Free basic block info.  */
690
  df_rd_local_compute,        /* Local compute function.  */
691
  df_rd_init_solution,        /* Init the solution specific data.  */
692
  df_worklist_dataflow,       /* Worklist solver.  */
693
  NULL,                       /* Confluence operator 0.  */
694
  df_rd_confluence_n,         /* Confluence operator n.  */
695
  df_rd_transfer_function,    /* Transfer function.  */
696
  NULL,                       /* Finalize function.  */
697
  df_rd_free,                 /* Free all of the problem information.  */
698
  df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
699
  df_rd_start_dump,           /* Debugging.  */
700
  df_rd_top_dump,             /* Debugging start block.  */
701
  df_rd_bottom_dump,          /* Debugging end block.  */
702
  NULL,                       /* Incremental solution verify start.  */
703
  NULL,                       /* Incremental solution verify end.  */
704
  NULL,                       /* Dependent problem.  */
705
  TV_DF_RD,                   /* Timing variable.  */
706
  true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
707
};
708
 
709
 
710
 
711
/* Create a new RD instance and add it to the existing instance
712
   of DF.  */
713
 
714
void
715
df_rd_add_problem (void)
716
{
717
  df_add_problem (&problem_RD);
718
}
719
 
720
 
721
 
722
/*----------------------------------------------------------------------------
723
   LIVE REGISTERS
724
 
725
   Find the locations in the function where any use of a pseudo can
726
   reach in the backwards direction.  In and out bitvectors are built
727
   for each basic block.  The regno is used to index into these sets.
728
   See df.h for details.
729
   ----------------------------------------------------------------------------*/
730
 
731
/* Private data used to verify the solution for this problem.  */
732
struct df_lr_problem_data
733
{
734
  bitmap *in;
735
  bitmap *out;
736
};
737
 
738
 
739
/* Set basic block info.  */
740
 
741
static void
742
df_lr_set_bb_info (unsigned int index,
743
                   struct df_lr_bb_info *bb_info)
744
{
745
  gcc_assert (df_lr);
746
  gcc_assert (index < df_lr->block_info_size);
747
  df_lr->block_info[index] = bb_info;
748
}
749
 
750
 
751
/* Free basic block info.  */
752
 
753
static void
754
df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
755
                    void *vbb_info)
756
{
757
  struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
758
  if (bb_info)
759
    {
760
      BITMAP_FREE (bb_info->use);
761
      BITMAP_FREE (bb_info->def);
762
      BITMAP_FREE (bb_info->in);
763
      BITMAP_FREE (bb_info->out);
764
      pool_free (df_lr->block_pool, bb_info);
765
    }
766
}
767
 
768
 
769
/* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
770
   not touched unless the block is new.  */
771
 
772
static void
773
df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
774
{
775
  unsigned int bb_index;
776
  bitmap_iterator bi;
777
 
778
  if (!df_lr->block_pool)
779
    df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
780
                                           sizeof (struct df_lr_bb_info), 50);
781
 
782
  df_grow_bb_info (df_lr);
783
 
784
  EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
785
    {
786
      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
787
      if (bb_info)
788
        {
789
          bitmap_clear (bb_info->def);
790
          bitmap_clear (bb_info->use);
791
        }
792
      else
793
        {
794
          bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
795
          df_lr_set_bb_info (bb_index, bb_info);
796
          bb_info->use = BITMAP_ALLOC (NULL);
797
          bb_info->def = BITMAP_ALLOC (NULL);
798
          bb_info->in = BITMAP_ALLOC (NULL);
799
          bb_info->out = BITMAP_ALLOC (NULL);
800
        }
801
    }
802
 
803
  df_lr->optional_p = false;
804
}
805
 
806
 
807
/* Reset the global solution for recalculation.  */
808
 
809
static void
810
df_lr_reset (bitmap all_blocks)
811
{
812
  unsigned int bb_index;
813
  bitmap_iterator bi;
814
 
815
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
816
    {
817
      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
818
      gcc_assert (bb_info);
819
      bitmap_clear (bb_info->in);
820
      bitmap_clear (bb_info->out);
821
    }
822
}
823
 
824
 
825
/* Compute local live register info for basic block BB.  */
826
 
827
static void
828
df_lr_bb_local_compute (unsigned int bb_index)
829
{
830
  basic_block bb = BASIC_BLOCK (bb_index);
831
  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
832
  rtx insn;
833
  df_ref *def_rec;
834
  df_ref *use_rec;
835
 
836
  /* Process the registers set in an exception handler.  */
837
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
838
    {
839
      df_ref def = *def_rec;
840
      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
841
        {
842
          unsigned int dregno = DF_REF_REGNO (def);
843
          bitmap_set_bit (bb_info->def, dregno);
844
          bitmap_clear_bit (bb_info->use, dregno);
845
        }
846
    }
847
 
848
  /* Process the hardware registers that are always live.  */
849
  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
850
    {
851
      df_ref use = *use_rec;
852
      /* Add use to set of uses in this BB.  */
853
      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
854
        bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
855
    }
856
 
857
  FOR_BB_INSNS_REVERSE (bb, insn)
858
    {
859
      unsigned int uid = INSN_UID (insn);
860
 
861
      if (!NONDEBUG_INSN_P (insn))
862
        continue;
863
 
864
      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
865
        {
866
          df_ref def = *def_rec;
867
          /* If the def is to only part of the reg, it does
868
             not kill the other defs that reach here.  */
869
          if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
870
            {
871
              unsigned int dregno = DF_REF_REGNO (def);
872
              bitmap_set_bit (bb_info->def, dregno);
873
              bitmap_clear_bit (bb_info->use, dregno);
874
            }
875
        }
876
 
877
      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
878
        {
879
          df_ref use = *use_rec;
880
          /* Add use to set of uses in this BB.  */
881
          bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
882
        }
883
    }
884
 
885
  /* Process the registers set in an exception handler or the hard
886
     frame pointer if this block is the target of a non local
887
     goto.  */
888
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
889
    {
890
      df_ref def = *def_rec;
891
      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
892
        {
893
          unsigned int dregno = DF_REF_REGNO (def);
894
          bitmap_set_bit (bb_info->def, dregno);
895
          bitmap_clear_bit (bb_info->use, dregno);
896
        }
897
    }
898
 
899
#ifdef EH_USES
900
  /* Process the uses that are live into an exception handler.  */
901
  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
902
    {
903
      df_ref use = *use_rec;
904
      /* Add use to set of uses in this BB.  */
905
      if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
906
        bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
907
    }
908
#endif
909
 
910
  /* If the df_live problem is not defined, such as at -O0 and -O1, we
911
     still need to keep the luids up to date.  This is normally done
912
     in the df_live problem since this problem has a forwards
913
     scan.  */
914
  if (!df_live)
915
    df_recompute_luids (bb);
916
}
917
 
918
 
919
/* Compute local live register info for each basic block within BLOCKS.  */
920
 
921
static void
922
df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
923
{
924
  unsigned int bb_index;
925
  bitmap_iterator bi;
926
 
927
  bitmap_clear (df->hardware_regs_used);
928
 
929
  /* The all-important stack pointer must always be live.  */
930
  bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
931
 
932
  /* Before reload, there are a few registers that must be forced
933
     live everywhere -- which might not already be the case for
934
     blocks within infinite loops.  */
935
  if (!reload_completed)
936
    {
937
      /* Any reference to any pseudo before reload is a potential
938
         reference of the frame pointer.  */
939
      bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
940
 
941
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
942
      /* Pseudos with argument area equivalences may require
943
         reloading via the argument pointer.  */
944
      if (fixed_regs[ARG_POINTER_REGNUM])
945
        bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
946
#endif
947
 
948
      /* Any constant, or pseudo with constant equivalences, may
949
         require reloading from memory using the pic register.  */
950
      if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
951
          && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
952
        bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
953
    }
954
 
955
  EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
956
    {
957
      if (bb_index == EXIT_BLOCK)
958
        {
959
          /* The exit block is special for this problem and its bits are
960
             computed from thin air.  */
961
          struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
962
          bitmap_copy (bb_info->use, df->exit_block_uses);
963
        }
964
      else
965
        df_lr_bb_local_compute (bb_index);
966
    }
967
 
968
  bitmap_clear (df_lr->out_of_date_transfer_functions);
969
}
970
 
971
 
972
/* Initialize the solution vectors.  */
973
 
974
static void
975
df_lr_init (bitmap all_blocks)
976
{
977
  unsigned int bb_index;
978
  bitmap_iterator bi;
979
 
980
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
981
    {
982
      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
983
      bitmap_copy (bb_info->in, bb_info->use);
984
      bitmap_clear (bb_info->out);
985
    }
986
}
987
 
988
 
989
/* Confluence function that processes infinite loops.  This might be a
990
   noreturn function that throws.  And even if it isn't, getting the
991
   unwind info right helps debugging.  */
992
static void
993
df_lr_confluence_0 (basic_block bb)
994
{
995
  bitmap op1 = df_lr_get_bb_info (bb->index)->out;
996
  if (bb != EXIT_BLOCK_PTR)
997
    bitmap_copy (op1, df->hardware_regs_used);
998
}
999
 
1000
 
1001
/* Confluence function that ignores fake edges.  */
1002
 
1003
static void
1004
df_lr_confluence_n (edge e)
1005
{
1006
  bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
1007
  bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
1008
 
1009
  /* Call-clobbered registers die across exception and call edges.  */
1010
  /* ??? Abnormal call edges ignored for the moment, as this gets
1011
     confused by sibling call edges, which crashes reg-stack.  */
1012
  if (e->flags & EDGE_EH)
1013
    bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
1014
  else
1015
    bitmap_ior_into (op1, op2);
1016
 
1017
  bitmap_ior_into (op1, df->hardware_regs_used);
1018
}
1019
 
1020
 
1021
/* Transfer function.  */
1022
 
1023
static bool
1024
df_lr_transfer_function (int bb_index)
1025
{
1026
  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1027
  bitmap in = bb_info->in;
1028
  bitmap out = bb_info->out;
1029
  bitmap use = bb_info->use;
1030
  bitmap def = bb_info->def;
1031
 
1032
  return bitmap_ior_and_compl (in, use, out, def);
1033
}
1034
 
1035
 
1036
/* Run the fast dce as a side effect of building LR.  */
1037
 
1038
static void
1039
df_lr_finalize (bitmap all_blocks)
1040
{
1041
  df_lr->solutions_dirty = false;
1042
  if (df->changeable_flags & DF_LR_RUN_DCE)
1043
    {
1044
      run_fast_df_dce ();
1045
 
1046
      /* If dce deletes some instructions, we need to recompute the lr
1047
         solution before proceeding further.  The problem is that fast
1048
         dce is a pessimestic dataflow algorithm.  In the case where
1049
         it deletes a statement S inside of a loop, the uses inside of
1050
         S may not be deleted from the dataflow solution because they
1051
         were carried around the loop.  While it is conservatively
1052
         correct to leave these extra bits, the standards of df
1053
         require that we maintain the best possible (least fixed
1054
         point) solution.  The only way to do that is to redo the
1055
         iteration from the beginning.  See PR35805 for an
1056
         example.  */
1057
      if (df_lr->solutions_dirty)
1058
        {
1059
          df_clear_flags (DF_LR_RUN_DCE);
1060
          df_lr_alloc (all_blocks);
1061
          df_lr_local_compute (all_blocks);
1062
          df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1063
          df_lr_finalize (all_blocks);
1064
          df_set_flags (DF_LR_RUN_DCE);
1065
        }
1066
    }
1067
}
1068
 
1069
 
1070
/* Free all storage associated with the problem.  */
1071
 
1072
static void
1073
df_lr_free (void)
1074
{
1075
  if (df_lr->block_info)
1076
    {
1077
      unsigned int i;
1078
      for (i = 0; i < df_lr->block_info_size; i++)
1079
        {
1080
          struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1081
          if (bb_info)
1082
            {
1083
              BITMAP_FREE (bb_info->use);
1084
              BITMAP_FREE (bb_info->def);
1085
              BITMAP_FREE (bb_info->in);
1086
              BITMAP_FREE (bb_info->out);
1087
            }
1088
        }
1089
      free_alloc_pool (df_lr->block_pool);
1090
 
1091
      df_lr->block_info_size = 0;
1092
      free (df_lr->block_info);
1093
    }
1094
 
1095
  BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1096
  free (df_lr);
1097
}
1098
 
1099
 
1100
/* Debugging info at top of bb.  */
1101
 
1102
static void
1103
df_lr_top_dump (basic_block bb, FILE *file)
1104
{
1105
  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1106
  struct df_lr_problem_data *problem_data;
1107
  if (!bb_info || !bb_info->in)
1108
    return;
1109
 
1110
  fprintf (file, ";; lr  in  \t");
1111
  df_print_regset (file, bb_info->in);
1112
  if (df_lr->problem_data)
1113
    {
1114
      problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1115
      fprintf (file, ";;  old in  \t");
1116
      df_print_regset (file, problem_data->in[bb->index]);
1117
    }
1118
  fprintf (file, ";; lr  use \t");
1119
  df_print_regset (file, bb_info->use);
1120
  fprintf (file, ";; lr  def \t");
1121
  df_print_regset (file, bb_info->def);
1122
}
1123
 
1124
 
1125
/* Debugging info at bottom of bb.  */
1126
 
1127
static void
1128
df_lr_bottom_dump (basic_block bb, FILE *file)
1129
{
1130
  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1131
  struct df_lr_problem_data *problem_data;
1132
  if (!bb_info || !bb_info->out)
1133
    return;
1134
 
1135
  fprintf (file, ";; lr  out \t");
1136
  df_print_regset (file, bb_info->out);
1137
  if (df_lr->problem_data)
1138
    {
1139
      problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1140
      fprintf (file, ";;  old out  \t");
1141
      df_print_regset (file, problem_data->out[bb->index]);
1142
    }
1143
}
1144
 
1145
 
1146
/* Build the datastructure to verify that the solution to the dataflow
1147
   equations is not dirty.  */
1148
 
1149
static void
1150
df_lr_verify_solution_start (void)
1151
{
1152
  basic_block bb;
1153
  struct df_lr_problem_data *problem_data;
1154
  if (df_lr->solutions_dirty)
1155
    {
1156
      df_lr->problem_data = NULL;
1157
      return;
1158
    }
1159
 
1160
  /* Set it true so that the solution is recomputed.  */
1161
  df_lr->solutions_dirty = true;
1162
 
1163
  problem_data = XNEW (struct df_lr_problem_data);
1164
  df_lr->problem_data = problem_data;
1165
  problem_data->in = XNEWVEC (bitmap, last_basic_block);
1166
  problem_data->out = XNEWVEC (bitmap, last_basic_block);
1167
 
1168
  FOR_ALL_BB (bb)
1169
    {
1170
      problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1171
      problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1172
      bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1173
      bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1174
    }
1175
}
1176
 
1177
 
1178
/* Compare the saved datastructure and the new solution to the dataflow
1179
   equations.  */
1180
 
1181
static void
1182
df_lr_verify_solution_end (void)
1183
{
1184
  struct df_lr_problem_data *problem_data;
1185
  basic_block bb;
1186
 
1187
  if (df_lr->problem_data == NULL)
1188
    return;
1189
 
1190
  problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1191
 
1192
  if (df_lr->solutions_dirty)
1193
    /* Do not check if the solution is still dirty.  See the comment
1194
       in df_lr_finalize for details.  */
1195
    df_lr->solutions_dirty = false;
1196
  else
1197
    FOR_ALL_BB (bb)
1198
      {
1199
        if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1200
            || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1201
          {
1202
            /*df_dump (stderr);*/
1203
            gcc_unreachable ();
1204
          }
1205
      }
1206
 
1207
  /* Cannot delete them immediately because you may want to dump them
1208
     if the comparison fails.  */
1209
  FOR_ALL_BB (bb)
1210
    {
1211
      BITMAP_FREE (problem_data->in[bb->index]);
1212
      BITMAP_FREE (problem_data->out[bb->index]);
1213
    }
1214
 
1215
  free (problem_data->in);
1216
  free (problem_data->out);
1217
  free (problem_data);
1218
  df_lr->problem_data = NULL;
1219
}
1220
 
1221
 
1222
/* All of the information associated with every instance of the problem.  */
1223
 
1224
static struct df_problem problem_LR =
1225
{
1226
  DF_LR,                      /* Problem id.  */
1227
  DF_BACKWARD,                /* Direction.  */
1228
  df_lr_alloc,                /* Allocate the problem specific data.  */
1229
  df_lr_reset,                /* Reset global information.  */
1230
  df_lr_free_bb_info,         /* Free basic block info.  */
1231
  df_lr_local_compute,        /* Local compute function.  */
1232
  df_lr_init,                 /* Init the solution specific data.  */
1233
  df_worklist_dataflow,       /* Worklist solver.  */
1234
  df_lr_confluence_0,         /* Confluence operator 0.  */
1235
  df_lr_confluence_n,         /* Confluence operator n.  */
1236
  df_lr_transfer_function,    /* Transfer function.  */
1237
  df_lr_finalize,             /* Finalize function.  */
1238
  df_lr_free,                 /* Free all of the problem information.  */
1239
  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
1240
  NULL,                       /* Debugging.  */
1241
  df_lr_top_dump,             /* Debugging start block.  */
1242
  df_lr_bottom_dump,          /* Debugging end block.  */
1243
  df_lr_verify_solution_start,/* Incremental solution verify start.  */
1244
  df_lr_verify_solution_end,  /* Incremental solution verify end.  */
1245
  NULL,                       /* Dependent problem.  */
1246
  TV_DF_LR,                   /* Timing variable.  */
1247
  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
1248
};
1249
 
1250
 
1251
/* Create a new DATAFLOW instance and add it to an existing instance
1252
   of DF.  The returned structure is what is used to get at the
1253
   solution.  */
1254
 
1255
void
1256
df_lr_add_problem (void)
1257
{
1258
  df_add_problem (&problem_LR);
1259
  /* These will be initialized when df_scan_blocks processes each
1260
     block.  */
1261
  df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1262
}
1263
 
1264
 
1265
/* Verify that all of the lr related info is consistent and
1266
   correct.  */
1267
 
1268
void
1269
df_lr_verify_transfer_functions (void)
1270
{
1271
  basic_block bb;
1272
  bitmap saved_def;
1273
  bitmap saved_use;
1274
  bitmap saved_adef;
1275
  bitmap saved_ause;
1276
  bitmap all_blocks;
1277
 
1278
  if (!df)
1279
    return;
1280
 
1281
  saved_def = BITMAP_ALLOC (NULL);
1282
  saved_use = BITMAP_ALLOC (NULL);
1283
  saved_adef = BITMAP_ALLOC (NULL);
1284
  saved_ause = BITMAP_ALLOC (NULL);
1285
  all_blocks = BITMAP_ALLOC (NULL);
1286
 
1287
  FOR_ALL_BB (bb)
1288
    {
1289
      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1290
      bitmap_set_bit (all_blocks, bb->index);
1291
 
1292
      if (bb_info)
1293
        {
1294
          /* Make a copy of the transfer functions and then compute
1295
             new ones to see if the transfer functions have
1296
             changed.  */
1297
          if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1298
                             bb->index))
1299
            {
1300
              bitmap_copy (saved_def, bb_info->def);
1301
              bitmap_copy (saved_use, bb_info->use);
1302
              bitmap_clear (bb_info->def);
1303
              bitmap_clear (bb_info->use);
1304
 
1305
              df_lr_bb_local_compute (bb->index);
1306
              gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1307
              gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1308
            }
1309
        }
1310
      else
1311
        {
1312
          /* If we do not have basic block info, the block must be in
1313
             the list of dirty blocks or else some one has added a
1314
             block behind our backs. */
1315
          gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1316
                                    bb->index));
1317
        }
1318
      /* Make sure no one created a block without following
1319
         procedures.  */
1320
      gcc_assert (df_scan_get_bb_info (bb->index));
1321
    }
1322
 
1323
  /* Make sure there are no dirty bits in blocks that have been deleted.  */
1324
  gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1325
                                         all_blocks));
1326
 
1327
  BITMAP_FREE (saved_def);
1328
  BITMAP_FREE (saved_use);
1329
  BITMAP_FREE (saved_adef);
1330
  BITMAP_FREE (saved_ause);
1331
  BITMAP_FREE (all_blocks);
1332
}
1333
 
1334
 
1335
 
1336
/*----------------------------------------------------------------------------
1337
   LIVE AND MUST-INITIALIZED REGISTERS.
1338
 
1339
   This problem first computes the IN and OUT bitvectors for the
1340
   must-initialized registers problems, which is a forward problem.
1341
   It gives the set of registers for which we MUST have an available
1342
   definition on any path from the entry block to the entry/exit of
1343
   a basic block.  Sets generate a definition, while clobbers kill
1344
   a definition.
1345
 
1346
   In and out bitvectors are built for each basic block and are indexed by
1347
   regnum (see df.h for details).  In and out bitvectors in struct
1348
   df_live_bb_info actually refers to the must-initialized problem;
1349
 
1350
   Then, the in and out sets for the LIVE problem itself are computed.
1351
   These are the logical AND of the IN and OUT sets from the LR problem
1352
   and the must-initialized problem.
1353
----------------------------------------------------------------------------*/
1354
 
1355
/* Private data used to verify the solution for this problem.  */
1356
struct df_live_problem_data
1357
{
1358
  bitmap *in;
1359
  bitmap *out;
1360
};
1361
 
1362
/* Scratch var used by transfer functions.  This is used to implement
1363
   an optimization to reduce the amount of space used to compute the
1364
   combined lr and live analysis.  */
1365
static bitmap df_live_scratch;
1366
 
1367
/* Set basic block info.  */
1368
 
1369
static void
1370
df_live_set_bb_info (unsigned int index,
1371
                   struct df_live_bb_info *bb_info)
1372
{
1373
  gcc_assert (df_live);
1374
  gcc_assert (index < df_live->block_info_size);
1375
  df_live->block_info[index] = bb_info;
1376
}
1377
 
1378
 
1379
/* Free basic block info.  */
1380
 
1381
static void
1382
df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1383
                    void *vbb_info)
1384
{
1385
  struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1386
  if (bb_info)
1387
    {
1388
      BITMAP_FREE (bb_info->gen);
1389
      BITMAP_FREE (bb_info->kill);
1390
      BITMAP_FREE (bb_info->in);
1391
      BITMAP_FREE (bb_info->out);
1392
      pool_free (df_live->block_pool, bb_info);
1393
    }
1394
}
1395
 
1396
 
1397
/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1398
   not touched unless the block is new.  */
1399
 
1400
static void
1401
df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1402
{
1403
  unsigned int bb_index;
1404
  bitmap_iterator bi;
1405
 
1406
  if (!df_live->block_pool)
1407
    df_live->block_pool = create_alloc_pool ("df_live_block pool",
1408
                                           sizeof (struct df_live_bb_info), 100);
1409
  if (!df_live_scratch)
1410
    df_live_scratch = BITMAP_ALLOC (NULL);
1411
 
1412
  df_grow_bb_info (df_live);
1413
 
1414
  EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1415
    {
1416
      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1417
      if (bb_info)
1418
        {
1419
          bitmap_clear (bb_info->kill);
1420
          bitmap_clear (bb_info->gen);
1421
        }
1422
      else
1423
        {
1424
          bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1425
          df_live_set_bb_info (bb_index, bb_info);
1426
          bb_info->kill = BITMAP_ALLOC (NULL);
1427
          bb_info->gen = BITMAP_ALLOC (NULL);
1428
          bb_info->in = BITMAP_ALLOC (NULL);
1429
          bb_info->out = BITMAP_ALLOC (NULL);
1430
        }
1431
    }
1432
  df_live->optional_p = (optimize <= 1);
1433
}
1434
 
1435
 
1436
/* Reset the global solution for recalculation.  */
1437
 
1438
static void
1439
df_live_reset (bitmap all_blocks)
1440
{
1441
  unsigned int bb_index;
1442
  bitmap_iterator bi;
1443
 
1444
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1445
    {
1446
      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1447
      gcc_assert (bb_info);
1448
      bitmap_clear (bb_info->in);
1449
      bitmap_clear (bb_info->out);
1450
    }
1451
}
1452
 
1453
 
1454
/* Compute local uninitialized register info for basic block BB.  */
1455
 
1456
static void
1457
df_live_bb_local_compute (unsigned int bb_index)
1458
{
1459
  basic_block bb = BASIC_BLOCK (bb_index);
1460
  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1461
  rtx insn;
1462
  df_ref *def_rec;
1463
  int luid = 0;
1464
 
1465
  FOR_BB_INSNS (bb, insn)
1466
    {
1467
      unsigned int uid = INSN_UID (insn);
1468
      struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1469
 
1470
      /* Inserting labels does not always trigger the incremental
1471
         rescanning.  */
1472
      if (!insn_info)
1473
        {
1474
          gcc_assert (!INSN_P (insn));
1475
          insn_info = df_insn_create_insn_record (insn);
1476
        }
1477
 
1478
      DF_INSN_INFO_LUID (insn_info) = luid;
1479
      if (!INSN_P (insn))
1480
        continue;
1481
 
1482
      luid++;
1483
      for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
1484
        {
1485
          df_ref def = *def_rec;
1486
          unsigned int regno = DF_REF_REGNO (def);
1487
 
1488
          if (DF_REF_FLAGS_IS_SET (def,
1489
                                   DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1490
            /* All partial or conditional def
1491
               seen are included in the gen set. */
1492
            bitmap_set_bit (bb_info->gen, regno);
1493
          else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1494
            /* Only must clobbers for the entire reg destroy the
1495
               value.  */
1496
            bitmap_set_bit (bb_info->kill, regno);
1497
          else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1498
            bitmap_set_bit (bb_info->gen, regno);
1499
        }
1500
    }
1501
 
1502
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1503
    {
1504
      df_ref def = *def_rec;
1505
      bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1506
    }
1507
}
1508
 
1509
 
1510
/* Compute local uninitialized register info.  */
1511
 
1512
static void
1513
df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1514
{
1515
  unsigned int bb_index;
1516
  bitmap_iterator bi;
1517
 
1518
  df_grow_insn_info ();
1519
 
1520
  EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1521
                            0, bb_index, bi)
1522
    {
1523
      df_live_bb_local_compute (bb_index);
1524
    }
1525
 
1526
  bitmap_clear (df_live->out_of_date_transfer_functions);
1527
}
1528
 
1529
 
1530
/* Initialize the solution vectors.  */
1531
 
1532
static void
1533
df_live_init (bitmap all_blocks)
1534
{
1535
  unsigned int bb_index;
1536
  bitmap_iterator bi;
1537
 
1538
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1539
    {
1540
      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1541
      struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1542
 
1543
      /* No register may reach a location where it is not used.  Thus
1544
         we trim the rr result to the places where it is used.  */
1545
      bitmap_and (bb_info->out, bb_info->gen, bb_lr_info->out);
1546
      bitmap_clear (bb_info->in);
1547
    }
1548
}
1549
 
1550
/* Forward confluence function that ignores fake edges.  */
1551
 
1552
static void
1553
df_live_confluence_n (edge e)
1554
{
1555
  bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
1556
  bitmap op2 = df_live_get_bb_info (e->src->index)->out;
1557
 
1558
  if (e->flags & EDGE_FAKE)
1559
    return;
1560
 
1561
  bitmap_ior_into (op1, op2);
1562
}
1563
 
1564
 
1565
/* Transfer function for the forwards must-initialized problem.  */
1566
 
1567
static bool
1568
df_live_transfer_function (int bb_index)
1569
{
1570
  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1571
  struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1572
  bitmap in = bb_info->in;
1573
  bitmap out = bb_info->out;
1574
  bitmap gen = bb_info->gen;
1575
  bitmap kill = bb_info->kill;
1576
 
1577
  /* We need to use a scratch set here so that the value returned from this
1578
     function invocation properly reflects whether the sets changed in a
1579
     significant way; i.e. not just because the lr set was anded in.  */
1580
  bitmap_and (df_live_scratch, gen, bb_lr_info->out);
1581
  /* No register may reach a location where it is not used.  Thus
1582
     we trim the rr result to the places where it is used.  */
1583
  bitmap_and_into (in, bb_lr_info->in);
1584
 
1585
  return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
1586
}
1587
 
1588
 
1589
/* And the LR info with the must-initialized registers, to produce the LIVE info.  */
1590
 
1591
static void
1592
df_live_finalize (bitmap all_blocks)
1593
{
1594
 
1595
  if (df_live->solutions_dirty)
1596
    {
1597
      bitmap_iterator bi;
1598
      unsigned int bb_index;
1599
 
1600
      EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1601
        {
1602
          struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1603
          struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1604
 
1605
          /* No register may reach a location where it is not used.  Thus
1606
             we trim the rr result to the places where it is used.  */
1607
          bitmap_and_into (bb_live_info->in, bb_lr_info->in);
1608
          bitmap_and_into (bb_live_info->out, bb_lr_info->out);
1609
        }
1610
 
1611
      df_live->solutions_dirty = false;
1612
    }
1613
}
1614
 
1615
 
1616
/* Free all storage associated with the problem.  */
1617
 
1618
static void
1619
df_live_free (void)
1620
{
1621
  if (df_live->block_info)
1622
    {
1623
      unsigned int i;
1624
 
1625
      for (i = 0; i < df_live->block_info_size; i++)
1626
        {
1627
          struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1628
          if (bb_info)
1629
            {
1630
              BITMAP_FREE (bb_info->gen);
1631
              BITMAP_FREE (bb_info->kill);
1632
              BITMAP_FREE (bb_info->in);
1633
              BITMAP_FREE (bb_info->out);
1634
            }
1635
        }
1636
 
1637
      free_alloc_pool (df_live->block_pool);
1638
      df_live->block_info_size = 0;
1639
      free (df_live->block_info);
1640
 
1641
      if (df_live_scratch)
1642
        BITMAP_FREE (df_live_scratch);
1643
    }
1644
  BITMAP_FREE (df_live->out_of_date_transfer_functions);
1645
  free (df_live);
1646
}
1647
 
1648
 
1649
/* Debugging info at top of bb.  */
1650
 
1651
static void
1652
df_live_top_dump (basic_block bb, FILE *file)
1653
{
1654
  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1655
  struct df_live_problem_data *problem_data;
1656
 
1657
  if (!bb_info || !bb_info->in)
1658
    return;
1659
 
1660
  fprintf (file, ";; live  in  \t");
1661
  df_print_regset (file, bb_info->in);
1662
  if (df_live->problem_data)
1663
    {
1664
      problem_data = (struct df_live_problem_data *)df_live->problem_data;
1665
      fprintf (file, ";;  old in  \t");
1666
      df_print_regset (file, problem_data->in[bb->index]);
1667
    }
1668
  fprintf (file, ";; live  gen \t");
1669
  df_print_regset (file, bb_info->gen);
1670
  fprintf (file, ";; live  kill\t");
1671
  df_print_regset (file, bb_info->kill);
1672
}
1673
 
1674
 
1675
/* Debugging info at bottom of bb.  */
1676
 
1677
static void
1678
df_live_bottom_dump (basic_block bb, FILE *file)
1679
{
1680
  struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1681
  struct df_live_problem_data *problem_data;
1682
 
1683
  if (!bb_info || !bb_info->out)
1684
    return;
1685
 
1686
  fprintf (file, ";; live  out \t");
1687
  df_print_regset (file, bb_info->out);
1688
  if (df_live->problem_data)
1689
    {
1690
      problem_data = (struct df_live_problem_data *)df_live->problem_data;
1691
      fprintf (file, ";;  old out  \t");
1692
      df_print_regset (file, problem_data->out[bb->index]);
1693
    }
1694
}
1695
 
1696
 
1697
/* Build the datastructure to verify that the solution to the dataflow
1698
   equations is not dirty.  */
1699
 
1700
static void
1701
df_live_verify_solution_start (void)
1702
{
1703
  basic_block bb;
1704
  struct df_live_problem_data *problem_data;
1705
  if (df_live->solutions_dirty)
1706
    {
1707
      df_live->problem_data = NULL;
1708
      return;
1709
    }
1710
 
1711
  /* Set it true so that the solution is recomputed.  */
1712
  df_live->solutions_dirty = true;
1713
 
1714
  problem_data = XNEW (struct df_live_problem_data);
1715
  df_live->problem_data = problem_data;
1716
  problem_data->in = XNEWVEC (bitmap, last_basic_block);
1717
  problem_data->out = XNEWVEC (bitmap, last_basic_block);
1718
 
1719
  FOR_ALL_BB (bb)
1720
    {
1721
      problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1722
      problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1723
      bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
1724
      bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
1725
    }
1726
}
1727
 
1728
 
1729
/* Compare the saved datastructure and the new solution to the dataflow
1730
   equations.  */
1731
 
1732
static void
1733
df_live_verify_solution_end (void)
1734
{
1735
  struct df_live_problem_data *problem_data;
1736
  basic_block bb;
1737
 
1738
  if (df_live->problem_data == NULL)
1739
    return;
1740
 
1741
  problem_data = (struct df_live_problem_data *)df_live->problem_data;
1742
 
1743
  FOR_ALL_BB (bb)
1744
    {
1745
      if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
1746
          || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1747
        {
1748
          /*df_dump (stderr);*/
1749
          gcc_unreachable ();
1750
        }
1751
    }
1752
 
1753
  /* Cannot delete them immediately because you may want to dump them
1754
     if the comparison fails.  */
1755
  FOR_ALL_BB (bb)
1756
    {
1757
      BITMAP_FREE (problem_data->in[bb->index]);
1758
      BITMAP_FREE (problem_data->out[bb->index]);
1759
    }
1760
 
1761
  free (problem_data->in);
1762
  free (problem_data->out);
1763
  free (problem_data);
1764
  df_live->problem_data = NULL;
1765
}
1766
 
1767
 
1768
/* All of the information associated with every instance of the problem.  */
1769
 
1770
static struct df_problem problem_LIVE =
1771
{
1772
  DF_LIVE,                      /* Problem id.  */
1773
  DF_FORWARD,                   /* Direction.  */
1774
  df_live_alloc,                /* Allocate the problem specific data.  */
1775
  df_live_reset,                /* Reset global information.  */
1776
  df_live_free_bb_info,         /* Free basic block info.  */
1777
  df_live_local_compute,        /* Local compute function.  */
1778
  df_live_init,                 /* Init the solution specific data.  */
1779
  df_worklist_dataflow,         /* Worklist solver.  */
1780
  NULL,                         /* Confluence operator 0.  */
1781
  df_live_confluence_n,         /* Confluence operator n.  */
1782
  df_live_transfer_function,    /* Transfer function.  */
1783
  df_live_finalize,             /* Finalize function.  */
1784
  df_live_free,                 /* Free all of the problem information.  */
1785
  df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
1786
  NULL,                         /* Debugging.  */
1787
  df_live_top_dump,             /* Debugging start block.  */
1788
  df_live_bottom_dump,          /* Debugging end block.  */
1789
  df_live_verify_solution_start,/* Incremental solution verify start.  */
1790
  df_live_verify_solution_end,  /* Incremental solution verify end.  */
1791
  &problem_LR,                  /* Dependent problem.  */
1792
  TV_DF_LIVE,                   /* Timing variable.  */
1793
  false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
1794
};
1795
 
1796
 
1797
/* Create a new DATAFLOW instance and add it to an existing instance
1798
   of DF.  The returned structure is what is used to get at the
1799
   solution.  */
1800
 
1801
void
1802
df_live_add_problem (void)
1803
{
1804
  df_add_problem (&problem_LIVE);
1805
  /* These will be initialized when df_scan_blocks processes each
1806
     block.  */
1807
  df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1808
}
1809
 
1810
 
1811
/* Set all of the blocks as dirty.  This needs to be done if this
1812
   problem is added after all of the insns have been scanned.  */
1813
 
1814
void
1815
df_live_set_all_dirty (void)
1816
{
1817
  basic_block bb;
1818
  FOR_ALL_BB (bb)
1819
    bitmap_set_bit (df_live->out_of_date_transfer_functions,
1820
                    bb->index);
1821
}
1822
 
1823
 
1824
/* Verify that all of the lr related info is consistent and
1825
   correct.  */
1826
 
1827
void
1828
df_live_verify_transfer_functions (void)
1829
{
1830
  basic_block bb;
1831
  bitmap saved_gen;
1832
  bitmap saved_kill;
1833
  bitmap all_blocks;
1834
 
1835
  if (!df)
1836
    return;
1837
 
1838
  saved_gen = BITMAP_ALLOC (NULL);
1839
  saved_kill = BITMAP_ALLOC (NULL);
1840
  all_blocks = BITMAP_ALLOC (NULL);
1841
 
1842
  df_grow_insn_info ();
1843
 
1844
  FOR_ALL_BB (bb)
1845
    {
1846
      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1847
      bitmap_set_bit (all_blocks, bb->index);
1848
 
1849
      if (bb_info)
1850
        {
1851
          /* Make a copy of the transfer functions and then compute
1852
             new ones to see if the transfer functions have
1853
             changed.  */
1854
          if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1855
                             bb->index))
1856
            {
1857
              bitmap_copy (saved_gen, bb_info->gen);
1858
              bitmap_copy (saved_kill, bb_info->kill);
1859
              bitmap_clear (bb_info->gen);
1860
              bitmap_clear (bb_info->kill);
1861
 
1862
              df_live_bb_local_compute (bb->index);
1863
              gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
1864
              gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
1865
            }
1866
        }
1867
      else
1868
        {
1869
          /* If we do not have basic block info, the block must be in
1870
             the list of dirty blocks or else some one has added a
1871
             block behind our backs. */
1872
          gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1873
                                    bb->index));
1874
        }
1875
      /* Make sure no one created a block without following
1876
         procedures.  */
1877
      gcc_assert (df_scan_get_bb_info (bb->index));
1878
    }
1879
 
1880
  /* Make sure there are no dirty bits in blocks that have been deleted.  */
1881
  gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1882
                                         all_blocks));
1883
  BITMAP_FREE (saved_gen);
1884
  BITMAP_FREE (saved_kill);
1885
  BITMAP_FREE (all_blocks);
1886
}
1887
 
1888
/*----------------------------------------------------------------------------
1889
   CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1890
 
1891
   Link either the defs to the uses and / or the uses to the defs.
1892
 
1893
   These problems are set up like the other dataflow problems so that
1894
   they nicely fit into the framework.  They are much simpler and only
1895
   involve a single traversal of instructions and an examination of
1896
   the reaching defs information (the dependent problem).
1897
----------------------------------------------------------------------------*/
1898
 
1899
#define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1900
 
1901
/* Create a du or ud chain from SRC to DST and link it into SRC.   */
1902
 
1903
struct df_link *
1904
df_chain_create (df_ref src, df_ref dst)
1905
{
1906
  struct df_link *head = DF_REF_CHAIN (src);
1907
  struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);
1908
 
1909
  DF_REF_CHAIN (src) = link;
1910
  link->next = head;
1911
  link->ref = dst;
1912
  return link;
1913
}
1914
 
1915
 
1916
/* Delete any du or ud chains that start at REF and point to
1917
   TARGET.  */
1918
static void
1919
df_chain_unlink_1 (df_ref ref, df_ref target)
1920
{
1921
  struct df_link *chain = DF_REF_CHAIN (ref);
1922
  struct df_link *prev = NULL;
1923
 
1924
  while (chain)
1925
    {
1926
      if (chain->ref == target)
1927
        {
1928
          if (prev)
1929
            prev->next = chain->next;
1930
          else
1931
            DF_REF_CHAIN (ref) = chain->next;
1932
          pool_free (df_chain->block_pool, chain);
1933
          return;
1934
        }
1935
      prev = chain;
1936
      chain = chain->next;
1937
    }
1938
}
1939
 
1940
 
1941
/* Delete a du or ud chain that leave or point to REF.  */
1942
 
1943
void
1944
df_chain_unlink (df_ref ref)
1945
{
1946
  struct df_link *chain = DF_REF_CHAIN (ref);
1947
  while (chain)
1948
    {
1949
      struct df_link *next = chain->next;
1950
      /* Delete the other side if it exists.  */
1951
      df_chain_unlink_1 (chain->ref, ref);
1952
      pool_free (df_chain->block_pool, chain);
1953
      chain = next;
1954
    }
1955
  DF_REF_CHAIN (ref) = NULL;
1956
}
1957
 
1958
 
1959
/* Copy the du or ud chain starting at FROM_REF and attach it to
1960
   TO_REF.  */
1961
 
1962
void
1963
df_chain_copy (df_ref to_ref,
1964
               struct df_link *from_ref)
1965
{
1966
  while (from_ref)
1967
    {
1968
      df_chain_create (to_ref, from_ref->ref);
1969
      from_ref = from_ref->next;
1970
    }
1971
}
1972
 
1973
 
1974
/* Remove this problem from the stack of dataflow problems.  */
1975
 
1976
static void
1977
df_chain_remove_problem (void)
1978
{
1979
  bitmap_iterator bi;
1980
  unsigned int bb_index;
1981
 
1982
  /* Wholesale destruction of the old chains.  */
1983
  if (df_chain->block_pool)
1984
    free_alloc_pool (df_chain->block_pool);
1985
 
1986
  EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1987
    {
1988
      rtx insn;
1989
      df_ref *def_rec;
1990
      df_ref *use_rec;
1991
      basic_block bb = BASIC_BLOCK (bb_index);
1992
 
1993
      if (df_chain_problem_p (DF_DU_CHAIN))
1994
        for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1995
          DF_REF_CHAIN (*def_rec) = NULL;
1996
      if (df_chain_problem_p (DF_UD_CHAIN))
1997
        for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1998
          DF_REF_CHAIN (*use_rec) = NULL;
1999
 
2000
      FOR_BB_INSNS (bb, insn)
2001
        {
2002
          unsigned int uid = INSN_UID (insn);
2003
 
2004
          if (INSN_P (insn))
2005
            {
2006
              if (df_chain_problem_p (DF_DU_CHAIN))
2007
                for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2008
                  DF_REF_CHAIN (*def_rec) = NULL;
2009
              if (df_chain_problem_p (DF_UD_CHAIN))
2010
                {
2011
                  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2012
                    DF_REF_CHAIN (*use_rec) = NULL;
2013
                  for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
2014
                    DF_REF_CHAIN (*use_rec) = NULL;
2015
                }
2016
            }
2017
        }
2018
    }
2019
 
2020
  bitmap_clear (df_chain->out_of_date_transfer_functions);
2021
  df_chain->block_pool = NULL;
2022
}
2023
 
2024
 
2025
/* Remove the chain problem completely.  */
2026
 
2027
static void
2028
df_chain_fully_remove_problem (void)
2029
{
2030
  df_chain_remove_problem ();
2031
  BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2032
  free (df_chain);
2033
}
2034
 
2035
 
2036
/* Create def-use or use-def chains.  */
2037
 
2038
static void
2039
df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2040
{
2041
  df_chain_remove_problem ();
2042
  df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2043
                                         sizeof (struct df_link), 50);
2044
  df_chain->optional_p = true;
2045
}
2046
 
2047
 
2048
/* Reset all of the chains when the set of basic blocks changes.  */
2049
 
2050
static void
2051
df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2052
{
2053
  df_chain_remove_problem ();
2054
}
2055
 
2056
 
2057
/* Create the chains for a list of USEs.  */
2058
 
2059
static void
2060
df_chain_create_bb_process_use (bitmap local_rd,
2061
                                df_ref *use_rec,
2062
                                int top_flag)
2063
{
2064
  bitmap_iterator bi;
2065
  unsigned int def_index;
2066
 
2067
  while (*use_rec)
2068
    {
2069
      df_ref use = *use_rec;
2070
      unsigned int uregno = DF_REF_REGNO (use);
2071
      if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2072
          || (uregno >= FIRST_PSEUDO_REGISTER))
2073
        {
2074
          /* Do not want to go through this for an uninitialized var.  */
2075
          int count = DF_DEFS_COUNT (uregno);
2076
          if (count)
2077
            {
2078
              if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2079
                {
2080
                  unsigned int first_index = DF_DEFS_BEGIN (uregno);
2081
                  unsigned int last_index = first_index + count - 1;
2082
 
2083
                  EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2084
                    {
2085
                      df_ref def;
2086
                      if (def_index > last_index)
2087
                        break;
2088
 
2089
                      def = DF_DEFS_GET (def_index);
2090
                      if (df_chain_problem_p (DF_DU_CHAIN))
2091
                        df_chain_create (def, use);
2092
                      if (df_chain_problem_p (DF_UD_CHAIN))
2093
                        df_chain_create (use, def);
2094
                    }
2095
                }
2096
            }
2097
        }
2098
 
2099
      use_rec++;
2100
    }
2101
}
2102
 
2103
 
2104
/* Create chains from reaching defs bitmaps for basic block BB.  */
2105
 
2106
static void
2107
df_chain_create_bb (unsigned int bb_index)
2108
{
2109
  basic_block bb = BASIC_BLOCK (bb_index);
2110
  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2111
  rtx insn;
2112
  bitmap cpy = BITMAP_ALLOC (NULL);
2113
 
2114
  bitmap_copy (cpy, bb_info->in);
2115
  bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2116
 
2117
  /* Since we are going forwards, process the artificial uses first
2118
     then the artificial defs second.  */
2119
 
2120
#ifdef EH_USES
2121
  /* Create the chains for the artificial uses from the EH_USES at the
2122
     beginning of the block.  */
2123
 
2124
  /* Artificials are only hard regs.  */
2125
  if (!(df->changeable_flags & DF_NO_HARD_REGS))
2126
    df_chain_create_bb_process_use (cpy,
2127
                                    df_get_artificial_uses (bb->index),
2128
                                    DF_REF_AT_TOP);
2129
#endif
2130
 
2131
  df_rd_simulate_artificial_defs_at_top (bb, cpy);
2132
 
2133
  /* Process the regular instructions next.  */
2134
  FOR_BB_INSNS (bb, insn)
2135
    if (INSN_P (insn))
2136
      {
2137
        unsigned int uid = INSN_UID (insn);
2138
 
2139
        /* First scan the uses and link them up with the defs that remain
2140
           in the cpy vector.  */
2141
        df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2142
        if (df->changeable_flags & DF_EQ_NOTES)
2143
          df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2144
 
2145
        /* Since we are going forwards, process the defs second.  */
2146
        df_rd_simulate_one_insn (bb, insn, cpy);
2147
      }
2148
 
2149
  /* Create the chains for the artificial uses of the hard registers
2150
     at the end of the block.  */
2151
  if (!(df->changeable_flags & DF_NO_HARD_REGS))
2152
    df_chain_create_bb_process_use (cpy,
2153
                                    df_get_artificial_uses (bb->index),
2154
                                    0);
2155
 
2156
  BITMAP_FREE (cpy);
2157
}
2158
 
2159
/* Create def-use chains from reaching use bitmaps for basic blocks
2160
   in BLOCKS.  */
2161
 
2162
static void
2163
df_chain_finalize (bitmap all_blocks)
2164
{
2165
  unsigned int bb_index;
2166
  bitmap_iterator bi;
2167
 
2168
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2169
    {
2170
      df_chain_create_bb (bb_index);
2171
    }
2172
}
2173
 
2174
 
2175
/* Free all storage associated with the problem.  */
2176
 
2177
static void
2178
df_chain_free (void)
2179
{
2180
  free_alloc_pool (df_chain->block_pool);
2181
  BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2182
  free (df_chain);
2183
}
2184
 
2185
 
2186
/* Debugging info.  */
2187
 
2188
static void
2189
df_chain_top_dump (basic_block bb, FILE *file)
2190
{
2191
  if (df_chain_problem_p (DF_DU_CHAIN))
2192
    {
2193
      rtx insn;
2194
      df_ref *def_rec = df_get_artificial_defs (bb->index);
2195
      if (*def_rec)
2196
        {
2197
 
2198
          fprintf (file, ";;  DU chains for artificial defs\n");
2199
          while (*def_rec)
2200
            {
2201
              df_ref def = *def_rec;
2202
              fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
2203
              df_chain_dump (DF_REF_CHAIN (def), file);
2204
              fprintf (file, "\n");
2205
              def_rec++;
2206
            }
2207
        }
2208
 
2209
      FOR_BB_INSNS (bb, insn)
2210
        {
2211
          if (INSN_P (insn))
2212
            {
2213
              struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2214
              def_rec = DF_INSN_INFO_DEFS (insn_info);
2215
              if (*def_rec)
2216
                {
2217
                  fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
2218
                           DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2219
 
2220
                  while (*def_rec)
2221
                    {
2222
                      df_ref def = *def_rec;
2223
                      fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
2224
                      if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2225
                        fprintf (file, "read/write ");
2226
                      df_chain_dump (DF_REF_CHAIN (def), file);
2227
                      fprintf (file, "\n");
2228
                      def_rec++;
2229
                    }
2230
                }
2231
            }
2232
        }
2233
    }
2234
}
2235
 
2236
 
2237
static void
2238
df_chain_bottom_dump (basic_block bb, FILE *file)
2239
{
2240
  if (df_chain_problem_p (DF_UD_CHAIN))
2241
    {
2242
      rtx insn;
2243
      df_ref *use_rec = df_get_artificial_uses (bb->index);
2244
 
2245
      if (*use_rec)
2246
        {
2247
          fprintf (file, ";;  UD chains for artificial uses\n");
2248
          while (*use_rec)
2249
            {
2250
              df_ref use = *use_rec;
2251
              fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
2252
              df_chain_dump (DF_REF_CHAIN (use), file);
2253
              fprintf (file, "\n");
2254
              use_rec++;
2255
            }
2256
        }
2257
 
2258
      FOR_BB_INSNS (bb, insn)
2259
        {
2260
          if (INSN_P (insn))
2261
            {
2262
              struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2263
              df_ref *eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
2264
              use_rec = DF_INSN_INFO_USES (insn_info);
2265
              if (*use_rec || *eq_use_rec)
2266
                {
2267
                  fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
2268
                           DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2269
 
2270
                  while (*use_rec)
2271
                    {
2272
                      df_ref use = *use_rec;
2273
                      fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
2274
                      if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2275
                        fprintf (file, "read/write ");
2276
                      df_chain_dump (DF_REF_CHAIN (use), file);
2277
                      fprintf (file, "\n");
2278
                      use_rec++;
2279
                    }
2280
                  while (*eq_use_rec)
2281
                    {
2282
                      df_ref use = *eq_use_rec;
2283
                      fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
2284
                      df_chain_dump (DF_REF_CHAIN (use), file);
2285
                      fprintf (file, "\n");
2286
                      eq_use_rec++;
2287
                    }
2288
                }
2289
            }
2290
        }
2291
    }
2292
}
2293
 
2294
 
2295
static struct df_problem problem_CHAIN =
2296
{
2297
  DF_CHAIN,                   /* Problem id.  */
2298
  DF_NONE,                    /* Direction.  */
2299
  df_chain_alloc,             /* Allocate the problem specific data.  */
2300
  df_chain_reset,             /* Reset global information.  */
2301
  NULL,                       /* Free basic block info.  */
2302
  NULL,                       /* Local compute function.  */
2303
  NULL,                       /* Init the solution specific data.  */
2304
  NULL,                       /* Iterative solver.  */
2305
  NULL,                       /* Confluence operator 0.  */
2306
  NULL,                       /* Confluence operator n.  */
2307
  NULL,                       /* Transfer function.  */
2308
  df_chain_finalize,          /* Finalize function.  */
2309
  df_chain_free,              /* Free all of the problem information.  */
2310
  df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
2311
  NULL,                       /* Debugging.  */
2312
  df_chain_top_dump,          /* Debugging start block.  */
2313
  df_chain_bottom_dump,       /* Debugging end block.  */
2314
  NULL,                       /* Incremental solution verify start.  */
2315
  NULL,                       /* Incremental solution verify end.  */
2316
  &problem_RD,                /* Dependent problem.  */
2317
  TV_DF_CHAIN,                /* Timing variable.  */
2318
  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2319
};
2320
 
2321
 
2322
/* Create a new DATAFLOW instance and add it to an existing instance
2323
   of DF.  The returned structure is what is used to get at the
2324
   solution.  */
2325
 
2326
void
2327
df_chain_add_problem (unsigned int chain_flags)
2328
{
2329
  df_add_problem (&problem_CHAIN);
2330
  df_chain->local_flags = chain_flags;
2331
  df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2332
}
2333
 
2334
#undef df_chain_problem_p
2335
 
2336
 
2337
/*----------------------------------------------------------------------------
2338
   BYTE LEVEL LIVE REGISTERS
2339
 
2340
   Find the locations in the function where any use of a pseudo can
2341
   reach in the backwards direction.  In and out bitvectors are built
2342
   for each basic block.  There are two mapping functions,
2343
   df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2344
   used to map regnos into bit vector positions.
2345
 
2346
   This problem differs from the regular df_lr function in the way
2347
   that subregs, *_extracts and strict_low_parts are handled. In lr
2348
   these are consider partial kills, here, the exact set of bytes is
2349
   modeled.  Note that any reg that has none of these operations is
2350
   only modeled with a single bit since all operations access the
2351
   entire register.
2352
 
2353
   This problem is more brittle that the regular lr.  It currently can
2354
   be used in dce incrementally, but cannot be used in an environment
2355
   where insns are created or modified.  The problem is that the
2356
   mapping of regnos to bitmap positions is relatively compact, in
2357
   that if a pseudo does not do any of the byte wise operations, only
2358
   one slot is allocated, rather than a slot for each byte.  If insn
2359
   are created, where a subreg is used for a reg that had no subregs,
2360
   the mapping would be wrong.  Likewise, there are no checks to see
2361
   that new pseudos have been added.  These issues could be addressed
2362
   by adding a problem specific flag to not use the compact mapping,
2363
   if there was a need to do so.
2364
 
2365
   ----------------------------------------------------------------------------*/
2366
 
2367
/* Private data used to verify the solution for this problem.  */
2368
struct df_byte_lr_problem_data
2369
{
2370
  /* Expanded versions of bitvectors used in lr.  */
2371
  bitmap invalidated_by_call;
2372
  bitmap hardware_regs_used;
2373
 
2374
  /* Indexed by regno, this is true if there are subregs, extracts or
2375
     strict_low_parts for this regno.  */
2376
  bitmap needs_expansion;
2377
 
2378
  /* The start position and len for each regno in the various bit
2379
     vectors.  */
2380
  unsigned int* regno_start;
2381
  unsigned int* regno_len;
2382
  /* An obstack for the bitmaps we need for this problem.  */
2383
  bitmap_obstack byte_lr_bitmaps;
2384
};
2385
 
2386
 
2387
/* Get the starting location for REGNO in the df_byte_lr bitmaps.  */
2388
 
2389
int
2390
df_byte_lr_get_regno_start (unsigned int regno)
2391
{
2392
  struct df_byte_lr_problem_data *problem_data
2393
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2394
  return problem_data->regno_start[regno];
2395
}
2396
 
2397
 
2398
/* Get the len for REGNO in the df_byte_lr bitmaps.  */
2399
 
2400
int
2401
df_byte_lr_get_regno_len (unsigned int regno)
2402
{
2403
  struct df_byte_lr_problem_data *problem_data
2404
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2405
  return problem_data->regno_len[regno];
2406
}
2407
 
2408
 
2409
/* Set basic block info.  */
2410
 
2411
static void
2412
df_byte_lr_set_bb_info (unsigned int index,
2413
                        struct df_byte_lr_bb_info *bb_info)
2414
{
2415
  gcc_assert (df_byte_lr);
2416
  gcc_assert (index < df_byte_lr->block_info_size);
2417
  df_byte_lr->block_info[index] = bb_info;
2418
}
2419
 
2420
 
2421
/* Free basic block info.  */
2422
 
2423
static void
2424
df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2425
                         void *vbb_info)
2426
{
2427
  struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info;
2428
  if (bb_info)
2429
    {
2430
      BITMAP_FREE (bb_info->use);
2431
      BITMAP_FREE (bb_info->def);
2432
      BITMAP_FREE (bb_info->in);
2433
      BITMAP_FREE (bb_info->out);
2434
      pool_free (df_byte_lr->block_pool, bb_info);
2435
    }
2436
}
2437
 
2438
 
2439
/* Check all of the refs in REF_REC to see if any of them are
2440
   extracts, subregs or strict_low_parts.  */
2441
 
2442
static void
2443
df_byte_lr_check_regs (df_ref *ref_rec)
2444
{
2445
  struct df_byte_lr_problem_data *problem_data
2446
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2447
 
2448
  for (; *ref_rec; ref_rec++)
2449
    {
2450
      df_ref ref = *ref_rec;
2451
      if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT
2452
                               | DF_REF_ZERO_EXTRACT
2453
                               | DF_REF_STRICT_LOW_PART)
2454
          || GET_CODE (DF_REF_REG (ref)) == SUBREG)
2455
        bitmap_set_bit (problem_data->needs_expansion, DF_REF_REGNO (ref));
2456
    }
2457
}
2458
 
2459
 
2460
/* Expand bitmap SRC which is indexed by regno to DEST which is indexed by
2461
   regno_start and regno_len.  */
2462
 
2463
static void
2464
df_byte_lr_expand_bitmap (bitmap dest, bitmap src)
2465
{
2466
  struct df_byte_lr_problem_data *problem_data
2467
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2468
  bitmap_iterator bi;
2469
  unsigned int i;
2470
 
2471
  bitmap_clear (dest);
2472
  EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi)
2473
    {
2474
      bitmap_set_range (dest, problem_data->regno_start[i],
2475
                        problem_data->regno_len[i]);
2476
    }
2477
}
2478
 
2479
 
2480
/* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2481
   not touched unless the block is new.  */
2482
 
2483
static void
2484
df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2485
{
2486
  unsigned int bb_index;
2487
  bitmap_iterator bi;
2488
  basic_block bb;
2489
  unsigned int regno;
2490
  unsigned int index = 0;
2491
  unsigned int max_reg = max_reg_num();
2492
  struct df_byte_lr_problem_data *problem_data
2493
    = XNEW (struct df_byte_lr_problem_data);
2494
 
2495
  df_byte_lr->problem_data = problem_data;
2496
 
2497
  if (!df_byte_lr->block_pool)
2498
    df_byte_lr->block_pool = create_alloc_pool ("df_byte_lr_block pool",
2499
                                           sizeof (struct df_byte_lr_bb_info), 50);
2500
 
2501
  df_grow_bb_info (df_byte_lr);
2502
 
2503
  /* Create the mapping from regnos to slots. This does not change
2504
     unless the problem is destroyed and recreated.  In particular, if
2505
     we end up deleting the only insn that used a subreg, we do not
2506
     want to redo the mapping because this would invalidate everything
2507
     else.  */
2508
 
2509
  bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps);
2510
  problem_data->regno_start = XNEWVEC (unsigned int, max_reg);
2511
  problem_data->regno_len = XNEWVEC (unsigned int, max_reg);
2512
  problem_data->hardware_regs_used = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2513
  problem_data->invalidated_by_call = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2514
  problem_data->needs_expansion = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2515
 
2516
  /* Discover which regno's use subregs, extracts or
2517
     strict_low_parts.  */
2518
  FOR_EACH_BB (bb)
2519
    {
2520
      rtx insn;
2521
      FOR_BB_INSNS (bb, insn)
2522
        {
2523
          if (INSN_P (insn))
2524
            {
2525
              struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2526
              df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info));
2527
              df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info));
2528
            }
2529
        }
2530
      bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, bb->index);
2531
    }
2532
 
2533
  bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2534
  bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2535
 
2536
  /* Allocate the slots for each regno.  */
2537
  for (regno = 0; regno < max_reg; regno++)
2538
    {
2539
      int len;
2540
      problem_data->regno_start[regno] = index;
2541
      if (bitmap_bit_p (problem_data->needs_expansion, regno))
2542
        len = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2543
      else
2544
        len = 1;
2545
 
2546
      problem_data->regno_len[regno] = len;
2547
      index += len;
2548
    }
2549
 
2550
  df_byte_lr_expand_bitmap (problem_data->hardware_regs_used,
2551
                            df->hardware_regs_used);
2552
  df_byte_lr_expand_bitmap (problem_data->invalidated_by_call,
2553
                            regs_invalidated_by_call_regset);
2554
 
2555
  EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2556
    {
2557
      struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2558
      if (bb_info)
2559
        {
2560
          bitmap_clear (bb_info->def);
2561
          bitmap_clear (bb_info->use);
2562
        }
2563
      else
2564
        {
2565
          bb_info = (struct df_byte_lr_bb_info *) pool_alloc (df_byte_lr->block_pool);
2566
          df_byte_lr_set_bb_info (bb_index, bb_info);
2567
          bb_info->use = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2568
          bb_info->def = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2569
          bb_info->in = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2570
          bb_info->out = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2571
        }
2572
    }
2573
 
2574
  df_byte_lr->optional_p = true;
2575
}
2576
 
2577
 
2578
/* Reset the global solution for recalculation.  */
2579
 
2580
static void
2581
df_byte_lr_reset (bitmap all_blocks)
2582
{
2583
  unsigned int bb_index;
2584
  bitmap_iterator bi;
2585
 
2586
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2587
    {
2588
      struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2589
      gcc_assert (bb_info);
2590
      bitmap_clear (bb_info->in);
2591
      bitmap_clear (bb_info->out);
2592
    }
2593
}
2594
 
2595
 
2596
/* Compute local live register info for basic block BB.  */
2597
 
2598
static void
2599
df_byte_lr_bb_local_compute (unsigned int bb_index)
2600
{
2601
  struct df_byte_lr_problem_data *problem_data
2602
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2603
  basic_block bb = BASIC_BLOCK (bb_index);
2604
  struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2605
  rtx insn;
2606
  df_ref *def_rec;
2607
  df_ref *use_rec;
2608
 
2609
  /* Process the registers set in an exception handler.  */
2610
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2611
    {
2612
      df_ref def = *def_rec;
2613
      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2614
        {
2615
          unsigned int dregno = DF_REF_REGNO (def);
2616
          unsigned int start = problem_data->regno_start[dregno];
2617
          unsigned int len = problem_data->regno_len[dregno];
2618
          bitmap_set_range (bb_info->def, start, len);
2619
          bitmap_clear_range (bb_info->use, start, len);
2620
        }
2621
    }
2622
 
2623
  /* Process the hardware registers that are always live.  */
2624
  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2625
    {
2626
      df_ref use = *use_rec;
2627
      /* Add use to set of uses in this BB.  */
2628
      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2629
        {
2630
          unsigned int uregno = DF_REF_REGNO (use);
2631
          unsigned int start = problem_data->regno_start[uregno];
2632
          unsigned int len = problem_data->regno_len[uregno];
2633
          bitmap_set_range (bb_info->use, start, len);
2634
        }
2635
    }
2636
 
2637
  FOR_BB_INSNS_REVERSE (bb, insn)
2638
    {
2639
      unsigned int uid = INSN_UID (insn);
2640
 
2641
      if (!INSN_P (insn))
2642
        continue;
2643
 
2644
      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2645
        {
2646
          df_ref def = *def_rec;
2647
          /* If the def is to only part of the reg, it does
2648
             not kill the other defs that reach here.  */
2649
          if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2650
            {
2651
              unsigned int dregno = DF_REF_REGNO (def);
2652
              unsigned int start = problem_data->regno_start[dregno];
2653
              unsigned int len = problem_data->regno_len[dregno];
2654
              unsigned int sb;
2655
              unsigned int lb;
2656
              if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2657
                {
2658
                  start += sb;
2659
                  len = lb - sb;
2660
                }
2661
              if (len)
2662
                {
2663
                  bitmap_set_range (bb_info->def, start, len);
2664
                  bitmap_clear_range (bb_info->use, start, len);
2665
                }
2666
            }
2667
        }
2668
 
2669
      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2670
        {
2671
          df_ref use = *use_rec;
2672
          unsigned int uregno = DF_REF_REGNO (use);
2673
          unsigned int start = problem_data->regno_start[uregno];
2674
          unsigned int len = problem_data->regno_len[uregno];
2675
          unsigned int sb;
2676
          unsigned int lb;
2677
          if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2678
            {
2679
              start += sb;
2680
              len = lb - sb;
2681
            }
2682
          /* Add use to set of uses in this BB.  */
2683
          if (len)
2684
            bitmap_set_range (bb_info->use, start, len);
2685
        }
2686
    }
2687
 
2688
  /* Process the registers set in an exception handler or the hard
2689
     frame pointer if this block is the target of a non local
2690
     goto.  */
2691
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2692
    {
2693
      df_ref def = *def_rec;
2694
      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2695
        {
2696
          unsigned int dregno = DF_REF_REGNO (def);
2697
          unsigned int start = problem_data->regno_start[dregno];
2698
          unsigned int len = problem_data->regno_len[dregno];
2699
          bitmap_set_range (bb_info->def, start, len);
2700
          bitmap_clear_range (bb_info->use, start, len);
2701
        }
2702
    }
2703
 
2704
#ifdef EH_USES
2705
  /* Process the uses that are live into an exception handler.  */
2706
  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2707
    {
2708
      df_ref use = *use_rec;
2709
      /* Add use to set of uses in this BB.  */
2710
      if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2711
        {
2712
          unsigned int uregno = DF_REF_REGNO (use);
2713
          unsigned int start = problem_data->regno_start[uregno];
2714
          unsigned int len = problem_data->regno_len[uregno];
2715
          bitmap_set_range (bb_info->use, start, len);
2716
        }
2717
    }
2718
#endif
2719
}
2720
 
2721
 
2722
/* Compute local live register info for each basic block within BLOCKS.  */
2723
 
2724
static void
2725
df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2726
{
2727
  unsigned int bb_index;
2728
  bitmap_iterator bi;
2729
 
2730
  EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2731
    {
2732
      if (bb_index == EXIT_BLOCK)
2733
        {
2734
          /* The exit block is special for this problem and its bits are
2735
             computed from thin air.  */
2736
          struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (EXIT_BLOCK);
2737
          df_byte_lr_expand_bitmap (bb_info->use, df->exit_block_uses);
2738
        }
2739
      else
2740
        df_byte_lr_bb_local_compute (bb_index);
2741
    }
2742
 
2743
  bitmap_clear (df_byte_lr->out_of_date_transfer_functions);
2744
}
2745
 
2746
 
2747
/* Initialize the solution vectors.  */
2748
 
2749
static void
2750
df_byte_lr_init (bitmap all_blocks)
2751
{
2752
  unsigned int bb_index;
2753
  bitmap_iterator bi;
2754
 
2755
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2756
    {
2757
      struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2758
      bitmap_copy (bb_info->in, bb_info->use);
2759
      bitmap_clear (bb_info->out);
2760
    }
2761
}
2762
 
2763
 
2764
/* Confluence function that processes infinite loops.  This might be a
2765
   noreturn function that throws.  And even if it isn't, getting the
2766
   unwind info right helps debugging.  */
2767
static void
2768
df_byte_lr_confluence_0 (basic_block bb)
2769
{
2770
  struct df_byte_lr_problem_data *problem_data
2771
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2772
  bitmap op1 = df_byte_lr_get_bb_info (bb->index)->out;
2773
  if (bb != EXIT_BLOCK_PTR)
2774
    bitmap_copy (op1, problem_data->hardware_regs_used);
2775
}
2776
 
2777
 
2778
/* Confluence function that ignores fake edges.  */
2779
 
2780
static void
2781
df_byte_lr_confluence_n (edge e)
2782
{
2783
  struct df_byte_lr_problem_data *problem_data
2784
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2785
  bitmap op1 = df_byte_lr_get_bb_info (e->src->index)->out;
2786
  bitmap op2 = df_byte_lr_get_bb_info (e->dest->index)->in;
2787
 
2788
  /* Call-clobbered registers die across exception and call edges.  */
2789
  /* ??? Abnormal call edges ignored for the moment, as this gets
2790
     confused by sibling call edges, which crashes reg-stack.  */
2791
  if (e->flags & EDGE_EH)
2792
    bitmap_ior_and_compl_into (op1, op2, problem_data->invalidated_by_call);
2793
  else
2794
    bitmap_ior_into (op1, op2);
2795
 
2796
  bitmap_ior_into (op1, problem_data->hardware_regs_used);
2797
}
2798
 
2799
 
2800
/* Transfer function.  */
2801
 
2802
static bool
2803
df_byte_lr_transfer_function (int bb_index)
2804
{
2805
  struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2806
  bitmap in = bb_info->in;
2807
  bitmap out = bb_info->out;
2808
  bitmap use = bb_info->use;
2809
  bitmap def = bb_info->def;
2810
 
2811
  return bitmap_ior_and_compl (in, use, out, def);
2812
}
2813
 
2814
 
2815
/* Free all storage associated with the problem.  */
2816
 
2817
static void
2818
df_byte_lr_free (void)
2819
{
2820
  struct df_byte_lr_problem_data *problem_data
2821
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2822
 
2823
 
2824
  if (df_byte_lr->block_info)
2825
    {
2826
      free_alloc_pool (df_byte_lr->block_pool);
2827
      df_byte_lr->block_info_size = 0;
2828
      free (df_byte_lr->block_info);
2829
    }
2830
 
2831
  BITMAP_FREE (df_byte_lr->out_of_date_transfer_functions);
2832
  bitmap_obstack_release (&problem_data->byte_lr_bitmaps);
2833
  free (problem_data->regno_start);
2834
  free (problem_data->regno_len);
2835
  free (problem_data);
2836
  free (df_byte_lr);
2837
}
2838
 
2839
 
2840
/* Debugging info at top of bb.  */
2841
 
2842
static void
2843
df_byte_lr_top_dump (basic_block bb, FILE *file)
2844
{
2845
  struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2846
  if (!bb_info || !bb_info->in)
2847
    return;
2848
 
2849
  fprintf (file, ";; blr  in  \t");
2850
  df_print_byte_regset (file, bb_info->in);
2851
  fprintf (file, ";; blr  use \t");
2852
  df_print_byte_regset (file, bb_info->use);
2853
  fprintf (file, ";; blr  def \t");
2854
  df_print_byte_regset (file, bb_info->def);
2855
}
2856
 
2857
 
2858
/* Debugging info at bottom of bb.  */
2859
 
2860
static void
2861
df_byte_lr_bottom_dump (basic_block bb, FILE *file)
2862
{
2863
  struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2864
  if (!bb_info || !bb_info->out)
2865
    return;
2866
 
2867
  fprintf (file, ";; blr  out \t");
2868
  df_print_byte_regset (file, bb_info->out);
2869
}
2870
 
2871
 
2872
/* All of the information associated with every instance of the problem.  */
2873
 
2874
static struct df_problem problem_BYTE_LR =
2875
{
2876
  DF_BYTE_LR,                      /* Problem id.  */
2877
  DF_BACKWARD,                     /* Direction.  */
2878
  df_byte_lr_alloc,                /* Allocate the problem specific data.  */
2879
  df_byte_lr_reset,                /* Reset global information.  */
2880
  df_byte_lr_free_bb_info,         /* Free basic block info.  */
2881
  df_byte_lr_local_compute,        /* Local compute function.  */
2882
  df_byte_lr_init,                 /* Init the solution specific data.  */
2883
  df_worklist_dataflow,            /* Worklist solver.  */
2884
  df_byte_lr_confluence_0,         /* Confluence operator 0.  */
2885
  df_byte_lr_confluence_n,         /* Confluence operator n.  */
2886
  df_byte_lr_transfer_function,    /* Transfer function.  */
2887
  NULL,                            /* Finalize function.  */
2888
  df_byte_lr_free,                 /* Free all of the problem information.  */
2889
  df_byte_lr_free,                 /* Remove this problem from the stack of dataflow problems.  */
2890
  NULL,                            /* Debugging.  */
2891
  df_byte_lr_top_dump,             /* Debugging start block.  */
2892
  df_byte_lr_bottom_dump,          /* Debugging end block.  */
2893
  NULL,                            /* Incremental solution verify start.  */
2894
  NULL,                            /* Incremental solution verify end.  */
2895
  NULL,                            /* Dependent problem.  */
2896
  TV_DF_BYTE_LR,                   /* Timing variable.  */
2897
  false                            /* Reset blocks on dropping out of blocks_to_analyze.  */
2898
};
2899
 
2900
 
2901
/* Create a new DATAFLOW instance and add it to an existing instance
2902
   of DF.  The returned structure is what is used to get at the
2903
   solution.  */
2904
 
2905
void
2906
df_byte_lr_add_problem (void)
2907
{
2908
  df_add_problem (&problem_BYTE_LR);
2909
  /* These will be initialized when df_scan_blocks processes each
2910
     block.  */
2911
  df_byte_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2912
}
2913
 
2914
 
2915
/* Simulate the effects of the defs of INSN on LIVE.  */
2916
 
2917
void
2918
df_byte_lr_simulate_defs (rtx insn, bitmap live)
2919
{
2920
  struct df_byte_lr_problem_data *problem_data
2921
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2922
  df_ref *def_rec;
2923
  unsigned int uid = INSN_UID (insn);
2924
 
2925
  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2926
    {
2927
      df_ref def = *def_rec;
2928
 
2929
      /* If the def is to only part of the reg, it does
2930
         not kill the other defs that reach here.  */
2931
      if (!(DF_REF_FLAGS (def) & DF_REF_CONDITIONAL))
2932
        {
2933
          unsigned int dregno = DF_REF_REGNO (def);
2934
          unsigned int start = problem_data->regno_start[dregno];
2935
          unsigned int len = problem_data->regno_len[dregno];
2936
          unsigned int sb;
2937
          unsigned int lb;
2938
          if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2939
            {
2940
              start += sb;
2941
              len = lb - sb;
2942
            }
2943
 
2944
          if (len)
2945
            bitmap_clear_range (live, start, len);
2946
        }
2947
    }
2948
}
2949
 
2950
 
2951
/* Simulate the effects of the uses of INSN on LIVE.  */
2952
 
2953
void
2954
df_byte_lr_simulate_uses (rtx insn, bitmap live)
2955
{
2956
  struct df_byte_lr_problem_data *problem_data
2957
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2958
  df_ref *use_rec;
2959
  unsigned int uid = INSN_UID (insn);
2960
 
2961
  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2962
    {
2963
      df_ref use = *use_rec;
2964
      unsigned int uregno = DF_REF_REGNO (use);
2965
      unsigned int start = problem_data->regno_start[uregno];
2966
      unsigned int len = problem_data->regno_len[uregno];
2967
      unsigned int sb;
2968
      unsigned int lb;
2969
 
2970
      if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2971
        {
2972
          start += sb;
2973
          len = lb - sb;
2974
        }
2975
 
2976
      /* Add use to set of uses in this BB.  */
2977
      if (len)
2978
        bitmap_set_range (live, start, len);
2979
    }
2980
}
2981
 
2982
 
2983
/* Apply the artificial uses and defs at the top of BB in a forwards
2984
   direction.  */
2985
 
2986
void
2987
df_byte_lr_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
2988
{
2989
  struct df_byte_lr_problem_data *problem_data
2990
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2991
  df_ref *def_rec;
2992
#ifdef EH_USES
2993
  df_ref *use_rec;
2994
#endif
2995
  int bb_index = bb->index;
2996
 
2997
#ifdef EH_USES
2998
  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2999
    {
3000
      df_ref use = *use_rec;
3001
      if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3002
        {
3003
          unsigned int uregno = DF_REF_REGNO (use);
3004
          unsigned int start = problem_data->regno_start[uregno];
3005
          unsigned int len = problem_data->regno_len[uregno];
3006
          bitmap_set_range (live, start, len);
3007
        }
3008
    }
3009
#endif
3010
 
3011
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3012
    {
3013
      df_ref def = *def_rec;
3014
      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3015
        {
3016
          unsigned int dregno = DF_REF_REGNO (def);
3017
          unsigned int start = problem_data->regno_start[dregno];
3018
          unsigned int len = problem_data->regno_len[dregno];
3019
          bitmap_clear_range (live, start, len);
3020
        }
3021
    }
3022
}
3023
 
3024
 
3025
/* Apply the artificial uses and defs at the end of BB in a backwards
3026
   direction.  */
3027
 
3028
void
3029
df_byte_lr_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3030
{
3031
  struct df_byte_lr_problem_data *problem_data
3032
    = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
3033
  df_ref *def_rec;
3034
  df_ref *use_rec;
3035
  int bb_index = bb->index;
3036
 
3037
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3038
    {
3039
      df_ref def = *def_rec;
3040
      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3041
        {
3042
          unsigned int dregno = DF_REF_REGNO (def);
3043
          unsigned int start = problem_data->regno_start[dregno];
3044
          unsigned int len = problem_data->regno_len[dregno];
3045
          bitmap_clear_range (live, start, len);
3046
        }
3047
    }
3048
 
3049
  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3050
    {
3051
      df_ref use = *use_rec;
3052
      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3053
        {
3054
          unsigned int uregno = DF_REF_REGNO (use);
3055
          unsigned int start = problem_data->regno_start[uregno];
3056
          unsigned int len = problem_data->regno_len[uregno];
3057
          bitmap_set_range (live, start, len);
3058
        }
3059
    }
3060
}
3061
 
3062
 
3063
 
3064
/*----------------------------------------------------------------------------
3065
   This problem computes REG_DEAD and REG_UNUSED notes.
3066
   ----------------------------------------------------------------------------*/
3067
 
3068
static void
3069
df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3070
{
3071
  df_note->optional_p = true;
3072
}
3073
 
3074
#ifdef REG_DEAD_DEBUGGING
3075
static void
3076
df_print_note (const char *prefix, rtx insn, rtx note)
3077
{
3078
  if (dump_file)
3079
    {
3080
      fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3081
      print_rtl (dump_file, note);
3082
      fprintf (dump_file, "\n");
3083
    }
3084
}
3085
#endif
3086
 
3087
 
3088
/* After reg-stack, the x86 floating point stack regs are difficult to
3089
   analyze because of all of the pushes, pops and rotations.  Thus, we
3090
   just leave the notes alone. */
3091
 
3092
#ifdef STACK_REGS
3093
static inline bool
3094
df_ignore_stack_reg (int regno)
3095
{
3096
  return regstack_completed
3097
    && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3098
}
3099
#else
3100
static inline bool
3101
df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3102
{
3103
  return false;
3104
}
3105
#endif
3106
 
3107
 
3108
/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3109
   them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */
3110
 
3111
static void
3112
df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3113
{
3114
  rtx *pprev = &REG_NOTES (insn);
3115
  rtx link = *pprev;
3116
  rtx dead = NULL;
3117
  rtx unused = NULL;
3118
 
3119
  while (link)
3120
    {
3121
      switch (REG_NOTE_KIND (link))
3122
        {
3123
        case REG_DEAD:
3124
          /* After reg-stack, we need to ignore any unused notes
3125
             for the stack registers.  */
3126
          if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3127
            {
3128
              pprev = &XEXP (link, 1);
3129
              link = *pprev;
3130
            }
3131
          else
3132
            {
3133
              rtx next = XEXP (link, 1);
3134
#ifdef REG_DEAD_DEBUGGING
3135
              df_print_note ("deleting: ", insn, link);
3136
#endif
3137
              XEXP (link, 1) = dead;
3138
              dead = link;
3139
              *pprev = link = next;
3140
            }
3141
          break;
3142
 
3143
        case REG_UNUSED:
3144
          /* After reg-stack, we need to ignore any unused notes
3145
             for the stack registers.  */
3146
          if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3147
            {
3148
              pprev = &XEXP (link, 1);
3149
              link = *pprev;
3150
            }
3151
          else
3152
            {
3153
              rtx next = XEXP (link, 1);
3154
#ifdef REG_DEAD_DEBUGGING
3155
              df_print_note ("deleting: ", insn, link);
3156
#endif
3157
              XEXP (link, 1) = unused;
3158
              unused = link;
3159
              *pprev = link = next;
3160
            }
3161
          break;
3162
 
3163
        default:
3164
          pprev = &XEXP (link, 1);
3165
          link = *pprev;
3166
          break;
3167
        }
3168
    }
3169
 
3170
  *old_dead_notes = dead;
3171
  *old_unused_notes = unused;
3172
}
3173
 
3174
 
3175
/* Set a NOTE_TYPE note for REG in INSN.  Try to pull it from the OLD
3176
   list, otherwise create a new one.  */
3177
 
3178
static inline rtx
3179
df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3180
{
3181
  rtx curr = old;
3182
  rtx prev = NULL;
3183
 
3184
  gcc_assert (!DEBUG_INSN_P (insn));
3185
 
3186
  while (curr)
3187
    if (XEXP (curr, 0) == reg)
3188
      {
3189
        if (prev)
3190
          XEXP (prev, 1) = XEXP (curr, 1);
3191
        else
3192
          old = XEXP (curr, 1);
3193
        XEXP (curr, 1) = REG_NOTES (insn);
3194
        REG_NOTES (insn) = curr;
3195
        return old;
3196
      }
3197
    else
3198
      {
3199
        prev = curr;
3200
        curr = XEXP (curr, 1);
3201
      }
3202
 
3203
  /* Did not find the note.  */
3204
  add_reg_note (insn, note_type, reg);
3205
  return old;
3206
}
3207
 
3208
/* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3209
   arguments.  Return true if the register value described by MWS's
3210
   mw_reg is known to be completely unused, and if mw_reg can therefore
3211
   be used in a REG_UNUSED note.  */
3212
 
3213
static bool
3214
df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3215
                          bitmap live, bitmap artificial_uses)
3216
{
3217
  unsigned int r;
3218
 
3219
  /* If MWS describes a partial reference, create REG_UNUSED notes for
3220
     individual hard registers.  */
3221
  if (mws->flags & DF_REF_PARTIAL)
3222
    return false;
3223
 
3224
  /* Likewise if some part of the register is used.  */
3225
  for (r = mws->start_regno; r <= mws->end_regno; r++)
3226
    if (bitmap_bit_p (live, r)
3227
        || bitmap_bit_p (artificial_uses, r))
3228
      return false;
3229
 
3230
  gcc_assert (REG_P (mws->mw_reg));
3231
  return true;
3232
}
3233
 
3234
/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3235
   based on the bits in LIVE.  Do not generate notes for registers in
3236
   artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
3237
   not generated if the reg is both read and written by the
3238
   instruction.
3239
*/
3240
 
3241
static rtx
3242
df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3243
                            bitmap live, bitmap do_not_gen,
3244
                            bitmap artificial_uses)
3245
{
3246
  unsigned int r;
3247
 
3248
#ifdef REG_DEAD_DEBUGGING
3249
  if (dump_file)
3250
    fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3251
             mws->start_regno, mws->end_regno);
3252
#endif
3253
 
3254
  if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3255
    {
3256
      unsigned int regno = mws->start_regno;
3257
      old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3258
 
3259
#ifdef REG_DEAD_DEBUGGING
3260
      df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3261
#endif
3262
      bitmap_set_bit (do_not_gen, regno);
3263
      /* Only do this if the value is totally dead.  */
3264
    }
3265
  else
3266
    for (r = mws->start_regno; r <= mws->end_regno; r++)
3267
      {
3268
        if (!bitmap_bit_p (live, r)
3269
            && !bitmap_bit_p (artificial_uses, r))
3270
          {
3271
            old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3272
#ifdef REG_DEAD_DEBUGGING
3273
            df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3274
#endif
3275
          }
3276
        bitmap_set_bit (do_not_gen, r);
3277
      }
3278
  return old;
3279
}
3280
 
3281
 
3282
/* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3283
   arguments.  Return true if the register value described by MWS's
3284
   mw_reg is known to be completely dead, and if mw_reg can therefore
3285
   be used in a REG_DEAD note.  */
3286
 
3287
static bool
3288
df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3289
                        bitmap live, bitmap artificial_uses,
3290
                        bitmap do_not_gen)
3291
{
3292
  unsigned int r;
3293
 
3294
  /* If MWS describes a partial reference, create REG_DEAD notes for
3295
     individual hard registers.  */
3296
  if (mws->flags & DF_REF_PARTIAL)
3297
    return false;
3298
 
3299
  /* Likewise if some part of the register is not dead.  */
3300
  for (r = mws->start_regno; r <= mws->end_regno; r++)
3301
    if (bitmap_bit_p (live, r)
3302
        || bitmap_bit_p (artificial_uses, r)
3303
        || bitmap_bit_p (do_not_gen, r))
3304
      return false;
3305
 
3306
  gcc_assert (REG_P (mws->mw_reg));
3307
  return true;
3308
}
3309
 
3310
/* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3311
   on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
3312
   from being set if the instruction both reads and writes the
3313
   register.  */
3314
 
3315
static rtx
3316
df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3317
                          bitmap live, bitmap do_not_gen,
3318
                          bitmap artificial_uses, bool *added_notes_p)
3319
{
3320
  unsigned int r;
3321
  bool is_debug = *added_notes_p;
3322
 
3323
  *added_notes_p = false;
3324
 
3325
#ifdef REG_DEAD_DEBUGGING
3326
  if (dump_file)
3327
    {
3328
      fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
3329
               mws->start_regno, mws->end_regno);
3330
      df_print_regset (dump_file, do_not_gen);
3331
      fprintf (dump_file, "  live =");
3332
      df_print_regset (dump_file, live);
3333
      fprintf (dump_file, "  artificial uses =");
3334
      df_print_regset (dump_file, artificial_uses);
3335
    }
3336
#endif
3337
 
3338
  if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3339
    {
3340
      /* Add a dead note for the entire multi word register.  */
3341
      if (is_debug)
3342
        {
3343
          *added_notes_p = true;
3344
          return old;
3345
        }
3346
      old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3347
#ifdef REG_DEAD_DEBUGGING
3348
      df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3349
#endif
3350
    }
3351
  else
3352
    {
3353
      for (r = mws->start_regno; r <= mws->end_regno; r++)
3354
        if (!bitmap_bit_p (live, r)
3355
            && !bitmap_bit_p (artificial_uses, r)
3356
            && !bitmap_bit_p (do_not_gen, r))
3357
          {
3358
            if (is_debug)
3359
              {
3360
                *added_notes_p = true;
3361
                return old;
3362
              }
3363
            old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3364
#ifdef REG_DEAD_DEBUGGING
3365
            df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3366
#endif
3367
          }
3368
    }
3369
  return old;
3370
}
3371
 
3372
 
3373
/* Create a REG_UNUSED note if necessary for DEF in INSN updating
3374
   LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
3375
 
3376
static rtx
3377
df_create_unused_note (rtx insn, rtx old, df_ref def,
3378
                       bitmap live, bitmap artificial_uses)
3379
{
3380
  unsigned int dregno = DF_REF_REGNO (def);
3381
 
3382
#ifdef REG_DEAD_DEBUGGING
3383
  if (dump_file)
3384
    {
3385
      fprintf (dump_file, "  regular looking at def ");
3386
      df_ref_debug (def, dump_file);
3387
    }
3388
#endif
3389
 
3390
  if (!(bitmap_bit_p (live, dregno)
3391
        || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3392
        || bitmap_bit_p (artificial_uses, dregno)
3393
        || df_ignore_stack_reg (dregno)))
3394
    {
3395
      rtx reg = (DF_REF_LOC (def))
3396
                ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3397
      old = df_set_note (REG_UNUSED, insn, old, reg);
3398
#ifdef REG_DEAD_DEBUGGING
3399
      df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3400
#endif
3401
    }
3402
 
3403
  return old;
3404
}
3405
 
3406
 
3407
/* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3408
   info: lifetime, bb, and number of defs and uses for basic block
3409
   BB.  The three bitvectors are scratch regs used here.  */
3410
 
3411
static void
3412
df_note_bb_compute (unsigned int bb_index,
3413
                    bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3414
{
3415
  basic_block bb = BASIC_BLOCK (bb_index);
3416
  rtx insn;
3417
  df_ref *def_rec;
3418
  df_ref *use_rec;
3419
 
3420
  bitmap_copy (live, df_get_live_out (bb));
3421
  bitmap_clear (artificial_uses);
3422
 
3423
#ifdef REG_DEAD_DEBUGGING
3424
  if (dump_file)
3425
    {
3426
      fprintf (dump_file, "live at bottom ");
3427
      df_print_regset (dump_file, live);
3428
    }
3429
#endif
3430
 
3431
  /* Process the artificial defs and uses at the bottom of the block
3432
     to begin processing.  */
3433
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3434
    {
3435
      df_ref def = *def_rec;
3436
#ifdef REG_DEAD_DEBUGGING
3437
      if (dump_file)
3438
        fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3439
#endif
3440
 
3441
      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3442
        bitmap_clear_bit (live, DF_REF_REGNO (def));
3443
    }
3444
 
3445
  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3446
    {
3447
      df_ref use = *use_rec;
3448
      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3449
        {
3450
          unsigned int regno = DF_REF_REGNO (use);
3451
          bitmap_set_bit (live, regno);
3452
 
3453
          /* Notes are not generated for any of the artificial registers
3454
             at the bottom of the block.  */
3455
          bitmap_set_bit (artificial_uses, regno);
3456
        }
3457
    }
3458
 
3459
#ifdef REG_DEAD_DEBUGGING
3460
  if (dump_file)
3461
    {
3462
      fprintf (dump_file, "live before artificials out ");
3463
      df_print_regset (dump_file, live);
3464
    }
3465
#endif
3466
 
3467
  FOR_BB_INSNS_REVERSE (bb, insn)
3468
    {
3469
      unsigned int uid = INSN_UID (insn);
3470
      struct df_mw_hardreg **mws_rec;
3471
      rtx old_dead_notes;
3472
      rtx old_unused_notes;
3473
      int debug_insn;
3474
 
3475
      if (!INSN_P (insn))
3476
        continue;
3477
 
3478
      debug_insn = DEBUG_INSN_P (insn);
3479
 
3480
      bitmap_clear (do_not_gen);
3481
      df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3482
 
3483
      /* Process the defs.  */
3484
      if (CALL_P (insn))
3485
        {
3486
#ifdef REG_DEAD_DEBUGGING
3487
          if (dump_file)
3488
            {
3489
              fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
3490
              df_print_regset (dump_file, live);
3491
            }
3492
#endif
3493
          /* We only care about real sets for calls.  Clobbers cannot
3494
             be depended on to really die.  */
3495
          mws_rec = DF_INSN_UID_MWS (uid);
3496
          while (*mws_rec)
3497
            {
3498
              struct df_mw_hardreg *mws = *mws_rec;
3499
              if ((DF_MWS_REG_DEF_P (mws))
3500
                  && !df_ignore_stack_reg (mws->start_regno))
3501
                old_unused_notes
3502
                  = df_set_unused_notes_for_mw (insn, old_unused_notes,
3503
                                                mws, live, do_not_gen,
3504
                                                artificial_uses);
3505
              mws_rec++;
3506
            }
3507
 
3508
          /* All of the defs except the return value are some sort of
3509
             clobber.  This code is for the return.  */
3510
          for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3511
            {
3512
              df_ref def = *def_rec;
3513
              unsigned int dregno = DF_REF_REGNO (def);
3514
              if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3515
                {
3516
                  old_unused_notes
3517
                    = df_create_unused_note (insn, old_unused_notes,
3518
                                             def, live, artificial_uses);
3519
                  bitmap_set_bit (do_not_gen, dregno);
3520
                }
3521
 
3522
              if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3523
                bitmap_clear_bit (live, dregno);
3524
            }
3525
        }
3526
      else
3527
        {
3528
          /* Regular insn.  */
3529
          mws_rec = DF_INSN_UID_MWS (uid);
3530
          while (*mws_rec)
3531
            {
3532
              struct df_mw_hardreg *mws = *mws_rec;
3533
              if (DF_MWS_REG_DEF_P (mws))
3534
                old_unused_notes
3535
                  = df_set_unused_notes_for_mw (insn, old_unused_notes,
3536
                                                mws, live, do_not_gen,
3537
                                                artificial_uses);
3538
              mws_rec++;
3539
            }
3540
 
3541
          for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3542
            {
3543
              df_ref def = *def_rec;
3544
              unsigned int dregno = DF_REF_REGNO (def);
3545
              old_unused_notes
3546
                = df_create_unused_note (insn, old_unused_notes,
3547
                                         def, live, artificial_uses);
3548
 
3549
              if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3550
                bitmap_set_bit (do_not_gen, dregno);
3551
 
3552
              if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3553
                bitmap_clear_bit (live, dregno);
3554
            }
3555
        }
3556
 
3557
      /* Process the uses.  */
3558
      mws_rec = DF_INSN_UID_MWS (uid);
3559
      while (*mws_rec)
3560
        {
3561
          struct df_mw_hardreg *mws = *mws_rec;
3562
          if ((DF_MWS_REG_DEF_P (mws))
3563
              && !df_ignore_stack_reg (mws->start_regno))
3564
            {
3565
              bool really_add_notes = debug_insn != 0;
3566
 
3567
              old_dead_notes
3568
                = df_set_dead_notes_for_mw (insn, old_dead_notes,
3569
                                            mws, live, do_not_gen,
3570
                                            artificial_uses,
3571
                                            &really_add_notes);
3572
 
3573
              if (really_add_notes)
3574
                debug_insn = -1;
3575
            }
3576
          mws_rec++;
3577
        }
3578
 
3579
      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3580
        {
3581
          df_ref use = *use_rec;
3582
          unsigned int uregno = DF_REF_REGNO (use);
3583
 
3584
#ifdef REG_DEAD_DEBUGGING
3585
          if (dump_file && !debug_insn)
3586
            {
3587
              fprintf (dump_file, "  regular looking at use ");
3588
              df_ref_debug (use, dump_file);
3589
            }
3590
#endif
3591
          if (!bitmap_bit_p (live, uregno))
3592
            {
3593
              if (debug_insn)
3594
                {
3595
                  debug_insn = -1;
3596
                  break;
3597
                }
3598
 
3599
              if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
3600
                   && (!bitmap_bit_p (do_not_gen, uregno))
3601
                   && (!bitmap_bit_p (artificial_uses, uregno))
3602
                   && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
3603
                   && (!df_ignore_stack_reg (uregno)))
3604
                {
3605
                  rtx reg = (DF_REF_LOC (use))
3606
                            ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3607
                  old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3608
 
3609
#ifdef REG_DEAD_DEBUGGING
3610
                  df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3611
#endif
3612
                }
3613
              /* This register is now live.  */
3614
              bitmap_set_bit (live, uregno);
3615
            }
3616
        }
3617
 
3618
      while (old_unused_notes)
3619
        {
3620
          rtx next = XEXP (old_unused_notes, 1);
3621
          free_EXPR_LIST_node (old_unused_notes);
3622
          old_unused_notes = next;
3623
        }
3624
      while (old_dead_notes)
3625
        {
3626
          rtx next = XEXP (old_dead_notes, 1);
3627
          free_EXPR_LIST_node (old_dead_notes);
3628
          old_dead_notes = next;
3629
        }
3630
 
3631
      if (debug_insn == -1)
3632
        {
3633
          /* ??? We could probably do better here, replacing dead
3634
             registers with their definitions.  */
3635
          INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3636
          df_insn_rescan_debug_internal (insn);
3637
        }
3638
    }
3639
}
3640
 
3641
 
3642
/* Compute register info: lifetime, bb, and number of defs and uses.  */
3643
static void
3644
df_note_compute (bitmap all_blocks)
3645
{
3646
  unsigned int bb_index;
3647
  bitmap_iterator bi;
3648
  bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
3649
  bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
3650
  bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
3651
 
3652
#ifdef REG_DEAD_DEBUGGING
3653
  if (dump_file)
3654
    print_rtl_with_bb (dump_file, get_insns());
3655
#endif
3656
 
3657
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3658
  {
3659
    df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
3660
  }
3661
 
3662
  BITMAP_FREE (live);
3663
  BITMAP_FREE (do_not_gen);
3664
  BITMAP_FREE (artificial_uses);
3665
}
3666
 
3667
 
3668
/* Free all storage associated with the problem.  */
3669
 
3670
static void
3671
df_note_free (void)
3672
{
3673
  free (df_note);
3674
}
3675
 
3676
 
3677
/* All of the information associated every instance of the problem.  */
3678
 
3679
static struct df_problem problem_NOTE =
3680
{
3681
  DF_NOTE,                    /* Problem id.  */
3682
  DF_NONE,                    /* Direction.  */
3683
  df_note_alloc,              /* Allocate the problem specific data.  */
3684
  NULL,                       /* Reset global information.  */
3685
  NULL,                       /* Free basic block info.  */
3686
  df_note_compute,            /* Local compute function.  */
3687
  NULL,                       /* Init the solution specific data.  */
3688
  NULL,                       /* Iterative solver.  */
3689
  NULL,                       /* Confluence operator 0.  */
3690
  NULL,                       /* Confluence operator n.  */
3691
  NULL,                       /* Transfer function.  */
3692
  NULL,                       /* Finalize function.  */
3693
  df_note_free,               /* Free all of the problem information.  */
3694
  df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
3695
  NULL,                       /* Debugging.  */
3696
  NULL,                       /* Debugging start block.  */
3697
  NULL,                       /* Debugging end block.  */
3698
  NULL,                       /* Incremental solution verify start.  */
3699
  NULL,                       /* Incremental solution verify end.  */
3700
  &problem_LR,                /* Dependent problem.  */
3701
  TV_DF_NOTE,                 /* Timing variable.  */
3702
  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3703
};
3704
 
3705
 
3706
/* Create a new DATAFLOW instance and add it to an existing instance
3707
   of DF.  The returned structure is what is used to get at the
3708
   solution.  */
3709
 
3710
void
3711
df_note_add_problem (void)
3712
{
3713
  df_add_problem (&problem_NOTE);
3714
}
3715
 
3716
 
3717
 
3718
 
3719
/*----------------------------------------------------------------------------
3720
   Functions for simulating the effects of single insns.
3721
 
3722
   You can either simulate in the forwards direction, starting from
3723
   the top of a block or the backwards direction from the end of the
3724
   block.  If you go backwards, defs are examined first to clear bits,
3725
   then uses are examined to set bits.  If you go forwards, defs are
3726
   examined first to set bits, then REG_DEAD and REG_UNUSED notes
3727
   are examined to clear bits.  In either case, the result of examining
3728
   a def can be undone (respectively by a use or a REG_UNUSED note).
3729
 
3730
   If you start at the top of the block, use one of DF_LIVE_IN or
3731
   DF_LR_IN.  If you start at the bottom of the block use one of
3732
   DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
3733
   THEY WILL BE DESTROYED.
3734
----------------------------------------------------------------------------*/
3735
 
3736
 
3737
/* Find the set of DEFs for INSN.  */
3738
 
3739
void
3740
df_simulate_find_defs (rtx insn, bitmap defs)
3741
{
3742
  df_ref *def_rec;
3743
  unsigned int uid = INSN_UID (insn);
3744
 
3745
  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3746
    {
3747
      df_ref def = *def_rec;
3748
      /* If the def is to only part of the reg, it does
3749
         not kill the other defs that reach here.  */
3750
      if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3751
        bitmap_set_bit (defs, DF_REF_REGNO (def));
3752
    }
3753
}
3754
 
3755
 
3756
/* Simulate the effects of the defs of INSN on LIVE.  */
3757
 
3758
void
3759
df_simulate_defs (rtx insn, bitmap live)
3760
{
3761
  df_ref *def_rec;
3762
  unsigned int uid = INSN_UID (insn);
3763
 
3764
  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3765
    {
3766
      df_ref def = *def_rec;
3767
      unsigned int dregno = DF_REF_REGNO (def);
3768
 
3769
      /* If the def is to only part of the reg, it does
3770
         not kill the other defs that reach here.  */
3771
      if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3772
        bitmap_clear_bit (live, dregno);
3773
    }
3774
}
3775
 
3776
 
3777
/* Simulate the effects of the uses of INSN on LIVE.  */
3778
 
3779
void
3780
df_simulate_uses (rtx insn, bitmap live)
3781
{
3782
  df_ref *use_rec;
3783
  unsigned int uid = INSN_UID (insn);
3784
 
3785
  if (DEBUG_INSN_P (insn))
3786
    return;
3787
 
3788
  for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3789
    {
3790
      df_ref use = *use_rec;
3791
      /* Add use to set of uses in this BB.  */
3792
      bitmap_set_bit (live, DF_REF_REGNO (use));
3793
    }
3794
}
3795
 
3796
 
3797
/* Add back the always live regs in BB to LIVE.  */
3798
 
3799
static inline void
3800
df_simulate_fixup_sets (basic_block bb, bitmap live)
3801
{
3802
  /* These regs are considered always live so if they end up dying
3803
     because of some def, we need to bring the back again.  */
3804
  if (bb_has_eh_pred (bb))
3805
    bitmap_ior_into (live, df->eh_block_artificial_uses);
3806
  else
3807
    bitmap_ior_into (live, df->regular_block_artificial_uses);
3808
}
3809
 
3810
 
3811
/*----------------------------------------------------------------------------
3812
   The following three functions are used only for BACKWARDS scanning:
3813
   i.e. they process the defs before the uses.
3814
 
3815
   df_simulate_initialize_backwards should be called first with a
3816
   bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
3817
   df_simulate_one_insn_backwards should be called for each insn in
3818
   the block, starting with the last one.  Finally,
3819
   df_simulate_finalize_backwards can be called to get a new value
3820
   of the sets at the top of the block (this is rarely used).
3821
   ----------------------------------------------------------------------------*/
3822
 
3823
/* Apply the artificial uses and defs at the end of BB in a backwards
3824
   direction.  */
3825
 
3826
void
3827
df_simulate_initialize_backwards (basic_block bb, bitmap live)
3828
{
3829
  df_ref *def_rec;
3830
  df_ref *use_rec;
3831
  int bb_index = bb->index;
3832
 
3833
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3834
    {
3835
      df_ref def = *def_rec;
3836
      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3837
        bitmap_clear_bit (live, DF_REF_REGNO (def));
3838
    }
3839
 
3840
  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3841
    {
3842
      df_ref use = *use_rec;
3843
      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3844
        bitmap_set_bit (live, DF_REF_REGNO (use));
3845
    }
3846
}
3847
 
3848
 
3849
/* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3850
 
3851
void
3852
df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3853
{
3854
  if (!NONDEBUG_INSN_P (insn))
3855
    return;
3856
 
3857
  df_simulate_defs (insn, live);
3858
  df_simulate_uses (insn, live);
3859
  df_simulate_fixup_sets (bb, live);
3860
}
3861
 
3862
 
3863
/* Apply the artificial uses and defs at the top of BB in a backwards
3864
   direction.  */
3865
 
3866
void
3867
df_simulate_finalize_backwards (basic_block bb, bitmap live)
3868
{
3869
  df_ref *def_rec;
3870
#ifdef EH_USES
3871
  df_ref *use_rec;
3872
#endif
3873
  int bb_index = bb->index;
3874
 
3875
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3876
    {
3877
      df_ref def = *def_rec;
3878
      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3879
        bitmap_clear_bit (live, DF_REF_REGNO (def));
3880
    }
3881
 
3882
#ifdef EH_USES
3883
  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3884
    {
3885
      df_ref use = *use_rec;
3886
      if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3887
        bitmap_set_bit (live, DF_REF_REGNO (use));
3888
    }
3889
#endif
3890
}
3891
/*----------------------------------------------------------------------------
3892
   The following three functions are used only for FORWARDS scanning:
3893
   i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3894
   Thus it is important to add the DF_NOTES problem to the stack of
3895
   problems computed before using these functions.
3896
 
3897
   df_simulate_initialize_forwards should be called first with a
3898
   bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
3899
   df_simulate_one_insn_forwards should be called for each insn in
3900
   the block, starting with the first one.
3901
   ----------------------------------------------------------------------------*/
3902
 
3903
/* Apply the artificial uses and defs at the top of BB in a forwards
3904
   direction.  ??? This is wrong; defs mark the point where a pseudo
3905
   becomes live when scanning forwards (unless a def is unused).  Since
3906
   there are no REG_UNUSED notes for artificial defs, passes that
3907
   require artificial defs probably should not call this function
3908
   unless (as is the case for fwprop) they are correct when liveness
3909
   bitmaps are *under*estimated.  */
3910
 
3911
void
3912
df_simulate_initialize_forwards (basic_block bb, bitmap live)
3913
{
3914
  df_ref *def_rec;
3915
  int bb_index = bb->index;
3916
 
3917
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3918
    {
3919
      df_ref def = *def_rec;
3920
      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3921
        bitmap_clear_bit (live, DF_REF_REGNO (def));
3922
    }
3923
}
3924
 
3925
/* Simulate the forwards effects of INSN on the bitmap LIVE.  */
3926
 
3927
void
3928
df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
3929
{
3930
  rtx link;
3931
  if (! INSN_P (insn))
3932
    return;
3933
 
3934
  /* Make sure that DF_NOTE really is an active df problem.  */
3935
  gcc_assert (df_note);
3936
 
3937
  /* Note that this is the opposite as how the problem is defined, because
3938
     in the LR problem defs _kill_ liveness.  However, they do so backwards,
3939
     while here the scan is performed forwards!  So, first assume that the
3940
     def is live, and if this is not true REG_UNUSED notes will rectify the
3941
     situation.  */
3942
  df_simulate_find_defs (insn, live);
3943
 
3944
  /* Clear all of the registers that go dead.  */
3945
  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3946
    {
3947
      switch (REG_NOTE_KIND (link))
3948
        {
3949
        case REG_DEAD:
3950
        case REG_UNUSED:
3951
          {
3952
            rtx reg = XEXP (link, 0);
3953
            int regno = REGNO (reg);
3954
            if (regno < FIRST_PSEUDO_REGISTER)
3955
              {
3956
                int n = hard_regno_nregs[regno][GET_MODE (reg)];
3957
                while (--n >= 0)
3958
                  bitmap_clear_bit (live, regno + n);
3959
              }
3960
            else
3961
              bitmap_clear_bit (live, regno);
3962
          }
3963
          break;
3964
        default:
3965
          break;
3966
        }
3967
    }
3968
  df_simulate_fixup_sets (bb, live);
3969
}
3970
 
3971
 
3972
 
3973
/*----------------------------------------------------------------------------
3974
   MULTIPLE DEFINITIONS
3975
 
3976
   Find the locations in the function reached by multiple definition sites
3977
   for a live pseudo.  In and out bitvectors are built for each basic
3978
   block.  They are restricted for efficiency to live registers.
3979
 
3980
   The gen and kill sets for the problem are obvious.  Together they
3981
   include all defined registers in a basic block; the gen set includes
3982
   registers where a partial or conditional or may-clobber definition is
3983
   last in the BB, while the kill set includes registers with a complete
3984
   definition coming last.  However, the computation of the dataflow
3985
   itself is interesting.
3986
 
3987
   The idea behind it comes from SSA form's iterated dominance frontier
3988
   criterion for inserting PHI functions.  Just like in that case, we can use
3989
   the dominance frontier to find places where multiple definitions meet;
3990
   a register X defined in a basic block BB1 has multiple definitions in
3991
   basic blocks in BB1's dominance frontier.
3992
 
3993
   So, the in-set of a basic block BB2 is not just the union of the
3994
   out-sets of BB2's predecessors, but includes some more bits that come
3995
   from the basic blocks of whose dominance frontier BB2 is part (BB1 in
3996
   the previous paragraph).  I called this set the init-set of BB2.
3997
 
3998
      (Note: I actually use the kill-set only to build the init-set.
3999
      gen bits are anyway propagated from BB1 to BB2 by dataflow).
4000
 
4001
    For example, if you have
4002
 
4003
       BB1 : r10 = 0
4004
             r11 = 0
4005
             if <...> goto BB2 else goto BB3;
4006
 
4007
       BB2 : r10 = 1
4008
             r12 = 1
4009
             goto BB3;
4010
 
4011
       BB3 :
4012
 
4013
    you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4014
    init-set of BB3 includes r10 and r12, but not r11.  Note that we do
4015
    not need to iterate the dominance frontier, because we do not insert
4016
    anything like PHI functions there!  Instead, dataflow will take care of
4017
    propagating the information to BB3's successors.
4018
   ---------------------------------------------------------------------------*/
4019
 
4020
/* Scratch var used by transfer functions.  This is used to do md analysis
4021
   only for live registers.  */
4022
static bitmap df_md_scratch;
4023
 
4024
/* Set basic block info.  */
4025
 
4026
static void
4027
df_md_set_bb_info (unsigned int index,
4028
                   struct df_md_bb_info *bb_info)
4029
{
4030
  gcc_assert (df_md);
4031
  gcc_assert (index < df_md->block_info_size);
4032
  df_md->block_info[index] = bb_info;
4033
}
4034
 
4035
 
4036
static void
4037
df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4038
                    void *vbb_info)
4039
{
4040
  struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
4041
  if (bb_info)
4042
    {
4043
      BITMAP_FREE (bb_info->kill);
4044
      BITMAP_FREE (bb_info->gen);
4045
      BITMAP_FREE (bb_info->init);
4046
      BITMAP_FREE (bb_info->in);
4047
      BITMAP_FREE (bb_info->out);
4048
      pool_free (df_md->block_pool, bb_info);
4049
    }
4050
}
4051
 
4052
 
4053
/* Allocate or reset bitmaps for DF_MD. The solution bits are
4054
   not touched unless the block is new.  */
4055
 
4056
static void
4057
df_md_alloc (bitmap all_blocks)
4058
{
4059
  unsigned int bb_index;
4060
  bitmap_iterator bi;
4061
 
4062
  if (!df_md->block_pool)
4063
    df_md->block_pool = create_alloc_pool ("df_md_block pool",
4064
                                           sizeof (struct df_md_bb_info), 50);
4065
 
4066
  df_grow_bb_info (df_md);
4067
  df_md_scratch = BITMAP_ALLOC (NULL);
4068
 
4069
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4070
    {
4071
      struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4072
      if (bb_info)
4073
        {
4074
          bitmap_clear (bb_info->init);
4075
          bitmap_clear (bb_info->gen);
4076
          bitmap_clear (bb_info->kill);
4077
          bitmap_clear (bb_info->in);
4078
          bitmap_clear (bb_info->out);
4079
        }
4080
      else
4081
        {
4082
          bb_info = (struct df_md_bb_info *) pool_alloc (df_md->block_pool);
4083
          df_md_set_bb_info (bb_index, bb_info);
4084
          bb_info->init = BITMAP_ALLOC (NULL);
4085
          bb_info->gen = BITMAP_ALLOC (NULL);
4086
          bb_info->kill = BITMAP_ALLOC (NULL);
4087
          bb_info->in = BITMAP_ALLOC (NULL);
4088
          bb_info->out = BITMAP_ALLOC (NULL);
4089
        }
4090
    }
4091
 
4092
  df_md->optional_p = true;
4093
}
4094
 
4095
/* Add the effect of the top artificial defs of BB to the multiple definitions
4096
   bitmap LOCAL_MD.  */
4097
 
4098
void
4099
df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4100
{
4101
  int bb_index = bb->index;
4102
  df_ref *def_rec;
4103
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4104
    {
4105
      df_ref def = *def_rec;
4106
      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4107
        {
4108
          unsigned int dregno = DF_REF_REGNO (def);
4109
          if (DF_REF_FLAGS (def)
4110
              & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4111
            bitmap_set_bit (local_md, dregno);
4112
          else
4113
            bitmap_clear_bit (local_md, dregno);
4114
        }
4115
    }
4116
}
4117
 
4118
 
4119
/* Add the effect of the defs of INSN to the reaching definitions bitmap
4120
   LOCAL_MD.  */
4121
 
4122
void
4123
df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
4124
                        bitmap local_md)
4125
{
4126
  unsigned uid = INSN_UID (insn);
4127
  df_ref *def_rec;
4128
 
4129
  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4130
    {
4131
      df_ref def = *def_rec;
4132
      unsigned int dregno = DF_REF_REGNO (def);
4133
      if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4134
          || (dregno >= FIRST_PSEUDO_REGISTER))
4135
        {
4136
          if (DF_REF_FLAGS (def)
4137
              & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4138
           bitmap_set_bit (local_md, DF_REF_ID (def));
4139
         else
4140
           bitmap_clear_bit (local_md, DF_REF_ID (def));
4141
        }
4142
    }
4143
}
4144
 
4145
static void
4146
df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4147
                                    df_ref *def_rec,
4148
                                    int top_flag)
4149
{
4150
  df_ref def;
4151
  bitmap_clear (seen_in_insn);
4152
 
4153
  while ((def = *def_rec++) != NULL)
4154
    {
4155
      unsigned int dregno = DF_REF_REGNO (def);
4156
      if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4157
            || (dregno >= FIRST_PSEUDO_REGISTER))
4158
          && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4159
        {
4160
          if (!bitmap_bit_p (seen_in_insn, dregno))
4161
            {
4162
              if (DF_REF_FLAGS (def)
4163
                  & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4164
                {
4165
                  bitmap_set_bit (bb_info->gen, dregno);
4166
                  bitmap_clear_bit (bb_info->kill, dregno);
4167
                }
4168
              else
4169
                {
4170
                  /* When we find a clobber and a regular def,
4171
                     make sure the regular def wins.  */
4172
                  bitmap_set_bit (seen_in_insn, dregno);
4173
                  bitmap_set_bit (bb_info->kill, dregno);
4174
                  bitmap_clear_bit (bb_info->gen, dregno);
4175
                }
4176
            }
4177
        }
4178
    }
4179
}
4180
 
4181
 
4182
/* Compute local multiple def info for basic block BB.  */
4183
 
4184
static void
4185
df_md_bb_local_compute (unsigned int bb_index)
4186
{
4187
  basic_block bb = BASIC_BLOCK (bb_index);
4188
  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4189
  rtx insn;
4190
 
4191
  /* Artificials are only hard regs.  */
4192
  if (!(df->changeable_flags & DF_NO_HARD_REGS))
4193
    df_md_bb_local_compute_process_def (bb_info,
4194
                                        df_get_artificial_defs (bb_index),
4195
                                        DF_REF_AT_TOP);
4196
 
4197
  FOR_BB_INSNS (bb, insn)
4198
    {
4199
      unsigned int uid = INSN_UID (insn);
4200
      if (!INSN_P (insn))
4201
        continue;
4202
 
4203
      df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4204
    }
4205
 
4206
  if (!(df->changeable_flags & DF_NO_HARD_REGS))
4207
    df_md_bb_local_compute_process_def (bb_info,
4208
                                        df_get_artificial_defs (bb_index),
4209
                                        0);
4210
}
4211
 
4212
/* Compute local reaching def info for each basic block within BLOCKS.  */
4213
 
4214
static void
4215
df_md_local_compute (bitmap all_blocks)
4216
{
4217
  unsigned int bb_index, df_bb_index;
4218
  bitmap_iterator bi1, bi2;
4219
  basic_block bb;
4220
  bitmap *frontiers;
4221
 
4222
  seen_in_insn = BITMAP_ALLOC (NULL);
4223
 
4224
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4225
    {
4226
      df_md_bb_local_compute (bb_index);
4227
    }
4228
 
4229
  BITMAP_FREE (seen_in_insn);
4230
 
4231
  frontiers = XNEWVEC (bitmap, last_basic_block);
4232
  FOR_ALL_BB (bb)
4233
    frontiers[bb->index] = BITMAP_ALLOC (NULL);
4234
 
4235
  compute_dominance_frontiers (frontiers);
4236
 
4237
  /* Add each basic block's kills to the nodes in the frontier of the BB.  */
4238
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4239
    {
4240
      bitmap kill = df_md_get_bb_info (bb_index)->kill;
4241
      EXECUTE_IF_SET_IN_BITMAP (frontiers[bb_index], 0, df_bb_index, bi2)
4242
        {
4243
          basic_block bb = BASIC_BLOCK (df_bb_index);
4244
          if (bitmap_bit_p (all_blocks, df_bb_index))
4245
            bitmap_ior_and_into (df_md_get_bb_info (df_bb_index)->init, kill,
4246
                                 df_get_live_in (bb));
4247
        }
4248
    }
4249
 
4250
  FOR_ALL_BB (bb)
4251
    BITMAP_FREE (frontiers[bb->index]);
4252
  free (frontiers);
4253
}
4254
 
4255
 
4256
/* Reset the global solution for recalculation.  */
4257
 
4258
static void
4259
df_md_reset (bitmap all_blocks)
4260
{
4261
  unsigned int bb_index;
4262
  bitmap_iterator bi;
4263
 
4264
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4265
    {
4266
      struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4267
      gcc_assert (bb_info);
4268
      bitmap_clear (bb_info->in);
4269
      bitmap_clear (bb_info->out);
4270
    }
4271
}
4272
 
4273
static bool
4274
df_md_transfer_function (int bb_index)
4275
{
4276
  basic_block bb = BASIC_BLOCK (bb_index);
4277
  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4278
  bitmap in = bb_info->in;
4279
  bitmap out = bb_info->out;
4280
  bitmap gen = bb_info->gen;
4281
  bitmap kill = bb_info->kill;
4282
 
4283
  /* We need to use a scratch set here so that the value returned from this
4284
     function invocation properly reflects whether the sets changed in a
4285
     significant way; i.e. not just because the live set was anded in.  */
4286
  bitmap_and (df_md_scratch, gen, df_get_live_out (bb));
4287
 
4288
  /* Multiple definitions of a register are not relevant if it is not
4289
     live.  Thus we trim the result to the places where it is live.  */
4290
  bitmap_and_into (in, df_get_live_in (bb));
4291
 
4292
  return bitmap_ior_and_compl (out, df_md_scratch, in, kill);
4293
}
4294
 
4295
/* Initialize the solution bit vectors for problem.  */
4296
 
4297
static void
4298
df_md_init (bitmap all_blocks)
4299
{
4300
  unsigned int bb_index;
4301
  bitmap_iterator bi;
4302
 
4303
  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4304
    {
4305
      struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4306
 
4307
      bitmap_copy (bb_info->in, bb_info->init);
4308
      df_md_transfer_function (bb_index);
4309
    }
4310
}
4311
 
4312
static void
4313
df_md_confluence_0 (basic_block bb)
4314
{
4315
  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4316
  bitmap_copy (bb_info->in, bb_info->init);
4317
}
4318
 
4319
/* In of target gets or of out of source.  */
4320
 
4321
static void
4322
df_md_confluence_n (edge e)
4323
{
4324
  bitmap op1 = df_md_get_bb_info (e->dest->index)->in;
4325
  bitmap op2 = df_md_get_bb_info (e->src->index)->out;
4326
 
4327
  if (e->flags & EDGE_FAKE)
4328
    return;
4329
 
4330
  if (e->flags & EDGE_EH)
4331
    bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
4332
  else
4333
    bitmap_ior_into (op1, op2);
4334
}
4335
 
4336
/* Free all storage associated with the problem.  */
4337
 
4338
static void
4339
df_md_free (void)
4340
{
4341
  unsigned int i;
4342
  for (i = 0; i < df_md->block_info_size; i++)
4343
    {
4344
      struct df_md_bb_info *bb_info = df_md_get_bb_info (i);
4345
      if (bb_info)
4346
        {
4347
          BITMAP_FREE (bb_info->kill);
4348
          BITMAP_FREE (bb_info->gen);
4349
          BITMAP_FREE (bb_info->init);
4350
          BITMAP_FREE (bb_info->in);
4351
          BITMAP_FREE (bb_info->out);
4352
        }
4353
    }
4354
 
4355
  BITMAP_FREE (df_md_scratch);
4356
  free_alloc_pool (df_md->block_pool);
4357
 
4358
  df_md->block_info_size = 0;
4359
  free (df_md->block_info);
4360
  free (df_md);
4361
}
4362
 
4363
 
4364
/* Debugging info at top of bb.  */
4365
 
4366
static void
4367
df_md_top_dump (basic_block bb, FILE *file)
4368
{
4369
  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4370
  if (!bb_info || !bb_info->in)
4371
    return;
4372
 
4373
  fprintf (file, ";; md  in  \t");
4374
  df_print_regset (file, bb_info->in);
4375
  fprintf (file, ";; md  init  \t");
4376
  df_print_regset (file, bb_info->init);
4377
  fprintf (file, ";; md  gen \t");
4378
  df_print_regset (file, bb_info->gen);
4379
  fprintf (file, ";; md  kill \t");
4380
  df_print_regset (file, bb_info->kill);
4381
}
4382
 
4383
/* Debugging info at bottom of bb.  */
4384
 
4385
static void
4386
df_md_bottom_dump (basic_block bb, FILE *file)
4387
{
4388
  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4389
  if (!bb_info || !bb_info->out)
4390
    return;
4391
 
4392
  fprintf (file, ";; md  out \t");
4393
  df_print_regset (file, bb_info->out);
4394
}
4395
 
4396
static struct df_problem problem_MD =
4397
{
4398
  DF_MD,                      /* Problem id.  */
4399
  DF_FORWARD,                 /* Direction.  */
4400
  df_md_alloc,                /* Allocate the problem specific data.  */
4401
  df_md_reset,                /* Reset global information.  */
4402
  df_md_free_bb_info,         /* Free basic block info.  */
4403
  df_md_local_compute,        /* Local compute function.  */
4404
  df_md_init,                 /* Init the solution specific data.  */
4405
  df_worklist_dataflow,       /* Worklist solver.  */
4406
  df_md_confluence_0,         /* Confluence operator 0.  */
4407
  df_md_confluence_n,         /* Confluence operator n.  */
4408
  df_md_transfer_function,    /* Transfer function.  */
4409
  NULL,                       /* Finalize function.  */
4410
  df_md_free,                 /* Free all of the problem information.  */
4411
  df_md_free,                 /* Remove this problem from the stack of dataflow problems.  */
4412
  NULL,                       /* Debugging.  */
4413
  df_md_top_dump,             /* Debugging start block.  */
4414
  df_md_bottom_dump,          /* Debugging end block.  */
4415
  NULL,                       /* Incremental solution verify start.  */
4416
  NULL,                       /* Incremental solution verify end.  */
4417
  NULL,                       /* Dependent problem.  */
4418
  TV_DF_MD,                   /* Timing variable.  */
4419
  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
4420
};
4421
 
4422
/* Create a new MD instance and add it to the existing instance
4423
   of DF.  */
4424
 
4425
void
4426
df_md_add_problem (void)
4427
{
4428
  df_add_problem (&problem_MD);
4429
}
4430
 
4431
 
4432
 

powered by: WebSVN 2.1.0

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