Fix PR40710: Outlined Function has token parameter but isn't an intrinsic

[hiraditya]

Summary

Code extractor outlines function with token parameter which isn't an intrinsic. This patch:

• Adds a verifier to check valid parameter types.
• Allows hotcoldsplit to bail out once input parameters are calculated (before splitting)
• Adds a sanity check using the verifier in debug mode (after splitting)

https://bugs.llvm.org/show_bug.cgi?id=40710

[compnerd]

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

313

For some reason it feels like an odd name to me. What do you think of something like validateDataDependencies or something along those lines? I think the fact that input is slightly fuzzy is why it just feels odd, but, I can understand where that comes from too.

llvm/test/Transforms/HotColdSplit/token-arg.ll

2

Might not be a bad idea to ensure that the transformation is idempotent - that is to have checks on the output IR

[hiraditya]

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

313

Sounds good.

llvm/test/Transforms/HotColdSplit/token-arg.ll

2

sure

[hiraditya]

Comments from @compnerd

[vsk]

Thanks for working on this!

llvm/include/llvm/Transforms/Utils/CodeExtractor.h

113–118

The validation done by validateInputDataDependencies should be moved into isEligible. This way, extractCodeRegion will simply fail on non-eligible regions -- this is something clients of CodeExtractor can already handle.

Adding a new validation API may leave some clients, like PartialInliner, unfixed.

[hiraditya]

llvm/include/llvm/Transforms/Utils/CodeExtractor.h

113–118

Makes sense, i'll update this.

[hiraditya]

Addressed comments from @vsk

• Move input parameter validation to isEligible().

This now requires recomputing inputs in extractCodeRegion because PHI nodes, and return blocks are split. The computation cost of input is same as before because previously the input parameter would be computed on the client side (caller of extractCodeRegion) and introduce extra overhead to be taken care of.

[vsk]

llvm/lib/Transforms/Utils/CodeExtractor.cpp

554

Why not set a bit inside of the CodeExtractor instance the first time findInputsOutputs runs? Then there's no need to duplicate the 'findInputs' logic.

[hiraditya]

Do we have further feedback for this patch?

[vsk]

llvm/lib/Transforms/Utils/CodeExtractor.cpp

1351

On closer inspection, I don't think my suggestion for storing an 'are inputs eligible' bit inside of CodeExtractor after findInputsOutputs runs the first time is a great idea (and I see that you haven't followed that advice here). The problem with that approach is that it requires clients to run findInputsOutputs, not modify any IR, and then call extractCodeRegion. That happens to be how clients use CodeExtractor today, but the new requirement could be brittle.

That said, I don't think the solution can be to run findInputsOutputs a third time. In addition to being expensive, it creates some confusion over the need for the operation to be repeated three times.

I think there's a simpler and cheaper alternative: run findInputsOutputs() exactly once within extractCodeRegion(). Note that splitReturnBlocks() doesn't change the input set. In severSplitPHINodesOfEntry(), you can add phis from the old header block to the input set if they have uses in the extraction region. Similarly, severSplitPHINodesOfExits() can be modified to remove exit block phis from the output set, and to add any newly created split phis.

To recap, please call findInputsOutputs() just once at the start of extractCodeRegion() and delete the subsequent call. Any input validation can happen up front (e.g. findInputsOutputs could return an llvm::Error indicating whether validation succeeded).

[hiraditya]

llvm/lib/Transforms/Utils/CodeExtractor.cpp

1351

That said, I don't think the solution can be to run findInputsOutputs a third time. In addition to being expensive, it creates some confusion over the need for the operation to be repeated three times.

One of the reasons why verification of input parameters could be a separate function and not called from isEligible here. The clients can make sanity checks before calling the extractCodeRegion. In general, any optimization pass, would have analysis phase and a transformation phase. IMHO This function should just extract the region and not do anything else. But there's already some check in place here which isn't ideal. The goal of this diff was to fix the ICE. I'm totally fine with repairing CodeExtractor in a separate patch.

[hiraditya]

