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