This article presents the first optimal algorithm for trace scheduling. The trace is a global scheduling region used by compilers to exploit instruction-level parallelism across basic block boundaries. Several heuristic techniques have been proposed for trace scheduling, but the precision of these techniques has not been studied relative to optimality. This article describes a technique for finding provably optimal trace schedules, where optimality is defined in terms of a weighted sum of schedule lengths across all code paths in a trace. The optimal algorithm uses branch-and-bound enumeration to efficiently explore the entire solution space. Experimental evaluation of the algorithm shows that, with a time limit of 1 s per problem, 91% of the hard trace scheduling problems in the SPEC CPU 2006 Integer Benchmarks are solved optimally. For 58% of these hard problems, the optimal schedule is improved compared to that produced by a heuristic scheduler with a geometric mean improvement of 3.2% in weighted schedule length and 18% in compensation code size.

A highly optimized register allocator should provide an efficient placement of save/restore code for procedures that contain calls. This paper presents a new approach to placing callee-saved save and restore instructions that generalizes Chow's shrink-wrapping technique (Chow, 1988). An efficient, profile-guided, hierarchical spill code placement algorithm is used to analyze the structure of a procedure to calculate the minimum dynamic execution count locations to place callee-saved save and restore code. The algorithm is implemented in the Gnu Compiler Collection and has been tested on the SPEC CPU2000 Integer Benchmark suite. Results show that the technique reduces the number of dynamic load and store instructions by 15% compared to saving and restoring at procedure entry and exit while Chow's shrink-wrapping technique reduces dynamic load and store instructions by only 1% compared to saving and restoring at procedure entry and exit. The dynamic number of callee-saved save and restore instructions inserted with this new approach is never greater than the number produced by Chow's shrink-wrapping technique or the placement at procedure entry and exit.

The superblock is a scheduling region which exposes instruction level parallelism beyond the basic block through speculative execution of instructions. In general, scheduling superblocks is an NP-hard optimization and prior work includes both heuristic (polynomial-time) and optimal (enumerative) scheduling techniques. This paper presents a set of transformations to the data-dependency graph which significantly improves the results of heuristic and enumerative superblock scheduling. The graph transformations prune redundant and inferior schedules from the problem solution space. Heuristically scheduling the transformed data-dependency graphs yields significant reduction in expected execution time for hard superblocks. Also, enumeratively scheduling the transformed graphs is faster, and an optimal schedule is found for more problem instances within a bounded time. The transformations are applied to superblocks generated with the GNU compiler collection (GCC) using the SPEC CPU2000 benchmarks targeted to various processor models. The experimental results confirm that the transformations significantly improve the results for heuristic and enumerative superblock scheduling

The superblock is a scheduling region that is used by compilers for exploiting instruction-level parallelism across basic blocks. Many heuristic techniques have been proposed for solving this difficult scheduling problem, but none accurately approximates the optimal solution. This paper presents a new technique that finds provably optimal solutions to superblock scheduling problems. The technique is based on reducing the problem of finding branch combinations that yield incrementally increasing weighted execution times to a subset-sum problem, which is solved by dynamic programming. An enumerative approach that employs a number of powerful pruning techniques to efficiently explore the solution space is then used to search for a feasible schedule for each branch combination. Experimental evaluation using the SPEC CPU fp2000 and int2000 benchmarks shows that, within a per-problem time limit of one second, this combination of dynamic programming and enumeration optimally solves about 99% of the hard superblock scheduling problems with an average solution time of 9 milliseconds per problem. For 80% of the hard problems, the optimal schedule is improved compared to the schedule produced by an established heuristic technique.

Recently researchers have proposed modeling register allocation as an integer linear programming (IP) problem and solving it optimally for general purpose processors and for dedicated embedded systems. Compared with traditional graph-coloring approaches, the IP-based allocators can improve a program's performance. However the solution times are much slower This paper presents an IP-based optimal register allocator which is much faster than previous work. We present several local and global reduction techniques to identify locations in a program's control-flow graph where spill decisions and register deallocation decisions are unnecessary for optimal register allocation. We propose a hierarchical reduction approach to efficiently remove the corresponding redundant decisions and constraints from the IP model. This allocator is built into the Gnu C Compiler and is evaluated experimentally using the SPEC92INT benchmarks. The results show that the improved IP model is much simpler The number of constraints produced is almost linear with the function size. The optimal allocation time is much faster with a speedup factor of about 150 for hard allocation problems.

This paper presents a new approach to local instruction scheduling based on integer programming that produces optimal instruction schedules in a reasonable time, even for very large basic blocks. The new approach first uses a set of graph transformations to simplify the data-dependency graph while preserving the optimality of the final schedule. The simplified graph results in a simplified integer program which can be solved much faster. A new integer-programming formulation is then applied to the simplified graph. Various techniques are used to simplify the formulation, resulting in fewer integer-program variables, fewer integer-program constraints and fewer terms in some of the remaining constraints, thus reducing integer-program solution time. The new formulation also uses certain adaptively added constraints (cuts) to reduce solution time. The proposed optimal instruction scheduler is built within the Gnu Compiler Collection (GCC) and is evaluated experimentally using the SPEC95 floating point benchmarks. Although optimal scheduling for the target processor is considered intractable, all of the benchmarks' basic blocks are optimally scheduled, including blocks with up to 1000 instructions, while total compile time increases by only 14%.

