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