gcc/df.c

   1 /* Dataflow support routines.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005
   3    Free Software Foundation, Inc.
   4    Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz,
   5                                     mhayes@redhat.com)
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 2, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING.  If not, write to the Free
  21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  22 02110-1301, USA.
  23
  24
  25 OVERVIEW:
  26
  27 This file provides some dataflow routines for computing reaching defs,
  28 upward exposed uses, live variables, def-use chains, and use-def
  29 chains.  The global dataflow is performed using simple iterative
  30 methods with a worklist and could be sped up by ordering the blocks
  31 with a depth first search order.
  32
  33 A `struct ref' data structure (ref) is allocated for every register
  34 reference (def or use) and this records the insn and bb the ref is
  35 found within.  The refs are linked together in chains of uses and defs
  36 for each insn and for each register.  Each ref also has a chain field
  37 that links all the use refs for a def or all the def refs for a use.
  38 This is used to create use-def or def-use chains.
  39
  40
  41 USAGE:
  42
  43 Here's an example of using the dataflow routines.
  44
  45       struct df *df;
  46
  47       df = df_init ();
  48
  49       df_analyze (df, 0, DF_ALL);
  50
  51       df_dump (df, DF_ALL, stderr);
  52
  53       df_finish (df);
  54
  55
  56 df_init simply creates a poor man's object (df) that needs to be
  57 passed to all the dataflow routines.  df_finish destroys this
  58 object and frees up any allocated memory.   DF_ALL says to analyze
  59 everything.
  60
  61 df_analyze performs the following:
  62
  63 1. Records defs and uses by scanning the insns in each basic block
  64    or by scanning the insns queued by df_insn_modify.
  65 2. Links defs and uses into insn-def and insn-use chains.
  66 3. Links defs and uses into reg-def and reg-use chains.
  67 4. Assigns LUIDs to each insn (for modified blocks).
  68 5. Calculates local reaching definitions.
  69 6. Calculates global reaching definitions.
  70 7. Creates use-def chains.
  71 8. Calculates local reaching uses (upwards exposed uses).
  72 9. Calculates global reaching uses.
  73 10. Creates def-use chains.
  74 11. Calculates local live registers.
  75 12. Calculates global live registers.
  76 13. Calculates register lifetimes and determines local registers.
  77
  78
  79 PHILOSOPHY:
  80
  81 Note that the dataflow information is not updated for every newly
  82 deleted or created insn.  If the dataflow information requires
  83 updating then all the changed, new, or deleted insns needs to be
  84 marked with df_insn_modify (or df_insns_modify) either directly or
  85 indirectly (say through calling df_insn_delete).  df_insn_modify
  86 marks all the modified insns to get processed the next time df_analyze
  87  is called.
  88
  89 Beware that tinkering with insns may invalidate the dataflow information.
  90 The philosophy behind these routines is that once the dataflow
  91 information has been gathered, the user should store what they require
  92 before they tinker with any insn.  Once a reg is replaced, for example,
  93 then the reg-def/reg-use chains will point to the wrong place.  Once a
  94 whole lot of changes have been made, df_analyze can be called again
  95 to update the dataflow information.  Currently, this is not very smart
  96 with regard to propagating changes to the dataflow so it should not
  97 be called very often.
  98
  99
 100 DATA STRUCTURES:
 101
 102 The basic object is a REF (reference) and this may either be a DEF
 103 (definition) or a USE of a register.
 104
 105 These are linked into a variety of lists; namely reg-def, reg-use,
 106   insn-def, insn-use, def-use, and use-def lists.  For example,
 107 the reg-def lists contain all the refs that define a given register
 108 while the insn-use lists contain all the refs used by an insn.
 109
 110 Note that the reg-def and reg-use chains are generally short (except for
 111 the hard registers) and thus it is much faster to search these chains
 112 rather than searching the def or use bitmaps.
 113
 114 If the insns are in SSA form then the reg-def and use-def lists
 115 should only contain the single defining ref.
 116
 117
 118 TODO:
 119
 120 1) Incremental dataflow analysis.
 121
 122 Note that if a loop invariant insn is hoisted (or sunk), we do not
 123 need to change the def-use or use-def chains.  All we have to do is to
 124 change the bb field for all the associated defs and uses and to
 125 renumber the LUIDs for the original and new basic blocks of the insn.
 126
 127 When shadowing loop mems we create new uses and defs for new pseudos
 128 so we do not affect the existing dataflow information.
 129
 130 My current strategy is to queue up all modified, created, or deleted
 131 insns so when df_analyze is called we can easily determine all the new
 132 or deleted refs.  Currently the global dataflow information is
 133 recomputed from scratch but this could be propagated more efficiently.
 134
 135 2) Reduced memory requirements.
 136
 137 We could operate a pool of ref structures.  When a ref is deleted it
 138 gets returned to the pool (say by linking on to a chain of free refs).
 139 This will require a pair of bitmaps for defs and uses so that we can
 140 tell which ones have been changed.  Alternatively, we could
 141 periodically squeeze the def and use tables and associated bitmaps and
 142 renumber the def and use ids.
 143
 144 3) Ordering of reg-def and reg-use lists.
 145
 146 Should the first entry in the def list be the first def (within a BB)?
 147 Similarly, should the first entry in the use list be the last use
 148 (within a BB)?
 149
 150 4) Working with a sub-CFG.
 151
 152 Often the whole CFG does not need to be analyzed, for example,
 153 when optimizing a loop, only certain registers are of interest.
 154 Perhaps there should be a bitmap argument to df_analyze to specify
 155 which registers should be analyzed?
 156
 157
 158 NOTES:
 159
 160 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
 161 both a use and a def.  These are both marked read/write to show that they
 162 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
 163 will generate a use of reg 42 followed by a def of reg 42 (both marked
 164 read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
 165 generates a use of reg 41 then a def of reg 41 (both marked read/write),
 166 even though reg 41 is decremented before it is used for the memory
 167 address in this second example.
 168
 169 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
 170 for which the number of word_mode units covered by the outer mode is
 171 smaller than that covered by the inner mode, invokes a read-modify-write.
 172 operation.  We generate both a use and a def and again mark them
 173 read/write.
 174 Paradoxical subreg writes don't leave a trace of the old content, so they
 175 are write-only operations.  */
 176
 177 #include "config.h"
 178 #include "system.h"
 179 #include "coretypes.h"
 180 #include "tm.h"
 181 #include "rtl.h"
 182 #include "tm_p.h"
 183 #include "insn-config.h"
 184 #include "recog.h"
 185 #include "function.h"
 186 #include "regs.h"
 187 #include "alloc-pool.h"
 188 #include "hard-reg-set.h"
 189 #include "basic-block.h"
 190 #include "sbitmap.h"
 191 #include "bitmap.h"
 192 #include "df.h"
 193
 194 #define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE)    \
 195   do                                                    \
 196     {                                                   \
 197       unsigned int node_;                               \
 198       bitmap_iterator bi;                               \
 199       EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, bi) \
 200         {                                               \
 201           (BB) = BASIC_BLOCK (node_);                   \
 202           CODE;                                         \
 203         }                                               \
 204     }                                                   \
 205   while (0)
 206
 207 static alloc_pool df_ref_pool;
 208 static alloc_pool df_link_pool;
 209 static struct df *ddf;
 210
 211 static void df_reg_table_realloc (struct df *, int);
 212 static void df_insn_table_realloc (struct df *, unsigned int);
 213 static void df_bb_table_realloc (struct df *, unsigned int);
 214 static void df_bitmaps_alloc (struct df *, bitmap, int);
 215 static void df_bitmaps_free (struct df *, int);
 216 static void df_free (struct df *);
 217 static void df_alloc (struct df *, int);
 218
 219 static rtx df_reg_use_gen (unsigned int);
 220
 221 static inline struct df_link *df_link_create (struct ref *, struct df_link *);
 222 static struct df_link *df_ref_unlink (struct df_link **, struct ref *);
 223 static void df_def_unlink (struct df *, struct ref *);
 224 static void df_use_unlink (struct df *, struct ref *);
 225 static void df_insn_refs_unlink (struct df *, basic_block, rtx);
 226 #if 0
 227 static void df_bb_refs_unlink (struct df *, basic_block);
 228 static void df_refs_unlink (struct df *, bitmap);
 229 #endif
 230
 231 static struct ref *df_ref_create (struct df *, rtx, rtx *, rtx,
 232                                   enum df_ref_type, enum df_ref_flags);
 233 static void df_ref_record_1 (struct df *, rtx, rtx *, rtx, enum df_ref_type,
 234                              enum df_ref_flags);
 235 static void df_ref_record (struct df *, rtx, rtx *, rtx, enum df_ref_type,
 236                            enum df_ref_flags);
 237 static void df_def_record_1 (struct df *, rtx, basic_block, rtx);
 238 static void df_defs_record (struct df *, rtx, basic_block, rtx);
 239 static void df_uses_record (struct df *, rtx *, enum df_ref_type,
 240                             basic_block, rtx, enum df_ref_flags);
 241 static void df_insn_refs_record (struct df *, basic_block, rtx);
 242 static void df_bb_refs_record (struct df *, basic_block);
 243 static void df_refs_record (struct df *, bitmap);
 244
 245 static void df_bb_reg_def_chain_create (struct df *, basic_block);
 246 static void df_reg_def_chain_create (struct df *, bitmap, bool);
 247 static void df_bb_reg_use_chain_create (struct df *, basic_block);
 248 static void df_reg_use_chain_create (struct df *, bitmap, bool);
 249 static void df_bb_du_chain_create (struct df *, basic_block, bitmap);
 250 static void df_du_chain_create (struct df *, bitmap);
 251 static void df_bb_ud_chain_create (struct df *, basic_block);
 252 static void df_ud_chain_create (struct df *, bitmap);
 253 static void df_bb_rd_local_compute (struct df *, basic_block, bitmap);
 254 static void df_rd_local_compute (struct df *, bitmap);
 255 static void df_bb_ru_local_compute (struct df *, basic_block);
 256 static void df_ru_local_compute (struct df *, bitmap);
 257 static void df_bb_lr_local_compute (struct df *, basic_block);
 258 static void df_lr_local_compute (struct df *, bitmap);
 259 static void df_bb_reg_info_compute (struct df *, basic_block, bitmap);
 260 static void df_reg_info_compute (struct df *, bitmap);
 261
 262 static int df_bb_luids_set (struct df *df, basic_block);
 263 static int df_luids_set (struct df *df, bitmap);
 264
 265 static int df_modified_p (struct df *, bitmap);
 266 static int df_refs_queue (struct df *);
 267 static int df_refs_process (struct df *);
 268 static int df_bb_refs_update (struct df *, basic_block);
 269 static int df_refs_update (struct df *, bitmap);
 270 static void df_analyze_1 (struct df *, bitmap, int, int);
 271
 272 static void df_insns_modify (struct df *, basic_block, rtx, rtx);
 273 static int df_rtx_mem_replace (rtx *, void *);
 274 static int df_rtx_reg_replace (rtx *, void *);
 275 void df_refs_reg_replace (struct df *, bitmap, struct df_link *, rtx, rtx);
 276
 277 static int df_def_dominates_all_uses_p (struct df *, struct ref *def);
 278 static int df_def_dominates_uses_p (struct df *, struct ref *def, bitmap);
 279 static struct ref *df_bb_insn_regno_last_use_find (struct df *, basic_block,
 280                                                    rtx, unsigned int);
 281 static struct ref *df_bb_insn_regno_first_def_find (struct df *, basic_block,
 282                                                     rtx, unsigned int);
 283
 284 static void df_chain_dump (struct df_link *, FILE *file);
 285 static void df_chain_dump_regno (struct df_link *, FILE *file);
 286 static void df_regno_debug (struct df *, unsigned int, FILE *);
 287 static void df_ref_debug (struct df *, struct ref *, FILE *);
 288 static void df_rd_transfer_function (int, int *, void *, void *, void *,
 289                                      void *, void *);
 290 static void df_ru_transfer_function (int, int *, void *, void *, void *,
 291                                      void *, void *);
 292 static void df_lr_transfer_function (int, int *, void *, void *, void *,
 293                                      void *, void *);
 294 static void hybrid_search (basic_block, struct dataflow *,
 295                            sbitmap, sbitmap, sbitmap);
 296
 297 \f
 298 /* Local memory allocation/deallocation routines.  */
 299
 300
 301 /* Increase the insn info table to have space for at least SIZE + 1
 302    elements.  */
 303 static void
 304 df_insn_table_realloc (struct df *df, unsigned int size)
 305 {
 306   size++;
 307   if (size <= df->insn_size)
 308     return;
 309
 310   /* Make the table a little larger than requested, so we do not need
 311      to enlarge it so often.  */
 312   size += df->insn_size / 4;
 313
 314   df->insns = xrealloc (df->insns, size * sizeof (struct insn_info));
 315
 316   memset (df->insns + df->insn_size, 0,
 317           (size - df->insn_size) * sizeof (struct insn_info));
 318
 319   df->insn_size = size;
 320
 321   if (! df->insns_modified)
 322     {
 323       df->insns_modified = BITMAP_ALLOC (NULL);
 324       bitmap_zero (df->insns_modified);
 325     }
 326 }
 327
 328 /* Increase the bb info table to have space for at least SIZE + 1
 329    elements.  */
 330
 331 static void
 332 df_bb_table_realloc (struct df *df, unsigned int size)
 333 {
 334   size++;
 335   if (size <= df->n_bbs)
 336     return;
 337
 338   /* Make the table a little larger than requested, so we do not need
 339      to enlarge it so often.  */
 340   size += df->n_bbs / 4;
 341
 342   df->bbs = xrealloc (df->bbs, size * sizeof (struct bb_info));
 343
 344   memset (df->bbs + df->n_bbs, 0, (size - df->n_bbs) * sizeof (struct bb_info));
 345
 346   df->n_bbs = size;
 347 }
 348
 349 /* Increase the reg info table by SIZE more elements.  */
 350 static void
 351 df_reg_table_realloc (struct df *df, int size)
 352 {
 353   /* Make table 25 percent larger by default.  */
 354   if (! size)
 355     size = df->reg_size / 4;
 356
 357   size += df->reg_size;
 358   if (size < max_reg_num ())
 359     size = max_reg_num ();
 360
 361   df->regs = xrealloc (df->regs, size * sizeof (struct reg_info));
 362   df->reg_def_last = xrealloc (df->reg_def_last,
 363                                size * sizeof (struct ref *));
 364
 365   /* Zero the new entries.  */
 366   memset (df->regs + df->reg_size, 0,
 367           (size - df->reg_size) * sizeof (struct reg_info));
 368
 369   df->reg_size = size;
 370 }
 371
 372
 373 /* Allocate bitmaps for each basic block.  */
 374
 375 static void
 376 df_bitmaps_alloc (struct df *df, bitmap blocks, int flags)
 377 {
 378   basic_block bb;
 379
 380   df->n_defs = df->def_id;
 381   df->n_uses = df->use_id;
 382
 383   if (!blocks)
 384     blocks = df->all_blocks;
 385
 386   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
 387     {
 388       struct bb_info *bb_info = DF_BB_INFO (df, bb);
 389
 390       if (flags & DF_RD)
 391         {
 392           if (!bb_info->rd_in)
 393             {
 394               /* Allocate bitmaps for reaching definitions.  */
 395               bb_info->rd_kill = BITMAP_ALLOC (NULL);
 396               bb_info->rd_gen = BITMAP_ALLOC (NULL);
 397               bb_info->rd_in = BITMAP_ALLOC (NULL);
 398               bb_info->rd_out = BITMAP_ALLOC (NULL);
 399             }
 400           else
 401             {
 402               bitmap_clear (bb_info->rd_kill);
 403               bitmap_clear (bb_info->rd_gen);
 404               bitmap_clear (bb_info->rd_in);
 405               bitmap_clear (bb_info->rd_out);
 406             }
 407         }
 408
 409       if (flags & DF_RU)
 410         {
 411           if (!bb_info->ru_in)
 412             {
 413               /* Allocate bitmaps for upward exposed uses.  */
 414               bb_info->ru_kill = BITMAP_ALLOC (NULL);
 415               bb_info->ru_gen = BITMAP_ALLOC (NULL);
 416               bb_info->ru_in = BITMAP_ALLOC (NULL);
 417               bb_info->ru_out = BITMAP_ALLOC (NULL);
 418             }
 419           else
 420             {
 421               bitmap_clear (bb_info->ru_kill);
 422               bitmap_clear (bb_info->ru_gen);
 423               bitmap_clear (bb_info->ru_in);
 424               bitmap_clear (bb_info->ru_out);
 425             }
 426         }
 427
 428       if (flags & DF_LR)
 429         {
 430           if (!bb_info->lr_in)
 431             {
 432               /* Allocate bitmaps for live variables.  */
 433               bb_info->lr_def = BITMAP_ALLOC (NULL);
 434               bb_info->lr_use = BITMAP_ALLOC (NULL);
 435               bb_info->lr_in = BITMAP_ALLOC (NULL);
 436               bb_info->lr_out = BITMAP_ALLOC (NULL);
 437             }
 438           else
 439             {
 440               bitmap_clear (bb_info->lr_def);
 441               bitmap_clear (bb_info->lr_use);
 442               bitmap_clear (bb_info->lr_in);
 443               bitmap_clear (bb_info->lr_out);
 444             }
 445         }
 446     });
 447 }
 448
 449
 450 /* Free bitmaps for each basic block.  */
 451 static void
 452 df_bitmaps_free (struct df *df, int flags)
 453 {
 454   unsigned i;
 455
 456   for (i = 0; i < df->n_bbs; i++)
 457     {
 458       struct bb_info *bb_info = &df->bbs[i];
 459
 460       if ((flags & DF_RD) && bb_info->rd_in)
 461         {
 462           /* Free bitmaps for reaching definitions.  */
 463           BITMAP_FREE (bb_info->rd_kill);
 464           bb_info->rd_kill = NULL;
 465           BITMAP_FREE (bb_info->rd_gen);
 466           bb_info->rd_gen = NULL;
 467           BITMAP_FREE (bb_info->rd_in);
 468           bb_info->rd_in = NULL;
 469           BITMAP_FREE (bb_info->rd_out);
 470           bb_info->rd_out = NULL;
 471         }
 472
 473       if ((flags & DF_RU) && bb_info->ru_in)
 474         {
 475           /* Free bitmaps for upward exposed uses.  */
 476           BITMAP_FREE (bb_info->ru_kill);
 477           bb_info->ru_kill = NULL;
 478           BITMAP_FREE (bb_info->ru_gen);
 479           bb_info->ru_gen = NULL;
 480           BITMAP_FREE (bb_info->ru_in);
 481           bb_info->ru_in = NULL;
 482           BITMAP_FREE (bb_info->ru_out);
 483           bb_info->ru_out = NULL;
 484         }
 485
 486       if ((flags & DF_LR) && bb_info->lr_in)
 487         {
 488           /* Free bitmaps for live variables.  */
 489           BITMAP_FREE (bb_info->lr_def);
 490           bb_info->lr_def = NULL;
 491           BITMAP_FREE (bb_info->lr_use);
 492           bb_info->lr_use = NULL;
 493           BITMAP_FREE (bb_info->lr_in);
 494           bb_info->lr_in = NULL;
 495           BITMAP_FREE (bb_info->lr_out);
 496           bb_info->lr_out = NULL;
 497         }
 498     }
 499   df->flags &= ~(flags & (DF_RD | DF_RU | DF_LR));
 500 }
 501
 502
 503 /* Allocate and initialize dataflow memory.  */
 504 static void
 505 df_alloc (struct df *df, int n_regs)
 506 {
 507   int n_insns;
 508   basic_block bb;
 509
 510   df_link_pool = create_alloc_pool ("df_link pool", sizeof (struct df_link),
 511                                     100);
 512   df_ref_pool  = create_alloc_pool ("df_ref pool", sizeof (struct ref), 100);
 513
 514   /* Perhaps we should use LUIDs to save memory for the insn_refs
 515      table.  This is only a small saving; a few pointers.  */
 516   n_insns = get_max_uid () + 1;
 517
 518   df->def_id = 0;
 519   df->n_defs = 0;
 520   /* Approximate number of defs by number of insns.  */
 521   df->def_size = n_insns;
 522   df->defs = xmalloc (df->def_size * sizeof (*df->defs));
 523
 524   df->use_id = 0;
 525   df->n_uses = 0;
 526   /* Approximate number of uses by twice number of insns.  */
 527   df->use_size = n_insns * 2;
 528   df->uses = xmalloc (df->use_size * sizeof (*df->uses));
 529
 530   df->n_regs = n_regs;
 531   df->n_bbs = last_basic_block;
 532
 533   /* Allocate temporary working array used during local dataflow analysis.  */
 534   df_insn_table_realloc (df, n_insns);
 535
 536   df_reg_table_realloc (df, df->n_regs);
 537
 538   df->bbs_modified = BITMAP_ALLOC (NULL);
 539   bitmap_zero (df->bbs_modified);
 540
 541   df->flags = 0;
 542
 543   df->bbs = xcalloc (last_basic_block, sizeof (struct bb_info));
 544
 545   df->all_blocks = BITMAP_ALLOC (NULL);
 546   FOR_EACH_BB (bb)
 547     bitmap_set_bit (df->all_blocks, bb->index);
 548 }
 549
 550
 551 /* Free all the dataflow info.  */
 552 static void
 553 df_free (struct df *df)
 554 {
 555   df_bitmaps_free (df, DF_ALL);
 556
 557   if (df->bbs)
 558     free (df->bbs);
 559   df->bbs = 0;
 560
 561   if (df->insns)
 562     free (df->insns);
 563   df->insns = 0;
 564   df->insn_size = 0;
 565
 566   if (df->defs)
 567     free (df->defs);
 568   df->defs = 0;
 569   df->def_size = 0;
 570   df->def_id = 0;
 571
 572   if (df->uses)
 573     free (df->uses);
 574   df->uses = 0;
 575   df->use_size = 0;
 576   df->use_id = 0;
 577
 578   if (df->regs)
 579     free (df->regs);
 580   df->regs = 0;
 581   df->reg_size = 0;
 582
 583   BITMAP_FREE (df->bbs_modified);
 584   df->bbs_modified = 0;
 585
 586   BITMAP_FREE (df->insns_modified);
 587   df->insns_modified = 0;
 588
 589   BITMAP_FREE (df->all_blocks);
 590   df->all_blocks = 0;
 591
 592   free_alloc_pool (df_ref_pool);
 593   free_alloc_pool (df_link_pool);
 594 }
 595 \f
 596 /* Local miscellaneous routines.  */
 597
 598 /* Return a USE for register REGNO.  */
 599 static rtx df_reg_use_gen (unsigned int regno)
 600 {
 601   rtx reg;
 602   rtx use;
 603
 604   reg = regno_reg_rtx[regno];
 605
 606   use = gen_rtx_USE (GET_MODE (reg), reg);
 607   return use;
 608 }
 609 \f
 610 /* Local chain manipulation routines.  */
 611
 612 /* Create a link in a def-use or use-def chain.  */
 613 static inline struct df_link *
 614 df_link_create (struct ref *ref, struct df_link *next)
 615 {
 616   struct df_link *link;
 617
 618   link = pool_alloc (df_link_pool);
 619   link->next = next;
 620   link->ref = ref;
 621   return link;
 622 }
 623
 624 /* Releases members of the CHAIN.  */
 625
 626 static void
 627 free_reg_ref_chain (struct df_link **chain)
 628 {
 629   struct df_link *act, *next;
 630
 631   for (act = *chain; act; act = next)
 632     {
 633       next = act->next;
 634       pool_free (df_link_pool, act);
 635     }
 636
 637   *chain = NULL;
 638 }
 639
 640 /* Add REF to chain head pointed to by PHEAD.  */
 641 static struct df_link *
 642 df_ref_unlink (struct df_link **phead, struct ref *ref)
 643 {
 644   struct df_link *link = *phead;
 645
 646   if (link)
 647     {
 648       if (! link->next)
 649         {
 650           /* Only a single ref.  It must be the one we want.
 651              If not, the def-use and use-def chains are likely to
 652              be inconsistent.  */
 653           gcc_assert (link->ref == ref);
 654
 655           /* Now have an empty chain.  */
 656           *phead = NULL;
 657         }
 658       else
 659         {
 660           /* Multiple refs.  One of them must be us.  */
 661           if (link->ref == ref)
 662             *phead = link->next;
 663           else
 664             {
 665               /* Follow chain.  */
 666               for (; link->next; link = link->next)
 667                 {
 668                   if (link->next->ref == ref)
 669                     {
 670                       /* Unlink from list.  */
 671                       link->next = link->next->next;
 672                       return link->next;
 673                     }
 674                 }
 675             }
 676         }
 677     }
 678   return link;
 679 }
 680
 681
 682 /* Unlink REF from all def-use/use-def chains, etc.  */
 683 int
 684 df_ref_remove (struct df *df, struct ref *ref)
 685 {
 686   if (DF_REF_REG_DEF_P (ref))
 687     {
 688       df_def_unlink (df, ref);
 689       df_ref_unlink (&df->insns[DF_REF_INSN_UID (ref)].defs, ref);
 690     }
 691   else
 692     {
 693       df_use_unlink (df, ref);
 694       df_ref_unlink (&df->insns[DF_REF_INSN_UID (ref)].uses, ref);
 695     }
 696   return 1;
 697 }
 698
 699
 700 /* Unlink DEF from use-def and reg-def chains.  */
 701 static void
 702 df_def_unlink (struct df *df ATTRIBUTE_UNUSED, struct ref *def)
 703 {
 704   struct df_link *du_link;
 705   unsigned int dregno = DF_REF_REGNO (def);
 706
 707   /* Follow def-use chain to find all the uses of this def.  */
 708   for (du_link = DF_REF_CHAIN (def); du_link; du_link = du_link->next)
 709     {
 710       struct ref *use = du_link->ref;
 711
 712       /* Unlink this def from the use-def chain.  */
 713       df_ref_unlink (&DF_REF_CHAIN (use), def);
 714     }
 715   DF_REF_CHAIN (def) = 0;
 716
 717   /* Unlink def from reg-def chain.  */
 718   df_ref_unlink (&df->regs[dregno].defs, def);
 719
 720   df->defs[DF_REF_ID (def)] = 0;
 721 }
 722
 723
 724 /* Unlink use from def-use and reg-use chains.  */
 725 static void
 726 df_use_unlink (struct df *df ATTRIBUTE_UNUSED, struct ref *use)
 727 {
 728   struct df_link *ud_link;
 729   unsigned int uregno = DF_REF_REGNO (use);
 730
 731   /* Follow use-def chain to find all the defs of this use.  */
 732   for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
 733     {
 734       struct ref *def = ud_link->ref;
 735
 736       /* Unlink this use from the def-use chain.  */
 737       df_ref_unlink (&DF_REF_CHAIN (def), use);
 738     }
 739   DF_REF_CHAIN (use) = 0;
 740
 741   /* Unlink use from reg-use chain.  */
 742   df_ref_unlink (&df->regs[uregno].uses, use);
 743
 744   df->uses[DF_REF_ID (use)] = 0;
 745 }
 746 \f
 747 /* Local routines for recording refs.  */
 748
 749
 750 /* Create a new ref of type DF_REF_TYPE for register REG at address
 751    LOC within INSN of BB.  */
 752 static struct ref *
 753 df_ref_create (struct df *df, rtx reg, rtx *loc, rtx insn,
 754                enum df_ref_type ref_type, enum df_ref_flags ref_flags)
 755 {
 756   struct ref *this_ref;
 757
 758   this_ref = pool_alloc (df_ref_pool);
 759   DF_REF_REG (this_ref) = reg;
 760   DF_REF_LOC (this_ref) = loc;
 761   DF_REF_INSN (this_ref) = insn;
 762   DF_REF_CHAIN (this_ref) = 0;
 763   DF_REF_TYPE (this_ref) = ref_type;
 764   DF_REF_FLAGS (this_ref) = ref_flags;
 765   DF_REF_DATA (this_ref) = NULL;
 766
 767   if (ref_type == DF_REF_REG_DEF)
 768     {
 769       if (df->def_id >= df->def_size)
 770         {
 771           /* Make table 25 percent larger.  */
 772           df->def_size += (df->def_size / 4);
 773           df->defs = xrealloc (df->defs,
 774                                df->def_size * sizeof (*df->defs));
 775         }
 776       DF_REF_ID (this_ref) = df->def_id;
 777       df->defs[df->def_id++] = this_ref;
 778     }
 779   else
 780     {
 781       if (df->use_id >= df->use_size)
 782         {
 783           /* Make table 25 percent larger.  */
 784           df->use_size += (df->use_size / 4);
 785           df->uses = xrealloc (df->uses,
 786                                df->use_size * sizeof (*df->uses));
 787         }
 788       DF_REF_ID (this_ref) = df->use_id;
 789       df->uses[df->use_id++] = this_ref;
 790     }
 791   return this_ref;
 792 }
 793
 794
 795 /* Create a new reference of type DF_REF_TYPE for a single register REG,
 796    used inside the LOC rtx of INSN.  */
 797 static void
 798 df_ref_record_1 (struct df *df, rtx reg, rtx *loc, rtx insn,
 799                  enum df_ref_type ref_type, enum df_ref_flags ref_flags)
 800 {
 801   df_ref_create (df, reg, loc, insn, ref_type, ref_flags);
 802 }
 803
 804
 805 /* Create new references of type DF_REF_TYPE for each part of register REG
 806    at address LOC within INSN of BB.  */
 807 static void
 808 df_ref_record (struct df *df, rtx reg, rtx *loc, rtx insn,
 809                enum df_ref_type ref_type, enum df_ref_flags ref_flags)
 810 {
 811   unsigned int regno;
 812
 813   gcc_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
 814
 815   /* For the reg allocator we are interested in some SUBREG rtx's, but not
 816      all.  Notably only those representing a word extraction from a multi-word
 817      reg.  As written in the docu those should have the form
 818      (subreg:SI (reg:M A) N), with size(SImode) > size(Mmode).
 819      XXX Is that true?  We could also use the global word_mode variable.  */
 820   if ((df->flags & DF_SUBREGS) == 0
 821       && GET_CODE (reg) == SUBREG
 822       && (GET_MODE_SIZE (GET_MODE (reg)) < GET_MODE_SIZE (word_mode)
 823           || GET_MODE_SIZE (GET_MODE (reg))
 824                >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (reg)))))
 825     {
 826       loc = &SUBREG_REG (reg);
 827       reg = *loc;
 828       ref_flags |= DF_REF_STRIPPED;
 829     }
 830
 831   regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
 832   if (regno < FIRST_PSEUDO_REGISTER)
 833     {
 834       int i;
 835       int endregno;
 836
 837       if (! (df->flags & DF_HARD_REGS))
 838         return;
 839
 840       /* GET_MODE (reg) is correct here.  We do not want to go into a SUBREG
 841          for the mode, because we only want to add references to regs, which
 842          are really referenced.  E.g., a (subreg:SI (reg:DI 0) 0) does _not_
 843          reference the whole reg 0 in DI mode (which would also include
 844          reg 1, at least, if 0 and 1 are SImode registers).  */
 845       endregno = hard_regno_nregs[regno][GET_MODE (reg)];
 846       if (GET_CODE (reg) == SUBREG)
 847         regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
 848                                       SUBREG_BYTE (reg), GET_MODE (reg));
 849       endregno += regno;
 850
 851       for (i = regno; i < endregno; i++)
 852         df_ref_record_1 (df, regno_reg_rtx[i],
 853                          loc, insn, ref_type, ref_flags);
 854     }
 855   else
 856     {
 857       df_ref_record_1 (df, reg, loc, insn, ref_type, ref_flags);
 858     }
 859 }
 860
 861
 862 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
 863    covered by the outer mode is smaller than that covered by the inner mode,
 864    is a read-modify-write operation.
 865    This function returns true iff the SUBREG X is such a SUBREG.  */
 866 bool
 867 read_modify_subreg_p (rtx x)
 868 {
 869   unsigned int isize, osize;
 870   if (GET_CODE (x) != SUBREG)
 871     return false;
 872   isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
 873   osize = GET_MODE_SIZE (GET_MODE (x));
 874   return (isize > osize && isize > UNITS_PER_WORD);
 875 }
 876
 877
 878 /* Process all the registers defined in the rtx, X.  */
 879 static void
 880 df_def_record_1 (struct df *df, rtx x, basic_block bb, rtx insn)
 881 {
 882   rtx *loc;
 883   rtx dst;
 884   enum df_ref_flags flags = 0;
 885
 886  /* We may recursively call ourselves on EXPR_LIST when dealing with PARALLEL
 887      construct.  */
 888   if (GET_CODE (x) == EXPR_LIST || GET_CODE (x) == CLOBBER)
 889     loc = &XEXP (x, 0);
 890   else
 891     loc = &SET_DEST (x);
 892   dst = *loc;
 893
 894   /* Some targets place small structures in registers for
 895      return values of functions.  */
 896   if (GET_CODE (dst) == PARALLEL && GET_MODE (dst) == BLKmode)
 897     {
 898       int i;
 899
 900       for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
 901         {
 902           rtx temp = XVECEXP (dst, 0, i);
 903           if (GET_CODE (temp) == EXPR_LIST || GET_CODE (temp) == CLOBBER
 904               || GET_CODE (temp) == SET)
 905             df_def_record_1 (df, temp, bb, insn);
 906         }
 907       return;
 908     }
 909
 910   /* Maybe, we should flag the use of STRICT_LOW_PART somehow.  It might
 911      be handy for the reg allocator.  */
 912   while (GET_CODE (dst) == STRICT_LOW_PART
 913          || GET_CODE (dst) == ZERO_EXTRACT
 914          || read_modify_subreg_p (dst))
 915     {
 916       /* Strict low part always contains SUBREG, but we do not want to make
 917          it appear outside, as whole register is always considered.  */
 918       if (GET_CODE (dst) == STRICT_LOW_PART)
 919         {
 920           loc = &XEXP (dst, 0);
 921           dst = *loc;
 922         }
 923       loc = &XEXP (dst, 0);
 924       dst = *loc;
 925       flags |= DF_REF_READ_WRITE;
 926     }
 927
 928   if (REG_P (dst)
 929       || (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst))))
 930     df_ref_record (df, dst, loc, insn, DF_REF_REG_DEF, flags);
 931 }
 932
 933
 934 /* Process all the registers defined in the pattern rtx, X.  */
 935 static void
 936 df_defs_record (struct df *df, rtx x, basic_block bb, rtx insn)
 937 {
 938   RTX_CODE code = GET_CODE (x);
 939
 940   if (code == SET || code == CLOBBER)
 941     {
 942       /* Mark the single def within the pattern.  */
 943       df_def_record_1 (df, x, bb, insn);
 944     }
 945   else if (code == PARALLEL)
 946     {
 947       int i;
 948
 949       /* Mark the multiple defs within the pattern.  */
 950       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
 951         {
 952           code = GET_CODE (XVECEXP (x, 0, i));
 953           if (code == SET || code == CLOBBER)
 954             df_def_record_1 (df, XVECEXP (x, 0, i), bb, insn);
 955         }
 956     }
 957 }
 958
 959
 960 /* Process all the registers used in the rtx at address LOC.  */
 961 static void
 962 df_uses_record (struct df *df, rtx *loc, enum df_ref_type ref_type,
 963                 basic_block bb, rtx insn, enum df_ref_flags flags)
 964 {
 965   RTX_CODE code;
 966   rtx x;
 967  retry:
 968   x = *loc;
 969   if (!x)
 970     return;
 971   code = GET_CODE (x);
 972   switch (code)
 973     {
 974     case LABEL_REF:
 975     case SYMBOL_REF:
 976     case CONST_INT:
 977     case CONST:
 978     case CONST_DOUBLE:
 979     case CONST_VECTOR:
 980     case PC:
 981     case CC0:
 982     case ADDR_VEC:
 983     case ADDR_DIFF_VEC:
 984       return;
 985
 986     case CLOBBER:
 987       /* If we are clobbering a MEM, mark any registers inside the address
 988          as being used.  */
 989       if (MEM_P (XEXP (x, 0)))
 990         df_uses_record (df, &XEXP (XEXP (x, 0), 0),
 991                         DF_REF_REG_MEM_STORE, bb, insn, flags);
 992
 993       /* If we're clobbering a REG then we have a def so ignore.  */
 994       return;
 995
 996     case MEM:
 997       df_uses_record (df, &XEXP (x, 0), DF_REF_REG_MEM_LOAD, bb, insn, 0);
 998       return;
 999
1000     case SUBREG:
1001       /* While we're here, optimize this case.  */
1002
1003       /* In case the SUBREG is not of a REG, do not optimize.  */
1004       if (!REG_P (SUBREG_REG (x)))
1005         {
1006           loc = &SUBREG_REG (x);
1007           df_uses_record (df, loc, ref_type, bb, insn, flags);
1008           return;
1009         }
1010       /* ... Fall through ...  */
1011
1012     case REG:
1013       df_ref_record (df, x, loc, insn, ref_type, flags);
1014       return;
1015
1016     case SET:
1017       {
1018         rtx dst = SET_DEST (x);
1019
1020         df_uses_record (df, &SET_SRC (x), DF_REF_REG_USE, bb, insn, 0);
1021
1022         switch (GET_CODE (dst))
1023           {
1024             case SUBREG:
1025               if (read_modify_subreg_p (dst))
1026                 {
1027                   df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
1028                                   insn, DF_REF_READ_WRITE);
1029                   break;
1030                 }
1031               /* Fall through.  */
1032             case REG:
1033             case PARALLEL:
1034             case SCRATCH:
1035             case PC:
1036             case CC0:
1037                 break;
1038             case MEM:
1039               df_uses_record (df, &XEXP (dst, 0),
1040                               DF_REF_REG_MEM_STORE,
1041                               bb, insn, 0);
1042               break;
1043             case STRICT_LOW_PART:
1044               /* A strict_low_part uses the whole REG and not just the
1045                  SUBREG.  */
1046               dst = XEXP (dst, 0);
1047               gcc_assert (GET_CODE (dst) == SUBREG);
1048               df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
1049                              insn, DF_REF_READ_WRITE);
1050               break;
1051             case ZERO_EXTRACT:
1052             case SIGN_EXTRACT:
1053               df_uses_record (df, &XEXP (dst, 0), DF_REF_REG_USE, bb, insn,
1054                               DF_REF_READ_WRITE);
1055               df_uses_record (df, &XEXP (dst, 1), DF_REF_REG_USE, bb, insn, 0);
1056               df_uses_record (df, &XEXP (dst, 2), DF_REF_REG_USE, bb, insn, 0);
1057               dst = XEXP (dst, 0);
1058               break;
1059             default:
1060               gcc_unreachable ();
1061           }
1062         return;
1063       }
1064
1065     case RETURN:
1066       break;
1067
1068     case ASM_OPERANDS:
1069     case UNSPEC_VOLATILE:
1070     case TRAP_IF:
1071     case ASM_INPUT:
1072       {
1073         /* Traditional and volatile asm instructions must be considered to use
1074            and clobber all hard registers, all pseudo-registers and all of
1075            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
1076
1077            Consider for instance a volatile asm that changes the fpu rounding
1078            mode.  An insn should not be moved across this even if it only uses
1079            pseudo-regs because it might give an incorrectly rounded result.
1080
1081            For now, just mark any regs we can find in ASM_OPERANDS as
1082            used.  */
1083
1084         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1085            We can not just fall through here since then we would be confused
1086            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1087            traditional asms unlike their normal usage.  */
1088         if (code == ASM_OPERANDS)
1089           {
1090             int j;
1091
1092             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1093               df_uses_record (df, &ASM_OPERANDS_INPUT (x, j),
1094                               DF_REF_REG_USE, bb, insn, 0);
1095             return;
1096           }
1097         break;
1098       }
1099
1100     case PRE_DEC:
1101     case POST_DEC:
1102     case PRE_INC:
1103     case POST_INC:
1104     case PRE_MODIFY:
1105     case POST_MODIFY:
1106       /* Catch the def of the register being modified.  */
1107       df_ref_record (df, XEXP (x, 0), &XEXP (x, 0), insn, DF_REF_REG_DEF, DF_REF_READ_WRITE);
1108
1109       /* ... Fall through to handle uses ...  */
1110
1111     default:
1112       break;
1113     }
1114
1115   /* Recursively scan the operands of this expression.  */
1116   {
1117     const char *fmt = GET_RTX_FORMAT (code);
1118     int i;
1119
1120     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1121       {
1122         if (fmt[i] == 'e')
1123           {
1124             /* Tail recursive case: save a function call level.  */
1125             if (i == 0)
1126               {
1127                 loc = &XEXP (x, 0);
1128                 goto retry;
1129               }
1130             df_uses_record (df, &XEXP (x, i), ref_type, bb, insn, flags);
1131           }
1132         else if (fmt[i] == 'E')
1133           {
1134             int j;
1135             for (j = 0; j < XVECLEN (x, i); j++)
1136               df_uses_record (df, &XVECEXP (x, i, j), ref_type,
1137                               bb, insn, flags);
1138           }
1139       }
1140   }
1141 }
1142
1143
1144 /* Record all the df within INSN of basic block BB.  */
1145 static void
1146 df_insn_refs_record (struct df *df, basic_block bb, rtx insn)
1147 {
1148   int i;
1149
1150   if (INSN_P (insn))
1151     {
1152       rtx note;
1153
1154       /* Record register defs.  */
1155       df_defs_record (df, PATTERN (insn), bb, insn);
1156
1157       if (df->flags & DF_EQUIV_NOTES)
1158         for (note = REG_NOTES (insn); note;
1159              note = XEXP (note, 1))
1160           {
1161             switch (REG_NOTE_KIND (note))
1162               {
1163               case REG_EQUIV:
1164               case REG_EQUAL:
1165                 df_uses_record (df, &XEXP (note, 0), DF_REF_REG_USE,
1166                                 bb, insn, 0);
1167               default:
1168                 break;
1169               }
1170           }
1171
1172       if (CALL_P (insn))
1173         {
1174           rtx note;
1175           rtx x;
1176
1177           /* Record the registers used to pass arguments.  */
1178           for (note = CALL_INSN_FUNCTION_USAGE (insn); note;
1179                note = XEXP (note, 1))
1180             {
1181               if (GET_CODE (XEXP (note, 0)) == USE)
1182                 df_uses_record (df, &XEXP (XEXP (note, 0), 0), DF_REF_REG_USE,
1183                                 bb, insn, 0);
1184             }
1185
1186           /* The stack ptr is used (honorarily) by a CALL insn.  */
1187           x = df_reg_use_gen (STACK_POINTER_REGNUM);
1188           df_uses_record (df, &XEXP (x, 0), DF_REF_REG_USE, bb, insn, 0);
1189
1190           if (df->flags & DF_HARD_REGS)
1191             {
1192               /* Calls may also reference any of the global registers,
1193                  so they are recorded as used.  */
1194               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1195                 if (global_regs[i])
1196                   {
1197                     x = df_reg_use_gen (i);
1198                     df_uses_record (df, &XEXP (x, 0),
1199                                     DF_REF_REG_USE, bb, insn, 0);
1200                   }
1201             }
1202         }
1203
1204       /* Record the register uses.  */
1205       df_uses_record (df, &PATTERN (insn),
1206                       DF_REF_REG_USE, bb, insn, 0);
1207
1208       if (CALL_P (insn))
1209         {
1210           rtx note;
1211
1212           /* We do not record hard registers clobbered by the call,
1213              since there are awfully many of them and "defs" created
1214              through them are not interesting (since no use can be legally
1215              reached by them).  So we must just make sure we include them when
1216              computing kill bitmaps.  */
1217
1218           /* There may be extra registers to be clobbered.  */
1219           for (note = CALL_INSN_FUNCTION_USAGE (insn);
1220                note;
1221                note = XEXP (note, 1))
1222             if (GET_CODE (XEXP (note, 0)) == CLOBBER)
1223               df_defs_record (df, XEXP (note, 0), bb, insn);
1224         }
1225     }
1226 }
1227
1228
1229 /* Record all the refs within the basic block BB.  */
1230 static void
1231 df_bb_refs_record (struct df *df, basic_block bb)
1232 {
1233   rtx insn;
1234
1235   /* Scan the block an insn at a time from beginning to end.  */
1236   FOR_BB_INSNS (bb, insn)
1237     {
1238       if (INSN_P (insn))
1239         {
1240           /* Record defs within INSN.  */
1241           df_insn_refs_record (df, bb, insn);
1242         }
1243     }
1244 }
1245
1246
1247 /* Record all the refs in the basic blocks specified by BLOCKS.  */
1248 static void
1249 df_refs_record (struct df *df, bitmap blocks)
1250 {
1251   basic_block bb;
1252
1253   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1254     {
1255       df_bb_refs_record (df, bb);
1256     });
1257 }
1258 \f
1259 /* Dataflow analysis routines.  */
1260
1261 /* Create reg-def chains for basic block BB.  These are a list of
1262    definitions for each register.  */
1263
1264 static void
1265 df_bb_reg_def_chain_create (struct df *df, basic_block bb)
1266 {
1267   rtx insn;
1268
1269   /* Perhaps the defs should be sorted using a depth first search
1270      of the CFG (or possibly a breadth first search).  */
1271
1272   FOR_BB_INSNS_REVERSE (bb, insn)
1273     {
1274       struct df_link *link;
1275       unsigned int uid = INSN_UID (insn);
1276
1277       if (! INSN_P (insn))
1278         continue;
1279
1280       for (link = df->insns[uid].defs; link; link = link->next)
1281         {
1282           struct ref *def = link->ref;
1283           unsigned int dregno = DF_REF_REGNO (def);
1284
1285           /* Do not add ref's to the chain twice, i.e., only add new
1286              refs.  XXX the same could be done by testing if the
1287              current insn is a modified (or a new) one.  This would be
1288              faster.  */
1289           if (DF_REF_ID (def) < df->def_id_save)
1290             continue;
1291
1292           df->regs[dregno].defs = df_link_create (def, df->regs[dregno].defs);
1293         }
1294     }
1295 }
1296
1297
1298 /* Create reg-def chains for each basic block within BLOCKS.  These
1299    are a list of definitions for each register.  If REDO is true, add
1300    all defs, otherwise just add the new defs.  */
1301
1302 static void
1303 df_reg_def_chain_create (struct df *df, bitmap blocks, bool redo)
1304 {
1305   basic_block bb;
1306 #ifdef ENABLE_CHECKING
1307   unsigned regno;
1308 #endif
1309   unsigned old_def_id_save = df->def_id_save;
1310
1311   if (redo)
1312     {
1313 #ifdef ENABLE_CHECKING
1314       for (regno = 0; regno < df->n_regs; regno++)
1315         gcc_assert (!df->regs[regno].defs);
1316 #endif
1317
1318       /* Pretend that all defs are new.  */
1319       df->def_id_save = 0;
1320     }
1321
1322   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1323     {
1324       df_bb_reg_def_chain_create (df, bb);
1325     });
1326
1327   df->def_id_save = old_def_id_save;
1328 }
1329
1330 /* Remove all reg-def chains stored in the dataflow object DF.  */
1331
1332 static void
1333 df_reg_def_chain_clean (struct df *df)
1334 {
1335   unsigned regno;
1336
1337   for (regno = 0; regno < df->n_regs; regno++)
1338     free_reg_ref_chain (&df->regs[regno].defs);
1339 }
1340
1341 /* Create reg-use chains for basic block BB.  These are a list of uses
1342    for each register.  */
1343
1344 static void
1345 df_bb_reg_use_chain_create (struct df *df, basic_block bb)
1346 {
1347   rtx insn;
1348
1349   /* Scan in forward order so that the last uses appear at the start
1350      of the chain.  */
1351
1352   FOR_BB_INSNS (bb, insn)
1353     {
1354       struct df_link *link;
1355       unsigned int uid = INSN_UID (insn);
1356
1357       if (! INSN_P (insn))
1358         continue;
1359
1360       for (link = df->insns[uid].uses; link; link = link->next)
1361         {
1362           struct ref *use = link->ref;
1363           unsigned int uregno = DF_REF_REGNO (use);
1364
1365           /* Do not add ref's to the chain twice, i.e., only add new
1366              refs.  XXX the same could be done by testing if the
1367              current insn is a modified (or a new) one.  This would be
1368              faster.  */
1369           if (DF_REF_ID (use) < df->use_id_save)
1370             continue;
1371
1372           df->regs[uregno].uses
1373             = df_link_create (use, df->regs[uregno].uses);
1374         }
1375     }
1376 }
1377
1378
1379 /* Create reg-use chains for each basic block within BLOCKS.  These
1380    are a list of uses for each register.  If REDO is true, remove the
1381    old reg-use chains first, otherwise just add new uses to them.  */
1382
1383 static void
1384 df_reg_use_chain_create (struct df *df, bitmap blocks, bool redo)
1385 {
1386   basic_block bb;
1387 #ifdef ENABLE_CHECKING
1388   unsigned regno;
1389 #endif
1390   unsigned old_use_id_save = df->use_id_save;
1391
1392   if (redo)
1393     {
1394 #ifdef ENABLE_CHECKING
1395       for (regno = 0; regno < df->n_regs; regno++)
1396         gcc_assert (!df->regs[regno].uses);
1397 #endif
1398
1399       /* Pretend that all uses are new.  */
1400       df->use_id_save = 0;
1401     }
1402
1403   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1404     {
1405       df_bb_reg_use_chain_create (df, bb);
1406     });
1407
1408   df->use_id_save = old_use_id_save;
1409 }
1410
1411 /* Remove all reg-use chains stored in the dataflow object DF.  */
1412
1413 static void
1414 df_reg_use_chain_clean (struct df *df)
1415 {
1416   unsigned regno;
1417
1418   for (regno = 0; regno < df->n_regs; regno++)
1419     free_reg_ref_chain (&df->regs[regno].uses);
1420 }
1421
1422 /* Create def-use chains from reaching use bitmaps for basic block BB.  */
1423 static void
1424 df_bb_du_chain_create (struct df *df, basic_block bb, bitmap ru)
1425 {
1426   struct bb_info *bb_info = DF_BB_INFO (df, bb);
1427   rtx insn;
1428
1429   bitmap_copy (ru, bb_info->ru_out);
1430
1431   /* For each def in BB create a linked list (chain) of uses
1432      reached from the def.  */
1433   FOR_BB_INSNS_REVERSE (bb, insn)
1434     {
1435       struct df_link *def_link;
1436       struct df_link *use_link;
1437       unsigned int uid = INSN_UID (insn);
1438
1439       if (! INSN_P (insn))
1440         continue;
1441
1442       /* For each def in insn...  */
1443       for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
1444         {
1445           struct ref *def = def_link->ref;
1446           unsigned int dregno = DF_REF_REGNO (def);
1447
1448           DF_REF_CHAIN (def) = 0;
1449
1450           /* While the reg-use chains are not essential, it
1451              is _much_ faster to search these short lists rather
1452              than all the reaching uses, especially for large functions.  */
1453           for (use_link = df->regs[dregno].uses; use_link;
1454                use_link = use_link->next)
1455             {
1456               struct ref *use = use_link->ref;
1457
1458               if (bitmap_bit_p (ru, DF_REF_ID (use)))
1459                 {
1460                   DF_REF_CHAIN (def)
1461                     = df_link_create (use, DF_REF_CHAIN (def));
1462
1463                   bitmap_clear_bit (ru, DF_REF_ID (use));
1464                 }
1465             }
1466         }
1467
1468       /* For each use in insn...  */
1469       for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
1470         {
1471           struct ref *use = use_link->ref;
1472           bitmap_set_bit (ru, DF_REF_ID (use));
1473         }
1474     }
1475 }
1476
1477
1478 /* Create def-use chains from reaching use bitmaps for basic blocks
1479    in BLOCKS.  */
1480 static void
1481 df_du_chain_create (struct df *df, bitmap blocks)
1482 {
1483   bitmap ru;
1484   basic_block bb;
1485
1486   ru = BITMAP_ALLOC (NULL);
1487
1488   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1489     {
1490       df_bb_du_chain_create (df, bb, ru);
1491     });
1492
1493   BITMAP_FREE (ru);
1494 }
1495
1496
1497 /* Create use-def chains from reaching def bitmaps for basic block BB.  */
1498 static void
1499 df_bb_ud_chain_create (struct df *df, basic_block bb)
1500 {
1501   struct bb_info *bb_info = DF_BB_INFO (df, bb);
1502   struct ref **reg_def_last = df->reg_def_last;
1503   rtx insn;
1504
1505   memset (reg_def_last, 0, df->n_regs * sizeof (struct ref *));
1506
1507   /* For each use in BB create a linked list (chain) of defs
1508      that reach the use.  */
1509   FOR_BB_INSNS (bb, insn)
1510     {
1511       unsigned int uid = INSN_UID (insn);
1512       struct df_link *use_link;
1513       struct df_link *def_link;
1514
1515       if (! INSN_P (insn))
1516         continue;
1517
1518       /* For each use in insn...  */
1519       for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
1520         {
1521           struct ref *use = use_link->ref;
1522           unsigned int regno = DF_REF_REGNO (use);
1523
1524           DF_REF_CHAIN (use) = 0;
1525
1526           /* Has regno been defined in this BB yet?  If so, use
1527              the last def as the single entry for the use-def
1528              chain for this use.  Otherwise, we need to add all
1529              the defs using this regno that reach the start of
1530              this BB.  */
1531           if (reg_def_last[regno])
1532             {
1533               DF_REF_CHAIN (use)
1534                 = df_link_create (reg_def_last[regno], 0);
1535             }
1536           else
1537             {
1538               /* While the reg-def chains are not essential, it is
1539                  _much_ faster to search these short lists rather than
1540                  all the reaching defs, especially for large
1541                  functions.  */
1542               for (def_link = df->regs[regno].defs; def_link;
1543                    def_link = def_link->next)
1544                 {
1545                   struct ref *def = def_link->ref;
1546
1547                   if (bitmap_bit_p (bb_info->rd_in, DF_REF_ID (def)))
1548                     {
1549                       DF_REF_CHAIN (use)
1550                         = df_link_create (def, DF_REF_CHAIN (use));
1551                     }
1552                 }
1553             }
1554         }
1555
1556
1557       /* For each def in insn... record the last def of each reg.  */
1558       for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
1559         {
1560           struct ref *def = def_link->ref;
1561           int dregno = DF_REF_REGNO (def);
1562
1563           reg_def_last[dregno] = def;
1564         }
1565     }
1566 }
1567
1568
1569 /* Create use-def chains from reaching def bitmaps for basic blocks
1570    within BLOCKS.  */
1571 static void
1572 df_ud_chain_create (struct df *df, bitmap blocks)
1573 {
1574   basic_block bb;
1575
1576   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1577     {
1578       df_bb_ud_chain_create (df, bb);
1579     });
1580 }
1581 \f
1582
1583
1584 static void
1585 df_rd_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
1586                          void *out, void *gen, void *kill,
1587                          void *data ATTRIBUTE_UNUSED)
1588 {
1589   *changed = bitmap_ior_and_compl (out, gen, in, kill);
1590 }
1591
1592
1593 static void
1594 df_ru_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
1595                          void *out, void *gen, void *kill,
1596                          void *data ATTRIBUTE_UNUSED)
1597 {
1598   *changed = bitmap_ior_and_compl (in, gen, out, kill);
1599 }
1600
1601
1602 static void
1603 df_lr_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
1604                          void *out, void *use, void *def,
1605                          void *data ATTRIBUTE_UNUSED)
1606 {
1607   *changed = bitmap_ior_and_compl (in, use, out, def);
1608 }
1609
1610
1611 /* Compute local reaching def info for basic block BB.  */
1612 static void
1613 df_bb_rd_local_compute (struct df *df, basic_block bb, bitmap call_killed_defs)
1614 {
1615   struct bb_info *bb_info = DF_BB_INFO (df, bb);
1616   rtx insn;
1617   bitmap seen = BITMAP_ALLOC (NULL);
1618   bool call_seen = false;
1619
1620   FOR_BB_INSNS_REVERSE (bb, insn)
1621     {
1622       unsigned int uid = INSN_UID (insn);
1623       struct df_link *def_link;
1624
1625       if (! INSN_P (insn))
1626         continue;
1627
1628       for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
1629         {
1630           struct ref *def = def_link->ref;
1631           unsigned int regno = DF_REF_REGNO (def);
1632           struct df_link *def2_link;
1633
1634           if (bitmap_bit_p (seen, regno)
1635               || (call_seen
1636                   && regno < FIRST_PSEUDO_REGISTER
1637                   && TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)))
1638             continue;
1639
1640           for (def2_link = df->regs[regno].defs; def2_link;
1641                def2_link = def2_link->next)
1642             {
1643               struct ref *def2 = def2_link->ref;
1644
1645               /* Add all defs of this reg to the set of kills.  This
1646                  is greedy since many of these defs will not actually
1647                  be killed by this BB but it keeps things a lot
1648                  simpler.  */
1649               bitmap_set_bit (bb_info->rd_kill, DF_REF_ID (def2));
1650             }
1651
1652           bitmap_set_bit (bb_info->rd_gen, DF_REF_ID (def));
1653           bitmap_set_bit (seen, regno);
1654         }
1655
1656       if (CALL_P (insn) && (df->flags & DF_HARD_REGS))
1657         {
1658           bitmap_ior_into (bb_info->rd_kill, call_killed_defs);
1659           call_seen = 1;
1660         }
1661     }
1662
1663   BITMAP_FREE (seen);
1664 }
1665
1666
1667 /* Compute local reaching def info for each basic block within BLOCKS.  */
1668 static void
1669 df_rd_local_compute (struct df *df, bitmap blocks)
1670 {
1671   basic_block bb;
1672   bitmap killed_by_call = NULL;
1673   unsigned regno;
1674   struct df_link *def_link;
1675
1676   if (df->flags & DF_HARD_REGS)
1677     {
1678       killed_by_call = BITMAP_ALLOC (NULL);
1679       for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1680         {
1681           if (!TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
1682             continue;
1683
1684           for (def_link = df->regs[regno].defs;
1685                def_link;
1686                def_link = def_link->next)
1687             bitmap_set_bit (killed_by_call, DF_REF_ID (def_link->ref));
1688         }
1689     }
1690
1691   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1692   {
1693     df_bb_rd_local_compute (df, bb, killed_by_call);
1694   });
1695
1696   if (df->flags & DF_HARD_REGS)
1697     BITMAP_FREE (killed_by_call);
1698 }
1699
1700
1701 /* Compute local reaching use (upward exposed use) info for basic
1702    block BB.  */
1703 static void
1704 df_bb_ru_local_compute (struct df *df, basic_block bb)
1705 {
1706   /* This is much more tricky than computing reaching defs.  With
1707      reaching defs, defs get killed by other defs.  With upwards
1708      exposed uses, these get killed by defs with the same regno.  */
1709
1710   struct bb_info *bb_info = DF_BB_INFO (df, bb);
1711   rtx insn;
1712
1713
1714   FOR_BB_INSNS_REVERSE (bb, insn)
1715     {
1716       unsigned int uid = INSN_UID (insn);
1717       struct df_link *def_link;
1718       struct df_link *use_link;
1719
1720       if (! INSN_P (insn))
1721         continue;
1722
1723       for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
1724         {
1725           struct ref *def = def_link->ref;
1726           unsigned int dregno = DF_REF_REGNO (def);
1727
1728           for (use_link = df->regs[dregno].uses; use_link;
1729                use_link = use_link->next)
1730             {
1731               struct ref *use = use_link->ref;
1732
1733               /* Add all uses of this reg to the set of kills.  This
1734                  is greedy since many of these uses will not actually
1735                  be killed by this BB but it keeps things a lot
1736                  simpler.  */
1737               bitmap_set_bit (bb_info->ru_kill, DF_REF_ID (use));
1738
1739               /* Zap from the set of gens for this BB.  */
1740               bitmap_clear_bit (bb_info->ru_gen, DF_REF_ID (use));
1741             }
1742         }
1743
1744       for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
1745         {
1746           struct ref *use = use_link->ref;
1747           /* Add use to set of gens in this BB.  */
1748           bitmap_set_bit (bb_info->ru_gen, DF_REF_ID (use));
1749         }
1750     }
1751 }
1752
1753
1754 /* Compute local reaching use (upward exposed use) info for each basic
1755    block within BLOCKS.  */
1756 static void
1757 df_ru_local_compute (struct df *df, bitmap blocks)
1758 {
1759   basic_block bb;
1760
1761   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1762   {
1763     df_bb_ru_local_compute (df, bb);
1764   });
1765 }
1766
1767
1768 /* Compute local live variable info for basic block BB.  */
1769 static void
1770 df_bb_lr_local_compute (struct df *df, basic_block bb)
1771 {
1772   struct bb_info *bb_info = DF_BB_INFO (df, bb);
1773   rtx insn;
1774
1775   FOR_BB_INSNS_REVERSE (bb, insn)
1776     {
1777       unsigned int uid = INSN_UID (insn);
1778       struct df_link *link;
1779
1780       if (! INSN_P (insn))
1781         continue;
1782
1783       for (link = df->insns[uid].defs; link; link = link->next)
1784         {
1785           struct ref *def = link->ref;
1786           unsigned int dregno = DF_REF_REGNO (def);
1787
1788           /* Add def to set of defs in this BB.  */
1789           bitmap_set_bit (bb_info->lr_def, dregno);
1790
1791           bitmap_clear_bit (bb_info->lr_use, dregno);
1792         }
1793
1794       for (link = df->insns[uid].uses; link; link = link->next)
1795         {
1796           struct ref *use = link->ref;
1797           /* Add use to set of uses in this BB.  */
1798           bitmap_set_bit (bb_info->lr_use, DF_REF_REGNO (use));
1799         }
1800     }
1801 }
1802
1803
1804 /* Compute local live variable info for each basic block within BLOCKS.  */
1805 static void
1806 df_lr_local_compute (struct df *df, bitmap blocks)
1807 {
1808   basic_block bb;
1809
1810   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1811   {
1812     df_bb_lr_local_compute (df, bb);
1813   });
1814 }
1815
1816
1817 /* Compute register info: lifetime, bb, and number of defs and uses
1818    for basic block BB.  */
1819 static void
1820 df_bb_reg_info_compute (struct df *df, basic_block bb, bitmap live)
1821 {
1822   struct reg_info *reg_info = df->regs;
1823   struct bb_info *bb_info = DF_BB_INFO (df, bb);
1824   rtx insn;
1825
1826   bitmap_copy (live, bb_info->lr_out);
1827
1828   FOR_BB_INSNS_REVERSE (bb, insn)
1829     {
1830       unsigned int uid = INSN_UID (insn);
1831       unsigned int regno;
1832       struct df_link *link;
1833       bitmap_iterator bi;
1834
1835       if (! INSN_P (insn))
1836         continue;
1837
1838       for (link = df->insns[uid].defs; link; link = link->next)
1839         {
1840           struct ref *def = link->ref;
1841           unsigned int dregno = DF_REF_REGNO (def);
1842
1843           /* Kill this register.  */
1844           bitmap_clear_bit (live, dregno);
1845           reg_info[dregno].n_defs++;
1846         }
1847
1848       for (link = df->insns[uid].uses; link; link = link->next)
1849         {
1850           struct ref *use = link->ref;
1851           unsigned int uregno = DF_REF_REGNO (use);
1852
1853           /* This register is now live.  */
1854           bitmap_set_bit (live, uregno);
1855           reg_info[uregno].n_uses++;
1856         }
1857
1858       /* Increment lifetimes of all live registers.  */
1859       EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
1860         {
1861           reg_info[regno].lifetime++;
1862         }
1863     }
1864 }
1865
1866
1867 /* Compute register info: lifetime, bb, and number of defs and uses.  */
1868 static void
1869 df_reg_info_compute (struct df *df, bitmap blocks)
1870 {
1871   basic_block bb;
1872   bitmap live;
1873
1874   live = BITMAP_ALLOC (NULL);
1875
1876   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1877   {
1878     df_bb_reg_info_compute (df, bb, live);
1879   });
1880
1881   BITMAP_FREE (live);
1882 }
1883
1884
1885 /* Assign LUIDs for BB.  */
1886 static int
1887 df_bb_luids_set (struct df *df, basic_block bb)
1888 {
1889   rtx insn;
1890   int luid = 0;
1891
1892   /* The LUIDs are monotonically increasing for each basic block.  */
1893
1894   FOR_BB_INSNS (bb, insn)
1895     {
1896       if (INSN_P (insn))
1897         DF_INSN_LUID (df, insn) = luid++;
1898       DF_INSN_LUID (df, insn) = luid;
1899     }
1900   return luid;
1901 }
1902
1903
1904 /* Assign LUIDs for each basic block within BLOCKS.  */
1905 static int
1906 df_luids_set (struct df *df, bitmap blocks)
1907 {
1908   basic_block bb;
1909   int total = 0;
1910
1911   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1912     {
1913       total += df_bb_luids_set (df, bb);
1914     });
1915   return total;
1916 }
1917
1918
1919 /* Perform dataflow analysis using existing DF structure for blocks
1920    within BLOCKS.  If BLOCKS is zero, use all basic blocks in the CFG.  */
1921 static void
1922 df_analyze_1 (struct df *df, bitmap blocks, int flags, int update)
1923 {
1924   int aflags;
1925   int dflags;
1926   basic_block bb;
1927   struct dataflow dflow;
1928
1929   dflags = 0;
1930   aflags = flags;
1931   if (flags & DF_UD_CHAIN)
1932     aflags |= DF_RD | DF_RD_CHAIN;
1933
1934   if (flags & DF_DU_CHAIN)
1935     aflags |= DF_RU;
1936
1937   if (flags & DF_RU)
1938     aflags |= DF_RU_CHAIN;
1939
1940   if (flags & DF_REG_INFO)
1941     aflags |= DF_LR;
1942
1943   if (! blocks)
1944     blocks = df->all_blocks;
1945
1946   df->flags = flags;
1947   if (update)
1948     {
1949       df_refs_update (df, NULL);
1950       /* More fine grained incremental dataflow analysis would be
1951          nice.  For now recompute the whole shebang for the
1952          modified blocks.  */
1953 #if 0
1954       df_refs_unlink (df, blocks);
1955 #endif
1956       /* All the def-use, use-def chains can be potentially
1957          modified by changes in one block.  The size of the
1958          bitmaps can also change.  */
1959     }
1960   else
1961     {
1962       /* Scan the function for all register defs and uses.  */
1963       df_refs_queue (df);
1964       df_refs_record (df, blocks);
1965
1966       /* Link all the new defs and uses to the insns.  */
1967       df_refs_process (df);
1968     }
1969
1970   /* Allocate the bitmaps now the total number of defs and uses are
1971      known.  If the number of defs or uses have changed, then
1972      these bitmaps need to be reallocated.  */
1973   df_bitmaps_alloc (df, NULL, aflags);
1974
1975   /* Set the LUIDs for each specified basic block.  */
1976   df_luids_set (df, blocks);
1977
1978   /* Recreate reg-def and reg-use chains from scratch so that first
1979      def is at the head of the reg-def chain and the last use is at
1980      the head of the reg-use chain.  This is only important for
1981      regs local to a basic block as it speeds up searching.  */
1982   if (aflags & DF_RD_CHAIN)
1983     {
1984       df_reg_def_chain_create (df, blocks, false);
1985     }
1986
1987   if (aflags & DF_RU_CHAIN)
1988     {
1989       df_reg_use_chain_create (df, blocks, false);
1990     }
1991
1992   df->dfs_order = xmalloc (sizeof (int) * n_basic_blocks - NUM_FIXED_BLOCKS);
1993   df->rc_order = xmalloc (sizeof (int) * n_basic_blocks - NUM_FIXED_BLOCKS);
1994   df->rts_order = xmalloc (sizeof (int) * n_basic_blocks - NUM_FIXED_BLOCKS);
1995
1996   pre_and_rev_post_order_compute (df->dfs_order, df->rc_order, false);
1997   post_order_compute (df->rts_order, false);
1998   if (aflags & DF_RD)
1999     {
2000       /* Compute the sets of gens and kills for the defs of each bb.  */
2001       dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
2002       dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
2003       dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
2004       dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
2005
2006       df_rd_local_compute (df, df->flags & DF_RD ? blocks : df->all_blocks);
2007       FOR_EACH_BB (bb)
2008         {
2009           dflow.in[bb->index] = DF_BB_INFO (df, bb)->rd_in;
2010           dflow.out[bb->index] = DF_BB_INFO (df, bb)->rd_out;
2011           dflow.gen[bb->index] = DF_BB_INFO (df, bb)->rd_gen;
2012           dflow.kill[bb->index] = DF_BB_INFO (df, bb)->rd_kill;
2013         }
2014
2015       dflow.repr = SR_BITMAP;
2016       dflow.dir = DF_FORWARD;
2017       dflow.conf_op = DF_UNION;
2018       dflow.transfun = df_rd_transfer_function;
2019       dflow.n_blocks = n_basic_blocks - NUM_FIXED_BLOCKS;
2020       dflow.order = df->rc_order;
2021       dflow.data = NULL;
2022
2023       iterative_dataflow (&dflow);
2024       free (dflow.in);
2025       free (dflow.out);
2026       free (dflow.gen);
2027       free (dflow.kill);
2028     }
2029
2030   if (aflags & DF_UD_CHAIN)
2031     {
2032       /* Create use-def chains.  */
2033       df_ud_chain_create (df, df->all_blocks);
2034
2035       if (! (flags & DF_RD))
2036         dflags |= DF_RD;
2037     }
2038
2039   if (aflags & DF_RU)
2040     {
2041       /* Compute the sets of gens and kills for the upwards exposed
2042          uses in each bb.  */
2043       dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
2044       dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
2045       dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
2046       dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
2047
2048       df_ru_local_compute (df, df->flags & DF_RU ? blocks : df->all_blocks);
2049
2050       FOR_EACH_BB (bb)
2051         {
2052           dflow.in[bb->index] = DF_BB_INFO (df, bb)->ru_in;
2053           dflow.out[bb->index] = DF_BB_INFO (df, bb)->ru_out;
2054           dflow.gen[bb->index] = DF_BB_INFO (df, bb)->ru_gen;
2055           dflow.kill[bb->index] = DF_BB_INFO (df, bb)->ru_kill;
2056         }
2057
2058       dflow.repr = SR_BITMAP;
2059       dflow.dir = DF_BACKWARD;
2060       dflow.conf_op = DF_UNION;
2061       dflow.transfun = df_ru_transfer_function;
2062       dflow.n_blocks = n_basic_blocks - NUM_FIXED_BLOCKS;
2063       dflow.order = df->rts_order;
2064       dflow.data = NULL;
2065
2066       iterative_dataflow (&dflow);
2067       free (dflow.in);
2068       free (dflow.out);
2069       free (dflow.gen);
2070       free (dflow.kill);
2071     }
2072
2073   if (aflags & DF_DU_CHAIN)
2074     {
2075       /* Create def-use chains.  */
2076       df_du_chain_create (df, df->all_blocks);
2077
2078       if (! (flags & DF_RU))
2079         dflags |= DF_RU;
2080     }
2081
2082   /* Free up bitmaps that are no longer required.  */
2083   if (dflags)
2084     df_bitmaps_free (df, dflags);
2085
2086   if (aflags & DF_LR)
2087     {
2088       /* Compute the sets of defs and uses of live variables.  */
2089       dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
2090       dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
2091       dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
2092       dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
2093
2094       df_lr_local_compute (df, df->flags & DF_LR ? blocks : df->all_blocks);
2095
2096       FOR_EACH_BB (bb)
2097         {
2098           dflow.in[bb->index] = DF_BB_INFO (df, bb)->lr_in;
2099           dflow.out[bb->index] = DF_BB_INFO (df, bb)->lr_out;
2100           dflow.gen[bb->index] = DF_BB_INFO (df, bb)->lr_use;
2101           dflow.kill[bb->index] = DF_BB_INFO (df, bb)->lr_def;
2102         }
2103
2104       dflow.repr = SR_BITMAP;
2105       dflow.dir = DF_BACKWARD;
2106       dflow.conf_op = DF_UNION;
2107       dflow.transfun = df_lr_transfer_function;
2108       dflow.n_blocks = n_basic_blocks - NUM_FIXED_BLOCKS;
2109       dflow.order = df->rts_order;
2110       dflow.data = NULL;
2111
2112       iterative_dataflow (&dflow);
2113       free (dflow.in);
2114       free (dflow.out);
2115       free (dflow.gen);
2116       free (dflow.kill);
2117     }
2118
2119   if (aflags & DF_REG_INFO)
2120     {
2121       df_reg_info_compute (df, df->all_blocks);
2122     }
2123
2124   free (df->dfs_order);
2125   free (df->rc_order);
2126   free (df->rts_order);
2127 }
2128
2129
2130 /* Initialize dataflow analysis.  */
2131 struct df *
2132 df_init (void)
2133 {
2134   struct df *df;
2135
2136   df = xcalloc (1, sizeof (struct df));
2137
2138   /* Squirrel away a global for debugging.  */
2139   ddf = df;
2140
2141   return df;
2142 }
2143
2144
2145 /* Start queuing refs.  */
2146 static int
2147 df_refs_queue (struct df *df)
2148 {
2149   df->def_id_save = df->def_id;
2150   df->use_id_save = df->use_id;
2151   /* ???? Perhaps we should save current obstack state so that we can
2152      unwind it.  */
2153   return 0;
2154 }
2155
2156
2157 /* Process queued refs.  */
2158 static int
2159 df_refs_process (struct df *df)
2160 {
2161   unsigned int i;
2162
2163   /* Build new insn-def chains.  */
2164   for (i = df->def_id_save; i != df->def_id; i++)
2165     {
2166       struct ref *def = df->defs[i];
2167       unsigned int uid = DF_REF_INSN_UID (def);
2168
2169       /* Add def to head of def list for INSN.  */
2170       df->insns[uid].defs
2171         = df_link_create (def, df->insns[uid].defs);
2172     }
2173
2174   /* Build new insn-use chains.  */
2175   for (i = df->use_id_save; i != df->use_id; i++)
2176     {
2177       struct ref *use = df->uses[i];
2178       unsigned int uid = DF_REF_INSN_UID (use);
2179
2180       /* Add use to head of use list for INSN.  */
2181       df->insns[uid].uses
2182         = df_link_create (use, df->insns[uid].uses);
2183     }
2184   return 0;
2185 }
2186
2187
2188 /* Update refs for basic block BB.  */
2189 static int
2190 df_bb_refs_update (struct df *df, basic_block bb)
2191 {
2192   rtx insn;
2193   int count = 0;
2194
2195   /* While we have to scan the chain of insns for this BB, we do not
2196      need to allocate and queue a long chain of BB/INSN pairs.  Using
2197      a bitmap for insns_modified saves memory and avoids queuing
2198      duplicates.  */
2199
2200   FOR_BB_INSNS (bb, insn)
2201     {
2202       unsigned int uid;
2203
2204       uid = INSN_UID (insn);
2205
2206       if (bitmap_bit_p (df->insns_modified, uid))
2207         {
2208           /* Delete any allocated refs of this insn.  MPH,  FIXME.  */
2209           df_insn_refs_unlink (df, bb, insn);
2210
2211           /* Scan the insn for refs.  */
2212           df_insn_refs_record (df, bb, insn);
2213
2214           count++;
2215         }
2216     }
2217   return count;
2218 }
2219
2220
2221 /* Process all the modified/deleted insns that were queued.  */
2222 static int
2223 df_refs_update (struct df *df, bitmap blocks)
2224 {
2225   basic_block bb;
2226   unsigned count = 0, bbno;
2227
2228   df->n_regs = max_reg_num ();
2229   if (df->n_regs >= df->reg_size)
2230     df_reg_table_realloc (df, 0);
2231
2232   df_refs_queue (df);
2233
2234   if (!blocks)
2235     {
2236       FOR_EACH_BB_IN_BITMAP (df->bbs_modified, 0, bb,
2237         {
2238           count += df_bb_refs_update (df, bb);
2239         });
2240     }
2241   else
2242     {
2243       bitmap_iterator bi;
2244
2245       EXECUTE_IF_AND_IN_BITMAP (df->bbs_modified, blocks, 0, bbno, bi)
2246         {
2247           count += df_bb_refs_update (df, BASIC_BLOCK (bbno));
2248         }
2249     }
2250
2251   df_refs_process (df);
2252   return count;
2253 }
2254
2255
2256 /* Return nonzero if any of the requested blocks in the bitmap
2257    BLOCKS have been modified.  */
2258 static int
2259 df_modified_p (struct df *df, bitmap blocks)
2260 {
2261   int update = 0;
2262   basic_block bb;
2263
2264   if (!df->n_bbs)
2265     return 0;
2266
2267   FOR_EACH_BB (bb)
2268     if (bitmap_bit_p (df->bbs_modified, bb->index)
2269         && (! blocks || (blocks == (bitmap) -1) || bitmap_bit_p (blocks, bb->index)))
2270     {
2271       update = 1;
2272       break;
2273     }
2274
2275   return update;
2276 }
2277
2278 /* Analyze dataflow info for the basic blocks specified by the bitmap
2279    BLOCKS, or for the whole CFG if BLOCKS is zero, or just for the
2280    modified blocks if BLOCKS is -1.  */
2281
2282 int
2283 df_analyze (struct df *df, bitmap blocks, int flags)
2284 {
2285   int update;
2286
2287   /* We could deal with additional basic blocks being created by
2288      rescanning everything again.  */
2289   gcc_assert (!df->n_bbs || df->n_bbs == (unsigned int) last_basic_block);
2290
2291   update = df_modified_p (df, blocks);
2292   if (update || (flags != df->flags))
2293     {
2294       if (! blocks)
2295         {
2296           if (df->n_bbs)
2297             {
2298               /* Recompute everything from scratch.  */
2299               df_free (df);
2300             }
2301           /* Allocate and initialize data structures.  */
2302           df_alloc (df, max_reg_num ());
2303           df_analyze_1 (df, 0, flags, 0);
2304           update = 1;
2305         }
2306       else
2307         {
2308           if (blocks == (bitmap) -1)
2309             blocks = df->bbs_modified;
2310
2311           gcc_assert (df->n_bbs);
2312
2313           df_analyze_1 (df, blocks, flags, 1);
2314           bitmap_zero (df->bbs_modified);
2315           bitmap_zero (df->insns_modified);
2316         }
2317     }
2318   return update;
2319 }
2320
2321 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
2322    the order of the remaining entries.  Returns the length of the resulting
2323    list.  */
2324
2325 static unsigned
2326 prune_to_subcfg (int list[], unsigned len, bitmap blocks)
2327 {
2328   unsigned act, last;
2329
2330   for (act = 0, last = 0; act < len; act++)
2331     if (bitmap_bit_p (blocks, list[act]))
2332       list[last++] = list[act];
2333
2334   return last;
2335 }
2336
2337 /* Alternative entry point to the analysis.  Analyze just the part of the cfg
2338    graph induced by BLOCKS.
2339
2340    TODO I am not quite sure how to avoid code duplication with df_analyze_1
2341    here, and simultaneously not make even greater chaos in it.  We behave
2342    slightly differently in some details, especially in handling modified
2343    insns.  */
2344
2345 void
2346 df_analyze_subcfg (struct df *df, bitmap blocks, int flags)
2347 {
2348   rtx insn;
2349   basic_block bb;
2350   struct dataflow dflow;
2351   unsigned n_blocks;
2352
2353   if (flags & DF_UD_CHAIN)
2354     flags |= DF_RD | DF_RD_CHAIN;
2355   if (flags & DF_DU_CHAIN)
2356     flags |= DF_RU;
2357   if (flags & DF_RU)
2358     flags |= DF_RU_CHAIN;
2359   if (flags & DF_REG_INFO)
2360     flags |= DF_LR;
2361
2362   if (!df->n_bbs)
2363     {
2364       df_alloc (df, max_reg_num ());
2365
2366       /* Mark all insns as modified.  */
2367
2368       FOR_EACH_BB (bb)
2369         {
2370           FOR_BB_INSNS (bb, insn)
2371             {
2372               df_insn_modify (df, bb, insn);
2373             }
2374         }
2375     }
2376
2377   df->flags = flags;
2378
2379   df_reg_def_chain_clean (df);
2380   df_reg_use_chain_clean (df);
2381
2382   df_refs_update (df, blocks);
2383
2384   /* Clear the updated stuff from ``modified'' bitmaps.  */
2385   FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
2386     {
2387       if (bitmap_bit_p (df->bbs_modified, bb->index))
2388         {
2389           FOR_BB_INSNS (bb, insn)
2390             {
2391               bitmap_clear_bit (df->insns_modified, INSN_UID (insn));
2392             }
2393
2394           bitmap_clear_bit (df->bbs_modified, bb->index);
2395         }
2396     });
2397
2398   /* Allocate the bitmaps now the total number of defs and uses are
2399      known.  If the number of defs or uses have changed, then
2400      these bitmaps need to be reallocated.  */
2401   df_bitmaps_alloc (df, blocks, flags);
2402
2403   /* Set the LUIDs for each specified basic block.  */
2404   df_luids_set (df, blocks);
2405
2406   /* Recreate reg-def and reg-use chains from scratch so that first
2407      def is at the head of the reg-def chain and the last use is at
2408      the head of the reg-use chain.  This is only important for
2409      regs local to a basic block as it speeds up searching.  */
2410   if (flags & DF_RD_CHAIN)
2411     {
2412       df_reg_def_chain_create (df, blocks, true);
2413     }
2414
2415   if (flags & DF_RU_CHAIN)
2416     {
2417       df_reg_use_chain_create (df, blocks, true);
2418     }
2419
2420   df->dfs_order = xmalloc (sizeof (int) * n_basic_blocks - NUM_FIXED_BLOCKS);
2421   df->rc_order = xmalloc (sizeof (int) * n_basic_blocks - NUM_FIXED_BLOCKS);
2422   df->rts_order = xmalloc (sizeof (int) * n_basic_blocks - NUM_FIXED_BLOCKS);
2423
2424   pre_and_rev_post_order_compute (df->dfs_order, df->rc_order, false);
2425   post_order_compute (df->rts_order, false);
2426
2427   n_blocks = prune_to_subcfg (df->dfs_order, n_basic_blocks - NUM_FIXED_BLOCKS, blocks);
2428   prune_to_subcfg (df->rc_order, n_basic_blocks - NUM_FIXED_BLOCKS, blocks);
2429   prune_to_subcfg (df->rts_order, n_basic_blocks - NUM_FIXED_BLOCKS, blocks);
2430
2431   dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
2432   dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
2433   dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
2434   dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
2435
2436   if (flags & DF_RD)
2437     {
2438       /* Compute the sets of gens and kills for the defs of each bb.  */
2439       df_rd_local_compute (df, blocks);
2440
2441       FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
2442         {
2443           dflow.in[bb->index] = DF_BB_INFO (df, bb)->rd_in;
2444           dflow.out[bb->index] = DF_BB_INFO (df, bb)->rd_out;
2445           dflow.gen[bb->index] = DF_BB_INFO (df, bb)->rd_gen;
2446           dflow.kill[bb->index] = DF_BB_INFO (df, bb)->rd_kill;
2447         });
2448
2449       dflow.repr = SR_BITMAP;
2450       dflow.dir = DF_FORWARD;
2451       dflow.conf_op = DF_UNION;
2452       dflow.transfun = df_rd_transfer_function;
2453       dflow.n_blocks = n_blocks;
2454       dflow.order = df->rc_order;
2455       dflow.data = NULL;
2456
2457       iterative_dataflow (&dflow);
2458     }
2459
2460   if (flags & DF_UD_CHAIN)
2461     {
2462       /* Create use-def chains.  */
2463       df_ud_chain_create (df, blocks);
2464     }
2465
2466   if (flags & DF_RU)
2467     {
2468       /* Compute the sets of gens and kills for the upwards exposed
2469          uses in each bb.  */
2470       df_ru_local_compute (df, blocks);
2471
2472       FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
2473         {
2474           dflow.in[bb->index] = DF_BB_INFO (df, bb)->ru_in;
2475           dflow.out[bb->index] = DF_BB_INFO (df, bb)->ru_out;
2476           dflow.gen[bb->index] = DF_BB_INFO (df, bb)->ru_gen;
2477           dflow.kill[bb->index] = DF_BB_INFO (df, bb)->ru_kill;
2478         });
2479
2480       dflow.repr = SR_BITMAP;
2481       dflow.dir = DF_BACKWARD;
2482       dflow.conf_op = DF_UNION;
2483       dflow.transfun = df_ru_transfer_function;
2484       dflow.n_blocks = n_blocks;
2485       dflow.order = df->rts_order;
2486       dflow.data = NULL;
2487
2488       iterative_dataflow (&dflow);
2489     }
2490
2491   if (flags & DF_DU_CHAIN)
2492     {
2493       /* Create def-use chains.  */
2494       df_du_chain_create (df, blocks);
2495     }
2496
2497   if (flags & DF_LR)
2498     {
2499       /* Compute the sets of defs and uses of live variables.  */
2500       df_lr_local_compute (df, blocks);
2501
2502       FOR_EACH_BB (bb)
2503         {
2504           dflow.in[bb->index] = DF_BB_INFO (df, bb)->lr_in;
2505           dflow.out[bb->index] = DF_BB_INFO (df, bb)->lr_out;
2506           dflow.gen[bb->index] = DF_BB_INFO (df, bb)->lr_use;
2507           dflow.kill[bb->index] = DF_BB_INFO (df, bb)->lr_def;
2508         }
2509
2510       dflow.repr = SR_BITMAP;
2511       dflow.dir = DF_BACKWARD;
2512       dflow.conf_op = DF_UNION;
2513       dflow.transfun = df_lr_transfer_function;
2514       dflow.n_blocks = n_blocks;
2515       dflow.order = df->rts_order;
2516       dflow.data = NULL;
2517
2518       iterative_dataflow (&dflow);
2519     }
2520
2521   if (flags & DF_REG_INFO)
2522     {
2523       df_reg_info_compute (df, blocks);
2524     }
2525
2526   free (dflow.in);
2527   free (dflow.out);
2528   free (dflow.gen);
2529   free (dflow.kill);
2530
2531   free (df->dfs_order);
2532   free (df->rc_order);
2533   free (df->rts_order);
2534 }
2535
2536 /* Free all the dataflow info and the DF structure.  */
2537 void
2538 df_finish (struct df *df)
2539 {
2540   df_free (df);
2541   free (df);
2542 }
2543
2544 /* Unlink INSN from its reference information.  */
2545 static void
2546 df_insn_refs_unlink (struct df *df, basic_block bb ATTRIBUTE_UNUSED, rtx insn)
2547 {
2548   struct df_link *link;
2549   unsigned int uid;
2550
2551   uid = INSN_UID (insn);
2552
2553   /* Unlink all refs defined by this insn.  */
2554   for (link = df->insns[uid].defs; link; link = link->next)
2555     df_def_unlink (df, link->ref);
2556
2557   /* Unlink all refs used by this insn.  */
2558   for (link = df->insns[uid].uses; link; link = link->next)
2559     df_use_unlink (df, link->ref);
2560
2561   df->insns[uid].defs = 0;
2562   df->insns[uid].uses = 0;
2563 }
2564
2565
2566 #if 0
2567 /* Unlink all the insns within BB from their reference information.  */
2568 static void
2569 df_bb_refs_unlink (struct df *df, basic_block bb)
2570 {
2571   rtx insn;
2572
2573   /* Scan the block an insn at a time from beginning to end.  */
2574   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
2575     {
2576       if (INSN_P (insn))
2577         {
2578           /* Unlink refs for INSN.  */
2579           df_insn_refs_unlink (df, bb, insn);
2580         }
2581       if (insn == BB_END (bb))
2582         break;
2583     }
2584 }
2585
2586
2587 /* Unlink all the refs in the basic blocks specified by BLOCKS.
2588    Not currently used.  */
2589 static void
2590 df_refs_unlink (struct df *df, bitmap blocks)
2591 {
2592   basic_block bb;
2593
2594   if (blocks)
2595     {
2596       FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
2597       {
2598         df_bb_refs_unlink (df, bb);
2599       });
2600     }
2601   else
2602     {
2603       FOR_EACH_BB (bb)
2604         df_bb_refs_unlink (df, bb);
2605     }
2606 }
2607 #endif
2608 \f
2609 /* Functions to modify insns.  */
2610
2611
2612 /* Delete INSN and all its reference information.  */
2613 rtx
2614 df_insn_delete (struct df *df, basic_block bb ATTRIBUTE_UNUSED, rtx insn)
2615 {
2616   /* If the insn is a jump, we should perhaps call delete_insn to
2617      handle the JUMP_LABEL?  */
2618
2619   /* We should not be deleting the NOTE_INSN_BASIC_BLOCK or label.  */
2620   gcc_assert (insn != BB_HEAD (bb));
2621
2622   /* Delete the insn.  */
2623   delete_insn (insn);
2624
2625   df_insn_modify (df, bb, insn);
2626
2627   return NEXT_INSN (insn);
2628 }
2629
2630 /* Mark that basic block BB was modified.  */
2631
2632 static void
2633 df_bb_modify (struct df *df, basic_block bb)
2634 {
2635   if ((unsigned) bb->index >= df->n_bbs)
2636     df_bb_table_realloc (df, bb->index);
2637
2638   bitmap_set_bit (df->bbs_modified, bb->index);
2639 }
2640
2641 /* Mark that INSN within BB may have changed  (created/modified/deleted).
2642    This may be called multiple times for the same insn.  There is no
2643    harm calling this function if the insn wasn't changed; it will just
2644    slow down the rescanning of refs.  */
2645 void
2646 df_insn_modify (struct df *df, basic_block bb, rtx insn)
2647 {
2648   unsigned int uid;
2649
2650   uid = INSN_UID (insn);
2651   if (uid >= df->insn_size)
2652     df_insn_table_realloc (df, uid);
2653
2654   df_bb_modify (df, bb);
2655   bitmap_set_bit (df->insns_modified, uid);
2656
2657   /* For incremental updating on the fly, perhaps we could make a copy
2658      of all the refs of the original insn and turn them into
2659      anti-refs.  When df_refs_update finds these anti-refs, it annihilates
2660      the original refs.  If validate_change fails then these anti-refs
2661      will just get ignored.  */
2662 }
2663
2664 /* Check if INSN was marked as changed.  Of course the correctness of
2665    the information depends on whether the instruction was really modified
2666    at the time df_insn_modify was called.  */
2667 bool
2668 df_insn_modified_p (struct df *df, rtx insn)
2669 {
2670   unsigned int uid;
2671
2672   uid = INSN_UID (insn);
2673   return (df->insns_modified
2674           && uid < df->insn_size
2675           && bitmap_bit_p (df->insns_modified, uid));
2676 }
2677
2678 typedef struct replace_args
2679 {
2680   rtx match;
2681   rtx replacement;
2682   rtx insn;
2683   int modified;
2684 } replace_args;
2685
2686
2687 /* Replace mem pointed to by PX with its associated pseudo register.
2688    DATA is actually a pointer to a structure describing the
2689    instruction currently being scanned and the MEM we are currently
2690    replacing.  */
2691 static int
2692 df_rtx_mem_replace (rtx *px, void *data)
2693 {
2694   replace_args *args = (replace_args *) data;
2695   rtx mem = *px;
2696
2697   if (mem == NULL_RTX)
2698     return 0;
2699
2700   switch (GET_CODE (mem))
2701     {
2702     case MEM:
2703       break;
2704
2705     case CONST_DOUBLE:
2706       /* We're not interested in the MEM associated with a
2707          CONST_DOUBLE, so there's no need to traverse into one.  */
2708       return -1;
2709
2710     default:
2711       /* This is not a MEM.  */
2712       return 0;
2713     }
2714
2715   if (!rtx_equal_p (args->match, mem))
2716     /* This is not the MEM we are currently replacing.  */
2717     return 0;
2718
2719   /* Actually replace the MEM.  */
2720   validate_change (args->insn, px, args->replacement, 1);
2721   args->modified++;
2722
2723   return 0;
2724 }
2725
2726
2727 int
2728 df_insn_mem_replace (struct df *df, basic_block bb, rtx insn, rtx mem, rtx reg)
2729 {
2730   replace_args args;
2731
2732   args.insn = insn;
2733   args.match = mem;
2734   args.replacement = reg;
2735   args.modified = 0;
2736
2737   /* Search and replace all matching mems within insn.  */
2738   for_each_rtx (&insn, df_rtx_mem_replace, &args);
2739
2740   if (args.modified)
2741     df_insn_modify (df, bb, insn);
2742
2743   /* ???? FIXME.  We may have a new def or one or more new uses of REG
2744      in INSN.  REG should be a new pseudo so it won't affect the
2745      dataflow information that we currently have.  We should add
2746      the new uses and defs to INSN and then recreate the chains
2747      when df_analyze is called.  */
2748   return args.modified;
2749 }
2750
2751
2752 /* Replace one register with another.  Called through for_each_rtx; PX
2753    points to the rtx being scanned.  DATA is actually a pointer to a
2754    structure of arguments.  */
2755 static int
2756 df_rtx_reg_replace (rtx *px, void *data)
2757 {
2758   rtx x = *px;
2759   replace_args *args = (replace_args *) data;
2760
2761   if (x == NULL_RTX)
2762     return 0;
2763
2764   if (x == args->match)
2765     {
2766       validate_change (args->insn, px, args->replacement, 1);
2767       args->modified++;
2768     }
2769
2770   return 0;
2771 }
2772
2773
2774 /* Replace the reg within every ref on CHAIN that is within the set
2775    BLOCKS of basic blocks with NEWREG.  Also update the regs within
2776    REG_NOTES.  */
2777 void
2778 df_refs_reg_replace (struct df *df, bitmap blocks, struct df_link *chain, rtx oldreg, rtx newreg)
2779 {
2780   struct df_link *link;
2781   replace_args args;
2782
2783   if (! blocks)
2784     blocks = df->all_blocks;
2785
2786   args.match = oldreg;
2787   args.replacement = newreg;
2788   args.modified = 0;
2789
2790   for (link = chain; link; link = link->next)
2791     {
2792       struct ref *ref = link->ref;
2793       rtx insn = DF_REF_INSN (ref);
2794
2795       if (! INSN_P (insn))
2796         continue;
2797
2798       gcc_assert (bitmap_bit_p (blocks, DF_REF_BBNO (ref)));
2799
2800       df_ref_reg_replace (df, ref, oldreg, newreg);
2801
2802       /* Replace occurrences of the reg within the REG_NOTES.  */
2803       if ((! link->next || DF_REF_INSN (ref)
2804            != DF_REF_INSN (link->next->ref))
2805           && REG_NOTES (insn))
2806         {
2807           args.insn = insn;
2808           for_each_rtx (&REG_NOTES (insn), df_rtx_reg_replace, &args);
2809         }
2810     }
2811 }
2812
2813
2814 /* Replace all occurrences of register OLDREG with register NEWREG in
2815    blocks defined by bitmap BLOCKS.  This also replaces occurrences of
2816    OLDREG in the REG_NOTES but only for insns containing OLDREG.  This
2817    routine expects the reg-use and reg-def chains to be valid.  */
2818 int
2819 df_reg_replace (struct df *df, bitmap blocks, rtx oldreg, rtx newreg)
2820 {
2821   unsigned int oldregno = REGNO (oldreg);
2822
2823   df_refs_reg_replace (df, blocks, df->regs[oldregno].defs, oldreg, newreg);
2824   df_refs_reg_replace (df, blocks, df->regs[oldregno].uses, oldreg, newreg);
2825   return 1;
2826 }
2827
2828
2829 /* Try replacing the reg within REF with NEWREG.  Do not modify
2830    def-use/use-def chains.  */
2831 int
2832 df_ref_reg_replace (struct df *df, struct ref *ref, rtx oldreg, rtx newreg)
2833 {
2834   /* Check that insn was deleted by being converted into a NOTE.  If
2835    so ignore this insn.  */
2836   if (! INSN_P (DF_REF_INSN (ref)))
2837     return 0;
2838
2839   gcc_assert (!oldreg || oldreg == DF_REF_REG (ref));
2840
2841   if (! validate_change (DF_REF_INSN (ref), DF_REF_LOC (ref), newreg, 1))
2842     return 0;
2843
2844   df_insn_modify (df, DF_REF_BB (ref), DF_REF_INSN (ref));
2845   return 1;
2846 }
2847
2848
2849 struct ref*
2850 df_bb_def_use_swap (struct df *df, basic_block bb, rtx def_insn, rtx use_insn, unsigned int regno)
2851 {
2852   struct ref *def;
2853   struct ref *use;
2854   int def_uid;
2855   int use_uid;
2856   struct df_link *link;
2857
2858   def = df_bb_insn_regno_first_def_find (df, bb, def_insn, regno);
2859   if (! def)
2860     return 0;
2861
2862   use = df_bb_insn_regno_last_use_find (df, bb, use_insn, regno);
2863   if (! use)
2864     return 0;
2865
2866   /* The USE no longer exists.  */
2867   use_uid = INSN_UID (use_insn);
2868   df_use_unlink (df, use);
2869   df_ref_unlink (&df->insns[use_uid].uses, use);
2870
2871   /* The DEF requires shifting so remove it from DEF_INSN
2872      and add it to USE_INSN by reusing LINK.  */
2873   def_uid = INSN_UID (def_insn);
2874   link = df_ref_unlink (&df->insns[def_uid].defs, def);
2875   link->ref = def;
2876   link->next = df->insns[use_uid].defs;
2877   df->insns[use_uid].defs = link;
2878
2879 #if 0
2880   link = df_ref_unlink (&df->regs[regno].defs, def);
2881   link->ref = def;
2882   link->next = df->regs[regno].defs;
2883   df->insns[regno].defs = link;
2884 #endif
2885
2886   DF_REF_INSN (def) = use_insn;
2887   return def;
2888 }
2889
2890
2891 /* Record df between FIRST_INSN and LAST_INSN inclusive.  All new
2892    insns must be processed by this routine.  */
2893 static void
2894 df_insns_modify (struct df *df, basic_block bb, rtx first_insn, rtx last_insn)
2895 {
2896   rtx insn;
2897
2898   for (insn = first_insn; ; insn = NEXT_INSN (insn))
2899     {
2900       unsigned int uid;
2901
2902       /* A non-const call should not have slipped through the net.  If
2903          it does, we need to create a new basic block.  Ouch.  The
2904          same applies for a label.  */
2905       gcc_assert ((!CALL_P (insn) || CONST_OR_PURE_CALL_P (insn))
2906                   && !LABEL_P (insn));
2907
2908       uid = INSN_UID (insn);
2909
2910       if (uid >= df->insn_size)
2911         df_insn_table_realloc (df, uid);
2912
2913       df_insn_modify (df, bb, insn);
2914
2915       if (insn == last_insn)
2916         break;
2917     }
2918 }
2919
2920
2921 /* Emit PATTERN before INSN within BB.  */
2922 rtx
2923 df_pattern_emit_before (struct df *df, rtx pattern, basic_block bb, rtx insn)
2924 {
2925   rtx ret_insn;
2926   rtx prev_insn = PREV_INSN (insn);
2927
2928   /* We should not be inserting before the start of the block.  */
2929   gcc_assert (insn != BB_HEAD (bb));
2930   ret_insn = emit_insn_before (pattern, insn);
2931   if (ret_insn == insn)
2932     return ret_insn;
2933
2934   df_insns_modify (df, bb, NEXT_INSN (prev_insn), ret_insn);
2935   return ret_insn;
2936 }
2937
2938
2939 /* Emit PATTERN after INSN within BB.  */
2940 rtx
2941 df_pattern_emit_after (struct df *df, rtx pattern, basic_block bb, rtx insn)
2942 {
2943   rtx ret_insn;
2944
2945   ret_insn = emit_insn_after (pattern, insn);
2946   if (ret_insn == insn)
2947     return ret_insn;
2948
2949   df_insns_modify (df, bb, NEXT_INSN (insn), ret_insn);
2950   return ret_insn;
2951 }
2952
2953
2954 /* Emit jump PATTERN after INSN within BB.  */
2955 rtx
2956 df_jump_pattern_emit_after (struct df *df, rtx pattern, basic_block bb, rtx insn)
2957 {
2958   rtx ret_insn;
2959
2960   ret_insn = emit_jump_insn_after (pattern, insn);
2961   if (ret_insn == insn)
2962     return ret_insn;
2963
2964   df_insns_modify (df, bb, NEXT_INSN (insn), ret_insn);
2965   return ret_insn;
2966 }
2967
2968
2969 /* Move INSN within BB before BEFORE_INSN within BEFORE_BB.
2970
2971    This function should only be used to move loop invariant insns
2972    out of a loop where it has been proven that the def-use info
2973    will still be valid.  */
2974 rtx
2975 df_insn_move_before (struct df *df, basic_block bb, rtx insn, basic_block before_bb, rtx before_insn)
2976 {
2977   struct df_link *link;
2978   unsigned int uid;
2979
2980   if (! bb)
2981     return df_pattern_emit_before (df, insn, before_bb, before_insn);
2982
2983   uid = INSN_UID (insn);
2984
2985   /* Change bb for all df defined and used by this insn.  */
2986   for (link = df->insns[uid].defs; link; link = link->next)
2987     DF_REF_BB (link->ref) = before_bb;
2988   for (link = df->insns[uid].uses; link; link = link->next)
2989     DF_REF_BB (link->ref) = before_bb;
2990
2991   /* The lifetimes of the registers used in this insn will be reduced
2992      while the lifetimes of the registers defined in this insn
2993      are likely to be increased.  */
2994
2995   /* ???? Perhaps all the insns moved should be stored on a list
2996      which df_analyze removes when it recalculates data flow.  */
2997
2998   return emit_insn_before (insn, before_insn);
2999 }
3000 \f
3001 /* Functions to query dataflow information.  */
3002
3003
3004 int
3005 df_insn_regno_def_p (struct df *df, basic_block bb ATTRIBUTE_UNUSED,
3006                      rtx insn, unsigned int regno)
3007 {
3008   unsigned int uid;
3009   struct df_link *link;
3010
3011   uid = INSN_UID (insn);
3012
3013   for (link = df->insns[uid].defs; link; link = link->next)
3014     {
3015       struct ref *def = link->ref;
3016
3017       if (DF_REF_REGNO (def) == regno)
3018         return 1;
3019     }
3020
3021   return 0;
3022 }
3023
3024 /* Finds the reference corresponding to the definition of REG in INSN.
3025    DF is the dataflow object.  */
3026
3027 struct ref *
3028 df_find_def (struct df *df, rtx insn, rtx reg)
3029 {
3030   struct df_link *defs;
3031
3032   if (GET_CODE (reg) == SUBREG)
3033     reg = SUBREG_REG (reg);
3034   gcc_assert (REG_P (reg));
3035
3036   for (defs = DF_INSN_DEFS (df, insn); defs; defs = defs->next)
3037     if (rtx_equal_p (DF_REF_REAL_REG (defs->ref), reg))
3038       return defs->ref;
3039
3040   return NULL;
3041 }
3042
3043 /* Finds the reference corresponding to the use of REG in INSN.
3044    DF is the dataflow object.  */
3045
3046 struct ref *
3047 df_find_use (struct df *df, rtx insn, rtx reg)
3048 {
3049   struct df_link *uses;
3050
3051   if (GET_CODE (reg) == SUBREG)
3052     reg = SUBREG_REG (reg);
3053   gcc_assert (REG_P (reg));
3054
3055   for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
3056     if (rtx_equal_p (DF_REF_REAL_REG (uses->ref), reg))
3057       return uses->ref;
3058
3059   return NULL;
3060 }
3061
3062 /* Return 1 if REG is referenced in INSN, zero otherwise.  */
3063
3064 int
3065 df_reg_used (struct df *df, rtx insn, rtx reg)
3066 {
3067   return df_find_use (df, insn, reg) != NULL;
3068 }
3069
3070 static int
3071 df_def_dominates_all_uses_p (struct df *df ATTRIBUTE_UNUSED, struct ref *def)
3072 {
3073   struct df_link *du_link;
3074
3075   /* Follow def-use chain to find all the uses of this def.  */
3076   for (du_link = DF_REF_CHAIN (def); du_link; du_link = du_link->next)
3077     {
3078       struct ref *use = du_link->ref;
3079       struct df_link *ud_link;
3080
3081       /* Follow use-def chain to check all the defs for this use.  */
3082       for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
3083         if (ud_link->ref != def)
3084           return 0;
3085     }
3086   return 1;
3087 }
3088
3089
3090 int
3091 df_insn_dominates_all_uses_p (struct df *df, basic_block bb ATTRIBUTE_UNUSED,
3092                               rtx insn)
3093 {
3094   unsigned int uid;
3095   struct df_link *link;
3096
3097   uid = INSN_UID (insn);
3098
3099   for (link = df->insns[uid].defs; link; link = link->next)
3100     {
3101       struct ref *def = link->ref;
3102
3103       if (! df_def_dominates_all_uses_p (df, def))
3104         return 0;
3105     }
3106
3107   return 1;
3108 }
3109
3110
3111 /* Return nonzero if all DF dominates all the uses within the bitmap
3112    BLOCKS.  */
3113 static int
3114 df_def_dominates_uses_p (struct df *df ATTRIBUTE_UNUSED, struct ref *def,
3115                          bitmap blocks)
3116 {
3117   struct df_link *du_link;
3118
3119   /* Follow def-use chain to find all the uses of this def.  */
3120   for (du_link = DF_REF_CHAIN (def); du_link; du_link = du_link->next)
3121     {
3122       struct ref *use = du_link->ref;
3123       struct df_link *ud_link;
3124
3125       /* Only worry about the uses within BLOCKS.  For example,
3126       consider a register defined within a loop that is live at the
3127       loop exits.  */
3128       if (bitmap_bit_p (blocks, DF_REF_BBNO (use)))
3129         {
3130           /* Follow use-def chain to check all the defs for this use.  */
3131           for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
3132             if (ud_link->ref != def)
3133               return 0;
3134         }
3135     }
3136   return 1;
3137 }
3138
3139
3140 /* Return nonzero if all the defs of INSN within BB dominates
3141    all the corresponding uses.  */
3142 int
3143 df_insn_dominates_uses_p (struct df *df, basic_block bb ATTRIBUTE_UNUSED,
3144                           rtx insn, bitmap blocks)
3145 {
3146   unsigned int uid;
3147   struct df_link *link;
3148
3149   uid = INSN_UID (insn);
3150
3151   for (link = df->insns[uid].defs; link; link = link->next)
3152     {
3153       struct ref *def = link->ref;
3154
3155       /* Only consider the defs within BLOCKS.  */
3156       if (bitmap_bit_p (blocks, DF_REF_BBNO (def))
3157           && ! df_def_dominates_uses_p (df, def, blocks))
3158         return 0;
3159     }
3160   return 1;
3161 }
3162
3163
3164 /* Return the basic block that REG referenced in or NULL if referenced
3165    in multiple basic blocks.  */
3166 basic_block
3167 df_regno_bb (struct df *df, unsigned int regno)
3168 {
3169   struct df_link *defs = df->regs[regno].defs;
3170   struct df_link *uses = df->regs[regno].uses;
3171   struct ref *def = defs ? defs->ref : 0;
3172   struct ref *use = uses ? uses->ref : 0;
3173   basic_block bb_def = def ? DF_REF_BB (def) : 0;
3174   basic_block bb_use = use ? DF_REF_BB (use) : 0;
3175
3176   /* Compare blocks of first def and last use.  ???? FIXME.  What if
3177      the reg-def and reg-use lists are not correctly ordered.  */
3178   return bb_def == bb_use ? bb_def : 0;
3179 }
3180
3181
3182 /* Return nonzero if REG used in multiple basic blocks.  */
3183 int
3184 df_reg_global_p (struct df *df, rtx reg)
3185 {
3186   return df_regno_bb (df, REGNO (reg)) != 0;
3187 }
3188
3189
3190 /* Return total lifetime (in insns) of REG.  */
3191 int
3192 df_reg_lifetime (struct df *df, rtx reg)
3193 {
3194   return df->regs[REGNO (reg)].lifetime;
3195 }
3196
3197
3198 /* Return nonzero if REG live at start of BB.  */
3199 int
3200 df_bb_reg_live_start_p (struct df *df, basic_block bb, rtx reg)
3201 {
3202   struct bb_info *bb_info = DF_BB_INFO (df, bb);
3203
3204   gcc_assert (bb_info->lr_in);
3205
3206   return bitmap_bit_p (bb_info->lr_in, REGNO (reg));
3207 }
3208
3209
3210 /* Return nonzero if REG live at end of BB.  */
3211 int
3212 df_bb_reg_live_end_p (struct df *df, basic_block bb, rtx reg)
3213 {
3214   struct bb_info *bb_info = DF_BB_INFO (df, bb);
3215
3216   gcc_assert (bb_info->lr_in);
3217
3218   return bitmap_bit_p (bb_info->lr_out, REGNO (reg));
3219 }
3220
3221
3222 /* Return -1 if life of REG1 before life of REG2, 1 if life of REG1
3223    after life of REG2, or 0, if the lives overlap.  */
3224 int
3225 df_bb_regs_lives_compare (struct df *df, basic_block bb, rtx reg1, rtx reg2)
3226 {
3227   unsigned int regno1 = REGNO (reg1);
3228   unsigned int regno2 = REGNO (reg2);
3229   struct ref *def1;
3230   struct ref *use1;
3231   struct ref *def2;
3232   struct ref *use2;
3233
3234
3235   /* The regs must be local to BB.  */
3236   gcc_assert (df_regno_bb (df, regno1) == bb
3237               && df_regno_bb (df, regno2) == bb);
3238
3239   def2 = df_bb_regno_first_def_find (df, bb, regno2);
3240   use1 = df_bb_regno_last_use_find (df, bb, regno1);
3241
3242   if (DF_INSN_LUID (df, DF_REF_INSN (def2))
3243       > DF_INSN_LUID (df, DF_REF_INSN (use1)))
3244     return -1;
3245
3246   def1 = df_bb_regno_first_def_find (df, bb, regno1);
3247   use2 = df_bb_regno_last_use_find (df, bb, regno2);
3248
3249   if (DF_INSN_LUID (df, DF_REF_INSN (def1))
3250       > DF_INSN_LUID (df, DF_REF_INSN (use2)))
3251     return 1;
3252
3253   return 0;
3254 }
3255
3256
3257 /* Return true if the definition DEF, which is in the same basic
3258    block as USE, is available at USE.  So DEF may as well be
3259    dead, in which case using it will extend its live range.  */
3260 bool
3261 df_local_def_available_p (struct df *df, struct ref *def, struct ref *use)
3262 {
3263   struct df_link *link;
3264   int def_luid = DF_INSN_LUID (df, DF_REF_INSN (def));
3265   int in_bb = 0;
3266   unsigned int regno = REGNO (def->reg);
3267   basic_block bb;
3268
3269   /* The regs must be local to BB.  */
3270   gcc_assert (DF_REF_BB (def) == DF_REF_BB (use));
3271   bb = DF_REF_BB (def);
3272
3273   /* This assumes that the reg-def list is ordered such that for any
3274      BB, the first def is found first.  However, since the BBs are not
3275      ordered, the first def in the chain is not necessarily the first
3276      def in the function.  */
3277   for (link = df->regs[regno].defs; link; link = link->next)
3278     {
3279       struct ref *this_def = link->ref;
3280       if (DF_REF_BB (this_def) == bb)
3281         {
3282           int this_luid = DF_INSN_LUID (df, DF_REF_INSN (this_def));
3283           /* Do nothing with defs coming before DEF.  */
3284           if (this_luid > def_luid)
3285             return this_luid > DF_INSN_LUID (df, DF_REF_INSN (use));
3286
3287           in_bb = 1;
3288         }
3289       else if (in_bb)
3290         /* DEF was the last in its basic block.  */
3291         return 1;
3292     }
3293
3294   /* DEF was the last in the function.  */
3295   return 1;
3296 }
3297
3298
3299 /* Return last use of REGNO within BB.  */
3300 struct ref *
3301 df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
3302 {
3303   struct df_link *link;
3304
3305   /* This assumes that the reg-use list is ordered such that for any
3306      BB, the last use is found first.  However, since the BBs are not
3307      ordered, the first use in the chain is not necessarily the last
3308      use in the function.  */
3309   for (link = df->regs[regno].uses; link; link = link->next)
3310     {
3311       struct ref *use = link->ref;
3312
3313       if (DF_REF_BB (use) == bb)
3314         return use;
3315     }
3316   return 0;
3317 }
3318
3319
3320 /* Return first def of REGNO within BB.  */
3321 struct ref *
3322 df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
3323 {
3324   struct df_link *link;
3325
3326   /* This assumes that the reg-def list is ordered such that for any
3327      BB, the first def is found first.  However, since the BBs are not
3328      ordered, the first def in the chain is not necessarily the first
3329      def in the function.  */
3330   for (link = df->regs[regno].defs; link; link = link->next)
3331     {
3332       struct ref *def = link->ref;
3333
3334       if (DF_REF_BB (def) == bb)
3335         return def;
3336     }
3337   return 0;
3338 }
3339
3340 /* Return last def of REGNO within BB.  */
3341 struct ref *
3342 df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
3343 {
3344   struct df_link *link;
3345   struct ref *last_def = NULL;
3346   int in_bb = 0;
3347
3348   /* This assumes that the reg-def list is ordered such that for any
3349      BB, the first def is found first.  However, since the BBs are not
3350      ordered, the first def in the chain is not necessarily the first
3351      def in the function.  */
3352   for (link = df->regs[regno].defs; link; link = link->next)
3353     {
3354       struct ref *def = link->ref;
3355       /* The first time in the desired block.  */
3356       if (DF_REF_BB (def) == bb)
3357           in_bb = 1;
3358       /* The last def in the desired block.  */
3359       else if (in_bb)
3360         return last_def;
3361       last_def = def;
3362     }
3363   return last_def;
3364 }
3365
3366 /* Return last use of REGNO inside INSN within BB.  */
3367 static struct ref *
3368 df_bb_insn_regno_last_use_find (struct df *df,
3369                                 basic_block bb ATTRIBUTE_UNUSED, rtx insn,
3370                                 unsigned int regno)
3371 {
3372   unsigned int uid;
3373   struct df_link *link;
3374
3375   uid = INSN_UID (insn);
3376
3377   for (link = df->insns[uid].uses; link; link = link->next)
3378     {
3379       struct ref *use = link->ref;
3380
3381       if (DF_REF_REGNO (use) == regno)
3382         return use;
3383     }
3384
3385   return 0;
3386 }
3387
3388
3389 /* Return first def of REGNO inside INSN within BB.  */
3390 static struct ref *
3391 df_bb_insn_regno_first_def_find (struct df *df,
3392                                  basic_block bb ATTRIBUTE_UNUSED, rtx insn,
3393                                  unsigned int regno)
3394 {
3395   unsigned int uid;
3396   struct df_link *link;
3397
3398   uid = INSN_UID (insn);
3399
3400   for (link = df->insns[uid].defs; link; link = link->next)
3401     {
3402       struct ref *def = link->ref;
3403
3404       if (DF_REF_REGNO (def) == regno)
3405         return def;
3406     }
3407
3408   return 0;
3409 }
3410
3411
3412 /* Return insn using REG if the BB contains only a single
3413    use and def of REG.  */
3414 rtx
3415 df_bb_single_def_use_insn_find (struct df *df, basic_block bb, rtx insn, rtx reg)
3416 {
3417   struct ref *def;
3418   struct ref *use;
3419   struct df_link *du_link;
3420
3421   def = df_bb_insn_regno_first_def_find (df, bb, insn, REGNO (reg));
3422
3423   gcc_assert (def);
3424
3425   du_link = DF_REF_CHAIN (def);
3426
3427   if (! du_link)
3428     return NULL_RTX;
3429
3430   use = du_link->ref;
3431
3432   /* Check if def is dead.  */
3433   if (! use)
3434     return NULL_RTX;
3435
3436   /* Check for multiple uses.  */
3437   if (du_link->next)
3438     return NULL_RTX;
3439
3440   return DF_REF_INSN (use);
3441 }
3442 \f
3443 /* Functions for debugging/dumping dataflow information.  */
3444
3445
3446 /* Dump a def-use or use-def chain for REF to FILE.  */
3447 static void
3448 df_chain_dump (struct df_link *link, FILE *file)
3449 {
3450   fprintf (file, "{ ");
3451   for (; link; link = link->next)
3452     {
3453       fprintf (file, "%c%d ",
3454                DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
3455                DF_REF_ID (link->ref));
3456     }
3457   fprintf (file, "}");
3458 }
3459
3460
3461 /* Dump a chain of refs with the associated regno.  */
3462 static void
3463 df_chain_dump_regno (struct df_link *link, FILE *file)
3464 {
3465   fprintf (file, "{ ");
3466   for (; link; link = link->next)
3467     {
3468       fprintf (file, "%c%d(%d) ",
3469                DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
3470                DF_REF_ID (link->ref),
3471                DF_REF_REGNO (link->ref));
3472     }
3473   fprintf (file, "}");
3474 }
3475
3476
3477 /* Dump dataflow info.  */
3478 void
3479 df_dump (struct df *df, int flags, FILE *file)
3480 {
3481   unsigned int j;
3482   basic_block bb;
3483
3484   if (! df || ! file)
3485     return;
3486
3487   fprintf (file, "\nDataflow summary:\n");
3488   fprintf (file, "n_regs = %d, n_defs = %d, n_uses = %d, n_bbs = %d\n",
3489            df->n_regs, df->n_defs, df->n_uses, df->n_bbs);
3490
3491   if (flags & DF_RD)
3492     {
3493       basic_block bb;
3494
3495       fprintf (file, "Reaching defs:\n");
3496       FOR_EACH_BB (bb)
3497         {
3498           struct bb_info *bb_info = DF_BB_INFO (df, bb);
3499
3500           if (! bb_info->rd_in)
3501             continue;
3502
3503           fprintf (file, "bb %d in  \t", bb->index);
3504           dump_bitmap (file, bb_info->rd_in);
3505           fprintf (file, "bb %d gen \t", bb->index);
3506           dump_bitmap (file, bb_info->rd_gen);
3507           fprintf (file, "bb %d kill\t", bb->index);
3508           dump_bitmap (file, bb_info->rd_kill);
3509           fprintf (file, "bb %d out \t", bb->index);
3510           dump_bitmap (file, bb_info->rd_out);
3511         }
3512     }
3513
3514   if (flags & DF_UD_CHAIN)
3515     {
3516       fprintf (file, "Use-def chains:\n");
3517       for (j = 0; j < df->n_defs; j++)
3518         {
3519           if (df->defs[j])
3520             {
3521               fprintf (file, "d%d bb %d luid %d insn %d reg %d ",
3522                        j, DF_REF_BBNO (df->defs[j]),
3523                        DF_INSN_LUID (df, DF_REF_INSN (df->defs[j])),
3524                        DF_REF_INSN_UID (df->defs[j]),
3525                        DF_REF_REGNO (df->defs[j]));
3526               if (df->defs[j]->flags & DF_REF_READ_WRITE)
3527                 fprintf (file, "read/write ");
3528               df_chain_dump (DF_REF_CHAIN (df->defs[j]), file);
3529               fprintf (file, "\n");
3530             }
3531         }
3532     }
3533
3534   if (flags & DF_RU)
3535     {
3536       fprintf (file, "Reaching uses:\n");
3537       FOR_EACH_BB (bb)
3538         {
3539           struct bb_info *bb_info = DF_BB_INFO (df, bb);
3540
3541           if (! bb_info->ru_in)
3542             continue;
3543
3544           fprintf (file, "bb %d in  \t", bb->index);
3545           dump_bitmap (file, bb_info->ru_in);
3546           fprintf (file, "bb %d gen \t", bb->index);
3547           dump_bitmap (file, bb_info->ru_gen);
3548           fprintf (file, "bb %d kill\t", bb->index);
3549           dump_bitmap (file, bb_info->ru_kill);
3550           fprintf (file, "bb %d out \t", bb->index);
3551           dump_bitmap (file, bb_info->ru_out);
3552         }
3553     }
3554
3555   if (flags & DF_DU_CHAIN)
3556     {
3557       fprintf (file, "Def-use chains:\n");
3558       for (j = 0; j < df->n_uses; j++)
3559         {
3560           if (df->uses[j])
3561             {
3562               fprintf (file, "u%d bb %d luid %d insn %d reg %d ",
3563                        j, DF_REF_BBNO (df->uses[j]),
3564                        DF_INSN_LUID (df, DF_REF_INSN (df->uses[j])),
3565                        DF_REF_INSN_UID (df->uses[j]),
3566                        DF_REF_REGNO (df->uses[j]));
3567               if (df->uses[j]->flags & DF_REF_READ_WRITE)
3568                 fprintf (file, "read/write ");
3569               df_chain_dump (DF_REF_CHAIN (df->uses[j]), file);
3570               fprintf (file, "\n");
3571             }
3572         }
3573     }
3574
3575   if (flags & DF_LR)
3576     {
3577       fprintf (file, "Live regs:\n");
3578       FOR_EACH_BB (bb)
3579         {
3580           struct bb_info *bb_info = DF_BB_INFO (df, bb);
3581
3582           if (! bb_info->lr_in)
3583             continue;
3584
3585           fprintf (file, "bb %d in  \t", bb->index);
3586           dump_bitmap (file, bb_info->lr_in);
3587           fprintf (file, "bb %d use \t", bb->index);
3588           dump_bitmap (file, bb_info->lr_use);
3589           fprintf (file, "bb %d def \t", bb->index);
3590           dump_bitmap (file, bb_info->lr_def);
3591           fprintf (file, "bb %d out \t", bb->index);
3592           dump_bitmap (file, bb_info->lr_out);
3593         }
3594     }
3595
3596   if (flags & (DF_REG_INFO | DF_RD_CHAIN | DF_RU_CHAIN))
3597     {
3598       struct reg_info *reg_info = df->regs;
3599
3600       fprintf (file, "Register info:\n");
3601       for (j = 0; j < df->n_regs; j++)
3602         {
3603           if (((flags & DF_REG_INFO)
3604                && (reg_info[j].n_uses || reg_info[j].n_defs))
3605               || ((flags & DF_RD_CHAIN) && reg_info[j].defs)
3606               || ((flags & DF_RU_CHAIN) && reg_info[j].uses))
3607             {
3608               fprintf (file, "reg %d", j);
3609               if ((flags & DF_RD_CHAIN) && (flags & DF_RU_CHAIN))
3610                 {
3611                   basic_block bb = df_regno_bb (df, j);
3612
3613                   if (bb)
3614                     fprintf (file, " bb %d", bb->index);
3615                   else
3616                     fprintf (file, " bb ?");
3617                 }
3618               if (flags & DF_REG_INFO)
3619                 {
3620                   fprintf (file, " life %d", reg_info[j].lifetime);
3621                 }
3622
3623               if ((flags & DF_REG_INFO) || (flags & DF_RD_CHAIN))
3624                 {
3625                   fprintf (file, " defs ");
3626                   if (flags & DF_REG_INFO)
3627                     fprintf (file, "%d ", reg_info[j].n_defs);
3628                   if (flags & DF_RD_CHAIN)
3629                     df_chain_dump (reg_info[j].defs, file);
3630                 }
3631
3632               if ((flags & DF_REG_INFO) || (flags & DF_RU_CHAIN))
3633                 {
3634                   fprintf (file, " uses ");
3635                   if (flags & DF_REG_INFO)
3636                     fprintf (file, "%d ", reg_info[j].n_uses);
3637                   if (flags & DF_RU_CHAIN)
3638                     df_chain_dump (reg_info[j].uses, file);
3639                 }
3640
3641               fprintf (file, "\n");
3642             }
3643         }
3644     }
3645   fprintf (file, "\n");
3646 }
3647
3648
3649 void
3650 df_insn_debug (struct df *df, rtx insn, FILE *file)
3651 {
3652   unsigned int uid;
3653   int bbi;
3654
3655   uid = INSN_UID (insn);
3656   if (uid >= df->insn_size)
3657     return;
3658
3659   if (df->insns[uid].defs)
3660     bbi = DF_REF_BBNO (df->insns[uid].defs->ref);
3661   else if (df->insns[uid].uses)
3662     bbi = DF_REF_BBNO (df->insns[uid].uses->ref);
3663   else
3664     bbi = -1;
3665
3666   fprintf (file, "insn %d bb %d luid %d defs ",
3667            uid, bbi, DF_INSN_LUID (df, insn));
3668   df_chain_dump (df->insns[uid].defs, file);
3669   fprintf (file, " uses ");
3670   df_chain_dump (df->insns[uid].uses, file);
3671   fprintf (file, "\n");
3672 }
3673
3674
3675 void
3676 df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
3677 {
3678   unsigned int uid;
3679   int bbi;
3680
3681   uid = INSN_UID (insn);
3682   if (uid >= df->insn_size)
3683     return;
3684
3685   if (df->insns[uid].defs)
3686     bbi = DF_REF_BBNO (df->insns[uid].defs->ref);
3687   else if (df->insns[uid].uses)
3688     bbi = DF_REF_BBNO (df->insns[uid].uses->ref);
3689   else
3690     bbi = -1;
3691
3692   fprintf (file, "insn %d bb %d luid %d defs ",
3693            uid, bbi, DF_INSN_LUID (df, insn));
3694   df_chain_dump_regno (df->insns[uid].defs, file);
3695   fprintf (file, " uses ");
3696   df_chain_dump_regno (df->insns[uid].uses, file);
3697   fprintf (file, "\n");
3698 }
3699
3700
3701 static void
3702 df_regno_debug (struct df *df, unsigned int regno, FILE *file)
3703 {
3704   if (regno >= df->reg_size)
3705     return;
3706
3707   fprintf (file, "reg %d life %d defs ",
3708            regno, df->regs[regno].lifetime);
3709   df_chain_dump (df->regs[regno].defs, file);
3710   fprintf (file, " uses ");
3711   df_chain_dump (df->regs[regno].uses, file);
3712   fprintf (file, "\n");
3713 }
3714
3715
3716 static void
3717 df_ref_debug (struct df *df, struct ref *ref, FILE *file)
3718 {
3719   fprintf (file, "%c%d ",
3720            DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
3721            DF_REF_ID (ref));
3722   fprintf (file, "reg %d bb %d luid %d insn %d chain ",
3723            DF_REF_REGNO (ref),
3724            DF_REF_BBNO (ref),
3725            DF_INSN_LUID (df, DF_REF_INSN (ref)),
3726            INSN_UID (DF_REF_INSN (ref)));
3727   df_chain_dump (DF_REF_CHAIN (ref), file);
3728   fprintf (file, "\n");
3729 }
3730 \f
3731 /* Functions for debugging from GDB.  */
3732
3733 void
3734 debug_df_insn (rtx insn)
3735 {
3736   df_insn_debug (ddf, insn, stderr);
3737   debug_rtx (insn);
3738 }
3739
3740
3741 void
3742 debug_df_reg (rtx reg)
3743 {
3744   df_regno_debug (ddf, REGNO (reg), stderr);
3745 }
3746
3747
3748 void
3749 debug_df_regno (unsigned int regno)
3750 {
3751   df_regno_debug (ddf, regno, stderr);
3752 }
3753
3754
3755 void
3756 debug_df_ref (struct ref *ref)
3757 {
3758   df_ref_debug (ddf, ref, stderr);
3759 }
3760
3761
3762 void
3763 debug_df_defno (unsigned int defno)
3764 {
3765   df_ref_debug (ddf, ddf->defs[defno], stderr);
3766 }
3767
3768
3769 void
3770 debug_df_useno (unsigned int defno)
3771 {
3772   df_ref_debug (ddf, ddf->uses[defno], stderr);
3773 }
3774
3775
3776 void
3777 debug_df_chain (struct df_link *link)
3778 {
3779   df_chain_dump (link, stderr);
3780   fputc ('\n', stderr);
3781 }
3782 \f
3783
3784 /* Perform the set operation OP1 OP OP2, using set representation REPR, and
3785    storing the result in OP1.  */
3786
3787 static void
3788 dataflow_set_a_op_b (enum set_representation repr,
3789                      enum df_confluence_op op,
3790                      void *op1, void *op2)
3791 {
3792   switch (repr)
3793     {
3794     case SR_SBITMAP:
3795       switch (op)
3796         {
3797         case DF_UNION:
3798           sbitmap_a_or_b (op1, op1, op2);
3799           break;
3800
3801         case DF_INTERSECTION:
3802           sbitmap_a_and_b (op1, op1, op2);
3803           break;
3804
3805         default:
3806           gcc_unreachable ();
3807         }
3808       break;
3809
3810     case SR_BITMAP:
3811       switch (op)
3812         {
3813         case DF_UNION:
3814           bitmap_ior_into (op1, op2);
3815           break;
3816
3817         case DF_INTERSECTION:
3818           bitmap_and_into (op1, op2);
3819           break;
3820
3821         default:
3822           gcc_unreachable ();
3823         }
3824       break;
3825
3826     default:
3827       gcc_unreachable ();
3828     }
3829 }
3830
3831 static void
3832 dataflow_set_copy (enum set_representation repr, void *dest, void *src)
3833 {
3834   switch (repr)
3835     {
3836     case SR_SBITMAP:
3837       sbitmap_copy (dest, src);
3838       break;
3839
3840     case SR_BITMAP:
3841       bitmap_copy (dest, src);
3842       break;
3843
3844     default:
3845       gcc_unreachable ();
3846     }
3847 }
3848
3849 /* Hybrid search algorithm from "Implementation Techniques for
3850    Efficient Data-Flow Analysis of Large Programs".  */
3851
3852 static void
3853 hybrid_search (basic_block bb, struct dataflow *dataflow,
3854                sbitmap visited, sbitmap pending, sbitmap considered)
3855 {
3856   int changed;
3857   int i = bb->index;
3858   edge e;
3859   edge_iterator ei;
3860
3861   SET_BIT (visited, bb->index);
3862   gcc_assert (TEST_BIT (pending, bb->index));
3863   RESET_BIT (pending, i);
3864
3865 #define HS(E_ANTI, E_ANTI_BB, E_ANTI_START_BB, IN_SET,                  \
3866            E, E_BB, E_START_BB, OUT_SET)                                \
3867   do                                                                    \
3868     {                                                                   \
3869       /*  Calculate <conf_op> of predecessor_outs.  */                  \
3870       bitmap_zero (IN_SET[i]);                                          \
3871       FOR_EACH_EDGE (e, ei, bb->E_ANTI)                                 \
3872         {                                                               \
3873           if (e->E_ANTI_BB == E_ANTI_START_BB)                          \
3874             continue;                                                   \
3875           if (!TEST_BIT (considered, e->E_ANTI_BB->index))              \
3876             continue;                                                   \
3877                                                                         \
3878           dataflow_set_a_op_b (dataflow->repr, dataflow->conf_op,       \
3879                                IN_SET[i],                               \
3880                                OUT_SET[e->E_ANTI_BB->index]);           \
3881         }                                                               \
3882                                                                         \
3883       (*dataflow->transfun)(i, &changed,                                \
3884                             dataflow->in[i], dataflow->out[i],          \
3885                             dataflow->gen[i], dataflow->kill[i],        \
3886                             dataflow->data);                            \
3887                                                                         \
3888       if (!changed)                                                     \
3889         break;                                                          \
3890                                                                         \
3891       FOR_EACH_EDGE (e, ei, bb->E)                                              \
3892         {                                                               \
3893           if (e->E_BB == E_START_BB || e->E_BB->index == i)             \
3894             continue;                                                   \
3895                                                                         \
3896           if (!TEST_BIT (considered, e->E_BB->index))                   \
3897             continue;                                                   \
3898                                                                         \
3899           SET_BIT (pending, e->E_BB->index);                            \
3900         }                                                               \
3901                                                                         \
3902       FOR_EACH_EDGE (e, ei, bb->E)                                              \
3903         {                                                               \
3904           if (e->E_BB == E_START_BB || e->E_BB->index == i)             \
3905             continue;                                                   \
3906                                                                         \
3907           if (!TEST_BIT (considered, e->E_BB->index))                   \
3908             continue;                                                   \
3909                                                                         \
3910           if (!TEST_BIT (visited, e->E_BB->index))                      \
3911             hybrid_search (e->E_BB, dataflow, visited, pending, considered); \
3912         }                                                               \
3913     } while (0)
3914
3915   if (dataflow->dir == DF_FORWARD)
3916     HS (preds, src, ENTRY_BLOCK_PTR, dataflow->in,
3917         succs, dest, EXIT_BLOCK_PTR, dataflow->out);
3918   else
3919     HS (succs, dest, EXIT_BLOCK_PTR, dataflow->out,
3920         preds, src, ENTRY_BLOCK_PTR, dataflow->in);
3921 }
3922
3923 /* This function will perform iterative bitvector dataflow described by
3924    DATAFLOW, producing the in and out sets.  Only the part of the cfg
3925    induced by blocks in DATAFLOW->order is taken into account.
3926
3927    For forward problems, you probably want to pass in rc_order.  */
3928
3929 void
3930 iterative_dataflow (struct dataflow *dataflow)
3931 {
3932   unsigned i, idx;
3933   sbitmap visited, pending, considered;
3934
3935   pending = sbitmap_alloc (last_basic_block);
3936   visited = sbitmap_alloc (last_basic_block);
3937   considered = sbitmap_alloc (last_basic_block);
3938   sbitmap_zero (pending);
3939   sbitmap_zero (visited);
3940   sbitmap_zero (considered);
3941
3942   for (i = 0; i < dataflow->n_blocks; i++)
3943     {
3944       idx = dataflow->order[i];
3945       SET_BIT (pending, idx);
3946       SET_BIT (considered, idx);
3947       if (dataflow->dir == DF_FORWARD)
3948         dataflow_set_copy (dataflow->repr,
3949                            dataflow->out[idx], dataflow->gen[idx]);
3950       else
3951         dataflow_set_copy (dataflow->repr,
3952                            dataflow->in[idx], dataflow->gen[idx]);
3953     };
3954
3955   while (1)
3956     {
3957       for (i = 0; i < dataflow->n_blocks; i++)
3958         {
3959           idx = dataflow->order[i];
3960
3961           if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
3962             hybrid_search (BASIC_BLOCK (idx), dataflow,
3963                            visited, pending, considered);
3964         }
3965
3966       if (sbitmap_first_set_bit (pending) == -1)
3967         break;
3968
3969       sbitmap_zero (visited);
3970     }
3971
3972   sbitmap_free (pending);
3973   sbitmap_free (visited);
3974   sbitmap_free (considered);
3975 }