gcc/df.c

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