Outliner: Add MIR-level outlining pass

[paquette]

Summary

This is an updated patch for the outliner described in the RFC at: http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html

The outliner is a code-size reduction pass which works by finding repeated sequences of instructions in a program, and replacing them with calls to functions. This would be especially useful to people working in low-memory environments, where sacrificing performance for space is acceptable.

This would add a interprocedural outliner directly before printing assembly. For reference on how this would work, this patch also includes X86 target hooks and an X86 test.

The outliner is run like so:

clang -mno-red-zone -mllvm -enable-machine-outliner file.c

I would love for people to test it out and tell me about how well it works for them, and maybe even play around with the provided target hooks. Tell me what you think!

[paquette]

Thanks for the feedback on the previous patches! I've updated the outliner significantly from the previous version. In this version there is...

• No suffix tree in ADT: The suffix tree is now a part of MachineOutliner.h

• No TerminatedString: Everything is done just using std::vectors now with a couple helper methods.

• Slightly different outlining technique: We don't have to keep track of offsets anymore by sorting candidates in descending order rather than ascending order.

• Better documentation, comments, etc: I fixed up the Doxygen stuff, went through, and wrote detailed explanations of each function. I also added some FIXMEs and TODOs to help guide further development on the outliner.

Tell me what you think!

[aprantl]

It might help to mark all comments that were addressed so far as "Done" in phabricator.

[paquette]

I realized I missed a bunch of stuff on MachineOutliner.cpp/MachineOutliner.h, so I went ahead and picked through the code and fixed a good chunk of it.

Highlights:

• No more MachineOutliner.h!
• Less gross X86 TargetInstrInfo!
• Range-based for loops!
• Proper pass initialization!

I'd also like to ask about the best way to handle custom epilogue/prologue insertion. I left in the three separate virtual functions in TargetInstrInfo.h. Does anyone think it'd be better to just smack them all together into one function which handles function call insertion? I feel like that'd be the best way to do it, but I left it as is for now.

Thanks!
Jessica

[• chadbrewbaker]

It would be awesome to have an option that serializes the Collection for use by external tools like Souper:
//std::vector<std::vector<unsigned> *> Collection;

Perhaps replace SuffixTree with SuffixContainer<SuffixTree> and SuffixContainter<SuffixArray>? Suffix arrays are more performant and are trivial to copy. Suffix trees are nice to walk.

Also, think about Vitanyai's approximation of Kolmogorov complexity using gzip, https://arxiv.org/pdf/cs/0111054.pdf

Dirty hack, but you could use the nesting of instructions that gzip comes up with.

[MatzeB]

Hi Jessica,

