[Compilers] Interprocedural Analysis

Cost of procedure calls

Without interprocedural analysis, make the flow function for call nodes return TOP. –> loss of precision (“lost-precision” cost) / indirect cost
Calls incur cost of return, argument & result passing, stack frame maintenance. –> “direct runtime” cost / direct cost

Ways to address

Get rid of calls using inlining and other techniques.
– Pros: eliminate overhead of call/return sequence, eliminate overhead of passing args & returning results, can optimize callee in context of caller and vice versa
– Cons: can increase compiled code space requirements, can slow down compilation, recursion?
– Let this be done by heuristics (machine learning can be used these days…)

Interprocedural analysis
– Pros: extend intraprocedural analysis to work across calls, doesn’t increase code size
– Cons: doesn’t eliminate direct runtime costs of calls, may not be as effective as inlining at cutting the precision cost of procedure calls.

Interprocedural Analysis

Simple approach: create a single CFG

Given call graph and CFGs of procedures, create a single CFG.
– connecting call sites to entry nodes of callees.
– connecting return nodes of callees back to calls.

Cons: speed, separate compilation, imprecision due to unrealizable paths.

Another approach: summaries

Compute summary info for each procedure
– Callee summary: summarizes effect/results of callee procedures for callers
– Caller summary: summarizes context of all callers for callee procedure.

Compute summaries using the worklist algorithm 🙂
– output (callee): summarizes effect/results (output) of callee procedures for callers
– input (caller): summarizes context (input) of all callers for callee procedure


main
fgh
inputoutputinputoutputinputoutputinputoutput

u
mainu
gl
mainl
fl
hu
fu
mainu
uuluullu

main
fg
inputoutputinputoutputinputoutput
u
mainu
gl
mainl
fu, llu, l
gu, l
maineu, l

Problem: need context!

Approach #1 to context-sensitivity


main
fg
inputoutputinputoutputinputoutput
L0: u
mainL0: uL1: u
gL0: uL1: uL1: l
mainL0: uL2: lL1: uL1: l
fL0: uL2: l
L1: u
L3: l
L1: l

gL0: uL2: l
L1: u
L3: l
L1: l
L3: u
fL0: u

L2: lL2: uL1: u
L3: l
L1: l
L3: u

Problem: we might need more than one level of stack… –> Shivers’ k-CFA

Approach #2 to context-sensitivity

Use transfer functions: this looks like functions from input information to output information.


main
fg
inputoutputinputoutputinputoutput
u: u
main
u: u
gu: l
mainl: l
f
u: u
l: l
u: l

g
u: l
l: u
f
l: u
mainu: u

For data-based context sensitivity, we can also run the analysis bottom-up.
There are ways to handle the problem using Graph Theory (Reps Horowitz and Sagiv 95 (RHS))

Procedure specialization

Interprocedural analysis is great for callers, but for the callee, information is still merged.
Even if you know everything about the context, it might not help! So just duplicate the callee procedures and it might help.

Summary

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.