MVM: Minimal Virtual Machine | a project by Stefan Reich
As a sample algorithm, a bubblesort was implemented in MVM. Here's some stats:
The code was produced from within Java using a somewhat ad-hoc utility class called CodeGen. CodeGen provides the typical macros you want when you program for MVM (copy, load, store, add). Handling labels is a bit messy (note how the forward-jump requires manual patching).
listStart and listEnd are constant addresses. ax, bx, i and j are variables or memory-mapped registers, however you like to perceive them.
Here's the Java source:
gen.set(i, 1-(listEnd-listStart-1)); // i is a negative counter int lLoop = gen.getPC(); gen.set(j, listStart); // load pair int lLoopJ = gen.getPC(); gen.load(ax, j); gen.addC(j, 1); gen.load(bx, j); gen.subC(j, 1); int patchNoSwap = gen.getPC()+2; gen.subleq(ax, bx, PATCH); // swap gen.add(ax, bx); // restore ax gen.addC(j, 1); gen.store(j, ax); gen.subC(j, 1); gen.store(j, bx); // loop while j <= listEnd-2 gen.patch(patchNoSwap, gen.getPC()); gen.addC(j, 1); gen.copy(ax, j); gen.subleqC(ax, listEnd-2, lLoopJ); // loop while ++i <= 0 gen.subleqC(i, -1, lLoop);Alright, it's not a beauty, but at least we get 60 subleqs out of far less than 60 lines.
1016: 00000003 00000003 000003FB | clr i 1019: FFFFFFFC 000003E6 000003FE | sub i #(998) 1022: 00000004 00000004 00000401 | lLoopI: clr j 1025: FFFFFFFB FFFFFFF0 00000404 | sub j #(-16) 1028: 00000000 00000004 00000407 | lLoopJ: sub Z j 1031: 00000411 00000411 0000040A | clr 1041 1034: 00000411 00000000 0000040D | sub 1041 Z 1037: 00000000 00000000 00000410 | clr Z 1040: 00000000 7FFFFFFF 00000413 | sub Z * 1043: 00000001 00000001 00000416 | clr ax 1046: 00000001 00000000 00000419 | sub ax Z 1049: 00000000 00000000 0000041C | clr Z 1052: FFFFFFFB FFFFFFFF 0000041F | sub j #(-1) 1055: 00000000 00000004 00000422 | sub Z j 1058: 0000042C 0000042C 00000425 | clr 1068 1061: 0000042C 00000000 00000428 | sub 1068 Z 1064: 00000000 00000000 0000042B | clr Z 1067: 00000000 7FFFFFFF 0000042E | sub Z * 1070: 00000002 00000002 00000431 | clr bx 1073: 00000002 00000000 00000434 | sub bx Z 1076: 00000000 00000000 00000437 | clr Z 1079: FFFFFFFB 00000001 0000043A | sub j #(1) 1082: 00000001 00000002 00000494 | sub ax bx leq lNoSwap 1085: 00000000 00000002 00000440 | sub Z bx 1088: 00000001 00000000 00000443 | sub ax Z 1091: 00000000 00000000 00000446 | clr Z 1094: FFFFFFFB FFFFFFFF 00000449 | sub j #(-1) 1097: 00000000 00000004 0000044C | sub Z j 1100: 00000461 00000461 0000044F | clr 1121 1103: 00000461 00000000 00000452 | sub 1121 Z 1106: 00000462 00000462 00000455 | clr 1122 1109: 00000462 00000000 00000458 | sub 1122 Z 1112: 00000467 00000467 0000045B | clr 1127 1115: 00000467 00000000 0000045E | sub 1127 Z 1118: 00000000 00000000 00000461 | clr Z 1121: 7FFFFFFF 7FFFFFFF 00000464 | sub * * 1124: 00000000 00000001 00000467 | sub Z ax 1127: 7FFFFFFF 00000000 0000046A | sub * Z 1130: 00000000 00000000 0000046D | clr Z 1133: FFFFFFFB 00000001 00000470 | sub j #(1) 1136: 00000000 00000004 00000473 | sub Z j 1139: 00000488 00000488 00000476 | clr 1160 1142: 00000488 00000000 00000479 | sub 1160 Z 1145: 00000489 00000489 0000047C | clr 1161 1148: 00000489 00000000 0000047F | sub 1161 Z 1151: 0000048E 0000048E 00000482 | clr 1166 1154: 0000048E 00000000 00000485 | sub 1166 Z 1157: 00000000 00000000 00000488 | clr Z 1160: 7FFFFFFF 7FFFFFFF 0000048B | sub * * 1163: 00000000 00000002 0000048E | sub Z bx 1166: 7FFFFFFF 00000000 00000491 | sub * Z 1169: 00000000 00000000 00000494 | clr Z 1172: FFFFFFFB FFFFFFFF 00000497 | lNoSwap: sub j #(-1) 1175: 00000000 00000004 0000049A | sub Z j 1178: 00000001 00000001 0000049D | clr ax 1181: 00000001 00000000 000004A0 | sub ax Z 1184: 00000000 00000000 000004A3 | clr Z 1187: FFFFFFFE 000003F6 00000404 | sub ax #(1014) leq lLoopJ 1190: FFFFFFFC FFFFFFFF 000003FE | sub i #(-1) leq lLoopI 1193: 00000000 00000000 FFFFFFFF | sub Z Z leq NIRVANA