Page MenuHomePhabricator

[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

There are a very large number of changes, so older changes are hidden. Show Older Changes
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

1153–1179

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

1188
1190
1192

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

1194

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

1196

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

1329

simpler:

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

1340

I think this could be called like "PhiBlockForRetVal"

1341

this could also use a more descriptive name

1365
  • this can be a one-liner
  • I think this should use cast?
1369

don't recalculate loop invariant

1381

simpler:

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

1385

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

1386

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?

1388
1421

this could use a better name (like above)

1424

formatting

1441

is this guaranteed to have a value?

1459

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

1466

unfinished comment?

1469

this could use a more descriptive name or a comment

1485
PHINode *cloneImpl() const;

do you have to cast here? static_cast seems wrong too

1489

just call this IncomingVal?

1490

just call this IncomingBlock?

1494

call this FirstNonPhi?

1496

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?

1365

braces

1368

comment on the successors?

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

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?

1357
1362

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

1391

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–1149

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

1175

comment for this part?

1399

This can probably be a one-liner?

1423

Can probably eliminate the variable.

1529

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
1348
1497

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.