programl 0.2.0

A Graph-based Program Representation for Data Flow Analysis and Compiler Optimizations

ProGraML: Program Graphs for Machine Learning

License
OS	GNU/Linux, macOS ≥ 10.15
Python Versions	3.6, 3.7, 3.8, 3.9
development Branch
stable Branch
Development Activity

1. Overview
2. Getting Started
3. Installation
4. Datasets
5. Constructing the ProGraML Representation
6. Step 1: Compiler IR
7. Step 2: Control-flow
8. Step 3: Data-flow
9. Step 4: Call graph
10. Usage
11. End-to-end C++ flow
12. Dataflow experiments
13. Contributing
14. Acknowledgements

Overview

ProGraML is a representation for programs as input to a machine learning model.

Key features are:

• Expressiveness: We represent programs as graphs, capturing all of the control, data, and call relations. Each node in the graph represents an instruction, variable, or constant, and edges are positional such that non-commutative operations can be differentiated.
• Portability: ProGraML is derived from compiler IRs, making it independent of the source language (e.g. we have trained models to reason across five different source languages at a time). It is easy to target new IRs (we currently support LLVM and XLA).
• Extensibility: Features and labels can easily be added at the whole-program level, per-instruction level, or for individual relations.

Getting Started

To get stuck in and play around with our graph representation, visit:

Or if papers are more your ☕, have a read of ours:

Installation

Install the latest release of the Python package using:

pip install -U programl

See INSTALL.md for alternative installation options.

Datasets

Please see this doc for download links for our publicly available datasets of LLVM-IRs, ProGraML graphs, and data flow analysis labels.

Constructing the ProGraML Representation

The ProGraML representation is constructed in multiple stages. Here we describe the process for a simple recursive Fibonacci implementation in C. For instructions on how to run this process, see Usage below.

Step 1: Compiler IR

We start by lowering the program to a compiler IR. In this case, we'll use LLVM-IR. This can be done using: clang -emit-llvm -S -O3 fib.c.

Step 2: Control-flow

We begin building a graph by constructing a full-flow graph of the program. In a full-flow graph, every instruction is a node and the edges are control-flow. Note that edges are positional so that we can differentiate the branching control flow in that switch instruction.

Step 3: Data-flow

Then we add a graph node for every variable and constant. In the drawing above, the diamonds are constants and the variables are ovals. We add data-flow edges to describe the relations between constants and the instructions that use them, and variables and the constants which define/use them. Like control edges, data edges have positions. In the case of data edges, the position encodes the order of a data element in the list of instruction operands.

Step 4: Call graph

Finally, we add call edges (green) from callsites to the function entry instruction, and return edges from function exits to the callsite. Since this is a graph of a recursive function, the callsites refer back to the entry of the function (the switch). The external node is used to represent a call from an external site.

The process described above can be run locally using our clang2graph and graph2dot tools: clang clang2graph -O3 fib.c | graph2dot

Usage

End-to-end C++ flow

In the manner of Unix Zen, creating and manipulating ProGraML graphs is done using command-line tools which act as filters, reading in graphs from stdin and emitting graphs to stdout. The structure for graphs is described through a series of protocol buffers.

This section provides an example step-by-step guide for generating a program graph for a C++ application.

1. Install LLVM-10 and the ProGraML command line tools.
2. Compile your C++ code to LLVM-IR. The way to do this to modify your build system so that clang is passed the -emit-llvm -S flags. For a single-source application, the command line invocation would be:

$ clang-10 -emit-llvm -S -c my_app.cpp -o my_app.ll

For a multi-source application, you can compile each file to LLVM-IR separately and then link the results. For example:

$ clang-10 -emit-llvm -S -c foo.cpp -o foo.ll
$ clang-10 -emit-llvm -S -c bar.cpp -o bar.ll
$ llvm-link foo.ll bar.ll -S -o my_app.ll

3. Generate a ProGraML graph protocol buffer from the LLVM-IR using the llvm2graph commnand:

$ llvm2graph < my_app.ll > my_app.pbtxt

The generated file my_app.pbtxt uses a human-readable ProgramGraph format which you can inspect using a text editor. In this case, we will render it to an image file using Graphviz.

4. Generate a Graphviz dotfile from the ProGraML graph using graph2dot:

$ graph2dot < my_app.pbtxt > my_app.dot

5. Render the dotfile to a PNG image using Graphviz:

$ dot -Tpng my_app.dot -o my_app.png

Dataflow experiments

1. Follow the instructions for building from source
2. Download and unpack our dataflow dataset
3. Train and evaluate a graph neural network model using:

bazel run -c opt //tasks/dataflow:train_ggnn -- \
    --analysis reachability \
    --path=$HOME/programl

where --analysis is the name of the analysis you want to evaluate, and --path is the root of the unpacked dataset. There are a lot of options that you can use to control the behavior of the experiment, see --helpfull for a full list. Some useful ones include:

• --batch_size controls the number of nodes in each batch of graphs.
• --layer_timesteps defines the layers of the GGNN model, and the number of timesteps used for each.
• --learning_rate sets the initial learning rate of the optimizer.
• --lr_decay_rate the rate at which learning rate decays.
• --lr_decay_steps number of gradient steps until the lr is decayed.
• --train_graph_counts lists the number of graphs to train on between runs of the validation set.

🏗️ Under construction We are in the process of refactoring the dataflow experiments with a revamped API. There are currently bugs in the data loader which may affect training jobs, see #147.

Contributing

Patches, bug reports, feature requests are welcome! Please use the issue tracker to file a bug report or question. If you would like to help out with the code, please read this document.

Acknowledgements

Made with ❤️️ by Chris Cummins and Zach Fisches, with help from folks at the University of Edinburgh and ETH Zurich: Tal Ben-Nun, Torsten Hoefler, Hugh Leather, and Michael O'Boyle.

Funding sources: HiPEAC Travel Grant.