Expander¶

Overview¶

The primary purpose of the expander module is to translate the ILMs produced by the semantic analyzer into ILIs, the internal language that is processed by the LLVM-bridge. The LLVM-bridge then converts the ILI into LLVM Intermediate Representation (IR).

During ILM to ILI translation, the ILIs are grouped into blocks, where the extent of a block is determined by certain compiler options and the characteristics of the control flow ILMs.

For each block, the expander creates a block information header (see later sections for more detail) which describes the contents of the block. In addition, global information is gathered. This includes:

a names table reflecting precisely the variables being referenced (e.g., \*p, st.x, a[i], etc.). These entries are accessed by the the ILI which perform loads and stores.

The expander is separated into language dependent and language independent modules. The Fortran-specific portions of the expander are contained in exp_ftn.c.

Data Structures¶

Global Data Structures Used¶

Symbol Table — described in section 11.

ILMs — internal representation of executable statements read from a temporary file into an area used by the semantic analyzer and the expander. Refer to section 12 for a general description and appendix IV for a list of the ILM opcodes and descriptions of their meanings.

Static ILM Information — Static tables describing the ILM to ILI table driven expansions, ILM attributes, etc. This information is generated by the ILMTP utility. Refer to section 12 for a general description and appendix IV for a list of the ILM opcodes and descriptions of their meanings.

ILIs — internal representation created by the expander which are shared for an entire source file (across all functions in that source file). The ILIs are maintained in a single dynamic memory area. This area is an array of unsigned short ints. Refer to section 13 for a general description and appendix V for a list of the ILI opcodes and descriptions of their meanings.

Static ILI Information — Static tables describing ILI attributes, etc. This information is generated by the ILITP utility. Refer to section 13 for a general description and appendix V for a list of the ILI opcodes and descriptions of their meanings.

ILTs — internal representation created by the expander which represents the terminal nodes of an ILI “statement”. An ILI statement may be a function call, a store, register move or a branch. A sequence of ILTs represents a block of ILIs.

BIHs — block information header table. Refer to section 13 for a description.

NMEs — name table entries. Refer to section 13 for a description.

ILM Area¶

This area is a single dynamic memory area (an array of short ints) used to hold the ILMs read in for a block. This space is allocated by the semantic analyzer and freed by the expander. An additional memory area (an array of structs) is used to store auxiliary information created for an ILM by the Expander. This area parallels the area used for reading in ILMs; that is, an index (relative offset from the beginning of the ILM area) locating an ILM also locates the auxiliary structure for that ILM. After an ILM is expanded, the pointer (actually an unsigned int offset from the beginning of the ILI area) to the ILI which is considered the result of the ILM may be stored in its (the ILMs) auxiliary structure. This is done for those ILMs which may be “linked” to by other ILMs. References to an ILM whose result has been saved is just an indirection through this word. In addition, for those ILMs which produce an address result (e.g, a “reference” ILM, a pointer load ILM, etc.), the index to the names table entry representing the reference is stored in the ILM’s auxiliary structure. For certain ILMs (stores and pseudo stores), the ILI block index (a BIH index) is stored in the auxiliary structure indicating the ILI block which contains the store or pseudo store ILI for the ILM (see section 6.3.6, Common ILM Expressions, for more details). Figure 6-1 shows the dependencies of the two areas.

	ILM Area		Auxiliary Area
	_		_
0		0
	…		…

	_		_
i	opc	i	ili	nme	blk
	_		_

	_		_

	_		_

	…		…

	_		_

i	index of an ILM
opc	opcode of the ILM
ili	index to the ILI created for the ILM at i
nme	index to the names entry created for the ILM
blk	bih index containing the ili for the ILM (see section 6.3.6)

Figure 6-1. ILM Areas The following variable, global to the expander module and declared in the file ilm.h, is used to locate the memory area and to give the size of the area:

struct {
    short ilm_base; /\* pointer to the memory area \*/
    short ilm_size; /\* size in units of short words \*/
    short ilmavl;   /\* available index (used by semant) \*/
} ilmb;

A definition for the parallel area occurs in the local expander data structure (described in the next section).

While an ILM is being expanded, it may be necessary to temporarily save pointers to ILI created. An ILI saved in this fashion is associated with a temporary number. The area used to remember the ILI is just a static array, local to the expander module and defined in the local expander data structure. This array is indexed by the temporary number, and is n words long, where n is a number sufficient for the temporary locations required by any one ILM macro. Any references to a temporary are just indirections through this area. Note that this number is hard-coded in expand.h and will have to be increased if the number of temp locations required by an ILM exceeds 9.

Local Expander Data Structure¶

The file expand.h contains the data structure (the structure exp) which is local to the expander module, and various C macros used to access the values of an ILM and its auxiliary information. Details about the structure exp can be obtained by examining the file expand.h. The ILM macros used by the expander module are:

ILM_OPC(ip), ILM_OPND(ip,j): used to extract the opcode and the j-th operand of ILM in the ILM area located by ip. ip is an absolute pointer (not an offset) to the ILM.
ILM_RESULT(ix): is used to store the result (and index to an ILI) of an ILM. The ILM is located by the index ix (the offset from the beginning of the ILM area to the ILM in units of short ints).
NME_RESULT(ix): used to store the “names” result of an ILM.
ILI_OF(ix): used to extract the ILI result of ILM located at index ix.
NME_OF(ix): used to extract the “names” result of ILM located at index ix.
ILM_BLOCK(ix): used to store and extract the block identification (a BIH index) of the block containing the ILI generated for ILM ix. This is used for the ILMs which are stores or pseudo stores.

Processing¶

Overview¶

The Expander module is divided into the following parts:

expand

This routine is the main routine of the expand module and is the routine which is called by the Program Controller. expand is responsible for reading in an ILM block, processing the terminal ILMs in that block, and for cleaning up after the block has been processed. expand processes ILMs by scanning through the ILM blocks calling eval_ilm on the terminal ILMs (an attribute in the static ILM information). Refer to Figure 6-2 for a high level description of expand.

exp_init() ;
while ( not end of ILM file ) {
   rdilms();    /\* this routine reads in the BOS ILM,
                   processes the BOS, and then reads
                   in the ILMS in the ILM block \*/

   for each ILM, located by index ilmx, in the block {
     if ILM is a terminal ILM
        eval_ilm(ilmx);
   }
}
cleanup expand module;

Figure 6-2. expand(^)

exp_init

This routine is called by expand to initialize the Expander data items and to allocate space for certain Expander data structures. This routine is called immediately before expanding any ILMs for the source program.

eval_ilm

This routine controls the main processing of an ILM. This routine is called by expand when expand sees a “terminal” ILM. The routine makes recursive calls on the ILMs operands which are links and have not yet been evaluated (ILI have not been created for it). If an ILM has already been processed, check_ilm is called to ensure that the ILI originally generated will be be used as a common expression (see section 6.3.6, Common ILM Expressions). eval_ilm sets three variables which are static to the expand module and are used by the various expansion routines: ilmp (a pointer, not an index, to the ILM being evaluated), curilm (the index of the ILM being evaluated), and opc (the opcode of the ILM being evaluated). Refer to Figure 6-3 for a high level description of the main expand process.

expansion routines

The ILMs are divided into two classes:

table driven expansion defined by the ILM macros. The routine exp_mac is responsible for expanding ILMs using the template or macro information created by the utility ILMTP.
special case ILMs. Several routines are responsible for these ILMs. The ILIs produced for these ILMs are determined by various conditions as determined by the routines. Typically, a routine will exist for each of the ILM types (i.e., reference, branch, load, store, etc.) which are to be special cased.

/\*  evaluate all operands of ilmp  \*/

for each ILM link operand, opnd, of ilmp
    if opnd has not been processed
        eval_ilm(opnd);
    else
        check_ilm(opnd);

define curilm, ilmp, opc;

/\*  evaluate ilmp  \*/

select processing for ilmp {

case ILM is table driven:
    exp_mac();

/\*  the following are special cased ILMS  \*/

case ILM is type reference:
    exp_ref();
case ILM is type branch:
    exp_bran();
case ILM is type procedure:
    exp_call();
case ILM is type load:
    exp_load();
case ILM is type store:
    exp_store();
case ILM is type arithmetic, constant, or miscellaneous:
    process ILM according to its opcode;
}

Figure 6-3. Expand Process

utility routines

These routines are called by the various expand routines to perform such functions as reading in a block of ILMs, creating and completing a basic block of ILI, and performing certain ILI optimizations, etc. These routines are found in the file exputil.c.

Important expander issues are discussed in the remainder of this section.

ILT Blocks¶

During expansion, ILT nodes are grouped into a unit called a basic block or extended basic block. A basic block of ILT nodes consists of a sequence of ILTs which can only be entered at the beginning and may be exited only at the end (it has a single exit point). An extended basic block is the same as a basic block except that there may be more than one exit. A basic block is formed according to the following rules:

The occurrence of the LABEL ILM causes a new block to be created provided that the label is referenced (its reference count is greater than zero).
A branch (conditional and unconditional) ends a block.
At opt level 0, at least one basic block is created for one ILM block (note that an ILM block always begins with a BOS ILM). At opt levels greater than 0, a basic block may span ILM block boundaries.

The operands of an ILI cannot span a block boundary. This can only occur if the operand of an ILM is a store or pseudo store ILM (refer to section 6.3.6, Common ILM Expressions).

/\*
   previlt - the previous ILT
   curilt  - the current ILT
   curilm  - current ILM being expanded
   optlvl  - opt level selected
\*/

-----  curilm is a BOS  -----

if (optlvl==0) {
   wrtilts();             /\* save block just created \*/
   create new block;
   process BOS;
}

