This is an archive of the discontinued LLVM Phabricator instance.

[IROutliner] Allowing PHINodes in Exit Blocks
ClosedPublic

Authored by AndrewLitteken on Jul 28 2021, 1:09 PM.

Details

Summary

In addition to having multiple exit locations, there can be multiple blocks leading to the same exit location, which results in a potential phi node. If we find that multiple blocks within the region branch to the same block outside the region, resulting in a phi node, the code extractor pulls this phi node into the function and uses it as an output.

We make sure that this phi node is given an output slot, and that the two values are removed from the outputs if they are not used anywhere else outside of the region. Across the extracted regions, the phi nodes are combined into a single block for each potential output block, similar to the previous patch.

Diff Detail

Event Timeline

AndrewLitteken created this revision.Jul 28 2021, 1:09 PM
AndrewLitteken requested review of this revision.Jul 28 2021, 1:09 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 28 2021, 1:09 PM

Updating to handle a global in the split phi node, and correcting which successor gets reassigned when creating a new aggregate phi block.

Updating to clean up the patch, splitting into several patches, and adding more tests.

AndrewLitteken added inline comments.Aug 24 2021, 1:04 PM
llvm/lib/Transforms/IPO/IROutliner.cpp
1050

clang-format

paquette added inline comments.Sep 8 2021, 10:52 AM
llvm/lib/Transforms/IPO/IROutliner.cpp
107

Why this number?

372
867

run on?

898

avoid double negative with variable name?

908

this comment is a bit of a run-on

933

if you rename NotOnlyUsedInExitBlocks to OnlyUsedInExitBlocks and change the code accordingly, you can just return that variable.

958

in for loops like this, it's more idiomatic to write

for (unsigned I = 0, E = PN.getNumIncomingValues(); I < E; ++I)
   ...
965

Using empty() would be more explicit here.

967

Don't need else since you would have continued already

993

Add comments for what these types represent?

1030

Can this use

if (any_of(...))
  return None;

?

1043

Maybe pull PN->getNumIncomingValues into a variable to avoid recalculating it across the two loops?

1047

actually, can this loop be merged into the previous one?

1053

what happens if BBGVN doesn't have a value?

1399

comments?

1449

this looks like it could be

bool GVNMatches = all_of(...);

or even better:

if (all_of(...))
   return CurrPN;
2252–2253
2317

What happens if OVGN doesn't have a value?

AndrewLitteken added inline comments.Sep 8 2021, 11:32 AM
llvm/lib/Transforms/IPO/IROutliner.cpp
107

It has to count backwards from -3 (or rather the unsigned version) since -2, and -1 are reserved as tombstone and empty values for unsigned integers in the DenseMap. I'll add it as a comment.

1047

yes, I think so. But I think enough values would need to be passed into the lambda for this that I don't think it makes sense to put it in any_of if that's the case.

1053

It shouldn't since the block of a Phi node containing should be the target of some branch in the region, and will have been marked in that case, but I will add an assertion to make sure it exists.

2317

Right now, it will throw an assertion in the Optional code that there isn't a value.

Updating based on initial comments.

paquette added inline comments.Sep 14 2021, 10:35 AM
llvm/lib/Transforms/IPO/IROutliner.cpp
110

Can we assert somewhere that -2 and -1 are actually used by DenseMap?

884

avoid recalculating loop invariant

889

probably don't need the variable here

891

probably don't need the variable here either

918

drop braces

955

we calculate IncomingVals.size()s twice here

how about

unsigned NumIncoming = IncomingVals.size();

if (NumIncoming == 0)
  continue;

if (NumIncoming == 1) {
   ...
}
958

comments here?

1007
1189

comment?

1413

can you do this like

if (!AdjustArgNo) {
// The call instruction was already removed when we created a call to an outlined function. So, we have all the arguments already. Just grab the argument.
IVal = CI->getArgOperand(ArgNum);
continue;
}

if (Region.AggArgToConstant.count(ArgNum)) {
  // The argument is/isn't a constant...
  // do stuff
  continue;
}

// Other case
1459

use phis()?

1476

avoid recalculating loop invariant

1482

getFirstNonPHI can return nullptr. assert?

2252

comment?

2262

why is there an assert below and not here?

2308

code duplication with change above?

llvm/lib/Transforms/IPO/IROutliner.cpp
110

I'm not sure where to do that? They are representing the tombstone value, and empty key value, so you can't use them as keys for other items.

1413

There is a shared action between all three of the cases. I can clean up what the checks are, but I don't think it makes sense to use this pattern to continue and then duplicate the canonical number finding below in each case. These cases are to make sure we are getting the canonical number for the correct value, and then we can use the same code below to find the canonical number.

paquette added inline comments.Sep 14 2021, 2:45 PM
llvm/lib/Transforms/IPO/IROutliner.cpp
110

The MachineOutliner does:

InstructionMapper() {
  // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
  // changed.
  assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
         "DenseMapInfo<unsigned>'s empty key isn't -1!");
  assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
         "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
}
AndrewLitteken marked 15 inline comments as done.Sep 15 2021, 9:08 AM

Updating based on comments

paquette added inline comments.Sep 15 2021, 1:02 PM
llvm/lib/Transforms/IPO/IROutliner.cpp
884

don't recalculate loop invariant

also can this just be an any_of?

895

this comment could be more succinct, like "Check if the value is used by any instructions outside of the region."

896

