[aarch64][win] Update Called Globals info when updating Call Site info (#122762)

Fixes the "use after poison" issue introduced by #121516 (see
<https://github.com/llvm/llvm-project/pull/121516#issue

[aarch64][win] Update Called Globals info when updating Call Site info (#122762)

Fixes the "use after poison" issue introduced by #121516 (see
<https://github.com/llvm/llvm-project/pull/121516#issuecomment-2585912395>).

The root cause of this issue is that #121516 introduced "Called Global"
information for call instructions modeling how "Call Site" info is
stored in the machine function, HOWEVER it didn't copy the
copy/move/erase operations for call site information.

The fix is to rename and update the existing copy/move/erase functions
so they also take care of Called Global info.

show more ...

[NFC] Remove some unnecessary semicolons

All inside LLVM_DEBUG, some of which have been cleaned up by adding block
scopes to allow them to format more nicely.

[CodeGen] Remove unused includes (NFC) (#115996)

Identified with misc-include-cleaner.

[llvm] Remove redundant calls to std::unique_ptr<T>::get (NFC) (#113415)

[LLVM] Use {} instead of std::nullopt to initialize empty ArrayRef (#109133)

It is almost always simpler to use {} instead of std::nullopt to
initialize an empty ArrayRef. This patch changes all oc

[LLVM] Use {} instead of std::nullopt to initialize empty ArrayRef (#109133)

It is almost always simpler to use {} instead of std::nullopt to
initialize an empty ArrayRef. This patch changes all occurrences I could
find in LLVM itself. In future the ArrayRef(std::nullopt_t) constructor
could be deprecated or removed.

show more ...

Attempt to fix [CGData][MachineOutliner] Global Outlining (#90074) (#108037)

[CGData][MachineOutliner] Global Outlining (#90074)

This commit introduces support for outlining functions across modules
using codegen data generated from previous codegen. The codegen data
curre

[CGData][MachineOutliner] Global Outlining (#90074)

This commit introduces support for outlining functions across modules
using codegen data generated from previous codegen. The codegen data
currently manages the outlined hash tree, which records outlining
instances that occurred locally in the past.

The machine outliner now operates in one of three modes:

1. CGDataMode::None: This is the default outliner mode that uses the
suffix tree to identify (local) outlining candidates within a module.
This mode is also used by (full)LTO to maintain optimal behavior with
the combined module.
2. CGDataMode::Write (`-codegen-data-generate`): This mode is identical
to the default mode, but it also publishes the stable hash sequences of
instructions in the outlined functions into a local outlined hash tree.
It then encodes this into the `__llvm_outline` section, which will be
dead-stripped at link time.
3. CGDataMode::Read (`-codegen-data-use-path={.cgdata}`): This mode
reads a codegen data file (.cgdata) and initializes a global outlined
hash tree. This tree is used to generate global outlining candidates.
Note that the codegen data file has been post-processed with the raw
`__llvm_outline` sections from all native objects using the
`llvm-cgdata` tool (or a linker, `LLD`, or a new ThinLTO pipeline
later).

This depends on https://github.com/llvm/llvm-project/pull/105398. After
this PR, LLD (https://github.com/llvm/llvm-project/pull/90166) and Clang
(https://github.com/llvm/llvm-project/pull/90304) will follow for each
client side support.
This is a patch for
https://discourse.llvm.org/t/rfc-enhanced-machine-outliner-part-2-thinlto-nolto/78753.

show more ...

[MachineOutliner] Preserve instruction bundles (#106402)

When the machine outliner copies instructions from a source function
into an outlined function, it was doing it using `CloneMachineInstr`,

[MachineOutliner] Preserve instruction bundles (#106402)

When the machine outliner copies instructions from a source function
into an outlined function, it was doing it using `CloneMachineInstr`,
which is documented as not preserving the interior of any instruction
bundle. So outlining code that includes an instruction bundle would
fail, because in the outlined version, the bundle would be empty, so
instructions would go missing in the move.

This occurs when any bundled instruction appears in the outlined code,
so there was no need to construct an unusual test case: I've just copied
a function from the existing `stp-opt-with-renaming.mir`, which happens
to contain an SVE instruction bundle. Including two identical copies of
that function makes the outliner merge them, and then we check that it
didn't destroy the interior of the bundle in the process.

show more ...

[MachineOutliner][NFC] Refactor (#105398)

This patch prepares the NFC groundwork for global outlining using
CGData, which will follow
https://github.com/llvm/llvm-project/pull/90074.

- The `Min

[MachineOutliner][NFC] Refactor (#105398)

This patch prepares the NFC groundwork for global outlining using
CGData, which will follow
https://github.com/llvm/llvm-project/pull/90074.

- The `MinRepeats` parameter is now explicitly passed to the
`getOutliningCandidateInfo` function, rather than relying on a default
value of 2. For local outlining, the minimum number of repetitions is
typically 2, but for the global outlining (mentioned above), we will
optimistically create a single `Candidate` for each `OutlinedFunction`
if stable hashes match a specific code sequence. This parameter is
adjusted accordingly in global outlining scenarios.
- I have also implemented `unique_ptr` for `OutlinedFunction` to ensure
safe and efficient memory management within `FunctionList`, avoiding
unnecessary implicit copies.

This depends on https://github.com/llvm/llvm-project/pull/101461.
This is a patch for
https://discourse.llvm.org/t/rfc-enhanced-machine-outliner-part-2-thinlto-nolto/78753.

show more ...

MachineOutliner: Use PM to query MachineModuleInfo (#99688)

Avoid getting this from the MachineFunction

[llvm][CodeGen] Avoid 'raw_string_ostream::str' (NFC) (#97318)

Since `raw_string_ostream` doesn't own the string buffer, it is
desirable (in terms of memory safety) for users to directly reference

[llvm][CodeGen] Avoid 'raw_string_ostream::str' (NFC) (#97318)

Since `raw_string_ostream` doesn't own the string buffer, it is
desirable (in terms of memory safety) for users to directly reference
the string buffer rather than use `raw_string_ostream::str()`.

Work towards TODO comment to remove `raw_string_ostream::str()`.

show more ...

[IRBuilder] Don't include Module.h (NFC) (#97159)

This used to be necessary to fetch the DataLayout, but isn't anymore.

[MachineOutliner] Leaf Descendants (#90275)

This PR depends on https://github.com/llvm/llvm-project/pull/90264

In the current implementation, only leaf children of each internal node
in the suf

[MachineOutliner] Leaf Descendants (#90275)

This PR depends on https://github.com/llvm/llvm-project/pull/90264

In the current implementation, only leaf children of each internal node
in the suffix tree are included as candidates for outlining. But all
leaf descendants are outlining candidates, which we include in the new
implementation. This is enabled on a flag `outliner-leaf-descendants`
which is default to be true.

The reason for _enabling this on a flag_ is because machine outliner is
not the only pass that uses suffix tree.

The reason for _having this default to be true_ is because including all
leaf descendants show consistent size win.
* For Clang/LLD, it shows around 3% reduction in text segment size when
compared to the baseline `-Oz` linker binary.
* For selected benchmark tests in LLVM test suite

| run (CTMark/) | only leaf children | all leaf descendants | reduction
% |

|------------------|--------------------|----------------------|-------------|
| lencod | 349624 | 348564 | -0.2004% |
| SPASS | 219672 | 218440 | -0.4738% |
| kc | 271956 | 250068 | -0.4506% |
| sqlite3 | 223920 | 222484 | -0.5471% |
| 7zip-benchmark | 405364 | 401244 | -0.3428% |
| bullet | 139820 | 138340 | -0.8315% |
| consumer-typeset | 295684 | 286628 | -1.2295% |
| pairlocalalign | 72236 | 71936 | -0.2164% |
| tramp3d-v4 | 189572 | 183676 | -2.9668% |

This is part of an enhanced version of machine outliner -- see
[RFC](https://discourse.llvm.org/t/rfc-enhanced-machine-outliner-part-1-fulllto-part-2-thinlto-nolto-to-come/78732).

show more ...

[MachineOutliner] Sort by Benefit to Cost Ratio (#90264)

This PR depends on https://github.com/llvm/llvm-project/pull/90260

We changed the order in which functions are outlined in Machine
Outlin

[MachineOutliner] Sort by Benefit to Cost Ratio (#90264)

This PR depends on https://github.com/llvm/llvm-project/pull/90260

We changed the order in which functions are outlined in Machine
Outliner.

The formula for priority is found via a black-box Bayesian optimization
toolbox. Using this formula for sorting consistently reduces the
uncompressed size of large real-world mobile apps. We also ran a few
benchmarks using LLVM test suites, and showed that sorting by priority
consistently reduces the text segment size.

|run (CTMark/)   |baseline (1)|priority (2)|diff (1 -> 2)|
|----------------|------------|------------|-------------|
|lencod          |349624      |349264      |-0.1030%     |
|SPASS           |219672      |219480      |-0.0874%     |
|kc              |271956      |251200      |-7.6321%     |
|sqlite3         |223920      |223708      |-0.0947%     |
|7zip-benchmark  |405364      |402624      |-0.6759%     |
|bullet          |139820      |139500      |-0.2289%     |
|consumer-typeset|295684      |290196      |-1.8560%     |
|pairlocalalign  |72236       |72092       |-0.1993%     |
|tramp3d-v4      |189572      |189292      |-0.1477%     |

This is part of an enhanced version of machine outliner -- see
[RFC](https://discourse.llvm.org/t/rfc-enhanced-machine-outliner-part-1-fulllto-part-2-thinlto-nolto-to-come/78732).

show more ...

[MachineOutliner] Efficient Implementation of MachineOutliner::findCandidates() (#90260)

This reduce the time complexity of the main loop of `findCandidates()`
method from $O(n^2)$ to $O(n \log n)$

[MachineOutliner] Efficient Implementation of MachineOutliner::findCandidates() (#90260)

This reduce the time complexity of the main loop of `findCandidates()`
method from $O(n^2)$ to $O(n \log n)$.

For small $n$, the modification does not regress the build time, but it
helps significantly when $n$ is large.

For one application, this reduces the runtime of the main loop from 120
seconds to 28 seconds.

This is the first commit for an enhanced version of machine outliner --
see
[RFC](https://discourse.llvm.org/t/rfc-enhanced-machine-outliner-part-1-fulllto-part-2-thinlto-nolto-to-come/78732).

show more ...

[IR] Do not set `none` for function uwtable (#93387)

This avoids the pitfall where we set the uwtable to none:
```
func.setUWTableKind(llvm::UWTableKind::None)
```
`Attribute::getAsString()` wou

[IR] Do not set `none` for function uwtable (#93387)

This avoids the pitfall where we set the uwtable to none:
```
func.setUWTableKind(llvm::UWTableKind::None)
```
`Attribute::getAsString()` would see an unknown attribute and fail an
assertion. In this patch, we assert that we do not see a None uwtable
kind.

This also skips the check of `UWTableKind::Async`. It is dominated by
the check of `UWTableKind::Default`, which has the same enum value
(nfc).

show more ...

[CodeGen] Do not pass MF into MachineRegisterInfo methods. NFC. (#84770)

MachineRegisterInfo already knows the MF so there is no need to pass it
in as an argument.

[MachineOutliner] Refactor iterating over Candidate's instructions (#78972)

Make Candidate's front() and back() functions return references to
MachineInstr and introduce begin() and end() returning

[MachineOutliner] Refactor iterating over Candidate's instructions (#78972)

Make Candidate's front() and back() functions return references to
MachineInstr and introduce begin() and end() returning iterators, the
same way it is usually done in other container-like classes.

This makes possible to iterate over the instructions contained in
Candidate the same way one can iterate over MachineBasicBlock (note that
begin() and end() return bundled iterators, just like MachineBasicBlock
does, but no instr_begin() and instr_end() are defined yet).

show more ...

[MachineOutliner] NFC: Add debug output to MachineOutliner::outline

Add some debug output to `outline` to assist in debugging + understanding the
code.

This will say

- How many things we found wor

[MachineOutliner] NFC: Add debug output to MachineOutliner::outline

Add some debug output to `outline` to assist in debugging + understanding the
code.

This will say

- How many things we found worth turning into outlined functions
- Whether or not candidates were pruned via the outlining algorithm
- The function created (if it was created)
- Where the calls were inserted
- What instruction was used to create the call

Sample output below:

```
NUMBER OF POTENTIAL FUNCTIONS: 5
WALKING FUNCTION LIST
PRUNED: 0/2 candidates
OUTLINE: Expected benefit (12 B) > threshold (1 B)
NEW FUNCTION: OUTLINED_FUNCTION_0
CREATE OUTLINED CALLS
CALL: OUTLINED_FUNCTION_0 in bar:<unknown>
.. BL @OUTLINED_FUNCTION_0, implicit-def $lr, implicit $sp
CALL: OUTLINED_FUNCTION_0 in bar:<unknown>
.. BL @OUTLINED_FUNCTION_0, implicit-def $lr, implicit $sp
PRUNED: 2/2 candidates
SKIP: Expected benefit (0 B) < threshold (1 B)
PRUNED: 0/2 candidates
OUTLINE: Expected benefit (8 B) > threshold (1 B)
NEW FUNCTION: OUTLINED_FUNCTION_1
CREATE OUTLINED CALLS
CALL: OUTLINED_FUNCTION_1 in bar:<unknown>
.. BL @OUTLINED_FUNCTION_1, implicit-def $lr, implicit $sp
CALL: OUTLINED_FUNCTION_1 in bar:<unknown>
.. BL @OUTLINED_FUNCTION_1, implicit-def $lr, implicit $sp
PRUNED: 2/2 candidates
SKIP: Expected benefit (0 B) < threshold (1 B)
PRUNED: 2/2 candidates
SKIP: Expected benefit (0 B) < threshold (1 B)
```

show more ...

[MachineOutliner] Add IsOutlined to MachineFunction

We add a field `IsOutlined` to indicate whether a MachineFunction
is outlined and set it true for outlined functions in MachineOutliner.

Reviewed

[MachineOutliner] Add IsOutlined to MachineFunction

We add a field `IsOutlined` to indicate whether a MachineFunction
is outlined and set it true for outlined functions in MachineOutliner.

Reviewed By: paquette

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

show more ...

[Outliner] Add an option to only enable outlining of patterns above a certain threshold

Outlining isn't always a win when the saved instruction count is >= 1.
The overhead of representing a new func

[Outliner] Add an option to only enable outlining of patterns above a certain threshold

Outlining isn't always a win when the saved instruction count is >= 1.
The overhead of representing a new function in the binary depends on
exception metadata and alignment. So parameterize this for local tuning.

Reviewed By: paquette

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

show more ...

[NFC][Outliner] Delete default ctors for Candidate & OutlinedFunction.

I think it's good practice to avoid having default ctors unless they're really
valid/useful. For OutlinedFunction the default c

[NFC][Outliner] Delete default ctors for Candidate & OutlinedFunction.

I think it's good practice to avoid having default ctors unless they're really
valid/useful. For OutlinedFunction the default ctor was used to represent a
bail-out value for getOutliningCandidateInfo(), so I changed the API to return
an optional<getOutliningCandidateInfo> instead which seems a tad cleaner.

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

show more ...

[MachineOutliner] Improve mapper statistics

Add a test for statistics as well.

The mapper size stats were nested in a loop unnecessarily. Move them out.

Give existing stats better names, and add o

[MachineOutliner] Improve mapper statistics

Add a test for statistics as well.

The mapper size stats were nested in a loop unnecessarily. Move them out.

Give existing stats better names, and add one which also tracks the number of
sentinels added.

show more ...

[MachineOutliner] NFC: Add debug output to populateMapper

Adding debug output to improve outliner debuggability + testability.

Move `nooutline` attribute test into the new debug output test.

[MachineOutliner] NFC: Add debug output to overlap pruning code

This had no debug output. Since it was committed as NFC, it had no testcase.

The me of today was nerdsniped by the me of 6 years ago

[MachineOutliner] NFC: Add debug output to overlap pruning code

This had no debug output. Since it was committed as NFC, it had no testcase.

The me of today was nerdsniped by the me of 6 years ago and decided that this
ought to have a testcase and some debug output.

show more ...