Deep Data Flow Analysis
Authors: Chris Cummins
Zacharias Fisches
Tal Ben-Nun
Torsten Hoefler
Hugh Leather
Michael O'Boyle
Venue:  (2021)
Keywords: program representations
program analysis
compilers
graph neural networks

Abstract: Compiler architects increasingly look to machine learning when building heuristics for compiler optimization. The promise of automatic heuristic design, freeing the compiler engineer from the complex interactions of program, architecture, and other optimizations, is alluring. However, most machine learning methods cannot replicate even the simplest of the abstract interpretations of data flow analysis that are critical to making good optimization decisions. This must change for machine learning to become the dominant technology in compiler heuristics.

To this end, we propose ProGraML - Program Graphs for Machine Learning - a language-independent, portable representation of whole-program semantics for deep learning. To benchmark current and future learning techniques for compiler analyses we introduce an open dataset of 461k Intermediate Representation (IR) files for LLVM, covering five source programming languages, and 15.4M corresponding data flow results. We formulate data flow analysis as an MPNN and show that, using ProGraML, standard analyses can be learned, yielding improved performance on downstream compiler optimization tasks.

Under review as a conference paper at ICLR 2021
DEEP DATA FLOW ANALYSIS
Anonymous authors Paper under double-blind review
ABSTRACT
Compiler architects increasingly look to machine learning when building heuris- ties for compiler optimization. The promise of automatic heuristic design, freeing the compiler engineer from the complex interactions of program, architecture, and other optimizations, is alluring. However, most machine learning methods cannot replicate even the simplest of the abstract interpretations of data flow analysis that are critical to making good optimization decisions. This must change for machine learning to become the dominant technology in compiler heuristics.
To this end, propose PROGRAML Program Graphs for Machine Learning a langunge-independent, portable representation of whole-program semantics for deep learning. To benchmark current and future learning techniques for com- piler analyses we introduce an open dataset of 461k Intermediate Representation (IR) files for LLVM, covering five source programming languages, and 15.4M corresponding data flow results. We formulate data flow analysis as an MPNN and show that, using PROGRAML, standard analyses can be learned, yielding improved performance on downstream compiler optimization tasks.
INTRODUCTION
Compiler implementation is complex and expensive activity (Cooper & Torczon, 2012). For this reason, there has been significant interest in using machine learning to automate various compiler tasks (Allamanis et al., 2018). Most works have restricted their attention to selecting compiler heuristics or making optimization decisions (Ashouri et al., 2018; Wang & O' O'Boyle, 2018). Whether learned or engineered by human experts, these decisions naturally require reasoning about the pro- gram and its behavior. Human experts most often rely upon data flow analyses (Kildall, 1973; Kam & Ullman, 1976). These are algorithms on abstract interpretations of the program, propagating in- formation of interest through the program's 's control-flow graph until fixed point is reached (Kam & Ullman, 1977). Two examples out of many data flow analyses are: liveness determining when resources become dead (unused) and may be reclaimed; and available expressions discovering which expressions have been computed on all paths to points in the program. Prior machine learn- ing works, the other hand, have typically represented the entirety of the program's 's behavior fixed-length, statically computed feature vector (Ashouri et al., 2018). Typical feature values might be the number of instructions in a loop the dependency depth. The weakness of these techniques is shown by the fact that they are trivially confused by the addition of dead code, which changes their feature vectors without changing the program's behavior its response optimizations. Such learning algorithms are unable to learn their own abstract interpretations of the program and so cannot avoid these pitfalls or more subtle versions thereof (Barchi et al., 2019).
Recently, there have been attempts to develop representations that allow finer-grain program rea- soning. Many, however, are limited both by how inputs are represented as well as how inputs are processed. Representations based on source code and its direct artifacts (c.g.. AST) (Alon et al., 2018a; Yin al., 2018: Haj-Ali et al., 2020) put unnecessary emphasis on naming and stylistic choices that may not correlate with the functionality of the code (e.g., Fig. 2a). Approaches based on intermediate representations (IR) (Ben-Nun et al., 2018; Mirhoseini et al., 2017: Brauckmann et al., 2020) remove such noise but fail to capture information about the program that is important for analysis (e.g., Fig. 2b variables, Fig. 2c commutativity). In both cases, models are expected to reason about the flow of information in programs using representations that do not directly en- code this information. Clearly, a program representation is needed that enables machine learning algorithms to reason about the execution of program by developing its data flow analyses.

---

Under review as a conference paper at ICLR 2021
Compller
Intermediate Representation
Optimization
Output Exocutable
Input Program
Passes
Message Passing
Representatiin
Neural Networks
Figure 1: Our proposed approach for compiler analyses driven by graph-based deep learning.
Since current approaches are ill-suited to program-wide data flow analysis, we propose overcoming their limitations by making the program's control, data, and call dependencies central part of the program's representation and a primary consideration when processing it. We achieve this by graph in which individual statements are connected other statements
seeing the program through relational dependencies. Each statement in the program understood only in the context of the statements interacting with it. Through relational reasoning (Battaglia al., 2018), latent representation of each statement is learned that is function of not just the statement itself, but also of the (latent) representations of its graph neighborhood. Notably, this formulation has a striking similarity to the IRs used by compilers, and the iterative propagation of information resembles the transfer functions and meet operators in traditional data flow analyses (Kildall, 1973).
Recently proposed techniques for learning over graphs have shown promise in a number of do- mains (Schlichtkrull al.. 2018: Ziwei al., 2020). With a suitable representation and graph-based model, we extend these approaches to the domain of compiler analysis, enabling downstream tasks built on top of such graph models to natively incorporate reasoning about data flow into their decision making. This improves performance on downstream tasks without requiring additional features.
We make the following contributions:
We propose a portable, language-independent graph representation of programs derived from compiler IRs. PROGRAML is the first representation to capture whole-program control-, data-, and call relations between instructions and operands as well as their or- der and data types. PROGRAML is a compilcr-agnostic design for use at all points in the optimization pipeline; we provide implementations for LLVM and XLA IRs.
We introduce a benchmark dataset that poses suite of established compiler analysis tasks as supervised machine learning problems. DEEPDATAFLOW comprises five tasks that re- quire, in combination, the ability to model: control- and data-flow, function boundaries, instruction types, and the type and order of operands over complex programs. DEEP- DATAFLOW is constructed from 461k real-world program IRs covering a diverse range of domains and source languages, totaling 8.5 billion data flow analysis classification labels.
We adapt Gated-Graph Neural Networks (GGNN) to the PROGRAML. representation. We show that, within a bounded problem size, our approach achieves 2 0.939 F, score on all analysis tasks, a significant improvement over state-of-the-ar representations. In evaluat- ing the limits of this approach we propose directions to better learn over programs.
RELATED WORK
Data flow analysis is long established area of work firmly embedded in modern compilers. Despite its central role, there has been limited work in learning such analysis. Bielik et al. (2017) use ASTs and code synthesis learn rule-sets for static analyses, some of which are dataflow-related. Our approach does not require a program generator or a hand-crafted DSI. for rules. Shi et al. (2020) and Wang & Su (2020) use dynamic information (e.g., register snapshots and traces) from instrumented binaries to embed need runtime features. Si et al. (2018) use a graph embedding of an SSA form to generate invariants. The lack of phi nodes and function call/return edges means that the representation is not suitable for interprocedural analysis as it stands. Kanade et al. (2020) explore a large-scale, context-dependen vector embedding. This is done at token level, however, and is unsuited for dataflow analysis.
assembler graph representation. We propose static approach that does not
Prior work on learning over programs employed methods from Natural Language Processing that represented programs as sequence of lexical tokens (Allamanis, 2016; Cummins al., 2017a).
2

---

