Search code examples
algorithmcompiler-constructioncompiler-optimizationstatic-analysiscode-analysis

Iteration number of live variable analysis


I know that the algorithm for live variable analysis can finally terminate and give a solution. However, I'd like to know whether the iteration number of the algorithm is determined(i.e., can I calculate the iteration number of the algorithm with some parameters, I guess the parameters may be related to the program to be analyzed).


Solution

  • Although I still don't know how to calculate the accurate iteration number, it's easy to compute the maximum iteration number we need. It can be solved by applying the lattice theorems.

    In terms of simplicity, assume the height of the lattice corresponding to the analysis is i and the number of the nodes in CFG is k, then the maximum iteration number is i*k.