The problem posed was to investigate the implementation of a version of the switch statement described by
SwitchStatement
= "switch" "(" Expression ")" "{"
{ CaseLabelList Statement { Statement } }
[ "default" ":" { Statement } ]
"}" .
CaseLabelList = CaseLabel { CaseLabel } .
CaseLabel = "case" [ "+" | "-" ] Constant ":" .
The semantics here require that the Expression be evaluated once, and its value compared for membership of one of the sets of CaseLabelLists, a match being followed by execution of the associated statement list. If no match is found, the statement list associated with the optional default clause is executed (or, in the absence of the default option, no action is taken at all). There are many variations on this theme, but for the one illlustrated here we suggest that (a) there is an automagic BreakStatement introduced at the end of each statement list so that there is no need to include an explicit BreakStatement in each statement list, although these may occur if needed (b) the concept of "falling through" in the absence of an explicit BreakStatement thus does not apply (c) more than one CaseLabel may be associated with a given statement list and (d) each CaseLabelList must be separated from the next one by at least one statement in its statement list (even if this is an empty statement).
Here is an example of a (silly) switch statement:
switch (i + j) {
case 2 : if (i === j) break; write("i = " , i); read(i, j);
case 4 : write("four"); i = 12;
case 6 : write("six");
case -9 :
case 9 :
case -10 :
case 10 : write("plus or minus nine or ten"); i = 12;
default : write("not 2, 4, 6, 9 or 10");
}
One way to implement this would be to generate code matching an equivalent set of IfStatements on the lines of the following, where we have taken some liberties with syntax, though the effect should be obvious:
if (i + j == 2) { if (i === j) goto out; write("i = " , i); read(i, j); goto out; }
elsif (i + j == 4) { write("four"); i = 12; goto out; }
elsif (i + j == 6) { write("six"); goto out; }
elsif (i + j in (-9, 9, -10, 10)) { write("plus or minus nine or ten"); i = 12; goto out; }
else write("not 2, 4, 6, 9 or 10");
out: ...
If we treat this slightly differently:
temp = i + j;
if (temp == 2) { if (i === j) goto out; write("i = " , i); read(i, j); goto out; }
elsif (temp == 4) { write("four"); i = 12; goto out; }
elsif (temp == 6) { write("six"); goto out; }
elsif (temp in (-9, 9, -10, 10)) { write("plus or minus nine or ten"); i = 12; goto out; }
else write("not 2, 4, 6, 9 or 10");
out: ...
then the temp value needed can be stored on the stack - if we can duplicate the value on the top of the stack before each successive comparison or test for list membership is effected, we can ensure that the value of the selector is preserved, in readiness for the next comparison. This calls for yet another simple opcode for the PVM, which can be generated by calling:
public static void duplicate() {
// Generates code to push another copy of top of stack
emit(PVM.dup);
}
and whose interpretation is as follows:
case PVM.dup: // duplicate top of stack
cpu.sp--;
if (inBounds(cpu.sp)) mem[cpu.sp] = mem[cpu.sp + 1];
break;
Although this idea does not lead to a highly efficient implementation of the SwitchStatement, it is relatively easy to implement - the complexity arising from the need, as usual, to impose semantic checks that all labels are unique, that the type of the selector is compatible with the type of each label, and from a desire to keep the number of branching operations as low as possible. To effect the test for membership of a list of labels like the -9, 9, -10 and 10 of the example we play the same game again - another code generation routine:
public static void membership(int count, int type) {
// Generates code to check membership of a list of count expressions
if (count == 1) comparison(CodeGen.ceq, type);
else { emit(PVM.memb); emit(count); }
}
with a two-word opcode interpreted as follows:
case PVM.memb: // membership test
boolean isMember = false;
loop = next();
int test = mem[cpu.sp + loop];
for (int m = 0; m < loop; m++) if (pop() == test) isMember = true;
mem[cpu.sp] = isMember ? 1 : 0;
break;
The code for the parsing routine follows:
SwitchStatement<StackFrame frame> (. int expType, labelCount;
boolean branchNeeded = false;
boolean hasClauses = false;
Label nextSwitch = new Label(!known);
Label switchExit = new Label(!known);
ArrayList<Integer> labelList = new ArrayList<Integer>(); .)
= "switch" "("
Expression<out expType> (. if (isRef(expType) || expType == Entry.noType)
SemError("invalid selector type"); .)
")"
"{"
{ (. if (branchNeeded) CodeGen.branch(switchExit);
branchNeeded = true;
nextSwitch.here();
nextSwitch = new Label(!known);
CodeGen.duplicate(); .)
CaseLabelList<out labelCount, expType, labelList>
(. CodeGen.membership(labelCount, expType);
CodeGen.branchFalse(nextSwitch); .)
Statement<frame, switchExit> (. hasClauses = true; .)
{ Statement<frame, switchExit> }
}
( "default" ":" (. if (branchNeeded) CodeGen.branch(switchExit);
nextSwitch.here(); .)
{ Statement<frame, switchExit> (. hasClauses = true; .)
}
| (. nextSwitch.here(); .)
)
"}" (. if (!hasClauses) Warning("Empty switch statement");
switchExit.here();
CodeGen.pop(1); .) .
CaseLabelList<. out int labelCount, int expType, ArrayList<Integer> labelList .>
= CaseLabel<expType, labelList> (. labelCount = 1; .)
{ CaseLabel<expType, labelList> (. labelCount++; .)
} .
CaseLabel<. int expType, ArrayList<Integer> labelList .>
(. ConstRec con;
int factor = 1;
boolean signed = false; .)
= "case"
[ ( "+" | "-" (. factor = -1; .)
) (. signed = true; .)
] Constant<out con> ":" (. if (!compatible(con.type, expType)
|| signed && con.type != Entry.intType)
SemError("invalid label type");
int lab = factor * con.value;
if (labelList.contains(lab))
SemError("duplicated case label");
else labelList.add(lab);
CodeGen.loadConstant(lab); .) .
Notes
switch (selector) {
case 20: case 30: case 40: statement 1;
case 50: statement 2;
default: statement 3;
}
which gives rise to code like
selector
DUP
LDC 20
LDC 30
LDC 40
MEMB 3
BZE next
statement 1
BRN exit
next DUP
LDC 50
CEQ
BZE default
statement 2
BRN exit
default statement 3
exit DSP -1
...