[alias-improvements] Review of branch as of 2009-01-23

[Diego Novillo]

I took a snapshot of the branch as of 2009-01-23 and reviewed the
diff against trunk as of the latest merge point.  I saw various
changes to the branch come in during this time, so some of the
comments may be stale by now (sorry).

Some general observations:

- Overall, the cleanups in the branch look impressive.  There is
  a lot of simplified logic in the basic operand manipulation
  routines.  Good stuff.

- We need to get an idea of how much codegen quality has degraded
  (or not).  This change is very disruptive as it shifts the
  responsibility from the memory SSA web to the alias oracle. We
  need to find the right balance.  I suspect that the memory web
  in the IL will always need to be very coarse.

- What is the compile time performance profile?  We are trading
  slowness in one place for slowness in another.  Though now the
  slowness should only happen in memory passes.  I also didn't
  notice very many changes to the various memory optimizers
  (except, perhaps PRE), it mostly looked like updates for the
  new virtual operand interfaces.  What do you estimate needs to
  be changed for them to come back to parity with the existing
  behaviour?

- DSE has changed significantly, but it shouldn't matter as it
  really needs to be re-implemented.

- The entry points to the alias oracle should use a timer so that
  we can get an idea of its impact on the memory optimizers.

- I only briefly looked at the changes in PRE and aliasing.  I'd
  rather have dannyb look at those.

- The internal documentation on alias analysis needs to be
  updated.

