Softpanorama (slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-) Softpanorama Search

Peephole Refactoring As Program Analysis and Decompilation Method

Peephole optimization is a very simple and powerful method for both refactoring and reverse engineering of program control flow.  It was invented by Bill McKeeman  and published in 1965 in his famous article MCKEEMAN, W.M. Peephole optimization. Commun. ACM 8,  7 (July 1965), 443-444.  It was used in XPL complier that McKeeman  developed. XPL language was specialized compiler writing languages that has strings with garbage collection.  The text of the compiler was freely available (and still is). Later peephole optimizers were developed for many compilers in all major hardware architectures and intermediate languages. See roster

The concept of peephole is somewhat collected with the concept of a slice and in general case nothing prevents  peephole from being applied to a selective view of the intermediate code or assembler code. Such selective view might have,  for example,  only all control related statements in assembler.  Slicing proved its great value in program understanding and as such is a valuable tool in any program reconstruction activity.

Stony Brook Pascal, a popular Pascal compiler for S/370 from the State University of New York at Stony Brook was built with XPL.

The peephole is a small moving window on the target program. Instructions are optimized only considering the instructions in the peephole. Peephole optimization is applied over the while target program, moving the peephole window. Several passes can be used if necessary.  It can be adapted to intermediate simplified marking language representation (XML or XHTML+styleseet ).  Some people even tried to used XSLT to generate code in an application software project like "template-driven code generator". See Soumen Sarkar experience of using XSLT and the book Program Generators with XML and Java for more information.

Peephole optimization should be probably called refactoring to make it sound more modern and fashionable :-) 

Peephole refactoring is essentially a the pattern matching and multistage conditional replacement technique that reminds Floyd-Evans production parsing algorithms as described by David Gries in his famous 1971 book Compiler Construction for Digital Computers .  It is performed on small sliding window called peephole. By pattern matching the tuples of the control flow graph we can determine if they can be replaced by an equivalent higher level construction. This approach can be used for the decomplation of control flow  in assembler programs. Regular expressions are the most natural candidate for recognition of simple control structures. The most relevant paper for this usage of regular expressions is:

GOTO Removal Based On Regular Expressions - Paul Morris Ronald      

......our GOTO removal program served as a bridge to extend the range of the software. We have also applied this work to the process of "levitating" IBM 370 assembly language code to higher-level forms (Morris et al., 1996). Previous work (Ashcroft et al., 1972, Peterson et al., 1973, Ramshaw, 1988, Erosa et al., 1994), while highly developed and abstract in nature, treats GOTO removal as an isolated problem in the area of programming languages. This paper is based on the observation that GOTO removal for flowcharts resembles the problem of converting finite-state transition networks to regular expressions, and ......

......preferred over maintaining the existing structure. The algorithm presented here is applicable to nonreducible programs, and meets the lesser path-equivalence standard. Subjectively, this standard appears to produce more readable results than approaches that introduce auxiliary variables, such as (Erosa et al., 1994), and is easier to relate to the source presented for restructuring. These considerations are important for reverse-engineering. While the algorithm discussed in this paper has worked well in practical contexts, we feel its most significant feature is the link to important concepts in computer ......

