On Thu, 18 Jul 2024, Filip Kastl wrote:
> On Thu 2024-07-18 12:07:42, Richard Biener wrote:
> > On Wed, 17 Jul 2024, Filip Kastl wrote:
> > > > > + }
> > > > > +
> > > > > + vec<basic_block> v;
> > > > > + v.create (1);
> > > > > + v.quick_push (m_final_bb);
> > > > > + iterate_fix_dominators (CDI_DOMINATORS, v, true);
> > > >
> > > > The final BB should have the condition block as immediate dominator
> > > > if it's old immediate dominator was the switch block, otherwise
> > > > it's immediate dominator shouldn't change.
> > > I think that this is not true. Consider this CFG where no path through
> > > default
> > > BB intersects final BB:
> > >
> > > switch BB ---+
> > > / | \ \
> > > case BBs default BB
> > > \ | / /
> > > final BB /
> > > | /
> > >
> > > Here idom(final BB) == switch BB.
> > > After the index exponential transform the CFG looks like this
> > >
> > > cond BB ---------+
> > > | |
> > > switch BB ---+ |
> > > / | \ \ |
> > > case BBs default BB
> > > \ | / /
> > > final BB /
> > > | /
> > >
> > > It still holds that idom(final BB) == switch BB.
> >
> > Sure but you still know the dominator of the default BB as the cond BB
> > then? That said, I think that using iterate_fix_dominators is overkill
> > and you should know the new immediate dominator and can set it directly?
>
> 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
> }
>
> 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?!)?
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?
Richard.
> If the old immediate dominator of the merge bb was the switch bb then I set
> its
> immediate dominator to cond bb. Otherwise its immediate dominator stays the
> same.
>
> I try to prove that this is correct here:
>
> > > + 3 Other blocks that had the switch block as their immediate dominator
> > > + should now have the cond block as their immediate dominator.
> > > +
> > > + 4 Immediate dominators of the rest of the blocks shouldn't change.
> > > +
> > > + Reasoning for 3 and 4:
> > > +
> > > + We'll only consider blocks that do not fall into 1 or 2.
> > > +
> > > + Consider a block X whose original imm dom was the switch block. All
> > > + paths to X must also intersect the cond block since it's the only
> > > + pred of the switch block. The final block doesn't dominate X so at
> > > + least one path P must lead through the default block. Let P' be P but
> > > + instead of going through the switch block, take E. The switch block
> > > + doesn't dominate X so its imm dom must now be the cond block.
> > > +
> > > + Consider a block X whose original imm dom was Y != the switch block.
> > > + We only added an edge so all original paths to X are still present.
> > > + So X gained no new dominators. Observe that Y still dominates X.
> > > + There would have to be a path that avoids Y otherwise. But any block
> > > + we can avoid now except for the switch block we were able to avoid
> > > + before adding E. */
>
> Cheers,
> Filip Kastl
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstra
