Skip to content

Latest commit

 

History

History
73 lines (56 loc) · 1.82 KB

README.md

File metadata and controls

73 lines (56 loc) · 1.82 KB
Raw

Static Analysis for TIP

An implementation of a bunch of different static analyses for TIP (Tiny Imperative Language) presented by Anders Møller during the Static Analysis course at University of Aarhus.

Contributors:

RUN

Use make compile to compile the files, and e.g. make run FILE=tests/sign_interprocedural_normalized.tip to run the analyses on tests/sign_interprocedural_normalized.tip.

TIP

Programs:

P ::= F
    | F P

Functions:

F ::= id(id, ..., id) { S return E; }

Statements:

S ::= var id, ..., id;
    | id = E;
    | *id = E;
    | output E;
    | S S
    | if (E) { S }
    | if (E) { S } else { S }
    | while (E) { S }

Expressions:

E ::= intconst
    | id
    | E+E | E-E | E*E | E/E | E>E | E==E
    | (E)
    | input
    | id(E, ..., E)
    | (E)(E, ..., E)
    | &id
    | malloc
    | *E
    | null

ANALYSES

  • Type Analysis
  • Control Flow Analysis/Closure Analysis
  • Intraprocedural Liveness Analysis
  • Intraprocedural Available Expressions Analysis
  • Intraprocedural Constant Propagation Analysis
  • Intraprocedural Initialized Variables Analysis
  • Intraprocedural Reaching Definitions Analysis
  • Intraprocedural Very Busy Expressions Analysis
  • Intraprocedural, Context Insensitive Interprocedural, and Context Sensitive Interprocedural Sign Analysis
  • Interprocedural Pointer Analysis using Andersen's Analysis

TODO

  • Currently working on making a separate normalized AST. As a consequence Andersen's Analysis is currently commented out.
  • The interprocedural analyses assumes that variable names are unique across functions.