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