The fast_ssa_liveness analysis introduced recently is quite complex. We need some benchmarking to justify its presence in pliron.
What to measure?
Considering that we can compile bzip2 through pliron, we can do the following:
- Instrument a "pass" that computes
LivenessInfo for a module
- Collect all values in the module.
- Test liveness of every value at every program point
- Measure time for (1) and (3)
- Repeat over all modules.
Comparison
It may be worthwhile to implement a simpler liveness query system (such as Algorithm 6 in [1]).
Note: Any new liveness implementation only needs to implement the RegionLiveness trait. Liveness<T: RegionLiveness> will take care of the rest.
Further experiments:
- The paper discusses an optimization for reducible graphs when querying
is_live_in_block. This is implemented in our code too. This optimization doesn't (seem to) hold for is_live_out_block. In practice, is_live_out_block seems to be the more useful one. So in some cases (such as when there are, say, only 2 successors), when it's a reducible CFG, we can fall back to live_out = Union_{succ in successors} { live_in (succ) } and see if that's faster than calling is_live_out_block.
- Data-structure choice can be experimented with too. MLIR (
Liveness.cpp) seems to use SmallPtrSet which is hash-table based. LiveVariables in LLVM's codegen uses sparse-bit-vectors. We could experiment b/w the current hi_sparse_bitset and FxHashSet.
The fast_ssa_liveness analysis introduced recently is quite complex. We need some benchmarking to justify its presence in pliron.
What to measure?
Considering that we can compile bzip2 through
pliron, we can do the following:LivenessInfofor a moduleComparison
It may be worthwhile to implement a simpler liveness query system (such as Algorithm 6 in [1]).
Note: Any new liveness implementation only needs to implement the
RegionLivenesstrait.Liveness<T: RegionLiveness>will take care of the rest.Further experiments:
is_live_in_block. This is implemented in our code too. This optimization doesn't (seem to) hold foris_live_out_block. In practice,is_live_out_blockseems to be the more useful one. So in some cases (such as when there are, say, only 2 successors), when it's a reducible CFG, we can fall back tolive_out = Union_{succ in successors} { live_in (succ) }and see if that's faster than callingis_live_out_block.Liveness.cpp) seems to use SmallPtrSet which is hash-table based. LiveVariables in LLVM's codegen uses sparse-bit-vectors. We could experiment b/w the currenthi_sparse_bitsetandFxHashSet.