David's Web Repository David Boddie - Projects David Boddie - Updates

Juggling Registers

Previously, I talked about the problem of making sure that virtual registers are allocated correctly when generating bytecode for DEX files. Ideally, the registers will be allocated in a fairly efficient way, though we can at least aim to do a reasonable job and look for optimisations later.

Virtual Registers

We encounter virtual registers when we look at the way methods are implemented in the Dalvik virtual machine. The registers are “virtual” because they are not actually CPU registers. The way to think about them is 32-bit words in a stack frame. When a method is entered, the virtual registers contain values for the arguments to the method plus enough registers for the method to use as workspace. As a starting point for seeing how this works, let's consider two methods defined in a class called HelloActivity.

class HelloActivity(Activity):

    def __init__(self):
    
        Activity.__init__(self)

    @args(void, [Bundle])
    def onCreate(self, bundle):
    
        Activity.onCreate(self, bundle)
        
        view = TextView(self)
        view.setText("Hello world!")
        self.setContentView(view)

The first of these is the class's __init__ method, which takes one argument, uses no additional local variables and calls the __init__ method of the base class with the argument supplied. Describing this to the virtual machine, we say that the method has one incoming argument (taking one register in this case) and one outgoing argument (the same register), and it uses a total of one register.

The second method, onCreate, takes two arguments – both of which refer to objects and only require a register each. However, it also uses two additional registers for local and temporary variables. There are also method calls that use a maximum of two registers.

The total number of registers needed for a method is the number of arguments plus the number of local variables (named or temporary). The number of outputs to the method is not part of this sum. Note also that the total cannot be less than the number of inputs or outputs.

To see how the registers are arranged, we will take a look at each of these methods in turn.

A Very Simple Method

Below, we show the code for the __init__ method alongside the instructions generated for it. Remembering that there is a total of one register allocated for this method, we see that this is the same register used to hold the argument passed to the method: the instance object corresponding to self. Although there is a need for a register to hold the argument to the Activity.__init__ call, this is the same register that was passed as the argument to this method.

Registers:
Input: 1 Output: 1 Total: 1

Arguments:
v0: self : com/example/hello/HelloActivity

HelloActivity.__init__
Activity.__init__(self)
0: invoke_direct <Count 1>,v0,@2 method (android/app/Activity.<init>)
3: return_void

The instructions generated for the method correspond closely to the high level code. The first one invokes the base class's __init__ method (though the actual name is <init>) with the register holding the self object which was supplied as the method's argument. The instruction contains an index into the DEX file's method table which we have dereferenced here for clarity. The second instruction simply exits the method without returning any value. Although it might be expected that the method should return None, the virtual machine neither expects nor wants to receive a return value, so we exit in this manner.

A Simple Method with Variables

The onCreate method is a bit better at showing us how registers are allocated. Remember that it accepts two arguments, each of which can be represented using one register. The total number of registers used is four, since two variables are also allocated that use one register each. At any time, a maximum of two of these registers are used in method calls from within the method.

Registers:
Input: 2 Output: 2 Total: 4

Variables:
v0: view : android/widget/TextView
v1: [temporary] : java/lang/String

Arguments:
v2: self : com/example/hello/HelloActivity
v3: bundle : android/os/Bundle

It should be apparent that the virtual registers for incoming method arguments are allocated in a block at the top of the range of registers that the method requires, and that the local variables use the lowest registers. This makes sense if we think of a stack being extended downwards in memory when a method is called.

The method is called self bundle ... The arguments have been stored on the stack.
In the method out0 out1 v0 v1 v2 self v3 bundle ... Arguments and variables are referenced using the virtual registers for this method.
Calling Activity.onCreate ... self bundle v0 v1 v2 self v3 bundle ... The arguments are copied lower down in the stack into the number of slots declared by the callee, in preparation for it to be called.
Creating the TextView instance out0 out1 v0 view v1 v2 self v3 bundle ... Register v0 is assigned to the view variable for the rest of the method.

While this shows a simplified version of the method calling mechanism, we can use this picture to help us think about how to allocate registers and which ones to use to hold the contents of local variables and method arguments. The instructions generated from the high level code are shown below.

HelloActivity.onCreate
Activity.onCreate(self, bundle)
00: invoke_super <Count 2>,v2,v3,@3 method (android/app/Activity.onCreate)
view = TextView(self)
03: new_instance v0,@6 (android/widget/TextView)
05: invoke_direct <Count 2>,v0,v2,@4 method (android/widget/TextView.<init>)
view.setText('Hello world!')
08: const_string v1,@5 (Hello world!)
0a: invoke_virtual <Count 2>,v0,v1,@5 method (android/widget/TextView.setText)
self.setContentView(view)
0d: invoke_virtual <Count 2>,v2,v0,@9 method (com/example/hello/HelloActivity.setContentView)
10: return_void

The Activity.onCreate call is as described above, with the same registers containing input arguments used to call the base class's method. The creation of the TextView instance involves the first local variable, view, whose value is held in the virtual register, v0. Immediately after creating this instance, we call its __init__ method with self (v2) as the argument – this method call only requires two registers.

The setText method call uses the temporary, unnamed variable (v1) created to hold a reference to the "Hello world!" string and is a virtual method call invoked on the TextView instance held by view (v0). Again, only two registers are needed for this method call. The final method call on self (v2) passes the view (v0).

More Complex Methods

The two examples shown above don't require much in the way of resources. When the number of registers needed for arguments or local variables increases, we can no longer guarantee that we will use less than 16 virtual registers. Some instructions can only use registers v0 to v15, such as comparisons, field/attribute access operations, method calls and type casting instructions, so it is inevitable that we will need to assign higher registers to some variables and arguments, copying their values down to low registers for some operations and copying the results back into those registers afterwards.

In addition to the restrictions on registers used for certain operations, methods that we want to call which require more than five arguments also need to be handled specially with contiguous blocks of registers, almost certainly requiring values to be copied into place. We could potentially arrange variables to be allocated in a way that avoids this, but it may not be possible to do this in a general way, especially if the same variables need to be passed to another method in a different order.

Categories: Free Software, Android

Copyright © 2016 David Boddie
Published: 2016-05-14 00:00:00 UTC
Last updated: 2016-10-14 11:14:08 UTC

This document is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International license.