[MachineOutliner][NFC] Use MBB flags to avoid call checks in getOutliningInfo

We already determine a bunch of information about an MBB in
getMachineOutlinerMBBFlags. We can reuse that information to

[MachineOutliner][NFC] Use MBB flags to avoid call checks in getOutliningInfo

We already determine a bunch of information about an MBB in
getMachineOutlinerMBBFlags. We can reuse that information to avoid calculating
things that must be false/true.

The first thing we can easily check is if an outlined sequence could ever
contain calls. There's no reason to walk over the outlined range, checking for
calls, if we already know that there are no calls in the block containing the
sequence.

llvm-svn: 346809

show more ...

[MachineOutliner][NFC] Exit getOutliningType if there are < 2 candidates

Since we never outline anything with fewer than 2 occurrences, there's no
reason to compute cost model information if there's

[MachineOutliner][NFC] Exit getOutliningType if there are < 2 candidates

Since we never outline anything with fewer than 2 occurrences, there's no
reason to compute cost model information if there's less than that.

llvm-svn: 346803

show more ...

Fix uninitialized variable.

Flags variable was not initialized and later used (both isMBBSafeToOutlineFrom
implementations assume it's initialized), which breaks
test/CodeGen/AArch64/machine-outline

Fix uninitialized variable.

Flags variable was not initialized and later used (both isMBBSafeToOutlineFrom
implementations assume it's initialized), which breaks
test/CodeGen/AArch64/machine-outliner.mir. under memory sanitizer:
MemorySanitizer: use-of-uninitialized-value
#0 in llvm::AArch64InstrInfo::getOutliningType(llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>&, unsigned int) const llvm/lib/Target/AArch64/AArch64InstrInfo.cpp:5494:9
#1 in (anonymous namespace)::InstructionMapper::convertToUnsignedVec(llvm::MachineBasicBlock&, llvm::TargetInstrInfo const&) llvm/lib/CodeGen/MachineOutliner.cpp:772:19
#2 in (anonymous namespace)::MachineOutliner::populateMapper((anonymous namespace)::InstructionMapper&, llvm::Module&, llvm::MachineModuleInfo&) llvm/lib/CodeGen/MachineOutliner.cpp:1543:14
#3 in (anonymous namespace)::MachineOutliner::runOnModule(llvm::Module&) llvm/lib/CodeGen/MachineOutliner.cpp:1645:3
#4 in (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) llvm/lib/IR/LegacyPassManager.cpp:1744:27
#5 in llvm::legacy::PassManagerImpl::run(llvm::Module&) llvm/lib/IR/LegacyPassManager.cpp:1857:44
#6 in compileModule(char**, llvm::LLVMContext&) llvm/tools/llc/llc.cpp:597:8

llvm-svn: 346761

show more ...

[MachineOutliner][NFC] Change getMachineOutlinerMBBFlags to isMBBSafeToOutlineFrom

Instead of returning Flags, return true if the MBB is safe to outline from.

This lets us check for unsafe situatio

[MachineOutliner][NFC] Change getMachineOutlinerMBBFlags to isMBBSafeToOutlineFrom

Instead of returning Flags, return true if the MBB is safe to outline from.

This lets us check for unsafe situations, like say, in AArch64, X17 is live
across a MBB without being defined in that MBB. In that case, there's no point
in performing an instruction mapping.

llvm-svn: 346718

show more ...

[MachineOutliner][NFC] Early exit pruning when candidates don't share an MBB

There's no way they can overlap in this case.

This can save a few iterations when the candidate is close to the beginnin

[MachineOutliner][NFC] Early exit pruning when candidates don't share an MBB

There's no way they can overlap in this case.

This can save a few iterations when the candidate is close to the beginning
of a MachineBasicBlock. It's particularly useful when the average length of
a MachineBasicBlock in the program is small.

llvm-svn: 346682

show more ...

[MachineOutliner][NFC] Put suffix tree in buildCandidateList

It's only used there, so it doesn't make much sense to have it in runOnModule.

llvm-svn: 346681

[MachineOutliner][NFC] Only map blocks which have adjacent legal instructions

If a block doesn't have any ranges of adjacent legal instructions, then it
can't have outlining candidates. There's no p

[MachineOutliner][NFC] Only map blocks which have adjacent legal instructions

If a block doesn't have any ranges of adjacent legal instructions, then it
can't have outlining candidates. There's no point in mapping legal isntructions
in situations like this.

I noticed this reduces the size of the suffix tree in sqlite3 for AArch64 at
-Oz by about 3%.

llvm-svn: 346379

show more ...

[MachineOutliner][NFC] Don't map MBBs that don't contain legal instructions

I noticed that there are lots of basic blocks that don't have enough legal
instructions in them to warrant outlining. We c

[MachineOutliner][NFC] Don't map MBBs that don't contain legal instructions

I noticed that there are lots of basic blocks that don't have enough legal
instructions in them to warrant outlining. We can skip mapping these entirely.

In sqlite3, compiled for AArch64 at -Oz, this results in a 10% reduction of
the total nodes in the suffix tree. These nodes can never be part of a
repeated substring, and so they don't impact the result at all.

Before this, there were 62128 nodes in the tree for sqlite3. After this, there
are 56457 nodes.

llvm-svn: 346373

show more ...

[MachineOutliner][NFC] Remove Parent field from SuffixTreeNode

This is only used for calculating ConcatLen. This isn't necessary,
since it's easily derived from the traversal setting suffix indices.

[MachineOutliner][NFC] Remove Parent field from SuffixTreeNode

This is only used for calculating ConcatLen. This isn't necessary,
since it's easily derived from the traversal setting suffix indices.

Remove that. Rename CurrIdx to CurrNodeLen to better describe what's
going on.

llvm-svn: 346349

show more ...

[MachineOutliner][NFC] Traverse suffix tree using a RepeatedSubstring iterator

This takes the traversal methods introduced in r346269 and adapts them
into an iterator. This allows the outliner to it

[MachineOutliner][NFC] Traverse suffix tree using a RepeatedSubstring iterator

This takes the traversal methods introduced in r346269 and adapts them
into an iterator. This allows the outliner to iterate over repeated substrings
within the suffix tree directly without having to initially find all of the
substrings and then iterate over them after you've found them.

llvm-svn: 346345

show more ...

[MachineOutliner] Don't store outlined function numberings on OutlinedFunction

NFC-ish. This doesn't change the behaviour of the outliner, but does make sure
that you won't end up with say

OUTLINED

[MachineOutliner] Don't store outlined function numberings on OutlinedFunction

NFC-ish. This doesn't change the behaviour of the outliner, but does make sure
that you won't end up with say

OUTLINED_FUNCTION_2:
...
ret

OUTLINED_FUNCTION_248:
...
ret

as the only outlined functions in your module. Those should really be

OUTLINED_FUNCTION_0:
...
ret

OUTLINED_FUNCTION_1:
...
ret

If we produce outlined functions, they probably should have sequential numbers
attached to them. This makes it a bit easier+stable to write outliner tests.

The point of this is to move towards a bit more stability in outlined function
names. By doing this, we at least don't rely on the traversal order of the
suffix tree. Instead, we rely on the order of the candidate list, which is
*far* more consistent. The candidate list is ordered by the end indices of
candidates, so we're more likely to get a stable ordering. This is still
susceptible to changes in the cost model though (like, if we suddenly find new
candidates, for example).

llvm-svn: 346340

show more ...

[MachineOutliner][NFC] Remove OccurrenceCount from SuffixTreeNode

After changing the way we find candidates in r346269, this is no longer used.

llvm-svn: 346275

[MachineOutliner][NFC] Remove IsInTree from SuffixTreeNode

After changing the way we find repeated substrings in r346269, this
field is no longer used by anything, so it can be removed.

llvm-svn: 3

[MachineOutliner][NFC] Remove IsInTree from SuffixTreeNode

After changing the way we find repeated substrings in r346269, this
field is no longer used by anything, so it can be removed.

llvm-svn: 346274

show more ...

[MachineOutliner][NFC] Add findRepeatedSubstrings to SuffixTree, kill LeafVector

Instead of iterating over the leaves to find repeated substrings, and walking
collecting leaf children when we don't

[MachineOutliner][NFC] Add findRepeatedSubstrings to SuffixTree, kill LeafVector

Instead of iterating over the leaves to find repeated substrings, and walking
collecting leaf children when we don't necessarily need them, let's just
calculate what we need and iterate over that.

By doing this, we don't have to save every leaf. It's easier to read the code
too and understand what's going on.

The goal here, at the end of the day, is to set up to allow us to do something
like

for (RepeatedSubstring &RS : ST) {
... do stuff with RS ...
}

Which would let us perform the cost model stuff and the repeated substring
query at the same time.

llvm-svn: 346269

show more ...

[MachineOutliner][NFC] Remember when you map something illegal across MBBs

Instruction mapping in the outliner uses "illegal numbers" to signify that
something can't ever be part of an outlining can

[MachineOutliner][NFC] Remember when you map something illegal across MBBs

Instruction mapping in the outliner uses "illegal numbers" to signify that
something can't ever be part of an outlining candidate. This means that the
number is unique and can't be part of any repeated substring.

Because each of these is unique, we can use a single unique number to represent
a range of things we can't outline.

The outliner tries to leverage this using a flag which is set in an MBB when
the previous instruction we tried to map was "illegal". This patch improves
that logic to work across MBBs. As a bonus, this also simplifies the mapping
logic somewhat.

This also updates the machine-outliner-remarks test, which was impacted by the
order of Candidates on an OutlinedFunction changing. This order isn't
guaranteed, so I added a FIXME to fix that in a follow-up. The order of
Candidates on an OutlinedFunction isn't important, so this still is NFC.

llvm-svn: 345906

show more ...

[MachineOutliner] Inherit target features from parent function

If a function has target features, it may contain instructions that aren't
represented in the default set of instructions. If the outli

[MachineOutliner] Inherit target features from parent function

If a function has target features, it may contain instructions that aren't
represented in the default set of instructions. If the outliner pulls out one
of these instructions, and the function doesn't have the right attributes
attached, we'll run into an LLVM error explaining that the target doesn't
support the necessary feature for the instruction.

This makes outlined functions inherit target features from their parents.

It also updates the machine-outliner.ll test to check that we're properly
inheriting target features.

llvm-svn: 345535

show more ...

[MachineOutliner][NFC] Don't add MBBs with a size < 2 to the search space

The suffix tree won't ever consider sequences with a length less than 2.

Therefore, we really ought to not even consider th

[MachineOutliner][NFC] Don't add MBBs with a size < 2 to the search space

The suffix tree won't ever consider sequences with a length less than 2.

Therefore, we really ought to not even consider them in the first place.

Also add a FIXME explaining that this should be defined in terms of the size
in B of an outlined call versus the size in B of the MBB.

llvm-svn: 342688

show more ...

[MachineOutliner][NFC] Move debug info emission to createOutlinedFunction

When you create an outlined function, you know everything you need to know
to decide if debug info should be created. If we

[MachineOutliner][NFC] Move debug info emission to createOutlinedFunction

When you create an outlined function, you know everything you need to know
to decide if debug info should be created. If we emit debug info in
createOutlinedFunction, then we don't need to keep track of every IR function
we create.

llvm-svn: 342677

show more ...

[MachineOutliner][NFC] Don't map more illegal instrs than you have to

We were mapping an instruction every time we saw something we couldn't map
before this. Since each illegal mapping is unique, we

[MachineOutliner][NFC] Don't map more illegal instrs than you have to

We were mapping an instruction every time we saw something we couldn't map
before this. Since each illegal mapping is unique, we only have to do this once.

This makes it so that we don't map illegal instructions when the previous
mapped instruction was illegal.

In CTMark (AArch64), this results in 240 fewer instruction mappings on
average over 619 files in total. The largest improvement is 12576 fewer
mappings in one file, and the smallest is 0. The median improvement is 101
fewer mappings.

llvm-svn: 342405

show more ...

[MachineOutliner] Add codegen size remarks to the MachineOutliner

Since the outliner is a module pass, it doesn't get codegen size remarks like
the other codegen passes do. This adds size remarks *t

[MachineOutliner] Add codegen size remarks to the MachineOutliner

Since the outliner is a module pass, it doesn't get codegen size remarks like
the other codegen passes do. This adds size remarks *to* the outliner.

This is kind of a workaround, so it's peppered with FIXMEs; size remarks
really ought to not ever be handled by the pass itself. However, since the
outliner is the only "MachineModulePass", this works for now. Since the
entire purpose of the MachineOutliner is to produce code size savings, it
really ought to be included in codgen size remarks.

If we ever go ahead and make a MachineModulePass (say, something similar to
MachineFunctionPass), then all of this ought to be moved there.

llvm-svn: 342009

show more ...

[MachineOutliner][NFC] Factor out instruction mapping into its own function

Just some tidy-up. Pull the mapper stuff into `populateMapper`. This makes it
a bit easier to read what's going on in `run

[MachineOutliner][NFC] Factor out instruction mapping into its own function

Just some tidy-up. Pull the mapper stuff into `populateMapper`. This makes it
a bit easier to read what's going on in `runOnModule`.

llvm-svn: 341959

show more ...

[MI] Change the array of `MachineMemOperand` pointers to be
a generically extensible collection of extra info attached to
a `MachineInstr`.

The primary change here is cleaning up the APIs used for s

[MI] Change the array of `MachineMemOperand` pointers to be
a generically extensible collection of extra info attached to
a `MachineInstr`.

The primary change here is cleaning up the APIs used for setting and
manipulating the `MachineMemOperand` pointer arrays so chat we can
change how they are allocated.

Then we introduce an extra info object that using the trailing object
pattern to attach some number of MMOs but also other extra info. The
design of this is specifically so that this extra info has a fixed
necessary cost (the header tracking what extra info is included) and
everything else can be tail allocated. This pattern works especially
well with a `BumpPtrAllocator` which we use here.

I've also added the basic scaffolding for putting interesting pointers
into this, namely pre- and post-instruction symbols. These aren't used
anywhere yet, they're just there to ensure I've actually gotten the data
structure types correct. I'll flesh out support for these in
a subsequent patch (MIR dumping, parsing, the works).

Finally, I've included an optimization where we store any single pointer
inline in the `MachineInstr` to avoid the allocation overhead. This is
expected to be the overwhelmingly most common case and so should avoid
any memory usage growth due to slightly less clever / dense allocation
when dealing with >1 MMO. This did require several ergonomic
improvements to the `PointerSumType` to reasonably support the various
usage models.

This also has a side effect of freeing up 8 bits within the
`MachineInstr` which could be repurposed for something else.

The suggested direction here came largely from Hal Finkel. I hope it was
worth it. ;] It does hopefully clear a path for subsequent extensions
w/o nearly as much leg work. Lots of thanks to Reid and Justin for
careful reviews and ideas about how to do all of this.

Differential Revision: https://reviews.llvm.org/D50701

llvm-svn: 339940

show more ...

[MachineOutliner] Clean up subtarget handling.

Call shouldOutlineFromFunctionByDefault, isFunctionSafeToOutlineFrom,
getOutliningType, and getMachineOutlinerMBBFlags using the correct
TargetInstrInf

[MachineOutliner] Clean up subtarget handling.

Call shouldOutlineFromFunctionByDefault, isFunctionSafeToOutlineFrom,
getOutliningType, and getMachineOutlinerMBBFlags using the correct
TargetInstrInfo. And don't create a MachineFunction for a function
declaration.

The call to getOutliningCandidateInfo is still a little weird, but at
least the weirdness is explicitly called out.

Differential Revision: https://reviews.llvm.org/D49880

llvm-svn: 338465

show more ...

Remove trailing space

sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h}

llvm-svn: 338293

[MachineOutliner] Exit getOutliningCandidateInfo when we erase all candidates

There was a missing check for if a candidate list was entirely deleted. This
adds that check.

This fixes an asan failur

[MachineOutliner] Exit getOutliningCandidateInfo when we erase all candidates

There was a missing check for if a candidate list was entirely deleted. This
adds that check.

This fixes an asan failure caused by running test/CodeGen/AArch64/addsub_ext.ll
with the MachineOutliner enabled.

llvm-svn: 338148

show more ...