[tree-ssa] Documentation and cleanup tree-dfa.c

[Diego Novillo <dnovillo at redhat dot com>]

More documentation and formatting cleanup.  This time in tree-dfa.c. 
The patch also removes some unused functions.


Diego.


	* tree-dfa.c: Update comments and reformat for legibility.
	(find_vars_r): Remove special casing of MODIFY_EXPR and
	simplify logic.
	(compute_reached_uses, compute_reaching_defs, remove_decl,
	find_decl_location): Remove.
	(discover_nonconstat_array_refs_r,
	discover_nonconstant_array_refs): Move ...
	* tree-outof-ssa.c: ... here.

Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.223
diff -d -c -p -r1.1.4.223 tree-dfa.c
*** tree-dfa.c	3 Apr 2004 11:12:00 -0000	1.1.4.223
--- tree-dfa.c	6 Apr 2004 19:00:08 -0000
***************
*** 1,5 ****
  /* Data flow functions for trees.
!    Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
     Contributed by Diego Novillo <dnovillo@redhat.com>
  
  This file is part of GCC.
--- 1,5 ----
  /* Data flow functions for trees.
!    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
     Contributed by Diego Novillo <dnovillo@redhat.com>
  
  This file is part of GCC.
*************** struct walk_state
*** 72,80 ****
  };
  
  
- /* Data and functions shared with tree-ssa.c.  */
- struct dfa_stats_d dfa_stats;
- 
  /* Local functions.  */
  static void collect_dfa_stats (struct dfa_stats_d *);
  static tree collect_dfa_stats_r (tree *, int *, void *);
--- 72,77 ----
*************** static tree find_hidden_use_vars_r (tree
*** 92,97 ****
--- 89,95 ----
  /* Array of all variables referenced in the function.  */
  varray_type referenced_vars;
  
+ 
  /*---------------------------------------------------------------------------
  			Dataflow analysis (DFA) routines
  ---------------------------------------------------------------------------*/
*************** find_referenced_vars (void)
*** 112,117 ****
--- 110,117 ----
    struct walk_state walk_state;
    tree block;
  
+   /* This is the very first pass in preparation for building the SSA
+      form of the function, so initialize internal data structures now.  */
    init_tree_ssa ();
  
    /* Walk the lexical blocks in the function looking for variables that may
*************** struct tree_opt_pass pass_referenced_var
*** 159,168 ****
  };
  
  
! /* Compute immediate uses.  The parameter calc_for is an option function 
!    pointer which indicates whether immediate uses information should be
!    calculated for a given SSA variable. If NULL, then information is computed
!    for all variables.  */
  
  void
  compute_immediate_uses (int flags, bool (*calc_for)(tree))
--- 159,174 ----
  };
  
  
! /* Compute immediate uses.  
!    
!    CALC_FOR is an optional function pointer which indicates whether
!       immediate uses information should be calculated for a given SSA
!       variable.  If NULL, then information is computed for all
!       variables.
! 
!    FLAGS is one of {TDFA_USE_OPS, TDFA_USE_VOPS}.  It is used by
!       compute_immediate_uses_for_stmt to determine whether to look at
!       virtual and/or real operands while computing def-use chains.  */
  
  void
  compute_immediate_uses (int flags, bool (*calc_for)(tree))
*************** compute_immediate_uses (int flags, bool 
*** 186,191 ****
--- 192,198 ----
      }
  }
  
+ 
  /* Invalidates dataflow information for a statement STMT.  */
  
  static void
*************** free_df_for_stmt (tree stmt)
*** 197,203 ****
      ann->df = NULL;
  }
  
! /* Invalidates dataflow information.  */
  
  void
  free_df (void)
--- 204,211 ----
      ann->df = NULL;
  }
  
! 
! /* Invalidate dataflow information for the whole function.  */
  
  void
  free_df (void)
*************** free_df (void)
*** 220,230 ****
      }
  }
  
  /* Helper for compute_immediate_uses.  Check all the USE and/or VUSE
     operands in phi node PHI and add a def-use edge between their
!    defining statement and PHI.
  
!    PHI nodes are easy, we only need to look at its arguments.  */
  
  static void
  compute_immediate_uses_for_phi (tree phi, bool (*calc_for)(tree))
