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