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
1046

clang-format

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

Why this number?

370
863

run on?

894

avoid double negative with variable name?

904

this comment is a bit of a run-on

929

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

954

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

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

Using empty() would be more explicit here.

963

Don't need else since you would have continued already

989

Add comments for what these types represent?

1026

Can this use

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

?

1039

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

1043

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

1049

what happens if BBGVN doesn't have a value?

1395

comments?

1445

this looks like it could be

bool GVNMatches = all_of(...);

or even better:

if (all_of(...))
   return CurrPN;
2264–2265
2329

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
109

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.

1043

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.

1049

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.

2329

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
112

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

880

avoid recalculating loop invariant

885

probably don't need the variable here

887

probably don't need the variable here either

914

drop braces

951

we calculate IncomingVals.size()s twice here

how about

unsigned NumIncoming = IncomingVals.size();

if (NumIncoming == 0)
  continue;

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

comments here?

1003
1185

comment?

1409

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
1455

use phis()?

1472

avoid recalculating loop invariant

1478

getFirstNonPHI can return nullptr. assert?

2264

comment?

2274

why is there an assert below and not here?

2320

code duplication with change above?

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

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.

1409

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
112

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
880

don't recalculate loop invariant

also can this just be an any_of?

891

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

892

this could probably also be an any_of

899

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

904

can you explain this a bit more?

919

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)"

924

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"

925

this could be named "BasicBlocksInRegion"

928

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

930

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)

941

don't recalculate loop invariant

999
1008

this could probably be called "BasicBlocksInRegion" or something

1017

can this be named Cand or something?

1020

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

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

comment is pretty wordy, split it up?

1026

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

1033

is this guaranteed to have a value?

1034

simpler?

1036

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

1091–1096

these could use more descriptive names

1151–1174

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

1183
1185
1187

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

1189

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

1191

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

1324

simpler:

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

1335

I think this could be called like "PhiBlockForRetVal"

1336

this could also use a more descriptive name

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

don't recalculate loop invariant

1376

simpler:

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

1380

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

1381

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?

1383
1416

this could use a better name (like above)

1419

formatting

1436

is this guaranteed to have a value?

1454

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

1461

unfinished comment?

1464

this could use a more descriptive name or a comment

1480
PHINode *cloneImpl() const;

do you have to cast here? static_cast seems wrong too

1484

just call this IncomingVal?

1485

just call this IncomingBlock?

1489

call this FirstNonPhi?

1491

this could use a more descriptive name?

2229

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
863

we can be even more concise here:

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

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

880

Would it make sense to use a SmallVector here?

883

couple probably be a one-liner?

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

Return the any_of rather than using an if?

927

"it" is unclear IMO

also update comment for updated variable names?

1360

braces

1363

comment on the successors?

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

update comment to reflect variable name?

2229
2230

"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
381

This is being computed twice?

1352
1357

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

1386

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
1146

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

1173

comment for this part?

1394

This can probably be a one-liner?

1418

Can probably eliminate the variable.

1524

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
1343
1492

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.