Erosa, A. M. and Hendron, L. J. (1994). `Taming Control Flow: A structured Approach to Eliminating Goto Statements,' Proc. IEEE International Conference on Computer Languages, 229--240.

Old News ;-)

A Peephole Optimizer for Python

This paper describes the implementation of a peephole optimizer for Python byte codes. Python's byte code compiler currently generates code that can easily be improved. The peephole optimizer implemented presented here implements a number of common optimizations, including jump chaining, constant expression evaluation and elimination of unecessary loads. Some optimizations rely on specific properties of Python or its virtual machine. Some optimizations common to statically typed languages, such as algebraic simplification and expression rearrangement, are prevented by Python's dynamic typing. Preliminary results obtained using pybench [Lemb] suggest that the optimizer has a positive benefit for specific operations. With the current measurement tools available however, it is difficult to quantify benefits that can be derived by using the optimizer. Situations in which the benchmarks may not yield reliable results are considered. The limitations Python places on the optimizer are discussed, especially restrictions caused by the dynamic nature of the language. Other performance improvements to the Python interpreter are discussed briefly.

Declarative Peephole Optimization Using String Pattern Matching

Peephole optimisation as a last step of a compilation sequence capitalises on significant opportunities for removing low level code slackness left over by the code generation process. We have designed a peephole optimiser that operates using a declarative specification of the optimisations to be performed. The optimiser's implementation is based on string pattern matching using regular expressions. We used this approach to prototype an optimiser to convert target machine instruction sequences containing conditional execution of instructions inside loop bodies into code that adaptively executes the optimum branch instructions according to the program's branch behaviour.

Peephole Optimization - Untitled

Recursive descend query compilers easily miss opportunities for better code generation, because limited context is retained or lookahead available. The peephole optimizer is built around such recurring patterns and compensates for the compilers 'mistakes'. The collection of peephole patterns should grow over time and front-end specific variations are foreseen.

The SQL frontend heavily relies on a pivot table, which is a generated oid sequence. Unfortunately, this is not seen and the pattern '$i := calc.oid(0@0); $j:= algebra.markT($k,$i);' occurs often. This can be replaced with '$j:= algebra.markT($k)';

<Steven.R.Walk@att.com> wrote:
> In the article listed below Peter Kessler describes a method for automatically
> analyzing a machine description to discover 'machine idioms'. He mentions
> near the end of the article that over 300 idioms for the 68000 and a similar
> number for the VAX were found.
 

There's a related paper by Massalin in ASPLOS '87:
Superoptimizer --- A look at the smallest program. Proceedings of the
Second International Conference on Architectural Support for
Programming Languages and Operating Systems (ASPLOS II), Oct. 1987, IEEE.
 

Abstract:
        The superoptimizer is a tool that, given an instruction set, finds
        the shortest program to compute a function. Startling programs
        have been generated, many of them engaging in convoluted bit-
        fiddling bearing little resemblance to the source programs which
        defined the functions. The key idea in the superoptimizer is a
        probabilistic test that makes exhaustive searches practical for
        programs of useful size. The search space is defined by the
        processor's instruction set, which may include the whole set, but
        it is typically restricted to a subset. By constraining the
        instructions and observing the effect on the output program, it is
        possible to gain insight into the design of instruction sets. In
        addition, superoptimized programs may be used by peephole
        optimizers to improve the quality of generated code, or by
        assembly language programmers to improve manually written code
 

--
Mark Leone <mleone@cs.cmu.edu>
School of Computer Science, Carnegie Mellon University
Pittsburgh, PA 15213 USA

Another example of a 2-way instruction sequence produced is then '$j:= algebra.markT($k); $l:= bat.reverse($j);', which can be replaced by '$l:= algebra.markH($k);'.

The reverse-reverse operation also falls into this category. Reversal pairs may result from the processing scheme of a front-end compiler or from a side-effect from other optimization steps. Such reversal pairs should be removed as quickly as possible, so as to reduce the complexity of finding alternative optimization opportunities. As in all cases we should ensure that the intermediates dropped are not used for other purposes as well.

	r:bat[:int,:int]:= bat.new(:int,:int);
	o:= calc.oid(0@0);
	z:= algebra.markT(r,o);
	rr:= bat.reverse(z);
	s := bat.reverse(r);
	t := bat.reverse(s);
	io.print(t);
	optimizer.peephole();

which is translated by the peephole optimizer into:

	r:bat[:int,:int] := bat.new(:int,:int);
	rr := algebra.markH(r);
	io.print(r);

The peephole optimizer

Last updated 3 June 1996.

The peephole optimizer is now available for both C and Scheme.

PDF] Peephole Optimization

Quick Compilers Using Peephole Optimization - Davidson, Whalley (ResearchIndex)

Abstract: machine modeling is a popular technique for developing portable compilers. A compiler can be quickly realized by translating the abstract machine operations to target machine operations. The problem with these compilers is that they trade execution efficiency for portability. Typically the code emitted by these compilers runs two to three times slower than the code generated by compilers that employ sophisticated code generators. This paper describes a C compiler that uses abstract machine... (Update)

Recommended Links

---

In case of broken links please try to use Google search. If you find the page please notify us about new location

Peephole optimization - Wikipedia, the free encyclopedia

Peephole Optimization

[PDF] Using Peephole Optimization on Intermediate Code ANDREW S. TANENBAUM, HANS van STAVEREN, and JOHAN W. STEVENSON  Vrije Universiteit, Amsterdam, The Netherlands

Many portable compilers generate an intermediate code that is subsequently translated into the Target machine's assembly language. In this paper a stack-machine-based intermediate code suitable for algebraic languages (e.g., PASCAL, C, FORTRAN) and most byte-addressed mini- and microcomputers is described. A table-driven optimizer that improves this intermediate code is then discussed in detail and compared with other local optimization methods. Measurements show an improvement of about 15 percent, depending on the precise metric used.

Categories and Subject Descriptors: D.3.4 [Programming Languages]:

Using and Porting GNU CC - Peephole Definitions

Code Compaction Bibliography Keywords code compaction, code compression, code size, code size reduction, code density, compression, compact code, compiler, code size o

Peephole Optimization from Optimized Code Generation for Digital Signal Processors Thomas Brüggen - Andreas Ropers 11.08.1999

KOPI Classfile API Java peephole optimizer

Larceny Note #6 Larceny on the SPARC

Peephole “Optimization”

Peephole optimization

Tucows Linux perlguts.1

Compile pass 3: peephole optimization

After the compile tree for a subroutine (or for an eval or a file) is created, an additional pass over the code is performed. This pass is neither top-down or bottom-up, but in the execution order (with additional complications for conditionals). These optimizations are done in the subroutine peep(). Optimizations performed at this stage are subject to the same restrictions as in the pass 2.

Peephole Optimisation -- Peephole optimization is a local form of optimization. It can be defined as 'The pattern matching and conditional replacement performed on small sections' [Allan 1990]. By pattern matching the tuples of the computational graph we can determine if they can be replaced by an equivalent instruction or set of instructions that are more efficient.

Peephole optimization as a targeting and coupling tool

A Preliminary Exploration of Optimized Stack Code Generation

Optimizing Alpha Executables on Windows NT with Spike Windows NT-based applications, Spike Optimizer, optimization system for Alpha executables

Delivering Binary Object Modification Tools for Program Analysis and Optimization

A Peephole Optimizer for Python -- Skip Montanaro Automatrix, Inc. Rexford, NY

• http://www.automatrix.com/~skip/python/optimizer.patch. Montanaro, Skip. "Peephole Optimizer Patch"

Using and Porting GNU CC - Peephole Definitions

Amortizing 3D Graphics Optimization Across Multiple Frames

www.partner.digital.comwww-swdevpagesHomeTECHdocumentsalpha_cookbooklccport.htm

Java Bytecode to Native Code Translators October, 1997

Catalog of compilers y+po

Peephole Log Optimization - Huston, Honeyman (ResearchIndex)

http://www.ics.uci.edu/~kistler/ics-tr-96-54.ps Kistler, Thomas. "Dynamic Runtime Optimization", UC Irvine Technical Report 96-54, November 1996.

Chambers, Craig. "The Design and Implementation of the Self Compiler, an Optimizing Compiler for Object-Oriented Programming Languages". Ph. D. dissertation, Computer Science Department, Stanford University, March 1992.

An Approach for Exploring Code Improving Transformations - Whitfield, Soffa (ResearchIndex)

Abstract: : Although code transformations are routinely applied to improve the performance of programs for both scalar and parallel machines, the properties of code improving transformations are not well understood. In this paper we present a framework that enables the exploration, both analytically and experimentally, of properties of code improving transformations. The major component of the framework is a specification language, Gospel, for expressing the conditions needed to safely apply a... (Update)