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