Merge tree-ssa-20020619-branch into mainline.

From-SVN: r81764

1 files changed, 596 insertions, 0 deletions

diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
new file mode 100644
index 0000000..853eb1a
--- /dev/null
+++ b/gcc/tree-flow.h
@@ -0,0 +1,596 @@
+/* Data and Control Flow Analysis for Trees.
+   Copyright (C) 2001, 2003, 2004 Free Software Foundation, Inc.
+   Contributed by Diego Novillo <dnovillo@redhat.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+
+#ifndef _TREE_FLOW_H
+#define _TREE_FLOW_H 1
+
+#include "bitmap.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "hashtab.h"
+#include "tree-simple.h"
+#include "tree-ssa-operands.h"
+
+/* Forward declare structures for the garbage collector GTY markers.  */
+#ifndef GCC_BASIC_BLOCK_H
+struct edge_def;
+typedef struct edge_def *edge;
+struct basic_block_def;
+typedef struct basic_block_def *basic_block;
+#endif
+
+/*---------------------------------------------------------------------------
+		   Tree annotations stored in tree_common.ann
+---------------------------------------------------------------------------*/
+enum tree_ann_type { TREE_ANN_COMMON, VAR_ANN, STMT_ANN, SSA_NAME_ANN };
+
+struct tree_ann_common_d GTY(())
+{
+  /* Annotation type.  */
+  enum tree_ann_type type;
+};
+
+/* It is advantageous to avoid things like life analysis for variables which
+   do not need PHI nodes.  This enum describes whether or not a particular
+   variable may need a PHI node.  */
+
+enum need_phi_state {
+  /* This is the default.  If we are still in this state after finding
+     all the definition and use sites, then we will assume the variable
+     needs PHI nodes.  This is probably an overly conservative assumption.  */
+  NEED_PHI_STATE_UNKNOWN,
+
+  /* This state indicates that we have seen one or more sets of the 
+     variable in a single basic block and that the sets dominate all
+     uses seen so far.  If after finding all definition and use sites
+     we are still in this state, then the variable does not need any
+     PHI nodes.  */
+  NEED_PHI_STATE_NO,
+
+  /* This state indicates that we have either seen multiple definitions of
+     the variable in multiple blocks, or that we encountered a use in a
+     block that was not dominated by the block containing the set(s) of
+     this variable.  This variable is assumed to need PHI nodes.  */
+  NEED_PHI_STATE_MAYBE
+};
+
+
+/* When computing aliasing information, we represent the memory pointed-to
+   by pointers with artificial variables called "memory tags" (MT).  There
+   are two kinds of tags: type and name.  Type tags (TMT) are used in
+   type-based alias analysis, they represent all the pointed-to locations
+   and variables of the same alias set class.  Name tags (NMT) are used in
+   flow-sensitive points-to alias analysis, they represent the variables
+   and memory locations pointed-to by a specific SSA_NAME pointer.  */
+enum mem_tag_kind {
+  /* This variable is not a memory tag.  */
+  NOT_A_TAG,
+
+  /* This variable is a type memory tag (TMT).  */
+  TYPE_TAG,
+
+  /* This variable is a name memory tag (NMT).  */
+  NAME_TAG
+};
+
+struct var_ann_d GTY(())
+{
+  struct tree_ann_common_d common;
+
+  /* Nonzero if this variable has uses which may not appear
+     in the IL.  This can happen in the following cases:
+
+       1. If the variable is used in a variable length
+          array declaration.
+
+	2. If the variable is the return value in a C++
+	   function where the named return value optimization
+	   has been performed.  */
+  unsigned has_hidden_use : 1;
+
+  /* Used by the out of SSA pass to determine whether this variable has
+     been seen yet or not.  */
+  unsigned out_of_ssa_tag : 1;
+
+  /* Used when building root_var structures in tree_ssa_live.[ch].  */
+  unsigned root_var_processed : 1;
+
+  /* If nonzero, this variable is a memory tag.  */
+  ENUM_BITFIELD (mem_tag_kind) mem_tag_kind : 2;
+
+  /* Nonzero if this variable is an alias tag that represents references to
+     other variables (i.e., this variable appears in the MAY_ALIASES array
+     of other variables).  */
+  unsigned is_alias_tag : 1;
+
+  /* Nonzero if this variable was used after SSA optimizations were
+     applied.  We set this when translating out of SSA form.  */
+  unsigned used : 1;
+
+  /* This field indicates whether or not the variable may need PHI nodes.
+     See the enum's definition for more detailed information about the
+     states.  */
+  ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
+
+  /* An artificial variable representing the memory location pointed-to by
+     all the pointers that TBAA (type-based alias analysis) considers
+     to be aliased.  If the variable is not a pointer or if it is never
+     dereferenced, this must be NULL.  */
+  tree type_mem_tag;
+
+  /* Variables that may alias this variable.  */
+  varray_type may_aliases;
+
+  /* Unique ID of this variable.  */
+  size_t uid;
+
+  /* Used when going out of SSA form to indicate which partition this
+     variable represents storage for.  */
+  unsigned partition;
+
+  /* Used by the root-var object in tree-ssa-live.[ch].  */
+  unsigned root_index;
+
+  /* Default definition for this symbol.  If this field is not NULL, it
+     means that the first reference to this variable in the function is a
+     USE or a VUSE.  In those cases, the SSA renamer creates an SSA name
+     for this variable with an empty defining statement.  */
+  tree default_def;
+
+  /* During into-ssa and the dominator optimizer, this field holds the
+     current version of this variable (an SSA_NAME). 
+
+     This was previously two varrays (one in into-ssa the other in the
+     dominator optimizer).  That is wasteful, particularly since the
+     dominator optimizer calls into-ssa resulting in having two varrays
+     live at the same time and this can happen for each call to the
+     dominator optimizer.  */
+  tree current_def;
+};
+
+
+struct dataflow_d GTY(())
+{
+  /* Immediate uses.  This is a list of all the statements and PHI nodes
+     that are immediately reached by the definitions made in this
+     statement.  */
+  varray_type immediate_uses;
+
+  /* Use this array for very small numbers of uses instead of the varray.  */
+  tree uses[2];
+
+  /* Reached uses.  This is a list of all the possible program statements
+     that may be reached directly or indirectly by definitions made in this
+     statement.  Notice that this is a superset of IMMEDIATE_USES.
+     For instance, given the following piece of code:
+
+	    1	a1 = 10;
+	    2	if (a1 > 3)
+	    3	  a2 = a1 + 5;
+	    4	a3 = PHI (a1, a2)
+	    5	b1 = a3 - 2;
+
+     IMMEDIATE_USES for statement #1 are all those statements that use a1
+     directly (i.e., #2, #3 and #4).  REACHED_USES for statement #1 also
+     includes statement #5 because 'a1' could reach 'a3' via the PHI node
+     at statement #4.  The set of REACHED_USES is then the transitive
+     closure over all the PHI nodes in the IMMEDIATE_USES set.  */
+
+  /* Reaching definitions.  Similarly to REACHED_USES, the set
+     REACHING_DEFS is the set of all the statements that make definitions
+     that may reach this statement.  Notice that we don't need to have a
+     similar entry for immediate definitions, as these are represented by
+     the SSA_NAME nodes themselves (each SSA_NAME node contains a pointer
+     to the statement that makes that definition).  */
+};
+
+typedef struct dataflow_d *dataflow_t;
+
+
+struct stmt_ann_d GTY(())
+{
+  struct tree_ann_common_d common;
+
+  /* Nonzero if the statement has been modified (meaning that the operands
+     need to be scanned again).  */
+  unsigned modified : 1;
+
+  /* Nonzero if the statement is in the CCP worklist and has not been
+     "cancelled".  If we ever need to use this bit outside CCP, then
+     it should be renamed.  */
+  unsigned in_ccp_worklist: 1;
+
+  /* Nonzero if the statement makes aliased loads.  */
+  unsigned makes_aliased_loads : 1;
+
+  /* Nonzero if the statement makes aliased stores.  */
+  unsigned makes_aliased_stores : 1;
+
+  /* Nonzero if the statement makes references to volatile storage.  */
+  unsigned has_volatile_ops : 1;
+
+  /* Nonzero if the statement makes a function call that may clobber global
+     and local addressable variables.  */
+  unsigned makes_clobbering_call : 1;
+
+  /* Basic block that contains this statement.  */
+  basic_block GTY ((skip (""))) bb;
+
+  /* Statement operands.  */
+  struct def_optype_d * GTY (()) def_ops;
+  struct use_optype_d * GTY (()) use_ops;
+
+  /* Virtual operands (VDEF and VUSE).  */
+  struct vdef_optype_d * GTY (()) vdef_ops;
+  struct vuse_optype_d * GTY (()) vuse_ops;
+
+  /* Dataflow information.  */
+  dataflow_t df;
+
+  /* Set of variables that have had their address taken in the statement.  */
+  bitmap addresses_taken;
+
+  /* Unique identifier for this statement.  These ID's are to be created
+     by each pass on an as-needed basis in any order convenient for the
+     pass which needs statement UIDs.  */
+  unsigned int uid;
+};
+
+
+struct ssa_name_ann_d GTY(())
+{
+  struct tree_ann_common_d common;
+
+  /* Nonzero if points-to analysis couldn't determine where this pointer
+     is pointing to.  */
+  unsigned int pt_anything : 1;
+
+  /* Nonzero if this pointer is the result of a call to malloc.  */
+  unsigned int pt_malloc : 1;
+
+  /* Nonzero if the value of this pointer escapes the current function.  */
+  unsigned int value_escapes_p : 1;
+
+  /* Set of variables that this pointer may point to.  */
+  bitmap pt_vars;
+
+  /* If this pointer has been dereferenced, and points-to information is
+     more precise than type-based aliasing, indirect references to this
+     pointer will be represented by this memory tag, instead of the type
+     tag computed by TBAA.  */
+  tree name_mem_tag;
+};
+
+
+union tree_ann_d GTY((desc ("ann_type ((tree_ann)&%h)")))
+{
+  struct tree_ann_common_d GTY((tag ("TREE_ANN_COMMON"))) common;
+  struct var_ann_d GTY((tag ("VAR_ANN"))) decl;
+  struct stmt_ann_d GTY((tag ("STMT_ANN"))) stmt;
+  struct ssa_name_ann_d GTY((tag ("SSA_NAME_ANN"))) ssa_name;
+};
+
+typedef union tree_ann_d *tree_ann;
+typedef struct var_ann_d *var_ann_t;
+typedef struct stmt_ann_d *stmt_ann_t;
+typedef struct ssa_name_ann_d *ssa_name_ann_t;
+
+static inline var_ann_t var_ann (tree);
+static inline var_ann_t get_var_ann (tree);
+static inline stmt_ann_t stmt_ann (tree);
+static inline stmt_ann_t get_stmt_ann (tree);
+static inline ssa_name_ann_t ssa_name_ann (tree);
+static inline ssa_name_ann_t get_ssa_name_ann (tree);
+static inline enum tree_ann_type ann_type (tree_ann);
+static inline basic_block bb_for_stmt (tree);
+extern void set_bb_for_stmt (tree, basic_block);
+static inline void modify_stmt (tree);
+static inline void unmodify_stmt (tree);
+static inline bool stmt_modified_p (tree);
+static inline varray_type may_aliases (tree);
+static inline int get_lineno (tree);
+static inline const char *get_filename (tree);
+static inline bool is_exec_stmt (tree);
+static inline bool is_label_stmt (tree);
+static inline vdef_optype get_vdef_ops (stmt_ann_t);
+static inline vuse_optype get_vuse_ops (stmt_ann_t);
+static inline use_optype get_use_ops (stmt_ann_t);
+static inline def_optype get_def_ops (stmt_ann_t);
+static inline bitmap addresses_taken (tree);
+static inline int num_immediate_uses (dataflow_t);
+static inline tree immediate_use (dataflow_t, int);
+static inline dataflow_t get_immediate_uses (tree);
+static inline bool has_hidden_use (tree);
+static inline void set_has_hidden_use (tree);
+static inline void set_default_def (tree, tree);
+static inline tree default_def (tree);
+static inline bool may_be_aliased (tree);
+
+/*---------------------------------------------------------------------------
+                  Structure representing predictions in tree level.
+---------------------------------------------------------------------------*/
+struct edge_prediction GTY((chain_next ("%h.next")))
+{
+  struct edge_prediction *next;
+  edge edge;
+  enum br_predictor predictor;
+  int probability;
+};
+
+/*---------------------------------------------------------------------------
+		  Block annotations stored in basic_block.tree_annotations
+---------------------------------------------------------------------------*/
+struct bb_ann_d GTY(())
+{
+  /* Chain of PHI nodes for this block.  */
+  tree phi_nodes;
+
+  /* Chain of EPHI nodes created in this block.  */
+  tree ephi_nodes;
+  
+  /* Number of predecessors for this block.  This is only valid during
+     SSA rewriting.  It is not maintained after conversion into SSA form.  */
+  int num_preds;
+
+  /* Nonzero if this block is forwardable during cfg cleanups.  This is also
+     used to detect loops during cfg cleanups.  */
+  unsigned forwardable: 1;
+
+  /* Nonzero if this block contains an escape point (see is_escape_site).  */
+  unsigned has_escape_site : 1;
+
+  struct edge_prediction *predictions;
+};
+
+typedef struct bb_ann_d *bb_ann_t;
+
+/* Accessors for basic block annotations.  */
+static inline bb_ann_t bb_ann (basic_block);
+static inline tree phi_nodes (basic_block);
+static inline void set_phi_nodes (basic_block, tree);
+
+/*---------------------------------------------------------------------------
+			      Global declarations
+---------------------------------------------------------------------------*/
+/* Array of all variables referenced in the function.  */
+extern GTY(()) varray_type referenced_vars;
+
+#define num_referenced_vars VARRAY_ACTIVE_SIZE (referenced_vars)
+#define referenced_var(i) VARRAY_TREE (referenced_vars, i)
+
+/* Artificial variable used to model the effects of function calls.  */
+extern GTY(()) tree global_var;
+
+/* Call clobbered variables in the function.  If bit I is set, then
+   REFERENCED_VARS (I) is call-clobbered.  */
+extern bitmap call_clobbered_vars;
+
+/* 'true' after aliases have been computed (see compute_may_aliases).  */
+extern bool aliases_computed_p;
+
+/* Macros for showing usage statistics.  */
+#define SCALE(x) ((unsigned long) ((x) < 1024*10	\
+		  ? (x)					\
+		  : ((x) < 1024*1024*10			\
+		     ? (x) / 1024			\
+		     : (x) / (1024*1024))))
+
+#define LABEL(x) ((x) < 1024*10 ? 'b' : ((x) < 1024*1024*10 ? 'k' : 'M'))
+
+#define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
+
+
+/*---------------------------------------------------------------------------
+			      Block iterators
+---------------------------------------------------------------------------*/
+
+typedef struct {
+  tree_stmt_iterator tsi;
+  basic_block bb;
+} block_stmt_iterator;
+
+static inline block_stmt_iterator bsi_start (basic_block);
+static inline block_stmt_iterator bsi_last (basic_block);
+static inline bool bsi_end_p (block_stmt_iterator);
+static inline void bsi_next (block_stmt_iterator *);
+static inline void bsi_prev (block_stmt_iterator *);
+static inline tree bsi_stmt (block_stmt_iterator);
+static inline tree * bsi_stmt_ptr (block_stmt_iterator);
+
+extern void bsi_remove (block_stmt_iterator *);
+extern void bsi_move_before (block_stmt_iterator *, block_stmt_iterator *);
+extern void bsi_move_after (block_stmt_iterator *, block_stmt_iterator *);
+extern void bsi_move_to_bb_end (block_stmt_iterator *, basic_block);
+
+enum bsi_iterator_update
+{
+  /* Note that these are intentionally in the same order as TSI_FOO.  They
+     mean exactly the same as their TSI_* counterparts.  */
+  BSI_NEW_STMT,
+  BSI_SAME_STMT,
+  BSI_CHAIN_START,
+  BSI_CHAIN_END,
+  BSI_CONTINUE_LINKING
+};
+
+extern void bsi_insert_before (block_stmt_iterator *, tree,
+			       enum bsi_iterator_update);
+extern void bsi_insert_after (block_stmt_iterator *, tree,
+			      enum bsi_iterator_update);
+
+extern void bsi_replace (const block_stmt_iterator *, tree, bool);
+
+/*---------------------------------------------------------------------------
+			      Function prototypes
+---------------------------------------------------------------------------*/
+/* In tree-cfg.c  */
+
+/* Location to track pending stmt for edge insertion.  */
+#define PENDING_STMT(e)	((e)->insns.t)
+
+extern void delete_tree_cfg (void);
+extern void disband_implicit_edges (void);
+extern bool stmt_ends_bb_p (tree);
+extern bool is_ctrl_stmt (tree);
+extern bool is_ctrl_altering_stmt (tree);
+extern bool computed_goto_p (tree);
+extern bool simple_goto_p (tree);
+extern void tree_dump_bb (basic_block, FILE *, int);
+extern void debug_tree_bb (basic_block);
+extern basic_block debug_tree_bb_n (int);
+extern void dump_tree_cfg (FILE *, int);
+extern void debug_tree_cfg (int);
+extern void dump_cfg_stats (FILE *);
+extern void debug_cfg_stats (void);
+extern void debug_loop_ir (void);
+extern void print_loop_ir (FILE *);
+extern void cleanup_tree_cfg (void);
+extern tree first_stmt (basic_block);
+extern tree last_stmt (basic_block);
+extern tree *last_stmt_ptr (basic_block);
+extern tree last_and_only_stmt (basic_block);
+extern edge find_taken_edge (basic_block, tree);
+extern void cfg_remove_useless_stmts (void);
+extern edge thread_edge (edge, basic_block);
+extern basic_block label_to_block (tree);
+extern void tree_optimize_tail_calls (bool, enum tree_dump_index);
+extern edge tree_block_forwards_to (basic_block bb);
+extern void bsi_insert_on_edge (edge, tree);
+extern void bsi_commit_edge_inserts (int *);
+extern void notice_special_calls (tree);
+extern void clear_special_calls (void);
+extern void compute_dominance_frontiers (bitmap *);
+extern void verify_stmts (void);
+extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
+
+/* In tree-pretty-print.c.  */
+extern void dump_generic_bb (FILE *, basic_block, int, int);
+
+/* In tree-dfa.c  */
+extern var_ann_t create_var_ann (tree);
+extern stmt_ann_t create_stmt_ann (tree);
+extern ssa_name_ann_t create_ssa_name_ann (tree);
+extern tree create_phi_node (tree, basic_block);
+extern void add_phi_arg (tree *, tree, edge);
+extern void remove_phi_arg (tree, basic_block);
+extern void remove_phi_arg_num (tree, int);
+extern void remove_phi_node (tree, tree, basic_block);
+extern void remove_all_phi_nodes_for (bitmap);
+extern void dump_dfa_stats (FILE *);
+extern void debug_dfa_stats (void);
+extern void debug_referenced_vars (void);
+extern void dump_referenced_vars (FILE *);
+extern void dump_variable (FILE *, tree);
+extern void debug_variable (tree);
+extern void dump_immediate_uses (FILE *);
+extern void debug_immediate_uses (void);
+extern void dump_immediate_uses_for (FILE *, tree);
+extern void debug_immediate_uses_for (tree);
+extern void compute_immediate_uses (int, bool (*)(tree));
+extern void free_df (void);
+extern tree get_virtual_var (tree);
+extern void add_referenced_tmp_var (tree var);
+extern void mark_new_vars_to_rename (tree, bitmap);
+extern void redirect_immediate_uses (tree, tree);
+
+/* Flags used when computing reaching definitions and reached uses.  */
+#define TDFA_USE_OPS		1 << 0
+#define TDFA_USE_VOPS		1 << 1
+
+/* In gimple-low.c  */
+struct lower_data;
+extern void lower_stmt_body (tree, struct lower_data *);
+extern void expand_used_vars (void);
+extern void record_vars (tree);
+extern bool block_may_fallthru (tree block);
+
+/* In tree-ssa-alias.c  */
+extern void dump_may_aliases_for (FILE *, tree);
+extern void debug_may_aliases_for (tree);
+extern void dump_alias_info (FILE *);
+extern void debug_alias_info (void);
+extern void dump_points_to_info (FILE *);
+extern void debug_points_to_info (void);
+
+/* Call-back function for walk_use_def_chains().  At each reaching
+   definition, a function with this prototype is called.  */
+typedef bool (*walk_use_def_chains_fn) (tree, tree, void *);
+
+/* In tree-ssa.c  */
+extern void init_tree_ssa (void);
+extern void rewrite_vars_out_of_ssa (bitmap);
+extern void dump_reaching_defs (FILE *);
+extern void debug_reaching_defs (void);
+extern void dump_tree_ssa (FILE *);
+extern void debug_tree_ssa (void);
+extern void debug_def_blocks (void);
+extern void dump_tree_ssa_stats (FILE *);
+extern void debug_tree_ssa_stats (void);
+extern void ssa_remove_edge (edge);
+extern edge ssa_redirect_edge (edge, basic_block);
+extern void set_is_used (tree);
+extern bool tree_ssa_useless_type_conversion (tree);
+extern bool tree_ssa_useless_type_conversion_1 (tree, tree);
+extern void verify_ssa (void);
+extern void delete_tree_ssa (void);
+extern void register_new_def (tree, varray_type *);
+extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *);
+
+/* In tree-into-ssa.c  */
+extern void rewrite_into_ssa (void);
+
+extern unsigned int highest_ssa_version;
+
+/* In tree-ssa-pre.c  */
+extern void tree_perform_ssapre (tree, enum tree_dump_index);
+
+/* In tree-ssa-ccp.c  */
+bool fold_stmt (tree *);
+tree widen_bitfield (tree, tree, tree);
+
+/* In tree-ssa-dom.c  */
+extern void dump_dominator_optimization_stats (FILE *);
+extern void debug_dominator_optimization_stats (void);
+
+/* In tree-ssa-copy.c  */
+extern void propagate_value (tree *, tree);
+extern void replace_exp (tree *, tree);
+extern bool cprop_into_stmt (tree, varray_type);
+extern void cprop_into_successor_phis (basic_block, varray_type);
+
+/* In tree-flow-inline.h  */
+static inline int phi_arg_from_edge (tree, edge);
+static inline struct phi_arg_d *phi_element_for_edge (tree, edge);
+static inline bool may_propagate_copy (tree, tree);
+static inline bool is_call_clobbered (tree);
+static inline void mark_call_clobbered (tree);
+
+/* In tree-eh.c  */
+extern void make_eh_edges (tree);
+extern bool tree_could_trap_p (tree);
+extern bool tree_could_throw_p (tree);
+extern bool tree_can_throw_internal (tree);
+extern bool tree_can_throw_external (tree);
+extern void add_stmt_to_eh_region (tree, int);
+
+#include "tree-flow-inline.h"
+
+#endif /* _TREE_FLOW_H  */