Alias analysis is a fundamental compiler analysis that powers numerous optimizations. While research has focused on deriving more precise alias information assuming that the compiler will optimize better, recent work shows a negligible, or even negative, performance impact of alias information. In this work, we shift the perspective from refining to relaxing alias information, i.e. , removing information, to complement existing work and challenge that assumption systematically. Our study on a state-of-the-art compiler, LLVM, running the SPEC CPU 2017 benchmark suite, shows (1) a small overall impact —removing alias analysis entirely has little impact on the final binaries, (2) few influential queries —only a small fraction, namely ∼3%, of the alias information leads to changes in the final binary, and (3) lost potential —random relaxations can reduce execution time by 21% and binary size by 39% for certain cases, suggesting that compilers could better utilize alias information. Through this work, we advocate that it is beneficial for future research to avoid simply refining the general precision of alias analysis, but also to explore how to find and refine the most relevant queries, and how to more effectively utilize alias information.

We introduce a novel approach for testing optimizing compilers with code from real-world applications The main idea is to construct well-formed programs by fusing multiple code snippets from various realworld projects. The key insight is backed by the fact that the large volume of real-world code exercises rich syntactical and semantic language features, which current engineering-intensive approaches like random program generators are hard to fully support. To construct well-formed programs from real-world code our approach works by (1) extracting real-world code at the granularity of function, (2) injecting function calls into seed programs, and (3) leveraging dynamic execution information to maintain the semantics and build complex data dependencies between injected functions and the seed program. With this idea, our approach complements the existing generators by boosting their expressiveness via fusing real-world code in a semantics-preserving way. We implement our idea in a tool, Creal, to test C compilers. In a nine-month testing period, we have reported 132 bugs to GCC and LLVM, two of the most popular and well-tested C compilers. At the time of writing, 121 of them have been confirmed as unknown bugs, and 101 of them have been fixed. Most of these bugs were miscompilations, and many were recognized as long-latent and critical. Our evaluation results evidently demonstrate the significant advantage of using real-world code to stress-test compilers. We believe this idea will benefit the general compiler testing direction and will be directly applicable to other compilers.

To optimize a program, a compiler needs precise information about it. Significant effort is dedicated to improving the ability of compilers to analyze programs, with the expectation that more information results in better optimization. But this assumption does not always hold: due to unexpected interactions between compiler components and phase ordering issues, sometimes more information leads to worse optimization. This can lead to wasted research and engineering effort whenever compilers cannot efficiently leverage additional information. In this work, we systematically examine the extent to which additional information can be detrimental to compilers. We consider two types of information: dead code, i.e ., whether a program location is unreachable, and value ranges, i.e ., the possible values a variable can take at a specific program location. Given a seed program, we refine it with additional information and check whether this degrades the output. Based on this approach, we develop a fully automated and effective testing method for identifying such issues, and through an extensive evaluation and analysis, we quantify their existence and prevalence in widely used compilers. In particular, we have reported 59 cases in GCC and LLVM, of which 55 have been confirmed or fixed so far, highlighting the practical relevance and value of our findings. This work’s fresh perspective opens up a new direction in understanding and improving compilers.

Inlining is a core transformation in optimizing compilers. It replaces a function call (call site) with the body of the called function (callee). It helps reduce function call overhead and binary size, and more importantly, enables other optimizations. The problem of inlining has been extensively studied, but it is far from being solved; predicting which inlining decisions are beneficial is nontrivial due to interactions with the rest of the compiler pipeline. Previous work has mainly focused on designing heuristics for better inlining decisions and has not investigated optimal inlining, i.e., exhaustively finding the optimal inlining decisions. Optimal inlining is necessary for identifying and exploiting missed opportunities and evaluating the state of the art. This paper fills this gap through an extensive empirical analysis of optimal inlining using the SPEC2017 benchmark suite. Our novel formulation drastically reduces the inlining search space size (from 2349 down to 225) and allows us to exhaustively evaluate all inlining choices on 1,135 SPEC2017 files. We show a significant gap between the state-of-the-art strategy in LLVM and optimal inlining when optimizing for binary size, an important, deterministic metric independent of workload (in contrast to performance, another important metric). Inspired by our analysis, we introduce a simple, effective autotuning strategy for inlining that outperforms the state of the art by 7% on average (and up to 28%) on SPEC2017, 15% on the source code of LLVM itself, and 10% on the source code of SQLite. This work highlights the importance of exploring optimal inlining by providing new, actionable insight and an effective autotuning strategy that is of practical utility.

Compilers are foundational software development tools and incorporate increasingly sophisticated optimizations. Due to their complexity, it is difficult to systematically identify opportunities for improving them. Indeed, the automatic discovery of missed optimizations has been an important and significant challenge. The few existing approaches either cannot accurately pinpoint missed optimizations or target only specific analyses. This paper tackles this challenge by introducing a novel, effective approach that --- in a simple and general manner --- automatically identifies a wide range of missed optimizations. Our core insight is to leverage dead code elimination (DCE) to both analyze how well compilers optimize code and identify missed optimizations: (1) insert "optimization markers" in the basic blocks of a given program, (2) compute the program's live/dead basic blocks using the "optimization markers", and (3) identify missed optimizations from how well compilers eliminate dead blocks. We essentially exploit that, since DCE heavily depends on the rest of the optimization pipeline, through the lens of DCE, one can systematically quantify how well compilers optimize code. We conduct an extensive analysis of GCC and LLVM using our approach, which (1) provides quantitative and qualitative insights regarding their optimization capabilities, and (2) uncovers a diverse set of missed optimizations. Our results also lead to 84 bug reports for GCC and LLVM, of which 62 have already been confirmed or fixed, demonstrating our work's strong practical utility. We expect that the simplicity and generality of our approach will make it widely applicable for understanding compiler performance and finding missed optimizations. This work opens and initiates this promising direction.

A plethora of program analysis and optimization techniques rely on linear programming at their heart. However, such techniques are often considered too slow for production use. While today’s best solvers are optimized for complex problems with thousands of dimensions, linear programming, as used in compilers, is typically applied to small and seemingly trivial problems, but to many instances in a single compilation run. As a result, compilers do not benefit from decades of research on optimizing large-scale linear programming. We design a simplex solver targeted at compilers. A novel theory of transprecision computation applied from individual elements to full data-structures provides the computational foundation. By carefully combining it with optimized representations for small and sparse matrices and specialized small-coefficient algorithms, we (1) reduce memory traffic, (2) exploit wide vectors, and (3) use low-precision arithmetic units effectively. We evaluate our work by embedding our solver into a state-of-the-art integer set library and implement one essential operation, coalescing, on top of our transprecision solver. Our evaluation shows more than an order-of-magnitude speedup on the core simplex pivot operation and a mean speedup of 3.2x (vs. GMP) and 4.6x (vs. IMath) for the optimized coalescing operation. Our results demonstrate that our optimizations exploit the wide SIMD instructions of modern microarchitectures effectively. We expect our work to provide foundations for a future integer set library that uses transprecision arithmetic to accelerate compiler analyses.

Deep learning frameworks automate the deployment, distribution, synchronization, memory allocation, and hardware acceleration of models represented as graphs of computational operators. These operators wrap high-performance libraries such as cuDNN or NNPACK. When the computation does not match any predefined library call, custom operators must be implemented, often at high engineering cost and performance penalty, limiting the pace of innovation. To address this productivity gap, we propose and evaluate: (1) a domain-specific language with a tensor notation close to the mathematics of deep learning; (2) a Just-In-Time optimizing compiler based on the polyhedral framework; (3) carefully coordinated linear optimization and evolutionary algorithms to synthesize high-performance CUDA kernels; (4) the transparent integration of our flow into PyTorch and Caffe2, providing the fully automatic synthesis of high-performance GPU kernels from simple tensor algebra. The performance is comparable to, and often exceeds the performance of, highly tuned libraries.

