spirit/example/qi/compiler_tutorial/conjure3/compiler.cpp
2018-12-27 19:36:51 +03:00

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;
}
}}