[Salto Home Page]

Overview of Salto


oData Structures
oMachine Description oDemonstrations
oUser Interface oPublications

For a more accurate description, you can refer to the documentation: SALTO.PS or SALTO.PDF. Online documentation is also available.


A Salto application is composed of three parts: a kernel, a machine description file and an optimization or instrumentation algorithm. Figure 1 illustrates the organization of these three components.
Interaction between different parts of Salto
Figure 1: Overview of Salto

Data Structures

The data structures used in Salto are divided into two groups, depending on their role. The first group represents the control flow of the program, the second group describes resource usage and data dependencies between instructions.

Control Flow Structures

A program written in assembly-language can be viewed as consisting of several procedures, each of which is a list of instructions. Within a procedure, instructions are grouped into basic-blocks. While parsing the code, Salto builds the list of the procedures it encounters. Each procedure has a list of basic-blocks, and each block ``knows'' its list of instructions. The internal representation is hidden by the user interface.
Additionally, the control flow graph is built for each procedure. The vertices are the basic-blocks and the edges denote the execution order of the basic-blocks. Edges are labeled to indicate if they correspond to the taken or not-taken branch.

Hardware Resources and Data Dependences

The second part of the data structures provided by Salto gives information about the resources needed by an instruction to complete execution. A resource is usually a register, a functional unit or the memory, but it could be any piece of hardware needed to describe the behavior of the machine. Each instruction needs a resource during a number of cycles with a particular access mode: three modes are available for a resource: read, write or use.
Each instruction is described by a reservation-table, which indicates the list of resources it needs and the mode and cycle a resource is accessed. This information is used when determining the type of dependence between two instructions: RAW (read after write), WAW (write after write), WAR (write after read).

Machine Description

Salto is designed to be a retargetable tool. Thus, the target machine must be described in a flexible way, permitting an accurate description while retaining the ability to easily modify parameters. This is achieved with a Lisp-like language based on the reservation-table formalism. The description file is parsed by Salto and an internal representation is built using RTL (Register Transfer Language). The machine description contains:
  1. the syntax of the assembly-language used, that is, how does a comment start, how many registers are there, and what are their names;
  2. all the resources needed for the computation of data dependencies;
  3. the list of the instructions recognized by the assembler with the applicable formats and the associated reservation-tables;
  4. semantical information to warn Salto about special features implemented in the processor like bypass-mechanism or delayed branch.
A simplified description of the Sparc v7 architecture can be seen as an example.

User Interface

The object-oriented user interface provides a flexible way to deal with the internal data structures. Features of Salto include: The easiest way to understand how the user interface is used, is to have a look at small examples of tools written with Salto.