Chapter 1

Middle End Data-Structures and Tools

1.1 Introduction

This chapter and the following chapter discuss the middle end of the Id compiler. In theory, the middle end of the compiler encompasses a machine independent data structure for representing Id programs and a set of modules that transform one instance of the data structure into another semantically equivalent (but hopefully more efficient) instance. However, one should always be wary of sweeping claims. As in most optimizing compilers, our current implementations of semantics preserving optimizations have not always been rigorously checked (not of course, due to lack of desire, but these problems are still open areas of research). Making claims that certain machine independent code transformations result in more efficient execution (in time or space) on a particular machine is even harder to decide. Therefore, the reader is encouraged to adopt a critical attitude for the next two chapters and towards machine independent compiler optimizations in general until the field reaches firmer ground.

Disclaimers aside, the overall philosphy of machine independent optimizations seems appropriate. There are many well known program transformations that work best when applied before the details of specific machine implementations obscure the landscape of a program. For the Id compiler these include: optimizing accesses to statically known data (either through constant folding and propagation or fetch elimination from static structures), simplifying algebraic expressions, unrolling procedure calls and loops, and hoisting code out of loops among others.

Also, over time, features that have more to do with specific machine models than machine independent optimizations have crept into middle end modules. Hence the middle end is an amalgam of modules that perform general optimizations as well as add features that make programs easier to implement in the dataflow model or on a specific machine.

Current wisdom dictates that graphs are the most appropriate data structure for middle end transformations. The Id compiler has the fortune to use very similar graph structures for both the middle and the back end (decsribed in chapters ?? and ?? ). Hence, both program graphs (in the middle end) and ets machine graphs (in the back end) are implemented on top of the same low level structure provided by DFCS. Unfortunately, sometimes the underlying details of the low-level data structure obscure the higher level abstraction used by the middle end (largely for reasons of efficiency). In particular, it’s worthwhile to pay extra attention to the details of surfaces which can confuse the novice.

1.2 Program Graphs

The Id compiler’s middle end modules manipulate program graphs, a graph data structure for representing Id programs. Program graphs are a generalization of the dataflow graph data structure provided by DFCS. Conceptually, progam graphs consist of instructions wired together into a graph:

Definition 1 A Program graph contains

1. A set of instructions, each with the following components:

(a) An opcode, represented by a keyword symbol.

(b) An external surface with a set of input and output ports. The name of the external surface is the keyword symbol :exterior.

(c) Zero or more internal surfaces, each with their own sets of input and output ports. The name of each internal surface is represented by a keyword symbol.

(d) Various other fields for characterizing an instruction’s properties and keeping bookkeeping information.

2. A set of directed arcs connecting instruction output ports to instruction input ports:

• No input ports may have more than one incoming arc.

• Output ports have no limitation on the number of outgoing arcs.

3. An (implicit) notion of the graph’s inputs and outputs:

• A graph’s inputs are the set of its unconnected instruction inputs.

• A graph’s outputs are the set of its unconnected instruction outputs.

In the dataflow model, where arcs carry tokens from outputs to inputs, every dataflow instruction produces a complete set of output tokens when presented with a complete set of input tokens. Program graph instructions have dataflow instruction behavior. Dataflow behavior can be generalized to graphs of instructions as well.

Definition 2 A Basic Block (or just a block) is a program graph where if a token arrives at every input:

1. Every output emits a token.

2. Every instruction in the graph executes exactly once.

Its useful to classify program graph instructions based on the number of internal surfaces they have:

Definition 3 Simple instructions have no internal surfaces.

Simple instructions represent primitive Id operators (like + or i-store). A simple instruction’s input ports represent arguments to the operator and its outputs represent the results returned by the operator. Some simple instructions can be classified by their use of input and output ports:

• Purely functional instructions (like +) depend only on their inputs and have no observable effects outside the results they return.

• Purely side-effecting instructions (like i-store) have no outputs.

• Constant instructions have no inputs.

Definition 4 Encapsulating instructions (called encapsulators) have at least one internal surface.

Each internal surface of an encapsulator connects to different, disjoint basic blocks. Encapsulators are used to represent Id operators with complex translations from parse trees to blocks of machine graph instructions (called translation schemas). The opcode of the encapsulating instruction represents the invariant part of the schema and the blocks connected to each internal surface of the instruction correspond to the variant subgraphs of the schema.

Alternatively, encapsulators can be thought of as simple instructions whose semantics are completely determined by their opcode and internal blocks. They represent black boxes, hiding internal surfaces from the outside. Like simple instructions, they produce a full set of output tokens on their external outputs when presented with a full set of tokens on their external inputs.

For example, the Id if expression is represented by an if encapsulator with the following components:

1. An external input taking the output of the predicate expression.

2. n external inputs for the arguments (free variables) of the then and else expressions.

3. m external outputs.

4. Two internal surfaces named :then and :else which connect to blocks of n inputs and m outputs.

Note, after being presented with a full set of input tokens, the if encapsulator produces a full set of output tokens, though only one of its internal blocks executes.

1.3 Port Names

The input and output ports on each surface of an instruction can be referred to either by number or symbolic name. If a surface has n input ports then each input port can be referred to as a number in the range {0,…, n − 1} (similarly for output ports). Alternatively, ports can be referred to by symbolic names (which map onto port numbers) using the following conventions:

• A Symbolic Name is either

1. A keyword symbol (a simple name).

2. (keyword . i) (a subscripted name), where i is a non-negative integer.

• An input or output port may have at most one symbolic name.

• No two input ports or output ports of the same instruction may have the same symbolic name although an input port and an output port may have the same name.

• If (keyword . n) is a port name then so is (keyword . i) for all i from zero through n.

• Subscripted names with consecutive subscripts always map to consecutive port numbers.

The following functions translate between port names and numbers:

instruction-input-name-to-number instruction input-name  [Function]
instruction-output-name-to-number instruction output-name  [Function]

instruction-input-number-to-name instruction input-number  [Function]
instruction-output-number-to-name instruction output-number  [Function]

These functions return nil if the name or number is ill-defined for the given instruction. The names returned are always subscripted.

1.4 Arcs, Sources and Sinks

Definition 5 Sources and sinks allow the programmer to specify a specific output or input port of an instruction:

• A source points to an instruction’s output port.

• A sink points to an instruction’s input port.

Definition 6 An Arc is a source-sink pair.

