gcc/df.c

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