-----  curilm is a LABEL  -----

   lbl = label defined by ILM;
   while (previlt is a branch which references lbl) {
      previlt = delilt(previlt);  /\* delete this ILT and
                               update previlt \*/
      rfcnt(lbl)--;
      if (branch deleted was in a jump table) break;
   }
   if (rfcnt(lbl) > 0 ) {
      wrtilts();  /\*  save block just created  \*/
      create new block;
   }
}

-----  curilm is one which creates an ILT  -----

if (curilt is a branch) {
   if (curilt is unconditional && previlt is unconditional){
      if (not in jump table) {
   delilt(curilt);   /\*  the result of delilt is
                         discarded  \*/
   curilt = NULL;
      }
   else {
      wrtilts();
      create new block;
      previlt = curilt;
      curilt = NULL;
   }
}
else {    /\*  just add curilt to block  \*/
   next(previlt) = curilt;
   prev(curilt) = previlt;
   previlt = curilt;
}

Figure 6-4. ILT Basic Block Creation

Extended basic blocks are created by the expander only at opt level 1. These blocks are formed according to the same rules as above except that a branch does not terminate an extended basic block (i.e., the block may have more than one exit point).

Creating a block initially involves creating a BIH for it and then adding ILTs. Whether an ILT is added to the block or causes a new block to be created depends on its type and the opt level selected. An ILT may be one of the following:

store: The ILT locates the store ILI created by a store ILM.
branch: The ILT locates the branch ILI created by a branch ILM.
procedure call: The ILT locates the function ILI that is called. The result of the function is either is type void or is discarded. This ILT may also be created when an ILT is deleted (since its expressions are scanned for function calls), or when the ESTMT ILM is processed.
move: he ILT locates a register move ILI.
entry/exit: The ILT locates the entry/exit ILI. Note that these ILTs are always in their own blocks at opt not equal to 1 or if the option debug was selected.

After an ILT is created, it is determined if the previous ILT (if one exists) is a branch. If so, one of four cases occurs:

the previous ILT is an unconditional branch which is not a member of a switch-jump table. The current ILT is deleted.
the current ILT is an unconditional branch. The previous ILT is deleted if the target labels are identical. Function ILTs may be created by this action.
The current ILT is an unconditional branch and the previous ILT is a conditional branch. The creation of the block is delayed until the next ILM is processed (this is a non-BOS ILM if the opt level is 1). If the ILM is a LABEL, then the following optimization is performed if the label is referenced by the conditional branch:

.CW
if (cond) goto y; goto x;

y: … .CE

.CW
if (!cond) goto x;

y: …
Otherwise, the previous block is complete. The current ILT becomes the first ILT of the new block.

If the previous ILT is not a branch, the current ILT is added to the current block.

When a LABEL ILM is processed, the following checks are performed:

The above-mentioned optimization (3) occurs if the conditions are satisfied. In addition, the reference count of the label described as x is decremented. If the label is not referenced by the conditional branch and the opt level is not 1, the ILT for the conditional branch is the last ILT of the current block. The ILT for the unconditional branch becomes the first ILT of the next block.
If (1) does not occur, the previous ILT is checked to determine if it is some sort of branch to the label. If so, the ILT is deleted and the label’s reference count is decremented. Deleting this ILT could cause a function ILT or ILTs to be created if it is a conditional branch.
If the reference count of the label is greater than zero (this check is performed regardless of the outcome of (1) or (2)), a new block is created with the label defining the beginning of the block.

When a BOS ILM is processed and the opt level is zero, a new block is created whose line number is extracted from the BOS. Otherwise, the line number is saved away for use by the next block created. Note that if multiple ILI blocks are created for an ILM block, all but the first block have their line numbers set to zero.

Debugger Interface¶

When the debug compiler option is selected, the first ILT of a block which is neither an entry nor an exit block is a call to the debugger routine dbg$i_line. This involves creating an ILI which is a call to the routine and an ILT which locates this ILI. Note that this is done for only those blocks which have non-zero line numbers.

ILM Macro Expansion¶

The routine exp_mac is responsible for expanding ILMs which are defined as macros as specified by the ILM template definitions. This expansion is straightforward and consists of looping through the template to add the ILI. All detail can be found in the code for the routine.

Reference ILMs¶

The routine exp_ref expands the reference ILMs (c BASE, ELEMENT, and MEMBER). The ILI generated represent the memory address of the reference. In addition, a names table entry is created which represents the reference. The cases are:

BASE sym

The add ILI routine, addili (described in section 13), is called to produce the ILI ACON sym' (where sym' is an address constant whose value is <sym,0>). The final result of this ACON is either the stack offset allocated to sym by the code scheduler (if sym is automatic or a dummy argument), or a relative offset allocated by the code scheduler from the beginning of its psect (if sym is static or external).

The add names entry routine, addnme (described in section 13), is called to create a names entry for the BASE ILM. addnme is called with a template which describes a names entry of type variable (c NT_VAR) whose symbol field is sym. This template is described as

