Add breadth-first search option to walk_use_defs

[Diego Novillo <dnovillo at redhat dot com>]

I ended up not using it in the only user of walk_use_defs that we have
now.  But it may prove useful to someone else.

Bootstrapped and tested x86, alpha, ppc.

Diego.


	* tree-ssa.c (walk_use_def_chains_1): Add new argument IS_DFS.
	If true, do a depth-first search.  Do a breadht-first search,
	otherwise.
	(walk_use_def_chains): Add new argument IS_DFS.
	Update all users.
	* tree-flow.h (walk_use_def_chains): Update prototype.

Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.27
diff -d -c -p -r2.27 tree-flow.h
*** tree-flow.h	22 Jul 2004 08:20:38 -0000	2.27
--- tree-flow.h	22 Jul 2004 13:49:23 -0000
*************** extern bool tree_ssa_useless_type_conver
*** 576,582 ****
  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 *);
  extern void kill_redundant_phi_nodes (void);
  
  /* In tree-into-ssa.c  */
--- 576,582 ----
  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 *, bool);
  extern void kill_redundant_phi_nodes (void);
  
  /* In tree-into-ssa.c  */

Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.21
diff -d -c -p -r2.21 tree-ssa.c
*** tree-ssa.c	22 Jul 2004 02:48:27 -0000	2.21
--- tree-ssa.c	22 Jul 2004 13:49:25 -0000
*************** tree_ssa_useless_type_conversion (tree e
*** 598,609 ****
  
  
  /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
!    described in walk_use_def_chains.  VISITED is a bitmap used to mark
!    visited SSA_NAMEs to avoid infinite loops.  */
  
  static bool
  walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
! 		       bitmap visited)
  {
    tree def_stmt;
  
--- 794,813 ----
  
  
  /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
!    described in walk_use_def_chains.
!    
!    VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
!       infinite loops.
! 
!    IS_DFS is true if the caller wants to perform a depth-first search
!       when visiting PHI nodes.  A DFS will visit each PHI argument and
!       call FN after each one.  Otherwise, all the arguments are
!       visited first and then FN is called with each of the visited
!       arguments in a separate pass.  */
  
  static bool
  walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
! 		       bitmap visited, bool is_dfs)
  {
    tree def_stmt;
  
*************** walk_use_def_chains_1 (tree var, walk_us
*** 617,665 ****
    if (TREE_CODE (def_stmt) != PHI_NODE)
      {
        /* If we reached the end of the use-def chain, call FN.  */
!       return (*fn) (var, def_stmt, data);
      }
    else
      {
        int i;
  
!       /* Otherwise, follow use-def links out of each PHI argument and call
! 	 FN after visiting each one.  */
        for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
  	{
  	  tree arg = PHI_ARG_DEF (def_stmt, i);
  	  if (TREE_CODE (arg) == SSA_NAME
! 	      && walk_use_def_chains_1 (arg, fn, data, visited))
! 	    return true;
! 	  
! 	  if ((*fn) (arg, def_stmt, data))
  	    return true;
  	}
      }
    return false;
  }
    
  
  
! /* Walk use-def chains starting at the SSA variable VAR.  Call function FN
!    at each reaching definition found.  FN takes three arguments: VAR, its
!    defining statement (DEF_STMT) and a generic pointer to whatever state
!    information that FN may want to maintain (DATA).  FN is able to stop the 
!    walk by returning true, otherwise in order to continue the walk, FN 
!    should return false.  
  
     Note, that if DEF_STMT is a PHI node, the semantics are slightly
!    different.  For each argument ARG of the PHI node, this function will:
  
! 	1- Walk the use-def chains for ARG.
! 	2- Call (*FN) (ARG, PHI, DATA).
  
-    Note how the first argument to FN is no longer the original variable
-    VAR, but the PHI argument currently being examined.  If FN wants to get
-    at VAR, it should call PHI_RESULT (PHI).  */
  
  void
! walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data)
  {
    tree def_stmt;
  
--- 821,885 ----
    if (TREE_CODE (def_stmt) != PHI_NODE)
      {
        /* If we reached the end of the use-def chain, call FN.  */
!       return fn (var, def_stmt, data);
      }
    else
      {
        int i;
  
!       /* When doing a breadth-first search, call FN before following the
! 	 use-def links for each argument.  */
!       if (!is_dfs)
! 	for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
! 	  if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
! 	    return true;
! 
!       /* Follow use-def links out of each PHI argument.  */
        for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
  	{
  	  tree arg = PHI_ARG_DEF (def_stmt, i);
  	  if (TREE_CODE (arg) == SSA_NAME
! 	      && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
  	    return true;
  	}
+ 
+       /* When doing a depth-first search, call FN after following the
+ 	 use-def links for each argument.  */
+       if (is_dfs)
+ 	for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
+ 	  if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
+ 	    return true;
      }
+   
    return false;
  }
    
  
  
! /* Walk use-def chains starting at the SSA variable VAR.  Call
!    function FN at each reaching definition found.  FN takes three
!    arguments: VAR, its defining statement (DEF_STMT) and a generic
!    pointer to whatever state information that FN may want to maintain
!    (DATA).  FN is able to stop the walk by returning true, otherwise
!    in order to continue the walk, FN should return false.  
  
     Note, that if DEF_STMT is a PHI node, the semantics are slightly
!    different.  The first argument to FN is no longer the original
!    variable VAR, but the PHI argument currently being examined.  If FN
!    wants to get at VAR, it should call PHI_RESULT (PHI).
  
!    If IS_DFS is true, this function will:
! 
! 	1- walk the use-def chains for all the PHI arguments, and,
! 	2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
! 
!    If IS_DFS is false, the two steps above are done in reverse order
!    (i.e., a breadth-first search).  */
  
  
  void
! walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
!                      bool is_dfs)
  {
    tree def_stmt;
  
*************** walk_use_def_chains (tree var, walk_use_
*** 677,687 ****
    else
      {
        bitmap visited = BITMAP_XMALLOC ();
!       walk_use_def_chains_1 (var, fn, data, visited);
        BITMAP_XFREE (visited);
      }
  }
  
  /* Replaces VAR with REPL in memory reference expression *X in
     statement STMT.  */
  
--- 897,908 ----
    else
      {
        bitmap visited = BITMAP_XMALLOC ();
!       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
        BITMAP_XFREE (visited);
      }
  }
  
+ 
  /* Replaces VAR with REPL in memory reference expression *X in
     statement STMT.  */