On Tue 2024-07-30 14:34:54, Richard Biener wrote:
> On Tue, 30 Jul 2024, Filip Kastl wrote:
>
> > > > > Ah, I see you fix those up. Then 2.) is left - the final block. Iff
> > > > > the final block needs adjustment you know there was a path from
> > > > > the default case to it which means one of its predecessors is
> > > > > dominated
> > > > > by the default case? In that case, adjust the dominator to cond_bb,
> > > > > otherwise leave it at switch_bb?
> > > >
> > > > Yes, what I'm saying is that if I want to know idom of final_bb after
> > > > the
> > > > transformation, I have to know if there is a path between default_bb and
> > > > final_bb. It is because of these two cases:
> > > >
> > > > 1.
> > > >
> > > > cond BB ---------+
> > > > | |
> > > > switch BB ---+ |
> > > > / | \ \ |
> > > > case BBs default BB
> > > > \ | / /
> > > > final BB <---+ <- this may be an edge or a path
> > > > |
> > > >
> > > > 2.
> > > >
> > > > cond BB ---------+
> > > > | |
> > > > switch BB ---+ |
> > > > / | \ \ |
> > > > case BBs default BB
> > > > \ | / /
> > > > final BB / <- this may be an edge or a path
> > > > | /
> > > >
> > > > In the first case, there is a path between default_bb and final_bb and
> > > > in the
> > > > second there isn't. Otherwise the cases are the same. In the first
> > > > case idom
> > > > of final_bb should be cond_bb. In the second case idom of final_bb
> > > > should be
> > > > switch_bb. Algorithm deciding what should be idom of final_bb therefore
> > > > has to
> > > > know if there is a path between default_bb and final_bb.
> > > >
> > > > You said that if there is a path between default_bb and final_bb, one
> > > > of the
> > > > predecessors of final_bb is dominated by default_bb. That would indeed
> > > > give a
> > > > nice way to check existence of a path between default_bb and final_bb.
> > > > But
> > > > does it hold? Consider this situation:
> > > >
> > > > | |
> > > > cond BB --------------+
> > > > | | |
> > > > switch BB --------+ |
> > > > / | \ | \ |
> > > > case BBs | default BB
> > > > \ | / | /
> > > > final BB <- pred BB -+
> > > > |
> > > >
> > > > Here no predecessors of final_bb are dominated by default_bb but at the
> > > > same
> > > > time there does exist a path from default_bb to final_bb. Or is this
> > > > CFG
> > > > impossible for some reason?
> > >
> > > I think in this case the dominator simply need not change - the only case
> > > you need to adjust it is when the immediate dominator of final BB was
> > > switch BB before the transform, and then we know we have to update it
> > > too cond BB, no?
> >
> > Ah, my bad. Yes, my counterexample actually isn't a problem. I was glad
> > when
> > I realized that and started thinking that this...
> >
> > if (original idom(final bb) == switch bb)
> > {
> > if (exists a pred of final bb dominated by default bb)
> > {
> > idom(final bb) = cond bb;
> > }
> > else
> > {
> > idom(final bb) = switch bb;
> > }
> > }
> > else
> > {
> > // idom(final bb) doesn't change
> > }
> >
> > ...might be the final solution. But after thinking about it for a while I
> > (saddly) came up with another counterexample.
> >
> > |
> > cond BB --------------+
> > | |
> > switch BB --------+ |
> > / | \ \ |
> > case BBs default BB
> > \ | / /
> > final BB <- pred BB -+
> > | ^
> > | |
> > +-----------+ <- this may be a path or an edge I guess
> >
> > Here there *is* a path between default_bb and final_bb but since no
> > predecessor
> > of final_bb is dominated by default_bb we incorrectly decide that there is
> > no
> > such path. Therefore we incorrectly assign idom(final_bb) = switch_bb
> > instead
> > of idom(final_bb) = cond_bb.
> >
> > So unless I'm missing something, "final has a pred dominated by default"
> > isn't
> > equivalent with "there is a path between default and final" even when we
> > assume
> > that the original idom of final_bb was switch_bb. Therefore I think we're
> > back
> > to searching for a nice way to test "there is a path between default and
> > final".
>
> Hmm.
>
> > Maybe you can spot a flaw in my logic or maybe you see a solution I don't.
> > Meanwhile I'll look into source code of the rest of the switch conversion
> > pass.
> > Switch conversion pass inserts conditions similar to what I'm doing so
> > someone
> > before me may have already solved how to properly fix dominators in this
> > situation.
>
> OK, as I see in your next followup that uses iterate_fix_dominators as
> well.
>
> So your patch is OK as-is.
>
> It might be nice to factor out a common helper from gen_inbound_check
> and your "copy" of it though. As followup, if you like.
>
> Thanks and sorry for the confusion,
> Richard.
Alright, I pushed the patch. I bootstrapped and regtested it once again to be
sure nothing breaks on the new master. I also noticed that I didn't fill out
the changelog in the commit message of the second version of the patch so I
fixed that and I fixed two other mistakes I found in the commit message.
I'm adding the task of factoring out the common code to my list of possible
future projects.
It's a shame that we didn't manage to figure out the final bb idom. For a
while, it looked like the predecessor dominated by default idea would really
work.
Thank you for all the guidance with this patch.
Cheers,
Filip Kastl
