gcc/df.h

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