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