gcc/df.c

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