[tree-ssa] Cgraph overall comment + fixes

[Jan Hubicka <jh at suse dot cz>]

Hi,
while working on merging cgraph code into mainline I noticed few problems,
fixed by this patch.  I also add overall documentation based on the design
document I sent few months ago.  Any comments are welcome :)

Bootstrapped/regtested i686-pc-gnu-linux, will commit it tomorrow
baring complains.

Honza

2004-02-05  Jan Hubicka  <jh@suse.cz>
	* cgraph.c: Add overview comment.
	(cgraph_remove_node): Release more datastructures
	* cgraphunit.c: Add overview comment.
	(cgraph_finalize_function): Release DECL_SAVED_INSNS for extern inline
	functions.
	(cgraph_expand_function): Release more datastructures
	(cgraph_remove_unreachable_nodes): Likewsie; avoid unconditional cgraph
	verification.
	* tree-inline.c (save_body): Fix production of new PARM_DECL.
Index: cgraph.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraph.c,v
retrieving revision 1.4.4.17
diff -c -3 -p -r1.4.4.17 cgraph.c
*** cgraph.c	30 Jan 2004 13:13:38 -0000	1.4.4.17
--- cgraph.c	5 Feb 2004 10:11:00 -0000
*************** along with GCC; see the file COPYING.  I
*** 19,24 ****
--- 19,84 ----
  Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  02111-1307, USA.  */
  
+ /*  This file contains basic routines manipulating call graph and variable pool
+   
+ The callgraph:
+ 
+     The call-graph is data structure designed for intra-procedural optimization
+     but it is also used in non-unit-at-a-time compilation to allow easier code
+     sharing.
+ 
+     The call-graph consist of nodes and edges represented via linked lists.
+     Each function (external or not) corresponds to the unique node (in
+     contrast to tree DECL nodes where we can have multiple nodes for each
+     function).
+ 
+     The mapping from declarations to call-graph nodes is done using hash table
+     based on DECL_ASSEMBLER_NAME, so it is essential for assembler name to
+     not change once the declaration is inserted into the call-graph.
+     The call-graph nodes are created lazily using cgraph_node function when
+     called for unknown declaration.
+     
+     When built, there is one edge for each direct call.  It is possible that
+     the reference will be later optimized out.  The call-graph is built
+     conservatively in order to make conservative data flow analysis possible.
+ 
+     The callgraph at the moment does not represent indirect calls or calls
+     from other compilation unit.  Flag NEEDED is set for each node that may
+     be accessed in such a invisible way and it shall be considered an
+     entry point to the callgraph.
+ 
+     Intraprocedural information:
+ 
+       Callgraph is place to store data needed for intraprocedural optimization.
+       All datastructures are divided into three components: local_info that
+       is produced while analyzing the function, global_info that is result
+       of global walkking of the callgraph on the end of compilation and
+       rtl_info used by RTL backend to propagate data from already compiled
+       functions to their callers.
+ 
+     Inlining plans:
+ 
+       The function inlining information is decided in advance and maintained
+       in the callgraph as so called inline plan.
+       For each inlined call, the calle's node is clonned to represent the
+       new function copy produced by inlininer.
+       Each inlined call gets unque corresponding clone node of the callee
+       and the datastructure is updated while inlining is performed, so
+       the clones are elliminated and their callee edges redirected to the
+       caller. 
+ 
+       Each edge has "inline_failed" field.  When the field is set to NULL,
+       the call will be inlined.  When it is non-NULL it contains an reason
+       why inlining wasn't performaned.
+ 
+ 
+ The varpool data structure:
+ 
+     Varpool is used to maintain variables in similar manner as call-graph
+     is used for functions.  Most of the API is symmetric replacing cgraph
+     function prefix by cgraph_varpool  */
+ 
+ 
  #include "config.h"
  #include "system.h"
  #include "coretypes.h"
*************** cgraph_remove_node (struct cgraph_node *
*** 298,304 ****
  	{
            htab_clear_slot (cgraph_hash, slot);
  	  if (!dump_enabled_p (TDI_all))
!             DECL_SAVED_TREE (node->decl) = NULL;
  	  check_dead = false;
  	}
      }
--- 358,369 ----
  	{
            htab_clear_slot (cgraph_hash, slot);
  	  if (!dump_enabled_p (TDI_all))
! 	    {
!               DECL_SAVED_TREE (node->decl) = NULL;
! 	      DECL_SAVED_INSNS (node->decl) = NULL;
! 	      DECL_ARGUMENTS (node->decl) = NULL;
! 	      DECL_INITIAL (node->decl) = error_mark_node;
! 	    }
  	  check_dead = false;
  	}
      }
*************** cgraph_remove_node (struct cgraph_node *
*** 323,329 ****
  		&& !TREE_ASM_WRITTEN (n->decl) && !DECL_EXTERNAL (n->decl)))
  	  break;
        if (!n && !dump_enabled_p (TDI_all))
!         DECL_SAVED_TREE (node->decl) = NULL;
      }
    cgraph_n_nodes--;
    /* Do not free the structure itself so the walk over chain can continue.  */
--- 388,399 ----
  		&& !TREE_ASM_WRITTEN (n->decl) && !DECL_EXTERNAL (n->decl)))
  	  break;
        if (!n && !dump_enabled_p (TDI_all))
! 	{
! 	  DECL_SAVED_TREE (node->decl) = NULL;
! 	  DECL_SAVED_INSNS (node->decl) = NULL;
! 	  DECL_ARGUMENTS (node->decl) = NULL;
! 	  DECL_INITIAL (node->decl) = error_mark_node;
! 	}
      }
    cgraph_n_nodes--;
    /* Do not free the structure itself so the walk over chain can continue.  */
Index: cgraphunit.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraphunit.c,v
retrieving revision 1.1.4.33
diff -c -3 -p -r1.1.4.33 cgraphunit.c
*** cgraphunit.c	1 Feb 2004 12:42:11 -0000	1.1.4.33
--- cgraphunit.c	5 Feb 2004 10:11:00 -0000
*************** along with GCC; see the file COPYING.  I
*** 19,24 ****
--- 19,168 ----
  Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  02111-1307, USA.  */
  
