Department of Computer Science & Engineering

Syllabus

• Basic Dataflow Analysis: iterative worklist based, dead-code elimination, reaching definitions, monotone frameworks, confluence operators, MFP/MOP solution, analysis dimensions: flow-sensitivity, context-sensitivity, field-sensitivity, path-sensitivity.
• Pointer Analysis: introduction, applications, as a DFA problem, design decisions for precision vs. efficiency trade-off, heap modeling, analysis dimensions, set implementation, Andersens's and Steensgaard's analyses, common model. as a graph problem, reachability, online cycle detection, dominators, propagation orders, optimal ordering, heuristics, applications to optimizations such as dead-code elimination, reaching definitions, parallelization, escape analysis, parallelization of PTR, constraint-based formulation, parallelization using replication, graph rewrite-rules.
• Shape Analysis: limitations of pointer analysis, identification of simple structures like lists, identifying trees, DAGs and cyclic graphs, identifying rotations, limitations, reversal and other transformations, limitations.
• Dynamic Analysis: limitations of static analysis, trade-offs, applications, introduction, profiling techniques, intrusive and non-intrusive methods, limitations, applications, finding invariants, equality invariants, finding affine invariants and other applications dynamic type inferencing, limitations.
• Polyhedral Model: iteration space, identifying inequalities, ILP, transformations, tiling, unrolling, fusion, splitting, skewing, interchange.
• Parallelization: motivation, simple auto-parallelization, dependencies, using polyhedral model, limitations, synchronization, atomics, barriers, locks, semaphores, happens-before and may-happen-before analysis, parallelizing irregular algorithms.
• Program Slicing: concept, applications, methodology, static slicing, interprocedural analysis, object-oriented codes, exception-handling constructs, dynamic slicing, overheads, precision.
• Security Analysis: information flow, role of program analysis, applications, identifying string vulnerabilities, array out-of bound checks, null pointer analysis, dangling pointers, pointers beyond a range, type-based security, secure constructs and operations.

Textbooks

• Advanced Compiler Design and Implementation, Muchnick, Morgan Kaufmann 1997.

References

• Compilers: Principles, Techniques and Tools (2nd Edition), Aho, Lam, Sethi, Ullman, Addison Wesley 2006.
• Data Flow Analysis: Theory and Practice, Khedker, Sanyal, Karkare, CRC Press 2009.
• Principles of Program Analysis: Nielson, Nielson, Hankin, Springer 2004.