Saturday, July 14, 2012

Assembly Code Generation - part#4

This is the 4th post in the series of assembly code generation.

Part - I
Part - II
Part - III

In this post, I will try to describe how a method definition and dispatch might be translated to assembly language.

Methods also define a local "scope". Any global variables can be overriden in this scope and new ones(called local variables) can be defined here. Typically whenever a method call is made, we put a specific structure called "stack frame"(or "activation record") in the memory. In the "activation record" method parameters, local variables, return address etc are kept at known positions. Typically parameters and local variable values are kept at fixed offsets from a know position called the "frame pointer" in the activation record.

One of the main task while emitting code for method definition or dispatch is to design the strcuture of your activation record. Typically method dispatch fills part of the activation record and remaining is filled by the code generated by method definition.

We will use register \$fp for frame pointer and \$ra for return address, to hold them whenever required.

At this point I will introduce a few more invariants..

1. Inside a method register \$s0 always has the address to self object .

So, here is the structure of my activation record.

argument # n
argument # n-1
argument # 1
------------------------- <-- I keep \$fp to have this location
fixed space reserved
for local variables

One more thing we need to understand is the structure of something called, a "dispatch table". Remember, in part-III of this series, I described the structure of the prototype objects, which keep a pointer, dispatch table pointer, at offset 8.
The dispatch table is nothing but a list of all the methods visible(defined in the class and the ones defined in the parent and its parent and so on.) in the class of the prototype object.

Let us look at one method table...

class A inherits Object {

      foo(x:Int, y:Int): Int {

      --overriding copy
      copy():SELF {

Generate method table..

  .word  Object.abort
  .word  Object.type_name
  .word  A.copy

Notice the ordering, they are listed from super type to the base type in the order of their definition. Notice A.copy appears before because copy() is defined in base class Object, before foo(..) is defined in A. Compiler will generate dispatch tables like this for all the classes defined in the program. And labels like are generated where we generate the code for method definition for foo in A.

Let us see how a method dispatch might translate to assembly...

Original code..,param2);

Assembly code generated...

#push all the argument to the stack..

  #generate code to evaluate param2
  #that should put param2 result in \$a0
  sw    \$a0     0(\$sp)
  addiu \$sp     \$sp     -4

  #generate code to evaluate param1
  #that should put param1 result in \$a0
  sw    \$a0     0(\$sp)
  addiu \$sp     \$sp     -4

  #emit code to evaluate x from that
  #should put x evaluation result object pointer
  #in \$a0
  #after pushing the arguments in memory
  #locate the label for method foo and jump

  #Object returned by x will have dispatch table pointer
  #located at offset 8, in the dispatch table label can
  #be found at a fixed offset known at compile time
  #here we just jump to that location

Let us now see, how the method definition for translates to assembly..

#First the label is generated
  #caller has pushed the arguments on stack
  #store location of current stack pointer
  #in the frame pointer
  move    \$fp   \$sp
  #evaluate at compile time, how much
  #space you'll need for local variables
  #or temporaries and reserve it
  addiu    \$sp  \$sp 

  #generate code to evaluate method body

  #in the method body, arguments and locals
  #can be looked at from compile time known
  #offsets from frame pointer

  #load value of return address from stack frame
  #to register \$ra and jump there
  jump \$ra

Finally, for anyone reading these posts, I will highly recommend to take the online compiler class from coursera. And, to really learn it, you *HAVE TO* finish all the programming assignments.

No comments:

Post a Comment