This paper proposes a precise approach to register allocation for irregular-register architectures which is based on 0-1 integer programming (IP). Prior work shows that IP register allocation is feasible for RISC architectures, which have uniform registers and register usage. Extensions to the prior work are proposed that precisely model register irregularities including combined source/destination specifiers, memory operands, and variations in the cost of register usage. The x86 architecture is selected as a representative irregular-register architecture for experimental study. An IP register allocator is built for the x86 architecture within the Gnu C Compiler (GCC), and is compared experimentally with GCC's graph-coloring register allocator. Experimental results show that the IP allocator reduces register allocation overhead by 61% compared with the graph coloring allocator. The results also show that the x86 IP allocator is dramatically faster than the prior RISC IP allocator; because of the smaller number of registers in the x86 architecture and because of the register irregularities. These results suggest that IP register allocation is well suited for irregular-register architectures.

A new approach allows low-cost concurrent detection of two important types of faults, software and hardware data-access faults, using an extension of the existing signature monitoring approach. The proposed approach detects data-access faults using a new type of redundant data structure that contains an embedded signature. Low-cast fault detection is achieved using simple architecture support and compiler support that exploit natural redundancies in the data structures, in the instruction set architecture, and in the data-access mechanism. The software data-access faults that the approach can detect include faults that have been shown to cause a high percentage of system failures. Hardware data-access faults that occur in all levels of the data-memory hierarchy are also detectable, including faults in the register file, the data cache, the data-cache TLB, the memory address and data buses, etc. Benchmark results for the MIPS R300D processor executing code scheduled by a modified GNU C Compiler show that the new approach can concurrently check a high percentage of data accesses, while causing little performance overhead and little memory overhead.

This paper presents a fundamentally new approach to global register allocation that optimally allocates registers and optimally places spill code, significantly decreasing spill code overhead compared with the traditional graph-coloring approach. The Optimal Register Allocation (ORA) approach formulates global register allocation as a 0–1 integer programming problem, incorporating all aspects of register allocation within a unified framework, including copy elimination, live range splitting, rematerialization, callee and caller register spilling, special instruction-operand requirements, and paired registers. A prototype ORA allocator is built into the Gnu C Compiler (GCC). For the SPEC92 integer benchmarks, the ORA allocator actually produces a net decrease of more than 100 million cycles across the entire benchmark set, because the dynamic copies the ORA allocator removes exceed the dynamic loads and stores that are inserted. In contrast, the GCC allocator and a Chaitin-style graph-coloring allocator each cause a net increase of more than 1 billion cycles. Because global register allocation is NP-complete, optimal register allocation has been considered intractable. However, the run-time complexity of the ORA approach is shown experimentally to be O(n3). A profile-guided hybrid allocation approach is proposed that uses the ORA allocator for the performance critical regions in the performance critical functions, while using a graph-coloring allocator for the non-critical functions and regions. An ORA-GCC hybrid allocator takes an average of 4.6 seconds per function to produce an allocation that is within 1% of optimal for 97% of the SPEC92 integer benchmark functions, showing that the hybrid allocator is practical as an advanced optimization for performance-critical codes.

A new approach produces optimal signature placement for concurrent detection of processor and program-memory errors using signature monitoring. A program control-how graph, labeled with the overhead for placing a signature on each node and arc, is transformed into an undirected graph. For an order-independent signature function such as an XOR or arithmetic checksum, the undirected graph and a spanning tree algorithm are shown to produce an optimal placement in O(n log beta (n, m)) time. Cyclic codes, which are order dependent, are shown to allow significantly lower overhead than order-independent functions. Prior work suggests overhead is unrelated to signature-function type. An O(n) graph-construction algorithm produces an optimal signature placement for cyclic codes. Experimental data show that using a cyclic code and horizontal reference signatures, the new approach can reduce average performance overhead to a fraction of a percent for the SPEC89 benchmark suite, more than 9 times lower than the performance overhead of an existing O(n/sup 2/) placement algorithm.>

A low-cost approach to concurrent detection of processor control errors is presented that uses a simple hardware monitor and signatures embedded into the executing program. Existing signature-monitoring techniques detect a large portion of processor control errors at a fraction of the cost of duplication. Analytical methods developed in this study show that the new approach, continuous signature monitoring (CSM), makes major advances beyond existing techniques. CSM reduces the fraction of undetected control-flow errors by orders of magnitude, to less than 10/sup -6/, while the number of signatures reaches a theoretical minimum, being lowered by as much as three times to a range of 4-11%. Signature cost is reduced by placing CSM signatures at locations that minimize performance loss and (for some architectures) memory overhead. CSM exploits the program memory's SEC/DED code to decrease error-detection latency by as much as 1000 times, to 0.016 program memory cycles, without increasing memory overhead. This short latency allows transient faults to be tolerated.>

Concurrent detection of processor control errors using signatured programs is discussed. The approach, called continuous signature monitoring (CSM), makes significant advances beyond the existing signature-monitoring techniques. For typical programs, CSM decreased average error-detection latency by as much as eight times, down to 1.2 to 1.6 program memory cycles. Memory overhead for storing signatures reaches a theoretical minimum, lowered as much as four times, dozen to 3-7%. The CSM monitor is less complex by more than half, and processor-performance loss is reduced as much as 10 times down to 0.6-1.5%. CSM increases coverage of control-flow errors and detects certain types of errors not detected by the existing techniques, including a stuck program counter.>