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