gcc/df.c

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