On Thu, 11 Jul 2024, Filip Kastl wrote:
> > > > > +/* 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.
I think they are fine as-is. Other APIs like this chose to emit stmts
to a gimple_seq which the caller can then insert in the way of his
choosing.
Ideally we'd abstract this better in the infrastructure, like having
a insert-iterator that embeds both 'before' and update with the
insertion point. I guess the standard library would have a
insert_before_forward_iterator and insert_after_forward_iterator
and insert_before_backward_iterator, etc. ... Note that as you
emit a sequence of stmts their order is of course fixed, it's only
the sequence insertion that the caller should influence.
I think that GSI_CONTINUE_LINKING is what works for both before
and after insertion, I'm not sure your GSI_SAME_STMT use for before
is correct?
Richard.
> 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;
> }
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
