gcc/df-core.c

   1 /* Allocation for dataflow support routines.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
   3    Free Software Foundation, Inc.
   4    Originally contributed by Michael P. Hayes
   5              (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
   6    Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
   7              and Kenneth Zadeck (zadeck@naturalbridge.com).
   8
   9 This file is part of GCC.
  10
  11 GCC is free software; you can redistribute it and/or modify it under
  12 the terms of the GNU General Public License as published by the Free
  13 Software Foundation; either version 2, or (at your option) any later
  14 version.
  15
  16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19 for more details.
  20
  21 You should have received a copy of the GNU General Public License
  22 along with GCC; see the file COPYING.  If not, write to the Free
  23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  24 02110-1301, USA.
  25 */
  26
  27 /*
  28 OVERVIEW:
  29
  30 The files in this collection (df*.c,df.h) provide a general framework
  31 for solving dataflow problems.  The global dataflow is performed using
  32 a good implementation of iterative dataflow analysis.
  33
  34 The file df-problems.c provides problem instance for the most common
  35 dataflow problems: reaching defs, upward exposed uses, live variables,
  36 uninitialized variables, def-use chains, and use-def chains.  However,
  37 the interface allows other dataflow problems to be defined as well.
  38
  39
  40 USAGE:
  41
  42 Here is an example of using the dataflow routines.
  43
  44       struct df *df;
  45
  46       df = df_init (init_flags);
  47
  48       df_add_problem (df, problem);
  49
  50       df_set_blocks (df, blocks);
  51
  52       df_rescan_blocks (df, blocks);
  53
  54       df_analyze (df);
  55
  56       df_dump (df, stderr);
  57
  58       df_finish (df);
  59
  60
  61
  62 DF_INIT simply creates a poor man's object (df) that needs to be
  63 passed to all the dataflow routines.  df_finish destroys this object
  64 and frees up any allocated memory.
  65
  66 There are two flags that can be passed to df_init:
  67
  68 DF_NO_SCAN means that no scanning of the rtl code is performed.  This
  69 is used if the problem instance is to do it's own scanning.
  70
  71 DF_HARD_REGS means that the scanning is to build information about
  72 both pseudo registers and hardware registers.  Without this
  73 information, the problems will be solved only on pseudo registers.
  74
  75
  76
  77 DF_ADD_PROBLEM adds a problem, defined by an instance to struct
  78 df_problem, to the set of problems solved in this instance of df.  All
  79 calls to add a problem for a given instance of df must occur before
  80 the first call to DF_RESCAN_BLOCKS or DF_ANALYZE.
  81
  82 For all of the problems defined in df-problems.c, there are
  83 convienence functions named DF_*_ADD_PROBLEM.
  84
  85
  86 Problems can be dependent on other problems.  For instance, solving
  87 def-use or use-def chains is dependant on solving reaching
  88 definitions. As long as these dependancies are listed in the problem
  89 definition, the order of adding the problems is not material.
  90 Otherwise, the problems will be solved in the order of calls to
  91 df_add_problem.  Note that it is not necessary to have a problem.  In
  92 that case, df will just be used to do the scanning.
  93
  94
  95
  96 DF_SET_BLOCKS is an optional call used to define a region of the
  97 function on which the analysis will be performed.  The normal case is
  98 to analyze the entire function and no call to df_set_blocks is made.
  99
 100 When a subset is given, the analysis behaves as if the function only
 101 contains those blocks and any edges that occur directly between the
 102 blocks in the set.  Care should be taken to call df_set_blocks right
 103 before the call to analyze in order to eliminate the possiblity that
 104 optimizations that reorder blocks invalidate the bitvector.
 105
 106
 107
 108 DF_RESCAN_BLOCKS is an optional call that causes the scanner to be
 109  (re)run over the set of blocks passed in.  If blocks is NULL, the entire
 110 function (or all of the blocks defined in df_set_blocks) is rescanned.
 111 If blocks contains blocks that were not defined in the call to
 112 df_set_blocks, these blocks are added to the set of blocks.
 113
 114
 115 DF_ANALYZE causes all of the defined problems to be (re)solved.  It
 116 does not cause blocks to be (re)scanned at the rtl level unless no
 117 prior call is made to df_rescan_blocks.
 118
 119
 120 DF_DUMP can then be called to dump the information produce to some
 121 file.
 122
 123
 124
 125 DF_FINISH causes all of the datastructures to be cleaned up and freed.
 126 The df_instance is also freed and its pointer should be NULLed.
 127
 128
 129
 130
 131 Scanning produces a `struct df_ref' data structure (ref) is allocated
 132 for every register reference (def or use) and this records the insn
 133 and bb the ref is found within.  The refs are linked together in
 134 chains of uses and defs for each insn and for each register.  Each ref
 135 also has a chain field that links all the use refs for a def or all
 136 the def refs for a use.  This is used to create use-def or def-use
 137 chains.
 138
 139 Different optimizations have different needs.  Ultimately, only
 140 register allocation and schedulers should be using the bitmaps
 141 produced for the live register and uninitialized register problems.
 142 The rest of the backend should be upgraded to using and maintaining
 143 the linked information such as def use or use def chains.
 144
 145
 146
 147 PHILOSOPHY:
 148
 149 While incremental bitmaps are not worthwhile to maintain, incremental
 150 chains may be perfectly reasonable.  The fastest way to build chains
 151 from scratch or after significant modifications is to build reaching
 152 definitions (RD) and build the chains from this.
 153
 154 However, general algorithms for maintaining use-def or def-use chains
 155 are not practical.  The amount of work to recompute the chain any
 156 chain after an arbitrary change is large.  However, with a modest
 157 amount of work it is generally possible to have the application that
 158 uses the chains keep them up to date.  The high level knowledge of
 159 what is really happening is essential to crafting efficient
 160 incremental algorithms.
 161
 162 As for the bit vector problems, there is no interface to give a set of
 163 blocks over with to resolve the iteration.  In general, restarting a
 164 dataflow iteration is difficult and expensive.  Again, the best way to
 165 keep the dataflow infomation up to data (if this is really what is
 166 needed) it to formulate a problem specific solution.
 167
 168 There are fine grained calls for creating and deleting references from
 169 instructions in df-scan.c.  However, these are not currently connected
 170 to the engine that resolves the dataflow equations.
 171
 172
 173 DATA STRUCTURES:
 174
 175 The basic object is a DF_REF (reference) and this may either be a
 176 DEF (definition) or a USE of a register.
 177
 178 These are linked into a variety of lists; namely reg-def, reg-use,
 179 insn-def, insn-use, def-use, and use-def lists.  For example, the
 180 reg-def lists contain all the locations that define a given register
 181 while the insn-use lists contain all the locations that use a
 182 register.
 183
 184 Note that the reg-def and reg-use chains are generally short for
 185 pseudos and long for the hard registers.
 186
 187 ACCESSING REFS:
 188
 189 There are 4 ways to obtain access to refs:
 190
 191 1) References are divided into two categories, REAL and ARTIFICIAL.
 192
 193    REAL refs are associated with instructions.  They are linked into
 194    either in the insn's defs list (accessed by the DF_INSN_DEFS or
 195    DF_INSN_UID_DEFS macros) or the insn's uses list (accessed by the
 196    DF_INSN_USES or DF_INSN_UID_USES macros).  These macros produce a
 197    ref (or NULL), the rest of the list can be obtained by traversal of
 198    the NEXT_REF field (accessed by the DF_REF_NEXT_REF macro.)  There
 199    is no significance to the ordering of the uses or refs in an
 200    instruction.
 201
 202    ARTIFICIAL refs are associated with basic blocks.  The heads of
 203    these lists can be accessed by calling get_artificial_defs or
 204    get_artificial_uses for the particular basic block.  Artificial
 205    defs and uses are only there if DF_HARD_REGS was specified when the
 206    df instance was created.
 207
 208    Artificial defs and uses occur both at the beginning and ends of blocks.
 209
 210      For blocks that area at the destination of eh edges, the
 211      artificial uses and defs occur at the beginning.  The defs relate
 212      to the registers specified in EH_RETURN_DATA_REGNO and the uses
 213      relate to the registers specified in ED_USES.  Logically these
 214      defs and uses should really occur along the eh edge, but there is
 215      no convenient way to do this.  Artificial edges that occur at the
 216      beginning of the block have the DF_REF_AT_TOP flag set.
 217
 218      Artificial uses occur at the end of all blocks.  These arise from
 219      the hard registers that are always live, such as the stack
 220      register and are put there to keep the code from forgetting about
 221      them.
 222
 223      Artifical defs occur at the end of the entry block.  These arise
 224      from registers that are live at entry to the function.
 225
 226 2) All of the uses and defs associated with each pseudo or hard
 227    register are linked in a bidirectional chain.  These are called
 228    reg-use or reg_def chains.
 229
 230    The first use (or def) for a register can be obtained using the
 231    DF_REG_USE_GET macro (or DF_REG_DEF_GET macro).  Subsequent uses
 232    for the same regno can be obtained by following the next_reg field
 233    of the ref.
 234
 235    In previous versions of this code, these chains were ordered.  It
 236    has not been practical to continue this practice.
 237
 238 3) If def-use or use-def chains are built, these can be traversed to
 239    get to other refs.
 240
 241 4) An array of all of the uses (and an array of all of the defs) can
 242    be built.  These arrays are indexed by the value in the id
 243    structure.  These arrays are only lazily kept up to date, and that
 244    process can be expensive.  To have these arrays built, call
 245    df_reorganize_refs.   Note that the values in the id field of a ref
 246    may change across calls to df_analyze or df_reorganize refs.
 247
 248    If the only use of this array is to find all of the refs, it is
 249    better to traverse all of the registers and then traverse all of
 250    reg-use or reg-def chains.
 251
 252
 253
 254 NOTES:
 255
 256 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
 257 both a use and a def.  These are both marked read/write to show that they
 258 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
 259 will generate a use of reg 42 followed by a def of reg 42 (both marked
 260 read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
 261 generates a use of reg 41 then a def of reg 41 (both marked read/write),
 262 even though reg 41 is decremented before it is used for the memory
 263 address in this second example.
 264
 265 A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
 266 for which the number of word_mode units covered by the outer mode is
 267 smaller than that covered by the inner mode, invokes a read-modify-write.
 268 operation.  We generate both a use and a def and again mark them
 269 read/write.
 270
 271 Paradoxical subreg writes do not leave a trace of the old content, so they
 272 are write-only operations.
 273 */
 274
 275
 276 #include "config.h"
 277 #include "system.h"
 278 #include "coretypes.h"
 279 #include "tm.h"
 280 #include "rtl.h"
 281 #include "tm_p.h"
 282 #include "insn-config.h"
 283 #include "recog.h"
 284 #include "function.h"
 285 #include "regs.h"
 286 #include "output.h"
 287 #include "alloc-pool.h"
 288 #include "flags.h"
 289 #include "hard-reg-set.h"
 290 #include "basic-block.h"
 291 #include "sbitmap.h"
 292 #include "bitmap.h"
 293 #include "timevar.h"
 294 #include "df.h"
 295 #include "tree-pass.h"
 296
 297 static struct df *ddf = NULL;
 298 struct df *shared_df = NULL;
 299
 300 static void * df_get_bb_info (struct dataflow *, unsigned int);
 301 static void df_set_bb_info (struct dataflow *, unsigned int, void *);
 302 /*----------------------------------------------------------------------------
 303   Functions to create, destroy and manipulate an instance of df.
 304 ----------------------------------------------------------------------------*/
 305
 306
 307 /* Initialize dataflow analysis and allocate and initialize dataflow
 308    memory.  */
 309
 310 struct df *
 311 df_init (int flags)
 312 {
 313   struct df *df = XCNEW (struct df);
 314   df->flags = flags;
 315
 316   /* This is executed once per compilation to initialize platform
 317      specific data structures. */
 318   df_hard_reg_init ();
 319
 320   /* All df instance must define the scanning problem.  */
 321   df_scan_add_problem (df);
 322   ddf = df;
 323   return df;
 324 }
 325
 326 /* Add PROBLEM to the DF instance.  */
 327
 328 struct dataflow *
 329 df_add_problem (struct df *df, struct df_problem *problem)
 330 {
 331   struct dataflow *dflow;
 332
 333   /* First try to add the dependent problem. */
 334   if (problem->dependent_problem)
 335     df_add_problem (df, problem->dependent_problem);
 336
 337   /* Check to see if this problem has already been defined.  If it
 338      has, just return that instance, if not, add it to the end of the
 339      vector.  */
 340   dflow = df->problems_by_index[problem->id];
 341   if (dflow)
 342     return dflow;
 343
 344   /* Make a new one and add it to the end.  */
 345   dflow = XCNEW (struct dataflow);
 346   dflow->df = df;
 347   dflow->problem = problem;
 348   df->problems_in_order[df->num_problems_defined++] = dflow;
 349   df->problems_by_index[dflow->problem->id] = dflow;
 350
 351   return dflow;
 352 }
 353
 354
 355 /* Set the blocks that are to be considered for analysis.  If this is
 356    not called or is called with null, the entire function in
 357    analyzed.  */
 358
 359 void
 360 df_set_blocks (struct df *df, bitmap blocks)
 361 {
 362   if (blocks)
 363     {
 364       if (df->blocks_to_analyze)
 365         {
 366           int p;
 367           bitmap diff = BITMAP_ALLOC (NULL);
 368           bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
 369           for (p = df->num_problems_defined - 1; p >= 0 ;p--)
 370             {
 371               struct dataflow *dflow = df->problems_in_order[p];
 372               if (dflow->problem->reset_fun)
 373                 dflow->problem->reset_fun (dflow, df->blocks_to_analyze);
 374               else if (dflow->problem->free_bb_fun)
 375                 {
 376                   bitmap_iterator bi;
 377                   unsigned int bb_index;
 378
 379                   EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
 380                     {
 381                       basic_block bb = BASIC_BLOCK (bb_index);
 382                       if (bb)
 383                         {
 384                           dflow->problem->free_bb_fun
 385                             (dflow, bb, df_get_bb_info (dflow, bb_index));
 386                           df_set_bb_info (dflow, bb_index, NULL);
 387                         }
 388                     }
 389                 }
 390             }
 391
 392           BITMAP_FREE (diff);
 393         }
 394       else
 395         {
 396           /* If we have not actually run scanning before, do not try
 397              to clear anything.  */
 398           struct dataflow *scan_dflow = df->problems_by_index [DF_SCAN];
 399           if (scan_dflow->problem_data)
 400             {
 401               bitmap blocks_to_reset = NULL;
 402               int p;
 403               for (p = df->num_problems_defined - 1; p >= 0 ;p--)
 404                 {
 405                   struct dataflow *dflow = df->problems_in_order[p];
 406                   if (dflow->problem->reset_fun)
 407                     {
 408                       if (!blocks_to_reset)
 409                         {
 410                           basic_block bb;
 411                           blocks_to_reset = BITMAP_ALLOC (NULL);
 412                           FOR_ALL_BB(bb)
 413                             {
 414                               bitmap_set_bit (blocks_to_reset, bb->index);
 415                             }
 416                         }
 417                       dflow->problem->reset_fun (dflow, blocks_to_reset);
 418                     }
 419                 }
 420               if (blocks_to_reset)
 421                 BITMAP_FREE (blocks_to_reset);
 422             }
 423           df->blocks_to_analyze = BITMAP_ALLOC (NULL);
 424         }
 425       bitmap_copy (df->blocks_to_analyze, blocks);
 426     }
 427   else
 428     {
 429       if (df->blocks_to_analyze)
 430         {
 431           BITMAP_FREE (df->blocks_to_analyze);
 432           df->blocks_to_analyze = NULL;
 433         }
 434     }
 435 }
 436
 437
 438 /* Free all the dataflow info and the DF structure.  This should be
 439    called from the df_finish macro which also NULLs the parm.  */
 440
 441 void
 442 df_finish1 (struct df *df)
 443 {
 444   int i;
 445
 446   for (i = 0; i < df->num_problems_defined; i++)
 447     df->problems_in_order[i]->problem->free_fun (df->problems_in_order[i]);
 448
 449   free (df);
 450 }
 451
 452 \f
 453 /*----------------------------------------------------------------------------
 454    The general data flow analysis engine.
 455 ----------------------------------------------------------------------------*/
 456
 457
 458 /* Hybrid search algorithm from "Implementation Techniques for
 459    Efficient Data-Flow Analysis of Large Programs".  */
 460
 461 static void
 462 df_hybrid_search_forward (basic_block bb,
 463                           struct dataflow *dataflow,
 464                           bool single_pass)
 465 {
 466   int result_changed;
 467   int i = bb->index;
 468   edge e;
 469   edge_iterator ei;
 470
 471   SET_BIT (dataflow->visited, bb->index);
 472   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
 473   RESET_BIT (dataflow->pending, i);
 474
 475   /*  Calculate <conf_op> of predecessor_outs.  */
 476   if (EDGE_COUNT (bb->preds) > 0)
 477     FOR_EACH_EDGE (e, ei, bb->preds)
 478       {
 479         if (!TEST_BIT (dataflow->considered, e->src->index))
 480           continue;
 481
 482         dataflow->problem->con_fun_n (dataflow, e);
 483       }
 484   else if (dataflow->problem->con_fun_0)
 485     dataflow->problem->con_fun_0 (dataflow, bb);
 486
 487   result_changed = dataflow->problem->trans_fun (dataflow, i);
 488
 489   if (!result_changed || single_pass)
 490     return;
 491
 492   FOR_EACH_EDGE (e, ei, bb->succs)
 493     {
 494       if (e->dest->index == i)
 495         continue;
 496       if (!TEST_BIT (dataflow->considered, e->dest->index))
 497         continue;
 498       SET_BIT (dataflow->pending, e->dest->index);
 499     }
 500
 501   FOR_EACH_EDGE (e, ei, bb->succs)
 502     {
 503       if (e->dest->index == i)
 504         continue;
 505
 506       if (!TEST_BIT (dataflow->considered, e->dest->index))
 507         continue;
 508       if (!TEST_BIT (dataflow->visited, e->dest->index))
 509         df_hybrid_search_forward (e->dest, dataflow, single_pass);
 510     }
 511 }
 512
 513 static void
 514 df_hybrid_search_backward (basic_block bb,
 515                            struct dataflow *dataflow,
 516                            bool single_pass)
 517 {
 518   int result_changed;
 519   int i = bb->index;
 520   edge e;
 521   edge_iterator ei;
 522
 523   SET_BIT (dataflow->visited, bb->index);
 524   gcc_assert (TEST_BIT (dataflow->pending, bb->index));
 525   RESET_BIT (dataflow->pending, i);
 526
 527   /*  Calculate <conf_op> of predecessor_outs.  */
 528   if (EDGE_COUNT (bb->succs) > 0)
 529     FOR_EACH_EDGE (e, ei, bb->succs)
 530       {
 531         if (!TEST_BIT (dataflow->considered, e->dest->index))
 532           continue;
 533
 534         dataflow->problem->con_fun_n (dataflow, e);
 535       }
 536   else if (dataflow->problem->con_fun_0)
 537     dataflow->problem->con_fun_0 (dataflow, bb);
 538
 539   result_changed = dataflow->problem->trans_fun (dataflow, i);
 540
 541   if (!result_changed || single_pass)
 542     return;
 543
 544   FOR_EACH_EDGE (e, ei, bb->preds)
 545     {
 546       if (e->src->index == i)
 547         continue;
 548
 549       if (!TEST_BIT (dataflow->considered, e->src->index))
 550         continue;
 551
 552       SET_BIT (dataflow->pending, e->src->index);
 553     }
 554
 555   FOR_EACH_EDGE (e, ei, bb->preds)
 556     {
 557       if (e->src->index == i)
 558         continue;
 559
 560       if (!TEST_BIT (dataflow->considered, e->src->index))
 561         continue;
 562
 563       if (!TEST_BIT (dataflow->visited, e->src->index))
 564         df_hybrid_search_backward (e->src, dataflow, single_pass);
 565     }
 566 }
 567
 568
 569 /* This function will perform iterative bitvector dataflow described
 570    by DATAFLOW, producing the in and out sets.  Only the part of the
 571    cfg induced by blocks in DATAFLOW->order is taken into account.
 572
 573    SINGLE_PASS is true if you just want to make one pass over the
 574    blocks.  */
 575
 576 void
 577 df_iterative_dataflow (struct dataflow *dataflow,
 578                        bitmap blocks_to_consider, bitmap blocks_to_init,
 579                        int *blocks_in_postorder, int n_blocks,
 580                        bool single_pass)
 581 {
 582   unsigned int idx;
 583   int i;
 584   sbitmap visited = sbitmap_alloc (last_basic_block);
 585   sbitmap pending = sbitmap_alloc (last_basic_block);
 586   sbitmap considered = sbitmap_alloc (last_basic_block);
 587   bitmap_iterator bi;
 588
 589   dataflow->visited = visited;
 590   dataflow->pending = pending;
 591   dataflow->considered = considered;
 592
 593   sbitmap_zero (visited);
 594   sbitmap_zero (pending);
 595   sbitmap_zero (considered);
 596
 597   EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi)
 598     {
 599       SET_BIT (considered, idx);
 600     }
 601
 602   for (i = 0; i < n_blocks; i++)
 603     {
 604       idx = blocks_in_postorder[i];
 605       SET_BIT (pending, idx);
 606     };
 607
 608   dataflow->problem->init_fun (dataflow, blocks_to_init);
 609
 610   while (1)
 611     {
 612
 613       /* For forward problems, you want to pass in reverse postorder
 614          and for backward problems you want postorder.  This has been
 615          shown to be as good as you can do by several people, the
 616          first being Mathew Hecht in his phd dissertation.
 617
 618          The nodes are passed into this function in postorder.  */
 619
 620       if (dataflow->problem->dir == DF_FORWARD)
 621         {
 622           for (i = n_blocks - 1 ; i >= 0 ; i--)
 623             {
 624               idx = blocks_in_postorder[i];
 625
 626               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
 627                 df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass);
 628             }
 629         }
 630       else
 631         {
 632           for (i = 0; i < n_blocks; i++)
 633             {
 634               idx = blocks_in_postorder[i];
 635
 636               if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
 637                 df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass);
 638             }
 639         }
 640
 641       if (sbitmap_first_set_bit (pending) == -1)
 642         break;
 643
 644       sbitmap_zero (visited);
 645     }
 646
 647   sbitmap_free (pending);
 648   sbitmap_free (visited);
 649   sbitmap_free (considered);
 650 }
 651
 652
 653 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
 654    the order of the remaining entries.  Returns the length of the resulting
 655    list.  */
 656
 657 static unsigned
 658 df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
 659 {
 660   unsigned act, last;
 661
 662   for (act = 0, last = 0; act < len; act++)
 663     if (bitmap_bit_p (blocks, list[act]))
 664       list[last++] = list[act];
 665
 666   return last;
 667 }
 668
 669
 670 /* Execute dataflow analysis on a single dataflow problem.
 671
 672    There are three sets of blocks passed in:
 673
 674    BLOCKS_TO_CONSIDER are the blocks whose solution can either be
 675    examined or will be computed.  For calls from DF_ANALYZE, this is
 676    the set of blocks that has been passed to DF_SET_BLOCKS.  For calls
 677    from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of
 678    blocks in the fringe (the set of blocks passed in plus the set of
 679    immed preds and succs of those blocks).
 680
 681    BLOCKS_TO_INIT are the blocks whose solution will be changed by
 682    this iteration.  For calls from DF_ANALYZE, this is the set of
 683    blocks that has been passed to DF_SET_BLOCKS.  For calls from
 684    DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks
 685    passed in.
 686
 687    BLOCKS_TO_SCAN are the set of blocks that need to be rescanned.
 688    For calls from DF_ANALYZE, this is the accumulated set of blocks
 689    that has been passed to DF_RESCAN_BLOCKS since the last call to
 690    DF_ANALYZE.  For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS,
 691    this is the set of blocks passed in.
 692
 693                    blocks_to_consider    blocks_to_init    blocks_to_scan
 694    full redo       all                   all               all
 695    partial redo    all                   all               sub
 696    small fixup     fringe                sub               sub
 697 */
 698
 699 static void
 700 df_analyze_problem (struct dataflow *dflow,
 701                     bitmap blocks_to_consider,
 702                     bitmap blocks_to_init,
 703                     bitmap blocks_to_scan,
 704                     int *postorder, int n_blocks, bool single_pass)
 705 {
 706   /* (Re)Allocate the datastructures necessary to solve the problem.  */
 707   if (dflow->problem->alloc_fun)
 708     dflow->problem->alloc_fun (dflow, blocks_to_scan);
 709
 710   /* Set up the problem and compute the local information.  This
 711      function is passed both the blocks_to_consider and the
 712      blocks_to_scan because the RD and RU problems require the entire
 713      function to be rescanned if they are going to be updated.  */
 714   if (dflow->problem->local_compute_fun)
 715     dflow->problem->local_compute_fun (dflow, blocks_to_consider, blocks_to_scan);
 716
 717   /* Solve the equations.  */
 718   if (dflow->problem->dataflow_fun)
 719     dflow->problem->dataflow_fun (dflow, blocks_to_consider, blocks_to_init,
 720                                   postorder, n_blocks, single_pass);
 721
 722   /* Massage the solution.  */
 723   if (dflow->problem->finalize_fun)
 724     dflow->problem->finalize_fun (dflow, blocks_to_consider);
 725 }
 726
 727
 728 /* Analyze dataflow info for the basic blocks specified by the bitmap
 729    BLOCKS, or for the whole CFG if BLOCKS is zero.  */
 730
 731 void
 732 df_analyze (struct df *df)
 733 {
 734   int *postorder = XNEWVEC (int, last_basic_block);
 735   bitmap current_all_blocks = BITMAP_ALLOC (NULL);
 736   int n_blocks;
 737   int i;
 738   bool everything;
 739
 740   n_blocks = post_order_compute (postorder, true);
 741
 742   if (n_blocks != n_basic_blocks)
 743     delete_unreachable_blocks ();
 744
 745   for (i = 0; i < n_blocks; i++)
 746     bitmap_set_bit (current_all_blocks, postorder[i]);
 747
 748   /* No one called df_rescan_blocks, so do it.  */
 749   if (!df->blocks_to_scan)
 750     df_rescan_blocks (df, NULL);
 751
 752   /* Make sure that we have pruned any unreachable blocks from these
 753      sets.  */
 754   bitmap_and_into (df->blocks_to_scan, current_all_blocks);
 755
 756   if (df->blocks_to_analyze)
 757     {
 758       everything = false;
 759       bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
 760       n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze);
 761       BITMAP_FREE (current_all_blocks);
 762     }
 763   else
 764     {
 765       everything = true;
 766       df->blocks_to_analyze = current_all_blocks;
 767       current_all_blocks = NULL;
 768     }
 769
 770   /* Skip over the DF_SCAN problem. */
 771   for (i = 1; i < df->num_problems_defined; i++)
 772     df_analyze_problem (df->problems_in_order[i],
 773                         df->blocks_to_analyze, df->blocks_to_analyze,
 774                         df->blocks_to_scan,
 775                         postorder, n_blocks, false);
 776
 777   if (everything)
 778     {
 779       BITMAP_FREE (df->blocks_to_analyze);
 780       df->blocks_to_analyze = NULL;
 781     }
 782
 783   BITMAP_FREE (df->blocks_to_scan);
 784   df->blocks_to_scan = NULL;
 785 }
 786
 787
 788 \f
 789 /*----------------------------------------------------------------------------
 790    Functions to support limited incremental change.
 791 ----------------------------------------------------------------------------*/
 792
 793
 794 /* Get basic block info.  */
 795
 796 static void *
 797 df_get_bb_info (struct dataflow *dflow, unsigned int index)
 798 {
 799   return (struct df_scan_bb_info *) dflow->block_info[index];
 800 }
 801
 802
 803 /* Set basic block info.  */
 804
 805 static void
 806 df_set_bb_info (struct dataflow *dflow, unsigned int index,
 807                 void *bb_info)
 808 {
 809   dflow->block_info[index] = bb_info;
 810 }
 811
 812
 813 /* Called from the rtl_compact_blocks to reorganize the problems basic
 814    block info.  */
 815
 816 void
 817 df_compact_blocks (struct df *df)
 818 {
 819   int i, p;
 820   basic_block bb;
 821   void **problem_temps;
 822   int size = last_basic_block *sizeof (void *);
 823   problem_temps = xmalloc (size);
 824
 825   for (p = 0; p < df->num_problems_defined; p++)
 826     {
 827       struct dataflow *dflow = df->problems_in_order[p];
 828       if (dflow->problem->free_bb_fun)
 829         {
 830           df_grow_bb_info (dflow);
 831           memcpy (problem_temps, dflow->block_info, size);
 832
 833           /* Copy the bb info from the problem tmps to the proper
 834              place in the block_info vector.  Null out the copied
 835              item.  */
 836           i = NUM_FIXED_BLOCKS;
 837           FOR_EACH_BB (bb)
 838             {
 839               df_set_bb_info (dflow, i, problem_temps[bb->index]);
 840               problem_temps[bb->index] = NULL;
 841               i++;
 842             }
 843           memset (dflow->block_info + i, 0,
 844                   (last_basic_block - i) *sizeof (void *));
 845
 846           /* Free any block infos that were not copied (and NULLed).
 847              These are from orphaned blocks.  */
 848           for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
 849             {
 850               basic_block bb = BASIC_BLOCK (i);
 851               if (problem_temps[i] && bb)
 852                 dflow->problem->free_bb_fun
 853                   (dflow, bb, problem_temps[i]);
 854             }
 855         }
 856     }
 857
 858   free (problem_temps);
 859
 860   i = NUM_FIXED_BLOCKS;
 861   FOR_EACH_BB (bb)
 862     {
 863       SET_BASIC_BLOCK (i, bb);
 864       bb->index = i;
 865       i++;
 866     }
 867
 868   gcc_assert (i == n_basic_blocks);
 869
 870   for (; i < last_basic_block; i++)
 871     SET_BASIC_BLOCK (i, NULL);
 872 }
 873
 874
 875 /* Shove NEW_BLOCK in at OLD_INDEX.  Called from if-cvt to hack a
 876    block.  There is no excuse for people to do this kind of thing.  */
 877
 878 void
 879 df_bb_replace (struct df *df, int old_index, basic_block new_block)
 880 {
 881   int p;
 882
 883   for (p = 0; p < df->num_problems_defined; p++)
 884     {
 885       struct dataflow *dflow = df->problems_in_order[p];
 886       if (dflow->block_info)
 887         {
 888           void *temp;
 889
 890           df_grow_bb_info (dflow);
 891
 892           /* The old switcheroo.  */
 893
 894           temp = df_get_bb_info (dflow, old_index);
 895           df_set_bb_info (dflow, old_index,
 896                           df_get_bb_info (dflow, new_block->index));
 897           df_set_bb_info (dflow, new_block->index, temp);
 898         }
 899     }
 900
 901   SET_BASIC_BLOCK (old_index, new_block);
 902   new_block->index = old_index;
 903 }
 904
 905 /*----------------------------------------------------------------------------
 906    PUBLIC INTERFACES TO QUERY INFORMATION.
 907 ----------------------------------------------------------------------------*/
 908
 909
 910 /* Return last use of REGNO within BB.  */
 911
 912 struct df_ref *
 913 df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
 914 {
 915   rtx insn;
 916   struct df_ref *use;
 917
 918   FOR_BB_INSNS_REVERSE (bb, insn)
 919     {
 920       unsigned int uid = INSN_UID (insn);
 921       for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
 922         if (DF_REF_REGNO (use) == regno)
 923           return use;
 924     }
 925   return NULL;
 926 }
 927
 928
 929 /* Return first def of REGNO within BB.  */
 930
 931 struct df_ref *
 932 df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
 933 {
 934   rtx insn;
 935   struct df_ref *def;
 936
 937   FOR_BB_INSNS (bb, insn)
 938     {
 939       unsigned int uid = INSN_UID (insn);
 940       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 941         if (DF_REF_REGNO (def) == regno)
 942           return def;
 943     }
 944   return NULL;
 945 }
 946
 947
 948 /* Return last def of REGNO within BB.  */
 949
 950 struct df_ref *
 951 df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
 952 {
 953   rtx insn;
 954   struct df_ref *def;
 955
 956   FOR_BB_INSNS_REVERSE (bb, insn)
 957     {
 958       unsigned int uid = INSN_UID (insn);
 959
 960       for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 961         if (DF_REF_REGNO (def) == regno)
 962           return def;
 963     }
 964
 965   return NULL;
 966 }
 967
 968 /* Return true if INSN defines REGNO.  */
 969
 970 bool
 971 df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno)
 972 {
 973   unsigned int uid;
 974   struct df_ref *def;
 975
 976   uid = INSN_UID (insn);
 977   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
 978     if (DF_REF_REGNO (def) == regno)
 979       return true;
 980
 981   return false;
 982 }
 983
 984
 985 /* Finds the reference corresponding to the definition of REG in INSN.
 986    DF is the dataflow object.  */
 987
 988 struct df_ref *
 989 df_find_def (struct df *df, rtx insn, rtx reg)
 990 {
 991   unsigned int uid;
 992   struct df_ref *def;
 993
 994   if (GET_CODE (reg) == SUBREG)
 995     reg = SUBREG_REG (reg);
 996   gcc_assert (REG_P (reg));
 997
 998   uid = INSN_UID (insn);
 999   for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
1000     if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
1001       return def;
1002
1003   return NULL;
1004 }
1005
1006
1007 /* Return true if REG is defined in INSN, zero otherwise.  */
1008
1009 bool
1010 df_reg_defined (struct df *df, rtx insn, rtx reg)
1011 {
1012   return df_find_def (df, insn, reg) != NULL;
1013 }
1014
1015
1016 /* Finds the reference corresponding to the use of REG in INSN.
1017    DF is the dataflow object.  */
1018
1019 struct df_ref *
1020 df_find_use (struct df *df, rtx insn, rtx reg)
1021 {
1022   unsigned int uid;
1023   struct df_ref *use;
1024
1025   if (GET_CODE (reg) == SUBREG)
1026     reg = SUBREG_REG (reg);
1027   gcc_assert (REG_P (reg));
1028
1029   uid = INSN_UID (insn);
1030   for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
1031     if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
1032       return use;
1033
1034   return NULL;
1035 }
1036
1037
1038 /* Return true if REG is referenced in INSN, zero otherwise.  */
1039
1040 bool
1041 df_reg_used (struct df *df, rtx insn, rtx reg)
1042 {
1043   return df_find_use (df, insn, reg) != NULL;
1044 }
1045
1046 \f
1047 /*----------------------------------------------------------------------------
1048    Debugging and printing functions.
1049 ----------------------------------------------------------------------------*/
1050
1051 /* Dump dataflow info.  */
1052 void
1053 df_dump (struct df *df, FILE *file)
1054 {
1055   int i;
1056
1057   if (! df || ! file)
1058     return;
1059
1060   fprintf (file, "\n\n%s\n", current_function_name ());
1061   fprintf (file, "\nDataflow summary:\n");
1062   fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
1063            df->def_info.bitmap_size, df->use_info.bitmap_size);
1064
1065   for (i = 0; i < df->num_problems_defined; i++)
1066     df->problems_in_order[i]->problem->dump_fun (df->problems_in_order[i], file);
1067
1068   fprintf (file, "\n");
1069 }
1070
1071
1072 void
1073 df_refs_chain_dump (struct df *df, struct df_ref *ref,
1074                    bool follow_chain, FILE *file)
1075 {
1076   fprintf (file, "{ ");
1077   while (ref)
1078     {
1079       fprintf (file, "%c%d(%d) ",
1080                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1081                DF_REF_ID (ref),
1082                DF_REF_REGNO (ref));
1083       if (follow_chain)
1084         df_chain_dump (df, DF_REF_CHAIN (ref), file);
1085       ref = ref->next_ref;
1086     }
1087   fprintf (file, "}");
1088 }
1089
1090
1091 /* Dump either a ref-def or reg-use chain.  */
1092
1093 void
1094 df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref,  FILE *file)
1095 {
1096   fprintf (file, "{ ");
1097   while (ref)
1098     {
1099       fprintf (file, "%c%d(%d) ",
1100                DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1101                DF_REF_ID (ref),
1102                DF_REF_REGNO (ref));
1103       ref = ref->next_reg;
1104     }
1105   fprintf (file, "}");
1106 }
1107
1108
1109 void
1110 df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file)
1111 {
1112   unsigned int uid;
1113   int bbi;
1114
1115   uid = INSN_UID (insn);
1116
1117   if (DF_INSN_UID_DEFS (df, uid))
1118     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1119   else if (DF_INSN_UID_USES(df, uid))
1120     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1121   else
1122     bbi = -1;
1123
1124   fprintf (file, "insn %d bb %d luid %d defs ",
1125            uid, bbi, DF_INSN_LUID (df, insn));
1126
1127   df_refs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), follow_chain, file);
1128   fprintf (file, " defs ");
1129   df_refs_chain_dump (df, DF_INSN_UID_USES (df, uid), follow_chain, file);
1130   fprintf (file, "\n");
1131 }
1132
1133 void
1134 df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
1135 {
1136   unsigned int uid;
1137   int bbi;
1138
1139   uid = INSN_UID (insn);
1140   if (DF_INSN_UID_DEFS (df, uid))
1141     bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
1142   else if (DF_INSN_UID_USES(df, uid))
1143     bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
1144   else
1145     bbi = -1;
1146
1147   fprintf (file, "insn %d bb %d luid %d defs ",
1148            uid, bbi, DF_INSN_LUID (df, insn));
1149   df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file);
1150
1151   fprintf (file, " uses ");
1152   df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file);
1153   fprintf (file, "\n");
1154 }
1155
1156 void
1157 df_regno_debug (struct df *df, unsigned int regno, FILE *file)
1158 {
1159   fprintf (file, "reg %d defs ", regno);
1160   df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file);
1161   fprintf (file, " uses ");
1162   df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file);
1163   fprintf (file, "\n");
1164 }
1165
1166
1167 void
1168 df_ref_debug (struct df *df, struct df_ref *ref, FILE *file)
1169 {
1170   fprintf (file, "%c%d ",
1171            DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
1172            DF_REF_ID (ref));
1173   fprintf (file, "reg %d bb %d luid %d insn %d chain ",
1174            DF_REF_REGNO (ref),
1175            DF_REF_BBNO (ref),
1176            DF_REF_INSN (ref) ? DF_INSN_LUID (df, DF_REF_INSN (ref)) : -1,
1177            DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1);
1178   df_chain_dump (df, DF_REF_CHAIN (ref), file);
1179   fprintf (file, "\n");
1180 }
1181 \f
1182 /* Functions for debugging from GDB.  */
1183
1184 void
1185 debug_df_insn (rtx insn)
1186 {
1187   df_insn_debug (ddf, insn, true, stderr);
1188   debug_rtx (insn);
1189 }
1190
1191
1192 void
1193 debug_df_reg (rtx reg)
1194 {
1195   df_regno_debug (ddf, REGNO (reg), stderr);
1196 }
1197
1198
1199 void
1200 debug_df_regno (unsigned int regno)
1201 {
1202   df_regno_debug (ddf, regno, stderr);
1203 }
1204
1205
1206 void
1207 debug_df_ref (struct df_ref *ref)
1208 {
1209   df_ref_debug (ddf, ref, stderr);
1210 }
1211
1212
1213 void
1214 debug_df_defno (unsigned int defno)
1215 {
1216   df_ref_debug (ddf, DF_DEFS_GET (ddf, defno), stderr);
1217 }
1218
1219
1220 void
1221 debug_df_useno (unsigned int defno)
1222 {
1223   df_ref_debug (ddf, DF_USES_GET (ddf, defno), stderr);
1224 }
1225
1226
1227 void
1228 debug_df_chain (struct df_link *link)
1229 {
1230   df_chain_dump (ddf, link, stderr);
1231   fputc ('\n', stderr);
1232 }