A Short Course in Compilers -- Emitter

Expand Semantic Action Sequence into CPU Sequence

Emitter Constructor

The emitter activity is mostly confined to the local constructs in the compiled X file. The emitter needs information about other files to call subprograms; The constructor is passed external information for this purpose.

Semantic Actions

The emitter object implements a collection of methods translating semantic actions into hardware actions. The semantic actions of X are:

name	summary	actions
prolog	X program entry	set hardware frame, callee save, point at X frame
epilog	X program exit	callee restore, cleanup frame, return to xcom
arithAbort(rule,tok)	X program run error	in case of divide by 0
stmt	statement processing	no action needed
call(outputs,name,inputs)	call X subprogram	find called subprogram check inputs&outputs for type prepare input&output transfer vector call linker, cleanup after return
opd=var(tok)	LHS var	symbol lookup, set tag S
opd=expr0(rule,tok)	0-ary expression processing literals, RHS var, rand	literal: capture text: set tag L var: symbol lookup: set tag S rand: call rand: set tag X
opd=expr1(rule,opd)	1-ary expression processing	~ i2b -(integer): set tag R i2r r2i -(real): set tag X
opd=expr2(rule,left,right)	2-ary expression processing	\| &: set tag R integer < <= = ~= >= >: set tag F integer + - * / //; set tag R real < <= >= >: set tag D real + - * /: set tag X
store(lefts,rights)	store to frame	:= set tags A
iffiEnd(list)	finish up if-fi	fixup alt ends to beyond fi
iffiAbort(tok)	failed all guards	abort X progran
loc=doodBegin	start do-od	save loop start
doodEnd(list,loc)	finish up do-od	fixup alt ends back to loop head
loc=guardEnd(opd,tok)	finish up guard	emit conditional branch after guard set tag A
loc=altEnd(loc)	finish up alt	emit branch to next alt fixup previous alt branch

Tracking Operands

X expressions combine variables and literal constants to compute values. The names and constants are transformed by stages between forms acceptable for the target hardware (in this case Intel 32-bit x86).

An array of operands is maintained. The array contains structs for active operands as well as a pool of available structs for new operands. The status of a particular operand is determined by its status tag. Once assigned, an operand is modified in-place via its index and its tag updated accordingly. When the operand is no longer needed, the operand is tagged as available and returned to the pool for later use (tag A).

                OPERAND TAGS AND TRANSITIONS:
                
                              F            A -- available
   A --- L --------.         / \           L -- literal constant
                    \        \ /   /\      S -- symbol table index
                     >------- R --<  X     M -- in memory frame
                    /        / \   \/      X -- in temporary memory
   A --- S --- M --'        D   F          R -- in a register
                             \ /           F -- in general flags
                              R            D -- in floating flags

                OPERAND CONTENTS:
  tag    A    L      S      M      X      R     R     D     F 
  ty     ?    b|i|r  b|i|r  b|i|r  b|i|r  b|i   r     b     b 
  val    ?    token  idx    idx    idx    reg   ?     test  test

                OPERAND TRANSFORMERS:
                
  toA  toR  toX  toF  L2R  R2X  X2R  S2M  M2R  F2R  D2R

A literal constant (e.g. true, 13, 1.01) is tagged L, the type is set and the text form of the constant, still in the source text, is converted to machine form and recorded as the val field. Real values are punned to MATLAB int32, and need to be punned back to MATLAB single when they are used. When the value is needed, an operand transform L2R is provided.

Each variable is already in the symbol table (an earlier phase). When the name is encountered in the tree walk, the type is looked up and copied, the operand is tagged S, and the operand value is set to the symbol table index. When the variable is needed, a transform S2M is provided. The type and val fields remains unchanged, the tag becomes M (the memory offset in the frame is the same as the symbol table index).

If the value is needed from memory, a transform M2R is provided. Code is generated to get the value from the frame into a register. The tag becomes R, the type is unchanged. If the type is integer or logical, an Intel general register is used and the operand value field is set to the register number; if the type is real, the Intel FPS is used and the value field is ignored.

The result of a comparison is either in the integer flags (tag F) or the FPS flags (tag D). The test needed is the value. The Intel branching logic requires that the information gets to tag F before it can be used. The transform toF insures that a type logical operand is in the flags.

Computer hardware resets the flags after most operations. The motto is "flag: use it or lose it". There is a provision that insures that a D or F flag is never left hanging around (and thereby getting clobbered). Unless the logical value is assigned, the tag F operand immediately becomes available (tag A) after use.

