1// Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_COMPILER_BACKEND_IL_DESERIALIZER_H_
6#define RUNTIME_VM_COMPILER_BACKEND_IL_DESERIALIZER_H_
7
8#if defined(DART_PRECOMPILED_RUNTIME)
9#error "AOT runtime should not use compiler sources (including header files)"
10#endif // defined(DART_PRECOMPILED_RUNTIME)
11
12#include "platform/assert.h"
13
14#include "vm/allocation.h"
15#include "vm/compiler/backend/flow_graph.h"
16#include "vm/compiler/backend/il.h"
17#include "vm/compiler/backend/sexpression.h"
18#include "vm/compiler/compiler_pass.h"
19#include "vm/object.h"
20#include "vm/parser.h"
21#include "vm/thread.h"
22#include "vm/zone.h"
23
24namespace dart {
25
26// Deserializes FlowGraphs from S-expressions.
27class FlowGraphDeserializer : ValueObject {
28 public:
29 // Adds to the given array all the instructions in the flow graph that are
30 // guaranteed not to be handled by the current implementation of the
31 // FlowGraphDeserializer. This way, we can filter out graphs that are
32 // guaranteed not to be deserializable before going through the round-trip
33 // serialization process.
34 //
35 // Note that there may be other reasons that the deserializer may fail on
36 // a given flow graph, so no new members of the array is necessary, but not
37 // sufficient, for a successful round-trip pass.
38 static void AllUnhandledInstructions(const FlowGraph* graph,
39 GrowableArray<Instruction*>* out);
40
41 // Takes the FlowGraph from [state] and runs it through the serializer
42 // and deserializer. If the deserializer successfully deserializes the
43 // graph, then the FlowGraph in [state] is replaced with the new one.
44 static void RoundTripSerialization(CompilerPassState* state);
45
46 FlowGraphDeserializer(Thread* thread,
47 Zone* zone,
48 SExpression* root,
49 const ParsedFunction* pf = nullptr)
50 : thread_(ASSERT_NOTNULL(thread)),
51 zone_(ASSERT_NOTNULL(zone)),
52 root_sexp_(ASSERT_NOTNULL(root)),
53 parsed_function_(pf),
54 block_map_(zone),
55 definition_map_(zone),
56 values_map_(zone),
57 recursive_types_map_(zone),
58 pending_typeref_map_(zone),
59 array_type_args_(TypeArguments::Handle(zone)),
60 instance_class_(Class::Handle(zone)),
61 instance_field_(Field::Handle(zone)),
62 instance_fields_array_(Array::Handle(zone)),
63 instance_type_args_(TypeArguments::Handle(zone)),
64 name_class_(Class::Handle(zone)),
65 name_field_(Field::Handle(zone)),
66 name_function_(Function::Handle(zone)),
67 name_library_(Library::Handle(zone)),
68 type_class_(Class::Handle(zone)),
69 type_param_class_(Class::Handle(zone)),
70 type_param_function_(Function::Handle(zone)),
71 tmp_string_(String::Handle(zone)) {
72 // See canonicalization comment in ParseDartValue as to why this is
73 // currently necessary.
74 ASSERT(thread->zone() == zone);
75 }
76
77 // Walks [root_sexp_] and constructs a new FlowGraph.
78 FlowGraph* ParseFlowGraph();
79
80 const char* error_message() const { return error_message_; }
81 SExpression* error_sexp() const { return error_sexp_; }
82
83 // Prints the current error information to stderr and aborts.
84 DART_NORETURN void ReportError() const;
85
86 private:
87#define FOR_EACH_HANDLED_BLOCK_TYPE_IN_DESERIALIZER(M) \
88 M(FunctionEntry) \
89 M(GraphEntry) \
90 M(JoinEntry) \
91 M(TargetEntry)
92
93#define FOR_EACH_HANDLED_INSTRUCTION_IN_DESERIALIZER(M) \
94 M(AllocateObject) \
95 M(AssertAssignable) \
96 M(AssertBoolean) \
97 M(BooleanNegate) \
98 M(Branch) \
99 M(CheckNull) \
100 M(CheckStackOverflow) \
101 M(Constant) \
102 M(DebugStepCheck) \
103 M(Goto) \
104 M(InstanceCall) \
105 M(LoadClassId) \
106 M(LoadField) \
107 M(NativeCall) \
108 M(Parameter) \
109 M(Return) \
110 M(SpecialParameter) \
111 M(StaticCall) \
112 M(StoreInstanceField) \
113 M(StrictCompare) \
114 M(Throw)
115
116 // Helper methods for AllUnhandledInstructions.
117 static bool IsHandledInstruction(Instruction* inst);
118 static bool IsHandledConstant(const Object& obj);
119
120 // **GENERAL DESIGN NOTES FOR PARSING METHODS**
121 //
122 // For functions that take an SExpression or a subclass, they should return
123 // an error signal (false, nullptr, etc.) without changing the error state if
124 // passed in nullptr. This way, methods can be chained without intermediate
125 // checking.
126 //
127 // Also, for parsing methods for expressions that are known to be of a certain
128 // form, they will take the appropriate subclass of SExpression and assume
129 // that the form was already pre-checked by the caller. For forms that are
130 // tagged lists, this includes the fact that there is at least one element
131 // and the first element is a symbol. If the form can only have one possible
132 // tag, they also assume the tag has already been checked.
133
134 // Helper functions that do length/key exists checking and also check that
135 // the retrieved element is not nullptr. Notably, do not use these if the
136 // retrieved element is optional, to avoid changing the error state
137 // unnecessarily.
138 SExpression* Retrieve(SExpList* list, intptr_t index);
139 SExpression* Retrieve(SExpList* list, const char* key);
140
141 bool ParseConstantPool(SExpList* pool);
142 bool ParseEntries(SExpList* list);
143
144 using BlockWorklist = GrowableArray<intptr_t>;
145
146 // Starts parsing the contents of [list], where the blocks begin at position
147 // [pos] and [worklist] contains the blocks whose body instructions should
148 // be parsed first.
149 bool ParseBlocks(SExpList* list, intptr_t pos, BlockWorklist* worklist);
150
151 // Block parsing is split into two passes. This pass adds function entries
152 // to the flow graph and also parses initial definitions found in the Entries
153 // list. The block is added to the [block_map_] before returning.
154 BlockEntryInstr* ParseBlockHeader(SExpList* list,
155 intptr_t block_id,
156 SExpSymbol* tag);
157
158 // Expects [current_block_] to be set before calling.
159 bool ParseInitialDefinitions(SExpList* list);
160
161 // Expects [current_block_] to be set before calling.
162 // Takes the tagged list to parse and the index where parsing should start.
163 // Attempts to parse Phi definitions until the first non-Phi instruction.
164 bool ParsePhis(SExpList* list);
165
166 // Expects [current_block_] to be set before calling.
167 // Returns the position of the first non-Phi instruction in a block.
168 intptr_t SkipPhis(SExpList* list);
169
170 // Parses the deopt environment, Phi definitions for JoinEntrys, and the
171 // instructions in the body of the block. Adds the IDs of the block successors
172 // to the worklist, if any. [current_block_] and [pushed_stack_] must be set
173 // before calling.
174 bool ParseBlockContents(SExpList* list, BlockWorklist* worklist);
175
176 // Helper function used by ParseConstantPool, ParsePhis, and ParseDefinition.
177 // This handles all the extra information stored in (def ...) expressions,
178 // and also ensures the index of the definition is appropriately adjusted to
179 // match those found in the serialized form.
180 bool ParseDefinitionWithParsedBody(SExpList* list, Definition* def);
181
182 Definition* ParseDefinition(SExpList* list);
183 Instruction* ParseInstruction(SExpList* list);
184
185 struct EntryInfo {
186 intptr_t block_id;
187 intptr_t try_index;
188 intptr_t deopt_id;
189 };
190
191#define HANDLER_DECL(name) \
192 name##Instr* Deserialize##name(SExpList* list, const EntryInfo& info);
193
194 FOR_EACH_HANDLED_BLOCK_TYPE_IN_DESERIALIZER(HANDLER_DECL);
195
196#undef HANDLER_DECL
197
198 struct InstrInfo {
199 intptr_t deopt_id;
200 TokenPosition token_pos;
201 };
202
203 enum HandledInstruction {
204#define HANDLED_INST_DECL(name) kHandled##name,
205 FOR_EACH_HANDLED_INSTRUCTION_IN_DESERIALIZER(HANDLED_INST_DECL)
206#undef HANDLED_INST_DECL
207 // clang-format off
208 kHandledInvalid = -1,
209 // clang-format on
210 };
211
212#define HANDLE_CASE(name) \
213 if (strcmp(tag->value(), #name) == 0) return kHandled##name;
214 HandledInstruction HandledInstructionForTag(SExpSymbol* tag) {
215 ASSERT(tag != nullptr);
216 FOR_EACH_HANDLED_INSTRUCTION_IN_DESERIALIZER(HANDLE_CASE)
217 return kHandledInvalid;
218 }
219#undef HANDLE_CASE
220
221#define HANDLER_DECL(name) \
222 name##Instr* Deserialize##name(SExpList* list, const InstrInfo& info);
223
224 FOR_EACH_HANDLED_INSTRUCTION_IN_DESERIALIZER(HANDLER_DECL);
225
226#undef HANDLER_DECL
227
228 // Common information parsed from call instruction S-expressions.
229 struct CallInfo : public ValueObject {
230 explicit CallInfo(Zone* zone) : argument_names(Array::ZoneHandle(zone)) {}
231
232 Array& argument_names;
233 intptr_t type_args_len = 0;
234 intptr_t args_len = 0;
235 InputsArray* inputs = nullptr;
236 CompileType* result_type = nullptr;
237 Code::EntryKind entry_kind = Code::EntryKind::kNormal;
238 };
239
240 // Helper function for parsing call instructions that returns a structure
241 // of information common to all calls.
242 bool ParseCallInfo(SExpList* call,
243 CallInfo* out,
244 intptr_t num_extra_inputs = 0);
245
246 // Parses [sexp] as a value form, that is, either the binding name for
247 // a definition as a symbol or the form (value <name> { ... }).
248 // If [allow_pending], then values for definitions not already in the
249 // [definition_map_] will be added to the [values_map_], otherwise,
250 // values for definitions not yet seen cause an error to be stored and
251 // nullptr to be returned.
252 Value* ParseValue(SExpression* sexp, bool allow_pending = true);
253 CompileType* ParseCompileType(SExpList* list);
254
255 // Parses [list] as an environment form: a list containing either binding
256 // names for definitions or a# for pushed arguments (where # is the depth
257 // of the argument from the top of the stack). Requires [pushed_stack_] to
258 // be set if any references to pushed arguments are found.
259 Environment* ParseEnvironment(SExpList* list);
260
261 // Parsing functions for which there are no good distinguished error
262 // values, so use out parameters and a boolean return instead.
263
264 // Parses a Dart value and returns a canonicalized result.
265 bool ParseDartValue(SExpression* sexp, Object* out);
266
267 // Canonicalizes and replaces the original contents of the handle pointed to
268 // by [inst] if [inst] is an Instance (if not, it trivially succeeds). The
269 // replacement happens whether successful or not. [sexp] is the SExpression
270 // to be used for error reporting.
271 bool CanonicalizeInstance(SExpression* sexp, Object* inst);
272
273 // Helper functions for ParseDartValue for parsing particular type of values.
274 // If necessary, they canonicalize the returned value, and so may be used
275 // directly by other code as well. Helpers that take SExpression* take either
276 // serialized constants or references to constant definitions.
277 //
278 // Due to particulars of operator=() on non-Object values, for a given X,
279 // ParseX takes Object* instead of X* for the out parameter.
280 bool ParseAbstractType(SExpression* sexp, Object* out);
281 bool ParseClass(SExpList* list, Object* out);
282 bool ParseClosure(SExpList* list, Object* out);
283 bool ParseField(SExpList* list, Object* out);
284 bool ParseFunction(SExpList* list, Object* out);
285 bool ParseImmutableList(SExpList* list, Object* out);
286 bool ParseInstance(SExpList* list, Object* out);
287 bool ParseType(SExpression* sexp, Object* out);
288 bool ParseTypeParameter(SExpList* list, Object* out);
289 bool ParseTypeArguments(SExpression* sexp, Object* out);
290 bool ParseTypeRef(SExpList* list, Object* out);
291
292 bool ParseCanonicalName(SExpSymbol* sym, Object* out);
293
294 const Field& MayCloneField(const Field& field) const;
295 bool ParseSlot(SExpList* list, const Slot** out);
296 bool ParseRange(SExpList* list, Range* out);
297 bool ParseRangeBoundary(SExpression* sexp, RangeBoundary* out);
298
299 bool ParseBlockId(SExpSymbol* sym, intptr_t* out);
300 bool ParseSSATemp(SExpSymbol* sym, intptr_t* out);
301 bool ParseUse(SExpSymbol* sym, intptr_t* out);
302 bool ParseSymbolAsPrefixedInt(SExpSymbol* sym, char prefix, intptr_t* out);
303
304 bool ArePendingTypeRefs() const;
305
306 // Allocates a new ICData structure. [list] is the ICData S-expression, while
307 // [inst] is the Instruction generated from the instruction S-expression
308 // containing [list].
309 bool CreateICData(SExpList* list, Instruction* inst);
310
311 // Helper function for creating a placeholder value when the definition
312 // with index [i] has not yet been seen. If [inherit_type], then the type of
313 // the definition should be used as the reaching type for the use. [s] is used
314 // for any errors that occur when resolving the pending value.
315 Value* AddNewPendingValue(SExpression* s, intptr_t i, bool inherit_type);
316
317 // Helper function for rebinding values pending on this definition.
318 bool FixPendingValues(intptr_t index, Definition* def);
319
320 // Retrieves the block corresponding to the given block ID symbol from
321 // [block_map_]. Assumes all blocks have had their header parsed.
322 BlockEntryInstr* FetchBlock(SExpSymbol* sym);
323
324 // Utility functions for checking the shape of an S-expression.
325 // If these functions return nullptr for a non-null argument, they have the
326 // side effect of setting the stored error message.
327#define BASE_CHECK_DECL(name, type) SExp##name* Check##name(SExpression* sexp);
328 FOR_EACH_S_EXPRESSION(BASE_CHECK_DECL)
329#undef BASE_CHECK_DECL
330
331 // Checks whether [sexp] is a symbol with the given label.
332 bool IsTag(SExpression* sexp, const char* label);
333
334 // A version of CheckList that also checks that the list has at least one
335 // element and that the first element is a symbol. If [label] is non-null,
336 // then the initial symbol element is checked against it.
337 SExpList* CheckTaggedList(SExpression* sexp, const char* label = nullptr);
338
339 // Stores appropriate error information using the SExpression as the location
340 // and the rest of the arguments as an error message for the user.
341 void StoreError(SExpression* s, const char* fmt, ...) PRINTF_ATTRIBUTE(3, 4);
342
343 Thread* thread() const { return thread_; }
344 Zone* zone() const { return zone_; }
345
346 Thread* const thread_;
347 Zone* const zone_;
348 SExpression* const root_sexp_;
349 const ParsedFunction* parsed_function_;
350
351 FlowGraph* flow_graph_ = nullptr;
352 BlockEntryInstr* current_block_ = nullptr;
353 intptr_t max_block_id_ = -1;
354 intptr_t max_ssa_index_ = -1;
355
356 // Map from block IDs to blocks. Does not contain an entry for block 0
357 // (the graph entry), since it is only used at known points and is already
358 // available via [flow_graph_].
359 IntMap<BlockEntryInstr*> block_map_;
360
361 // Map from variable indexes to definitions.
362 IntMap<Definition*> definition_map_;
363
364 // Information needed to handle uses seen prior to their definitions.
365 struct PendingValue {
366 // SExpression used for error reporting.
367 SExpression* sexp;
368 // Value to be rebound once the right definition is found.
369 Value* value;
370 // Whether the type should inherit the type of the found definition.
371 bool inherit_type;
372 };
373
374 // Map from variable indices to lists of values. The list of values are
375 // values that were parsed prior to the corresponding definition being found.
376 IntMap<ZoneGrowableArray<PendingValue>*> values_map_;
377
378 // Map from hash values to SExpLists. This is used by ParseTypeRef to
379 // determine whether or not the recursive type it refers to is being currently
380 // built. The SExpList can be used to report hash collisions.
381 IntMap<SExpList*> recursive_types_map_;
382
383 // Map from hash values to arrays of TypeRefs. This is used by ParseType and
384 // ParseTypeRef to store and later fill in TypeRefs pending on the type being
385 // constructed. Since entries are added at the start of parsing recursive
386 // Type S-exps and removed before the resulting Type is successfully returned,
387 // this map should be empty outside of parsing recursive types.
388 IntMap<ZoneGrowableArray<TypeRef*>*> pending_typeref_map_;
389
390 // Temporary handles used by functions that are not re-entrant or where the
391 // handle is not live after the re-entrant call. Comments show which handles
392 // are expected to only be used within a single method.
393 TypeArguments& array_type_args_; // ParseImmutableList
394 Class& instance_class_; // ParseInstance
395 Field& instance_field_; // ParseInstance
396 Array& instance_fields_array_; // ParseInstance
397 TypeArguments& instance_type_args_; // ParseInstance
398 Class& name_class_; // ParseCanonicalName
399 Field& name_field_; // ParseCanonicalName
400 Function& name_function_; // ParseCanonicalName
401 Library& name_library_; // ParseCanonicalName
402 Class& type_class_; // ParseType
403 Class& type_param_class_; // ParseTypeParameter
404 Function& type_param_function_; // ParseTypeParameter
405 // Uses of string handles tend to be immediate, so we only need one.
406 String& tmp_string_;
407
408 // Stores a message appropriate to surfacing to the user when an error
409 // occurs.
410 const char* error_message_ = nullptr;
411 // Stores the location of the deserialization error by containing the
412 // S-expression which caused the failure.
413 SExpression* error_sexp_ = nullptr;
414
415 DISALLOW_COPY_AND_ASSIGN(FlowGraphDeserializer);
416};
417
418} // namespace dart
419
420#endif // RUNTIME_VM_COMPILER_BACKEND_IL_DESERIALIZER_H_
421