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