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 "config.hpp" 8 #include "compiler.hpp" 9 #include "annotation.hpp" 10 #include "vm.hpp" 11 12 #include <boost/foreach.hpp> 13 #include <boost/variant/apply_visitor.hpp> 14 #include <boost/range/adaptor/transformed.hpp> 15 #include <boost/assert.hpp> 16 #include <set> 17 18 namespace client { namespace code_gen 19 { value()20 value::value() 21 : v(0), 22 is_lvalue_(false), 23 builder(0) 24 {} 25 value(llvm::Value * v,bool is_lvalue_,llvm::IRBuilder<> * builder)26 value::value( 27 llvm::Value* v, 28 bool is_lvalue_, 29 llvm::IRBuilder<>* builder) 30 : v(v), 31 is_lvalue_(is_lvalue_), 32 builder(builder) 33 {} 34 value(value const & rhs)35 value::value(value const& rhs) 36 : v(rhs.v), 37 is_lvalue_(rhs.is_lvalue_), 38 builder(rhs.builder) 39 {} 40 is_lvalue() const41 bool value::is_lvalue() const 42 { 43 return is_lvalue_; 44 } 45 is_valid() const46 bool value::is_valid() const 47 { 48 return v != 0; 49 } 50 operator bool() const51 value::operator bool() const 52 { 53 return v != 0; 54 } 55 name(char const * id)56 void value::name(char const* id) 57 { 58 v->setName(id); 59 } 60 name(std::string const & id)61 void value::name(std::string const& id) 62 { 63 v->setName(id); 64 } 65 operator llvm::Value*() const66 value::operator llvm::Value*() const 67 { 68 if (is_lvalue_) 69 { 70 BOOST_ASSERT(builder != 0); 71 return builder->CreateLoad(v, v->getName()); 72 } 73 return v; 74 } 75 operator =(value const & rhs)76 value& value::operator=(value const& rhs) 77 { 78 v = rhs.v; 79 is_lvalue_ = rhs.is_lvalue_; 80 builder = rhs.builder; 81 return *this; 82 } 83 assign(value const & rhs)84 value& value::assign(value const& rhs) 85 { 86 BOOST_ASSERT(is_lvalue()); 87 BOOST_ASSERT(builder != 0); 88 builder->CreateStore(rhs, v); 89 return *this; 90 } 91 operator -(value a)92 value operator-(value a) 93 { 94 BOOST_ASSERT(a.builder != 0); 95 return value( 96 a.builder->CreateNeg(a, "neg_tmp"), 97 false, a.builder 98 ); 99 } 100 operator !(value a)101 value operator!(value a) 102 { 103 BOOST_ASSERT(a.builder != 0); 104 return value( 105 a.builder->CreateNot(a, "not_tmp"), 106 false, a.builder 107 ); 108 } 109 operator +(value a,value b)110 value operator+(value a, value b) 111 { 112 BOOST_ASSERT(a.builder != 0); 113 return value( 114 a.builder->CreateAdd(a, b, "add_tmp"), 115 false, a.builder 116 ); 117 } 118 operator -(value a,value b)119 value operator-(value a, value b) 120 { 121 BOOST_ASSERT(a.builder != 0); 122 return value( 123 a.builder->CreateSub(a, b, "sub_tmp"), 124 false, a.builder 125 ); 126 } 127 operator *(value a,value b)128 value operator*(value a, value b) 129 { 130 BOOST_ASSERT(a.builder != 0); 131 return value( 132 a.builder->CreateMul(a, b, "mul_tmp"), 133 false, a.builder 134 ); 135 } 136 operator /(value a,value b)137 value operator/(value a, value b) 138 { 139 BOOST_ASSERT(a.builder != 0); 140 return value( 141 a.builder->CreateSDiv(a, b, "div_tmp"), 142 false, a.builder 143 ); 144 } 145 operator %(value a,value b)146 value operator%(value a, value b) 147 { 148 BOOST_ASSERT(a.builder != 0); 149 return value( 150 a.builder->CreateSRem(a, b, "mod_tmp"), 151 false, a.builder 152 ); 153 } 154 operator &(value a,value b)155 value operator&(value a, value b) 156 { 157 BOOST_ASSERT(a.builder != 0); 158 return value( 159 a.builder->CreateAnd(a, b, "and_tmp"), 160 false, a.builder 161 ); 162 } 163 operator |(value a,value b)164 value operator|(value a, value b) 165 { 166 BOOST_ASSERT(a.builder != 0); 167 return value( 168 a.builder->CreateOr(a, b, "or_tmp"), 169 false, a.builder 170 ); 171 } 172 operator ^(value a,value b)173 value operator^(value a, value b) 174 { 175 BOOST_ASSERT(a.builder != 0); 176 return value( 177 a.builder->CreateXor(a, b, "xor_tmp"), 178 false, a.builder 179 ); 180 } 181 operator <<(value a,value b)182 value operator<<(value a, value b) 183 { 184 BOOST_ASSERT(a.builder != 0); 185 return value( 186 a.builder->CreateShl(a, b, "shl_tmp"), 187 false, a.builder 188 ); 189 } 190 operator >>(value a,value b)191 value operator>>(value a, value b) 192 { 193 BOOST_ASSERT(a.builder != 0); 194 return value( 195 a.builder->CreateLShr(a, b, "shr_tmp"), 196 false, a.builder 197 ); 198 } 199 operator ==(value a,value b)200 value operator==(value a, value b) 201 { 202 BOOST_ASSERT(a.builder != 0); 203 return value( 204 a.builder->CreateICmpEQ(a, b, "eq_tmp"), 205 false, a.builder 206 ); 207 } 208 operator !=(value a,value b)209 value operator!=(value a, value b) 210 { 211 BOOST_ASSERT(a.builder != 0); 212 return value( 213 a.builder->CreateICmpNE(a, b, "ne_tmp"), 214 false, a.builder 215 ); 216 } 217 operator <(value a,value b)218 value operator<(value a, value b) 219 { 220 BOOST_ASSERT(a.builder != 0); 221 return value( 222 a.builder->CreateICmpSLT(a, b, "slt_tmp"), 223 false, a.builder 224 ); 225 } 226 operator <=(value a,value b)227 value operator<=(value a, value b) 228 { 229 BOOST_ASSERT(a.builder != 0); 230 return value( 231 a.builder->CreateICmpSLE(a, b, "sle_tmp"), 232 false, a.builder 233 ); 234 } 235 operator >(value a,value b)236 value operator>(value a, value b) 237 { 238 BOOST_ASSERT(a.builder != 0); 239 return value( 240 a.builder->CreateICmpSGT(a, b, "sgt_tmp"), 241 false, a.builder 242 ); 243 } 244 operator >=(value a,value b)245 value operator>=(value a, value b) 246 { 247 BOOST_ASSERT(a.builder != 0); 248 return value( 249 a.builder->CreateICmpSGE(a, b, "sge_tmp"), 250 false, a.builder 251 ); 252 } 253 254 struct function::to_value 255 { 256 typedef value result_type; 257 llvm_compiler* c; 258 to_valueclient::code_gen::function::to_value259 to_value(llvm_compiler* c = 0) : c(c) {} 260 operator ()client::code_gen::function::to_value261 value operator()(llvm::Value& v) const 262 { 263 return c->val(&v); 264 } 265 }; 266 has_terminator() const267 bool basic_block::has_terminator() const 268 { 269 return b->getTerminator() != 0; 270 } 271 is_valid() const272 bool basic_block::is_valid() const 273 { 274 return b != 0; 275 } 276 operator llvm::Function*() const277 function::operator llvm::Function*() const 278 { 279 return f; 280 } 281 arg_size() const282 std::size_t function::arg_size() const 283 { 284 return f->arg_size(); 285 } 286 add(basic_block const & b)287 void function::add(basic_block const& b) 288 { 289 f->getBasicBlockList().push_back(b); 290 } 291 erase_from_parent()292 void function::erase_from_parent() 293 { 294 f->eraseFromParent(); 295 } 296 last_block()297 basic_block function::last_block() 298 { 299 return &f->getBasicBlockList().back(); 300 } 301 empty() const302 bool function::empty() const 303 { 304 return f->empty(); 305 } 306 name() const307 std::string function::name() const 308 { 309 return f->getName(); 310 } 311 args() const312 function::arg_range function::args() const 313 { 314 BOOST_ASSERT(c != 0); 315 arg_val_iterator first(f->arg_begin(), to_value()); 316 arg_val_iterator last(f->arg_end(), to_value()); 317 return arg_range(first, last); 318 } 319 is_valid() const320 bool function::is_valid() const 321 { 322 return f != 0; 323 } 324 verify() const325 void function::verify() const 326 { 327 llvm::verifyFunction(*f); 328 } 329 val(unsigned int x)330 value llvm_compiler::val(unsigned int x) 331 { 332 return value( 333 llvm::ConstantInt::get(context(), llvm::APInt(int_size, x)), 334 false, &llvm_builder); 335 } 336 val(int x)337 value llvm_compiler::val(int x) 338 { 339 return value( 340 llvm::ConstantInt::get(context(), llvm::APInt(int_size, x)), 341 false, &llvm_builder); 342 } 343 val(bool x)344 value llvm_compiler::val(bool x) 345 { 346 return value( 347 llvm::ConstantInt::get(context(), llvm::APInt(1, x)), 348 false, &llvm_builder); 349 } 350 val(llvm::Value * v)351 value llvm_compiler::val(llvm::Value* v) 352 { 353 return value(v, false, &llvm_builder); 354 } 355 356 namespace 357 { 358 // Create an alloca instruction in the entry block of 359 // the function. This is used for mutable variables etc. 360 llvm::AllocaInst* make_entry_block_alloca(llvm::Function * f,char const * name,llvm::LLVMContext & context)361 make_entry_block_alloca( 362 llvm::Function* f, 363 char const* name, 364 llvm::LLVMContext& context) 365 { 366 llvm::IRBuilder<> builder( 367 &f->getEntryBlock(), 368 f->getEntryBlock().begin()); 369 370 return builder.CreateAlloca( 371 llvm::Type::getIntNTy(context, int_size), 0, name); 372 } 373 } 374 var(char const * name)375 value llvm_compiler::var(char const* name) 376 { 377 llvm::Function* f = llvm_builder.GetInsertBlock()->getParent(); 378 llvm::IRBuilder<> builder( 379 &f->getEntryBlock(), 380 f->getEntryBlock().begin()); 381 382 llvm::AllocaInst* alloca = builder.CreateAlloca( 383 llvm::Type::getIntNTy(context(), int_size), 0, name); 384 385 return value(alloca, true, &llvm_builder); 386 } 387 388 struct value::to_llvm_value 389 { 390 typedef llvm::Value* result_type; operator ()client::code_gen::value::to_llvm_value391 llvm::Value* operator()(value const& x) const 392 { 393 return x; 394 } 395 }; 396 397 template <typename C> call_impl(function callee,C const & args_)398 llvm::Value* llvm_compiler::call_impl( 399 function callee, 400 C const& args_) 401 { 402 // Sigh. LLVM requires CreateCall arguments to be random access. 403 // It would have been better if it can accept forward iterators. 404 // I guess it needs the arguments to be in contiguous memory. 405 // So, we have to put the args into a temporary std::vector. 406 std::vector<llvm::Value*> args( 407 args_.begin(), args_.end()); 408 409 // Check the args for null values. We can't have null values. 410 // Return 0 if we find one to flag error. 411 BOOST_FOREACH(llvm::Value* arg, args) 412 { 413 if (arg == 0) 414 return 0; 415 } 416 417 return llvm_builder.CreateCall( 418 callee, args.begin(), args.end(), "call_tmp"); 419 } 420 421 template <typename Container> call(function callee,Container const & args)422 value llvm_compiler::call( 423 function callee, 424 Container const& args) 425 { 426 llvm::Value* call = call_impl( 427 callee, 428 args | boost::adaptors::transformed(value::to_llvm_value())); 429 430 if (call == 0) 431 return val(); 432 return value(call, false, &llvm_builder); 433 } 434 get_function(char const * name)435 function llvm_compiler::get_function(char const* name) 436 { 437 return function(vm.module()->getFunction(name), this); 438 } 439 get_current_function()440 function llvm_compiler::get_current_function() 441 { 442 // get the current function 443 return function(llvm_builder.GetInsertBlock()->getParent(), this); 444 } 445 declare_function(bool void_return,std::string const & name,std::size_t nargs)446 function llvm_compiler::declare_function( 447 bool void_return 448 , std::string const& name 449 , std::size_t nargs) 450 { 451 llvm::Type const* int_type = 452 llvm::Type::getIntNTy(context(), int_size); 453 llvm::Type const* void_type = llvm::Type::getVoidTy(context()); 454 455 std::vector<llvm::Type const*> ints(nargs, int_type); 456 llvm::Type const* return_type = void_return ? void_type : int_type; 457 458 llvm::FunctionType* function_type = 459 llvm::FunctionType::get(void_return ? void_type : int_type, ints, false); 460 461 return function(llvm::Function::Create( 462 function_type, llvm::Function::ExternalLinkage, 463 name, vm.module()), this); 464 } 465 make_basic_block(char const * name,function parent,basic_block before)466 basic_block llvm_compiler::make_basic_block( 467 char const* name 468 , function parent 469 , basic_block before) 470 { 471 return llvm::BasicBlock::Create(context(), name, parent, before); 472 } 473 var(std::string const & name)474 value llvm_compiler::var(std::string const& name) 475 { 476 return var(name.c_str()); 477 } 478 get_function(std::string const & name)479 function llvm_compiler::get_function(std::string const& name) 480 { 481 return get_function(name.c_str()); 482 } 483 get_insert_block()484 basic_block llvm_compiler::get_insert_block() 485 { 486 return llvm_builder.GetInsertBlock(); 487 } 488 set_insert_point(basic_block b)489 void llvm_compiler::set_insert_point(basic_block b) 490 { 491 llvm_builder.SetInsertPoint(b); 492 } 493 conditional_branch(value cond,basic_block true_br,basic_block false_br)494 void llvm_compiler::conditional_branch( 495 value cond, basic_block true_br, basic_block false_br) 496 { 497 llvm_builder.CreateCondBr(cond, true_br, false_br); 498 } 499 branch(basic_block b)500 void llvm_compiler::branch(basic_block b) 501 { 502 llvm_builder.CreateBr(b); 503 } 504 return_()505 void llvm_compiler::return_() 506 { 507 llvm_builder.CreateRetVoid(); 508 } 509 return_(value v)510 void llvm_compiler::return_(value v) 511 { 512 llvm_builder.CreateRet(v); 513 } 514 optimize_function(function f)515 void llvm_compiler::optimize_function(function f) 516 { 517 // Optimize the function. 518 fpm.run(*f); 519 } 520 init_fpm()521 void llvm_compiler::init_fpm() 522 { 523 // Set up the optimizer pipeline. Start with registering info about how the 524 // target lays out data structures. 525 fpm.add(new llvm::TargetData(*vm.execution_engine()->getTargetData())); 526 // Provide basic AliasAnalysis support for GVN. 527 fpm.add(llvm::createBasicAliasAnalysisPass()); 528 // Promote allocas to registers. 529 fpm.add(llvm::createPromoteMemoryToRegisterPass()); 530 // Do simple "peephole" optimizations and bit-twiddling optzns. 531 fpm.add(llvm::createInstructionCombiningPass()); 532 // Reassociate expressions. 533 fpm.add(llvm::createReassociatePass()); 534 // Eliminate Common SubExpressions. 535 fpm.add(llvm::createGVNPass()); 536 // Simplify the control flow graph (deleting unreachable blocks, etc). 537 fpm.add(llvm::createCFGSimplificationPass()); 538 539 fpm.doInitialization(); 540 } 541 operator ()(unsigned int x)542 value compiler::operator()(unsigned int x) 543 { 544 return val(x); 545 } 546 operator ()(bool x)547 value compiler::operator()(bool x) 548 { 549 return val(x); 550 } 551 operator ()(ast::primary_expr const & x)552 value compiler::operator()(ast::primary_expr const& x) 553 { 554 return boost::apply_visitor(*this, x.get()); 555 } 556 operator ()(ast::identifier const & x)557 value compiler::operator()(ast::identifier const& x) 558 { 559 // Look this variable up in the function. 560 if (locals.find(x.name) == locals.end()) 561 { 562 error_handler(x.id, "Undeclared variable: " + x.name); 563 return val(); 564 } 565 return locals[x.name]; 566 } 567 operator ()(ast::unary_expr const & x)568 value compiler::operator()(ast::unary_expr const& x) 569 { 570 value operand = boost::apply_visitor(*this, x.operand_); 571 if (!operand.is_valid()) 572 return val(); 573 574 switch (x.operator_) 575 { 576 case token_ids::compl_: return operand ^ val(-1); 577 case token_ids::minus: return -operand; 578 case token_ids::not_: return !operand; 579 case token_ids::plus: return operand; 580 case token_ids::plus_plus: 581 { 582 if (!operand.is_lvalue()) 583 { 584 error_handler(x.id, "++ needs an var"); 585 return val(); 586 } 587 588 value r = operand + val(1); 589 operand.assign(r); 590 return operand; 591 } 592 case token_ids::minus_minus: 593 { 594 if (!operand.is_lvalue()) 595 { 596 error_handler(x.id, "-- needs an var"); 597 return val(); 598 } 599 600 value r = operand - val(1); 601 operand.assign(r); 602 return operand; 603 } 604 default: 605 BOOST_ASSERT(0); 606 return val(); 607 } 608 } 609 610 namespace 611 { 612 struct compile_args 613 { 614 compiler& c; compile_argsclient::code_gen::__anoncb5fad930211::compile_args615 compile_args(compiler& c) : c(c) {} 616 617 typedef value result_type; operator ()client::code_gen::__anoncb5fad930211::compile_args618 value operator()(ast::expression const& expr) const 619 { 620 return c(expr); 621 } 622 }; 623 } 624 operator ()(ast::function_call const & x)625 value compiler::operator()(ast::function_call const& x) 626 { 627 function callee = get_function(x.function_name.name); 628 if (!callee.is_valid()) 629 { 630 error_handler(x.function_name.id, 631 "Function not found: " + x.function_name.name); 632 return val(); 633 } 634 635 if (callee.arg_size() != x.args.size()) 636 { 637 error_handler(x.function_name.id, 638 "Wrong number of arguments: " + x.function_name.name); 639 return val(); 640 } 641 642 return call(callee, 643 x.args | boost::adaptors::transformed(compile_args(*this))); 644 } 645 646 namespace 647 { 648 int precedence[] = { 649 // precedence 1 650 1, // op_comma 651 652 // precedence 2 653 2, // op_assign 654 2, // op_plus_assign 655 2, // op_minus_assign 656 2, // op_times_assign 657 2, // op_divide_assign 658 2, // op_mod_assign 659 2, // op_bit_and_assign 660 2, // op_bit_xor_assign 661 2, // op_bitor_assign 662 2, // op_shift_left_assign 663 2, // op_shift_right_assign 664 665 // precedence 3 666 3, // op_logical_or 667 668 // precedence 4 669 4, // op_logical_and 670 671 // precedence 5 672 5, // op_bit_or 673 674 // precedence 6 675 6, // op_bit_xor 676 677 // precedence 7 678 7, // op_bit_and 679 680 // precedence 8 681 8, // op_equal 682 8, // op_not_equal 683 684 // precedence 9 685 9, // op_less 686 9, // op_less_equal 687 9, // op_greater 688 9, // op_greater_equal 689 690 // precedence 10 691 10, // op_shift_left 692 10, // op_shift_right 693 694 // precedence 11 695 11, // op_plus 696 11, // op_minus 697 698 // precedence 12 699 12, // op_times 700 12, // op_divide 701 12 // op_mod 702 }; 703 } 704 precedence_of(token_ids::type op)705 inline int precedence_of(token_ids::type op) 706 { 707 return precedence[op & 0xFF]; 708 } 709 compile_binary_expression(value lhs,value rhs,token_ids::type op)710 value compiler::compile_binary_expression( 711 value lhs, value rhs, token_ids::type op) 712 { 713 switch (op) 714 { 715 case token_ids::plus: return lhs + rhs; 716 case token_ids::minus: return lhs - rhs; 717 case token_ids::times: return lhs * rhs; 718 case token_ids::divide: return lhs / rhs; 719 case token_ids::mod: return lhs % rhs; 720 721 case token_ids::logical_or: 722 case token_ids::bit_or: return lhs | rhs; 723 724 case token_ids::logical_and: 725 case token_ids::bit_and: return lhs & rhs; 726 727 case token_ids::bit_xor: return lhs ^ rhs; 728 case token_ids::shift_left: return lhs << rhs; 729 case token_ids::shift_right: return lhs >> rhs; 730 731 case token_ids::equal: return lhs == rhs; 732 case token_ids::not_equal: return lhs != rhs; 733 case token_ids::less: return lhs < rhs; 734 case token_ids::less_equal: return lhs <= rhs; 735 case token_ids::greater: return lhs > rhs; 736 case token_ids::greater_equal: return lhs >= rhs; 737 738 default: BOOST_ASSERT(0); return val(); 739 } 740 } 741 742 // The Shunting-yard algorithm compile_expression(int min_precedence,value lhs,std::list<ast::operation>::const_iterator & rest_begin,std::list<ast::operation>::const_iterator rest_end)743 value compiler::compile_expression( 744 int min_precedence, 745 value lhs, 746 std::list<ast::operation>::const_iterator& rest_begin, 747 std::list<ast::operation>::const_iterator rest_end) 748 { 749 while ((rest_begin != rest_end) && 750 (precedence_of(rest_begin->operator_) >= min_precedence)) 751 { 752 token_ids::type op = rest_begin->operator_; 753 value rhs = boost::apply_visitor(*this, rest_begin->operand_); 754 if (!rhs.is_valid()) 755 return val(); 756 ++rest_begin; 757 758 while ((rest_begin != rest_end) && 759 (precedence_of(rest_begin->operator_) > precedence_of(op))) 760 { 761 token_ids::type next_op = rest_begin->operator_; 762 rhs = compile_expression( 763 precedence_of(next_op), rhs, rest_begin, rest_end); 764 } 765 766 lhs = compile_binary_expression(lhs, rhs, op); 767 } 768 return lhs; 769 } 770 operator ()(ast::expression const & x)771 value compiler::operator()(ast::expression const& x) 772 { 773 value lhs = boost::apply_visitor(*this, x.first); 774 if (!lhs.is_valid()) 775 return val(); 776 std::list<ast::operation>::const_iterator rest_begin = x.rest.begin(); 777 return compile_expression(0, lhs, rest_begin, x.rest.end()); 778 } 779 operator ()(ast::assignment const & x)780 value compiler::operator()(ast::assignment const& x) 781 { 782 if (locals.find(x.lhs.name) == locals.end()) 783 { 784 error_handler(x.lhs.id, "Undeclared variable: " + x.lhs.name); 785 return val(); 786 } 787 788 value lhs = locals[x.lhs.name]; 789 value rhs = (*this)(x.rhs); 790 if (!rhs.is_valid()) 791 return val(); 792 793 if (x.operator_ == token_ids::assign) 794 { 795 lhs.assign(rhs); 796 return lhs; 797 } 798 799 value result; 800 switch (x.operator_) 801 { 802 case token_ids::plus_assign: result = lhs + rhs; break; 803 case token_ids::minus_assign: result = lhs - rhs; break; 804 case token_ids::times_assign: result = lhs * rhs; break; 805 case token_ids::divide_assign: result = lhs / rhs; break; 806 case token_ids::mod_assign: result = lhs % rhs; break; 807 case token_ids::bit_and_assign: result = lhs & rhs; break; 808 case token_ids::bit_xor_assign: result = lhs ^ rhs; break; 809 case token_ids::bit_or_assign: result = lhs | rhs; break; 810 case token_ids::shift_left_assign: result = lhs << rhs; break; 811 case token_ids::shift_right_assign: result = lhs >> rhs; break; 812 default: BOOST_ASSERT(0); return val(); 813 } 814 815 lhs.assign(result); 816 return lhs; 817 } 818 operator ()(ast::variable_declaration const & x)819 bool compiler::operator()(ast::variable_declaration const& x) 820 { 821 if (locals.find(x.lhs.name) != locals.end()) 822 { 823 error_handler(x.lhs.id, "Duplicate variable: " + x.lhs.name); 824 return false; 825 } 826 827 value init; 828 std::string const& name = x.lhs.name; 829 830 if (x.rhs) // if there's an RHS initializer 831 { 832 init = (*this)(*x.rhs); 833 if (!init.is_valid()) // don't add the variable if the RHS fails 834 return false; 835 } 836 837 value var_ = var(name.c_str()); 838 if (init.is_valid()) 839 var_.assign(init); 840 841 // Remember this binding. 842 locals[name] = var_; 843 return true; 844 } 845 846 struct compiler::statement_compiler : compiler 847 { 848 typedef bool result_type; 849 }; 850 as_statement()851 compiler::statement_compiler& compiler::as_statement() 852 { 853 return *static_cast<statement_compiler*>(this); 854 } 855 operator ()(ast::statement const & x)856 bool compiler::operator()(ast::statement const& x) 857 { 858 if (boost::get<ast::nil>(&x) != 0) // empty statement 859 return true; 860 return boost::apply_visitor(as_statement(), x); 861 } 862 operator ()(ast::statement_list const & x)863 bool compiler::operator()(ast::statement_list const& x) 864 { 865 BOOST_FOREACH(ast::statement const& s, x) 866 { 867 if (!(*this)(s)) 868 return false; 869 } 870 return true; 871 } 872 operator ()(ast::if_statement const & x)873 bool compiler::operator()(ast::if_statement const& x) 874 { 875 value condition = (*this)(x.condition); 876 if (!condition.is_valid()) 877 return false; 878 879 function f = get_current_function(); 880 881 // Create blocks for the then and else cases. Insert the 'then' block at the 882 // end of the function. 883 basic_block then_block = make_basic_block("if.then", f); 884 basic_block else_block; 885 basic_block exit_block; 886 887 if (x.else_) 888 { 889 else_block = make_basic_block("if.else"); 890 conditional_branch(condition, then_block, else_block); 891 } 892 else 893 { 894 exit_block = make_basic_block("if.end"); 895 conditional_branch(condition, then_block, exit_block); 896 } 897 898 // Emit then value. 899 set_insert_point(then_block); 900 if (!(*this)(x.then)) 901 return false; 902 if (!then_block.has_terminator()) 903 { 904 if (!exit_block.is_valid()) 905 exit_block = make_basic_block("if.end"); 906 branch(exit_block); 907 } 908 // Codegen of 'then' can change the current block, update then_block 909 then_block = get_insert_block(); 910 911 if (x.else_) 912 { 913 // Emit else block. 914 f.add(else_block); 915 set_insert_point(else_block); 916 if (!(*this)(*x.else_)) 917 return false; 918 if (!else_block.has_terminator()) 919 { 920 if (!exit_block.is_valid()) 921 exit_block = make_basic_block("if.end"); 922 branch(exit_block); 923 } 924 // Codegen of 'else' can change the current block, update else_block 925 else_block = get_insert_block(); 926 } 927 928 if (exit_block.is_valid()) 929 { 930 // Emit exit block 931 f.add(exit_block); 932 set_insert_point(exit_block); 933 } 934 return true; 935 } 936 operator ()(ast::while_statement const & x)937 bool compiler::operator()(ast::while_statement const& x) 938 { 939 function f = get_current_function(); 940 941 basic_block cond_block = make_basic_block("while.cond", f); 942 basic_block body_block = make_basic_block("while.body"); 943 basic_block exit_block = make_basic_block("while.end"); 944 945 branch(cond_block); 946 set_insert_point(cond_block); 947 value condition = (*this)(x.condition); 948 if (!condition.is_valid()) 949 return false; 950 conditional_branch(condition, body_block, exit_block); 951 f.add(body_block); 952 set_insert_point(body_block); 953 954 if (!(*this)(x.body)) 955 return false; 956 957 if (!body_block.has_terminator()) 958 branch(cond_block); // loop back 959 960 // Emit exit block 961 f.add(exit_block); 962 set_insert_point(exit_block); 963 964 return true; 965 } 966 operator ()(ast::return_statement const & x)967 bool compiler::operator()(ast::return_statement const& x) 968 { 969 if (void_return) 970 { 971 if (x.expr) 972 { 973 error_handler( 974 x.id, "'void' function returning a value: "); 975 return false; 976 } 977 } 978 else 979 { 980 if (!x.expr) 981 { 982 error_handler( 983 x.id, current_function_name 984 + " function must return a value: "); 985 return false; 986 } 987 } 988 989 if (x.expr) 990 { 991 value return_val = (*this)(*x.expr); 992 if (!return_val.is_valid()) 993 return false; 994 return_var.assign(return_val); 995 } 996 997 branch(return_block); 998 return true; 999 } 1000 function_decl(ast::function const & x)1001 function compiler::function_decl(ast::function const& x) 1002 { 1003 void_return = x.return_type == "void"; 1004 current_function_name = x.function_name.name; 1005 1006 function f = 1007 declare_function( 1008 void_return 1009 , current_function_name 1010 , x.args.size()); 1011 1012 // If function conflicted, the function already exixts. If it has a 1013 // body, don't allow redefinition or reextern. 1014 if (f.name() != current_function_name) 1015 { 1016 // Delete the one we just made and get the existing one. 1017 f.erase_from_parent(); 1018 f = get_function(current_function_name); 1019 1020 // If function already has a body, reject this. 1021 if (!f.empty()) 1022 { 1023 error_handler( 1024 x.function_name.id, 1025 "Duplicate function: " + x.function_name.name); 1026 return function(); 1027 } 1028 1029 // If function took a different number of args, reject. 1030 if (f.arg_size() != x.args.size()) 1031 { 1032 error_handler( 1033 x.function_name.id, 1034 "Redefinition of function with different # args: " 1035 + x.function_name.name); 1036 return function(); 1037 } 1038 1039 // Set names for all arguments. 1040 function::arg_range rng = f.args(); 1041 function::arg_range::const_iterator iter = rng.begin(); 1042 BOOST_FOREACH(ast::identifier const& arg, x.args) 1043 { 1044 iter->name(arg.name); 1045 ++iter; 1046 } 1047 } 1048 return f; 1049 } 1050 function_allocas(ast::function const & x,function f)1051 void compiler::function_allocas(ast::function const& x, function f) 1052 { 1053 // Create variables for each argument and register the 1054 // argument in the symbol table so that references to it will succeed. 1055 function::arg_range rng = f.args(); 1056 function::arg_range::const_iterator iter = rng.begin(); 1057 BOOST_FOREACH(ast::identifier const& arg, x.args) 1058 { 1059 // Create an arg_ for this variable. 1060 value arg_ = var(arg.name); 1061 1062 // Store the initial value into the arg_. 1063 arg_.assign(*iter); 1064 1065 // Add arguments to variable symbol table. 1066 locals[arg.name] = arg_; 1067 ++iter; 1068 } 1069 1070 if (!void_return) 1071 { 1072 // Create an alloca for the return value 1073 return_var = var("return.val"); 1074 } 1075 } 1076 operator ()(ast::function const & x)1077 bool compiler::operator()(ast::function const& x) 1078 { 1079 /////////////////////////////////////////////////////////////////////// 1080 // the signature: 1081 function f = function_decl(x); 1082 if (!f.is_valid()) 1083 return false; 1084 1085 /////////////////////////////////////////////////////////////////////// 1086 // the body: 1087 if (x.body) // compile the body if this is not a prototype 1088 { 1089 // Create a new basic block to start insertion into. 1090 basic_block block = make_basic_block("entry", f); 1091 set_insert_point(block); 1092 1093 function_allocas(x, f); 1094 return_block = make_basic_block("return"); 1095 1096 if (!(*this)(*x.body)) 1097 { 1098 // Error reading body, remove function. 1099 f.erase_from_parent(); 1100 return false; 1101 } 1102 1103 basic_block last_block = f.last_block(); 1104 1105 // If the last block is unterminated, connect it to return_block 1106 if (!last_block.has_terminator()) 1107 { 1108 set_insert_point(last_block); 1109 branch(return_block); 1110 } 1111 1112 f.add(return_block); 1113 set_insert_point(return_block); 1114 1115 if (void_return) 1116 return_(); 1117 else 1118 return_(return_var); 1119 1120 // Validate the generated code, checking for consistency. 1121 f.verify(); 1122 1123 // Optimize the function. 1124 optimize_function(f); 1125 } 1126 1127 return true; 1128 } 1129 operator ()(ast::function_list const & x)1130 bool compiler::operator()(ast::function_list const& x) 1131 { 1132 BOOST_FOREACH(ast::function const& f, x) 1133 { 1134 locals.clear(); // clear the variables 1135 if (!(*this)(f)) 1136 return false; 1137 } 1138 return true; 1139 } 1140 }} 1141 1142