Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:chaotic_iteration_in_abstract_interpretation [2008/05/20 13:29] vkuncak |
sav08:chaotic_iteration_in_abstract_interpretation [2008/05/20 19:34] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Chaotic Iteration in Abstract Interpretation ====== | + | ====== Chaotic Iteration in Abstract Interpretation: How to compute the fixpoint? ====== |
| In [[Abstract Interpretation Recipe]], note that if the set of program points is $p'_1,\ldots,p'_n$, then we are solving the system of eqautions in $n$ variables $g_1,\ldots,g_n$ | In [[Abstract Interpretation Recipe]], note that if the set of program points is $p'_1,\ldots,p'_n$, then we are solving the system of eqautions in $n$ variables $g_1,\ldots,g_n$ | ||
| Line 50: | Line 50: | ||
| Compare values $I$, $L_1$, $C_1$, $I_n$, $C_n$ in the lattice | Compare values $I$, $L_1$, $C_1$, $I_n$, $C_n$ in the lattice | ||
| - | * in general | + | * in general ++|$C_1 \sqsubseteq L_1$, generally $C_i \sqsubseteq L_i$ ++ |
| - | ++++| | + | * when selecting equations by fixed permutation ++| $L_1 \sqsubseteq C_n$, generally $L_i \sqsubseteq C_{ni}$ ++ |
| - | $C_i \sqleq L_i$ | + | |
| - | ++++ | + | |
| - | * when selecting equations by fixed permutation | + | |
| ==== Worklist Algorithm and Iteration Strategies ==== | ==== Worklist Algorithm and Iteration Strategies ==== | ||
| Line 75: | Line 72: | ||
| Strongly connected component (SCC) of a directed graph: path between each two nodes of component. | Strongly connected component (SCC) of a directed graph: path between each two nodes of component. | ||
| * compute until fixpoint within each SCC | * compute until fixpoint within each SCC | ||
| + | |||
| + | If we generate control-flow graph from our simple language, what do strongly connected components correspond to? | ||
| ===== References ===== | ===== References ===== | ||