gcc/tree-flow.h

   1 /* Data and Control Flow Analysis for Trees.
   2    Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #ifndef _TREE_FLOW_H
  23 #define _TREE_FLOW_H 1
  24
  25 #include "bitmap.h"
  26 #include "hard-reg-set.h"
  27 #include "basic-block.h"
  28 #include "hashtab.h"
  29 #include "gimple.h"
  30 #include "tree-ssa-operands.h"
  31 #include "cgraph.h"
  32 #include "ipa-reference.h"
  33 #include "tree-ssa-alias.h"
  34
  35
  36 /* Gimple dataflow datastructure. All publicly available fields shall have
  37    gimple_ accessor defined in tree-flow-inline.h, all publicly modifiable
  38    fields should have gimple_set accessor.  */
  39 struct GTY(()) gimple_df {
  40   /* Array of all variables referenced in the function.  */
  41   htab_t GTY((param_is (union tree_node))) referenced_vars;
  42
  43   /* A vector of all the noreturn calls passed to modify_stmt.
  44      cleanup_control_flow uses it to detect cases where a mid-block
  45      indirect call has been turned into a noreturn call.  When this
  46      happens, all the instructions after the call are no longer
  47      reachable and must be deleted as dead.  */
  48   VEC(gimple,gc) *modified_noreturn_calls;
  49
  50   /* Array of all SSA_NAMEs used in the function.  */
  51   VEC(tree,gc) *ssa_names;
  52
  53   /* Artificial variable used for the virtual operand FUD chain.  */
  54   tree vop;
  55
  56   /* Artificial variable used to model the effects of nonlocal
  57      variables.  */
  58   tree nonlocal_all;
  59
  60   /* The PTA solution for the ESCAPED artificial variable.  */
  61   struct pt_solution escaped;
  62
  63   /* The PTA solution for the CALLUSED artificial variable.  */
  64   struct pt_solution callused;
  65
  66   /* A map of decls to artificial ssa-names that point to the partition
  67      of the decl.  */
  68   struct pointer_map_t * GTY((skip(""))) decls_to_pointers;
  69
  70   /* Free list of SSA_NAMEs.  */
  71   tree free_ssanames;
  72
  73   /* Hashtable holding definition for symbol.  If this field is not NULL, it
  74      means that the first reference to this variable in the function is a
  75      USE or a VUSE.  In those cases, the SSA renamer creates an SSA name
  76      for this variable with an empty defining statement.  */
  77   htab_t GTY((param_is (union tree_node))) default_defs;
  78
  79   /* Symbols whose SSA form needs to be updated or created for the first
  80      time.  */
  81   bitmap syms_to_rename;
  82
  83   /* True if the code is in ssa form.  */
  84   unsigned int in_ssa_p : 1;
  85
  86   struct ssa_operands ssa_operands;
  87 };
  88
  89 /* Accessors for internal use only.  Generic code should use abstraction
  90    provided by tree-flow-inline.h or specific modules.  */
  91 #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
  92 #define SSANAMES(fun) (fun)->gimple_df->ssa_names
  93 #define MODIFIED_NORETURN_CALLS(fun) (fun)->gimple_df->modified_noreturn_calls
  94 #define DEFAULT_DEFS(fun) (fun)->gimple_df->default_defs
  95 #define SYMS_TO_RENAME(fun) (fun)->gimple_df->syms_to_rename
  96
  97 typedef struct
  98 {
  99   htab_t htab;
 100   PTR *slot;
 101   PTR *limit;
 102 } htab_iterator;
 103
 104 /* Iterate through the elements of hashtable HTAB, using htab_iterator ITER,
 105    storing each element in RESULT, which is of type TYPE.  */
 106 #define FOR_EACH_HTAB_ELEMENT(HTAB, RESULT, TYPE, ITER) \
 107   for (RESULT = (TYPE) first_htab_element (&(ITER), (HTAB)); \
 108         !end_htab_p (&(ITER)); \
 109         RESULT = (TYPE) next_htab_element (&(ITER)))
 110
 111 /*---------------------------------------------------------------------------
 112                       Attributes for SSA_NAMEs.
 113
 114   NOTE: These structures are stored in struct tree_ssa_name
 115   but are only used by the tree optimizers, so it makes better sense
 116   to declare them here to avoid recompiling unrelated files when
 117   making changes.
 118 ---------------------------------------------------------------------------*/
 119
 120 /* Aliasing information for SSA_NAMEs representing pointer variables.  */
 121 struct GTY(()) ptr_info_def
 122 {
 123   /* The points-to solution, TBAA-pruned if the pointer is dereferenced.  */
 124   struct pt_solution pt;
 125 };
 126
 127
 128 /* It is advantageous to avoid things like life analysis for variables which
 129    do not need PHI nodes.  This enum describes whether or not a particular
 130    variable may need a PHI node.  */
 131
 132 enum need_phi_state {
 133   /* This is the default.  If we are still in this state after finding
 134      all the definition and use sites, then we will assume the variable
 135      needs PHI nodes.  This is probably an overly conservative assumption.  */
 136   NEED_PHI_STATE_UNKNOWN,
 137
 138   /* This state indicates that we have seen one or more sets of the
 139      variable in a single basic block and that the sets dominate all
 140      uses seen so far.  If after finding all definition and use sites
 141      we are still in this state, then the variable does not need any
 142      PHI nodes.  */
 143   NEED_PHI_STATE_NO,
 144
 145   /* This state indicates that we have either seen multiple definitions of
 146      the variable in multiple blocks, or that we encountered a use in a
 147      block that was not dominated by the block containing the set(s) of
 148      this variable.  This variable is assumed to need PHI nodes.  */
 149   NEED_PHI_STATE_MAYBE
 150 };
 151
 152
 153 /* The "no alias" attribute allows alias analysis to make more
 154    aggressive assumptions when assigning alias sets, computing
 155    points-to information and memory partitions.  These attributes
 156    are the result of user annotations or flags (e.g.,
 157    -fargument-noalias).  */
 158 enum noalias_state {
 159     /* Default state.  No special assumptions can be made about this
 160        symbol.  */
 161     MAY_ALIAS = 0,
 162
 163     /* The symbol does not alias with other symbols that have a
 164        NO_ALIAS* attribute.  */
 165     NO_ALIAS,
 166
 167     /* The symbol does not alias with other symbols that have a
 168        NO_ALIAS*, and it may not alias with global symbols.  */
 169     NO_ALIAS_GLOBAL,
 170
 171     /* The symbol does not alias with any other symbols.  */
 172     NO_ALIAS_ANYTHING
 173 };
 174
 175
 176 struct GTY(()) var_ann_d {
 177   /* Used when building base variable structures in a var_map.  */
 178   unsigned base_var_processed : 1;
 179
 180   /* Nonzero if this variable was used after SSA optimizations were
 181      applied.  We set this when translating out of SSA form.  */
 182   unsigned used : 1;
 183
 184   /* This field indicates whether or not the variable may need PHI nodes.
 185      See the enum's definition for more detailed information about the
 186      states.  */
 187   ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
 188
 189   /* True for HEAP artificial variables.  These variables represent
 190      the memory area allocated by a call to malloc.  */
 191   unsigned is_heapvar : 1;
 192
 193   /* This field describes several "no alias" attributes that some
 194      symbols are known to have.  See the enum's definition for more
 195      information on each attribute.  */
 196   ENUM_BITFIELD (noalias_state) noalias_state : 2;
 197
 198   /* Used by var_map for the base index of ssa base variables.  */
 199   unsigned base_index;
 200
 201   /* During into-ssa and the dominator optimizer, this field holds the
 202      current version of this variable (an SSA_NAME).  */
 203   tree current_def;
 204 };
 205
 206
 207 /* Immediate use lists are used to directly access all uses for an SSA
 208    name and get pointers to the statement for each use.
 209
 210    The structure ssa_use_operand_d consists of PREV and NEXT pointers
 211    to maintain the list.  A USE pointer, which points to address where
 212    the use is located and a LOC pointer which can point to the
 213    statement where the use is located, or, in the case of the root
 214    node, it points to the SSA name itself.
 215
 216    The list is anchored by an occurrence of ssa_operand_d *in* the
 217    ssa_name node itself (named 'imm_uses').  This node is uniquely
 218    identified by having a NULL USE pointer. and the LOC pointer
 219    pointing back to the ssa_name node itself.  This node forms the
 220    base for a circular list, and initially this is the only node in
 221    the list.
 222
 223    Fast iteration allows each use to be examined, but does not allow
 224    any modifications to the uses or stmts.
 225
 226    Normal iteration allows insertion, deletion, and modification. the
 227    iterator manages this by inserting a marker node into the list
 228    immediately before the node currently being examined in the list.
 229    this marker node is uniquely identified by having null stmt *and* a
 230    null use pointer.
 231
 232    When iterating to the next use, the iteration routines check to see
 233    if the node after the marker has changed. if it has, then the node
 234    following the marker is now the next one to be visited. if not, the
 235    marker node is moved past that node in the list (visualize it as
 236    bumping the marker node through the list).  this continues until
 237    the marker node is moved to the original anchor position. the
 238    marker node is then removed from the list.
 239
 240    If iteration is halted early, the marker node must be removed from
 241    the list before continuing.  */
 242 typedef struct immediate_use_iterator_d
 243 {
 244   /* This is the current use the iterator is processing.  */
 245   ssa_use_operand_t *imm_use;
 246   /* This marks the last use in the list (use node from SSA_NAME)  */
 247   ssa_use_operand_t *end_p;
 248   /* This node is inserted and used to mark the end of the uses for a stmt.  */
 249   ssa_use_operand_t iter_node;
 250   /* This is the next ssa_name to visit.  IMM_USE may get removed before
 251      the next one is traversed to, so it must be cached early.  */
 252   ssa_use_operand_t *next_imm_name;
 253 } imm_use_iterator;
 254
 255
 256 /* Use this iterator when simply looking at stmts.  Adding, deleting or
 257    modifying stmts will cause this iterator to malfunction.  */
 258
 259 #define FOR_EACH_IMM_USE_FAST(DEST, ITER, SSAVAR)                       \
 260   for ((DEST) = first_readonly_imm_use (&(ITER), (SSAVAR));     \
 261        !end_readonly_imm_use_p (&(ITER));                       \
 262        (DEST) = next_readonly_imm_use (&(ITER)))
 263
 264 /* Use this iterator to visit each stmt which has a use of SSAVAR.  */
 265
 266 #define FOR_EACH_IMM_USE_STMT(STMT, ITER, SSAVAR)               \
 267   for ((STMT) = first_imm_use_stmt (&(ITER), (SSAVAR));         \
 268        !end_imm_use_stmt_p (&(ITER));                           \
 269        (STMT) = next_imm_use_stmt (&(ITER)))
 270
 271 /* Use this to terminate the FOR_EACH_IMM_USE_STMT loop early.  Failure to
 272    do so will result in leaving a iterator marker node in the immediate
 273    use list, and nothing good will come from that.   */
 274 #define BREAK_FROM_IMM_USE_STMT(ITER)                           \
 275    {                                                            \
 276      end_imm_use_stmt_traverse (&(ITER));                       \
 277      break;                                                     \
 278    }
 279
 280
 281 /* Use this iterator in combination with FOR_EACH_IMM_USE_STMT to
 282    get access to each occurrence of ssavar on the stmt returned by
 283    that iterator..  for instance:
 284
 285      FOR_EACH_IMM_USE_STMT (stmt, iter, var)
 286        {
 287          FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 288            {
 289              SET_USE (use_p, blah);
 290            }
 291          update_stmt (stmt);
 292        }                                                         */
 293
 294 #define FOR_EACH_IMM_USE_ON_STMT(DEST, ITER)                    \
 295   for ((DEST) = first_imm_use_on_stmt (&(ITER));                \
 296        !end_imm_use_on_stmt_p (&(ITER));                        \
 297        (DEST) = next_imm_use_on_stmt (&(ITER)))
 298
 299
 300
 301 typedef struct var_ann_d *var_ann_t;
 302
 303 static inline var_ann_t var_ann (const_tree);
 304 static inline var_ann_t get_var_ann (tree);
 305 static inline void update_stmt (gimple);
 306 static inline int get_lineno (const_gimple);
 307
 308 /*---------------------------------------------------------------------------
 309                   Structure representing predictions in tree level.
 310 ---------------------------------------------------------------------------*/
 311 struct GTY((chain_next ("%h.ep_next"))) edge_prediction {
 312   struct edge_prediction *ep_next;
 313   edge ep_edge;
 314   enum br_predictor ep_predictor;
 315   int ep_probability;
 316 };
 317
 318 /* Accessors for basic block annotations.  */
 319 static inline gimple_seq phi_nodes (const_basic_block);
 320 static inline void set_phi_nodes (basic_block, gimple_seq);
 321
 322 /*---------------------------------------------------------------------------
 323                               Global declarations
 324 ---------------------------------------------------------------------------*/
 325 struct GTY(()) int_tree_map {
 326
 327   unsigned int uid;
 328   tree to;
 329 };
 330
 331 extern unsigned int int_tree_map_hash (const void *);
 332 extern int int_tree_map_eq (const void *, const void *);
 333
 334 extern unsigned int uid_decl_map_hash (const void *);
 335 extern int uid_decl_map_eq (const void *, const void *);
 336
 337 typedef struct
 338 {
 339   htab_iterator hti;
 340 } referenced_var_iterator;
 341
 342
 343 /* This macro loops over all the referenced vars, one at a time, putting the
 344    current var in VAR.  Note:  You are not allowed to add referenced variables
 345    to the hashtable while using this macro.  Doing so may cause it to behave
 346    erratically.  */
 347
 348 #define FOR_EACH_REFERENCED_VAR(VAR, ITER) \
 349   for ((VAR) = first_referenced_var (&(ITER)); \
 350        !end_referenced_vars_p (&(ITER)); \
 351        (VAR) = next_referenced_var (&(ITER)))
 352
 353
 354 typedef struct
 355 {
 356   int i;
 357 } safe_referenced_var_iterator;
 358
 359 /* This macro loops over all the referenced vars, one at a time, putting the
 360    current var in VAR.  You are allowed to add referenced variables during the
 361    execution of this macro, however, the macro will not iterate over them.  It
 362    requires a temporary vector of trees, VEC, whose lifetime is controlled by
 363    the caller.  The purpose of the vector is to temporarily store the
 364    referenced_variables hashtable so that adding referenced variables does not
 365    affect the hashtable.  */
 366
 367 #define FOR_EACH_REFERENCED_VAR_SAFE(VAR, VEC, ITER) \
 368   for ((ITER).i = 0, fill_referenced_var_vec (&(VEC)); \
 369        VEC_iterate (tree, (VEC), (ITER).i, (VAR)); \
 370        (ITER).i++)
 371
 372 extern tree referenced_var_lookup (unsigned int);
 373 extern bool referenced_var_check_and_insert (tree);
 374 #define num_referenced_vars htab_elements (gimple_referenced_vars (cfun))
 375 #define referenced_var(i) referenced_var_lookup (i)
 376
 377 #define num_ssa_names (VEC_length (tree, cfun->gimple_df->ssa_names))
 378 #define ssa_name(i) (VEC_index (tree, cfun->gimple_df->ssa_names, (i)))
 379
 380 /* Macros for showing usage statistics.  */
 381 #define SCALE(x) ((unsigned long) ((x) < 1024*10        \
 382                   ? (x)                                 \
 383                   : ((x) < 1024*1024*10                 \
 384                      ? (x) / 1024                       \
 385                      : (x) / (1024*1024))))
 386
 387 #define LABEL(x) ((x) < 1024*10 ? 'b' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 388
 389 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
 390
 391 /*---------------------------------------------------------------------------
 392                               OpenMP Region Tree
 393 ---------------------------------------------------------------------------*/
 394
 395 /* Parallel region information.  Every parallel and workshare
 396    directive is enclosed between two markers, the OMP_* directive
 397    and a corresponding OMP_RETURN statement.  */
 398
 399 struct omp_region
 400 {
 401   /* The enclosing region.  */
 402   struct omp_region *outer;
 403
 404   /* First child region.  */
 405   struct omp_region *inner;
 406
 407   /* Next peer region.  */
 408   struct omp_region *next;
 409
 410   /* Block containing the omp directive as its last stmt.  */
 411   basic_block entry;
 412
 413   /* Block containing the OMP_RETURN as its last stmt.  */
 414   basic_block exit;
 415
 416   /* Block containing the OMP_CONTINUE as its last stmt.  */
 417   basic_block cont;
 418
 419   /* If this is a combined parallel+workshare region, this is a list
 420      of additional arguments needed by the combined parallel+workshare
 421      library call.  */
 422   tree ws_args;
 423
 424   /* The code for the omp directive of this region.  */
 425   enum gimple_code type;
 426
 427   /* Schedule kind, only used for OMP_FOR type regions.  */
 428   enum omp_clause_schedule_kind sched_kind;
 429
 430   /* True if this is a combined parallel+workshare region.  */
 431   bool is_combined_parallel;
 432 };
 433
 434 extern struct omp_region *root_omp_region;
 435 extern struct omp_region *new_omp_region (basic_block, enum gimple_code,
 436                                           struct omp_region *);
 437 extern void free_omp_regions (void);
 438 void omp_expand_local (basic_block);
 439 extern tree find_omp_clause (tree, enum omp_clause_code);
 440 tree copy_var_decl (tree, tree, tree);
 441
 442 /*---------------------------------------------------------------------------
 443                               Function prototypes
 444 ---------------------------------------------------------------------------*/
 445 /* In tree-cfg.c  */
 446
 447 /* Location to track pending stmt for edge insertion.  */
 448 #define PENDING_STMT(e) ((e)->insns.g)
 449
 450 extern void delete_tree_cfg_annotations (void);
 451 extern bool stmt_ends_bb_p (gimple);
 452 extern bool is_ctrl_stmt (gimple);
 453 extern bool is_ctrl_altering_stmt (gimple);
 454 extern bool simple_goto_p (gimple);
 455 extern bool stmt_can_make_abnormal_goto (gimple);
 456 extern basic_block single_noncomplex_succ (basic_block bb);
 457 extern void gimple_dump_bb (basic_block, FILE *, int, int);
 458 extern void gimple_debug_bb (basic_block);
 459 extern basic_block gimple_debug_bb_n (int);
 460 extern void gimple_dump_cfg (FILE *, int);
 461 extern void gimple_debug_cfg (int);
 462 extern void dump_cfg_stats (FILE *);
 463 extern void dot_cfg (void);
 464 extern void debug_cfg_stats (void);
 465 extern void debug_loops (int);
 466 extern void debug_loop (struct loop *, int);
 467 extern void debug_loop_num (unsigned, int);
 468 extern void print_loops (FILE *, int);
 469 extern void print_loops_bb (FILE *, basic_block, int, int);
 470 extern void cleanup_dead_labels (void);
 471 extern void group_case_labels (void);
 472 extern gimple first_stmt (basic_block);
 473 extern gimple last_stmt (basic_block);
 474 extern gimple last_and_only_stmt (basic_block);
 475 extern edge find_taken_edge (basic_block, tree);
 476 extern basic_block label_to_block_fn (struct function *, tree);
 477 #define label_to_block(t) (label_to_block_fn (cfun, t))
 478 extern void notice_special_calls (gimple);
 479 extern void clear_special_calls (void);
 480 extern void verify_stmts (void);
 481 extern void verify_gimple (void);
 482 extern void verify_types_in_gimple_seq (gimple_seq);
 483 extern tree gimple_block_label (basic_block);
 484 extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
 485 extern bool gimple_duplicate_sese_region (edge, edge, basic_block *, unsigned,
 486                                         basic_block *);
 487 extern bool gimple_duplicate_sese_tail (edge, edge, basic_block *, unsigned,
 488                                       basic_block *);
 489 extern void gather_blocks_in_sese_region (basic_block entry, basic_block exit,
 490                                           VEC(basic_block,heap) **bbs_p);
 491 extern void add_phi_args_after_copy_bb (basic_block);
 492 extern void add_phi_args_after_copy (basic_block *, unsigned, edge);
 493 extern bool gimple_purge_dead_abnormal_call_edges (basic_block);
 494 extern bool gimple_purge_dead_eh_edges (basic_block);
 495 extern bool gimple_purge_all_dead_eh_edges (const_bitmap);
 496 extern tree gimplify_build1 (gimple_stmt_iterator *, enum tree_code,
 497                              tree, tree);
 498 extern tree gimplify_build2 (gimple_stmt_iterator *, enum tree_code,
 499                              tree, tree, tree);
 500 extern tree gimplify_build3 (gimple_stmt_iterator *, enum tree_code,
 501                              tree, tree, tree, tree);
 502 extern void init_empty_tree_cfg (void);
 503 extern void init_empty_tree_cfg_for_function (struct function *);
 504 extern void fold_cond_expr_cond (void);
 505 extern void make_abnormal_goto_edges (basic_block, bool);
 506 extern void replace_uses_by (tree, tree);
 507 extern void start_recording_case_labels (void);
 508 extern void end_recording_case_labels (void);
 509 extern basic_block move_sese_region_to_fn (struct function *, basic_block,
 510                                            basic_block, tree);
 511 void remove_edge_and_dominated_blocks (edge);
 512 void mark_virtual_ops_in_bb (basic_block);
 513 bool tree_node_can_be_shared (tree);
 514
 515 /* In tree-cfgcleanup.c  */
 516 extern bitmap cfgcleanup_altered_bbs;
 517 extern bool cleanup_tree_cfg (void);
 518
 519 /* In tree-pretty-print.c.  */
 520 extern void dump_generic_bb (FILE *, basic_block, int, int);
 521 extern int op_code_prio (enum tree_code);
 522 extern int op_prio (const_tree);
 523 extern const char *op_symbol_code (enum tree_code);
 524
 525 /* In tree-dfa.c  */
 526 extern var_ann_t create_var_ann (tree);
 527 extern void renumber_gimple_stmt_uids (void);
 528 extern void renumber_gimple_stmt_uids_in_blocks (basic_block *, int);
 529 extern void dump_dfa_stats (FILE *);
 530 extern void debug_dfa_stats (void);
 531 extern void debug_referenced_vars (void);
 532 extern void dump_referenced_vars (FILE *);
 533 extern void dump_variable (FILE *, tree);
 534 extern void debug_variable (tree);
 535 extern tree get_virtual_var (tree);
 536 extern bool add_referenced_var (tree);
 537 extern void remove_referenced_var (tree);
 538 extern void mark_symbols_for_renaming (gimple);
 539 extern void find_new_referenced_vars (gimple);
 540 extern tree make_rename_temp (tree, const char *);
 541 extern void set_default_def (tree, tree);
 542 extern tree gimple_default_def (struct function *, tree);
 543 extern bool stmt_references_abnormal_ssa_name (gimple);
 544 extern tree get_ref_base_and_extent (tree, HOST_WIDE_INT *,
 545                                      HOST_WIDE_INT *, HOST_WIDE_INT *);
 546 extern void find_referenced_vars_in (gimple);
 547
 548 /* In tree-phinodes.c  */
 549 extern void reserve_phi_args_for_new_edge (basic_block);
 550 extern void add_phi_node_to_bb (gimple phi, basic_block bb);
 551 extern gimple make_phi_node (tree var, int len);
 552 extern gimple create_phi_node (tree, basic_block);
 553 extern void add_phi_arg (gimple, tree, edge, source_location);
 554 extern void remove_phi_args (edge);
 555 extern void remove_phi_node (gimple_stmt_iterator *, bool);
 556 extern void remove_phi_nodes (basic_block);
 557 extern void init_phinodes (void);
 558 extern void fini_phinodes (void);
 559 extern void release_phi_node (gimple);
 560 #ifdef GATHER_STATISTICS
 561 extern void phinodes_print_statistics (void);
 562 #endif
 563
 564 /* In gimple-low.c  */
 565 extern void record_vars_into (tree, tree);
 566 extern void record_vars (tree);
 567 extern bool block_may_fallthru (const_tree);
 568 extern bool gimple_seq_may_fallthru (gimple_seq);
 569 extern bool gimple_stmt_may_fallthru (gimple);
 570 extern bool gimple_check_call_args (gimple);
 571
 572
 573 /* In tree-ssa.c  */
 574
 575 /* Mapping for redirected edges.  */
 576 struct GTY(()) _edge_var_map {
 577   tree result;                  /* PHI result.  */
 578   tree def;                     /* PHI arg definition.  */
 579   source_location locus;        /* PHI arg location.  */
 580 };
 581 typedef struct _edge_var_map edge_var_map;
 582
 583 DEF_VEC_O(edge_var_map);
 584 DEF_VEC_ALLOC_O(edge_var_map, heap);
 585
 586 /* A vector of var maps.  */
 587 typedef VEC(edge_var_map, heap) *edge_var_map_vector;
 588
 589 extern void init_tree_ssa (struct function *);
 590 extern void redirect_edge_var_map_add (edge, tree, tree, source_location);
 591 extern void redirect_edge_var_map_clear (edge);
 592 extern void redirect_edge_var_map_dup (edge, edge);
 593 extern edge_var_map_vector redirect_edge_var_map_vector (edge);
 594 extern void redirect_edge_var_map_destroy (void);
 595
 596 extern edge ssa_redirect_edge (edge, basic_block);
 597 extern void flush_pending_stmts (edge);
 598 extern void verify_ssa (bool);
 599 extern void delete_tree_ssa (void);
 600 extern bool ssa_undefined_value_p (tree);
 601 extern void execute_update_addresses_taken (bool);
 602
 603 /* Call-back function for walk_use_def_chains().  At each reaching
 604    definition, a function with this prototype is called.  */
 605 typedef bool (*walk_use_def_chains_fn) (tree, gimple, void *);
 606
 607 extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *, bool);
 608
 609 void insert_debug_temps_for_defs (gimple_stmt_iterator *);
 610 void insert_debug_temp_for_var_def (gimple_stmt_iterator *, tree);
 611 void release_defs_bitset (bitmap toremove);
 612
 613 /* In tree-into-ssa.c  */
 614 void update_ssa (unsigned);
 615 void delete_update_ssa (void);
 616 void register_new_name_mapping (tree, tree);
 617 tree create_new_def_for (tree, gimple, def_operand_p);
 618 bool need_ssa_update_p (struct function *);
 619 bool name_mappings_registered_p (void);
 620 bool name_registered_for_update_p (tree);
 621 bitmap ssa_names_to_replace (void);
 622 void release_ssa_name_after_update_ssa (tree);
 623 void compute_global_livein (bitmap, bitmap);
 624 void mark_sym_for_renaming (tree);
 625 void mark_set_for_renaming (bitmap);
 626 tree get_current_def (tree);
 627 void set_current_def (tree, tree);
 628
 629 /* In tree-ssanames.c  */
 630 extern void init_ssanames (struct function *, int);
 631 extern void fini_ssanames (void);
 632 extern tree make_ssa_name_fn (struct function *, tree, gimple);
 633 extern tree duplicate_ssa_name (tree, gimple);
 634 extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *);
 635 extern void release_ssa_name (tree);
 636 extern void release_defs (gimple);
 637 extern void replace_ssa_name_symbol (tree, tree);
 638
 639 #ifdef GATHER_STATISTICS
 640 extern void ssanames_print_statistics (void);
 641 #endif
 642
 643 /* In tree-ssa-ccp.c  */
 644 bool fold_stmt (gimple_stmt_iterator *);
 645 bool fold_stmt_inplace (gimple);
 646 tree get_symbol_constant_value (tree);
 647 tree fold_const_aggregate_ref (tree);
 648 bool may_propagate_address_into_dereference (tree, tree);
 649
 650
 651 /* In tree-ssa-dom.c  */
 652 extern void dump_dominator_optimization_stats (FILE *);
 653 extern void debug_dominator_optimization_stats (void);
 654 int loop_depth_of_name (tree);
 655 tree degenerate_phi_result (gimple);
 656
 657 /* In tree-ssa-copy.c  */
 658 extern void propagate_value (use_operand_p, tree);
 659 extern void propagate_tree_value (tree *, tree);
 660 extern void propagate_tree_value_into_stmt (gimple_stmt_iterator *, tree);
 661 extern void replace_exp (use_operand_p, tree);
 662 extern bool may_propagate_copy (tree, tree);
 663 extern bool may_propagate_copy_into_stmt (gimple, tree);
 664 extern bool may_propagate_copy_into_asm (tree);
 665
 666 /* Affine iv.  */
 667
 668 typedef struct
 669 {
 670   /* Iv = BASE + STEP * i.  */
 671   tree base, step;
 672
 673   /* True if this iv does not overflow.  */
 674   bool no_overflow;
 675 } affine_iv;
 676
 677 /* Description of number of iterations of a loop.  All the expressions inside
 678    the structure can be evaluated at the end of the loop's preheader
 679    (and due to ssa form, also anywhere inside the body of the loop).  */
 680
 681 struct tree_niter_desc
 682 {
 683   tree assumptions;     /* The boolean expression.  If this expression evaluates
 684                            to false, then the other fields in this structure
 685                            should not be used; there is no guarantee that they
 686                            will be correct.  */
 687   tree may_be_zero;     /* The boolean expression.  If it evaluates to true,
 688                            the loop will exit in the first iteration (i.e.
 689                            its latch will not be executed), even if the niter
 690                            field says otherwise.  */
 691   tree niter;           /* The expression giving the number of iterations of
 692                            a loop (provided that assumptions == true and
 693                            may_be_zero == false), more precisely the number
 694                            of executions of the latch of the loop.  */
 695   double_int max;       /* The upper bound on the number of iterations of
 696                            the loop.  */
 697
 698   /* The simplified shape of the exit condition.  The loop exits if
 699      CONTROL CMP BOUND is false, where CMP is one of NE_EXPR,
 700      LT_EXPR, or GT_EXPR, and step of CONTROL is positive if CMP is
 701      LE_EXPR and negative if CMP is GE_EXPR.  This information is used
 702      by loop unrolling.  */
 703   affine_iv control;
 704   tree bound;
 705   enum tree_code cmp;
 706 };
 707
 708 /* In tree-ssa-phiopt.c */
 709 bool empty_block_p (basic_block);
 710 basic_block *blocks_in_phiopt_order (void);
 711
 712 /* In tree-ssa-loop*.c  */
 713
 714 void tree_ssa_lim (void);
 715 unsigned int tree_ssa_unswitch_loops (void);
 716 unsigned int canonicalize_induction_variables (void);
 717 unsigned int tree_unroll_loops_completely (bool, bool);
 718 unsigned int tree_ssa_prefetch_arrays (void);
 719 void tree_ssa_iv_optimize (void);
 720 unsigned tree_predictive_commoning (void);
 721 tree canonicalize_loop_ivs (struct loop *, tree *);
 722 bool parallelize_loops (void);
 723
 724 bool loop_only_exit_p (const struct loop *, const_edge);
 725 bool number_of_iterations_exit (struct loop *, edge,
 726                                 struct tree_niter_desc *niter, bool);
 727 tree find_loop_niter (struct loop *, edge *);
 728 tree loop_niter_by_eval (struct loop *, edge);
 729 tree find_loop_niter_by_eval (struct loop *, edge *);
 730 void estimate_numbers_of_iterations (void);
 731 bool array_at_struct_end_p (tree);
 732 bool scev_probably_wraps_p (tree, tree, gimple, struct loop *, bool);
 733 bool convert_affine_scev (struct loop *, tree, tree *, tree *, gimple, bool);
 734
 735 bool nowrap_type_p (tree);
 736 enum ev_direction {EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN};
 737 enum ev_direction scev_direction (const_tree);
 738
 739 void free_numbers_of_iterations_estimates (void);
 740 void free_numbers_of_iterations_estimates_loop (struct loop *);
 741 void rewrite_into_loop_closed_ssa (bitmap, unsigned);
 742 void verify_loop_closed_ssa (void);
 743 bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
 744 void create_iv (tree, tree, tree, struct loop *, gimple_stmt_iterator *, bool,
 745                 tree *, tree *);
 746 basic_block split_loop_exit_edge (edge);
 747 void standard_iv_increment_position (struct loop *, gimple_stmt_iterator *,
 748                                      bool *);
 749 basic_block ip_end_pos (struct loop *);
 750 basic_block ip_normal_pos (struct loop *);
 751 bool gimple_duplicate_loop_to_header_edge (struct loop *, edge,
 752                                          unsigned int, sbitmap,
 753                                          edge, VEC (edge, heap) **,
 754                                          int);
 755 struct loop *slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *, edge);
 756 void rename_variables_in_loop (struct loop *);
 757 void rename_variables_in_bb (basic_block bb);
 758 struct loop *tree_ssa_loop_version (struct loop *, tree,
 759                                     basic_block *);
 760 tree expand_simple_operations (tree);
 761 void substitute_in_loop_info (struct loop *, tree, tree);
 762 edge single_dom_exit (struct loop *);
 763 bool can_unroll_loop_p (struct loop *loop, unsigned factor,
 764                         struct tree_niter_desc *niter);
 765 void tree_unroll_loop (struct loop *, unsigned,
 766                        edge, struct tree_niter_desc *);
 767 typedef void (*transform_callback)(struct loop *, void *);
 768 void tree_transform_and_unroll_loop (struct loop *, unsigned,
 769                                      edge, struct tree_niter_desc *,
 770                                      transform_callback, void *);
 771 bool contains_abnormal_ssa_name_p (tree);
 772 bool stmt_dominates_stmt_p (gimple, gimple);
 773 void mark_virtual_ops_for_renaming (gimple);
 774
 775 /* In tree-ssa-dce.c */
 776 void mark_virtual_phi_result_for_renaming (gimple);
 777
 778 /* In tree-ssa-threadedge.c */
 779 extern void threadedge_initialize_values (void);
 780 extern void threadedge_finalize_values (void);
 781 extern VEC(tree,heap) *ssa_name_values;
 782 #define SSA_NAME_VALUE(x) \
 783     (SSA_NAME_VERSION(x) < VEC_length(tree, ssa_name_values) \
 784      ? VEC_index(tree, ssa_name_values, SSA_NAME_VERSION(x)) \
 785      : NULL_TREE)
 786 extern void set_ssa_name_value (tree, tree);
 787 extern bool potentially_threadable_block (basic_block);
 788 extern void thread_across_edge (gimple, edge, bool,
 789                                 VEC(tree, heap) **, tree (*) (gimple, gimple));
 790
 791 /* In tree-ssa-loop-im.c  */
 792 /* The possibilities of statement movement.  */
 793
 794 enum move_pos
 795   {
 796     MOVE_IMPOSSIBLE,            /* No movement -- side effect expression.  */
 797     MOVE_PRESERVE_EXECUTION,    /* Must not cause the non-executed statement
 798                                    become executed -- memory accesses, ... */
 799     MOVE_POSSIBLE               /* Unlimited movement.  */
 800   };
 801 extern enum move_pos movement_possibility (gimple);
 802 char *get_lsm_tmp_name (tree, unsigned);
 803
 804 /* In tree-flow-inline.h  */
 805 static inline bool is_call_clobbered (const_tree);
 806 static inline void set_is_used (tree);
 807 static inline bool unmodifiable_var_p (const_tree);
 808 static inline bool ref_contains_array_ref (const_tree);
 809 static inline bool array_ref_contains_indirect_ref (const_tree);
 810
 811 /* In tree-eh.c  */
 812 extern void make_eh_edges (gimple);
 813 extern bool make_eh_dispatch_edges (gimple);
 814 extern edge redirect_eh_edge (edge, basic_block);
 815 extern void redirect_eh_dispatch_edge (gimple, edge, basic_block);
 816 extern bool tree_could_trap_p (tree);
 817 extern bool operation_could_trap_helper_p (enum tree_code, bool, bool, bool,
 818                                            bool, tree, bool *);
 819 extern bool operation_could_trap_p (enum tree_code, bool, bool, tree);
 820 extern bool stmt_could_throw_p (gimple);
 821 extern bool tree_could_throw_p (tree);
 822 extern bool stmt_can_throw_internal (gimple);
 823 extern bool stmt_can_throw_external (gimple);
 824 extern void add_stmt_to_eh_lp_fn (struct function *, gimple, int);
 825 extern void add_stmt_to_eh_lp (gimple, int);
 826 extern bool remove_stmt_from_eh_lp (gimple);
 827 extern bool remove_stmt_from_eh_lp_fn (struct function *, gimple);
 828 extern int lookup_stmt_eh_lp_fn (struct function *, gimple);
 829 extern int lookup_stmt_eh_lp (gimple);
 830 extern bool maybe_clean_eh_stmt_fn (struct function *, gimple);
 831 extern bool maybe_clean_eh_stmt (gimple);
 832 extern bool maybe_clean_or_replace_eh_stmt (gimple, gimple);
 833 extern bool maybe_duplicate_eh_stmt_fn (struct function *, gimple,
 834                                         struct function *, gimple,
 835                                         struct pointer_map_t *, int);
 836 extern bool maybe_duplicate_eh_stmt (gimple, gimple);
 837 extern bool verify_eh_edges (gimple);
 838 extern bool verify_eh_dispatch_edge (gimple);
 839
 840 /* In tree-ssa-pre.c  */
 841 struct pre_expr_d;
 842 void add_to_value (unsigned int, struct pre_expr_d *);
 843 void debug_value_expressions (unsigned int);
 844 void print_value_expressions (FILE *, unsigned int);
 845
 846 /* In tree-ssa-sink.c  */
 847 bool is_hidden_global_store (gimple);
 848
 849 /* In tree-loop-linear.c  */
 850 extern void linear_transform_loops (void);
 851 extern unsigned perfect_loop_nest_depth (struct loop *);
 852
 853 /* In graphite.c  */
 854 extern void graphite_transform_loops (void);
 855
 856 /* In tree-data-ref.c  */
 857 extern void tree_check_data_deps (void);
 858
 859 /* In tree-ssa-loop-ivopts.c  */
 860 bool expr_invariant_in_loop_p (struct loop *, tree);
 861 bool stmt_invariant_in_loop_p (struct loop *, gimple);
 862 bool multiplier_allowed_in_address_p (HOST_WIDE_INT, enum machine_mode,
 863                                       addr_space_t);
 864 unsigned multiply_by_cost (HOST_WIDE_INT, enum machine_mode, bool);
 865
 866 /* In tree-ssa-threadupdate.c.  */
 867 extern bool thread_through_all_blocks (bool);
 868 extern void register_jump_thread (edge, edge);
 869
 870 /* In gimplify.c  */
 871 tree force_gimple_operand (tree, gimple_seq *, bool, tree);
 872 tree force_gimple_operand_gsi (gimple_stmt_iterator *, tree, bool, tree,
 873                                bool, enum gsi_iterator_update);
 874 tree gimple_fold_indirect_ref (tree);
 875
 876 /* In tree-ssa-live.c */
 877 extern void remove_unused_locals (void);
 878 extern void dump_scope_blocks (FILE *, int);
 879 extern void debug_scope_blocks (int);
 880 extern void debug_scope_block (tree, int);
 881
 882 /* In tree-ssa-address.c  */
 883
 884 /* Description of a memory address.  */
 885
 886 struct mem_address
 887 {
 888   tree symbol, base, index, step, offset;
 889 };
 890
 891 struct affine_tree_combination;
 892 tree create_mem_ref (gimple_stmt_iterator *, tree,
 893                      struct affine_tree_combination *, tree, bool);
 894 rtx addr_for_mem_ref (struct mem_address *, addr_space_t, bool);
 895 void get_address_description (tree, struct mem_address *);
 896 tree maybe_fold_tmr (tree);
 897
 898 unsigned int execute_free_datastructures (void);
 899 unsigned int execute_fixup_cfg (void);
 900
 901 #include "tree-flow-inline.h"
 902
 903 void swap_tree_operands (gimple, tree *, tree *);
 904
 905 int least_common_multiple (int, int);
 906
 907 #endif /* _TREE_FLOW_H  */