<NT_VAR, sym, 0, 0>

(the last two 0’s represent a names table entry and a constant offset, respectively).

If sym is an argument of type double (on 32-bit machines), struct, or union, a LDA ILI referencing the ACON is also generated which will extract the argument’s address from the argument list. This is done since double (on 32-bit machines), struct, and union values passed to procedures are actually passed in temporaries. The address of the temporary is passed and it is as if the formal argument is a pointer to the double, struct, or union argument. The names entry created by addnme is used in the LDA.

ELEMENT base subs dt

base
is the base ILI of this reference.

subs
is the subscript ILI.

dt
is a pointer to the dtype record which represents the data type of the element and is used to compute the multiplier of subs. The multiplier is defined to be the size of each element in units of bytes. However, for certain machines, it is possible to use a scaling instruction which will scale a value before adding. Consequently, two values, size (the number of units to scale) and scl (the scale factor), are computed from dt using the function scale_of in the compiler module dtypeutil.c. The multiplier based on these values is size\*2\\*[scl\\*]. For a machine which does not have this capability, size is the number of bytes in each element and scl is 0.

The handling of ELEMENT depends on subs:

subs is a constant ILI (let c be its value)
```
(1)  ACON c \* size
(2)  AADD base (1) scl
```
Note that the constant c\*size may be folded into base by addili.

subs is i + c — add c\*size to the base

(1)  ACON c \* size       The constant may be folded into base.
(2)  AADD base (1) scl
(3)  ICON size
(4)  IMUL i (3)
(5)  DAMV (4)
(6)  AADD (2) (5) scl     i is added to the (new) base.

subs is i - c — subtract c\*size from the base

(1)  ACON c \* size       The constant may be folded into base.
(2)  ASUB base (1) scl
(3)  ICON size
(4)  IMUL i (3)
(5)  DAMV (4)
(6)  AADD (2) (5) scl     i is added to the (new) base.

otherwise,

(1)  ICON size
(2)  IMUL subs (1)
(3)  DAMV (2)
(4)  AADD (3) base scl

addnme is called with the template

<NT_ARR, arr, bnme, cnst>

to create a names entry for the ARRAY ILM. bnme is the names entry of the base ILI. arr and cnst combine to indicate if this array reference is one with constant subscripts. If subs is a constant, arr is 0 and cnst is the value of the constant subscript multiplied by size. Otherwise, arr is -1.

MEMBER base sym
base
is the base ILI of the reference.

sym
is the member symbol table item used to extract its offset from the beginning of the structure.
(1)  ACON offset
(2)  AADD base (1) 0

The names entry template for the MEMBER ILM is

<NT_MEM, psmem, bnme, 0> .

bnme is the names entry of the base ILI. psmem is the symbol table item which is the value of the pseudo member field of sym (refer to the section, Symbol Table).

Loads and Stores¶

The ILMs of type load and store perform loads and stores of “variables” (scalar, array element, structure member) and loads and stores of structures (the SMOVE ILM). The “variable” ILMs correspond to the C scalar types. Expanding these types of ILMs to ILIs involves chosing the ILI which reflects the size of the data type on the target machine. For the ILIs LD and ST (load and store data register), an additional operand value is used to denote the size of the fetch or store. These ILIs are of the form:

LD adr sym stc
ST val adr sym stc

where

adr: is a link to the address of the load or store
sym: is the names table entry of the reference
val: is a link to the value being stored
siz: is an immediate constant selecting size. These are of the form MSZ_<name> and are described in the ILI section.

The remaining ILIs are for loading and storing pointers (c PLD and PST), loading and storing doubles (c DLD and DST), and loading and storing floats (c RLD and RST) are of the form:

LDA/LDDP/LDSP adr sym	PLD/DLD/RLD
STA/STDP/STSP val adr sym1	PST/DST/RST

Each ILM has a link to an expression which represents the address of the quantity to be loaded or stored. For the load ILMs, this is the only link; for the stores, this is the first link. This link is also used to locate the names table entry of the entity being fetched or stored (the next word following that link contains the index to the names table entry).

For the PLD ILM, a new names entry of type indirection is created. The template for this entry is

<NT_IND, 0, sym, 0>

(c sym is the names entry located by link). The index to this entry is stored away in the second word of the PLD ILM.

For field operations, the LD or ST ILIs are used. The names table entry created for the referenced MEMBER ILM is used in these operations. The size of the operation depends on the LDSIZE field of the member symbol table item in the MEMBER ILM located by the address ILM link. This value is one of 1 (byte), 2 (half-word), or 4 (word) and indicates which memory unit in a load or store operation (byte, half-word, or word) is used to reference the field.

