[PATCH] Unit at a time comment fixes, speedup

[Steven Bosscher <s dot bosscher at student dot tudelft dot nl>]

Hi, 

This patch adds a few comments in places where it wasn't clear to me
what was going on there.  The comments are based on Honza's explanation.
Also fixed indentation in a few places. 

The only real change is to use walk_tree_without_duplicates instead of
plain walk_tree, which should speed up things somewhat. 

Honza thinks the patch looks fine. 

Booted&regtested just to be sure.  OK for mainline? 

Greetz 
Steven 


2003-05-10  Steven Bosscher  <steven@gcc.gnu.org> 

	* cgraphunit.c (cgraph_create_edges): Drop walk_tree in
	favor of walk_tree_without_duplicates.

Index: cgraphunit.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraphunit.c,v
retrieving revision 1.4
diff -c -3 -p -r1.4 cgraphunit.c
*** cgraphunit.c	15 Mar 2003 13:43:28 -0000	1.4
--- cgraphunit.c	10 May 2003 09:36:51 -0000
*************** static struct cgraph_node *queue = NULL;
*** 68,73 ****
--- 68,74 ----
  
  /* Notify finalize_compilation_unit that given node is reachable
     or needed.  */
+ 
  void
  cgraph_mark_needed_node (node, needed)
       struct cgraph_node *node;
*************** record_call_1 (tp, walk_subtrees, data)
*** 107,112 ****
--- 108,118 ----
      }
    else if (TREE_CODE (*tp) == CALL_EXPR)
      {
+       /* We cannot use get_callee_fndecl here because it actually tries
+ 	 too hard to get the function declaration, looking for indirect
+ 	 references and stripping NOPS.  As a result, get_callee_fndecl
+ 	 finds calls that shouldn't be in the call graph.  */
+ 
        tree decl = TREE_OPERAND (*tp, 0);
        if (TREE_CODE (decl) == ADDR_EXPR)
  	decl = TREE_OPERAND (decl, 0);
*************** record_call_1 (tp, walk_subtrees, data)
*** 115,120 ****
--- 121,134 ----
  	  if (DECL_BUILT_IN (decl))
  	    return NULL;
  	  cgraph_record_call (data, decl);
+ 	     
+ 	  /* When we see a function call, we don't want to look at the
+ 	     function reference in the ADDR_EXPR that is hanging from
+ 	     the CALL_EXPR we're examining here, because we would
+ 	     conclude incorrectly that the function's address could be
+ 	     taken by something that is not a function call.  So only
+ 	     walk the function parameter list, skip the other subtrees.  */
+ 
  	  walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
  	  *walk_subtrees = 0;
  	}
*************** record_call_1 (tp, walk_subtrees, data)
*** 122,135 ****
    return NULL;
  }
  
! /* Create cgraph edges for function calles via BODY.  */
  
  void
  cgraph_create_edges (decl, body)
       tree decl;
       tree body;
  {
!   walk_tree (&body, record_call_1, decl, NULL);
  }
  
  /* Analyze the whole compilation unit once it is parsed completely.  */
--- 136,151 ----
    return NULL;
  }
  
! /* Create cgraph edges for function calls inside BODY from DECL.  */
  
  void
  cgraph_create_edges (decl, body)
       tree decl;
       tree body;
  {
!   /* The nodes we're interested in are never shared, so walk
!      the tree ignoring duplicates.  */
!   walk_tree_without_duplicates (&body, record_call_1, decl);
  }
  
  /* Analyze the whole compilation unit once it is parsed completely.  */
*************** cgraph_finalize_compilation_unit ()
*** 155,168 ****
  	  || (DECL_ASSEMBLER_NAME_SET_P (decl)
  	      && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
  	{
!           cgraph_mark_needed_node (node, 1);
  	}
      }
  
!   /*  Propagate reachability flag and lower representation of all reachable
!       functions.  In the future, lowering will introduce new functions and
!       new entry points on the way (by template instantiation and virtual
!       method table generation for instance).  */
    while (queue)
      {
        tree decl = queue->decl;
--- 171,186 ----
  	  || (DECL_ASSEMBLER_NAME_SET_P (decl)
  	      && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
  	{
! 	  /* This function can be called from outside this compliation
! 	     unit, so it most definitely is needed.  */
! 	  cgraph_mark_needed_node (node, 1);
  	}
      }
  
!   /* Propagate reachability flag and lower representation of all reachable
!      functions.  In the future, lowering will introduce new functions and
!      new entry points on the way (by template instantiation and virtual
!      method table generation for instance).  */
    while (queue)
      {
        tree decl = queue->decl;
*************** cgraph_finalize_compilation_unit ()
*** 184,189 ****
--- 202,208 ----
  
        if (lang_hooks.callgraph.lower_function)
  	(*lang_hooks.callgraph.lower_function) (decl);
+ 
        /* First kill forward declaration so reverse inling works properly.  */
        cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
  
*************** cgraph_finalize_compilation_unit ()
*** 194,199 ****
--- 213,219 ----
  	}
        node->lowered = true;
      }
+ 
    if (!quiet_flag)
      fprintf (stderr, "\n\nReclaiming functions:");
  
