Search

Inline substitution is an optimization that replaces a procedure call with the body of the procedure that it calls. Inlining has the immediate benefit of reducing the overhead associated with the call, including register saves and restores, parameter evaluation, and activation record setup and teardown. It has secondary benefits that arise from providing greater context for global optimizations. These benefits can be offset by the effects of increased code size, and by deleterious interactions with other optimizations, such as register allocation. The difficult aspect of inline substitution is choosing which calls to inline. Previous work has focused on static, one-size-fits-all heuristics. This paper presents a feedback-driven adaptive scheme that derives a program-specific inlining heuristic. The key contributions of this work are: (1) a novel parameterization scheme for the inliner that makes it susceptible to fine-grained external control, (2) a scheme for discretizing large integer parameter spaces, and (3) effective search techniques for the resulting search space. This work provides a proof of concept that can provide insight into the design of adaptive controllers for other optimizations with complex decision heuristics. Our goal in this work is not to exhibit the world΄s best inliner. Instead, we present evidence to suggest that a program-specific, adaptive scheme is needed to achieve the best results. [ABSTRACT FROM AUTHOR]

Techniques for global register allocation via graph coloring have been extensively studied and widely implemented in compiler frameworks. This paper examines a particular variant - the Callahan Koblenz allocator - and compares it to the Chaitin-Briggs graph coloring register allocator. Both algorithms were published in the 1990's, yet the academic literature does not contain an assessment of the Callahan-Koblenz allocator. This paper evaluates and contrasts the allocation decisions made by both algorithms. In particular, we focus on two key differences between the allocators: Spill code: The Callahan-Koblenz allocator attempts to minimize the effect of spill code by using program structure to guide allocation and spill code placement. We evaluate the impact of this strategy on allocated code. Copy elimination: Effective register-to-register copy removal is important for producing good code. The allocators use different techniques to eliminate these copies. We compare the mechanisms and provide insights into the relative performance of the contrasting techniques. The Callahan-Koblenz allocator may potentially insert extra branches as part of the allocation process. We also measure the performance overhead due to these branches. [ABSTRACT FROM AUTHOR]

Instruction scheduling is a necessary step in compiling for many modern microprocessors. Traditionally, global instruction scheduling techniques have outperformed local techniques. However many of the global scheduling techniques described in the literature have a side effect of increasing the size of compiled code. In an embedded system, the size of compiled code is often a critical issue. In such circumstances, the scheduler should use techniques that avoid increasing the size of the generated code. This paper explores two global scheduling techniques, extended basic block scheduling and dominator path scheduling, that do not increase the size of the object code, and, in some cases, decrease it. [ABSTRACT FROM AUTHOR]