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