EEL: An Executable Editing Library

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.

Why Edit Executables?

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

Another use of executable editing is program observation. Profiling and tracing tools, such as MIPS's pixie or 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.

How EEL Helps

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.

Details

EEL currently operates on SPARC processors, including UltraSPARCs with the V8+ instruction set. Earlier versions worked for SunOS or Solaris, but the new versions only work for Solaris. A partial port to RS6000s running AIX exists, but is not currently distributed.

EEL is distributed as part of the Wisconsin Architectural Research Toolset (WARTS). WARTS is available without charge for university researchers and is available to other researchers for a modest research donation.

Tools Built with EEL

For More Information

Click here for slides of a talk on EEL.

An overview paper for EEL (appeared in the ACM SIGPLAN PLDI Conference, June 1995).

Another paper demonstrating that simple instruction scheduling can hide 20-65% of the cost of program instrumentation and that rescheduling legacy code for superscalar processors can significantly improve performance.

Etch tool for editing Win32 x86 executables.

James Larus
Computer Sciences Department
University of Wisconsin
1210 West Dayton Street
Madison, WI 53706
larus@cs.wisc.edu
608-262-9519

Last modified: Sat Jun 1 08:09:20 1996 by James Larus