+ /* This module implements main driver of compilation process as well as
+    few basic intraprocedural optimizers.
+ 
+    The main scope of this file is to act as an interface in between
+    tree based frontends and the backend (and middle end)
+ 
+    The front-end is supposed to use following functionality:
+ 
+     - cgraph_finalize_function
+ 
+       This function is called once front-end has parsed whole body of function
+       and it is certain that the function body nor the declaration will change.
+ 
+       (There is one exception needed for implementing GCC extern inline function.)
+ 
+     - cgraph_varpool_finalize_variable
+ 
+       This function has same behaviour as the above but is used for static
+       variables.
+ 
+     - cgraph_finalize_compilation_unit
+ 
+       This function is called once compilation unit is finalized and it will
+       no longer change.
+ 
+       In the unit-at-a-time the call-graph construction and local function
+       analysis takes place here.  Bodies of unreachable functions are released
+       to conserve memory usage.
+ 
+       ???  The compilation unit in this point of view should be compilation
+       unit as defined by the language - for instance C frontend allows multiple
+       compilation units to be parsed at once and it should call function each
+       time parsing is done so we save memory.
+ 
+     - cgraph_optimize
+ 
+       In this unit-at-a-time compilation the intra procedural analysis takes
+       place here.  In particular the static functions whose address is never
+       taken are marked as local.  Backend can then use this information to
+       modify calling conventions, do better inlining or similar optimizations.
+ 
+     - cgraph_assemble_pending_functions
+     - cgraph_varpool_assemble_pending_variables
+ 
+       In non-unit-at-a-time mode these functions can be used to force compilation
+       of functions or variables that are known to be needed at given stage
+       of compilation
+ 
+     - cgraph_mark_needed_node
+     - cgraph_varpool_mark_needed_node
+ 
+       When function or variable is referenced by some hidden way (for instance
+       via assembly code and marked by attribute "used"), the call-graph data structure
+       must be updated accordingly by this function.
+ 
+     - analyze_expr callback
+ 
+       This function is responsible for lowering tree nodes not understood by
+       generic code into understandable ones or alternatively marking
+       callgraph and varpool nodes referenced by the as needed.
+ 
+       ??? On the tree-ssa genericizing should take place here and we will avoid
+       need for these hooks (replacing them by genericizing hook)
+ 
+     - expand_function callback
+ 
+       This function is used to expand function and pass it into RTL back-end.
+       Front-end should not make any assumptions about when this function can be
+       called.  In particular cgraph_assemble_pending_functions,
+       cgraph_varpool_assemble_pending_variables, cgraph_finalize_function,
+       cgraph_varpool_finalize_function, cgraph_optimize can cause arbitrarily
+       previously finalized functions to be expanded.
+ 
+     We implement two compilation modes.
+ 
+       - unit-at-a-time:  In this mode analyzing of all functions is deferred
+ 	to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
+ 
+ 	In cgraph_finalize_compilation_unit the reachable functions are
+ 	analyzed.  During analysis the call-graph edges from reachable
+ 	functions are constructed and their destinations are marked as
+ 	reachable.  References to functions and variables are discovered too
+ 	and variables found to be needed output to the assembly file.  Via
+ 	mark_referenced call in assemble_variable functions referenced by
+ 	static variables are noticed too.
+ 
+ 	The intra-procedural information is produced and it's existence
+ 	indicated by global_info_ready.  Once this flag is set it is impossible
+ 	to change function from !reachable to reachable and thus
+ 	assemble_variable no longer call mark_referenced.
+ 
+ 	Finally the call-graph is topologically sorted and all reachable functions
+ 	that has not been completely inlined or are not external are output.
+ 
+ 	??? It is possible that reference to function or variable is optimized
+ 	out.  We can not deal with this nicely because topological order is not
+ 	suitable for it.  For tree-ssa we may consider another pass doing
+ 	optimization and re-discovering reachable functions.
+ 
+ 	??? Reorganize code so variables are output very last and only if they
+ 	really has been referenced by produced code, so we catch more cases
+ 	where reference has been optimized out.
+ 
+       - non-unit-at-a-time
+ 
+ 	All functions are variables are output as early as possible to conserve
+ 	memory consumption.  This may or may not result in less memory used but
+ 	it is still needed for some legacy code that rely on particular ordering
+ 	of things output from the compiler.
+ 
+ 	Varpool data structures are not used and variables are output directly.
+ 
+ 	Functions are output early using call of
+ 	cgraph_assemble_pending_function from cgraph_finalize_function.  The
+ 	decision on whether function is needed is made more conservative so
+ 	uninlininable static functions are needed too.  During the call-graph
+ 	construction the edge destinations are not marked as reachable and it
+ 	is completely relied upn assemble_variable to mark them.
+ 	
+      Inlining decision heuristics
+         ??? Move this to separate file after tree-ssa merge.
+ 
+ 	We separate inlining decisions from the inliner itself and store it
+ 	inside callgraph as so called inline plan.  Reffer to cgraph.c
+ 	documentation about particular representation of inline plans in the
+ 	callgraph
+ 
+ 	The implementation of particular heuristics is separated from
+ 	the rest of code to make it easier to replace it with more complicated
+ 	implementation in the future.  The rest of inlining code acts as a
+ 	library aimed to modify the callgraph and verify that the parameters
+ 	on code size growth fits.
+ 
+ 	To mark given call inline, use cgraph_mark_inline function, the
+ 	verification is performed by cgraph_default_inline_p and
+ 	cgraph_check_inline_limits.
+ 
+ 	The heuristics implements simple knapsack style algorithm ordering
+ 	all functions by their "profitability" (estimated by code size growth)
+ 	and inlining them in priority order.
+ 
+ 	cgraph_decide_inlining implements heuristics taking whole callgraph
+ 	into account, while cgraph_decide_inlining_incrementally considers
+ 	only one function at a time and is used in non-unit-at-a-time mode.  */
  #include "config.h"
  #include "system.h"
  #include "coretypes.h"
