diff options
| author | Fangrui Song <maskray@google.com> | 2019-02-20 04:39:42 +0000 |
|---|---|---|
| committer | Fangrui Song <maskray@google.com> | 2019-02-20 04:39:42 +0000 |
| commit | d990c2a9e23f1b8d6d7ee17c2d1f46202d70b88e (patch) | |
| tree | c624eb4050aa6417a659fa4b4c43fa1ff6391905 /llvm/lib | |
| parent | b94dde7f9bc9b1eeef13bd8e67828c607d15503b (diff) | |
| download | bcm5719-llvm-d990c2a9e23f1b8d6d7ee17c2d1f46202d70b88e.tar.gz bcm5719-llvm-d990c2a9e23f1b8d6d7ee17c2d1f46202d70b88e.zip | |
[Dominators] Simplify and optimize path compression used in link-eval forest.
Summary:
* NodeToInfo[*] have been allocated so the addresses are stable. We can store them instead of NodePtr to save NumToNode lookups.
* Nodes are traversed twice. Using `Visited` to check the traversal number is expensive and obscure. Just split the two traversals into two loops explicitly.
* The check `VInInfo.DFSNum < LastLinked` is redundant as it is implied by `VInInfo->Parent < LastLinked`
* VLabelInfo PLabelInfo are used to save a NodeToInfo lookup in the second traversal.
Also add some comments explaining eval().
This shows a ~4.5% improvement (9.8444s -> 9.3996s) on
perf stat -r 10 taskset -c 0 opt -passes=$(printf '%.0srequire<domtree>,invalidate<domtree>,' {1..1000})'require<domtree>' -disable-output sqlite-autoconf-3270100/sqlite3.bc
Reviewers: kuhar, sanjoy, asbirlea
Reviewed By: kuhar
Subscribers: brzycki, NutshellySima, kristina, jdoerfert, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D58327
llvm-svn: 354433
Diffstat (limited to 'llvm/lib')
0 files changed, 0 insertions, 0 deletions
