RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.

[Tamar Christina <Tamar.Christina@arm.com>]

> -----Original Message-----
> From: Richard Biener <richard.guenther@gmail.com>
> Sent: Tuesday, August 2, 2022 10:11 AM
> To: Tamar Christina <Tamar.Christina@arm.com>
> Cc: Richard Biener <rguenther@suse.de>; jakub@redhat.com; nd
> <nd@arm.com>; 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 <gcc-
> patches@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 <gcond *> (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 <gcond *> (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'?

As discussed on IRC, here's the version using keep_edge:

@@ -422,12 +436,17 @@ replace_phi_edge_with_variable (basic_block cond_block,
   SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree);

   /* Remove the empty basic block.  */
-  edge edge_to_remove;
+  edge edge_to_remove = NULL, keep_edge = NULL;
   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);
-  if (EDGE_COUNT (edge_to_remove->dest->preds) == 1)
+  else if ((keep_edge = find_edge (cond_block, e->src)))
+    ;
+  else
+    gcc_unreachable ();
+
+  if (edge_to_remove && EDGE_COUNT (edge_to_remove->dest->preds) == 1)
     {
       e->flags |= EDGE_FALLTHRU;
       e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
@@ -438,6 +457,18 @@ replace_phi_edge_with_variable (basic_block cond_block,
       gsi = gsi_last_bb (cond_block);
       gsi_remove (&gsi, true);
     }
+  else if (keep_edge)
+    {
+      /* If we're in a diamond then we have identified the edge
+        that we want to keep.  Since the dominators will require
+        updating in a non-trivial way we leave it to CFG cleanup
+        but mark the condition as appropriately true/false.  */
+      gcond *cond = as_a <gcond *> (last_stmt (cond_block));
+      if (keep_edge->flags & EDGE_FALSE_VALUE)
+       gimple_cond_make_false (cond);
+      else if (keep_edge->flags & EDGE_TRUE_VALUE)
+       gimple_cond_make_true (cond);
+    }
   else
     {
       /* If there are other edges into the middle block make
@@ -1733,15 +1764,52 @@ value_replacement (basic_block cond_bb, basic_block middle_bb,
   return 0;
 }

Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.

Ok with change?

Thanks,
Tamar

> 
> > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
> >
> > Ok with this Change?
> >
> > Thanks,
> > Tamar