Static program analysis for TIP
TIP is a tiny imperative programming language aimed at teaching the fundamental concepts of static program analysis. This code accompanies the lecture notes on Static Program Analysis.
Prerequisites:
We suggest you to use IntelliJ for working on TIP, but all the following options are viable.
git clone https://github.com/cs-au-dk/TIP.git tip
Tip.scala
in src/tip
, then select "Run 'Tip'". To supply arguments, use Run... -> Edit Configurations in the Run menu.Important: if you experience spurious type errors reported by IntelliJ for code involving Scala implicits, try disabling type-aware highlighting
by clicking on the small [T]
icon on the bottom right corner of the window.
If your IntelliJ has high-CPU and high-memory peaks while editing, the following tweaks might be useful:
[T]
icon on the
bottom right corner of the window.-Xms500m -Xmx1500m
IntelliJ offers an option to optimize imports upon commit. We suggest not to use that feature, as it may remove needed imports thereby breaking compilation.
A wrapper command tip
(tip.bat
for Windows) is provided to compile and run
TIP with the given arguments.
Example:
./tip -run examples/fib.tip
To build:
sbt compile
Usage:
tip <options> <source> [out]
where <source>
can be a file or a directory containing .tip
files and
[out]
is an output directory (default: ./out).
To see the possible options, run tip
without options.
Option -verbose
is recommended when developing and testing analyses.
The main function Tip.scala
emits control flow graphs and analysis results as ".dot" files
that can be processed by Graphviz to produce images, for example using the Graphviz dot command-line tool:
dot -O -Tpng out/example.tip__sign.dot
Some analyses require the programs use restricted subsets of TIP. The following kinds of normalization can be performed automatically:
-normalizecalls
:
normalizes function calls to be top-level only and such that arguments are identifiers
(e.g. id1 = id2(id3,id4)
)-normalizereturns
:
normalizes return expressions to be identifiers
(e.g. return id
)-normalizepointers
:
normalizes pointer operations to primitive statements
(id = alloc P
where P
is null or an integer constant, id1 = &id2
, id1 = id2
, id1 = *id2
, *id1 = id2
, orid = null
)If one or more of these options are enabled, the normalized program is printed to e.g. out/example.tip__normalized.tip
.
This implementation takes advantage of many cool Scala language features that allow the code to be concise and flexible. Many of these language features are quite intuitive and easy to understand for anyone familiar with object oriented and functional programming, even without prior knowledge of Scala. Still, the following language features deserve some extra attention:
Tutorials and extensive documentation for Scala are available at http://docs.scala-lang.org/.
Useful tips:
To avoid using inconsistent code styles and meaningless diffs caused by IDE reformatting we use scalafmt.
The code is automatically formatted upon compilation by SBT.
Before committing, please double-check that all the code is in the right format by executing sbt scalafmt
.
To automatically format when the file is saved, go to File -> Settings..., under 'Editor', 'Code Style', 'Scala', make sure 'Scalafmt' is selected under 'Formatter'. (Unfortunately the formatting is only triggered when the file is explicitly saved with Ctrl-S.)
with contributions from