Hi Richard,
> > Sorry, I'm not sure if I understand. Are you suggesting something like
> > this?
> >
> > if (idom(default bb) == cond bb)
> > {
> > if (exists a path from default bb to final bb)
> > {
> > idom(final bb) = cond bb;
> > }
> > else
> > {
> > idom(final bb) = switch bb;
> > }
> > }
> > else
> > {
> > // idom(final bb) doesn't change
> > }
Sidenote: I've just noticed that this code wouldn't work since the original
idom of final_bb may be some block outside of the switch. In that case, idom
of final_bb should remain the same after the transformation regardless of if
idom(default bb) == cond bb. So the code would look like this
if (original idom(final bb) == switch bb and idom(default bb) == cond bb)
{
if (exists a path from default bb to final bb)
{
idom(final bb) = cond bb;
}
else
{
idom(final bb) = switch bb;
}
}
else
{
// idom(final bb) doesn't change
}
> >
> > If so, how do I implement testing existence of a path from default bb to
> > final
> > bb? I guess I could do BFS but that seems like a pretty complicated
> > solution.
> > >
> > > That said, even above if there's a merge of the default BB and final BB
> > > downstream in the CFG, inserting cond BB requires adjustment of the
> > > immediate dominator of that merge block and you are missing that?
> >
> > I think this isn't a problem because I do
> >
> > redirect_immediate_dominators (CDI_DOMINATORS, swtch_bb, cond_bb);
>
> Hmm, I'm probably just confused. So the problem is that
> redirect_immediate_dominators makes the dominator of final_bb incorrect
> (but also all case_bb immediate dominator?!)?
Yes, the problem is what the idom of final_bb should be after the
transformation. However, redirect_immediate_dominators doesn't *make* the idom
of final_bb incorrect. It may have been already incorrect before the call (the
call may also possibly make the idom correct btw).
This has probably already been clear to you. I'm just making sure we're on the
same page.
>
> 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?
Btw to further check that we're on the same page: Right now we're only trying
to figure out if there is a way to update idom of final_bb after the
transformation without using iterate_fix_dominators, right? The rest of my
dominator fixing code makes sense / is ok?
Cheers,
Filip Kastl
