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