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