For the SLD or FLD ILMs, a LD ILI is generated which will fetch from memory the unit which contains the field. Following the LD ILI, a sequence of ILI is generated to extract from this unit the actual field, using either the field EXTRACT instruction, if one exists, or a left shift followed by a right shift. The end result is that the field is right justified in a data register. These shifts are calculated from the BITOFF, FLDSZ, and LDSIZE fields of the member symbol table item. The actual calculation depends on the bit ordering ( “big-endian” or “little-endian”) of the target machine. See the code for details.

For the FST ILM, a ST ILI is generated to store the value of the field and any bits from other members of the structure which are in the memory unit. Prior to the ST ILI, a sequence of ILI is generated to insert into a data register the value being stored. These ILI consist of shifts and masking operations, or field MERGE instructions if available, which are derived from the BITOFF, FLDSZ, and LDSIZE fields. Again, see the code for details.

Field load and store operations are optimized in cases where the field takes up a whole load unit (e.g., 8 bits), and when the field is left justified in the load unit.

The SMOVE ILM for the structure assignment, a = b, consists of three operands: addr link to the ILM defining the address of a expr link to the ILM defining the address of b sym pointer to the data type of the structure

The ILI generated for the SMOVE depend on the size and alignment of the structure type:

size of the structure is less than or equal to eight units, where units depends on the alignment and is one of bytes, half-words, words, or double words. For this case, the structures a and b are divided into size distinct units. A sequence of LD and ST ILIs are generated to move a unit of a to its position (according to the same offset for the beginning) in b. The names entries created for addr and expr are used in these ILIs.
size of the structure is greater than eight units. For this case, an external call ILI is generated to (depending on the alignment) one of c$bcopy (copy bytes), c$hcopy (copy half-words), c$wcopy (copy words), or c$dcopy (copy double words). These are procedure linkage routines whose arguments are n, a, and b where a and b are pointers to char, short, int, or double and n is the number of bytes, half-words, words, or double words to copy. Note that 8 is approximately the number of cycles for the call overhead <this will change and needs to be part of the MACHAR utility>.

Special ILMs called NCSELD and NCSEST are used to support the volatile type modifier of C. When a load of a volatile location is generated, it is covered by a NCSELD ILM. This generates a special names entry that forces the scheduler to always do the load (i.e., it is never optimized out).

When a store to a volatile location is generated, the store is covered by a NCSEST ILM. This generates a special names entry that forces the scheduler to always do the store. Note that, since both store ILMs and the NCSEST ILM are terminal, care must be taken to avoid calling the check_ilm routine on the store when it is covered by a NCESST ILM.

Pseudo Stores¶

The pseudo store ILM, PSEDUOST, is generated by the semantic analyzer for postfix operations. For example, i++ causes a PSEUDOST to be generated which will represent the original value of i. Subsequent uses of i, in particular the add, will locate this ILM. The expander creates a pseudo store ILI which is one of FREEIR, FREEAR, FREESP, or FREEDP, depending on the type of the register needed to load i. Subsequent references to this ILM will cause the expander to create an ILI to ensure that the reference uses the original value of i instead of the updated value of i (refer to section 6.3.6, Common ILM Expressions).

The PSEUDOST ILM is also used to force the expander to evaluate expressions protected by unary + as written without reordering.

Names Conflicts¶

In certain situations, the names entry created by normal processing may not be sufficient for the detection of memory reference conflicts. For example, consider the following program segment:

/\* (1) \*/   int a[2], k;
/\* (2) \*/   (double \*)&a[0] = 0.0;
/\* (3) \*/   k = a[1];

The names entry created for a[0] indicates that it is an array reference with a constant offset of 0. Because of the double context at statement (2), a[1] is also modified. At statement (3), the names entry for a[1] is an array reference with a constant offset of 4. This entry does not conflict with the names entry for a[0]. For the reference at (2), the expander recognizes that a double reference occurs on an entity which is not type double. For this situation, the expander changes the names reference for a[0] to one which denotes an array reference with variable subscripts. This names entry will conflict with the one at (3).

This processing occurs whenever:

the load or store operation is not double and the item involved is type double, or the load or store operation is double and the item involved is not type double, and
the names entry denotes an array with constant subscripts or an indirection with constant subscripts.

Common ILM Expressions¶

A common ILM expression occurs when an ILM has multiple references. Common situations are prefix expressions and using the results of assignments and postfix expressions. For common ILMs, the expander must ensure that the “value” stored is the one that is re-used.

When the store or pseudo store ILM is processed, the index locating the terminal ILI generated for the ILM is saved away as the “result” of the ILM. Also, the block id, a BIH index, of the ILI block containing the ILI is saved. When the expander finds an ILM which has been evaluated (in eval_ilm while recursively searching a terminal ILM’s links), routine check_ilm is called to examine the “result” of the ILM. If the block of the result is the same as the current block being created, then all that has to be done is to create a cse (common subexpression) ILI of the value being stored (this is always the first operand of the terminal ILI). This (cse) ILI replaces the result of the ILM which is being referenced and is therefore the ILI used by the referencing ILM (note that subsequent evaluations of this ILM will use the cse ILI). The expander must guarantee that the scheduler will see the cse’d ILI before it sees the cse ILI. For example,

