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