When a general register is needed and not available, function R2X dumps a busy register into a temporary location in the frame (tag X), the type is unchanged, the value is the temp index. The pending request for a register can then be satisfied. Later, transform X2R recovers the temporarily saved value and frees the temporary location in the frame for later use.

To avoid thrashing temporary stores, the lookup for getting a register can protect one register (presumably another register it is immediately going to need).

In an error situation where the failure report must be delayed, the operand is tagged as an error (tag E) and the value is the error message. There are no examples in xcom.

Emitting Expression Code

The emitter object exists to emit machine code. Each time an operand transitions, corresponding code is sent on to the assembler as a side-effect. The details of the emitters are most easily understood by examining the emitter code. Such understanding requires some understanding of the underlying hardware.

Control Logic

Intel x86 control is provided by branching instructions. Branches are used for conditional execution and also subprogram calls.

The X 'if-fi' requires a set of forward branches. After each failed guard the next guard must be tried. After each successful case, the statement following the 'if-fi' must be reached. If all guards fail, the X program must abort. The branches following the guards are conditional; the branches following the statements are unconditional.

   --> if     guard +--> stmts -.
          ,------<--'           |
       :: `-> guard +--> stmts -.
          ,------<--'           |
       :: `-> guard +--> stmts -.
          ,------<--'           |
       :: `-> guard +--> stmts -.
          ,------<--'           |
          `-> abort             |
       fi                       |
      ,----------<--------------'
      ` next stmt

The X 'do-od' requires some of the same forward branches plus a set of backward branches. After each failed guard the next guard must be tried. After a successful case, the loop must be repeated. If all cases fail, the statement after the do-od must be reached.

      ,----------<--------------.
      |                         |
  --> `do     guard +--> stmts -'
          ,------<--'           |
       :: `-> guard +--> stmts -'
          ,------<--'           |
       :: `-> guard +--> stmts -'
          ,------<--'           |
       :: `-> guard +--> stmts -'
       od           |
      ,----------<--'
      `-> next stmt

Forward branches must be placed in the code stream before the relative offset to the destination is known. This is accomplished by leaving a "hole" for the offset field and then "fixing it up" later. Backward branches can be filled in immediately or can use the "fixup" mechanism.

Fixups

Two integers suffice to determine a fixup action: the index of the "hole" and the index of the branch destination. The program counter is always left pointing at the next unused byte. A relative branch therefore is relative to the start of the next instruction. For a forward branch, which is recorded as soon as the destination is known, the implicit destination is the program counter (which points at the next code, whatever it is going to be). The value of the program counter at any time is supplied by assembler method getPc. The value of EIP, the hardware program counter might be anything, but since everything is self-relative, it does not matter.

Code Selection

Code selection is the process of choosing a sequence of machine instructions to implement the semantic actions. The choices are usually straightforward; they can be seen in EmitX86.m. One choice that may seem strange is forcing real values back into memory after each operation. One consequence is that at most two of the eight FPS registers are used. One advantage is that xcom can never cause FPS stack overflow. A better reason is to keep the arithmetic consistent. The FPS carries 80 bits; xcom variables are 32 bits. The results in xcom do not, therefore, depend on the details of the FPS management. The real reason is that it makes the emitter code easier to understand.

The assembler contains logic to error on FPS overflow, but it never happens.

Targetting Other Hardware

The xcom compiler, in one form or another, has been implemented for a dozen different CPUs. Soon enough, another important "box" will come along, and the emitter will have to be retargetted once again. Industrial strength compilers typically impose another layer of abstraction between the emitter and assembler (a so-called UNCOL) so that the inevitable retargeting is less painful.

Runtime Errors

When something bad happens in the runtime, the compiler is obligated to give the X user enough information to fix the problem. Divide by zero is a common case.

What the user needs is a message about what happened and the location (say file, line and column) of the trouble in the X program. There are usually not very many such trouble spots; they can be numbered from 1 to N. In xcom, the location and message are precomputed "just in case", and the messages are tabulated, 1 to N in an xcom table. The runtime merely needs to report the table index back to xcom to enable xcom to make a reasonable report. There is a special early exit called bailout in the assembler for this purpose.

The alternative is to report errors directly from the emitted code. This is far too messy a process to inflict on students. MATLAB already knows how to do it, so let it.