The phase ordering problem, which aims to find suitable pass sequences for a given program on a target architecture, is critical in compiler optimization.One key challenge of this problem lies in the complex interplay among different passes within the vast optimization space of possible pass sequences.To better explore the interplay among passes, this paper proposes a new concept called booster pass chain (BPC), and presents a novel approach that identifies and leverages the BPCs to optimize the code size.Specifically, a BPC is a sequence of passes with positive interplay that, when presented as a whole, may exhibit significant optimization effects for certain programs.We then propose an iterative algorithm to extract BPCs, based on which we build a candidate set of pass sequences.For a given program, we also train a neural network to predict the suitable pass sequences from the candidate set.Experimental evaluations on 16 datasets containing 6,186 programs demonstrate the effectiveness of the proposed approach.That is, the candidate set achieves an average of 9.9% improvement compared to the LLVM -Oz flag in code size reduction, and selecting the top-3 pass sequences using the neural network predictor achieves 6.9% improvement.Our code and results are available at https://github.com/SoftWiser-group/EBPC4CPO.

ABSTRACT Self‐adaptive applications are becoming increasingly attractive, with the ability to smartly understand their runtime environments (or contexts) and deliver adaptive services, for example, location‐aware navigation or resource‐sensitive suggestions. However, due to inherent noises in the process of sensing and interpreting environmental information, there is a growing demand for guarding the consistency of collected contexts to avoid application misbehaviour and, at the same time, minimize extra costs. Existing work attempted to achieve this by speeding up the kernel constraint checking module inside the consistency guarding process. Most of these efforts were spent on reusing previous checking results or parallelizing the checking process, but they all leave one central step of constraint checking, that is, link generation, untouched. In this step, the checking engine provides reasons to explain the violation of constraints under check. It occupies a substantial part of the total time cost. Focusing on this key link generation step, we proposed MG, which deploys a rigourous analysis to automatically identify and avoid redundancy in the link generation without harming any correctness of the checking results. MG has been proven sound (always guaranteeing correctness) and complete (entirely removing redundancy). Moreover, based on our observation that MG's redundancy elimination also assists another core step of constraint checking to reduce unnecessary computation further, we additionally enhance MG with an escape‐condition optimization to escape unnecessary evaluation of truth values to further improve the efficiency of constraint checking in an aspect other than link generation. We call it MG+ for distinguishing. Our experiments with synthesized and real‐world consistency constraints reported that, compared with existing work, MG eliminates all link redundancy (83% to 0%), and based on it, MG+ further reduces significant truth value calculations (e.g., 49.74% reduction when combined with ECC and Con‐C). Generally, MG brought 14–500 speed‐ups in link generation, and MG+ further made 1.2–1.9 speed‐ups in truth value evaluation. Altogether, MG reduced the total constraint checking time up to 45.4%, and MG+ reduced it up to 61.0%.

API plays an important role in modern software development. Automatic API recommendation has been studied for years to facilitate developers' learning process of APIs. Previous approaches mainly use statistical models and collab-orative filtering (CF) techniques to mine API usage patterns for recommendation. Despite the encouraging results, they still struggle to obtain the accurate embeddings of the client methods and called APIs. Prior studies generally formulate the process of API call interactions as undirected graph structure, neglecting the order in which the API invocations appear, thus fail to seize the rich relationship and complex transitions of API calls. To transcend the limitations, we propose a novel method, namely PARO, to predict the next API invocations using gated graph neural networks (GGNNs). In our proposed method, the API call sequences are modeled as directed graphs, thus the GNN models prone to capture features such as the partial order and complex transitions between API invocations. Besides, we also learn the text attribute representations of API invocations and client methods through word embedding, which further corroborates the semantic and lexical similarities between them. We conduct experimental evaluations on a large number of Java projects extracted from Github and Maven Central. Results show that our approach outperforms the state-of-the-art by a large margin, in terms of Hit@N and MRR@N.

Treating programs as graphs and employing graph learning techniques to analyze them have been widely adopted in many software engineering tasks. A recent progress in this vein is to apply graph neural networks (GNNs) to model program graphs, which is built upon the homophily assumption, i.e., similar nodes tend to connect each other. However, this assumption is not always valid in program graphs, as various edges such as AST edges and token occurrence edges may connect dissimilar nodes with quite different properties. Such phenomenon is termed as the heterophily of program graphs. In this paper, we propose a new heterophily-aware graph convolutional network (HAGCN) to better handle the heterophilic program graphs. Specifically, we first introduce the subtraction operation into the message passing mechanism of GNNs, which allows HAGCN to push apart dissimilar nodes in the representation space. Then, HAGCN separately encodes each type of edges, and uses a global relation-aware attention mechanism to fuse messages from different edge types. Moreover, we also theoretically analyze the expressive power of HAGCN from the perspective of convolution filters and contrast the differences between HAGCN and other GNNs. Finally, we take type inference as an example to evaluate the effectiveness of the proposed approach. Experimental results demonstrate that HAGCN significantly outperforms the existing non-heterophilic competitors, as well as the existing state-of-the-art graph-based type inference approaches.

Nowadays applications are getting increasingly attractive by being capable of adapting their behaviors based on their understanding to running environments (a.k.a. contexts). However, such capability can be subject to illness or even unexpected crash, when contexts, for suffering environmental noises, become inaccurate or even conflict with each other. Fortunately, various constraint checking techniques have been proposed to validate contexts against consistency constraints, in order to guard context consistency for applications in a timely manner. However, with the growth of environmental dynamics and context volume, it is getting more and more challenging to check context consistency in time. In this paper, we propose a novel approach, INFuse, to soundly fuse together two lines of techniques, namely, incremental checking and concurrent checking, for efficient constraint checking. Realizing such check fusion has to address the challenges rising from the gap between the micro analysis for reusable elements in incremental checking and the macro collection of parallel tasks in concurrent checking. INFuse solves the challenges by automatically deciding maximal concurrent boundaries for context changes under checking (i.e., what-correctness problem), and soundly fusing incremental and concurrent checking for context consistency (i.e., how-correctness problem), with theoretical guarantees. Our experimental evaluation with real-world data shows that INFuse could improve constraint checking efficiency by 18.6x–171.1x, as compared with existing state-of-the-art techniques.

Adaptive applications rely on conditions about their environments (or contexts) to deliver smart services, e.g., location-aware services. Due to inherent noises in environmental sensing and interpretation, there is an increasing demand for guarding the consistency of contexts to avoid application misbehavior, and at the same time minimizing the guarding cost. Existing work has tried to reduce the cost by speeding up the kernel constraint checking module inside the consistency guarding process. Most efforts have been spent on reusing previous checking results or checking constraints in parallel, while leaving untouched one central problem of link generation, the step that consumes a substantially large part of the total time cost for explaining why constraints have been violated. In this paper, we propose a novel technique, MG, to automatically identify and remove redundant link generation, without harming any checking result. We show that MG is sound (always checking correctly) and complete (removing all redundancy). Our experiments with synthesized and real-world consistency constraints reported that compared with existing work, MG achieved significant efficiency improvements on the link generation (tens to hundreds times speedup), and could reduce the total constraint checking time up to 45.4%.