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.
