gcc/df.h

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