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);
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
