10. Separate Assembly and Objects

Part of 22C:60, Computer Organization Notes
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Classes and Objects

In the previous chapter, we discussed many classes of number representations, along with the implementation of operations ranging from addition and subtraction, on the one hand, to multiplication and division. In an object-oriented programming language such as C++ or Java, we can identify each of these classes or data types with a specific linguistic construct, the class definition. Each class definition completely encapsulates all of the details of the representation of all objects of that class, so that outside that class definition, operations on objects of that class are carried out only by the methods defined as part of the class definition.

Assembly and machine language programmers cannot completely hide the details of the data types with which they work. Any time an object is loaded into registers, its size is exposed, and any time specific machine instructions are used to manipulate an object, these instructions must be used with full knowledge of their effect on the representation of the object as well as on the abstract value connected to that representation.

Nonetheless, an assembly language programmer on a machine such as the Hawk can go a considerable distance toward isolating the users of objects from the details of their representations! We can do this in several steps, first isolating the code used to implement operations from the code that uses those operations, second, providing clean interface specifications for the objects, and finally allowing for polymorphic classes, that is, mixtures of different but compatable representations.

Separate Assembly

Suppose you have a set of subroutines, for example, multiply and divide, that you want to break off from a large program. Since the mid 1950's, there have been assembly languages that allowed such routines to be separately assembled before use in other programs. We have already been using such tools here, specifically, in the form of the Hawk Monitor, a separately assembled block of code that includes input, output, limited arithmetic support, and handlers for traps.

There are at two good reasons to separate any program into multiple source files, no matter what programming language is being used. First, smaller source files are frequently easier to edit. Real-world application programs are frequently huge, with total sizes measured in thousands or even millions of lines of code. Second, by separating an application into multiple separate pieces, we can isolate program components that have already been tested from those currently undergoing development. Some files may contain standard components that are used in many applications, while other files are unique to one application.

In assembly language programs, and to some extent, in C and C++ programs, there is another reason to separate programs into multiple source files. In these languages, some identifiers are defined locally within one source file, while other identifiers are global to all source files. In C and C++, for example, static functions and static global variables are local to the source file in which they are defined, while other functions and globals are global across all source files that make up an appliction. The use of the type qualifier static in these languages is eccentric, in that the word does not say what it means, but the idea is quite useful.

In the SMAL assembly language, all identifiers are, by default, purely local to the source file in which they are declared, but they may be made global using explicit INT and EXT declarations. The declaration INT X says that the symbol X that is defined internally in this source file is visible globally. If X is not given a value in this file, it is an error.

The declaration EXT X says that the definition of the symbol X is external to this source file. This sorce file must not give X a value. Some other source file must contain the declaration INT X and that source file must give a value to X.

If we wanted to put our own integer multiply and divide routines in a separate source file from the program or programs that used them, we might structure the file like this:

Outline of a separately assembled source file for the Hawk
        TITLE   "intmuldiv.a, integer multiply and divide"
        INT     INTMUL
        INT     INTDIV

        SUBTITLE "multiply"

INTMUL:         ; link through R1
                ; on entry, R3 = multiplier
                ;           R4 = multiplicand
                ; ... other interface specifications

        ... Code for multiply

        SUBTITLE "divide"

INTDIV:         ; link through R1
                ; on entry, R3 = low 32 bits of dividend
                ;           R4 = high 32 bits of dividend
                ; ... other interface specifications

        ...  Code for divide

        END

 

This source file, named intmuldiv.a, contains no main program and has no starting address. Some aspects of the file are merely examples of good programming practice. For example, the title of the file begins with the file name, so that assembly listings are always self-descriptive, and the remainder of the title briefly describes the contents. The subtitle given before each routine adds additional documentation. Most decent assemblers provide similar documentation support, and where they do not, careful use of comments can achieve the same effect. Listings created by the SMAL assembler will always contain a table of contents constructed from the subtitles in the source file.

We have adopted a naming convention here that is worth noting. Instead of calling our multiplication and division routines MULTIPLY and DIVIDE, we have named them INTMUL and INTDIV. There could be many different multiply and divide routines in a large program, some for integers, some for long integers, some for floating point and perhaps some for complex numbers. In a language like C++ or Java, we would distinguish between these using overloading rules or using object prefixes such as a.multiply(), meaning "the multiply routine from the class of the variable a." In assembly language, we can't easily do either of these, but we can prefix the name of the subroutine with the name (or an abbreviated name) of the class to which it belongs.

