0
$\begingroup$

I want to translate a java switch-case statement to intermediate representation of the three address code form. Three address code or TAC is a form of intermediate representation where each instruction contains at most three addresses and one operator. An address is a name such as x (stored in the symbol table), compiler generated temporary such as $t_{1}$ or a constant such as 3.14 or ‘s’. A name could refer to a variable, label, etc. If you have an arithmetic statement

(3 * w) + y

then the corresponding TAC would be

$t_{1}$ = 3 * w

$t_{2}$ = $t_{1}$ + y

Now, when it comes to switch statements, my textbook (the Dragon Book for Compilers), gives a translation of this form:

TAC for switch-case statement

for a switch-case statement of this type:

switch E

case V1: S1

...

case Vn-1: Sn-1

default: Sn

Assuming the first translation is used, at the code generation stage (when we convert 3AC to machine code), the code generator will interpret the instructions as a sequence of conditional and unconditional jumps with intervening labeled statement blocks. It would translate them into the machine code (say x86) version of the same. When these instructions are executed by the processor, it handles each jump sequentially to determine the correct labeled block to be executed. But, I have also read that the machine code translation of a switch-case statement includes a jump table that allows the processor to execute the entire switch statement in one go. So, then which version is used?

I wanted to post this on stackoverflow but I do not have enough reputation to post an image.

$\endgroup$
2
$\begingroup$

Some more things to look at:

First, mixed table/branch approach. Say you have cases 1, 2, 3, 4, 5, 6 and 999,999,999. You might check for 999,999,999 first, then use a table for the rest. And remember for the table approach that you need to check if the case is within the table. So take a table for 0-5, compare if case ≥ 6, if not you use the table, if yes, you handle the remaining case.

Second, probably most important: Binary search. Say you have cases 1-20. First you compare against 10. Branch to a second compare block if the case is >10. That alone halves the average number of comparisons needed.

Third, take advantage of one comparison usually giving multiple results. If you know that x = 1, 2 or 3, then you need only one comparison with 2 and two conditional branches.

$\endgroup$
1
  • $\begingroup$ So you are saying that if the range of possible case label values is small then the compiler generates a jump table(providing for O(1) evaluation of jump target by the processor) , otherwise it generates a sequence of jumps leading to O(n) time evaluation. Also, if there are several groups of label values, where the values within a group are close to each other, but the groups themselves are separated from each other by large distances, then the compiler generates a jump table for each group of closely separated labels and the processor sequentially checks for each group. $\endgroup$ Apr 17 '20 at 8:46
1
$\begingroup$

Both translations are valid. There's no way to answer - the compiler will choose one, using whatever strategy it uses. It is typical for a compiler to choose between those two options based on performance considerations, using some heuristics to try to predict which will perform better.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.