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