Re: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Wed, Aug 3, 2022 at 1:26 AM Richard Biener via Gcc-patches
wrote:
>
> On Wed, 3 Aug 2022, Tamar Christina wrote:
>
> >
> > > -Original Message-
> > > From: Richard Biener
> > > Sent: Tuesday, August 2, 2022 10:11 AM
> > > To: Tamar Christina
> > > Cc: Richard Biener ; ja...@redhat.com; nd
> > > ; gcc-patches@gcc.gnu.org
> > > Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way
> > > max/min.
> > >
> > > On Tue, Aug 2, 2022 at 10:33 AM Tamar Christina via Gcc-patches > > patc...@gcc.gnu.org> wrote:
> > > >
> > > > > > > > When this function replaces the edge it doesn't seem to update
> > > > > > > > the
> > > > > > > dominators.
> > > > > > > > Since It's replacing the middle BB we then end up with an
> > > > > > > > error
> > > > > > > >
> > > > > > > > gcc/testsuite/gcc.dg/tree-ssa/minmax-14.c:17:1: error:
> > > > > > > > dominator of 5 should be 4, not 2
> > > > > > > >
> > > > > > > > during early verify. So instead, I replace the BB but defer
> > > > > > > > its deletion until cleanup which removes it and updates the
> > > dominators.
> > > > > > >
> > > > > > > Hmm, for a diamond shouldn't you replace
> > > > > > >
> > > > > > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > > > > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > > > > > else
> > > > > > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > > > > >
> > > > > > > with
> > > > > > >
> > > > > > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > > > > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > > > > > else if (EDGE_SUCC (cond_block, 1)->dest == bb)
> > > > > > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > > > > >
> > > > > > > thus, the code expects to be left with a fallthru to the PHI
> > > > > > > block which is expected to have the immediate dominator being
> > > > > > > cond_block but with a diamond there's a (possibly empty) block
> > > > > > > inbetween and dominators are wrong.
> > > > > >
> > > > > > Agreed, but the (EDGE_SUCC (cond_block, 1)->dest == bb) doesn't
> > > > > > seem like the Right one since for a diamond there will be a block
> > > > > > in between the two. Did you perhaps mean EDGE_SUCC (EDGE_SUCC
> > > > > > (cond_block, 1)->dest, 0)->dest == bb? i.e. that that destination
> > > > > > across the
> > > > > diamond be bb, and then you remove the middle block?
> > > > >
> > > > > Hmm, I think my condition was correct - the code tries to remove the
> > > > > edge to the middle-block and checks the remaining edge falls through
> > > > > to the merge block. With a true diamond there is no fallthru to the
> > > > > merge block to keep so we better don't remove any edge?
> > > > >
> > > > > > For the minmax diamond we want both edges removed, since all the
> > > > > > code in the middle BBs are now dead. But this is probably not
> > > > > > true in the general
> > > > > sense.
> > > >
> > > > Ah! Sorry I was firing a few cylinders short, I get what you mean now:
> > > >
> > > > @@ -425,8 +439,19 @@ replace_phi_edge_with_variable (basic_block
> > > cond_block,
> > > >edge edge_to_remove;
> > > >if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > > - else
> > > > + else if (EDGE_SUCC (cond_block, 1)->dest == bb)
> > > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > > + else
> > > > +{
> > > > + /* If neither edge from the conditional is the final bb
> > > > +then we must have a diamond block, in which case
> > > > +the true edge was changed by SET_USE above and we must
> > > > +mark the other edge as the false edge. */
> > > > + gcond *cond =
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Wed, 3 Aug 2022, Tamar Christina wrote:
>
> > -Original Message-
> > From: Richard Biener
> > Sent: Tuesday, August 2, 2022 10:11 AM
> > To: Tamar Christina
> > Cc: Richard Biener ; ja...@redhat.com; nd
> > ; gcc-patches@gcc.gnu.org
> > Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way
> > max/min.
> >
> > On Tue, Aug 2, 2022 at 10:33 AM Tamar Christina via Gcc-patches > patc...@gcc.gnu.org> wrote:
> > >
> > > > > > > When this function replaces the edge it doesn't seem to update
> > > > > > > the
> > > > > > dominators.
> > > > > > > Since It's replacing the middle BB we then end up with an
> > > > > > > error
> > > > > > >
> > > > > > > gcc/testsuite/gcc.dg/tree-ssa/minmax-14.c:17:1: error:
> > > > > > > dominator of 5 should be 4, not 2
> > > > > > >
> > > > > > > during early verify. So instead, I replace the BB but defer
> > > > > > > its deletion until cleanup which removes it and updates the
> > dominators.
> > > > > >
> > > > > > Hmm, for a diamond shouldn't you replace
> > > > > >
> > > > > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > > > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > > > > else
> > > > > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > > > >
> > > > > > with
> > > > > >
> > > > > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > > > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > > > > else if (EDGE_SUCC (cond_block, 1)->dest == bb)
> > > > > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > > > >
> > > > > > thus, the code expects to be left with a fallthru to the PHI
> > > > > > block which is expected to have the immediate dominator being
> > > > > > cond_block but with a diamond there's a (possibly empty) block
> > > > > > inbetween and dominators are wrong.
> > > > >
> > > > > Agreed, but the (EDGE_SUCC (cond_block, 1)->dest == bb) doesn't
> > > > > seem like the Right one since for a diamond there will be a block
> > > > > in between the two. Did you perhaps mean EDGE_SUCC (EDGE_SUCC
> > > > > (cond_block, 1)->dest, 0)->dest == bb? i.e. that that destination
> > > > > across the
> > > > diamond be bb, and then you remove the middle block?
> > > >
> > > > Hmm, I think my condition was correct - the code tries to remove the
> > > > edge to the middle-block and checks the remaining edge falls through
> > > > to the merge block. With a true diamond there is no fallthru to the
> > > > merge block to keep so we better don't remove any edge?
> > > >
> > > > > For the minmax diamond we want both edges removed, since all the
> > > > > code in the middle BBs are now dead. But this is probably not
> > > > > true in the general
> > > > sense.
> > >
> > > Ah! Sorry I was firing a few cylinders short, I get what you mean now:
> > >
> > > @@ -425,8 +439,19 @@ replace_phi_edge_with_variable (basic_block
> > cond_block,
> > >edge edge_to_remove;
> > >if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > - else
> > > + else if (EDGE_SUCC (cond_block, 1)->dest == bb)
> > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > + else
> > > +{
> > > + /* If neither edge from the conditional is the final bb
> > > +then we must have a diamond block, in which case
> > > +the true edge was changed by SET_USE above and we must
> > > +mark the other edge as the false edge. */
> > > + gcond *cond = as_a (last_stmt (cond_block));
> > > + gimple_cond_make_false (cond);
> > > + return;
> > > +}
> > > +
> >
> > Note there is already
> >
> > if (EDGE_COUNT (edge_to_remove->dest->preds) == 1)
> > {
> > ...
> > }
> > else
> > {
> > /* If there are other edges into the middle block make
> > CFG cleanup deal with the edge
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
> -Original Message-
> From: Richard Biener
> Sent: Tuesday, August 2, 2022 10:11 AM
> To: Tamar Christina
> Cc: Richard Biener ; ja...@redhat.com; nd
> ; gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way
> max/min.
>
> On Tue, Aug 2, 2022 at 10:33 AM Tamar Christina via Gcc-patches patc...@gcc.gnu.org> wrote:
> >
> > > > > > When this function replaces the edge it doesn't seem to update
> > > > > > the
> > > > > dominators.
> > > > > > Since It's replacing the middle BB we then end up with an
> > > > > > error
> > > > > >
> > > > > > gcc/testsuite/gcc.dg/tree-ssa/minmax-14.c:17:1: error:
> > > > > > dominator of 5 should be 4, not 2
> > > > > >
> > > > > > during early verify. So instead, I replace the BB but defer
> > > > > > its deletion until cleanup which removes it and updates the
> dominators.
> > > > >
> > > > > Hmm, for a diamond shouldn't you replace
> > > > >
> > > > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > > > else
> > > > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > > >
> > > > > with
> > > > >
> > > > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > > > else if (EDGE_SUCC (cond_block, 1)->dest == bb)
> > > > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > > >
> > > > > thus, the code expects to be left with a fallthru to the PHI
> > > > > block which is expected to have the immediate dominator being
> > > > > cond_block but with a diamond there's a (possibly empty) block
> > > > > inbetween and dominators are wrong.
> > > >
> > > > Agreed, but the (EDGE_SUCC (cond_block, 1)->dest == bb) doesn't
> > > > seem like the Right one since for a diamond there will be a block
> > > > in between the two. Did you perhaps mean EDGE_SUCC (EDGE_SUCC
> > > > (cond_block, 1)->dest, 0)->dest == bb? i.e. that that destination
> > > > across the
> > > diamond be bb, and then you remove the middle block?
> > >
> > > Hmm, I think my condition was correct - the code tries to remove the
> > > edge to the middle-block and checks the remaining edge falls through
> > > to the merge block. With a true diamond there is no fallthru to the
> > > merge block to keep so we better don't remove any edge?
> > >
> > > > For the minmax diamond we want both edges removed, since all the
> > > > code in the middle BBs are now dead. But this is probably not
> > > > true in the general
> > > sense.
> >
> > Ah! Sorry I was firing a few cylinders short, I get what you mean now:
> >
> > @@ -425,8 +439,19 @@ replace_phi_edge_with_variable (basic_block
> cond_block,
> >edge edge_to_remove;
> >if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > - else
> > + else if (EDGE_SUCC (cond_block, 1)->dest == bb)
> > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > + else
> > +{
> > + /* If neither edge from the conditional is the final bb
> > +then we must have a diamond block, in which case
> > +the true edge was changed by SET_USE above and we must
> > +mark the other edge as the false edge. */
> > + gcond *cond = as_a (last_stmt (cond_block));
> > + gimple_cond_make_false (cond);
> > + return;
> > +}
> > +
>
> Note there is already
>
> if (EDGE_COUNT (edge_to_remove->dest->preds) == 1)
> {
> ...
> }
> else
> {
> /* If there are other edges into the middle block make
> CFG cleanup deal with the edge removal to avoid
> updating dominators here in a non-trivial way. */
> gcond *cond = as_a (last_stmt (cond_block));
> if (edge_to_remove->flags & EDGE_TRUE_VALUE)
> gimple_cond_make_false (cond);
> else
> gimple_cond_make_true (cond);
> }
>
> I'm not sure how you can say 'e' is always the true edge? May I suggest to
> amend the first condition with edge_to_remove && (and initialize that to
> NULL) and use e-&
Re: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Tue, Aug 2, 2022 at 10:33 AM Tamar Christina via Gcc-patches
wrote:
>
> > > > > When this function replaces the edge it doesn't seem to update the
> > > > dominators.
> > > > > Since It's replacing the middle BB we then end up with an error
> > > > >
> > > > > gcc/testsuite/gcc.dg/tree-ssa/minmax-14.c:17:1: error: dominator
> > > > > of 5 should be 4, not 2
> > > > >
> > > > > during early verify. So instead, I replace the BB but defer its
> > > > > deletion until cleanup which removes it and updates the dominators.
> > > >
> > > > Hmm, for a diamond shouldn't you replace
> > > >
> > > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > > else
> > > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > >
> > > > with
> > > >
> > > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > > else if (EDGE_SUCC (cond_block, 1)->dest == bb)
> > > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > >
> > > > thus, the code expects to be left with a fallthru to the PHI block
> > > > which is expected to have the immediate dominator being cond_block
> > > > but with a diamond there's a (possibly empty) block inbetween and
> > > > dominators are wrong.
> > >
> > > Agreed, but the (EDGE_SUCC (cond_block, 1)->dest == bb) doesn't seem
> > > like the Right one since for a diamond there will be a block in
> > > between the two. Did you perhaps mean EDGE_SUCC (EDGE_SUCC
> > > (cond_block, 1)->dest, 0)->dest == bb? i.e. that that destination across
> > > the
> > diamond be bb, and then you remove the middle block?
> >
> > Hmm, I think my condition was correct - the code tries to remove the edge to
> > the middle-block and checks the remaining edge falls through to the merge
> > block. With a true diamond there is no fallthru to the merge block to keep
> > so
> > we better don't remove any edge?
> >
> > > For the minmax diamond we want both edges removed, since all the code
> > > in the middle BBs are now dead. But this is probably not true in the
> > > general
> > sense.
>
> Ah! Sorry I was firing a few cylinders short, I get what you mean now:
>
> @@ -425,8 +439,19 @@ replace_phi_edge_with_variable (basic_block cond_block,
>edge edge_to_remove;
>if (EDGE_SUCC (cond_block, 0)->dest == bb)
> edge_to_remove = EDGE_SUCC (cond_block, 1);
> - else
> + else if (EDGE_SUCC (cond_block, 1)->dest == bb)
> edge_to_remove = EDGE_SUCC (cond_block, 0);
> + else
> +{
> + /* If neither edge from the conditional is the final bb
> +then we must have a diamond block, in which case
> +the true edge was changed by SET_USE above and we must
> +mark the other edge as the false edge. */
> + gcond *cond = as_a (last_stmt (cond_block));
> + gimple_cond_make_false (cond);
> + return;
> +}
> +
Note there is already
if (EDGE_COUNT (edge_to_remove->dest->preds) == 1)
{
...
}
else
{
/* If there are other edges into the middle block make
CFG cleanup deal with the edge removal to avoid
updating dominators here in a non-trivial way. */
gcond *cond = as_a (last_stmt (cond_block));
if (edge_to_remove->flags & EDGE_TRUE_VALUE)
gimple_cond_make_false (cond);
else
gimple_cond_make_true (cond);
}
I'm not sure how you can say 'e' is always the true edge? May I suggest
to amend the first condition with edge_to_remove && (and initialize that
to NULL) and use e->flags instead of edge_to_remove in the else,
of course also inverting the logic since we're keeping 'e'?
> Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
>
> Ok with this Change?
>
> Thanks,
> Tamar
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
> > > > When this function replaces the edge it doesn't seem to update the
> > > dominators.
> > > > Since It's replacing the middle BB we then end up with an error
> > > >
> > > > gcc/testsuite/gcc.dg/tree-ssa/minmax-14.c:17:1: error: dominator
> > > > of 5 should be 4, not 2
> > > >
> > > > during early verify. So instead, I replace the BB but defer its
> > > > deletion until cleanup which removes it and updates the dominators.
> > >
> > > Hmm, for a diamond shouldn't you replace
> > >
> > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > else
> > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > >
> > > with
> > >
> > > if (EDGE_SUCC (cond_block, 0)->dest == bb)
> > > edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > else if (EDGE_SUCC (cond_block, 1)->dest == bb)
> > > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > >
> > > thus, the code expects to be left with a fallthru to the PHI block
> > > which is expected to have the immediate dominator being cond_block
> > > but with a diamond there's a (possibly empty) block inbetween and
> > > dominators are wrong.
> >
> > Agreed, but the (EDGE_SUCC (cond_block, 1)->dest == bb) doesn't seem
> > like the Right one since for a diamond there will be a block in
> > between the two. Did you perhaps mean EDGE_SUCC (EDGE_SUCC
> > (cond_block, 1)->dest, 0)->dest == bb? i.e. that that destination across the
> diamond be bb, and then you remove the middle block?
>
> Hmm, I think my condition was correct - the code tries to remove the edge to
> the middle-block and checks the remaining edge falls through to the merge
> block. With a true diamond there is no fallthru to the merge block to keep so
> we better don't remove any edge?
>
> > For the minmax diamond we want both edges removed, since all the code
> > in the middle BBs are now dead. But this is probably not true in the
> > general
> sense.
Ah! Sorry I was firing a few cylinders short, I get what you mean now:
@@ -425,8 +439,19 @@ replace_phi_edge_with_variable (basic_block cond_block,
edge edge_to_remove;
if (EDGE_SUCC (cond_block, 0)->dest == bb)
edge_to_remove = EDGE_SUCC (cond_block, 1);
- else
+ else if (EDGE_SUCC (cond_block, 1)->dest == bb)
edge_to_remove = EDGE_SUCC (cond_block, 0);
+ else
+{
+ /* If neither edge from the conditional is the final bb
+then we must have a diamond block, in which case
+the true edge was changed by SET_USE above and we must
+mark the other edge as the false edge. */
+ gcond *cond = as_a (last_stmt (cond_block));
+ gimple_cond_make_false (cond);
+ return;
+}
+
Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
Ok with this Change?
Thanks,
Tamar
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Wed, 27 Jul 2022, Tamar Christina wrote:
> > -Original Message-
> > From: Richard Biener
> > Sent: Tuesday, July 12, 2022 2:19 PM
> > To: Tamar Christina
> > Cc: gcc-patches@gcc.gnu.org; nd ; ja...@redhat.com
> > Subject: RE: [PATCH 2/2]middle-end: Support recognition of three-way
> > max/min.
> >
> > On Tue, 5 Jul 2022, Tamar Christina wrote:
> >
> > > > > }
> > > > > + else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
> > > > > +&& single_succ_p (bb1)
> > > > > +&& single_succ_p (bb2)
> > > > > +&& single_pred_p (bb1)
> > > > > +&& single_pred_p (bb2)
> > > > > +&& single_succ_p (EDGE_SUCC (bb1, 0)->dest))
> > > >
> > > > please do the single_succ/pred checks below where appropriate, also
> > > > what's the last check about?
> > >
> > > Done.
> > >
> > > > why does the merge block need a single successor?
> > >
> > > I was using it to fix an ICE, but I realize that's not the right fix.
> > > I'm now checking If the BB is empty instead, in which case it's just a
> > > fall through edge so don't treat it as a diamond.
> > >
> > > >
> > > > > + {
> > > > > + gimple_stmt_iterator it1 = gsi_start_nondebug_after_labels_bb
> > > > (bb1);
> > > > > + gimple_stmt_iterator it2 = gsi_start_nondebug_after_labels_bb
> > > > (bb2);
> > > > > + if (gsi_one_before_end_p (it1) && gsi_one_before_end_p (it2))
> > > > > + {
> > > > > + gimple *stmt1 = gsi_stmt (it1);
> > > > > + gimple *stmt2 = gsi_stmt (it2);
> > > > > + if (is_gimple_assign (stmt1) && is_gimple_assign (stmt2))
> > > > > + {
> > > > > + enum tree_code code1 = gimple_assign_rhs_code (stmt1);
> > > > > + enum tree_code code2 = gimple_assign_rhs_code (stmt2);
> > > > > + diamond_minmax_p
> > > > > + = (code1 == MIN_EXPR || code1 == MAX_EXPR)
> > > > > + && (code2 == MIN_EXPR || code2 == MAX_EXPR);
> > > > > + }
> > > > > + }
> > > > > + }
> > > >
> > > > I'd generalize this to general diamond detection, simply cutting off
> > > > *_replacement workers that do not handle diamonds and do appropriate
> > > > checks in minmax_replacement only.
> > > >
> > >
> > > Done.
> > >
> > > > >else
> > > > > continue;
> > > > >
> > > > > @@ -316,6 +340,13 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > > > bool do_hoist_loads, bool early_p)
> > > > > if (!candorest)
> > > > > continue;
> > > > >
> > > > > + /* Check that we're looking for nested phis. */
> > > > > + if (phis == NULL && diamond_minmax_p)
> > > > > + {
> > > > > + phis = phi_nodes (EDGE_SUCC (bb2, 0)->dest);
> > > > > + e2 = EDGE_SUCC (bb2, 0);
> > > > > + }
> > > > > +
> > > >
> > > > instead
> > > >
> > > > basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest :
> > > > bb2;
> > > > gimple_seq phis = phi_nodes (merge);
> > > >
> > >
> > > Done.
> > >
> > > >
> > > > > phi = single_non_singleton_phi_for_edges (phis, e1, e2);
> > > > > if (!phi)
> > > > > continue;
> > > > > @@ -329,6 +360,7 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > > > > bool do_hoist_loads, bool early_p)
> > > > >
> > > > > gphi *newphi;
> > > > > if (single_pred_p (bb1)
> > > > > + && !diamond_minmax_p
> > > > > && (newphi = factor_out_conditional_conversion (e1, e2,
> > > > > phi,
> > > > > arg0,
> > > >
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
> -Original Message-
> From: Richard Biener
> Sent: Tuesday, July 12, 2022 2:19 PM
> To: Tamar Christina
> Cc: gcc-patches@gcc.gnu.org; nd ; ja...@redhat.com
> Subject: RE: [PATCH 2/2]middle-end: Support recognition of three-way
> max/min.
>
> On Tue, 5 Jul 2022, Tamar Christina wrote:
>
> > > > }
> > > > + else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
> > > > + && single_succ_p (bb1)
> > > > + && single_succ_p (bb2)
> > > > + && single_pred_p (bb1)
> > > > + && single_pred_p (bb2)
> > > > + && single_succ_p (EDGE_SUCC (bb1, 0)->dest))
> > >
> > > please do the single_succ/pred checks below where appropriate, also
> > > what's the last check about?
> >
> > Done.
> >
> > > why does the merge block need a single successor?
> >
> > I was using it to fix an ICE, but I realize that's not the right fix.
> > I'm now checking If the BB is empty instead, in which case it's just a
> > fall through edge so don't treat it as a diamond.
> >
> > >
> > > > + {
> > > > + gimple_stmt_iterator it1 = gsi_start_nondebug_after_labels_bb
> > > (bb1);
> > > > + gimple_stmt_iterator it2 = gsi_start_nondebug_after_labels_bb
> > > (bb2);
> > > > + if (gsi_one_before_end_p (it1) && gsi_one_before_end_p (it2))
> > > > + {
> > > > + gimple *stmt1 = gsi_stmt (it1);
> > > > + gimple *stmt2 = gsi_stmt (it2);
> > > > + if (is_gimple_assign (stmt1) && is_gimple_assign (stmt2))
> > > > + {
> > > > + enum tree_code code1 = gimple_assign_rhs_code (stmt1);
> > > > + enum tree_code code2 = gimple_assign_rhs_code (stmt2);
> > > > + diamond_minmax_p
> > > > + = (code1 == MIN_EXPR || code1 == MAX_EXPR)
> > > > + && (code2 == MIN_EXPR || code2 == MAX_EXPR);
> > > > + }
> > > > + }
> > > > + }
> > >
> > > I'd generalize this to general diamond detection, simply cutting off
> > > *_replacement workers that do not handle diamonds and do appropriate
> > > checks in minmax_replacement only.
> > >
> >
> > Done.
> >
> > > >else
> > > > continue;
> > > >
> > > > @@ -316,6 +340,13 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > > bool do_hoist_loads, bool early_p)
> > > > if (!candorest)
> > > > continue;
> > > >
> > > > + /* Check that we're looking for nested phis. */
> > > > + if (phis == NULL && diamond_minmax_p)
> > > > + {
> > > > + phis = phi_nodes (EDGE_SUCC (bb2, 0)->dest);
> > > > + e2 = EDGE_SUCC (bb2, 0);
> > > > + }
> > > > +
> > >
> > > instead
> > >
> > > basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
> > > gimple_seq phis = phi_nodes (merge);
> > >
> >
> > Done.
> >
> > >
> > > > phi = single_non_singleton_phi_for_edges (phis, e1, e2);
> > > > if (!phi)
> > > > continue;
> > > > @@ -329,6 +360,7 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > > > bool do_hoist_loads, bool early_p)
> > > >
> > > > gphi *newphi;
> > > > if (single_pred_p (bb1)
> > > > + && !diamond_minmax_p
> > > > && (newphi = factor_out_conditional_conversion (e1, e2,
> > > > phi,
> > > > arg0,
> > > > arg1,
> > > >
> > > > cond_stmt)))
> > > > @@ -343,20 +375,25 @@ tree_ssa_phiopt_worker (bool
> do_store_elim,
> > > bool do_hoist_loads, bool early_p)
> > > > }
> > > >
> > > > /* Do the replacement of conditional if it can be done. */
> > > > - if (!early_p && two_value_replacement (bb, bb1, e2, phi
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Tue, 5 Jul 2022, Tamar Christina wrote:
> > > }
> > > + else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
> > > +&& single_succ_p (bb1)
> > > +&& single_succ_p (bb2)
> > > +&& single_pred_p (bb1)
> > > +&& single_pred_p (bb2)
> > > +&& single_succ_p (EDGE_SUCC (bb1, 0)->dest))
> >
> > please do the single_succ/pred checks below where appropriate, also what's
> > the last check about?
>
> Done.
>
> > why does the merge block need a single successor?
>
> I was using it to fix an ICE, but I realize that's not the right fix. I'm now
> checking
> If the BB is empty instead, in which case it's just a fall through edge so
> don't
> treat it as a diamond.
>
> >
> > > + {
> > > + gimple_stmt_iterator it1 = gsi_start_nondebug_after_labels_bb
> > (bb1);
> > > + gimple_stmt_iterator it2 = gsi_start_nondebug_after_labels_bb
> > (bb2);
> > > + if (gsi_one_before_end_p (it1) && gsi_one_before_end_p (it2))
> > > + {
> > > + gimple *stmt1 = gsi_stmt (it1);
> > > + gimple *stmt2 = gsi_stmt (it2);
> > > + if (is_gimple_assign (stmt1) && is_gimple_assign (stmt2))
> > > + {
> > > + enum tree_code code1 = gimple_assign_rhs_code (stmt1);
> > > + enum tree_code code2 = gimple_assign_rhs_code (stmt2);
> > > + diamond_minmax_p
> > > + = (code1 == MIN_EXPR || code1 == MAX_EXPR)
> > > + && (code2 == MIN_EXPR || code2 == MAX_EXPR);
> > > + }
> > > + }
> > > + }
> >
> > I'd generalize this to general diamond detection, simply cutting off
> > *_replacement workers that do not handle diamonds and do appropriate
> > checks in minmax_replacement only.
> >
>
> Done.
>
> > >else
> > > continue;
> > >
> > > @@ -316,6 +340,13 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > bool do_hoist_loads, bool early_p)
> > > if (!candorest)
> > > continue;
> > >
> > > + /* Check that we're looking for nested phis. */
> > > + if (phis == NULL && diamond_minmax_p)
> > > + {
> > > + phis = phi_nodes (EDGE_SUCC (bb2, 0)->dest);
> > > + e2 = EDGE_SUCC (bb2, 0);
> > > + }
> > > +
> >
> > instead
> >
> > basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
> > gimple_seq phis = phi_nodes (merge);
> >
>
> Done.
>
> >
> > > phi = single_non_singleton_phi_for_edges (phis, e1, e2);
> > > if (!phi)
> > > continue;
> > > @@ -329,6 +360,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool
> > > do_hoist_loads, bool early_p)
> > >
> > > gphi *newphi;
> > > if (single_pred_p (bb1)
> > > + && !diamond_minmax_p
> > > && (newphi = factor_out_conditional_conversion (e1, e2, phi,
> > > arg0, arg1,
> > > cond_stmt)))
> > > @@ -343,20 +375,25 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > bool do_hoist_loads, bool early_p)
> > > }
> > >
> > > /* Do the replacement of conditional if it can be done. */
> > > - if (!early_p && two_value_replacement (bb, bb1, e2, phi, arg0,
> > arg1))
> > > + if (!early_p
> > > + && !diamond_minmax_p
> > > + && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
> > > cfgchanged = true;
> > > - else if (match_simplify_replacement (bb, bb1, e1, e2, phi,
> > > -arg0, arg1,
> > > -early_p))
> > > + else if (!diamond_minmax_p
> > > +&& match_simplify_replacement (bb, bb1, e1, e2, phi,
> > > + arg0, arg1, early_p))
> > > cfgchanged = true;
> > > else if (!early_p
> > > +&& !diamond_minmax_p
> > > && single_pred_p (bb1)
> > > && cond_removal_in_builtin_zero_pattern (bb, bb1, e1,
> > e2,
> > > phi, arg0, arg1))
> > > cfgchanged = true;
> > > - else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
> > > + else if (minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1,
> > > +diamond_minmax_p))
> > > cfgchanged = true;
> > > else if (single_pred_p (bb1)
> > > +&& !diamond_minmax_p
> > > && spaceship_replacement (bb, bb1, e1, e2, phi, arg0,
> > arg1))
> > > cfgchanged = true;
> > > }
> > > @@ -385,7 +422,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool
> > > do_hoist_loads, bool early_p)
> > >
> > > static void
> > > replace_phi_edge_with_variable (basic_block cond_block,
> > > - edge e, gphi *phi, tree new_tree)
> > > + edge e, gphi *phi, tree new_tree, bool
> > delete_bb = true)
> > > {
> > >basic_block bb = gimple_bb (phi);
> > >gimple_stmt_iterator gsi;
> > > @@ -428,7 +465,7 @@ replace_phi_edge_with_variable
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
ping
> -Original Message-
> From: Tamar Christina
> Sent: Tuesday, July 5, 2022 4:26 PM
> To: Richard Biener
> Cc: gcc-patches@gcc.gnu.org; nd ; ja...@redhat.com
> Subject: RE: [PATCH 2/2]middle-end: Support recognition of three-way
> max/min.
>
> > > }
> > > + else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
> > > +&& single_succ_p (bb1)
> > > +&& single_succ_p (bb2)
> > > +&& single_pred_p (bb1)
> > > +&& single_pred_p (bb2)
> > > +&& single_succ_p (EDGE_SUCC (bb1, 0)->dest))
> >
> > please do the single_succ/pred checks below where appropriate, also
> > what's the last check about?
>
> Done.
>
> > why does the merge block need a single successor?
>
> I was using it to fix an ICE, but I realize that's not the right fix. I'm now
> checking If the BB is empty instead, in which case it's just a fall through
> edge
> so don't treat it as a diamond.
>
> >
> > > + {
> > > + gimple_stmt_iterator it1 = gsi_start_nondebug_after_labels_bb
> > (bb1);
> > > + gimple_stmt_iterator it2 = gsi_start_nondebug_after_labels_bb
> > (bb2);
> > > + if (gsi_one_before_end_p (it1) && gsi_one_before_end_p (it2))
> > > + {
> > > + gimple *stmt1 = gsi_stmt (it1);
> > > + gimple *stmt2 = gsi_stmt (it2);
> > > + if (is_gimple_assign (stmt1) && is_gimple_assign (stmt2))
> > > + {
> > > + enum tree_code code1 = gimple_assign_rhs_code (stmt1);
> > > + enum tree_code code2 = gimple_assign_rhs_code (stmt2);
> > > + diamond_minmax_p
> > > + = (code1 == MIN_EXPR || code1 == MAX_EXPR)
> > > + && (code2 == MIN_EXPR || code2 == MAX_EXPR);
> > > + }
> > > + }
> > > + }
> >
> > I'd generalize this to general diamond detection, simply cutting off
> > *_replacement workers that do not handle diamonds and do appropriate
> > checks in minmax_replacement only.
> >
>
> Done.
>
> > >else
> > > continue;
> > >
> > > @@ -316,6 +340,13 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > bool do_hoist_loads, bool early_p)
> > > if (!candorest)
> > > continue;
> > >
> > > + /* Check that we're looking for nested phis. */
> > > + if (phis == NULL && diamond_minmax_p)
> > > + {
> > > + phis = phi_nodes (EDGE_SUCC (bb2, 0)->dest);
> > > + e2 = EDGE_SUCC (bb2, 0);
> > > + }
> > > +
> >
> > instead
> >
> > basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
> > gimple_seq phis = phi_nodes (merge);
> >
>
> Done.
>
> >
> > > phi = single_non_singleton_phi_for_edges (phis, e1, e2);
> > > if (!phi)
> > > continue;
> > > @@ -329,6 +360,7 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> bool
> > > do_hoist_loads, bool early_p)
> > >
> > > gphi *newphi;
> > > if (single_pred_p (bb1)
> > > + && !diamond_minmax_p
> > > && (newphi = factor_out_conditional_conversion (e1, e2, phi,
> > > arg0, arg1,
> > > cond_stmt)))
> > > @@ -343,20 +375,25 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > bool do_hoist_loads, bool early_p)
> > > }
> > >
> > > /* Do the replacement of conditional if it can be done. */
> > > - if (!early_p && two_value_replacement (bb, bb1, e2, phi, arg0,
> > arg1))
> > > + if (!early_p
> > > + && !diamond_minmax_p
> > > + && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
> > > cfgchanged = true;
> > > - else if (match_simplify_replacement (bb, bb1, e1, e2, phi,
> > > -arg0, arg1,
> > > -early_p))
> > > + else if (!diamond_minmax_p
> > > +&& match_simplify_replacement (bb, bb1, e1, e2, phi,
> > > + arg0, arg1, early_p))
> > > cfgchanged = true;
> > > else if (!early_p
> > > +&& !diamond_minmax_p
> > >
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
> > }
> > + else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
> > + && single_succ_p (bb1)
> > + && single_succ_p (bb2)
> > + && single_pred_p (bb1)
> > + && single_pred_p (bb2)
> > + && single_succ_p (EDGE_SUCC (bb1, 0)->dest))
>
> please do the single_succ/pred checks below where appropriate, also what's
> the last check about?
Done.
> why does the merge block need a single successor?
I was using it to fix an ICE, but I realize that's not the right fix. I'm now
checking
If the BB is empty instead, in which case it's just a fall through edge so don't
treat it as a diamond.
>
> > + {
> > + gimple_stmt_iterator it1 = gsi_start_nondebug_after_labels_bb
> (bb1);
> > + gimple_stmt_iterator it2 = gsi_start_nondebug_after_labels_bb
> (bb2);
> > + if (gsi_one_before_end_p (it1) && gsi_one_before_end_p (it2))
> > + {
> > + gimple *stmt1 = gsi_stmt (it1);
> > + gimple *stmt2 = gsi_stmt (it2);
> > + if (is_gimple_assign (stmt1) && is_gimple_assign (stmt2))
> > + {
> > + enum tree_code code1 = gimple_assign_rhs_code (stmt1);
> > + enum tree_code code2 = gimple_assign_rhs_code (stmt2);
> > + diamond_minmax_p
> > + = (code1 == MIN_EXPR || code1 == MAX_EXPR)
> > + && (code2 == MIN_EXPR || code2 == MAX_EXPR);
> > + }
> > + }
> > + }
>
> I'd generalize this to general diamond detection, simply cutting off
> *_replacement workers that do not handle diamonds and do appropriate
> checks in minmax_replacement only.
>
Done.
> >else
> > continue;
> >
> > @@ -316,6 +340,13 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> bool do_hoist_loads, bool early_p)
> > if (!candorest)
> > continue;
> >
> > + /* Check that we're looking for nested phis. */
> > + if (phis == NULL && diamond_minmax_p)
> > + {
> > + phis = phi_nodes (EDGE_SUCC (bb2, 0)->dest);
> > + e2 = EDGE_SUCC (bb2, 0);
> > + }
> > +
>
> instead
>
> basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
> gimple_seq phis = phi_nodes (merge);
>
Done.
>
> > phi = single_non_singleton_phi_for_edges (phis, e1, e2);
> > if (!phi)
> > continue;
> > @@ -329,6 +360,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool
> > do_hoist_loads, bool early_p)
> >
> > gphi *newphi;
> > if (single_pred_p (bb1)
> > + && !diamond_minmax_p
> > && (newphi = factor_out_conditional_conversion (e1, e2, phi,
> > arg0, arg1,
> > cond_stmt)))
> > @@ -343,20 +375,25 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> bool do_hoist_loads, bool early_p)
> > }
> >
> > /* Do the replacement of conditional if it can be done. */
> > - if (!early_p && two_value_replacement (bb, bb1, e2, phi, arg0,
> arg1))
> > + if (!early_p
> > + && !diamond_minmax_p
> > + && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
> > cfgchanged = true;
> > - else if (match_simplify_replacement (bb, bb1, e1, e2, phi,
> > - arg0, arg1,
> > - early_p))
> > + else if (!diamond_minmax_p
> > + && match_simplify_replacement (bb, bb1, e1, e2, phi,
> > + arg0, arg1, early_p))
> > cfgchanged = true;
> > else if (!early_p
> > + && !diamond_minmax_p
> >&& single_pred_p (bb1)
> >&& cond_removal_in_builtin_zero_pattern (bb, bb1, e1,
> e2,
> > phi, arg0, arg1))
> > cfgchanged = true;
> > - else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
> > + else if (minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1,
> > + diamond_minmax_p))
> > cfgchanged = true;
> > else if (single_pred_p (bb1)
> > + && !diamond_minmax_p
> >&& spaceship_replacement (bb, bb1, e1, e2, phi, arg0,
> arg1))
> > cfgchanged = true;
> > }
> > @@ -385,7 +422,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool
> > do_hoist_loads, bool early_p)
> >
> > static void
> > replace_phi_edge_with_variable (basic_block cond_block,
> > - edge e, gphi *phi, tree new_tree)
> > + edge e, gphi *phi, tree new_tree, bool
> delete_bb = true)
> > {
> >basic_block bb = gimple_bb (phi);
> >gimple_stmt_iterator gsi;
> > @@ -428,7 +465,7 @@ replace_phi_edge_with_variable (basic_block
> cond_block,
> > edge_to_remove = EDGE_SUCC (cond_block, 1);
> >else
> > edge_to_remove = EDGE_SUCC (cond_block, 0);
> > - if (EDGE_COUNT
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Tue, 21 Jun 2022, Tamar Christina wrote:
> > -Original Message-
> > From: Richard Biener
> > Sent: Tuesday, June 21, 2022 2:15 PM
> > To: Tamar Christina
> > Cc: gcc-patches@gcc.gnu.org; nd ; ja...@redhat.com
> > Subject: RE: [PATCH 2/2]middle-end: Support recognition of three-way
> > max/min.
> >
> > On Mon, 20 Jun 2022, Tamar Christina wrote:
> >
> > > > -Original Message-
> > > > From: Richard Biener
> > > > Sent: Monday, June 20, 2022 9:36 AM
> > > > To: Tamar Christina
> > > > Cc: gcc-patches@gcc.gnu.org; nd ; ja...@redhat.com
> > > > Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way
> > > > max/min.
> > > >
> > > > On Thu, 16 Jun 2022, Tamar Christina wrote:
> > > >
> > > > > Hi All,
> > > > >
> > > > > This patch adds support for three-way min/max recognition in phi-opts.
> > > > >
> > > > > Concretely for e.g.
> > > > >
> > > > > #include
> > > > >
> > > > > uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > > > uint8_t xk;
> > > > > if (xc < xm) {
> > > > > xk = (uint8_t) (xc < xy ? xc : xy);
> > > > > } else {
> > > > > xk = (uint8_t) (xm < xy ? xm : xy);
> > > > > }
> > > > > return xk;
> > > > > }
> > > > >
> > > > > we generate:
> > > > >
> > > > >[local count: 1073741824]:
> > > > > _5 = MIN_EXPR ;
> > > > > _7 = MIN_EXPR ;
> > > > > return _7;
> > > > >
> > > > > instead of
> > > > >
> > > > > :
> > > > > if (xc_2(D) < xm_3(D))
> > > > > goto ;
> > > > > else
> > > > > goto ;
> > > > >
> > > > > :
> > > > > xk_5 = MIN_EXPR ;
> > > > > goto ;
> > > > >
> > > > > :
> > > > > xk_6 = MIN_EXPR ;
> > > > >
> > > > > :
> > > > > # xk_1 = PHI
> > > > > return xk_1;
> > > > >
> > > > > The same function also immediately deals with turning a
> > > > > minimization problem into a maximization one if the results are
> > > > > inverted. We do this here since doing it in match.pd would end up
> > > > > changing the shape of the BBs and adding additional instructions
> > > > > which would prevent various
> > > > optimizations from working.
> > > >
> > > > Can you explain a bit more?
> > >
> > > I'll respond to this one first In case it changes how you want me to
> > > proceed.
> > >
> > > I initially had used a match.pd rule to do the min to max conversion,
> > > but a number of testcases started to fail. The reason was that a lot
> > > of the foldings checked that the BB contains only a single SSA and that
> > > that
> > SSA is a phi node.
> > >
> > > By changing the min into max, the negation of the result ends up In
> > > the same BB and so the optimizations are skipped leading to less optimal
> > code.
> > >
> > > I did look into relaxing those phi opts but it felt like I'd make a
> > > rather arbitrary exception for minus and seemed better to handle it in the
> > minmax folding.
> >
> > That's a possibility but we try to maintain a single place for a transform
> > which
> > might be in match.pd which would then also handle this when there's a RHS
> > COND_EXPR connecting the stmts rather than a PHI node.
>
> Sorry, I am probably missing something here. Just to be clear at the moment
> I just do it all in
> minmax_replacement, so everything is already in one place. It's a simple
> extension of the code
> already there.
>
> Are you suggesting I have to move it all to match.pd? That's non-trivial..
I was hoping Andrew was going to respond with an estimate as to how
far he is along moving the minmax replacement to match.pd.
I'm just after less overall work. But then improving minmax_replacement
is OK (see my comments on the actual patch), it just will make the
match.pd attempt more complex because of the need to handle diamonds.
Richard.
> Thanks,
> Tamar
>
> >
> > Richard.
>
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
> -Original Message-
> From: Richard Biener
> Sent: Tuesday, June 21, 2022 2:15 PM
> To: Tamar Christina
> Cc: gcc-patches@gcc.gnu.org; nd ; ja...@redhat.com
> Subject: RE: [PATCH 2/2]middle-end: Support recognition of three-way
> max/min.
>
> On Mon, 20 Jun 2022, Tamar Christina wrote:
>
> > > -Original Message-
> > > From: Richard Biener
> > > Sent: Monday, June 20, 2022 9:36 AM
> > > To: Tamar Christina
> > > Cc: gcc-patches@gcc.gnu.org; nd ; ja...@redhat.com
> > > Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way
> > > max/min.
> > >
> > > On Thu, 16 Jun 2022, Tamar Christina wrote:
> > >
> > > > Hi All,
> > > >
> > > > This patch adds support for three-way min/max recognition in phi-opts.
> > > >
> > > > Concretely for e.g.
> > > >
> > > > #include
> > > >
> > > > uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > > uint8_t xk;
> > > > if (xc < xm) {
> > > > xk = (uint8_t) (xc < xy ? xc : xy);
> > > > } else {
> > > > xk = (uint8_t) (xm < xy ? xm : xy);
> > > > }
> > > > return xk;
> > > > }
> > > >
> > > > we generate:
> > > >
> > > >[local count: 1073741824]:
> > > > _5 = MIN_EXPR ;
> > > > _7 = MIN_EXPR ;
> > > > return _7;
> > > >
> > > > instead of
> > > >
> > > > :
> > > > if (xc_2(D) < xm_3(D))
> > > > goto ;
> > > > else
> > > > goto ;
> > > >
> > > > :
> > > > xk_5 = MIN_EXPR ;
> > > > goto ;
> > > >
> > > > :
> > > > xk_6 = MIN_EXPR ;
> > > >
> > > > :
> > > > # xk_1 = PHI
> > > > return xk_1;
> > > >
> > > > The same function also immediately deals with turning a
> > > > minimization problem into a maximization one if the results are
> > > > inverted. We do this here since doing it in match.pd would end up
> > > > changing the shape of the BBs and adding additional instructions
> > > > which would prevent various
> > > optimizations from working.
> > >
> > > Can you explain a bit more?
> >
> > I'll respond to this one first In case it changes how you want me to
> > proceed.
> >
> > I initially had used a match.pd rule to do the min to max conversion,
> > but a number of testcases started to fail. The reason was that a lot
> > of the foldings checked that the BB contains only a single SSA and that that
> SSA is a phi node.
> >
> > By changing the min into max, the negation of the result ends up In
> > the same BB and so the optimizations are skipped leading to less optimal
> code.
> >
> > I did look into relaxing those phi opts but it felt like I'd make a
> > rather arbitrary exception for minus and seemed better to handle it in the
> minmax folding.
>
> That's a possibility but we try to maintain a single place for a transform
> which
> might be in match.pd which would then also handle this when there's a RHS
> COND_EXPR connecting the stmts rather than a PHI node.
Sorry, I am probably missing something here. Just to be clear at the moment I
just do it all in
minmax_replacement, so everything is already in one place. It's a simple
extension of the code
already there.
Are you suggesting I have to move it all to match.pd? That's non-trivial..
Thanks,
Tamar
>
> Richard.
>
> > Thanks,
> > Tamar
> >
> > >
> > > > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
> > > >
> > > > Ok for master?
> > > >
> > > > Thanks,
> > > > Tamar
> > > >
> > > > gcc/ChangeLog:
> > > >
> > > > * tree-ssa-phiopt.cc (minmax_replacement): Optionally search for
> > > the phi
> > > > sequence of a three-way conditional.
> > > > (replace_phi_edge_with_variable): Support deferring of BB
> > > > removal.
> > > > (tree_ssa_phiopt_worker): Detect diamond phi structure for
> > > > three-
> > > way
> > > > min/max.
> > > > (strip_bit_not, invert_minmax_code): New.
> > > >
> > > > gcc/testsuite/ChangeL
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Mon, 20 Jun 2022, Tamar Christina wrote:
> > -Original Message-
> > From: Richard Biener
> > Sent: Monday, June 20, 2022 9:36 AM
> > To: Tamar Christina
> > Cc: gcc-patches@gcc.gnu.org; nd ; ja...@redhat.com
> > Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way
> > max/min.
> >
> > On Thu, 16 Jun 2022, Tamar Christina wrote:
> >
> > > Hi All,
> > >
> > > This patch adds support for three-way min/max recognition in phi-opts.
> > >
> > > Concretely for e.g.
> > >
> > > #include
> > >
> > > uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > uint8_t xk;
> > > if (xc < xm) {
> > > xk = (uint8_t) (xc < xy ? xc : xy);
> > > } else {
> > > xk = (uint8_t) (xm < xy ? xm : xy);
> > > }
> > > return xk;
> > > }
> > >
> > > we generate:
> > >
> > >[local count: 1073741824]:
> > > _5 = MIN_EXPR ;
> > > _7 = MIN_EXPR ;
> > > return _7;
> > >
> > > instead of
> > >
> > > :
> > > if (xc_2(D) < xm_3(D))
> > > goto ;
> > > else
> > > goto ;
> > >
> > > :
> > > xk_5 = MIN_EXPR ;
> > > goto ;
> > >
> > > :
> > > xk_6 = MIN_EXPR ;
> > >
> > > :
> > > # xk_1 = PHI
> > > return xk_1;
> > >
> > > The same function also immediately deals with turning a minimization
> > > problem into a maximization one if the results are inverted. We do
> > > this here since doing it in match.pd would end up changing the shape
> > > of the BBs and adding additional instructions which would prevent various
> > optimizations from working.
> >
> > Can you explain a bit more?
>
> I'll respond to this one first In case it changes how you want me to proceed.
>
> I initially had used a match.pd rule to do the min to max conversion, but a
> number of testcases started to fail. The reason was that a lot of the
> foldings
> checked that the BB contains only a single SSA and that that SSA is a phi
> node.
>
> By changing the min into max, the negation of the result ends up In the same
> BB
> and so the optimizations are skipped leading to less optimal code.
>
> I did look into relaxing those phi opts but it felt like I'd make a rather
> arbitrary
> exception for minus and seemed better to handle it in the minmax folding.
That's a possibility but we try to maintain a single place for a transform
which might be in match.pd which would then also handle this when
there's a RHS COND_EXPR connecting the stmts rather than a PHI node.
Richard.
> Thanks,
> Tamar
>
> >
> > > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
> > >
> > > Ok for master?
> > >
> > > Thanks,
> > > Tamar
> > >
> > > gcc/ChangeLog:
> > >
> > > * tree-ssa-phiopt.cc (minmax_replacement): Optionally search for
> > the phi
> > > sequence of a three-way conditional.
> > > (replace_phi_edge_with_variable): Support deferring of BB removal.
> > > (tree_ssa_phiopt_worker): Detect diamond phi structure for three-
> > way
> > > min/max.
> > > (strip_bit_not, invert_minmax_code): New.
> > >
> > > gcc/testsuite/ChangeLog:
> > >
> > > * gcc.dg/tree-ssa/split-path-1.c: Disable phi-opts so we don't
> > optimize
> > > code away.
> > > * gcc.dg/tree-ssa/minmax-3.c: New test.
> > > * gcc.dg/tree-ssa/minmax-4.c: New test.
> > > * gcc.dg/tree-ssa/minmax-5.c: New test.
> > > * gcc.dg/tree-ssa/minmax-6.c: New test.
> > > * gcc.dg/tree-ssa/minmax-7.c: New test.
> > > * gcc.dg/tree-ssa/minmax-8.c: New test.
> > >
> > > --- inline copy of patch --
> > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > > new file mode 100644
> > > index
> > >
> > ..de3b2e946e81701e3b75f580e
> > 6a8
> > > 43695a05786e
> > > --- /dev/null
> > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > > @@ -0,0 +1,17 @@
> > > +/* { dg-do compile } */
> > > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > > +
> > > +#include
> > > +
> > > +uint8_t three_min (uint8_t xc,
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
> -Original Message-
> From: Andrew Pinski
> Sent: Tuesday, June 21, 2022 12:16 AM
> To: Tamar Christina
> Cc: GCC Patches ; Jakub Jelinek
> ; nd ; Richard Guenther
>
> Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way
> max/min.
>
> On Thu, Jun 16, 2022 at 4:11 AM Tamar Christina via Gcc-patches patc...@gcc.gnu.org> wrote:
> >
> > Hi All,
> >
> > This patch adds support for three-way min/max recognition in phi-opts.
> >
> > Concretely for e.g.
> >
> > #include
> >
> > uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > uint8_t xk;
> > if (xc < xm) {
> > xk = (uint8_t) (xc < xy ? xc : xy);
> > } else {
> > xk = (uint8_t) (xm < xy ? xm : xy);
> > }
> > return xk;
> > }
> >
> > we generate:
> >
> >[local count: 1073741824]:
> > _5 = MIN_EXPR ;
> > _7 = MIN_EXPR ;
> > return _7;
> >
> > instead of
> >
> > :
> > if (xc_2(D) < xm_3(D))
> > goto ;
> > else
> > goto ;
> >
> > :
> > xk_5 = MIN_EXPR ;
> > goto ;
> >
> > :
> > xk_6 = MIN_EXPR ;
> >
> > :
> > # xk_1 = PHI
> > return xk_1;
> >
> > The same function also immediately deals with turning a minimization
> > problem into a maximization one if the results are inverted. We do
> > this here since doing it in match.pd would end up changing the shape
> > of the BBs and adding additional instructions which would prevent various
> optimizations from working.
> >
> > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
> >
> > Ok for master?
> >
> > Thanks,
> > Tamar
> >
> > gcc/ChangeLog:
> >
> > * tree-ssa-phiopt.cc (minmax_replacement): Optionally search for the
> phi
> > sequence of a three-way conditional.
> > (replace_phi_edge_with_variable): Support deferring of BB removal.
> > (tree_ssa_phiopt_worker): Detect diamond phi structure for three-
> way
> > min/max.
> > (strip_bit_not, invert_minmax_code): New.
>
> I have been working on getting rid of minmax_replacement and a few others
> and only having match_simplify_replacement and having the simplification
> logic all in match.pd instead.
> Is there a reason why you can't expand match_simplify_replacement and
> match.pd?
Because this is just a simple extension of minmax_replacement which just adds
a third case but re-uses all the validation and normalization code already
present
in the pass.
>
> >The reason was that a lot of the foldings checked that the BB contains
> >only a single SSA and that that SSA is a phi node.
>
> Could you expand on that?
Passes that call last_and_only_stmt break because you push an extra statement
into the BB. The phi node is then no longer the last and only statement.
From the top of my head, ssa-spit-path is one that started giving some failures
in the testsuite because of this.
Tamar
>
> Thanks,
> Andrew
>
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.dg/tree-ssa/split-path-1.c: Disable phi-opts so we don't
> > optimize
> > code away.
> > * gcc.dg/tree-ssa/minmax-3.c: New test.
> > * gcc.dg/tree-ssa/minmax-4.c: New test.
> > * gcc.dg/tree-ssa/minmax-5.c: New test.
> > * gcc.dg/tree-ssa/minmax-6.c: New test.
> > * gcc.dg/tree-ssa/minmax-7.c: New test.
> > * gcc.dg/tree-ssa/minmax-8.c: New test.
> >
> > --- inline copy of patch --
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > new file mode 100644
> > index
> >
> ..de3b2e946e81701e3b75f580e
> 6a8
> > 43695a05786e
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > @@ -0,0 +1,17 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > +
> > +#include
> > +
> > +uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > + uint8_t xk;
> > +if (xc < xm) {
> > +xk = (uint8_t) (xc < xy ? xc : xy);
> > +} else {
> > +xk = (uint8_t) (xm < xy ? xm : xy);
> > +}
> > +return xk;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 3 "phiopt1" } } */
> > +/* { dg-final { scan-tree-dump-times "MAX_EXPR
Re: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Mon, 20 Jun 2022, Andrew Pinski wrote:
> On Thu, Jun 16, 2022 at 4:11 AM Tamar Christina via Gcc-patches
> wrote:
> >
> > Hi All,
> >
> > This patch adds support for three-way min/max recognition in phi-opts.
> >
> > Concretely for e.g.
> >
> > #include
> >
> > uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > uint8_t xk;
> > if (xc < xm) {
> > xk = (uint8_t) (xc < xy ? xc : xy);
> > } else {
> > xk = (uint8_t) (xm < xy ? xm : xy);
> > }
> > return xk;
> > }
> >
> > we generate:
> >
> >[local count: 1073741824]:
> > _5 = MIN_EXPR ;
> > _7 = MIN_EXPR ;
> > return _7;
> >
> > instead of
> >
> > :
> > if (xc_2(D) < xm_3(D))
> > goto ;
> > else
> > goto ;
> >
> > :
> > xk_5 = MIN_EXPR ;
> > goto ;
> >
> > :
> > xk_6 = MIN_EXPR ;
> >
> > :
> > # xk_1 = PHI
> > return xk_1;
> >
> > The same function also immediately deals with turning a minimization problem
> > into a maximization one if the results are inverted. We do this here since
> > doing it in match.pd would end up changing the shape of the BBs and adding
> > additional instructions which would prevent various optimizations from
> > working.
> >
> > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
> >
> > Ok for master?
> >
> > Thanks,
> > Tamar
> >
> > gcc/ChangeLog:
> >
> > * tree-ssa-phiopt.cc (minmax_replacement): Optionally search for
> > the phi
> > sequence of a three-way conditional.
> > (replace_phi_edge_with_variable): Support deferring of BB removal.
> > (tree_ssa_phiopt_worker): Detect diamond phi structure for three-way
> > min/max.
> > (strip_bit_not, invert_minmax_code): New.
>
> I have been working on getting rid of minmax_replacement and a few
> others and only having match_simplify_replacement and having the
> simplification logic all in match.pd instead.
> Is there a reason why you can't expand match_simplify_replacement and
> match.pd?
Btw, I have the below change pending to remove GENERIC comparison op
handling from GIMPLE matching. I don't yet like the phi-op part very
much which is why I didn't push that yet.
Maybe you can take that into account when extending
match_simplify_replacement... (and maybe you have a nicer idea)
Richard.
>From 5c2428227e2fbfde72244dbc4aabeecf70c763ed Mon Sep 17 00:00:00 2001
From: Richard Biener
Date: Tue, 17 May 2022 09:58:59 +0200
Subject: [PATCH] Remove genmatch GENERIC condition in COND_EXPR support
To: gcc-patches@gcc.gnu.org
The following removes support for matching a GENERIC condition
in COND_EXPRs when doing GIMPLE matching. Thus cuts 5% of the
size of gimple-match.cc.
Unfortunately it makes phiopt a bit more awkward since the
COND_EXPRs it tries to simplify no longer fit the single
gimple_match_op but instead the comparison now needs to be
separately built. That also means it is emitted and we have
to avoid leaving it around when it is not actually used by
the simplification to make the cascading transforms work.
Handling insertion only of the used parts of a sequence as
produced by simplification or stmt build and simplification
is something that asks to be separated out in a convenient
way and I have to think on how to best do this still.
2022-05-17 Richard Biener
* genmatch.cc ():
* gimple-match.head.cc ():
* tree-ssa-phiopt.cc ():
---
gcc/genmatch.cc | 140 +++
gcc/gimple-match-head.cc | 61 +++--
gcc/tree-ssa-phiopt.cc | 45 ++---
3 files changed, 57 insertions(+), 189 deletions(-)
diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 2b84b849330..5fbe5aa28b3 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -697,12 +697,12 @@ public:
expr (id_base *operation_, location_t loc, bool is_commutative_ = false)
: operand (OP_EXPR, loc), operation (operation_),
ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
- is_generic (false), force_single_use (false), force_leaf (false),
+ force_single_use (false), force_leaf (false),
opt_grp (0) {}
expr (expr *e)
: operand (OP_EXPR, e->location), operation (e->operation),
ops (vNULL), expr_type (e->expr_type), is_commutative
(e->is_commutative),
- is_generic (e->is_generic), force_single_use (e->force_single_use),
+ force_single_use (e->force_single_use),
force_leaf (e->force_leaf), opt_grp (e->opt_grp) {}
void append_op (operand *op) { ops.safe_push (op); }
/* The operator and its operands. */
@@ -713,8 +713,6 @@ public:
/* Whether the operation is to be applied commutatively. This is
later lowered to two separate patterns. */
bool is_commutative;
- /* Whether the expression is expected to be in GENERIC form. */
- bool is_generic;
/* Whether pushing any stmt to the sequence should be conditional
on this expression having a single-use. */
bool force_single_use;
Re: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Thu, Jun 16, 2022 at 4:11 AM Tamar Christina via Gcc-patches
wrote:
>
> Hi All,
>
> This patch adds support for three-way min/max recognition in phi-opts.
>
> Concretely for e.g.
>
> #include
>
> uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> uint8_t xk;
> if (xc < xm) {
> xk = (uint8_t) (xc < xy ? xc : xy);
> } else {
> xk = (uint8_t) (xm < xy ? xm : xy);
> }
> return xk;
> }
>
> we generate:
>
>[local count: 1073741824]:
> _5 = MIN_EXPR ;
> _7 = MIN_EXPR ;
> return _7;
>
> instead of
>
> :
> if (xc_2(D) < xm_3(D))
> goto ;
> else
> goto ;
>
> :
> xk_5 = MIN_EXPR ;
> goto ;
>
> :
> xk_6 = MIN_EXPR ;
>
> :
> # xk_1 = PHI
> return xk_1;
>
> The same function also immediately deals with turning a minimization problem
> into a maximization one if the results are inverted. We do this here since
> doing it in match.pd would end up changing the shape of the BBs and adding
> additional instructions which would prevent various optimizations from
> working.
>
> Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
>
> Ok for master?
>
> Thanks,
> Tamar
>
> gcc/ChangeLog:
>
> * tree-ssa-phiopt.cc (minmax_replacement): Optionally search for the
> phi
> sequence of a three-way conditional.
> (replace_phi_edge_with_variable): Support deferring of BB removal.
> (tree_ssa_phiopt_worker): Detect diamond phi structure for three-way
> min/max.
> (strip_bit_not, invert_minmax_code): New.
I have been working on getting rid of minmax_replacement and a few
others and only having match_simplify_replacement and having the
simplification logic all in match.pd instead.
Is there a reason why you can't expand match_simplify_replacement and match.pd?
>The reason was that a lot of the foldings checked that the BB contains only
> a single SSA and that that SSA is a phi node.
Could you expand on that?
Thanks,
Andrew
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/split-path-1.c: Disable phi-opts so we don't
> optimize
> code away.
> * gcc.dg/tree-ssa/minmax-3.c: New test.
> * gcc.dg/tree-ssa/minmax-4.c: New test.
> * gcc.dg/tree-ssa/minmax-5.c: New test.
> * gcc.dg/tree-ssa/minmax-6.c: New test.
> * gcc.dg/tree-ssa/minmax-7.c: New test.
> * gcc.dg/tree-ssa/minmax-8.c: New test.
>
> --- inline copy of patch --
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> new file mode 100644
> index
> ..de3b2e946e81701e3b75f580e6a843695a05786e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-phiopt" } */
> +
> +#include
> +
> +uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> + uint8_t xk;
> +if (xc < xm) {
> +xk = (uint8_t) (xc < xy ? xc : xy);
> +} else {
> +xk = (uint8_t) (xm < xy ? xm : xy);
> +}
> +return xk;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 3 "phiopt1" } } */
> +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 0 "phiopt1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> b/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> new file mode 100644
> index
> ..0b6d667be868c2405eaefd17cb522da44bafa0e2
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-phiopt" } */
> +
> +#include
> +
> +uint8_t three_max (uint8_t xc, uint8_t xm, uint8_t xy) {
> +uint8_t xk;
> +if (xc > xm) {
> +xk = (uint8_t) (xc > xy ? xc : xy);
> +} else {
> +xk = (uint8_t) (xm > xy ? xm : xy);
> +}
> +return xk;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 0 "phiopt1" } } */
> +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 3 "phiopt1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-5.c
> b/gcc/testsuite/gcc.dg/tree-ssa/minmax-5.c
> new file mode 100644
> index
> ..650601a3cc75d09a9e6e54a35f5b9993074f8510
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-5.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-phiopt" } */
> +
> +#include
> +
> +uint8_t three_minmax1 (uint8_t xc, uint8_t xm, uint8_t xy) {
> + uint8_t xk;
> +if (xc > xm) {
> +xk = (uint8_t) (xc < xy ? xc : xy);
> +} else {
> +xk = (uint8_t) (xm < xy ? xm : xy);
> +}
> +return xk;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 2 "phiopt1" } } */
> +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "phiopt1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-6.c
> b/gcc/testsuite/gcc.dg/tree-ssa/minmax-6.c
> new file mode 100644
> index
>
RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
> -Original Message-
> From: Richard Biener
> Sent: Monday, June 20, 2022 9:36 AM
> To: Tamar Christina
> Cc: gcc-patches@gcc.gnu.org; nd ; ja...@redhat.com
> Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way
> max/min.
>
> On Thu, 16 Jun 2022, Tamar Christina wrote:
>
> > Hi All,
> >
> > This patch adds support for three-way min/max recognition in phi-opts.
> >
> > Concretely for e.g.
> >
> > #include
> >
> > uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > uint8_t xk;
> > if (xc < xm) {
> > xk = (uint8_t) (xc < xy ? xc : xy);
> > } else {
> > xk = (uint8_t) (xm < xy ? xm : xy);
> > }
> > return xk;
> > }
> >
> > we generate:
> >
> >[local count: 1073741824]:
> > _5 = MIN_EXPR ;
> > _7 = MIN_EXPR ;
> > return _7;
> >
> > instead of
> >
> > :
> > if (xc_2(D) < xm_3(D))
> > goto ;
> > else
> > goto ;
> >
> > :
> > xk_5 = MIN_EXPR ;
> > goto ;
> >
> > :
> > xk_6 = MIN_EXPR ;
> >
> > :
> > # xk_1 = PHI
> > return xk_1;
> >
> > The same function also immediately deals with turning a minimization
> > problem into a maximization one if the results are inverted. We do
> > this here since doing it in match.pd would end up changing the shape
> > of the BBs and adding additional instructions which would prevent various
> optimizations from working.
>
> Can you explain a bit more?
I'll respond to this one first In case it changes how you want me to proceed.
I initially had used a match.pd rule to do the min to max conversion, but a
number of testcases started to fail. The reason was that a lot of the foldings
checked that the BB contains only a single SSA and that that SSA is a phi node.
By changing the min into max, the negation of the result ends up In the same BB
and so the optimizations are skipped leading to less optimal code.
I did look into relaxing those phi opts but it felt like I'd make a rather
arbitrary
exception for minus and seemed better to handle it in the minmax folding.
Thanks,
Tamar
>
> > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
> >
> > Ok for master?
> >
> > Thanks,
> > Tamar
> >
> > gcc/ChangeLog:
> >
> > * tree-ssa-phiopt.cc (minmax_replacement): Optionally search for
> the phi
> > sequence of a three-way conditional.
> > (replace_phi_edge_with_variable): Support deferring of BB removal.
> > (tree_ssa_phiopt_worker): Detect diamond phi structure for three-
> way
> > min/max.
> > (strip_bit_not, invert_minmax_code): New.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.dg/tree-ssa/split-path-1.c: Disable phi-opts so we don't
> optimize
> > code away.
> > * gcc.dg/tree-ssa/minmax-3.c: New test.
> > * gcc.dg/tree-ssa/minmax-4.c: New test.
> > * gcc.dg/tree-ssa/minmax-5.c: New test.
> > * gcc.dg/tree-ssa/minmax-6.c: New test.
> > * gcc.dg/tree-ssa/minmax-7.c: New test.
> > * gcc.dg/tree-ssa/minmax-8.c: New test.
> >
> > --- inline copy of patch --
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > new file mode 100644
> > index
> >
> ..de3b2e946e81701e3b75f580e
> 6a8
> > 43695a05786e
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > @@ -0,0 +1,17 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > +
> > +#include
> > +
> > +uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > + uint8_t xk;
> > +if (xc < xm) {
> > +xk = (uint8_t) (xc < xy ? xc : xy);
> > +} else {
> > +xk = (uint8_t) (xm < xy ? xm : xy);
> > +}
> > +return xk;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 3 "phiopt1" } } */
> > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 0 "phiopt1" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> > new file mode 100644
> > index
> >
> ..0b6d667be868c2405eaefd17c
> b52
> > 2da44bafa0e2
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> > @@ -0,0 +1,17 @@
> >
Re: [PATCH 2/2]middle-end: Support recognition of three-way max/min.
On Thu, 16 Jun 2022, Tamar Christina wrote:
> Hi All,
>
> This patch adds support for three-way min/max recognition in phi-opts.
>
> Concretely for e.g.
>
> #include
>
> uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> uint8_t xk;
> if (xc < xm) {
> xk = (uint8_t) (xc < xy ? xc : xy);
> } else {
> xk = (uint8_t) (xm < xy ? xm : xy);
> }
> return xk;
> }
>
> we generate:
>
>[local count: 1073741824]:
> _5 = MIN_EXPR ;
> _7 = MIN_EXPR ;
> return _7;
>
> instead of
>
> :
> if (xc_2(D) < xm_3(D))
> goto ;
> else
> goto ;
>
> :
> xk_5 = MIN_EXPR ;
> goto ;
>
> :
> xk_6 = MIN_EXPR ;
>
> :
> # xk_1 = PHI
> return xk_1;
>
> The same function also immediately deals with turning a minimization problem
> into a maximization one if the results are inverted. We do this here since
> doing it in match.pd would end up changing the shape of the BBs and adding
> additional instructions which would prevent various optimizations from
> working.
Can you explain a bit more?
> Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
>
> Ok for master?
>
> Thanks,
> Tamar
>
> gcc/ChangeLog:
>
> * tree-ssa-phiopt.cc (minmax_replacement): Optionally search for the phi
> sequence of a three-way conditional.
> (replace_phi_edge_with_variable): Support deferring of BB removal.
> (tree_ssa_phiopt_worker): Detect diamond phi structure for three-way
> min/max.
> (strip_bit_not, invert_minmax_code): New.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/split-path-1.c: Disable phi-opts so we don't optimize
> code away.
> * gcc.dg/tree-ssa/minmax-3.c: New test.
> * gcc.dg/tree-ssa/minmax-4.c: New test.
> * gcc.dg/tree-ssa/minmax-5.c: New test.
> * gcc.dg/tree-ssa/minmax-6.c: New test.
> * gcc.dg/tree-ssa/minmax-7.c: New test.
> * gcc.dg/tree-ssa/minmax-8.c: New test.
>
> --- inline copy of patch --
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> new file mode 100644
> index
> ..de3b2e946e81701e3b75f580e6a843695a05786e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-phiopt" } */
> +
> +#include
> +
> +uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> + uint8_t xk;
> +if (xc < xm) {
> +xk = (uint8_t) (xc < xy ? xc : xy);
> +} else {
> +xk = (uint8_t) (xm < xy ? xm : xy);
> +}
> +return xk;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 3 "phiopt1" } } */
> +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 0 "phiopt1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> b/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> new file mode 100644
> index
> ..0b6d667be868c2405eaefd17cb522da44bafa0e2
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-phiopt" } */
> +
> +#include
> +
> +uint8_t three_max (uint8_t xc, uint8_t xm, uint8_t xy) {
> +uint8_t xk;
> +if (xc > xm) {
> +xk = (uint8_t) (xc > xy ? xc : xy);
> +} else {
> +xk = (uint8_t) (xm > xy ? xm : xy);
> +}
> +return xk;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 0 "phiopt1" } } */
> +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 3 "phiopt1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-5.c
> b/gcc/testsuite/gcc.dg/tree-ssa/minmax-5.c
> new file mode 100644
> index
> ..650601a3cc75d09a9e6e54a35f5b9993074f8510
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-5.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-phiopt" } */
> +
> +#include
> +
> +uint8_t three_minmax1 (uint8_t xc, uint8_t xm, uint8_t xy) {
> + uint8_t xk;
> +if (xc > xm) {
> +xk = (uint8_t) (xc < xy ? xc : xy);
> +} else {
> +xk = (uint8_t) (xm < xy ? xm : xy);
> +}
> +return xk;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 2 "phiopt1" } } */
> +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "phiopt1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-6.c
> b/gcc/testsuite/gcc.dg/tree-ssa/minmax-6.c
> new file mode 100644
> index
> ..a628f6d99222958cfd8c410f0e85639e3a49dd4b
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-6.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-phiopt" } */
> +
> +#include
> +
> +uint8_t three_minmax3 (uint8_t xc, uint8_t xm, uint8_t xy) {
> +uint8_t xk;
> +if (xc > xm) {
> +xk = (uint8_t) (xy < xc ? xc : xy);
> +} else {
> +xk = (uint8_t) (xm < xy ? xm : xy);
> +
