On Tue, 2011-05-24 at 14:26 +0200, Richard Guenther wrote:
<snip>
> > +/* Recursive subroutine of powi_as_mults. This function takes the
> > + array, CACHE, of already calculated exponents and an exponent N and
> > + returns a tree that corresponds to CACHE[1]**N, with type TYPE. */
> > +
> > +static tree
> > +powi_as_mults_1 (gimple_stmt_iterator *gsi, location_t loc, tree type,
> > + HOST_WIDE_INT n, tree *cache, tree target)
> > +{
> > + tree op0, op1, ssa_target;
> > + unsigned HOST_WIDE_INT digit;
> > + gimple mult_stmt;
> > +
> > + if (n < POWI_TABLE_SIZE)
> > + {
> > + if (cache[n])
> > + return cache[n];
> > +
> > + ssa_target = make_ssa_name (target, NULL);
>
> You can hoist the ssa_target creation before the if instead of
> replicating it ...
OK. The time spent in make_ssa_name will be wasted in the common case
where the value is found in the cache. But I can restructure the logic
to avoid that.
>
> > + cache[n] = ssa_target;
> > +
> > + op0 = powi_as_mults_1 (gsi, loc, type, n - powi_table[n], cache,
> > target);
> > + op1 = powi_as_mults_1 (gsi, loc, type, powi_table[n], cache, target);
> > + }
> > + else if (n & 1)
> > + {
> > + digit = n & ((1 << POWI_WINDOW_SIZE) - 1);
> > + op0 = powi_as_mults_1 (gsi, loc, type, n - digit, cache, target);
> > + op1 = powi_as_mults_1 (gsi, loc, type, digit, cache, target);
> > + ssa_target = make_ssa_name (target, NULL);
>
> here and
>
> > + }
> > + else
> > + {
> > + op0 = powi_as_mults_1 (gsi, loc, type, n >> 1, cache, target);
> > + op1 = op0;
> > + ssa_target = make_ssa_name (target, NULL);
>
> here.
>
> > + }
> > +
> > + mult_stmt = gimple_build_assign_with_ops (MULT_EXPR, ssa_target, op0,
> > op1);
> > + gsi_insert_before (gsi, mult_stmt, GSI_SAME_STMT);
> > +
> > + return ssa_target;
> > +}
> > +
> > +/* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
> > + This function needs to be kept in sync with powi_cost above. */
> > +
> > +static tree
> > +powi_as_mults (gimple_stmt_iterator *gsi, location_t loc,
> > + tree arg0, HOST_WIDE_INT n)
> > +{
> > + tree cache[POWI_TABLE_SIZE], result, type = TREE_TYPE (arg0), target;
> > + gimple div_stmt;
> > +
> > + if (n == 0)
> > + return build_real (type, dconst1);
> > +
> > + memset (cache, 0, sizeof (cache));
> > + cache[1] = arg0;
> > +
> > + target = create_tmp_var (type, "powmult");
> > + add_referenced_var (target);
> > +
> > + result = powi_as_mults_1 (gsi, loc, type, (n < 0) ? -n : n, cache,
> > target);
> > +
> > + if (n >= 0)
> > + return result;
> > +
> > + /* If the original exponent was negative, reciprocate the result. */
> > + target = create_tmp_var (type, "powmult");
> > + add_referenced_var (target);
>
> re-use target from above.
>
Oops, sorry, that was sloppy.
> > + target = make_ssa_name (target, NULL);
> > +
> > + div_stmt = gimple_build_assign_with_ops (RDIV_EXPR, target,
> > + build_real (type, dconst1),
> > + result);
> > + gsi_insert_before (gsi, div_stmt, GSI_SAME_STMT);
> > +
> > + return target;
> > +}
> > +
> > +/* ARG0 and N are the two arguments to a powi builtin in GSI with
> > + location info LOC. If the arguments are appropriate, create an
> > + equivalent sequence of statements prior to GSI using an optimal
> > + number of multiplications, and return an expession holding the
> > + result. */
> > +
> > +static tree
> > +gimple_expand_builtin_powi (gimple_stmt_iterator *gsi, location_t loc,
> > + tree arg0, HOST_WIDE_INT n)
> > +{
> > + /* Avoid largest negative number. */
> > + if (n != -n
> > + && ((n >= -1 && n <= 2)
> > + || (optimize_function_for_speed_p (cfun)
> > + && powi_cost (n) <= POWI_MAX_MULTS)))
> > + return powi_as_mults (gsi, loc, arg0, n);
> > +
> > + return NULL_TREE;
> > +}
> > +
> > /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
> > - on the SSA_NAME argument of each of them. */
> > + on the SSA_NAME argument of each of them. Also expand powi(x,n) into
> > + an optimal number of multiplies, when n is a constant. */
> >
> > static unsigned int
> > execute_cse_sincos (void)
> > @@ -821,7 +1056,9 @@ execute_cse_sincos (void)
> > && (fndecl = gimple_call_fndecl (stmt))
> > && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
> > {
> > - tree arg;
> > + tree arg, arg0, arg1, result;
> > + HOST_WIDE_INT n, n_hi;
> > + location_t loc;
> >
> > switch (DECL_FUNCTION_CODE (fndecl))
> > {
> > @@ -833,6 +1070,29 @@ execute_cse_sincos (void)
> > cfg_changed |= execute_cse_sincos_1 (arg);
> > break;
> >
> > + CASE_FLT_FN (BUILT_IN_POWI):
> > + arg0 = gimple_call_arg (stmt, 0);
> > + arg1 = gimple_call_arg (stmt, 1);
> > + if (!host_integerp (arg1, 0))
> > + break;
> > +
> > + n = TREE_INT_CST_LOW (arg1);
> > + n_hi = TREE_INT_CST_HIGH (arg1);
> > + if (n_hi != 0 && n_hi != -1)
> > + break;
>
> The n_hi query and check isn't necessary as host_integerp already
> ensures this.
>
Ah, OK. Thanks.
> > +
> > + loc = gimple_location (stmt);
> > + result = gimple_expand_builtin_powi (&gsi, loc, arg0, n);
> > +
> > + if (result)
> > + {
> > + tree lhs = gimple_get_lhs (stmt);
> > + gimple new_stmt = gimple_build_assign (lhs, result);
> > + gimple_set_location (new_stmt, loc);
> > + gsi_replace (&gsi, new_stmt, true);
> > + }
> > + break;
> > +
> > default:;
> > }
> > }
> > @@ -849,10 +1109,9 @@ execute_cse_sincos (void)
> > static bool
> > gate_cse_sincos (void)
> > {
> > - /* Make sure we have either sincos or cexp. */
> > - return (TARGET_HAS_SINCOS
> > - || TARGET_C99_FUNCTIONS)
> > - && optimize;
> > + /* We no longer require either sincos or cexp, since powi expansion
> > + piggybacks on this pass. */
> > + return optimize;
> > }
> >
> > struct gimple_opt_pass pass_cse_sincos =
>
> With the above changes the patch is ok for trunk, possibly after we
> resolved the gsi_replace virtual operand case (you probably
> can reproduce it with -funsafe-math-optimizations -ferrno-math).
OK, just saw your other note. I'll copy the logic from
update_call_from-tree ().
Thanks,
Bill
>
> Thanks,
> Richard.
