HomePhabricator

[Dominators] Simplify and optimize path compression used in link-eval forest.

Description

[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

Details

Committed
MaskRayFeb 19 2019, 8:39 PM
Reviewer
kuhar
Differential Revision
D58327: [Dominators] Simplify and optimize path compression used in link-eval forest.
Parents
rL354432: Remove test on incompatible mpis target.
Branches
Unknown
Tags
Unknown