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