1 /*
2 toy vm
3 register A, B : 32bit
4 PC : program counter
5
6 mem_ 4byte x 65536
7
8 ���٤Ƥ�̿���4byte����
9 ¨�ͤ�����16bit
10
11 R = A or B
12 vldiR, imm ; R = imm
13 vldR, idx ; R = mem_[idx]
14 vstR, idx ; mem_[idx] = R
15 vaddiR, imm ; R += imm
16 vsubiR, imm ; R -= imm
17 vaddR, idx ; R += mem_[idx]
18 vsubR, idx ; R -= mem_[idx]
19 vputR ; print R
20 vjnzR, offset; if (R != 0) then jmp(PC += offset(signed))
21 */
22 #if defined(_MSC_VER) && (_MSC_VER <= 1200)
23 #pragma warning(disable:4514)
24 #pragma warning(disable:4786)
25 #endif
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <memory.h>
29 #include <vector>
30 #define XBYAK_NO_OP_NAMES
31 #include "xbyak/xbyak.h"
32 #include "xbyak/xbyak_util.h"
33 #define NUM_OF_ARRAY(x) (sizeof(x) / sizeof(x[0]))
34
35 #ifdef XBYAK64
36 #error "only 32bit"
37 #endif
38
39 using namespace Xbyak;
40
41 class ToyVm : public Xbyak::CodeGenerator {
42 typedef std::vector<uint32> Buffer;
43 public:
44 enum Reg {
45 A, B
46 };
47 enum Code {
48 LD, LDI, ST, ADD, ADDI, SUB, SUBI, PUT, JNZ,
49 END_OF_CODE
50 };
ToyVm()51 ToyVm()
52 : mark_(0)
53 {
54 ::memset(mem_, 0, sizeof(mem_));
55 }
vldi(Reg r,uint16 imm)56 void vldi(Reg r, uint16 imm) { encode(LDI, r, imm); }
vld(Reg r,uint16 idx)57 void vld(Reg r, uint16 idx) { encode(LD, r, idx); }
vst(Reg r,uint16 idx)58 void vst(Reg r, uint16 idx) { encode(ST, r, idx); }
vadd(Reg r,uint16 idx)59 void vadd(Reg r, uint16 idx) { encode(ADD, r, idx); }
vaddi(Reg r,uint16 imm)60 void vaddi(Reg r, uint16 imm) { encode(ADDI, r, imm); }
vsub(Reg r,uint16 idx)61 void vsub(Reg r, uint16 idx) { encode(SUB, r, idx); }
vsubi(Reg r,uint16 imm)62 void vsubi(Reg r, uint16 imm) { encode(SUBI, r, imm); }
vjnz(Reg r,int offset)63 void vjnz(Reg r, int offset) { encode(JNZ, r, static_cast<uint16>(offset)); }
vput(Reg r)64 void vput(Reg r) { encode(PUT, r); }
setMark()65 void setMark()
66 {
67 mark_ = (int)code_.size();
68 }
getMarkOffset()69 int getMarkOffset()
70 {
71 return mark_ - (int)code_.size() - 1;
72 }
run()73 void run()
74 {
75 bool debug = false;//true;
76 uint32 reg[2] = { 0, 0 };
77 const size_t end = code_.size();
78 uint32 pc = 0;
79 for (;;) {
80 uint32 x = code_[pc];
81 uint32 code, r, imm;
82 decode(code, r, imm, x);
83 if (debug) {
84 printf("---\n");
85 printf("A %08x B %08x\n", reg[0], reg[1]);
86 printf("mem_[] = %08x %08x %08x\n", mem_[0], mem_[1], mem_[2]);
87 printf("pc=%4d, code=%02x, r=%d, imm=%04x\n", pc, code, r, imm);
88 }
89 switch (code) {
90 case LDI:
91 reg[r] = imm;
92 break;
93 case LD:
94 reg[r] = mem_[imm];
95 break;
96 case ST:
97 mem_[imm] = reg[r];
98 break;
99 case ADD:
100 reg[r] += mem_[imm];
101 break;
102 case ADDI:
103 reg[r] += imm;
104 break;
105 case SUB:
106 reg[r] -= mem_[imm];
107 break;
108 case SUBI:
109 reg[r] -= imm;
110 break;
111 case PUT:
112 printf("%c %8d(0x%08x)\n", 'A' + r, reg[r], reg[r]);
113 break;
114 case JNZ:
115 if (reg[r] != 0) pc += static_cast<signed short>(imm);
116 break;
117 default:
118 assert(0);
119 break;
120 }
121 pc++;
122 if (pc >= end) break;
123 } // for (;;)
124 }
recompile()125 void recompile()
126 {
127 using namespace Xbyak;
128 /*
129 esi : A
130 edi : B
131 ebx : mem_
132 for speed up
133 mem_[0] : eax
134 mem_[1] : ecx
135 mem_[2] : edx
136 */
137 push(ebx);
138 push(esi);
139 push(edi);
140
141 const Reg32 reg[2] = { esi, edi };
142 const Reg32 mem(ebx);
143
144 const Reg32 memTbl[] = { eax, ecx, edx };
145 const size_t memTblNum = NUM_OF_ARRAY(memTbl);
146 for (size_t i = 0; i < memTblNum; i++) xor_(memTbl[i], memTbl[i]);
147
148 xor_(esi, esi);
149 xor_(edi, edi);
150 mov(mem, (size_t)mem_);
151 const size_t end = code_.size();
152 uint32 pc = 0;
153 uint32 labelNum = 0;
154 for (;;) {
155 uint32 x = code_[pc];
156 uint32 code, r, imm;
157 decode(code, r, imm, x);
158 L(Label::toStr(labelNum++));
159 switch (code) {
160 case LDI:
161 mov(reg[r], imm);
162 break;
163 case LD:
164 if (imm < memTblNum) {
165 mov(reg[r], memTbl[imm]);
166 } else {
167 mov(reg[r], ptr[mem + imm * 4]);
168 }
169 break;
170 case ST:
171 if (imm < memTblNum) {
172 mov(memTbl[imm], reg[r]);
173 } else {
174 mov(ptr [mem + imm * 4], reg[r]);
175 }
176 break;
177 case ADD:
178 if (imm < memTblNum) {
179 add(reg[r], memTbl[imm]);
180 } else {
181 add(reg[r], ptr [mem + imm * 4]);
182 }
183 break;
184 case ADDI:
185 add(reg[r], imm);
186 break;
187 case SUB:
188 if (imm < memTblNum) {
189 sub(reg[r], memTbl[imm]);
190 } else {
191 sub(reg[r], ptr [mem + imm * 4]);
192 }
193 break;
194 case SUBI:
195 sub(reg[r], imm);
196 break;
197 case PUT:
198 {
199 static const char *str = "%c %8d(0x%08x)\n";
200 push(eax);
201 push(edx);
202 push(ecx);
203 push(reg[r]);
204 push(reg[r]);
205 push('A' + r);
206 push((int)str);
207 call(reinterpret_cast<const void*>(printf));
208 add(esp, 4 * 4);
209 pop(ecx);
210 pop(edx);
211 pop(eax);
212 }
213 break;
214 case JNZ:
215 test(reg[r], reg[r]);
216 jnz(Label::toStr(labelNum + static_cast<signed short>(imm)));
217 break;
218 default:
219 assert(0);
220 break;
221 }
222 pc++;
223 if (pc >= end) break;
224 } // for (;;)
225
226 pop(edi);
227 pop(esi);
228 pop(ebx);
229 ret();
230 }
231 private:
232 uint32 mem_[65536];
233 Buffer code_;
234 int mark_;
decode(uint32 & code,uint32 & r,uint32 & imm,uint32 x)235 void decode(uint32& code, uint32& r, uint32& imm, uint32 x)
236 {
237 code = x >> 24;
238 r = (x >> 16) & 0xff;
239 imm = x & 0xffff;
240 }
encode(Code code,Reg r,uint16 imm=0)241 void encode(Code code, Reg r, uint16 imm = 0)
242 {
243 uint32 x = (code << 24) | (r << 16) | imm;
244 code_.push_back(x);
245 }
246 };
247
248 class Fib : public ToyVm {
249 public:
Fib(int n)250 Fib(int n)
251 {
252 if (n >= 65536) {
253 fprintf(stderr, "current version support only imm16\n");
254 return;
255 }
256 /*
257 A : c
258 B : temporary
259 mem_[0] : p
260 mem_[1] : t
261 mem_[2] : n
262 */
263 vldi(A, 1); // c
264 vst(A, 0); // p(1)
265 vldi(B, static_cast<uint16>(n));
266 vst(B, 2); // n
267 // lp
268 setMark();
269 vst(A, 1); // t = c
270 vadd(A, 0); // c += p
271 vld(B, 1);
272 vst(B, 0); // p = t
273 // vput(A);
274 vld(B, 2);
275 vsubi(B, 1);
276 vst(B, 2); // n--
277 vjnz(B, getMarkOffset());
278 vput(A);
279 }
runByJIT()280 void runByJIT()
281 {
282 getCode<void (*)()>();
283 }
284 };
285
fibC(uint32 n)286 void fibC(uint32 n)
287 {
288 uint32 p, c, t;
289 p = 1;
290 c = 1;
291 lp:
292 t = c;
293 c += p;
294 p = t;
295 n--;
296 if (n != 0) goto lp;
297 printf("c=%d(0x%08x)\n", c, c);
298 }
299
main()300 int main()
301 {
302 try {
303 const int n = 10000;
304 Fib fib(n);
305
306 fib.recompile();
307
308 {
309 Xbyak::util::Clock clk;
310 clk.begin();
311 fib.run();
312 clk.end();
313 printf("vm %.2fKclk\n", clk.getClock() * 1e-3);
314 }
315
316 {
317 Xbyak::util::Clock clk;
318 clk.begin();
319 fib.runByJIT();
320 clk.end();
321 printf("jit %.2fKclk\n", clk.getClock() * 1e-3);
322 }
323
324 {
325 Xbyak::util::Clock clk;
326 clk.begin();
327 fibC(n);
328 clk.end();
329 printf("native C %.2fKclk\n", clk.getClock() * 1e-3);
330 }
331 } catch (std::exception& e) {
332 printf("ERR:%s\n", e.what());
333 } catch (...) {
334 printf("unknown error\n");
335 }
336 return 0;
337 }
338
339 /*
340 the code generated by Xbyak
341 push ebx
342 push esi
343 push edi
344 xor eax,eax
345 xor ecx,ecx
346 xor edx,edx
347 xor esi,esi
348 xor edi,edi
349 mov ebx,0EFF58h
350 mov esi,1
351 mov eax,esi
352 mov edi,2710h
353 mov edx,edi
354 .lp:
355 mov ecx,esi
356 add esi,eax
357 mov edi,ecx
358 mov eax,edi
359 mov edi,edx
360 sub edi,1
361 mov edx,edi
362 test edi,edi
363 jne .lp
364 push eax
365 push edx
366 push ecx
367 push esi
368 push esi
369 push 41h
370 push 42C434h
371 call printf (409342h)
372 add esp,10h
373 pop ecx
374 pop edx
375 pop eax
376 pop edi
377 pop esi
378 pop ebx
379 ret
380 */
381