gcc/df.c

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