This is an archive of the discontinued LLVM Phabricator instance.

Implementation of Simple Outliner Module Pass
Changes PlannedPublic

Authored by kamaub on May 11 2020, 2:35 PM.

Details

Reviewers
nemanjai
shchenz
fhahn
Group Reviewers
Restricted Project
Summary

The simple outliner module pass looks for functions that have an
early exit condition from their entry to a exit block that has
only one PHINode and a return. It then outlines the rest of the
funtion to a tail call once the exiting and entry block meet the
"Simple Criteria".

A simple entry: no calls or stores and all loads are either used
in the entry or returned in the exit block. Must have a
conditional branch with two successors were the simple exit is
one of them.

A simple exit: must have only one PHI and a ret instruction.

Diff Detail

Event Timeline

kamaub created this revision.May 11 2020, 2:35 PM
kamaub added a reviewer: Restricted Project.May 11 2020, 2:37 PM
lkail added a subscriber: lkail.May 11 2020, 8:42 PM
lkail added inline comments.
llvm/lib/Target/PowerPC/PPCSimpleOutliner.cpp
206 ↗(On Diff #263280)

Can we use SmallVector instead, since most cases num of args won't be large?

288 ↗(On Diff #263280)

Could be replaced with !ClonedFunctions.count(&F).

1: I like the idea about reducing csr cost in prologue/epilogue by outlining some function bodies. Any special reason for applying this pass only on PowerPC? I think many other platforms also can benefit from this pass.

2: Is there any plan to extend the light path definition. Currently in this pass a light path is a path from entry block directly to exit block. But I think light path can be more general. A simple example

//   ENTRY
//     |
//    BB1 
//    / \    
//   |  BB2    
//   |   | \     
//   |  ANY BLOCKS   
//   |  /                   
//   RET
//

A light path for this case can be ENTRY->BB1->RET and outline other blocks.

If we plan to extend light path definition, I think better to do a little change in the code framework. Eg: define a function like findLightPath() in tryOutlining instead of hard code the light path?

3: After get the light path, I think it’s better to call interfaces in class CodeExtractor to do outlining like hotcoldsplitting pass and PartialInliner pass did.

llvm/lib/Target/PowerPC/PPCSimpleOutliner.cpp
274 ↗(On Diff #263280)

Can this be a function pass?

kamaub planned changes to this revision.EditedMay 13 2020, 10:37 AM
kamaub edited reviewers, added: shchenz; removed: kbarton.

1: I like the idea about reducing csr cost in prologue/epilogue by outlining some function bodies. Any special reason for applying this pass only on PowerPC? I think many other platforms also can benefit from this pass.

I can definitely do this, I'll mark this patch as "changes planned" and then post the updated target independent version when it is completed.

2: Is there any plan to extend the light path definition. Currently in this pass a light path is a path from entry block directly to exit block. But I think light path can be more general. A simple example

//   ENTRY
//     |
//    BB1 
//    / \    
//   |  BB2    
//   |   | \     
//   |  ANY BLOCKS   
//   |  /                   
//   RET
//

A light path for this case can be ENTRY->BB1->RET and outline other blocks.

If we plan to extend light path definition, I think better to do a little change in the code framework. Eg: define a function like findLightPath() in tryOutlining instead of hard code the light path?

There are plans to improve this pass once that pass is completed and makes it into the compiler. Thank you for this guidance, I will keep it in mind.

3: After get the light path, I think it’s better to call interfaces in class CodeExtractor to do outlining like hotcoldsplitting pass and PartialInliner pass did.

I had not considered this , I will investigate this possibility as well.

llvm/lib/Target/PowerPC/PPCSimpleOutliner.cpp
274 ↗(On Diff #263280)

We decided to change it it from a function pass to a module pass early on because we see it as 'bad form' to edit or introduce code outside of the scope of operation, that is, as a function pass you are cloning and creating functions outside of where you are operating where as a module pass you are optimizing the whole scope(module) and can introduce functions(clones) as needed.

Do you agree? Could you expand on why you think it should be a function pass.

kamaub updated this revision to Diff 264053.May 14 2020, 12:11 PM

Addressing review and clang-tidy comments

kamaub updated this revision to Diff 264055.May 14 2020, 12:17 PM

Addressing review and clang-tidy comments

kamaub updated this revision to Diff 264212.May 15 2020, 5:28 AM

While using Arcanist I accidentally made the differential change BASE because the recorded HEAD commit hash on phabricator somehow became mixed-matched with my local HEAD that i use for this branch.
I am manually uploading the diff to correct this.

kamaub marked 2 inline comments as done.May 15 2020, 5:30 AM

Addressed some review comments.

kamaub updated this revision to Diff 268267.Jun 3 2020, 11:42 AM

Updating this patch to make it a target independent IPO module pass.

kamaub updated this revision to Diff 268269.Jun 3 2020, 11:46 AM

Address clang-format suggestions.

kamaub updated this revision to Diff 268270.Jun 3 2020, 11:49 AM

Addressing clang-format suggestion.

kamaub updated this revision to Diff 268271.Jun 3 2020, 11:52 AM

Third attempt to address clang-format.

kamaub retitled this revision from [PowerPC] Implementation of Simple Outliner Module Pass to Implementation of Simple Outliner Module Pass.Jun 3 2020, 12:00 PM
kamaub removed reviewers: lei, stefanp, amyk, bsaleil, NeHuang, saghir.
fhahn added a subscriber: fhahn.Jun 3 2020, 12:22 PM

I think it would be great to add more details about the benefit of the outlining to the description. For the example in the test case, outlining seems quite heavy handed. Wouldn't it be simpler and faster in those cases to just duplicate the return block?

Harbormaster failed remote builds in B58967: Diff 268267!
Harbormaster failed remote builds in B58968: Diff 268269!
kamaub planned changes to this revision.Jun 23 2020, 7:44 AM
kamaub added a reviewer: fhahn.

I think it would be great to add more details about the benefit of the outlining to the description. For the example in the test case, outlining seems quite heavy handed. Wouldn't it be simpler and faster in those cases to just duplicate the return block?

Thank you for suggestion, this is an initial implementation so we handled the specific general case as duplicating the return block would not always be possible, I will post a motivating test case to show this and we can continue to discuss, but that won't be possible immediately.

I am marking this patch for changes planned; we see degradations in performance in particularly concerning areas that need to be investigated and addressed before we move forward.

kamaub updated this revision to Diff 272733.Jun 23 2020, 7:59 AM

Updating test case.

kamaub planned changes to this revision.Jun 23 2020, 8:00 AM