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