This article introduces a combinatorial optimization approach to register allocation and instruction scheduling, two central compiler problems. Combinatorial optimization has the potential to solve these problems optimally and to exploit processor-specific features readily. Our approach is the first to leverage this potential in practice : it captures the complete set of program transformations used in state-of-the-art compilers, scales to medium-sized functions of up to 1,000 instructions, and generates executable code. This level of practicality is reached by using constraint programming, a particularly suitable combinatorial optimization technique. Unison, the implementation of our approach, is open source, used in industry, and integrated with the LLVM toolchain. An extensive evaluation confirms that Unison generates better code than LLVM while scaling to medium-sized functions. The evaluation uses systematically selected benchmarks from MediaBench and SPEC CPU2006 and different processor architectures (Hexagon, ARM, MIPS). Mean estimated speedup ranges from 1.1% to 10% and mean code size reduction ranges from 1.3% to 3.8% for the different architectures. A significant part of this improvement is due to the integrated nature of the approach. Executing the generated code on Hexagon confirms that the estimated speedup results in actual speedup. Given a fixed time limit, Unison solves optimally functions of up to 946 instructions, nearly an order of magnitude larger than previous approaches. The results show that our combinatorial approach can be applied in practice to trade compilation time for code quality beyond the usual compiler optimization levels, identify improvement opportunities in heuristic algorithms, and fully exploit processor-specific features.

In code generation, instruction selection chooses processor instructions to implement a program under compilation where code quality crucially depends on the choice of instructions. Using methods from combinatorial optimization, this paper proposes an expressive model that integrates global instruction selection with global code motion. The model introduces (1) handling of memory computations and function calls, (2) a method for inserting additional jump instructions where necessary, (3) a dependency-based technique to ensure correct combinations of instructions, (4) value reuse to improve code quality, and (5) an objective function that reduces compilation time and increases scalability by exploiting bounding techniques. The approach is demonstrated to be complete and practical, competitive with LLVM, and potentially optimal (w.r.t. the model) for medium-sized functions. The results show that combinatorial optimization for instruction selection is well-suited to exploit the potential of modern processors in embedded systems.

In software validation, regression testing aims to check the absence of regression faults in new releases of a software system. Typically, test cases used in regression testing are executed during a limited amount of time and are selected to check a given set of user requirements. When testing large systems, the number of regression tests grows quickly over the years, and yet the available time slot stays limited. In order to overcome this problem, an approach known as test suite reduction (TSR), has been developed in software engineering to select a smallest subset of test cases, so that each requirement remains covered at least once. However solving the TSR problem is difficult as the underlying optimization problem is NP-hard, but it is also crucial for vendors interested in reducing the time to market of new software releases. In this paper, we address regression testing and TSR with Constraint Programming (CP). More specifically, we propose new CP models to solve TSR that exploit global constraints, namely NVALUE and GCC. We reuse a set of preprocessing rules to reduce a priori each instance, and we introduce a structureaware search heuristic. We evaluated our CP models and proposed improvements against existing approaches, including a simple greedy approach and MINTS, the state-of-theart tool of the software engineering community. Our experiments show that CP outperforms both the greedy approach and MINTS when it is interfaced with MiniSAT, in terms of percentage of reduction and execution time. When MINTS is interfaced with CPLEX, we show that our CP model performs better only on percentage of reduction. Finally, by working closely with validation engineers from Cisco Systems, Norway, we integrated our CP model into an industrial regression testing process.

This paper describes Unison, a simple, flexible, and potentially optimal software tool that performs register allocation and instruction scheduling in integration using combinatorial optimization. The tool can be used as an alternative or as a complement to traditional approaches, which are fast but complex and suboptimal. Unison is most suitable whenever high-quality code is required and longer compilation times can be tolerated (such as in embedded systems or library releases), or the targeted processors are so irregular that traditional compilers fail to generate satisfactory code.

We present DPT: a wireless sensor network protocol for bulk traffic that uniquely leverages electronically switchable directional (ESD) antennas. Bulk traffic is found in several scenarios and supporting protocols based on standard antenna technology abound. ESD antennas may improve performance in these scenarios; for example, by reducing channel contention as the antenna can steer the radiated energy only towards the intended receivers, and by extending the communication range at no additional energy cost. The corresponding protocol support, however, is largely missing. DPT addresses precisely this issue. First, while the network is quiescent, we collect link metrics across all possible antenna configurations. We use this information to formulate a constraint satisfaction problem (CSP) that allows us to find two multi-hop disjoint paths connecting source and sink, along with the corresponding antenna configurations. Domain-specific heuristics we conceive ameliorate the processing demands in solving the CSP, improving scalability. Second, the routing configuration we obtain is injected back into the network. During the actual bulk transfer, the source funnels data through the two paths by quickly alternating between them. Packet forwarding occurs deterministically at every hop. This allows the source to implicitly "clock" the entire pipeline, sparing the need of proactively synchronizing the transmissions across the two paths. Our results, obtained in a real testbed using 802.15.4-compliant radios and custom ESD antennas we built, indicate that DPT approaches the maximum throughput supported by the link layer, peaking at 214 kbit/s in the settings we test.

This paper presents a novel combinatorial model that integrates global register allocation based on ultimate coalescing, spill code optimization, register packing, and multiple register banks with instruction scheduling (including VLIW). The model exploits alternative temporaries that hold the same value as a new concept for ultimate coalescing and spill code optimization.

We provide a filtering algorithm achieving GAC for the conjunction of constraints atleast (b, [x(0),x(1),...,x(n-1)], V) and (a(0)*x(0) +...+ a(n-1)*x(n-1)) <= c, where the atleast constraint enforcesb variables out of x(0), x(1), ..., x(n-1) to be assigned to avalue in the set V. This work was motivated by learning simplepolynomials, i.e. finding the coefficients of polynomialsin several variables from example parameter and function values.We additionally require that coefficients be integers, andthat most coefficients be assigned to zero or integers close to0. These problems occur in the context of learning constraintmodels from sample solutions of different sizes. Experimentswith this more global filtering show an improvement by severalorders of magnitude compared to handling the constraintsin isolation or with cost gcc, while also out-performing a0/1 MIP model of the problem.

Abstract SICStus Prolog has evolved for nearly 25 years. This is an appropriate point in time for revisiting the main language and design decisions, and try to distill some lessons. SICStus Prolog was conceived in a context of multiple, conflicting Prolog dialect camps and a fledgling standardization effort. We reflect on the impact of this effort and role model implementations on our development. After summarizing the development history, we give a guided tour of the system anatomy, exposing some designs that were not published before. We give an overview of our new interactive development environment, and describe a sample of key applications. Finally, we try to identify key good and not so good design decisions.

Wanting to improve execution speed and reduce code size of SICStus Prolog programs, we embarked on a project whose aim was to systematically investigate combination and specialization of WAM instructions. Various variants of the SICStus Prolog virtual machine instruction set were designed, implemented, and their performance was evaluated against standard benchmarks and on big Prolog programs. In this paper, we describe our methodology in finding appropriate candicates for instruction merging and specialization, discuss related trade-offs, present detailed statistics and performance measurements that we gathered, and report on our experiences from our involvement in this feat. In short, our experience is positiv e: the speedup of performing instruction merging and specialization in the context of the SICStus emulator is approximately 10%, while the bytecode size reduction is about 15%.

Since the early days of logic programming, researchers in the field realized the potential for exploitation of parallelism present in the execution of logic programs. Their high-level nature, the presence of nondeterminism, and their referential transparency, among other characteristics, make logic programs interesting candidates for obtaining speedups through parallel execution. At the same time, the fact that the typical applications of logic programming frequently involve irregular computations, make heavy use of dynamic data structures with logical variables, and involve search and speculation, makes the techniques used in the corresponding parallelizing compilers and run-time systems potentially interesting even outside the field. The objective of this article is to provide a comprehensive survey of the issues arising in parallel execution of logic programming languages along with the most relevant approaches explored to date in the field. Focus is mostly given to the challenges emerging from the parallel execution of Prolog programs. The article describes the major techniques used for shared memory implementation of Or-parallelism, And-parallelism, and combinations of the two. We also explore some related issues, such as memory management, compile-time analysis, and execution visualization.