Jump Table

Jump table is the efficient way of transferring program control from one point to another based on a table of branch instructions. Many compilers use this technique, especially when using a switch statement which contain consecutive integers as case and number of case is not too small. The MSP compiler uses this optimization method if the number of case condition is not too low. This can be explained using a C code which contains 15 case condition. We can generate the assembly code by compiling the C code with -S option. The code contain a local variable i assigned to 1 and 0 to 14 case condition each having the same assignment with different values.

 

The code sections shown below are parts of the assembly code generated

The first step is to decrement the stack pointer SP by two as our code contain a local variable. The stack pointer address is moved to register r4.

Now move the initial value 1 to the address stored in r4. Value in r4 is taken as the value of switch and checked whether the value is greater than the values assigned for case condition. If so the control simply jump to the end. We move the value in the address location stored in r4 to register r15. rla is rotate left arithmetically. This step simply doubles the value at r15. The need for doubling is every entry in the jump table is entered as a word. .L18 is the base address of the jump table. We add it to the value in register r15. Now the value in r15 act as an offset. r15 contains an address, that holds the value which is the address of a step in the jump table which is to be executed. This value is brought to the register r15. br will simply branch the control to the matching address in the jump table. Thus there is no need to check each and every cases to find the execution steps to follow.

The above figure is a minimized part of the jump table.

In our example case the control jump to .L4 as our initial value is 1.

In .L4 a simple move instruction is executed and the control jumps to the end.

This optimization is possible only if consecutive numbers constitute the case condition. The same code with lesser number of case statement do simple comparison and jump. Thus jump table creation is based on the compiler. Some compiler may generate the table for small number of case statement others may do it when a large number of case statement.

Advertisements

About Odol Shinu

I've completed my B Tech in Information Technology in 2010 from Government Engineering College Sreekrishnapuram Palakkad under Calicut University.

Posted on November 3, 2010, in MSP430 Family. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: