rvsdg-treedc

rvsdg-treedc is a tool to read a RVSDG represented as a dotfile, load it into an in-memory graph representation and run a set of heuristic treewidth algorithms on the graph. Implements and reports on heuristics described in Googate & Detchter.

Includes a tool to generate dotfiles from XML representation created by the jlm compiler. See more in xml_parser

Building

Depends on the unittest-cpp framework: Installation instructions

mkdir build
cd build && cmake ..
make

Running

By default, parses and runs heuristics on every dotfile in xml_parser/dotfiles. Takes an optional argument to run on another directory.

bin/rvsdg-treedc xml_parser/dotfiles

The run_heuristics.sh script runs the heuristics on all generated graphs for a set of xml-files. By default this is the programs of the jlm-polybench benchmark suite. The output from the heuristics are aggregated and logged to run_heuristics.log. The script also supports aggregating the output from the heuristics, feeding it into a set of gnuplot files to generate visualisations of the output.

Testing

A set of sanity tests in test/unittests.cpp are run on the default target.

More autogenerated tests for the heuristics can be created by the tools in gen_tests:

cd gen_tests
./gen_test.sh

this reads the test_config.txt file and autogenerates unittest-cpp tests for each graph with bounds found. The graphs are encoded in the graph6 format and are retrieved from the ToTo treewidth database, along with the graphs upper and lower bounds on treewidth.

To get the graph6 string from a chosen graph in the database, this can be retrieved it from the URL itself e.g., https://treedecompositions.com/#/graph/FrSXg, where the graph6 string is FrSXg. Optionally, use the database query to and exporting the graphs to a csv file. This can then be converted to a test_config-file by using the conf_from_csv.py tool:

python3 conf_from_csv.py input_csv.csv test_config.txt

The current tests in the config are mix of graphs with high bounds gap with an increasing number of vertices.

After the tests are generated, they can be run with the heurisitc_tests target:

cmake .. -DTESTS=1
make
bin/heurisitc_tests

rvsdg-xmlparser

Parser of the RVSDG XML output from the jlm compiler: jlm-print --j2rx, producing a corresponding dotfile for each region in the graph.

Uses the pugixml library to parse the XML, which can be acquired via apt as libpugixml-dev, or via other means as described on https://pugixml.org/.

Running

Produces dotfiles from an input RVSDG XML-file, placing them in the xml_parser/dot_files folder.

bin/xml_parser path/to/file.xml

To perform this translation, nodes and edges are mapped from the XML to the graph by considering inputs to be edges into, and outputs edges out of their corresponding nodes. Arguments and results of a region are modeled as the entry and exit nodes of the graph respectively.