Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav07_lecture_20 [2007/06/05 19:04] kremena.diatchka |
sav07_lecture_20 [2009/05/27 10:28] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Lecture 20: Interprocedural analysis ====== | + | ====== Lecture 20: Interprocedural Analysis - Introduction ====== |
| intraprocedural analysis = analysis for language without procedures | intraprocedural analysis = analysis for language without procedures | ||
| Line 44: | Line 44: | ||
| - must follow protocol: (open (read+write)* close)* | - must follow protocol: (open (read+write)* close)* | ||
| - must follow protocol: (startLog stopLog)* | - must follow protocol: (startLog stopLog)* | ||
| - | |||
| - | |||
| - | |||
| ==== Semantics for language with procedure calls ==== | ==== Semantics for language with procedure calls ==== | ||
| Line 57: | Line 54: | ||
| $(c,s)$ | $(c,s)$ | ||
| - | where $c \in V$, $s \in S, | + | where $c \in V, s \in S$ |
| Line 68: | Line 65: | ||
| Then we can formally define the semantics of a big step ($\mapsto$) as: | Then we can formally define the semantics of a big step ($\mapsto$) as: | ||
| - | $(c_{0},s_{1}) \mapsto (c_{3}, s_{2})$ | + | $(c_{1},s_{1}) \mapsto (c_{2}, s_{2})$ |
| where $(s_{1},s_{2}) \in r$ iff $(c_{0},s_{1}) \rightarrow (c_{3},s_{2})$ | where $(s_{1},s_{2}) \in r$ iff $(c_{0},s_{1}) \rightarrow (c_{3},s_{2})$ | ||
| Line 93: | Line 90: | ||
| $(s, l, c, t)$ | $(s, l, c, t)$ | ||
| - | Here $l \in L$, where $L$ is the set of local variables of a procedure. Everything would be popped off from $l$ when the procedure returns control to the callee. | + | Here $l \in L$, where $L$ is the set of mappings of local variables of a procedure to their values. Furthermore, on each procedure call, the program pushes $l$ on the stack along with the program point. Everything would be popped off from $l$ when the procedure returns control to the callee. |
| One instance where small step semantics would be necessary is in concurrency, so that we can take into account interleaving. | One instance where small step semantics would be necessary is in concurrency, so that we can take into account interleaving. | ||
| Line 124: | Line 121: | ||
| When a procedure call is encountered, it is replaced by the statements of the procedure (so the procedure code is inlined with the code of the callee). A problem arises when the procedure being inlined is recursive. One approach to dealing with this situation is to inline the recursive procedure a few times, and then treat the recursive call as a havoc statement (as described above). However, even if this is done, inlining increases the size of the code exponentially. | When a procedure call is encountered, it is replaced by the statements of the procedure (so the procedure code is inlined with the code of the callee). A problem arises when the procedure being inlined is recursive. One approach to dealing with this situation is to inline the recursive procedure a few times, and then treat the recursive call as a havoc statement (as described above). However, even if this is done, inlining increases the size of the code exponentially. | ||
| - | |||
| - | |||
| === Treat procedure calls as goto statements === | === Treat procedure calls as goto statements === | ||