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