search

UQ-PAC / BASIL

Apache License 2.0
8 stars 0 forks source link

Const Prop SSA analysis performance bottleneck #242

Open ailrst opened 2 months ago

ailrst commented 2 months ago

Doing tests on random programs of different sizes generated by csmith, and the timeout point is consistently the constant prop solver with SSA, this should definitely not be the bottleneck so something is wrong.
The flamegraph profile seems to show most of the work still in map join so I'm guessing its due to there being one variable per assignment in the state domain now. We could make it so only initial definitions and phi nodes increase the size of the variable mapping, ie. previous state mapping on the same variable with different index can be deleted when they are redefined (assuming they are never referenced which is the case immediately after the ssa transform but may not neccessarily be maintained).

cpssa

cpssaloglog

(graph ran out of colours but the top line is ConstantPropagationSolverWithSSA)

image

full flamegraph

l-kent commented 2 months ago

The SSA constant propagation is exponential with branching (unlike the regular constant propagation), and pretty inefficient because it really doesn't need to store the state per CFGPosition given that each assignment is to a unique variable. Those combined are probably why it's the bottleneck unless there's a bug that causes it to get stuck for some cases or something.