The Machine SUIF system is an extension of Stanford SUIF version 2 that supports construction of compiler back ends. Themachinelibrary is the core of Machine SUIF. It enables you to create machine descriptions, to construct and manipulate machine-level intermediate forms during back-end optimization, and to emit object code.While the library itself is machine independent, it is the basis for producing other libraries that are machine specific. These machine-specific libraries supply the parameters that make machine-independent optimization passes sensitive to the peculiarities of target machines.
The optimization programming interface (OPI) used for creating Machine-SUIF passes and libraries is described elsewhere [cite bibext, bibopiusr]. This document fills in details of the OPI as implemented in Machine SUIF. It also discusses aspects of the implementation that will help you use and extend the system.
The Machine SUIF system is an extension of Stanford SUIF version 2 that supports construction of compiler back ends. This document is part of a set of documents explaining how to use and how to extend Machine SUIF. It is aimed at three kinds of readers:
We assume that you have read An Introduction to Machine SUIF and Its Portable Libraries for Analysis and Optimization and A User's Guide to the Optimization Programming Interface. As explained in those documents, Machine SUIF implements an interface for optimization writers, the OPI, that can be used not only for static compilation, an in Machine SUIF, but also in other settings, such as run-time code optimization. Since the OPI has a wider scope than Machine SUIF, it has been documented separately.
This document begins the description of how the OPI is implemented as an extension of SUIF version 2. [You will need to be familiar with the basic concepts of SUIF 2, also referred to here as base SUIF. See the SUIF 2 home page for information on that system.] It also describes the mechanisms that allow extension of the system in several directions. The OPI itself can be extended by the addition of new intermediate representations. New target-architecture families can be added to the system, and existing ones can be augmented, either to reflect new implementations by vendors or to accommodate architectural experiments.
The core of the Machine SUIF implementation is the machine library,
which is the subject of this document. It implements the most basic IR
classes in the OPI and it also establishes extension machinery. Other
Machine-SUIF libraries, such as the control-flow graph (cfg) library,
continue the OPI implementation and they illustrate how Machine SUIF allows
the OPI to be extended by users. The documents describing those libraries
should be helpful both to users and extenders of the system.
The machine library, the cfg library, and others that develop the
OPI implementation are machine-independent: they are designed to apply to
all kinds of target machines. A different series of libraries supply the
machine descriptions necessary to carry out machine-level optimization. We
say that the OPI is parameterized over the features of target
machines. The machine-specific libraries supply the parameter bindings.
The main sections of this document correspond to implementation modules. The interfaces they display are exactly the source code that is extracted and used to build the system.
As hinted above, the machine library plays several diferent roles.
We touch on each of these roles in the following subsections.
We rely on the SUIF substrate to provide:
Connection to the SUIF substrate is mostly quite simple. The OPI uses a
naming convention similar to that used in SUIF. Its names tend to be
shorter than SUIF's, so some classes are renamed via typedefs. For
example, SUIF's VariableSymbol becomes VarSym. The OPI uses a
different style for annotating IR objects than base SUIF, so the
machine library encapsulates SUIF annotations as OPI notes.
A more pervasive style difference is that base SUIF makes little use of
global variables and expresses all functionality through class methods,
while the OPI makes use of both global variables and overloaded global
functions. Part of the machine library's substrate-interface role is
simply to convert calls on class methods into calls on plain functions.
In Machine SUIF, when IR objects are created by OPI functions, they
sometimes need to be connected to other objects in ways that are not
apparent at the OPI level. The chief example is the Machine-SUIF operand,
of type Opnd, which will be discussed in the next subsection.
The machine library implements the core of the OPI's IR classes: those
for instruction-lists (InstrList), instructions (Instr), operands
(Opnd), and annotations (Note). It also implements
functions and classes that create, inspect, and manipulate IR objects.
The OPI tries not to hard-wire the decision of what program units shall be
optimized. While it's traditional to deal with one source procedure at a
time, the OPI doesn't lock users into that model. Nevertheless, in Machine
SUIF, the OPI data type OptUnit is exactly the SUIF
ProcedureDefinition (which we also nickname ProcDef).
The Machine-SUIF class InstrList is used to represent a sequence of
machine instructions, including label ``instructions'' that serve as the
targets of control-transfer instructions (CTI). Thus a single
InstrList object can represent all of the control behavior of a
machine-level program.
InstrList is implemented as a subclass of AnyBody, which is itself
a subclass of SUIF's ExecutionObject. Since the the body field of
a SUIF procedure definition has type ExecutionObject*, an InstrList
can be used as the body of a SUIF procedure representation. This is one of
the key points of connection between base SUIF and Machine SUIF.
The OPI defines one instruction class, Instr, which it describes in
four categories, two real (executable) and two ``pseudo''. Mirroring that
breakdown, the Machine SUIF class hierarchy defines four instruction
classes: InstrAlm (arithmetic, logical and memory), InstrCti
(control-transfer), InstrLabel (label-defining), and InstrDot
(pseudo-op). An OPI user needs to understand the categories, but shouldn't
need to mention the implementation classes that correspond to them.
Instances of class Instr must correspond one-to-one with real machine
instructions, but must be manipulated by machine-independent tools. It
seems pointless to try to reflect the myriad formats of real machine
instructions in the Machine-SUIF representation of instructions. For a
small gain in space efficiency, we would add considerable complexity and
would make it harder to tranform instructions in place, e.g., by altering
opcodes and shifting operands.
The OPI defines one operand class, Opnd, which it breaks downs into
several categories. One of these, the address expressions, is further
broken down into subcategories. As with Instr, the implementation of
Opnd uses a class hierarchy that closely parallels the OPI
characterization.
But Opnd presents a special problem in the Machine SUIF implementation
because the OPI describes it not as a heap-allocated object handled through
pointers, but as a scalar value. The reason is that in a run-time
optimization setting, operands can and should have a very lightweight
implementation, requiring no storage management. It would be a mistake to
require them to be treated as pointers in that setting simply to make the
Machine-SUIF implementation a bit more uniform.
For this reason, the OPI leaves open the question of whether instances
of non-pointer IR data types such as Opnd behave like references
or like independent values. An implementation is free to use
reference semantics, and in fact, Machine SUIF does so. For
algorithms that aren't meant to be reusable in an on-line setting,
that's all you need to know. For maximum portability of your
OPI-based programs, however, you should explicitly clone mutable operands to
prevent accidental side effects. (See the description of clone in
Section [->].) In practice, this is seldom needed,
since the most frequently-used kinds of operands are immutable.
Under the hood, a Machine-SUIF operand is really a pointer to a SUIF object. Machine SUIF hides the allocation and deallocation of these objects. The user interface to operands is through functions and interface classes defined by the OPI, not through the methods of the implementation objects.
The situation is similar for Machine-SUIF annotations. Class Note
needs to be amenable to a variety of lightweight implementations. Like
Opnd, it is used as a scalar, not an explicit pointer. But as with
Opnd, Machine SUIF employs a hidden pointer to a base SUIF annotation
object, and it reflects reference sementics. And again, a clone
function allows you to avoid accidental mutation.
The machine library defines the classes for machine-description data
structures that are instantiated by target-specific libraries. A typical
example of these is the RegInfo class (Section [->]). A
RegInfo object describes the register architecture of a family of
target machines, including the number and kinds of register files, the
widths of their registers and the number in each bank, and so on. Machine
descriptions of this kind are an important part of the binding that a
machine-specific library establishes when it is loaded.
Machine-independent optimization code queries these machine descriptions in
order to cater to machine characteristics without hard-wiring in.
Most back ends constructed in Machine-SUIF start with passes for lowering
and code generation and end with a finalization pass and a pass for
emitting object code. Lowering is machine-independent; it translates from
the base SUIF intermediate form to Machine SUIF, using the SUIFvm idealized
machine as the target. The other three kinds of passes need to be
specialized for the target machine, but for each kind, the pattern is much
the same from target to target. The machine library provides base
classes that are used as frameworks for such passes. For a specific
target, the corresponding library derives from these base classes and fills
in the target-specific particulars.
For example, a typical finalization pass does such things as allocating the
stack frame for each compiled procedure, it replaces symbolic stack
references by effective-address expressions with specific frame offsets, it
generates register-saving and restoring prologue and epilogue code, and so
on. The machine library defines a CodeFin class that provides the
framework for finalization passes. To produce an actual finalization pass
for the Alpha target, say, the Alpha library derives a subclass of
CodeFin and specializes the methods representing the different
finalization steps.
In addition to CodeFin, the machine library currently has such
frameworks for emitting object code in two forms: assembly code
(Printer) and C code (CPrinter). Eventually, there will be another
one for binary object modules.
The framework for code generation is called CodeGen. Its input is in
the form of SUIFvm code, and for that reason it's defined in the suifvm
library, not the machine library.
The fact that the OPI relies heavily on global variables and functions is conducive to extensibility of the system. A problem arises, of course, if binding the OPI to a particular target machine is done simply by setting some global variables that are shared by the code for a pass and all the libraries that it links in. The issue is that occasionally passes may need to deal with more than one machine binding at a time. A binary translator, for example, needs the descriptions of both its source and target machines at the same time. If it needs flow graphs for both kinds of machines at the same time, then it wouldn't do for the CFG library to rely only on global variables when accessing machine characteristics. Elements of such a library need to be explicitly parameterized so that they can be used for more than one target within the same application.
To solve this problem, the machine library provides a class called
Context (Section [->]). Its main purpose is to gather
in one place the target-specific bindings needed for a particular
compilation context. For example, the function that takes a machine
instruction and returns true if it reads memory is actually stored in a
Context. That's because it is target-specific; it's definition must
come from a target-specific library. Likewise, the RegInfo record that
describes that target's register architecture is stored in a Context.
On the other hand, nearly every kind of pass other than a binary translator is concerned with only one target machine at a time. To accommodate that very common case, the system includes a distinguished global context, and you access its contents through simple global functions. Most pass writers can therefore ignore the context mechanism records and use these global functions.
In addition to making optimization code simpler to write, this scheme is best for porting passes into the dynamic optimization world as well. In that setting, a context record would be an unnecessary encumbrance, since the target is well known.
Libraries may of course extend the set of target-specific features of the
OPI. For example, the library that supports instruction scheduling needs
more detailed hardware descriptions than are defined in the machine
library. The Extender's Guide describes how contexts help. This
document explains the implementation.
The central classes in the representation of machine-level code are those
for instruction lists (InstrList), instructions (Instr), and
operands (Opnd). This section and the next introduce these classes and
the OPI functions that relate to them.
Every machine instruction is an instance of Instr. Each has
an opcode and most have operands, representing their sources
(``arguments'') and destinations (``results'').
An opcode is a non-negative integer. With two exceptions, the opcode of a
machine instruction is meaningful only when interpreted with respect to an
architecture family. (The exceptions are opcode_null and
opcode_label, which are the opcodes of any null instruction or label
instruction, respectively.) The particular numbers used as opcodes are not
dictated by ISAs; they are arbitrarily assigned small integers, useful for
accessing instruction properties by table lookup. The same integer that
represents mov in an x86 instruction may be used for addq in an
Alpha instruction. The architecture-specific libraries assign identifiers
to opcodes; for example, MOV stands for mov in the x86 library
and ADDQ stands for addq in the Alpha library. (See
Section [->] for more discussion of opcodes.)
The get_opcode function returns an instruction's opcode, which is
always set when the instruction is created.
In general, an instruction may have source operands and destination operands; together, these are its direct operands. However, an operand that represents an effective address calculation may itself contain operands; so an instruction can also involve indirect operands.
Machine SUIF imposes the constraints that locations read by an instruction must be explicit in its operands (though possibly indirectly), and that locations written by an instruction must be explicit destination operands. We distinguish the input operands of an instruction, which are all the values read during the instruction's execution, from the source operands of the instruction, which simply identify its direct arguments.
As an example, consider an x86 instruction that adds the contents of the
%eax register to the memory location specified by the effective address
(EA) expression 40(%esp). Even though x86 has a two-address ISA, the
Machine-SUIF representation of this instruction has two source operands, an
address-expression operand 40(%esp) and a register operand %eax,
and one destination operand, an address-expression operand 40(%esp).
[It actually has two destination operands. The second is a
register operand corresponding to the x86 condition-code register.]
But this add instruction has five inputs: the three register operands (the
direct source operand %eax and the two occurrences of %esp in the
address expressions) and two immediate operands (also in the address
expressions).
The library provides facilities for enumerating and possibly changing all the input operands of an instruction. We begin with functions that access and alter the direct operands of an instruction.
<Instr operand accessors and mutators>= (U->)
Opnd get_src(Instr*, int pos);
Opnd get_src(Instr*, OpndHandle);
void set_src(Instr*, int pos, Opnd src);
void set_src(Instr*, OpndHandle, Opnd src);
void prepend_src(Instr*, Opnd src);
void append_src(Instr*, Opnd src);
void insert_before_src(Instr*, int pos, Opnd src);
void insert_before_src(Instr*, OpndHandle, Opnd src);
void insert_after_src(Instr*, int pos, Opnd src);
void insert_after_src(Instr*, OpndHandle, Opnd src);
Opnd remove_src(Instr*, int pos);
Opnd remove_src(Instr*, OpndHandle);
int srcs_size(Instr* instr);
OpndHandle srcs_start(Instr*);
OpndHandle srcs_last(Instr*);
OpndHandle srcs_end(Instr*);
Opnd get_dst(Instr*);
Opnd get_dst(Instr*, int pos);
Opnd get_dst(Instr*, OpndHandle);
void set_dst(Instr*, Opnd dst);
void set_dst(Instr*, int pos, Opnd dst);
void set_dst(Instr*, OpndHandle, Opnd dst);
void prepend_dst(Instr*, Opnd dst);
void append_dst(Instr*, Opnd dst);
void insert_before_dst(Instr*, int pos, Opnd dst);
void insert_before_dst(Instr*, OpndHandle, Opnd dst);
void insert_after_dst(Instr*, int pos, Opnd dst);
void insert_after_dst(Instr*, OpndHandle, Opnd dst);
Opnd remove_dst(Instr*, int pos);
Opnd remove_dst(Instr*, OpndHandle);
int dsts_size(Instr*);
OpndHandle dsts_start(Instr*);
OpndHandle dsts_last(Instr*);
OpndHandle dsts_end(Instr*);
In the capsule summaries of the above functions, place represents
a sequence position, which is either a zero-based integer or an
OpndHandle:
get_src(instr, place)returns the source ofinstratplace.set_src(instr, place, src)makessrcthe source ofinstratplace.prepend_src(instr, src)insertssrcat the beginning ofinstr's sources.append_src(instr, src)insertssrcat the end ofinstr's sources.insert_before_src(instr, place, src)insertssrcbeforeplaceininstr's sources.insert_after_src(instr, place, src)insertssrcafterplaceininstr's sources.remove_src(instr, place)removes and returns the operand atplaceininstr's sources.srcs_size(instr)returns the number of source operands ofinstr.srcs_start(instr)returns a handle on the first source ofinstr.srcs_last(instr)returns a handle on the last source operand ofinstr.srcs_end(instr)returns the sentinel handle forinstr's sources.
get_dst(instr, pos)returns the destination ofinstrat positionpos. (posdefaults to 0 if omitted.)set_dst(instr, pos, dst)replaces the destination ofinstrat positionposbydst. (posdefaults to 0 if omitted.)prepend_dst(instr, dst)insertsdstat the beginning ofinstr's destinations.append_dst(instr, dst)insertsdstat the end ofinstr's destinations.insert_before_dst(instr, place, dst)insertsdstbeforeplaceininstr's destinations.insert_after_dst(instr, place, dst)insertsdstafterplaceininstr's destinations.remove_dst(instr, place)removes and returns the operand atplaceininstr's destinations.dsts_size(instr)returns the number of destination operands ofinstr.dsts_start(instr)returns a handle on the first destination ofinstr.dsts_end(instr)returns the sentinel place forinstr's destinations.
The srcs_size and dsts_size functions simply return the size of
the underlying operand sequences. They do not necessarily represent
the semantics of the instruction's opcode. If set_src or
set_dst is called with an index greater than or equal to the
current sequence size, the sequence is extended automatically.
Functions get_dst and set_dst each have variants in
which the operand number can be omitted because the case of
single-destination instructions is so common.
The indirect operands of an instruction can be accessed or changed by first fetching a direct address operand and then operating on that, using methods to be described in Section [->].
Some instructions have constituents that are neither sources nor
destinations. These are managed by functions in the OPI that operate on
instructions. Control-transfer instructions usually have target labels,
for example; they are not operands, but separate attributes. These target
symbols are accessed and modified by the OPI functions get_target and
set_target (Section [->]). A
code label is represented by a special instruction that marks its position
in the instruction sequence. It has no operands. Its constituent label is
accessed and modified by the OPI functions get_label and set_label.
InstrWe refer to functions in the OPI that create new instances of objects as ``creation functions'', or simply creators. A machine instruction creator takes an opcode and possibly some operands, and it produces a machine instruction.
We divide instructions into broad categories and provide creators for each. Here's a summary of the breakdown and the mnemonics used for the categories.
alm) Arithmetic, logical, and memory instructions
alu) Arithmetic and logical
mem) Load and store
cti) Control-transfer instructions
label) Label instructions
dot) Assembler pseudo-operations [
Many assemblers use a leading period (``.'') to
identify non-code directives.]
The purpose of defining categories is two-fold. It allows us to provide creators that are convenient to use because their argument types and numbers are appropriate for the kind of instruction being created. It also allows for an implementation in which different categories may have different representations.
Not every real machine instruction falls neatly into one of the above
categories, of course. The control-transfer instructions (cti) are
the instructions that modify the program counter non-trivially. They
include conditional and unconditional branches and function calls. Each
contains a symbol that represents the transfer target.
The instruction categories aren't exclusive. On some machines, a
control-transfer instruction might perform arithmetic, so it might have
side effects other than modifying the program counter. Furthermore, a
program transformation may change an instruction from a pure ALU
operation to one that both computes a value and stores it in memory.
When creating an instruction, you pick the category that most closely
matches the need. If an instruction needs more operands than the
provided creation function accepts, you add them separately. The only
constraints to be aware of are pretty obvious: an active instruction can
never acquire a label, an instruction that needs a transfer target
(i.e., a target symbol) must be created as a control-transfer
instruction, and so on.
Here's are the prototypes of the instruction creators provided in the
machine library. Their names include the category mnemonics listed
above. Each returns a result of type Instr*.
<Instr creation functions>= (U->)
Instr* new_instr_alm(int opcode);
Instr* new_instr_alm(int opcode, Opnd src);
Instr* new_instr_alm(int opcode, Opnd src1, Opnd src2);
Instr* new_instr_alm(Opnd dst, int opcode);
Instr* new_instr_alm(Opnd dst, int opcode, Opnd src);
Instr* new_instr_alm(Opnd dst, int opcode, Opnd src1, Opnd src2);
Instr* new_instr_cti(int opcode, Sym *target);
Instr* new_instr_cti(int opcode, Sym *target, Opnd src);
Instr* new_instr_cti(int opcode, Sym *target, Opnd src1, Opnd src2);
Instr* new_instr_cti(Opnd dst, int opcode, Sym *target);
Instr* new_instr_cti(Opnd dst, int opcode, Sym *target, Opnd src);
Instr* new_instr_cti(Opnd dst, int opcode, Sym *target,
Opnd src1, Opnd src2);
Instr* new_instr_label(LabelSym *label);
Instr* new_instr_dot(int opcode);
Instr* new_instr_dot(int opcode, Opnd src);
Instr* new_instr_dot(int opcode, Opnd src1, Opnd src2);
Note that the opcode always separates the destination from the sources, if any. The only difference between two overloadings with the same name is that they allow different numbers of operands to be put in the created instruction. Of course, the number can always be adjusted later. To obtain an instruction with more than one destination or more than two sources, you must use one of the above creators and then add operands to the instruction that it returns.
Recall our example of an x86 add instruction. Suppose value is the
operand representing register %eax (which holds the value to be added
in) and addr is the address operand standing for 40(%esp).
Suppose that body is an InstrList* that we are extending as we
generate code, created perhaps as follows:
InstrList *body = new_instr_list();
Then the add instruction might be created and appended like this:
[Still ignoring the setting of the condition-code register.]
append(body, new_instr_alm(addr, ADD, addr, value));
(Here ADD is the x86 opcode for addition.)
On a load/store machine like the Alpha, the same operation might take three
instructions and an extra register. Let tmp be the operand
representing a scratch register. Then the sequence to accomplish the same
add might be:
append(body, new_instr_alm(tmp, LDQ, addr));
append(body, new_instr_alm(tmp, ADDQ, tmp, value));
append(body, new_instr_alm(addr, STQ, tmp));
InstrThe OPI provides Boolean functions to use when your analysis or optimization pass is trying to detect a particular kind of instruction (e.g., a move instruction). Some of these have target-independent semantics.
Others make use of the prevailing target context to inspect the instruction passed to them in a machine-specific way. As an OPI user, you don't have to know which is which. As an extender, you may, and this is covered in Section [->].
<Instr predicates>= (U->)
bool is_null(Instr*);
bool is_label(Instr*);
bool is_dot(Instr*);
bool is_mbr(Instr*);
bool is_indirect(Instr*);
bool is_cti(Instr*);
bool reads_memory(Instr*);
bool writes_memory(Instr*);
bool is_builtin(Instr*);
bool is_ldc(Instr*);
bool is_move(Instr*);
bool is_cmove(Instr*);
bool is_predicated(Instr*);
bool is_line(Instr*);
bool is_ubr(Instr*);
bool is_cbr(Instr*);
bool is_call(Instr*);
bool is_return(Instr*);
bool is_binary_exp(Instr*);
bool is_unary_exp(Instr*);
bool is_commutative(Instr*);
bool is_two_opnd(Instr*);
bool is_param_init(Instr*);
Their capsule summaries:
is_null(instr)returns true ifinstris a null instruction.is_label(instr)returns true ifinstris a label instruction.is_dot(instr)returns true ifinstris a pseudo-op instruction.is_mbr(instr)returns true ifinstris a multi-way branch instruction.is_indirect(instr)returns true ifinstris an indirect-jump instruction.is_cti(instr)returns true ifinstris a control-transfer instruction.
reads_memory(instr)returns true ifinstrreads memory.writes_memory(instr)returns true ifinstrwrites memory.
is_builtin(instr)returns true ifinstrrequires special implementation on each target platform.
is_ldc(instr)returns true ifinstris a load-constant instruction.is_move(instr)returns true ifinstris a register-move instruction.is_cmove(instr)returns true ifinstris a conditional move instruction.is_predicated(instr)returns true ifinstris a predicated instruction.is_line(instr)returns true ifinstris a source-code location instruction.
is_ubr(instr)returns true ifinstris an unconditional branch instruction.is_cbr(instr)returns true ifinstris a conditional branch instruction.is_call(instr)returns true ifinstris a call instruction.is_return(instr)returns true ifinstris a return instruction.is_binary_exp(instr)returns true ifinstris a side-effect-free binary expression.is_unary_exp(instr)returns true ifinstris a side-effect-free unary expression.is_commutative(instr)returns true ifinstrhas two source operands that can be exchanged without changing its meaning.is_two_opnd(instr)returns true ifinstris required to be in two-operand (or ``two-address'') form, i.e., if its first source operand must equal its (first) destination operand.is_param_init(instr)returns true ifinstrtransfers a procedure argument from its register or stack transmission location to the parameter variable.
A note about is_cbr above: a ``conditional branch'' instruction is
one that has two targets, one of which is an implicit fall-through
target. The latter characteristic distinguishes it from a multiway
branch that happens to have two targets. An instruction may satisfy
is_cbr even if its branch condition is statically known or if its
fall-through target is the same as its taken target.
A typical instruction satisfying is_builtin is one representing an
action like va_start in C, which is often implemented by macro
expansion.
A predicated instruction (for purposes of is_predicated) is one that
executes only if a predicate operand evaluates to true at run time. (An
instruction whose predicate is statically known to be true will not satisfy
the is_predicated test.)
The two-operand constraint is typical of arithmetic instructions on CISC machines like x86. While the physical instruction uses one operand field to express both a source and a destination, Machine SUIF uses distinct source and destination operand fields, but requires the operands they hold be equal.
Instr
In addition to the functions of Instr for accessing and
modifying operands, the OPI provides functions for getting and
setting the fields of particular kinds of instructions:
<Instr field accessors>= (U->)
int get_opcode(Instr *instr);
void set_opcode(Instr *instr, int opcode);
Sym* get_target(Instr *instr);
void set_target(Instr *instr, Sym *target);
LabelSym* get_label(Instr *instr);
void set_label(Instr *instr, LabelSym *label);
Their summaries:
get_opcode(instr)returns the opcode ofinstr.set_opcode(instr, opcode)replaces the opcode ofinstrwithopcode.get_target(instr)returns the target of aCTIinstruction.set_target(instr, target)replaces the target ofinstrwithtarget.get_label(instr)returns the label of a label instruction.set_label(instr, label)replaces the label ofinstrwithlabel.
InstrPrinting of instructions in a form acceptable to an assembler is naturally a target-specific task. It's the subject of Section [->]. Here's a function that uses the target-specific mechanism to print a single instruction, perhaps for debugging purposes.
<Instr print function>= (U->)
void fprint(FILE*, Instr*);
InstrList represents a simple sequence of instructions, so most of the
functions related to class InstrList are sequence manipulators.
<InstrList functions>= (U->)
InstrList* new_instr_list();
InstrList* to_instr_list(AnyBody*);
int instrs_size(InstrList *list);
InstrHandle instrs_start(InstrList *list);
InstrHandle instrs_last(InstrList *list);
InstrHandle instrs_end(InstrList *list);
void prepend(InstrList *list, Instr *instr);
void append(InstrList *list, Instr *instr);
void replace(InstrList *list, InstrHandle handle, Instr *instr);
void insert_before(InstrList *list, InstrHandle handle, Instr *instr);
void insert_after(InstrList *list, InstrHandle handle, Instr *instr);
Instr* remove(InstrList *list, InstrHandle handle);
Their summaries:
new_instr_list()returns a newInstrList*containing no instructions.to_instr_list(body)returns a newInstrList*after moving the contents ofbodyinto that new list, leavingbodyempty.instrs_size(list)returns the number of elements inlist.instrs_begin(list)returns a handle on the first element oflist.instrs_end(list)returns the sentinel handle forlist.prepend(list, instr)insertsinstrat the beginning oflist.append(list, instr)insertsinstrat the end oflist.replace(list, instr, handle)replaces the element athandleinlistbyinstr.insert_before(list, handle, instr)insertsinstrbeforehandleinlist.insert_after(list, handle, instr)insertsinstrafterhandleinlist.remove(list, handle)removes and returns the instruction athandleinlist.
Type InstrHandle is an abbreviation for a C++ sequence ``iterator''.
So it behaves like a pointer into a list of instructions.
<InstrHandle definition>= (U->)
typedef list<Instr*>::iterator InstrHandle;
Function to_instr_list serves to produce a ``go-between''
representation for the bodies of optimization units. To convert the body
of an optimization unit, the generic type for which is AnyBody*, to a
specific form that you need (such as Cfg*), you can apply
to_instr_list and then build your specific form from the resulting
linear list.
The instrs_ functions are so named because the sequence of instruction
pointers in an InstrList is called instrs. These functions are
frequently used; since an InstrList contains only one sequence, we
can provide shorter names for these handle-related functions without
ambiguity.
<InstrList function nicknames>= (U->)
inline int
size(InstrList *instr_list)
{
return instrs_size(instr_list);
}
inline InstrHandle
start(InstrList *instr_list)
{
return instrs_start(instr_list);
}
inline InstrHandle
last(InstrList *instr_list)
{
return instrs_last(instr_list);
}
inline InstrHandle
end(InstrList *instr_list)
{
return instrs_end(instr_list);
}
To print the instructions of an InstrList using the conventions of the
prevailing target:
<InstrList print function>= (U->)
void fprint(FILE*, InstrList*);
instr.hThe header file for instructions and instruction lists has the following outline:
<machine/instr.h>= /* file "machine/instr.h" */ <Machine-SUIF copyright> #ifndef MACHINE_INSTR_H #define MACHINE_INSTR_H #include <machine/copyright.h> #ifdef USE_PRAGMA_INTERFACE #pragma interface "machine/instr.h" #endif #include <machine/substrate.h> #include <machine/opnd.h> #include <machine/machine_ir.h> <Instroperand accessors and mutators> <InstrHandledefinition> <Instrcreation functions> <Instrfield accessors> <Instrpredicates> <Instrprint function> <InstrListfunctions> <InstrListfunction nicknames> <InstrListprint function> #endif /* MACHINE_INSTR_H */
Opnd interface
An instruction operand in Machine SUIF is an instance of class Opnd.
Whereas you always deal with instructions using a pointer (of type
Instr*), an operand is treated as a non-pointer value. Thus operand
creation functions are not called new_...; their names all have the
prefix opnd_. They return an Opnd, not an Opnd*, and you don't
need to worry about delete-ing operands when you're finished with them.
That's not to say that operands cannot have reference behavior. As
mentioned earlier, class Opnd encapsulates a pointer to a SUIF object.
If you insert a mutable operand into multiple instructions without cloning
it, then a side effect on one occurrence will affect the others. You must
avoid this if you want to reuse OPI code in settings other than Machine
SUIF.
There are several kinds of operands, and most of the operand-related functions have to do with one particular kind or another. Before going through the kinds, we describe some functions that can be applied to any operand.
To ask what kind of operand is represented by a particular Opnd value
(e.g., register operand versus address-symbol operand), you use the
get_kind function, which returns an integer indicator. As we go
through the operand kinds in the rest of this section, we'll give the
symbolic names for the various operand-kind indicators.
<Opnd common functions>= (U->) [D->]
int get_kind(Opnd);
There are also predicates for testing whether an operand is of a particular kind. Although they are applicable to any operand, we'll also list these predicates as we go through the kinds.
Every operand has a type, i.e., a TypeId that gives the type of the
value that the operand represents. You use the get_type function to
obtain this type.
<Opnd common functions>+= (U->) [<-D->]
TypeId get_type(Opnd);
The other function that all operands have in common is a replication utility.
<Opnd common functions>+= (U->) [<-D->]
Opnd clone(Opnd);
clone returns its argument unchanged unless it is of a kind that has
mutable fields. (Currently, only the address-expression operands have that
property.) In this case, it returns a copy of the argument operand, one
whose fields can be changed without affecting the original.
Two operands are equal under operator == only if their kind
and type attributes are equal and they satisfy additional conditions.
These conditions are spelled out below. The disequality operator (!=)
just inverts the equality result.
Because you sometimes need to map from operands to other types of values, we define a function that extracts a hash code from an operand.
<Opnd common functions>+= (U->) [<-D->]
size_t hash(Opnd);
For debugging purposes, there is a function for printing operands in a machine-independent manner. This is not the way operands are printed in machine-specific assembly output, of course. See Section [->] to understand more about of how that works.
<Opnd common functions>+= (U->) [<-D]
void fprint(FILE*, Opnd);
Now let's go through the different kinds of operands and the functions that relate to each kind.
These are simply placeholders. They always have void type. Any null
operand is equal to another one. There are two OPI functions for null
operands:
<null-operand functions>= (U->) Opnd opnd_null(); bool is_null(Opnd);
Synopses:
opnd_null()returns a null operand.is_null(opnd)returnstrueifopndis null.
In addition, the default constructor for class Opnd is publicly
accessible and yields a null operand.
The kind identifier for a null operand is opnd::NONE.
These are occurrences of source-language variables or compiler-generated temporary variables. (Not to be confused with virtual registers, which do not involve a symbol.)
The OPI has the following functions for variable-symbol operands:
<variable-symbol-operand functions>= (U->) Opnd opnd_var(VarSym* var); bool is_var(Opnd); VarSym* get_var(Opnd);
Synopses:
opnd_var(var)returns a variable-symbol operand referring tovar.is_var(opnd)returnstrueifopndis a variable-symbol operand.get_var(opnd)returns the variable symbol embedded inopnd.
The kind identifier for a variable-symbol operand is opnd::VAR.
Two variable-symbol operands are equal if and only if their embedded symbols
are equal. Since the type of this kind of operand is taken from the type
of the embedded variable-symbol, this definition of equality implicitly
requires equal types.
These represent machine registers, both the real architectural registers of the target machine and any virtual registers (sometimes called pseudo-registers) created by the compiler prior to register allocation. Each contains a non-negative register number and an explicit type. The real hardware registers have numbers that can be interpreted via the register description of the target machine (see Section [->]).
The OPI provides the following functions for register operands:
<register-operand functions>= (U->) Opnd opnd_reg(int reg, TypeId, bool is_virtual = false); Opnd opnd_reg(TypeId); bool is_reg(Opnd); bool is_hard_reg(Opnd); bool is_virtual_reg(Opnd); int get_reg(Opnd);
Synopses:
opnd_reg(reg, type, is_virtual)returns an operand for registerreg.opnd_reg(type)returns a new virtual register operand.is_reg(opnd)returnstrueifopndis a register.is_hard_reg(opnd)returnstrueifopndis a hardware register.is_virtual_reg(opnd)returnstrueifopndis a virtual register.get_reg(opnd)returns the register number ofopnd.
The usual way to create a virtual-register operand is simply to provide its
type; in this case, an unused virtual number is allocated and incorporated
in the new operand. To create a hard-register operand, you supply the
register number and the type. Occasionally, you need to create a
virtual-register operand with a specific number. In that case, you provide
the number, the type, and the Boolean true when calling opnd_reg.
The kind identifier for hardware-register operands is opnd::REG_HARD.
The kind identifier for virtual-register operands is opnd::REG_VIRTUAL.
Two register operands are equal if and only if they are of the same kind,
and their reg and type attributes are are pairwise equal.
There are two kinds of immediate operands: one holds integers and the
other strings. Integer immediates can represent either signed or
unsigned integer immediate values of any magnitude. The accompanying
type gives the intended precision. For floating-point immediate
operands, we use strings describing the numeric value, again paired with
a type. We also use untyped immediate string operands, though they
don't appear in operate instructions. They allow the pseudo-instruction
(dot) class, which sometimes requires string literals, to use the
same operand interface as the other instruction classes.
The OPI functions for immediate operands are as follows:
<immediate-operand functions>= (U->) Opnd opnd_immed(int, TypeId); Opnd opnd_immed(Integer, TypeId); Opnd opnd_immed(IdString, TypeId); Opnd opnd_immed(IdString); bool is_immed(Opnd); bool is_immed_integer(Opnd); bool is_immed_string(Opnd); int get_immed_int(Opnd); Integer get_immed_integer(Opnd); IdString get_immed_string(Opnd);
opnd_immed(integer, type)returns an integer immediate operand with typetype.opnd_immed(string, type)returns a floating immediate operand with typetype.opnd_immed(string)returns a string immediate operand, with no type.is_immed(opnd)returnstrueifopndis an immediate.is_immed_integer(opnd)returnstrueifopndis an integer immediate.is_immed_string(opnd)returnstrueifopndis a string immediate.get_immed_int(opnd)returns the value of an integer immediate operand as a Cint, or raises an exception if that's impossible.get_immed_integer(opnd)returns the value of an integer immediate operand.get_immed_string(opnd)returns the value of a string immediate operand.
Note that, when operand opnd satisfies is_immed_string(opnd), you
can tell whether it's numeric or not by checking its type:
get_type(opnd) returns 0 if opnd represents a
simple string literal. (In practice, the nature of the immediate operand
is nearly always apparent from the context.)
The kind identifier for an integer-immediate operand is
opnd::IMMED_INTEGER; that for a string-immediate operand is
opnd::IMMED_STRING. Two immediate operands are equal if and only
if they are of the same kind and their type and value attributes
are pairwise equal.
The remaining kinds of builtin operands are address symbols and address
expressions, which together we call address operands. An address
operand represents the effective-address (EA) calculation performed during
a machine instruction to generate a memory address. The type of an address
operand is always a pointer type. Such an operand is created with the
pointer-to-void type appropriate for the compilation target. (This is
the same TypeId that results from evaluating type_ptr. See
Section [->].)
It is often useful to be able to determine the referent type of an
address operand, i.e., the type of the value obtained by dereferencing the
address that the operand represents. Obviously, this information could be
incorporated in the address-operand type if the OPI required precise
pointer-type constructors. But that would entail a good deal of pointer
type composition and decomposition at optimization time. So instead,
address operands carry an additional type attribute called deref_type.
You access and update it it using:
<address-operand functions>= (U->) [D->] TypeId get_deref_type(Opnd); void set_deref_type(Opnd, TypeId);
If non-null, this attribute gives the type of the dereferenced value. (We explain below when and why the referent type attribute may be null.)
There is a predicate satisfied only by an address operand:
<address-operand functions>+= (U->) [<-D] bool is_addr(Opnd);
The simplest kind of address operand is the address symbol, which represents the address of a variable symbol or a code label symbol.
The OPI functions for address symbols are:
<address-symbol-operand functions>= (U->) Opnd opnd_addr_sym(Sym* sym); bool is_addr_sym(Opnd); Sym* get_sym(Opnd addr_sym);
Synopses:
opnd_addr_sym(sym)returns an address symbol based onsym.is_addr_sym(opnd)returnstrueifopndis an address symbol.get_sym(opnd)returns the symbol underlyingopnd.
The kind identifier for an address-symbol operand is opnd::ADDR_SYM.
Two address-symbol operands are equal if and only if they have equal
sym values.
The deref_type of an address symbol is always derived from the
underlying symbol. If it's a variable or procedure symbol, then the
deref_type is the type of the variable or procedure. If it's a label
symbol, then get_deref_type returns NULL.
Recall our earlier example of an x86 add-to-memory instruction, with
addr representing the address of the memory location that is
incremented by value. If the memory location is that of variable
foo, then operand addr would be an address symbol constructed from
the VarSym* for foo (which we might call var_foo). The code
might look like this:
Opnd addr = opnd_addr_sym(var_foo);
append(body, new_instr_alm(addr, ADD, addr, value));
There are several varieties of address expression, corresponding to the
addressing modes used in hardware. We use address operands to represent
whole EA calculations. Like address symbols, all address expression
operands are created with a type attribute equal to type_ptr.
The unique characteristics of address expressions are that they embed other
operands and they are mutable: you can replace the operands that make up an
address expression. For example, a ``base-plus-displacement'' operand
represents the address that results at run time from adding a fixed
displacement to the contents of a base register. Earlier, for instance, we
used the example of an x86 stack cell located at $esp + 40. The
corresponding address-expression operand would contain the register operand
for $esp as its base part and an immediate operand for the number
40 as its displacement part.
A typical program transformation that could change the constituent operands of an address expression is register allocation. A base-plus-displacement operand with a virtual register as its base would be modified when the virtual register is allocated to a physical one.
Because address expressions are mutable, you should be aware that the
implementation allows the mutable parts to be shared between occurrences.
Machine SUIF doesn't force you to maintain separate copies, since this
would often be semantically pointless. In our earlier example of the x86
add-to-memory instruction that updates stack location 40(%esp), we
didn't bother to clone the address expression before using it a second
time:
append(body, new_instr_alm(addr, ADD, addr, value));
Neither its base register %esp nor its displacement 40 will be
affected by a register allocator, and in any case, the hardware sees addr
as a single operand, not as two separate once. Be warned, though, that
Machine SUIF doesn't guarantee to preserve sharing patterns that you may
establish in this way. For example, when an instruction
is cloned, i.e., replicated, its address expressions are replicated
individually.
To produce the variable of type Opnd called addr in the above
example, we might write:
Opnd esp = opnd_reg(REG_esp, type_ptr);
Opnd i40 = opnd_immed(40, type_s32);
Opnd addr = BaseDispOpnd(esp, i40, type_s32);
Here REG_esp is an integer variable previously set to the register
number for %esp (see Section [->]). It is incorporated
into a register operand esp with the generic pointer type that is
appropriate for the current target; the OPI calls this type_ptr.
Next, the displacement operand i40 is created and given a signed 32-bit
integral type. Finally, the address expression addr is constructed
from these base and displacement suboperands. The third argument to the
constructor BaseDispOpnd is the deref_type, i.e., the type of the
value in the address that addr refers to.
Sometimes an address expression is used purely for address computation; the
referent type is unknown and unneeded. For those cases, the OPI allows you
to omit it, which leaves it NULL. For example, in Alpha code, a stack
frame is allocated by subtracting a constant from the stack-pointer
register. This is usually expressed using a load-address instruction:
Opnd sp = opnd_reg(REG_sp, type_ptr); // stack pointer reg ($sp)
Opnd sz = opnd_immed(-80, type_s32); // -(frame size)
append(body, new_instr_alm(sp, LDA, BaseDispOpnd(sp, sz)));
where LDA is the Alpha load-address opcode.
Machine SUIF includes these functions for testing and creating address expressions:
<address-expression-operand functions>= (U->) bool is_addr_exp(Opnd); Opnd opnd_addr_exp(int kind); Opnd opnd_addr_exp(int kind, TypeId deref_type);
is_addr_exp(opnd)returnstruewhenopndis an address expression.opnd_addr_exp(kind, deref_type)returns an address expression operand of kindkindreferring to a value of typederef_type.
The kind argument to opnd_addr_exp must be one associated with a
specific address-expression kind, e.g., one of those in
Table [->]. There is no way to create a ``generic''
address expression.
The deref_type argument to opnd_addr_exp may be omitted, in which
case the resulting operand's referent type is unspecified (and it equals
zero when tested).
The function opnd_addr_exp described above is not part of the
OPI. It's meant for extenders of the system. In optimization passes or
libraries, you should use class AddrExpOpnd and its subclasses as the
interface to address expressions.
<class AddrExpOpnd>= (U->)
class AddrExpOpnd : public Opnd {
public:
AddrExpOpnd() { }
AddrExpOpnd(const Opnd&);
AddrExpOpnd(Opnd&);
AddrExpOpnd(int kind, TypeId deref_type = 0)
: Opnd(opnd_addr_exp(kind, deref_type)) { }
TypeId get_deref_type() const;
int srcs_size() const;
OpndHandle srcs_start()const ;
OpndHandle srcs_end() const;
Opnd get_src(int pos) const;
Opnd get_src(OpndHandle handle) const;
void set_src(int pos, Opnd src);
void set_src(OpndHandle handle, Opnd src);
};
Here
AddrExpOpnd(kind, deref_type)produces a new address expression with the given kind and referent type. (The latter is optional.)srcs_size()returns the size of the address expression'ssrcssequence.srcs_start()gives a handle on the first element ofsrcs, if any.srcs_end()gives the end-sentinel ofsrcs.get_src(p)returns the source of the address expression at positionp, which may be a zero-based integer or a handle.set_src(p, src)substitutessrcfor the source of the address expression at positionp(which may be a zero-based integer or a handle).
Both get_src and set_src extend the srcs sequence if necessary.
Just as an instruction contains a sequence of direct source operands that
we call its srcs field, every address expression has a srcs
sequence, and the same functions for scanning, accessing, and changing the
elements of the sequence apply. For each kind of address expression, there
is a subclass of Opnd that allows referring to source operands by more
descriptive field names, such as base or disp, but these fields are
just elements of the overall source sequence.
Although address expressions describe how to compute the value of an effective address, they don't encode side effects that might be associated with a particular addressing mode, such as post-increment.
For two address expression operands to be equal under the == operator,
they must be of the same kind and have the same deref_type, and their
source operands must be equal in number and pairwise equal under ==.
The AddrExpOpnd interface is convenient for operations that are
indifferent to the specific kind of an address expression. A register
allocator, for instance, may make substitutions among the components of an
address expression without needing to know the particular kind. For other
purposes, though, a specific interface is needed for each kind of address
expression that the target machine supports.
The specific kinds of address expression that the OPI defines are summarized in Table [->], which matches each kind indicator with the corresponding form of address expression.
opnd::SYM_DISPaddress-symbol + displacement opnd::INDEX_SYM_DISPindex-register + address-symbol + displacement opnd::BASE_DISPbase + displacement opnd::BASE_INDEXbase + index opnd::BASE_INDEX_DISPbase + index + displacement opnd::INDEX_SCALE_DISPindex×scale + displacement opnd::BASE_INDEX_SCALE_DISPbase + index×scale + displacement
Address expression categories. [*] ------
index-register is a register operand address-symbol is an address-symbol operand base and index are either register or variable-symbol operands; the latter stand for variables to be assigned to registers scale is an immediate operand containing an unsigned integer (typically a small power of 2) displacement is an immediate operand containing a signed integer
srcs sequence, so that it can be fetched and replaced using
mnemonically-named methods. Here are the field names:
addr_sym | an address symbol |
disp | an integer immediate |
index | a register operand |
base | a register or variable-symbol operand |
scale | an integer immediate |
For each kind of address expression, we now describe the subclass of
Opnd that gives access to the applicable fields through its
methods. For each of these kinds, there is an operand-kind identifier, a
creation function (prefix opnd_) and a predicate (prefix is_).
This address form represents a fixed displacement (disp) from the
memory address of a symbol (addr_sym). Its Opnd subclass is
SymDispOpnd. Its kind identifier is opnd::SYM_DISP.
Class SymDispOpnd gives the methods for composing, inspecting and
changing symbol-plus-displacement operands:
<class SymDispOpnd>= (U->)
class SymDispOpnd : public AddrExpOpnd {
public:
SymDispOpnd(Opnd addr_sym, Opnd disp, TypeId deref_type = 0);
SymDispOpnd(const Opnd&);
SymDispOpnd(Opnd&);
Opnd get_addr_sym() const;
void set_addr_sym(Opnd);
Opnd get_disp() const;
void set_disp(Opnd);
};
bool is_sym_disp(Opnd);
This address form combines the run-time value of an index register with
a fixed displacement and the memory address of a symbol. Its kind identifier is
opnd::INDEX_SYM_DISP.
Class IndexSymDispOpnd gives the methods for composing, inspecting and
changing index-plus-symbol-plus-displacement operands:
<class IndexSymDispOpnd>= (U->)
class IndexSymDispOpnd : public AddrExpOpnd {
public:
IndexSymDispOpnd(Opnd index, Opnd addr_sym, Opnd disp,
TypeId deref_type = 0);
IndexSymDispOpnd(const Opnd&);
IndexSymDispOpnd(Opnd&);
Opnd get_index() const;
void set_index(Opnd);
Opnd get_addr_sym() const;
void set_addr_sym(Opnd);
Opnd get_disp() const;
void set_disp(Opnd);
};
bool is_index_sym_disp(Opnd);
This address form combines the value of a base register with a fixed
displacement. Its Opnd subclass is BaseDispOpnd. Its kind
identifier is opnd::BASE_DISP. The base operand may either be a
register operand or a variable symbol that represents a register candidate.
Class BaseDispOpnd gives the methods for composing, inspecting and
changing base-plus-displacement operands:
<class BaseDispOpnd>= (U->)
class BaseDispOpnd : public AddrExpOpnd {
public:
BaseDispOpnd(Opnd base, Opnd disp, TypeId deref_type = 0);
BaseDispOpnd(const Opnd&);
BaseDispOpnd(Opnd&);
Opnd get_base() const;
void set_base(Opnd);
Opnd get_disp() const;
void set_disp(Opnd);
};
bool is_base_disp(Opnd);
This address form combines the values two registers, base and index. Its
Opnd subclass is BaseIndexOpnd. Its kind identifier is
opnd::BASE_INDEX.
Class BaseIndexOpnd gives the methods for composing, inspecting and
changing base-plus-index operands:
<class BaseIndexOpnd>= (U->)
class BaseIndexOpnd : public AddrExpOpnd {
public:
BaseIndexOpnd(Opnd base, Opnd index, TypeId deref_type = 0);
BaseIndexOpnd(const Opnd&);
BaseIndexOpnd(Opnd&);
Opnd get_base() const;
void set_base(Opnd);
Opnd get_index() const;
void set_index(Opnd);
};
bool is_base_index(Opnd);
This address form combines two registers (base and index) with a fixed
displacement. Its Opnd subclass is BaseIndexDispOpnd. Its kind
identifier is opnd::BASE_INDEX_DISP.
Class BaseIndexDispOpnd gives the methods for composing, inspecting and
changing base-plus-index-plus-displacement operands:
<class BaseIndexDispOpnd>= (U->)
class BaseIndexDispOpnd : public AddrExpOpnd {
public:
BaseIndexDispOpnd(Opnd base, Opnd index, Opnd disp, TypeId deref_type = 0);
BaseIndexDispOpnd(const Opnd&);
BaseIndexDispOpnd(Opnd&);
Opnd get_base() const;
void set_base(Opnd);
Opnd get_index() const;
void set_index(Opnd);
Opnd get_disp() const;
void set_disp(Opnd);
};
bool is_base_index_disp(Opnd);
This address form multiplies an index register's value by a fixed scale
factor and adds a fixed displacement. Its Opnd subclass is
IndexScaleDispOpnd. Its kind identifier is opnd::INDEX_SCALE_DISP.
<class IndexScaleDispOpnd>= (U->)
class IndexScaleDispOpnd : public AddrExpOpnd {
public:
IndexScaleDispOpnd(Opnd index, Opnd scale, Opnd disp,
TypeId deref_type = 0);
IndexScaleDispOpnd(const Opnd&);
IndexScaleDispOpnd(Opnd&);
Opnd get_index() const;
void set_index(Opnd);
Opnd get_scale() const;
void set_scale(Opnd);
Opnd get_disp() const;
void set_disp(Opnd);
};
bool is_index_scale_disp(Opnd);
This address form combines the value of a base register with the result of
scaling an index register and adding a fixed displacement. Its Opnd
subclass is BaseIndexScaleDispOpnd. Its kind identifier is
opnd::BASE_INDEX_SCALE_DISP.
<class BaseIndexScaleDispOpnd>= (U->)
class BaseIndexScaleDispOpnd : public AddrExpOpnd {
public:
BaseIndexScaleDispOpnd(Opnd base, Opnd index, Opnd scale, Opnd disp,
TypeId deref_type = 0);
BaseIndexScaleDispOpnd(const Opnd&);
BaseIndexScaleDispOpnd(Opnd&);
Opnd get_base() const;
void set_base(Opnd);
Opnd get_index() const;
void set_index(Opnd);
Opnd get_scale() const;
void set_scale(Opnd);
Opnd get_disp() const;
void set_disp(Opnd);
};
bool is_base_index_scale_disp(Opnd);
OpndCatalog
It is often useful in program analysis and optimization to map operands to
a dense range of natural numbers. Class OpndCatalog is an abstract
interface for such a map. For different problems, it is realized by
different concrete subclasses. In bit-vector data-flow problems, the
numbers assigned to operands are often called slots, meaning
positions in the bit vectors. Here we'll call them indices.
Every OpndCatalog maps operands to integer indices, but not every one
has to store the inverse map, which gives the operand corresponding to an
index. The decision whether to record the inverse map is made when the
catalog object is constructed. One benefit of keeping the inverses is that
they allow the catalog's contents to be printed. So even when a particular
optimization algorithm doesn't need the inverse map, its implementation may
save it anyway during debugging, in order to activate the catalog's
print method.
<classOpndCatalog>= (U->) class OpndCatalog { public: virtual ~OpndCatalog(); virtual int size() const = 0; int num_slots() const { return size(); } // deprecated virtual bool enroll(Opnd, int *index = NULL) = 0; virtual bool lookup(Opnd, int *index = NULL) const = 0; virtual void print(FILE* = stdout) const; virtual Opnd inverse(int index) const; <OpndCatalogprotected parts> };
Here's what the above methods do.
size() | Returns the total number of indices allocated so far for all enrolled operands. |
num_slots() | A deprecated synonym for size(). |
| enroll(o, i) | Tries to put operand o under management. Returns
true exactly when o has not been
enrolled before and is entered successfully
(not filtered out). In addition, the optional
index pointer i serves as an output
variable. If i is non-null, the index
for operand o (if it has one) is stored
in the location that i points to. This
return of o's index via i
occurs whether o is newly enrolled or was in
the catalog previously. |
| lookup(o, i) | Returns true if operand o already in the
catalog. In that case, and if the optional
index pointer i is non-null, the index
for o is stored into the location i
points to. Never makes a new entry in the
catalog. |
inverse(i) | If the catalog holds the optional inverse map of
indices to operands, inverse returns the operand
associated with index i, which must be less
than the number of operands enrolled. Otherwise,
it returns a null operand. |
print(s) | If the catalog records the inverse map of operands
enrolled, print lists each member in order of
entry on the output stream s, preceded by the
index assigned to it.
|
Opnd implementation
<Opnd definition>= (U->)
class Opnd {
public:
Opnd();
Opnd(const Opnd &other) { o = other.o; }
Opnd(IrOpnd *other_o) { o = other_o; }
Opnd & operator=(const Opnd &other) { o = other.o; return *this; }
~Opnd() { }
bool operator==(const Opnd &other) const;
bool operator!=(const Opnd &other) const { return !(*this == other); }
operator IrOpnd*() { return o; }
operator bool();
protected:
IrOpnd *o;
};
Type OpndHandle is used for scanning the srcs field of an address
expression. The implementation of this field has type
suif_vector<IrOpnd>. Therefore, OpndHandle is an alias for the
iterator type associated with this sequence type.
<OpndHandle definition>= (U->)
typedef suif_vector<IrOpnd*>::iterator OpndHandle;
<focus functions>= (U->) void focus(FileBlock*); void focus(OptUnit*); void defocus(OptUnit*);
<scope management>= (U->) extern FileBlock *the_file_block; extern ScopeTable *the_file_scope; extern OptUnit *the_local_unit; extern ScopeTable *the_local_scope;
<virtual-register management>= (U->) extern int the_vr_count; int next_vr_number();
OpndCatalog.
Since OpndCatalog is an interface, meant to be subclassed, it has no
public constructor. Its protected constructor takes an option Boolean
argument record that, when explicitly set to true, causes the
catalog to remember the inverse map from indices to operands. This map is
represented as a pointer to a vector. The pointer is NULL when the
inverse map is not saved. A second optional argument is just for
efficiency when the map is recorded. It specifies the initial capacity of
the vector (i.e., space for elements that will be appended to it later).
The protected enroll_inverse method is invoked by the implementation
of enroll when a new association is being added to the catalog. It
takes care of recording the inverse map, if one is being kept.
<OpndCatalog protected parts>= (<-U)
protected:
OpndCatalog(bool record = false, unsigned roll_reserve = 100);
void enroll_inverse(unsigned index, Opnd);
private:
Vector<Opnd> *roll;
<storage measurement>= (U->) void audit_opnds(FILE*, const char *heading);
opnd.hThe header file for operands has the following outline:
<machine/opnd.h>=
/* file "machine/opnd.h" */
<Machine-SUIF copyright>
#ifndef MACHINE_OPND_H
#define MACHINE_OPND_H
#include <machine/copyright.h>
#ifdef USE_PRAGMA_INTERFACE
#pragma interface "machine/opnd.h"
#endif
#include <machine/substrate.h>
class IrOpnd;
namespace opnd {
enum { NONE,
REG_HARD,
REG_VIRTUAL,
VAR,
IMMED_INTEGER,
IMMED_STRING,
ADDR_SYM,
SYM_DISP,
INDEX_SYM_DISP,
BASE_DISP,
BASE_INDEX,
BASE_INDEX_DISP,
INDEX_SCALE_DISP,
BASE_INDEX_SCALE_DISP,
};
} // namespace opnd
#define LAST_OPND_KIND opnd::BASE_INDEX_SCALE_DISP
<OpndHandle definition>
<Opnd definition>
<Opnd common functions>
<null-operand functions>
<variable-symbol-operand functions>
<register-operand functions>
<immediate-operand functions>
<address-operand functions>
<address-symbol-operand functions>
<address-expression-operand functions>
<class AddrExpOpnd>
<class SymDispOpnd>
<class IndexSymDispOpnd>
<class BaseDispOpnd>
<class BaseIndexOpnd>
<class BaseIndexDispOpnd>
<class IndexScaleDispOpnd>
<class BaseIndexScaleDispOpnd>
<focus functions>
<scope management>
<storage measurement>
<virtual-register management>
<class OpndCatalog>
#endif /* MACHINE_OPND_H */
The parlance of compiler infrastructure overloads a number of terms, such as ``type'', ``variable'', and ``procedure'', which makes it difficult to talk clearly about the implementation of a system like Machine SUIF. When we say ``OPI type'' or ``SUIF type'' or ``C++ type'', we are talking about artifacts of our compiler's implementation. But often we use ``type'' to mean either a property of the program being compiled, or the object in the compiler that represents that property. As the length of the preceding sentence indicates, we don't have nice crisp terminology for the latter type of types, except to call them ``source types'', which isn't great. It might work to say ``type object'' when referring to elements of the infrastructure that represent types in the program being compiled, but the OPI attempts to make a distinction between IR objects, which are accessed indirectly via explicity pointers, and potentially lighter-weight things like operands and types, which might not need to involve pointers.
The OPI uses the term type identifier (and the name TypeId) for
this lightweight type representation.
The SUIF system provides us with a rich type system. As much as possible, we attempt to maintain type information when converting from a SUIF IR to the Machine-SUIF IR and when performing optimizations in Machine SUIF. Often, however, we are interested only in some simple type information. For these times, we provide several predefined type variables for your use.
The first set of predefined type variables are those that are target
independent. We declare these type variables in
<target-independent types>. Each of these types is aligned.
type_v0 describes a void value of size 0 bits.
type_s8, type_s16, type_s32, and type_s64
describe aligned, signed integers of the specified bit sizes.
type_u8, type_u16, type_u32, and type_u64
describe aligned, unsigned integers of the specified bit sizes.
type_f32, type_f64, and type_f128 describe
aligned, floating-point values of the specified bit sizes.
type_addr is a function that returns the type ``pointer to
type_v0''. The size of this type depends upon the target. This occurs
so frequently in code, that we define the macro type_ptr to be
equivalent to type_addr(). As mentioned earlier, this is the type that
we use as the type of an address expression.
The following are predefined type variables that are globally available
to any Machine-SUIF pass. These target-independent types are aligned.
They are initialized in machine/init.cc.
<target-independent types>= (U->) extern TypeId type_v0; // void extern TypeId type_s8; // signed ints extern TypeId type_s16; extern TypeId type_s32; extern TypeId type_s64; extern TypeId type_u8; // unsigned ints extern TypeId type_u16; extern TypeId type_u32; extern TypeId type_u64; extern TypeId type_f32; // floats extern TypeId type_f64; extern TypeId type_f128; extern TypeId type_p32; // pointers extern TypeId type_p64; void attach_opi_predefined_types(FileSetBlock*); void set_opi_predefined_types(FileSetBlock*);
Function set_opi_predefined_types fills in the target-independent
types, which it obtains from the generic_types annotation of a
file_set_block. This note is created once at the time the Machine-SUIF
representation of a file set is first created (by function
attach_opi_predefined_types), and it is carried along
as the file set is transformed. Using this note is an efficient way
to avoid creating redundant types in a global symbol
table.
A pass typically calls set_opi_predefined_types during its
do_file_set_block method.
For now Machine SUIF has one target-dependent type parameter, namely the
type of a generic pointer or address on the target machine. You fetch it
from the target context by calling type_addr(). To permit a uniform
style between the target-independent and the target-dependent types, we
define a macro, type_ptr that expands to type_addr(). Thus in both
cases a reference looks like a simple constant.
<target-dependent type>= (U->) #define type_ptr type_addr() TypeId type_addr();
types.hThe interface file has the following layout:
<machine/types.h>= /* file "machine/types.h" */ <Machine-SUIF copyright> #ifndef MACHINE_TYPES_H #define MACHINE_TYPES_H #include <machine/copyright.h> #ifdef USE_PRAGMA_INTERFACE #pragma interface "machine/types.h" #endif #include <machine/substrate.h> <target-independent types> <target-dependent type> void fprint(FILE*, TypeId); #endif /* MACHINE_TYPES_H */
In general, a machine opcode value uniquely identifies a particular operation on a particular machine. On different machines, a specific value will (most-likely) correspond to different operations. In other words, an opcode value does not encode any target information beyond the target-relative operation. You must interpret the opcode value in the context of a particular target. The same interpretation rules apply for Machine-SUIF opcodes.
In Machine SUIF, an opcode is an integer. When you define an
opcode for a machine instruction, you must use the opcode enumeration
appropriate for your current target. Each target architecture defines
its own extensible opcode enum in an opcodes.h file. All
targets of the same architecture family use the same opcode enum.
We provide an OPI function, called target_implements, that allows
you to determine if an opcode is supported on your current target.
<opcode OPI>= (U->) [D->] bool target_implements(int opcode);
In Machine SUIF, an opcode has an associated name. It is the string
by which the current target's assembler recognizes the opcode. The
opcode-to-name mapping is one-to-many since an opcode's name may vary from
one vender-OS to another. We provide an OPI function, called
opcode_name, that you can use to get an opcode's target-appropriate
name.
<opcode OPI>+= (U->) [<-D->] char* opcode_name(int opcode);
Given an opcode enum, if you know that you want to generate
SUIFvm instructions, you can write:
Instr *mi = new_instr_alm(d_opnd, MOV, s_opnd);
Or, if you know that you want to generate an Alpha integer move
instruction, you can write:
Instr *mi = new_instr_alm(d_opnd, MOV, s_opnd);
In general, having knowledge of an architecture's opcode enum is
sufficient to write a target-specific pass or function, but not very useful
for the development of parameterized passes. To create an instruction that
is specific to a target without having to know the target at
pass-development time, the OPI provides some target-specific opcode
generators.
For example, opcode_move returns the move opcode appropriate for
your current target:
Instr *mi = new_instr_alm(d_opnd, opcode_move(d_type), s_opnd);
This generator is called a typed opcode generator because you must
provide a type to get a type-appropriate opcode. In other words,
opcode_move uses the d_type parameter to determine if it should
generate an integer or floating-point move opcode.
The OPI calls for provides three typed opcode generators:
<opcode OPI>+= (U->) [<-D->] int opcode_move(TypeId); int opcode_load(TypeId); int opcode_store(TypeId);
where
opcode_move: generates a type- and target-appropriate move opcode;
opcode_load: generates a type- and target-appropriate load opcode;
opcode_store: generates a type- and target-appropriate store opcode;
and the following untyped opcode generators:
<opcode OPI>+= (U->) [<-D->] int opcode_line(); int opcode_ubr();
where
opcode_line: generates a target-appropriate line pseudo-op opcode.
opcode_ubr: generates a target-appropriate unconditional branch
opcode.
The OPI also provides the function opcode_cbr_inverse which takes a
conditional branch opcode and returns the opcode checking the opposite
condition.
<opcode OPI>+= (U->) [<-D->] int opcode_cbr_inverse(int opcode);
Finally, there are two global opcodes, which are the same across all architectures:
<opcode OPI>+= (U->) [<-D] const int opcode_null = 0; const int opcode_label = 1;
Since these are considered part of each architecture's opcode space, the
first target-specific opcode in each opcode enum should start with
value 2.
opcodes.hThe interface file has the following layout:
<machine/opcodes.h>= /* file "machine/opcodes.h" */ <Machine-SUIF copyright> #ifndef MACHINE_OPCODES_H #define MACHINE_OPCODES_H #include <machine/copyright.h> #ifdef USE_PRAGMA_INTERFACE #pragma interface "machine/opcodes.h" #endif #include <machine/substrate.h> <opcode OPI> int opcode_from_name(const char *name); #endif /* MACHINE_OPCODES_H */
A Machine SUIF register allocator should be coded without hard-wiring the particulars of any target machine, but it nevertheless needs a way to access information about the target's registers. This section gives the register-description interface that you must implement when developing a target library. Its purpose is to enumerate the hardware registers, and for those that are subject to register allocation, to classify them according to the different purposes they serve in the instruction-set architecture.
A register class is a set of registers that are equally suitable for
playing a particular role in programs of the target machine. For example,
the set of registers that can be operands of an integer add instruction
comprise a register class. The members of a class are interchangeable:
whenever one of them is playing the role for which the class is defined
(e.g., the add-operand role), then it is legal to use any other member
of the class in its place. Usually, the same register class is associated
with many related instructions, e.g., the full set of integer arithmetic
and logical instructions. But this is not always the case. The Motorola
68000, for instance, has a class of address registers for addressing memory
and a class of data registers for doing certain integer computations. A
data register can't be the base register for a load instruction, and an
address register can't be the operand of a multiply instruction, so there
are disjoint classes for those distinct roles. However, the add
instruction can operate on either an address register or a data register,
so the machine has a third register class that is the union of the other
two.
The register-description interface doesn't involve a C++ class of its own.
It is made up of functions, all of whose names begin with reg_. These
correspond to virtual methods in the context interface of the machine
library, i.e., in class MachineContext (see Section [->]).
The target library provides implementations for those methods.
A register is identified by a non-negative integer whose particular value is only meaningful within the target library.
reg_count returns the number of registers in the target. Every
register identifier must be less than this number.
reg_name returns the name of the register designated by its
argument. The is the form that the target assembler expects to see.
reg_width returns the size in bits of the designated register.
reg_maximal, returns the maximal-width register that subsumes the
register given as its argument.
reg_aliases returns the set of registers that overlap the
designated register in whole or in part, including the register
itself. Register x is in reg_aliases(y) if and only if
writing a value into y can affect the value in x.
reg_allocables returns the set of identifiers for all
registers that are available for register allocation. When called
with its optional argument true, it returns the subset that have
maximal width.
reg_caller_saves returns the subset of allocable registers that
obey a caller-saves convention, i.e., that need not be preserved
by a called procedure. With optional argument true,
it returns only the maximal-width caller-saves registers.
reg_callee_saves returns the subset of allocable registers that
obey a callee-saves convention, i.e., that must be restored by
a called procedure if it changes them. With optional argument true,
it returns only the maximal-width callee-saves registers.
reg_info_print prints a description of the registers of the
current target.
<register description functions>= (U->) int reg_count(); const char* reg_name(int reg); int reg_width(int reg); int reg_maximal(int reg); const NatSet* reg_aliases(int reg); const NatSet* reg_allocables(bool maximals = false); const NatSet* reg_caller_saves(bool maximals = false); const NatSet* reg_callee_saves(bool maximals = false); void reg_info_print(FILE*);
Every register class is also identified by a non-negative integer that we call the class identifier.
<type RegClassId>= (U->)
typedef int RegClassId;
The set of classes must be closed under intersection: if two classes have
one or more members in common, then their intersection must also be a class
that is identified in this machine description. The intersection function
recognizes two distinguished class-identifier values. REG_CLASS_ANY is
the identity element for class intersection, and REG_CLASS_NONE is the
zero element.
<distinguished class identifiers>= (U->) const RegClassId REG_CLASS_ANY = -1; // universal class const RegClassId REG_CLASS_NONE = -2; // empty class
The following functions describe register classes and their relationships.
reg_class_count returns the number of classes. Every class
identifier must be less than this number.
reg_members returns a set of register numbers for the members of
the designated register class.
reg_class_intersection returns the identifier of the class that
is the intersection of its two argument classes. If one argument is
REG_CLASS_ANY, it returns the other argument. If the
intersection is empty, it returns REG_CLASS_NONE.
<register class description functions>= (U->) int reg_class_count(); const NatSet* reg_members(RegClassId); RegClassId reg_class_intersection(RegClassId, RegClassId);
Instead of mapping directly from operands to class identifiers, the class map is keyed on the operand indices assigned by an operand catalog (see Section [<-]). So it is just a vector of class identifiers, indexed by operand number.
<type RegClassMap>= (U->)
typedef Vector<RegClassId> RegClassMap;
A register candidate normally appears in more than one instruction, and its
class should reflect the most constrained role that it plays. In other
words, it is the intersection of the classes ascribed to it in the various
places where it appears. The process of classification therefore starts by
intializing every element of the class map to REG_CLASS_ANY, and at
each occurrence of a candidate operand, the corresponding map entry is
replaced by the intersection of its current value and the class determined
by the use of the operand. When the classification id finished, every
map entry for a register candidate should neither be the empty class nor
the original universal class.
reg_classify scans the operands of an instruction, using an
operand catalog to obtain an integer index for each register
candidate. It updates a class map that gives the feasible register
classes for each operand.
<allocator support functions>= (U->) [D->] void reg_classify(Instr*, OpndCatalog*, RegClassMap*);
reg_choice tries to select one register from a given class that
is also a member of a register pool, and that is not in a set of
excluded registers. Its final argument is a flag rotate indicating
whether successive choices satisfying similar criteria should
cycle through the feasible values or should be confined to as small
a collection as possible. Returns a negative result if there is no
register satisfying all the constraints.
<allocator support functions>+= (U->) [<-D->]
int reg_choice(RegClassId, const NatSet *pool, const NatSet *excluded,
bool rotate);
The OPI functions reg_spill and reg_fill allow you to define
target-specific spill-code injectors. It is usually acceptable for these
functions to introduce new virtual registers, which the allocator
recognizes as additional register candidates. Sometimes an allocator must
call reg_spill or reg_fill after register assignments have all been
made. In that case, it passes a flag (post_reg_alloc) indicating that
no new register candidates may be mentioned in the inserted code.
reg_spill inserts a sequence of instructions after marker
whose effect is to store a spilled value from src (a register) to
dst (a memory address). It returns the handle of the last
instruction inserted. When the optional argument post_reg_alloc
is true, the inserted sequence is not allowed to introduce register
candidates, such as virtual registers.
reg_fill inserts a sequence of instructions before marker
whose effect is to load a spilled value from src (a memory
address) to dst (a register). It returns the handle of the first
instruction inserted. When the optional argument post_reg_alloc
is true, the inserted sequence is not allowed to introduce register
candidates, such as virtual registers.
When implementing either of these functions for a particular target, you
should assume that the marker argument refers to an instruction that is
part of a CfgNode object.[cite bibcfg] You can reach that CFG node
using the get_parent_node function provided in the CFG library.
<allocator support functions>+= (U->) [<-D]
InstrHandle reg_fill (Opnd dst, Opnd src, InstrHandle marker,
bool post_reg_alloc = false);
InstrHandle reg_spill(Opnd dst, Opnd src, InstrHandle marker,
bool post_reg_alloc = false);