]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*============================================================================= |
2 | Copyright (c) 2001-2011 Joel de Guzman | |
3 | ||
4 | Distributed under the Boost Software License, Version 1.0. (See accompanying | |
5 | file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
6 | =============================================================================*/ | |
7 | #include "compiler.hpp" | |
8 | #include "vm.hpp" | |
9 | #include <boost/foreach.hpp> | |
10 | #include <boost/variant/apply_visitor.hpp> | |
11 | #include <boost/assert.hpp> | |
12 | #include <boost/lexical_cast.hpp> | |
13 | #include <set> | |
14 | ||
15 | namespace client { namespace code_gen | |
16 | { | |
17 | void function::op(int a) | |
18 | { | |
19 | code.push_back(a); | |
20 | size_ += 1; | |
21 | } | |
22 | ||
23 | void function::op(int a, int b) | |
24 | { | |
25 | code.push_back(a); | |
26 | code.push_back(b); | |
27 | size_ += 2; | |
28 | } | |
29 | ||
30 | void function::op(int a, int b, int c) | |
31 | { | |
32 | code.push_back(a); | |
33 | code.push_back(b); | |
34 | code.push_back(c); | |
35 | size_ += 3; | |
36 | } | |
37 | ||
38 | int const* function::find_var(std::string const& name) const | |
39 | { | |
40 | std::map<std::string, int>::const_iterator i = variables.find(name); | |
41 | if (i == variables.end()) | |
42 | return 0; | |
43 | return &i->second; | |
44 | } | |
45 | ||
46 | void function::add_var(std::string const& name) | |
47 | { | |
48 | std::size_t n = variables.size(); | |
49 | variables[name] = n; | |
50 | } | |
51 | ||
52 | void function::link_to(std::string const& name, std::size_t address) | |
53 | { | |
54 | function_calls[address] = name; | |
55 | } | |
56 | ||
57 | void function::print_assembler() const | |
58 | { | |
59 | std::vector<int>::const_iterator pc = code.begin() + address; | |
60 | ||
61 | std::vector<std::string> locals(variables.size()); | |
62 | typedef std::pair<std::string, int> pair; | |
63 | BOOST_FOREACH(pair const& p, variables) | |
64 | { | |
65 | locals[p.second] = p.first; | |
66 | std::cout << " local " | |
67 | << p.first << ", @" << p.second << std::endl; | |
68 | } | |
69 | ||
70 | std::map<std::size_t, std::string> lines; | |
71 | std::set<std::size_t> jumps; | |
72 | ||
73 | while (pc != (code.begin() + address + size_)) | |
74 | { | |
75 | std::string line; | |
76 | std::size_t address = pc - code.begin(); | |
77 | ||
78 | switch (*pc++) | |
79 | { | |
80 | case op_neg: | |
81 | line += " op_neg"; | |
82 | break; | |
83 | ||
84 | case op_not: | |
85 | line += " op_not"; | |
86 | break; | |
87 | ||
88 | case op_add: | |
89 | line += " op_add"; | |
90 | break; | |
91 | ||
92 | case op_sub: | |
93 | line += " op_sub"; | |
94 | break; | |
95 | ||
96 | case op_mul: | |
97 | line += " op_mul"; | |
98 | break; | |
99 | ||
100 | case op_div: | |
101 | line += " op_div"; | |
102 | break; | |
103 | ||
104 | case op_eq: | |
105 | line += " op_eq"; | |
106 | break; | |
107 | ||
108 | case op_neq: | |
109 | line += " op_neq"; | |
110 | break; | |
111 | ||
112 | case op_lt: | |
113 | line += " op_lt"; | |
114 | break; | |
115 | ||
116 | case op_lte: | |
117 | line += " op_lte"; | |
118 | break; | |
119 | ||
120 | case op_gt: | |
121 | line += " op_gt"; | |
122 | break; | |
123 | ||
124 | case op_gte: | |
125 | line += " op_gte"; | |
126 | break; | |
127 | ||
128 | case op_and: | |
129 | line += " op_and"; | |
130 | break; | |
131 | ||
132 | case op_or: | |
133 | line += " op_or"; | |
134 | break; | |
135 | ||
136 | case op_load: | |
137 | line += " op_load "; | |
92f5a8d4 | 138 | line += locals[*pc++]; |
7c673cae FG |
139 | break; |
140 | ||
141 | case op_store: | |
142 | line += " op_store "; | |
92f5a8d4 | 143 | line += locals[*pc++]; |
7c673cae FG |
144 | break; |
145 | ||
146 | case op_int: | |
147 | line += " op_int "; | |
148 | line += boost::lexical_cast<std::string>(*pc++); | |
149 | break; | |
150 | ||
151 | case op_true: | |
152 | line += " op_true"; | |
153 | break; | |
154 | ||
155 | case op_false: | |
156 | line += " op_false"; | |
157 | break; | |
158 | ||
159 | case op_jump: | |
160 | { | |
161 | line += " op_jump "; | |
162 | std::size_t pos = (pc - code.begin()) + *pc++; | |
163 | if (pos == code.size()) | |
164 | line += "end"; | |
165 | else | |
166 | line += boost::lexical_cast<std::string>(pos); | |
167 | jumps.insert(pos); | |
168 | } | |
169 | break; | |
170 | ||
171 | case op_jump_if: | |
172 | { | |
173 | line += " op_jump_if "; | |
174 | std::size_t pos = (pc - code.begin()) + *pc++; | |
175 | if (pos == code.size()) | |
176 | line += "end"; | |
177 | else | |
178 | line += boost::lexical_cast<std::string>(pos); | |
179 | jumps.insert(pos); | |
180 | } | |
181 | break; | |
182 | ||
183 | case op_call: | |
184 | { | |
185 | line += " op_call "; | |
186 | int nargs = *pc++; | |
187 | std::size_t jump = *pc++; | |
188 | line += boost::lexical_cast<std::string>(nargs) + ", "; | |
189 | BOOST_ASSERT(function_calls.find(jump) != function_calls.end()); | |
190 | line += function_calls.find(jump)->second; | |
191 | } | |
192 | break; | |
193 | ||
194 | case op_stk_adj: | |
195 | line += " op_stk_adj "; | |
196 | line += boost::lexical_cast<std::string>(*pc++); | |
197 | break; | |
198 | ||
199 | ||
200 | case op_return: | |
201 | line += " op_return"; | |
202 | break; | |
203 | } | |
204 | lines[address] = line; | |
205 | } | |
206 | ||
207 | std::cout << "start:" << std::endl; | |
208 | typedef std::pair<std::size_t, std::string> line_info; | |
209 | BOOST_FOREACH(line_info const& l, lines) | |
210 | { | |
211 | std::size_t pos = l.first; | |
212 | if (jumps.find(pos) != jumps.end()) | |
213 | std::cout << pos << ':' << std::endl; | |
214 | std::cout << l.second << std::endl; | |
215 | } | |
216 | ||
217 | std::cout << "end:" << std::endl << std::endl; | |
218 | } | |
219 | ||
220 | bool compiler::operator()(unsigned int x) | |
221 | { | |
222 | BOOST_ASSERT(current != 0); | |
223 | current->op(op_int, x); | |
224 | return true; | |
225 | } | |
226 | ||
227 | bool compiler::operator()(bool x) | |
228 | { | |
229 | BOOST_ASSERT(current != 0); | |
230 | current->op(x ? op_true : op_false); | |
231 | return true; | |
232 | } | |
233 | ||
234 | bool compiler::operator()(ast::identifier const& x) | |
235 | { | |
236 | BOOST_ASSERT(current != 0); | |
237 | int const* p = current->find_var(x.name); | |
238 | if (p == 0) | |
239 | { | |
240 | error_handler(x.id, "Undeclared variable: " + x.name); | |
241 | return false; | |
242 | } | |
243 | current->op(op_load, *p); | |
244 | return true; | |
245 | } | |
246 | ||
247 | bool compiler::operator()(ast::operation const& x) | |
248 | { | |
249 | BOOST_ASSERT(current != 0); | |
250 | if (!boost::apply_visitor(*this, x.operand_)) | |
251 | return false; | |
252 | switch (x.operator_) | |
253 | { | |
254 | case ast::op_plus: current->op(op_add); break; | |
255 | case ast::op_minus: current->op(op_sub); break; | |
256 | case ast::op_times: current->op(op_mul); break; | |
257 | case ast::op_divide: current->op(op_div); break; | |
258 | ||
259 | case ast::op_equal: current->op(op_eq); break; | |
260 | case ast::op_not_equal: current->op(op_neq); break; | |
261 | case ast::op_less: current->op(op_lt); break; | |
262 | case ast::op_less_equal: current->op(op_lte); break; | |
263 | case ast::op_greater: current->op(op_gt); break; | |
264 | case ast::op_greater_equal: current->op(op_gte); break; | |
265 | ||
266 | case ast::op_and: current->op(op_and); break; | |
267 | case ast::op_or: current->op(op_or); break; | |
268 | default: BOOST_ASSERT(0); return false; | |
269 | } | |
270 | return true; | |
271 | } | |
272 | ||
273 | bool compiler::operator()(ast::unary const& x) | |
274 | { | |
275 | BOOST_ASSERT(current != 0); | |
276 | if (!boost::apply_visitor(*this, x.operand_)) | |
277 | return false; | |
278 | switch (x.operator_) | |
279 | { | |
280 | case ast::op_negative: current->op(op_neg); break; | |
281 | case ast::op_not: current->op(op_not); break; | |
282 | case ast::op_positive: break; | |
283 | default: BOOST_ASSERT(0); return false; | |
284 | } | |
285 | return true; | |
286 | } | |
287 | ||
288 | bool compiler::operator()(ast::function_call const& x) | |
289 | { | |
290 | BOOST_ASSERT(current != 0); | |
291 | ||
292 | if (functions.find(x.function_name.name) == functions.end()) | |
293 | { | |
294 | error_handler(x.function_name.id, "Function not found: " + x.function_name.name); | |
295 | return false; | |
296 | } | |
297 | ||
298 | boost::shared_ptr<code_gen::function> p = functions[x.function_name.name]; | |
299 | ||
300 | if (p->nargs() != x.args.size()) | |
301 | { | |
302 | error_handler(x.function_name.id, "Wrong number of arguments: " + x.function_name.name); | |
303 | return false; | |
304 | } | |
305 | ||
306 | BOOST_FOREACH(ast::expression const& expr, x.args) | |
307 | { | |
308 | if (!(*this)(expr)) | |
309 | return false; | |
310 | } | |
311 | ||
312 | current->op( | |
313 | op_call, | |
314 | p->nargs(), | |
315 | p->get_address()); | |
316 | current->link_to(x.function_name.name, p->get_address()); | |
317 | ||
318 | return true; | |
319 | } | |
320 | ||
321 | bool compiler::operator()(ast::expression const& x) | |
322 | { | |
323 | BOOST_ASSERT(current != 0); | |
324 | if (!boost::apply_visitor(*this, x.first)) | |
325 | return false; | |
326 | BOOST_FOREACH(ast::operation const& oper, x.rest) | |
327 | { | |
328 | if (!(*this)(oper)) | |
329 | return false; | |
330 | } | |
331 | return true; | |
332 | } | |
333 | ||
334 | bool compiler::operator()(ast::assignment const& x) | |
335 | { | |
336 | BOOST_ASSERT(current != 0); | |
337 | if (!(*this)(x.rhs)) | |
338 | return false; | |
339 | int const* p = current->find_var(x.lhs.name); | |
340 | if (p == 0) | |
341 | { | |
342 | error_handler(x.lhs.id, "Undeclared variable: " + x.lhs.name); | |
343 | return false; | |
344 | } | |
345 | current->op(op_store, *p); | |
346 | return true; | |
347 | } | |
348 | ||
349 | bool compiler::operator()(ast::variable_declaration const& x) | |
350 | { | |
351 | BOOST_ASSERT(current != 0); | |
352 | int const* p = current->find_var(x.lhs.name); | |
353 | if (p != 0) | |
354 | { | |
355 | error_handler(x.lhs.id, "Duplicate variable: " + x.lhs.name); | |
356 | return false; | |
357 | } | |
358 | if (x.rhs) // if there's an RHS initializer | |
359 | { | |
360 | bool r = (*this)(*x.rhs); | |
361 | if (r) // don't add the variable if the RHS fails | |
362 | { | |
363 | current->add_var(x.lhs.name); | |
364 | current->op(op_store, *current->find_var(x.lhs.name)); | |
365 | } | |
366 | return r; | |
367 | } | |
368 | else | |
369 | { | |
370 | current->add_var(x.lhs.name); | |
371 | } | |
372 | return true; | |
373 | } | |
374 | ||
375 | bool compiler::operator()(ast::statement const& x) | |
376 | { | |
377 | BOOST_ASSERT(current != 0); | |
378 | return boost::apply_visitor(*this, x); | |
379 | } | |
380 | ||
381 | bool compiler::operator()(ast::statement_list const& x) | |
382 | { | |
383 | BOOST_ASSERT(current != 0); | |
384 | BOOST_FOREACH(ast::statement const& s, x) | |
385 | { | |
386 | if (!(*this)(s)) | |
387 | return false; | |
388 | } | |
389 | return true; | |
390 | } | |
391 | ||
392 | bool compiler::operator()(ast::if_statement const& x) | |
393 | { | |
394 | BOOST_ASSERT(current != 0); | |
395 | if (!(*this)(x.condition)) | |
396 | return false; | |
397 | current->op(op_jump_if, 0); // we shall fill this (0) in later | |
398 | std::size_t skip = current->size()-1; // mark its position | |
399 | if (!(*this)(x.then)) | |
400 | return false; | |
401 | (*current)[skip] = current->size()-skip; // now we know where to jump to (after the if branch) | |
402 | ||
92f5a8d4 | 403 | if (x.else_) // We got an else |
7c673cae FG |
404 | { |
405 | (*current)[skip] += 2; // adjust for the "else" jump | |
406 | current->op(op_jump, 0); // we shall fill this (0) in later | |
407 | std::size_t exit = current->size()-1; // mark its position | |
408 | if (!(*this)(*x.else_)) | |
409 | return false; | |
410 | (*current)[exit] = current->size()-exit;// now we know where to jump to (after the else branch) | |
411 | } | |
412 | ||
413 | return true; | |
414 | } | |
415 | ||
416 | bool compiler::operator()(ast::while_statement const& x) | |
417 | { | |
418 | BOOST_ASSERT(current != 0); | |
419 | std::size_t loop = current->size(); // mark our position | |
420 | if (!(*this)(x.condition)) | |
421 | return false; | |
422 | current->op(op_jump_if, 0); // we shall fill this (0) in later | |
423 | std::size_t exit = current->size()-1; // mark its position | |
424 | if (!(*this)(x.body)) | |
425 | return false; | |
426 | current->op(op_jump, | |
427 | int(loop-1) - int(current->size())); // loop back | |
428 | (*current)[exit] = current->size()-exit; // now we know where to jump to (to exit the loop) | |
429 | return true; | |
430 | } | |
431 | ||
432 | bool compiler::operator()(ast::return_statement const& x) | |
433 | { | |
434 | if (void_return) | |
435 | { | |
436 | if (x.expr) | |
437 | { | |
438 | error_handler(x.id, "'void' function returning a value: "); | |
439 | return false; | |
440 | } | |
441 | } | |
442 | else | |
443 | { | |
444 | if (!x.expr) | |
445 | { | |
446 | error_handler(x.id, current_function_name + " function must return a value: "); | |
447 | return false; | |
448 | } | |
449 | } | |
450 | ||
451 | if (x.expr) | |
452 | { | |
453 | if (!(*this)(*x.expr)) | |
454 | return false; | |
455 | } | |
456 | current->op(op_return); | |
457 | return true; | |
458 | } | |
459 | ||
460 | bool compiler::operator()(ast::function const& x) | |
461 | { | |
462 | void_return = x.return_type == "void"; | |
463 | if (functions.find(x.function_name.name) != functions.end()) | |
464 | { | |
465 | error_handler(x.function_name.id, "Duplicate function: " + x.function_name.name); | |
466 | return false; | |
467 | } | |
468 | boost::shared_ptr<code_gen::function>& p = functions[x.function_name.name]; | |
469 | p.reset(new code_gen::function(code, x.args.size())); | |
470 | current = p.get(); | |
471 | current_function_name = x.function_name.name; | |
472 | ||
473 | // op_stk_adj 0 for now. we'll know how many variables | |
474 | // we'll have later and add them | |
475 | current->op(op_stk_adj, 0); | |
476 | BOOST_FOREACH(ast::identifier const& arg, x.args) | |
477 | { | |
478 | current->add_var(arg.name); | |
479 | } | |
480 | ||
481 | if (!(*this)(x.body)) | |
482 | return false; | |
483 | (*current)[1] = current->nvars(); // now store the actual number of variables | |
484 | // this includes the arguments | |
485 | return true; | |
486 | } | |
487 | ||
488 | bool compiler::operator()(ast::function_list const& x) | |
489 | { | |
490 | // Jump to the main function | |
491 | code.push_back(op_jump); | |
492 | code.push_back(0); // we will fill this in later when we finish compiling | |
493 | // and we know where the main function is | |
494 | ||
495 | BOOST_FOREACH(ast::function const& f, x) | |
496 | { | |
497 | if (!(*this)(f)) | |
498 | { | |
499 | code.clear(); | |
500 | return false; | |
501 | } | |
502 | } | |
503 | // find the main function | |
504 | boost::shared_ptr<code_gen::function> p = | |
505 | find_function("main"); | |
506 | ||
507 | if (!p) // main function not found | |
508 | { | |
509 | std::cerr << "Error: main function not defined" << std::endl; | |
510 | return false; | |
511 | } | |
512 | code[1] = p->get_address()-1; // jump to this (main function) address | |
513 | ||
514 | return true; | |
515 | } | |
516 | ||
517 | void compiler::print_assembler() const | |
518 | { | |
519 | typedef std::pair<std::string, boost::shared_ptr<code_gen::function> > pair; | |
520 | BOOST_FOREACH(pair const& p, functions) | |
521 | { | |
522 | std::cout << ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;" << std::endl; | |
523 | std::cout << p.second->get_address() << ": function " << p.first << std::endl; | |
524 | p.second->print_assembler(); | |
525 | } | |
526 | } | |
527 | ||
528 | boost::shared_ptr<code_gen::function> | |
529 | compiler::find_function(std::string const& name) const | |
530 | { | |
531 | function_table::const_iterator i = functions.find(name); | |
532 | if (i == functions.end()) | |
533 | return boost::shared_ptr<code_gen::function>(); | |
534 | else | |
535 | return i->second; | |
536 | } | |
537 | }} | |
538 |