Under review as a conference paper at ICLR 2021
Fient
factonial
80.88%
else return n -(n-1)
1f to = 4) return
tustRlun
19.16%
8.82%
load
Flint
+ls return n (0e1))
1f & zz 6) return 1;
times
3.89%
x1
x2
int Fibonacei 1)
clse return n fibonacti(n-1));
1f de == e) return
0.75%
fdiv float
Fdiv float
getelementper
(a) code2vec is sensitive to naming over se- mantics.
(b) CDFG omits operands.
(c) XFG cannot distinguish non- commutative statements.
Figure 2: Limitations in state-of-the-art learnable code representations: code2vec (Alon et al., 201 8a), CDFG (Brauckmann et al., 2020), and XFG (Ben-Nun et al., 2018).
However, source-level representations are not suited for analyzing partially optimized compiler IRs as the input source cannot be recovered. In program analysis it is critical to capture the structured nature of programs (Raychev et al., 2015; Allamanis et al., 2017; Alon al., 2018b). Thus, syntac- tic (tree-based) well as semantic (graph-basee) representations have been proposed (Allamanis et al., 2018; Brauckmann et al., 2020). Dam et al. (2018) annotate nodes Abstract Syntax Trees (ASTs) with type information and employ Tree-Based LSTMs (Tai et al., 2015) for program defect prediction. Both Raychev et al. (2015) and Alon et al. (2018a;b) use path- abstractions of the AST as program representations, while Allamanis et al. (2017) augment ASTs with hand-crafted set of additional typed edges and use GGNNs (Li et al., 2015) to learn downstream tasks related variable naming. Another line of research considers modelling binary similarity via control-flow graphs (CFGs) with an adaptation of GNNs called Graph Matching Networks (Li et al., 2019).
The history of IR-based graph representations for optimization goes back to Ferrante et al. (1987), who remove superfluous control-flow edges to case optimization with a compact graph representa- tion. A more contemporary precursor our approach the ConteXtual Flow Graph (XFG) (Ben- Nun et al., 2018), which combines control-flow with data-flow relations in order to learn unsuper- vised embeddings of LLVM-IR statements. XFGs omit information that is critical to analysis in- cluding the notion of argument order, vertices for both variables and constants, and all control-flow edges. PROGR MMI, in combining call-graphs (CG), control-flow graphs, and data-flow graphs (DFG), offers IR-level program representation that is designed to be useful for variety of pur- poses from specific program analyses to downstream optimization tasks. Control and Data Flow Graphs (CDFG) (Brauckmann al., 2020) graph vertices for statements and have bi-directional edges for control and data dependencies. The CDFG uses only the instruction opcode to represent statement, omitting operands, variables, data types, and constants. This prohibits the reasoning about variables and expressions that are required for many data flow analyses, including 3 out of the benchmark tasks that we establish below. Mendis et al. (2019) represent LLVM-IR using graph that is specialized to a vectorization task. They use unique edge types to differentiate the first five operand positions and augment the graph structure with vectorization opportunities that they com- pute a priori. Our approach is not specialized to task, enabling such opportunities learned (e.g., subexpression detection), and uses embedding weighting to differentiate edge positions without having to learn separate edge transfer weights for each. Finally, an alternate approach is taken by IR2Vec (Keerthy S et al., 2019), an LLLMM-IR-specin statements as relations. However, in order to compute the values of the embeddings, IR2Vec requires access to the type of data flow analyses that our approach learns from data alone.
representation that elegantly models part-of-
A GRAPHICAL REPRESENTATION FOR DEEP PROGRAM ANALYSIS
This section presents PROGRAMI, novel IR-based program representation that closely matches the data structures used traditionally in inter-procedural data flow analysis and can be processed na- tively by deep learning models. We represent programs as directed multigraphs where instructions, variables, and constants are vertices, and relations between vertices are edges. Edges are typed to differentiate control-, data-, and call-flow. Additionally, augment edges with local posi- tion attribute to encode the order of operands to instructions, and to differentiate between divergent branches in control-flow.
3

---

Under review as a conference paper at ICLR 2021
Int Fibćint x)
define 132 WPib(132) en
Loxcornal
switchh (x)
snitch 132 sa, lubel 53
case
132 6, 1abel t9
reture 0;
132 1, label
defaulti:
return
-1abe1>:2:
br Tabel
br
phs
add
return Fib 13
<label>:3:
14 new 132
tall 132 eFinc132 54)
udd
Input
tail wrinciaz 16)
call
E1, 523,
IR
(a) The input program is passed through the compiler front-end to produce an IR. In this ex- ample, LLVM-IR is used.
(b) full-flow graph is constructed of instruc- tions control dependencies. All edges have position attributes: for clarity, we have omitted position labels where not required.
Textemnl3)
Cexternll
sai tcn
phi
ret
20:
(c) Vertices added for data elements (ellipti- are variables, diamonds are constants). Data edges capture use/def relations. 1.32 indi- cates 32 hit signed integers. Numbers on edges indicate operand positions.
(d) Functions have single entry instruction and zero or more instructions. Call edges are in- serted from sites to function entry instruc- tions, and returneedess from function exits to call sites.
Figure 3: PROGRAML construction from a Fibonacci implementation using LLVM-IR.
We construct PROGRAML graph G (V) by traversing compiler IR. An initially empty graph G is populated in three stages: control-flow, data-flow, and call-flow, shown Figure 3. In practice the three stages of graph construction can be combined in single O(VV (E]) pass.
(I) Control Flow We construct the full-flow graph of an IR by inserting a vertex for each instruc- tion and connecting control-flow edges (Fig. 3a. 3b). Control edges are augmented with numeric position using an ascending sequence based on their order in the list of an instruction's 's successors.
(II) Data Flow We introduce constant values and variables as graph vertices (Fig. 3c). Data- flow edges inserted to capture the relation from constants and variables the instructions that use them as operands, and from instructions to produced variables. As each unique variable and constant is vertex, variables can be distinguished by their scope, and unlike the source-level rep- resentations of prior works, variables different scopes map to distinct vertices and can thus be discerned. Data edges have position attribute that encodes the order of operands for instructions. The latent representation of a statement (e.g., , $1 add i32 80, 1) is thus function of the vertex representing the instruction and the vertices of any operand variables or constants, modulated by their order in the list of operands.
(III) Call Flow Call edges capture the relation between an instruction that calls a function and the entry instruction of the called function (Fig. 3d). Return call edges are added from each of the terminal instructions of a function to the calling statement. Control edges do not span functions, such that an IR with functions F produces |F] disconnected subgraphs (the same is not true for data edges which may cross function boundaries, e.g., in the case of a global constant which is used across many parts of program). For IRs that support external linkage, additional vertex is
4

---