this could probably also be an any_of

903

This sentence is pretty long and kind of confusing. Can you simplify it?

908

can you explain this a bit more?

923

this is kind of wordy, maybe rewrite it like

"Test whether \p ExitBlock contains any PhiNodes that should be considered outputs. PhiNodes should be outputs when...(blah)"

928

the comments here don't line up with the variable names in the function

this could be a more descriptive name as well, like "PotentialExitsFromRegion"

929

this could be named "BasicBlocksInRegion"

932

I think this variable would be better-named "OutputsReplacedByPhis"

934

maybe this could have a more descriptive name too, like "OutputsWithNonPhiUses" or "OutputsThatCouldNotBeReplacedWithPhis"

(second option is kind of wordy, but it describes what's happening pretty well)

945

don't recalculate loop invariant

1003
1012

this could probably be called "BasicBlocksInRegion" or something

1021

can this be named Cand or something?

1024

since you don't use the index here, could this just be a loop like this?

for (Value *Incoming : PN->incoming_values()) {
   ...
}
1027

comment is pretty wordy, split it up?

1030

can you pull C.getGVN(V) into a variable, since you reuse it below?

1037

is this guaranteed to have a value?

1038

simpler?

1040

can you add a comment explaining what you're going to do in this portion of the function here?

1095–1100

these could use more descriptive names

1155–1156

pull Group.ArgumentTypes.size() into a variable and reuse it? it's calculated 4 times in this function.

1165
1167
1169

this comment has a lot of run-ons; can you split it up a little?

1171

this comment is confusing. Is it two PhiNodes or one?

1173

can you expand on the store sets a little more? I feel like it's kind of out of nowhere.

1328

simpler:

Find or create a BasicBlock in the outlined function containing PhiBlocks for \p RetVal.

1339

I think this could be called like "PhiBlockForRetVal"

1340

this could also use a more descriptive name

1364
  • this can be a one-liner
  • I think this should use cast?
1368

don't recalculate loop invariant

1380

simpler:

\returns The Value representing \p A at the call location for some outlined function.

1384

maybe this should be "the region corresponding to the outlined function" or something?

1385

or even simpler:

"True when \p A's location must be adjusted. This happens when... (stuff)."

I think this could also be named something like "HasAlreadyBeenReplacedWithOutlinedCall" or something?

1387
1420

this could use a better name (like above)

1423

formatting

1440

is this guaranteed to have a value?

1458

should this ever be null? can it be a reference?

1465

unfinished comment?

1468

this could use a more descriptive name or a comment

1484
PHINode *cloneImpl() const;

do you have to cast here? static_cast seems wrong too

1488

just call this IncomingVal?

1489

just call this IncomingBlock?

1493

call this FirstNonPhi?

1495

this could use a more descriptive name?

2217

this sentence is confusing

\returns The Value represented by a canonical number \p OutputCanon in \p Region.

I assume this is an output as well? Should this function be called "findOutputValueInRegion" or something?

Updating based off of newest comments.

paquette added inline comments.Sep 15 2021, 5:17 PM
llvm/lib/Transforms/IPO/IROutliner.cpp
867

we can be even more concise here:

\returns true if \p V has any uses outside its region other than \p PN.
876

this is redundant, since you mention it in the first part of the comment.

884

Would it make sense to use a SmallVector here?

887

couple probably be a one-liner?

return (Idx != PhiLoc || V == PN.getIncomingValue(Idx) || !BlocksInRegion.contains(PN.getIncomingBlock(Idx)));
898

Return the any_of rather than using an if?

931

"it" is unclear IMO

also update comment for updated variable names?

1364

braces

1367

comment on the successors?

1469
paquette added inline comments.Sep 15 2021, 5:21 PM
llvm/lib/Transforms/IPO/IROutliner.cpp
1420

update comment to reflect variable name?

2217
2218

"one the first incoming value" doesn't parse for me

Updating comment variables and few stylistic points.

paquette added inline comments.Dec 20 2021, 12:12 PM
llvm/lib/Transforms/IPO/IROutliner.cpp
383

This is being computed twice?

1356
1361

This comment would be more useful if it said something like "find the predecessors in order to (blah)"

1390

I think I'd prefer two functions here rather than one with a flag? It'd be clearer what's going on.

Something like

  • getPassedArgumentAndAdjustArgumentLocation(Argument *A, OutlinableRegion &Region)
  • getPassedArgumentInAlreadyOutlinedFunction(Argument *A, const OutlinableRegion &Region)

Also I think A can probably be const?

Updating based on comments

Updating diff with context

paquette added inline comments.Jan 5 2022, 4:02 PM
llvm/lib/Transforms/IPO/IROutliner.cpp
1150–1151

probably want a comment here explaining what's going on?

1177

comment for this part?

1398

This can probably be a one-liner?

1422

Can probably eliminate the variable.

1528

Can probably just do this as a one-liner?

paquette added inline comments.Jan 5 2022, 4:10 PM
llvm/lib/Transforms/IPO/IROutliner.cpp
1347
1496

Missing /* ReplacedWithOutlinedCall = */ on bool param?

Updating with one-liners and extra comments.

ormris removed a subscriber: ormris.Jan 18 2022, 4:24 PM
This revision is now accepted and ready to land.Jan 21 2022, 2:20 PM
This revision was landed with ongoing or failed builds.Jan 25 2022, 9:34 AM
This revision was automatically updated to reflect the committed changes.