Arcs are implemented as pairs of sources and sinks. The source of the pair points to the output port attached to the arc’s tail. The sink of the pair points to the input port attached to the arc’s head.

Notice that instructions never point directly to other instructions. Instead, sources and sinks provide a doubly linked list corresponding to arcs. For example, if instruction A points to instruction B then A points to a sink pointing to an input of B and B points to a source pointing to an output of A.

Sources, sinks and arcs can also carry annotations which are either nil or a pointer to some data-structure.

Constructors

make-instruction-sink instruction port &optional annotation  [Function]
make-instruction-source instruction port &optional annotation  [Function]

Creates and returns an instruction source or sink referring to an input or output port of instruction. Port may be either a symbolic name or a port number.

Selectors

instruction-sink-instruction instruction-sink  [Function]
instruction-source-instruction instruction-source  [Function]

Returns the instruction referred to by instruction-sink or instruction-source. May not be used with

setf.

instruction-sink-input instruction-sink  [Function]

instruction-source-output instruction-source  [Function]

Returns the port number referred to by instruction-sink or instruction-source. Note that the value returned is always a number. These functions are discussed further in section ??. May not be used with setf.

instruction-sink-annotation instruction-sink  [Function]
instruction-source-annotation instruction-source  [Function]

Returns the annotation slot of instruction-sink or instruction-source. May not be used with setf.

1.5 Parameters, Slots and Properties

Instruction Parameters

Instruction parameters are used when one opcode stands for a family of instructions. For example, there might be an instruction with opcode :constant which emits a certain value upon the receipt of any input. The :constant instruction’s parameter determines what constant it emits.

Instruction Slots

It’s possible to define extra slots for program graph instructions. These extra slots can store additional information about a given instruction. Also, slots can be added and removed without the entire compiler being recompiled. Section ?? describes slots used in the compiler’s current implementation.

Instruction Properties

Read-only slots called properties can be set up that store information for all instructions with a particular opcode. See section 1.7 and the explanation of the define-program-graph-instruction macro for the details of defining instruction properties. Section 1.12 describes properties used in the compiler’s current implementation.

1.6 Using Program Graph Instructions

Now that the basic components of program graph instructions have been defined, we can describe the Lisp functions operate on instructions.

Selectors

instruction-opcode instruction  [Function]

Returns the contents of the opcode slot of instruction.

instruction-parameter instruction  [Function]

Returns the parameter value of instruction. May be used with setf.

instruction-encapsulator-p instruction  [Function]

Returns true if the instruction contains internal surfaces.

instruction-block-names instruction  [Function]

Returns a list of the names of instruction’s surfaces.

instruction-<property-name> instruction  [Function]

Returns the value of the property for instruction. May not be used with setf.

define-program-graph-instruction-slot selector-name &key copyable-p  [Macro]

Sets up a new instruction slot with name selector-name.

instruction-<slot-name> instruction  [Function]

Returns the value of the slot for instruction. May be used with setf.

instruction-n-exterior-inputs instruction  [Function]
instruction-n-exterior-outputs instruction  [Function]

Returns the number of exterior inputs or outputs for instruction.

1.6.1 Surface Related Functions

For historical and efficiency reasons, an encapsulator’s internal surfaces are manipulated with the same functions used for manipulating a simple instruction’s external surface. In actuality, input and output ports are assigned to different surfaces only by convention. For simple instructions, an instruction’s input and output ports are the same as the ports for its exterior surface. For encapsulators, functions are provided to map between the absolute ports of the instruction (considering all ports to be on the :exterior surface) and the ports for each surface.

Fact 1 A simple instructions input and output ports are the same as the ports on its exterior surface.

instruction-inputs instruction  [Function]

Returns an array containing the inputs of instruction. Each element of the array is an instruction source and each element’s index is its port number. May not be used with setf.

instruction-outputs instruction  [Function]

Returns an array containing the outputs of instruction. Each element of the array is a list of instruction sinks and each elements index is its port number. May not be used with setf.

Fact 2 An encapsulating instruction has an indirect mapping between the ports of its surfaces

and its absolute ports referenced by instruction-inputs and instruction-outputs.

There is an indirect mapping between: (<surface-name>, <surface-port-num>) and <absoluteport-num>

Mapping from Surface to Absolute Ports

The following functions implement the mapping from (<surface-name>, <surface-port-num>) to <absolute-port-num>.

instruction-surface-lowest-input instruction surface  [Function]
instruction-surface-lowest-output instruction surface  [Function]

instruction-surface-highest-input instruction surface  [Function]
instruction-surface-highest-output instruction surface  [Function]

These functions return the number of the lowest (or highest) numbered port belonging to a given surface, or nil if there is no such surface. Note that a number is returned in the case where a surface exists but has no ports.

Note: <absolute-port-num> = <lowest-surface-absolute-port-num> + <surface-port-num>.

Mapping from Absolute to Surface Ports

The following functions implement the mapping from <absolute-port-num> to (<surface-name>, <surface-port-num>).

instruction-input-surface instruction port  [Function]
instruction-output-surface instruction port  [Function]

These return the surface on which a given port of instruction lies, or nil if the instruction has no such port.

1.6.2 Using Internal Surfaces

The definition of interior surfaces, as implemented above, usually confuses novice users. Though program graph instructions make no distinction between internal and external ports, a user’s mental picture of an instruction does! In the diagrams we draw to represent an encapsulating instruction (see figure ??), external inputs connect to the “top” of the instruction and outputs extend from its “bottom.” However, for internal blocks, outputs hang off the “top” of the internal block and inputs enter from the “bottom” of the internal block. It’s vital to keep in mind that the outputs from an interior surface feed the inputs of an internal block (and vice versa for the inputs of an interior surface).

An Example

Here are some Lisp functions using instruction surfaces:

;;;-------------------------------------------------------------------------
;;; multiple value giving number of lowest & highest port for given surface
(defun instruction-surface-input-numbers (instruction surface)
  (values (instruction-surface-lowest-input instruction surface)
  (instruction-surface-highest-input instruction surface)))
(defun instruction-surface-output-numbers (instruction surface)
  (values (instruction-surface-lowest-output instruction surface)
  (instruction-surface-highest-output instruction surface)))
