cs618-2020-21 Lecture Material
Lecture Time: 3:30 to 5:00 pm (Slot 11)
We have moved to moodle. Please check your batch (Tuesday or Friday) for the meeting
There will be no live lectures. Pre-recorded lecture videos will be released in the beginning of the week and lecture slots will be used for live discussions which will be supplemented by moodle discussions. Use the meeting slots to ask questions and clarify doubts. Additionally, you can ask questions on Moodle.
Week Lecture Day Module Topics Lecture Videos Lecture Slides Interactive Tutorial (Moodle)
0
 Tuesday 11 Aug
Introduction and Motivation
Examples of optimization and analyses, course Overview
The lecture begin with a welcome, and then motivate the need of a systematic analysis technique by illustrating the classical optimizations, which is followed by examining a contemporary optimization of heap memory. Then the lecture tries to answer the question what is program analysis, The lecture concludes with the course details.
Friday 14 Aug
1
 Tuesday 18 Aug
Bit Vector Data Flow Frameworks
Live variables analysis, Available expressions analysis, Observations about data flow analysis, Reaching definitions analysis, Anticipable expressions analysis, A taxonomy of data flow analysis
The first lecture in this module introduces bit vector data flow frameworks with the help of live variables analysis. It introduces the concepts of data flow information, data flow equations, the process of solving the data flow equations, the soundness and precision of solutions, the role of initialization, and the ineaxtness of data flow analysis. For convenience, the lecture has been divided into four parts: Live Variables Analysis Part A, Live Variables Analysis Part B, Live Variables Analysis Part C, and Live Variables Analysis Part D.

The second lecture in this module builds on the concepts of bit vector data flow frameworks with the help of available expressions analysis. In particular, it shows that the data flow equations continue to have the same form. It also explains the role of boundary information and describes the soundness and precision requirements of available expressions analysis. The lecture has been divided into three parts: Available Expressions Analyisis Part A, Available Expressions Analysis Part B, Available Expressions Analysis Part C.

The third lecture of the module introduces reaching definitions analysis and anticipable expressions analysis and concludes the module by identifying the common features of bit vector frameworks.
Friday 21 Aug
2
 Tuesday 25 Aug
Friday 28 Aug
3
 Tuesday 1 Sep
Friday 4 Sep
4
 Tuesday 8 Sep
Theoretical Abstractsions in Data Flow Analysis
Introduction to constant propagation, Lattice theoretic modeling of data flow information, Flow functions, monotonicity and distributivity, MoP and MFP assignments, Complexity of data flow analysis, Worklist based methods
The first lecture in this module begins by motivating the need of a more general setting which is then followed by a digression on lattices.

The second lecture in this moduls explains lattice theory and has been divided in three parts: Lattice Theory Part A, Lattice Theory Part B, Lattice Theory Part C.

The third lecture explains the general theory behind setting up the wolrld of data flow values in terms of lattice and formalizes the notions of soundness and precision of the abstraction created by data flow values. It has been divided into four parts: Data Flow Values Part A, Data Flow Values Part B, Data Flow Values Part C, and Data Flow Values Part D.

The fourth lecture in this module explains the flow functions and the solutions of data flow analysis (Part A, Part B, Part C) and the algorithms of data flow analysis.
Friday 11 Sep
5
 Tuesday 15 Sep
Friday 18 Sep
6
 Tuesday 22 Sep
Friday 25 Sep

Monday 28 Sep

Friday 2 Oct Holiday
7
 Tuesday 6 Oct
Midsem Week





Friday 9 Oct
8
 Tuesday 13 Oct
General Data Flow Frameworks
Constant propagation revisited,Strongly live variables analysis, Pointer analysis, Anderson's and Steensgard's approaches, Flow-sensitive pointer analysis, Liveness-based pointer analysis, Liveness analysis of heap data
We have deliberately slowed down by two weeks in response to the request of a dead week before the mid-senester examination and general request to reduce the teaching material for the online mode.

The third module of the course begins by exploring precise modelling of general frameworks and introduces the loop closure bound and separability of flow functions. Then we complete the story of constant propagation.

The second lecture in this module covers strongly live variables analysis and the third lecture introduces pointer analysis (Part A, Part B, Part C, and Part D). This is followed by studying flow-insensitive pointer analysis (Part A and Part B). The final lecture covers flow-sensitive pointer analysis (Part A, Part B, and Part C). and liveness based pointer analysis.
The module concludes by studying heap reference analysis to identify live heap memory.

                                                                                                                                              












Friday 16 Oct
9
 Tuesday 20 Oct
Friday 23 Oct
10
 Tuesday 27 Oct
Friday 30 Oct Holiday
Saturday 31 Oct
Interprocedural Data Flow Analysis
Introduction to interprocedural data flow analysis, Functional Approach, Call Strings base method, Value context based interprocedural analysis, A unified view of interprocedural analysis


11
 Tuesday 3 Nov
Friday 6 Nov
12
 Tuesday 10 Nov
Friday 13 Nov
13
 Tuesday 17 Nov
Friday 20 Nov Wrap Up