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