this is great progress from the last patch! I think we need one more roundtrip until we can commit the code and keep improving it inside the repository (as this is an independent pass it shouldn't affect the rest of the compiler).

For the whole Outliner.cpp file: Internal types and functions should be marked as such. In this case it's probably best to open an anonymous namespace (except for the externally visible functions createOutlinerPass(), and InitializerMachineOutliner())

include/llvm/CodeGen/Passes.h

401

Indent.

include/llvm/Target/TargetInstrInfo.h

1517–1563

You should move this block a bit upwards (We usually try to keep private fields at the beginning or end of a class, this would move them in the middle).

1559

As this is a codegen API passing in a MachineFunction& parameter is more natural. (Implementations can always use MF.getFunction() to get back to the llvm::Function)

lib/CodeGen/MachineOutliner.cpp

1

MachineOutliner.cpp

108

std::pair<String *, size_t>?

178–186

Looks like this could be a constructor.

179

This looks like it could just be a constructor on the SuffixTreeNode struct.

189

Should this be called deleteSuffixTreeSubTree or similar as it deletes more than 1 node?

205–206

this has no effect

391

can be size_t size() const

397

\param

416–417

No need for to cast EndIdx.

468

use a reference instead of a pointer?

476

Could do an early exit:

if (MaxHeight == 0)
  return nullptr;

551

the braces around the cases are unnecessary

582

This can use an early exit so you do not need to indent everything inside the if.

595

This seems to be an impossible case as you already tested for N != nullptr.

617–621

This could be

for (SuffixTreeNode *T = N->Link; T && T != Root; T = T->Link)
  T->Valid = false;

(It is usually better to go with a for loop instead of while() { ... increment; } on principle, because you do not have to remember to duplicate the increment code when you want to use continue somewhere inside the loop)

630–631

Maybe do not initialize these to give a hint to the reader that they will be set by findString() anyway (If findString() doesn't always set them, then you should make it).

634

Could be an early exit.

647

Use const StringCollection &Strings

666

The deleteSuffixTreeNode() implementation already protects against nullptrs.

713

the llvm:: prefix should not be necessary (same for OccBB)

741

You probably only need to put INITIALIZE_PASS and createOutlinerPass() in the llvm namespace.

772

Maybe use "MIR Function Outlining" to be in sync with INITIALIZE_PASS. Most llvm pass 'names' read more like short descriptions.

799–801

Could use references instead of pointers.

843–845

This makes no sense.

853

Maybe use "machine-outliner" to be in sync with DEBUG_TYPE.

868

Maybe add assert(CurrLegalInstrMapping < CurrIllegalInstrMapping && "Overflow"); The same at the place where you increment CurrLegalInstrMapping.

875–877

The find(), if (I != end()) ... else insert() sequence walks over the datastructure in the find() and again in the insert() step.

Instead you can simply always insert() and check the return value to see whether an element was actually inserted or an existing one reused:

auto I = map.insert(make_pair(MI, CurrLegalInstrMapping));
// Newly inserted?
if (I.second)
  CurrLegalInstrMapping++;
unsigned MINumber = I.first;

895

Use a reference.

990

I don't think the value names need to be kept around.

1019

Can be begin() instead of instr_begin().

1024

Should probably document this with something like
`// The cloned memory operands reference the old function. Drop them.`

1025

can be MBB->begin()

1047–1050

Could use a range based for:

for (OutlinedFunction &OF : FunctionList)
  OF.MF = createOutlinedFunction(M, OF);

1108–1112

Constructing names should not be necessary here. You should be able to add a GlobalValue MachineOperand instead of a Symbol one when you construct the call instruction.

1147–1149

You can move those out of the loop.

1158

There seems to be an unnecessary duplication of the string.

[silvas]

Some stylistic comments.

Also, the amount of testing seems small compared to the amount of code being added. Can you beef it up? Especially testing for the handling of "unsafe" cases would be good.

lib/CodeGen/MachineOutliner.cpp

16

A link to your devmtg talk might be good (together with some explanation about how it relates to what is implemented here).

54

This seems to have some nontrivial invariants, so you may want something a bit stronger than a typedef. Maybe a lightweight struct around this would be better? You already have a couple helpers that seems like they could quite naturally be methods of such a struct.

I guess the question is: does it ever make sense for a random piece of code that is using this typedef to actually operate on it using the std::vector API? Or would such code inherently risk violating some sort of invariant? If the latter, a lightweight struct encapsulating the underlying vector is likely to be a good choice.

60

This doesn't really make much sense to me. Can you explain this data structure a bit better?

73

This could use a better name.

124

Is there a good online resource you can link to about Ukkonen's algorithm? If this implementation is patterned off of a particular resource that might be good to link to if possible.

126

Small coding standard nit: use static/anonymous namespace on all the helper stuff here and elsewhere: http://llvm.org/docs/CodingStandards.html#anonymous-namespaces

141

I assume "start" was meant here. But "star index" (as in Kleene) sounds vaguely plausible in the context of a string algorithm so this typo is worth fixing.

152

Do you really need a std::map? http://llvm.org/docs/ProgrammersManual.html#map-like-containers-std-map-densemap-etc

Also, if the number of outgoing edges is small, a small-type container is probably better here.

157

As per the comment, maybe call this "is in tree" or "already pruned" or something like that?

163

Can you be a bit more specific about where this shortcut link comes in in Ukkonen's algorithm?

172

Both Start and End here are described as "index" but one is a pointer. That's worth explaining in the comment.

Also, SuffixIndex is also an "index" and gets an "Index" suffix to its variable name. Maybe these should be StartIndex and EndIndex?
Also, other places in this patch use Idx for variable names to mean "index". Maybe these should be StartIdx etc.?

306

Move the comment inside the braces so that this can use the more common } else { style, here and elsewhere.

337

There's quite a few naked new/delete in this code. Can you encapsulate the ownership better? If not, can you centralize the new/delete in helpers and add some comments about lifetime/ownership?

770

Can you hold this by value?

1175

Can you improve the ownership here? E.g. use a std::unique_ptr to manage the lifetime?

lib/CodeGen/TargetPassConfig.cpp

95

What is the official name? "machine outliner" or "MIR outliner". Please be consistent here and elsewhere.

[paquette]

Hi everyone,

I think I addressed most if not all of the comments from the previous patch; thanks for all of the help with reviewing this! I'm quite happy with how this has been coming along in progressing from intern project to real code.

Major changes:

• No use of raw new/delete in the outliner
• Tried to decouple the "program strings" from normal strings-- that seemed to be somewhat confusing
• New test which also checks if the outliner obeys basic block boundaries
• Lots of type changes; lots of things that didn't have to be pointers are no longer pointers
• More use of appropriate LLVM data structures for memory management, maps, etc.

Tell me what you think!

[silvas]

Great work!

This round of review feedback is mostly about comment accuracy and some implementation improvements like centralizing/encapsulating the numbering state machine, handling the EndIdx for leaf nodes in a simpler way, and avoiding copying too many vectors around. Also various style/readability nits.

The testing still seems light considering how much functionality this adds. Can we use MIR to test this? Ideally we'd have pretty good coverage of X86InstrInfo::isLegalToOutline
One way to think about this is: suppose we run this on a bunch of programs in the wild and find some bugs in the suffix tree construction algorithm or isLegalToOutline. How are we going to write tests for those fixes?
Since you've done such a nice job keeping SuffixTree separate (with the simple interface based on unsigned) it might even be possible to write a C++ unittest for it. That requires pulling it up into a header though and other headaches/boilerplate that might not be worth it right now.

lib/CodeGen/MachineOutliner.cpp

71

My reading of this comment interprets this as saying that this class e.g. holds a DenseMap of MI's to integers itself, but that is not the case. Can you make this more precise?

The term "mapping" is somewhat confusing since in common usage a "mapping" usually denotes a container. But throughout this patch the term "mapping" is used to refer to a "string". I think I get what sense it is meant in (e.g. "this is the mapping of this MBB through the our value numbering map"). I can't think of any really good names except for something horribly verbose like "StringOfInstructionNumbers" or something like that. Anyway, you probably want to beef up this comment to describe the sense in which "mapping" is used here and throughout this patch.

After staring at the patch for a while the term "mapping" has grown on me, so it's not a big deal.

73

Rather than a generic "this is used for compatibility with the suffix tree", can you be more precise. Something like "Our suffix tree implementation operates on this class" or something? After changing the constructor argument of SuffixTree to const std::vector<std::vector<unsigned>> & the only use of this class is as an internal data structure of the SuffixTree, which is an even more precise statement.

77

This description in terms of "hash" vs "unique" doesn't seem accurate. Once you pull out a class to encapsulate the numbering you can just mention that here. As far as users of this class are concerned the numbers are just unique symbols; I don't think you need to go into too much detail besides linking to the place where we assign the numbering.

100

Generally the term "program" is reserved for talking about the final linked executable, but this code (except during LTO) generally operates on a single Module/TU. Can you give this a better name? Maybe just BlockMappings or something like that.

144

Why is this comment talking about "2D mapping"? There is just a single index.

203

This comment is pure gold. Nice.

242

Comment on the + 1.

265

Isn't it a more like that the leaves "represent" suffixes rather than "contain" suffixes?

267

I don't think this is correct. It isn't the leaves representing suffixes per se that facilitates finding repeated substrings, but rather the fact that the internal nodes represent repeated substrings (shared prefixes of the suffixes). You may want to beef up this paragraph on suffix trees a bit to describe the basic invariants a bit more (leaves represent suffixes, internal nodes represent shared prefixes of the suffixes).

270

Same comment as on ProgramMapping. The integers themselves aren't hashes (otherwise this code would have to do something special for collisions).

280

I'm not sure what you are trying to convey with this paragraph. Maybe you can just mention that the implementation maintains parent links (maybe also describe what they are used for). I don't see the big picture for talking about cycles or explicit digraphs here.

289

The RAII behavior of BumpPtrAllocator is pretty well-known, so you don't need to explicitly mention it (that's the beauty of RAII; it just cleans up for you!). This comment can probably be reduced to "Allocator that owns all nodes in the tree".

293

This arrangement of adding an extra layer of indirection for the special "EndIdx" handling for leaf nodes is interesting but after staring at the code for a while it seems like it obscures things (or maybe I'm missing something).

It seems that the only thing that needs this extra layer of indirection is during construction in the test if (StrIdx > *(CurrSuffixTreeNode->EndIdx)) { which could be replaced by something like if (StrIdx > (CurrSuffixTreeNode->EndIdx == -1 : LeafEndIdx : CurrSuffixTreeNode->EndIdx) { or similar. To do that, SuffixTreeNode::EndIdx would just be an integer held by value, with -1 being a sentinel indicating that this is a leaf that needs the special handling in that one test.

295

what does the EndIdx even mean for an internal node, since they can be shared? Maybe explain that in the comment of the EndIdx member of SuffixTreeNode?

303

You can use the same BumpPtrAllocator for both of these if you want. It's kind of nice to have a place for these comments though so no biggie.

348

Can Parent just be a constructor argument?

367

This assert is inside an if(ChildPair.second != nullptr) so probably doesn't buy you much.

548

Nit: move the comment inside so you can use the coding-standard compliant } else if (...) {

596

Nit: Putting this CurrSuffixTreeNode->Children[QueryString[CurrIdx]] expression (used 3 times) in a variable will make things a bit shorter and also give you an opportunity to give that value a name. E.g. maybe if (Child && Child->IsInTree) {?

605

Nit: move this comment inside the else so that you have } else {.

614

Comment on the - 1 part of this. It's setting off my off-by-one error spidey sense.

674

You're copying quite a few std::vector's here. Can they be ArrayRef's?

726

This iterates over Strings.MBBMappings. In what sense does it treat Strings as "flat" if it looks at individual substrings?

Also, I find it a bit weird that we take a ProgramMapping as input to this constructor, but then all these append calls seem to build up a different ProgramMapping. Do the two ProgramMapping's end up being equivalent? It would be nice to see a bit more explanation about this. At least for the purposes of this constructor, maybe a const std::vector<std::vector<unsigned>> & is the natural interface because it doesn't use any of the fancy methods on ProgramMapping.

752

It seems a bit weird to me that this class is caring explicitly about the distinction between the "flat" and non-"flat" senses of ProgramMapping. I thought that ProgramMapping was just supposed to encapsulate a 2D ragged array and make it look flat, but here it seems that the external code still cares about the distinction between 2D-ness and flat-ness. Can you make it a bit clearer in the code and comments what ProgramMapping is supposed to represent and what its interactions with the rest of the code are?

798

I don't see much mention of the function Id's in ProgramMapping. Looking at the code, it seems like it should be unsigned and roughly represents the call instruction that jumps to the outlined function.

827

There are a couple members here related to the legal-instruction/illegal-instruction/function numbering that could stand to be pulled out into an isolated class (which can then be held by value in the pass) separate from the pass boilerplate. Such a class will also be a good place to authoritatively document the numbering scheme and encapsulate it.

944

Small readability nit: use std::tie(I, WasInserted) = ... or something like that to make this a bit clearer (this map interface returning the pair is always confusing without that).

1155

It isn't really the "function's id" but rather the id for a call instruction that jumps to it, right?

1156

Nit: remove commented out code.

[silvas]

lib/CodeGen/MachineOutliner.cpp

96

Can you add a high-level explanation of why we have a 2D vector in the first place. I.e. why do we need to "pretend" instead of just materializing the flattened vector?

One thing that may help make this clearer is encapsulating the mutation of MBBMappings a bit better. Right now there seem to be some un-encapsulated mutations, so just looking at the class it's not clear what the elementary operations on it are.

123

It shouldn't be too hard to bring this down to log(N) if necessary, but it surprises me that O(N) is fine when N = number of MBB's in the module (for reference, a typical FullLTO for a codebase ~ the size of clang has 10's of thousands of functions, and probably an order of magnitude more MBB's). Can you add a comment explaining that it takes linear time and why that's fine (or not fine, but fine for now)?

[aprantl]

lib/CodeGen/MachineOutliner.cpp

200

Did you get a chance to look into this?

[silvas]

I did a quick run on SPEC CPU 2006 with FullLTO and it seems like I ran into 3 different assertion failures across various programs: https://reviews.llvm.org/P7954
There seem to be 3 different assertions getting hit.

Here are some basic bugpoint-reduced test cases. Repro with llc -enable-machine-outliner -O3 foo.ll (though I expect these will be sensitive to minor codegen changes; I assume you have access to SPEC so you can reduce them again if needed)

https://reviews.llvm.org/P7957 :

Assertion `!NodePtr->isKnownSentinel()' failed.

https://reviews.llvm.org/P7958 :

Assertion `(isImpReg || Op.isRegMask() || MCID->isVariadic() || OpNo < MCID->getNumOperands() || isMetaDataOp) && "Trying to add an operand to a machine instr that is already done!"' failed.

https://reviews.llvm.org/P7960 :

Assertion `Occurrences.size() > 0 && "Longest repeated substring has no occurrences."' failed.

Also, here is a case that takes a really long time to compile (it does eventually finish) stuck in MachineOutliner::buildCandidateList :
https://reviews.llvm.org/P7959
Bugpoint found this one from the "Occurrences.size() > 0" assertion failure case.

For now, it's probably best to focus on the code review comments. Once the code is in good shape and committed, these sorts of bugs can be incrementally hammered out (tracked in bugzilla, fixed with clear individual patches (with test cases :) )).

include/llvm/CodeGen/Passes.h

402

Nit: comment and function aren't aligned.

include/llvm/Target/TargetInstrInfo.h

1518

Nit: inconsistent indent.

lib/CodeGen/MachineOutliner.cpp

49

Nit: this won't work on case-sensitive file systems.

[silvas]

In case you're wondering, that didn't take that long to reduce to that point. Just have to learn the tools and workflow. We have amazing tools for doing test case reduction and an easily understandable test-suite build system! (mad props to those who made bugpoint; the folks that made test-suite awesome; and LLD's -save-temps; and a bit of -globalopt and -metarenamer to clean things up)

[MatzeB]

• I hear that you are planning to get rid of the ProgramMapping construct which would be my last real stopper.
• There is still a lot of nitpicky stuff around.
• This time I checked the suffix tree construction algorithm which looks good.
• For future patches: Having a DenseMap<unsigned, SuffixTreeNode *> in every node is potentially wasteful. Intuitively I would expect the majority of nodes to only have a small number of entries, so it may be good to measure and explore alternative representations like a dynamically adapting datastructure (i.e. switching from linear list to map depending on number of children).

include/llvm/CodeGen/Passes.h

401–402

This should probably be createMachineOutlinerPass() to be consistent.

include/llvm/Target/TargetInstrInfo.h

1518

indentation.

You should also consider to move these functions towards the other functions so the "private:" part can stay at the end of the class definition.

1530

Indentation

1559

As this is a codegen API I would rather pass a MachineFunction&

lib/CodeGen/MachineOutliner.cpp

41

Move this below the #includes so you do not accidentally affect the headers.

64–65

Maybe drop the Stat suffix, esp. in a statistic dump that looks superfluous.

173

Suggestion (possibly for later patches):
As far as I see it a node is either a leaf or an inner node and never changes it nature. You could make this and the constraints on the End and Children members a bit more obvious when representing this in a type hierarchy (and safe a bit of memory):

struct SuffixTreeNode {
  bool IsLeaf; ...
};
struct SuffixTreeLeafNode : public SuffixTreeNode {
  size_t *EndIdx;
  size_t SuffixIdx;
};
struct SuffixTreeInternalNode : SuffixTreeNode {
  Map<SuffixTreeNode*> Children;
};

238

can be const.

239–244

• Maybe handle the special case early:

if (StartIdx == EmptyIdx)
  return 0;

return *EndIdx - StartIdx + 1;

• I assume this is not supposed to be called with *EndIdx == EmptyIdx? Add an assert()?

249–251

Interesting to see this packaged up in an own struct instead of just putting the members directly into the SuffixTree class. But doesn't hurt either I guess.

303

It looks like you can use a single allocator for nodes and EndIndexes.

346

Maybe add

else
  assert(EndIdx == EmptyIdx);

to make sure callers know what they are doing. An alternative would be to provide different functions for inserting leafs or inner nodes.

364

You can save an indentation level here with

if (ChildPair.second == nullptr)
  continue;

388

As you only have 1 "out" parameter you could simply return the new value instead. At the call side I find SuffixesToAdd = extend(x, y, SuffixesToAdd); easier to understand when you do not have to wonder whether a parameters is an "out" parameter.

The NeedsLink parameter is nullptr for all callers?

391–392

General note on comments: I would expect comments at this indentation level to talk about properties/situations at that level and not just inside the if. This gets clearer if you formulate the comment as a question, or an if-then statement (or move the comment into the if block):

// Look at the last character if the current mapping is 0.
if (Active.Len == 0)
  Active.Idx = EndIdx;

// Current mapping is 0?
if (Active.Len == 0) {
  // Look at the last added character.
  Active.Idx = EndIdx;
}

398

LastChar can be moved further down as it's not used by some paths through the function.

473

Add a comment that you check whether Active.Node is the root
or alternatively add a SuffixTreeNode::isRoot() function.

484–485

Indentation

491

This should rather be ArrayRef<unsigned>.

513

Add assert(SuffixesToAdd == 0);?

518

Maybe setSuffixIndices(..., /*LabelHeight =*/0) instead of the local variable so readers do not keep wondering whether it is an "out" parameter.

688

move this into the loop.

804–808

C++ does the right thing for Name(Name) etc. so you can drop the _ suffixes from the parameter names. Similar with some other constructors.

810

You should extend the anonymous namespace to include the MachineOutliner class. The only things that needs to be visible to the outside are initializeMachineOutlinerPass() (=the stuff coming out of INITIALIZE_PASS) and createOutlinerPass().

833

Because this relies on implementation details of DenseMapInfo, better play it safe with static_assert so the compilation fails if someone decides to change the values:

static_assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1);
static_assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2);

that way things also explain themselves and you can get away with a shorter comment.

The module pass instance can in theory be reused for multiple programs. So the state here needs to be initialized and cleared in runOnModule().

835

It's the next number to be assigned, isn't it? Same with CurrIllegalInstrMapping.

922

Indentation, MBB can be const

953–954

The overflow could (in theory) be triggered by a user and not just by compiler bugs. So could use report_fatal_error() so it stays around in release builds:

if (CurrLegalInstrMapping < CurIllegalInstrMapping)
  report_fatal_error("Instruction mapping overflow!");

955

Use DenseMapInfo<unsigned>::get{Empty|Tombstone}Key() instead of hardcoding the values.

1009

Could use emplace_back(OccBB, StartIdxInBB, ...)

1018

Could use emplace_back().

1051

I think getOrInsertFunction() copies the name and does not take ownership of the passed string so this is an unnecessary copy and a memory leak.

1067–1069

Use references for variables that cannot be nullptr.

1104–1105

I think CandidateList and FunctionList can be const or better ArrayRef.

1214

Move to assignment.

1215–1216

As you have some state such as CurrentFunctionID, CurrLegalMapping in the class anyway, maybe the two vectors and the Worklist can move there as well so you do not need to pass them around? Just need to clear() them at the end of the function then.

[MatzeB]

And a few more for the X86 part.

lib/Target/X86/X86InstrInfo.cpp

9613–9615

Heh, in theory every single x86 instruction modifies RIP. But I assume we don't model it like that in LLVM. In any way restricting this to reads(RIP) should be enough.

9625–9630

Are those tests necessary given that you already throw out operations with FrameIndex operands?

9632

You could use MachineInstr::isPosition() instead of checking for isLabel() and isCFIInstruction()

9635

Better use const MachineOperand &MOP to avoid some copying.

lib/Target/X86/X86InstrInfo.h

633

This linebreak seems unnecessary.

[aprantl]

lib/CodeGen/MachineOutliner.cpp

200

Ping :-)

Note that it is really important to skip over any DBG_VALUE intrinsics while deciding whether to outline a sequence of instructions. Otherwise compiling with -g will produce different code than without, which we generally consider to be serious bug in the compiler.

[paquette]

Alright, it's been a while, but here's the next version of the outlining patch! As always, thanks to everyone taking the time to read through all this code. This version of the outliner is quite different from the previous one, since I've improved on it a lot since the last patch.

Major changes

• More LLVM-ey and most comments addressed!

• X86 target won't outline debug instructions anymore. There are other things to think about wrt debug info, which I'm currently working on.

• More tests: Right now, MIR tests with the outliner make LLC unhappy, so I wrote a couple IR tests which should be easy enough to transition to MIR.

• No more ProgramMapping: instead there's another vector which keeps track of the positions of each instruction in the program. It uses iterators because the delete function on MachineBasicBlocks takes a start and end iterator. (If that makes anyone uncomfortable, I can change it to pointers.)

• Improved suffix tree pruning: the previous version was too aggressive and threw out too many candidates. The new version uses a vector of leaves.

• No more unnecessary functions: the previous version had a FIXME stating that sometimes the outliner could create unnecessary functions when all of the candidates for a function were removed. Now overlap pruning happens directly before outlining, so functions are created as they're needed.

• Outlined functions are now link once ODR: This allows the linker to dedupe outlined functions without LTO.

• Mapper class: This class performs the instruction-integer mappings and is passed around the outliner

• General suffix tree queries: Different targets will have different benefit functions, and even different types of functions to outline. For example, after this, I have a version of the outliner which supports tail-calling outlined functions. In the interest of keeping target-specific stuff out of the SuffixTree, the target now defines a benefit function, which is then maximized by the DFS query for repeated substrings. I think this will allow for more fine-grained outlining on various targets.

Tell me what you think!

[aprantl]

lib/Target/X86/X86InstrInfo.cpp

9622

This is not the right way to do this. We need to skip over DBG_VALUE instruction as if they didn't exist. Otherwise the presence of DBG_VALUEs in the instruction stream will have an effect on the outlining decision, which means that compiling with -g will generate different code than without.

Please also be sure to include a testcase that exercises this.

[MatzeB]

Thanks for pushing this, this is coming along nicely!

At this point I don't see any correctness or compiletime problems (with the comments below addressed).
Let's commit this and keep improving it in-tree. This should also make reviewing easier as we can have smaller follow-up patches.

lib/CodeGen/MachineOutliner.cpp

783–784

An instance of this only describes a single outlined function.

801

doxygen ///

845

I don't think you need to initialize this, it gets overwritten anyway in the next line.

1226–1242

Hmm...

• This hash doesn't seem collision free. Someone having two files with the same name (maybe in two different projects that he links together later) may happen.
• Of course a collision shouldn't hurt as the linker will compare the contents anyway, but why even bother with a hash then?
• I think the linker will only try to merge functions with the same name but the function name(-hash) is currently based on the name not the contents of the function so I would expect this to be not helpful in most cases.

Maybe stay with the previous internal linking and try the LinkOnce tricks in a follow-up commit (where it is based on the contents).

lib/Target/X86/X86InstrInfo.cpp

9634–9635

This is surprising, checking the MCInstrDesc should not be necessary.
This is most probably a bug somewhere else in codegen, so there is nothing we can do here.

However I'd be good if you could find the time later to create a reproducer and file a PR about it, reading and writing registers without having operands for it looks like a bug waiting to happen elsewhere.

test/CodeGen/X86/machine-outliner-basic.ll

1 ↗

(On Diff #89535)

Better use -mtriple=x86_64-- instead of -march so we also force the operating system etc.

24 ↗

(On Diff #89535)

You probably want to force this test to use the same outlined function everywhere. FileCheck allows assigning names and checking for repeated patterns:

; CHECK: callq [[_OUTLINED_FUNCTION[0-9]+_0:OUTLINEFUNC]]
...
; CHECK: callq [[OUTLINEFUNC]]
...
; CHECK-LABEL: [[OUTLINEFUNC]]:

test/CodeGen/X86/machine-outliner-bb-boundaries.ll

1 ↗

(On Diff #89535)

You can probably merge the tests together into a single file as they are all about the same pass and use the same llc flags.

22 ↗

(On Diff #89535)

I'd remove those standard dumping comments. If you actually care about the label give it a real name, if not the comment shouldn't be necessary either.

[silvas]

lib/CodeGen/MachineOutliner.cpp

1226–1242

Of course a collision shouldn't hurt as the linker will compare the contents anyway, but why even bother with a hash then?

No. linkonce_odr requires that if the name matches then the contents are interchangeable, since one gets selected arbitrarily. So for correctness the hash must be collision-free.

(see also the discussion in D29512 which also involves finding a stable "name" for the TU)

Also, I don't see the point of doing this. The linker's content-based deduplication ("ICF") should handle this case without caring about the name. If you want to use the linker's comdat/linkonce (i.e. name-based) deduplication then you can just use the function's contents as the name (mangling away NUL bytes), or a *strong* hash (collisions are a correctness problem).

Presumably, if users are using this pass, then they care about code size and so they are likely to have ICF enabled already. So I don't see the point of doing this linkage trick.

test/CodeGen/X86/machine-outliner-interprocedural.ll

8 ↗

(On Diff #89535)

The leading underscore here is darwin-specific. Add an explicit triple to avoid this (otherwise non-Darwin bots will break).

[silvas]

FYI this doesn't build on Linux with gcc

[94/1782] Building CXX object lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/MachineOutliner.cpp.o
FAILED: lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/MachineOutliner.cpp.o 
/usr/bin/c++   -DGTEST_HAS_RTTI=0 -DLLVM_BUILD_GLOBAL_ISEL -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/CodeGen -I/usr/local/google/home/silvasean/pg/llvm/llvm/lib/CodeGen -Iinclude -I/usr/local/google/home/silvasean/pg/llvm/llvm/include -fPIC -fvisibility-inlines-hidden -Wall -W -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wno-maybe-uninitialized -Wdelete-non-virtual-dtor -Wno-comment -std=c++11 -ffunction-sections -fdata-sections -O2 -g -DNDEBUG    -fno-exceptions -fno-rtti -MD -MT lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/MachineOutliner.cpp.o -MF lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/MachineOutliner.cpp.o.d -o lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/MachineOutliner.cpp.o -c /usr/local/google/home/silvasean/pg/llvm/llvm/lib/CodeGen/MachineOutliner.cpp
/usr/local/google/home/silvasean/pg/llvm/llvm/lib/CodeGen/MachineOutliner.cpp:171:18: error: enclosing class of constexpr non-static member function ‘bool {anonymous}::SuffixTreeNode::isLeaf() const’ is not a literal type
   constexpr bool isLeaf() const { return SuffixIdx != EmptyIdx; }
                  ^
/usr/local/google/home/silvasean/pg/llvm/llvm/lib/CodeGen/MachineOutliner.cpp:91:8: note: ‘{anonymous}::SuffixTreeNode’ is not literal because:
 struct SuffixTreeNode {
        ^
/usr/local/google/home/silvasean/pg/llvm/llvm/lib/CodeGen/MachineOutliner.cpp:91:8: note:   ‘{anonymous}::SuffixTreeNode’ has a non-trivial destructor
/usr/local/google/home/silvasean/pg/llvm/llvm/lib/CodeGen/MachineOutliner.cpp:174:18: error: enclosing class of constexpr non-static member function ‘bool {anonymous}::SuffixTreeNode::isRoot() const’ is not a literal type
   constexpr bool isRoot() const { return StartIdx == EmptyIdx; }
                  ^
[143/1782] Building CXX object lib/CodeGen/CMakeFiles/LLVMCodeGen.dir/RegAllocGreedy.cpp.o

The compiler is gcc 4.8.4

[silvas]

I just tested on SPECCPU2006 (FullLTO) and no assertion failures!

However, 403.gcc and 483.xalancbmk (at least) seem to have a huge compile time slowdown (superlinear behavior?). Some rough numbers comparing LLC runtime:
403.gcc 11s -> 66s
483.xalancbmk 16s -> 144s
(so about 5-10x slowdown of LLC due to the suffix tree)

Most of the time seems to be spent inside buildCandidateList. Sampling a couple stacks it seems like it is stuck in findBest, usually just 1 or 2 stack frames in findBest and so at least the problem isn't that it is recursing too deeply.
I added some printfs to print out the depth and vertex degree of each node in the suffix tree for 483.xalancbmk and I got this: https://reviews.llvm.org/F3114496

So it makes sense that typically one would be only 1 or 2 stack frames deep.

Modulo the pruning that is going on, we seem to do O(N) work in bestRepeatedSubstring once per outlining candidate. Is the pruning effective enough that the sum of all calls to bestRepeatedSubstring doesn't grow out of control? My suspicion is that it isn't, and I think a contrived case like AAABBBCCCDDD... (Assume "A" represents constant-size string large enough to be profitable to outline) will trigger O(N^2) behavior in the number of instructions in the module.
Is it possible to do algorithmically better? (exploiting suffix tree invariants maybe?)

Also, it looks like this pass actually increases (1-5%) text size on all of the SPEC binaries except for 401.bzip2: https://reviews.llvm.org/F3114409

(I double and triple checked and I don't have it switched around; the raw data (doublechecked the labels are right) is: https://reviews.llvm.org/P7971)

Can you please find out why this isn't helping (and in fact is hurting)? Are better heuristics needed? At the very least, the cost function seems like it needs to be amended to take into account the true overheads.

In particular, it seems that the cost function does not take into account that the outlined functions will have some minimum alignment applied to them (or can you mark them as not requiring this alignment? still, it would end up depending on linker placement (alignment of adjacent sections) and such as to how much padding actually is inserted).
On 483.xalancbmk, the suffix tree based outliner find 2311 functoins to outline, and almost all of them are 2 instructions, which is typically less than 16 bytes, which is the minimum alignment that will be imposed (just from looking at the output binary).
A naive approach which just looks for identical runs of outlinable instructions (ignoring substrings) outlines 2391 functions (slightly more). The total benefit is somewhat greater for the suffix tree though at 29379 vs 27994 for the naive approach.
This appears to be due to the outliner finding many more length-2 sequences to outline: https://reviews.llvm.org/F3114690

Overall, it seems like the vast majority of the benefit on 483.xalancbmk is due to extremely short instruction sequences. But if we are going to avoid very short instruction sequences because they actually aren't profitable, then most of the outlinable instructions disappear on this test case (and at a glance, the other SPEC benchmarks are pretty similar). I'd also like to note that this testing is with FullLTO, so it is a best-case scenario for the outliner (whole program visibility to the suffix tree). What kinds of programs does this outliner perform well on?

For reference, here are all the outlined functions from 483.xalancbmk: https://reviews.llvm.org/F3114805

One interesting thing is that they are almost all short sequences of mov instructions. Staring at the code that calls them, it's clear why this is: almost all of the outlined functions in 483.xalancbmk are in sequences like this:

...
  362a1e:`      e8 dd 20 0e 00       `  callq  444b00 <OUTLINED_FUNCTION2637142655534006531_61>
  362a23:`      e8 4c e8 09 00       `  callq  401274 <_ZN11xercesc_2_512XMLBufferMgr13releaseBufferERNS_9XMLBufferE>
...

(FWIW, I tried and IPRA doesn't actually decrease text size much on SPEC with FullLTO)

I.e. what has been outlined is function setup overhead. There are also quite a few outlined functions right before jumps, which are factoring out code sequences like this:

00000000004a2eb0 <OUTLINED_FUNCTION2637142655534006531_2458>:
  4a2eb0:`      48 8b 41 18          `  mov    0x18(%rcx),%rax
  4a2eb4:`      48 85 c0             `  test   %rax,%rax
  4a2eb7:`      c3                   `  retq␣␣␣
  4a2eb8:`      0f 1f 84 00 00 00 00 `  nopl   0x0(%rax,%rax,1)
  4a2ebf:`      00␣

lib/CodeGen/MachineOutliner.cpp

1032

If I understand what this is doing correctly, it can be easily made less than O(N^2) by sorting ascending by Start and descending by End (SROA does something similar to do efficient overlap calculations).

lib/Target/X86/X86InstrInfo.cpp

9597

This name does not follow the coding standard. Should be getOutliningBenefit or something

9610

isFunctionSafeToOutlineFrom

[silvas]

Also, this pass will almost surely introduce timing side-channel attacks into cryptography code (code that would otherwise by "constant time" and needs to be for security).

I'm not sure how heavily we care about this security aspect as a community, but I'm a slightly wary of having this on by default at any optimization level due to this issue. E.g. a size-constrained program for a secure processing element on a phone recompiles with this option and it silently breaks the security of the entire device. Hopefully the folks programming the secure element have some sort of testing to avoid this or at least have all critical primitives written in asm (or done by a hardware peripheral).

I can't think of any other optimizations we have that would move a program away from being "constant time"; is there any precedent?

[silvas]

In D26872#686175, @silvas wrote:

I'm not sure how heavily we care about this security aspect as a community, but I'm a slightly wary of having this on by default at any optimization level due to this issue.

Not that it is on by default right now. Just a concern to keep in mind down the road.

[MatzeB]

In D26872#686175, @silvas wrote:

Also, this pass will almost surely introduce timing side-channel attacks into cryptography code (code that would otherwise by "constant time" and needs to be for security).

I'm not sure how heavily we care about this security aspect as a community, but I'm a slightly wary of having this on by default at any optimization level due to this issue. E.g. a size-constrained program for a secure processing element on a phone recompiles with this option and it silently breaks the security of the entire device. Hopefully the folks programming the secure element have some sort of testing to avoid this or at least have all critical primitives written in asm (or done by a hardware peripheral).

I can't think of any other optimizations we have that would move a program away from being "constant time"; is there any precedent?

?!? This should be true for most compiler transformations. I don't know how these problems are handled in practice but I doubt they enable compiler optimizations. I don't see why we should start this discussion with this particular review.

[silvas]

In D26872#686220, @MatzeB wrote:

?!? This should be true for most compiler transformations. I don't know how these problems are handled in practice but I doubt they enable compiler optimizations. I don't see why we should start this discussion with this particular review.

I agree that we don't want to discuss it in this review (that's why I said "down the road"), but most compiler transformations I can think of remove indirection or otherwise simplify things towards the set of "constant time" instructions (such as elementary reg-reg adds and such). This pass introduces call instructions into arbitrary code (and calls on x86 architecturally write to memory and are subject to branch prediction, etc.). I agree, let's not have this discussion here though.

[silvas]

btw, down the road you may want to have this pass really know in detail the encoded length of each instruction on x86. There are quite a few *single instructions* that would be beneficial from a code size perspective to outline (if the outlined function is set to have alignment of 1). A quick analysis of an LLD binary (which contains all of LLVM linked in for LTO) shows there is over 5% code size savings just from outlining single instructions (since many x86 instructions encode to be larger than a CALL instruction which is 5 bytes). About half of the benefit (so about 2-3% of the total on this test case) comes from instructions that reference the stack via %rsp (mostly zeroing out stack slots), which could still be outlined if the offset was rewritten.

[paquette]

In D26872#686155, @silvas wrote:

... 403.gcc and 483.xalancbmk (at least) seem to have a huge compile time slowdown (superlinear behavior?). Some rough numbers comparing LLC runtime:
403.gcc 11s -> 66s
483.xalancbmk 16s -> 144s
(so about 5-10x slowdown of LLC due to the suffix tree)

Most of the time seems to be spent inside buildCandidateList. Sampling a couple stacks it seems like it is stuck in findBest...
...
Modulo the pruning that is going on, we seem to do O(N) work in bestRepeatedSubstring once per outlining candidate. Is the pruning effective enough that the sum of all calls to bestRepeatedSubstring doesn't grow out of control? My suspicion is that it isn't, and I think a contrived case like AAABBBCCCDDD... (Assume "A" represents constant-size string large enough to be profitable to outline) will trigger O(N^2) behavior in the number of instructions in the module.
Is it possible to do algorithmically better? (exploiting suffix tree invariants maybe?)

Yeah that'd be a nasty case, and it's worth looking into, for sure.

Some quick ideas off the top of my head:

• Pre-prune nodes which can never lead to outlining candidates while setting suffix indices. This would still be vulnerable to programs that look like AABBCC, but may improve query time on average.
• Keep track of a collection of prospective "Outlining points". During the first traversal, if we find anything beneficial remember where it was. On the next traversal, if we have a next best point, start at that point instead of the root.
• Keep track of every beneficial substring, during one O(n) traversal, and prune overlaps choosing the most beneficial ones greedily.

In D26872#686155, @silvas wrote:

... it seems that the cost function does not take into account that the outlined functions will have some minimum alignment applied to them (or can you mark them as not requiring this alignment? still, it would end up depending on linker placement (alignment of adjacent sections) and such as to how much padding actually is inserted).

I'll have to look into that and see what happens.

In D26872#686155, @silvas wrote:

On 483.xalancbmk, the suffix tree based outliner find 2311 functoins to outline, and almost all of them are 2 instructions, which is typically less than 16 bytes, which is the minimum alignment that will be imposed (just from looking at the output binary).
...
Overall, it seems like the vast majority of the benefit on 483.xalancbmk is due to extremely short instruction sequences. But if we are going to avoid very short instruction sequences because they actually aren't profitable, then most of the outlinable instructions disappear on this test case (and at a glance, the other SPEC benchmarks are pretty similar). I'd also like to note that this testing is with FullLTO, so it is a best-case scenario for the outliner (whole program visibility to the suffix tree).

Did you modify the benefit function to verify that removing length-2 instruction sequences actually removes most candidates? We could have found, say BC as the most beneficial, which would prune out all instances of ABC. There could very well be repeated instances of ABC that would be beneficial to outline. It might be possible to impose a minimum length restriction on x86 without losing all of the candidates.

In D26872#686155, @silvas wrote:

What kinds of programs does this outliner perform well on?

In the test suite, the x86 outliner tended to do well on programs with heavy macro usage or automatically-generated code.

As you found, x86 is a particularly hostile environment for this sort of pass. :) It was just used for a proof of concept and for ease of testing. Most work for this pass should be done for other targets, like, say ARM64.

In D26872#686770, @silvas wrote:

btw, down the road you may want to have this pass really know in detail the encoded length of each instruction on x86. There are quite a few *single instructions* that would be beneficial from a code size perspective to outline (if the outlined function is set to have alignment of 1). A quick analysis of an LLD binary (which contains all of LLVM linked in for LTO) shows there is over 5% code size savings just from outlining single instructions (since many x86 instructions encode to be larger than a CALL instruction which is 5 bytes). About half of the benefit (so about 2-3% of the total on this test case) comes from instructions that reference the stack via %rsp (mostly zeroing out stack slots), which could still be outlined if the offset was rewritten.

I would really love to do this, but I'm not sure if it's possible in LLVM at the moment. If it is, then I'll gladly add it in since I think it's probably one of the main reasons that x86 tests can get larger rather than smaller. The only thing that's (architecturally) tricky is that the target would need to know about the instruction-integer mappings. This could be done by moving the InstructionMapper over to the target, but I'm not sure if that's the best approach. If it's okay to do that, I doubt it'd be too difficult.

[paquette]

Okay, here's the next revision, everyone!

Changes

• Debug info is now skipped over as if it doesn't exist
• isLegalToOutline->getOutliningType, which returns Legal, Illegal, or Invisible. Invisible is used for instructions which should be ignored.
• Combined outliner tests
• Added test with debug info
• Outlined functions are private again without the wonky "hash"
• Style conformance changes, etc.

[MatzeB]

My LGTM still stands. Should I commit on your behalf or do you already have access?

[aprantl]

lib/Target/X86/X86InstrInfo.cpp

9649

Thanks!

test/CodeGen/X86/machine-outliner-debuginfo.ll

43 ↗

(On Diff #89928)

There should also be a negative check to ensure no DBG_VALUE is in the outlined function and that that no debug locations are attached to the outlined function.

[paquette]

In D26872#687815, @MatzeB wrote:

My LGTM still stands. Should I commit on your behalf or do you already have access?

I don't have commit access yet, so go ahead.

[paquette]

Changes

• Added negative test for debug info in machine-outliner-debuginfo.ll. The check allows for is_stmt debug stuff because that seems to be out of my control.

[paquette]

Changes

• Realized that the last debug test wasn't sufficient, so I fixed it up. It now handles debug values as well.

[paquette]

Third time is the charm. Edits to the tests. The debug test now *truly* makes sure that debug values don't impact outlining. Also removed some cruft from the tests.

[MatzeB]

I went ahead and committed the current state as we believe all immediately actionable things are addressed. And I'd really like us to do further work on it upstream so we don't get a 2000 lines review for every little change.

We do appreciate all the discussion here and hope we can continue on llvm-dev and the upcoming patches.

[silvas]

Nice to see this finally land!

FWIW, I did talk to a security professional inside google (the type of person for which common advice "don't write your own crypto" doesn't apply) and they said that they weren't particularly worried about the transformation done by this pass. Phew!

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   /// if available with PysicalRegisterUsageInfo pass.
   FunctionPass *createRegUsageInfoPropPass();
 
   /// This pass performs software pipelining on machine instructions.
   extern char &MachinePipelinerID;
 
   /// This pass frees the memory occupied by the MachineFunction.
   FunctionPass *createFreeMachineFunctionPass();
+
+  /// This pass performs outlining on machine instructions directly before printing assembly.
+   ModulePass *createOutlinerPass();
 } // End llvm namespace
 
 /// Target machine pass initializer for passes with dependencies. Use with
 /// INITIALIZE_TM_PASS_END.
 #define INITIALIZE_TM_PASS_BEGIN INITIALIZE_PASS_BEGIN
 
 /// Target machine pass initializer for passes with dependencies. Use with
 /// INITIALIZE_TM_PASS_BEGIN.
 #define INITIALIZE_TM_PASS_END(passName, arg, name, cfg, analysis)             \

include/llvm/InitializePasses.h

 void initializeMachineCombinerPass(PassRegistry &);
 void initializeMachineCopyPropagationPass(PassRegistry&);
 void initializeMachineDominanceFrontierPass(PassRegistry&);
 void initializeMachineDominatorTreePass(PassRegistry&);
 void initializeMachineFunctionPrinterPassPass(PassRegistry&);
 void initializeMachineLICMPass(PassRegistry&);
 void initializeMachineLoopInfoPass(PassRegistry&);
 void initializeMachineModuleInfoPass(PassRegistry&);
+void initializeMachineOutlinerPass(PassRegistry&);
 void initializeMachinePipelinerPass(PassRegistry&);
 void initializeMachinePostDominatorTreePass(PassRegistry&);
 void initializeMachineRegionInfoPassPass(PassRegistry&);
 void initializeMachineSchedulerPass(PassRegistry&);
 void initializeMachineSinkingPass(PassRegistry&);
 void initializeMachineTraceMetricsPass(PassRegistry&);
 void initializeMachineVerifierPassPass(PassRegistry&);
 void initializeMemCpyOptLegacyPassPass(PassRegistry&);

include/llvm/Target/TargetInstrInfo.h

public:
   virtual bool isTailCall(const MachineInstr &Inst) const {
     return false;
   }
 
 private:
   unsigned CallFrameSetupOpcode, CallFrameDestroyOpcode;
   unsigned CatchRetOpcode;
   unsigned ReturnOpcode;
+
+  public:
+
+  /// Return true if the instruction is legal to outline.
+  virtual bool isLegalToOutline(MachineInstr &MI) const {
+    llvm_unreachable(
+        "Target didn't implement TargetInstrInfo::isLegalToOutline!");
+  }
+
+  /// Insert a custom epilogue for outlined functions.
+  /// This may be empty, in which case no epilogue or return statement will be
+  /// emitted.
+  virtual void insertOutlinerEpilog(MachineBasicBlock &MBB,
+                                    MachineFunction &MF) const {
+    llvm_unreachable(
+        "Target didn't implement TargetInstrInfo::insertOutlinerEpilog!");
+  }
+
+  /// Insert a call to an outlined function into the program.
+  /// Returns an iterator to the spot where we inserted the call. This must be
+  /// implemented by the target.
+  virtual MachineBasicBlock::iterator
+  insertOutlinedCall(MachineBasicBlock &MBB,
+                     MachineBasicBlock::iterator &It,
+                     MachineFunction &MF,
+                     MCSymbol *Name) const {
+    llvm_unreachable(
+        "Target didn't implement TargetInstrInfo::insertOutlinedCall!"
+        );
+  }
+
+  /// Insert a custom prologue for outlined functions.
+  /// This may be empty, in which case no prologue will be emitted.
+  virtual void insertOutlinerProlog(MachineBasicBlock &MBB,
+                                    MachineFunction &MF) const {
+    llvm_unreachable(
+        "Target didn't implement TargetInstrInfo::insertOutlinerProlog!"
+        );
+  }
+
+  /// Return true if the function can safely be outlined from.
+  /// By default, this means that the function has no red zone.
+  virtual bool functionIsSafeToOutlineFrom(Function &F) const {
+    llvm_unreachable(
+        "Target didn't implement TargetInstrInfo::functionIsSafeToOutlineFrom!"
+        );
+  }
 };
 
 /// \brief Provide DenseMapInfo for TargetInstrInfo::RegSubRegPair.
 template<>
 struct DenseMapInfo<TargetInstrInfo::RegSubRegPair> {
   typedef DenseMapInfo<unsigned> RegInfo;
 
   static inline TargetInstrInfo::RegSubRegPair getEmptyKey() {

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   MachineFunctionPass.cpp
   MachineFunctionPrinterPass.cpp
   MachineInstrBundle.cpp
   MachineInstr.cpp
   MachineLICM.cpp
   MachineLoopInfo.cpp
   MachineModuleInfo.cpp
   MachineModuleInfoImpls.cpp
+  MachineOutliner.cpp
   MachinePassRegistry.cpp
   MachinePipeliner.cpp
   MachinePostDominators.cpp
   MachineRegionInfo.cpp
   MachineRegisterInfo.cpp
   MachineScheduler.cpp
   MachineSink.cpp
   MachineSSAUpdater.cpp
add_llvm_library(LLVMCodeGen
   TargetRegisterInfo.cpp
   TargetSchedule.cpp
   TargetSubtargetInfo.cpp
   TwoAddressInstructionPass.cpp
   UnreachableBlockElim.cpp
   VirtRegMap.cpp
   WinEHPrepare.cpp
   XRayInstrumentation.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/CodeGen
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/CodeGen/PBQP
 
   LINK_LIBS ${PTHREAD_LIB}
 
   DEPENDS
   intrinsics_gen
   )
 
 add_subdirectory(SelectionDAG)
 add_subdirectory(AsmPrinter)
 add_subdirectory(MIRParser)
 add_subdirectory(GlobalISel)

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeImplicitNullChecksPass(Registry);
   initializeMachineCombinerPass(Registry);
   initializeMachineCopyPropagationPass(Registry);
   initializeMachineDominatorTreePass(Registry);
   initializeMachineFunctionPrinterPassPass(Registry);
   initializeMachineLICMPass(Registry);
   initializeMachineLoopInfoPass(Registry);
   initializeMachineModuleInfoPass(Registry);
+  initializeMachineOutlinerPass(Registry);
   initializeMachinePipelinerPass(Registry);
   initializeMachinePostDominatorTreePass(Registry);
   initializeMachineSchedulerPass(Registry);
   initializeMachineSinkingPass(Registry);
   initializeMachineVerifierPassPass(Registry);
   initializeXRayInstrumentationPass(Registry);
   initializePatchableFunctionPass(Registry);
   initializeOptimizePHIsPass(Registry);

lib/CodeGen/MachineOutliner.cpp

+//===---- MachineOutliner.h - Outline instructions -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Replaces repeated sequences of instructions with function calls.
+///
+/// This works by placing every instruction from every basic block in a
+/// suffix tree, and repeatedly querying that tree for repeated sequences of
+/// instructions. If a sequence of instructions appears often, then it ought
+/// to be beneficial to pull out into a function.
+///
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "machine-outliner"
+
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/passes.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+#include <map>
+#include <sstream>
+#include <vector>
+
+using namespace llvm;
+
+STATISTIC(NumOutlinedStat, "Number of candidates outlined");
+STATISTIC(FunctionsCreatedStat, "Number of functions created");
+
+// In the outliner, we store a "string" for each MachineBasicBlock in the
+// program. Each string consists of integers. Each integer is either the
+// unique hash for an instruction, or an unique integer. In the latter case,
+// the integer represents something we ought not to outline.
+
+/// Convenience typedef for the "string" type for the outliner.
+typedef std::vector<unsigned> String;
+
+/// Convenience typedef for a "two-dimensional string".
+// NOTE: This is used as a 2D array *and* as a 2D string.
+// For example, say we have these strings: [0,1,2] [3,4] [5,6,7]
+// Then a StringCollection SC consisting of those strings would look like this:
+//
+// [[0,1,2][3,4][5,6,7]]
+//
+// And we would have SC[0] = 0, SC[2] = 2, SC[7] = 7, etc.
+typedef std::vector<String *> StringCollection;
+
+/// Represents a non-existent index into the string.
+const size_t EmptyIndex = -1;
+
+/// Returns the index of the string containing the index \p Offset.
+///
+/// \param StringList The collection of strings to be queried.
+/// \param [in, out] Offset The query offset. Filled with the local offset in
+/// the returned string on success.
+///
+/// \returns The index of the string that \p Offset appears in.
+size_t indexAndOffsetHelper(const StringCollection &StringList,
+                            size_t &Offset) {
+  size_t StringIndex = 0;
+
+  while (StringIndex < StringList.size()) {
+    size_t CurrSize = StringList[StringIndex]->size();
+    if (Offset < CurrSize)
+      break;
+    Offset -= CurrSize;
+    ++StringIndex;
+  }
+
+  assert(StringIndex < StringList.size() && "Offset is out of bounds!");
+
+  return StringIndex;
+}
+
+/// Returns the element of \p StringList as a 2D string at \p QueryIndex.
+unsigned getElementInStringCollection(const StringCollection &StringList,
+                                      size_t QueryIndex) {
+  size_t StringIndex = indexAndOffsetHelper(StringList, QueryIndex);
+  return (*StringList[StringIndex])[QueryIndex];
+}
+
+/// Returns the index of the \p String containing the index \p QueryIndex and
+/// the offset \p QueryIndex maps into in that string.
+std::pair<unsigned, unsigned>
+getStringIndexAndOffset(const StringCollection &StringList, size_t QueryIndex) {
+  size_t StringIndex = indexAndOffsetHelper(StringList, QueryIndex);
+  return std::make_pair(StringIndex, QueryIndex);
+}
+
+/// Returns the string that contains the index \p QueryIndex in the 
+/// \p StringCollection \p StringList and the offset into that string that
+/// \p QueryIndex maps to.
+std::pair<std::vector<unsigned> *, size_t>
+stringContainingIndex(const StringCollection &StringList, size_t QueryIndex) {
+  size_t StringIndex = indexAndOffsetHelper(StringList, QueryIndex);
+  return std::make_pair(StringList[StringIndex], QueryIndex);
+}
+
+/// A data structure for fast string searching.
+///
+/// Suffix trees contain the suffixes of their input strings in their leaves.
+/// This property makes it possible to quickly determine long repeated
+/// substrings of strings.
+///
+/// In this implementation, a "string" is a vector of unsigned integers.
+/// These integers may result from hashing some data type. A suffix tree can
+/// contain 1 or many strings, which can then be queried as one large string.
+/// 
+/// The suffix tree is implemented using Ukkonen's algorithm for linear-time
+/// suffix tree construction.
+class SuffixTree {
+
+private:
+
+  /// A node in a suffix tree which represents a substring or suffix.
+  ///
+  /// Each node has either no children or at least two children, with the root
+  /// being a exception in the empty tree.
+  ///
+  /// Children are represented as a map between unsigned integers and nodes. If
+  /// a node N has a child M on unsigned integer k, then the string represented
+  /// by N is a proper prefix of the string represented by M.
+  ///
+  /// Each internal node contains a pointer to the internal node representing
+  /// the same string, but with the first character chopped off. This is stored
+  /// in \p Link. Each leaf node stores the star index of its respective suffix
+  /// in \p SuffixIndex.
+  struct SuffixTreeNode {
+    /// The parent of this node.
+    SuffixTreeNode *Parent = nullptr;
+
+    /// The children of this node.
+    ///
+    /// A child existing on an unsigned integer implies that from the string
+    /// represented *by the current node*, there is a way to reach *another*
+    /// string by tacking that character on the end of the current string.
+    std::map<unsigned, SuffixTreeNode *> Children;
+
+    /// Represents wherther or not the node has been pruned from the tree.
+    ///
+    /// If a node is invalid, then it is not considered in any future queries.
+    bool Valid = true;
+
+    /// If this node is internal, pointer to the internal node representing the
+    /// same string missing the first character.
+    ///
+    /// This is used as a shortcut in the construction algorithm. For more
+    /// information, look into Ukkonen's algorithm.
+    /// It is also used during the tree pruning process to let us quickly throw
+    /// out a bunch of potential overlaps.
+    SuffixTreeNode *Link;
+
+    /// Start index of this node's substring in the main string.
+    size_t Start;
+
+    /// End index of this node's substring in the main string.
+    size_t *End = nullptr;
+
+    /// Start index of this node's associated suffix if it is a leaf.
+    size_t SuffixIndex = EmptyIndex;
+  };
+
+  /// Create a node starting at \p S, ending at \p E, and with suffix link \p L.
+  SuffixTreeNode *createSuffixTreeNode(size_t S, size_t *E, SuffixTreeNode *L) {
+    SuffixTreeNode *Node = new SuffixTreeNode;
+    Node->Start = S;
+    Node->End = E;
+    Node->Link = L;
+
+    return Node;
+  }
+
+  /// Delete the node \p N.
+  void deleteSuffixTreeNode(SuffixTreeNode *N) {
+    if (N == nullptr)
+      return;
+
+    N->Link = nullptr;
+    N->Parent = nullptr;
+
+    if (N->SuffixIndex == EmptyIndex && N->End != nullptr)
+      delete N->End;
+
+    for (auto ChildPair : N->Children) {
+      if (ChildPair.second != nullptr) {
+        deleteSuffixTreeNode(ChildPair.second);
+        ChildPair.second = nullptr;
+      }
+    }
+
+    N = nullptr;
+  }
+
+  /// Return the length of the substring defined by \p N.
+  inline size_t nodeSize(const SuffixTreeNode &N) {
+    size_t SubstringLen = 0;
+
+    if (N.Start != EmptyIndex)
+      SubstringLen = *N.End - N.Start + 1;
+
+    return SubstringLen;
+  }
+
+  /// The sum of the lengths of the strings that form the input string.
+  size_t InputLen;
+
+  /// The amount by which we extend all leaves in the tree during the
+  /// construction algorithm
+  size_t LeafEnd;
+
+  /// Keeps track of what we're currently working on in the tree during the
+  /// construction algorithm.
+  struct ActiveState {
+
+    /// The current node in the tree.
+    SuffixTreeNode *Node = nullptr;
+
+    /// Index of the active character in the current substring.
+    size_t Idx = EmptyIndex;
+
+    /// Length of the current substring.
+    size_t Len = 0;
+  };
+
+  /// The active state for Ukkonen's algorithm.
+  ActiveState Active;
+
+  /// Set the end of each leaf in the tree after constructing it.
+  ///
+  /// Each leaf will store the start index of its respective suffix after
+  /// setting the leaf ends in its \p SuffixIndex.
+  void setLeafEnds(SuffixTreeNode *CurrentNode, size_t LabelHeight) {
+    if (CurrentNode == nullptr)
+      return;
+
+    bool IsLeaf = true;
+
+    for (auto ChildPair : CurrentNode->Children) {
+      if (ChildPair.second != nullptr) {
+        IsLeaf = false;
+        setLeafEnds(ChildPair.second,
+                    LabelHeight + nodeSize(*ChildPair.second));
+      }
+    }
+
+    if (IsLeaf)
+      CurrentNode->SuffixIndex = size() - LabelHeight;
+  }
+
+  /// Construct the suffix tree for the prefix of the input string ending at
+  /// \p EndIdx.
+  /// 
+  /// Used to construct the full suffix tree iteratively. For more detail,
+  /// see Ukkonen's algorithm.
+  ///
+  /// \param EndIdx The end index of the current prefix in the main string.
+  /// \param NeedsLink The internal \p SuffixTreeNode that needs a suffix link.
+  /// \param [in, out] SuffixesToAdd The number of suffixes that must be added
+  /// to complete the suffix tree at the current phase. 
+  void extend(size_t EndIdx, SuffixTreeNode *NeedsLink,
+                     size_t &SuffixesToAdd) {
+    while (SuffixesToAdd > 0) {
+
+      // The length of the current string is 0, so we look at the last added
+      // character to our substring.
+      if (Active.Len == 0)
+        Active.Idx = EndIdx;
+
+      // The first and last character in the current substring we're looking at.
+      unsigned FirstChar =
+          getElementInStringCollection(InputString, Active.Idx);
+
+      unsigned LastChar = getElementInStringCollection(InputString, EndIdx);
+
+      // During the previous step, we stopped on a node *and* it has no
+      // transition to another node on the next character in our current
+      // suffix.
+      if (Active.Node->Children[FirstChar] == nullptr) {
+        SuffixTreeNode *Child = createSuffixTreeNode(EndIdx, &LeafEnd, Root);
+        Child->Parent = Active.Node;
+        Active.Node->Children[FirstChar] = Child;
+
+        // The active node is an internal node, and we visited it, so it must
+        // need a link if it doesn't have one.
+        if (NeedsLink != nullptr) {
+          NeedsLink->Link = Active.Node;
+          NeedsLink = nullptr;
+        }
+      }
+
+      // There *is* a match, so we have to traverse the tree and find out where
+      // to put the node.
+      else {
+        SuffixTreeNode *NextNode = Active.Node->Children[FirstChar];
+
+        // The child that we want to move to already contains our current string
+        // up to some point.Move to the index in that node where we'd have a
+        // mismatch and try again.
+        size_t SubstringLen = nodeSize(*NextNode);
+        if (Active.Len >= SubstringLen) {
+          Active.Idx += SubstringLen;
+          Active.Len -= SubstringLen;
+          Active.Node = NextNode;
+          continue;
+        }
+
+        // The string is already in the tree, so we're done.
+        if (getElementInStringCollection(
+                InputString, NextNode->Start + Active.Len) == LastChar) {
+          if (NeedsLink != nullptr && !(Active.Node->Start == EmptyIndex)) {
+            NeedsLink->Link = Active.Node;
+            NeedsLink = nullptr;
+          }
+
+          Active.Len++;
+          break;
+        }
+
+        // If the other two cases don't hold, then we must have found a
+        // mismatch. In this case, we split the edge to represent the two
+        // choices: the old string we found, or the string on the mismatch.
+        size_t *SplitEnd = new size_t(NextNode->Start + Active.Len - 1);
+        SuffixTreeNode *SplitNode =
+            createSuffixTreeNode(NextNode->Start, SplitEnd, Root);
+        SplitNode->Parent = Active.Node;
+        Active.Node->Children[FirstChar] = SplitNode;
+
+        // Create the new node...
+        SuffixTreeNode *Child = createSuffixTreeNode(EndIdx, &LeafEnd, Root);
+
+        // The child of the split node on our mismatch = the new node.
+        Child->Parent = SplitNode;
+        SplitNode->Children[LastChar] = Child;
+
+        // The old node's parent becomes the split node.
+        NextNode->Start += Active.Len;
+        NextNode->Parent = SplitNode;
+        SplitNode->Children[getElementInStringCollection(
+            InputString, NextNode->Start)] = NextNode;
+
+        // We visited an internal node, so we have to update the suffix link.
+        if (NeedsLink != nullptr)
+          NeedsLink->Link = SplitNode;
+
+        NeedsLink = SplitNode;
+      }
+
+      // We've added something new to the tree. Now we can move to the next
+      // suffix.
+      SuffixesToAdd--;
+      if (Active.Node->Start == EmptyIndex) {
+        if (Active.Len > 0) {
+          Active.Len--;
+
+          // Move one index over in the string for the next step
+          Active.Idx = EndIdx - SuffixesToAdd + 1;
+        }
+      }
+
+      // Start the next phase at the next smallest suffix.
+      else {
+        Active.Node = Active.Node->Link;
+      }
+    }
+  }
+
+public:
+  /// The string the suffix tree was constructed for.
+  StringCollection InputString; 
+
+  /// The root of the suffix tree.
+  /// The root represents the empty string.
+  SuffixTreeNode *Root = nullptr;
+
+  /// The sum of the lengths of the strings contained in \p InputString.
+  size_t size() {
+    return InputLen; 
+  }
+
+  /// Append a new string to \p InputString and update the suffix tree.
+  ///
+  /// /param NewStr The string to append to the tree.
+  void append(String *NewStr) {
+    InputString.push_back(NewStr);
+
+    // Save the old size so we can start at the end of the old string
+    size_t OldSize = InputLen;
+    InputLen = OldSize + NewStr->size();
+
+    // Keep track of the number of suffixes we have to add of the current
+    // prefix.
+    size_t SuffixesToAdd = 0;
+    SuffixTreeNode *NeedsLink = nullptr; // The last internal node added
+
+    // OldSize is initially 0 on the insertion of the first string. At the
+    // insertion of the next string, OldSize is the index of the end of the
+    // previous string.
+    for (size_t EndIdx = OldSize; EndIdx < InputLen; EndIdx++) {
+      SuffixesToAdd++;
+      NeedsLink = nullptr;
+      LeafEnd = (size_t)EndIdx;
+      extend((size_t)EndIdx, NeedsLink, SuffixesToAdd);
+    }
+
+    // Set the leaf ends so we can query the tree.
+    size_t LabelHeight = 0;
+    setLeafEnds(Root, LabelHeight);
+  }
+
+  /// Traverse the tree depth-first and return the node whose substring is
+  /// longest and appears at least twice.
+  /// 
+  /// \param Node The current node being visited in the traversal.
+  /// \param LabelHeight The length of the node currently being visited.
+  /// \param MaxLength [in, out] The length of the longest repeated substring.
+  /// \param SubstringStartIdx [in, out] The start index of the first
+  /// occurrence of the longest repeated substring found during the query.
+  /// \param NumOccurrences [in, out] The number of times the longest repeated
+  /// substring appears.
+  void longestRepeatedNode(SuffixTreeNode &N, size_t LabelHeight,
+                           size_t &MaxLength, size_t &SubstringStartIdx,
+                           size_t &NumOccurrences) {
+
+    // We hit an internal node, so we can traverse further down the tree.
+    // For each child, traverse down as far as possible and set MaxHeight
+    if (N.SuffixIndex == EmptyIndex) {
+      for (auto ChildPair : N.Children) {
+        if (ChildPair.second && ChildPair.second->Valid)
+          longestRepeatedNode(*ChildPair.second,
+                              LabelHeight + nodeSize(*ChildPair.second),
+                              MaxLength, SubstringStartIdx, NumOccurrences);
+      }
+    }
+
+    // We hit a leaf, so update MaxHeight if we've gone further down the
+    // tree
+    else if (N.SuffixIndex != EmptyIndex &&
+             MaxLength < (LabelHeight - nodeSize(N))) {
+      MaxLength = LabelHeight - nodeSize(N);
+      SubstringStartIdx = N.SuffixIndex;
+      NumOccurrences = (size_t)N.Parent->Children.size();
+    }
+  }
+
+  /// Return a new \p String representing the longest substring of \p
+  /// InputString which is repeated at least one time.
+  /// 
+  /// \returns The longest repeated substring in the suffix tree if it exists,
+  /// and nullptr otherwise.
+  String *longestRepeatedSubstring() {
+    size_t MaxHeight = 0;
+    size_t FirstChar = 0;
+    SuffixTreeNode *N = Root;
+    size_t NumOccurrences = 0;
+
+    longestRepeatedNode(*N, 0, MaxHeight, FirstChar, NumOccurrences);
+    String *Longest = nullptr;
+
+    // We found something in the tree, so we know the string must appear
+    // at least once
+    if (MaxHeight > 0) {
+      Longest = new String();
+
+      for (size_t Idx = 0; Idx < MaxHeight; Idx++)
+        Longest->push_back(
+            getElementInStringCollection(InputString, Idx + FirstChar));
+    }
+
+    return Longest;
+  }
+
+  /// Perform a depth-first search for \p QueryString on the suffix tree.
+  ///
+  /// \param QueryString The string to search for.
+  /// \param CurrIdx The current index in the query string that is being
+  /// matched against.
+  /// \param CurrSuffixTreeNode The suffix tree node being searched in.
+  ///
+  /// \returns A \p SuffixTreeNode that \p QueryString appears in if such a
+  /// node exists, and nullptr otherwise.
+  SuffixTreeNode *findString(const String &QueryString, size_t &CurrIdx,
+                             SuffixTreeNode *CurrSuffixTreeNode) {
+    SuffixTreeNode *RetSuffixTreeNode;
+    SuffixTreeNode *NextNode;
+
+    if (CurrSuffixTreeNode == nullptr || CurrSuffixTreeNode->Valid == false) {
+      RetSuffixTreeNode = nullptr;
+    }
+
+    // If we're at the root we have to check if there's a child, and move to
+    // that child. We don't consume the character since Root represents the
+    // empty string
+    else if (CurrSuffixTreeNode->Start == EmptyIndex) {
+      if (CurrSuffixTreeNode->Children[QueryString[CurrIdx]] != nullptr &&
+          CurrSuffixTreeNode->Children[QueryString[CurrIdx]]->Valid) {
+        NextNode = CurrSuffixTreeNode->Children[QueryString[CurrIdx]];
+        RetSuffixTreeNode = findString(QueryString, CurrIdx, NextNode);
+      }
+
+      else {
+        RetSuffixTreeNode = nullptr;
+      }
+    }
+
+    // The node represents a non-empty string, so we should match against it and
+    // check its children if necessary
+    else {
+      size_t StrIdx = CurrSuffixTreeNode->Start;
+      enum FoundState { ExactMatch, SubMatch, Mismatch };
+      FoundState Found = ExactMatch;
+
+      // Increment CurrIdx while checking the string for equivalence. Set
+      // Found and possibly break based off of the case we find.
+      while (CurrIdx < QueryString.size() - 1) {
+
+        // Failure case 1: We moved outside the string, BUT we matched
+        // perfectly up to that point.
+        if (StrIdx > *(CurrSuffixTreeNode->End)) {
+          Found = SubMatch;
+          break;
+        }
+
+        // Failure case 2: We have a true mismatch.
+        if (QueryString[CurrIdx] !=
+            getElementInStringCollection(InputString, StrIdx)) {
+          Found = Mismatch;
+          break;
+        }
+
+        StrIdx++;
+        CurrIdx++;
+      }
+
+      // Decide whether or not we should keep searching.
+      switch (Found) {
+      case (ExactMatch):
+        RetSuffixTreeNode = CurrSuffixTreeNode;
+        break;
+      case (SubMatch):
+        NextNode = CurrSuffixTreeNode->Children[QueryString[CurrIdx]];
+        RetSuffixTreeNode = findString(QueryString, CurrIdx, NextNode);
+        break;
+      case (Mismatch):
+        RetSuffixTreeNode = nullptr;
+        break;
+      }
+    }
+
+    return RetSuffixTreeNode;
+  }
+
+  /// Find each occurrence of of a string in \p InputString. Prunes each
+  /// occurrence found from the tree by setting their nodes to invalid.
+  ///
+  /// \param QueryString The string to search for.
+  ///
+  /// \returns A pointer to a list of pairs of \p Strings and offsets into
+  /// \p InputString representing each occurrence if \p QueryString is present,
+  /// and nullptr otherwise.
+  std::vector<std::pair<String *, size_t>> *
+  findOccurrencesAndPrune(const String &QueryString) {
+    size_t Len = 0;
+    std::vector<std::pair<String *, size_t>> *Occurrences = nullptr;
+    SuffixTreeNode *N = findString(QueryString, Len, Root);
+
+    // FIXME: Pruning should happen in a separate function.
+    if (N != nullptr && N->Valid) {
+      N->Valid = false;
+      Occurrences = new std::vector<std::pair<String *, size_t>>();
+
+      // We matched exactly, so we're in a suffix. There's then exactly one
+      // occurrence.
+      if (N->SuffixIndex != EmptyIndex) {
+        size_t StartIdx = N->SuffixIndex;
+        auto StrPair = stringContainingIndex(InputString, StartIdx);
+        Occurrences->push_back(make_pair(StrPair.first, StartIdx));
+      }
+
+      // There are no occurrences, so return null.
+      else if (N == nullptr) {
+        delete Occurrences;
+        Occurrences = nullptr;
+      }
+
+      // There are occurrences, so find them and invalidate paths along the way.
+      else {
+        SuffixTreeNode *M;
+
+        for (auto ChildPair : N->Children) {
+          M = ChildPair.second;
+
+          if ((M != nullptr) && (M->SuffixIndex != EmptyIndex)) {
+            M->Valid = false;
+            size_t StartIdx = M->SuffixIndex;
+            auto StrPair = stringContainingIndex(InputString, StartIdx);
+            Occurrences->push_back(make_pair(StrPair.first, StartIdx));
+          }
+        }
+      }
+
+      // Now invalidate the original node.
+      N = N->Link;
+      while (N && N != Root) {
+        N->Valid = false;
+        N = N->Link;
+      }
+    }
+
+    return Occurrences;
+  }
+
+  /// Return the number of times the string \p QueryString appears in \p
+  /// InputString.
+  size_t numOccurrences(const String &QueryString) {
+    size_t Dummy = 0;
+    size_t NumOccurrences = 0;
+    SuffixTreeNode *N = findString(QueryString, Dummy, Root);
+
+    if (N != nullptr) {
+      if (N->SuffixIndex != EmptyIndex)
+        NumOccurrences = N->Parent->Children.size();
+
+      else
+        NumOccurrences = N->Children.size();
+    }
+
+    return NumOccurrences;
+  }
+
+  /// Create a suffix tree from a list of strings \p Strings, treating that list
+  /// as a flat string.
+  SuffixTree(StringCollection Strings) : InputLen(0), LeafEnd(EmptyIndex) {
+    size_t *RootEnd = new size_t(EmptyIndex);
+    Root = createSuffixTreeNode(EmptyIndex, RootEnd, Root);
+    Active.Node = Root;
+
+    for (auto *Str : Strings)
+      append(Str);
+  }
+
+  /// Create an empty suffix tree.
+  SuffixTree() : InputLen(0), LeafEnd(EmptyIndex) {
+    size_t *RootEnd = new size_t(EmptyIndex);
+    Root = createSuffixTreeNode(EmptyIndex, RootEnd, Root);
+    Active.Node = Root;
+  }
+
+  /// Delete the suffix tree by calling \p deleteSuffixTreeNode recursively.
+  ~SuffixTree() {
+    Active.Node = nullptr;
+    if (Root != nullptr)
+      deleteSuffixTreeNode(Root);
+  }
+};
+
+/// \brief An individual string of instructions to be replaced with a call
+/// to an outlined function.
+struct Candidate {
+  /// \brief The index of the \p MachineBasicBlock in the worklist containing
+  /// the first occurrence of this \p Candidate.
+  size_t BBIndex;
+
+  /// \brief The start index of this candidate in its containing \p String and
+  /// \p MachineBasicBlock.
+  size_t BBOffset;
+
+  /// The number of instructions in this \p Candidate.
+  size_t Length;
+
+  /// The start index of \p Str in the full 2D string.
+  size_t StartIdxIn2DString;
+
+  /// The index of this \p Candidate's \p OutlinedFunction in the list of
+  /// \p OutlinedFunctions.
+  size_t FunctionIdx;
+
+  /// The \p String that will be outlined.
+  /// Stored to ensure that we don't have any overlaps.
+  String *Str; // FIXME: This doesn't have to be stored
+
+  Candidate(size_t BBIndex_, size_t BBOffset_, size_t Length_,
+            size_t StartIdxIn2DString_, size_t FunctionIdx_, String *Str_)
+      : BBIndex(BBIndex_), BBOffset(BBOffset_), Length(Length_),
+        StartIdxIn2DString(StartIdxIn2DString_), FunctionIdx(FunctionIdx_),
+        Str(Str_) {}
+
+  /// Allows us to ensure that \p Candidates that appear later in the program
+  /// are outlined first.
+  bool operator<(const Candidate &rhs) const {
+    return StartIdxIn2DString > rhs.StartIdxIn2DString;
+  }
+};
+
+/// Stores information about an actual outlined function.
+struct OutlinedFunction {
+  /// The actual outlined function created.
+  /// This is initialized after we go through and create the actual function.
+  llvm::MachineFunction *MF;
+
+  /// \brief The MachineBasicBlock containing the first occurrence of the
+  /// string associated with this function.
+  llvm::MachineBasicBlock *OccBB;
+
+  /// The start index of the instructions to outline in \p OccBB.
+  size_t StartIdxInBB;
+
+  /// The end index of the instructions to outline in \p OccBB.
+  size_t EndIdxInBB;
+
+  /// The number this function will be assigned in the program.
+  size_t Name;
+
+  /// The number this function will be given in the full 2D string.
+  size_t Id;
+
+  /// The number of times that this function has appeared.
+  size_t OccurrenceCount;
+
+  OutlinedFunction(llvm::MachineBasicBlock *OccBB_, const size_t &StartIdxInBB_,
+                   const size_t &EndIdxInBB_, const size_t &Name_,
+                   const size_t &Id_, const size_t &OccurrenceCount_)
+      : OccBB(OccBB_), StartIdxInBB(StartIdxInBB_), EndIdxInBB(EndIdxInBB_),
+        Name(Name_), Id(Id_), OccurrenceCount(OccurrenceCount_) {}
+};
+
+namespace llvm {
+
+/// \brief An interprocedural pass which finds repeated sequences of
+/// instructions and replaces them with calls to functions.
+///
+/// Each instruction is mapped to an unsigned integer and placed in a string.
+/// The resulting string is then placed in a \p SuffixTree. The \p SuffixTree
+/// is then repeatedly queried for repeated sequences of instructions. Each
+/// non-overlapping repeated sequence is then placed in its own
+/// \p MachineFunctionand each instance is then replaced with a call to that
+/// function.
+struct MachineOutliner : public ModulePass {
+  static char ID;
+
+  /// \brief Used to either hash functions or mark them as illegal to outline
+  /// depending on the instruction.
+  DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
+      InstructionIntegerMap;
+
+  /// The last value assigned to an instruction we ought not to outline.
+  unsigned CurrIllegalInstrMapping;
+
+  /// The last value assigned to an instruction we ought to outline.
+  unsigned CurrLegalInstrMapping;
+
+  /// The ID of the last function created.
+  size_t CurrentFunctionID;
+
+  /// The names of each function created. 
+  std::vector<std::string *> *FunctionNames;
+
+  StringRef getPassName() const override { return "Outliner"; }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<MachineModuleInfo>();
+    AU.addPreserved<MachineModuleInfo>();
+    AU.setPreservesAll();
+    ModulePass::getAnalysisUsage(AU);
+  }
+
+  MachineOutliner() : ModulePass(ID) {
+    // FIXME: Release function names.
+    initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
+    FunctionNames = new std::vector<std::string *>;
+  }
+
+  /// Construct a proxy string for a MachineBasicBlock.
+  ///
+  /// This function translates each instruction into an unsigned integer. Two
+  /// instructions are assigned the same integer if they are identical. If an
+  /// instruction is deemed unsafe to outline, then it will be assigned an
+  /// unique integer. The resultant string is placed into a suffix tree and
+  /// queried for candidates.
+  ///
+  /// \param [out] Container Filled with the instruction-integer mappings for
+  /// the program.
+  /// \param BB The \p MachineBasicBlock to be translated into integers.
+  void buildProxyString(std::vector<unsigned> &Container,
+                        llvm::MachineBasicBlock *BB,
+                        const TargetRegisterInfo *TRI,
+                        const TargetInstrInfo *TII);
+
+  /// \brief Replace the sequences of instructions represented by the
+  /// \p Candidates in \p CandidateList with calls to \p MachineFunctions
+  /// described in \p FunctionList.
+  ///
+  /// \param Worklist The basic blocks in the program in order of appearance.
+  /// \param CandidateList A list of candidates to be outlined from the program.
+  /// \param FunctionList A list of functions to be inserted into the program.
+  bool outline(Module &M, std::vector<llvm::MachineBasicBlock *> &Worklist,
+               std::vector<Candidate> &CandidateList,
+               std::vector<OutlinedFunction> &FunctionList,
+               StringCollection &SC);
+
+  /// Creates a function for \p OF and inserts it into the program.
+  llvm::MachineFunction *createOutlinedFunction(Module &M,
+                                                const OutlinedFunction &OF);
+
+  /// Find potential outlining candidates and store them in \p CandidateList.
+  ///
+  /// For each type of potential candidate, also build an \p OutlinedFunction
+  /// struct containing the information to build the function for that
+  /// candidate.
+  ///
+  /// \param [out] CandidateList Filled with outlining candidates for the
+  /// module.
+  /// \param [out] FunctionList Filled with functions corresponding to each
+  /// type of \p Candidate.
+  /// \param WorkList The basic blocks in the program in order of appearance.
+
+  void buildCandidateList(std::vector<Candidate> &CandidateList,
+                          std::vector<OutlinedFunction> &FunctionList,
+                          std::vector<llvm::MachineBasicBlock *> Worklist,
+                          SuffixTree &ST);
+
+  /// Construct a suffix tree on the instructions in \p M and outline repeated
+  /// strings from that tree.
+  bool runOnModule(Module &M) override;
+};
+
+// FIXME: Free after printing.
+
+// Keep the function names from the outliner around to keep the ASMPrinter
+// happy...
+std::vector<std::string *> *OutlinerFunctionNames;
+ModulePass *createOutlinerPass() {
+  MachineOutliner *OL = new MachineOutliner();
+  OutlinerFunctionNames = OL->FunctionNames;
+  return OL;
+}
+}
+
+INITIALIZE_PASS(MachineOutliner, "outliner", "MIR Function Outlining", false, false)
+char MachineOutliner::ID = 0;
+
+void MachineOutliner::buildProxyString(std::vector<unsigned> &Container,
+                                       MachineBasicBlock *BB,
+                                       const TargetRegisterInfo *TRI,
+                                       const TargetInstrInfo *TII) {
+  for (MachineInstr &MI : *BB) {
+
+    // First, check if the current instruction is legal to outline at all.
+    bool IsSafeToOutline = TII->isLegalToOutline(MI);
+
+    // If it's not, give it a bad number.
+    if (!IsSafeToOutline) {
+      Container.push_back(CurrIllegalInstrMapping);
+      CurrIllegalInstrMapping--;
+    }
+
+    // It's safe to outline, so we should give it a legal integer. If it's in
+    // the map, then give it the previously assigned integer. Otherwise, give
+    // it the next available one.
+    else {
+      auto Mapping = InstructionIntegerMap.find(&MI);
+
+      if (Mapping != InstructionIntegerMap.end()) {
+        Container.push_back(Mapping->second);
+      }
+
+      else {
+        InstructionIntegerMap.insert(
+          std::make_pair(&MI, CurrLegalInstrMapping));
+        Container.push_back(CurrLegalInstrMapping);
+        CurrLegalInstrMapping++;
+        CurrentFunctionID++;
+      }
+    }
+  }
+}
+
+void MachineOutliner::buildCandidateList(
+    std::vector<Candidate> &CandidateList,
+    std::vector<OutlinedFunction> &FunctionList,
+    std::vector<MachineBasicBlock *> Worklist,
+    SuffixTree &ST) {
+
+  // TODO: It would be better to use a "most beneficial substring" query if we
+  // decide to be a bit smarter and use a dynamic programming approximation
+  // scheme. For a naive greedy choice, LRS and MBS appear to be about as
+  // effective as each other. This is because both can knock out a candidate
+  // that would be better, or would lead to a better combination of candidates
+  // being chosen.
+  String *CandidateString = ST.longestRepeatedSubstring();
+
+  // FIXME: Use the following cost model.
+  // Weight = Occurrences * length
+  // Benefit = Weight - [Len(outline prologue) + Len(outline epilogue) +
+  // Len(functon call)]
+  //
+  // TODO: Experiment with dynamic programming-based approximation scheme. If it
+  // isn't too memory intensive, we really ought to switch to it.
+  if (CandidateString != nullptr && CandidateString->size() >= 2) {
+    StringCollection SC = ST.InputString;
+    std::vector<std::pair<String *, size_t>> *Occurrences =
+        ST.findOccurrencesAndPrune(*CandidateString);
+
+    // Query the tree for candidates until we run out of candidates to outline.
+    do {
+      assert(Occurrences != nullptr &&
+             "Null occurrences for longestRepeatedSubstring!");
+
+      // If there are at least two occurrences of this candidate, then we should
+      // make it a function and keep track of it.
+      if (Occurrences->size() >= 2) {
+        std::pair<String *, size_t> FirstOcc = (*Occurrences)[0];
+
+        // The index of the first character of the candidate in the 2D string.
+        size_t IndexIn2DString = FirstOcc.second;
+
+        // Use that to find the index of the string/MachineBasicBlock it appears
+        // in and the point that it begins in in that string/MBB.
+        std::pair<size_t, size_t> FirstIndexAndOffset =
+            getStringIndexAndOffset(SC, IndexIn2DString);
+
+        // From there, we can tell where the string starts and ends in the first
+        // occurrence so that we can copy it over.
+        size_t StartIdxInBB = FirstIndexAndOffset.second;
+        size_t EndIdxInBB = StartIdxInBB + CandidateString->size() - 1;
+
+        // Keep track of the MachineBasicBlock and its parent so that we can
+        // copy from it later.
+        MachineBasicBlock *OccBB = Worklist[FirstIndexAndOffset.first];
+        FunctionList.push_back(
+            OutlinedFunction(OccBB, StartIdxInBB, EndIdxInBB,
+                             FunctionList.size(), CurrentFunctionID,
+                             Occurrences->size()));
+
+        // Save each of the occurrences for the outlining process.
+        for (auto &Occ : *Occurrences) {
+          std::pair<size_t, size_t> IndexAndOffset =
+              getStringIndexAndOffset(SC, Occ.second);
+
+          CandidateList.push_back(Candidate(
+              IndexAndOffset.first, // Idx of MBB containing candidate.
+              IndexAndOffset.second,   // Starting idx in that MBB.
+              CandidateString->size(), // Length of the candidate.
+              Occ.second,              // Start index in the full string.
+              FunctionList.size()-1, // Index of the corresponding function.
+              CandidateString // The actual string.
+              )
+          );
+        }
+
+        CurrentFunctionID++;
+        FunctionsCreatedStat++;
+      }
+
+      // Find the next candidate and continue the process.
+      CandidateString = ST.longestRepeatedSubstring();
+    } while (CandidateString && CandidateString->size() >= 2 &&
+             (Occurrences = ST.findOccurrencesAndPrune(*CandidateString)));
+
+    // Sort the candidates in decending order. This will simplify the outlining
+    // process when we have to remove the candidates from the string by
+    // allowing us to cut them out without keeping track of an offset.
+    std::stable_sort(CandidateList.begin(), CandidateList.end());
+  }
+}
+
+MachineFunction *
+MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF) {
+
+  // Create the function name and store it in the list of function names.
+  // This has to be done because the char* for the name has to be around
+  // after the pass is done for the ASMPrinter to print out.
+  std::ostringstream NameStream;
+  NameStream << "OUTLINED_FUNCTION" << OF.Name;
+  std::string *Name = new std::string(NameStream.str());
+  FunctionNames->push_back(Name);
+
+  // Create the function using an IR-level function.
+  LLVMContext &C = M.getContext();
+  Function *F = dyn_cast<Function>(
+      M.getOrInsertFunction(Name->c_str(), Type::getVoidTy(C), NULL));
+  assert(F != nullptr);
+
+  F->setLinkage(GlobalValue::PrivateLinkage);
+
+  BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
+  IRBuilder<> Builder(EntryBB);
+  Builder.CreateRetVoid();
+
+  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
+  MachineFunction &MF = MMI.getMachineFunction(*F);
+  MachineBasicBlock *MBB = MF.CreateMachineBasicBlock();
+  const TargetSubtargetInfo *STI = &(MF.getSubtarget());
+  const TargetInstrInfo *TII = STI->getInstrInfo();
+
+  /// Find where the occurrence we want to copy starts and ends.
+  DEBUG(dbgs() << "OF.StartIdxInBB = " << OF.StartIdxInBB << "\n";
+        dbgs() << "OF.EndIdxInBB = " << OF.EndIdxInBB << "\n";);
+
+  // Insert instructions into the function and a custom outlined
+  // prologue/epilogue.
+  MF.insert(MF.begin(), MBB);
+  TII->insertOutlinerEpilog(*MBB, MF);
+
+  auto It = OF.OccBB->instr_begin();
+  std::advance(It, OF.EndIdxInBB);
+
+  for (size_t i = 0, e = OF.EndIdxInBB - OF.StartIdxInBB + 1; i != e; i++) {
+    MachineInstr* MI = MF.CloneMachineInstr(&*It);
+    MI->dropMemRefs();
+    MBB->insert(MBB->instr_begin(), MI);
+    It--;
+  }
+
+  TII->insertOutlinerProlog(*MBB, MF);
+
+  DEBUG(dbgs() << "New function: \n"; dbgs() << *Name << ":\n";
+    for (MachineBasicBlock &MBB : MF)
+      MBB.dump(); 
+  );
+
+  return &MF;
+}
+
+bool MachineOutliner::outline(Module &M,
+                              std::vector<MachineBasicBlock *> &Worklist,
+                              std::vector<Candidate> &CandidateList,
+                              std::vector<OutlinedFunction> &FunctionList,
+                              StringCollection &SC) {
+  bool OutlinedSomething = false;
+
+  // Create an outlined function for each candidate.
+  for (size_t i = 0, e = FunctionList.size(); i < e; i++) {
+    OutlinedFunction OF = FunctionList[i];
+    FunctionList[i].MF = createOutlinedFunction(M, OF);
+  }
+
+  // Replace the candidates with calls to their respective outlined functions.
+  //
+  // FIXME: Change the suffix tree pruning technique so that it follows the
+  // *longest* path on each internal node which *contains the node* that we're
+  // invalidating stuff *for*. This will allow us to catch cases like this:
+  // Outline "123", Outline "112". This method would make this unnecessary.
+  //
+  // FIXME: Currently, this method can allow us to unnecessarily outline stuff.
+  // This should be done *before* we create the outlined functions.
+  for (const Candidate &C : CandidateList) {
+
+    size_t StartIndex = C.BBOffset;
+    size_t EndIndex = StartIndex + C.Length;
+
+    // If the index is below 0, then we must have already outlined from it.
+    bool AlreadyOutlinedFrom = EndIndex - StartIndex > C.Length;
+
+    // Check if we have any different characters in the string collection versus
+    // the string we want to outline. If so, then we must have already outlined
+    // from the spot this candidate appeared at.
+    if (!AlreadyOutlinedFrom) {
+      for (size_t i = StartIndex; i < EndIndex; i++) {
+        size_t j = i - StartIndex;
+        if ((*SC[C.BBIndex])[i] != (*(C.Str))[j]) {
+          FunctionList[C.FunctionIdx].OccurrenceCount--;
+          AlreadyOutlinedFrom = true;
+          break;
+        }
+      }
+    }
+
+    // If we've outlined from this spot, or we don't have enough occurrences to
+    // justify outlining stuff, then skip this candidate.
+    if (AlreadyOutlinedFrom || FunctionList[C.FunctionIdx].OccurrenceCount < 2)
+      continue;
+
+    // We have a candidate which doesn't conflict with any other candidates, so
+    // we can go ahead and outline it.
+    OutlinedSomething = true;
+    NumOutlinedStat++;
+
+    // Remove the candidate from the string in the suffix tree first, and
+    // replace it with the associated function's id.
+    auto Begin = SC[C.BBIndex]->begin() + C.BBOffset;
+    auto End = Begin + C.Length;
+
+    SC[C.BBIndex]->erase(Begin, End);
+    SC[C.BBIndex]->insert(Begin, FunctionList[C.FunctionIdx].Id);
+
+    // Now outline the function in the module using the same idea.
+    MachineFunction *MF = FunctionList[C.FunctionIdx].MF;
+    MachineBasicBlock *MBB = Worklist[C.BBIndex];
+    const TargetSubtargetInfo *STI = &(MF->getSubtarget());
+    const TargetInstrInfo *TII = STI->getInstrInfo();
+    MCContext &Ctx = MF->getContext();
+
+    // We need the function name to match up with the internal symbol
+    // build for it. There's no nice way to do this, so we'll just stick
+    // an l_ in front of it manually.
+    Twine InternalName = Twine("l_", MF->getName());
+    MCSymbol *Name = Ctx.getOrCreateSymbol(InternalName);
+
+    // Now, insert the function name and delete the instructions we don't need.
+    MachineBasicBlock::iterator StartIt = MBB->begin();
+    MachineBasicBlock::iterator EndIt = StartIt;
+
+    std::advance(StartIt, StartIndex);
+    std::advance(EndIt, EndIndex);
+    StartIt = TII->insertOutlinedCall(*MBB, StartIt, *MF, Name);
+    ++StartIt;
+    MBB->erase(StartIt, EndIt);
+  }
+
+  return OutlinedSomething;
+}
+
+bool MachineOutliner::runOnModule(Module &M) {
+  MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
+
+  std::vector<MachineBasicBlock *> Worklist;
+
+  // The current number we'll assign to instructions we ought not to outline.
+  CurrIllegalInstrMapping = -1;
+
+  // The current number we'll assign to instructions we want to outline.
+  CurrLegalInstrMapping = 0;
+  std::vector<std::vector<unsigned> *> Collection;
+
+  // Set up the suffix tree by creating strings for each basic block.
+  // Note: This means that the i-th string and the i-th MachineBasicBlock
+  // in the work list correspond to each other. It also means that the
+  // j-th character in that string and the j-th instruction in that
+  // MBB correspond with each other.
+  for (Function &F : M) {
+    MachineFunction &MF = MMI.getMachineFunction(F);
+    const TargetSubtargetInfo *STI = &(MF.getSubtarget());
+    const TargetRegisterInfo *TRI = STI->getRegisterInfo();
+    const TargetInstrInfo *TII = STI->getInstrInfo();
+
+    if (F.empty() || !TII->functionIsSafeToOutlineFrom(F))
+      continue;
+
+    for (MachineBasicBlock &MBB : MF) {
+      Worklist.push_back(&MBB);
+      std::vector<unsigned> Container;
+      buildProxyString(Container, &MBB, TRI, TII);
+      String *BBString = new String(Container);
+      Collection.push_back(BBString);
+    }
+  }
+
+  SuffixTree ST = SuffixTree(Collection);
+
+  // Find all of the candidates for outlining.
+  bool OutlinedSomething = false;
+  std::vector<Candidate> CandidateList;
+  std::vector<OutlinedFunction> FunctionList;
+
+  CurrentFunctionID = InstructionIntegerMap.size();
+  buildCandidateList(CandidateList, FunctionList, Worklist, ST);
+  OutlinedSomething = outline(M, Worklist, CandidateList, FunctionList, Collection);
+
+  for (size_t i = 0, e = Collection.size(); i != e; i++)
+    delete Collection[i];
+
+  return OutlinedSomething;
+}

lib/CodeGen/TargetPassConfig.cpp

 static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
     cl::desc("Print LLVM IR input to isel pass"));
 static cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden,
     cl::desc("Dump garbage collector data"));
 static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden,
     cl::desc("Verify generated machine code"),
     cl::init(false),
     cl::ZeroOrMore);
+static cl::opt<bool> EnableMIROutliner("enable-machine-outliner", cl::Hidden,
+    cl::desc("Enable machine outliner"));
 
 static cl::opt<std::string>
 PrintMachineInstrs("print-machineinstrs", cl::ValueOptional,
                    cl::desc("Print machine instrs"),
                    cl::value_desc("pass-name"), cl::init("option-unspecified"));
 
 static cl::opt<int> EnableGlobalISelAbort(
     "global-isel-abort", cl::Hidden,
void TargetPassConfig::addMachinePasses() {
   addPass(&FuncletLayoutID, false);
 
   addPass(&StackMapLivenessID, false);
   addPass(&LiveDebugValuesID, false);
 
   addPass(&XRayInstrumentationID, false);
   addPass(&PatchableFunctionID, false);
 
+  if (EnableMIROutliner)
+    PM->add(createOutlinerPass());
+
   AddingMachinePasses = false;
 }
 
 /// Add passes that optimize machine instructions in SSA form.
 void TargetPassConfig::addMachineSSAOptimization() {
   // Pre-ra tail duplication.
   addPass(&EarlyTailDuplicateID);
 

lib/Target/X86/X86InstrInfo.h

MachineInstr *foldMemoryOperandCustom(MachineFunction &MF, MachineInstr &MI,
                                         MachineBasicBlock::iterator InsertPt,
                                         unsigned Size, unsigned Align) const;
 
   /// isFrameOperand - Return true and the FrameIndex if the specified
   /// operand and follow operands form a reference to the stack frame.
   bool isFrameOperand(const MachineInstr &MI, unsigned int Op,
                       int &FrameIndex) const;
 
+public:
+  bool functionIsSafeToOutlineFrom(Function &F) const override;
+
+  bool isLegalToOutline(MachineInstr &MI) const override;
+
+  void insertOutlinerEpilog(MachineBasicBlock &MBB,
+                            MachineFunction &MF) const override;
+
+  void insertOutlinerProlog(MachineBasicBlock &MBB,
+                            MachineFunction &MF) const override;
+
+  MachineBasicBlock::iterator
+  insertOutlinedCall(MachineBasicBlock &MBB,
+                     MachineBasicBlock::iterator &It, MachineFunction &MF,
+                     MCSymbol *Name) const override;
+
   /// Returns true iff the routine could find two commutable operands in the
   /// given machine instruction with 3 vector inputs.
   /// The 'SrcOpIdx1' and 'SrcOpIdx2' are INPUT and OUTPUT arguments. Their
   /// input values can be re-defined in this method only if the input values
   /// are not pre-defined, which is designated by the special value
   /// 'CommuteAnyOperandIndex' assigned to it.
   /// If both of indices are pre-defined and refer to some operands, then the
   /// method simply returns true if the corresponding operands are commutable
   /// and returns false otherwise.
   ///
   /// For example, calling this method this way:
   ///     unsigned Op1 = 1, Op2 = CommuteAnyOperandIndex;
   ///     findThreeSrcCommutedOpIndices(MI, Op1, Op2);
   /// can be interpreted as a query asking to find an operand that would be
   /// commutable with the operand#1.
   bool findThreeSrcCommutedOpIndices(const MachineInstr &MI,
                                      unsigned &SrcOpIdx1,
                                      unsigned &SrcOpIdx2) const;
 };
 
 } // End llvm namespace
 
 #endif

lib/Target/X86/X86InstrInfo.cpp

void getAnalysisUsage(AnalysisUsage &AU) const override {
       MachineFunctionPass::getAnalysisUsage(AU);
     }
   };
 }
 
 char LDTLSCleanup::ID = 0;
 FunctionPass*
 llvm::createCleanupLocalDynamicTLSPass() { return new LDTLSCleanup(); }
+
+bool X86InstrInfo::functionIsSafeToOutlineFrom(Function &F) const {
+  return F.hasFnAttribute(Attribute::NoRedZone);
+}
+
+bool X86InstrInfo::isLegalToOutline(MachineInstr &MI) const {
+  int Dummy;
+
+  // Don't outline returns or basic block terminators.
+  if (MI.isReturn() || MI.isTerminator())
+    return false;
+
+  // Don't outline anything that modifies or reads from the stack pointer.
+  if (MI.modifiesRegister(X86::RSP, &RI) ||
+      MI.readsRegister(X86::RSP, &RI))
+    return false;
+
+  if (MI.modifiesRegister(X86::RIP, &RI) ||
+      MI.readsRegister(X86::RIP, &RI))
+    return false;
+
+  // Don't outline the frame setup or destroy for a function
+  if (MI.getFlag(MachineInstr::MIFlag::FrameSetup) ||
+      MI.getFlag(MachineInstr::MIFlag::FrameDestroy))
+    return false;
+
+  if (MI.isCFIInstruction())
+    return false;
+
+  if (isLoadFromStackSlot(MI, Dummy) || isStoreToStackSlot(MI, Dummy))
+    return false;
+
+  if (isLoadFromStackSlotPostFE(MI, Dummy) ||
+      isStoreToStackSlotPostFE(MI, Dummy))
+    return false;
+
+  if (MI.isLabel())
+    return false;
+
+  for (MachineOperand MOP : MI.operands())
+    if (MOP.isCPI() || MOP.isJTI() || MOP.isCFIIndex() || 
+        MOP.isFI() || MOP.isTargetIndex())
+        return false;
+
+  return true;
+}
+
+void X86InstrInfo::insertOutlinerEpilog(MachineBasicBlock &MBB,
+                                        MachineFunction &MF) const {
+  MachineInstr *retq = BuildMI(MF, DebugLoc(), get(X86::RETQ));
+  MBB.insert(MBB.begin(), retq);
+}
+
+void X86InstrInfo::insertOutlinerProlog(MachineBasicBlock &MBB,
+                                        MachineFunction &MF) const {
+  return;
+}
+
+MachineBasicBlock::iterator
+X86InstrInfo::insertOutlinedCall(MachineBasicBlock &MBB,
+                                 MachineBasicBlock::iterator &It,
+                                 MachineFunction &MF, MCSymbol *Name) const {
+  It = MBB.insert(
+      It, BuildMI(MF, DebugLoc(), get(X86::CALL64pcrel32)).addSym(Name));
+  return It;
+}

