contrib/gcc-5.0/gcc/df.h

   1 /* Form lists of pseudo register references for autoinc optimization
   2    for GNU compiler.  This is part of flow optimization.
   3    Copyright (C) 1999-2015 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 3, 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 COPYING3.  If not see
  23 <http://www.gnu.org/licenses/>.  */
  24
  25 #ifndef GCC_DF_H
  26 #define GCC_DF_H
  27
  28 #include "bitmap.h"
  29 #include "regset.h"
  30 #include "sbitmap.h"
  31 #include "predict.h"
  32 #include "vec.h"
  33 #include "hashtab.h"
  34 #include "hash-set.h"
  35 #include "machmode.h"
  36 #include "tm.h"
  37 #include "hard-reg-set.h"
  38 #include "input.h"
  39 #include "function.h"
  40 #include "alloc-pool.h"
  41 #include "timevar.h"
  42
  43 struct dataflow;
  44 struct df_d;
  45 struct df_problem;
  46 struct df_link;
  47 struct df_insn_info;
  48 union df_ref_d;
  49
  50 /* Data flow problems.  All problems must have a unique id here.  */
  51
  52 /* Scanning is not really a dataflow problem, but it is useful to have
  53    the basic block functions in the vector so that things get done in
  54    a uniform manner.  The last four problems can be added or deleted
  55    at any time are always defined (though LIVE is always there at -O2
  56    or higher); the others are always there.  */
  57 #define DF_SCAN    0
  58 #define DF_LR      1      /* Live Registers backward. */
  59 #define DF_LIVE    2      /* Live Registers & Uninitialized Registers */
  60 #define DF_RD      3      /* Reaching Defs. */
  61 #define DF_CHAIN   4      /* Def-Use and/or Use-Def Chains. */
  62 #define DF_WORD_LR 5      /* Subreg tracking lr.  */
  63 #define DF_NOTE    6      /* REG_DEAD and REG_UNUSED notes.  */
  64 #define DF_MD      7      /* Multiple Definitions. */
  65
  66 #define DF_LAST_PROBLEM_PLUS1 (DF_MD + 1)
  67
  68 /* Dataflow direction.  */
  69 enum df_flow_dir
  70   {
  71     DF_NONE,
  72     DF_FORWARD,
  73     DF_BACKWARD
  74   };
  75
  76 /* Descriminator for the various df_ref types.  */
  77 enum df_ref_class {DF_REF_BASE, DF_REF_ARTIFICIAL, DF_REF_REGULAR};
  78
  79 /* The first of these us a set of a registers.  The remaining three
  80    are all uses of a register (the mem_load and mem_store relate to
  81    how the register as an addressing operand).  */
  82 enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE,
  83                   DF_REF_REG_MEM_LOAD, DF_REF_REG_MEM_STORE};
  84
  85 enum df_ref_flags
  86   {
  87     /* This flag is set if this ref occurs inside of a conditional
  88        execution instruction.  */
  89     DF_REF_CONDITIONAL = 1 << 0,
  90
  91     /* If this flag is set for an artificial use or def, that ref
  92        logically happens at the top of the block.  If it is not set
  93        for an artificial use or def, that ref logically happens at the
  94        bottom of the block.  This is never set for regular refs.  */
  95     DF_REF_AT_TOP = 1 << 1,
  96
  97     /* This flag is set if the use is inside a REG_EQUAL or REG_EQUIV
  98        note.  */
  99     DF_REF_IN_NOTE = 1 << 2,
 100
 101     /* This bit is true if this ref can make regs_ever_live true for
 102        this regno.  */
 103     DF_HARD_REG_LIVE = 1 << 3,
 104
 105
 106     /* This flag is set if this ref is a partial use or def of the
 107        associated register.  */
 108     DF_REF_PARTIAL = 1 << 4,
 109
 110     /* Read-modify-write refs generate both a use and a def and
 111        these are marked with this flag to show that they are not
 112        independent.  */
 113     DF_REF_READ_WRITE = 1 << 5,
 114
 115     /* This flag is set if this ref, generally a def, may clobber the
 116        referenced register.  This is generally only set for hard
 117        registers that cross a call site.  With better information
 118        about calls, some of these could be changed in the future to
 119        DF_REF_MUST_CLOBBER.  */
 120     DF_REF_MAY_CLOBBER = 1 << 6,
 121
 122     /* This flag is set if this ref, generally a def, is a real
 123        clobber. This is not currently set for registers live across a
 124        call because that clobbering may or may not happen.
 125
 126        Most of the uses of this are with sets that have a
 127        GET_CODE(..)==CLOBBER.  Note that this is set even if the
 128        clobber is to a subreg.  So in order to tell if the clobber
 129        wipes out the entire register, it is necessary to also check
 130        the DF_REF_PARTIAL flag.  */
 131     DF_REF_MUST_CLOBBER = 1 << 7,
 132
 133
 134     /* If the ref has one of the following two flags set, then the
 135        struct df_ref can be cast to struct df_ref_extract to access
 136        the width and offset fields.  */
 137
 138     /* This flag is set if the ref contains a SIGN_EXTRACT.  */
 139     DF_REF_SIGN_EXTRACT = 1 << 8,
 140
 141     /* This flag is set if the ref contains a ZERO_EXTRACT.  */
 142     DF_REF_ZERO_EXTRACT = 1 << 9,
 143
 144     /* This flag is set if the ref contains a STRICT_LOW_PART.  */
 145     DF_REF_STRICT_LOW_PART = 1 << 10,
 146
 147     /* This flag is set if the ref contains a SUBREG.  */
 148     DF_REF_SUBREG = 1 << 11,
 149
 150
 151     /* This bit is true if this ref is part of a multiword hardreg.  */
 152     DF_REF_MW_HARDREG = 1 << 12,
 153
 154     /* This flag is set if this ref is a usage of the stack pointer by
 155        a function call.  */
 156     DF_REF_CALL_STACK_USAGE = 1 << 13,
 157
 158     /* This flag is used for verification of existing refs. */
 159     DF_REF_REG_MARKER = 1 << 14,
 160
 161     /* This flag is set if this ref is inside a pre/post modify.  */
 162     DF_REF_PRE_POST_MODIFY = 1 << 15
 163
 164   };
 165
 166 /* The possible ordering of refs within the df_ref_info.  */
 167 enum df_ref_order
 168   {
 169     /* There is not table.  */
 170     DF_REF_ORDER_NO_TABLE,
 171
 172     /* There is a table of refs but it is not (or no longer) organized
 173        by one of the following methods.  */
 174     DF_REF_ORDER_UNORDERED,
 175     DF_REF_ORDER_UNORDERED_WITH_NOTES,
 176
 177     /* Organize the table by reg order, all of the refs with regno 0
 178        followed by all of the refs with regno 1 ... .  Within all of
 179        the regs for a particular regno, the refs are unordered.  */
 180     DF_REF_ORDER_BY_REG,
 181
 182     /* For uses, the refs within eq notes may be added for
 183        DF_REF_ORDER_BY_REG.  */
 184     DF_REF_ORDER_BY_REG_WITH_NOTES,
 185
 186     /* Organize the refs in insn order.  The insns are ordered within a
 187        block, and the blocks are ordered by FOR_ALL_BB_FN.  */
 188     DF_REF_ORDER_BY_INSN,
 189
 190     /* For uses, the refs within eq notes may be added for
 191        DF_REF_ORDER_BY_INSN.  */
 192     DF_REF_ORDER_BY_INSN_WITH_NOTES
 193   };
 194
 195 /* Function prototypes added to df_problem instance.  */
 196
 197 /* Allocate the problem specific data.  */
 198 typedef void (*df_alloc_function) (bitmap);
 199
 200 /* This function is called if the problem has global data that needs
 201    to be cleared when ever the set of blocks changes.  The bitmap
 202    contains the set of blocks that may require special attention.
 203    This call is only made if some of the blocks are going to change.
 204    If everything is to be deleted, the wholesale deletion mechanisms
 205    apply. */
 206 typedef void (*df_reset_function) (bitmap);
 207
 208 /* Free the basic block info.  Called from the block reordering code
 209    to get rid of the blocks that have been squished down.   */
 210 typedef void (*df_free_bb_function) (basic_block, void *);
 211
 212 /* Local compute function.  */
 213 typedef void (*df_local_compute_function) (bitmap);
 214
 215 /* Init the solution specific data.  */
 216 typedef void (*df_init_function) (bitmap);
 217
 218 /* Iterative dataflow function.  */
 219 typedef void (*df_dataflow_function) (struct dataflow *, bitmap, int *, int);
 220
 221 /* Confluence operator for blocks with 0 out (or in) edges.  */
 222 typedef void (*df_confluence_function_0) (basic_block);
 223
 224 /* Confluence operator for blocks with 1 or more out (or in) edges.
 225    Return true if BB input data has changed.  */
 226 typedef bool (*df_confluence_function_n) (edge);
 227
 228 /* Transfer function for blocks.
 229    Return true if BB output data has changed.  */
 230 typedef bool (*df_transfer_function) (int);
 231
 232 /* Function to massage the information after the problem solving.  */
 233 typedef void (*df_finalizer_function) (bitmap);
 234
 235 /* Function to free all of the problem specific datastructures.  */
 236 typedef void (*df_free_function) (void);
 237
 238 /* Function to remove this problem from the stack of dataflow problems
 239    without effecting the other problems in the stack except for those
 240    that depend on this problem.  */
 241 typedef void (*df_remove_problem_function) (void);
 242
 243 /* Function to dump basic block independent results to FILE.  */
 244 typedef void (*df_dump_problem_function) (FILE *);
 245
 246 /* Function to dump top or bottom of basic block results to FILE.  */
 247 typedef void (*df_dump_bb_problem_function) (basic_block, FILE *);
 248
 249 /* Function to dump before or after an insn to FILE.  */
 250 typedef void (*df_dump_insn_problem_function) (const rtx_insn *, FILE *);
 251
 252 /* Function to dump top or bottom of basic block results to FILE.  */
 253 typedef void (*df_verify_solution_start) (void);
 254
 255 /* Function to dump top or bottom of basic block results to FILE.  */
 256 typedef void (*df_verify_solution_end) (void);
 257
 258 /* The static description of a dataflow problem to solve.  See above
 259    typedefs for doc for the function fields.  */
 260
 261 struct df_problem {
 262   /* The unique id of the problem.  This is used it index into
 263      df->defined_problems to make accessing the problem data easy.  */
 264   unsigned int id;
 265   enum df_flow_dir dir;                 /* Dataflow direction.  */
 266   df_alloc_function alloc_fun;
 267   df_reset_function reset_fun;
 268   df_free_bb_function free_bb_fun;
 269   df_local_compute_function local_compute_fun;
 270   df_init_function init_fun;
 271   df_dataflow_function dataflow_fun;
 272   df_confluence_function_0 con_fun_0;
 273   df_confluence_function_n con_fun_n;
 274   df_transfer_function trans_fun;
 275   df_finalizer_function finalize_fun;
 276   df_free_function free_fun;
 277   df_remove_problem_function remove_problem_fun;
 278   df_dump_problem_function dump_start_fun;
 279   df_dump_bb_problem_function dump_top_fun;
 280   df_dump_bb_problem_function dump_bottom_fun;
 281   df_dump_insn_problem_function dump_insn_top_fun;
 282   df_dump_insn_problem_function dump_insn_bottom_fun;
 283   df_verify_solution_start verify_start_fun;
 284   df_verify_solution_end verify_end_fun;
 285   struct df_problem *dependent_problem;
 286   unsigned int block_info_elt_size;
 287
 288   /* The timevar id associated with this pass.  */
 289   timevar_id_t tv_id;
 290
 291   /* True if the df_set_blocks should null out the basic block info if
 292      this block drops out of df->blocks_to_analyze.  */
 293   bool free_blocks_on_set_blocks;
 294 };
 295
 296
 297 /* The specific instance of the problem to solve.  */
 298 struct dataflow
 299 {
 300   struct df_problem *problem;           /* The problem to be solved.  */
 301
 302   /* Array indexed by bb->index, that contains basic block problem and
 303      solution specific information.  */
 304   void *block_info;
 305   unsigned int block_info_size;
 306
 307   /* The pool to allocate the block_info from. */
 308   alloc_pool block_pool;
 309
 310   /* The lr and live problems have their transfer functions recomputed
 311      only if necessary.  This is possible for them because, the
 312      problems are kept active for the entire backend and their
 313      transfer functions are indexed by the REGNO.  These are not
 314      defined for any other problem.  */
 315   bitmap out_of_date_transfer_functions;
 316
 317   /* Other problem specific data that is not on a per basic block
 318      basis.  The structure is generally defined privately for the
 319      problem.  The exception being the scanning problem where it is
 320      fully public.  */
 321   void *problem_data;
 322
 323   /* Local flags for some of the problems. */
 324   unsigned int local_flags;
 325
 326   /* True if this problem of this instance has been initialized.  This
 327      is used by the dumpers to keep garbage out of the dumps if, for
 328      debugging a dump is produced before the first call to
 329      df_analyze after a new problem is added.  */
 330   bool computed;
 331
 332   /* True if the something has changed which invalidates the dataflow
 333      solutions.  Note that this bit is always true for all problems except
 334      lr and live.  */
 335   bool solutions_dirty;
 336
 337   /* If true, this pass is deleted by df_finish_pass.  This is never
 338      true for DF_SCAN and DF_LR.  It is true for DF_LIVE if optimize >
 339      1.  It is always true for the other problems.  */
 340   bool optional_p;
 341 };
 342
 343
 344 /* The set of multiword hardregs used as operands to this
 345    instruction. These are factored into individual uses and defs but
 346    the aggregate is still needed to service the REG_DEAD and
 347    REG_UNUSED notes.  */
 348 struct df_mw_hardreg
 349 {
 350   df_mw_hardreg *next;          /* Next entry for this instruction.  */
 351   rtx mw_reg;                   /* The multiword hardreg.  */
 352   /* These two bitfields are intentionally oversized, in the hope that
 353      accesses to 16-bit fields will usually be quicker.  */
 354   ENUM_BITFIELD(df_ref_type) type : 16;
 355                                 /* Used to see if the ref is read or write.  */
 356   int flags : 16;               /* Various df_ref_flags.  */
 357   unsigned int start_regno;     /* First word of the multi word subreg.  */
 358   unsigned int end_regno;       /* Last word of the multi word subreg.  */
 359   unsigned int mw_order;        /* Same as df_ref.ref_order.  */
 360 };
 361
 362
 363 /* Define a register reference structure.  One of these is allocated
 364     for every register reference (use or def).  Note some register
 365     references (e.g., post_inc, subreg) generate both a def and a use.  */
 366 struct df_base_ref
 367 {
 368   /* These three bitfields are intentionally oversized, in the hope that
 369      accesses to 8 and 16-bit fields will usually be quicker.  */
 370   ENUM_BITFIELD(df_ref_class) cl : 8;
 371
 372   ENUM_BITFIELD(df_ref_type) type : 8;
 373                                 /* Type of ref.  */
 374   int flags : 16;               /* Various df_ref_flags.  */
 375   unsigned int regno;           /* The register number referenced.  */
 376   rtx reg;                      /* The register referenced.  */
 377   union df_ref_d *next_loc;     /* Next ref for same insn or bb.  */
 378   struct df_link *chain;        /* Head of def-use, use-def.  */
 379   /* Pointer to the insn info of the containing instruction.  FIXME!
 380      Currently this is NULL for artificial refs but this will be used
 381      when FUDs are added.  */
 382   struct df_insn_info *insn_info;
 383   /* For each regno, there are three chains of refs, one for the uses,
 384      the eq_uses and the defs.  These chains go through the refs
 385      themselves rather than using an external structure.  */
 386   union df_ref_d *next_reg;     /* Next ref with same regno and type.  */
 387   union df_ref_d *prev_reg;     /* Prev ref with same regno and type.  */
 388   /* Location in the ref table.  This is only valid after a call to
 389      df_maybe_reorganize_[use,def]_refs which is an expensive operation.  */
 390   int id;
 391   /* The index at which the operand was scanned in the insn.  This is
 392      used to totally order the refs in an insn.  */
 393   unsigned int ref_order;
 394 };
 395
 396
 397 /* The three types of df_refs.  Note that the df_ref_extract is an
 398    extension of the df_regular_ref, not the df_base_ref.  */
 399 struct df_artificial_ref
 400 {
 401   struct df_base_ref base;
 402
 403   /* Artificial refs do not have an insn, so to get the basic block,
 404      it must be explicitly here.  */
 405   basic_block bb;
 406 };
 407
 408
 409 struct df_regular_ref
 410 {
 411   struct df_base_ref base;
 412   /* The loc is the address in the insn of the reg.  This is not
 413      defined for special registers, such as clobbers and stack
 414      pointers that are also associated with call insns and so those
 415      just use the base.  */
 416   rtx *loc;
 417 };
 418
 419 /* Union of the different kinds of defs/uses placeholders.  */
 420 union df_ref_d
 421 {
 422   struct df_base_ref base;
 423   struct df_regular_ref regular_ref;
 424   struct df_artificial_ref artificial_ref;
 425 };
 426 typedef union df_ref_d *df_ref;
 427
 428
 429 /* One of these structures is allocated for every insn.  */
 430 struct df_insn_info
 431 {
 432   rtx_insn *insn;               /* The insn this info comes from.  */
 433   df_ref defs;                  /* Head of insn-def chain.  */
 434   df_ref uses;                  /* Head of insn-use chain.  */
 435   /* Head of insn-use chain for uses in REG_EQUAL/EQUIV notes.  */
 436   df_ref eq_uses;
 437   struct df_mw_hardreg *mw_hardregs;
 438   /* The logical uid of the insn in the basic block.  This is valid
 439      after any call to df_analyze but may rot after insns are added,
 440      deleted or moved. */
 441   int luid;
 442 };
 443
 444 /* These links are used for ref-ref chains.  Currently only DEF-USE and
 445    USE-DEF chains can be built by DF.  */
 446 struct df_link
 447 {
 448   df_ref ref;
 449   struct df_link *next;
 450 };
 451
 452 \f
 453 enum df_chain_flags
 454 {
 455   /* Flags that control the building of chains.  */
 456   DF_DU_CHAIN      =  1, /* Build DU chains.  */
 457   DF_UD_CHAIN      =  2  /* Build UD chains.  */
 458 };
 459
 460 enum df_changeable_flags
 461 {
 462   /* Scanning flags.  */
 463   /* Flag to control the running of dce as a side effect of building LR.  */
 464   DF_LR_RUN_DCE           = 1 << 0, /* Run DCE.  */
 465   DF_NO_HARD_REGS         = 1 << 1, /* Skip hard registers in RD and CHAIN Building.  */
 466
 467   DF_EQ_NOTES             = 1 << 2, /* Build chains with uses present in EQUIV/EQUAL notes. */
 468   DF_NO_REGS_EVER_LIVE    = 1 << 3, /* Do not compute the regs_ever_live.  */
 469
 470   /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to
 471   return immediately.  This is used by passes that know how to update
 472   the scanning them selves.  */
 473   DF_NO_INSN_RESCAN       = 1 << 4,
 474
 475   /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to
 476   return after marking the insn for later processing.  This allows all
 477   rescans to be batched.  */
 478   DF_DEFER_INSN_RESCAN    = 1 << 5,
 479
 480   /* Compute the reaching defs problem as "live and reaching defs" (LR&RD).
 481      A DEF is reaching and live at insn I if DEF reaches I and REGNO(DEF)
 482      is in LR_IN of the basic block containing I.  */
 483   DF_RD_PRUNE_DEAD_DEFS   = 1 << 6,
 484
 485   DF_VERIFY_SCHEDULED     = 1 << 7
 486 };
 487
 488 /* Two of these structures are inline in df, one for the uses and one
 489    for the defs.  This structure is only contains the refs within the
 490    boundary of the df_set_blocks if that has been defined.  */
 491 struct df_ref_info
 492 {
 493   df_ref *refs;                 /* Ref table, indexed by id.  */
 494   unsigned int *begin;          /* First ref_index for this pseudo.  */
 495   unsigned int *count;          /* Count of refs for this pseudo.  */
 496   unsigned int refs_size;       /* Size of currently allocated refs table.  */
 497
 498   /* Table_size is the number of elements in the refs table.  This
 499      will also be the width of the bitvectors in the rd and ru
 500      problems.  Total_size is the number of refs.  These will be the
 501      same if the focus has not been reduced by df_set_blocks.  If the
 502      focus has been reduced, table_size will be smaller since it only
 503      contains the refs in the set blocks.  */
 504   unsigned int table_size;
 505   unsigned int total_size;
 506
 507   enum df_ref_order ref_order;
 508 };
 509
 510 /* Three of these structures are allocated for every pseudo reg. One
 511    for the uses, one for the eq_uses and one for the defs.  */
 512 struct df_reg_info
 513 {
 514   /* Head of chain for refs of that type and regno.  */
 515   df_ref reg_chain;
 516   /* Number of refs in the chain.  */
 517   unsigned int n_refs;
 518 };
 519
 520
 521 /*----------------------------------------------------------------------------
 522    Problem data for the scanning dataflow problem.  Unlike the other
 523    dataflow problems, the problem data for scanning is fully exposed and
 524    used by owners of the problem.
 525 ----------------------------------------------------------------------------*/
 526
 527 struct df_d
 528 {
 529
 530   /* The set of problems to be solved is stored in two arrays.  In
 531      PROBLEMS_IN_ORDER, the problems are stored in the order that they
 532      are solved.  This is an internally dense array that may have
 533      nulls at the end of it.  In PROBLEMS_BY_INDEX, the problem is
 534      stored by the value in df_problem.id.  These are used to access
 535      the problem local data without having to search the first
 536      array.  */
 537
 538   struct dataflow *problems_in_order[DF_LAST_PROBLEM_PLUS1];
 539   struct dataflow *problems_by_index[DF_LAST_PROBLEM_PLUS1];
 540
 541   /* If not NULL, this subset of blocks of the program to be
 542      considered for analysis.  At certain times, this will contain all
 543      the blocks in the function so it cannot be used as an indicator
 544      of if we are analyzing a subset.  See analyze_subset.  */
 545   bitmap blocks_to_analyze;
 546
 547   /* The following information is really the problem data for the
 548      scanning instance but it is used too often by the other problems
 549      to keep getting it from there.  */
 550   struct df_ref_info def_info;   /* Def info.  */
 551   struct df_ref_info use_info;   /* Use info.  */
 552
 553   /* The following three arrays are allocated in parallel.   They contain
 554      the sets of refs of each type for each reg.  */
 555   struct df_reg_info **def_regs;       /* Def reg info.  */
 556   struct df_reg_info **use_regs;       /* Eq_use reg info.  */
 557   struct df_reg_info **eq_use_regs;    /* Eq_use info.  */
 558   unsigned int regs_size;       /* Size of currently allocated regs table.  */
 559   unsigned int regs_inited;     /* Number of regs with reg_infos allocated.  */
 560
 561
 562   struct df_insn_info **insns;   /* Insn table, indexed by insn UID.  */
 563   unsigned int insns_size;       /* Size of insn table.  */
 564
 565   int num_problems_defined;
 566
 567   bitmap_head hardware_regs_used;     /* The set of hardware registers used.  */
 568   /* The set of hard regs that are in the artificial uses at the end
 569      of a regular basic block.  */
 570   bitmap_head regular_block_artificial_uses;
 571   /* The set of hard regs that are in the artificial uses at the end
 572      of a basic block that has an EH pred.  */
 573   bitmap_head eh_block_artificial_uses;
 574   /* The set of hardware registers live on entry to the function.  */
 575   bitmap entry_block_defs;
 576   bitmap exit_block_uses;        /* The set of hardware registers used in exit block.  */
 577
 578   /* Insns to delete, rescan or reprocess the notes at next
 579      df_rescan_all or df_process_deferred_rescans. */
 580   bitmap_head insns_to_delete;
 581   bitmap_head insns_to_rescan;
 582   bitmap_head insns_to_notes_rescan;
 583   int *postorder;                /* The current set of basic blocks
 584                                     in reverse postorder.  */
 585   int *postorder_inverted;       /* The current set of basic blocks
 586                                     in reverse postorder of inverted CFG.  */
 587   int n_blocks;                  /* The number of blocks in reverse postorder.  */
 588   int n_blocks_inverted;         /* The number of blocks
 589                                     in reverse postorder of inverted CFG.  */
 590
 591   /* An array [FIRST_PSEUDO_REGISTER], indexed by regno, of the number
 592      of refs that qualify as being real hard regs uses.  Artificial
 593      uses and defs as well as refs in eq notes are ignored.  If the
 594      ref is a def, it cannot be a MAY_CLOBBER def.  If the ref is a
 595      use, it cannot be the emim_reg_set or be the frame or arg pointer
 596      register.  Uses in debug insns are ignored.
 597
 598      IT IS NOT ACCEPTABLE TO MANUALLY CHANGE THIS ARRAY.  This array
 599      always reflects the actual number of refs in the insn stream that
 600      satisfy the above criteria.  */
 601   unsigned int *hard_regs_live_count;
 602
 603   /* This counter provides a way to totally order refs without using
 604      addresses.  It is incremented whenever a ref is created.  */
 605   unsigned int ref_order;
 606
 607   /* Problem specific control information.  This is a combination of
 608      enum df_changeable_flags values.  */
 609   int changeable_flags : 8;
 610
 611   /* If this is true, then only a subset of the blocks of the program
 612      is considered to compute the solutions of dataflow problems.  */
 613   bool analyze_subset;
 614
 615   /* True if someone added or deleted something from regs_ever_live so
 616      that the entry and exit blocks need be reprocessed.  */
 617   bool redo_entry_and_exit;
 618 };
 619
 620 #define DF_SCAN_BB_INFO(BB) (df_scan_get_bb_info ((BB)->index))
 621 #define DF_RD_BB_INFO(BB) (df_rd_get_bb_info ((BB)->index))
 622 #define DF_LR_BB_INFO(BB) (df_lr_get_bb_info ((BB)->index))
 623 #define DF_LIVE_BB_INFO(BB) (df_live_get_bb_info ((BB)->index))
 624 #define DF_WORD_LR_BB_INFO(BB) (df_word_lr_get_bb_info ((BB)->index))
 625 #define DF_MD_BB_INFO(BB) (df_md_get_bb_info ((BB)->index))
 626
 627 /* Most transformations that wish to use live register analysis will
 628    use these macros.  This info is the and of the lr and live sets.  */
 629 #define DF_LIVE_IN(BB) (&DF_LIVE_BB_INFO (BB)->in)
 630 #define DF_LIVE_OUT(BB) (&DF_LIVE_BB_INFO (BB)->out)
 631
 632 /* These macros are used by passes that are not tolerant of
 633    uninitialized variables.  This intolerance should eventually
 634    be fixed.  */
 635 #define DF_LR_IN(BB) (&DF_LR_BB_INFO (BB)->in)
 636 #define DF_LR_OUT(BB) (&DF_LR_BB_INFO (BB)->out)
 637
 638 /* These macros are used by passes that are not tolerant of
 639    uninitialized variables.  This intolerance should eventually
 640    be fixed.  */
 641 #define DF_WORD_LR_IN(BB) (&DF_WORD_LR_BB_INFO (BB)->in)
 642 #define DF_WORD_LR_OUT(BB) (&DF_WORD_LR_BB_INFO (BB)->out)
 643
 644 /* Macros to access the elements within the ref structure.  */
 645
 646
 647 #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->base.reg) == SUBREG \
 648                                 ? SUBREG_REG ((REF)->base.reg) : ((REF)->base.reg))
 649 #define DF_REF_REGNO(REF) ((REF)->base.regno)
 650 #define DF_REF_REAL_LOC(REF) (GET_CODE (*((REF)->regular_ref.loc)) == SUBREG \
 651                                ? &SUBREG_REG (*((REF)->regular_ref.loc)) : ((REF)->regular_ref.loc))
 652 #define DF_REF_REG(REF) ((REF)->base.reg)
 653 #define DF_REF_LOC(REF) (DF_REF_CLASS (REF) == DF_REF_REGULAR ? \
 654                          (REF)->regular_ref.loc : NULL)
 655 #define DF_REF_BB(REF) (DF_REF_IS_ARTIFICIAL (REF) \
 656                         ? (REF)->artificial_ref.bb \
 657                         : BLOCK_FOR_INSN (DF_REF_INSN (REF)))
 658 #define DF_REF_BBNO(REF) (DF_REF_BB (REF)->index)
 659 #define DF_REF_INSN_INFO(REF) ((REF)->base.insn_info)
 660 #define DF_REF_INSN(REF) ((REF)->base.insn_info->insn)
 661 #define DF_REF_INSN_UID(REF) (INSN_UID (DF_REF_INSN(REF)))
 662 #define DF_REF_CLASS(REF) ((REF)->base.cl)
 663 #define DF_REF_TYPE(REF) ((REF)->base.type)
 664 #define DF_REF_CHAIN(REF) ((REF)->base.chain)
 665 #define DF_REF_ID(REF) ((REF)->base.id)
 666 #define DF_REF_FLAGS(REF) ((REF)->base.flags)
 667 #define DF_REF_FLAGS_IS_SET(REF, v) ((DF_REF_FLAGS (REF) & (v)) != 0)
 668 #define DF_REF_FLAGS_SET(REF, v) (DF_REF_FLAGS (REF) |= (v))
 669 #define DF_REF_FLAGS_CLEAR(REF, v) (DF_REF_FLAGS (REF) &= ~(v))
 670 #define DF_REF_ORDER(REF) ((REF)->base.ref_order)
 671 /* If DF_REF_IS_ARTIFICIAL () is true, this is not a real
 672    definition/use, but an artificial one created to model always live
 673    registers, eh uses, etc.  */
 674 #define DF_REF_IS_ARTIFICIAL(REF) (DF_REF_CLASS (REF) == DF_REF_ARTIFICIAL)
 675 #define DF_REF_REG_MARK(REF) (DF_REF_FLAGS_SET ((REF),DF_REF_REG_MARKER))
 676 #define DF_REF_REG_UNMARK(REF) (DF_REF_FLAGS_CLEAR ((REF),DF_REF_REG_MARKER))
 677 #define DF_REF_IS_REG_MARKED(REF) (DF_REF_FLAGS_IS_SET ((REF),DF_REF_REG_MARKER))
 678 #define DF_REF_NEXT_LOC(REF) ((REF)->base.next_loc)
 679 #define DF_REF_NEXT_REG(REF) ((REF)->base.next_reg)
 680 #define DF_REF_PREV_REG(REF) ((REF)->base.prev_reg)
 681 /* The following two macros may only be applied if one of
 682    DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT is true. */
 683 #define DF_REF_EXTRACT_WIDTH(REF) ((REF)->extract_ref.width)
 684 #define DF_REF_EXTRACT_OFFSET(REF) ((REF)->extract_ref.offset)
 685 #define DF_REF_EXTRACT_MODE(REF) ((REF)->extract_ref.mode)
 686
 687 /* Macros to determine the reference type.  */
 688 #define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF)
 689 #define DF_REF_REG_USE_P(REF) (!DF_REF_REG_DEF_P (REF))
 690 #define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE)
 691 #define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD)
 692 #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \
 693                                || DF_REF_REG_MEM_LOAD_P (REF))
 694
 695 #define DF_MWS_REG_DEF_P(MREF) (DF_MWS_TYPE (MREF) == DF_REF_REG_DEF)
 696 #define DF_MWS_REG_USE_P(MREF) (!DF_MWS_REG_DEF_P (MREF))
 697 #define DF_MWS_NEXT(MREF) ((MREF)->next)
 698 #define DF_MWS_TYPE(MREF) ((MREF)->type)
 699
 700 /* Macros to get the refs out of def_info or use_info refs table.  If
 701    the focus of the dataflow has been set to some subset of blocks
 702    with df_set_blocks, these macros will only find the uses and defs
 703    in that subset of blocks.
 704
 705    These macros should be used with care.  The def macros are only
 706    usable after a call to df_maybe_reorganize_def_refs and the use
 707    macros are only usable after a call to
 708    df_maybe_reorganize_use_refs.  HOWEVER, BUILDING AND USING THESE
 709    ARRAYS ARE A CACHE LOCALITY KILLER.  */
 710
 711 #define DF_DEFS_TABLE_SIZE() (df->def_info.table_size)
 712 #define DF_DEFS_GET(ID) (df->def_info.refs[(ID)])
 713 #define DF_DEFS_SET(ID,VAL) (df->def_info.refs[(ID)]=(VAL))
 714 #define DF_DEFS_COUNT(ID) (df->def_info.count[(ID)])
 715 #define DF_DEFS_BEGIN(ID) (df->def_info.begin[(ID)])
 716 #define DF_USES_TABLE_SIZE() (df->use_info.table_size)
 717 #define DF_USES_GET(ID) (df->use_info.refs[(ID)])
 718 #define DF_USES_SET(ID,VAL) (df->use_info.refs[(ID)]=(VAL))
 719 #define DF_USES_COUNT(ID) (df->use_info.count[(ID)])
 720 #define DF_USES_BEGIN(ID) (df->use_info.begin[(ID)])
 721
 722 /* Macros to access the register information from scan dataflow record.  */
 723
 724 #define DF_REG_SIZE(DF) (df->regs_inited)
 725 #define DF_REG_DEF_GET(REG) (df->def_regs[(REG)])
 726 #define DF_REG_DEF_CHAIN(REG) (df->def_regs[(REG)]->reg_chain)
 727 #define DF_REG_DEF_COUNT(REG) (df->def_regs[(REG)]->n_refs)
 728 #define DF_REG_USE_GET(REG) (df->use_regs[(REG)])
 729 #define DF_REG_USE_CHAIN(REG) (df->use_regs[(REG)]->reg_chain)
 730 #define DF_REG_USE_COUNT(REG) (df->use_regs[(REG)]->n_refs)
 731 #define DF_REG_EQ_USE_GET(REG) (df->eq_use_regs[(REG)])
 732 #define DF_REG_EQ_USE_CHAIN(REG) (df->eq_use_regs[(REG)]->reg_chain)
 733 #define DF_REG_EQ_USE_COUNT(REG) (df->eq_use_regs[(REG)]->n_refs)
 734
 735 /* Macros to access the elements within the reg_info structure table.  */
 736
 737 #define DF_REGNO_FIRST_DEF(REGNUM) \
 738 (DF_REG_DEF_GET(REGNUM) ? DF_REG_DEF_GET (REGNUM) : 0)
 739 #define DF_REGNO_LAST_USE(REGNUM) \
 740 (DF_REG_USE_GET(REGNUM) ? DF_REG_USE_GET (REGNUM) : 0)
 741
 742 /* Macros to access the elements within the insn_info structure table.  */
 743
 744 #define DF_INSN_SIZE() ((df)->insns_size)
 745 #define DF_INSN_INFO_GET(INSN) (df->insns[(INSN_UID (INSN))])
 746 #define DF_INSN_INFO_SET(INSN,VAL) (df->insns[(INSN_UID (INSN))]=(VAL))
 747 #define DF_INSN_INFO_LUID(II) ((II)->luid)
 748 #define DF_INSN_INFO_DEFS(II) ((II)->defs)
 749 #define DF_INSN_INFO_USES(II) ((II)->uses)
 750 #define DF_INSN_INFO_EQ_USES(II) ((II)->eq_uses)
 751 #define DF_INSN_INFO_MWS(II) ((II)->mw_hardregs)
 752
 753 #define DF_INSN_LUID(INSN) (DF_INSN_INFO_LUID (DF_INSN_INFO_GET (INSN)))
 754 #define DF_INSN_DEFS(INSN) (DF_INSN_INFO_DEFS (DF_INSN_INFO_GET (INSN)))
 755 #define DF_INSN_USES(INSN) (DF_INSN_INFO_USES (DF_INSN_INFO_GET (INSN)))
 756 #define DF_INSN_EQ_USES(INSN) (DF_INSN_INFO_EQ_USES (DF_INSN_INFO_GET (INSN)))
 757
 758 #define DF_INSN_UID_GET(UID) (df->insns[(UID)])
 759 #define DF_INSN_UID_SET(UID,VAL) (df->insns[(UID)]=(VAL))
 760 #define DF_INSN_UID_SAFE_GET(UID) (((unsigned)(UID) < DF_INSN_SIZE ())  \
 761                                      ? DF_INSN_UID_GET (UID) \
 762                                      : NULL)
 763 #define DF_INSN_UID_LUID(INSN) (DF_INSN_UID_GET (INSN)->luid)
 764 #define DF_INSN_UID_DEFS(INSN) (DF_INSN_UID_GET (INSN)->defs)
 765 #define DF_INSN_UID_USES(INSN) (DF_INSN_UID_GET (INSN)->uses)
 766 #define DF_INSN_UID_EQ_USES(INSN) (DF_INSN_UID_GET (INSN)->eq_uses)
 767 #define DF_INSN_UID_MWS(INSN) (DF_INSN_UID_GET (INSN)->mw_hardregs)
 768
 769 #define FOR_EACH_INSN_INFO_DEF(ITER, INSN) \
 770   for (ITER = DF_INSN_INFO_DEFS (INSN); ITER; ITER = DF_REF_NEXT_LOC (ITER))
 771
 772 #define FOR_EACH_INSN_INFO_USE(ITER, INSN) \
 773   for (ITER = DF_INSN_INFO_USES (INSN); ITER; ITER = DF_REF_NEXT_LOC (ITER))
 774
 775 #define FOR_EACH_INSN_INFO_EQ_USE(ITER, INSN) \
 776   for (ITER = DF_INSN_INFO_EQ_USES (INSN); ITER; ITER = DF_REF_NEXT_LOC (ITER))
 777
 778 #define FOR_EACH_INSN_INFO_MW(ITER, INSN) \
 779   for (ITER = DF_INSN_INFO_MWS (INSN); ITER; ITER = DF_MWS_NEXT (ITER))
 780
 781 #define FOR_EACH_INSN_DEF(ITER, INSN) \
 782   FOR_EACH_INSN_INFO_DEF(ITER, DF_INSN_INFO_GET (INSN))
 783
 784 #define FOR_EACH_INSN_USE(ITER, INSN) \
 785   FOR_EACH_INSN_INFO_USE(ITER, DF_INSN_INFO_GET (INSN))
 786
 787 #define FOR_EACH_INSN_EQ_USE(ITER, INSN) \
 788   FOR_EACH_INSN_INFO_EQ_USE(ITER, DF_INSN_INFO_GET (INSN))
 789
 790 #define FOR_EACH_ARTIFICIAL_USE(ITER, BB_INDEX) \
 791   for (ITER = df_get_artificial_uses (BB_INDEX); ITER; \
 792        ITER = DF_REF_NEXT_LOC (ITER))
 793
 794 #define FOR_EACH_ARTIFICIAL_DEF(ITER, BB_INDEX) \
 795   for (ITER = df_get_artificial_defs (BB_INDEX); ITER; \
 796        ITER = DF_REF_NEXT_LOC (ITER))
 797
 798 /* An obstack for bitmap not related to specific dataflow problems.
 799    This obstack should e.g. be used for bitmaps with a short life time
 800    such as temporary bitmaps.  This obstack is declared in df-core.c.  */
 801
 802 extern bitmap_obstack df_bitmap_obstack;
 803
 804
 805 /* One of these structures is allocated for every basic block.  */
 806 struct df_scan_bb_info
 807 {
 808   /* The entry block has many artificial defs and these are at the
 809      bottom of the block.
 810
 811      Blocks that are targets of exception edges may have some
 812      artificial defs.  These are logically located at the top of the
 813      block.
 814
 815      Blocks that are the targets of non-local goto's have the hard
 816      frame pointer defined at the top of the block.  */
 817   df_ref artificial_defs;
 818
 819   /* Blocks that are targets of exception edges may have some
 820      artificial uses.  These are logically at the top of the block.
 821
 822      Most blocks have artificial uses at the bottom of the block.  */
 823   df_ref artificial_uses;
 824 };
 825
 826
 827 /* Reaching definitions.  All bitmaps are indexed by the id field of
 828    the ref except sparse_kill which is indexed by regno.  For the
 829    LR&RD problem, the kill set is not complete: It does not contain
 830    DEFs killed because the set register has died in the LR set.  */
 831 struct df_rd_bb_info
 832 {
 833   /* Local sets to describe the basic blocks.   */
 834   bitmap_head kill;
 835   bitmap_head sparse_kill;
 836   bitmap_head gen;   /* The set of defs generated in this block.  */
 837
 838   /* The results of the dataflow problem.  */
 839   bitmap_head in;    /* At the top of the block.  */
 840   bitmap_head out;   /* At the bottom of the block.  */
 841 };
 842
 843
 844 /* Multiple reaching definitions.  All bitmaps are referenced by the
 845    register number.  */
 846
 847 struct df_md_bb_info
 848 {
 849   /* Local sets to describe the basic blocks.  */
 850   bitmap_head gen;    /* Partial/conditional definitions live at BB out.  */
 851   bitmap_head kill;   /* Other definitions that are live at BB out.  */
 852   bitmap_head init;   /* Definitions coming from dominance frontier edges. */
 853
 854   /* The results of the dataflow problem.  */
 855   bitmap_head in;    /* Just before the block itself. */
 856   bitmap_head out;   /* At the bottom of the block.  */
 857 };
 858
 859
 860 /* Live registers, a backwards dataflow problem.  All bitmaps are
 861    referenced by the register number.  */
 862
 863 struct df_lr_bb_info
 864 {
 865   /* Local sets to describe the basic blocks.  */
 866   bitmap_head def;   /* The set of registers set in this block
 867                         - except artificial defs at the top.  */
 868   bitmap_head use;   /* The set of registers used in this block.  */
 869
 870   /* The results of the dataflow problem.  */
 871   bitmap_head in;    /* Just before the block itself. */
 872   bitmap_head out;   /* At the bottom of the block.  */
 873 };
 874
 875
 876 /* Uninitialized registers.  All bitmaps are referenced by the
 877    register number.  Anded results of the forwards and backward live
 878    info.  Note that the forwards live information is not available
 879    separately.  */
 880 struct df_live_bb_info
 881 {
 882   /* Local sets to describe the basic blocks.  */
 883   bitmap_head kill;  /* The set of registers unset in this block.  Calls,
 884                         for instance, unset registers.  */
 885   bitmap_head gen;   /* The set of registers set in this block.  */
 886
 887   /* The results of the dataflow problem.  */
 888   bitmap_head in;    /* At the top of the block.  */
 889   bitmap_head out;   /* At the bottom of the block.  */
 890 };
 891
 892
 893 /* Live registers, a backwards dataflow problem.  These bitmaps are
 894    indexed by 2 * regno for each pseudo and have two entries for each
 895    pseudo.  Only pseudos that have a size of 2 * UNITS_PER_WORD are
 896    meaningfully tracked.  */
 897
 898 struct df_word_lr_bb_info
 899 {
 900   /* Local sets to describe the basic blocks.  */
 901   bitmap_head def;   /* The set of registers set in this block
 902                         - except artificial defs at the top.  */
 903   bitmap_head use;   /* The set of registers used in this block.  */
 904
 905   /* The results of the dataflow problem.  */
 906   bitmap_head in;    /* Just before the block itself. */
 907   bitmap_head out;   /* At the bottom of the block.  */
 908 };
 909
 910
 911 /* This is used for debugging and for the dumpers to find the latest
 912    instance so that the df info can be added to the dumps.  This
 913    should not be used by regular code.  */
 914 extern struct df_d *df;
 915 #define df_scan    (df->problems_by_index[DF_SCAN])
 916 #define df_rd      (df->problems_by_index[DF_RD])
 917 #define df_lr      (df->problems_by_index[DF_LR])
 918 #define df_live    (df->problems_by_index[DF_LIVE])
 919 #define df_chain   (df->problems_by_index[DF_CHAIN])
 920 #define df_word_lr (df->problems_by_index[DF_WORD_LR])
 921 #define df_note    (df->problems_by_index[DF_NOTE])
 922 #define df_md      (df->problems_by_index[DF_MD])
 923
 924 /* This symbol turns on checking that each modification of the cfg has
 925   been identified to the appropriate df routines.  It is not part of
 926   verification per se because the check that the final solution has
 927   not changed covers this.  However, if the solution is not being
 928   properly recomputed because the cfg is being modified, adding in
 929   calls to df_check_cfg_clean can be used to find the source of that
 930   kind of problem.  */
 931 #if 0
 932 #define DF_DEBUG_CFG
 933 #endif
 934
 935
 936 /* Functions defined in df-core.c.  */
 937
 938 extern void df_add_problem (struct df_problem *);
 939 extern int df_set_flags (int);
 940 extern int df_clear_flags (int);
 941 extern void df_set_blocks (bitmap);
 942 extern void df_remove_problem (struct dataflow *);
 943 extern void df_finish_pass (bool);
 944 extern void df_analyze_problem (struct dataflow *, bitmap, int *, int);
 945 extern void df_analyze ();
 946 extern void df_analyze_loop (struct loop *);
 947 extern int df_get_n_blocks (enum df_flow_dir);
 948 extern int *df_get_postorder (enum df_flow_dir);
 949 extern void df_simple_dataflow (enum df_flow_dir, df_init_function,
 950                                 df_confluence_function_0, df_confluence_function_n,
 951                                 df_transfer_function, bitmap, int *, int);
 952 extern void df_mark_solutions_dirty (void);
 953 extern bool df_get_bb_dirty (basic_block);
 954 extern void df_set_bb_dirty (basic_block);
 955 extern void df_compact_blocks (void);
 956 extern void df_bb_replace (int, basic_block);
 957 extern void df_bb_delete (int);
 958 extern void df_verify (void);
 959 #ifdef DF_DEBUG_CFG
 960 extern void df_check_cfg_clean (void);
 961 #endif
 962 extern df_ref df_bb_regno_first_def_find (basic_block, unsigned int);
 963 extern df_ref df_bb_regno_last_def_find (basic_block, unsigned int);
 964 extern df_ref df_find_def (rtx_insn *, rtx);
 965 extern bool df_reg_defined (rtx_insn *, rtx);
 966 extern df_ref df_find_use (rtx_insn *, rtx);
 967 extern bool df_reg_used (rtx_insn *, rtx);
 968 extern void df_worklist_dataflow (struct dataflow *,bitmap, int *, int);
 969 extern void df_print_regset (FILE *file, bitmap r);
 970 extern void df_print_word_regset (FILE *file, bitmap r);
 971 extern void df_dump (FILE *);
 972 extern void df_dump_region (FILE *);
 973 extern void df_dump_start (FILE *);
 974 extern void df_dump_top (basic_block, FILE *);
 975 extern void df_dump_bottom (basic_block, FILE *);
 976 extern void df_dump_insn_top (const rtx_insn *, FILE *);
 977 extern void df_dump_insn_bottom (const rtx_insn *, FILE *);
 978 extern void df_refs_chain_dump (df_ref, bool, FILE *);
 979 extern void df_regs_chain_dump (df_ref,  FILE *);
 980 extern void df_insn_debug (rtx_insn *, bool, FILE *);
 981 extern void df_insn_debug_regno (rtx_insn *, FILE *);
 982 extern void df_regno_debug (unsigned int, FILE *);
 983 extern void df_ref_debug (df_ref, FILE *);
 984 extern void debug_df_insn (rtx_insn *);
 985 extern void debug_df_regno (unsigned int);
 986 extern void debug_df_reg (rtx);
 987 extern void debug_df_defno (unsigned int);
 988 extern void debug_df_useno (unsigned int);
 989 extern void debug_df_ref (df_ref);
 990 extern void debug_df_chain (struct df_link *);
 991
 992 /* Functions defined in df-problems.c. */
 993
 994 extern struct df_link *df_chain_create (df_ref, df_ref);
 995 extern void df_chain_unlink (df_ref);
 996 extern void df_chain_copy (df_ref, struct df_link *);
 997 extern void df_grow_bb_info (struct dataflow *);
 998 extern void df_chain_dump (struct df_link *, FILE *);
 999 extern void df_print_bb_index (basic_block bb, FILE *file);
