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 :-) 

• a change made to the internal structure of software to make it easier to understand and cheaper to modify without changing its observable behavior

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   of 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.

NEWS CONTENTS

• 190701 : A Peephole Optimizer for Python ( A Peephole Optimizer for Python, )

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)';

<[email protected]> 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 <[email protected]>
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

Softpanorama Recommended

Top articles

Sites

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

Internal documentation on the peephole optimizer

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)

[PDF] The Design and Application of a Retargetable Peephole Optimizer

[PDF] A Compact, Machine-Independent Peephole Optimizer

File Format: PDF/Adobe Acrobat - View as HTML PEEPHOLE. OPTIMIZER. Christopher. W. Fraser. Abstract. Department ... independent. peephole. optimizer. Introduction. Of. all. optimizations, ... www.well.com/~cwf/pro/ Fraser.%20A%20compact,%20machine-independent%20peephole%20optimizer.pdf - Similar pages

[PDF] Optimizer paper

Raisonance CodeCompressor technology - Using Peephole scripts

Static Analysis for a Software Transformation Tool - Morgenthaler (ResearchIndex)

Abstract: Software is difficult and costly to modify correctly. Automating tiresome mechanical tasks such as program restructuring is one approach to reducing the burden of software maintenance. Several restructuring tools have been proposed and prototyped, all centered on the concept of meaning-preserving transformations similar in spirit to compiler optimizations. Like optimizing compilers, these tools rely on static analysis to reason about the correctness of program changes. However, the cost (in... (Update)

Active bibliography (related documents): More All
1.1: Building an Efficient Software Manipulation Tool - Morgenthaler (1998) (Correct)
0.7: Program Restructuring as an Aid to Software Maintenance - Griswold (1991) (Correct)
0.6: Supporting the Restructuring of Data Abstractions through.. - Bowdidge (1995) (Correct)

Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes :  Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce :  Bernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS :  Programming Languages History : PL/1 : Simula 67 : C : History of GCC development :  Scripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month :  How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March 12, 2019