test/CodeGen/X86/machineoutliner.ll

+; RUN: llc -enable-machine-outliner -march=x86-64 < %s | FileCheck %s
+; Test that the outliner can outline a simple function.
+
+; Function Attrs: noredzone nounwind ssp uwtable
+define void @foo() #0 {
+entry:
+  ; CHECK-LABEL: foo:
+  %x = alloca i32, align 4
+  %y = alloca i32, align 4
+  %z = alloca i32, align 4
+  store i32 1, i32* %x, align 4
+  store i32 2, i32* %y, align 4
+  store i32 3, i32* %z, align 4
+  ret void
+  ; CHECK:  subq  $12, %rsp
+  ; CHECK:  callq l_OUTLINED_FUNCTION0
+  ; CHECK:  addq  $12, %rsp
+}
+
+; Function Attrs: noredzone nounwind ssp uwtable
+define i32 @main() #0 {
+entry:
+  ; CHECK-LABEL: main:
+  %retval = alloca i32, align 4
+  %x = alloca i32, align 4
+  %y = alloca i32, align 4
+  %z = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  store i32 1, i32* %x, align 4
+  store i32 2, i32* %y, align 4
+  store i32 3, i32* %z, align 4
+  ret i32 0
+  ; CHECK:  movl  $0, -16(%rbp)
+  ; CHECK:  callq l_OUTLINED_FUNCTION0
+  ; CHECK:  xorl  %eax, %eax
+
+}
+
+attributes #0 = { noredzone }
+; CHECK:  movl  $1, -12(%rbp)
+; CHECK:  movl  $2, -8(%rbp)
+; CHECK:  movl  $3, -4(%rbp)
+; CHECK:  retq