Fast, Effective Analysis and
Optimization of C++ Programs
David F. Bacon and Peter F. Sweeney
IBM T.J. Watson Research Center
David F. Bacon
10/11/98
1
IBM C++ Optimization Group
Michael Burke
u Michael Hind
u G. Ramalingam
u Harini Srinivasan
u
David F. Bacon
10/11/98
2
Introduction
u
C++ has powerful features
– Virtual Function Calls
– Virtual Base Classes
– Dynamic Casts
u
But they cost
– Time
– Space
David F. Bacon
10/11/98
3
Optimization
u
?
Analysis
– ask the right questions
u
Transformation
– use the answers
u
Evaluation
– how well does it work?
David F. Bacon
10/11/98
4
?
Analysis Framework
u
What classes are created?
shape
triangle
rectangle
square
David F. Bacon
10/11/98
5
?
Analysis Framework
u
What classes are created?
shape
triangle
rectangle
square
David F. Bacon
10/11/98
6
?
Analysis Framework
u
David F. Bacon
What are the classes of each value?
object->draw();
{ triangle }
sign.reshape();
{ rectange, square }
10/11/98
7
?
Class Hierarchy Analysis
u
What classes are created?
– all classes
u
What are the classes of each value?
– the classes derived from the declared type
David F. Bacon
10/11/98
8
?
Class Hierarchy Analysis
u
the classes derived from the declared type
shape
triangle
rectangle* r;
rectangle {rectangle,square}
square
David F. Bacon
10/11/98
square * s;
{square}
9
8
?
Rapid Type Analysis
u
What classes are created?
– the classes in the call graph
u
What are the classes of each value?
– the classes derived from the declared type
– that have been created
David F. Bacon
10/11/98
10
?
Rapid Type Analysis
u
the classes in the call graph
main
rectangle::draw
build
new square;
David F. Bacon
square::draw
10/11/98
11
?
Rapid Type Analysis
u
the classes in the call graph: {square}
main
build
new square;
David F. Bacon
square::draw
10/11/98
12
?
Rapid Type Analysis
u
What are the classes of each value?
– the classes derived from the declared type
– that have been created
shape
triangle
rectangle* r;
rectangle {square}
square
David F. Bacon
10/11/98
square * s;
{square}
13
Transformation
u
virtual base classes to non-virtual bases
u
dynamic casts to static casts
u
virtual calls to direct calls
David F. Bacon
10/11/98
14
Virtual Bases
shape
triangle
Is shape multiply
inherited?
u
Is that class live?
u
If not, make shape
a non-virtual base
rectangle
square
pyramid
David F. Bacon
u
10/11/98
15
Dynamic Casts
foo(shape* p) {dynamic_cast<square> p;}
What object types could p be?
u Is square the only possible type?
u If so, do a compile-time cast
u
David F. Bacon
10/11/98
16
Virtual Calls
p->draw();
What object types could p be?
u What draw() functions are defined?
u If only 1 draw() function
u
– resolve the call
David F. Bacon
10/11/98
17
Benefits of VFR
u
Time
– direct calls are faster
– in-lining is possible
u
Space
– unused functions can be eliminated
u
Understandability
– programmer doesn’t see unused code
David F. Bacon
10/11/98
18
Evaluation
u
Compare 3 analysis algorithms
– Rapid Type Analysis
– Class Hierarchy Analysis
– Unique Name
u
David F. Bacon
On virtual function resolution
10/11/98
19
Methodology
u
Use real programs as benchmarks
– 7 large programs 5000-20000 lines each
u
Determine causes of
– success
– failure
u
David F. Bacon
Evaluate against best possible algorithm
10/11/98
20
Dynamic Call Types
100%
80%
60%
40%
Direct Method
Indirect Function
20%
Direct Function
richards
deltablue
taldict
idl
simulate
hotwire
lcom
ixx
sched
0%
Program
David F. Bacon
10/11/98
21
Resolved Dynamic Calls
100%
80%
60%
Unresolved/Polymorphic
40%
Unresolved/Monomorphic
Resolved by RTA
Resolved by CHA
20%
richards
deltablue
taldict
idl
simulate
hotwire
lcom
ixx
sched
0%
Program
David F. Bacon
10/11/98
22
Why RTA Wins: ixx
String
u
RTA finds unused classes
u
String ops are in inner loops
u
Similar win for
UniqueString
– taldict
– hotwire
David F. Bacon
10/11/98
23
Why RTA Loses:sched
u
True Polymorphism
shape
u
Disjointed Polymorphism
shape
shape2
David F. Bacon
10/11/98
24
Reduction in Code Size
100%
80%
60%
Live
Not Eliminated/Unexecuted
40%
Eliminated by RTA
Eliminated by CHA
20%
richards
deltablue
taldict
idl
simulate
hotwire
lcom
ixx
sched
0%
Program
David F. Bacon
10/11/98
25
Speed of Analysis
Benchmark
sched
ixx
lcom
hotwire
simulate
idl
taldict
deltablue
richards
David F. Bacon
Size
(lines)
5,712
11,157
17,278
5,335
6,672
30,288
11,854
1,250
606
Analysis
Time (s)
1.94
5.22
6.50
2.06
2.75
6.42
1.78
0.44
0.32
10/11/98
Overhead
(%)
0.1%
1.4%
3.0%
1.3%
5.6%
1.4%
4.0%
2.4%
3.6%
26
Comparison: Alias Analysis
Best precision from a static analysis
u Complex algorithm--expensive to implement
u Slow
u
– between 0.4 and 55 source lines analyzed/second
– RTA is 45 to 8250 times faster
David F. Bacon
10/11/98
27
Comparison: Alias Analysis
100%
80%
60%
Unresolved/Polymorphic
Unresolved/Not Executed
Unresolved/Monomorphic
40%
Resolved by RTA
Resolved by CHA
20%
6:vcircle
8:shapes
12:primes
1:office
10:objects
5:garage
3:family
7:deriv2
9:deriv1
0%
Program
David F. Bacon
10/11/98
28
!
Contributions
u
Analysis Framework
u
Rapid Type Analysis (RTA) algorithm
u
Evaluation showing power of RTA
David F. Bacon
10/11/98
29
Rapid Type Analysis
!
RTA is effective:
– resolves 71% of virtual function calls
– reduces code size by 25%
u RTA is fast:
– analyzes 3300 lines per second
u RTA is often as good as alias analysis
u
David F. Bacon
10/11/98
30