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