[tree-ssa] Proper support for may-alias in SSA [patch]

[Diego Novillo <dnovillo at redhat dot com>]

With this patch we can now properly model may-alias information
and call clobbered variables in SSA.  It's rather large, but I
couldn't really break it appart any more because the changes are
related.

The minor fixes first:

- It moves calls to tree_find_refs and tree_compute_rdefs into
  the main SSA builder.

- It changes the semantics of the -fdump-tree-ssa flag.  By
  default we should only show the program in SSA form.  Right now
  the default will show nothing (patch in the works).  If you
  want output you need to specify -details or -refs or -rdefs.

- It modularizes CCP a bit more by having a unique function to
  replace uses in an expression for evaluation.


The major fixes are better described by the new documentation for
SSA in tree-ssa.c.  I'll just paste it here.  Notice that the
aggregation bits are still not present in this patch, but the
severe memory consumption I had experienced last week is gone
thanks to the new method we use to model call clobbered
variables.  In the bootstraps I've done the compiler grows up to
120Mb.  It's still gross, but it's nowhere near the 1.4Gb I was
experiencing last week.


   Partial references
   ------------------

   To deal with arrays and structures, we use the concept of non-killing
   definitions.  When an array location or structure element is defined,
   the SSA builder will consider that a partial definition of the array
   itself.  Partial definitions are modeled by keeping an SSA link
   (def-def link) between the current definition and the previous one.

   This is used to chain definitions to arrays and structures, so that all
   possible reaching defs can be found later by tree_compute_rdefs.  For
   instance,

	      1  A[i] = 5;
	      2  A[j] = 10;
	      3  y = A[k] + 10;

   Since the assignments to A[i] at line 1 and A[j] at line 2 are partial
   definitions of A, without def-def chains the use of A[k] at line 3 will
   not be reached by the defintion at line 1.


   Modeling may-alias information
   ------------------------------

   May-aliases are discovered by compute_may_aliases.  Currently, the set
   computed is conservatively large because it uses a type-based,
   flow-insensitive method.  For each variable V, we compute all the
   may-aliases for V and store them in tree_annotation(V)->may_aliases.

   When we build the SSA form for the program, a definition for V will be
   considered a regular killing definition for V, but will be considered a
   non-killing definition for V's aliases.  However, contrary to the case
   with arrays, we don't keep a single def-def link between this definition
   and the previous one.  We keep N def-def links at each definition site,
   one for each alias of V.  For instance, assume that in the following
   fragment *p may-alias a and b:

	    1	a = 2;  <-------------------------+
	    2	                                  |
	    3	b = 5;  <----------------------+  |
	    4	                               |  |
	    5	*p = 93;    ALIAS_IMM_RDEF = { +, + }
	    6	 ^------+
	    7	 |      |
	    8	 +--+   |
	    9	    |   |
	    10	c = a * b;

   At the definition site for *p, we keep an array of reaching definitions
   for each alias of *p (ALIAS_IMM_RDEF).  We also make *p the current
   reaching definition for a and b.  This way, we maintain the program in
   SSA form and also keep track of all the definitions that may reach a and
   b.

   When computing reaching definitions, since *p is not a killing
   definition for either a nor b, follow_chain will examine the
   ALIAS_IMM_RDEF array at the definition for *p and find the other
   definitions.  Giving the expected result that at line 10, a can be
   reached by '*p = 93' and by 'a = 2'.

   Notice that this array of def-def links for aliases is kept at *every*
   definition site.  If the may-alias information is too conservative,
   these arrays may be very large, causing severe memory problems.

   To address this problem, we have a heuristic aggregation mechanism that
   after a certain number of may-aliases, will give up and create a single
   virtual variable that represents all the variables in the may-alias set.
   After this, every reference to any variable in the may-alias set will be
   considered a reference to this one virtual variable.  This is,
   effectively, the same mechanism used to deal with array references.

   
   Modeling call-clobbered variables
   ---------------------------------

   Variables that might be call clobbered are handled by inserting a use
   and a clobbering definition of an artificial global variable call
   GLOBAL_VAR.  Every alias that may be call clobbered is added to the
   may-alias set of GLOBAL_VAR.  The aliasing mechanism built into SSA will
   naturally create def-use and use-def links at call sites for the
   affected variables.  */


Bootstrapped and tested on x86.


