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		f		g		h
	input	output	input	output	input	output	input	output
	u
main	“				u
g	“				“	l
main	“		l		“	“
f	“		“		“	“	l
h	“		“		“	“	“	u
f	“		“	u	“	“	“	“
main	“	u	“	“	“	“	“	“
	u	u	l	u	u	l	l	u

	main		f		g
	input	output	input	output	input	output
	u
main	“				u
g	“				“	l
main	“		l		“	“
f	u, l		“	l	u, l	“
g	“		“	“	“	u, l
main	“	e	u, l	“	“	“
	…	…	…	…	…	…

Problem: need context!

Approach #1 to context-sensitivity

	main		f		g
	input	output	input	output	input	output
	L0: u
main	L0: u				L1: u
g	L0: u				L1: u	L1: l
main	L0: u		L2: l		L1: u	L1: l
f	L0: u		L2: l		L1: u L3: l	L1: l
g	L0: u		L2: l		L1: u L3: l	L1: l L3: u
f	L0: u		L2: l	L2: u	L1: 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		f		g
	input	output	input	output	input	output
	u: u
main	“				u: u
g	“				“	u: l
main	“		l: l		“	“
f	“		“		u: u l: l	u: l
g	“		“		“	u: l l: u
f	“		“	l: u	“	“
main	“	u: 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