1000 extern void df_rd_add_problem (void);
1001 extern void df_rd_simulate_artificial_defs_at_top (basic_block, bitmap);
1002 extern void df_rd_simulate_one_insn (basic_block, rtx_insn *, bitmap);
1003 extern void df_lr_add_problem (void);
1004 extern void df_lr_verify_transfer_functions (void);
1005 extern void df_live_verify_transfer_functions (void);
1006 extern void df_live_add_problem (void);
1007 extern void df_live_set_all_dirty (void);
1008 extern void df_chain_add_problem (unsigned int);
1009 extern void df_word_lr_add_problem (void);
1010 extern bool df_word_lr_mark_ref (df_ref, bool, bitmap);
1011 extern bool df_word_lr_simulate_defs (rtx_insn *, bitmap);
1012 extern void df_word_lr_simulate_uses (rtx_insn *, bitmap);
1013 extern void df_word_lr_simulate_artificial_refs_at_top (basic_block, bitmap);
1014 extern void df_word_lr_simulate_artificial_refs_at_end (basic_block, bitmap);
1015 extern void df_note_add_problem (void);
1016 extern void df_md_add_problem (void);
1017 extern void df_md_simulate_artificial_defs_at_top (basic_block, bitmap);
1018 extern void df_md_simulate_one_insn (basic_block, rtx_insn *, bitmap);
1019 extern void df_simulate_find_noclobber_defs (rtx_insn *, bitmap);
1020 extern void df_simulate_find_defs (rtx_insn *, bitmap);
1021 extern void df_simulate_defs (rtx_insn *, bitmap);
1022 extern void df_simulate_uses (rtx_insn *, bitmap);
1023 extern void df_simulate_initialize_backwards (basic_block, bitmap);
1024 extern void df_simulate_one_insn_backwards (basic_block, rtx_insn *, bitmap);
1025 extern void df_simulate_finalize_backwards (basic_block, bitmap);
1026 extern void df_simulate_initialize_forwards (basic_block, bitmap);
1027 extern void df_simulate_one_insn_forwards (basic_block, rtx_insn *, bitmap);
1028 extern void simulate_backwards_to_point (basic_block, regset, rtx);
1029 extern bool can_move_insns_across (rtx_insn *, rtx_insn *,
1030                                    rtx_insn *, rtx_insn *,
1031                                    basic_block, regset,
1032                                    regset, rtx_insn **);
1033 /* Functions defined in df-scan.c.  */
1034
1035 extern void df_scan_alloc (bitmap);
1036 extern void df_scan_add_problem (void);
1037 extern void df_grow_reg_info (void);
1038 extern void df_grow_insn_info (void);
1039 extern void df_scan_blocks (void);
1040 extern void df_uses_create (rtx *, rtx_insn *, int);
1041 extern struct df_insn_info * df_insn_create_insn_record (rtx_insn *);
1042 extern void df_insn_delete (rtx_insn *);
1043 extern void df_bb_refs_record (int, bool);
1044 extern bool df_insn_rescan (rtx_insn *);
1045 extern bool df_insn_rescan_debug_internal (rtx_insn *);
1046 extern void df_insn_rescan_all (void);
1047 extern void df_process_deferred_rescans (void);
1048 extern void df_recompute_luids (basic_block);
1049 extern void df_insn_change_bb (rtx_insn *, basic_block);
1050 extern void df_maybe_reorganize_use_refs (enum df_ref_order);
1051 extern void df_maybe_reorganize_def_refs (enum df_ref_order);
1052 extern void df_ref_change_reg_with_loc (int, int, rtx);
1053 extern void df_notes_rescan (rtx_insn *);
1054 extern void df_hard_reg_init (void);
1055 extern void df_update_entry_block_defs (void);
1056 extern void df_update_exit_block_uses (void);
1057 extern void df_update_entry_exit_and_calls (void);
1058 extern bool df_hard_reg_used_p (unsigned int);
1059 extern unsigned int df_hard_reg_used_count (unsigned int);
1060 extern bool df_regs_ever_live_p (unsigned int);
1061 extern void df_set_regs_ever_live (unsigned int, bool);
1062 extern void df_compute_regs_ever_live (bool);
1063 extern bool df_read_modify_subreg_p (rtx);
1064 extern void df_scan_verify (void);
1065
1066 \f
1067 /*----------------------------------------------------------------------------
1068    Public functions access functions for the dataflow problems.
1069 ----------------------------------------------------------------------------*/
1070
1071 static inline struct df_scan_bb_info *
1072 df_scan_get_bb_info (unsigned int index)
1073 {
1074   if (index < df_scan->block_info_size)
1075     return &((struct df_scan_bb_info *) df_scan->block_info)[index];
1076   else
1077     return NULL;
1078 }
1079
1080 static inline struct df_rd_bb_info *
1081 df_rd_get_bb_info (unsigned int index)
1082 {
1083   if (index < df_rd->block_info_size)
1084     return &((struct df_rd_bb_info *) df_rd->block_info)[index];
1085   else
1086     return NULL;
1087 }
1088
1089 static inline struct df_lr_bb_info *
1090 df_lr_get_bb_info (unsigned int index)
1091 {
1092   if (index < df_lr->block_info_size)
1093     return &((struct df_lr_bb_info *) df_lr->block_info)[index];
1094   else
1095     return NULL;
1096 }
1097
1098 static inline struct df_md_bb_info *
1099 df_md_get_bb_info (unsigned int index)
1100 {
1101   if (index < df_md->block_info_size)
1102     return &((struct df_md_bb_info *) df_md->block_info)[index];
1103   else
1104     return NULL;
1105 }
1106
1107 static inline struct df_live_bb_info *
1108 df_live_get_bb_info (unsigned int index)
1109 {
1110   if (index < df_live->block_info_size)
1111     return &((struct df_live_bb_info *) df_live->block_info)[index];
1112   else
1113     return NULL;
1114 }
1115
1116 static inline struct df_word_lr_bb_info *
1117 df_word_lr_get_bb_info (unsigned int index)
1118 {
1119   if (index < df_word_lr->block_info_size)
1120     return &((struct df_word_lr_bb_info *) df_word_lr->block_info)[index];
1121   else
1122     return NULL;
1123 }
1124
1125 /* Get the live at out set for BB no matter what problem happens to be
1126    defined.  This function is used by the register allocators who
1127    choose different dataflow problems depending on the optimization
1128    level.  */
1129
1130 static inline bitmap
1131 df_get_live_out (basic_block bb)
1132 {
1133   gcc_checking_assert (df_lr);
1134
1135   if (df_live)
1136     return DF_LIVE_OUT (bb);
1137   else
1138     return DF_LR_OUT (bb);
1139 }
1140
1141 /* Get the live at in set for BB no matter what problem happens to be
1142    defined.  This function is used by the register allocators who
1143    choose different dataflow problems depending on the optimization
1144    level.  */
1145
1146 static inline bitmap
1147 df_get_live_in (basic_block bb)
1148 {
1149   gcc_checking_assert (df_lr);
1150
1151   if (df_live)
1152     return DF_LIVE_IN (bb);
1153   else
1154     return DF_LR_IN (bb);
1155 }
1156
1157 /* Get basic block info.  */
1158 /* Get the artificial defs for a basic block.  */
1159
1160 static inline df_ref
1161 df_get_artificial_defs (unsigned int bb_index)
1162 {
1163   return df_scan_get_bb_info (bb_index)->artificial_defs;
1164 }
1165
1166
1167 /* Get the artificial uses for a basic block.  */
1168
1169 static inline df_ref
1170 df_get_artificial_uses (unsigned int bb_index)
1171 {
1172   return df_scan_get_bb_info (bb_index)->artificial_uses;
1173 }
1174
1175 /* If INSN defines exactly one register, return the associated reference,
1176    otherwise return null.  */
1177
1178 static inline df_ref
1179 df_single_def (const df_insn_info *info)
1180 {
1181   df_ref defs = DF_INSN_INFO_DEFS (info);
1182   return defs && !DF_REF_NEXT_LOC (defs) ? defs : NULL;
1183 }
1184
1185 /* If INSN uses exactly one register, return the associated reference,
1186    otherwise return null.  */
1187
1188 static inline df_ref
1189 df_single_use (const df_insn_info *info)
1190 {
1191   df_ref uses = DF_INSN_INFO_USES (info);
1192   return uses && !DF_REF_NEXT_LOC (uses) ? uses : NULL;
1193 }
1194
1195 /* web */
1196
1197 class web_entry_base
1198 {
1199  private:
1200   /* Reference to the parent in the union/find tree.  */
1201   web_entry_base *pred_pvt;
1202
1203  public:
1204   /* Accessors.  */
1205   web_entry_base *pred () { return pred_pvt; }
1206   void set_pred (web_entry_base *p) { pred_pvt = p; }
1207
1208   /* Find representative in union-find tree.  */
1209   web_entry_base *unionfind_root ();
1210
1211   /* Union with another set, returning TRUE if they are already unioned.  */
1212   friend bool unionfind_union (web_entry_base *first, web_entry_base *second);
1213 };
1214
1215 #endif /* GCC_DF_H */