Object oriented versus conventional calls
Object oriented
    x = a.multiply( b )
    y = c.multiply( d )
Conventional
    x = integer_multiply( a, b )
    y = floating_multiply( c, d )

The one feature of the SMAL file given above that is specific to separate assembly is the use of INT directives to declare the identifiers INTMUL and INTDIV. These declare to the assembler that these internally defined identifiers are to be exported for use in other assembly source files. Up to this point, the scope rules of SMAL have appeared to be trivial: All identifiers declared by labels or definitions anywhere in a source file may be used anywhere in that file. Now, we add to this the rule that identifiers declared with the INT directive may be available elsewhere.

The user of separately compiled or assembled routines typically needs to write a short list of declarations in order to access each of those routines. While there is nothing in SMAL, or for that matter, C and C++ requiring that these declarations be gathered together, we will do so. Specifically, we will gather all declarations needed to use the contents of intmuldiv.a into a file called intmuldiv.h, and we will ask users to put USE intmuldiv.h into their source files instead of writing the declarations themselves. Files with the suffix .h are called header files or interface specification files. This convention comes from the world of C and C++.

The header file for users of a separately assembled source file
        ; intmuldiv.h -- interface specification for intmuldiv.a

        ALIGN   4
        EXT     INTMUL  ; integer multiply
PINTMUL:W       INTMUL  ; link through R1
                        ; on entry, R3 = multiplier
                        ;           R4 = multiplicand
                        ; ... other interface specifications

        EXT     INTDIV  ; integer divide
PINTDIV:W       INTDIV  ; link through R1
                        ; on entry, R3 = low 32 bits of dividend
                        ;           R4 = high 32 bits of dividend
                        ; ... other interface specifications

Here, again, we have decorated our source file with comments that are not, strictly speaking, necessary. We have given our file a title, but we have not used the TITLE directive because we don't usually want the header file to be listed in an assembly listing, and we have also included comments giving the complete interface definition for each routine listed in our header file.

The key elements of our header file are the EXT declarations for INTMUL and INTDIV to tell the assembler that these symbols are defined externally, that is, in a different file. There must be no local definitions of these symbols. This tells the assembler to arrange things so that the linker can fill in the definition of these symbols with values exported from some other object file. If no file exports a definiton, the linker will report an error.

The declarations of PINTMUL and PINTDIV as labels on words containing the values of INTMUL and INTDIV makes up for a shortcoming of the Hawk linker. The Hawk linker can fill in the value of a word from an external symbol, but external symbols cannot be used for PC relative indexed addressing on the Hawk. So, we must call externally defined subroutines using these pointers. Here is an fragment of an assembly source file that calls these integer multiply and divide routnes:

Using separately assembled subroutines
        TITLE   "main.a"
; ... any necessary header comments

        USE     "monitor.h"
        USE     "intmuldiv.h"

        ... whatever code is needed

        LOAD    R1,PINTMUL
        JSRS    R1,R1           ; call intmul

        ... whatever code is needed

In general, the code for all methods associated with an abstract class go in the same source file. This file serves as a class implementation file, while the header file holds the interface definition.

Sometimes, a group of subroutines must share some variables. This is done using class variables in Java or static variables in C. The SMAL assembly language provides COMMON blocks to serve this purpose. Suppose, for example, we wanted to keep statistics on the number of times INTMUL and INTDIV were called in a program. We could do this as follows:

Use of a COMMON block for static variables
        TITLE   "intmuldiv.a, integer multiply and divide"
        INT     INTMUL
        INT     INTDIV

        COMMON  INTSTATS,STATSIZE
MULCNT  =       0       ; count of calls to INTMUL
DIVCNT  =       4       ; count of calls to INTDIV
STATSIZE=       8
PSTATS: W       INTSTATS

        SUBTITLE "multiply"
INTMUL:

        ... Code for multiply

        LOAD    R5,PSTATS       ; prepare to access intstats fields
        LOAD    R6,R5,MULCNT
        ADDSI   R6,1
        STORE   R6,R5,MULCNT    ; mulcnt = mulcnt+1

        ... More code for multiply