> @@ -585,6 +585,13 @@ set_livein_block (tree var, basic_block 
>  static inline bool
>  symbol_marked_for_renaming (tree sym)
>  {
> +  if (sym == gimple_vop (cfun)
> +      && cfun->gimple_df->vop_needs_renaming)
> +    return true;

Why not have gimple_vop() be inserted in syms_to_rename like any other
symbol?

> @@ -595,6 +602,8 @@ static inline bool
>  is_old_name (tree name)
>  {
>    unsigned ver = SSA_NAME_VERSION (name);
> +  if (!new_ssa_names)
> +    return false;

Why is this guard necessary now?

>    return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
>  }
>  
> @@ -605,6 +614,8 @@ static inline bool
>  is_new_name (tree name)
>  {
>    unsigned ver = SSA_NAME_VERSION (name);
> +  if (!new_ssa_names)
> +    return false;

Likewise.

> @@ -1947,9 +1959,9 @@ rewrite_update_stmt (struct dom_walk_dat
>        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
>  	maybe_replace_use (use_p);
>  
> -      if (need_to_update_vops_p)
> -	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
> -	  maybe_replace_use (use_p);
> +      if (need_to_update_vops_p
> +	  && (use_p = gimple_vuse_op (stmt)) != NULL_USE_OPERAND_P)

I would just use NULL here, instead of NULL_USE_OPERAND_P.  Neither
NULL_USE_OPERAND_P nor NULL_DEF_OPERAND_P offer any kind of static
type protection (unlike NULL_TREE), so I would just ditch both.

> @@ -2293,6 +2305,7 @@ struct gimple_opt_pass pass_build_ssa = 
>    0,					/* properties_destroyed */
>    0,					/* todo_flags_start */
>    TODO_dump_func
> +    | TODO_update_ssa_only_virtuals

Hmm?  Why not build initial SSA with virtuals instead of having to do
a second pass at the end?

> +      print_generic_expr (file, gimple_vop (cfun), 0);
> +      fprintf (file, "\n");

Not special casing the VOP symbols would help remove extra handling
like this one.

> @@ -409,11 +405,9 @@ find_tail_calls (basic_block bb, struct 
>  	  break;
>  	}
>  
> -      /* If the statement has virtual or volatile operands, fail.  */
> -      if (!ZERO_SSA_OPERANDS (stmt, (SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS))
> -	  || gimple_has_volatile_ops (stmt)
> -	  || (!gimple_aliases_computed_p (cfun)
> -	      && gimple_references_memory_p (stmt)))
> +      /* If the statement references memory or volatile operands, fail.  */
> +      if (gimple_references_memory_p (stmt)

So, it seems that in the branch the following always holds:

gimple_references_memory_p (stmt) == gimple_vuse_op (stmt) || gimple_vdef_op (stmt)

is that right?  Perhaps we should make gimple_references_memory_p
return gimple_vuse_op||gimple_vdef_op?

> @@ -252,8 +238,7 @@ copy_rename_partition_coalesce (var_map 
>        && POINTER_TYPE_P (TREE_TYPE (root2))
>        && ((get_alias_set (TREE_TYPE (TREE_TYPE (root1)))
>  	   != get_alias_set (TREE_TYPE (TREE_TYPE (root2))))
> -	  || ((DECL_P (root1) && !MTAG_P (root1))
> -	      && (DECL_P (root2) && !MTAG_P (root2))
> +	  || (DECL_P (root1) && DECL_P (root2)
>  	      && DECL_NO_TBAA_P (root1) != DECL_NO_TBAA_P (root2))))

Vertical alignment for the predicate.

> @@ -554,6 +525,17 @@ likely_value (gimple stmt)
>  	has_constant_operand = true;
>      }
>  
> +  /* There may be constants in regular rhs operands.  */
> +  for (i = is_gimple_call (stmt) + gimple_has_lhs (stmt);

Guh, this looks confusing.  How about

	i = (is_gimple_call (stmt) && gimple_call_lhs (stmt) ? 3 : 0)

(arguments start in slot 3 for GIMPLE_CALL).

> -void
> -debug_may_aliases_for (tree var)
> +static bool
> +ref_may_used_by_call_p (gimple call, tree ref)

s/ref_may_used/ref_maybe_used/

> -/* Return true if VAR may be aliased.  */
> +/* If the statement STMT may use the memory reference REF return
> +   true, otherwise return false.  */
>  
>  bool
> -may_be_aliased (tree var)
> +ref_may_used_by_stmt_p (gimple stmt, tree ref)

s/may_used/maybe_used/

> -  set_symbol_mem_tag (ptr, tag);
> +/* Starting from a PHI node for the virtual operand of the memory reference
> +   REF find a continuation virtual operand that allows to continue walking
> +   statements dominating PHI skipping only statements that do not possibly

s/do not/cannot/

> +      def_stmt = SSA_NAME_DEF_STMT (vuse);
> +      if (gimple_nop_p (def_stmt))
> +	break;
> +      else if (gimple_code (def_stmt) == GIMPLE_PHI)
> +	vuse = get_continuation_for_phi (def_stmt, ref, &visited);
> +      else
> +	{
> +	  if (stmt_may_clobber_ref_p (def_stmt, ref))
> +	    break;
> +	  vuse = gimple_vuse (def_stmt);
> +	}
> +    }
> +  while (vuse);

This looks expensive.

> -  ptr->defs = (flags & SSA_OP_DEF) ? gimple_def_ops (stmt) : NULL;
> -  ptr->uses = (flags & SSA_OP_USE) ? gimple_use_ops (stmt) : NULL;
> -  ptr->vuses = (flags & SSA_OP_VUSE) ? gimple_vuse_ops (stmt) : NULL;
> -  ptr->vdefs = (flags & SSA_OP_VDEF) ? gimple_vdef_ops (stmt) : NULL;
> -  ptr->mayuses = (flags & SSA_OP_VMAYUSE) ? gimple_vdef_ops (stmt) : NULL;
> +  /* We do not support iterating over virtual defs or uses without
> +     iterating over defs or uses at the same time.  */

Why not?  I realize that VDEF/VUSE is now only one additional operand,
but a pass that is ignoring memory statements shouldn't have to also
stop at them.

> +	     ???  This verifying is now quite useless.  Checking that
> +	     the gimple VOP is not used in a real operand would be enough.  */
> +	  bitmap_set_bit (used_in_virtual_ops, 
> +			  DECL_UID (gimple_vop (cfun)));

Agreed, this check is not needed now.

> +	    {
> +	      if  (gimple_vuse_op (stmt) == NULL_USE_OPERAND_P)
> +		{
> +		  error ("statement has VUSE operand not in usess list");

s/usess/uses/


Diego.