blob: 826397ab216be800604bfdb63d10408ee0a8db91 [file] [log] [blame]
// Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#include <memory>
#include <vector>
#include <string>
#include "llvm/ADT/StringRef.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/ValueSymbolTable.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/WithColor.h"
// Ensure to use our own zone.
#include "custom_zone.h"
#include "vm/compiler/backend/sexpression.h"
// This file introduces several representations that exist between
// S-Expressions and llvm IR. To explain how each part is intended
// to be roughly translated using these I'll provide a mapping
// showing how each part is translated.
// At a high level two translations are very seamless:
// (function foo ...) -> DartFunction -> llvm::Function*
// (block B ...) -> DartBlock -> (sort of) llvm::BasicBlock*
// Internally within a function constants are given names and are then used in
// blocks. Each block additionally defines more names. Each of these names
// needs to be mapped to a DartValue (more on that later) so a context to help
// keep track of these name to DartValue mappings called a
// DartBasicBlockBuilder exists. It is only used for to aid in the
// (block B ...) -> DartBlock translation which is in turn used in the
// (function foo ...) -> DartFunction translation. DartFunctions and DartBlocks
// can be seen as validated representations of their S-Expression forms.
// Within a DartBlock we have DartInstructions. Each DartInstruction either
// has some effect (like calling a function or updating a value) or defines
// a new name mapping it to a DartValue later. DartValues are referenced as
// arguments to DartInstructions and map to llvm::Value*s. DartInstructions
// have no analogue which they're directly translated to in code but they
// do closely correspond mentally to llvm::Instruction*. The challenge is that
// a DartInstruction might map to a near arbitrary number of llvm Instructions
// and that mapping is very dependent on context. So instead of mapping them
// to objects DartInstructions just know how to add their llvm Instructions to
// an llvm::BasicBlock. These instructions might reference a verity of context
// and so BasicBlockBuilder is passed in to provide them with this context.
// Each DartInstruction is expected to already hold each DartValue that it
// needs as previously supplied by the DartBasicBlockBuilder on construction.
// An additional issue arises when translating DartInstructions into llvm IR.
// Many require introducing control flow when lowered to the level of llvm IR
// but this requires using multiple llvm::BasicBlock for a single DartBlock.
// Luckily each DartInstruction that is not a terminator is expected to make it
// possible for all non-exceptional control flow paths to wind up at a single
// basic block. Since BasicBlockBuilder keeps track of a "current" basic block
// via llvm::IRBuilder we simply ensure that after generating many blocks we
// end each instruction which requires new basic blocks on this final basic
// block that all generated blocks flow into. A picture better explains this:
// Say you have a DartBlock B_1 it would then be mapped to llvm blocks that
// look like this:
// B_1
// / \
// / \
// B_1_left B_1_right
// \ /
// \ /
// B_1_0
// And then we go on adding to B_1_0 as if it were the end of B_1 from before.
// Each DartValue knows how to map itself to an llvm::Value. In llvm a Value
// is really just anything you can give a name to in the IR but a DartValue
// is intended to be more specific, it's a compile time representation of a
// object, be it an integer, a tagged SMI, a pointer to a Dart Object, etc...
// its intended to correspond to some actual object that we're computing on.
// Class FunctionBuilder provides functionality for building
// and LLVM function object including the ability to add a
// named basic block, find an existing block, get the current
// context/module and additionally retrieve llvm Values valid
// in the current function.
class FunctionBuilder {
FunctionBuilder(llvm::LLVMContext& ctx,
llvm::Module& mod,
llvm::Function& func)
: ctx_(ctx), mod_(mod), func_(func) {}
llvm::LLVMContext& Context() { return ctx_; }
llvm::Module& Module() { return mod_; }
llvm::Value* GetSymbolValue(llvm::StringRef name) {
auto* symtab = func_.getValueSymbolTable();
return symtab->lookup(name);
llvm::BasicBlock* AddBasicBlock() {
return llvm::BasicBlock::Create(ctx_, "", &func_);
llvm::BasicBlock* AddBasicBlock(llvm::StringRef name) {
auto* bb = llvm::BasicBlock::Create(ctx_, name, &func_);
basic_blocks_[name] = bb;
return bb;
llvm::BasicBlock* GetBasicBlock(llvm::StringRef name) const {
auto iter = basic_blocks_.find(name);
if (iter != basic_blocks_.end()) return iter->getValue();
return nullptr;
llvm::LLVMContext& ctx_;
llvm::Module& mod_;
llvm::Function& func_;
llvm::StringMap<llvm::BasicBlock*> basic_blocks_;
class BasicBlockBuilder;
// TODO(jakehehrlich): Make this architecture dependent
// Class DartThreadObject is used as a high level object for generating
// code that reads fields from the thread object.
class DartThreadObject {
explicit DartThreadObject(BasicBlockBuilder& bb_builder)
: bb_builder_(bb_builder) {}
// StackLimit returns an llvm::Value representing the stack limit
// of the thread object.
llvm::Value* StackLimit() const;
static constexpr intptr_t kThreadStackLimitOffset = 72;
BasicBlockBuilder& bb_builder_;
// GetOffset returns an llvm::Value* representing a pointer to a particular
// field of the thread object. It adds the specified offset to the thread
// pointer, and then casts to the specified type.
llvm::Value* GetOffset(llvm::Type* type, intptr_t offset) const;
class DartValue;
// A class for keeping track of the basic block state and SSA values.
// This is similar to IRBuilder but also keeps track of the argument stack and
// basic block names.
class BasicBlockBuilder {
BasicBlockBuilder(llvm::BasicBlock* bb, FunctionBuilder& fb)
: fb_(fb), top_(bb), builder_(bb), thread_object_(*this) {}
llvm::LLVMContext& Context() { return fb_.Context(); }
llvm::Module& Module() { return fb_.Module(); }
llvm::IRBuilder<>& Builder() { return builder_; }
const DartThreadObject& ThreadObject() { return thread_object_; }
llvm::BasicBlock* AddBasicBlock() { return fb_.AddBasicBlock(); }
llvm::BasicBlock* GetBasicBlock(llvm::StringRef Name) const {
return fb_.GetBasicBlock(Name);
llvm::Value* GetSymbolValue(llvm::StringRef name) const {
return fb_.GetBasicBlock(name);
llvm::Value* GetValue(const DartValue* v);
void PushArgument(llvm::Value* v) { stack_.push_back(v); }
llvm::Value* PopArgument() {
llvm::Value* out = stack_.back();
return out;
FunctionBuilder& fb_;
llvm::BasicBlock* top_;
llvm::SmallVector<llvm::Value*, 16> stack_;
llvm::IRBuilder<> builder_;
llvm::DenseMap<const DartValue*, llvm::Value*> values_;
DartThreadObject thread_object_;
// Class DartValue represents an SSA value from the Dart SSA
// such that it can be converted into an llvm::Value*.
class DartValue {
virtual ~DartValue() {}
virtual llvm::Value* Make(BasicBlockBuilder& bb_builder) const = 0;
virtual llvm::Type* GetType(BasicBlockBuilder& bb_builder) const = 0;
// Class DartBasicBlockBuilder provides helpful context for going
// from an S-Expression basic block to a DartBlock. It just lets
// one lookup DartValue's by name at this time.
class DartBasicBlockBuilder {
void AddDef(llvm::StringRef name, const DartValue* v) { defs_[name] = v; }
const DartValue* GetDef(llvm::StringRef name) const {
auto iter = defs_.find(name);
if (iter != defs_.end()) return iter->getValue();
return nullptr;
llvm::StringMap<const DartValue*> defs_;
// A DartConstant is a DartValue for a constant.
class DartConstant : public DartValue {
std::string str;
enum class Type { String };
Type type;
llvm::Value* Make(BasicBlockBuilder& bb_builder) const override;
llvm::Type* GetType(BasicBlockBuilder& bb_builder) const override;
// Class DartInstruction represents a step within a DartBasicBlock.
// CheckStackOverflow or PushArgument are instructions. They contain
// DartValues as arguments typically. SSA definitions are also
// DartInstructions which assign DartValues to names in the function's
// context.
class DartInstruction {
virtual ~DartInstruction();
virtual void Build(BasicBlockBuilder& bb_builder) const = 0;
// Class InstCheckStackOverflow is a DartInstruction that represents
// an instance of a CheckStackOverflow instruction.
class InstCheckStackOverflow : public DartInstruction {
InstCheckStackOverflow() {}
~InstCheckStackOverflow() override {}
void Build(BasicBlockBuilder& bb_builder) const override;
static llvm::Expected<std::unique_ptr<DartInstruction>> Construct(
dart::SExpList* inst,
DartBasicBlockBuilder& bb_builder);
// Class InstPushArgument is a DartInstruction that represents
// and instance of a PushArgument Instruction.
class InstPushArgument : public DartInstruction {
explicit InstPushArgument(const DartValue* arg) : arg_(arg) {}
~InstPushArgument() override {}
void Build(BasicBlockBuilder& bb_builder) const override;
static llvm::Expected<std::unique_ptr<DartInstruction>> Construct(
dart::SExpList* inst,
DartBasicBlockBuilder& bb_builder);
const DartValue* arg_;
// Class InstStaticCall is a DartInstruction that represents a
// StaticCall instruction.
class InstStaticCall : public DartInstruction {
InstStaticCall(const DartValue* func, size_t args_len)
: function_(func), args_len_(args_len) {}
~InstStaticCall() override {}
void Build(BasicBlockBuilder& bb_builder) const override;
static llvm::Expected<std::unique_ptr<DartInstruction>> Construct(
dart::SExpList* inst,
DartBasicBlockBuilder& bb_builder);
const DartValue* function_;
size_t args_len_;
// Class InstReturn is a DartInstruction that represents a Return
// instruction.
class InstReturn : public DartInstruction {
InstReturn() {}
~InstReturn() override {}
void Build(BasicBlockBuilder& bb_builder) const override;
static llvm::Expected<std::unique_ptr<DartInstruction>> Construct(
dart::SExpList* inst,
DartBasicBlockBuilder& bb_builder);
// Class DartBlock represents a validated basic block as parsed from
// a (block ...) S-Expression.
struct DartBlock {
std::string name;
std::vector<std::unique_ptr<DartInstruction>> instructions;
// Class DartFunction represents a validated function parsed from a
// (function ...) S-Expression.
struct DartFunction {
std::string name;
DartBlock* normal_entry;
llvm::StringMap<DartConstant> constants;
llvm::StringMap<DartBlock> blocks;
// MakeFunction takes an S-Expression and an environment of externally
// defined DartValues and produces a DartFunction corresponding to the
// S-Expression if everything is valid. If something about the syntax
// of the S-Expression is invalid then the llvm::Expected will hold an
// error explaining the issue.
llvm::Expected<DartFunction> MakeFunction(
dart::Zone* zone,
dart::SExpression* sexpr,
const llvm::StringMap<const DartValue*>& env);