The pivotal idea of recognizing human aggressive behaviors underlines how a taxonomer models such actions to perform recognition. In this paper, we investigate both the recognition and modeling of aggressive behaviors using kinematic (3-D) and electromyographic performance data. For this purpose, the Gaussian ground-plan projection area model has been assessed as an excellent evolutionary paradigm for the multiclass action and behavior recognition problem. In fact, it has shown superior classification accuracy with and without the use of ensemble models compared with the standard Gaussian (distance and area) models and other metrics of divergence, when dedicated groups of actions (behaviors) are being modeled. Genetic Programming is being employed to construct behavior-based taxonomers with a biomechanical primitive language. The modeling process revealed a representative subset of parameters (limbs, body segments, and marker coordinates) that are selected through the evolutionary process.

In this paper, a survey is being conducted on the investigation of a four-class taxonomy related to security robots that appeared over the past three decades. The survey emphasizes on state-of-the-art mobile technologies that have been developed for crime-fighting robots, capable of crafting critical situations with confrontation strategies. Throughout this investigation, 60 projects are being examined with respect to faculties and sensor apparatus being used. A statistical analysis, which is carried on the historical developments of the most attractive frameworks, reveals the popularity of the four security robot categories and their chronological progress over the past 30 years. The categories being evaluated regard teleoperated, distributed, surveillance, and law-enforcement robot architectures. In the survey, an attempt is made to explain the importance of intelligent methodologies, and their emergent effects in security tasks. The major findings of this analysis illustrate the minor contribution of intelligent architectures in crime-fighting robots, and what constitutes an intelligent security robot.

In this paper, an investigation of evolvable probabilistic classifiers is conducted, along with a thorough comparison between a classical Gaussian distance model, and the induction of Gaussian-to-circle projection model. The newly introduced model refers to a distance fitness measure, based on the projection of Gaussian distributions with geometric circles. The projection architecture aims to model and classify physical aggressive behaviours, by using biomechanical primitives. The primitives are being used to model the dynamics of the aggressive activities, by evolving biomechanical classifiers, which can discriminate between three behaviours and six actions. Both evolutionary models have shown strong discrimination performances on recognising the individual actions of each behaviour. From the comparison, the proposed model outperformed the classical one with three ensemble programs.

A repertory of nine biomechanical aggressive activities is investigated in this paper, in our effort to instigate a new paradigm at aggregating descriptive mathematical models with evolutionary, symbolic program representations. Such representations are based on shared biomechanical primitives inspired from kinematics, dynamics, and energetics. Our intension is twofold, initially to study the nature of aggressive biomechanical models and then to classify their physical activities by evolving expression-trees with biomechanical synthesis. The methodology targets on evolving expression programs using the Gaussian Ground-plan Projection Area model, to discriminate among three aggressive behaviours and recognise the individual actions involved. For the n-class problem, three programs have been evolved, each for an aggressive behaviour such as the arm-Launch, the legLaunch, and the bodyLaunch behaviour, so that to be able to examine separately the evolvable characteristics induced. The proposed approach has evidently shown strong classification and discrimination performances.

Two different classifier representations based on dynamic Artificial Neural Networks (ANNs) and Genetic Programming (GP) are being compared on a human action recognition task by an ubiquitous mobile robot. The classification methodologies used, process time series generated by an indoor ubiquitous 3D tracker which generates spatial points based on 23 reflectable markers attached on a human body. This investigation focuses mainly on class discrimination of normal and aggressive action recognition performed by an architecture which implements an interconnection between an ubiquitous 3D sensory tracker system and a mobile robot to perceive, process, and classify physical human actions. The 3D tracker and the robot are used as a perception-to-action architecture to process physical activities generated by human subjects. Both classifiers process the activity time series to eventually generate surveillance assessment reports by generating evaluation statistics indicating the classification accuracy of the actions recognized.

This paper presents a novel Fuzzy Sarsa(λ) Learning (FSλL) approach applied to a strategic route leaning task of a mobile robot. FSlambdaL is a hybrid architecture that combines reinforcement learning and fuzzy logic control. The Sarsa(λ) learning algorithm is used to tune the rule-base of a fuzzy Logic controller which has been tested in a route learning task. The robot explores its environment using its fixed experience provided by a discretized fuzzy logic controller, and then learns optimal policies to achieve goals in less time and less error.