gcc/df.c

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