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