1142 lines
30 KiB
C++
1142 lines
30 KiB
C++
/*=============================================================================
|
|
Copyright (c) 2001-2011 Joel de Guzman
|
|
|
|
Distributed under the Boost Software License, Version 1.0. (See accompanying
|
|
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
|
|
=============================================================================*/
|
|
#include "config.hpp"
|
|
#include "compiler.hpp"
|
|
#include "annotation.hpp"
|
|
#include "vm.hpp"
|
|
|
|
#include <boost/foreach.hpp>
|
|
#include <boost/variant/apply_visitor.hpp>
|
|
#include <boost/range/adaptor/transformed.hpp>
|
|
#include <boost/assert.hpp>
|
|
#include <set>
|
|
|
|
namespace client { namespace code_gen
|
|
{
|
|
value::value()
|
|
: v(0),
|
|
is_lvalue_(false),
|
|
builder(0)
|
|
{}
|
|
|
|
value::value(
|
|
llvm::Value* v,
|
|
bool is_lvalue_,
|
|
llvm::IRBuilder<>* builder)
|
|
: v(v),
|
|
is_lvalue_(is_lvalue_),
|
|
builder(builder)
|
|
{}
|
|
|
|
value::value(value const& rhs)
|
|
: v(rhs.v),
|
|
is_lvalue_(rhs.is_lvalue_),
|
|
builder(rhs.builder)
|
|
{}
|
|
|
|
bool value::is_lvalue() const
|
|
{
|
|
return is_lvalue_;
|
|
}
|
|
|
|
bool value::is_valid() const
|
|
{
|
|
return v != 0;
|
|
}
|
|
|
|
value::operator bool() const
|
|
{
|
|
return v != 0;
|
|
}
|
|
|
|
void value::name(char const* id)
|
|
{
|
|
v->setName(id);
|
|
}
|
|
|
|
void value::name(std::string const& id)
|
|
{
|
|
v->setName(id);
|
|
}
|
|
|
|
value::operator llvm::Value*() const
|
|
{
|
|
if (is_lvalue_)
|
|
{
|
|
BOOST_ASSERT(builder != 0);
|
|
return builder->CreateLoad(v, v->getName());
|
|
}
|
|
return v;
|
|
}
|
|
|
|
value& value::operator=(value const& rhs)
|
|
{
|
|
v = rhs.v;
|
|
is_lvalue_ = rhs.is_lvalue_;
|
|
builder = rhs.builder;
|
|
return *this;
|
|
}
|
|
|
|
value& value::assign(value const& rhs)
|
|
{
|
|
BOOST_ASSERT(is_lvalue());
|
|
BOOST_ASSERT(builder != 0);
|
|
builder->CreateStore(rhs, v);
|
|
return *this;
|
|
}
|
|
|
|
value operator-(value a)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateNeg(a, "neg_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator!(value a)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateNot(a, "not_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator+(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateAdd(a, b, "add_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator-(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateSub(a, b, "sub_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator*(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateMul(a, b, "mul_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator/(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateSDiv(a, b, "div_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator%(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateSRem(a, b, "mod_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator&(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateAnd(a, b, "and_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator|(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateOr(a, b, "or_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator^(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateXor(a, b, "xor_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator<<(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateShl(a, b, "shl_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator>>(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateLShr(a, b, "shr_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator==(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateICmpEQ(a, b, "eq_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator!=(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateICmpNE(a, b, "ne_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator<(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateICmpSLT(a, b, "slt_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator<=(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateICmpSLE(a, b, "sle_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator>(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateICmpSGT(a, b, "sgt_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
value operator>=(value a, value b)
|
|
{
|
|
BOOST_ASSERT(a.builder != 0);
|
|
return value(
|
|
a.builder->CreateICmpSGE(a, b, "sge_tmp"),
|
|
false, a.builder
|
|
);
|
|
}
|
|
|
|
struct function::to_value
|
|
{
|
|
typedef value result_type;
|
|
llvm_compiler* c;
|
|
|
|
to_value(llvm_compiler* c = 0) : c(c) {}
|
|
|
|
value operator()(llvm::Value& v) const
|
|
{
|
|
return c->val(&v);
|
|
}
|
|
};
|
|
|
|
bool basic_block::has_terminator() const
|
|
{
|
|
return b->getTerminator() != 0;
|
|
}
|
|
|
|
bool basic_block::is_valid() const
|
|
{
|
|
return b != 0;
|
|
}
|
|
|
|
function::operator llvm::Function*() const
|
|
{
|
|
return f;
|
|
}
|
|
|
|
std::size_t function::arg_size() const
|
|
{
|
|
return f->arg_size();
|
|
}
|
|
|
|
void function::add(basic_block const& b)
|
|
{
|
|
f->getBasicBlockList().push_back(b);
|
|
}
|
|
|
|
void function::erase_from_parent()
|
|
{
|
|
f->eraseFromParent();
|
|
}
|
|
|
|
basic_block function::last_block()
|
|
{
|
|
return &f->getBasicBlockList().back();
|
|
}
|
|
|
|
bool function::empty() const
|
|
{
|
|
return f->empty();
|
|
}
|
|
|
|
std::string function::name() const
|
|
{
|
|
return f->getName();
|
|
}
|
|
|
|
function::arg_range function::args() const
|
|
{
|
|
BOOST_ASSERT(c != 0);
|
|
arg_val_iterator first(f->arg_begin(), to_value());
|
|
arg_val_iterator last(f->arg_end(), to_value());
|
|
return arg_range(first, last);
|
|
}
|
|
|
|
bool function::is_valid() const
|
|
{
|
|
return f != 0;
|
|
}
|
|
|
|
void function::verify() const
|
|
{
|
|
llvm::verifyFunction(*f);
|
|
}
|
|
|
|
value llvm_compiler::val(unsigned int x)
|
|
{
|
|
return value(
|
|
llvm::ConstantInt::get(context(), llvm::APInt(int_size, x)),
|
|
false, &llvm_builder);
|
|
}
|
|
|
|
value llvm_compiler::val(int x)
|
|
{
|
|
return value(
|
|
llvm::ConstantInt::get(context(), llvm::APInt(int_size, x)),
|
|
false, &llvm_builder);
|
|
}
|
|
|
|
value llvm_compiler::val(bool x)
|
|
{
|
|
return value(
|
|
llvm::ConstantInt::get(context(), llvm::APInt(1, x)),
|
|
false, &llvm_builder);
|
|
}
|
|
|
|
value llvm_compiler::val(llvm::Value* v)
|
|
{
|
|
return value(v, false, &llvm_builder);
|
|
}
|
|
|
|
namespace
|
|
{
|
|
// Create an alloca instruction in the entry block of
|
|
// the function. This is used for mutable variables etc.
|
|
llvm::AllocaInst*
|
|
make_entry_block_alloca(
|
|
llvm::Function* f,
|
|
char const* name,
|
|
llvm::LLVMContext& context)
|
|
{
|
|
llvm::IRBuilder<> builder(
|
|
&f->getEntryBlock(),
|
|
f->getEntryBlock().begin());
|
|
|
|
return builder.CreateAlloca(
|
|
llvm::Type::getIntNTy(context, int_size), 0, name);
|
|
}
|
|
}
|
|
|
|
value llvm_compiler::var(char const* name)
|
|
{
|
|
llvm::Function* f = llvm_builder.GetInsertBlock()->getParent();
|
|
llvm::IRBuilder<> builder(
|
|
&f->getEntryBlock(),
|
|
f->getEntryBlock().begin());
|
|
|
|
llvm::AllocaInst* alloca = builder.CreateAlloca(
|
|
llvm::Type::getIntNTy(context(), int_size), 0, name);
|
|
|
|
return value(alloca, true, &llvm_builder);
|
|
}
|
|
|
|
struct value::to_llvm_value
|
|
{
|
|
typedef llvm::Value* result_type;
|
|
llvm::Value* operator()(value const& x) const
|
|
{
|
|
return x;
|
|
}
|
|
};
|
|
|
|
template <typename C>
|
|
llvm::Value* llvm_compiler::call_impl(
|
|
function callee,
|
|
C const& args_)
|
|
{
|
|
// Sigh. LLVM requires CreateCall arguments to be random access.
|
|
// It would have been better if it can accept forward iterators.
|
|
// I guess it needs the arguments to be in contiguous memory.
|
|
// So, we have to put the args into a temporary std::vector.
|
|
std::vector<llvm::Value*> args(
|
|
args_.begin(), args_.end());
|
|
|
|
// Check the args for null values. We can't have null values.
|
|
// Return 0 if we find one to flag error.
|
|
BOOST_FOREACH(llvm::Value* arg, args)
|
|
{
|
|
if (arg == 0)
|
|
return 0;
|
|
}
|
|
|
|
return llvm_builder.CreateCall(
|
|
callee, args.begin(), args.end(), "call_tmp");
|
|
}
|
|
|
|
template <typename Container>
|
|
value llvm_compiler::call(
|
|
function callee,
|
|
Container const& args)
|
|
{
|
|
llvm::Value* call = call_impl(
|
|
callee,
|
|
args | boost::adaptors::transformed(value::to_llvm_value()));
|
|
|
|
if (call == 0)
|
|
return val();
|
|
return value(call, false, &llvm_builder);
|
|
}
|
|
|
|
function llvm_compiler::get_function(char const* name)
|
|
{
|
|
return function(vm.module()->getFunction(name), this);
|
|
}
|
|
|
|
function llvm_compiler::get_current_function()
|
|
{
|
|
// get the current function
|
|
return function(llvm_builder.GetInsertBlock()->getParent(), this);
|
|
}
|
|
|
|
function llvm_compiler::declare_function(
|
|
bool void_return
|
|
, std::string const& name
|
|
, std::size_t nargs)
|
|
{
|
|
llvm::Type const* int_type =
|
|
llvm::Type::getIntNTy(context(), int_size);
|
|
llvm::Type const* void_type = llvm::Type::getVoidTy(context());
|
|
|
|
std::vector<llvm::Type const*> ints(nargs, int_type);
|
|
llvm::Type const* return_type = void_return ? void_type : int_type;
|
|
|
|
llvm::FunctionType* function_type =
|
|
llvm::FunctionType::get(void_return ? void_type : int_type, ints, false);
|
|
|
|
return function(llvm::Function::Create(
|
|
function_type, llvm::Function::ExternalLinkage,
|
|
name, vm.module()), this);
|
|
}
|
|
|
|
basic_block llvm_compiler::make_basic_block(
|
|
char const* name
|
|
, function parent
|
|
, basic_block before)
|
|
{
|
|
return llvm::BasicBlock::Create(context(), name, parent, before);
|
|
}
|
|
|
|
value llvm_compiler::var(std::string const& name)
|
|
{
|
|
return var(name.c_str());
|
|
}
|
|
|
|
function llvm_compiler::get_function(std::string const& name)
|
|
{
|
|
return get_function(name.c_str());
|
|
}
|
|
|
|
basic_block llvm_compiler::get_insert_block()
|
|
{
|
|
return llvm_builder.GetInsertBlock();
|
|
}
|
|
|
|
void llvm_compiler::set_insert_point(basic_block b)
|
|
{
|
|
llvm_builder.SetInsertPoint(b);
|
|
}
|
|
|
|
void llvm_compiler::conditional_branch(
|
|
value cond, basic_block true_br, basic_block false_br)
|
|
{
|
|
llvm_builder.CreateCondBr(cond, true_br, false_br);
|
|
}
|
|
|
|
void llvm_compiler::branch(basic_block b)
|
|
{
|
|
llvm_builder.CreateBr(b);
|
|
}
|
|
|
|
void llvm_compiler::return_()
|
|
{
|
|
llvm_builder.CreateRetVoid();
|
|
}
|
|
|
|
void llvm_compiler::return_(value v)
|
|
{
|
|
llvm_builder.CreateRet(v);
|
|
}
|
|
|
|
void llvm_compiler::optimize_function(function f)
|
|
{
|
|
// Optimize the function.
|
|
fpm.run(*f);
|
|
}
|
|
|
|
void llvm_compiler::init_fpm()
|
|
{
|
|
// Set up the optimizer pipeline. Start with registering info about how the
|
|
// target lays out data structures.
|
|
fpm.add(new llvm::TargetData(*vm.execution_engine()->getTargetData()));
|
|
// Provide basic AliasAnalysis support for GVN.
|
|
fpm.add(llvm::createBasicAliasAnalysisPass());
|
|
// Promote allocas to registers.
|
|
fpm.add(llvm::createPromoteMemoryToRegisterPass());
|
|
// Do simple "peephole" optimizations and bit-twiddling optzns.
|
|
fpm.add(llvm::createInstructionCombiningPass());
|
|
// Reassociate expressions.
|
|
fpm.add(llvm::createReassociatePass());
|
|
// Eliminate Common SubExpressions.
|
|
fpm.add(llvm::createGVNPass());
|
|
// Simplify the control flow graph (deleting unreachable blocks, etc).
|
|
fpm.add(llvm::createCFGSimplificationPass());
|
|
|
|
fpm.doInitialization();
|
|
}
|
|
|
|
value compiler::operator()(unsigned int x)
|
|
{
|
|
return val(x);
|
|
}
|
|
|
|
value compiler::operator()(bool x)
|
|
{
|
|
return val(x);
|
|
}
|
|
|
|
value compiler::operator()(ast::primary_expr const& x)
|
|
{
|
|
return boost::apply_visitor(*this, x.get());
|
|
}
|
|
|
|
value compiler::operator()(ast::identifier const& x)
|
|
{
|
|
// Look this variable up in the function.
|
|
if (locals.find(x.name) == locals.end())
|
|
{
|
|
error_handler(x.id, "Undeclared variable: " + x.name);
|
|
return val();
|
|
}
|
|
return locals[x.name];
|
|
}
|
|
|
|
value compiler::operator()(ast::unary_expr const& x)
|
|
{
|
|
value operand = boost::apply_visitor(*this, x.operand_);
|
|
if (!operand.is_valid())
|
|
return val();
|
|
|
|
switch (x.operator_)
|
|
{
|
|
case token_ids::compl_: return operand ^ val(-1);
|
|
case token_ids::minus: return -operand;
|
|
case token_ids::not_: return !operand;
|
|
case token_ids::plus: return operand;
|
|
case token_ids::plus_plus:
|
|
{
|
|
if (!operand.is_lvalue())
|
|
{
|
|
error_handler(x.id, "++ needs an var");
|
|
return val();
|
|
}
|
|
|
|
value r = operand + val(1);
|
|
operand.assign(r);
|
|
return operand;
|
|
}
|
|
case token_ids::minus_minus:
|
|
{
|
|
if (!operand.is_lvalue())
|
|
{
|
|
error_handler(x.id, "-- needs an var");
|
|
return val();
|
|
}
|
|
|
|
value r = operand - val(1);
|
|
operand.assign(r);
|
|
return operand;
|
|
}
|
|
default:
|
|
BOOST_ASSERT(0);
|
|
return val();
|
|
}
|
|
}
|
|
|
|
namespace
|
|
{
|
|
struct compile_args
|
|
{
|
|
compiler& c;
|
|
compile_args(compiler& c) : c(c) {}
|
|
|
|
typedef value result_type;
|
|
value operator()(ast::expression const& expr) const
|
|
{
|
|
return c(expr);
|
|
}
|
|
};
|
|
}
|
|
|
|
value compiler::operator()(ast::function_call const& x)
|
|
{
|
|
function callee = get_function(x.function_name.name);
|
|
if (!callee.is_valid())
|
|
{
|
|
error_handler(x.function_name.id,
|
|
"Function not found: " + x.function_name.name);
|
|
return val();
|
|
}
|
|
|
|
if (callee.arg_size() != x.args.size())
|
|
{
|
|
error_handler(x.function_name.id,
|
|
"Wrong number of arguments: " + x.function_name.name);
|
|
return val();
|
|
}
|
|
|
|
return call(callee,
|
|
x.args | boost::adaptors::transformed(compile_args(*this)));
|
|
}
|
|
|
|
namespace
|
|
{
|
|
int precedence[] = {
|
|
// precedence 1
|
|
1, // op_comma
|
|
|
|
// precedence 2
|
|
2, // op_assign
|
|
2, // op_plus_assign
|
|
2, // op_minus_assign
|
|
2, // op_times_assign
|
|
2, // op_divide_assign
|
|
2, // op_mod_assign
|
|
2, // op_bit_and_assign
|
|
2, // op_bit_xor_assign
|
|
2, // op_bitor_assign
|
|
2, // op_shift_left_assign
|
|
2, // op_shift_right_assign
|
|
|
|
// precedence 3
|
|
3, // op_logical_or
|
|
|
|
// precedence 4
|
|
4, // op_logical_and
|
|
|
|
// precedence 5
|
|
5, // op_bit_or
|
|
|
|
// precedence 6
|
|
6, // op_bit_xor
|
|
|
|
// precedence 7
|
|
7, // op_bit_and
|
|
|
|
// precedence 8
|
|
8, // op_equal
|
|
8, // op_not_equal
|
|
|
|
// precedence 9
|
|
9, // op_less
|
|
9, // op_less_equal
|
|
9, // op_greater
|
|
9, // op_greater_equal
|
|
|
|
// precedence 10
|
|
10, // op_shift_left
|
|
10, // op_shift_right
|
|
|
|
// precedence 11
|
|
11, // op_plus
|
|
11, // op_minus
|
|
|
|
// precedence 12
|
|
12, // op_times
|
|
12, // op_divide
|
|
12 // op_mod
|
|
};
|
|
}
|
|
|
|
inline int precedence_of(token_ids::type op)
|
|
{
|
|
return precedence[op & 0xFF];
|
|
}
|
|
|
|
value compiler::compile_binary_expression(
|
|
value lhs, value rhs, token_ids::type op)
|
|
{
|
|
switch (op)
|
|
{
|
|
case token_ids::plus: return lhs + rhs;
|
|
case token_ids::minus: return lhs - rhs;
|
|
case token_ids::times: return lhs * rhs;
|
|
case token_ids::divide: return lhs / rhs;
|
|
case token_ids::mod: return lhs % rhs;
|
|
|
|
case token_ids::logical_or:
|
|
case token_ids::bit_or: return lhs | rhs;
|
|
|
|
case token_ids::logical_and:
|
|
case token_ids::bit_and: return lhs & rhs;
|
|
|
|
case token_ids::bit_xor: return lhs ^ rhs;
|
|
case token_ids::shift_left: return lhs << rhs;
|
|
case token_ids::shift_right: return lhs >> rhs;
|
|
|
|
case token_ids::equal: return lhs == rhs;
|
|
case token_ids::not_equal: return lhs != rhs;
|
|
case token_ids::less: return lhs < rhs;
|
|
case token_ids::less_equal: return lhs <= rhs;
|
|
case token_ids::greater: return lhs > rhs;
|
|
case token_ids::greater_equal: return lhs >= rhs;
|
|
|
|
default: BOOST_ASSERT(0); return val();
|
|
}
|
|
}
|
|
|
|
// The Shunting-yard algorithm
|
|
value compiler::compile_expression(
|
|
int min_precedence,
|
|
value lhs,
|
|
std::list<ast::operation>::const_iterator& rest_begin,
|
|
std::list<ast::operation>::const_iterator rest_end)
|
|
{
|
|
while ((rest_begin != rest_end) &&
|
|
(precedence_of(rest_begin->operator_) >= min_precedence))
|
|
{
|
|
token_ids::type op = rest_begin->operator_;
|
|
value rhs = boost::apply_visitor(*this, rest_begin->operand_);
|
|
if (!rhs.is_valid())
|
|
return val();
|
|
++rest_begin;
|
|
|
|
while ((rest_begin != rest_end) &&
|
|
(precedence_of(rest_begin->operator_) > precedence_of(op)))
|
|
{
|
|
token_ids::type next_op = rest_begin->operator_;
|
|
rhs = compile_expression(
|
|
precedence_of(next_op), rhs, rest_begin, rest_end);
|
|
}
|
|
|
|
lhs = compile_binary_expression(lhs, rhs, op);
|
|
}
|
|
return lhs;
|
|
}
|
|
|
|
value compiler::operator()(ast::expression const& x)
|
|
{
|
|
value lhs = boost::apply_visitor(*this, x.first);
|
|
if (!lhs.is_valid())
|
|
return val();
|
|
std::list<ast::operation>::const_iterator rest_begin = x.rest.begin();
|
|
return compile_expression(0, lhs, rest_begin, x.rest.end());
|
|
}
|
|
|
|
value compiler::operator()(ast::assignment const& x)
|
|
{
|
|
if (locals.find(x.lhs.name) == locals.end())
|
|
{
|
|
error_handler(x.lhs.id, "Undeclared variable: " + x.lhs.name);
|
|
return val();
|
|
}
|
|
|
|
value lhs = locals[x.lhs.name];
|
|
value rhs = (*this)(x.rhs);
|
|
if (!rhs.is_valid())
|
|
return val();
|
|
|
|
if (x.operator_ == token_ids::assign)
|
|
{
|
|
lhs.assign(rhs);
|
|
return lhs;
|
|
}
|
|
|
|
value result;
|
|
switch (x.operator_)
|
|
{
|
|
case token_ids::plus_assign: result = lhs + rhs; break;
|
|
case token_ids::minus_assign: result = lhs - rhs; break;
|
|
case token_ids::times_assign: result = lhs * rhs; break;
|
|
case token_ids::divide_assign: result = lhs / rhs; break;
|
|
case token_ids::mod_assign: result = lhs % rhs; break;
|
|
case token_ids::bit_and_assign: result = lhs & rhs; break;
|
|
case token_ids::bit_xor_assign: result = lhs ^ rhs; break;
|
|
case token_ids::bit_or_assign: result = lhs | rhs; break;
|
|
case token_ids::shift_left_assign: result = lhs << rhs; break;
|
|
case token_ids::shift_right_assign: result = lhs >> rhs; break;
|
|
default: BOOST_ASSERT(0); return val();
|
|
}
|
|
|
|
lhs.assign(result);
|
|
return lhs;
|
|
}
|
|
|
|
bool compiler::operator()(ast::variable_declaration const& x)
|
|
{
|
|
if (locals.find(x.lhs.name) != locals.end())
|
|
{
|
|
error_handler(x.lhs.id, "Duplicate variable: " + x.lhs.name);
|
|
return false;
|
|
}
|
|
|
|
value init;
|
|
std::string const& name = x.lhs.name;
|
|
|
|
if (x.rhs) // if there's an RHS initializer
|
|
{
|
|
init = (*this)(*x.rhs);
|
|
if (!init.is_valid()) // don't add the variable if the RHS fails
|
|
return false;
|
|
}
|
|
|
|
value var_ = var(name.c_str());
|
|
if (init.is_valid())
|
|
var_.assign(init);
|
|
|
|
// Remember this binding.
|
|
locals[name] = var_;
|
|
return true;
|
|
}
|
|
|
|
struct compiler::statement_compiler : compiler
|
|
{
|
|
typedef bool result_type;
|
|
};
|
|
|
|
compiler::statement_compiler& compiler::as_statement()
|
|
{
|
|
return *static_cast<statement_compiler*>(this);
|
|
}
|
|
|
|
bool compiler::operator()(ast::statement const& x)
|
|
{
|
|
if (boost::get<ast::nil>(&x) != 0) // empty statement
|
|
return true;
|
|
return boost::apply_visitor(as_statement(), x);
|
|
}
|
|
|
|
bool compiler::operator()(ast::statement_list const& x)
|
|
{
|
|
BOOST_FOREACH(ast::statement const& s, x)
|
|
{
|
|
if (!(*this)(s))
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool compiler::operator()(ast::if_statement const& x)
|
|
{
|
|
value condition = (*this)(x.condition);
|
|
if (!condition.is_valid())
|
|
return false;
|
|
|
|
function f = get_current_function();
|
|
|
|
// Create blocks for the then and else cases. Insert the 'then' block at the
|
|
// end of the function.
|
|
basic_block then_block = make_basic_block("if.then", f);
|
|
basic_block else_block;
|
|
basic_block exit_block;
|
|
|
|
if (x.else_)
|
|
{
|
|
else_block = make_basic_block("if.else");
|
|
conditional_branch(condition, then_block, else_block);
|
|
}
|
|
else
|
|
{
|
|
exit_block = make_basic_block("if.end");
|
|
conditional_branch(condition, then_block, exit_block);
|
|
}
|
|
|
|
// Emit then value.
|
|
set_insert_point(then_block);
|
|
if (!(*this)(x.then))
|
|
return false;
|
|
if (!then_block.has_terminator())
|
|
{
|
|
if (!exit_block.is_valid())
|
|
exit_block = make_basic_block("if.end");
|
|
branch(exit_block);
|
|
}
|
|
// Codegen of 'then' can change the current block, update then_block
|
|
then_block = get_insert_block();
|
|
|
|
if (x.else_)
|
|
{
|
|
// Emit else block.
|
|
f.add(else_block);
|
|
set_insert_point(else_block);
|
|
if (!(*this)(*x.else_))
|
|
return false;
|
|
if (!else_block.has_terminator())
|
|
{
|
|
if (!exit_block.is_valid())
|
|
exit_block = make_basic_block("if.end");
|
|
branch(exit_block);
|
|
}
|
|
// Codegen of 'else' can change the current block, update else_block
|
|
else_block = get_insert_block();
|
|
}
|
|
|
|
if (exit_block.is_valid())
|
|
{
|
|
// Emit exit block
|
|
f.add(exit_block);
|
|
set_insert_point(exit_block);
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool compiler::operator()(ast::while_statement const& x)
|
|
{
|
|
function f = get_current_function();
|
|
|
|
basic_block cond_block = make_basic_block("while.cond", f);
|
|
basic_block body_block = make_basic_block("while.body");
|
|
basic_block exit_block = make_basic_block("while.end");
|
|
|
|
branch(cond_block);
|
|
set_insert_point(cond_block);
|
|
value condition = (*this)(x.condition);
|
|
if (!condition.is_valid())
|
|
return false;
|
|
conditional_branch(condition, body_block, exit_block);
|
|
f.add(body_block);
|
|
set_insert_point(body_block);
|
|
|
|
if (!(*this)(x.body))
|
|
return false;
|
|
|
|
if (!body_block.has_terminator())
|
|
branch(cond_block); // loop back
|
|
|
|
// Emit exit block
|
|
f.add(exit_block);
|
|
set_insert_point(exit_block);
|
|
|
|
return true;
|
|
}
|
|
|
|
bool compiler::operator()(ast::return_statement const& x)
|
|
{
|
|
if (void_return)
|
|
{
|
|
if (x.expr)
|
|
{
|
|
error_handler(
|
|
x.id, "'void' function returning a value: ");
|
|
return false;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if (!x.expr)
|
|
{
|
|
error_handler(
|
|
x.id, current_function_name
|
|
+ " function must return a value: ");
|
|
return false;
|
|
}
|
|
}
|
|
|
|
if (x.expr)
|
|
{
|
|
value return_val = (*this)(*x.expr);
|
|
if (!return_val.is_valid())
|
|
return false;
|
|
return_var.assign(return_val);
|
|
}
|
|
|
|
branch(return_block);
|
|
return true;
|
|
}
|
|
|
|
function compiler::function_decl(ast::function const& x)
|
|
{
|
|
void_return = x.return_type == "void";
|
|
current_function_name = x.function_name.name;
|
|
|
|
function f =
|
|
declare_function(
|
|
void_return
|
|
, current_function_name
|
|
, x.args.size());
|
|
|
|
// If function conflicted, the function already exixts. If it has a
|
|
// body, don't allow redefinition or reextern.
|
|
if (f.name() != current_function_name)
|
|
{
|
|
// Delete the one we just made and get the existing one.
|
|
f.erase_from_parent();
|
|
f = get_function(current_function_name);
|
|
|
|
// If function already has a body, reject this.
|
|
if (!f.empty())
|
|
{
|
|
error_handler(
|
|
x.function_name.id,
|
|
"Duplicate function: " + x.function_name.name);
|
|
return function();
|
|
}
|
|
|
|
// If function took a different number of args, reject.
|
|
if (f.arg_size() != x.args.size())
|
|
{
|
|
error_handler(
|
|
x.function_name.id,
|
|
"Redefinition of function with different # args: "
|
|
+ x.function_name.name);
|
|
return function();
|
|
}
|
|
|
|
// Set names for all arguments.
|
|
function::arg_range rng = f.args();
|
|
function::arg_range::const_iterator iter = rng.begin();
|
|
BOOST_FOREACH(ast::identifier const& arg, x.args)
|
|
{
|
|
iter->name(arg.name);
|
|
++iter;
|
|
}
|
|
}
|
|
return f;
|
|
}
|
|
|
|
void compiler::function_allocas(ast::function const& x, function f)
|
|
{
|
|
// Create variables for each argument and register the
|
|
// argument in the symbol table so that references to it will succeed.
|
|
function::arg_range rng = f.args();
|
|
function::arg_range::const_iterator iter = rng.begin();
|
|
BOOST_FOREACH(ast::identifier const& arg, x.args)
|
|
{
|
|
// Create an arg_ for this variable.
|
|
value arg_ = var(arg.name);
|
|
|
|
// Store the initial value into the arg_.
|
|
arg_.assign(*iter);
|
|
|
|
// Add arguments to variable symbol table.
|
|
locals[arg.name] = arg_;
|
|
++iter;
|
|
}
|
|
|
|
if (!void_return)
|
|
{
|
|
// Create an alloca for the return value
|
|
return_var = var("return.val");
|
|
}
|
|
}
|
|
|
|
bool compiler::operator()(ast::function const& x)
|
|
{
|
|
///////////////////////////////////////////////////////////////////////
|
|
// the signature:
|
|
function f = function_decl(x);
|
|
if (!f.is_valid())
|
|
return false;
|
|
|
|
///////////////////////////////////////////////////////////////////////
|
|
// the body:
|
|
if (x.body) // compile the body if this is not a prototype
|
|
{
|
|
// Create a new basic block to start insertion into.
|
|
basic_block block = make_basic_block("entry", f);
|
|
set_insert_point(block);
|
|
|
|
function_allocas(x, f);
|
|
return_block = make_basic_block("return");
|
|
|
|
if (!(*this)(*x.body))
|
|
{
|
|
// Error reading body, remove function.
|
|
f.erase_from_parent();
|
|
return false;
|
|
}
|
|
|
|
basic_block last_block = f.last_block();
|
|
|
|
// If the last block is unterminated, connect it to return_block
|
|
if (!last_block.has_terminator())
|
|
{
|
|
set_insert_point(last_block);
|
|
branch(return_block);
|
|
}
|
|
|
|
f.add(return_block);
|
|
set_insert_point(return_block);
|
|
|
|
if (void_return)
|
|
return_();
|
|
else
|
|
return_(return_var);
|
|
|
|
// Validate the generated code, checking for consistency.
|
|
f.verify();
|
|
|
|
// Optimize the function.
|
|
optimize_function(f);
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
bool compiler::operator()(ast::function_list const& x)
|
|
{
|
|
BOOST_FOREACH(ast::function const& f, x)
|
|
{
|
|
locals.clear(); // clear the variables
|
|
if (!(*this)(f))
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
}}
|
|
|