Static Program Analysis

Preface......Page 2
Introduction......Page 6
Undecidability of Program Correctness......Page 10
The Syntax of TIP......Page 12
Normalization......Page 15
Abstract Syntax Trees......Page 16
Control Flow Graphs......Page 17
Type Analysis......Page 20
Types......Page 21
Type Constraints......Page 22
Solving Constraints with Unification......Page 24
Limitations of the Type Analysis......Page 28
Record Types......Page 30
Motivating Example - Sign Analysis......Page 33
Lattices......Page 34
Constructing Lattices......Page 36
Equations, Monotonicity & Fixed-Points......Page 38
Dataflow Analysis with Monotone Frameworks......Page 45
Sign Analysis, revisited......Page 46
Constant Propagation Analysis......Page 51
Fixed-Point Algorithms......Page 52
Live Variables Analysis......Page 56
Available Expressions Analysis......Page 60
Very Busy Expressions Analysis......Page 63
Reaching Definitions Analysis......Page 64
Forward, Backward, May & Must......Page 66
Initialized Variables Analysis......Page 68
Transfer Functions......Page 69
Interval Analysis......Page 70
Widening & Narrowing......Page 73
Assertions......Page 78
Branch Correlations......Page 80
Interprocedural Control Flow Graphs......Page 86
Context Sensitivity......Page 90
Context Sensitivity with Call Strings......Page 91
Context Sensitivity with the Functional Approach......Page 94
Closure Analysis for λ-Calculus......Page 98
The Cubic Algorithm......Page 99
TIP with Function Pointers......Page 100
Control Flow in Object oriented Languages......Page 104
Allocation-Site Abstraction......Page 105
Andersen Algorithm......Page 106
Steensgaard Algorithm......Page 108
Interprocedural Points-To Analysis......Page 109
Null Pointer Analysis......Page 110
Flow-Sensitive Points-To Analysis......Page 113
Escape Analysis......Page 115
Collecting Semantics for TIP......Page 116
Abstraction & Concretization......Page 119
Soundness......Page 125
Optimality......Page 130