gcc/df-problems.c

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