gcc/tree-flow.h

   1 /* Data and Control Flow Analysis for Trees.
   2    Copyright (C) 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  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 "tree-gimple.h"
  30 #include "tree-ssa-operands.h"
  31 #include "cgraph.h"
  32 #include "ipa-reference.h"
  33
  34 /* Forward declare structures for the garbage collector GTY markers.  */
  35 #ifndef GCC_BASIC_BLOCK_H
  36 struct edge_def;
  37 typedef struct edge_def *edge;
  38 struct basic_block_def;
  39 typedef struct basic_block_def *basic_block;
  40 #endif
  41
  42 /* Gimple dataflow datastructure. All publicly available fields shall have
  43    gimple_ accessor defined in tree-flow-inline.h, all publicly modifiable
  44    fields should have gimple_set accessor.  */
  45 struct gimple_df GTY(()) {
  46   /* Array of all variables referenced in the function.  */
  47   htab_t GTY((param_is (struct int_tree_map))) referenced_vars;
  48
  49   /* A list of all the noreturn calls passed to modify_stmt.
  50      cleanup_control_flow uses it to detect cases where a mid-block
  51      indirect call has been turned into a noreturn call.  When this
  52      happens, all the instructions after the call are no longer
  53      reachable and must be deleted as dead.  */
  54   VEC(tree,gc) *modified_noreturn_calls;
  55
  56   /* Array of all SSA_NAMEs used in the function.  */
  57   VEC(tree,gc) *ssa_names;
  58
  59   /* Artificial variable used to model the effects of function calls.  */
  60   tree global_var;
  61
  62   /* Artificial variable used to model the effects of nonlocal
  63      variables.  */
  64   tree nonlocal_all;
  65
  66   /* Call clobbered variables in the function.  If bit I is set, then
  67      REFERENCED_VARS (I) is call-clobbered.  */
  68   bitmap call_clobbered_vars;
  69
  70   /* Addressable variables in the function.  If bit I is set, then
  71      REFERENCED_VARS (I) has had its address taken.  Note that
  72      CALL_CLOBBERED_VARS and ADDRESSABLE_VARS are not related.  An
  73      addressable variable is not necessarily call-clobbered (e.g., a
  74      local addressable whose address does not escape) and not all
  75      call-clobbered variables are addressable (e.g., a local static
  76      variable).  */
  77   bitmap addressable_vars;
  78
  79   /* Free list of SSA_NAMEs.  */
  80   tree free_ssanames;
  81
  82   /* Hashtable holding definition for symbol.  If this field is not NULL, it
  83      means that the first reference to this variable in the function is a
  84      USE or a VUSE.  In those cases, the SSA renamer creates an SSA name
  85      for this variable with an empty defining statement.  */
  86   htab_t GTY((param_is (struct int_tree_map))) default_defs;
  87
  88   /* 'true' after aliases have been computed (see compute_may_aliases).  */
  89   unsigned int aliases_computed_p : 1;
  90
  91   /* True if the code is in ssa form.  */
  92   unsigned int in_ssa_p : 1;
  93
  94   struct ssa_operands ssa_operands;
  95 };
  96
  97 /* Accessors for internal use only.  Generic code should use abstraction
  98    provided by tree-flow-inline.h or specific modules.  */
  99 #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
 100 #define SSANAMES(fun) (fun)->gimple_df->ssa_names
 101 #define MODIFIED_NORETURN_CALLS(fun) (fun)->gimple_df->modified_noreturn_calls
 102 #define DEFAULT_DEFS(fun) (fun)->gimple_df->default_defs
 103
 104 typedef struct
 105 {
 106   htab_t htab;
 107   PTR *slot;
 108   PTR *limit;
 109 } htab_iterator;
 110
 111 /* Iterate through the elements of hashtable HTAB, using htab_iterator ITER,
 112    storing each element in RESULT, which is of type TYPE.  */
 113 #define FOR_EACH_HTAB_ELEMENT(HTAB, RESULT, TYPE, ITER) \
 114   for (RESULT = (TYPE) first_htab_element (&(ITER), (HTAB)); \
 115         !end_htab_p (&(ITER)); \
 116         RESULT = (TYPE) next_htab_element (&(ITER)))
 117
 118 /*---------------------------------------------------------------------------
 119                       Attributes for SSA_NAMEs.
 120
 121   NOTE: These structures are stored in struct tree_ssa_name
 122   but are only used by the tree optimizers, so it makes better sense
 123   to declare them here to avoid recompiling unrelated files when
 124   making changes.
 125 ---------------------------------------------------------------------------*/
 126
 127 /* Aliasing information for SSA_NAMEs representing pointer variables.  */
 128 struct ptr_info_def GTY(())
 129 {
 130   /* Nonzero if points-to analysis couldn't determine where this pointer
 131      is pointing to.  */
 132   unsigned int pt_anything : 1;
 133
 134   /* Nonzero if the value of this pointer escapes the current function.  */
 135   unsigned int value_escapes_p : 1;
 136
 137   /* Nonzero if this pointer is dereferenced.  */
 138   unsigned int is_dereferenced : 1;
 139
 140   /* Nonzero if this pointer points to a global variable.  */
 141   unsigned int pt_global_mem : 1;
 142
 143   /* Nonzero if this pointer points to NULL.  */
 144   unsigned int pt_null : 1;
 145
 146   /* Set of variables that this pointer may point to.  */
 147   bitmap pt_vars;
 148
 149   /* If this pointer has been dereferenced, and points-to information is
 150      more precise than type-based aliasing, indirect references to this
 151      pointer will be represented by this memory tag, instead of the type
 152      tag computed by TBAA.  */
 153   tree name_mem_tag;
 154
 155   /* Mask of reasons this pointer's value escapes the function  */
 156   unsigned int escape_mask;
 157 };
 158
 159
 160 /*---------------------------------------------------------------------------
 161                    Tree annotations stored in tree_base.ann
 162 ---------------------------------------------------------------------------*/
 163 enum tree_ann_type { TREE_ANN_COMMON, VAR_ANN, FUNCTION_ANN, STMT_ANN };
 164
 165 struct tree_ann_common_d GTY(())
 166 {
 167   /* Annotation type.  */
 168   enum tree_ann_type type;
 169
 170  /* Auxiliary info specific to a pass.  At all times, this
 171     should either point to valid data or be NULL.  */
 172   PTR GTY ((skip (""))) aux;
 173
 174   /* The value handle for this expression.  Used by GVN-PRE.  */
 175   tree GTY((skip)) value_handle;
 176 };
 177
 178 /* It is advantageous to avoid things like life analysis for variables which
 179    do not need PHI nodes.  This enum describes whether or not a particular
 180    variable may need a PHI node.  */
 181
 182 enum need_phi_state {
 183   /* This is the default.  If we are still in this state after finding
 184      all the definition and use sites, then we will assume the variable
 185      needs PHI nodes.  This is probably an overly conservative assumption.  */
 186   NEED_PHI_STATE_UNKNOWN,
 187
 188   /* This state indicates that we have seen one or more sets of the
 189      variable in a single basic block and that the sets dominate all
 190      uses seen so far.  If after finding all definition and use sites
 191      we are still in this state, then the variable does not need any
 192      PHI nodes.  */
 193   NEED_PHI_STATE_NO,
 194
 195   /* This state indicates that we have either seen multiple definitions of
 196      the variable in multiple blocks, or that we encountered a use in a
 197      block that was not dominated by the block containing the set(s) of
 198      this variable.  This variable is assumed to need PHI nodes.  */
 199   NEED_PHI_STATE_MAYBE
 200 };
 201
 202 struct subvar;
 203 typedef struct subvar *subvar_t;
 204
 205 /* This structure represents a fake sub-variable for a structure field.  */
 206 struct subvar GTY(())
 207 {
 208   /* Fake variable.  */
 209   tree var;
 210
 211   /* Next subvar for this structure.  */
 212   subvar_t next;
 213 };
 214
 215 struct var_ann_d GTY(())
 216 {
 217   struct tree_ann_common_d common;
 218
 219   /* Used by the out of SSA pass to determine whether this variable has
 220      been seen yet or not.  */
 221   unsigned out_of_ssa_tag : 1;
 222
 223   /* Used when building base variable structures in a var_map.  */
 224   unsigned base_var_processed : 1;
 225
 226   /* Nonzero if this variable is in the alias set of another variable.  */
 227   unsigned is_aliased : 1;
 228
 229   /* Nonzero if this variable was used after SSA optimizations were
 230      applied.  We set this when translating out of SSA form.  */
 231   unsigned used : 1;
 232
 233   /* This field indicates whether or not the variable may need PHI nodes.
 234      See the enum's definition for more detailed information about the
 235      states.  */
 236   ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
 237
 238   /* Used during operand processing to determine if this variable is already
 239      in the VUSE list.  */
 240   unsigned in_vuse_list : 1;
 241
 242   /* Used during operand processing to determine if this variable is already
 243      in the VDEF list.  */
 244   unsigned in_vdef_list : 1;
 245
 246   /* True for HEAP and PARM_NOALIAS artificial variables.  */
 247   unsigned is_heapvar : 1;
 248
 249   /* Memory partition tag assigned to this symbol.  */
 250   tree mpt;
 251
 252   /* If this variable is a pointer P that has been dereferenced, this
 253      field is an artificial variable that represents the memory
 254      location *P.  Every other pointer Q that is type-compatible with
 255      P will also have the same memory tag.  If the variable is not a
 256      pointer or if it is never dereferenced, this must be NULL.
 257      FIXME, do we really need this here?  How much slower would it be
 258      to convert to hash table?  */
 259   tree symbol_mem_tag;
 260
 261   /* Variables that may alias this variable.  This may only be set on
 262      memory tags (NAME_MEMORY_TAG or TYPE_MEMORY_TAG).  FIXME, move to
 263      struct tree_memory_tag.  */
 264   VEC(tree, gc) *may_aliases;
 265
 266   /* Used when going out of SSA form to indicate which partition this
 267      variable represents storage for.  */
 268   unsigned partition;
 269
 270   /* Used by var_map for the base index of ssa base variables.  */
 271   unsigned base_index;
 272
 273   /* During into-ssa and the dominator optimizer, this field holds the
 274      current version of this variable (an SSA_NAME).  */
 275   tree current_def;
 276
 277   /* If this variable is a structure, this fields holds a list of
 278      symbols representing each of the fields of the structure.  */
 279   subvar_t subvars;
 280
 281   /* Mask of values saying the reasons why this variable has escaped
 282      the function.  */
 283   unsigned int escape_mask;
 284 };
 285
 286 struct function_ann_d GTY(())
 287 {
 288   struct tree_ann_common_d common;
 289
 290   /* Pointer to the structure that contains the sets of global
 291      variables modified by function calls.  This field is only used
 292      for FUNCTION_DECLs.  */
 293   ipa_reference_vars_info_t GTY ((skip)) reference_vars_info;
 294 };
 295
 296 typedef struct immediate_use_iterator_d
 297 {
 298   /* This is the current use the iterator is processing.  */
 299   ssa_use_operand_t *imm_use;
 300   /* This marks the last use in the list (use node from SSA_NAME)  */
 301   ssa_use_operand_t *end_p;
 302   /* This node is inserted and used to mark the end of the uses for a stmt.  */
 303   ssa_use_operand_t iter_node;
 304   /* This is the next ssa_name to visit.  IMM_USE may get removed before
 305      the next one is traversed to, so it must be cached early.  */
 306   ssa_use_operand_t *next_imm_name;
 307 } imm_use_iterator;
 308
 309
 310 /* Use this iterator when simply looking at stmts.  Adding, deleting or
 311    modifying stmts will cause this iterator to malfunction.  */
 312
 313 #define FOR_EACH_IMM_USE_FAST(DEST, ITER, SSAVAR)                       \
 314   for ((DEST) = first_readonly_imm_use (&(ITER), (SSAVAR));     \
 315        !end_readonly_imm_use_p (&(ITER));                       \
 316        (DEST) = next_readonly_imm_use (&(ITER)))
 317
 318 /* Use this iterator to visit each stmt which has a use of SSAVAR.  */
 319
 320 #define FOR_EACH_IMM_USE_STMT(STMT, ITER, SSAVAR)               \
 321   for ((STMT) = first_imm_use_stmt (&(ITER), (SSAVAR));         \
 322        !end_imm_use_stmt_p (&(ITER));                           \
 323        (STMT) = next_imm_use_stmt (&(ITER)))
 324
 325 /* Use this to terminate the FOR_EACH_IMM_USE_STMT loop early.  Failure to
 326    do so will result in leaving a iterator marker node in the immediate
 327    use list, and nothing good will come from that.   */
 328 #define BREAK_FROM_IMM_USE_STMT(ITER)                           \
 329    {                                                            \
 330      end_imm_use_stmt_traverse (&(ITER));                       \
 331      break;                                                     \
 332    }
 333
 334
 335 /* Use this iterator in combination with FOR_EACH_IMM_USE_STMT to
 336    get access to each occurrence of ssavar on the stmt returned by
 337    that iterator..  for instance:
 338
 339      FOR_EACH_IMM_USE_STMT (stmt, iter, var)
 340        {
 341          FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 342            {
 343              SET_USE (use_p) = blah;
 344            }
 345          update_stmt (stmt);
 346        }                                                         */
 347
 348 #define FOR_EACH_IMM_USE_ON_STMT(DEST, ITER)                    \
 349   for ((DEST) = first_imm_use_on_stmt (&(ITER));                \
 350        !end_imm_use_on_stmt_p (&(ITER));                        \
 351        (DEST) = next_imm_use_on_stmt (&(ITER)))
 352
 353
 354
 355 struct stmt_ann_d GTY(())
 356 {
 357   struct tree_ann_common_d common;
 358
 359   /* Basic block that contains this statement.  */
 360   basic_block bb;
 361
 362   /* Operand cache for stmt.  */
 363   struct stmt_operands_d GTY ((skip (""))) operands;
 364
 365   /* Set of variables that have had their address taken in the statement.  */
 366   bitmap addresses_taken;
 367
 368   /* Nonzero if the statement references memory (at least one of its
 369      expressions contains a non-register operand).  */
 370   unsigned references_memory : 1;
 371
 372   /* Unique identifier for this statement.  These ID's are to be created
 373      by each pass on an as-needed basis in any order convenient for the
 374      pass which needs statement UIDs.  */
 375   unsigned int uid;
 376
 377   /* Nonzero if the statement has been modified (meaning that the operands
 378      need to be scanned again).  */
 379   unsigned modified : 1;
 380
 381   /* Nonzero if the statement makes references to volatile storage.  */
 382   unsigned has_volatile_ops : 1;
 383
 384   /* Nonzero if the statement makes a function call that may clobber global
 385      and local addressable variables.  */
 386   unsigned makes_clobbering_call : 1;
 387 };
 388
 389 union tree_ann_d GTY((desc ("ann_type ((tree_ann_t)&%h)")))
 390 {
 391   struct tree_ann_common_d GTY((tag ("TREE_ANN_COMMON"))) common;
 392   struct var_ann_d GTY((tag ("VAR_ANN"))) vdecl;
 393   struct function_ann_d GTY((tag ("FUNCTION_ANN"))) fdecl;
 394   struct stmt_ann_d GTY((tag ("STMT_ANN"))) stmt;
 395 };
 396
 397 typedef union tree_ann_d *tree_ann_t;
 398 typedef struct var_ann_d *var_ann_t;
 399 typedef struct function_ann_d *function_ann_t;
 400 typedef struct stmt_ann_d *stmt_ann_t;
 401 typedef struct tree_ann_common_d *tree_ann_common_t;
 402
 403 static inline tree_ann_common_t tree_common_ann (tree);
 404 static inline tree_ann_common_t get_tree_common_ann (tree);
 405 static inline var_ann_t var_ann (tree);
 406 static inline var_ann_t get_var_ann (tree);
 407 static inline function_ann_t function_ann (tree);
 408 static inline function_ann_t get_function_ann (tree);
 409 static inline stmt_ann_t stmt_ann (tree);
 410 static inline bool has_stmt_ann (tree);
 411 static inline stmt_ann_t get_stmt_ann (tree);
 412 static inline enum tree_ann_type ann_type (tree_ann_t);
 413 static inline basic_block bb_for_stmt (tree);
 414 extern void set_bb_for_stmt (tree, basic_block);
 415 static inline bool noreturn_call_p (tree);
 416 static inline void update_stmt (tree);
 417 static inline bool stmt_modified_p (tree);
 418 static inline VEC(tree, gc) *may_aliases (tree);
 419 static inline int get_lineno (tree);
 420 static inline const char *get_filename (tree);
 421 static inline bool is_exec_stmt (tree);
 422 static inline bool is_label_stmt (tree);
 423 static inline bitmap addresses_taken (tree);
 424
 425 /*---------------------------------------------------------------------------
 426                   Structure representing predictions in tree level.
 427 ---------------------------------------------------------------------------*/
 428 struct edge_prediction GTY((chain_next ("%h.ep_next")))
 429 {
 430   struct edge_prediction *ep_next;
 431   edge ep_edge;
 432   enum br_predictor ep_predictor;
 433   int ep_probability;
 434 };
 435
 436 /* Accessors for basic block annotations.  */
 437 static inline tree phi_nodes (basic_block);
 438 static inline void set_phi_nodes (basic_block, tree);
 439
 440 /*---------------------------------------------------------------------------
 441                               Global declarations
 442 ---------------------------------------------------------------------------*/
 443 struct int_tree_map GTY(())
 444 {
 445
 446   unsigned int uid;
 447   tree to;
 448 };
 449
 450 extern unsigned int int_tree_map_hash (const void *);
 451 extern int int_tree_map_eq (const void *, const void *);
 452
 453 typedef struct
 454 {
 455   htab_iterator hti;
 456 } referenced_var_iterator;
 457
 458
 459 /* This macro loops over all the referenced vars, one at a time, putting the
 460    current var in VAR.  Note:  You are not allowed to add referenced variables
 461    to the hashtable while using this macro.  Doing so may cause it to behave
 462    erratically.  */
 463
 464 #define FOR_EACH_REFERENCED_VAR(VAR, ITER) \
 465   for ((VAR) = first_referenced_var (&(ITER)); \
 466        !end_referenced_vars_p (&(ITER)); \
 467        (VAR) = next_referenced_var (&(ITER)))
 468
 469
 470 typedef struct
 471 {
 472   int i;
 473 } safe_referenced_var_iterator;
 474
 475 /* This macro loops over all the referenced vars, one at a time, putting the
 476    current var in VAR.  You are allowed to add referenced variables during the
 477    execution of this macro, however, the macro will not iterate over them.  It
 478    requires a temporary vector of trees, VEC, whose lifetime is controlled by
 479    the caller.  The purpose of the vector is to temporarily store the
 480    referenced_variables hashtable so that adding referenced variables does not
 481    affect the hashtable.  */
 482
 483 #define FOR_EACH_REFERENCED_VAR_SAFE(VAR, VEC, ITER) \
 484   for ((ITER).i = 0, fill_referenced_var_vec (&(VEC)); \
 485        VEC_iterate (tree, (VEC), (ITER).i, (VAR)); \
 486        (ITER).i++)
 487
 488 extern tree referenced_var_lookup (unsigned int);
 489 extern bool referenced_var_check_and_insert (tree);
 490 #define num_referenced_vars htab_elements (gimple_referenced_vars (cfun))
 491 #define referenced_var(i) referenced_var_lookup (i)
 492
 493 #define num_ssa_names (VEC_length (tree, cfun->gimple_df->ssa_names))
 494 #define ssa_name(i) (VEC_index (tree, cfun->gimple_df->ssa_names, (i)))
 495
 496 /* Macros for showing usage statistics.  */
 497 #define SCALE(x) ((unsigned long) ((x) < 1024*10        \
 498                   ? (x)                                 \
 499                   : ((x) < 1024*1024*10                 \
 500                      ? (x) / 1024                       \
 501                      : (x) / (1024*1024))))
 502
 503 #define LABEL(x) ((x) < 1024*10 ? 'b' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 504
 505 #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
 506
 507 /*---------------------------------------------------------------------------
 508                               Block iterators
 509 ---------------------------------------------------------------------------*/
 510
 511 typedef struct {
 512   tree_stmt_iterator tsi;
 513   basic_block bb;
 514 } block_stmt_iterator;
 515
 516 static inline block_stmt_iterator bsi_start (basic_block);
 517 static inline block_stmt_iterator bsi_last (basic_block);
 518 static inline block_stmt_iterator bsi_after_labels (basic_block);
 519 block_stmt_iterator bsi_for_stmt (tree);
 520 static inline bool bsi_end_p (block_stmt_iterator);
 521 static inline void bsi_next (block_stmt_iterator *);
 522 static inline void bsi_prev (block_stmt_iterator *);
 523 static inline tree bsi_stmt (block_stmt_iterator);
 524 static inline tree * bsi_stmt_ptr (block_stmt_iterator);
 525
 526 extern void bsi_remove (block_stmt_iterator *, bool);
 527 extern void bsi_move_before (block_stmt_iterator *, block_stmt_iterator *);
 528 extern void bsi_move_after (block_stmt_iterator *, block_stmt_iterator *);
 529 extern void bsi_move_to_bb_end (block_stmt_iterator *, basic_block);
 530
 531 enum bsi_iterator_update
 532 {
 533   /* Note that these are intentionally in the same order as TSI_FOO.  They
 534      mean exactly the same as their TSI_* counterparts.  */
 535   BSI_NEW_STMT,
 536   BSI_SAME_STMT,
 537   BSI_CHAIN_START,
 538   BSI_CHAIN_END,
 539   BSI_CONTINUE_LINKING
 540 };
 541
 542 extern void bsi_insert_before (block_stmt_iterator *, tree,
 543                                enum bsi_iterator_update);
 544 extern void bsi_insert_after (block_stmt_iterator *, tree,
 545                               enum bsi_iterator_update);
 546
 547 extern void bsi_replace (const block_stmt_iterator *, tree, bool);
 548
 549 /*---------------------------------------------------------------------------
 550                               OpenMP Region Tree
 551 ---------------------------------------------------------------------------*/
 552
 553 /* Parallel region information.  Every parallel and workshare
 554    directive is enclosed between two markers, the OMP_* directive
 555    and a corresponding OMP_RETURN statement.  */
 556
 557 struct omp_region
 558 {
 559   /* The enclosing region.  */
 560   struct omp_region *outer;
 561
 562   /* First child region.  */
 563   struct omp_region *inner;
 564
 565   /* Next peer region.  */
 566   struct omp_region *next;
 567
 568   /* Block containing the omp directive as its last stmt.  */
 569   basic_block entry;
 570
 571   /* Block containing the OMP_RETURN as its last stmt.  */
 572   basic_block exit;
 573
 574   /* Block containing the OMP_CONTINUE as its last stmt.  */
 575   basic_block cont;
 576
 577   /* If this is a combined parallel+workshare region, this is a list
 578      of additional arguments needed by the combined parallel+workshare
 579      library call.  */
 580   tree ws_args;
 581
 582   /* The code for the omp directive of this region.  */
 583   enum tree_code type;
 584
 585   /* Schedule kind, only used for OMP_FOR type regions.  */
 586   enum omp_clause_schedule_kind sched_kind;
 587
 588   /* True if this is a combined parallel+workshare region.  */
 589   bool is_combined_parallel;
 590 };
 591
 592 extern struct omp_region *root_omp_region;
 593 extern struct omp_region *new_omp_region (basic_block, enum tree_code,
 594                                           struct omp_region *);
 595 extern void free_omp_regions (void);
 596
 597 /*---------------------------------------------------------------------------
 598                               Function prototypes
 599 ---------------------------------------------------------------------------*/
 600 /* In tree-cfg.c  */
 601
 602 /* Location to track pending stmt for edge insertion.  */
 603 #define PENDING_STMT(e) ((e)->insns.t)
 604
 605 extern void delete_tree_cfg_annotations (void);
 606 extern void disband_implicit_edges (void);
 607 extern bool stmt_ends_bb_p (tree);
 608 extern bool is_ctrl_stmt (tree);
 609 extern bool is_ctrl_altering_stmt (tree);
 610 extern bool computed_goto_p (tree);
 611 extern bool simple_goto_p (tree);
 612 extern bool tree_can_make_abnormal_goto (tree);
 613 extern basic_block single_noncomplex_succ (basic_block bb);
 614 extern void tree_dump_bb (basic_block, FILE *, int);
 615 extern void debug_tree_bb (basic_block);
 616 extern basic_block debug_tree_bb_n (int);
 617 extern void dump_tree_cfg (FILE *, int);
 618 extern void debug_tree_cfg (int);
 619 extern void dump_cfg_stats (FILE *);
 620 extern void debug_cfg_stats (void);
 621 extern void debug_loop_ir (void);
 622 extern void print_loop_ir (FILE *);
 623 extern void cleanup_dead_labels (void);
 624 extern void group_case_labels (void);
 625 extern tree first_stmt (basic_block);
 626 extern tree last_stmt (basic_block);
 627 extern tree *last_stmt_ptr (basic_block);
 628 extern tree last_and_only_stmt (basic_block);
 629 extern edge find_taken_edge (basic_block, tree);
 630 extern basic_block label_to_block_fn (struct function *, tree);
 631 #define label_to_block(t) (label_to_block_fn (cfun, t))
 632 extern void bsi_insert_on_edge (edge, tree);
 633 extern basic_block bsi_insert_on_edge_immediate (edge, tree);
 634 extern void bsi_commit_one_edge_insert (edge, basic_block *);
 635 extern void bsi_commit_edge_inserts (void);
 636 extern void notice_special_calls (tree);
 637 extern void clear_special_calls (void);
 638 extern void verify_stmts (void);
 639 extern tree tree_block_label (basic_block);
 640 extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
 641 extern bool tree_duplicate_sese_region (edge, edge, basic_block *, unsigned,
 642                                         basic_block *);
 643 extern void add_phi_args_after_copy_bb (basic_block);
 644 extern void add_phi_args_after_copy (basic_block *, unsigned);
 645 extern bool tree_purge_dead_abnormal_call_edges (basic_block);
 646 extern bool tree_purge_dead_eh_edges (basic_block);
 647 extern bool tree_purge_all_dead_eh_edges (bitmap);
 648 extern tree gimplify_val (block_stmt_iterator *, tree, tree);
 649 extern tree gimplify_build1 (block_stmt_iterator *, enum tree_code,
 650                              tree, tree);
 651 extern tree gimplify_build2 (block_stmt_iterator *, enum tree_code,
 652                              tree, tree, tree);
 653 extern tree gimplify_build3 (block_stmt_iterator *, enum tree_code,
 654                              tree, tree, tree, tree);
 655 extern void init_empty_tree_cfg (void);
 656 extern void fold_cond_expr_cond (void);
 657 extern void make_abnormal_goto_edges (basic_block, bool);
 658 extern void replace_uses_by (tree, tree);
 659 extern void start_recording_case_labels (void);
 660 extern void end_recording_case_labels (void);
 661 extern basic_block move_sese_region_to_fn (struct function *, basic_block,
 662                                            basic_block);
 663
 664 /* In tree-cfgcleanup.c  */
 665 extern bool cleanup_tree_cfg (void);
 666 extern void cleanup_tree_cfg_loop (void);
 667
 668 /* In tree-pretty-print.c.  */
 669 extern void dump_generic_bb (FILE *, basic_block, int, int);
 670
 671 /* In tree-dfa.c  */
 672 extern var_ann_t create_var_ann (tree);
 673 extern function_ann_t create_function_ann (tree);
 674 extern stmt_ann_t create_stmt_ann (tree);
 675 extern tree_ann_common_t create_tree_common_ann (tree);
 676 extern void dump_dfa_stats (FILE *);
 677 extern void debug_dfa_stats (void);
 678 extern void debug_referenced_vars (void);
 679 extern void dump_referenced_vars (FILE *);
 680 extern void dump_variable (FILE *, tree);
 681 extern void debug_variable (tree);
 682 extern void dump_subvars_for (FILE *, tree);
 683 extern void debug_subvars_for (tree);
 684 extern tree get_virtual_var (tree);
 685 extern void add_referenced_var (tree);
 686 extern void mark_symbols_for_renaming (tree);
 687 extern void find_new_referenced_vars (tree *);
 688
 689 extern tree make_rename_temp (tree, const char *);
 690 extern void set_default_def (tree, tree);
 691 extern tree gimple_default_def (struct function *, tree);
 692
 693 /* In tree-phinodes.c  */
 694 extern void reserve_phi_args_for_new_edge (basic_block);
 695 extern tree create_phi_node (tree, basic_block);
 696 extern void add_phi_arg (tree, tree, edge);
 697 extern void remove_phi_args (edge);
 698 extern void remove_phi_node (tree, tree, bool);
 699 extern tree phi_reverse (tree);
 700
 701 /* In gimple-low.c  */
 702 extern void record_vars_into (tree, tree);
 703 extern void record_vars (tree);
 704 extern bool block_may_fallthru (tree);
 705
 706 /* In tree-ssa-alias.c  */
 707 extern void dump_may_aliases_for (FILE *, tree);
 708 extern void debug_may_aliases_for (tree);
 709 extern void dump_alias_info (FILE *);
 710 extern void debug_alias_info (void);
 711 extern void dump_points_to_info (FILE *);
 712 extern void debug_points_to_info (void);
 713 extern void dump_points_to_info_for (FILE *, tree);
 714 extern void debug_points_to_info_for (tree);
 715 extern bool may_be_aliased (tree);
 716 extern bool is_aliased_with (tree, tree);
 717 extern struct ptr_info_def *get_ptr_info (tree);
 718 extern void new_type_alias (tree, tree, tree);
 719 extern void count_uses_and_derefs (tree, tree, unsigned *, unsigned *, bool *);
 720 static inline subvar_t get_subvars_for_var (tree);
 721 static inline tree get_subvar_at (tree, unsigned HOST_WIDE_INT);
 722 static inline bool ref_contains_array_ref (tree);
 723 static inline bool array_ref_contains_indirect_ref (tree);
 724 extern tree get_ref_base_and_extent (tree, HOST_WIDE_INT *,
 725                                      HOST_WIDE_INT *, HOST_WIDE_INT *);
 726 static inline bool var_can_have_subvars (tree);
 727 static inline bool overlap_subvar (unsigned HOST_WIDE_INT,
 728                                    unsigned HOST_WIDE_INT,
 729                                    tree, bool *);
 730 extern tree create_tag_raw (enum tree_code, tree, const char *);
 731
 732 /* Call-back function for walk_use_def_chains().  At each reaching
 733    definition, a function with this prototype is called.  */
 734 typedef bool (*walk_use_def_chains_fn) (tree, tree, void *);
 735
 736
 737 /* In tree-ssa.c  */
 738 extern void init_tree_ssa (void);
 739 extern edge ssa_redirect_edge (edge, basic_block);
 740 extern void flush_pending_stmts (edge);
 741 extern bool tree_ssa_useless_type_conversion (tree);
 742 extern bool tree_ssa_useless_type_conversion_1 (tree, tree);
 743 extern void verify_ssa (bool);
 744 extern void delete_tree_ssa (void);
 745 extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *, bool);
 746 extern bool stmt_references_memory_p (tree);
 747
 748 /* In tree-into-ssa.c  */
 749 void update_ssa (unsigned);
 750 void delete_update_ssa (void);
 751 void register_new_name_mapping (tree, tree);
 752 tree create_new_def_for (tree, tree, def_operand_p);
 753 bool need_ssa_update_p (void);
 754 bool name_mappings_registered_p (void);
 755 bool name_registered_for_update_p (tree);
 756 bitmap ssa_names_to_replace (void);
 757 void release_ssa_name_after_update_ssa (tree);
 758 void compute_global_livein (bitmap, bitmap);
 759 tree duplicate_ssa_name (tree, tree);
 760 void mark_sym_for_renaming (tree);
 761 void mark_set_for_renaming (bitmap);
 762 tree get_current_def (tree);
 763 void set_current_def (tree, tree);
 764
 765 /* In tree-ssa-ccp.c  */
 766 bool fold_stmt (tree *);
 767 bool fold_stmt_inplace (tree);
 768 tree widen_bitfield (tree, tree, tree);
 769
 770 /* In tree-vrp.c  */
 771 tree vrp_evaluate_conditional (tree, bool);
 772 void simplify_stmt_using_ranges (tree);
 773
 774 /* In tree-ssa-dom.c  */
 775 extern void dump_dominator_optimization_stats (FILE *);
 776 extern void debug_dominator_optimization_stats (void);
 777 int loop_depth_of_name (tree);
 778
 779 /* In tree-ssa-copy.c  */
 780 extern void merge_alias_info (tree, tree);
 781 extern void propagate_value (use_operand_p, tree);
 782 extern void propagate_tree_value (tree *, tree);
 783 extern void replace_exp (use_operand_p, tree);
 784 extern bool may_propagate_copy (tree, tree);
 785 extern bool may_propagate_copy_into_asm (tree);
 786
 787 /* Affine iv.  */
 788
 789 typedef struct
 790 {
 791   /* Iv = BASE + STEP * i.  */
 792   tree base, step;
 793
 794   /* True if this iv does not overflow.  */
 795   bool no_overflow;
 796 } affine_iv;
 797
 798 /* Description of number of iterations of a loop.  All the expressions inside
 799    the structure can be evaluated at the end of the loop's preheader
 800    (and due to ssa form, also anywhere inside the body of the loop).  */
 801
 802 struct tree_niter_desc
 803 {
 804   tree assumptions;     /* The boolean expression.  If this expression evaluates
 805                            to false, then the other fields in this structure
 806                            should not be used; there is no guarantee that they
 807                            will be correct.  */
 808   tree may_be_zero;     /* The boolean expression.  If it evaluates to true,
 809                            the loop will exit in the first iteration (i.e.
 810                            its latch will not be executed), even if the niter
 811                            field says otherwise.  */
 812   tree niter;           /* The expression giving the number of iterations of
 813                            a loop (provided that assumptions == true and
 814                            may_be_zero == false), more precisely the number
 815                            of executions of the latch of the loop.  */
 816   tree additional_info; /* The boolean expression.  Sometimes we use additional
 817                            knowledge to simplify the other expressions
 818                            contained in this structure (for example the
 819                            knowledge about value ranges of operands on entry to
 820                            the loop).  If this is a case, conjunction of such
 821                            condition is stored in this field, so that we do not
 822                            lose the information: for example if may_be_zero
 823                            is (n <= 0) and niter is (unsigned) n, we know
 824                            that the number of iterations is at most
 825                            MAX_SIGNED_INT.  However if the (n <= 0) assumption
 826                            is eliminated (by looking at the guard on entry of
 827                            the loop), then the information would be lost.  */
 828
 829   /* The simplified shape of the exit condition.  The loop exits if
 830      CONTROL CMP BOUND is false, where CMP is one of NE_EXPR,
 831      LT_EXPR, or GT_EXPR, and step of CONTROL is positive if CMP is
 832      LE_EXPR and negative if CMP is GE_EXPR.  This information is used
 833      by loop unrolling.  */
 834   affine_iv control;
 835   tree bound;
 836   enum tree_code cmp;
 837 };
 838
 839 /* In tree-vectorizer.c */
 840 unsigned vectorize_loops (void);
 841 extern bool vect_can_force_dr_alignment_p (tree, unsigned int);
 842 extern tree get_vectype_for_scalar_type (tree);
 843
 844 /* In tree-ssa-phiopt.c */
 845 bool empty_block_p (basic_block);
 846
 847 /* In tree-ssa-loop*.c  */
 848
 849 void tree_ssa_lim (void);
 850 unsigned int tree_ssa_unswitch_loops (void);
 851 unsigned int canonicalize_induction_variables (void);
 852 unsigned int tree_unroll_loops_completely (bool);
 853 unsigned int tree_ssa_prefetch_arrays (void);
 854 unsigned int remove_empty_loops (void);
 855 void tree_ssa_iv_optimize (void);
 856
 857 bool number_of_iterations_exit (struct loop *, edge,
 858                                 struct tree_niter_desc *niter, bool);
 859 tree find_loop_niter (struct loop *, edge *);
 860 tree loop_niter_by_eval (struct loop *, edge);
 861 tree find_loop_niter_by_eval (struct loop *, edge *);
 862 void estimate_numbers_of_iterations (void);
 863 bool scev_probably_wraps_p (tree, tree, tree, struct loop *, bool);
 864 bool convert_affine_scev (struct loop *, tree, tree *, tree *, tree, bool);
 865
 866 bool nowrap_type_p (tree);
 867 enum ev_direction {EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN};
 868 enum ev_direction scev_direction (tree);
 869
 870 void free_numbers_of_iterations_estimates (void);
 871 void free_numbers_of_iterations_estimates_loop (struct loop *);
 872 void rewrite_into_loop_closed_ssa (bitmap, unsigned);
 873 void verify_loop_closed_ssa (void);
 874 bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
 875 void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool,
 876                 tree *, tree *);
 877 void split_loop_exit_edge (edge);
 878 unsigned force_expr_to_var_cost (tree);
 879 void standard_iv_increment_position (struct loop *, block_stmt_iterator *,
 880                                      bool *);
 881 basic_block ip_end_pos (struct loop *);
 882 basic_block ip_normal_pos (struct loop *);
 883 bool tree_duplicate_loop_to_header_edge (struct loop *, edge,
 884                                          unsigned int, sbitmap,
 885                                          edge, edge *,
 886                                          unsigned int *, int);
 887 struct loop *tree_ssa_loop_version (struct loop *, tree,
 888                                     basic_block *);
 889 tree expand_simple_operations (tree);
 890 void substitute_in_loop_info (struct loop *, tree, tree);
 891 edge single_dom_exit (struct loop *);
 892 bool can_unroll_loop_p (struct loop *loop, unsigned factor,
 893                         struct tree_niter_desc *niter);
 894 void tree_unroll_loop (struct loop *, unsigned,
 895                        edge, struct tree_niter_desc *);
 896 bool contains_abnormal_ssa_name_p (tree);
 897
 898 /* In tree-ssa-threadedge.c */
 899 extern bool potentially_threadable_block (basic_block);
 900 extern void thread_across_edge (tree, edge, bool,
 901                                 VEC(tree, heap) **, tree (*) (tree));
 902
 903 /* In tree-ssa-loop-im.c  */
 904 /* The possibilities of statement movement.  */
 905
 906 enum move_pos
 907   {
 908     MOVE_IMPOSSIBLE,            /* No movement -- side effect expression.  */
 909     MOVE_PRESERVE_EXECUTION,    /* Must not cause the non-executed statement
 910                                    become executed -- memory accesses, ... */
 911     MOVE_POSSIBLE               /* Unlimited movement.  */
 912   };
 913 extern enum move_pos movement_possibility (tree);
 914
 915 /* The reasons a variable may escape a function.  */
 916 enum escape_type
 917 {
 918   NO_ESCAPE = 0,                        /* Doesn't escape.  */
 919   ESCAPE_STORED_IN_GLOBAL = 1 << 1,
 920   ESCAPE_TO_ASM = 1 << 2,               /* Passed by address to an assembly
 921                                            statement.  */
 922   ESCAPE_TO_CALL = 1 << 3,              /* Escapes to a function call.  */
 923   ESCAPE_BAD_CAST = 1 << 4,             /* Cast from pointer to integer */
 924   ESCAPE_TO_RETURN = 1 << 5,            /* Returned from function.  */
 925   ESCAPE_TO_PURE_CONST = 1 << 6,        /* Escapes to a pure or constant
 926                                            function call.  */
 927   ESCAPE_IS_GLOBAL = 1 << 7,            /* Is a global variable.  */
 928   ESCAPE_IS_PARM = 1 << 8,              /* Is an incoming function argument.  */
 929   ESCAPE_UNKNOWN = 1 << 9               /* We believe it escapes for
 930                                            some reason not enumerated
 931                                            above.  */
 932 };
 933
 934 /* In tree-flow-inline.h  */
 935 static inline bool is_call_clobbered (tree);
 936 static inline void mark_call_clobbered (tree, unsigned int);
 937 static inline void set_is_used (tree);
 938 static inline bool unmodifiable_var_p (tree);
 939
 940 /* In tree-eh.c  */
 941 extern void make_eh_edges (tree);
 942 extern bool tree_could_trap_p (tree);
 943 extern bool tree_could_throw_p (tree);
 944 extern bool tree_can_throw_internal (tree);
 945 extern bool tree_can_throw_external (tree);
 946 extern int lookup_stmt_eh_region (tree);
 947 extern void add_stmt_to_eh_region (tree, int);
 948 extern bool remove_stmt_from_eh_region (tree);
 949 extern bool maybe_clean_or_replace_eh_stmt (tree, tree);
 950
 951 /* In tree-ssa-pre.c  */
 952 void add_to_value (tree, tree);
 953 void debug_value_expressions (tree);
 954 void print_value_expressions (FILE *, tree);
 955
 956
 957 /* In tree-vn.c  */
 958 bool expressions_equal_p (tree, tree);
 959 static inline tree get_value_handle (tree);
 960 hashval_t vn_compute (tree, hashval_t);
 961 void sort_vuses (VEC (tree, gc) *);
 962 tree vn_lookup_or_add (tree, tree);
 963 tree vn_lookup_or_add_with_vuses (tree, VEC (tree, gc) *);
 964 void vn_add (tree, tree);
 965 void vn_add_with_vuses (tree, tree, VEC (tree, gc) *);
 966 tree vn_lookup (tree, tree);
 967 tree vn_lookup_with_vuses (tree, VEC (tree, gc) *);
 968 void vn_init (void);
 969 void vn_delete (void);
 970
 971 /* In tree-ssa-sink.c  */
 972 bool is_hidden_global_store (tree);
 973
 974 /* In tree-sra.c  */
 975 void insert_edge_copies (tree, basic_block);
 976 void sra_insert_before (block_stmt_iterator *, tree);
 977 void sra_insert_after (block_stmt_iterator *, tree);
 978 void sra_init_cache (void);
 979 bool sra_type_can_be_decomposed_p (tree);
 980
 981 /* In tree-loop-linear.c  */
 982 extern void linear_transform_loops (void);
 983
 984 /* In tree-ssa-loop-ivopts.c  */
 985 bool expr_invariant_in_loop_p (struct loop *, tree);
 986 bool multiplier_allowed_in_address_p (HOST_WIDE_INT, enum machine_mode);
 987 unsigned multiply_by_cost (HOST_WIDE_INT, enum machine_mode);
 988
 989 /* In tree-ssa-threadupdate.c.  */
 990 extern bool thread_through_all_blocks (void);
 991 extern void register_jump_thread (edge, edge);
 992
 993 /* In gimplify.c  */
 994 tree force_gimple_operand (tree, tree *, bool, tree);
 995 tree force_gimple_operand_bsi (block_stmt_iterator *, tree, bool, tree);
 996
 997 /* In tree-ssa-structalias.c */
 998 bool find_what_p_points_to (tree);
 999
1000 /* In tree-ssa-live.c */
1001 extern void remove_unused_locals (void);
1002
1003 /* In tree-ssa-address.c  */
1004
1005 /* Description of a memory address.  */
1006
1007 struct mem_address
1008 {
1009   tree symbol, base, index, step, offset;
1010 };
1011
1012 struct affine_tree_combination;
1013 tree create_mem_ref (block_stmt_iterator *, tree,
1014                      struct affine_tree_combination *);
1015 rtx addr_for_mem_ref (struct mem_address *, bool);
1016 void get_address_description (tree, struct mem_address *);
1017 tree maybe_fold_tmr (tree);
1018
1019 /* This structure is simply used during pushing fields onto the fieldstack
1020    to track the offset of the field, since bitpos_of_field gives it relative
1021    to its immediate containing type, and we want it relative to the ultimate
1022    containing object.  */
1023
1024 struct fieldoff
1025 {
1026   tree type;
1027   tree size;
1028   tree decl;
1029   HOST_WIDE_INT offset;
1030 };
1031 typedef struct fieldoff fieldoff_s;
1032
1033 DEF_VEC_O(fieldoff_s);
1034 DEF_VEC_ALLOC_O(fieldoff_s,heap);
1035 int push_fields_onto_fieldstack (tree, VEC(fieldoff_s,heap) **,
1036                                  HOST_WIDE_INT, bool *);
1037 void sort_fieldstack (VEC(fieldoff_s,heap) *);
1038
1039 void init_alias_heapvars (void);
1040 void delete_alias_heapvars (void);
1041
1042 #include "tree-flow-inline.h"
1043
1044 void swap_tree_operands (tree, tree *, tree *);
1045
1046 int least_common_multiple (int, int);
1047
1048 #endif /* _TREE_FLOW_H  */