1// Copyright (c) 2017, 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#include "vm/compiler/frontend/prologue_builder.h"
6
7#include "vm/compiler/backend/il.h"
8#include "vm/compiler/backend/il_printer.h"
9#include "vm/compiler/frontend/base_flow_graph_builder.h"
10#include "vm/compiler/jit/compiler.h"
11#include "vm/kernel_loader.h"
12#include "vm/longjump.h"
13#include "vm/object_store.h"
14#include "vm/report.h"
15#include "vm/resolver.h"
16#include "vm/stack_frame.h"
17
18namespace dart {
19namespace kernel {
20
21#define Z (zone_)
22
23// Returns static type of the parameter if it can be trusted (was type checked
24// by caller) and dynamic otherwise.
25static CompileType ParameterType(LocalVariable* param,
26 Representation representation = kTagged) {
27 return param->was_type_checked_by_caller()
28 ? CompileType::FromAbstractType(param->type(),
29 representation == kTagged)
30 : ((representation == kTagged)
31 ? CompileType::Dynamic()
32 : CompileType::FromCid(kDynamicCid).CopyNonNullable());
33}
34
35bool PrologueBuilder::PrologueSkippableOnUncheckedEntry(
36 const Function& function) {
37 return !function.HasOptionalParameters() &&
38 !function.IsNonImplicitClosureFunction() && !function.IsGeneric();
39}
40
41bool PrologueBuilder::HasEmptyPrologue(const Function& function) {
42 return !function.HasOptionalParameters() && !function.IsGeneric() &&
43 !function.CanReceiveDynamicInvocation() &&
44 !function.IsClosureFunction();
45}
46
47BlockEntryInstr* PrologueBuilder::BuildPrologue(BlockEntryInstr* entry,
48 PrologueInfo* prologue_info) {
49 // We always have to build the graph, but we only link it sometimes.
50 const bool link = !is_inlining_ && !compiling_for_osr_;
51
52 const intptr_t previous_block_id = last_used_block_id_;
53
54 const bool load_optional_arguments = function_.HasOptionalParameters();
55 const bool expect_type_args = function_.IsGeneric();
56 const bool check_arguments = function_.CanReceiveDynamicInvocation();
57
58 Fragment prologue = Fragment(entry);
59 JoinEntryInstr* nsm = NULL;
60 if (load_optional_arguments || check_arguments || expect_type_args) {
61 nsm = BuildThrowNoSuchMethod();
62 }
63 if (check_arguments) {
64 Fragment f = BuildTypeArgumentsLengthCheck(nsm, expect_type_args);
65 if (link) prologue += f;
66 }
67 if (load_optional_arguments) {
68 Fragment f = BuildOptionalParameterHandling(
69 nsm, parsed_function_->expression_temp_var());
70 if (link) prologue += f;
71 } else if (check_arguments) {
72 Fragment f = BuildFixedParameterLengthChecks(nsm);
73 if (link) prologue += f;
74 }
75 if (function_.IsClosureFunction()) {
76 Fragment f = BuildClosureContextHandling();
77 if (!compiling_for_osr_) prologue += f;
78 }
79 if (expect_type_args) {
80 Fragment f = BuildTypeArgumentsHandling(nsm);
81 if (link) prologue += f;
82 }
83
84 const bool is_empty_prologue = prologue.entry == prologue.current;
85 // Double-check we create empty prologues when HasEmptyPrologue returns true.
86 ASSERT(!HasEmptyPrologue(function_) || is_empty_prologue);
87
88 // Always do this to preserve deoptid numbering.
89 JoinEntryInstr* normal_code = BuildJoinEntry();
90 Fragment jump_to_normal_code = Goto(normal_code);
91
92 if (is_empty_prologue) {
93 *prologue_info = PrologueInfo(-1, -1);
94 return entry;
95 } else {
96 prologue += jump_to_normal_code;
97 *prologue_info =
98 PrologueInfo(previous_block_id, normal_code->block_id() - 1);
99 return normal_code;
100 }
101}
102
103Fragment PrologueBuilder::BuildTypeArgumentsLengthCheck(JoinEntryInstr* nsm,
104 bool expect_type_args) {
105 Fragment check_type_args;
106 JoinEntryInstr* done = BuildJoinEntry();
107
108 // Type args are always optional, so length can always be zero.
109 // If expect_type_args, a non-zero length must match the declaration length.
110 TargetEntryInstr *then, *fail;
111 check_type_args += LoadArgDescriptor();
112 check_type_args += LoadNativeField(Slot::ArgumentsDescriptor_type_args_len());
113 if (expect_type_args) {
114 JoinEntryInstr* join2 = BuildJoinEntry();
115
116 LocalVariable* len = MakeTemporary();
117
118 TargetEntryInstr* otherwise;
119 check_type_args += LoadLocal(len);
120 check_type_args += IntConstant(0);
121 check_type_args += BranchIfEqual(&then, &otherwise);
122
123 TargetEntryInstr* then2;
124 Fragment check_len(otherwise);
125 check_len += LoadLocal(len);
126 check_len += IntConstant(function_.NumTypeParameters());
127 check_len += BranchIfEqual(&then2, &fail);
128
129 Fragment(then) + Goto(join2);
130 Fragment(then2) + Goto(join2);
131
132 Fragment(join2) + Drop() + Goto(done);
133 Fragment(fail) + Goto(nsm);
134 } else {
135 check_type_args += IntConstant(0);
136 check_type_args += BranchIfEqual(&then, &fail);
137 Fragment(then) + Goto(done);
138 Fragment(fail) + Goto(nsm);
139 }
140
141 return Fragment(check_type_args.entry, done);
142}
143
144Fragment PrologueBuilder::BuildOptionalParameterHandling(
145 JoinEntryInstr* nsm,
146 LocalVariable* temp_var) {
147 Fragment copy_args_prologue;
148 const int num_fixed_params = function_.num_fixed_parameters();
149 const int num_opt_pos_params = function_.NumOptionalPositionalParameters();
150 const int num_opt_named_params = function_.NumOptionalNamedParameters();
151 const int num_params =
152 num_fixed_params + num_opt_pos_params + num_opt_named_params;
153 ASSERT(function_.NumParameters() == num_params);
154 const intptr_t fixed_params_size =
155 FlowGraph::ParameterOffsetAt(function_, num_params, /*last_slot=*/false) -
156 num_opt_named_params - num_opt_pos_params;
157
158 // Check that min_num_pos_args <= num_pos_args <= max_num_pos_args,
159 // where num_pos_args is the number of positional arguments passed in.
160 const int min_num_pos_args = num_fixed_params;
161 const int max_num_pos_args = num_fixed_params + num_opt_pos_params;
162
163 copy_args_prologue += LoadArgDescriptor();
164 copy_args_prologue +=
165 LoadNativeField(Slot::ArgumentsDescriptor_positional_count());
166 LocalVariable* positional_count_var = MakeTemporary();
167
168 copy_args_prologue += LoadArgDescriptor();
169 copy_args_prologue += LoadNativeField(Slot::ArgumentsDescriptor_count());
170 LocalVariable* count_var = MakeTemporary();
171
172 // Ensure the caller provided at least [min_num_pos_args] arguments.
173 copy_args_prologue += IntConstant(min_num_pos_args);
174 copy_args_prologue += LoadLocal(positional_count_var);
175 copy_args_prologue += SmiRelationalOp(Token::kLTE);
176 TargetEntryInstr *success1, *fail1;
177 copy_args_prologue += BranchIfTrue(&success1, &fail1);
178 copy_args_prologue = Fragment(copy_args_prologue.entry, success1);
179
180 // Ensure the caller provided at most [max_num_pos_args] arguments.
181 copy_args_prologue += LoadLocal(positional_count_var);
182 copy_args_prologue += IntConstant(max_num_pos_args);
183 copy_args_prologue += SmiRelationalOp(Token::kLTE);
184 TargetEntryInstr *success2, *fail2;
185 copy_args_prologue += BranchIfTrue(&success2, &fail2);
186 copy_args_prologue = Fragment(copy_args_prologue.entry, success2);
187
188 // Link up the argument check failing code.
189 Fragment(fail1) + Goto(nsm);
190 Fragment(fail2) + Goto(nsm);
191
192 copy_args_prologue += LoadLocal(count_var);
193 copy_args_prologue += IntConstant(min_num_pos_args);
194 copy_args_prologue += SmiBinaryOp(Token::kSUB, /* truncate= */ true);
195 LocalVariable* optional_count_var = MakeTemporary();
196
197 // Copy mandatory parameters down.
198 intptr_t param = 0;
199 intptr_t param_offset = -1;
200
201 const auto update_param_offset = [&param_offset](const Function& function,
202 intptr_t param_id) {
203 if (param_id < 0) {
204 // Type arguments of Factory constructor is processed with parameters
205 param_offset++;
206 return;
207 }
208
209 // update parameter offset
210 if (function.is_unboxed_integer_parameter_at(param_id)) {
211 param_offset += compiler::target::kIntSpillFactor;
212 } else if (function.is_unboxed_double_parameter_at(param_id)) {
213 param_offset += compiler::target::kDoubleSpillFactor;
214 } else {
215 ASSERT(!function.is_unboxed_parameter_at(param_id));
216 // Tagged parameters always occupy one word
217 param_offset++;
218 }
219 };
220
221 for (; param < num_fixed_params; ++param) {
222 const intptr_t param_index = param - (function_.IsFactory() ? 1 : 0);
223 update_param_offset(function_, param_index);
224
225 const auto representation =
226 ((param_index >= 0)
227 ? FlowGraph::ParameterRepresentationAt(function_, param_index)
228 : kTagged);
229
230 copy_args_prologue += LoadLocal(optional_count_var);
231 copy_args_prologue += LoadFpRelativeSlot(
232 compiler::target::kWordSize *
233 (compiler::target::frame_layout.param_end_from_fp +
234 fixed_params_size - param_offset),
235 ParameterType(ParameterVariable(param), representation),
236 representation);
237 copy_args_prologue +=
238 StoreLocalRaw(TokenPosition::kNoSource, ParameterVariable(param));
239 copy_args_prologue += Drop();
240 }
241
242 // Copy optional parameters down.
243 if (num_opt_pos_params > 0) {
244 JoinEntryInstr* next_missing = NULL;
245 for (intptr_t opt_param = 1; param < num_params; ++param, ++opt_param) {
246 const intptr_t param_index = param - (function_.IsFactory() ? 1 : 0);
247 update_param_offset(function_, param_index);
248
249 TargetEntryInstr *supplied, *missing;
250 copy_args_prologue += IntConstant(opt_param);
251 copy_args_prologue += LoadLocal(optional_count_var);
252 copy_args_prologue += SmiRelationalOp(Token::kLTE);
253 copy_args_prologue += BranchIfTrue(&supplied, &missing);
254
255 Fragment good(supplied);
256 good += LoadLocal(optional_count_var);
257 good += LoadFpRelativeSlot(
258 compiler::target::kWordSize *
259 (compiler::target::frame_layout.param_end_from_fp +
260 fixed_params_size - param_offset),
261 ParameterType(ParameterVariable(param)));
262 good += StoreLocalRaw(TokenPosition::kNoSource, ParameterVariable(param));
263 good += Drop();
264
265 Fragment not_good(missing);
266 if (next_missing != NULL) {
267 not_good += Goto(next_missing);
268 not_good.current = next_missing;
269 }
270 next_missing = BuildJoinEntry();
271 not_good += Constant(DefaultParameterValueAt(opt_param - 1));
272 not_good +=
273 StoreLocalRaw(TokenPosition::kNoSource, ParameterVariable(param));
274 not_good += Drop();
275 not_good += Goto(next_missing);
276
277 copy_args_prologue.current = good.current;
278 }
279 copy_args_prologue += Goto(next_missing /* join good/not_good flows */);
280 copy_args_prologue.current = next_missing;
281
282 // If there are more arguments from the caller we haven't processed, go
283 // NSM.
284 TargetEntryInstr *done, *unknown_named_arg_passed;
285 copy_args_prologue += LoadLocal(positional_count_var);
286 copy_args_prologue += LoadLocal(count_var);
287 copy_args_prologue += BranchIfEqual(&done, &unknown_named_arg_passed);
288 copy_args_prologue.current = done;
289 {
290 Fragment f(unknown_named_arg_passed);
291 f += Goto(nsm);
292 }
293 } else {
294 ASSERT(num_opt_named_params > 0);
295
296 bool null_safety = Isolate::Current()->null_safety();
297 const intptr_t first_name_offset =
298 compiler::target::ArgumentsDescriptor::first_named_entry_offset() -
299 compiler::target::Array::data_offset();
300
301 // Start by alphabetically sorting the names of the optional parameters.
302 int* opt_param_position = Z->Alloc<int>(num_opt_named_params);
303 SortOptionalNamedParametersInto(opt_param_position, num_fixed_params,
304 num_params);
305
306 ASSERT(temp_var != nullptr);
307 LocalVariable* optional_count_vars_processed = temp_var;
308 copy_args_prologue += IntConstant(0);
309 copy_args_prologue +=
310 StoreLocalRaw(TokenPosition::kNoSource, optional_count_vars_processed);
311 copy_args_prologue += Drop();
312
313 for (intptr_t i = 0; param < num_params; ++param, ++i) {
314 copy_args_prologue += IntConstant(
315 compiler::target::ArgumentsDescriptor::named_entry_size() /
316 compiler::target::kWordSize);
317 copy_args_prologue += LoadLocal(optional_count_vars_processed);
318 copy_args_prologue += SmiBinaryOp(Token::kMUL, /* truncate= */ true);
319 LocalVariable* tuple_diff = MakeTemporary();
320
321 // name = arg_desc[names_offset + arg_desc_name_index + nameOffset]
322 copy_args_prologue += LoadArgDescriptor();
323 copy_args_prologue +=
324 IntConstant((first_name_offset +
325 compiler::target::ArgumentsDescriptor::name_offset()) /
326 compiler::target::kWordSize);
327 copy_args_prologue += LoadLocal(tuple_diff);
328 copy_args_prologue += SmiBinaryOp(Token::kADD, /* truncate= */ true);
329 copy_args_prologue +=
330 LoadIndexed(/* index_scale = */ compiler::target::kWordSize);
331
332 // first name in sorted list of all names
333 const String& param_name = String::ZoneHandle(
334 Z, function_.ParameterNameAt(opt_param_position[i]));
335 ASSERT(param_name.IsSymbol());
336 copy_args_prologue += Constant(param_name);
337
338 // Compare the two names: Note that the ArgumentDescriptor array always
339 // terminates with a "null" name (i.e. kNullCid), which will prevent us
340 // from running out-of-bounds.
341 TargetEntryInstr *supplied, *missing;
342 copy_args_prologue += BranchIfStrictEqual(&supplied, &missing);
343
344 // Join good/not_good.
345 JoinEntryInstr* join = BuildJoinEntry();
346
347 // Let's load position from arg descriptor (to see which parameter is the
348 // name) and move kEntrySize forward in ArgDescriptopr names array.
349 Fragment good(supplied);
350
351 {
352 // fp[target::frame_layout.param_end_from_fp + (count_var - pos)]
353 good += LoadLocal(count_var);
354 {
355 // pos = arg_desc[names_offset + arg_desc_name_index + positionOffset]
356 good += LoadArgDescriptor();
357 good += IntConstant(
358 (first_name_offset +
359 compiler::target::ArgumentsDescriptor::position_offset()) /
360 compiler::target::kWordSize);
361 good += LoadLocal(tuple_diff);
362 good += SmiBinaryOp(Token::kADD, /* truncate= */ true);
363 good += LoadIndexed(/* index_scale = */ compiler::target::kWordSize);
364 }
365 good += SmiBinaryOp(Token::kSUB, /* truncate= */ true);
366 good += LoadFpRelativeSlot(
367 compiler::target::kWordSize *
368 compiler::target::frame_layout.param_end_from_fp,
369 ParameterType(ParameterVariable(opt_param_position[i])));
370
371 // Copy down.
372 good += StoreLocalRaw(TokenPosition::kNoSource,
373 ParameterVariable(opt_param_position[i]));
374 good += Drop();
375
376 // Increase processed optional variable count.
377 good += LoadLocal(optional_count_vars_processed);
378 good += IntConstant(1);
379 good += SmiBinaryOp(Token::kADD, /* truncate= */ true);
380 good += StoreLocalRaw(TokenPosition::kNoSource,
381 optional_count_vars_processed);
382 good += Drop();
383
384 good += Goto(join);
385 }
386
387 // We had no match. If the param is required, throw a NoSuchMethod error.
388 // Otherwise just load the default constant.
389 Fragment not_good(missing);
390 if (null_safety && function_.IsRequiredAt(opt_param_position[i])) {
391 not_good += Goto(nsm);
392 } else {
393 not_good += Constant(
394 DefaultParameterValueAt(opt_param_position[i] - num_fixed_params));
395
396 // Copy down with default value.
397 not_good += StoreLocalRaw(TokenPosition::kNoSource,
398 ParameterVariable(opt_param_position[i]));
399 not_good += Drop();
400 not_good += Goto(join);
401 }
402
403 copy_args_prologue.current = join;
404 copy_args_prologue += Drop(); // tuple_diff
405 }
406
407 // If there are more arguments from the caller we haven't processed, go
408 // NSM.
409 TargetEntryInstr *done, *unknown_named_arg_passed;
410 copy_args_prologue += LoadLocal(optional_count_var);
411 copy_args_prologue += LoadLocal(optional_count_vars_processed);
412 copy_args_prologue += BranchIfEqual(&done, &unknown_named_arg_passed);
413 copy_args_prologue.current = done;
414
415 {
416 Fragment f(unknown_named_arg_passed);
417 f += Goto(nsm);
418 }
419 }
420
421 copy_args_prologue += Drop(); // optional_count_var
422 copy_args_prologue += Drop(); // count_var
423 copy_args_prologue += Drop(); // positional_count_var
424
425 return copy_args_prologue;
426}
427
428Fragment PrologueBuilder::BuildFixedParameterLengthChecks(JoinEntryInstr* nsm) {
429 Fragment check_args;
430 JoinEntryInstr* done = BuildJoinEntry();
431
432 check_args += LoadArgDescriptor();
433 check_args += LoadNativeField(Slot::ArgumentsDescriptor_count());
434 LocalVariable* count = MakeTemporary();
435
436 TargetEntryInstr *then, *fail;
437 check_args += LoadLocal(count);
438 check_args += IntConstant(function_.num_fixed_parameters());
439 check_args += BranchIfEqual(&then, &fail);
440
441 TargetEntryInstr *then2, *fail2;
442 Fragment check_len(then);
443 check_len += LoadArgDescriptor();
444 check_len += LoadNativeField(Slot::ArgumentsDescriptor_positional_count());
445 check_len += BranchIfEqual(&then2, &fail2);
446
447 Fragment(fail) + Goto(nsm);
448 Fragment(fail2) + Goto(nsm);
449 Fragment(then2) + Goto(done);
450
451 return Fragment(check_args.entry, done);
452}
453
454Fragment PrologueBuilder::BuildClosureContextHandling() {
455 LocalVariable* closure_parameter = parsed_function_->ParameterVariable(0);
456 LocalVariable* context = parsed_function_->current_context_var();
457
458 // Load closure.context & store it into the context variable.
459 // (both load/store happen on the copyied-down places).
460 Fragment populate_context;
461 populate_context += LoadLocal(closure_parameter);
462 populate_context += LoadNativeField(Slot::Closure_context());
463 populate_context += StoreLocal(TokenPosition::kNoSource, context);
464 populate_context += Drop();
465 return populate_context;
466}
467
468Fragment PrologueBuilder::BuildTypeArgumentsHandling(JoinEntryInstr* nsm) {
469 LocalVariable* type_args_var = parsed_function_->RawTypeArgumentsVariable();
470 ASSERT(type_args_var != nullptr);
471
472 Fragment handling;
473
474 Fragment store_type_args;
475 store_type_args += LoadArgDescriptor();
476 store_type_args += LoadNativeField(Slot::ArgumentsDescriptor_size());
477 store_type_args += LoadFpRelativeSlot(
478 compiler::target::kWordSize *
479 (1 + compiler::target::frame_layout.param_end_from_fp),
480 CompileType::CreateNullable(/*is_nullable=*/true, kTypeArgumentsCid));
481 store_type_args += StoreLocal(TokenPosition::kNoSource, type_args_var);
482 store_type_args += Drop();
483
484 Fragment store_null;
485 store_null += NullConstant();
486 store_null += StoreLocal(TokenPosition::kNoSource, type_args_var);
487 store_null += Drop();
488
489 handling += TestTypeArgsLen(store_null, store_type_args, 0);
490
491 if (parsed_function_->function().IsClosureFunction()) {
492 LocalVariable* closure = parsed_function_->ParameterVariable(0);
493
494 // Currently, delayed type arguments can only be introduced through type
495 // inference in the FE. So if they are present, we can assume they are
496 // correct in number and bound.
497 Fragment use_delayed_type_args;
498 use_delayed_type_args += LoadLocal(closure);
499 use_delayed_type_args +=
500 LoadNativeField(Slot::Closure_delayed_type_arguments());
501 use_delayed_type_args +=
502 StoreLocal(TokenPosition::kNoSource, type_args_var);
503 use_delayed_type_args += Drop();
504
505 handling += TestDelayedTypeArgs(
506 closure,
507 /*present=*/TestTypeArgsLen(use_delayed_type_args, Goto(nsm), 0),
508 /*absent=*/Fragment());
509 }
510
511 return handling;
512}
513
514void PrologueBuilder::SortOptionalNamedParametersInto(int* opt_param_position,
515 int num_fixed_params,
516 int num_params) {
517 String& name = String::Handle(Z);
518 String& name_i = String::Handle(Z);
519 for (int pos = num_fixed_params; pos < num_params; pos++) {
520 name = function_.ParameterNameAt(pos);
521 int i = pos - num_fixed_params;
522 while (--i >= 0) {
523 name_i = function_.ParameterNameAt(opt_param_position[i]);
524 const intptr_t result = name.CompareTo(name_i);
525 ASSERT(result != 0);
526 if (result > 0) break;
527 opt_param_position[i + 1] = opt_param_position[i];
528 }
529 opt_param_position[i + 1] = pos;
530 }
531}
532
533} // namespace kernel
534} // namespace dart
535