| Age | Commit message (Collapse) | Author |
|---|
|
|
|
|
|
|
|
|
|
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).
|
|
LeafChildren is used in an earlier version of the SuffixTree
implementation to keep track of each nodes' leaf nodes. In the
new/current version, this variable is no longer used, but a comment is
left behind. This patch updates the comment.
|
|
This reverts commit d3a6a05b1f95564f2c66f885a83cf0dbe1a004a9.
Some bots don't like it.
Boo.
|
|
Sometimes you want to see how much is being allocated in your data structure
in general.
Add statistics that show how many internal and leaf nodes have been allocated
in the suffix tree over the course of its construction.
Also add a testcase that shows that we actually get these stats out when we're
outlining stuff.
The test shows that we get the expected O(n) leaf nodes, a split, and so on.
|
|
Allows us to knock out a couple more includes from the header file.
Also clang-format SuffixTree.cpp while we're here.
Also use SuffixTreeNode::EmptyIdx in a couple more places.
|
|
This makes it clearer that EmptyIdx is related to the node.
Also add an allocator for the root so that in the main SuffixTree code we don't
see gross stuff like a nullptr parent etc.
|
|
Following guidelines in
https://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html
This allows us to
* Quickly discern between leaf and internal nodes
* Be more idiomatic with the rest of LLVM
* Save some size on node structs
* Reduce the number of allocations (because end indices for internal nodes no
longer need to be pointers to be compatible with leaf nodes)
Also object orientify the code some more. This allows for more asserts and
checks.
This shouldn't impact code size on the MachineOutliner.
- All unit tests pass (outliner lit + llvm-unit)
- No code size changes on CTMark @ -Oz for AArch64
|
|
The MachineOutliner + SuffixTree both used `std::vector` everywhere because I
didn't know any better at the time.
At least for small types, such as `unsigned` and iterators, I can't see any
particular reason to use std::vector over `SmallVector` here.
|
|
This moves the SuffixTree test used in the Machine Outliner and moves it into Support for use in other outliners elsewhere in the compilation pipeline.
Differential Revision: https://reviews.llvm.org/D80586
|
