Bonus: Advanced Branching (Switch Statement)

Consider a switch statement:

switch(r0) {
  case 0: ~~~0;
          break;
  case 1: ~~~1;
          break;
  ...
  case 0xf: ~~~f;
            break;
  default:
            ~~~default;
}
~~~done

If / Else Naive Implementation

  0: rr move r1, r0     # r1 = r0
     beq r1, 0x??0      # goto "0" case
     dec r1             # r1 = r0 - 1
     beq r1, 0x??1      # goto "1" case
     ...
     dec r1             # r1 = r0 - f
     beq r1, 0x??f      # goto "f" case
     ~~~default         # execute "default" case
     br 0x???           # exit
??0: ~~~0               # execute "0" case
     br 0x???           # exit
??1: ~~~1               # execute "1" case
     br 0x???           # exit
...
??f: ~~~f               # execute "f" case
???: ~~~done            # outside the switch

Case     # conditions evaluated      # branches taken
  0                 1                      2
  1                 2                      2
 ..
  e                15                      2
  f                16                      1
 <0                17                      1
 >f                17                      1
Sum:              170                     31

Every additional case adds progressively more and more to the number of conditions evaluated. The number of branches taken remains constant for each execution path.

Switch / Jump Table Implementation

   0:  move r1, r0          # r1 = r0
       dec r1               
       bgt r1 0x08          # ensure >=0 (in range)
       br "def"             # if not, goto "default" case
   8:  move r1, r0          # r1 = r0
       ld $0xFFFFFFF1, r2   # r2 = -f
       add r2, r1           # r1 = r0 - f
       bgt r1 "def"         # goto "default" case if > f
       move r1, r0          # r1 = r0 (and r1 is in range)
       ld $0x00001000, r2   # r2 = & jump table
       jmp *(4*r1, r2)      # jump to the right case
"c0":  ~~~0                 # case "0"
       br "done"            # exit
"c1":  ~~~1                 # case "1"
       br "done"            # exit
...
"cf":  ~~~f                 # case "f"
       br "done"            # exit
"def": ~~~~default         # "default" case
"done" ~~~~done            # outside the switch
...
1000:  &"c0"    # jump table, filled with addresses of cases
       &"c1"
       ...
       &"cf"

Case     # conditions evaluated      # branches taken
  0                 3                      3
  1                 3                      3
 ..
  e                 3                      3
  f                 3                      3
 <0                 1                      1
 >f                 2                      1
Sum:               48                     47

More cases do not grow the number of conditions evaluated per path, and the number of branches taken per path remains constant.

Special Note: the number of branches taken in the above example is higher than that of the if/else example due to the branch on the ">0" case. This branch can be eliminated by reversing the test:

   0:  move r1, r0          # r1 = r0
       not r1               # 
       inc r1               # r1 = -r0
       bgt r1 "def"         # goto "default" if <0
   8:  move r1, r0
       ld $0xFFFFFFF1, r2   # r2 = -f
       add r2, r1           # r1 = r0 - f
       bgt r1 "def"         # goto "default" case if > f
       move r1, r0          # r1 = r0 (and r1 is in range)
       ld $0x00001000, r2   # r2 = & jump table
       jmp *(4*r1, r2)      # jump to the right case
...

Case     # conditions evaluated      # branches taken
  0                 3                      2
  1                 3                      2
 ..
  e                 3                      2
  f                 3                      2
 <0                 1                      1
 >f                 2                      1
Sum:               48                     32

For more information, see Implementing Common Control Structures in Assembly Language and/or C to Assembly Translation III.