--- 228,240 ----
      }
  }
  
+ 
  /* Helper for compute_immediate_uses.  Check all the USE and/or VUSE
     operands in phi node PHI and add a def-use edge between their
!    defining statement and PHI.  CALC_FOR is as in
!    compute_immediate_uses.
  
!    PHI nodes are easy, we only need to look at their arguments.  */
  
  static void
  compute_immediate_uses_for_phi (tree phi, bool (*calc_for)(tree))
*************** compute_immediate_uses_for_phi (tree phi
*** 250,258 ****
  }
  
  
! /* Another helper for compute_immediate_uses.  Check all the USE and/or VUSE
!    operands in STMT and add a def-use edge between their defining statement
!    and STMT.  */
  
  static void
  compute_immediate_uses_for_stmt (tree stmt, int flags, bool (*calc_for)(tree))
--- 260,269 ----
  }
  
  
! /* Another helper for compute_immediate_uses.  Depending on the value
!    of FLAGS, check all the USE and/or VUSE operands in STMT and add a
!    def-use edge between their defining statement and STMT.  CALC_FOR
!    is as in compute_immediate_uses.  */
  
  static void
  compute_immediate_uses_for_stmt (tree stmt, int flags, bool (*calc_for)(tree))
*************** compute_immediate_uses_for_stmt (tree st
*** 263,270 ****
    vdef_optype vdefs;
    stmt_ann_t ann;
  
-   /* PHI nodes are handled elsewhere.  */
  #ifdef ENABLE_CHECKING
    if (TREE_CODE (stmt) == PHI_NODE)
      abort ();
  #endif
--- 274,281 ----
    vdef_optype vdefs;
    stmt_ann_t ann;
  
  #ifdef ENABLE_CHECKING
+   /* PHI nodes are handled elsewhere.  */
    if (TREE_CODE (stmt) == PHI_NODE)
      abort ();
  #endif
*************** compute_immediate_uses_for_stmt (tree st
*** 306,330 ****
  }
  
  
- /* Compute reached uses.  */
- 
- void
- compute_reached_uses (int flags ATTRIBUTE_UNUSED)
- {
-   abort ();
- }
- 
- 
- /* Compute reaching definitions.  */
- 
- void
- compute_reaching_defs (int flags ATTRIBUTE_UNUSED)
- {
-   abort ();
- }
- 
- 
- 
  /* Add statement USE_STMT to the list of statements that use definitions
      made by STMT.  */
  
--- 317,322 ----
*************** add_immediate_use (tree stmt, tree use_s
*** 355,361 ****
    VARRAY_PUSH_TREE (ann->df->immediate_uses, use_stmt);
  }
  
! /* If the any immediate use of USE points to OLD, then redirect it to NEW.  */
   
  static void
  redirect_immediate_use (tree use, tree old, tree new)
--- 347,354 ----
    VARRAY_PUSH_TREE (ann->df->immediate_uses, use_stmt);
  }
  
! 
! /* If the immediate use of USE points to OLD, then redirect it to NEW.  */
   
  static void
  redirect_immediate_use (tree use, tree old, tree new)
*************** redirect_immediate_use (tree use, tree o
*** 377,382 ****
--- 370,376 ----
      }
  }
  
+ 
  /* Redirect all immediate uses for operands in OLD so that they point
     to NEW.  This routine should have no knowledge of how immediate
     uses are stored.  */
*************** redirect_immediate_uses (tree old, tree 
*** 401,406 ****
--- 395,401 ----
      redirect_immediate_use (VDEF_OP (vdefs, i), old, new);
  }
  
+ 
  /*---------------------------------------------------------------------------
  			    Manage annotations
  ---------------------------------------------------------------------------*/
