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