Under review as a conference paper at ICLR 2021
created representing an external call site and connected all externaly visible functions. If a call site references a function not defined in the current IR, a dummy function is created consisting of a single instruction vertex and connected through call edges to all call sites in the current IR. A unique dummy function is created for each externally defined function.
GRAPH-BASED MACHINE LEARNING FOR PROGRAM ANALYSIS
We formulate our system in a Message Passing Neural Network (MPNN) framework (Gilmer et al., 2017). Our design mimics the transfer functions and meet operators of classical iterative data flow analysis (Kam & Ullman, 1977; Cooper et al., 2004), replacing the rulc-based implementations with learnable analogues (message and update functions). This single unified model can be specialized through training to solve diverse set of problems without human intervention or algorithm design.
The PROGRAML model is an adaptation GGNN (Li al., 2015) that takes as imput an attributed directed multigraph as presented in Section 3. It consists of three logical phases: input encoding, message propagation and update, and result readout.
(I) Input Encoding Starting from the augmented graph representation G = (V, E), we capture the semantics of the program graph vertices by mapping every instruction, constant, and variable vertex v E V to vector representation Λ. E Rd by lookup in fixed-size embedding table. The mapping from vertex learnable embedding vector f :: - h2 must be defined for each IR.
For LLVM-IR, we construct an embedding key from each vertex using the name of the instruction, e.g., store, and the data type for variables and constants, e.g., 132* (a pointer to 32-bit integer). In this manner we derive the set of unique embedding keys using the graph vertices of training set of LLVM-IRs described Section 5.1. This defines the embedding table used for training and deployment. An unknown element embedding is used during deployment map embedding keys which were not observed in the training data. Since composite types make the size of the vocabulary unbounded in principle, our data-driven approach trades certain amount of semantic resolution against good coverage of the vocabulary by the available datasets (cf. Table ??). The embedding vectors trained jointly with the rest of the model.
(II) Message Propagation Each iteration step is divided into message propagation followed by vertex state update. Receiving messages M (h--1 ewo) are a function of neighboring states and the respective edge. Messages are mean-aggregated over the neighborhood after transformation with custom posttien-augmented transfer function that scales hw elementwise with a position-gatiin -aating vector p(ewa):
Mh ewv) W Waypetew.)) (Nw- O p(ewe)) Deype(ew.))
The position-ge position-gating p(ewe) 2W, emb(ew)) + 6p) is implemented as sigmoid-activater linear layer mapping from constant sinusoidal position embedding (Vaswani et al., 2017: Gehring et al., 2017). It enables the network to distinguish non-commutative operations such division, and the branch type in diverging control-flow. In order to allow for reverse- proppagtooonntioonn of information, which necessary for backward compiler analyses, we add backward edges for each edge in the graph as separate edge-types. In all our experiments, we employ Gated Recurrent Units (GRU) (Cho al., 2014) as our update function.
Step (II) is iterated 7 times to extract vertex representations that are contextualized with respect to the given graph structure.
(III) Result Readout Data flow analyses compute value sets composed of instructions or vari- ables. We support per-instruction and per-variable classification tasks using readout head top of the iterated feature extraction, mapping, for each vertex, the extracted vertex features h to prob- abilities R2 (h²)" bg):
R. (h M (.) (f(N g(h")
where f(-) and g()) are linear layers and ((-) is the sigmoid activation function.
5

---

Under review as a conference paper at ICLR 2021
(a) REACHABILITY
(b) DOMINANCE
(c) DATADEP
(d) LIVENESS
(e) SUBEXPRESSIONS
Figure 4: Example input-output graphs for each of the five DEEPDATAFLOW tasks. A single ver- tex randomly selected from the input graph as the starting point for computing analysis results, indicated using the vertex selector (blue node). Each vertex in the output graph is annotated with binary value after the analysis has completed. As a supervised classification task, the goal is to pre- diet the output vertex labels given input graph. These small graphs are for illustrative purposes, the average DEEPDATAFLLOW graph contains 581 vertices and 1,051 edges.
DATA FLOW EXPERIMENTS
Data flow analysis is the heart of modern compiler technology. We pose suite of data flow analyses as supervised learning tasks to benchmark the representational power of machine learning approaches. We selected a diverse set of tasks that capture a mixture of both forward and backward analyses, and control-, data-, and procedure-sensitiy analyses. Full details of the analyses are provided in Appendix A. These particular data flow analyses can already be perfectly solved by non- ML techniques. Here, we use them to benchmark the capabilities of machine learning techniques.
5.1 THE DEEPDATAFLOW DATASET
We assembled a 256M-line corpus of LLVM-IR files from a variety of sources and produced labeled datasets using five traditional data flow analyses: control reachability, dominators, data dependen- cies, liveness, and subexpressions. Each of the 15.4M analysis examples consists of an input graph in which a single vertex annotated as the root node for analysis, and an output graph in which each vertex is annotated with a binary label corresponding sis has completed (Fig. 4). A 3:1:1 ratio used to divide the examples for the five problems into training, validation, and test instances. For further details see Appendix B.
its value once the data flow analy-
5.2 MODELS
We evaluate the effectiveness of our approach against two contrasting kate-of-theeart approaches for learning over programs: one sequential model and one other graph model.
(I) Sequential Model inst2vec (Ben-Nun al., 2018) sequentially processes the IR statements of a program to perform whole-program classification. An IR is tokenized and then mapped into a sequence of pre-trained 200 dimensional embedding vectors which are processed by an LSTM. The final state of the LSTM is fed through a two-layer fully connected neural network to produce classification the full sequence. We extend this approach by concatenating to the input sequence one-hot loken-selector to indicate the starting point for analysis. Then, we feed the LSTM state through a fully connected layer after every token, producing a prediction for each instruction of the IR. We the same model parameters in the original work.
(II) Graph Models CDFG (Brauckmann al.. 2020), and PROGRAML. For both approaches we use 32 dimensional embeddings initialized randomly, as in Brauckmann et al. (2020). Input veriex-selectors, encoded as binary one-hot vectors, are used to mark the starting point for analyses and are concatenated to the initial embeddings. For CDFG, For PROGRAML, we derive the vocabulary from the training set.
We use the model design outlined in Section 4 with two input representations:
the vocabulary described in Brauckmann et al. (2020).
Message Passing Neural Networks typically use small number of propagation steps out of practi- cal consideration for time and space efficiency (Gilmer et al., 2017: Brauckmann et al., 2020). In contrast, data flow analyses iterate until fixed point is reached. In this work iterate for fixed number of message passing steps and exclude from the training and validation sets graphs for which traditional implementation of the analysis task requires greater than T' iterations solve.

---

Under review as a conference paper at ICLR 2021
Vocabulary Size
Vocabulary Test Coverage
1.0
inst2vec
8,565
34.0 0%
Reschaiillyy
Liveness
PROGRAML
CDPG
2,230
75
98.3%
47.5%
02
Dombree
Sibbespressoos
Datader
10
10*
8. training graphs (log)
Table I: Vocabularies for LLVM-IR
Figure 5: F1 score on a 10k-graph validation set function of the number of training graphs.
We set T = 30 for training in all experiments and trained a model per task. Once trained, we eval- uate model inference using different T values accommodate programs which required greater number of steps to compute the ground truth. See Appendix C.2 for training details.
5.3
EVALUATION
First, we evaluate the effectiveness of each vocabulary representing unseen programs. Then we evaluate model performance on increasingly large subsets of the DEEPDATAFLOw (DDF) test sets.
Vocabulary Coverage Each of the three approaches uses vocabulary produce embeddings that describe the instructions and operands of a program. inst2vec uses a vocabulary of 8,565 LLVM-IR instruction and its operands) with identifiers and literals stripped.
statements (where a statement CDFG uses the 75 LLVM instruction opcodes. For PROGRAML we derive a vocabulary on a set of training graphs that represents instructions and data types separately. Table compares the coverage of these vocabularies as a percentage of the vertices in the test graphs that can be described using that vocabulary. PROGRAM ML provides 2.1 the coverage on unseen programs state-of-the-an approaches, the best of which can represent fewer than half of the graph vertices of unseen programs.
DDF-30: Testing on Limited Problem Size We initially limit our testing to the subset of each task's ' test set which can be solved using a traditional analysis implementation in S 30 steps, denoted DDF-30. This matches the T = 30 message passing iterations used in computing the graph models' final states to ensure that a learned model, if has successfully approximated the mechanism of an analysis, has sufficient message passing iterations to solve each test input. Table summarizes the performance of inst2vec, CDFG, and PROGRAML.
The relational representation of our approach shows excellent performance across all of the tasks. CDFG, which also captures control-flow, achieves comparable performance on the REACHABILITY and DOMINANCE tasks. However, the lack of operand vertices, positional edges, and data types renders poor performance on the SUBEXPRESSIONS task. Neither the CDFG or inst2vec represen- tations enable per-variable classification, so are incapable of the DATADEP and LIVENESS tasks. To simplify comparison, we exclude these two tasks from inst2vec and CDFG aggregate scores, In spite of this, PROGRAML correctly labels 4.50x and 1.12x more nodes than the state-of-the-art approaches. The weakest PROGRAML performance is on the LIVENESS task. When model per- formance considered as a function of the number of training graphs, shown Figure 5, we see that the performance of PROGRAML. quickly converges towards near-perfect P1 scores on a holdout validation set for all tasks except LIVENESS, where the model is still improving at the end of train- ing. This suggests estimating the transfer (message) and meet (update) operators of this backwards analysis poses a greater challenge for the network, and may benefit from further training.
DDF-60: Generalizing to Larger Problems The DDF-30 set excludes 28.7% of DEEP- DATAFLOW graphs which require more than steps to compute ground truth labels. To test whether these learned models can generalize to solve larger problems, we used the models we trained at T 30 but double the number of inference message passing steps to T 60 and repeated the tests all graphs which require < 60 analysis steps (excluding 19.6%). The results of this exper- iment, denoted DDF-60, are shown in Table 2. We observe that performance consistent on this larger problem set, demonstrating that PROGRAML models can generalize problems larger than those they were trained on. The results indicate that an approximate fixed- -oint algorithm is learned by the model, critical feature for enabling practical machine learning over programs.

---

Under review as a conference paper at ICLR 2021
Table 2: Data flow analysis results. For the restricted subset DDF-30 PROGRAML obtains strong results. Results on the full dataset (DDF) highlight the scalability challenges of MPNNs.
Analysis
Example Optimization
iner2vec DDF-30
CDFG
PROGRAMI. DDF-60
DDF-30
DDF-30
DDF
Reachability
Dead Code
Precision
0.105
1,000
0.998
0,997
0.996
Elimination
Recall
0.007
0.996
0.998
0,998
0.917
0,998
0,998
0,997
Dominance
Global Code Motion
Precision
0.999
1.000
0,983
Recall
0.002
1,000
1.000
1,000
0,950
Fi 0.004
0.999
1.000
0.991
0.123
DataDep
Instruction Scheduling
Precision
0.998
0.992
0.987
Recall
0.997
0,996
0.949
0,997
0,993
Liveness
Register Allocation
Precision
0,962
0,931
Recall
0.916
0,955
0,925
Fi
0.937
0.939
0.625
Subexpressions
Glohal Common Subexpreasion Elimination
Precision
0.000
0.139
0.997
0.954
0.938
Recall
0.000
0.005
0.996
0,999
0.992
0.009
0.996
0.967
0.959
DDF: Scalability Challenges Finally, we test the analysis models that were trained for 7 = 30 message passing iterations on all DEEPDATAFLOW graphs, shown in Table 2 as DDF, We use = 200 inference message passing iterations test the limits of stability and generalization of current graph neural networks. 9.6% DDF graphs require more than 200 steps to compute. Therefore, this experiment highlights two of the challenges in the formulation of data flow analysis in MPNN framework:
first, that using a fixed number of message passing iterations across each and every edge leads to unnecessary work for problems that be solved in fewer iterations by propagating only along a dynamic subset of the edges at each timestep (the maximum number of steps required by graph in DDF is 28,727). Secondly, models that compute correct results for graph when processed for an appropriate number of steps may prove unstable when processed for an excessively large number of steps. In Table we see substantial degradations of model performance in line with these two challenges. DOMINANCE and LIVENESS show reductions in precision as the models over-approximate and have a large number of false positives. REACHABILITY and DATADEP, in contrast, show drops in recall as the fixed T = 200 iterations is insufficient to propagate the signal to the edges of large problems. MPNNs do not scale the way that we should like for large programs. A part of this, believe, is that using a generic MPNN system is wasteful. Ordinary data flow engines process nodes in a particular order (usually reverse post order) and are naturally able to identify that fixed point has been reached. We believe that Jynamically-sparae message passing strategies and an adaptive number of iterations could address these scalability challenges.
DOWNSTREAM TASKS
In the previous section we focus on data flow analysis as benchmark for the capabilities of machine learning for compiler analysis. For the analyses considered, non-ML techniques achieve perfect scores. In this section we apply PROGRAML to two downstream data flow tasks for which non-ML techniques fail: predicting heterogeneous compute device mappings and algorithm classification. In both domains PROGRAML outperforms prior graph-based and aaquence-based representations, reducing test error by 1.20x and 1.35 respectively. Finally, we ablate every component of our representation and summarize the contribution of each.
Table Predicting heterogeneous compute device mapping.
AMD
NVIDIA
Error [%]
Precision
Recall
Error [%]
Precision
Recall
Static Mapping
41.2
0.35
0.59
43.1
0.32
.57
DeepTune
28.1
0.72
0.72
39.0
0.69
0.61
DeepTuneeR
26.2
0.76
0.74
31.6
0.70
0.68
inst2vec
19.7
0.81
0.80
21.5
0.79
0.79
PROGRAML
13.4
0.89
0.87
20.0
0.81
0.80
8

---

Under review as a conference paper at ICLR 2021
Table 4: Algorithm classification comparison to state-of-the-art, and ablations.
(a) Comparison to state-of of-the-rrt.
(b) PROGRAML ablations.
Error [%]
Relative [%]]
Error [%]
Relative [%]
TBCNN
6.00
+77.5
No vocab
3.70
+9.5
NCC
5.17
+53.0
inst2vee vocab
3.78
+11.8
XFG inst2vec vocab
4.56
+34.9
No control edges
3.88
+14.8
XFG
4.29
+26.9
No data edges
7.76
+129.6
PROGRAML
3.38
No call edges
3.88
+14.8
No backward edges
4.16
+23.1
No edge positions
3.43
+1.5
6.1 HETEROGENEOL'S DEVICE MAPPING
We apply our methodology to the challenging domain of heterogeneous compute device mapping. Given an OpenCL kernel and a choice of two devices to run it on (CPU or GPU), the task to predict the device which will provide the best performance. This problem has received significant prior attention, with previous approaches using both hand-engineered features (Grewe et al., 2013) and sequential models (Cummins al., 2017a; Ben-Nun et al., 2018). We use the OPENCI. DEVMAP dataset (Cummins et al., 2017a), which provides 680 labeled CPU/GPU instances derived from 256 OpenCL kernels sourced from seven benchmark suites on two combinations of CPU/GPU hardware, AMD and NVIDIA. cf. Appendix D.1 for details.
The performance of PROGRAML and baseline models is shown in Table As can be seen, PRO- GRAML outperforms prior works. We set new state-of-the-asd F1 scores of 0.88 and 0.80.
6.2 ALGORITIIM CLASSIFICATION
We apply our approach to the task of classifying algorithms from unlabeled implementations. We use the Mou et al. (2016) dataset. It contains implementations of 104 different algorithms that were submitted to a judge system. All samples were written by students in higher education. There are around 500 samples per algorithm. We compile them with different combinations of optimization flags to generate a dataset of overall 240k samples, as in Ben-Nun et al. (2018). Approximately 10,000 files are held out each development and test sets. of. Appendix D.2 for details.
Table 4a compares the test error of our method against prior works.
Ablation Studies We ablate the PROGRAML. representation in Table 4b. Every component of our representation contributes positively to performance. We note that structure alone (No vocab) is sufficient outperform prior work, suggesting that algorithm classification is problem that lends itself especially well to judging the power of the representation structure, since most algorithms are well-defined independent of implementation details, such as data types. However, the choice of vo- cabulary is important. Replacing the PROGRAML vocabulary with that of a prior approach (inst2vec vocab) degrades performance. The greatest contribution the performance of PROGRAML on this task is data flow edges. Backward edges, which are required for reasoning about backward data flow analyses, provide the second greatest contribution. These results highlight the importance of data flow analysis for improving program reasoning through machine learning.
7 CONCLUSIONS
The evolution of ML for compilers requires more expressive representations. We show that current techniques cannot reason about simple data flows which are at the core of all compilers. We present PROGRAML. a graph-based representation for programs derived from compiler IRs that accurately captures the semantics of a program's 's statements and the relations between them. We are releasing the DEEPDATAFLOW dataset as a community benchmark for evaluating approaches to learning over programs. PROGRAML and DEEPDATAFLOw open up new directions for research towards more flexible and useful program analysis. PROGRAML outperforms the state-of-the- art, but is limited by scalability issues imposed by MPNNs. As future work, we will investigate how MPNNs could be improved learn efficient and stable fixed-point algorithms, regardless of input graph size.

---

Under review as a conference paper at ICLR 2021
REFERENCES
M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, Levenberg, Monga, Moore, D. G. Murray, B. Steiner, Tucker,
V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng. TensorFlow: A System for Large-scale
Machine Learning. OSDI, 2016.
M. Allamanis. Learning Natural Coding Conventions. PhD) thesis, University of Edinburgh, 2016.
M. Allamanis, M. Brockschmidt, and M. Khademi. Learning to Represent Programs with Graphs. In ICLR, 2017.
M. Allamanis, E. T. Barr, P. Devanbu, and C. Sutton. A Survey of Machine Learning for Big Code and Naturalness. CSUR, 51(4), 2018.
U. Alon, M. Zilberstein, O. Levy, and E. Yahav. code2vec: Learning Distributed Representations of Code. In POPL. 2018a.
U. Alon, M. Zilberstein, O. Levy, and E. Yahav. A General Path-Based Representation for Predicting Program Properties. In PLDI. ACM, 201 8b.
A. H. Ashouri, W. Killian, J. Cavazos, G. Palermo, and C. Silvano. A Survey Compiler Autotun- ing using Machine Learning. CSUR, 51(5), 2018.
D. H. Bailey, E. Barszez, J. Barton, D. Browning, R. Carter, L. Dagum, R. Fatoohi, S. Fineberg, P. Frederickson, T. Lasinski, R. Schreiber, H. Simon, V. Venkatakrishnan, and S. Weeratunga. The NAS Parallel Benchmarks. IJHPCA, 5(3), 1991.
F. Barchi, G. Urgese, E. Macii, and A. Acquaviva. Code Mapping in Heterogencous Platforms Using Deep Learning and LLVM-IR, In DAC. ACM, 2019.
Battaglia, J. Hamrick, V. Bapst, A. Sanzhez-Gonzalez, Zambaldi, M. Malinowski, A. Tac- chetti, D. Raposo, A. Santoro, R. Faulkner, C. Gulcehre, F. Song, A. Ballard, J. Gilmer, G. Dahl, A. Vaswani, K. Allen, C. Nash, V. Langston, Dyer, N. Heess, D. Wierstra, P. Kohli, M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu. Relational Inductive Biases, Deep Learning, and Graph Networks. arXiv::806. 012.0,16111111 2018.
T. Ben-Nun, A. S. Jakobovits, and T. Hoefler. Neural Code Comprehension: A Learnable Represen- tation of Code Semantics. In NeurlPS, 2018.
Bielik, V. Raychev, and M. Vechev. Learning Static Analyzer from Data. In CAV, 2017.
Blazy, D. Demange, and D. Pichardie. Validating Dominator Trees for Fast, Verified Dominance Test. In ITP, 2015.
A. Brauckmann, S. Ertel, A. Goens, and J. Castrillon. Compiler-Basedl Based Graph Representations for Deep Learning Models Code. CC, 2020.
K. Cho, B. van Merrienboer, C. Gulcchre, D. Bahdanau, Bougares, H. Schwenk, and Y. Bengio. Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Transla- tion. In EMNLP, 2014.
K. D. Cooper and L.. Torczon. Engineering Compiler. Flsevier, 2012.
K. D. Cooper, T. J. Harvey, and K. Kennedy. Iterative Data-flow Analysis, Revisited. Technical report, Department of Computer Science, Rice University, 2004.
C. Cummins, Petoumenos, Z. Wang, and Leather. End-to-end Deep Learning of Optimization Heuristics. In PACT. IEEE, 2017a.
C. Cummins, P. Petoumenos, W. Zang, and H. Leather. Synthesizing Benchmarks for Predictive Modeling. CGO. IEEE, 2017b.
H. K. Dam, J. Grundy, T. Kim, and C. Kim. A Deep Model for Software Defect Predic- tion. arXiv: /802.00922 2018.
10

---

Convolutional Sequence to Se- Under review as a conference paper at ICLR 2021
J. Ferrante, K. J. Ottenstein, and J. D. Warren. The Program Dependence Graph and Its Use in Optimization. TOPLAS, 9(3), 1987.
J. Gehring, M. Auli, D. Grangier, D. Yarats, and Y. N. Dauphin. quence Learning. ICML. PMLR, 2017.
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural Message Passing for Quantum Chemistry. In ICML. PMLR, 2017.
D. Grewe, Z. Wang, and M. F. P. O' O'Boyle. Portable Mapping of Data Parallel Programs to OpenCL. for Heterogeneous Systems. In CGO. IEEE, 2013.
A. Haj-Ali, N. Ahmed, T. Willke, Shao, K. Asanovic, and Stoica. Neuro End-to- End Vectorization with Deep Reinforcement Learning. CGO, 2020.
G. Hinton, Srivastava, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Improving Neural Networks by Preventing Co-adaptation of Feature Detectors. arXiv:/207.0580, 2012.
S. loffe and C. Szegedy. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. In JCML. PMLR, 2015.
J. B. Kam and J. D. Ullman. Global Data Flow Analysis and Iterative Algorithms. JACM, 1976.
B. Kam and J. Ullman. Monotone Data Flow Analysis Frameworks. Acta Informatica, 7(3), 1977.
A. Kanade, P. Maniatis, G. Balakrishnan, and K. Shi. Learning and Evaluating Contextual Embed- ding of Source Code. In ICML, 2020.
V. Keerthy S, R. Aggarwal, S. Jain, M. S. Desarkar, R. Upadrasta, and Y. N. Spkant. IR2Vec: A Flow Analysis based Scalable Infrastructure for Program Encodings. arXiv:1909.06222 2019.
G. A. KildalI. A Unified Approach to Global Program Optimization. In POPL, 1973.
D. Kingma and J. L. Ba. Adam: Method for Stochastic Optimization. ICLR, 2015.
Lengauer and E. Tarjan. Fast Algorithm for Finding Dominators in Flow Graph. TOPLAS, 1(1), 1979.
L. Li, C. Gu, Dullien, O. Vinyals, and P. Kohli. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. In ICML. PMLR, 2019.
Y. Li, R. Zemel, M. Brocksemidt, and D. Tarlow. Gated Graph Sequence Neural Networks. 1:Xiv:55/1.5444 2015.
I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In ICLR, 2019.
C. Mendis, C. Yang, Y. Pu, Amarasinghe, and Michael. Compiler anto-vectorization with imitation learning, 2019.
A. Mirhoseini, H. Pham, Q. Le, B. Steiner, R. Larsen, Y. Zhou, N. Kumar, M. Norouzi. S. Bengio, and J. Dean. Device Placement Optimization with Reinforcement Learning, In ICML, 2017.
L. Mou, G. Li. L. Zhang, T. Wang, and Z. Jin. Convolutional Neural Networks over Tree Structures for Programming Language Processing. AAAI, 2016.
V. Raychev, M. Vechev, and A. Krause. Predicting Program Properties from "Big Code". In POPI., 2015.
M. Schlichtkrull, T. N. Kipf, P. Bloem, R. van den Berg, I. Titov, and M. Welling. Modeling Relational Data with Graph Convolutional Networks. In ESWC, 2018.
Z. Shi, K. Swersky, D. Tarlow, Ranganathan, and M. Hashemi. Learning Execution through Neural Code Fusion. In ICLR, 2020.
11

---

Under review as a conference paper at ICLR 2021
X. Si. H. Dai, M. Raghothaman, M. Naik, and L. Song. Learning Loop Invariants for Program Verification. In NeurlPS, 2018.
K. S. Tai, R. Socher, and C. D. Manning. Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks. arXiv:/503.0000 000300075, 2015.
A. Vaswani, N. Shazeer, N. Parmar, Uszkoreit, Jones, N. Gomez, L. Kaiser, and Polo- sukhin. Attention Is All You Need. In NIPS, 2017.
K. Wang and Z. Su. Blended, precise semantic program embeddings. In PLDI, 2020.
Z. Wang and M. O'Boyle. Machine learning in Compiler Optimization. Proceedings of the IEEE, 106(23), 2018.
P. Yin, G. Neubig, M. Allamanis, M. Brockschmidt, and A. L. Gaunt. Learning to Represent Edits. arXiv:1810.13337. 2018.
Ziwei, P. Cui, and W. Zhu, Deep Learning on Graphs: Survey. TKDE, 2020.
12

---

Under review as a conference paper at ICLR 2021
A DATA FLOW DEFINITIONS
This section provides the definitions of the five analysis tasks used in this paper to evaluate the representational power of deep learning over programs. We chose diverse set of analysis tasks to capture a mixture of both forward and backward analyses, and control-, data-, and procedure- sensitive analyses.
(I) REACHABILITY: Reachable Instructions Control reachability is fundamental compiler analysis which determines the set of points in program that can be reached from a particular starting point. Given succ(n), which returns the control successors of an instruction the set of reachable instructions starting at root n can found using forward analysis:
Reachable(n) {n}
U pεsuco(n)
Reachable(p)
(3)
MII) DOMINANCE: Instruction Dominance Instruction dominates statement if every control-foor path the from the program entry to passes through n. Like reachability, this anal- ysis only requires propagation of control-flow, but unlike reachability, the set of dominator instruc- tions are typically constructed through analysis of program's 's reverse control-flow graph (Lengauer & Tarjan, 1979; Blazy et al., 2015):
Dom(n) [n)
n
Dom(p)
pEpred(n)
Where (n) returns the control predecessors of instruction We formulate the DOMINANCE problem as: Given a root instruction vertex n, label all vertices m where n E Dom(m).
(III) DATADEP: Data Dependencies The data dependencies of variable is the of pre- decessor instructions that must be evaluated to produce v. Computing data dependencies requires traversing the reverse data-flow graph:
DataDep(n) defs(n) U
U
DataDep(p)
(5)
pEdefs(m)
Where defs(n) returns the instructions that produce the operands of n.
(IV) LIVENESS Live-out variables A variable live-out of statement if there exists some path from to statement that uses without redefining it. Given uses(n), which returns the operand variables of n, and defs(n), which returns defined variables, the live-out variables can be computed forwards using:
LiveOut(n))
U uses(s) U (LiveOut(s)) - defs(s)) (n)
(6)
(V) Global Common Subexpressions The identification of common subexpressions is an impor- tant analysis for optimization. For compiler IRs we define a subexpression as an instruction and its operands, ordered by either their position (for non-commutative operations), or lexicographically (for commutative operations). We thus formulate the common subexpression problem as: Given an instruction (which forms part of a subexpression), label any other instructions in the program which compute the same subexpression. This is an proce-rroe analysis, though operands must obey their scope. Common subexpressions typically identified using available expression analysis:
Avail(n) = uses(n) U
n pEpres((n)
Avail(p)
defs(n)
Where uses(n) return the expressions used by instruction n, and defs(n) returns the expressions defined by n.
13

---

Under review as a conference paper at ICLR 2021
Table 5: The DEEPDATAFLOW LLVM-IR corpus.
Language
Domain
IR files
IR lines
BLAS 3.8.0
Fortran
Scientific Computing
300
345,613
GitHub
Various
38,109
74,230,264
OpenCL Swift
5,224
9,772,858
4,386
1.586.161
Linux 4.19
Operating Systems
13,418
41,904,310
NPB (Bailey al., 1991)
C
Benchmarks
122
255,626
Cummins et al. (2017a)
OpenCL
Benchmarks
256
149,779
OpenCV 3.4.0
C++
Computer Vision
432
2,275,466
POJ-104 (Mou et al., 2016)
C++
Standard Algorithms
397,032
104,762,024
Tensorflow (Abadi al., 2016)
C++
Machine learning
1,903
18,152,361
Total
461,182
256,434,462
Table 6: Characterization of DEEPDATAFLOW subsets.
DDF-30
DDF-60
DDF-200
DDF
Max. data flow step count classification labels
30
60
200
28,727
6,038,709,880
6,758.353,737
7,638,510,145
8.623,030,254
#. graphs (3:1:1 train/val/test) Ratio of full test set
10,951,533
12,354,299
13,872,294
15,359,619
71.3%
80.4%
90.3%
100%
B DREPDATAFLOOW DATASET
The DEEPDATAFLOW dataset comprises: 461k LLVM-IR files assembled from a range of sources, PROGRAML representations each of the IRs, and 15.4M sets of labeled graphs for the five data flow analyses described in the previous section, totaling 8.5B classification labels.
Programs We assembled 256M-line corpus of real-world LLVM-IRs from variety of sources, summarized in Table 5. We selected popular open source software projects that cover a diverse range of domains and disciplines, augmented by uncategorized code mined from popular GitHub projects using the methodology described by Cummins al. (2017b). Our corpus comprises five source languages (C, C++, Fortran, OpenCL, and Swift) covering a range of domains from functional to imperative, high-level to accelerators. The software covers broad range of disciplines from com- pilers and operating systems traditional benchmarks, machine learning systems, and unclassified code downloaded from popular open source repositories.
PROGRAML Graphs We implemented PROGRAML construction an 11vm: :ModulePass. using LLVM version 10.0.0 and generated a graph representation of each of the LLVM-IRs. PRO- GRAML construction takes average of 10.72ms per file. Our corpus of unlabeled graphs totals 268M vertices and 485M edges, with an average of 581 vertices and 1,051 edges per graph. The maximum edge position is 355 (a large swit statement found in a TensorFlow compute kernel).
Data Flow Labels We produced labeled graph instances from the unlabeled corpus by computing ground truth labels for each of the analysis tasks descrihed in Section A using traditional analysis implementation. For each of the five tasks, and for every unlaheled graph in the corpus, produce labeled graphs by selecting unique source vertices vo E V, where n is proportional to the size of the graph:
[ 10
n = min
10
(8)
Each example in the dataset consists of an input graph in which the source vertex is indicated using the vertex selector. and an output graph with the ground truth labels used for training or for evaluat- ing the accuracy of model predictions. For every example steps that the iterative analysis required to compute the labels. use this value to produce subsets of the dataset test problems of different sizes, shown in Table 6.
produce, we also record the number of
14

---

Under review as a conference paper at ICLR 2021
X15 load 132, 132x Xnian, align 4, Iebaa 11
LLVM-IR
Xrent1 sremi 132 815, 190
Tokenized
5000 vocabulary indi
Embeddings
5000 200 inst2vec enbeddings
Auxiliary Inputs
nur nur_segnents "selector" vector
Model inputs 5006 (200-2) concatenated
LSTM
LSTM
Fully-connected
Model outputs
nun_segments
hot outputs
130 parans
Figure 6: Extending inst2vec (Ben-Nun et al., 2018) to perform per-instruction classification of LLVM-IR. The operator denotes vector concatenation.
We divided the datasets randomly using 3:1:1 ratio for training, validation, and test instances. The same random allocation of instances was used for each of the five tasks. Where multiple examples were derived from single IR, examples derived from the same IR were allocated to the same split.
As binary classification tasks, data flow analyses display strong class imbalances as only a small fraction of program graph is typically relevant to computing the result set of analysis. On the DDF test sets, an accuracy of 86.92% can be achieved by always predicting the negative class. For this reason report only binary precision, recall, and F1 scores with respect to the positive class when reporting model performance on DEEPDATAFLLOW tasks.
C DATA FLOW EXPERIMENTS: SUPPLEMENTARY DETAILS
This section provides additional details for the experiments presented in Section 5.
C.I
MODELS
(I) Sequential Model The inst2vec model consists of 619,650 trainable parameters in the configu- ration outlined in Figure 6. The model, implemented in TensorFlow, uses the same parameters as in the original work: 2x 64 dimensional LSTM layers followed by 64 dimensional dense layer and the final 2 dimensional output layer. Sequences are padded and truncated to 5k tokens and processed in batches of 64.
(II) Graph Models For CDFG and PROGRAML approaches we use the same model architecture. The model, implemented in PyTorch, consists of a customized GGNN with 87,0 $7,070 trainable pa- rameters. Batches are implemented as disconnected graphs that constructed to enable efficient processing of graphs of differing size in parallel without padding. We use a combined batch size of 10, 000 vertices. If single graph contains more than 10, 000 vertices, is processed its
15

---

Under review as a conference paper at ICLR 2021
Table 7: Average training and inference times on DDF-30 tasks
Train time
Test time
Train time/graph
Val time/graph
Test time/graph
inst2vec CDFG
10h52m
1h33m
45ms
3ms
36ms
13h14m
3h27m
64ms
ms
62ms
PROGRAML
7m21m
1h39m
26ms
3ms
24ms
C.2 EXPERIMENTAL SETUP
Training Details and Parameters All models were trained in an end-to-end fashion with the Adam optimizer (Kingma & Ba, 2015) using the default configuration and a learning rate of 1- 10-3 for the LSTMs and 2.5 10 for the GGNNs. We trained the models on 1M training graphs, evaluating on a fixed 10k validation set at 10k intervals for the first 50k training graphs, and at 100k intervals thereafter. The checkpoint with the greatest validation F1 score is used for testing.
Runtimes All experiments conducted shared machines equipped with an NVIDIA GTX 1080 32GB of RAM, mechanical hard drives, and server-grade Intel Xeon processors. Figure provides measurements of the average runtimes of each approach across the five DDF-30 tasks. In our implementation, we find training and testing to be I/O bound as programs are processed faster than loading many small files from disk. particular, CDFG performance suffers relative to PROGRAML as the conversion from PROGRAML to CDFG representations is performed on- demand. For validation, inputs are loaded once into system memory and re-used, so the measured time provides more accurate estimate of processing requirements.
D DOWNSTREAM TASKS: SUPPLEMENTARY DETAILS
This section provides additional details for the experiments present in Section
D.1 HETEROGENEOUS COMPUTE DEVICE MAPPING
Datasets The OPENCL DEVMAP dataset comprises 256 OpenCL. kernels from two combinations of CPU/GPU pairs. The AMD set NVIDIA set uses an Intel Core i7-3820 CPU and an NVIDIA GTX 970 GPU. Each dataset consists of 680 labeled examples derived from the 256 unique kernels by varying dynamic inputs.
Intel Core i7-3820 CPU and AMD Tahiti 7970 GPU; the
Models We compare PROGRAML with four approaches: First, with static baseline that selects the most-frequently optimal device for each dataset (CPU for AMD, GPU for NVIDIA). Second, with DeepTunee (Cummins et al., 2017a), which is sequential LSTM model the OpenCL source level. Third, to isolate the impact of transitioning from OpenCL source to LLVM-IR, we eval- uate against a DeepTuneeR model, which adapts Deep'Tune using tokenized sequences of LLVM-IR as input instead of OpenCL. tokens. Finally, we compare against the state-of-the-at ap- proach inst2vec (Ben-Nun et al., 2018), which replaces the OpenCL tokenizer with a sequence of 200-dimensional embeddings, pre-trained on a large corpus of LLVM-IR using a skip-gram model. PROGRAML itself uses the GGNN adaptation as described in the paper. We adapted the readout head to produce single classification label for each graph, rather than per-vertex classifications, by aggregating over the final iterated vertex states. We also included the available auxiliary input features of the DEVMAP dataset. The auxiliary features are concatenated to the features extracted by the GGNN before classification following the methodology of Cummins et al. (2017a).
The experimental results in this section come from an earlier development iteration of PROGRAML which deviates from the method described in the main paper in the way in which it produces initial vertex embeddings. Instead of deriving textual representation of instructions and data types to pro- duce a vocabulary, the vocabulary used for the DEVMAP experiment that of inst2vec (Ben-Nun al., 2018), where variables and constants all represented by single additional embedding tor. The poor vocabulary coverage achieved by using inst2vec motivated us to provide the improved vocabulary implementation that we describe in the main paper (see Table 1).
16

---

Under review as a conference paper at ICLR 2021
Training Details and Parameters All neural networks are regularized with dropout (Hinton et al., 2012) for generalization and Batch Normalization (loffe & Szegedy, 2015) in order to be uniformly applicable to vastly different scales of auxiliary input features. We used 10-fold cross-validatii with rotating 80/10/10 splits by training on 80% of the data and selecting the model with the highest validation accuracy, setting aside 1/ 1/10th of the training data to use for validation. We trained each model for 300 epochs and selected the epoch with the greatest validation accuracy for testing. Base- line models were trained with hyperparameters from the original works, For the PROGRAML results we used 6 layers in the GGNN corresponding to 6 timesteps of message propagation, while sharing parameters between even and odd layers introduce additional regularization of the weights. We ran sweep of basic hyperparameters which led us to use the pre-trained inst2vec statement em- beddings (Ben-Nun et al., 2018) and to exclude the use of position representations, Both of these hyperparameter choices help generalization by reducing the complexity of the model. This is not surprising in light of the fact that the dataset only contains 680 samples derived from 256 unique pro- grams. PROGRAML was trained with the Adam optimizer with default parameters, learning rate of 10-3 and a batch size of 18,000 nodes (resulting in ca. 12000 iteration steps of the optimizer). For the PROGRAMI. result, repeat the automated sweep for all hyperparameter configurations and picked the configuration with the best average validation performance. Performance on the unseen tenth of the data is reported.
D.2 ALGORITHM CLASSIFICATION
Dataset We use the POJ-104 dataset (Mou et al., 2016). It contains implementations of 104 dif- ferent algorithms that were submitted to a judge system. All programs were written by students in higher education. The dataset has around 500 samples per algorithm. We compile them with differ- ent combinations of optimization flags to generate a dataset of overall 240k samples, as in Ben-Nun et al. (2018). Approximately 10,000 files are held out each as a development and test set.
Models We compare with tree-based convolutional neural networks (TBCNN) (Mou et al., 2016) and inst2vec (Ben-Nun al., 2018). We used author-provided parameters for the baseline models. For PROGRAML we used 4 layers in the GGNN corresponding to 8 timesteps. To further test the expressive power of the graph-based representation against the tree-based (TBCNN) and sequential (inst2vec) prior work, we additionally compare against graph-based baselines based on XFG (Ben- Nun et al., 2018).
To better understand the qualitative aspects of replacing graph-based representation that captures program semantics like Contextual Flow Graphs (XFG) (Ben-Nun et al., 2018) with the more com- plete PROGRAML representation, we adapted a GGNN (Li et al., 2015) to directly predict algo- rithm classes from XFG representations of the programs. In contrast to this, Ben-Nun et al. (2018) used XFG only to generate statement contexts for in skip gram pre-training Here, we lift this graphical representation and make accessible to a deep neural network directly, as opposed to the structure-less sequential approach in the original work (inst2vec).
Training Details and Parameters All models were trained with the AdamW (Loshchilov & Hut- ter, 2019) optimizer with learning rate 2.5 10-4, , 0.9, 32 0.999, & 10- for 80 epochs. Dropout regularization is employed on the graph states with a rate of 0.2.
17


Reviews:
[{"review_id": "yf7IFdNwoJ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------------\nA methodology for learning representations of programs using graph neural networks applied to graphs extracted from a compiler intermediate representation is presented. The graph representation captures both control flow as well as data dependencies and also represents calls to/returns from functions. A large new dataset to evaluate if models can learn to perform dataflow analyses is introduced, and experimental results show that the described method can be trained to perform these with high accuracy (at least for small programs). Further experiments in the appendix illustrate that the proposed graph structure is also useful for more standard tasks that cannot be solved well using existing algorithms.\n\nStrong/Weak Points\n-------------\n* (+) The graph representation is novel and well-explained.\n* (+) The experimental results on data-flow tasks show that the representation and model are clearly able to capture important facts about programs.\n* (-) I'm surprised by the lack of \"real\" tasks in the main text of the paper, as it means that the main experiments are not on well-studied tasks. To be honest, I'd prefer just swapping the DDF-60/DDF results + discussion with one of the tasks from appendix D.\n* (-) I found the experimental details a bit hard to follow, for example, it remains unclear to me if the models are trained on all tasks together at the same time, or if they are trained separately for each task.\n\nRecommendation\n-------------\nI think this is nice work, but that the paper could still be significantly improved by reporting more details and potential new experiments. It passes the bar for acceptance as-is, but could be substantially more useful to other researchers if more experiments are described.\n\nQuestions\n-------------\n* While the appendix gives statistics about how many programs in the corpus come from different source languages, it remains unclear if the source language has an influence on the success of the method. Did you analyse the model results by language?\n* See above - it wasn't clear to me if one model is trained for each data flow task, or if one model is trained for all of them (with different heads). If the former, why not the latter? If the latter, how does it compare with results of the former?\n* Following on this line of thought: Did you evaluate if using the dataflow tasks as a pretraining routine for your model makes sense? I'm envisioning a scenario if you take the fully trained model for the data flow tasks and re-head it for the algorithm classification / placement tasks. \n\nDetail Feedback\n-------------\n* page 3: \"prohibt\" -> \"prohibit\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "sxtfn8SF4T", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary:\n\nThe paper proposes a new program representation to find semantic code embeddings (ProGraML). The authors use these embeddings to perform a number of traditional dataflow analysis tasks that you can find in modern day compilers. When trained under a supervised learning setting, Deep Data Flow (DDF) analysis learns to perform these tasks more accurately compared to other deep program representations.\n\n## Strengths:\n\n* Position-gate mapping to distinguish between positional arguments, branch directions etc.\n* Impressive scale of the dataset collected that require considerable engineering work.\n* Evaluation on a number of classic dataflow analysis tasks from compiler literature.\n\n## Weaknesses and Questions for authors:\n\n### Novelty and missing related work\n* The authors claim that ProGaML is the first to use operand order and data types to come up with an embedding for whole-programs targeting a compiler IR. Important related work is missing. For instance in [1], Mendis et. al. learn a program embedding for a program optimization task that explicitly models operand order and data types for whole functions at the LLVM IR level. [2] uses both dynamic and symbolic information to arrive at a program embedding that captures program semantics. Wang and Su use this embedding to perform the algorithm classification task.\n\n### Scalability and Usability\n* How fast is DDF compared to traditional dataflow analysis? If DDF is far slower, then its usability may be limited inside a traditional compiler, especially if traditional dataflow analysis gives more precise results.\n* What is the largest graph in the dataset and how long does a typical DDF task take on that graph for T=30? What is the comparative time (wall-clock) for traditional dataflow analysis?\n* Did you see any improvement of precision over traditional dataflow analysis when using fewer propagation steps? For example, say traditional  dataflow analysis takes T=2000 steps to reach a fixed point. Can DDF outperform traditional dataflow analysis at T=30 or at a similar step?\n* Did you try reusing any embedding trained on one task (task1) as a pre-trained embedding for another task (task2)? If yes, what are the results?  Do the embeddings generalize with minimal finetuning?\n\n### Correctness Guarantees\n* I did not see any discussion about guarantees of correctness of DDF. Will there be any violations? For example can there be false reaching definitions. In other terms is DDF sound? I assume F1 score is only measuring preciseness of the analysis in your case. If not, please explain, how exactly you compute them.\n\n[1] Mendis et. al. Compiler auto-vectorization with imitation learning. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019)\n\n[2] Ke Wang and Zhendong Su. 2020. Blended, precise semantic program embeddings. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation(PLDI 2020)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "i2gP2a01xnU", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis work proposes a new program representation called ProGRamL, which is suitable to be used as an input for graph-based machine learning techniques, and which can be used to learn compiler heuristics.  By formulating several problems with graph neural networks, authors evaluate ProGRamL’s ability to represent problems for classic compiler dataflow problems.\n\nStrengths:\n* Advances state of the art for representations of programs for ML\n* New benchmark dataset for program representation\n* Well written, clear paper\n\nWeaknesses:\n* Could be viewed as modest tweaks to existing representations.\n* Models are sensitive to the number of iterations, indicating they are perhaps not learning the same functions as in the exact algorithm\n\nComments:\n\nOverall I enjoyed reading this paper and I would be in favor of acceptance.  I very much appreciate the insight that GNNs can essentially learn classic dataflow operators, provided that you can run the GNN for more number of iterations (that seems to be true to some extent, barring caveats provided by the authors).  The representation seems substantially more compute while still being suited for machine learning.  The techniques for connecting this with graph neural networks are also valuable.  The benchmark dataset is appreciated and can be useful for future studies.  The case studies on downstream tasks are also a nice addition that proves this exercise is not purely academic.  \n\nOne thing to mention is that there does seem to be quite a large abstraction gap between the problems that ProGRamL is designed for (computing low-level node properties), and where it can actually be useful (where we need heuristics due to complex interactions like the algorithm classification and performance prediction).  In that sense, one wonders whether being able to compute dataflow properties is a novelty, or whether it has led to some new innovations that are useful in developing heuristics.  Either way, I think this work is still interesting, pushes the state of the art, and will ultimately provide value for future compiler developers.\n\nI also think it would be nice if the authors can provide more information about the limitations of the representation, and describe when it could conceivably introduce errors/approximations.\n\nQuestions:\n* One problem with the existing approach is that it is not stable to the number of iterations.  Do you foresee this as a sensitive parameter in downstream tasks?\n\n\n* Does the representation capture commutativity in operations which are commutative?  (also, does the operand order on the switch really matter?)\n\n* Why does CDFG have such poor vocabulary coverage?\n\n* What’s the reasoning behind using a dummy function to represent an external unavailable function?  Why not a new node type?  Could it be confounding to the analysis to assume a call to an empty function?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "g9FkwxBxhFH", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Changes after author response\nThanks for addressing the concerns in the review with the new revision. I am revising the score to 7 from 5 based on the reply and the revisions to the paper.\n\n---\n# Summary\nThis paper describes a directed graph representation for programs and a graph neural network architecture that can operate on these graphs to create per-vertex features and support per-instruction or per-variable classification tasks. The authors collect a dataset of programs from the web and convert them into the graph format for an empirical evaluation. The paper provides the results of an empirical evaluation using this dataset on several classical dataflow analysis tasks, like graph reachability and variable liveness.\n\n# Strengths\n- The graph representation builds upon the work done in LLVM to analyze and simplify programs. This approach contrasts with other previous works that use source code-based representations, and allows the learning portion to build upon a more convenient representation without needing to learn how to duplicate the same kinds of transformations performed by LLVM.\n- The empirical results show that the proposed representation and learning method can work better than baseline methods.\n\n# Weaknesses\n- Although the method is compared to prior work, there is no ablation of the neural network architecture or details of the graph representation (except for one experiment in the appendix), which would allow us to evaluate the contributions of different parts in a more controlled manner.\n- The representation used is not particularly novel, since it can be straightforwardly constructed from LLVM IR.\n- The tasks considered have existing exact hand-written solutions, so it is not clear how the methods proposed on the paper can have practical impact.\n\n# Recommendation\nOverall, I thought that the approach of leveraging LLVM IR makes a lot of sense, as well as preserving and effectively communicating its structure by using a graph neural architecture. However, it was strange to me that the focus of the empirical evaluation is on dataflow analysis tasks like computing reachability, when these tasks have well-known solutions (in fact, written as one equation each in the appendix). It is good to know that the proposed method can perform these tasks, but that has no direct practical implications since there are already good solutions for these tasks. These empirical results do not assure us that the method will perform well on other, more interesting tasks, either.\nI see that there are downstream tasks evaluated in the appendix. I would recommend reorganizing the paper to make these results more prominent, and making sure to compare with the latest work in a fair way. It would also be exciting to see how the paper's methods can be used to other tasks relevant for compilers, such as code optimization-related tasks which would be amenable to a reinforcement learning approach. I would be willing to revise the paper's rating given sufficient revision.\n\n# Questions\n- Was there any deduplication performed in the data collection process, to ensure that the same files, functions, or other large snippets would not be present in both the train and test sets? The same file might have been copied into multiple GitHub repositories, for example.\n- Why are all external functions references assigned to the same dummy function? That seems to prevent distinguishing between different standard library functions effectively, for example.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "HMarpmv-kw", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a language-independent, compiler-agnostic graph representation of programs (ProGraML) designed for machine learning.  Their representation is noteworthy for including the program's control, data, and call dependencies, and more generally for including enough information for standard dataflow analyses to be possible in principle.  Their goal is to train machine learning systems on this representation to provide heuristics to replace manual heuristic-engineering inside compilers.  The authors introduce a large benchmark dataset that poses several established compiler analysis tasks as supervised learning problems, and show that thanks to their well-designed program representation, established network architectures (i.e. Gated Graph Neural Networks) perform well on all analysis tasks.  Perhaps more importantly though only a side note in the text, they show that GGNNs on ProGraML outperform prior approaches on two downstream tasks for which non-ML techniques are not perfect: device mappings and algorithm classification.\n\nI think the paper addresses an important problem, makes a valuable contribution, and could be of broad interest to the community.  Thus I recommend that it be accepted. However, I have lingering reservations about their approach that I hope the authors will consider.  In the 'Heterogeneous Compute Device Mapping' experiment, the message passing is only iterated 6 times, compared to 30 for all dataflow analysis tasks, suggesting that---contra what seems to be implied by the paper---the network's ability to perform such dataflow analyses when T is large might not be a relevant factor in its strong performance on the downstream task.  I am unable to find in the paper the number of rounds used for the algorithm classification experiment.\n\nI think the paper could be strengthened by putting more emphasis on downstream tasks and by addressing the null hypothesis that the network is not doing anything like dataflow analysis for them.  This hypothesis might be addressed by plotting performance as a function of the number of message passing rounds; if performance continues to increase as T is increased, it would constitute some evidence it is using some analogue of dataflow analysis, while if performance peaks or plateaus at a small T, it would constitute some evidence that it is not.  Whether or not it is performing its own dataflow analysis, a second null hypothesis might be that the network could be even better if it simply saw the precomputed dataflow analyses as additional inputs. That is, standard analyses may suffice, and it may not be necessary to give the network the freedom to invent its own analyses.  Needless to say, just because GNNs can recapitulate standard dataflow analyses does not necessarily mean that they should need to recapitulate these analyses, particularly since (a) they are not 100% accurate and (b) they are wasteful and difficult to scale (as discussed in 'DDF: Scalability Challenges').\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
After reading the paper, reviews and authors’ feedback. The meta-reviewer agrees with the reviewers that the paper presented a very interesting idea and empirical studies.  R3 rightfully pointed out the need to clarify relation to related works, as well as the scalability issue.

Notably, because the analysis does not ensure correctness, it has limited applicability in tasks where absolution correctness are required(e.g. Dead code), but can benefit downstream tasks that do not require absolute correctness. A more thorough discussion about this perspective would strengthen the paper. 

Right now the paper is borderline, the meta-reviewer acknowledges the pros of the paper as mentioned in the reviews, but also thinks the paper can be further improved based on the comment. Therefore the meta-reviewer decided to not accept the paper but would encourage the authors to improve the paper per comments for a future submission.

Thank you for submitting the paper to ICLR. 

Decision: Reject