Code optimization as a side effect of instruction scheduling
7
Citation
15
Reference
10
Related Paper
Abstract:
An instruction scheduler utilizes code reordering techniques for generating schedules in which instructions can be issued without delays. In order to perform code reordering across branches, code motion is performed that hoists some instructions above branches and sinks others below branches. Following code reordering, compensation code must be introduced in order to preserve program semantics. In this paper, we demonstrate that several important code optimizations can be performed as a side-effect of generating compensation code. These optimizations include partial redundancy elimination, partial dead code elimination, elimination of redundant loads and elimination of dead stores. We demonstrate how existing data-flow frameworks for these optimizations can be extended for generating optimized compensation code.Keywords:
Unreachable code
Dead code
Dead code elimination
Code (set theory)
Unreachable code
Dead code
Machine code
Dead code elimination
Register allocation
Code (set theory)
Cite
Citations (30)
We describe the design and implementation of a compiler that automatically translates ordinary programs written in a subset of ML into code that generates native code at run time. Run-time code generation can make use of values and invariants that cannot be exploited at compile time, yielding code that is often superior to statically optimal code. But the cost of optimizing and generating code at run time can be prohibitive. We demonstrate how compile-time specialization can reduce the cost of run-time code generation by an order of magnitude without greatly affecting code quality. Several benchmark programs are examined, which exhibit an average cost of only six cycles per instruction generated at run time.
Compile time
Dead code elimination
Unreachable code
Dead code
Code (set theory)
Benchmark (surveying)
Cite
Citations (19)
We describe the design and implementation of a compiler that automatically translates ordinary programs written in a subset of ML into code that generates native code at run time. Run-time code generation can make use of values and invariants that cannot be exploited at compile time, yielding code that is often superior to statically optimal code. But the cost of optimizing and generating code at run time can be prohibitive. We demonstrate how compile-time specialization can reduce the cost of run-time code generation by an order of magnitude without greatly affecting code quality. Several benchmark programs are examined, which exhibit an average cost of only six cycles per instruction generated at run time.
Compile time
Dead code elimination
Unreachable code
Dead code
Code (set theory)
Benchmark (surveying)
Cite
Citations (5)
We describe the design and implementation of a compiler that automatically translates ordinary programs written in a subset of ML into code that generates native code at run time. Run-time code generation can make use of values and invariants that cannot be exploited at compile time, yielding code that is often superior to statically optimal code. But the cost of optimizing and generating code at run time can be prohibitive. We demonstrate how compile-time specialization can reduce the cost of run-time code generation by an order of magnitude without greatly affecting code quality. Several benchmark programs are examined, which exhibit an average cost of only six cycles per instruction generated at run time.
Compile time
Dead code elimination
Unreachable code
Dead code
Code (set theory)
Benchmark (surveying)
Cite
Citations (208)
A promising trend in software development is the increasing adoption of model-driven design. In this approach, a developer first constructs an abstract model of the required program behavior in a language, such as Statecharts or Stateflow, and then uses a code generator to automatically transform the model into an executable program. This approach has many advantages---typically, a model is not only more concise than code and hence more understandable, it is also more amenable to mechanized analysis. Moreover, automatic generation of code from a model usually produces code with fewer errors than hand-crafted code.One serious problem, however, is that a code generator may produce inefficient code. To address this problem, this paper describes a method for generating efficient code from SCR (Software Cost Reduction) specifications. While the SCR tabular notation and tools have been used successfully to specify, simulate, and verify numerous embedded systems, until now SCR has lacked an automated method for generating optimized code. This paper describes an efficient method for automatic code generation from SCR specifications, together with an implementation and an experimental evaluation. The method first synthesizes an execution-flow graph from the specification, then applies three optimizations to the graph, namely, input slicing, simplification, and output slicing, and then automatically generates code from the optimized graph. Experiments on seven benchmarks demonstrate that the method produces significant performance improvements in code generated from large specifications. Moreover, code generation is relatively fast, and the code produced is relatively compact.
Executable
Unreachable code
Dead code
KPI-driven code analysis
Code (set theory)
Dead code elimination
Compiled language
Control flow graph
Tracing
Program slicing
Stateflow
Cite
Citations (17)
The Twente Compiler Generator System (TCGS) is a parser-generator system which is typically used to generate a compiler that, given an input program, generates abstract stack code. A code generator for TCGS translates this stack code generated by a TCGS compiler to assembler code for a particular target machine.
This thesis discusses two code generators for TCGS: GUMP and COGGEN.
The simplest strategy to translate stack code into assembler code is to macro expand each stack code instruction to an equivalent sequence of assembler code instructions. This simple strategy is used in the code generator GUMP.
COGGEN, which stands for Code-Generator Generator, is a retargetable code generator. The intermediate language used in COGGEN modules is the Register Transfer Language (RTL). COGGEN consists of several modules. COGGEN’s expander translates abstract stack code of the TCGS compiler to RTL-code. COGGEN’s assigner maps the temporaries in the RTL-code upon machine registers of the target machine. From a machine description, COGGEN’s transformer builds the transducer, an automaton which translates RTL-code to assembler code for the target machine.
Both code generators are implemented for Intel’s 8086 microprocessor. Code generated with GUMP86 is 40 times faster than TCGS’ interpreter and code generated with COGGEN86 is roughly 65 times faster than TCGS’ interpreter.
Unreachable code
Dead code
Dead code elimination
Machine code
Assembly language
Code (set theory)
Cite
Citations (0)
E-Code is a higher-level language for dynamic code generation. E-Code specifically targets the dynamic generation of small code segments whose simplicity does not merit the complexity of a large interpreted environment. To that end, E-code is as simple and restricted a language as possible within the bounds of its target environment. E-Code’s dynamic code generation capabilities are based on DRISC, a Georgia Tech package that provides a programatic on-the-fly code generation through a virtual RISC instruction set. DRISC also has a “virtual register” mode in which it performs simple register allocation and assignment. E-Code consists primarily of a lexer, parser, semanticizer and code generator.
Unreachable code
Dead code
Code (set theory)
Compiled language
Intermediate language
Dead code elimination
Cite
Citations (10)
A new, template-based code generator has been implemented for the OpenModelica compiler. All data needed for target code generation has been collected in a new data structure that is then sent to templates which generate target code based on that data. This simplifies the implementation of the code generator and also makes it possible to write a different set of templates to generate target code in a different language. The new, template-based code generator currently only supports generation of target code for simulating Modelica models. In that scenario it translates models roughly at the same speed as the old code generator.
Template
Unreachable code
Code (set theory)
Dead code
Dead code elimination
Cite
Citations (0)
This paper describes GBURG, which generates tiny, fast code generators based on finite-state machine pattern matching. The code generators translate postfix intermediate code into machine instructions in one pass (except, of course, for backpatching addresses). A stack-based virtual machine---known as the Lean Virtual Machine (LVM)---tuned for fast code generation is also described. GBURG translates the two-page LVM-to-x86 specification into a code generator that fits entirely in an 8 KB I-cache and that emits x86 code at 3.6 MB/set on a 266-MHz P6. Our just-in-time code generator translates and executes small benchmarks at speeds within a factor of two of executables derived from the conventional compile-time code generator on which it is based.
Unreachable code
Executable
Dead code
x86
Dead code elimination
Code (set theory)
Machine code
Cite
Citations (4)
Dead code elimination
Register allocation
Dead code
Unreachable code
Code (set theory)
Software portability
Copying
Compiler construction
Benchmark (surveying)
Cite
Citations (10)