llvm dev - Nov 2019 - Seeking clarification about indirect critical edges

Hello all! (I apologize if I've ended up in the wrong list!)

I'm trying to get a better understanding of LLVM's critical edge
splitting,
as documented in `Transforms/Utils/BasicBlockUtils.h`; specifically in the
case of critical edges which are indirect transfer.

The code comments discuss the following example: a CFG with direct edges
A->D, B->D, and an indirect critical edge I->D; in this case two
identical
"dummy" nodes D0A and D0B would be inserted before D, and the edges
would
be re-routed as such: A->D0A, B->D0A, I->D0B, and D0A/D0B would just be
direct jumps to D.

What I'm not understanding is why it is necessary to split the non-critical
edges A->D and B->D? It seems like I->D0B would handle the only edge
causing us trouble in this example; since A and B are direct transfer,
couldn't their jump targets just remain the original D?

Also, the comments hint that this is only possible in some "easy
cases".
I'm guessing this means when D has at most one incoming indirect critical
edge?

Any explanation would be greatly appreciated!

Thanks,
-Stefan
-- 
Stefan Nagy
Department of Computer Science
Virginia Tech
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20191105/b9f8645d/attachment.html>

What the comment doesn’t specify, but the code implements, is that “D0B” is the
original block “D” (after copying/moving various things out of it as described).
That’s important because there’s code in the IR somewhere that gets the address
of D and passes it as an argument to the indirectbr, and that dataflow may be
arbitrarily complex so if the transform created some new block D0B, it wouldn’t
(in the general case) be able to do the necessary rewrite to pass the address of
D0B rather than the address of D to the indirectbr.

From your description it sounds like you were assuming that “D1”, rather than
“D0B”, is the original block “D”.  In the source, “D1” is “BodyBlock” and
“D”/”D0”/”D0B” are “Target” (and “D0A” is “DirectSucc”).

I’d guess that the “easy cases” remark corresponds to bailing out on EH pads.

-Joseph


From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Stefan
Nagy via llvm-dev
Sent: Tuesday, November 5, 2019 6:36 PM
To: llvm-dev at lists.llvm.org
Subject: [llvm-dev] Seeking clarification about indirect critical edges

Hello all! (I apologize if I've ended up in the wrong list!)

I'm trying to get a better understanding of LLVM's critical edge
splitting, as documented in `Transforms/Utils/BasicBlockUtils.h`; specifically
in the case of critical edges which are indirect transfer.

The code comments discuss the following example: a CFG with direct edges
A->D, B->D, and an indirect critical edge I->D; in this case two
identical "dummy" nodes D0A and D0B would be inserted before D, and
the edges would be re-routed as such: A->D0A, B->D0A, I->D0B, and
D0A/D0B would just be direct jumps to D.

What I'm not understanding is why it is necessary to split the non-critical
edges A->D and B->D? It seems like I->D0B would handle the only edge
causing us trouble in this example; since A and B are direct transfer,
couldn't their jump targets just remain the original D?

Also, the comments hint that this is only possible in some "easy
cases". I'm guessing this means when D has at most one incoming
indirect critical edge?

Any explanation would be greatly appreciated!

Thanks,
-Stefan
--
Stefan Nagy
Department of Computer Science
Virginia Tech
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20191106/a2b80f15/attachment.html>

That makes way more sense, thank you so much!
>From your description it sounds like you were assuming that “D1”, rather
> than “D0B”, is the original block “D”.  In the source, “D1” is “BodyBlock”
> and “D”/”D0”/”D0B” are “Target” (and “D0A” is “DirectSucc”).
> I’d guess that the “easy cases” remark corresponds to bailing out on EH
> pads.
Yeah I could see how exception handling branches are a challenge, but
wouldn't this also break if the critical edge is one of 2+ incoming
indirect branches to its target?

For example, if the CFG is A->D, I1->D, I2->D (assuming I1 and I2 have
multiple outgoing indirect edges), we could redirect A to D0A; but because
I1 and I2 both need to indirectly jump to D, we couldn't give them their
own "copies" of D (i.e., D0B and D0C). Is my understanding correct?

Thanks,
-Stefan

On Wed, Nov 6, 2019 at 12:23 PM Joseph Tremoulet <jotrem at microsoft.com>
wrote:
> What the comment doesn’t specify, but the code implements, is that “D0B”
> is the original block “D” (after copying/moving various things out of it as
> described).  That’s important because there’s code in the IR somewhere that
> gets the address of D and passes it as an argument to the indirectbr, and
> that dataflow may be arbitrarily complex so if the transform created some
> new block D0B, it wouldn’t (in the general case) be able to do the
> necessary rewrite to pass the address of D0B rather than the address of D
> to the indirectbr.
>
>
>
> From your description it sounds like you were assuming that “D1”, rather
> than “D0B”, is the original block “D”.  In the source, “D1” is “BodyBlock”
> and “D”/”D0”/”D0B” are “Target” (and “D0A” is “DirectSucc”).
>
>
>
> I’d guess that the “easy cases” remark corresponds to bailing out on EH
> pads.
>
>
>
> -Joseph
>
>
>
>
>
> *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> *On Behalf Of
*Stefan
> Nagy via llvm-dev
> *Sent:* Tuesday, November 5, 2019 6:36 PM
> *To:* llvm-dev at lists.llvm.org
> *Subject:* [llvm-dev] Seeking clarification about indirect critical edges
>
>
>
> Hello all! (I apologize if I've ended up in the wrong list!)
>
> I'm trying to get a better understanding of LLVM's critical edge
> splitting, as documented in `Transforms/Utils/BasicBlockUtils.h`;
> specifically in the case of critical edges which are indirect transfer.
>
> The code comments discuss the following example: a CFG with direct edges
> A->D, B->D, and an indirect critical edge I->D; in this case two
identical
> "dummy" nodes D0A and D0B would be inserted before D, and the
edges would
> be re-routed as such: A->D0A, B->D0A, I->D0B, and D0A/D0B would
just be
> direct jumps to D.
>
> What I'm not understanding is why it is necessary to split the
> non-critical edges A->D and B->D? It seems like I->D0B would
handle the
> only edge causing us trouble in this example; since A and B are direct
> transfer, couldn't their jump targets just remain the original D?
>
> Also, the comments hint that this is only possible in some "easy
cases".
> I'm guessing this means when D has at most one incoming indirect
critical
> edge?
>
> Any explanation would be greatly appreciated!
>
> Thanks,
> -Stefan
> --
>
> Stefan Nagy
>
> Department of Computer Science
>
> Virginia Tech
>

-- 
Stefan Nagy
Department of Computer Science
Virginia Tech
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20191106/d9b4bd14/attachment.html>