\section{Annotations}

An annotation attaches one or more values to an IR object.  Each such
association is identified by a \emph{key}.  An object can have one or more
annotations under a particular key.  You supply both the object pointer and
the key when you attach, detach, or inspect an annotation.


\paragraph{Type [[NoteKey]].}

The OPI uses type [[NoteKey]] as the type of annotation keys.  In Machine
SUIF, [[NoteKey]] is defined to be [[IdString]], since these values are
conveniently mnemonic and they can be tested for equality efficiently.

<<typedef [[NoteKey]]>>=
typedef IdString NoteKey;
@


\subsection{Class [[Note]]}

In Machine SUIF, class [[Note]] is implemented as a wrapper for a base SUIF
annotation.  The only storage underlying a [[Note]] consists of a value of
type [[Annote*]] and a pointer to a reference count.  You must use
subclasses of [[Note]] to construct useful annotations; the only public
[[Note]] constructors are the null-note constructor and the copy
constructor.  If you create a custom subclass of [[Note]], you should
record all of their state in the SUIF [[Annote]], and not add more instance
fields.  That allows the note to be written to and read from intermediate
files transparently (once a [[set_note]] call has attached the SUIF
annotation to the IR object), and it also enables easy interconversion
between the base class and your subclass, because there is no risk of
``slicing'' bugs, i.e., loss of instance data through upcasting.

<<class [[Note]]>>=
class Note {
  public:
    Note();				// null-note constructor
    Note(const Note&);			// copy constructor
    ~Note();

    const Note& operator=(const Note&);
    bool operator==(const Note&) const;
    operator bool() const { return annote != NULL; }

  protected:

    Annote *annote;			// underlying SUIF annotation
    mutable int *ref_count;		// nullified by set_note

    friend Note clone(const Note&);
    friend Note get_note (IrObject*, NoteKey);
    friend Note take_note(IrObject*, NoteKey);
    friend void set_note (IrObject*, NoteKey, const Note&);
    friend Note note_flag();
    friend Note note_list_any();

    // Protected constructor, only invoked by friends.
    Note(Annote*, bool owned);

    void clear();

    // Methods that access the value sequence of a BrickAnnote
    int _values_size() const;

    void _insert_before(int pos, long value);
    void _insert_before(int pos, Integer value);
    void _insert_before(int pos, IdString value);
    void _insert_before(int pos, IrObject *value);

    void _append(long value);
    void _append(Integer value);
    void _append(IdString value);
    void _append(IrObject *value);

    void _replace(int pos, long value);
    void _replace(int pos, Integer value);
    void _replace(int pos, IdString value);
    void _replace(int pos, IrObject *value);

    void _remove(int pos);

    long _get_value(int pos, long const&) const
        { return _get_c_long(pos); }
    Integer _get_value(int pos, Integer const&) const
        { return _get_integer(pos); }
    IdString _get_value(int pos, IdString const&) const
        { return _get_string(pos); }
    IrObject* _get_value(int pos, IrObject* const&) const
        { return _get_ir_object(pos); }

    long      _get_c_long(int pos) const;
    Integer   _get_integer(int pos) const;
    IdString  _get_string(int pos) const;
    IrObject* _get_ir_object(int pos) const;
};
@

\paragraph{Public methods.}
The public methods of class [[Note]] allow you to construct a null note, to
copy an existing note, to compare notes for equality, and to test whether a
note is null.  What does it mean to copy a note?  In Machine SUIF, it means
to make a new reference to the same underlying SUIF [[Annote]].  So if you
assign one [[Note]]-valued variable to another, then changes to the
underlying value of either variable \emph{does} affect the other.  (To
override this reference-semantics behavior, you have to use the [[clone]]
function.)

Two notes are equal when their underlying SUIF annotations are isomorphic
and have pairwise equal components.  A null note is recognized by the fact
that its internal pointers (the [[Annote*]] and the reference-count
pointer) are null.  The main purpose of a null note is to indicate the
absence of an attachment to a particular object, for example, if the result
of evaluating [[get_note(mi, k_line)]] is a null note value, it means that
object [[mi]] has no note under the key [[k_line]].

