《程序静态分析》 - 南京大学 李樾、谭添

课程笔记

Introduction

Static analysis: Analyzes a program P to reason about its behaviors and determines whether it satisfies some properties before running P.

Rice’s Theorem: Any non-trivial property of the behavior of programs in a r.e. language is undecidable.

r.e. (recursively enumerable) = recognizable by a Turing-machine

non-trivial properties ~= interesting properties ~= the properties related with run-time behaviors of programs

Static Analysis: Ensure (or get close to) soundness, while making good trade-offs between analysis precision and analysis speed.

Intermediate Representation

AST:

• high-level and closed to grammar structure
• usually language dependent
• suitable for fast type checking
• lack of control flow information

IR:

• low-level and closed to machine code
• usually language independent
• compact and uniform
• contains control flow information
• usually considered as the basis for static analysis

Three-Address Code (3AC): There is at most one operator on the right side of an instruction

Static Single Assignment (SSA): All assignments in SSA are to variables with distinct names

SSA vs 3AC:

• Flow information is indirectly incorporated into the unique variable names
• Define-and-Use pairs are explicit
• SSA may introduce too many variables and phi-functions
• May introduce inefficiency problem when translating to machine code (due to copy operations)

Basic blocks (BB) are maximal sequences of consecutive three-address instructions with the properties that 1)It can be entered only at the beginning; 2) It can be exited only at the end.

How to build:

1. Determine the leader instructions set S
2. Build BBs from s in S

Control Flow Graph (CFG): Basic blocks plus control flow edges (conditional or unconditional jumps).

Data Flow Analysis — Foundations

What is Data Flow Analysis?

Foundations first, because different perspectives help with review