gcc/df.c

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