| #
d9a00ed3 |
| 18-Jun-2024 |
Xuan Zhang <144393379+xuanzh-meta@users.noreply.github.com> |
[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 ...
|
|
Revision tags: llvmorg-18.1.8, llvmorg-18.1.7, llvmorg-18.1.6, llvmorg-18.1.5 |
|
| #
7683d07d |
| 26-Apr-2024 |
Xuan Zhang <144393379+xuanzh-meta@users.noreply.github.com> |
[NFC] update comments from an earlier version of SuffixTree (#89800)
LeafChildren is used in an earlier version of the SuffixTree
implementation to keep track of each nodes' leaf nodes. In the
new
[NFC] update comments from an earlier version of SuffixTree (#89800)
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.
show more ...
|
|
Revision tags: llvmorg-18.1.4, llvmorg-18.1.3, llvmorg-18.1.2, llvmorg-18.1.1, llvmorg-18.1.0, llvmorg-18.1.0-rc4, llvmorg-18.1.0-rc3, llvmorg-18.1.0-rc2, llvmorg-18.1.0-rc1, llvmorg-19-init, llvmorg-17.0.6, llvmorg-17.0.5, llvmorg-17.0.4, llvmorg-17.0.3, llvmorg-17.0.2, llvmorg-17.0.1, llvmorg-17.0.0, llvmorg-17.0.0-rc4, llvmorg-17.0.0-rc3, llvmorg-17.0.0-rc2, llvmorg-17.0.0-rc1, llvmorg-18-init, llvmorg-16.0.6, llvmorg-16.0.5, llvmorg-16.0.4 |
|
| #
9c0a3497 |
| 13-May-2023 |
Jessica Paquette <jpaquette@apple.com> |
Revert "[SuffixTree] Add suffix tree statistics"
This reverts commit d3a6a05b1f95564f2c66f885a83cf0dbe1a004a9.
Some bots don't like it.
Boo.
|
| #
d3a6a05b |
| 12-May-2023 |
Jessica Paquette <jpaquette@apple.com> |
[SuffixTree] Add suffix tree statistics
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
[SuffixTree] Add suffix tree statistics
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.
show more ...
|
| #
c2eeaf10 |
| 12-May-2023 |
Jessica Paquette <jpaquette@apple.com> |
[NFC] SuffixTree: Move advance() into SuffixTree.cpp + more cleanup
Allows us to knock out a couple more includes from the header file.
Also clang-format SuffixTree.cpp while we're here.
Also use
[NFC] SuffixTree: Move advance() into SuffixTree.cpp + more cleanup
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.
show more ...
|
| #
66520c04 |
| 12-May-2023 |
Jessica Paquette <jpaquette@apple.com> |
[NFC] SuffixTree: Move EmptyIdx into SuffixTreeNode and add a root allocator
This makes it clearer that EmptyIdx is related to the node.
Also add an allocator for the root so that in the main Suffi
[NFC] SuffixTree: Move EmptyIdx into SuffixTreeNode and add a root allocator
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.
show more ...
|
| #
c2f0c204 |
| 11-May-2023 |
Jessica Paquette <jpaquette@apple.com> |
[NFC] Refactor SuffixTree to use LLVM-style RTTI
Following guidelines in
https://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html
This allows us to
* Quickly discern between leaf and internal nodes
* B
[NFC] Refactor SuffixTree to use LLVM-style RTTI
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
show more ...
|
|
Revision tags: llvmorg-16.0.3, llvmorg-16.0.2, llvmorg-16.0.1, llvmorg-16.0.0, llvmorg-16.0.0-rc4, llvmorg-16.0.0-rc3, llvmorg-16.0.0-rc2 |
|
| #
ec37ebf5 |
| 04-Feb-2023 |
Jessica Paquette <jpaquette@apple.com> |
[NFC] Use SmallVector/ArrayRef in MachineOutliner/SuffixTree for small types
The MachineOutliner + SuffixTree both used `std::vector` everywhere because I
didn't know any better at the time.
At lea
[NFC] Use SmallVector/ArrayRef in MachineOutliner/SuffixTree for small types
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.
show more ...
|
|
Revision tags: llvmorg-16.0.0-rc1, llvmorg-17-init, llvmorg-15.0.7, llvmorg-15.0.6, llvmorg-15.0.5, llvmorg-15.0.4, llvmorg-15.0.3, working, llvmorg-15.0.2, llvmorg-15.0.1, llvmorg-15.0.0, llvmorg-15.0.0-rc3, llvmorg-15.0.0-rc2, llvmorg-15.0.0-rc1, llvmorg-16-init, llvmorg-14.0.6, llvmorg-14.0.5, llvmorg-14.0.4, llvmorg-14.0.3, llvmorg-14.0.2, llvmorg-14.0.1, llvmorg-14.0.0, llvmorg-14.0.0-rc4, llvmorg-14.0.0-rc3, llvmorg-14.0.0-rc2, llvmorg-14.0.0-rc1, llvmorg-15-init, llvmorg-13.0.1, llvmorg-13.0.1-rc3, llvmorg-13.0.1-rc2, llvmorg-13.0.1-rc1, llvmorg-13.0.0, llvmorg-13.0.0-rc4, llvmorg-13.0.0-rc3, llvmorg-13.0.0-rc2, llvmorg-13.0.0-rc1, llvmorg-14-init, llvmorg-12.0.1, llvmorg-12.0.1-rc4, llvmorg-12.0.1-rc3, llvmorg-12.0.1-rc2, llvmorg-12.0.1-rc1, llvmorg-12.0.0, llvmorg-12.0.0-rc5, llvmorg-12.0.0-rc4, llvmorg-12.0.0-rc3, llvmorg-12.0.0-rc2, llvmorg-11.1.0, llvmorg-11.1.0-rc3, llvmorg-12.0.0-rc1, llvmorg-13-init, llvmorg-11.1.0-rc2, llvmorg-11.1.0-rc1, llvmorg-11.0.1, llvmorg-11.0.1-rc2, llvmorg-11.0.1-rc1, llvmorg-11.0.0, llvmorg-11.0.0-rc6, llvmorg-11.0.0-rc5, llvmorg-11.0.0-rc4, llvmorg-11.0.0-rc3, llvmorg-11.0.0-rc2, llvmorg-11.0.0-rc1, llvmorg-12-init, llvmorg-10.0.1, llvmorg-10.0.1-rc4, llvmorg-10.0.1-rc3, llvmorg-10.0.1-rc2, llvmorg-10.0.1-rc1 |
|
| #
bb677cac |
| 08-Apr-2020 |
Andrew Litteken <andrew_litteken@apple.com> |
[SuffixTree][MachOpt] Factoring out Suffix Tree and adding Unit Tests
This moves the SuffixTree test used in the Machine Outliner and moves it into Support for use in other outliners elsewhere in th
[SuffixTree][MachOpt] Factoring out Suffix Tree and adding Unit Tests
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
show more ...
|