gcc/df-problems.c

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