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 { op(int a)17 void function::op(int a) 18 { 19 code.push_back(a); 20 size_ += 1; 21 } 22 op(int a,int b)23 void function::op(int a, int b) 24 { 25 code.push_back(a); 26 code.push_back(b); 27 size_ += 2; 28 } 29 op(int a,int b,int c)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 find_var(std::string const & name) const38 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 add_var(std::string const & name)46 void function::add_var(std::string const& name) 47 { 48 std::size_t n = variables.size(); 49 variables[name] = n; 50 } 51 link_to(std::string const & name,std::size_t address)52 void function::link_to(std::string const& name, std::size_t address) 53 { 54 function_calls[address] = name; 55 } 56 print_assembler() const57 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 "; 138 line += locals[*pc++]; 139 break; 140 141 case op_store: 142 line += " op_store "; 143 line += locals[*pc++]; 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 operator ()(unsigned int x)220 bool compiler::operator()(unsigned int x) 221 { 222 BOOST_ASSERT(current != 0); 223 current->op(op_int, x); 224 return true; 225 } 226 operator ()(bool x)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 operator ()(ast::identifier const & x)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 operator ()(ast::operation const & x)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 operator ()(ast::unary const & x)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 operator ()(ast::function_call const & x)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 operator ()(ast::expression const & x)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 operator ()(ast::assignment const & x)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 operator ()(ast::variable_declaration const & x)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 operator ()(ast::statement const & x)375 bool compiler::operator()(ast::statement const& x) 376 { 377 BOOST_ASSERT(current != 0); 378 return boost::apply_visitor(*this, x); 379 } 380 operator ()(ast::statement_list const & x)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 operator ()(ast::if_statement const & x)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 403 if (x.else_) // We got an else 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 operator ()(ast::while_statement const & x)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 operator ()(ast::return_statement const & x)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 operator ()(ast::function const & x)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 operator ()(ast::function_list const & x)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 print_assembler() const517 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> find_function(std::string const & name) const529 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 539