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