When a note is converted to type [[bool]], the result is false only when
the note is null; otherwise, the result is true.  The purpose of this
conversion rule is allow you declare, initialize, and test a note variable
in one statement.  For example,

\begin{verbatim}
    if (LineNote note = get_note(mi, k_line)) {
	const char *file = note.get_file().chars();
          ...
    }
\end{verbatim}

If object [[mi]] has no [[k_line]] note, the ``then'' clause of the [[if]]
statement is skipped.


\paragraph{Friends of [[Note]].}

Since the only way to construct a non-null note or to look at its
underlying representation is through protected methods, several OPI
functions are declared as friends of class [[Note]].

\paragraph{Protected methods.}

The way most notes come into being is via the protected constructor that
takes an [[Annote*]] and a Boolean.  The first of these arguments becomes
the underlying annotation in the new note.  The second is true if that
underlying [[Annote]] is already attached to (and hence, owned by) a SUIF
object.  If so, the new note needs no reference count; it will be reclaimed
when its owning object is reclaimed.  Otherwise, the annotation is not yet
attached; the new note gets a reference count to be sure that the
[[Annote*]] is properly [[delete]]d if it happens never to be attached to
an object.

The [[clear]] method is used when one of a note's references is discarded.
If the note has a reference count, this method decrements it, and it takes
care of reclaiming storage if the count reaches zero.

The rest of the methods in class [[Note]] are for the common case in which
the note associates a tuple of values with the object to which it is
attached.  You use them when building a specialized subclass of [[Note]];
they allow you to manipulate a tuple of values that comprise note's
contents.  We call it a ``tuple'' because it is not homogeneous: the tuple
methods allow for four kinds of values: C [[long]], [[Integer]],
[[IdString]], and [[IrObject*]].%
\footnote{The C [[long]] values are of course a subset of the [[Integer]]s,
but because relatively small numbers are so common, it is convenient to
have the extra case for [[long]]s.}

The names of the tuple methods follow the OPI's conventions for a
sequence whose (conceptual) name is [[values]], but there's an extra [[_]]
at the front of each to avoid precluding the use of the actual OPI name as
a public method of some derived class.  Because the [[values]] tuple can
have multiple element types, the [[_get_]]\ldots methods are unusual.  When
writing a subclass method, if you know that the tuple element you
want to extract is, say, a string, you use [[_get_string]] to fetch it.
But when writing a templated subclass, the type of the tuple element may be
a template parameter, e.g., [[T]].  In that case, you can write
[[_get_value(pos, T())]], and the C++ overloading mechanism will choose the
correct method for you.

\paragraph{Atomic notes.}

There are two kinds of \emph{atomic} notes: null notes, which can't be
attached to objects, and flag notes, which can be attached, but carry no
other information than that conveyed by their presence on an object.  There
is an OPI function to create each of these kinds, and a predicate to test
for nullness.

<<functions for atomic notes>>=
Note note_null();
bool is_null(const Note&);

Note note_flag();
@

As mentioned above, the representation for a null note contains a null
[[Annote*]] field.  A flag annote holds a pointer to a [[GeneralAnnote]], a
subclass of [[Annote]].


\paragraph{Tuple notes.}

A non-atomic note contains a pointer to a [[BrickAnnote]].  That's a kind
of [[Annote]] that can carry a heterogeneous series of values (``bricks'').
The methods of [[Note]] for manipulating these values are protected, so you
must use or create a derived note class in order to take advantage of
them.  Derived classes use the following function to generate a tuple-note
value.

<<creator for non-atomic notes>>=
Note note_list_any();	// used only by Note classes
@

You should only need this function when deriving a note subclass, however.


\paragraph{Attaching, detaching, and testing for notes.}

The OPI functions that you use to test for the presence of notes on an
object, to access or remove a note from an object, or to attach a note to
an object, are declared as follows.

<<note-object association functions>>=
bool has_notes(IrObject*);
bool has_note (IrObject*, NoteKey);
Note get_note (IrObject*, NoteKey);
Note take_note(IrObject*, NoteKey);
void set_note (IrObject*, NoteKey, const Note&);
@

Functions [[get_note]] and [[take_note]] return a null note if the object
passed to them has no associated note under the given note key.  You can
test for nullness with the [[is_null]] predicate or by using an [[if]] or
[[while]] statement that declares, binds, and tests a note variable all at
once.  (See the example of an [[if]] statement above.)


\subsection{Specialized Note Classes}

\paragraph{Single-valued notes.}

Class [[OneNote<ValueType>]] allows attachment of a single value to an
object.  The type of the value is the template parameter [[ValueType]].

<<class [[OneNote]]>>=
template <class ValueType>
class OneNote : public Note {
 public:
    OneNote() : Note(note_list_any()) { _replace(0, ValueType()); }
    OneNote(ValueType value) : Note(note_list_any()) { set_value(value); }
    OneNote(const OneNote<ValueType> &other) : Note(other) { }
    OneNote(const Note &note) : Note(note) { }

    ValueType get_value() const
        { return _get_value(0, ValueType()); }
    void set_value(ValueType value)
        { _replace(0, value); }
};
@

The first (parameterless) constructor gives the note a default value.  To
give it a non-default value, you can either use the second constructor,
which accepts a value, or you can create the note and then use the
[[set_value]] method.  To fetch the value from the note, you apply the
[[get_value]] method.


\paragraph{List-carrying notes.}

Class [[ListNote<ValueType>]] allows you to attach zero or more values, all
of which have type [[ValueType]].

<<class [[ListNote]]>>=
template <class ValueType>
class ListNote : public Note {
  public:
    ListNote() : Note(note_list_any()) { }
    ListNote(const ListNote<ValueType> &other) : Note(other) { }
    ListNote(const Note &note) : Note(note) { }

    int values_size() const
        { return _values_size(); }
    ValueType get_value(int pos) const
        { return _get_value(pos, ValueType()); }
    void set_value(int pos, ValueType value)
        { _replace(pos, value); }
    void append(ValueType value)
        { _append(value); }
    void insert_before(int pos, ValueType value)
        { _insert_before(pos, value); }
    void remove(int pos)
        { _remove(pos); }
};
@

When you first create a [[ListNote]], is contains no  values; that is, its
[[value_size]] method returns zero.  The methods of the class allow you to
add, remove, update, and access values.


\paragraph{Custom notes for source-code location.}

This is a typical custom note class.  It is mentioned as an example in
\emph{The Extender's Guide}.  You often want to be able to attach a few
values of different kinds to an object.  In this case, the object is
usually an instruction, and the values are the source file name (a string)
and the source line number (an integer) that gave rise to the instruction.
Here's the entire derived class:

<<class [[LineNote]]>>=
class LineNote : public Note {
 public:
    LineNote() : Note(note_list_any()) { }
    LineNote(const LineNote &other) : Note(other) { }
    LineNote(const Note &note) : Note(note) { }

    int get_line() const	{ return _get_c_long(0); }
    void set_line(int line)	{ _replace(0, line); }
    IdString get_file() const	{ return _get_string(1); }
    void set_file(IdString file){ _replace(1, file); }
};
@

Here, we chose to make the line number the first element of the underlying
tuple and the file name the second element.  But no users of class
[[LineNote]] need to know that.


\paragraph{Custom note for multiway branches.}

Notes of class [[MbrNote]] attach information about a multiway branch to
the instruction that implements it, which for some target is not
distinguishable from an ordinary indirect jump instruction without this
annotation.

<<class [[MbrNote]]>>=
class MbrNote : public Note {
 public:
    MbrNote() : Note(note_list_any()) { }
    MbrNote(const MbrNote &other) : Note(other) { }
    MbrNote(const Note &note) : Note(note) { }

    int get_case_count() const;
    VarSym* get_table_sym() const
        { return to<VarSym>(_get_ir_object(0)); }
    void set_table_sym(VarSym* var)
        { _replace(0, var); }

    LabelSym* get_default_label() const
        { return to<LabelSym>(_get_ir_object(1)); }
    void set_default_label(LabelSym* label)
        { _replace(1, label); }

    int get_case_constant(int pos) const
        { return _get_c_long((pos << 1) + 2); }
    void set_case_constant(int constant, int pos)
        { _replace((pos << 1) + 2, constant); }

    LabelSym* get_case_label(int pos) const
        { return to<LabelSym>(_get_ir_object((pos << 1) + 3)); }
    void set_case_label(LabelSym* label, int pos)
        { _replace((pos << 1) + 3, label); }
};
@

The contents of a [[MbrNote]] include a sequence of
([[case_constant]], [[case_label]]) pairs, where the [[case_constant]] is
the integral value of the tested expression that marks a particular case
and the [[case_label]] is the label of the code to which the instruction
jumps in that case.  In addition to the sequence of pairs, there are fixed
``fields'':  [[case_count]] is the number of non-default cases, i.e., the
length of the sequence of pairs just mentioned;  [[table_sym]] is the
variable symbol holding the dispatch table used to compute the target of
the indirect jump; and [[default_label]] is the code label to which control
transfers when the tested expression doesn't evaluate to one of the
explicit case constants.


\paragraph{Custom note for attaching a natural-number set.}

Class [[NatSetNote]] connects a [[NatSet]] to an IR object.  One use is to
record the sets of registers implicitly used or defined by an instruction
for the benefit of data-flow analyzers.

<<class [[NatSetNote]]>>=
class NatSetNote : public Note {
  public:
    NatSetNote(bool dense = false);
    NatSetNote(const NatSet*, bool dense = false);
    NatSetNote(const NatSetNote &other) : Note(other) { }
    NatSetNote(const Note &note) : Note(note) { }

    void get_set(NatSet*) const;
    void set_set(const NatSet*);
};
@

Just as there are ``dense'' (bit-vector based) and ``sparse'' (linked-list
based) representations for an in-memory [[NatSet]], you can chose between
dense and sparse [[NatSetNote]] representations.  By default, the sparse-set
form is used, meaning that each set element is stored individually in the
values tuple of the note.  On the other hand, if you pass the argument
[[true]] to the [[NatSetNote]] constructor, it will choose a dense-set form
and represent the set as a bit vector, stored in a single [[Integer]]
value.  In either case, the set is allowed to be the complement of a finite
set (the result of applying the [[NatSet::complement]] method).

You can the supply the set of values to attach by passing a [[NatSet*]] to
the [[NatSetNote]] constructor, or you can call the [[set_set]] method of
an existing note.  When you want to read back the set contained in a note,
you must pass a pointer to a [[NatSet]] to the [[get_set]] method, which
clears it and then fills it from the note.  Here is one way to do this:

\begin{verbatim}
    if (NatSetNote regs_used_note = get_note(instr, k_regs_used)) {
        NatSetDense regs_used;
	regs_used_note.get_set(&regs_used);
          ...                               // regs_used holds register set
    }
\end{verbatim}

You don't have to know whether the note was represented in sparse or dense
form when you read it back.  We could just as well have declared
[[regs_used]] to have type [[NatSetSparse]] in the example above.


\subsection{header file [[opnd.h]]}

The header file for operands has the following outline:

<<note.h>>=
/* file "machine/note.h" */

<<Machine-SUIF copyright>>

#ifndef MACHINE_NOTE_H
#define MACHINE_NOTE_H

#include <machine/copyright.h>

#ifndef SUPPRESS_PRAGMA_INTERFACE
#pragma interface "machine/note.h"
#endif

#include <machine/substrate.h>
#include <machine/nat_set.h>

<<typedef [[NoteKey]]>>

<<class [[Note]]>>

<<functions for atomic notes>>

<<creator for non-atomic notes>>

<<note-object association functions>>

<<class [[OneNote]]>>

<<class [[ListNote]]>>

<<class [[LineNote]]>>

<<class [[MbrNote]]>>

<<class [[NatSetNote]]>>

#endif /* MACHINE_NOTE_H */
@