Re: [PATCH] Operator Strength Reduction on trees

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> This patch is an implementation of Cooper, Simpson, and Vick's
> Operator Strength Reduction from their 1995 TOPLAS paper.

could you please explain what advantages does this algorithm
have over the trivial one using scev analysis, i.e., something
along the lines of

for_each_operand (op)
  {
    ev = analyze_scalar_evolution (op);
    if (is_affine (ev))
      {
        iv = find_or_create_biv_with_evolution (ev);
	SET_USE (op, iv);
      }
  }

One of my objections agains this patch is that it seems to duplicate
the work of induction variable analysis that we already have, so
you should somehow justify the need for this duplication
(especially since the iv analysis in OSR would probably have
to be improved to make it useful, including dealing with conversions
and other tricky parts that scev analysis already handles).

> I'll let Dan Berlin chime in with his own thoughts about why GCC
> should incorporate this optimization, but for my part I'll say that
> when I started experimenting with GCC I noticed a lot of loops with
> unnecessary induction variables, and this optimization succeeds at
> reducing that problem significantly. The result is a significant
> speedup for many loops.

Could you please provide some examples?  I guess some are in the
testcase you add, but given the lack of comments, it is hard to tell.

> 	* tree-ssa-osr.c: New file; add Dan Berlin's Operator
> 	Strength Reduction (OSR) implementation.
> 	* passes.c: Put OSR just before the iv_optimize pass, at
> 	Zdenek's suggestion.

please limit the changelogs to the description of changes, i.e.,
the "add Dan Berlin's Operator Strength Reduction (OSR) implementation"
and ", at Zdenek's suggestion." parts should not be here.  Also,
format the entries in the changelog in the usual way (see many examples
in the Changelog file).

> +static void
> +DFS (tree name)

Function names should not contain uppercase letters.  Also, more
descriptive name than just "dfs" would be preferable, to describe
for what reason we perform the dfs.

> +	      /* XXX: do something brainier about unsigned types.  */
> +	      if (TREE_CODE (op1) == SSA_NAME
> +		  && !TYPE_UNSIGNED (TREE_TYPE (op0))
> +		  && !TYPE_UNSIGNED (TREE_TYPE (op1))
> +		  && OSR_INFO (op1)->header != NULL
> +		  && region_const_def (op0, OSR_INFO (op1)->header))

This comment should be extended, to explain why you check here for
signed types (I guess it has something to do with overflows --
in case it is the case, also an explanation why the restriction to
signed types is sufficient).

Zdenek