Common blocks in the SMAL assembly language have global names, so we called our block holding statistics INTSTATS, using the same prefix we used for the other internal definitions we are exporting to the larger world. The size and contents of this common block, however, are private to this source file, so we can omit the prefix and use purely local names.

The COMMON directive in SMAL requires the programmer to declare the size of the block of memory required. Here, we have used a pattern for the declaration of the size and structure of the common block that is very similar to the pattern we used for activation records, so we have given each field of the COMMON block a symbolic name, and we have also given the block size a name.

Later in the code, when it comes time to reference the common block, we have loaded a register with the address of the entire block and then referenced the fields of the common block in exactly the same way that we referenced the fields of the activation record of a subroutine. The only difference is that we have not used R2. Local variables go in the activation record, while static or class variables go in the common block!

Exercises

a) Rewrite the recursive FIBONACCI routine from Chapter 6 so that it counts the number of calls to FIBONACCI (recursive calls as well as calls from outside).

b) Write header files for the DSPNUM and FIBONACCI routines from Chapter 6, assuming that they were each assembled in from a separate source file.

c) What code must be added to DSPNUM and FIBONACCI from Chapter 6 in order to allow them to be assembled from separate source files.

d) Header files are not strictly needed. Rewrite the code above for a user of INTMUL and INTDIV so that it does not use intmuldiv.h but instead includes the bare minimum content from intmuldiv.h directly in the source file of the caller.

Linkage

Once we have created the source files for a program that includes multiple separately assembled components, we must assemble them into one executable program. This is the function of the linker. In the above section, we assumed that we had a main program, main.a that called subroutines in intmuldiv.a and in the Hawk monitor. Each time a programmer changes intmuldiv.a the programmer should re-assemble it to produce a new version of intmuldiv.o, and each time main.a is changed, it should be re-assembled to make a new version of main.o. To test the program, however, we need to combine these object files to make an executable file. We do this using the linker, which combines main.o with intmuldiv.o and produces link.o, the executable file.

The path from source code to executable object code
source code main.a intmuldiv.a
assembled by smal main.a smal intmuldiv.a
object code main.o monitor.o intmuldiv.o
linked by link main.o intmuldiv.o
executable code:link.o

The linker does a number of jobs. It combines the two object files main.o and muldiv.o, but it also adds in monitor.o automatically, so that the user program can call on monitor routines. In addition, it takes all of the common blocks mentioned in any of the separate object files and appends them end to end in main memory. In allocating space for all of the code files and common blocks, the linker takes care to make each file or block begin at a memory address that is divisible by 4, so that aligned data within the code file or common block will be physically aligned in memory.

Exercises

e) Assuming that dspnum.a and fibonacci.a are the source files for separately assembled versions of the subroutines given in chapter 6, and that you have a main program main.a, give the sequence of commands you would issue in order to assemble these pieces, link them, and make them ready to execute as a file called link.o.

 

An example, a stack

To illustrate these ideas, consider the problem of creating a package that defines a stack of words, with the operations push and pop. There must also be an operation to initialize the stack to empty. First, of course, we need to define the interface to this package:
 

Interface specification for a stack package
        TITLE "stack.h, interface specification for stack.a"

        ; for all routines:
                ;   R1 = return address
                ;   R2 = pointer to activation record
                ;   R3-7 = parameters and temporaries
                ;   R8-15 = guaranteed to saved and restored

        ALIGN   4
        EXT     STKINI  ; initialize stack
PSTKINI:W       STKINI

        EXT     PUSH    ; push operation
PPUSH:  W       PUSH    ; on entry, R3 = word to push

        EXT     POP     ; pop operation
PPOP:   W       POP     ; on exit, R3 = word popped

 
Before starting to implement this package, we must decide on a data representation for stacks. Should we use a linked list? An array with a stack pointer? Here, we opt for the latter, using a common block to hold the stack pointer and the array. In addition, we opt for the convention that, between calls to the stack routine, the stack pointer points to the top item on the stack.

Implementation for a stack package
        TITLE   "stack.a, implementation of a stack"
	USE     "hawk.macs"

STACKSIZE = #1000

	COMMON	STACK,STACKSIZE
PSTACK: W	STACK
;	first word of this common is the stack pointer
;	later words are the stack itself.
	; for calling conventions, see stack.h

	SUBTITLE "STKINI -- initialize stack"
	INT	STKINI
STKINI:                 ; link through R1
	LOAD	R3,PSTACK
	STORES	R3,R3		; initialize the stack pointer;
	JUMPS	R1		; return

	SUBTITLE "PUSH -- push one word on the stack"
        INT     PUSH
PUSH:                   ; link through R1, data in R3
        LOAD    R4,PSTACK
        LOADS   R5,R4           ; get the stack pointer
        ADDSI   R5,4
        STORES  R5,R4           ; update the stack pointer
	STORES	R3,R5		; push data on the stack
	JUMPS	R1		; return

	SUBTITLE "POP -- pop one word from the stack"
        INT     POP
POP:                    ; link through R1, returns R3
        LOAD    R4,PSTACK
        LOADS   R5,R4           ; get the stack pointer
	LOADS 	R3,R5		; pop data on the stack
        ADDSI   R5,4
        STORES  R5,R4           ; update the stack pointer
	JUMPS	R1		; return

 
This stack package implementation has a number of deficits. First, it contains no error checking, neither for stack overflow nor for underflow (popping from an empty stack). Both of these should probably raise exceptions. In fact, the interface is also defective. Many stack applications need to know whether the stack is empty, so we ought to privide a routine to call to test for an empty stack. Finally, we ought to allow the user to specify the stack size instead of having an arbitrary size of 100016.

Exercises

f) Write a main program that makes minimal use of the stack, just initializing it and then pushing and popping a value.

g) Modify the pop routine given here so that it refuses to pop from an empty stack.

Object Oriented Notations

At this point, it should appear that an object, say a stack, is represented by a fixed block of memory holding the variables that compose the representation of that object, and that the methods of a class are simply subroutines that are called to operate on that memory block. This simple view is an oversimplification. It only applies when there is just one instance of the class. This is very common! For example, few applications use multiple stacks, and many of the classes in java programs are "wrapper classes" with no data part at all. They serve merely to group related subroutines.

If we have multiple instances of a class, we must move beyond our simple model. Consider the problem of implementing vectors and vector addition. A vector in two dimensions is a coordinate pair (x,y). The sum of two vectors (x,y) and (x',y') is (x+x',y+y'). That is, the sum is a vector where each component is the sum of the corresponding components of the operands. In a language such as C++ or Java, if we needed vectors, we would define a vector class. To sum two vectors a and b, we might write a.sum(b). That is, we would pass b as a parameter to the sum method of object a.

This notation, a.sum(b), is only really needed if the class of a is polymorphic. If a is not polymorphic, we might just as well write vector:add(a,b) (the notation varies depending on on the language). This notation is not really object oriented, but rather, it simply views the class as a package to hold a number of related subroutines.

The point is, so long as polymorphism is not involved, the mechanisms we have already discussed in the context of the stack example is sufficient. Here is how we might define the vector class and the vector add operation. In practice, we will want more vector operations, for example, initialization and dot product, but those do not concern us here.

Interface Specification for a vector package
        TITLE "vector.h, interface specification for vector.a"

VECSIZE	=	8	; size of one vector in bytes

        ; for all routines:
                ;   R1 = return address
                ;   R2 = pointer to activation record
                ;   R3-7 = parameters and temporaries
                ;   R8-15 = guaranteed to saved and restored

        ALIGN   4
        EXT     VECADD  ; vector add
PVECADD:W       VECADD	; on entry
                      	;   R3 points to vector to add to
                      	;   R4 points to vector to add to it

Note that the interface specification exports the size of the vector, but nothing about its representation. A user of vectors could statically allocate vectors in common blocks or allocate them in activation records knowing this size, but there is no need to give users any information about the internal structure of a vector. That information is needed only inside the implementation.

In many object oriented languages, a pointer to an object is called an object handle. We pass pointers to the objects instead of the values of the objects because we do not want the caller worrying about the details of passing an object. Passing a pointer to an object is done identically whether that object is one byte or ten thousand words long.

Exercises

h) Write the implementation for vector add, assuming that vectors are ordered pairs of integers.

