I don't know how deep call stacks go (and also separately don't know if I am allowed to quote stats like that) but people tend to not do points-to with k higher than 2 or 3 because it explodes the whole graph
IIRC the complexity of k-CFA is exponential in k, which is not great. There’s another version called m-CFA; I don’t remember exactly what it does differently, but it doesn’t blow up exponentially
I'll borrow a few choice pieces from the paper to try to explain why.
The main difference is that:
k-cfa is sensitive to the last k calls.
m-cfa is sensitive to the top m stack frames.
This turns out not equivalent: with k=1 vs m=1: a program where main calls a calls b. in k-cfa, the context will be the call to b. in m-cfa, the context will be the call to a.
How m-cfa came about and why it works:
k-CFA is EXPTIME-complete (so no polynomial algorithm can exist).
However, it was observed that there are plenty of provably k-cfa equivalent points-to for OO languages that ran in provably polynomial time (and none for functional languages). Diving into this caused folks to discover the difference between objects and closures matters a lot to the time-bounds, and led to the formulation of m-cfa.
Space complexity was never as much an issue as time complexity was, due to BDD's and other things.
