> > > 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".
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.
Cheers,
Filip Kastl
