This is an archive of the discontinued LLVM Phabricator instance.

[IRSim][IROutliner] Adding the extraction basics for the IROutliner.

Authored by AndrewLitteken on Sep 1 2020, 1:23 PM.



Extracting the similar regions is the first step in the IROutliner.

Using the IRSimilarityIdentifier, we collect the SimilarityGroups and sort them by how many instructions will be removed. Each IRSimilarityCandidate is used to define an OutlinableRegion. Each region is ordered by their occurrence in the Module and the regions that are not compatible with previously outlined regions are discarded.

Each region is then extracted with the CodeExtractor into its own function.
We test that correctly extract in:

  • test/Transforms/IROutliner/extraction.ll
  • test/Transforms/IROutliner/address-taken.ll
  • test/Transforms/IROutliner/outlining-same-globals.ll
  • test/Transforms/IROutliner/outlining-same-constants.ll
  • test/Transforms/IROutliner/outlining-different-structure.ll

Diff Detail

Event Timeline

AndrewLitteken created this revision.Sep 1 2020, 1:23 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 1 2020, 1:23 PM
AndrewLitteken requested review of this revision.Sep 1 2020, 1:23 PM
AndrewLitteken set the repository for this revision to rG LLVM Github Monorepo.
AndrewLitteken added a reviewer: paquette.

Updating for clang-format.

Hi Andrew,

This stuff looks really interesting! I've seen a whole bunch of review links on the list, but I'm particularly interested in seeing how you're doing your cost modelling, so where can I find that?

Hi Andrew,

This stuff looks really interesting! I've seen a whole bunch of review links on the list, but I'm particularly interested in seeing how you're doing your cost modelling, so where can I find that?

I just didn't have the cost modeling up yet, you can find it here:

jroelofs added inline comments.

Is it guaranteed that we'll find precisely one CallInst in this search? Should there be assertions to that effect?

Also, is it worth adding a break in the inner if to early exit once it has been found?


Can sink this to where the .clear() call is, since it's not used until then.


should make the copy cheaper


Out of curiosity, how did you decide that this was the optimal spot in the pass stack for it?

AndrewLitteken added inline comments.Sep 15 2020, 4:11 PM

There may be more than one CallInst due to lifetime instructions added by the code extractor, but there will not be more than one call to the outlined function. So a break would be appropriate but an assertion would not be.

jroelofs added inline comments.Sep 15 2020, 4:12 PM


Vector use cleanup.

Different handling of getSimilarity() to handle optionals.

Fixing some small nits.

Removing dead variable.

yroux added a subscriber: yroux.Nov 19 2020, 2:19 AM
yroux added inline comments.

Looking at what was presented by River Riddle back in 2017 and the former proposal of an IR Outlining pass in 2018, there was the notion of early (pre inlining) and late (pre Isel) outlining and the combination of both had better results in what was presented, is it something we can do here ?

I also think that it can be added to late LTO passes

AndrewLitteken added inline comments.Nov 19 2020, 8:52 AM

There isn't any configuration right now for the early/late outlining or some combination of the two, but there's nothing in the current implementation that would be blocking that. Similarly for LTO passes, there's no real limitation to adding it at that level other.

Would the former be something that would be needed in this patch? Or could it be extended in a future patch?

yroux accepted this revision.Nov 20 2020, 6:16 AM

I think that the previous comments were addressed. LGTM


Yes sure, it'd be great to have it in a future patch.

This revision is now accepted and ready to land.Nov 20 2020, 6:16 AM

Updating diff to reflect memory leak fixes, using strategy from D86968 to use SpecificBumpPtrAllocator rather than BumpPtrAllocatotr.

Updating an incorrect typo introduced from the fix-up patch.

yroux added a comment.Dec 17 2020, 1:03 AM

Hi Andrew, the new version LGTM

MaskRay added inline comments.

Try not to introducing global namespace types and variables (I fixed one in b69fe48ccf9ec19f6237ee2e9d16fc6a7071c17c)