*************** cgraph_mark_functions_to_output ()
*** 217,227 ****
  {
    struct cgraph_node *node;
  
-   /* Figure out functions we want to assemble.  */
    for (node = cgraph_nodes; node; node = node->next)
      {
        tree decl = node->decl;
  
        if (DECL_SAVED_TREE (decl)
  	  && (node->needed
  	      || (!node->local.inline_many && !node->global.inline_once
--- 237,249 ----
  {
    struct cgraph_node *node;
  
    for (node = cgraph_nodes; node; node = node->next)
      {
        tree decl = node->decl;
  
+       /* We need to output all local functions that are used and not
+ 	 always inlined, as well as those that are reachable from
+ 	 outside the current compilation unit.  */
        if (DECL_SAVED_TREE (decl)
  	  && (node->needed
  	      || (!node->local.inline_many && !node->global.inline_once
*************** cgraph_mark_functions_to_output ()
*** 234,239 ****
--- 256,262 ----
  }
  
  /* Optimize the function before expansion.  */
+ 
  static void
  cgraph_optimize_function (node)
       struct cgraph_node *node;
*************** cgraph_optimize_function (node)
*** 250,255 ****
--- 273,279 ----
  }
  
  /* Expand function specified by NODE.  */
+ 
  static void
  cgraph_expand_function (node)
       struct cgraph_node *node;
*************** cgraph_expand_function (node)
*** 260,270 ****
  
    cgraph_optimize_function (node);
  
!   /* Avoid RTL inlining from taking place.  */
    (*lang_hooks.callgraph.expand_function) (decl);
  
!   /* When we decided to inline the function once, we never ever should need to
!      output it separately.  */
    if (node->global.inline_once)
      abort ();
    if (!node->local.inline_many
--- 284,295 ----
  
    cgraph_optimize_function (node);
  
!   /* Generate RTL for the body of DECL.  Nested functions are expanded
!      via lang_expand_decl_stmt.  */
    (*lang_hooks.callgraph.expand_function) (decl);
  
!   /* When we decided to inline the function once, we never ever should
!      need to output it separately.  */
    if (node->global.inline_once)
      abort ();
    if (!node->local.inline_many
*************** cgraph_expand_function (node)
*** 277,287 ****
  /* Expand all functions that must be output. 
    
     Attempt to topologically sort the nodes so function is output when
!    all called functions are already assembled to allow data to be propagated
!    accross the callgraph.  Use stack to get smaller distance between function
!    and it's callees (later we may use more sophisticated algorithm for
!    function reordering, we will likely want to use subsections to make output
!    functions to appear in top-down order, not bottom-up they are assembled).  */
  
  static void
  cgraph_expand_functions ()
--- 302,313 ----
  /* Expand all functions that must be output. 
    
     Attempt to topologically sort the nodes so function is output when
!    all called functions are already assembled to allow data to be
!    propagated accross the callgraph.  Use a stack to get smaller distance
!    between a function and it's callees (later we may choose to use a more
!    sophisticated algorithm for function reordering; we will likely want
!    to use subsections to make the output functions appear in top-down
!    order.  */
  
  static void
  cgraph_expand_functions ()
*************** cgraph_expand_functions ()
*** 298,307 ****
  
    cgraph_mark_functions_to_output ();
  
!   /*  We have to deal with cycles nicely, so use depth first traversal
!       algorithm.  Ignore the fact that some functions won't need to be output
!       and put them into order as well, so we get dependencies right trought inlined
!       functions.  */
    for (node = cgraph_nodes; node; node = node->next)
      node->aux = NULL;
    for (node = cgraph_nodes; node; node = node->next)
--- 324,333 ----
  
    cgraph_mark_functions_to_output ();
  
!   /* We have to deal with cycles nicely, so use a depth first traversal
!      output algorithm.  Ignore the fact that some functions won't need
!      to be output and put them into order as well, so we get dependencies
!      right through intline functions.  */
    for (node = cgraph_nodes; node; node = node->next)
      node->aux = NULL;
    for (node = cgraph_nodes; node; node = node->next)
*************** cgraph_mark_local_functions ()
*** 380,387 ****
      }
  }
  
! /*  Decide what function should be inlined because they are invoked once
!     (so inlining won't result in duplication of the code).  */
  
  static void
  cgraph_mark_functions_to_inline_once ()
--- 406,413 ----
      }
  }
  
! /* Decide what function should be inlined because they are invoked once
!    (so inlining won't result in duplication of the code).  */
  
  static void
  cgraph_mark_functions_to_inline_once ()
*************** cgraph_mark_functions_to_inline_once ()
*** 391,398 ****
    if (!quiet_flag)
      fprintf (stderr, "\n\nMarking functions to inline once:");
  
!   /* Now look for function called only once and mark them to inline.  From this
!      point number of calls to given function won't grow.  */
    for (node = cgraph_nodes; node; node = node->next)
      {
        if (node->callers && !node->callers->next_caller && !node->needed
--- 417,424 ----
    if (!quiet_flag)
      fprintf (stderr, "\n\nMarking functions to inline once:");
  
!   /* Now look for function called only once and mark them to inline.
!      From this point number of calls to given function won't grow.  */
    for (node = cgraph_nodes; node; node = node->next)
      {
        if (node->callers && !node->callers->next_caller && !node->needed