Dissertation/Thesis Abstract

Peephole superoptimization
by Bansal, Sorav, Ph.D., Stanford University, 2008, 95; 3332986
Abstract (Summary)

The classical meaning of superoptimization is to find the optimal code sequence for a single, loop-free assembly sequence of instructions. Superoptimization has previously been studied for compiling small, performance critical code fragments, such as compute-intensive inner loops. This thesis investigates the use of superoptimization techniques in optimization and code generation for whole programs.

The first part of the thesis describes peephole superoptimizers and their construction. A peephole superoptimizer first generates a peephole optimizer using superoptimization techniques and then applies the generated peephole optimizer to improve executables. Using this approach, we are able to generate many useful peephole optimizations automatically and find improvements over code optimized by mature compilers.

The second part of the thesis applies peephole superoptimizers to perform efficient binary translation between two divergent architectures. We use a superoptimizer to generate equivalence relations between code snippets of two different architectures. The equivalence relation is represented as a peephole transformation. We discuss our PowerPC-X86 binary translator implemented using peephole superoptimization techniques, and compare it with existing binary translation tools.

The third part of the thesis discusses a novel approach to significantly lower the computational complexity of brute-force superoptimization. Our approach, which we call meet-in-the-middle superoptimization, uses reverse execution of instructions to significantly prune the superoptimizer's search space.

Indexing (document details)
School: Stanford University
School Location: United States -- California
Source: DAI-B 69/10, Dissertation Abstracts International
Subjects: Electrical engineering, Computer science
Keywords: Binary translation, Compiler optimization, ISA emulation, Peephole optimizers, Superoptimization
Publication Number: 3332986
ISBN: 978-0-549-85112-7
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy