\section{Processing Algorithms}
\label{processing}

\subsection{Phase 1}
\label{phase1}

This phase transforms the {\bf li}-code instructions into
{\tt ch{\uline}statements} (see below).
During this phase some of the features of the Hermes language, and
their implications, are exploited to infer a variety of information
about the {\bf li}-code and the variables upon which it operates.
Most of this information depends on Strong Typing and Typestate
Checking.

When the families of operands are known, generated code can be
improved.\footnote{ Phase 2 (see Section~\ref{phase2}) provides some
examples.} Strong Typing implies that a variable whose family is known
may always be assumed to contain a value of that family, when it is
initialized.  Thus the family of a variable may be inferred in many
cases from an explicit reference to it; e.g.

     \begin{quote}\tt size dst src \end{quote}

implies that {\tt dst} is an integer and that {\tt src} is a table.
A ubiquitous instruction\footnote{
ubiquitous instructions are {\tt copy, move, equal, notequal},
not including {\tt discard}.}
for which the family of one operand is known, may imply the
family of another operand; e.g. given that {\tt src1} is a record:

     \begin{quote} \tt notequal dst src1 src2 \end{quote}

implies that {\tt src2} is a record.  For base operands this is clear
enough, but one must be wary of operands which may be nested within a
variant.  For such operands a proof that the operand's family is
invariant is necessary.  A sufficient condition for sequential code
is:

\begin{quote}
{\bf definition:} An operand is a {\em container} of a {\em nested}
operand, if the {\tt Id} of the first operand is a prefix of the {\tt
Id} of the second operand.

{\bf condition:} No {\tt unite} or {\tt reveal} has any {\em
container} of the operand as destination on any execution path between
the operand reference and the implying instruction.
\end{quote}

This condition is not used in this transformation, since it requires
flow analysis.  A very simple sufficient condition is:

\begin{quote}
No {\em container} of the operand which may be a component of a {\tt
variant} is assigned more than once.
\end{quote}

A sufficiently strong restriction of ``assigned'' is:
\begin{itemize}
\item All operands of a {\tt call} (other than the outport)
are assumed to be assigned by the {\tt call}.\footnote{
This condition could be relaxed if {\em typestate}
information was available.}
\item An assignment to a compound variable assigns all of its
components.
\end{itemize}

A sufficiently strong restriction of ``may be component of a {\tt
variant}'', based on the following definition of {\em invariant}, is:

\begin{quote}
{\bf definition:} An operand is {\em invariant} if it is assigned
once, or if its {\tt data{\uline}family} is known and it is {\em
determinate}.

{\bf definition:} An operand is {\em determinate} if it is not {\em
nested} or if it is {\em well-founded}.

{\bf definition:} An operand is {\em well-founded} if its immediate
{\em container} is assigned once, or if its immediate container is
inferred to be of {\tt record}, {\tt callmessage} or {\tt program}
{\tt data{\uline}family}, and is itself {\em determinate}.

{\bf restriction:} An operand may be component of a variant if it is
not {\em invariant}.''
\end{quote}

A (deferred) superior approach is to carry the operand family from
previous analysis.  That method is not suitable to the current
organization of the hermes compiler/system, but might be included as a
goal of a major revision (e.g. include a table parallel to the code
table which carries the {\em type} (and {\em typestate}) of each operand).

It is also possible to infer other useful attributes of an operand.
For example, an operand whose family is known and whose only assigned
value is a scalar constant can be replaced in all arithmetic
operations and relations by the constant value, since the process
passed Typestate Checking.  This gives us many of the benefits of
constant declaration for free.  Typestate Checking also guarantees
that variables are instantiated wherever they appear as source
operands.
\subsubsection{Algorithms}
\label{algorithms}

{\bf Input:} liprog.code source {\bf li}-code list.
\begin{enumerate}
\item[1. ] Conversion to internal tables.

{\bf Input:} liprog.code

Collect:

\begin{verbatim}
a. statements : ch_statements;

   ch_statements : ordered table of ch_statement;
   ch_statement : record (
     opcode : opcode,            -- from li-code
     operands : operand_indices, -- indices to ch_operands
     qualifier : qualifier,      -- from li-code
     flow : instruction_flow,    -- initially <- descriptors[opcode]
     locus : execution_locus,    -- initially <- descriptors[opcode]
     position: counter,          -- statement index after processing
                                 -- initially = position in table
     references: counter         -- incremented for each branch
                                 -- which references this statement
   );

   operand_indices : ordered table of integer {init};

   execution_locus : ordered enumeration(
      'interpret',               -- not transformed - residual li-code
      'block',                   -- comprises a cblock of its own
                                    -- 'call', 'select', 'receive'
      'escape',                  -- first statement of a non-blocking
                                 -- cblock
      'ccode',                   -- element of a cblock
      'omit'                     -- omitted code
   );

   instruction_flow : ordered enumeration(
     'frame',                    -- may branch - only implemented by
                                 -- interpreter
     'branch',                   -- may branch - may be implemented
                                 -- by code only
     'emerge',                   -- transfer to handler or terminate
     'continue',                 -- continue sequentially
     'ubiquitous'                -- here for convenience
   );

b. jumps : statement_indices;    -- unconditional branches
   branches : statement_indices; -- conditional branches

   statement_indices : table of integer {init};

c. operands : ch_operands;

   ch_operands : ordered table of ch_operand {full};
   ch_operand : record (
     Id: operand,                -- from code.operands[*]
     Family: data_family,        -- initially <- descriptors[opcode]
     Assignments: counter,       -- count all assignments
     References: counter,        -- count all references
     Literal: qualifier_literal  -- literal value of variable
   );

   data_family: ordered enumeration (
     'boolean', 'enumeration', 'ordered_enumeration',
     'integer', 'real', 'string',
     'nominal', 'record', 'polymorph',
     'inport', 'outport',
     'callmessage', 'program',
     'variant', 'table', 'unknown'
   );

   qualifier_family: ordered enumeration (
     'boolean', 'integer', 'real', 'string', 'none',
     'variable', 'indeterminate'
   );

   qualifier_literal: variant of literal_family (
     'boolean' -> boolean : boolean {init},
     'integer' -> integer : integer {init},
     'real' -> real : real {init},
     'string' -> string : charstring {init},
     'none' -> none : empty {},
     'variable' -> variable : empty {},
     'indeterminate' -> indeterminate : empty {}
   );

d. equivalents : equivalents;    -- ubiquitous operand pairs

   equivalents : table of equivalent {full} KEYS(*);
   equivalent : record(
     x1 : integer,               -- operand index
     x2 : integer                -- operand index
   );
\end{verbatim}

The following definitions apply to the collection of the data.

\begin{quote}
{\bf definition} A {\em literal} {\em constant} {\em assignment} is
one of [{\tt boolean}, {\tt ilit}, {\tt enum{\uline}lit}, {\tt
ordenum{\uline}lit}, {\tt rlit}, {\tt chs{\uline}lit}].

{\bf definition} An unconditional branch instruction is an
{\em orphan} if it is
unreferenced, and it is preceded by another unconditional
branch or by an 'emerge' flow instruction, or if its
target is the next un{\tt 'omit'}ed instruction.
\end{quote}

Collection is straight-forward, with a few exceptions.

\begin{enumerate}
\item[(1) ] A {\tt select} instruction needs special processing, due to
the unusual pattern of its operands.  It is a {\em blocking} {\tt
statement}, and its {\tt locus},{\tt flow} are forced to {\tt
'block'},{\tt 'frame'} if the selection includes an {\tt inport}; such
instructions may block, if there are no queued messages.
\item[(2) ] All arguments of a {\tt call} instruction, except for
argument 0 (the {\tt outport}) are assumed to be
assigned (see {\tt chassign}).
\item[(3) ] {\em Literal} {\em constant} {\em assignments} are
treated specially.
\item[(4) ] A {\tt prog{\uline}lit} instruction causes the entire
transformation to recurse on its qualifier, which is a {\tt program}.
The process chprogram is called to transform the program literal.
\item[(5) ] An escape instruction causes the transformation of the
program to be abandoned, since it has been previously transformed.
\end{enumerate}

For operands, {\tt case of Literal} is set to {\tt 'none'} initially.
It is reset, monotonically, as follows (see {\tt chassign}):
\begin{enumerate}
\item[(1) ] one of [{\tt 'boolean'}, {\tt 'integer'}, {\tt 'real'},
{\tt 'string'}], if the first assignment is a {\em literal} {\em
constant} {\em assignment}.
\item[(2) ] {\tt 'variable'}, when any assignment is not a {\em literal}
{\em constant} {\em assignment} or if multiple assignments occur;
\item[(3) ] {\tt 'indeterminate'}, when there is a
conflict in inferred operand {\tt Family}.
\end{enumerate}

{\bf Output:} {\tt statements}, {\tt jumps}, {\tt branches}, {\tt operands},
{\tt equivalents}

\item[2. ] Branch processing

{\bf Input:} {\tt statements, jumps, branches}
\begin{enumerate}
\item[a. ] Process {\tt jumps}, chaining unconditional branches
in {\tt statements} to minimize the paths from$\rightarrow$target.
\item[b. ] Process {\tt branches}, implementing branch chaining
via {\tt statements}, using argument {\tt references}
(see {\tt chtransform}).
\item[c. ] Omit all {\em orphan} {\tt jumps}.
\item[d. ] Compute {\tt references} for every remaining target
instruction (labeled {\tt statement}), using argument {\tt references}.
\end{enumerate}

{\bf Modifies} {\tt statements}

\item[3. ]  Operand processing

{\bf Input:} {\tt operands}, {\tt equivalents}.
\begin{enumerate}
\item[a. ] Construct {\tt trees}, a tree of all {\tt operands},
where one operand is an ancestor of a second operand, if the
{\tt Id} of the first is a prefix of the {\tt Id} of the second.
\item[b. ] Construct {\tt containers}, a table of all {\tt Id} prefixes.
\item[c. ] Cumulate {\tt Assignments} for operands whose ancestors
are assigned.  An operand which is implicitly assigned is {\tt 'variable'}
(possibly with known {\tt Family}).
\item[d. ] Find implicit {\tt data{\uline}family} of {\tt 'unknown'}
operands of ubiquitous
instructions by family inference, using {\tt statements}, {\tt equivalents}.
An operand of a pair of {\tt equivalents} implies its partner's
family, if both are {\em invariant}.
\item[e. ] Remove every element of {\tt containers} which is
is not {\tt variant} and is {\em well-founded}.
\item[f. ] For every remaining element of {\tt containers}
which is assigned more than once,
mark all of its contained operands,
{\tt 'indeterminate'} and {\tt 'unknown'}.\footnote{
The unmarked operands are {\em invariant}; subsequent analysis
depends upon their families and {\tt Literal} values.}
\item[g. ] Find implicit {\tt data{\uline}family} of {\tt'unknown'}
operands of ubiquitous
instructions by family inference, using {\tt statements},
{\tt equivalents}. The operands of a pair of {\tt equivalents} must have
the same family throughout the process, unless either of them is
{\tt 'indeterminate'}.\footnote{
A weaker criterion is possible here because preceding steps have
proven that all variables of pairs which satisfy this criterion
are {\em invariant}.}
\end{enumerate}
{\bf Modifies:} {\tt operands}
\end{enumerate}

Most code inprovement is done in phase 2.  Some code improvements can
be applied directly to the {\bf li}-code, and some of these are done in
phase 1.  Branch chaining and redundant branch elimination are two of
these.

{\bf Output:} {\tt statements, operands}.

\subsection{Phase 2}
\label{phase2}

The information regarding the {\tt data{\uline}family}, {\tt Literal}
value and reference status of an operand
is useful for a variety of improvements.

Some abbreviations used below for references to instruction
source operands literal constants are:
\begin{itemize}
{\tt 
\item S ::= operands[src].Literal
\item S1 ::= operands[src1].Literal
\item S2 ::= operands[src2].Literal
\item G ::= operands[guard].Literal
}
\end{itemize}

\subsubsection{Algorithms}

{\bf Input:} {\tt statements, operands}.

\begin{enumerate}
\item[1. ] CBlock collection

{\bf Input:} {\tt statements}

Collect:

\begin{verbatim}
   CBlocks : ordered table of CBlock {full};

   CBlock : record (
     ingress : cblock_indices,   -- entry numbers of this block
     first : integer,            -- first statement of this block
     next : integer,             -- first statement of next block
     statements : statement_index_list  -- component instructions
   );

   cblock_indices : ordered table_of_integer {init};
   statement_index_list : ordered table of integer {init};

\end{verbatim}

The {\tt statements} of a {\tt CBlock} is an ordered list of successive
{\bf C}-codable {\tt statement} indices,
only the first of which may be referenced, except where all references to
an embedded {\tt statement} are from statements which are indexed in the
list.

The first {\tt statement} of the program is the first {\tt statement}
of the first {\tt cblock}, if it is not {\tt 'interpret'}ed.

Terminate a {\tt cblock} when the next {\tt statement} has {\tt locus}
{\tt 'interpret'} or {\tt 'block'}.

Terminate a {\tt cblock} when the next {\tt statement}'s {\tt references}
is greater than zero, and not every reference to that {\tt statement} is
already within the {\tt cblock}.

