gcc/df.c

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