Introduction to Program Analysis
and Optimization (CS5863)
Instructors: Jyothi Vedurada
TA: Soumik, Pirapuraj, Siddharth, Chinmay and Raj
Google class code: amfsrwq
What is Program Analysis?
• Approximating the runtime behaviour of a program statically
• and applying the analysis results for optimizations and other end tasks.
void main(){
Can this computation be avoided?
int a, b;
… Is ‘b’ a constant on all possible executions of the program?
a = b * 4;
…
}
Constant Propagation Analysis
What is Program Optimization?
• Transforming an input program to improve its efficiency without
changing its output.
Can this computation be avoided?
Is “b+c” sub expression available here?
What is Program Optimization?
• Transforming an input program
to improve its efficiency
without changing its output.
Can this computation be avoided?
Is “b+c” sub expression available here?
Common Sub-expression
Elimination
More Examples
Can the compiler reorder these instructions?
S1: p.f = varA + 1 Does statement S2 depend on S1?
S2: varB = q.f * 2
Do variables p and q point to the same memory location?
Opt/Transformation: Instruction Reordering
Analysis: Pointer Analysis
More Examples (Contd..)
For I = 1, 10 Can this loop be run parallel?
A(I) = A(I) + 5
For I = 1, 10 How about this loop?
A(I) = A(I-1) + 5
For I = 1, 10 How about this loop?
S1: A(I) = B(I-1) + C(I) Is there a data dependence between S1 and S2?
S2: B(I) = A(I+2) + C(I)
S1(1): A(1) = B(0) + C(1)
S2(1): B(1) = A(3) + C(1) Opt/Transformation: Parallelization
---- Analysis: Dependence Analysis
S1(2): A(2) = B(1) + C(2)
S2(2): B(2) = A(4) + C(2)
Where does
it fit in
Compiler
Passes? Analysis
Transformation
Are Optimizations All about Program Analysis?
No
• Optimizations (loop transformations for locality, register allocation,…)
• Security (array index range, dangling pointers,…)
• Bug funding (null pointer exceptions, data races,…)
• Debugging (slice)
• Program understanding (refactoring)
• Many others…
Learning Outcomes
• To implement program analyses and optimizations using efficient data
structures, frameworks and tools
• To design and implement analyses for interesting new problems
• To design and implement new optimizations and transformations
• To understand the challenges associated with designing a modern
compiler technology
Course Topics
• Introduction to Control-flow graphs, lattices, Iterative data-flow analysis,
du/ud chains
• Intra/inter-procedural constant propagation, Static Single Assignment form.
• Pointer analysis: various sensitivity -- flow-sensitive, context-sensitive,
object-sensitivity, value contexts and demand-driven variants.
• Program slicing
• Dependence analysis for loop transformations and parallelization
• Dynamic analysis
• Applications: Bug detection (functionality bugs, performance bugs, security
bugs), refactoring, program understanding.
Logistics
• Google classroom for assignment submissions, announcements and
discussions.
• Make sure from your side that you are added to the classroom
• Evaluation:
• End-Sem: 25%
• Assignments: 5%+40%
• Paper presentation: 10%
• Surprise Quizzes: (3) 15%
• Class participation: 5%
• C slot (Monday 11 am. Wednesday 10 AM. Thursday 9 AM.)
Assignments
• Assignments should be done using LLVM framework
• A1 focuses on getting hands-on experience with LLVM
• Other assignments (3 or 4) would involve implementing various
analyses and optimizations.
References
1. Advanced Compiler Design and Implementation: Steven S. Muchnick, First Edition, Morgan
Kaufmann publishers, 1997 (ISBN: 978-1-55860-320-2).
2. Compilers: Principles, Techniques, and Tools: A V Aho, Monical Lam, R Sethi, J D Ullman, Second
Edition, Pearson Education India publisher, 2013 (ISBN: 978-93-325-1866-7).
3. Principles of Program Analysis: Flemming Nielson, Hanne Riis Nielson, Chris Hankin, Second
Edition, Springer, 2005 (ISBN: 978-3540654100).
4. Y. N. Srikant and Priti Shankar. “The Compiler Design Handbook”, Second Edition, CRC Press,
2007.