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

[AndrewLitteken]

Summary

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

[AndrewLitteken]

Updating for clang-format.

[samparker]

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?

[AndrewLitteken]

In D86975#2260463, @samparker wrote:

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: https://reviews.llvm.org/D87299

[jroelofs]

llvm/include/llvm/Transforms/IPO/IROutliner.h

175

llvm/lib/Transforms/IPO/IROutliner.cpp

239

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?

278

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

304

should make the copy cheaper

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

879

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

[AndrewLitteken]

llvm/lib/Transforms/IPO/IROutliner.cpp

239

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]

llvm/lib/Transforms/IPO/IROutliner.cpp

239

👍

[AndrewLitteken]

Vector use cleanup.

[AndrewLitteken]

Different handling of getSimilarity() to handle optionals.

[AndrewLitteken]

Fixing some small nits.

[AndrewLitteken]

Removing dead variable.

[yroux]

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

879

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]

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

879

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]

I think that the previous comments were addressed. LGTM

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

879

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

[AndrewLitteken]

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

[AndrewLitteken]

@paquette @jroelofs @yroux for reverting fix.

[AndrewLitteken]

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

[yroux]

Hi Andrew, the new version LGTM

[MaskRay]

llvm/include/llvm/Transforms/IPO/IROutliner.h

50

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