This is a library to process Bril programs in Haskell. It includes a set of types that contain a Bril AST and utilities to convert the JSON representation of Bril programs to and from the AST along with testing utilities.
This is the top level package that contains the modules.
This package contains two modules Bril.Lang.AST and
Bril.Lang.Parse which contain code for
represending Bril programs in a type-safe way and convert that
representation to/from JSON.
The module Bril.Structure.CFG
contains utilities for converting a Bril program into basic blocks and CFG
and performing operations on them like finding dominators of each basic
block etc.
The module Bril.Structure.SSA
exports a function ssa for converting a Bril program into SSA form
by adding phi instruction and renaming variables and the function ssa'
which removes all the phi instructions and replaces with variable copies.
The module Bril.Structure.Loop
exports functions to extract all the natural loops in a Bril program.
The module Bril.Optim contains all the optimisation passes and
currently implements Trivial Dead Code Elimination (Bril.Optim.DCE),
Data Dlow Analysis (just Live Variables for now, Bril.Optim.DataFlow)
and Loop Invariant Code Motion (Bril.Optim.Loop).
The package is built using stack
which can be installed using brew install haskell-stack on macOS.
Currently the Main.hs file implements dominator utilities and SSA conversion,
and the optimization passes. It takes in a JSON Bril program and outputs the result.
$> stack build
$> bril2json < path/to/bril/program | stack run [doms | front | tree | ssa | nossa | tdce | licm]
The directory spec contains QuickCheck
specifications for the utility functions. Run them using stack.
$> stack test
...
bril-hs> test (suite: bril-hs-test)
=== prop_dominatorsDefn from spec/Bril/Structure/Spec.hs:75 ===
+++ OK, passed 10000 tests.
=== prop_dominationTreeDefn from spec/Bril/Structure/Spec.hs:91 ===
+++ OK, passed 10000 tests.
=== prop_dominationFrontierDefn from spec/Bril/Structure/Spec.hs:107 ===
+++ OK, passed 10000 tests.
bril-hs> Test suite bril-hs-test passed
Completed 2 action(s).
The directory test\ssa contains two test suites: check and overhead:
check uses Turnt to test whether the SSA
conversion is indeed SSA. overhead runs the full to SSA - from SSA roundtrip
and measures the overhead of the conversion.
$> cd test/ssa/check
$> turnt *.bril
1..6
ok 1 - argwrite.bril
ok 2 - if-const.bril
ok 3 - if.bril
ok 4 - loop.bril
ok 5 - selfloop.bril
ok 6 - while.bril
The average overhead of SSA roundtrip for these small test programs is 34%.
$> cd test/ssa/overhead
$> brench brench.toml
benchmark,run,result
if,baseline,5
if,ssa,7
if,roundtrip,7
loop,baseline,26
loop,ssa,31
loop,roundtrip,31
selfloop,baseline,20
selfloop,ssa,25
selfloop,roundtrip,26
argwrite,baseline,4
argwrite,ssa,6
argwrite,roundtrip,7
while,baseline,34
while,ssa,41
while,roundtrip,41
if-const,baseline,5
if-const,ssa,6
if-const,roundtrip,6
The directory test\licm contains two test suites. It has a turnt.toml
to test whether the LICM produces the same output as the original program. There is also
a brench.toml that measures the impact of LICM optimization.
$> cd test/licm
$> brench brench.toml
...
The file performance.csv contains the result on these benchmarks.
$> cat test/licm/performance.csv
...
,,min,0
,,max,22.584
,,avg,3.617
,,stddev,5.243
The average speedup obtained over SSA is 3.6%.