Diego.



	* Makefile.in (tree-dfa.o): Depend on flags.h
	* tree-cfg.c (tree_dump_cfg): Alter output format slightly.
	(block_invalidates_loop): Look for clobbering definitions of
	GLOBAL_VARIABLE.
	* tree-simple.c (get_base_symbol): Handle EXPR_WITH_FILE_LOCATION
	nodes.
	* tree-optimize.c (init_tree_flow): Remove.  Update all users.
	(build_tree_ssa): Don't call tree_find_refs.
	Don't call tree_compute_rdefs.

	* tree-dfa.c: Include flags.h
	(dump_file): Remove.
	(dump_flags): Remove.
	(pointer_refs): Remove.
	(struct dfa_stats_d): Add fields max_num_phi_args, num_may_alias,
	max_num_may_alias, num_alias_imm_rdefs and max_num_alias_imm_rdefs.
	Remove field num_fcalls.
	(dfa_counts): Declare.
	(tree_find_refs): Declare.
	(tree_ssa_dump_file): Declare.
	(tree_ssa_dump_flags): Declare.
	(dump_if_different): New function.
	(add_default_defs): Remove.  Update all users.
	(add_call_site_clobbers): Remove.  Update all users.
	(add_ptr_may_refs): Remove.  Update all users.
	(compute_may_aliases): New function.
	(find_may_aliases_for): New function.
	(add_may_alias): New function.
	(may_alias_p): New function.
	(is_visible_to): New function.
	(get_alias_index): New function.
	(call_sites): Remove.  Update all users.
	(global_var): Declare.
	(E_FCALL): Remove.  Adjust other constants.
	(M_INDIRECT): Remove.  Update all users.
	(M_RELOCATE): Declare.
	(tree_find_refs): Move debugging dumps to tree_build_ssa.
	Move initialization code to init_tree_ssa.
	Call compute_may_aliases.
	(find_refs_in_expr): For INDIRECT_REF nodes create a reference to
	the canonical INDIRECT_REF node associated with the pointer symbol.
	Given a pointer p, clobber the canonical INDIRECT_REF of p after
	creating a V_DEF for p.
	For CALL_EXPR nodes, if the called function is not pure nor
	const, create a use and a clobbering definition to GLOBAL_VAR.
	(create_ref): Allow INDIRECT_REF variables.
	(add_phi_arg): Keep track of number of PHI arguments created.
	(function_may_recurse_p): Look for clobbering definitions to
	GLOBAL_VAR.
	(get_fcalls): Remove unused function.
	(is_pure_fcall): Remove unused function.
	(fcall_takes_ref_args): Remove unused function.
	(find_declaration): Stop iterating at ENTRY_BLOCK_PTR.
	(debug_variable): New function.
	(dump_variable): New function.
	(dump_referenced_vars): Call it.
	(dump_phi_args): Don't dump NULL arguments.
	(PERCENT): Define.
	(dump_dfa_stats): Re-format output.
	Add new counters.
	Call dump_if_different.
	(collect_dfa_stats): Also recurse into GLOBAL_VAR.
	(collect_dfa_stats_r): Collect may-alias information.
	(count_tree_refs): Collect information about def-def links for
	aliases.
	Keep track of maximum values for number of PHI arguments, aliases
	and def-def links.
	(ref_type_name): Handle M_RELOCATE.
	(validate_ref_type): Ditto.

	* tree-ssa.c: Add more documentation.
	(tree_ssa_dump_file): Rename from dump_file.  Declare extern.
	(tree_ssa_dump_flags): Rename from dump_flags.  Declare extern.
	(added): New local varray.
	(in_work): New local varray.
	(work_stack): New local varray.
	(dfa_counts): Declare.
	(insert_phi_nodes_for): New local function.
	(add_phi_node): New local function.
	(set_ssa_links): New local function.
	(set_alias_imm_reaching_def): New local function.
	(create_default_def): New local function.
	(init_tree_ssa): New local function.
	(tree_find_refs): Relocate declaration from tree-flow.h
	(tree_build_ssa): Call init_tree_ssa.
	Call tree_find_refs.
	Process all SSA-related dump options.
	(insert_phi_nodes): Rename from insert_phi_terms.  Update all
	users.
	Call insert_phi_nodes_for.
	(build_fud_chains): Add more documentation.
	Initialize save_chain to 0.
	(search_fud_chains): Add more documentation.
	Call set_ssa_links.
	Call create_default_def.
	(tree_compute_rdefs): Initialize array marked to 0.
	(follow_chain): Follow def-def chains for non-killing definitions
	for aliases.
	(dump_reaching_defs): Call dump_variable.

	* tree-flow.h (E_FCALL): Remove.  Update all users.
	(M_INDIRECT): Remove.  Update all users.
	(M_RELOCATE): Declare.
	(struct var_ref): Add field alias_imm_rdefs.
	(alias_imm_reaching_def): New inline function.
	(struct tree_ann_d): Add field indirect_var.
	Add field may_aliases.
	(enum tree_flags): Relocate.
	(indirect_var): New inline function.
	(set_indirect_var): New inline function.
	(may_alias): New inline function.
	(num_may_alias): New inline function.
	(struct dfa_counts_d): Declare.
	(global_var): Declare.
	(FCALL_NON_PURE, FCALL_PURE, FCALL_BUILT_IN): Remove.
	(tree_find_refs): Move to tree-ssa.c.
	(dump_variable): Declare.
	(debug_variable): Declare.
	(get_fcalls): Remove.
	(is_pure_fcall): Remove.
	(fcall_takes_ref_args): Remove.
	(ref_defines): Declare.
	(is_killing_def): Declare.
	(get_alias_index): Declare.
	(delete_tree_ssa): Rename from delete_ssa.  Update all users.
	(set_currdef_for): Allow INDIRECT_REF nodes.
	(bb_annotation): Don't create a new one if the block didn't have an
	annotation already.

	* tree-ssa-ccp.c (substitute_and_fold): Rename from
	ssa_ccp_substitute_constants.  Update all users.
	Call replace_uses_in.
	(replace_uses_in): New local function.
	(evaluate_expr): Call it.
	(initialize): Call get_base_symbol.

	* tree-ssa-dce.c (tree_ssa_eliminate_dead_code): Don't handle
	E_FCALL.

Attachment: 20020925-may-alias-fixes.diff.gz
Description: application/gunzip