gcc/df.c

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