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
18namespace client { namespace code_gen
19{
20 value::value()
21 : v(0),
22 is_lvalue_(false),
23 builder(0)
24 {}
25
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
35 value::value(value const& rhs)
36 : v(rhs.v),
37 is_lvalue_(rhs.is_lvalue_),
38 builder(rhs.builder)
39 {}
40
41 bool value::is_lvalue() const
42 {
43 return is_lvalue_;
44 }
45
46 bool value::is_valid() const
47 {
48 return v != 0;
49 }
50
51 value::operator bool() const
52 {
53 return v != 0;
54 }
55
56 void value::name(char const* id)
57 {
58 v->setName(id);
59 }
60
61 void value::name(std::string const& id)
62 {
63 v->setName(id);
64 }
65
66 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
259 to_value(llvm_compiler* c = 0) : c(c) {}
260
261 value operator()(llvm::Value& v) const
262 {
263 return c->val(&v);
264 }
265 };
266
267 bool basic_block::has_terminator() const
268 {
269 return b->getTerminator() != 0;
270 }
271
272 bool basic_block::is_valid() const
273 {
274 return b != 0;
275 }
276
277 function::operator llvm::Function*() const
278 {
279 return f;
280 }
281
282 std::size_t function::arg_size() const
283 {
284 return f->arg_size();
285 }
286
287 void function::add(basic_block const& b)
288 {
289 f->getBasicBlockList().push_back(b);
290 }
291
292 void function::erase_from_parent()
293 {
294 f->eraseFromParent();
295 }
296
297 basic_block function::last_block()
298 {
299 return &f->getBasicBlockList().back();
300 }
301
302 bool function::empty() const
303 {
304 return f->empty();
305 }
306
307 std::string function::name() const
308 {
309 return f->getName();
310 }
311
312 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
320 bool function::is_valid() const
321 {
322 return f != 0;
323 }
324
325 void function::verify() const
326 {
327 llvm::verifyFunction(*f);
328 }
329
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
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
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
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*
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
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;
391 llvm::Value* operator()(value const& x) const
392 {
393 return x;
394 }
395 };
396
397 template <typename C>
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>
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
435 function llvm_compiler::get_function(char const* name)
436 {
437 return function(vm.module()->getFunction(name), this);
438 }
439
440 function llvm_compiler::get_current_function()
441 {
442 // get the current function
443 return function(llvm_builder.GetInsertBlock()->getParent(), this);
444 }
445
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
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
474 value llvm_compiler::var(std::string const& name)
475 {
476 return var(name: name.c_str());
477 }
478
479 function llvm_compiler::get_function(std::string const& name)
480 {
481 return get_function(name: name.c_str());
482 }
483
484 basic_block llvm_compiler::get_insert_block()
485 {
486 return llvm_builder.GetInsertBlock();
487 }
488
489 void llvm_compiler::set_insert_point(basic_block b)
490 {
491 llvm_builder.SetInsertPoint(b);
492 }
493
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
500 void llvm_compiler::branch(basic_block b)
501 {
502 llvm_builder.CreateBr(b);
503 }
504
505 void llvm_compiler::return_()
506 {
507 llvm_builder.CreateRetVoid();
508 }
509
510 void llvm_compiler::return_(value v)
511 {
512 llvm_builder.CreateRet(v);
513 }
514
515 void llvm_compiler::optimize_function(function f)
516 {
517 // Optimize the function.
518 fpm.run(*f);
519 }
520
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
542 value compiler::operator()(unsigned int x)
543 {
544 return val(x);
545 }
546
547 value compiler::operator()(bool x)
548 {
549 return val(x);
550 }
551
552 value compiler::operator()(ast::primary_expr const& x)
553 {
554 return boost::apply_visitor(visitor&: *this, visitable: x.get());
555 }
556
557 value compiler::operator()(ast::identifier const& x)
558 {
559 // Look this variable up in the function.
560 if (locals.find(x: 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
568 value compiler::operator()(ast::unary_expr const& x)
569 {
570 value operand = boost::apply_visitor(visitor&: *this, visitable: 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(rhs: 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(rhs: 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;
615 compile_args(compiler& c) : c(c) {}
616
617 typedef value result_type;
618 value operator()(ast::expression const& expr) const
619 {
620 return c(expr);
621 }
622 };
623 }
624
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
705 inline int precedence_of(token_ids::type op)
706 {
707 return precedence[op & 0xFF];
708 }
709
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
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(op: rest_begin->operator_) >= min_precedence))
751 {
752 token_ids::type op = rest_begin->operator_;
753 value rhs = boost::apply_visitor(visitor&: *this, visitable: rest_begin->operand_);
754 if (!rhs.is_valid())
755 return val();
756 ++rest_begin;
757
758 while ((rest_begin != rest_end) &&
759 (precedence_of(op: rest_begin->operator_) > precedence_of(op)))
760 {
761 token_ids::type next_op = rest_begin->operator_;
762 rhs = compile_expression(
763 min_precedence: precedence_of(op: next_op), lhs: rhs, rest_begin, rest_end);
764 }
765
766 lhs = compile_binary_expression(lhs, rhs, op);
767 }
768 return lhs;
769 }
770
771 value compiler::operator()(ast::expression const& x)
772 {
773 value lhs = boost::apply_visitor(visitor&: *this, visitable: 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(min_precedence: 0, lhs, rest_begin, rest_end: x.rest.end());
778 }
779
780 value compiler::operator()(ast::assignment const& x)
781 {
782 if (locals.find(x: 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(rhs: result);
816 return lhs;
817 }
818
819 bool compiler::operator()(ast::variable_declaration const& x)
820 {
821 if (locals.find(x: 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(rhs: 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
851 compiler::statement_compiler& compiler::as_statement()
852 {
853 return *static_cast<statement_compiler*>(this);
854 }
855
856 bool compiler::operator()(ast::statement const& x)
857 {
858 if (boost::get<ast::nil>(operand: &x) != 0) // empty statement
859 return true;
860 return boost::apply_visitor(visitor&: as_statement(), visitable: x);
861 }
862
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
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(b: 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(b: exit_block);
932 set_insert_point(exit_block);
933 }
934 return true;
935 }
936
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(b: 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(b: exit_block);
962 set_insert_point(exit_block);
963
964 return true;
965 }
966
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
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
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(rhs: *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
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
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

source code of boost/libs/spirit/example/qi/compiler_tutorial/conjure3/compiler.cpp