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