llvm/lib/Transforms/Utils/CodeExtractor.cpp

1351

To recap, please call findInputsOutputs() just once at the start of extractCodeRegion() and delete the subsequent call.
Any input validation can happen up front (e.g. findInputsOutputs could return an llvm::Error indicating whether
validation succeeded).

Maybe i misunderstood but keeping the first call as above, and removing the later call (line 1442) results in the following failure. Moving findInputsOutputs anywhere before splitting PHI, or splitting return could result in miscompilation.

Failing Tests (4):

LLVM :: Transforms/HotColdSplit/duplicate-phi-preds-crash.ll
LLVM :: Transforms/HotColdSplit/phi-with-distinct-outlined-values.ll
LLVM :: Transforms/HotColdSplit/split-phis-in-exit-blocks.ll
LLVM :: Transforms/HotColdSplit/succ-block-with-self-edge.ll

[hiraditya]

Essentially did this:

diff --git a/llvm/lib/Transforms/Utils/CodeExtractor.cpp b/llvm/lib/Transforms/Utils/CodeExtractor.cpp
index 952263c0b1f..49fa07a3648 100644
--- a/llvm/lib/Transforms/Utils/CodeExtractor.cpp
+++ b/llvm/lib/Transforms/Utils/CodeExtractor.cpp
@@ -1336,13 +1336,13 @@ void CodeExtractor::calculateNewCallTerminatorWeights(
 
 Function *CodeExtractor::extractCodeRegion() {
   ValueSet inputs, outputs, SinkingCands, HoistingCands;
-  findInputsOutputs(inputs, outputs, SinkingCands, true);
+  findInputsOutputs(inputs, outputs, SinkingCands);
 
   if (!isEligible(inputs))
     return nullptr;
   // After sanity check, clear inputs as it will be recomputed
   // after CFG is prepared for splitting.
-  inputs.clear();
+  //inputs.clear();
 
   // Assumption: this is a single-entry code region, and the header is the first
   // block in the region.
@@ -1439,7 +1439,7 @@ Function *CodeExtractor::extractCodeRegion() {
   assert(HoistingCands.empty() || CommonExit);
 
   // Find inputs to, outputs from the code region.
-  findInputsOutputs(inputs, outputs, SinkingCands);
+  //findInputsOutputs(inputs, outputs, SinkingCands);
 
   // Now sink all instructions which only have non-phi uses inside the region.

and got the failures:

Failing Tests (4):

LLVM :: Transforms/HotColdSplit/duplicate-phi-preds-crash.ll
LLVM :: Transforms/HotColdSplit/phi-with-distinct-outlined-values.ll
LLVM :: Transforms/HotColdSplit/split-phis-in-exit-blocks.ll
LLVM :: Transforms/HotColdSplit/succ-block-with-self-edge.ll

[vsk]

One of the reasons why verification of input parameters could be a separate function and not called from isEligible here. The clients can make sanity checks before calling the extractCodeRegion. In general, any optimization pass, would have analysis phase and a transformation phase. IMHO This function should just extract the region and not do anything else. But there's already some check in place here which isn't ideal. The goal of this diff was to fix the ICE. I'm totally fine with repairing CodeExtractor in a separate patch.

I'm not sure I follow. I think we're on the same page about wanting to fix CodeExtractor's handling of token inputs, but I'm not sure why a separate patch would be needed to do that.

Maybe i misunderstood but keeping the first call as above, and removing the later call (line 1442) results in the following failure. Moving findInputsOutputs anywhere before splitting PHI, or splitting return could result in miscompilation.

Oh, on this point I think we're not on the same page :). In addition to moving the call to findInputsOutputs to beginning of extractCodeRegion (where input validation must happen), I'm suggesting that we modify extractCodeRegion to update its input and output value sets as it modifies IR. I think I've outlined all the steps needed to do that in my previous comment. This would be simpler and cheaper than recomputing inputs & outputs from scratch a third time -- a side benefit is that it would probably make the phi splitting code clearer as well.

[hiraditya]

rebase against latest changes