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