;;;-------------------------------------------------------------------------
;;; Return sequence that corresponds to the subsequence of the port array
;;; for a given surface
(defun instruction-surface-inputs (instruction surface)
  (multiple-value-bind (l h)

 (instruction-surface-input-numbers instruction surface)
(and l h (coerce (safe-subseq (instruction-inputs instruction) l h) 'list))))
(defun instruction-surface-outputs (instruction surface)
(multiple-value-bind (l h)
 (instruction-surface-output-numbers instruction surface)
(and l h (coerce (safe-subseq (instruction-outputs instruction) l h) 'list))))

1.7 Defining Program Graph Instructions

The define-program-graph-instruction macro provides a convenient way of declaring program graph instructions. It sets up a blueprint that defines all instructions of a given opcode. It declares a parameterized constructor function to create instances of the instruction having the specified opcode. It defines the symbolic names of input and output ports, interior surface names, and what ports are associated with what surfaces. It also defines properties associated with any instructions created by the constructor.

The syntax is as follows:

define-program-graph-instruction opcode (arg1 arg2 . . . ) &clauses  [Macro]

{(:inputs {input-name input-expr}∗)} {(:outputs {output-name output-expr}∗)}

                            [(:constructor-name constructor-name)]

[(:blocks {block-name input-names output-names}∗)] [(:properties {indicator value}∗)]

input-expr :integer
output-expr :integer

<input-names> ::= (keyword*) <output-names> ::= (keyword*)

• The :inputs and :outputs clauses are required; all others are optional.

• The numbers of inputs and outputs are determined by evaluating the expression for each port name, where these expressions may refer to the arguments.

• The :blocks clause may be used to declare that certain inputs and outputs belong to interior subgraphs; there is always a surface named :exterior to which all ports not mentioned in the :blocks clause belong. If the :blocks clause is omitted entirely, then the only surface is

the :exterior.

• Ports within a surface are always assigned consecutive numbers. The lowest numbers are assigned to the :exterior surface, and the remaining numbers are assigned to surfaces in the order in which they appear in the :blocks clause. Within each surface, the ports are ordered as they appear in the :inputs or :outputs clause.

• The :properties clause can be used to associate properties to all instructions of a given opcode; Note that the properties are really assigned to opcodes, rather than individual instructions.

Evaluating the macro defines the lisp constructor:

make-<opcode>-instruction {arg}∗  [Function]

The constructor function for the instruction. The name may be overridden by the constructor-name clause. The argument values may be used to parameterize the numbers of inputs and outputs.

<opcode>-instruction-arg<i> instruction  [Function]

Returns the ith argument to the constructor creating the instruction

Examples

Here’s an example defining a simple instruction.

(define-program-graph-instruction make-tuple ()
  (:constructor-name make-make-tuple-instruction-internal)
  (:inputs :trigger 1 :anchor 1)
  (:outputs :output 1 :signal (if *resource-manager-signal-p* 1 0))
  (:properties :generate-ets-function 'g-ets-make-functional-tuple-instruction
       :side-effecting-p t
       :create-like-p t
       :k-allocator :make_k_tuples
       :k-deallocator :free_k_tuples))
;;;
;;; Constructor for make-tuple instruction. Notice make-...-internal is used
;;; to construct a tuple instruction with no parameter. The parameter of
;;; resulting instruction is set to be size. Parameters should be definable
;;; with define-program-graph-instruction, but apparently they must be
;;; set by hand!
;;;
(defun make-make-tuple-instruction (size)
  (let ((make-tuple-instruction (make-make-tuple-instruction-internal)))
    (setf (instruction-parameter make-tuple-instruction) size)
    make-tuple-instruction))
;;;
;;; Selector for the size of the tuple the instruction creates
;;;
(defun make-tuple-instruction-size (make-tuple-instruction)
  (instruction-parameter make-tuple-instruction))

Here’s an example defining an encapsulating instruction:

 (define-program-graph-instruction loop (n-variables n-constants)
   (:inputs :predicate 1
            :loop-constant n-constants
            :predicate-output n-variables
            :loop-input n-variables
            :body-output n-variables)

   (:outputs :predicate-input n-variables
             :body-input n-variables
             :loop-output n-variables)
   (:blocks :predicate (:predicate-output :predicate) (:predicate-input)
            :body (:body-output) (:body-input))
   (:properties :iterator-p t))

The example above defines the following functions:

      (make-loop-instruction n-variables n-constants)
      (loop-instruction-n-variables loop-instruction)
      (loop-instruction-n-constants loop-instruction)
      (instruction-iterator-p instruction)

1.8 @!-opcode program graph instructions

To be filled in.

1.9 Wiring Instructions Together

For now see the DFCS manual for a description of how to wire together dataflow graphs.

1.10 Traversing Program Graphs

Instruction Marks and Numbers

When traversing program graphs it’s often useful to mark instructions as they are processed, to avoid following loops in the graph. Instructions may also be numbered with non-negative integers. Algorithms which traverse program graphs cannot mark some instructions and number others since marks and numbers are stored in the same location within an instruction structure.

The functions below control marking a program graph:

reset-all-instruction-marks  [Function]

mark-instruction instruction  [Function]
instruction-marked-p instruction  [Function]
unmark-instruction instruction  [Function]

The functions below control numbering a program graph:

reset-all-instruction-numbers  [Function]

number-instruction instruction number  [Function]
instruction-number instruction  [Function]
unnumber-instruction instruction  [Function]

Iterating Over Blocks

The with-basic-block-array macro provides an efficient way to point to every instruction in a basic block. The macro stores the simple and encapsulating instructions of a block in two arrays (in no particular order). Iterating over the arrays provides access to every instruction in the block.

with-basic-block-array (bb-array encaps-array encapsulator bb-name) body  [Macro]

<bb-array> ::= symbol <encaps-array> ::= symbol <encapsulator> ::= <lisp form evaluating to an encapsulator instruction> <bb-name> ::= <keyword denoting a basic block in encapsulator>

• bb-array is bound to an array whose elements are the instructions comprising the block named bb-name in the encapsulator.

• encaps-array is bound to an array containing all instructions in it bb-array which are themselves encapsulators.

• The original encapsulator is not included in either array.

• Any values returned by the body are returned as the result of the entire macro.

• with-basic-block-array changes instruction marks.

With-basic-block-array is a macro because it recycles the arrays after executing the body. Therefore, no pointers to the arrays must exist when the body exits! If necessary, the body can make copies of these arrays.

An Example

Here’s a code fragment lifted from the circulate-structures module. Circ-basic-block traverses a basic block within an encapsulator from the bottom-up, applying circ-loop-instruction to every loop encapsulator in the block.

(defun circ-basic-block (encapsulator surface)
  (with-basic-block-array (instruction-array encapsulator-array encapsulator surface)
    instruction-array
    (map nil #'circ-encapsulator encapsulator-array)))
(defun circ-encapsulator (encapsulator)
  (loop for block in (instruction-block-names encapsulator) do
(circ-basic-block encapsulator block))
  (when (eq (instruction-opcode encapsulator) :loop)
    (circ-loop-instruction encapsulator)))

Iterating Without Blocks

The with-instruction-array stores all instructions in a program graph into an array, not separating encapsulators from simple instructions and not heeding block boundaries.

with-instruction-array (instruction-array dfgraph) body  [Macro]

<instruction-array> ::= symbol

<dfgraph> ::= <lisp form evaluating to a dataflow graph>

Instruction-array is bound to an array whose elements are all the instructions in the dfgraph. Instruction-array contains a pointer to every instruction in the graph, including those hidden by encapsulators. The restrictions for array reuse in with-basic-block apply to with-instruction-array. Note, that when dealing with program graphs, with-basic-block is preferred.

1.11 Anchors, Signals and Triggers

Though program graph’s are machine independent, they are also the preferred site for adding some machine dependent features. The fact that these transformations occur in the machine-independent “middle-end” is just a matter of semantics. In fact, it’s more correct to view the middle-end as a mixture of machine independent optimizations and some machine dependent transformations. I describe these concepts here because the modules that implement them work on program graphs as defined above.

1.11.1 Signals and Triggers

The abstract model of dataflow graph execution, though useful for reasoning about graph transformations, has flaws that make it hard to realize directly in executable machine instructions. The requirement that every instruction in a basic block execute exactly once, when all inputs are presented, needs clarification. In a block, reachable instructions with inputs fire after inputs are presented to the basic block since tokens will travel to every reachable instruction. However, constant instructions with no inputs, are not reachable from the block’s inputs and have no local method of determining when to fire. Similarly, it’s often necessary to know when every instruction in a block has executed since the resources required by the graph’s execution can be deallocated. But again, instructions with no outputs don’t contribute to the outputs of the block making a simplistic check of the outputs insufficient.

In order to solve the above problems and make dataflow graph evaluation easier to implement, two new software abstractions are added to our model of program graphs: signals and triggers. In essence, adding signals and triggers to the program graph gives every instruction at least one input and one output, making the question of when an instruction fires simple to determine. As a first approximation, trigger inputs are added to instructions with no other inputs and signal outputs are added to instructions with no other outputs:

Definition 7 A Trigger is an additional input to an instruction which must receives a token whenever a set of inputs arrive (the trigger may itself be the only input).

Definition 8 A Signal is an additional output of an instruction which emits a token whenever the instruction fires and a set of outputs appear (the signal may itself be the only output).

With these definitions in hand, we can define triggers and signals for basic blocks:

Definition 9 A Block Trigger is an additional input to a basic block that receives a “trigger token” whenever inputs arrive at the block. One token is received for every complete set of inputs that arrive.

Definition 10 A Block Signal is an additional output from a basic block that must emit a “signal token” after every instruction with a signal output fires.

Note, a block signal indicates only that instructions with signal outputs have fired. All instructions in a block have fired only after all outputs from the block (including the block signal) emit tokens.

Definition 11 A Signal Tree is a graph of instructions with n-inputs and one output that fires after receiving all it’s inputs.

A block signal is normally computed by connecting it to the output of a signal tree whose inputs are connected to all the signal outputs in the block. Though the addition of signals and triggers is closely related to a particular machine implementation, it’s easier to add them at the program graph level

1.11.2 Anchors

Signals and triggers make the semantics of basic blocks explicit by providing paths from a block’s inputs to all its instructions and from all its instructions to its outputs. However, signals and triggers also complicate the graph considerably and are usually added just before leaving the middle end. Before their addition, blocks can contain subgraphs with no paths to the block’s inputs or outputs (for example, constant instructions connected to purely side-effecting instructions). During optimizations it’s easier to work with fully connected graphs, so extra inputs are provided to “anchor” all instructions with either no inputs or outputs.

Definition 12 An Anchor is an additional input to an instruction with either no input’s or output’s that serves to keep blocks connected.

Definition 13 A Block Anchor is an additional input to a basic block that connects to every instruction in the block with no inputs or outputs

Semantically, anchors are superfluous. They are merely a convenience to the programmer, providing a simple way to keep blocks connected.

1.12 Program Graph Properties

What follows is a list of currently used program graph properties:

constant-p :boolean True for constant instructions and loop constants. propagatable-constant-p strict-p :boolean True for instructions which are strict in all their arguments. folding-function : value^{n} − > value^{m} Function which “executes” an instruction, taking n inputs and returning m outputs. side-effecting-p :boolean True for instructions that are non-functional. Includes those that allocate unfilled storage for aggregate structures as well as explicit store instructions. apply-like-p :boolean True for any instruction that matches the type signature of the apply instruction. Apply-like instructions are used to apply a function whose arity won’t be satisfied by the given arguments. encapsulator-propagation-alist create-like-p :boolean True for instructions that return a pointer to an aggregate structure that can be fetched from or stored into store-like-p :(list Input-port Output-port fe-Match-p) Instructions that store into part of an aggregate data structure. All store-like instructions are side-effecting. fetch-like-p :(list Input-port Output-port fe-Match-p sfe-Match) Instructions that retrieve part of an aggregate DS created by a create-like instruction. Where: fe-Match-p = (store-inst x fetch-inst − > boolean) is the type of a function which returns true if the fetch instruction retrieves the same item put in by the store instruction (ie storing and fetching on the same index). sfe-Match = (make-inst x fetch-inst − > input-Port) is the type of a function which returns the make-inst’s input port name that corresponds to the object the fetch instruction is fetching. For example, if (match :sfe-match ),(cons :make-inst ) and (head :fetch-inst ) then (match

cons head) returns `(:input .  0).

legal-unconnected-inputs : legal-unconnected-outputs : associative-p :boolean True for associative instructions. inhibit-constant-propagation k-allocator : k-deallocator : opcode-machine-translation : generate-ets-function :pg-inst − > ets-machine-graph Generates an ets machine graph for a given program graph instruction. sr-before-function :

1.13 Program Graph Slots

What follows is a list of currently used program graph slots:

instruction-unfold-count :copyable-p ti instruction-peel-count :copyable-p t instruction-loop-type :copyable-p t

Chapter 2

Middle End Modules

2.1 Introduction

The program graph structure is extremely flexible and expressive. Constraining middle end modules to work on program graphs is hardly a restraint since the number of different types of instructions in a program graph is indefinitely extendable. In retrospect, the design of the Id compiler is complicated by an intermediate language that is too flexible (though extensions to the core of the intermediate language are easier to express, if not implement). Without a more restrictive notion of an intermediate language, adding new program graph instructions can impinge on every module in the middle end. For ease of development, it’s probably best, to define several intermediate languages, each a small perturbation of the other, which have modules that work exclusively on them. Other, more general modules can be defined to work with every perturbation. In actuality, the Id compiler implements this scheme, but its boundaries are hard to define without close examination of the compiler’s code.

2.2 Ordering the Modules

The middle end modules can be divided into two categories: tranformation and optimization. Optimization modules perform machine independent optimizations within a given intermediate language. They can be used in any order, any number of times (including not at all). Transformation modules, convert one intermediate language to another. Usually they perform a small perturbation of the intermediate language by either excising opcodes, adding opcodes or enforcing some machine dependent constraint on the graph. They must be used exactly once in a sensible order.

• The following modules transform the program graph:

generate-program-graph  Creates a program graph from a parse tree.

      manager-synchronization  Connects release instructions.

call-substitution  Stores inlinable functions in the Exsym table.
synchronize-release  Translates the synch instruction.
thunk-splitting  Translates the thunk instruction.

      inlineable-definitions  Inlines functions.

loop-constant-propagation Inserts loop-constant instructions.
code-blocks  Splits loop’s into seperate code blocks.
loop-analysis  Determine’s when a while loop can be used as a for loop.
unroll-loops  Unroll and unfold loops.
signals-and-triggers  Insert signals and triggers into the graph.

The above ordering of transformation modules gives a middle end with a minimum number of modules.

• The following modules optimize the program graph:

fetch-elimination  Remove fetch’s when a corresponding store found.
simple-fetch-elimination Remove fetch’s from functional data-structures.

      dead-code-elimination  Remove dead code.

constant-propagation  Propagate constants through encapsulators and bodies.
cse-and-hoisting  Common subexpression eilmination and hoisting out of loops.
partial-evaluation  Simplify some algebraic identities.
circulate-structures  Hoist allocate’s and deallocate’s out of loops.

Note, a minimal middle end won’t necessarily compile quickly since some optimizations shrink the the program graph’s size considerably.

2.3 The Modules

Each module description briefly describes some high-level characteristic of the module, including:

Module: The defcompiler module definition.

Options: A description of the module’s options.

Description: A declarative description of the module’s effect on the program graph.

Strategy: The module’s method of traversing the graph.

Author: Primary person responsible for coding.

Caveats: Known limitations, warnings, points of interest etc.

Each module in the middle end of the compiler reads or modifies a number of global data structures in addition to its explicit program graph argument and result. The following entries, for each module, provide information about its usage of global data structures:

Exsym Properties: External symbol properties.

Graph Properties: Dataflow graph properties.

Instruction Properties: Program graph instruction properties.

Instruction Slots: Program graph instruction slots.

Not each module has all the entries filled in. If a module is the first to define an entry in a global structure or is the exclusive user of an entry then the entry’s name is in boldface followed by a description. Otherwise, just the name is listed.

2.3.1 Generate Program Graph

Module:

(defcompiler-module generate-program-graph id-compiler
  (:input parse-tree procedure)
  (:output program-graph procedure)
  (:options check-bounds)
  (:function gpg-definition))

Description: The primary function of this module is to transform the parse-tree into a program graph. Pattern matching is also compiled out at this stage, although it should probably be done at an earlier module.

1

Strategy: The information obtained from the scope-analysis module is used to wire together instructions, given the parse-tree.

Author: Ken Traub, October 1986.

Caveats: Pattern matching should logically being in the desugaring module in the front end. At this point, it would probably be too difficult to change move this code there.

2.3.2 Fetch Elimination

Instruction Properties: store-like-p, fetch-like-p

Module:

(defcompiler-module fetch-elimination id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options fetch-elimination)
  (:function fe-code-block))

Description: Fetch elimination traverses the program graph searching for instructions storing values into data aggregates. When a “store-like” instruction is found it looks back from it’s inputs for the create instruction allocating the aggregate. If found it follows the aggregate’s other uses looking for other fetch instructions retrieving information placed in the aggregate by the store. These fetches can be eliminated by rewiring from the store instruction’s input.

Strategy: Uses with-instruction-array to traverse every instruction in the graph, hence it doesn’t do fetch elimination across encapsulator boundaries^{2}. Fetch elimination is defined for istructures, tuples, sums and cons.

Caveats: Fetch elimination doesn’t look across encapsulator boundaries.

2.3.3 Simple Fetch Elimination

Instruction Properties: fetch-like-p

1Nikhil and Arvind figured out the algorithm for doing pattern matching regardless of the order of the patterns.

The algorithm for this is described in the file: /jj/nikhil/haskell/pattern-matching.text Unfortunately, this file has not been published – perhaps it should be turned into a CSG memo. Other pattern matching algorithms can be found in Simon Peyton Jones’s book [?]J90.

2To with-instruction-array an encapsulator’s subgraphs are disjoint from the graph containing the encapsulator.

Logical connections between the two are determined by the semantics of the encapsulator and are captured, for simple cases by an encapsulator’s encapsulator-propagating-alist property

Module:

(defcompiler-module simple-fetch-elimination id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options fetch-elimination)
  (:function sfe-code-block))

Description: Traverse the program graph searching for instructions fetching from a data aggregate. When the fetch is from an aggregate allocated by a functional create instruction (determined by the result of sfe-match) then the fetch instruction can eliminated by wiring directly from the create instruction’s input.

The following pairs of functional <constructor, selector> instructions can be “short-circuited” (ie. an input of the constructor instruction can be wired around the selector function. The, no longer connected, selector function can be removed.

<make-functional-tuple, tuple-fetch>
<make-functional-sum, sum-fetch>
<make-functional-sum, disjunct-number>

Strategy: Uses with-instruction-array to traverse every instruction in the graph, hence it doesn’t look across encapsulator boundaries.

Author: Jonathan Young, September 1988.

Caveats: Simple fetch elimination doesn’t look across encapsulator boundaries.

2.3.4 Dead Code Elimination

Instruction Properties: side-effecting-p, create-like-p

Module:

(defcompiler-module dead-code-elimination id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options dead-code-elimination)
  (:function dce-code-block))

Description: There are three types of dead code elimination:

1. Remove non-encapsulating, non-side-effecting instructions with unused outputs.

2. Remove arcs from encapsulators.

(a) If there is an if output not used, then disconnect the corresponding arcs feeding the

         interior then-output and else-output.

(b) If there is an if input or loop constant not used within any interior blocks, disconnect the corresponding arc feeding the exterior.

3. Find structure creating instructions that only feed structure storing instructions. Remove both the creating and storing instructions.

Strategy: Traverse the program graph doing 2a on the way down for each level. On the way up do 1 for all non-SE instruction in the basic-block (searching out the largest subgraphs with unused outputs) and 3 for all create-like instructions. Finish each level by doing 2b.

Author: Ken Traub, June, 1987

Caveats: Step 2 should be generalized to other encapsulators. Neither entire encapsulators, useless circulating variables from loops, or dead but cyclic portions of the graph are eliminated. Not all the dead code is caught in one pass.

2.3.5 Constant and Loop Constant Propagation

The constant propagation module and the loop constant propagation module use the same internal functions and differ only in the way they handle propagation of loop constants.

Instruction Properties: folding-function, inhibit-constant-propagation.

Module:

(defcompiler-module constant-propagation id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function cp-dataflow-graph)
  (:options constant-folding constant-propagation)

Options:

constant-folding :boolean Whether to evaluate constant expressions at compile time. constant-propagation :boolean Whether to propagate constants through encapsulators at compile time.

Description: Constant propagation,

1. Evaluates expressions involving only constants.

2. Pushes constants through encapsulators.

3. Removes encapsulators that choose which internal block to execute based on a constant expression by unencapsulating the appropriate block.

Strategy: Traverse the program graph top-down. At each level identify constant instructions and either evaluate (fold) them (creating a new constant instruction) or, depending on where on an encapsulator they are connected, push them in or use them to unencapsulate a block. If any blocks are unencapsulated then iterate the process again at the same level. Otherwise, recurse on the next lower level of the graph.

(defcompiler-module loop-constant-propagation id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function lcp-dataflow-graph)
  (:options constant-folding constant-propagation

Description: The loop constant propagation module, uses the same code as the constant propagation module except it performs an extra transformation on loop encapsulators. In addition to the constant propagation optimizations, it removes constant arcs from the predicate and body blocks of loop encapsulators and makes them the first variable arcs, splitting each arc with a loop-constant instruction. Only constants actually used within the body or predicate are retained.

Caveats: The loop-constant conversion is a machine specific optimization. It turns free-variables occurring inside loops into constants that must be evaluated before any of the loop’s iterations begin. Conceptually, it belongs in the back end.

2.3.6 Code Block Partitioning

Graph Properties:

code-block-summary : See below.

n-loops :

constant-area-size :

Program Graph Instructions:

The fastcall-apply instruction applies a code-block to n args and get m results.

The fastcall-def instruction defines a code block taking n args and returning m results.

Instruction Properties: side-effecting-p

Module:

(defcompiler-module code-blocks id-compiler
  (:input program-graph procedure)
  (:output program-graph procedure)
  (:function cb-procedure))

Description: The code block partitioning module takes a procedure’s program graph and splits off each of the graph’s loop encapsulators into their own code block. These code blocks are contained inside fastcall-def encapsulators and linked into from the existing code blocks with fastcall-apply. For efficiency, both the loop encapsulator and any of its constant inputs are lifted into the fastcall-def. As configured, the module limits every code block (including the top-level def) to at most one loop.

Naming Conventions: If the top level procedure is named F and has n code-blocks lifted out then their names are F-0, F-1, …, F-(n-1). Similarly, if F-i has n code blocks lifted out then their names are F-i-0, F-i-1, …, F-i-(n-1), etc.

1. Each code block has the same :procedure-name property as the outer code block.

2. The outer code block has a :code-block-summary property describing the names of code blocks lifted out and their hierarchy: (F (F-0) (F-1 (F-1-0))) says F has three code blocks lifted out, two from the body of F and one from the body of F-1.

Strategy: Code block partitioning proceeds top-down, splitting off all loop instructions at a given level before proceeding into the next level of encapsulators. It differentiates between loops at the top-most level and ones nested inside other loops. The first top-level loop is kept in the original code block and all others are split out. When a loop instruction is found and split out, all the constants attached to the loop’s inputs are taken along with the loop.

This module should be called immediately prior to signal and trigger generation.

Author: Ken Traub, May, 1986.

Caveats: The module’s name should say something about loops! Also, it uses a hack to find the constant instructions connected to a loop’s inputs which doesn’t always give the best results. The coding style might benefit from some graph cut and paste abstractions.

2.3.7 Inlinable Definitions

Exsym Properties:

:inlinable-definition :(string → dfgraph) maps procedure name to copy of dataflow-graph

Graph Properties: :inlinablep, :procedure-name

Module:

(defcompiler-module inlinable-definitions id-compiler
  (:input program-graph procedure)
  (:output program-graph procedure)
  (:function ild-procedure))

Description: For every code-block with the :inlinablep property true, make an entry in the current exsym table associating the procedure name of the code-block with a copy of the codeblock.

Caveats: Inlinable definitions must come before call substitution.

2.3.8 Call Substitution

Exsym Properties: :arity, :inlinable-definition, :recursive-set.

Instructions:

:direct-apply :instruction Known arity application (is not apply-like and is side-effecting). :apply-unsatisfied :instruction Unfulfilled arity application (is apply-like and not sideeffecting).

Instruction Properties: side-effecting-p, apply-like-p.

apply-like-p :boolean True for apply or apply-unsatisfied instructions

propagating-input-p :(encapsulator x input → boolean) True if input of encapsulator propagates to each block.

Instruction Slots:

instruction-cs-forwarding :? forwarding pointer from instruction which has all its connections moved to another instruction.

Module:

(defcompiler-module call-substitution id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options call-substitution)
  (:function cs-code-block))

Description:

1. Replaces a chain of applications of correct arity with :direct-apply (works across encapsulator boundaries) taking a :code-block literal (as the function) and n arguments.

2. Replaces applications of incorrect arity with :apply-unsatisfied

3. Performs inlining for identifiers having the :inlinable-definition property

(a) If the identifier is a constant then plug in its definition

(b) If the identifier defines a function, then replace a :direct-apply by the code-block for the function (if it’s not in the :recursive set of the top-level definition, to avoid infinite unwinding). Only full arity applications will be inlined.

Strategy: Traverse the program graph top-down. For each encapsulator, attach a source to the encapsulator’s anchor output. For every block in the encapsulator, first traverse every simple instruction, searching for identifier literals. Inline inlinable constant identifiers. For every nonconstant identifier, follow its application chain (perhaps into an encapsulator) and convert it to either a direct-apply on a code-block literal or a chain of apply-unsatisfieds. For every inlinable code-block literal, inline the function body (subject to the recursive constraint) and recursively do call substitution on its body. Finally, do call-substitution for every encapsulator in the current block.

Caveats: The code for cs-inline-function could use some abstractions. A function application can only be inlined if the function’s arity is satisfied by its arguments. It seems like there may be a cleaner and more efficient way of handling this optimization.

2.3.9 Common Subexpression Elimination and Code Hoisting

Instruction Properties: side-effecting-p, associative-p.

Options:

cse :boolean Whether to eliminate common subexpressions hoist :boolean Whether to hoist invariant subexpressions from loops

Module:

(defcompiler-module cse-and-hoisting id-compiler
(:input program-graph code-block)
(:output program-graph code-block)
(:function csech-dataflow-graph)
(:options cse hoist))

Description: This module combines two interrelated but conceptually independent optimizations, Common Subexpression Elimination (CSE) and Code Hoisting (CH)

CSE Common Subexpression Elimination (CSE) merges duplicated expressions that compute the same function on the same inputs. CSE is done only within a given code block and only for purely functional expressions composed entirely of simple instructions (see caveats). There is no attempt to detect and eliminate equivalent encapsulators (the rationale being that this case won’t occur often).

Combine Equivalent Inputs to Encapsulators CSE may make some inputs of a loop or seq encapsulator redundant and they should be eliminated before CH or else code may be duplicated when lifted out through the encapsulator inputs.

CH Code hoisting (CH), lifts invariant computations out of loop and seq encapsulators:

seq Non-constant (ie having at most one input), pure functional instructions connected to the seq inputs and their successors are hoisted out of the encapsulator “through their inputs.”

loop Loop expressions are reassociated and hoisted from both the predicate and body:

1. Find loop invariant expressions (called loop “constants” in the code), pure instructions (and their successors) connected to “constant inputs” or literal values.

2. Find loop variant expressions, instructions that have any input from the loop variable inputs or any non-functional instruction.

3. Chains of n associative instructions with the same opcode are re-associated to form a tree of log(n) depth with invariant and variant inputs partitioning the leaves from left to right.

4. Hoist loop invariant expressions outside the encapsulator.

Strategy: CSE and CH occurs bottom-up:

1. Recursively CSE-CH all the encapsulators (hoisting out invariants, which must be simple and functional).

2. CSE all the simple, functional instructions in the basic block.

3. Combine equivalent inputs for all encapsulating instructions in the block.

Author: Ian Lance Taylor, May ’87

Caveats:

1. Application is assumed to always be side-effecting.

2. Encapsulators are assumed to always be side-effecting.

3. Reassociation is a general notion that should be applied everywhere, not just in loops.

4. Invariants aren’t hoisted out of if encapsulators.

There should be a general abstraction to make lifting instructions out or pushing them into an encapsulator easy.

2.3.10 Loop Analysis

Instruction Slots:

loop-parameters :(keyword init-source upper-source step-source) Identifies the type of loop and sources for its bounds (see below).

Module:

(defcompiler-module loop-analysis id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function la-dataflow-graph))

Description: For every loop instruction, Loop-analysis examines the predicate and body to determine if the loop is equivalent to a simple for construct. If so, the module builds a piece of graph which computes the number of iterations and wires it into the loop as a new loop constant. Also, set up the loop-parameter slot to hold the sources for the loop’s initial value, upper-limit and increment.

Strategy: Proceed top-down, analyzing loop instructions.

2.3.11 Loop Unfolding and Unrolling

Instruction Slots:

peel-count :integer - number of times to peel loop unfold-count :integer - number of times to unfold loop sequential-loop-p :boolean - set true if loop is sequentialized

(defcompiler-module unroll-loops id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function ul-dataflow-graph))

Description: Performs loop unfolding and unrolling. An unrolled loop executes k copies of the loop’s body (ie k copies of the program graph corresponding to the loop’s body wired in series) before entering the loop itself. Inother words, it unroll’s k iterations from the start of the loop. Loop unfolding executes k copies of the loop’s body for every iteration of the loop. Of course, care must be taken that termination during an unfolded or unrolled body exits the loop correctly (which is accomplished by analyzing the loop’s behavior or by inserting checks of the loop’s predicate around every body).

Strategy: Proceed bottom up, replacing loop instructions with their unrolled or unfolded equivalents when the unroll-count or unfold-count is non-nil. Whileloops use the most general unfolding strategy, nesting additional conditionals around every new body graph. For loops are compiled without this additional overhead by changing the loop’s predicate and adding a series of (k-1) nested conditionals.

Author: Jamey Hicks, September 1989

Caveats: The terms unpeeling and unrolling are used interchangeably.

2.3.12 Circulate Structures

Instruction Properties: side-effecting-p, create-like-p, k-allocator, k-deallocator

Module:

(defcompiler-module circulate-structures id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options circulate-structures)
  (:function circ-code-block))

Description: Attempts to find structures that are allocated and deallocated within a given loop body. If a structure with these properties exists, its allocation and deallocation code is lifted out of the loop. [A k-bounded loop will have k copies of the structure allocated before starting?]

Strategy: Circulate structures proceeds bottom-up through the graph hoisting allocation and deallocation code out of loop encapsulators at each level on the way up.

Author: Jamey Hicks

2.3.13 Algebraic Identities (misnamed partial-evaluation)

Module:

(defcompiler-module partial-evaluation id-compiler
(:input program-graph code-block)
(:output program-graph code-block)
\#+DEBUG (:before-function program initialize-partial-evaluation)
(:function pe-dataflow-graph)
\#+DEBUG (:after-function program print-partial-evaluation-statistics)
(:options partial-evaluation))

Description: The algebraic identities module defines a set of rewriting rules for program graph fragments. A program graph fragment is some subgraph of the program graph all of whose instructions can be reached from a single instruction. A pattern is a parenthesized expression that can match a graph fragment:

<pattern> ::= (<opcode> { <input>* |<every-input> } <output>* [<triggers>] ) <simple-pattern> ::= variable |constant |<pattern> <opcode> ::= opcode [$parameter <sexp>] <input> ::= :input <simple-pattern> <every-input> ::= ($every <sexp>) <output> ::= <simple-pattern> <triggers> ::= :triggered-by <pattern>*

For example, (:intimes :input 1 :input x) represents an integer multiply instruction with two inputs.

(:make-functional-tuple ($every :component i) (:tuple-fetch $parameter i :tuple

x)) represents a tuple creating instruction connected to a tuple fetch instruction.

The module compiles a set of rewrite rules which describe how to rewrite existing patterns into new patterns. Sets of rewrite rules are defined by the defevaluator macro:

defevaluator name input-pattern output-pattern {constraint}∗  [Macro]

<name> ::= symbol <input-pattern> ::= ($or <pattern>*) |<pattern> <output-pattern> ::= <pattern> <constraint> ::= <lisp form>

The module searches for instructions matching the applicable rewrite rules. If any instruction matches against the input pattern of a defevaluator then that graph fragment is replaced by the output pattern if all the constraints evaluate to true.

For example, a defevaluator for additive integer identity might look like:

(defevaluator plus-zero
($or (:intplus :input 0 :input x)
  (:intplus :input x :input 0))
x)

Notice that repeated variable names refer to the same instruction in the scope of one defevaluator. Currently, there are defevaluators to do:

1. Algebraic simplification for integers and floats:

x + 0 = 0 + x → x x ∗ 0 = 0 ∗ x → 0 x ∗ 1 = 1 ∗ x → x

2. Reduction in strength for exponentiation

x^{2} → x ∗ x x^{3} → x ∗ x ∗ x

3. Algebraic simplification for booleans:

x ∧ x → x true ∧ x = x ∧ true → x false ∧ x = x ∧ false → false x ∨ x → x true ∨ x = x ∨ true → true

4. Fetch elimination for functional data-structures

5. Removal of gates controlled by constants

6. Swapping of form-address with set-ip instructions

(:set-ip :input (:form-addr :input x :input offset) :input ip) →
(:form-addr :input (:set-ip :input x :input ip) :input offset)

7. Composition of form-address instructions

(:form-addr :input (:form-addr :input x :input offset1) :input offset2) →
(:form-addr :input x :input (:intplus :input offset1 :input offset2))

Strategy: The algebraic identities module proceeds top down, trying first to rewrite graph fragments in the current basic block, before proceeding to basic blocks within encapsulators. New instructions created by the rewrite rules are added to the list of instructions to traverse within the block.

Author: Ken Traub

Caveats: The module searches the rewriting rules in order of their definition. This may not be the best strategy. Pathological rewrite rules might cause the compiler to enter an infinite loop.

2.3.14 Thunk Splitting

Graph Properties: Adds new code blocks to the current graph.

Module:

(defcompiler-module thunk-splitting id-compiler
(:input program-graph procedure)
(:output program-graph procedure)
(:function ts-proc))

Description: Delay encapsulators take arguments to a delayed expression and an address to store the result of the expression when evaluated. Thunk-splitting implements the delay abstraction by removing delay encapsulators and replacing them with lower level instructions. In detail, thunk-splitting implements the following: it encapsulates the delayed expression in a defthunk encapsulator and places it in its own code-block with the name “ i-THUNK- .” It replaces the delay encapsulator with a pair of make-thunk/store-thunk instructions which take the arguments to the delayed expression, the address to store the delayed value in (when it’s lazily computed) and the name of the thunk’d expressions code-block.

Strategy: Proceed bottom-up, transforming delay encapsulators into make-thunk/store-thunk pairs and add one defthunk code-block, for the delayed expression, to the current set of codeblocks.

Author: Jamey Hicks and ?

Caveats: Thunk splitting is very implementation dependent and should be considered part of the back end.

2.3.15 Synchronize Release

Instruction Properties: encapsulator-propagation-alist

sr-before-function :? Only defined for loop instructions. Function that given a loop instruction, seems to peel it once if it contains a loop-release and hasn’t been unrolled already. Jamey says that this has something to do with releasing nextified variables that are garbage after at least one iteration.

Instruction Slots:

instruction-unrolled-p :boolean Set for an unrolled loop instruction by sr-before-function

Module:

(defcompiler-module synchronize-release id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function sr-dataflow-graph))

Description: Synchronize-release implements the synch instruction in terms of the seq encapsulator and other simple instructions. Basic blocks containing synchs are wrapped in seq encapsulators. Conceptually, synch instructions and the instructions that depend on their outputs are moved outside the seq and synchs are turned into gates controlled by the seq’s completion signal.

Strategy: Synchronize-release proceeds bottom-up, (partially) wrapping every basic block containing a synch instruction with a seq encapsulator. It finds all the outputs of the block that don’t depend on synch instructions and wires them as the body outputs of the seq. All synch instructions and their successors are moved outside the encapsulator and replaced by gates controlled by the seq’s termination signal.

Author: Jamey Hicks

2.3.16 Manager Synchronization

Description: Manager-synchronization implements finer grain control over mutable structures than is possible using only block signals. Using Id’s enter construct, mutable data-structures can be atomically read and modified using a locking mechanism. Manager-synchronization makes the “unlocking” of the structure occur after all its uses within the enter block, but before the block itself terminates.

Strategy: Generate-program-graph creates enter and release instructions that delimit the scope of Id’s enter construct. The arc corrsponding to the imperative data-structure named in the enter statement is wired to the input of the enter instruction by generate-program-graph. Also, enter instruction’s outputs are wired to every use of the data-structure. In manager-synchronization, the release instruction (wired to the block’s signal by gpg), receives a signal tree taking its inputs from all the uses of the data-structure.

Author: Paul Barth

Caveats: This could (and probably should) be done by desugaring.

2.3.17 Signals and Triggers

Module:

(defcompiler-module signals-and-triggers id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function st-dataflow-graph))

Instruction Properties: strict-p,legal-unconnected-inputs,legal-unconnected-outputs

Description: Adds signals and triggers to the program graph, as described in the previous chapter.

Strategy: Signals-and-triggers proceeds top-down, adding block signals and triggers to every block in every encapsulator, then wiring them to the appropriate instruction signals and triggers.

Author: Ken Traub

Caveats: I’m not sure how much optimization goes on here, but there should be ample opportunities.