*************** collect_dfa_stats_r (tree *tp, int *walk
*** 826,874 ****
  /*---------------------------------------------------------------------------
  			     Miscellaneous helpers
  ---------------------------------------------------------------------------*/
- /* Remove variable DECL from the block that declares it.  */
- 
- void
- remove_decl (tree decl, tree block)
- {
-   tree *loc;
-   
-   loc = find_decl_location (decl, block);
-   if (loc)
-     *loc = TREE_CHAIN (decl);
- }
- 
- 
- /* Find the location for declaration DECL in lexical block BLOCK.  All the
-    subblocks of BLOCK are searched as well if BLOCK does not declare DECL.
-    Return an address LOC such that *LOC == DECL or NULL if DECL couldn't be
-    located.  */
- 
- tree *
- find_decl_location (tree decl, tree block)
- {
-   tree d, sub;
- 
-   /* Special case.  If DECL is the first symbol in the block, return its
-      location directly.  */
-   if (BLOCK_VARS (block) == decl)
-     return &(BLOCK_VARS (block));
- 
-   for (d = BLOCK_VARS (block); d; d = TREE_CHAIN (d))
-     if (TREE_CHAIN (d) == decl)
-       return &(TREE_CHAIN (d));
- 
-   for (sub = BLOCK_SUBBLOCKS (block); sub; sub = TREE_CHAIN (sub))
-     {
-       tree *loc = find_decl_location (decl, sub);
-       if (loc)
- 	return loc;
-     }
- 
-   return NULL;
- }
- 
- 
  /* Callback for walk_tree.  Used to collect variables referenced in
     the function.  */
  
--- 821,826 ----
*************** find_vars_r (tree *tp, int *walk_subtree
*** 878,936 ****
    tree t = *tp;
    struct walk_state *walk_state = (struct walk_state *)data;
  
!   /* Type and constant nodes have no interesting children.  Ignore them.  */
!   if (TYPE_P (t) || TREE_CODE_CLASS (TREE_CODE (t)) == 'c')
      {
!       *walk_subtrees = 0;
!       return NULL_TREE;
      }
! 
!   /* DECL nodes have no interesting children.  */
!   if (DECL_P (t))
      {
        *walk_subtrees = 0;
- 
-       /* If this _DECL node is not interesting to the SSA builder,
-          then we can just return now.  */
-       if (! SSA_VAR_P (t)) 
- 	return NULL_TREE;
      }
  
-   if (TREE_CODE (t) == MODIFY_EXPR)
-     {
-       tree *lhs_p = &TREE_OPERAND (t, 0);
-       tree *rhs_p = &TREE_OPERAND (t, 1);
- 
-       walk_tree (lhs_p, find_vars_r, walk_state, NULL);
-       walk_tree (rhs_p, find_vars_r, walk_state, NULL);
- 
-       /* If either side makes volatile references, mark the statement.  */
-       if (TREE_THIS_VOLATILE (*lhs_p)
- 	  || TREE_THIS_VOLATILE (*rhs_p))
- 	get_stmt_ann (t)->has_volatile_ops = 1;
- 
-       return t;
-     }
- 
-   if (SSA_VAR_P (t))
-     {
-       add_referenced_var (t, walk_state);
-       return NULL_TREE;
-     }
  
    return NULL_TREE;
  }
  
  
! /* Add VAR to the list of dereferenced variables.  If VAR is a candidate
!    for aliasing, add it to the ADDRESSABLE_VAR array.  If VAR is a memory
!    tag, add it to the POINTERS array.  These two arrays are used for
!    alias analysis (See compute_alias_sets).
  
     WALK_STATE contains a hash table used to avoid adding the same
!    variable more than once to its corresponding set as well as flags
!    indicating if we're processing a load or store.  Note that this
!    function assumes that VAR is a valid SSA variable.  */
  
  static void
  add_referenced_var (tree var, struct walk_state *walk_state)
--- 830,861 ----
    tree t = *tp;
    struct walk_state *walk_state = (struct walk_state *)data;
  
!   if (SSA_VAR_P (t))
      {
!       /* If T is a regular variable that the optimizers are interested
! 	 in, add it to the list of variables.  */
!       add_referenced_var (t, walk_state);
      }
!   else if (DECL_P (t)
! 	   || TYPE_P (t)
! 	   || TREE_CODE_CLASS (TREE_CODE (t)) == 'c')
      {
+       /* Type, _DECL and constant nodes have no interesting children.
+ 	 Ignore them.  */
        *walk_subtrees = 0;
      }
  
  
    return NULL_TREE;
  }
  
  
