Thread safety analysis very slow in long functions because of LocalVariableMap

[aaronpuchert]

Bugzilla Link	43311
Version	unspecified
OS	All
CC	@AaronBallman,@zygoloid

Extended Description

The LocalVariableMap data structure keeps a set of life values for every program point, which can be prohibitively expensive for very long functions. Since the entire state is copied over for every modification, the complexity is O(n²) in the worst case. Of course long functions are not good programming style, but they occur.

Currently the map is only used to find out if branch expressions are related to the result of a try-acquire function call. That doesn't require tracking all values in the program though.

[aaronpuchert]

assigned to @aaronpuchert

[aaronpuchert]

@​Delesley: Do you remember why you wrote the LocalVariableMap, was it indeed only for resolving try-lock expressions (ThreadSafetyAnalyzer::getTrylockCallExpr), or was it intended for some alias tracking as well? If it wasn't, I might consider rewriting it in a way that's more tailored to resolving try-lock expressions (and thus hopefully faster).

[aaronpuchert]

Nevermind, this was actually because I enabled EH edges in the control flow graph as an experiment. Performance is Ok without those. It's still somewhat strange, but I'll have to look into this myself.

Since the entire state is copied over for every modification, the complexity is O(n²) in the worst case.

That's not actually true: the ImmutableMap doesn't copy over the entire state, unchanged subtrees can be shared between different versions.