blob: 504985023ca9923c5421604404d59aa74ba8e2f0 [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.
#error "AOT runtime should not use compiler sources (including header files)"
#include "platform/assert.h"
#include "vm/allocation.h"
#include "vm/compiler/backend/flow_graph.h"
#include "vm/compiler/backend/il.h"
#include "vm/compiler/backend/sexpression.h"
#include "vm/compiler/compiler_pass.h"
#include "vm/object.h"
#include "vm/parser.h"
#include "vm/thread.h"
#include "vm/zone.h"
namespace dart {
// Deserializes FlowGraphs from S-expressions.
class FlowGraphDeserializer : ValueObject {
// Adds to the given array all the instructions in the flow graph that are
// guaranteed not to be handled by the current implementation of the
// FlowGraphDeserializer. This way, we can filter out graphs that are
// guaranteed not to be deserializable before going through the round-trip
// serialization process.
// Note that there may be other reasons that the deserializer may fail on
// a given flow graph, so no new members of the array is necessary, but not
// sufficient, for a successful round-trip pass.
static void AllUnhandledInstructions(const FlowGraph* graph,
GrowableArray<Instruction*>* out);
// Takes the FlowGraph from [state] and runs it through the serializer
// and deserializer. If the deserializer successfully deserializes the
// graph, then the FlowGraph in [state] is replaced with the new one.
static void RoundTripSerialization(CompilerPassState* state);
FlowGraphDeserializer(Thread* thread,
Zone* zone,
SExpression* root,
const ParsedFunction* pf = nullptr)
: thread_(ASSERT_NOTNULL(thread)),
tmp_string_(String::Handle(zone)) {
// See canonicalization comment in ParseDartValue as to why this is
// currently necessary.
ASSERT(thread->zone() == zone);
// Walks [root_sexp_] and constructs a new FlowGraph.
FlowGraph* ParseFlowGraph();
const char* error_message() const { return error_message_; }
SExpression* error_sexp() const { return error_sexp_; }
// Prints the current error information to stderr and aborts.
DART_NORETURN void ReportError() const;
M(FunctionEntry) \
M(GraphEntry) \
M(JoinEntry) \
M(AllocateObject) \
M(AssertAssignable) \
M(AssertBoolean) \
M(BooleanNegate) \
M(Branch) \
M(CheckNull) \
M(CheckStackOverflow) \
M(Constant) \
M(DebugStepCheck) \
M(Goto) \
M(InstanceCall) \
M(LoadClassId) \
M(LoadField) \
M(NativeCall) \
M(Parameter) \
M(Return) \
M(SpecialParameter) \
M(StaticCall) \
M(StoreInstanceField) \
M(StrictCompare) \
// Helper methods for AllUnhandledInstructions.
static bool IsHandledInstruction(Instruction* inst);
static bool IsHandledConstant(const Object& obj);
// For functions that take an SExpression or a subclass, they should return
// an error signal (false, nullptr, etc.) without changing the error state if
// passed in nullptr. This way, methods can be chained without intermediate
// checking.
// Also, for parsing methods for expressions that are known to be of a certain
// form, they will take the appropriate subclass of SExpression and assume
// that the form was already pre-checked by the caller. For forms that are
// tagged lists, this includes the fact that there is at least one element
// and the first element is a symbol. If the form can only have one possible
// tag, they also assume the tag has already been checked.
// Helper functions that do length/key exists checking and also check that
// the retrieved element is not nullptr. Notably, do not use these if the
// retrieved element is optional, to avoid changing the error state
// unnecessarily.
SExpression* Retrieve(SExpList* list, intptr_t index);
SExpression* Retrieve(SExpList* list, const char* key);
bool ParseConstantPool(SExpList* pool);
bool ParseEntries(SExpList* list);
using BlockWorklist = GrowableArray<intptr_t>;
// Starts parsing the contents of [list], where the blocks begin at position
// [pos] and [worklist] contains the blocks whose body instructions should
// be parsed first.
bool ParseBlocks(SExpList* list, intptr_t pos, BlockWorklist* worklist);
// Block parsing is split into two passes. This pass adds function entries
// to the flow graph and also parses initial definitions found in the Entries
// list. The block is added to the [block_map_] before returning.
BlockEntryInstr* ParseBlockHeader(SExpList* list,
intptr_t block_id,
SExpSymbol* tag);
// Expects [current_block_] to be set before calling.
bool ParseInitialDefinitions(SExpList* list);
// Expects [current_block_] to be set before calling.
// Takes the tagged list to parse and the index where parsing should start.
// Attempts to parse Phi definitions until the first non-Phi instruction.
bool ParsePhis(SExpList* list);
// Expects [current_block_] to be set before calling.
// Returns the position of the first non-Phi instruction in a block.
intptr_t SkipPhis(SExpList* list);
// Parses the deopt environment, Phi definitions for JoinEntrys, and the
// instructions in the body of the block. Adds the IDs of the block successors
// to the worklist, if any. [current_block_] and [pushed_stack_] must be set
// before calling.
bool ParseBlockContents(SExpList* list, BlockWorklist* worklist);
// Helper function used by ParseConstantPool, ParsePhis, and ParseDefinition.
// This handles all the extra information stored in (def ...) expressions,
// and also ensures the index of the definition is appropriately adjusted to
// match those found in the serialized form.
bool ParseDefinitionWithParsedBody(SExpList* list, Definition* def);
Definition* ParseDefinition(SExpList* list);
Instruction* ParseInstruction(SExpList* list);
struct EntryInfo {
intptr_t block_id;
intptr_t try_index;
intptr_t deopt_id;
#define HANDLER_DECL(name) \
name##Instr* Deserialize##name(SExpList* list, const EntryInfo& info);
struct InstrInfo {
const intptr_t deopt_id;
const InstructionSource source;
enum HandledInstruction {
#define HANDLED_INST_DECL(name) kHandled##name,
// clang-format off
kHandledInvalid = -1,
// clang-format on
#define HANDLE_CASE(name) \
if (strcmp(tag->value(), #name) == 0) return kHandled##name;
HandledInstruction HandledInstructionForTag(SExpSymbol* tag) {
ASSERT(tag != nullptr);
return kHandledInvalid;
#define HANDLER_DECL(name) \
name##Instr* Deserialize##name(SExpList* list, const InstrInfo& info);
// Common information parsed from call instruction S-expressions.
struct CallInfo : public ValueObject {
explicit CallInfo(Zone* zone) : argument_names(Array::ZoneHandle(zone)) {}
Array& argument_names;
intptr_t type_args_len = 0;
intptr_t args_len = 0;
InputsArray* inputs = nullptr;
CompileType* result_type = nullptr;
Code::EntryKind entry_kind = Code::EntryKind::kNormal;
// Helper function for parsing call instructions that returns a structure
// of information common to all calls.
bool ParseCallInfo(SExpList* call,
CallInfo* out,
intptr_t num_extra_inputs = 0);
// Parses [sexp] as a value form, that is, either the binding name for
// a definition as a symbol or the form (value <name> { ... }).
// If [allow_pending], then values for definitions not already in the
// [definition_map_] will be added to the [values_map_], otherwise,
// values for definitions not yet seen cause an error to be stored and
// nullptr to be returned.
Value* ParseValue(SExpression* sexp, bool allow_pending = true);
CompileType* ParseCompileType(SExpList* list);
// Parses [list] as an environment form: a list containing either binding
// names for definitions or a# for pushed arguments (where # is the depth
// of the argument from the top of the stack). Requires [pushed_stack_] to
// be set if any references to pushed arguments are found.
Environment* ParseEnvironment(SExpList* list);
// Parsing functions for which there are no good distinguished error
// values, so use out parameters and a boolean return instead.
// Parses a Dart value and returns a canonicalized result.
bool ParseDartValue(SExpression* sexp, Object* out);
// Canonicalizes and replaces the original contents of the handle pointed to
// by [inst] if [inst] is an Instance (if not, it trivially succeeds). The
// replacement happens whether successful or not. [sexp] is the SExpression
// to be used for error reporting.
bool CanonicalizeInstance(SExpression* sexp, Object* inst);
// Helper functions for ParseDartValue for parsing particular type of values.
// If necessary, they canonicalize the returned value, and so may be used
// directly by other code as well. Helpers that take SExpression* take either
// serialized constants or references to constant definitions.
// Due to particulars of operator=() on non-Object values, for a given X,
// ParseX takes Object* instead of X* for the out parameter.
bool ParseAbstractType(SExpression* sexp, Object* out);
bool ParseClass(SExpList* list, Object* out);
bool ParseClosure(SExpList* list, Object* out);
bool ParseField(SExpList* list, Object* out);
bool ParseFunction(SExpList* list, Object* out);
bool ParseSignature(SExpList* list, Object* out);
bool ParseArray(SExpList* list, Object* out);
bool ParseImmutableList(SExpList* list, Object* out);
bool ParseInstance(SExpList* list, Object* out);
bool ParseType(SExpression* sexp, Object* out);
bool ParseFunctionType(SExpList* list, Object* out);
bool ParseTypeParameter(SExpList* list, Object* out);
bool ParseTypeArguments(SExpression* sexp, Object* out);
bool ParseTypeRef(SExpList* list, Object* out);
bool ParseCanonicalName(SExpSymbol* sym, Object* out);
const Field& MayCloneField(const Field& field) const;
bool ParseSlot(SExpList* list, const Slot** out);
bool ParseRange(SExpList* list, Range* out);
bool ParseRangeBoundary(SExpression* sexp, RangeBoundary* out);
bool ParseBlockId(SExpSymbol* sym, intptr_t* out);
bool ParseSSATemp(SExpSymbol* sym, intptr_t* out);
bool ParseUse(SExpSymbol* sym, intptr_t* out);
bool ParseSymbolAsPrefixedInt(SExpSymbol* sym, char prefix, intptr_t* out);
bool ArePendingTypeRefs() const;
// Allocates a new ICData structure. [list] is the ICData S-expression, while
// [inst] is the Instruction generated from the instruction S-expression
// containing [list].
bool CreateICData(SExpList* list, Instruction* inst);
// Helper function for creating a placeholder value when the definition
// with index [i] has not yet been seen. If [inherit_type], then the type of
// the definition should be used as the reaching type for the use. [s] is used
// for any errors that occur when resolving the pending value.
Value* AddNewPendingValue(SExpression* s, intptr_t i, bool inherit_type);
// Helper function for rebinding values pending on this definition.
bool FixPendingValues(intptr_t index, Definition* def);
// Retrieves the block corresponding to the given block ID symbol from
// [block_map_]. Assumes all blocks have had their header parsed.
BlockEntryInstr* FetchBlock(SExpSymbol* sym);
// Utility functions for checking the shape of an S-expression.
// If these functions return nullptr for a non-null argument, they have the
// side effect of setting the stored error message.
#define BASE_CHECK_DECL(name, type) SExp##name* Check##name(SExpression* sexp);
// Checks whether [sexp] is a symbol with the given label.
bool IsTag(SExpression* sexp, const char* label);
// A version of CheckList that also checks that the list has at least one
// element and that the first element is a symbol. If [label] is non-null,
// then the initial symbol element is checked against it.
SExpList* CheckTaggedList(SExpression* sexp, const char* label = nullptr);
// Stores appropriate error information using the SExpression as the location
// and the rest of the arguments as an error message for the user.
void StoreError(SExpression* s, const char* fmt, ...) PRINTF_ATTRIBUTE(3, 4);
Thread* thread() const { return thread_; }
Zone* zone() const { return zone_; }
Thread* const thread_;
Zone* const zone_;
SExpression* const root_sexp_;
const ParsedFunction* parsed_function_;
FlowGraph* flow_graph_ = nullptr;
BlockEntryInstr* current_block_ = nullptr;
intptr_t max_block_id_ = -1;
intptr_t max_ssa_index_ = -1;
// Map from block IDs to blocks. Does not contain an entry for block 0
// (the graph entry), since it is only used at known points and is already
// available via [flow_graph_].
IntMap<BlockEntryInstr*> block_map_;
// Map from variable indexes to definitions.
IntMap<Definition*> definition_map_;
// Information needed to handle uses seen prior to their definitions.
struct PendingValue {
// SExpression used for error reporting.
SExpression* sexp;
// Value to be rebound once the right definition is found.
Value* value;
// Whether the type should inherit the type of the found definition.
bool inherit_type;
// Map from variable indices to lists of values. The list of values are
// values that were parsed prior to the corresponding definition being found.
IntMap<ZoneGrowableArray<PendingValue>*> values_map_;
// Map from hash values to SExpLists. This is used by ParseTypeRef to
// determine whether or not the recursive type it refers to is being currently
// built. The SExpList can be used to report hash collisions.
IntMap<SExpList*> recursive_types_map_;
// Map from hash values to arrays of TypeRefs. This is used by ParseType and
// ParseTypeRef to store and later fill in TypeRefs pending on the type being
// constructed. Since entries are added at the start of parsing recursive
// Type S-exps and removed before the resulting Type is successfully returned,
// this map should be empty outside of parsing recursive types.
IntMap<ZoneGrowableArray<TypeRef*>*> pending_typeref_map_;
// Temporary handles used by functions that are not re-entrant or where the
// handle is not live after the re-entrant call. Comments show which handles
// are expected to only be used within a single method.
TypeArguments& array_type_args_; // ParseImmutableList
Class& instance_class_; // ParseInstance
Field& instance_field_; // ParseInstance
Array& instance_fields_array_; // ParseInstance
TypeArguments& instance_type_args_; // ParseInstance
Class& name_class_; // ParseCanonicalName
Field& name_field_; // ParseCanonicalName
Function& name_function_; // ParseCanonicalName
Library& name_library_; // ParseCanonicalName
Class& type_class_; // ParseType
Class& type_param_class_; // ParseTypeParameter
// Uses of string handles tend to be immediate, so we only need one.
String& tmp_string_;
// Stores a message appropriate to surfacing to the user when an error
// occurs.
const char* error_message_ = nullptr;
// Stores the location of the deserialization error by containing the
// S-expression which caused the failure.
SExpression* error_sexp_ = nullptr;
} // namespace dart