> > > > +/* Check that the "exponential index transform" can be applied to this
> > > > switch.
> > > > +
> > > > + See comment of the exp_index_transform function for details about
> > > > this
> > > > + transformation.
> > > > +
> > > > + We want:
> > > > + - This form of the switch is more efficient
> > > > + - Cases are powers of 2
> > > > +
> > > > + Expects that SWTCH has at least one case. */
> > > > +
> > > > +bool
> > > > +switch_conversion::is_exp_index_transform_viable (gswitch *swtch)
> > > > +{
> > > > + tree index = gimple_switch_index (swtch);
> > > > + tree index_type = TREE_TYPE (index);
> > > > + basic_block swtch_bb = gimple_bb (swtch);
> > > > + unsigned num_labels = gimple_switch_num_labels (swtch);
> > > > +
> > > > + /* Check that we can efficiently compute logarithm of 2^k (using
> > > > FFS) and
> > > > + test that a given number is 2^k for some k (using POPCOUNT). */
> > > > + optimization_type opt_type = bb_optimization_type (swtch_bb);
> > > > + if (!direct_internal_fn_supported_p (IFN_FFS, index_type, opt_type)
> > > > + || !direct_internal_fn_supported_p (IFN_POPCOUNT, index_type,
> > > > opt_type))
> > > > + return false;
> > > > +
> > >
> > > See above, I think this can be improved. Would be nice to split out
> > > a can_pow2p (type) and can_log2 (type) and a corresponding
> > > gen_pow2p (op) and gen_log2 (op) function so this could be re-used
> > > and alternate variants added when required.
> > >
> >
> > Just to check that I understand this correctly: You'd like me to create
> > functions can_pow2p, can_log2. Those functions will check that there are
> > optabs for the target machine which allow us to efficiently test
> > power-of-2-ness of a number and which allow us to efficiently compute the
> > base-2 log of a power-of-2 number. You'd also like me to create functions
> > gen_pow2p and gen_log2 which generate this code. For now these functions
> > will
> > just use POPCOUNT and FFS but they can be later extended to also consider
> > different instructions. Is that right?
>
> Right.
>
> > Into which file should I put these functions?
>
> Just in this file for now.
>
> > Is can_pow2p and gen_pow2p necessary? As you noted one can always use
> > (x & -x) == x so testing pow2p can always be done efficiently.
>
> If you add this fallback then can_pow2p / gen_pow2p wouldn't be
> necessary indeed.
Hi Richard,
I put some work into splitting out the can_ and gen_ functions as you
suggested. I'm still a bit unsure what your vision of these is so before I
submit all the changes I made to the patch as version 2 I would like to share
how I implemented the functions (see bellow). Is this how you imagined the
functions? Would you change something or do the they look ok?
I wasn't sure how generic to make the functions. The more generic the more
convoluted the implementation becomes. For example: I could make them more
generic by also including a gsi_iterator_update parameter or I could make them
less generic but more straightforward by removing the BEFORE parameter.
Cheers,
Filip Kastl
/* Does the target have optabs needed to efficiently compute exact base two
logarithm of a value with type TYPE?
See gen_log2. */
static bool
can_log2 (tree type, optimization_type opt_type)
{
/* Check if target supports FFS. */
return direct_internal_fn_supported_p (IFN_FFS, type, opt_type);
}
/* Assume that OP is a power of two. Build a sequence of gimple statements
efficiently computing the base two logarithm of OP using special optabs.
Insert statements before GSI if BEFORE is true or after GSI otherwise.
Return the result value as an ssa name tree.
Leave GSI at the same statement (GSI_SAME_STMT behavior).
Should only be used if target supports the needed optabs. See can_log2. */
static tree
gen_log2 (gimple_stmt_iterator *gsi, bool before, location_t loc, tree op)
{
/* Use .FFS (op) - 1. */
gimple *s = gsi->ptr;
tree type = TREE_TYPE (op);
gsi_iterator_update update = before ? GSI_SAME_STMT : GSI_NEW_STMT;
tree tmp1 = gimple_build (gsi, before, update, loc, IFN_FFS, type, op);
tree tmp2 = gimple_build (gsi, before, update, loc, MINUS_EXPR, type, tmp1,
build_one_cst (type));
gsi->ptr = s;
return tmp2;
}
/* Build a sequence of gimple statements checking that OP is a power of 2. Use
special optabs if targets supports them. Insert statements before GSI if
BEFORE is true or after GSI otherwise. Return the result value as a
boolean_type_node ssa name tree.
Leave GSI at the same statement (GSI_SAME_STMT behavior). */
static tree
gen_pow2p (gimple_stmt_iterator *gsi, bool before, location_t loc, tree op)
{
tree result;
/* Use either .POPCOUNT (op) == 1 or op & -op == op. */
tree type = TREE_TYPE (op);
gimple *s = gsi->ptr;
gsi_iterator_update update = before ? GSI_SAME_STMT : GSI_NEW_STMT;
optimization_type opt_type = bb_optimization_type (gsi->bb);
if (direct_internal_fn_supported_p (IFN_POPCOUNT, type, opt_type))
{
tree tmp = gimple_build (gsi, before, update, loc, IFN_POPCOUNT, type,
op);
result = gimple_build (gsi, before, update, loc, EQ_EXPR,
boolean_type_node, tmp, build_one_cst (type));
}
else
{
tree tmp1 = gimple_build (gsi, before, update, loc, NEGATE_EXPR, type,
op);
tree tmp2 = gimple_build (gsi, before, update, loc, BIT_AND_EXPR, type,
op, tmp1);
result = gimple_build (gsi, before, update, loc, EQ_EXPR,
boolean_type_node, tmp2, op);
}
gsi->ptr = s;
return result;
}