! /* Add VAR to the list of dereferenced variables.
  
     WALK_STATE contains a hash table used to avoid adding the same
!       variable more than once. Note that this function assumes that
!       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
!       duplicate checking is done.  */
  
  static void
  add_referenced_var (tree var, struct walk_state *walk_state)
*************** get_virtual_var (tree var)
*** 991,996 ****
--- 916,924 ----
      }
  
  #ifdef ENABLE_CHECKING
+   /* Treating GIMPLE registers as virtual variables makes no sense.
+      Also complain if we couldn't extract a _DECL out of the original
+      expression.  */
    if (!SSA_VAR_P (var)
        || is_gimple_reg (var))
      abort ();
*************** get_virtual_var (tree var)
*** 999,1007 ****
    return var;
  }
  
- /* Mark variables that have hidden uses.
  
!    A hidden use can occur due to VLA declarations or nested functions.   */
  
  static void
  find_hidden_use_vars (tree block)
--- 927,935 ----
    return var;
  }
  
  
! /* Mark variables in BLOCK that have hidden uses.  A hidden use can
!    occur due to VLA declarations or nested functions.   */
  
  static void
  find_hidden_use_vars (tree block)
*************** find_hidden_use_vars (tree block)
*** 1009,1015 ****
    tree sub, decl, tem;
  
    /* Check all the arrays declared in the block for VLAs.
- 
       While scanning the block's variables, also see if there is
       a nested function at this scope.  */
    for (decl = BLOCK_VARS (block); decl; decl = TREE_CHAIN (decl))
--- 937,942 ----
*************** find_hidden_use_vars (tree block)
*** 1038,1043 ****
--- 965,971 ----
      }
  }
  
+ 
  /* Callback for walk_tree used by find_hidden_use_vars to analyze each 
     variable in a lexical block.  If the variable's size has a variable
     size, then mark all objects needed to compute the variable's size
*************** add_referenced_tmp_var (tree var)
*** 1087,1092 ****
--- 1015,1021 ----
    add_referenced_var (var, NULL);
  }
  
+ 
  /* Return true if VDEFS_AFTER contains fewer entries than VDEFS_BEFORE.
     Note that this assumes that both varrays are VDEF operands for the same
     statement.  */
*************** vdefs_disappeared_p (vdef_optype vdefs_b
*** 1106,1111 ****
--- 1035,1041 ----
    return false;
  }
  
+ 
  /* Add all the non-SSA variables found in STMT's operands to the bitmap
     VARS_TO_RENAME.  */
  