Terminate a {\tt cblock} if its first {\tt statement} has {\tt locus}
{\tt 'block}.

Terminate a {\tt cblock} when there is no next {\tt statement} (at end
of program).

Start a new {\tt cblock} with the first {\tt 'ccode'} or {\tt `block`}
{\tt locus} {\tt statement} following a sequence of {\tt
'interpret'}ed {\tt statement}s or a terminated {\tt cblock}.

If the {\tt locus} of the {\tt first} {\tt statement} entry
indexed by the {\tt CBlock} isnt {\tt 'block'}, reset it to {\tt
'escape}.  If the {\tt locus} was {\tt locus} {\tt 'omit'}, set its
{\tt opcode} = {\tt 'noop'}.

While collecting a {\tt cblock}, record all potentially internal
branch label references (see above).  These are all in statements
of {\tt flow 'branch'}.

\item[2. ] Do {\bf Hermes} redundancy improvements for each CBlock.\footnote{
A {\bf Hermes} redundancy improvement is the substitution for one
or more sequential {\tt encoding}s by (sometimes) fewer {\tt encoding}s,
and in many cases, a revision of one or more statements.}

It is possible for the last remaining operation of a {\tt CBlock} to
be removed by some of these improvements.  When that happens, the
statement is changed to a {\tt 'noop'}.

For the {\em constant propagation} and the {\em constant expression
evaluation} improvements described below, if {\tt Assignments} = 1,
the {\tt Literal} value of the {\tt operands[dst]} entry is updated.

\begin{itemize}
\item {\em constant propagation}

For the following substitutions, for {\tt operands[I]}, decrement
{\tt References} by 2, and decrement {\tt Assignments} by 1.

\begin{verbatim}
boolean I , Qualifier   ->   boolean dst , Qualifier
move dst I                   discard I

ilit I , Qualifier      ->   ilit dst , Qualifier
move dst I                   discard I

enum_lit I , Qualifier  ->   enum_lit dst , Qualifier
move dst I                   discard I

ordenum_lit I , Qualifier -> ordenum_lit dst , Qualifier
move dst I                   discard I

rlit I , Qualifier      ->   rlit dst , Qualifier
move dst I                   discard I

chs_lit I , String      ->   chs_lit dst , String
move dst I                   discard I
\end{verbatim}

\item {\em constant expression elimination}

The following substitutions are performed if all source operands,
are constant.  The substitution includes evaluation of an expression
as indicated.
Decrement {\tt References} by 1 for each source operand.

\begin{verbatim}

                             -- if (0 <= S.integer < CQ)
icvt_enum dst src , CQ  ->   ordenum_lit  dst , S.integer

rnegate dst src         ->   rlit dst , (-S.real)

oecvt_int dst src       ->   ilit dst , S.integer

and dst src1 src2       ->   boolean dst , (S1.boolean and
                                            S2.boolean)

idivide dst src1 src2   ->   ilit dst , (S1.integer /
                                         S2.integer)

radd dst src1 src2      ->   rlit dst , (S1.real + S2.real)

rlt dst src1 src2       ->   boolean dst , (S1.real < S2.real)
\end{verbatim}

and so forth for all of the boolean, integer, real and
ordered{\uline}enumeration conversions, operations and
relations.\footnote{
If evaluation causes an exception ({\tt Depletion, DivideByZero}),
the substitution is rejected.}

Iterate {\em constant expression elimination} until there are no
more constant expressions.

\item {\em constant argument elimination-1}

For all above binary arithmetic and logical operations and arithmetic
relations, if either source operand is a literal constant and the
other is not, decrement {\tt References} by 1 for the literal source
operand.\footnote{ This action is implied by {\em constant} {\em
argument} {\em elimination-2} below.}

\item {\em redundant test elimination}

A conditional branch whose condition is known at compile time can
be omited or replaced by an unconditional branch.\footnote{
It might be useful to iterate Phase 1 branch processing following
this improvement.}

The following substitutions are performed if the {\tt guard} argument,
is a literal constant.  For {\tt operands[guard]},
decrement {\tt References} by 1, and for\newline
{\tt statements[label]}, decrement {\tt references} by 1.

\begin{verbatim}
                             -- if G.boolean = 'true'
branch_false guard , label    ->   <omit>

                             -- if G.boolean = 'false
branch_true  guard , label    ->   <omit>

                             -- if G.boolean = 'false'
branch_false guard , label    ->   branch  , label


                             -- if G.boolean = 'true'
branch_true  guard , label    ->   branch  , label
\end{verbatim}

\item {\em peephole improvement}

For a pair of instructions, where the first assigns a destination
operand which is the same as the source of the second, which is a
{\tt move}, replace the destination operand of the first by the destination
operand of the second, and change the {\tt move} to a {\tt discard} of
the shared operand.\footnote{ When the first instruction is a call,
this improvement is permitted {\em iff} the shared argument is
assigned once.}  {\em Constant propagation} is a special case of
this {\em peephole improvement}, with the side-effect of propagating
the operand value.

When the {\tt select} instruction has no {\tt inport} arguments,
the tests which assign its boolean arguments may be transformed into
{\em test-and-branch} instructions.

For two successive {\tt discard} instructions, where the operand
of the second includes the operand of the first, omit the first.

\item {\em redundant instruction elimination}

Omit any {\tt discard} instruction whose operand is neither assigned
nor referenced.

\end{itemize}

\begin{quote}
{\bf definition:} An operand
assigned by a literal constant statement is {\em unreferenced} when
{\tt References} = 1 and {\tt Assignments} = 1.
\end{quote}

If as a result of any of the above operations, the operand
assigned by a literal constant statement becomes {\em unreferenced},
eliminate the instruction descriptor from its {\tt CBlock} and
reset its operand {\tt References} = 0, {\tt Assignments} = 0.

\item[3. ] Redundant {\tt CBlock} processing.
{\bf definition:} A {\em framed} {\tt CBlock} is one which can
only be reached from a 'frame' {\tt flow} {\tt statement}.

Process any {\tt CBlock} which contains only one statement, where
the {\tt opcode} of that statement is 'noop' or 'branch', and where
the next statement in order of execution has {\tt locus}:

\begin{itemize}
\item {\tt 'escape'} or {\tt 'block'}:

merge the {\tt ingress} of the eliminated {\tt CBlock} with the {\tt
ingress} of its successor.

If the {\tt CBlock} is {\em framed}, it is effectively eliminated by
emptying its {\tt statements} and its {\tt ingress}.

The {\tt CBlock} is {\em not} removed from {\tt CBlocks}, since this
would leave a gap in sequence.

\item {\tt 'interpret'} and there is at most one entry to the {\tt
CBlock} and no references to it and it immediately follows the {\tt
CBlock} which is being processed in code order.

Set the lone {\tt statement}'s {\tt locus} = {\tt 'omit'} and exchange
the {'interpret'}ed {\tt statement} with the lone {\tt statement}.

Remove the {\tt CBlock} from {\tt CBlocks}.
\end{itemize}

\end{enumerate}

{\bf Output:} {\tt statements, operands, CBlocks, operand{\uline}count}.

\subsection{Phase 3}
\label{phase3}

This phase produces the {\bf C}-coded text corresponding to the {\tt
statement}s indexed in {\tt CBlocks}.  Templates for the
transformation are supplied for each {\bf li}-code operation code
({\tt opcode}).

Where appropriate, alternative templates are chosen to improve the
generated code.  All template choices are based on {\em type} or value
of operands.

For compact scalar operands ({\tt 'boolean'}, {\tt 'integer'}, {\tt
'enumeration'}) {\tt FINALIZE} action (see
Appendix~\ref{representation}) is omitted and copying is done by
bit-copy.  All relations of scalar operands are evaluated in line.
For compound operands of known {\em type}, {\tt tsdr} functions are
called directly, or could be coded specially (e.g.  {\tt copy} \space
character-string or nominal).

Range tests (especially in ordered table operations) are omitted for
known constant operands where the test can be made during the code
generation process.

Another useful application of constant operands, would be to provide
special case coding for table operations with a character string
operand - e.g.

  \begin{quote}\tt concat dst src1 src2 \end{quote}

where {\tt src1} or {\tt src2} is known to be a character string could
be specially coded.

\subsubsection{Algorithms}

{\bf Input:} {\tt statements, operands, CBlocks lipart.name}.

\begin{enumerate}

\item[1. ] Renumber {\tt statements}.

Traverse {\tt statements} in order, starting with
{\tt Operand{\uline}count} = 0, assigning\newline
{\tt position := Operand{\uline}count} for each instruction.
Increment {\tt Operand{\uline}count} for each instruction
which is not {\tt 'omit'}ed.

\item[2. ] Traverse {\tt statements}, adjusting all branch addresses.

\item[3. ] Construct the reduced operand set.

Compute new {\tt Id}s for {\tt operands} entries.  Assign
values to all base entries which are referenced, starting
with 3.\footnote{
Base values 0, 1, 2 are predefined and cannot be reassigned
or altered.}
Then reassign the first element of each operand identifier.

\item[4. ] Construct residual {\bf li}-code table from renumbered {\tt
statements}.

\item[5. ] Do template improvements for each {\tt CBlock}.\footnote{
A template improvement is the choice of a better template to
generate improved code, based on knowledge of local computational state.}

\begin{itemize}
\item {\em constant argument elimination-2}

For all binary operations and arithmetic relations, if either source
operand is a literal constant, use the constant itself in the
generated code, in place of the reference to the operand variable.

\item {\em redundant test elimination}

Remove tests of operands which are known to be constant and which can
therefor be tested during code improvement.

\end{itemize}

\item[6. ] Construct {\bf C}-coded module, including global declarations,
entry line, local declarations, switch and labels, from {\tt CBlocks},
{\tt statements} and {\tt operands} (see Appendix~\ref{descriptors}
for details).  Pool qualifiers as necessary.

\end{enumerate}

{\bf Output:} {\tt liprog.code} residual {\bf li}-code list, {\tt chpart}
string of {\bf C}-coded module, {\tt lipart.pool} pooled qualifiers,
{\tt lipart.size} reduced operand count.