i = j = k;

results in the following ILM block:

BOS            3    17
BASE          43            ;i
BASE          44            ;j
BASE          45            ;k
ILD           7^
IST           5^    9^
IST           3^   11^

The ILM at (11) generates a store ILI which stores the value of k (a load ILI of k) in j. For ILM (14), the value stored (the second operand) is the value of ILM (11). Since this ILM has already been evaluated, the new “result” of (11) is a cse ILI of the value being stored (the load ILI of k). A cse ILI of the load ILI of k is the ILI which is accessed by the store ILI for ILM (14). Note that the scheduler will see the store of j before the store of i. Therefore, it will see the load of k before it sees its corresponding cse.

If the ILI occurs in a block which is not the current block, then the expander must add to the block containing the ILI a temporary store of a cse of the stored value. The result of the ILM is replaced by a load of the temporary. For example,

\*p++ = flag ? 1 : 0;

results in the following ILM block (created ILI basic block boundaries are denoted by ---:

BOS            6    55
BASE          45            ;p
PLD           3^
PSEUDOST       0    5^
ICON          35
PIADD         5^   10^     1
PST           3^   12^
BASE          44            ;flag
ILD          19^
BRF          21^    46
_____________________________________\_

BASE          47            ;.I0000
ICON          35
IST          26^   28^
BR            48
_____________________________________\_

LABEL         46
ICON          32
BASE          47            ;.I0000
ICON          32
IST          39^   41^
_____________________________________\_

LABEL         48
BASE          47            ;.I0000
ILD          48^
IST           7^   50^

In this case, the ILM at (52) references ILM (7) whose ILI is in a different ILI block. Therefore, the expander will add to the block containing the ILI for ILM (7) a store into a temporary. The value stored is just a cse of the ILI which does a load of p. ILM (52) will use a load of the temporary.

Functions¶

A function ILM exists for each scalar type and void type. The ILMs are:

VFUNC	void
IFUNC	int
UIFUNC	unsigned int
RFUNC	float
DFUNC	double
PFUNC	pointer

A function ILM has the form:

<function ILM>  n  lnk1  lnk\*

where,

n =: number of actual arguments
lnk1 =: address expression which computes the address of the function being called
lnk\* =: zero or more links locate the arguments that are passed to the function. These arguments are the actual values passed to the function.

The VFUNC ILM is also used whenever a non-void function is called and its value is discarded. The remaining ILMs are used in contexts which access their values.

Processing a function ILM involves:

possibly creating a dummy argument to keep the stack double word aligned.
looping through the argument links to generate ILI to push their values on the stack. The ILI generated are in the set IL_ARGIR (data register), IL_ARGAR (address register), IL_ARGSP (single precision floating register), IL_ARGDP (double precision floating register).
generating the ILI to push the argument count on the stack.
generating the “jsr” ILI which links to the function address and argument list address. This can be one of two ILI:
- JSR sym lnk — sym is the ST entry for the function (if lnk1 locates an ACON ILI)
- JSRA lnk lnk — the first lnk locates the function address which is computed, i.e., (\*p)()
1. If the function ILM is not void, the “define result” ILI is generated which will link to the “jsr”. This is one of:
  - DFRAR lnk 0 — pointer result; 0 indicates AR(0).
  - DFRIR lnk 0 — integer register result; 0 indicates IR(0).
  - DFRSP lnk 0 — single precision result; 0 indicates SP(0)
  - DFRDP lnk 0 — double precision result; 0 indicates DP(0).

If the function is a VFUNC ILM, an ILT is created. If the function is a PFUNC ILM, a names entry of type NT_UNK (unknown) is created for the names result of the ILM.

ESTMT Processing¶

The ESTMT ILM is used for an expression whose result is not used (its value is discarded). This is particularly true for all but the rightmost expression in a comma expression. The ILI expression tree located by the ESTMT’s link is searched for the functions. The result of this search is that ILTs are created which reference just the function ILIs. For example,

a = ( f() + g(), b )

----  ILM  ----          ----  ILI ----

ESTMT   -----+          (1) JSR "f"
             |          (2) DFRIR (1) 0
             |          (3) JSR "g"
             |          (4) DFRIR (3) 0
             +----->    (5) IADD (4) (2)

Two ILT nodes are created for this ILM: one locates the ILI at (1) and the second locates the ILI at (3).

Comparison and Relational Processing¶

Comparison ILMs serve only as placeholders for the relational ILMs. The appropriate ILM is generated by the semantic analyzer which reflects the scalar data type of its operands. The expander passes up the opcode of the equivalent ILI to the relational ILM accessing the compare by saving away the opcode. When the relational ILM is processed, the opcode and the compare’s operands are extracted, and the value denoting the relation is computed. The “compare for relation” ILI is then generated. Note that the value indicating the relation is an immediate value to the ILI. This value is computed by relying on the following consecutive ordering of the relational ILMs: EQ, NE, LT, GE, LE, and GT. The respective values are 1, 2, 3, 4, 5, and 6.

Branch Processing¶

Most branch ILMs are expanded using exp_mac. Certain ILMs require special handling by the expander. For now, there is just one ILM special cased — the SWITCH ILM.

The SWITCH ILM consists of the switch expression and the switch list (a list of the switch labels including the default; refer to Section 12 for a description of the switch list). Simple heuristics are used to generate the ILIs for the SWITCH. There are three cases:

The number of cases in the switch is less than or equal to four. A sequence of conditional if’s is used to represent the switch: For example,
```
switch (i) {
case 1: s1;
case 2: s2;
}
s3;
```
The ILIs generated are for a sequence of conditional if’s:
```
    if (i==1) goto l1;
    if (i==2) goto l2;
    goto l3:
l1: s1;
l2: s2;
l3: s3;
```
The number of cases in the switch is greater than four and less than or equal to 16, or the case values consist of a set of dense values (many values — 80 percent — which exist between the minimum and maximum values).
For example,
switch (i) { case 1: s1; case 2: s2; case 3: s3; case 5: s5; case 6: s6; } s7;
yields ILIs which select an entry from an address table. The address table is a data initialized, compiler created array, with a name of the form .Jxxxx where xxxx is a decimal number. The address table consists of a series of addresses where the first entry is the address of the default statement (c s7 in the above example), the second entry is the address of the statement corresponding to the smallest case value (c s1 in the example), the third entry is the address of the statement corresponding to the next (increase of 1) case value (c s2 in the example), and so forth. The index to the jump table is determined by adding to the switch expression (in the above example, i) a value which normalizes the switch value to 1. This calulation results in the minimum case value corresponding to the second entry (the first case value) in the jump table. In the example, the value added is one. If this value falls outside of the range of 1 to n (n is the number of entries in the table including the default entry), the default statement is branched to. For the above example, the following ILIs are generated:
(1) IADD i '1' '1' is a constant ST for the value 1 (2) JMPM (1) '7' tab The table has 7 entries. ... tab: l7 default l1 case 1 l2 case 2 l3 case 3 l7 case 4 is default l5 case 5 l6 case 6
An ILT is created for the JMPM ILI.

The number of cases in the switch is greater than 16 and the case values are sparse. In this case, ILIs are generated which will call the C support routine, c$i_switch, to perform the switch. Passed to the routine are the switch expression and the label list, which must be created by the expander module. The label list is a compiler created symbol (an auto integer array) whose name is .Jxxxx where xxxx is a decimal number. The label list has the form:

_

n

number of case value-label pairs

_

default label

label of default statment

_

case value\*<1\*>

value-label pair

_

^

case label\*<1\*>

for first entry

_

&…

_

case value\*<N\*>

value-label pair

_

^

case label\*<N\*>

for Nth entry

_

Note that the case values are in sorted (ascending) order. An ILT node is created which locates the ILI representing the call to the switch routine.

Entry Processing¶

When an ENTRY ILM is processed, the following actions are performed:

A basic block is created. This will be the first block of the function.
The ENTRY ILI is generated. This ILI has two operands: pro, and func, respectively. pro is a symbol table item of type ST_FUNC which represents the C prologue routine ( c$i_entry). func is the symbol table item of type ST_FUNC which represents the entry. Note that the first ILT in this block locates this ILI.
If exceptions are to be disabled and/or enabled, two constants are created from the values of the global variables flg.xon and flg.xoff. The first represents the mask value used to enable exceptions (by OR’ing). The second represents the mask value used to disable exceptions (by AND’ing). The method by which these exceptions are enabled and disabled is machine dependent and is specified in the MACHAR utility.
If the debug option was selected, an ILT is created to locate the ILI which calls the debugger routine dbg$i_entry <this may change>.

Return Processing¶

When the RET or RETV ILM is processed, a jump ILI is created which references the label (a compiler created symbol table item) of the exit block. This label’s name is .Rxxxx where xxxx is a decimal number. Its symbol table index is stored in exp.retlbl. Only one return label is needed per function. For the RETV, the appropriate move register ILI is generated to move the function’s return value into a register prior to the jump.

End Processing¶

When the END ILM is processed, the following actions are performed:

If a return ILM was processed, a label would have been created which is accessed by a JMP ILI. That is, a return is turned into a jump to the block defined by the return label. Note that the same rules for the label specified in a LABEL ILM apply to the return label (optimizing out, etc.).
If exceptions were modified, machine dependent exception cleanup ILI are generated and linked to by an ILT node.
If the debug option was selected, an ILT is created which locates the ILI which calls the debugger routine dbg$i_exit <this may change>.
The EXIT ILI is generated. This ILI has one operand, a ST_FUNC symbol table item representing the C epilogue routine c$i_exit). An ILT node locates this ILI.

