This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by hiraditya on Sep 29 2019, 6:58 AM.

Details

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://github.com/llvm/llvm-project/issues/40056

Diff Detail

Repository
rL LLVM

Event Timeline

hiraditya created this revision.Sep 29 2019, 6:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 29 2019, 6:58 AM
hiraditya updated this revision to Diff 222324.Sep 29 2019, 7:20 AM
hiraditya updated this revision to Diff 222325.Sep 29 2019, 7:23 AM
hiraditya updated this revision to Diff 222326.
hiraditya updated this revision to Diff 222327.Sep 29 2019, 7:26 AM
compnerd accepted this revision.Sep 30 2019, 8:30 AM
compnerd added inline comments.
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

This revision is now accepted and ready to land.Sep 30 2019, 8:30 AM
hiraditya marked 2 inline comments as done.Sep 30 2019, 8:55 AM
hiraditya added inline comments.
llvm/lib/Transforms/IPO/HotColdSplitting.cpp
313

Sounds good.

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

sure

vsk requested changes to this revision.Sep 30 2019, 12:58 PM

Thanks for working on this!

llvm/include/llvm/Transforms/Utils/CodeExtractor.h
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.

This revision now requires changes to proceed.Sep 30 2019, 12:58 PM
hiraditya marked an inline comment as done.Sep 30 2019, 1:18 PM
hiraditya added inline comments.
llvm/include/llvm/Transforms/Utils/CodeExtractor.h
118

Makes sense, i'll update this.

hiraditya updated this revision to Diff 222495.Sep 30 2019, 1:59 PM

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 added inline comments.Sep 30 2019, 5:18 PM
llvm/lib/Transforms/Utils/CodeExtractor.cpp
540

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 updated this revision to Diff 222534.Sep 30 2019, 6:09 PM
hiraditya marked an inline comment as done.

Do we have further feedback for this patch?

vsk added inline comments.Oct 1 2019, 2:25 PM
llvm/lib/Transforms/Utils/CodeExtractor.cpp
1337

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 marked an inline comment as done.Oct 1 2019, 3:06 PM
hiraditya added inline comments.
llvm/lib/Transforms/Utils/CodeExtractor.cpp
1337

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 marked an inline comment as done.Oct 1 2019, 3:25 PM
hiraditya added inline comments.
llvm/lib/Transforms/Utils/CodeExtractor.cpp
1337

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

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 added a comment.Oct 2 2019, 2:01 PM

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 updated this revision to Diff 225602.Oct 18 2019, 5:16 AM

rebase against latest changes

rjf added a subscriber: rjf.Jul 21 2020, 8:53 AM
rjf added a subscriber: rcorcs.Jul 31 2020, 9:45 AM
hiraditya edited the summary of this revision. (Show Details)Mar 23 2023, 2:02 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 23 2023, 2:02 PM
Herald added a subscriber: StephenFan. · View Herald Transcript