*************** cgraph_finalize_function (tree decl, boo
*** 228,233 ****
--- 372,382 ----
    /* If we've not yet emitted decl, tell the debug info about it.  */
    if (!TREE_ASM_WRITTEN (decl))
      (*debug_hooks->deferred_inline_function) (decl);
+ 
+   /* We will never really output the function body, clear the SAVED_INSNS array
+      early then.  */
+   if (DECL_EXTERNAL (decl))
+     DECL_SAVED_INSNS (decl) = NULL;
  }
  
  /* Walk tree and record all calls.  Called via walk_tree.  */
*************** cgraph_expand_function (struct cgraph_no
*** 646,652 ****
    current_function_decl = NULL;
    if (DECL_SAVED_TREE (node->decl)
        && !cgraph_preserve_function_body_p (node->decl))
!     DECL_SAVED_TREE (node->decl) = NULL;
  }
  
  /* Fill array order with all nodes with output flag set in the reverse
--- 795,806 ----
    current_function_decl = NULL;
    if (DECL_SAVED_TREE (node->decl)
        && !cgraph_preserve_function_body_p (node->decl))
!     {
!       DECL_SAVED_TREE (node->decl) = NULL;
!       DECL_SAVED_INSNS (node->decl) = NULL;
!       DECL_ARGUMENTS (node->decl) = NULL;
!       DECL_INITIAL (node->decl) = error_mark_node;
!     }
  }
  
  /* Fill array order with all nodes with output flag set in the reverse
*************** cgraph_remove_unreachable_nodes (void)
*** 722,728 ****
--- 876,884 ----
    bool changed = false;
    int insns = 0;
  
+ #ifdef ENABLE_CHECKING
    verify_cgraph ();
+ #endif
    if (cgraph_dump_file)
      fprintf (cgraph_dump_file, "\nReclaiming functions:");
  #ifdef ENABLE_CHECKING
*************** cgraph_remove_unreachable_nodes (void)
*** 798,804 ****
  		    if (clone->aux)
  		      break;
  		  if (!clone)
! 		    DECL_SAVED_TREE (node->decl) = NULL_TREE;
  		  while (node->callees)
  		    cgraph_remove_edge (node->callees);
  		  node->analyzed = false;
--- 954,965 ----
  		    if (clone->aux)
  		      break;
  		  if (!clone)
! 		    {
! 		      DECL_SAVED_TREE (node->decl) = NULL;
! 		      DECL_SAVED_INSNS (node->decl) = NULL;
! 		      DECL_ARGUMENTS (node->decl) = NULL;
! 		      DECL_INITIAL (node->decl) = error_mark_node;
! 		    }
  		  while (node->callees)
  		    cgraph_remove_edge (node->callees);
  		  node->analyzed = false;
*************** cgraph_remove_unreachable_nodes (void)
*** 815,821 ****
      node->aux = NULL;
    if (cgraph_dump_file)
      fprintf (cgraph_dump_file, "\nReclaimed %i insns", insns);
-   verify_cgraph ();
    return changed;
  }
  
--- 976,981 ----
Index: tree-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.c,v
retrieving revision 1.26.2.80
diff -c -3 -p -r1.26.2.80 tree-inline.c
*** tree-inline.c	30 Jan 2004 13:14:17 -0000	1.26.2.80
--- tree-inline.c	5 Feb 2004 10:11:02 -0000
*************** save_body (tree fn, tree *arg_copy)
*** 1909,1914 ****
--- 1909,1916 ----
    for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
      {
        tree new = copy_node (*parg);
+       (*lang_hooks.dup_lang_specific_decl) (new);
+       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*parg);
        insert_decl_map (&id, *parg, new);
        TREE_CHAIN (new) = TREE_CHAIN (*parg);
        *parg = new;