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