Release: EEL Executable Editing Library (James Larus)
Wed, 10 May 1995 18:30:43 GMT

          From comp.compilers

Related articles
Release: EEL Executable Editing Library (1995-05-10)
| List of all articles for this month |

Newsgroups: comp.arch,comp.compilers,comp.sys.sun.announce
From: (James Larus)
Keywords: linker, tools, available
Organization: University of Wisconsin, Computer Sciences Deptartment
Date: Wed, 10 May 1995 18:30:43 GMT

EEL Executable Editing Library

James Larus
University of Wisconsin--Madison

EEL (Executable Editing Library) is a new C++ library that hides much of
the complexity and system-specific detail of editing executables. EEL
provides abstractions that allow a tool to analyze and modify executable
programs without being concerned with particular instruction sets,
executable file formats, or consequences of deleting existing code and
adding foreign code. EEL greatly simplifies the construction of program
measurement, protection, translation, and debugging tools. EEL differs
from other systems in two major ways: it can edit fully-linked
executables, not just object files, and it emphasizes portability across
a wide range of systems.

Executable editing is widely used for three purposes: emulation,
observation, and optimization. An edited executable can emulate features
that hardware does not provide. For example, the Wisconsin Wind Tunnel
architecture simulator drives a distributed, discrete-event simulation of
a parallel computer from the logical cycle times of processors directly
executing a parallel program. The underlying hardware (a SPARC processor
in a Thinking Machines CM-5) does not provide a cycle counter or an
efficient mechanism for interleaving computation and simulation. The
Wind Tunnel system edits programs so that they update a cycle timer and
return control at timer expirations. Similarly, one version of the
Blizzard distributed shared-memory system edits programs to insert
fine-grain access tests before shared loads and stores. These tests
permit data sharing at cache-block granularity, which reduces the false
sharing incurred by page-granularity distributed shared-memory
systems. In the limit, editing can replace an entire program with
instructions for a different architecture. Translation is used both to
migrate legacy code to new architectures and to run binaries on other

Another use of executable editing is program observation. Profiling and
tracing tools, such as MIPS's pixie or my qpt, edit executables to record
execution frequencies or trace memory references. These tools are widely
used to study program or system behavior and computer architecture. More
recently, a tool based on EEL, Active Memory, dramatically lowered the
cost of cache simulation-to a 2-7x slowdown-by inserting cache-miss tests
before a program's memory references rather than post-processing an
address trace.

Finally, executable editing has also been used for global register
allocation and program optimization. Unlike most compilers, which
operate on a single file, editing can manipulate an entire program, which
permits it to perform interprocedural analysis rather than stopping at
procedure boundaries.

EEL provides five major abstractions (C++ class hierarchies) that allow a
tool to examine and modify an executable: executable, routine, CFG,
instruction, and snippet. An executable contains code and data from
either an object, library, or executable file. A tool opens an
executable, examines and modifies its contents, and writes an edited
version. An executable primarily contains routines, the second
abstraction, but also contains non-executable data. A tool can examine
and modify routines in any order and place them, and new routines, in the
edited executable in any order. EEL represents a routine's body with two
further abstractions: control-flow graphs (CFGs) and instructions. A CFG
is a directed graph whose nodes are basic blocks (single-entry,
single-exit straight-line code sequences) and whose edges represent
control flow between blocks. EEL provides extensive control-flow and
data-flow analysis for CFGs. Blocks contain a sequence of instructions,
each of which is a machine-independent description of a machine
instruction. A tool edits a CFG by deleting instructions or adding code
snippets to blocks and edges. A snippet encapsulates machine-specific
foreign code and provides context-dependent register allocation. EEL
modifies calls, branch, and jumps to ensure that control flows correctly
in the edited program.

EEL currently works for SPARC processors (running SunOS or Solaris).

EEL is distributed as part of the Wisconsin Architectural Research
Toolset (WARTS). For more information on WARTS:

WARTS is available without charge for university researchers and is
available to others for a modest research donation.

A paper describing EEL (to appear in PLDI '95, June 1995) is available:

James Larus
Computer Sciences Department
University of Wisconsin
1210 West Dayton Street
Madison, WI 53706

$Id: BLURB,v 1.4 1995/05/10 16:37:03 larus Exp $

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.