Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: # Changes after author response
Thanks 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.

---
# Summary
This 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.

# Strengths
- 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.
- The empirical results show that the proposed representation and learning method can work better than baseline methods.

# Weaknesses
- 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.
- The representation used is not particularly novel, since it can be straightforwardly constructed from LLVM IR.
- 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.

# Recommendation
Overall, 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.
I 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.

# Questions
- 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.
- 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.

review_title: Review

final_score: rating: 7: Good paper, accept
review_content: Summary

This 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.

Strengths:
* Advances state of the art for representations of programs for ML
* New benchmark dataset for program representation
* Well written, clear paper

Weaknesses:
* Could be viewed as modest tweaks to existing representations.
* Models are sensitive to the number of iterations, indicating they are perhaps not learning the same functions as in the exact algorithm

Comments:

Overall 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.  

One 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.

I 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.

Questions:
* 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?


* Does the representation capture commutativity in operations which are commutative?  (also, does the operand order on the switch really matter?)

* Why does CDFG have such poor vocabulary coverage?

* 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?


review_title: Novel Program Representation 

final_score: rating: 4: Ok but not good enough - rejection
review_content: ## Summary:

The 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.

## Strengths:

* Position-gate mapping to distinguish between positional arguments, branch directions etc.
* Impressive scale of the dataset collected that require considerable engineering work.
* Evaluation on a number of classic dataflow analysis tasks from compiler literature.

## Weaknesses and Questions for authors:

### Novelty and missing related work
* 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.

### Scalability and Usability
* 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.
* 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?
* 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?
* 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?

### Correctness Guarantees
* 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.

[1] Mendis et. al. Compiler auto-vectorization with imitation learning. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019)

[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)

review_title: Novelty and usability issues

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary
-------------
A 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.

Strong/Weak Points
-------------
* (+) The graph representation is novel and well-explained.
* (+) The experimental results on data-flow tasks show that the representation and model are clearly able to capture important facts about programs.
* (-) 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.
* (-) 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.

Recommendation
-------------
I 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.

Questions
-------------
* 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?
* 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?
* 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. 

Detail Feedback
-------------
* page 3: "prohibt" -> "prohibit"
review_title: Official Blind Review #1

final_score: rating: 7: Good paper, accept
review_content: 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.

I 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.

I 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').

review_title: Valuable contribution, some lingering reservations

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