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