[MachineOutliner][AArch64] NFC: Split MBBs into "outlinable ranges"
authorJessica Paquette <jpaquette@apple.com>
Wed, 16 Feb 2022 20:50:31 +0000 (12:50 -0800)
committerJessica Paquette <jpaquette@apple.com>
Mon, 21 Feb 2022 23:29:16 +0000 (15:29 -0800)
commitd97f997eb79d91b2872ac13619f49cb3a7120781
treecb41eed4e5128ad55b40ca6b9e46be4bc1e96d99
parentdc0981562e520a95e264a1fbe4596022d6055343
[MachineOutliner][AArch64] NFC: Split MBBs into "outlinable ranges"

We found a case in the Swift benchmarks where the MachineOutliner introduces
about a 20% compile time overhead in comparison to building without the
MachineOutliner.

The origin of this slowdown is that the benchmark has long blocks which incur
lots of LRU checks for lots of candidates.

Imagine a case like this:

```
bb:
  i1
  i2
  i3
  ...
  i123456
```

Now imagine that all of the outlining candidates appear early in the block, and
that something like, say, NZCV is defined at the end of the block.

The outliner has to check liveness for certain registers across all candidates,
because outlining from areas where those registers are used is unsafe at call
boundaries.

This is fairly wasteful because in the previously-described case, the outlining
candidates will never appear in an area where those registers are live.

To avoid this, precalculate areas where we will consider outlining from.
Anything outside of these areas is mapped to illegal and not included in the
outlining search space. This allows us to reduce the size of the outliner's
suffix tree as well, giving us a potential memory win.

By precalculating areas, we can also optimize other checks too, like whether
or not LR is live across an outlining candidate.

Doing all of this is about a 16% compile time improvement on the case.

This is likely useful for other targets (e.g. ARM + RISCV) as well, but for now,
this only implements the AArch64 path. The original "is the MBB safe" method
still works as before.
llvm/include/llvm/CodeGen/TargetInstrInfo.h
llvm/lib/CodeGen/MachineOutliner.cpp
llvm/lib/Target/AArch64/AArch64InstrInfo.cpp
llvm/lib/Target/AArch64/AArch64InstrInfo.h