*************** mark_new_vars_to_rename (tree stmt, bitm
*** 1211,1263 ****
      bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
  
    BITMAP_XFREE (vars_in_vops_to_rename);
- }
- 
- /* Helper function for discover_nonconstant_array_refs. 
-    Look for variables inside ARRAY_REF with non-constant operand
-    and mark them as addressable.  */
- static tree
- discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
- 				   void *data ATTRIBUTE_UNUSED)
- {
-   tree t = *tp;
-   if (TYPE_P (t) || DECL_P (t))
-     *walk_subtrees = 0;
-   else if (TREE_CODE (t) == ARRAY_REF)
-     {
-       while ((TREE_CODE (t) == ARRAY_REF
- 	      && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
- 	     || (TREE_CODE (t) == COMPONENT_REF
- 		 || TREE_CODE (t) == BIT_FIELD_REF
- 		 || TREE_CODE (t) == REALPART_EXPR
- 		 || TREE_CODE (t) == IMAGPART_EXPR))
- 	t = TREE_OPERAND (t, 0);
-       if (TREE_CODE (t) == ARRAY_REF)
- 	{
- 	  t = get_base_address (t);
- 	  if (t && DECL_P (t))
- 	    TREE_ADDRESSABLE (t) = 1;
- 	}
-       *walk_subtrees = 0;
-     }
-   return NULL_TREE;
- }
- 
- /* RTL expansion code is not able to compile array references with variable
-    offsets for arrays stored in single register.
-    Discover such expressions and mark variables as addressable to avoid
-    this scenario.  */
- 
- void
- discover_nonconstant_array_refs (void)
- {
-   basic_block bb;
-   block_stmt_iterator bsi;
- 
-   FOR_EACH_BB (bb)
-     {
-       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- 	walk_tree (bsi_stmt_ptr (bsi), discover_nonconstant_array_refs_r,
- 		   NULL , NULL);
-     }
  }
--- 1141,1144 ----
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.199
diff -d -c -p -r1.1.4.199 tree-flow.h
*** tree-flow.h	25 Mar 2004 18:42:21 -0000	1.1.4.199
--- tree-flow.h	6 Apr 2004 19:00:08 -0000
*************** extern void dump_immediate_uses (FILE *)
*** 494,509 ****
  extern void debug_immediate_uses (void);
  extern void dump_immediate_uses_for (FILE *, tree);
  extern void debug_immediate_uses_for (tree);
- extern void remove_decl (tree, tree);
- extern tree *find_decl_location (tree, tree);
- extern void compute_reached_uses (int);
  extern void compute_immediate_uses (int, bool (*)(tree));
  extern void free_df (void);
- extern void compute_reaching_defs (int);
  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 discover_nonconstant_array_refs (void);
  extern void redirect_immediate_uses (tree, tree);
  
  /* Flags used when computing reaching definitions and reached uses.  */
--- 494,504 ----
Index: tree-outof-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-outof-ssa.c,v
retrieving revision 1.1.2.1
diff -d -c -p -r1.1.2.1 tree-outof-ssa.c
*** tree-outof-ssa.c	19 Mar 2004 02:07:25 -0000	1.1.2.1
--- tree-outof-ssa.c	6 Apr 2004 19:00:08 -0000
*************** dump_replaceable_exprs (FILE *f, tree *e
*** 1664,1669 ****
--- 1664,1725 ----
  }
  
  
+ /* Helper function for discover_nonconstant_array_refs. 
+    Look for ARRAY_REF nodes with non-constant indexes and mark them
+    addressable.  */
+ 
+ static tree
+ discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
+ 				   void *data ATTRIBUTE_UNUSED)
+ {
+   tree t = *tp;
+ 
+   if (TYPE_P (t) || DECL_P (t))
+     *walk_subtrees = 0;
+   else if (TREE_CODE (t) == ARRAY_REF)
+     {
+       while ((TREE_CODE (t) == ARRAY_REF
+ 	      && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
+ 	     || (TREE_CODE (t) == COMPONENT_REF
+ 		 || TREE_CODE (t) == BIT_FIELD_REF
+ 		 || TREE_CODE (t) == REALPART_EXPR
+ 		 || TREE_CODE (t) == IMAGPART_EXPR))
+ 	t = TREE_OPERAND (t, 0);
+ 
+       if (TREE_CODE (t) == ARRAY_REF)
+ 	{
+ 	  t = get_base_address (t);
+ 	  if (t && DECL_P (t))
+ 	    TREE_ADDRESSABLE (t) = 1;
+ 	}
+ 
+       *walk_subtrees = 0;
+     }
+ 
+   return NULL_TREE;
+ }
+ 
+ 
+ /* RTL expansion is not able to compile array references with variable
+    offsets for arrays stored in single register.  Discover such
+    expressions and mark variables as addressable to avoid this
+    scenario.  */
+ 
+ static void
+ discover_nonconstant_array_refs (void)
+ {
+   basic_block bb;
+   block_stmt_iterator bsi;
+ 
+   FOR_EACH_BB (bb)
+     {
+       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	walk_tree (bsi_stmt_ptr (bsi), discover_nonconstant_array_refs_r,
+ 		   NULL , NULL);
+     }
+ }
+ 
+ 
  /* This function will rewrite the current program using the variable mapping
     found in 'map'. If the replacement vector 'values' is provided, any 
     occurrences of partitions with non-null entries in the vector will be