i) Write a main program that allocates two vectors, both global variables, and then demonstrates how to add them. Given that we have no mechanism for initializing vectors or using their value (aside from by addition), this program will be of no particular use.

Polymorphism

Whenever there are multiple implementations of the same interface specification for some class, we say that we have a polymorphic class. Consider the class stream, with subclasses input_stream, output_stream and perhaps window, a subclass of output_stream. This is a class that was understood to be polymorphic as far back as the 1960's.

When languages allow polymorphic classes are translated to assembly language, each object of each class that implements the same interface must begin with a type or class indicator to tell us which implementation to use. There are several ways to do this; some of these give faster access to methods of objects of polymorphic classes, while others give more compact representations for objects of such classes.

The fastest way to access methods of objects that are instances of polymorphic classes is to include pointers to the applicable methods directly in each instance of each object. For objects that are instances of the stream class or its subclasses, we might do this as follows:

A fast representation for a polymorphic stream class
; format of a stream object (stream of bytes)
;   for all stream operations,
;     on entry, R3 = pointer to stream object
;     on exit,  R3 = pointer to stream object

; all compatable stream objects begin with
; pointers to the implementations of each method
PSTINIT =       0       ; initialize a stream
PSTPUT  =       0       ; put a character on the stream
			;   takes R4 as the value to put
PSTGET  =       4       ; get a character from the stream
			;   returns R4 as the value gotten

; the following fields depend on the particular subclass and
; generally include a representation for the particular stream

This stream representation was first used in an operating system designed by Christopher Strachey and his students in the 1960's. The paper describing that work was one of the very first clear presentations of object oriented polymorphism. At around the same time, the developers of the Simula 67 programming language coined the terms object and class as they are used today.

Fast access to a method of a polymorphic method
; given R3, a pointer to an initialized stream object
LOAD    R1,R3,PSTPUT    ; get pointer to the appropriate PUT method
JSRS    R1,R1           ; call the method

The initializer for a class does not follow this pattern. Initializers are not polymorphic. To initialize an object, one must pick a particular implementation. Therefore, calls to initializers are never polymorphic calls, but rather, direct calls to the initializer routine of a particular implementation.

For objects as simple as streams, this an appropriate implementation, but consider what happens with a class such as "floating point number". Floating point numbers have many implementations: single precision, double precision, even arbitrary precision. They support many many operations: add, subtract, multiply, divide, sine, cosine, exponentiate, truncate, round, and many more. If each floating point object began with pointers to all applicable methods, this list would generally exceed the size of the number representaiton by a wide margin.

To avoid this huge storage overhead, we can store the pointers to the methods in a compact table outside the objects. The table of method pointers is constant for each class implementation, so it can be stored in in the same memory area that holds the code for the implementation. It is common to refer to this table of method pointers as the class descriptor, and to refer to the pointer to the class descriptor stored in each object as the tag field of that object. Most implementations of object-oriented programming languages use this approach. This leads to the following code for a call to a method of a polymorphic class:

Access to a method of an efficiently represented polymorphic floating point number
     
; assume R3 points to an initialized floating point value
LOADS   R1,R3           ; follow tag to descriptor of object's class
LOAD    R1,R1,PFLTSIN   ; get pointer to the SIN method
JSRS    R1,R1           ; call the method
     

This is the approach used in most modern object oriented languages. This means is that calls to methods of polymorphic classes cost, typically, one or at most two more instructions more than calls to simple subroutines. Good compilers always avoid using this more expensive mechanism when the method can be uniquely determined at compile time.

Languages like Java add a new layer of inefficiency by including large numbers of default attributes in every instance of every class. If each object knows its own name, debugging is greatly simplified, but this requires that each object representation hold a pointer to the string constant holding name. This adds significantly to the memory requirements of large programs.

For this reason, object oriented languages almost always include a large collection of built-in types that are outside the class hierarchy of the language. Built in integer, character and floating point numbers are implemented directly with the hardware's natural data types and are not referenced by handles, but rather, are included directly in the objects where they appear.

Exercises

j) Write an implementation OUTSTR, output stream, that calls DSPCH for each character put on the output stream. Attempts to get input from an output stream should always return zero (ideally, these ought to raise an unimplemented operation exception).