Miscellaneous¶

The following ILMs are the remaining “address” producing ILMs which require that each produces a names entry result in addition to an ILI result:

ACON — A names entry of type NT_VAR is created. The symbol field is set to the address constant.
IPTR — This ILM converts an integer value to a pointer value. The names entry created is type NT_UNK (unknown).
LOC — This ILM “passes” up the ILI and names entry located by its link.
PIADD/PISUB — These ILMs call the addnme routine with the template
```
<NT_ADD, ptr, bnme, cnst> .
```
NT_ADD indicates that addnme is to add bnme (the name entry of the address ILI located by the first ILM link) to the “value” denoted by ptr and cnst. ptr is zero if a constant is being added (c cnst is the constant value in the PIADD or the negative of the constant value in the PISUB), and (mi1 if a non-constant is being added.

Program Units¶

The expander module is composed of four C files: expdf.c, expand.c, exp_clang.c, and exputil.c. The file expdf.c contains the definitions and static initializations of the data structures required by the expander.

The file expand.c contains the following routines:

void exp_init()

Initialize the expander module: allocates space for the ILM, ILI, ILT, BIH, and NME areas. Clears the zeroth entry for the ILT and BIH areas (refer to section 13). The “noblock” flag in the expander local data area is set on (no current block exists). The ILM file is rewound.

void expand()

Main expander routine called by the program controller. This routine reads in a block of ILMs and scans the block for terminal ILMs. When one is found, it calls eval_ilm to evaluate the terminal ILM which in turn evaluates all of its operands.

void eval_ilm(ilmx)
int ilmx;

This routine controls evaluates the ILM indexed by ilmx and all of its operands. When the operands have been evaluated, eval_ilm sets up the following static variables for use by the various subordinate expand routines: ilmp pointer to the current ILM opc opcode of the current ILM curilm index of the current ILM eval_ilm selects the appropriate action depending on the ILM attributes.

void
exp_estmt(ilmx)
int ilmx;

Expands the ESTMT ILM.

void
exp_label(lbl)
int lbl;

Expands the LABEL ilm.

void
exp_load(opc, ilmp, curilm)
int opc;
ILM \*ilmp;
int curilm;

Expands the load ILMs.

void
exp_store(opc, ilmp, curilm)
int opc;
ILM \*ilmp;
int curilm;

Expands the store ILMs.

void
exp_mac(opc, ilmp, curilm)
int opc;
ILM \*ilmp;
int curilm;

Expands the non-special case ILMs using the templates defined using the ILITP utility.

void
exp_ref(opc, ilmp, curilm)
int opc;
ILM \*ilmp;
int curilm;

Expands the reference ILMs (except for ELEMENT) and creates names entries.

The C module file, exp_clang.c, contains:

void
exp_ac(opc, ilmp, curilm)
int opc;
ILM \*ilmp;
int curilm;

Expands the arithmetic and constant ILMs.

void
exp_array(opc, ilmp, curilm)
int opc;
ILM \*ilmp;
int curilm;

Expands the ELEMENT ILM and creates names entries.

void
exp_bran(opc, ilmp, curilm)
int opc;
ILM \*ilmp;
int curilm;

Expands the branch ILMs, particulary the switch.

void
exp_call(opc, ilmp, curilm)
int opc;
ILM \*ilmp;
int curilm;

Expands the call ilms.

void
exp_misc(opc, ilmp, curilm)
int opc;
ILM \*ilmp;
int curilm;

Expands the miscellanous ILMs.

The C module file, exputil.c, contains:

int mkfunc(name)
char \*name;

Creates a symbol table entry of type function given the name and returns its index.

cr_block()

Creates a BIH. Sets exp.curbih to its index and defines its line number.

wr_block()

Terminates the block defined by exp.curbih. Sets the first and last fields of the BIH. Sets the “noblock”flag in exp to 1 (no block currently exists).

void
flsh_block()

void
chk_block(ilix)
int ilix;

Checks to see if the ILI (located by ilix) will terminate the current block. If it will terminate the block, the block is terminated and the “noblock” flag in exp is set to 1. Otherwise, an ILT is created for the ILI and added to the current block.

int
check_ilm(ilmx)
int ilmx;

Checks the ILM (located by ilmx) which has already been evaluated. Actions are performed to ensure that the ILI originally generated for the ILM is treated as a common subexpression or is used if across block boundaries. Special care is take not to call this routine for store ILMs covered by the NCSEST ILM.

int mk_swlist(n, swhdr)
INT n;
SWEL \*swhdr

Makes the address/value table for the switch statement.

int mk_swtab(n, swhdr)
INT n;
SWEL \*swhdr

Makes the address table for the switch statement.

_
n	number of case value-label pairs
_
default label	label of default statment
_
case value\<1\>	value-label pair
_	^
case label\<1\>	for first entry
_
&…
_
case value\<N\>	value-label pair
_	^
case label\<N\>	for Nth entry
_