[llvm-dev] Seeking clarification about indirect critical edges

[Joseph Tremoulet via llvm-dev]

Yes, your understanding is correct regarding multiple incoming indirect branches.  The function in question bails on this case (see ‘findIBRPredecessor’ and the call to it) and just leaves those edges critical.

-Joseph


From: Stefan Nagy <snagy2 at vt.edu>
Sent: Wednesday, November 6, 2019 12:44 PM
To: Joseph Tremoulet <jotrem at microsoft.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Seeking clarification about indirect critical edges

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<mailto: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<mailto: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<mailto: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/2930fd65/attachment.html>