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
|
|
|
|
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
|
|
|
|
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 |
|
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 |
|
|
|
|