On Mon, 29 Jul 2024, Filip Kastl wrote:
> 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?
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?
> 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?
Yes. These "fix me up" utilities are used too often lazily - I have
the gut feeling that the situation here is very simple.
Richard.
