Princeton University
COS 217:  Introduction to Programming System

Precept 21:  Assembler Assignment Pass 2 - Expression Evaluation and Beyond

Purpose

Describe more of pass 2 of the assembler

In particular, describe expression evaluation, generation of relocation structures, and error handling (extra credit)

Reading

(None)

Stage 4:  Expressions with Operators

See the Assembler Assignment Development Stages summary sheet

To evaluate an expression, use this recursive process (in pseudocode):

int evalExp(struct expression *psExp)
{
   switch (type of expression)
   {
      case value:  
         Return the expression's "val" field;
      case symbol:  
         For now, return the symbol's offset (derived from symbol table)
      case operation:
         Recursively evaluate the (left and) right subexpressions.
         Return the result of applying the operator to the subexpression(s)
   }
}

Example:  add %r1, 5, %r3

Expression is a value

Example:  call label

Expression is a symbol

Example:  add %r1, (5+3) * -2, %r3

Expression is an operation

The %hi operator is no different from any other

Definition:  evaluates to the high-order 22 bits of its operand

Implementation:  right-shift by 10

Example:  sethi %hi(4101), %l1

Unusual (operand of %hi operator is usually a label), but OK

Evaluates to 8

4101 (decimal)
00002005 (hex)
0000 0000 0000 0000 0010 0000 0000 0101 (binary)
0000 0000 0000 0000 0000 0000 0000 1000 (right shift by 10)
00000008 (hex)
8 (decimal)

The %lo operator is no different from any other

Definition:  evaluates to the low-order 10 bits of its operand

Implementation:  "bitwise and" with 0x3ff (using C's "&" operator)

Example:  or %l1, %lo(4101), %l1

Unusual (operand of %lo operator is usually a label), but OK

Evaluates to 5

4101 (decimal)
00002005 (hex)
0000 0000 0000 0000 0010 0000 0000 0101 (binary)
0000 0000 0000 0000 0000 0011 1111 1111 (0x3ff in binary)
0000 0000 0000 0000 0000 0000 0000 0101 ("bitwise and" the two)
5 (decimal)

Example:  08expression.s

Looks ominous, but (through recursion) is very simple

Implementation suggestion:

Define expression handling code in files expression.h and expression.c -- shared by pass1.c and pass2.c

Note distinction between assembly time evaluation and runtime evaluation of expressions

add %r1, 4 + 8, %r3

Assembler performs addition

ld [%l0 + 8], %l1

Assembler cannot perform addition

Assembler produces format 3b instruction that gives 8 as the immediate operand

CPU performs addition at runtime

Stage 5:  Expressions with Labels

See the Assembler Assignment Development Stages summary sheet

Recall:  In the assignment, labels can occur within expressions in only 4 contexts:

call label
bx label
%hi(label)
%lo(label)

In the context of this assignment, these expressions are disallowed:

call label+4
%hi(label+12)
.word label
...

What should the evalExp function do in each of those 4 cases?

call label

if label is defined (as a local label) in the text section in this file
   Return the 30-bit displacement between the call instruction and label
else
   Generate a R_SPARC_WDISP30 relocation structure
   Return 0

bx label

if label is defined (as a local label) in the text section in this file
   Return the 22-bit displacement between the bx instruction and label
else
   Generate a R_SPARC_WDISP22 relocation structure
   Return 0 

%hi(label)

Generate a R_SPARC_HI22 relocation structure
Return 0

%lo(label)

Generate a R_SPARC_LO10 relocation structure
Return 0

Implementation:

Somewhat difficult

Expression evaluation code must know the context in which the expression resides

call mnemonic, branch mnemonic, %hi operator, or %lo operator

psInstr variable must be global

To test

Examine relocation structures using elfdump

Standard UNIX tool (not specific to this assignment)

Displays ELF file meta information, i.e. information about the contents of an ELF file

Example:  hellorel.s

Describe Assembler Output for hellorel.s

Trace pass 1

Trace pass 2

Note generation of relocation entries

Note that labels (printf) may be added to symbol table during pass 2

Examine elfdump hellorel.s

Example:  09relocation.s

Describe  Assembler Output for 09relocation.s

Trace pass 1

Trace pass 2

Examine elfdump 09relocation.o

Example:  10symbol+.s

Another example of generating relocation structures

Also illustrates the fact that pass 2 may need to add entries to the symbol table

Entry for label4 is added during pass 2

Briefly describe Assembler Output for 10symbol+.s

Briefly examine elfdump 10symbol+.o

More realistic:  call printf (as in many of the programs that we've seen)

Stage 5b:  Synthetic Instructions

(Could have been a separate stage listed on the Assembler Assignment Development Stages summary sheet)

For each synthetic instruction, must determine the corresponding "real" instruction

Example:  

cmp %r1, %r2 corresponds to subcc %r1, %r2, %g0

Example:  11synthetic.s

Bulky, but straightforward

Stage 6:  Complete Executable Programs

See the Assembler Assignment Development Stages summary sheet

Assembler should not resolve references to global symbols, even if it has enough information to do so

Example:  app_01fibonacci.s

Example:  app_02bubblesort.s

To test:

Use print_passes to examine symbol table

Use objcmp and objcmp_detail to examine data and text sections

Use elfdump to examine relocation structures

Use gcc to link, and then run!!!!!

Stage 7:  Error Handling (for extra credit)

See the Assembler Assignment Development Stages summary sheet

Worth ~15% extra credit

Max grade will be ~115%

Pattern your error messages after those generated by "as"

Except:  Report instruction numbers instead of line numbers

Detect error in pass 1 => exit at end of pass 1 (before executing pass 2)

Detect error in pass 2 => exit at end of pass 2 (before generating .o file)

See the Assembler Error Handling summary sheet

Example:  err_01boundary.s

Approach:

In pass1, check location counter when processing each mnemonic, .half directive, and .word directive

Example:  err_02symbol.s

Approach:

In pass 1, check symbol table for existing label with a defined section before putting new label

Example:  err_03directive.s

Approach:

Handle in pass 1

Example:  err_04immvalue.s

Approach:

Handle at various levels of pass 2

Most mnemonic errors can be handled at lowest level (process3bMnm)

ta and sll must be handled at higher logical levels

.byte and .half errors are handled separately

Example:  err_05relocation.s

Approach:

Enhance expression evaluation code

Make sure labels are used in an appropriate context

Copyright 2002 by Robert M. Dondero, Jr.