1	// Copyright (c) 2012, 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/backend/flow_graph.h"
6
7	#include "vm/bit_vector.h"
8	#include "vm/compiler/backend/flow_graph_compiler.h"
9	#include "vm/compiler/backend/il.h"
10	#include "vm/compiler/backend/il_printer.h"
11	#include "vm/compiler/backend/loops.h"
12	#include "vm/compiler/backend/range_analysis.h"
13	#include "vm/compiler/cha.h"
14	#include "vm/compiler/compiler_state.h"
15	#include "vm/compiler/compiler_timings.h"
16	#include "vm/compiler/frontend/flow_graph_builder.h"
17	#include "vm/compiler/frontend/kernel_translation_helper.h"
18	#include "vm/growable_array.h"
19	#include "vm/object_store.h"
20	#include "vm/resolver.h"
21
22	namespace dart {
23
24	#if defined(TARGET_ARCH_ARM) || defined(TARGET_ARCH_IA32)
25	// Smi->Int32 widening pass is disabled due to dartbug.com/32619.
26	DEFINE_FLAG(bool, use_smi_widening, false, "Enable Smi->Int32 widening pass.");
27	DEFINE_FLAG(bool, trace_smi_widening, false, "Trace Smi->Int32 widening pass.");
28	#endif
29	DEFINE_FLAG(bool, prune_dead_locals, true, "optimize dead locals away");
30
31	// Quick access to the current zone.
32	#define Z (zone())
33
34	FlowGraph::FlowGraph(const ParsedFunction& parsed_function,
35	GraphEntryInstr* graph_entry,
36	intptr_t max_block_id,
37	PrologueInfo prologue_info)
38	: thread_(Thread::Current()),
39	parent_(),
40	current_ssa_temp_index_(0),
41	max_block_id_(max_block_id),
42	parsed_function_(parsed_function),
43	num_direct_parameters_(parsed_function.function().MakesCopyOfParameters()
44	? 0
45	: parsed_function.function().NumParameters()),
46	direct_parameters_size_(0),
47	graph_entry_(graph_entry),
48	preorder_(),
49	postorder_(),
50	reverse_postorder_(),
51	optimized_block_order_(),
52	constant_null_(nullptr),
53	constant_dead_(nullptr),
54	licm_allowed_(true),
55	prologue_info_(prologue_info),
56	loop_hierarchy_(nullptr),
57	loop_invariant_loads_(nullptr),
58	captured_parameters_(new(zone()) BitVector(zone(), variable_count())),
59	inlining_id_(-1),
60	should_print_(false) {
61	should_print_ = FlowGraphPrinter::ShouldPrint(function: parsed_function.function(),
62	compiler_pass_filter: &compiler_pass_filters_);
63
64	direct_parameters_size_ = ParameterOffsetAt(
65	function: function(), index: num_direct_parameters_, /*last_slot*/ false);
66	DiscoverBlocks();
67	}
68
69	void FlowGraph::EnsureSSATempIndex(Definition* defn, Definition* replacement) {
70	if ((replacement->ssa_temp_index() == -1) && (defn->ssa_temp_index() != -1)) {
71	AllocateSSAIndex(def: replacement);
72	}
73	}
74
75	intptr_t FlowGraph::ParameterOffsetAt(const Function& function,
76	intptr_t index,
77	bool last_slot /*=true*/) {
78	ASSERT(index <= function.NumParameters());
79	intptr_t param_offset = 0;
80	for (intptr_t i = 0; i < index; i++) {
81	if (function.is_unboxed_integer_parameter_at(index: i)) {
82	param_offset += compiler::target::kIntSpillFactor;
83	} else if (function.is_unboxed_double_parameter_at(index: i)) {
84	param_offset += compiler::target::kDoubleSpillFactor;
85	} else {
86	ASSERT(!function.is_unboxed_parameter_at(i));
87	// Unboxed parameters always occupy one word
88	param_offset++;
89	}
90	}
91	if (last_slot) {
92	ASSERT(index < function.NumParameters());
93	if (function.is_unboxed_double_parameter_at(index) &&
94	compiler::target::kDoubleSpillFactor > 1) {
95	ASSERT(compiler::target::kDoubleSpillFactor == 2);
96	param_offset++;
97	} else if (function.is_unboxed_integer_parameter_at(index) &&
98	compiler::target::kIntSpillFactor > 1) {
99	ASSERT(compiler::target::kIntSpillFactor == 2);
100	param_offset++;
101	}
102	}
103	return param_offset;
104	}
105
106	Representation FlowGraph::ParameterRepresentationAt(const Function& function,
107	intptr_t index) {
108	if (function.IsNull()) {
109	return kTagged;
110	}
111	ASSERT(index < function.NumParameters());
112	if (function.is_unboxed_integer_parameter_at(index)) {
113	return kUnboxedInt64;
114	} else if (function.is_unboxed_double_parameter_at(index)) {
115	return kUnboxedDouble;
116	} else {
117	ASSERT(!function.is_unboxed_parameter_at(index));
118	return kTagged;
119	}
120	}
121
122	Representation FlowGraph::ReturnRepresentationOf(const Function& function) {
123	if (function.IsNull()) {
124	return kTagged;
125	}
126	if (function.has_unboxed_integer_return()) {
127	return kUnboxedInt64;
128	} else if (function.has_unboxed_double_return()) {
129	return kUnboxedDouble;
130	} else if (function.has_unboxed_record_return()) {
131	return kPairOfTagged;
132	} else {
133	ASSERT(!function.has_unboxed_return());
134	return kTagged;
135	}
136	}
137
138	void FlowGraph::ReplaceCurrentInstruction(ForwardInstructionIterator* iterator,
139	Instruction* current,
140	Instruction* replacement) {
141	Definition* current_defn = current->AsDefinition();
142	if ((replacement != nullptr) && (current_defn != nullptr)) {
143	Definition* replacement_defn = replacement->AsDefinition();
144	ASSERT(replacement_defn != nullptr);
145	current_defn->ReplaceUsesWith(other: replacement_defn);
146	EnsureSSATempIndex(defn: current_defn, replacement: replacement_defn);
147
148	if (FLAG_trace_optimization) {
149	THR_Print("Replacing v%" Pd " with v%" Pd "\n",
150	current_defn->ssa_temp_index(),
151	replacement_defn->ssa_temp_index());
152	}
153	} else if (FLAG_trace_optimization) {
154	if (current_defn == nullptr) {
155	THR_Print("Removing %s\n", current->DebugName());
156	} else {
157	ASSERT(!current_defn->HasUses());
158	THR_Print("Removing v%" Pd ".\n", current_defn->ssa_temp_index());
159	}
160	}
161	if (current->ArgumentCount() != 0) {
162	ASSERT(!current->HasMoveArguments());
163	}
164	iterator->RemoveCurrentFromGraph();
165	}
166
167	bool FlowGraph::ShouldReorderBlocks(const Function& function,
168	bool is_optimized) {
169	return is_optimized && FLAG_reorder_basic_blocks &&
170	!function.is_intrinsic() && !function.IsFfiTrampoline();
171	}
172
173	GrowableArray<BlockEntryInstr*>* FlowGraph::CodegenBlockOrder(
174	bool is_optimized) {
175	return ShouldReorderBlocks(function(), is_optimized) ? &optimized_block_order_
176	: &reverse_postorder_;
177	}
178
179	ConstantInstr* FlowGraph::GetExistingConstant(
180	const Object& object,
181	Representation representation) const {
182	return constant_instr_pool_.LookupValue(
183	key: ConstantAndRepresentation{.constant: object, .representation: representation});
184	}
185
186	ConstantInstr* FlowGraph::GetConstant(const Object& object,
187	Representation representation) {
188	ConstantInstr* constant = GetExistingConstant(object, representation);
189	if (constant == nullptr) {
190	// Otherwise, allocate and add it to the pool.
191	const Object& zone_object = Object::ZoneHandle(zone: zone(), ptr: object.ptr());
192	if (representation == kTagged) {
193	constant = new (zone()) ConstantInstr(zone_object);
194	} else {
195	constant = new (zone()) UnboxedConstantInstr(zone_object, representation);
196	}
197	AllocateSSAIndex(def: constant);
198	AddToGraphInitialDefinitions(defn: constant);
199	constant_instr_pool_.Insert(kv: constant);
200	}
201	return constant;
202	}
203
204	bool FlowGraph::IsConstantRepresentable(const Object& value,
205	Representation target_rep,
206	bool tagged_value_must_be_smi) {
207	switch (target_rep) {
208	case kTagged:
209	return !tagged_value_must_be_smi || value.IsSmi();
210
211	case kUnboxedInt32:
212	if (value.IsInteger()) {
213	return Utils::IsInt(N: 32, value: Integer::Cast(obj: value).AsInt64Value());
214	}
215	return false;
216
217	case kUnboxedUint32:
218	if (value.IsInteger()) {
219	return Utils::IsUint(N: 32, value: Integer::Cast(obj: value).AsInt64Value());
220	}
221	return false;
222
223	case kUnboxedInt64:
224	return value.IsInteger();
225
226	case kUnboxedDouble:
227	return value.IsInteger() || value.IsDouble();
228
229	default:
230	return false;
231	}
232	}
233
234	Definition* FlowGraph::TryCreateConstantReplacementFor(Definition* op,
235	const Object& value) {
236	// Check that representation of the constant matches expected representation.
237	const auto representation = op->representation();
238	if (!IsConstantRepresentable(
239	value, target_rep: representation,
240	/*tagged_value_must_be_smi=*/op->Type()->IsNullableSmi())) {
241	return op;
242	}
243
244	if (representation == kUnboxedDouble && value.IsInteger()) {
245	// Convert the boxed constant from int to double.
246	return GetConstant(object: Double::Handle(ptr: Double::NewCanonical(
247	d: Integer::Cast(obj: value).AsDoubleValue())),
248	representation: kUnboxedDouble);
249	}
250
251	return GetConstant(object: value, representation);
252	}
253
254	void FlowGraph::AddToGraphInitialDefinitions(Definition* defn) {
255	defn->set_previous(graph_entry_);
256	graph_entry_->initial_definitions()->Add(defn);
257	}
258
259	void FlowGraph::AddToInitialDefinitions(BlockEntryWithInitialDefs* entry,
260	Definition* defn) {
261	ASSERT(defn->previous() == nullptr);
262	defn->set_previous(entry);
263	if (auto par = defn->AsParameter()) {
264	par->set_block(entry); // set cached block
265	}
266	entry->initial_definitions()->Add(defn);
267	}
268
269	void FlowGraph::InsertAfter(Instruction* prev,
270	Instruction* instr,
271	Environment* env,
272	UseKind use_kind) {
273	if (use_kind == kValue) {
274	ASSERT(instr->IsDefinition());
275	AllocateSSAIndex(def: instr->AsDefinition());
276	}
277	instr->InsertAfter(prev);
278	ASSERT(instr->env() == nullptr);
279	if (env != nullptr) {
280	env->DeepCopyTo(zone: zone(), instr);
281	}
282	}
283
284	void FlowGraph::InsertSpeculativeAfter(Instruction* prev,
285	Instruction* instr,
286	Environment* env,
287	UseKind use_kind) {
288	InsertAfter(prev, instr, env, use_kind);
289	if (instr->env() != nullptr) {
290	instr->env()->MarkAsLazyDeoptToBeforeDeoptId();
291	}
292	}
293
294	Instruction* FlowGraph::AppendTo(Instruction* prev,
295	Instruction* instr,
296	Environment* env,
297	UseKind use_kind) {
298	if (use_kind == kValue) {
299	ASSERT(instr->IsDefinition());
300	AllocateSSAIndex(def: instr->AsDefinition());
301	}
302	ASSERT(instr->env() == nullptr);
303	if (env != nullptr) {
304	env->DeepCopyTo(zone: zone(), instr);
305	}
306	return prev->AppendInstruction(tail: instr);
307	}
308	Instruction* FlowGraph::AppendSpeculativeTo(Instruction* prev,
309	Instruction* instr,
310	Environment* env,
311	UseKind use_kind) {
312	auto result = AppendTo(prev, instr, env, use_kind);
313	if (instr->env() != nullptr) {
314	instr->env()->MarkAsLazyDeoptToBeforeDeoptId();
315	}
316	return result;
317	}
318
319	// A wrapper around block entries including an index of the next successor to
320	// be read.
321	class BlockTraversalState {
322	public:
323	explicit BlockTraversalState(BlockEntryInstr* block)
324	: block_(block),
325	next_successor_ix_(block->last_instruction()->SuccessorCount() - 1) {}
326
327	bool HasNextSuccessor() const { return next_successor_ix_ >= 0; }
328	BlockEntryInstr* NextSuccessor() {
329	ASSERT(HasNextSuccessor());
330	return block_->last_instruction()->SuccessorAt(index: next_successor_ix_--);
331	}
332
333	BlockEntryInstr* block() const { return block_; }
334
335	private:
336	BlockEntryInstr* block_;
337	intptr_t next_successor_ix_;
338
339	DISALLOW_ALLOCATION();
340	};
341
342	void FlowGraph::DiscoverBlocks() {
343	COMPILER_TIMINGS_TIMER_SCOPE(thread(), DiscoverBlocks);
344
345	StackZone zone(thread());
346
347	// Initialize state.
348	preorder_.Clear();
349	postorder_.Clear();
350	reverse_postorder_.Clear();
351	parent_.Clear();
352
353	GrowableArray<BlockTraversalState> block_stack;
354	graph_entry_->DiscoverBlock(nullptr, &preorder_, &parent_);
355	block_stack.Add(BlockTraversalState(graph_entry_));
356	while (!block_stack.is_empty()) {
357	BlockTraversalState& state = block_stack.Last();
358	BlockEntryInstr* block = state.block();
359	if (state.HasNextSuccessor()) {
360	// Process successors one-by-one.
361	BlockEntryInstr* succ = state.NextSuccessor();
362	if (succ->DiscoverBlock(block, &preorder_, &parent_)) {
363	block_stack.Add(BlockTraversalState(succ));
364	}
365	} else {
366	// All successors have been processed, pop the current block entry node
367	// and add it to the postorder list.
368	block_stack.RemoveLast();
369	block->set_postorder_number(postorder_.length());
370	postorder_.Add(block);
371	}
372	}
373
374	ASSERT(postorder_.length() == preorder_.length());
375
376	// Create an array of blocks in reverse postorder.
377	intptr_t block_count = postorder_.length();
378	for (intptr_t i = 0; i < block_count; ++i) {
379	reverse_postorder_.Add(postorder_[block_count - i - 1]);
380	}
381
382	ResetLoopHierarchy();
383	}
384
385	void FlowGraph::MergeBlocks() {
386	bool changed = false;
387	BitVector* merged = new (zone()) BitVector(zone(), postorder().length());
388	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
389	block_it.Advance()) {
390	BlockEntryInstr* block = block_it.Current();
391	if (block->IsGraphEntry()) continue;
392	if (merged->Contains(i: block->postorder_number())) continue;
393
394	Instruction* last = block->last_instruction();
395	BlockEntryInstr* last_merged_block = nullptr;
396	while (auto goto_instr = last->AsGoto()) {
397	JoinEntryInstr* successor = goto_instr->successor();
398	if (successor->PredecessorCount() > 1) break;
399	if (block->try_index() != successor->try_index()) break;
400
401	// Replace all phis with their arguments prior to removing successor.
402	for (PhiIterator it(successor); !it.Done(); it.Advance()) {
403	PhiInstr* phi = it.Current();
404	Value* input = phi->InputAt(0);
405	phi->ReplaceUsesWith(input->definition());
406	input->RemoveFromUseList();
407	}
408
409	// Remove environment uses and unlink goto and block entry.
410	successor->UnuseAllInputs();
411	last->previous()->LinkTo(next: successor->next());
412	last->UnuseAllInputs();
413
414	last = successor->last_instruction();
415	merged->Add(i: successor->postorder_number());
416	last_merged_block = successor;
417	changed = true;
418	if (FLAG_trace_optimization) {
419	THR_Print("Merged blocks B%" Pd " and B%" Pd "\n", block->block_id(),
420	successor->block_id());
421	}
422	}
423	// The new block inherits the block id of the last successor to maintain
424	// the order of phi inputs at its successors consistent with block ids.
425	if (last_merged_block != nullptr) {
426	block->set_block_id(last_merged_block->block_id());
427	}
428	}
429	// Recompute block order after changes were made.
430	if (changed) DiscoverBlocks();
431	}
432
433	void FlowGraph::ComputeIsReceiverRecursive(
434	PhiInstr* phi,
435	GrowableArray<PhiInstr*>* unmark) const {
436	if (phi->is_receiver() != PhiInstr::kUnknownReceiver) return;
437	phi->set_is_receiver(PhiInstr::kReceiver);
438	for (intptr_t i = 0; i < phi->InputCount(); ++i) {
439	Definition* def = phi->InputAt(i)->definition();
440	if (def->IsParameter() && (def->AsParameter()->env_index() == 0)) continue;
441	if (!def->IsPhi()) {
442	phi->set_is_receiver(PhiInstr::kNotReceiver);
443	break;
444	}
445	ComputeIsReceiverRecursive(phi: def->AsPhi(), unmark);
446	if (def->AsPhi()->is_receiver() == PhiInstr::kNotReceiver) {
447	phi->set_is_receiver(PhiInstr::kNotReceiver);
448	break;
449	}
450	}
451
452	if (phi->is_receiver() == PhiInstr::kNotReceiver) {
453	unmark->Add(phi);
454	}
455	}
456
457	void FlowGraph::ComputeIsReceiver(PhiInstr* phi) const {
458	GrowableArray<PhiInstr*> unmark;
459	ComputeIsReceiverRecursive(phi, unmark: &unmark);
460
461	// Now drain unmark.
462	while (!unmark.is_empty()) {
463	PhiInstr* phi = unmark.RemoveLast();
464	for (Value::Iterator it(phi->input_use_list()); !it.Done(); it.Advance()) {
465	PhiInstr* use = it.Current()->instruction()->AsPhi();
466	if ((use != nullptr) && (use->is_receiver() == PhiInstr::kReceiver)) {
467	use->set_is_receiver(PhiInstr::kNotReceiver);
468	unmark.Add(use);
469	}
470	}
471	}
472	}
473
474	bool FlowGraph::IsReceiver(Definition* def) const {
475	def = def->OriginalDefinition(); // Could be redefined.
476	if (def->IsParameter()) return (def->AsParameter()->env_index() == 0);
477	if (!def->IsPhi() || graph_entry()->HasSingleEntryPoint()) {
478	return false;
479	}
480	PhiInstr* phi = def->AsPhi();
481	if (phi->is_receiver() != PhiInstr::kUnknownReceiver) {
482	return (phi->is_receiver() == PhiInstr::kReceiver);
483	}
484	// Not known if this phi is the receiver yet. Compute it now.
485	ComputeIsReceiver(phi);
486	return (phi->is_receiver() == PhiInstr::kReceiver);
487	}
488
489	FlowGraph::ToCheck FlowGraph::CheckForInstanceCall(
490	InstanceCallInstr* call,
491	UntaggedFunction::Kind kind) const {
492	if (!FLAG_use_cha_deopt && !isolate_group()->all_classes_finalized()) {
493	// Even if class or function are private, lazy class finalization
494	// may later add overriding methods.
495	return ToCheck::kCheckCid;
496	}
497
498	// Best effort to get the receiver class.
499	Value* receiver = call->Receiver();
500	Class& receiver_class = Class::Handle(zone: zone());
501	bool receiver_maybe_null = false;
502	if (function().IsDynamicFunction() && IsReceiver(def: receiver->definition())) {
503	// Call receiver is callee receiver: calling "this.g()" in f().
504	receiver_class = function().Owner();
505	} else {
506	// Get the receiver's compile type. Note that
507	// we allow nullable types, which may result in just generating
508	// a null check rather than the more elaborate class check
509	CompileType* type = receiver->Type();
510	const intptr_t receiver_cid = type->ToNullableCid();
511	if (receiver_cid != kDynamicCid) {
512	receiver_class = isolate_group()->class_table()->At(cid: receiver_cid);
513	receiver_maybe_null = type->is_nullable();
514	} else {
515	const AbstractType* atype = type->ToAbstractType();
516	if (atype->IsInstantiated() && atype->HasTypeClass() &&
517	!atype->IsDynamicType()) {
518	if (type->is_nullable()) {
519	receiver_maybe_null = true;
520	}
521	receiver_class = atype->type_class();
522	if (receiver_class.is_implemented()) {
523	receiver_class = Class::null();
524	}
525	}
526	}
527	}
528
529	// Useful receiver class information?
530	if (receiver_class.IsNull()) {
531	return ToCheck::kCheckCid;
532	} else if (call->HasICData()) {
533	// If the static class type does not match information found in ICData
534	// (which may be "guessed"), then bail, since subsequent code generation
535	// (AOT and JIT) for inlining uses the latter.
536	// TODO(ajcbik): improve this by using the static class.
537	const intptr_t cid = receiver_class.id();
538	const ICData* data = call->ic_data();
539	bool match = false;
540	Class& cls = Class::Handle(zone: zone());
541	Function& fun = Function::Handle(zone: zone());
542	for (intptr_t i = 0, len = data->NumberOfChecks(); i < len; i++) {
543	if (!data->IsUsedAt(i)) {
544	continue; // do not consider
545	}
546	fun = data->GetTargetAt(index: i);
547	cls = fun.Owner();
548	if (data->GetReceiverClassIdAt(index: i) == cid || cls.id() == cid) {
549	match = true;
550	break;
551	}
552	}
553	if (!match) {
554	return ToCheck::kCheckCid;
555	}
556	}
557
558	const String& method_name =
559	(kind == UntaggedFunction::kMethodExtractor)
560	? String::Handle(zone(), Field::NameFromGetter(getter_name: call->function_name()))
561	: call->function_name();
562
563	// If the receiver can have the null value, exclude any method
564	// that is actually valid on a null receiver.
565	if (receiver_maybe_null) {
566	const Class& null_class =
567	Class::Handle(zone: zone(), ptr: isolate_group()->object_store()->null_class());
568	Function& target = Function::Handle(zone: zone());
569	if (null_class.EnsureIsFinalized(thread: thread()) == Error::null()) {
570	target = Resolver::ResolveDynamicAnyArgs(zone: zone(), receiver_class: null_class, function_name: method_name);
571	}
572	if (!target.IsNull()) {
573	return ToCheck::kCheckCid;
574	}
575	}
576
577	// Use CHA to determine if the method is not overridden by any subclass
578	// of the receiver class. Any methods that are valid when the receiver
579	// has a null value are excluded above (to avoid throwing an exception
580	// on something valid, like null.hashCode).
581	intptr_t subclass_count = 0;
582	CHA& cha = thread()->compiler_state().cha();
583	if (!cha.HasOverride(cls: receiver_class, function_name: method_name, subclass_count: &subclass_count)) {
584	if (FLAG_trace_cha) {
585	THR_Print(
586	" **(CHA) Instance call needs no class check since there "
587	"are no overrides of method '%s' on '%s'\n",
588	method_name.ToCString(), receiver_class.ToCString());
589	}
590	if (FLAG_use_cha_deopt) {
591	cha.AddToGuardedClassesForSubclassCount(cls: receiver_class, subclass_count);
592	}
593	return receiver_maybe_null ? ToCheck::kCheckNull : ToCheck::kNoCheck;
594	}
595	return ToCheck::kCheckCid;
596	}
597
598	Instruction* FlowGraph::CreateCheckClass(Definition* to_check,
599	const Cids& cids,
600	intptr_t deopt_id,
601	const InstructionSource& source) {
602	if (cids.IsMonomorphic() && cids.MonomorphicReceiverCid() == kSmiCid) {
603	return new (zone())
604	CheckSmiInstr(new (zone()) Value(to_check), deopt_id, source);
605	}
606	return new (zone())
607	CheckClassInstr(new (zone()) Value(to_check), deopt_id, cids, source);
608	}
609
610	Definition* FlowGraph::CreateCheckBound(Definition* length,
611	Definition* index,
612	intptr_t deopt_id) {
613	Value* val1 = new (zone()) Value(length);
614	Value* val2 = new (zone()) Value(index);
615	if (CompilerState::Current().is_aot()) {
616	return new (zone()) GenericCheckBoundInstr(val1, val2, deopt_id);
617	}
618	return new (zone()) CheckArrayBoundInstr(val1, val2, deopt_id);
619	}
620
621	void FlowGraph::AddExactnessGuard(InstanceCallInstr* call,
622	intptr_t receiver_cid) {
623	const Class& cls =
624	Class::Handle(zone: zone(), ptr: isolate_group()->class_table()->At(cid: receiver_cid));
625
626	Definition* load_type_args = new (zone()) LoadFieldInstr(
627	call->Receiver()->CopyWithType(),
628	Slot::GetTypeArgumentsSlotFor(thread: thread(), cls), call->source());
629	InsertBefore(next: call, instr: load_type_args, env: call->env(), use_kind: FlowGraph::kValue);
630
631	const AbstractType& type =
632	AbstractType::Handle(zone(), call->ic_data()->receivers_static_type());
633	ASSERT(!type.IsNull());
634	const TypeArguments& args = TypeArguments::Handle(
635	zone: zone(), ptr: Type::Cast(obj: type).GetInstanceTypeArguments(thread: thread()));
636	Instruction* guard = new (zone()) CheckConditionInstr(
637	new StrictCompareInstr(call->source(), Token::kEQ_STRICT,
638	new (zone()) Value(load_type_args),
639	new (zone()) Value(GetConstant(object: args)),
640	/*needs_number_check=*/false, call->deopt_id()),
641	call->deopt_id());
642	InsertBefore(next: call, instr: guard, env: call->env(), use_kind: FlowGraph::kEffect);
643	}
644
645	// Verify that a redefinition dominates all uses of the redefined value.
646	bool FlowGraph::VerifyRedefinitions() {
647	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
648	block_it.Advance()) {
649	for (ForwardInstructionIterator instr_it(block_it.Current());
650	!instr_it.Done(); instr_it.Advance()) {
651	RedefinitionInstr* redefinition = instr_it.Current()->AsRedefinition();
652	if (redefinition != nullptr) {
653	Definition* original = redefinition->value()->definition();
654	for (Value::Iterator it(original->input_use_list()); !it.Done();
655	it.Advance()) {
656	Value* original_use = it.Current();
657	if (original_use->instruction() == redefinition) {
658	continue;
659	}
660	if (original_use->instruction()->IsDominatedBy(dom: redefinition)) {
661	FlowGraphPrinter::PrintGraph(phase: "VerifyRedefinitions", flow_graph: this);
662	THR_Print("%s\n", redefinition->ToCString());
663	THR_Print("use=%s\n", original_use->instruction()->ToCString());
664	return false;
665	}
666	}
667	}
668	}
669	}
670	return true;
671	}
672
673	LivenessAnalysis::LivenessAnalysis(
674	intptr_t variable_count,
675	const GrowableArray<BlockEntryInstr*>& postorder)
676	: zone_(Thread::Current()->zone()),
677	variable_count_(variable_count),
678	postorder_(postorder),
679	live_out_(postorder.length()),
680	kill_(postorder.length()),
681	live_in_(postorder.length()) {}
682
683	bool LivenessAnalysis::UpdateLiveOut(const BlockEntryInstr& block) {
684	BitVector* live_out = live_out_[block.postorder_number()];
685	bool changed = false;
686	Instruction* last = block.last_instruction();
687	ASSERT(last != nullptr);
688	for (intptr_t i = 0; i < last->SuccessorCount(); i++) {
689	BlockEntryInstr* succ = last->SuccessorAt(index: i);
690	ASSERT(succ != nullptr);
691	if (live_out->AddAll(live_in_[succ->postorder_number()])) {
692	changed = true;
693	}
694	}
695	return changed;
696	}
697
698	bool LivenessAnalysis::UpdateLiveIn(const BlockEntryInstr& block) {
699	BitVector* live_out = live_out_[block.postorder_number()];
700	BitVector* kill = kill_[block.postorder_number()];
701	BitVector* live_in = live_in_[block.postorder_number()];
702	return live_in->KillAndAdd(kill, gen: live_out);
703	}
704
705	void LivenessAnalysis::ComputeLiveInAndLiveOutSets() {
706	const intptr_t block_count = postorder_.length();
707	bool changed;
708	do {
709	changed = false;
710
711	for (intptr_t i = 0; i < block_count; i++) {
712	const BlockEntryInstr& block = *postorder_[i];
713
714	// Live-in set depends only on kill set which does not
715	// change in this loop and live-out set. If live-out
716	// set does not change there is no need to recompute
717	// live-in set.
718	if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
719	changed = true;
720	}
721	}
722	} while (changed);
723	}
724
725	void LivenessAnalysis::Analyze() {
726	const intptr_t block_count = postorder_.length();
727	for (intptr_t i = 0; i < block_count; i++) {
728	live_out_.Add(new (zone()) BitVector(zone(), variable_count_));
729	kill_.Add(new (zone()) BitVector(zone(), variable_count_));
730	live_in_.Add(new (zone()) BitVector(zone(), variable_count_));
731	}
732
733	ComputeInitialSets();
734	ComputeLiveInAndLiveOutSets();
735	}
736
737	static void PrintBitVector(const char* tag, BitVector* v) {
738	THR_Print("%s:", tag);
739	for (BitVector::Iterator it(v); !it.Done(); it.Advance()) {
740	THR_Print(" %" Pd "", it.Current());
741	}
742	THR_Print("\n");
743	}
744
745	void LivenessAnalysis::Dump() {
746	const intptr_t block_count = postorder_.length();
747	for (intptr_t i = 0; i < block_count; i++) {
748	BlockEntryInstr* block = postorder_[i];
749	THR_Print("block @%" Pd " -> ", block->block_id());
750
751	Instruction* last = block->last_instruction();
752	for (intptr_t j = 0; j < last->SuccessorCount(); j++) {
753	BlockEntryInstr* succ = last->SuccessorAt(index: j);
754	THR_Print(" @%" Pd "", succ->block_id());
755	}
756	THR_Print("\n");
757
758	PrintBitVector(" live out", live_out_[i]);
759	PrintBitVector(" kill", kill_[i]);
760	PrintBitVector(" live in", live_in_[i]);
761	}
762	}
763
764	// Computes liveness information for local variables.
765	class VariableLivenessAnalysis : public LivenessAnalysis {
766	public:
767	explicit VariableLivenessAnalysis(FlowGraph* flow_graph)
768	: LivenessAnalysis(flow_graph->variable_count(), flow_graph->postorder()),
769	flow_graph_(flow_graph),
770	assigned_vars_() {}
771
772	// For every block (in preorder) compute and return set of variables that
773	// have new assigned values flowing out of that block.
774	const GrowableArray<BitVector*>& ComputeAssignedVars() {
775	// We can't directly return kill_ because it uses postorder numbering while
776	// SSA construction uses preorder numbering internally.
777	// We have to permute postorder into preorder.
778	assigned_vars_.Clear();
779
780	const intptr_t block_count = flow_graph_->preorder().length();
781	for (intptr_t i = 0; i < block_count; i++) {
782	BlockEntryInstr* block = flow_graph_->preorder()[i];
783	// All locals are assigned inside a try{} block.
784	// This is a safe approximation and workaround to force insertion of
785	// phis for stores that appear non-live because of the way catch-blocks
786	// are connected to the graph: They normally are dominated by the
787	// try-entry, but are direct successors of the graph entry in our flow
788	// graph.
789	// TODO(fschneider): Improve this approximation by better modeling the
790	// actual data flow to reduce the number of redundant phis.
791	BitVector* kill = GetKillSet(block);
792	if (block->InsideTryBlock()) {
793	kill->SetAll();
794	} else {
795	kill->Intersect(other: GetLiveOutSet(block));
796	}
797	assigned_vars_.Add(kill);
798	}
799
800	return assigned_vars_;
801	}
802
803	// Returns true if the value set by the given store reaches any load from the
804	// same local variable.
805	bool IsStoreAlive(BlockEntryInstr* block, StoreLocalInstr* store) {
806	if (store->local().Equals(other: *flow_graph_->CurrentContextVar())) {
807	return true;
808	}
809
810	if (store->is_dead()) {
811	return false;
812	}
813	if (store->is_last()) {
814	const intptr_t index = flow_graph_->EnvIndex(variable: &store->local());
815	return GetLiveOutSet(block)->Contains(index);
816	}
817
818	return true;
819	}
820
821	// Returns true if the given load is the last for the local and the value
822	// of the local will not flow into another one.
823	bool IsLastLoad(BlockEntryInstr* block, LoadLocalInstr* load) {
824	if (load->local().Equals(other: *flow_graph_->CurrentContextVar())) {
825	return false;
826	}
827	const intptr_t index = flow_graph_->EnvIndex(variable: &load->local());
828	return load->is_last() && !GetLiveOutSet(block)->Contains(index);
829	}
830
831	private:
832	virtual void ComputeInitialSets();
833
834	const FlowGraph* flow_graph_;
835	GrowableArray<BitVector*> assigned_vars_;
836	};
837
838	void VariableLivenessAnalysis::ComputeInitialSets() {
839	const intptr_t block_count = postorder_.length();
840
841	BitVector* last_loads = new (zone()) BitVector(zone(), variable_count_);
842	for (intptr_t i = 0; i < block_count; i++) {
843	BlockEntryInstr* block = postorder_[i];
844
845	BitVector* kill = kill_[i];
846	BitVector* live_in = live_in_[i];
847	last_loads->Clear();
848
849	// There is an implicit use (load-local) of every local variable at each
850	// call inside a try{} block and every call has an implicit control-flow
851	// to the catch entry. As an approximation we mark all locals as live
852	// inside try{}.
853	// TODO(fschneider): Improve this approximation, since not all local
854	// variable stores actually reach a call.
855	if (block->InsideTryBlock()) {
856	live_in->SetAll();
857	continue;
858	}
859
860	// Iterate backwards starting at the last instruction.
861	for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) {
862	Instruction* current = it.Current();
863
864	LoadLocalInstr* load = current->AsLoadLocal();
865	if (load != nullptr) {
866	const intptr_t index = flow_graph_->EnvIndex(variable: &load->local());
867	if (index >= live_in->length()) continue; // Skip tmp_locals.
868	live_in->Add(i: index);
869	if (!last_loads->Contains(i: index)) {
870	last_loads->Add(i: index);
871	load->mark_last();
872	}
873	continue;
874	}
875
876	StoreLocalInstr* store = current->AsStoreLocal();
877	if (store != nullptr) {
878	const intptr_t index = flow_graph_->EnvIndex(variable: &store->local());
879	if (index >= live_in->length()) continue; // Skip tmp_locals.
880	if (kill->Contains(i: index)) {
881	if (!live_in->Contains(i: index)) {
882	store->mark_dead();
883	}
884	} else {
885	if (!live_in->Contains(i: index)) {
886	store->mark_last();
887	}
888	kill->Add(i: index);
889	}
890	live_in->Remove(i: index);
891	continue;
892	}
893	}
894
895	// For blocks with parameter or special parameter instructions we add them
896	// to the kill set.
897	const bool is_function_entry = block->IsFunctionEntry();
898	const bool is_osr_entry = block->IsOsrEntry();
899	const bool is_catch_block_entry = block->IsCatchBlockEntry();
900	if (is_function_entry || is_osr_entry || is_catch_block_entry) {
901	const intptr_t parameter_count =
902	(is_osr_entry || is_catch_block_entry)
903	? flow_graph_->variable_count()
904	: flow_graph_->num_direct_parameters();
905	for (intptr_t i = 0; i < parameter_count; ++i) {
906	live_in->Remove(i);
907	kill->Add(i);
908	}
909	}
910	if (is_function_entry) {
911	if (flow_graph_->parsed_function().has_arg_desc_var()) {
912	const auto index = flow_graph_->ArgumentDescriptorEnvIndex();
913	live_in->Remove(i: index);
914	kill->Add(i: index);
915	}
916	}
917	}
918	}
919
920	void FlowGraph::ComputeSSA(
921	ZoneGrowableArray<Definition*>* inlining_parameters) {
922	GrowableArray<BitVector*> dominance_frontier;
923	GrowableArray<intptr_t> idom;
924
925	#ifdef DEBUG
926	if (inlining_parameters != nullptr) {
927	for (intptr_t i = 0, n = inlining_parameters->length(); i < n; ++i) {
928	Definition* defn = (*inlining_parameters)[i];
929	if (defn->IsConstant()) {
930	ASSERT(defn->previous() == graph_entry_);
931	ASSERT(defn->HasSSATemp());
932	ASSERT(defn->ssa_temp_index() < current_ssa_temp_index());
933	} else {
934	ASSERT(defn->previous() == nullptr);
935	ASSERT(!defn->HasSSATemp());
936	}
937	}
938	} else {
939	ASSERT(current_ssa_temp_index() == 0);
940	}
941	#endif
942
943	ComputeDominators(dominance_frontier: &dominance_frontier);
944
945	VariableLivenessAnalysis variable_liveness(this);
946	variable_liveness.Analyze();
947
948	GrowableArray<PhiInstr*> live_phis;
949
950	InsertPhis(preorder_, variable_liveness.ComputeAssignedVars(),
951	dominance_frontier, &live_phis);
952
953	// Rename uses to reference inserted phis where appropriate.
954	// Collect phis that reach a non-environment use.
955	Rename(live_phis: &live_phis, variable_liveness: &variable_liveness, inlining_parameters);
956
957	// Propagate alive mark transitively from alive phis and then remove
958	// non-live ones.
959	RemoveDeadPhis(live_phis: &live_phis);
960	}
961
962	// Compute immediate dominators and the dominance frontier for each basic
963	// block. As a side effect of the algorithm, sets the immediate dominator
964	// of each basic block.
965	//
966	// dominance_frontier: an output parameter encoding the dominance frontier.
967	// The array maps the preorder block number of a block to the set of
968	// (preorder block numbers of) blocks in the dominance frontier.
969	void FlowGraph::ComputeDominators(
970	GrowableArray<BitVector*>* dominance_frontier) {
971	// Use the SEMI-NCA algorithm to compute dominators. This is a two-pass
972	// version of the Lengauer-Tarjan algorithm (LT is normally three passes)
973	// that eliminates a pass by using nearest-common ancestor (NCA) to
974	// compute immediate dominators from semidominators. It also removes a
975	// level of indirection in the link-eval forest data structure.
976	//
977	// The algorithm is described in Georgiadis, Tarjan, and Werneck's
978	// "Finding Dominators in Practice".
979	// https://renatowerneck.files.wordpress.com/2016/06/gtw06-dominators.pdf
980
981	// All arrays are maps between preorder basic-block numbers.
982	intptr_t size = parent_.length();
983	GrowableArray<intptr_t> idom(size); // Immediate dominator.
984	GrowableArray<intptr_t> semi(size); // Semidominator.
985	GrowableArray<intptr_t> label(size); // Label for link-eval forest.
986
987	// 1. First pass: compute semidominators as in Lengauer-Tarjan.
988	// Semidominators are computed from a depth-first spanning tree and are an
989	// approximation of immediate dominators.
990
991	// Use a link-eval data structure with path compression. Implement path
992	// compression in place by mutating the parent array. Each block has a
993	// label, which is the minimum block number on the compressed path.
994
995	// Initialize idom, semi, and label used by SEMI-NCA. Initialize the
996	// dominance frontier output array.
997	for (intptr_t i = 0; i < size; ++i) {
998	idom.Add(parent_[i]);
999	semi.Add(i);
1000	label.Add(i);
1001	dominance_frontier->Add(new (zone()) BitVector(zone(), size));
1002	}
1003
1004	// Loop over the blocks in reverse preorder (not including the graph
1005	// entry). Clear the dominated blocks in the graph entry in case
1006	// ComputeDominators is used to recompute them.
1007	preorder_[0]->ClearDominatedBlocks();
1008	for (intptr_t block_index = size - 1; block_index >= 1; --block_index) {
1009	// Loop over the predecessors.
1010	BlockEntryInstr* block = preorder_[block_index];
1011	// Clear the immediately dominated blocks in case ComputeDominators is
1012	// used to recompute them.
1013	block->ClearDominatedBlocks();
1014	for (intptr_t i = 0, count = block->PredecessorCount(); i < count; ++i) {
1015	BlockEntryInstr* pred = block->PredecessorAt(index: i);
1016	ASSERT(pred != nullptr);
1017
1018	// Look for the semidominator by ascending the semidominator path
1019	// starting from pred.
1020	intptr_t pred_index = pred->preorder_number();
1021	intptr_t best = pred_index;
1022	if (pred_index > block_index) {
1023	CompressPath(block_index, pred_index, &parent_, &label);
1024	best = label[pred_index];
1025	}
1026
1027	// Update the semidominator if we've found a better one.
1028	semi[block_index] = Utils::Minimum(semi[block_index], semi[best]);
1029	}
1030
1031	// Now use label for the semidominator.
1032	label[block_index] = semi[block_index];
1033	}
1034
1035	// 2. Compute the immediate dominators as the nearest common ancestor of
1036	// spanning tree parent and semidominator, for all blocks except the entry.
1037	for (intptr_t block_index = 1; block_index < size; ++block_index) {
1038	intptr_t dom_index = idom[block_index];
1039	while (dom_index > semi[block_index]) {
1040	dom_index = idom[dom_index];
1041	}
1042	idom[block_index] = dom_index;
1043	preorder_[dom_index]->AddDominatedBlock(preorder_[block_index]);
1044	}
1045
1046	// 3. Now compute the dominance frontier for all blocks. This is
1047	// algorithm in "A Simple, Fast Dominance Algorithm" (Figure 5), which is
1048	// attributed to a paper by Ferrante et al. There is no bookkeeping
1049	// required to avoid adding a block twice to the same block's dominance
1050	// frontier because we use a set to represent the dominance frontier.
1051	for (intptr_t block_index = 0; block_index < size; ++block_index) {
1052	BlockEntryInstr* block = preorder_[block_index];
1053	intptr_t count = block->PredecessorCount();
1054	if (count <= 1) continue;
1055	for (intptr_t i = 0; i < count; ++i) {
1056	BlockEntryInstr* runner = block->PredecessorAt(index: i);
1057	while (runner != block->dominator()) {
1058	(*dominance_frontier)[runner->preorder_number()]->Add(block_index);
1059	runner = runner->dominator();
1060	}
1061	}
1062	}
1063	}
1064
1065	void FlowGraph::CompressPath(intptr_t start_index,
1066	intptr_t current_index,
1067	GrowableArray<intptr_t>* parent,
1068	GrowableArray<intptr_t>* label) {
1069	intptr_t next_index = (*parent)[current_index];
1070	if (next_index > start_index) {
1071	CompressPath(start_index, current_index: next_index, parent, label);
1072	(*label)[current_index] =
1073	Utils::Minimum((*label)[current_index], (*label)[next_index]);
1074	(*parent)[current_index] = (*parent)[next_index];
1075	}
1076	}
1077
1078	void FlowGraph::InsertPhis(const GrowableArray<BlockEntryInstr*>& preorder,
1079	const GrowableArray<BitVector*>& assigned_vars,
1080	const GrowableArray<BitVector*>& dom_frontier,
1081	GrowableArray<PhiInstr*>* live_phis) {
1082	const intptr_t block_count = preorder.length();
1083	// Map preorder block number to the highest variable index that has a phi
1084	// in that block. Use it to avoid inserting multiple phis for the same
1085	// variable.
1086	GrowableArray<intptr_t> has_already(block_count);
1087	// Map preorder block number to the highest variable index for which the
1088	// block went on the worklist. Use it to avoid adding the same block to
1089	// the worklist more than once for the same variable.
1090	GrowableArray<intptr_t> work(block_count);
1091
1092	// Initialize has_already and work.
1093	for (intptr_t block_index = 0; block_index < block_count; ++block_index) {
1094	has_already.Add(-1);
1095	work.Add(-1);
1096	}
1097
1098	// Insert phis for each variable in turn.
1099	GrowableArray<BlockEntryInstr*> worklist;
1100	for (intptr_t var_index = 0; var_index < variable_count(); ++var_index) {
1101	const bool always_live =
1102	!FLAG_prune_dead_locals || IsImmortalVariable(env_index: var_index);
1103	// Add to the worklist each block containing an assignment.
1104	for (intptr_t block_index = 0; block_index < block_count; ++block_index) {
1105	if (assigned_vars[block_index]->Contains(var_index)) {
1106	work[block_index] = var_index;
1107	worklist.Add(preorder[block_index]);
1108	}
1109	}
1110
1111	while (!worklist.is_empty()) {
1112	BlockEntryInstr* current = worklist.RemoveLast();
1113	// Ensure a phi for each block in the dominance frontier of current.
1114	for (BitVector::Iterator it(dom_frontier[current->preorder_number()]);
1115	!it.Done(); it.Advance()) {
1116	int index = it.Current();
1117	if (has_already[index] < var_index) {
1118	JoinEntryInstr* join = preorder[index]->AsJoinEntry();
1119	ASSERT(join != nullptr);
1120	PhiInstr* phi = join->InsertPhi(
1121	var_index, variable_count() + join->stack_depth());
1122	if (always_live) {
1123	phi->mark_alive();
1124	live_phis->Add(phi);
1125	}
1126	has_already[index] = var_index;
1127	if (work[index] < var_index) {
1128	work[index] = var_index;
1129	worklist.Add(join);
1130	}
1131	}
1132	}
1133	}
1134	}
1135	}
1136
1137	void FlowGraph::CreateCommonConstants() {
1138	constant_null_ = GetConstant(object: Object::ZoneHandle());
1139	constant_dead_ = GetConstant(object: Object::optimized_out());
1140	}
1141
1142	void FlowGraph::AddSyntheticPhis(BlockEntryInstr* block) {
1143	ASSERT(IsCompiledForOsr());
1144	if (auto join = block->AsJoinEntry()) {
1145	const intptr_t local_phi_count = variable_count() + join->stack_depth();
1146	// Never insert more phi's than that we had osr variables.
1147	const intptr_t osr_phi_count =
1148	Utils::Minimum(x: local_phi_count, y: osr_variable_count());
1149	for (intptr_t i = variable_count(); i < osr_phi_count; ++i) {
1150	if (join->phis() == nullptr || (*join->phis())[i] == nullptr) {
1151	join->InsertPhi(i, local_phi_count)->mark_alive();
1152	}
1153	}
1154	}
1155	}
1156
1157	void FlowGraph::Rename(GrowableArray<PhiInstr*>* live_phis,
1158	VariableLivenessAnalysis* variable_liveness,
1159	ZoneGrowableArray<Definition*>* inlining_parameters) {
1160	GraphEntryInstr* entry = graph_entry();
1161
1162	// Add global constants to the initial definitions.
1163	CreateCommonConstants();
1164
1165	// Initial renaming environment.
1166	GrowableArray<Definition*> env(variable_count());
1167	env.FillWith(constant_dead(), 0, num_direct_parameters());
1168	env.FillWith(constant_null(), num_direct_parameters(), num_stack_locals());
1169
1170	if (entry->catch_entries().length() > 0) {
1171	// Functions with try-catch have a fixed area of stack slots reserved
1172	// so that all local variables are stored at a known location when
1173	// on entry to the catch.
1174	entry->set_fixed_slot_count(num_stack_locals());
1175	} else {
1176	ASSERT(entry->unchecked_entry() != nullptr ? entry->SuccessorCount() == 2
1177	: entry->SuccessorCount() == 1);
1178	}
1179
1180	// For OSR on a non-empty stack, insert synthetic phis on every joining entry.
1181	// These phis are synthetic since they are not driven by live variable
1182	// analysis, but merely serve the purpose of merging stack slots from
1183	// parameters and other predecessors at the block in which OSR occurred.
1184	// The original definition could flow into a join via multiple predecessors
1185	// but with the same definition, not requiring a phi. However, with an OSR
1186	// entry in a different block, phis are required to merge the OSR variable
1187	// and original definition where there was no phi. Therefore, we need
1188	// synthetic phis in all (reachable) blocks, not just in the first join.
1189	if (IsCompiledForOsr()) {
1190	for (intptr_t i = 0, n = preorder().length(); i < n; ++i) {
1191	AddSyntheticPhis(preorder()[i]);
1192	}
1193	}
1194
1195	RenameRecursive(entry, &env, live_phis, variable_liveness,
1196	inlining_parameters);
1197
1198	#if defined(DEBUG)
1199	ValidatePhis();
1200	#endif // defined(DEBUG)
1201	}
1202
1203	void FlowGraph::PopulateEnvironmentFromFunctionEntry(
1204	FunctionEntryInstr* function_entry,
1205	GrowableArray<Definition*>* env,
1206	GrowableArray<PhiInstr*>* live_phis,
1207	VariableLivenessAnalysis* variable_liveness,
1208	ZoneGrowableArray<Definition*>* inlining_parameters) {
1209	ASSERT(!IsCompiledForOsr());
1210	const intptr_t direct_parameter_count = num_direct_parameters_;
1211
1212	// Check if inlining_parameters include a type argument vector parameter.
1213	const intptr_t inlined_type_args_param =
1214	((inlining_parameters != nullptr) && function().IsGeneric()) ? 1 : 0;
1215
1216	ASSERT(variable_count() == env->length());
1217	ASSERT(direct_parameter_count <= env->length());
1218	intptr_t param_offset = 0;
1219	for (intptr_t i = 0; i < direct_parameter_count; i++) {
1220	ASSERT(FLAG_precompiled_mode || !function().is_unboxed_parameter_at(i));
1221	ParameterInstr* param;
1222
1223	const intptr_t index = (function().IsFactory() ? (i - 1) : i);
1224
1225	if (index >= 0 && function().is_unboxed_integer_parameter_at(index)) {
1226	constexpr intptr_t kCorrection = compiler::target::kIntSpillFactor - 1;
1227	param = new (zone()) ParameterInstr(/*env_index=*/i, /*param_index=*/i,
1228	param_offset + kCorrection,
1229	function_entry, kUnboxedInt64);
1230	param_offset += compiler::target::kIntSpillFactor;
1231	} else if (index >= 0 && function().is_unboxed_double_parameter_at(index)) {
1232	constexpr intptr_t kCorrection = compiler::target::kDoubleSpillFactor - 1;
1233	param = new (zone()) ParameterInstr(/*env_index=*/i, /*param_index=*/i,
1234	param_offset + kCorrection,
1235	function_entry, kUnboxedDouble);
1236	param_offset += compiler::target::kDoubleSpillFactor;
1237	} else {
1238	ASSERT(index < 0 || !function().is_unboxed_parameter_at(index));
1239	param =
1240	new (zone()) ParameterInstr(/*env_index=*/i, /*param_index=*/i,
1241	param_offset, function_entry, kTagged);
1242	param_offset++;
1243	}
1244	AllocateSSAIndex(def: param);
1245	AddToInitialDefinitions(function_entry, param);
1246	(*env)[i] = param;
1247	}
1248
1249	// Override the entries in the renaming environment which are special (i.e.
1250	// inlining arguments, type parameter, args descriptor, context, ...)
1251	{
1252	// Replace parameter slots with inlining definitions coming in.
1253	if (inlining_parameters != nullptr) {
1254	for (intptr_t i = 0; i < function().NumParameters(); ++i) {
1255	Definition* defn = (*inlining_parameters)[inlined_type_args_param + i];
1256	if (defn->IsConstant()) {
1257	ASSERT(defn->previous() == graph_entry_);
1258	ASSERT(defn->HasSSATemp());
1259	} else {
1260	ASSERT(defn->previous() == nullptr);
1261	AllocateSSAIndex(def: defn);
1262	AddToInitialDefinitions(function_entry, defn);
1263	}
1264	intptr_t index = EnvIndex(variable: parsed_function_.RawParameterVariable(i));
1265	(*env)[index] = defn;
1266	}
1267	}
1268
1269	// Replace the type arguments slot with a special parameter.
1270	const bool reify_generic_argument = function().IsGeneric();
1271	if (reify_generic_argument) {
1272	ASSERT(parsed_function().function_type_arguments() != nullptr);
1273	Definition* defn;
1274	if (inlining_parameters == nullptr) {
1275	// Note: If we are not inlining, then the prologue builder will
1276	// take care of checking that we got the correct reified type
1277	// arguments. This includes checking the argument descriptor in order
1278	// to even find out if the parameter was passed or not.
1279	defn = constant_dead();
1280	} else {
1281	defn = (*inlining_parameters)[0];
1282	}
1283	if (defn->IsConstant()) {
1284	ASSERT(defn->previous() == graph_entry_);
1285	ASSERT(defn->HasSSATemp());
1286	} else {
1287	ASSERT(defn->previous() == nullptr);
1288	AllocateSSAIndex(def: defn);
1289	AddToInitialDefinitions(function_entry, defn);
1290	}
1291	(*env)[RawTypeArgumentEnvIndex()] = defn;
1292	}
1293
1294	// Replace the argument descriptor slot with a special parameter.
1295	if (parsed_function().has_arg_desc_var()) {
1296	Definition* defn =
1297	new (Z) SpecialParameterInstr(SpecialParameterInstr::kArgDescriptor,
1298	DeoptId::kNone, function_entry);
1299	AllocateSSAIndex(def: defn);
1300	AddToInitialDefinitions(function_entry, defn);
1301	(*env)[ArgumentDescriptorEnvIndex()] = defn;
1302	}
1303	}
1304	}
1305
1306	void FlowGraph::PopulateEnvironmentFromOsrEntry(
1307	OsrEntryInstr* osr_entry,
1308	GrowableArray<Definition*>* env) {
1309	ASSERT(IsCompiledForOsr());
1310	// During OSR, all variables and possibly a non-empty stack are
1311	// passed as parameters. The latter mimics the incoming expression
1312	// stack that was set up prior to triggering OSR.
1313	const intptr_t parameter_count = osr_variable_count();
1314	ASSERT(parameter_count == env->length());
1315	for (intptr_t i = 0; i < parameter_count; i++) {
1316	const intptr_t param_index = (i < num_direct_parameters())
1317	? i
1318	: ParameterInstr::kNotFunctionParameter;
1319	ParameterInstr* param = new (zone())
1320	ParameterInstr(/*env_index=*/i, param_index, i, osr_entry, kTagged);
1321	AllocateSSAIndex(def: param);
1322	AddToInitialDefinitions(osr_entry, param);
1323	(*env)[i] = param;
1324	}
1325	}
1326
1327	void FlowGraph::PopulateEnvironmentFromCatchEntry(
1328	CatchBlockEntryInstr* catch_entry,
1329	GrowableArray<Definition*>* env) {
1330	const intptr_t raw_exception_var_envindex =
1331	catch_entry->raw_exception_var() != nullptr
1332	? EnvIndex(variable: catch_entry->raw_exception_var())
1333	: -1;
1334	const intptr_t raw_stacktrace_var_envindex =
1335	catch_entry->raw_stacktrace_var() != nullptr
1336	? EnvIndex(variable: catch_entry->raw_stacktrace_var())
1337	: -1;
1338
1339	// Add real definitions for all locals and parameters.
1340	ASSERT(variable_count() == env->length());
1341	for (intptr_t i = 0, n = variable_count(); i < n; ++i) {
1342	// Replace usages of the raw exception/stacktrace variables with
1343	// [SpecialParameterInstr]s.
1344	Definition* param = nullptr;
1345	if (raw_exception_var_envindex == i) {
1346	param = new (Z) SpecialParameterInstr(SpecialParameterInstr::kException,
1347	DeoptId::kNone, catch_entry);
1348	} else if (raw_stacktrace_var_envindex == i) {
1349	param = new (Z) SpecialParameterInstr(SpecialParameterInstr::kStackTrace,
1350	DeoptId::kNone, catch_entry);
1351	} else {
1352	param = new (Z)
1353	ParameterInstr(/*env_index=*/i,
1354	/*param_index=*/ParameterInstr::kNotFunctionParameter,
1355	i, catch_entry, kTagged);
1356	}
1357
1358	AllocateSSAIndex(def: param); // New SSA temp.
1359	(*env)[i] = param;
1360	AddToInitialDefinitions(catch_entry, param);
1361	}
1362	}
1363
1364	void FlowGraph::AttachEnvironment(Instruction* instr,
1365	GrowableArray<Definition*>* env) {
1366	auto deopt_env = Environment::From(zone: zone(), definitions: *env, fixed_parameter_count: num_direct_parameters_,
1367	lazy_deopt_pruning_count: instr->NumberOfInputsConsumedBeforeCall(),
1368	parsed_function: parsed_function_);
1369	instr->SetEnvironment(deopt_env);
1370	for (Environment::DeepIterator it(deopt_env); !it.Done(); it.Advance()) {
1371	Value* use = it.CurrentValue();
1372	use->definition()->AddEnvUse(value: use);
1373	}
1374	}
1375
1376	void FlowGraph::RenameRecursive(
1377	BlockEntryInstr* block_entry,
1378	GrowableArray<Definition*>* env,
1379	GrowableArray<PhiInstr*>* live_phis,
1380	VariableLivenessAnalysis* variable_liveness,
1381	ZoneGrowableArray<Definition*>* inlining_parameters) {
1382	// 1. Process phis first.
1383	if (auto join = block_entry->AsJoinEntry()) {
1384	if (join->phis() != nullptr) {
1385	const intptr_t local_phi_count = variable_count() + join->stack_depth();
1386	ASSERT(join->phis()->length() == local_phi_count);
1387	for (intptr_t i = 0; i < local_phi_count; ++i) {
1388	PhiInstr* phi = (*join->phis())[i];
1389	if (phi != nullptr) {
1390	(*env)[i] = phi;
1391	AllocateSSAIndex(phi); // New SSA temp.
1392	if (block_entry->InsideTryBlock() && !phi->is_alive()) {
1393	// This is a safe approximation. Inside try{} all locals are
1394	// used at every call implicitly, so we mark all phis as live
1395	// from the start.
1396	// TODO(fschneider): Improve this approximation to eliminate
1397	// more redundant phis.
1398	phi->mark_alive();
1399	live_phis->Add(phi);
1400	}
1401	}
1402	}
1403	}
1404	} else if (auto osr_entry = block_entry->AsOsrEntry()) {
1405	PopulateEnvironmentFromOsrEntry(osr_entry: osr_entry, env);
1406	} else if (auto function_entry = block_entry->AsFunctionEntry()) {
1407	ASSERT(!IsCompiledForOsr());
1408	PopulateEnvironmentFromFunctionEntry(
1409	function_entry: function_entry, env, live_phis, variable_liveness, inlining_parameters);
1410	} else if (auto catch_entry = block_entry->AsCatchBlockEntry()) {
1411	PopulateEnvironmentFromCatchEntry(catch_entry: catch_entry, env);
1412	}
1413
1414	if (!block_entry->IsGraphEntry() &&
1415	!block_entry->IsBlockEntryWithInitialDefs()) {
1416	// Prune non-live variables at block entry by replacing their environment
1417	// slots with null.
1418	BitVector* live_in = variable_liveness->GetLiveInSet(block_entry);
1419	for (intptr_t i = 0; i < variable_count(); i++) {
1420	// TODO(fschneider): Make sure that live_in always contains the
1421	// CurrentContext variable to avoid the special case here.
1422	if (FLAG_prune_dead_locals && !live_in->Contains(i) &&
1423	!IsImmortalVariable(env_index: i)) {
1424	(*env)[i] = constant_dead();
1425	}
1426	}
1427	}
1428
1429	// Attach environment to the block entry.
1430	AttachEnvironment(block_entry, env);
1431
1432	// 2. Process normal instructions.
1433	for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) {
1434	Instruction* current = it.Current();
1435
1436	// Attach current environment to the instructions that need it.
1437	if (current->NeedsEnvironment()) {
1438	AttachEnvironment(instr: current, env);
1439	}
1440
1441	// 2a. Handle uses:
1442	// Update the expression stack renaming environment for each use by
1443	// removing the renamed value. For each use of a LoadLocal, StoreLocal,
1444	// MakeTemp, DropTemps or Constant (or any expression under OSR),
1445	// replace it with the renamed value.
1446	for (intptr_t i = current->InputCount() - 1; i >= 0; --i) {
1447	Value* v = current->InputAt(i);
1448	// Update expression stack.
1449	ASSERT(env->length() > variable_count());
1450	Definition* reaching_defn = env->RemoveLast();
1451	Definition* input_defn = v->definition();
1452	if (input_defn != reaching_defn) {
1453	// Inspect the replacing definition before making the change.
1454	if (IsCompiledForOsr()) {
1455	// Under OSR, constants can reside on the expression stack. Just
1456	// generate the constant rather than going through a synthetic phi.
1457	if (input_defn->IsConstant() && reaching_defn->IsPhi()) {
1458	ASSERT(env->length() < osr_variable_count());
1459	auto constant = GetConstant(object: input_defn->AsConstant()->value());
1460	current->ReplaceInEnvironment(current: reaching_defn, replacement: constant);
1461	reaching_defn = constant;
1462	}
1463	} else {
1464	// Note: constants can only be replaced with other constants.
1465	ASSERT(input_defn->IsLoadLocal() || input_defn->IsStoreLocal() ||
1466	input_defn->IsDropTemps() || input_defn->IsMakeTemp() ||
1467	(input_defn->IsConstant() && reaching_defn->IsConstant()));
1468	}
1469	// Assert we are not referencing nulls in the initial environment.
1470	ASSERT(reaching_defn->ssa_temp_index() != -1);
1471	// Replace the definition.
1472	v->set_definition(reaching_defn);
1473	input_defn = reaching_defn;
1474	}
1475	input_defn->AddInputUse(value: v);
1476	}
1477
1478	// 2b. Handle LoadLocal/StoreLocal/MakeTemp/DropTemps/Constant specially.
1479	// Other definitions are just pushed to the environment directly.
1480	Definition* result = nullptr;
1481	switch (current->tag()) {
1482	case Instruction::kLoadLocal: {
1483	LoadLocalInstr* load = current->Cast<LoadLocalInstr>();
1484
1485	// The graph construction ensures we do not have an unused LoadLocal
1486	// computation.
1487	ASSERT(load->HasTemp());
1488	const intptr_t index = EnvIndex(variable: &load->local());
1489	result = (*env)[index];
1490
1491	PhiInstr* phi = result->AsPhi();
1492	if ((phi != nullptr) && !phi->is_alive()) {
1493	phi->mark_alive();
1494	live_phis->Add(phi);
1495	}
1496
1497	if (FLAG_prune_dead_locals &&
1498	variable_liveness->IsLastLoad(block: block_entry, load)) {
1499	(*env)[index] = constant_dead();
1500	}
1501
1502	// Record captured parameters so that they can be skipped when
1503	// emitting sync code inside optimized try-blocks.
1504	if (load->local().is_captured_parameter()) {
1505	captured_parameters_->Add(i: index);
1506	}
1507
1508	if (phi != nullptr) {
1509	// Assign type to Phi if it doesn't have a type yet.
1510	// For a Phi to appear in the local variable it either was placed
1511	// there as incoming value by renaming or it was stored there by
1512	// StoreLocal which took this Phi from another local via LoadLocal,
1513	// to which this reasoning applies recursively.
1514	//
1515	// This means that we are guaranteed to process LoadLocal for a
1516	// matching variable first, unless there was an OSR with a non-empty
1517	// expression stack. In the latter case, Phi inserted by
1518	// FlowGraph::AddSyntheticPhis for expression temp will not have an
1519	// assigned type and may be accessed by StoreLocal and subsequent
1520	// LoadLocal.
1521	//
1522	if (!phi->HasType()) {
1523	// Check if phi corresponds to the same slot.
1524	auto* phis = phi->block()->phis();
1525	if ((index < phis->length()) && (*phis)[index] == phi) {
1526	phi->UpdateType(CompileType::FromAbstractType(
1527	type: load->local().type(), can_be_null: CompileType::kCanBeNull,
1528	/*can_be_sentinel=*/load->local().is_late()));
1529	} else {
1530	ASSERT(IsCompiledForOsr() && (phi->block()->stack_depth() > 0));
1531	}
1532	}
1533	}
1534	break;
1535	}
1536
1537	case Instruction::kStoreLocal: {
1538	StoreLocalInstr* store = current->Cast<StoreLocalInstr>();
1539	const intptr_t index = EnvIndex(variable: &store->local());
1540	result = store->value()->definition();
1541
1542	if (!FLAG_prune_dead_locals ||
1543	variable_liveness->IsStoreAlive(block: block_entry, store)) {
1544	(*env)[index] = result;
1545	} else {
1546	(*env)[index] = constant_dead();
1547	}
1548	break;
1549	}
1550
1551	case Instruction::kDropTemps: {
1552	// Drop temps from the environment.
1553	DropTempsInstr* drop = current->Cast<DropTempsInstr>();
1554	for (intptr_t j = 0; j < drop->num_temps(); j++) {
1555	env->RemoveLast();
1556	}
1557	if (drop->value() != nullptr) {
1558	result = drop->value()->definition();
1559	}
1560	ASSERT((drop->value() != nullptr) || !drop->HasTemp());
1561	break;
1562	}
1563
1564	case Instruction::kConstant: {
1565	ConstantInstr* constant = current->Cast<ConstantInstr>();
1566	if (constant->HasTemp()) {
1567	result = GetConstant(object: constant->value());
1568	}
1569	break;
1570	}
1571
1572	case Instruction::kMakeTemp: {
1573	// Simply push a #null value to the expression stack.
1574	result = constant_null_;
1575	break;
1576	}
1577
1578	case Instruction::kMoveArgument:
1579	UNREACHABLE();
1580	break;
1581
1582	case Instruction::kCheckStackOverflow:
1583	// Assert environment integrity at checkpoints.
1584	ASSERT((variable_count() +
1585	current->AsCheckStackOverflow()->stack_depth()) ==
1586	env->length());
1587	continue;
1588
1589	default:
1590	// Other definitions directly go into the environment.
1591	if (Definition* definition = current->AsDefinition()) {
1592	if (definition->HasTemp()) {
1593	// Assign fresh SSA temporary and update expression stack.
1594	AllocateSSAIndex(def: definition);
1595	env->Add(definition);
1596	}
1597	}
1598	continue;
1599	}
1600
1601	// Update expression stack and remove current instruction from the graph.
1602	Definition* definition = current->Cast<Definition>();
1603	if (definition->HasTemp()) {
1604	ASSERT(result != nullptr);
1605	env->Add(result);
1606	}
1607	it.RemoveCurrentFromGraph();
1608	}
1609
1610	// 3. Process dominated blocks.
1611	const bool set_stack = (block_entry == graph_entry()) && IsCompiledForOsr();
1612	for (intptr_t i = 0; i < block_entry->dominated_blocks().length(); ++i) {
1613	BlockEntryInstr* block = block_entry->dominated_blocks()[i];
1614	GrowableArray<Definition*> new_env(env->length());
1615	new_env.AddArray(*env);
1616	// During OSR, when traversing from the graph entry directly any block
1617	// (which may be a non-entry), we must adjust the environment to mimic
1618	// a non-empty incoming expression stack to ensure temporaries refer to
1619	// the right stack items.
1620	const intptr_t stack_depth = block->stack_depth();
1621	ASSERT(stack_depth >= 0);
1622	if (set_stack) {
1623	ASSERT(variable_count() == new_env.length());
1624	new_env.FillWith(constant_dead(), variable_count(), stack_depth);
1625	} else if (!block->last_instruction()->IsTailCall()) {
1626	// Assert environment integrity otherwise.
1627	ASSERT((variable_count() + stack_depth) == new_env.length());
1628	}
1629	RenameRecursive(block_entry: block, env: &new_env, live_phis, variable_liveness,
1630	inlining_parameters);
1631	}
1632
1633	// 4. Process successor block. We have edge-split form, so that only blocks
1634	// with one successor can have a join block as successor.
1635	if ((block_entry->last_instruction()->SuccessorCount() == 1) &&
1636	block_entry->last_instruction()->SuccessorAt(index: 0)->IsJoinEntry()) {
1637	JoinEntryInstr* successor =
1638	block_entry->last_instruction()->SuccessorAt(index: 0)->AsJoinEntry();
1639	intptr_t pred_index = successor->IndexOfPredecessor(pred: block_entry);
1640	ASSERT(pred_index >= 0);
1641	if (successor->phis() != nullptr) {
1642	for (intptr_t i = 0; i < successor->phis()->length(); ++i) {
1643	PhiInstr* phi = (*successor->phis())[i];
1644	if (phi != nullptr) {
1645	// Rename input operand.
1646	Definition* input = (*env)[i];
1647	ASSERT(input != nullptr);
1648	ASSERT(!input->IsMoveArgument());
1649	Value* use = new (zone()) Value(input);
1650	phi->SetInputAt(pred_index, use);
1651	}
1652	}
1653	}
1654	}
1655	}
1656
1657	#if defined(DEBUG)
1658	void FlowGraph::ValidatePhis() {
1659	if (!FLAG_prune_dead_locals) {
1660	// We can only check if dead locals are pruned.
1661	return;
1662	}
1663
1664	for (intptr_t i = 0, n = preorder().length(); i < n; ++i) {
1665	BlockEntryInstr* block_entry = preorder()[i];
1666	Instruction* last_instruction = block_entry->last_instruction();
1667
1668	if ((last_instruction->SuccessorCount() == 1) &&
1669	last_instruction->SuccessorAt(index: 0)->IsJoinEntry()) {
1670	JoinEntryInstr* successor =
1671	last_instruction->SuccessorAt(index: 0)->AsJoinEntry();
1672	if (successor->phis() != nullptr) {
1673	for (intptr_t j = 0; j < successor->phis()->length(); ++j) {
1674	PhiInstr* phi = (*successor->phis())[j];
1675	if (phi == nullptr && !IsImmortalVariable(env_index: j)) {
1676	// We have no phi node for the this variable.
1677	// Double check we do not have a different value in our env.
1678	// If we do, we would have needed a phi-node in the successor.
1679	ASSERT(last_instruction->env() != nullptr);
1680	Definition* current_definition =
1681	last_instruction->env()->ValueAt(ix: j)->definition();
1682	ASSERT(successor->env() != nullptr);
1683	Definition* successor_definition =
1684	successor->env()->ValueAt(j)->definition();
1685	if (!current_definition->IsConstant() &&
1686	!successor_definition->IsConstant()) {
1687	ASSERT(current_definition == successor_definition);
1688	}
1689	}
1690	}
1691	}
1692	}
1693	}
1694	}
1695	#endif // defined(DEBUG)
1696
1697	void FlowGraph::RemoveDeadPhis(GrowableArray<PhiInstr*>* live_phis) {
1698	// Augment live_phis with those that have implicit real used at
1699	// potentially throwing instructions if there is a try-catch in this graph.
1700	if (!graph_entry()->catch_entries().is_empty()) {
1701	for (BlockIterator it(postorder_iterator()); !it.Done(); it.Advance()) {
1702	JoinEntryInstr* join = it.Current()->AsJoinEntry();
1703	if (join == nullptr) continue;
1704	for (PhiIterator phi_it(join); !phi_it.Done(); phi_it.Advance()) {
1705	PhiInstr* phi = phi_it.Current();
1706	if (phi == nullptr || phi->is_alive() ||
1707	(phi->input_use_list() != nullptr) ||
1708	(phi->env_use_list() == nullptr)) {
1709	continue;
1710	}
1711	for (Value::Iterator it(phi->env_use_list()); !it.Done();
1712	it.Advance()) {
1713	Value* use = it.Current();
1714	if (use->instruction()->MayThrow() &&
1715	use->instruction()->GetBlock()->InsideTryBlock()) {
1716	live_phis->Add(phi);
1717	phi->mark_alive();
1718	break;
1719	}
1720	}
1721	}
1722	}
1723	}
1724
1725	while (!live_phis->is_empty()) {
1726	PhiInstr* phi = live_phis->RemoveLast();
1727	for (intptr_t i = 0; i < phi->InputCount(); i++) {
1728	Value* val = phi->InputAt(i);
1729	PhiInstr* used_phi = val->definition()->AsPhi();
1730	if ((used_phi != nullptr) && !used_phi->is_alive()) {
1731	used_phi->mark_alive();
1732	live_phis->Add(used_phi);
1733	}
1734	}
1735	}
1736
1737	for (BlockIterator it(postorder_iterator()); !it.Done(); it.Advance()) {
1738	JoinEntryInstr* join = it.Current()->AsJoinEntry();
1739	if (join != nullptr) join->RemoveDeadPhis(replacement: constant_dead());
1740	}
1741	}
1742
1743	RedefinitionInstr* FlowGraph::EnsureRedefinition(Instruction* prev,
1744	Definition* original,
1745	CompileType compile_type) {
1746	RedefinitionInstr* first = prev->next()->AsRedefinition();
1747	if (first != nullptr && (first->constrained_type() != nullptr)) {
1748	if ((first->value()->definition() == original) &&
1749	first->constrained_type()->IsEqualTo(other: &compile_type)) {
1750	// Already redefined. Do nothing.
1751	return nullptr;
1752	}
1753	}
1754	RedefinitionInstr* redef = new RedefinitionInstr(new Value(original));
1755
1756	// Don't set the constrained type when the type is None(), which denotes an
1757	// unreachable value (e.g. using value null after some form of null check).
1758	if (!compile_type.IsNone()) {
1759	redef->set_constrained_type(new CompileType(compile_type));
1760	}
1761
1762	InsertAfter(prev, instr: redef, env: nullptr, use_kind: FlowGraph::kValue);
1763	RenameDominatedUses(def: original, dom: redef, other: redef);
1764
1765	if (redef->input_use_list() == nullptr) {
1766	// There are no dominated uses, so the newly added Redefinition is useless.
1767	// Remove Redefinition to avoid interfering with
1768	// BranchSimplifier::Simplify which needs empty blocks.
1769	redef->RemoveFromGraph();
1770	return nullptr;
1771	}
1772
1773	return redef;
1774	}
1775
1776	void FlowGraph::RemoveRedefinitions(bool keep_checks) {
1777	// Remove redefinition and check instructions that were inserted
1778	// to make a control dependence explicit with a data dependence,
1779	// for example, to inhibit hoisting.
1780	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
1781	block_it.Advance()) {
1782	thread()->CheckForSafepoint();
1783	for (ForwardInstructionIterator instr_it(block_it.Current());
1784	!instr_it.Done(); instr_it.Advance()) {
1785	Instruction* instruction = instr_it.Current();
1786	if (auto redef = instruction->AsRedefinition()) {
1787	redef->ReplaceUsesWith(other: redef->value()->definition());
1788	instr_it.RemoveCurrentFromGraph();
1789	} else if (keep_checks) {
1790	continue;
1791	} else if (auto def = instruction->AsDefinition()) {
1792	Value* value = def->RedefinedValue();
1793	if (value != nullptr) {
1794	def->ReplaceUsesWith(other: value->definition());
1795	def->ClearSSATempIndex();
1796	}
1797	}
1798	}
1799	}
1800	}
1801
1802	BitVector* FlowGraph::FindLoopBlocks(BlockEntryInstr* m,
1803	BlockEntryInstr* n) const {
1804	GrowableArray<BlockEntryInstr*> stack;
1805	BitVector* loop_blocks = new (zone()) BitVector(zone(), preorder_.length());
1806
1807	loop_blocks->Add(i: n->preorder_number());
1808	if (n != m) {
1809	loop_blocks->Add(i: m->preorder_number());
1810	stack.Add(m);
1811	}
1812
1813	while (!stack.is_empty()) {
1814	BlockEntryInstr* p = stack.RemoveLast();
1815	for (intptr_t i = 0; i < p->PredecessorCount(); ++i) {
1816	BlockEntryInstr* q = p->PredecessorAt(index: i);
1817	if (!loop_blocks->Contains(i: q->preorder_number())) {
1818	loop_blocks->Add(i: q->preorder_number());
1819	stack.Add(q);
1820	}
1821	}
1822	}
1823	return loop_blocks;
1824	}
1825
1826	LoopHierarchy* FlowGraph::ComputeLoops() const {
1827	// Iterate over all entry blocks in the flow graph to attach
1828	// loop information to each loop header.
1829	ZoneGrowableArray<BlockEntryInstr*>* loop_headers =
1830	new (zone()) ZoneGrowableArray<BlockEntryInstr*>();
1831	for (BlockIterator it = postorder_iterator(); !it.Done(); it.Advance()) {
1832	BlockEntryInstr* block = it.Current();
1833	// Reset loop information on every entry block (since this method
1834	// may recompute loop information on a modified flow graph).
1835	block->set_loop_info(nullptr);
1836	// Iterate over predecessors to find back edges.
1837	for (intptr_t i = 0; i < block->PredecessorCount(); ++i) {
1838	BlockEntryInstr* pred = block->PredecessorAt(index: i);
1839	if (block->Dominates(other: pred)) {
1840	// Identify the block as a loop header and add the blocks in the
1841	// loop to the loop information. Loops that share the same loop
1842	// header are treated as one loop by merging these blocks.
1843	BitVector* loop_blocks = FindLoopBlocks(m: pred, n: block);
1844	if (block->loop_info() == nullptr) {
1845	intptr_t id = loop_headers->length();
1846	block->set_loop_info(new (zone()) LoopInfo(id, block, loop_blocks));
1847	loop_headers->Add(value: block);
1848	} else {
1849	ASSERT(block->loop_info()->header() == block);
1850	block->loop_info()->AddBlocks(blocks: loop_blocks);
1851	}
1852	block->loop_info()->AddBackEdge(block: pred);
1853	}
1854	}
1855	}
1856
1857	// Build the loop hierarchy and link every entry block to
1858	// the closest enveloping loop in loop hierarchy.
1859	return new (zone()) LoopHierarchy(loop_headers, preorder_);
1860	}
1861
1862	intptr_t FlowGraph::InstructionCount() const {
1863	intptr_t size = 0;
1864	// Iterate each block, skipping the graph entry.
1865	for (intptr_t i = 1; i < preorder_.length(); ++i) {
1866	BlockEntryInstr* block = preorder_[i];
1867
1868	// Skip any blocks from the prologue to make them not count towards the
1869	// inlining instruction budget.
1870	const intptr_t block_id = block->block_id();
1871	if (prologue_info_.Contains(block_id)) {
1872	continue;
1873	}
1874
1875	for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
1876	++size;
1877	}
1878	}
1879	return size;
1880	}
1881
1882	void FlowGraph::ConvertUse(Value* use, Representation from_rep) {
1883	const Representation to_rep =
1884	use->instruction()->RequiredInputRepresentation(idx: use->use_index());
1885	if (from_rep == to_rep || to_rep == kNoRepresentation) {
1886	return;
1887	}
1888	InsertConversion(from: from_rep, to: to_rep, use, /*is_environment_use=*/false);
1889	}
1890
1891	static bool IsUnboxedInteger(Representation rep) {
1892	return (rep == kUnboxedInt32) || (rep == kUnboxedUint32) ||
1893	(rep == kUnboxedInt64);
1894	}
1895
1896	static bool ShouldInlineSimd() {
1897	return FlowGraphCompiler::SupportsUnboxedSimd128();
1898	}
1899
1900	static bool CanUnboxDouble() {
1901	return FlowGraphCompiler::SupportsUnboxedDoubles();
1902	}
1903
1904	static bool CanConvertInt64ToDouble() {
1905	return FlowGraphCompiler::CanConvertInt64ToDouble();
1906	}
1907
1908	void FlowGraph::InsertConversion(Representation from,
1909	Representation to,
1910	Value* use,
1911	bool is_environment_use) {
1912	ASSERT(from != to);
1913	Instruction* insert_before;
1914	PhiInstr* phi = use->instruction()->AsPhi();
1915	if (phi != nullptr) {
1916	ASSERT(phi->is_alive());
1917	// For phis conversions have to be inserted in the predecessor.
1918	auto predecessor = phi->block()->PredecessorAt(index: use->use_index());
1919	insert_before = predecessor->last_instruction();
1920	ASSERT(insert_before->GetBlock() == predecessor);
1921	} else {
1922	insert_before = use->instruction();
1923	}
1924	const Instruction::SpeculativeMode speculative_mode =
1925	use->instruction()->SpeculativeModeOfInput(index: use->use_index());
1926	Instruction* deopt_target = nullptr;
1927	if (speculative_mode == Instruction::kGuardInputs || to == kUnboxedInt32) {
1928	deopt_target = insert_before;
1929	}
1930
1931	Definition* converted = nullptr;
1932	if (IsUnboxedInteger(rep: from) && IsUnboxedInteger(rep: to)) {
1933	const intptr_t deopt_id = (to == kUnboxedInt32) && (deopt_target != nullptr)
1934	? deopt_target->DeoptimizationTarget()
1935	: DeoptId::kNone;
1936	converted =
1937	new (Z) IntConverterInstr(from, to, use->CopyWithType(), deopt_id);
1938	} else if ((from == kUnboxedInt32) && (to == kUnboxedDouble)) {
1939	converted = new Int32ToDoubleInstr(use->CopyWithType());
1940	} else if ((from == kUnboxedInt64) && (to == kUnboxedDouble) &&
1941	CanConvertInt64ToDouble()) {
1942	const intptr_t deopt_id = (deopt_target != nullptr)
1943	? deopt_target->DeoptimizationTarget()
1944	: DeoptId::kNone;
1945	ASSERT(CanUnboxDouble());
1946	converted = new Int64ToDoubleInstr(use->CopyWithType(), deopt_id);
1947	} else if ((from == kTagged) && Boxing::Supports(rep: to)) {
1948	const intptr_t deopt_id = (deopt_target != nullptr)
1949	? deopt_target->DeoptimizationTarget()
1950	: DeoptId::kNone;
1951	converted =
1952	UnboxInstr::Create(to, value: use->CopyWithType(), deopt_id, speculative_mode);
1953	} else if ((to == kTagged) && Boxing::Supports(rep: from)) {
1954	converted = BoxInstr::Create(from, value: use->CopyWithType());
1955	} else if ((to == kPairOfTagged) && (from == kTagged)) {
1956	// Insert conversion to an unboxed record, which can be only used
1957	// in Return instruction.
1958	ASSERT(use->instruction()->IsReturn());
1959	Definition* x = new (Z)
1960	LoadFieldInstr(use->CopyWithType(),
1961	Slot::GetRecordFieldSlot(
1962	thread: thread(), offset_in_bytes: compiler::target::Record::field_offset(index: 0)),
1963	InstructionSource());
1964	InsertBefore(next: insert_before, instr: x, env: nullptr, use_kind: FlowGraph::kValue);
1965	Definition* y = new (Z)
1966	LoadFieldInstr(use->CopyWithType(),
1967	Slot::GetRecordFieldSlot(
1968	thread: thread(), offset_in_bytes: compiler::target::Record::field_offset(index: 1)),
1969	InstructionSource());
1970	InsertBefore(next: insert_before, instr: y, env: nullptr, use_kind: FlowGraph::kValue);
1971	converted = new (Z) MakePairInstr(new (Z) Value(x), new (Z) Value(y));
1972	} else if ((to == kTagged) && (from == kPairOfTagged)) {
1973	// Handled in FlowGraph::InsertRecordBoxing.
1974	UNREACHABLE();
1975	} else {
1976	// We have failed to find a suitable conversion instruction.
1977	// Insert two "dummy" conversion instructions with the correct
1978	// "from" and "to" representation. The inserted instructions will
1979	// trigger a deoptimization if executed. See #12417 for a discussion.
1980	// If the use is not speculative, then this code should be unreachable.
1981	// Insert Stop for a graceful error and aid unreachable code elimination.
1982	if (speculative_mode == Instruction::kNotSpeculative) {
1983	StopInstr* stop = new (Z) StopInstr("Incompatible conversion.");
1984	InsertBefore(next: insert_before, instr: stop, env: nullptr, use_kind: FlowGraph::kEffect);
1985	}
1986	const intptr_t deopt_id = (deopt_target != nullptr)
1987	? deopt_target->DeoptimizationTarget()
1988	: DeoptId::kNone;
1989	ASSERT(Boxing::Supports(from));
1990	ASSERT(Boxing::Supports(to));
1991	Definition* boxed = BoxInstr::Create(from, value: use->CopyWithType());
1992	use->BindTo(def: boxed);
1993	InsertBefore(next: insert_before, instr: boxed, env: nullptr, use_kind: FlowGraph::kValue);
1994	converted = UnboxInstr::Create(to, value: new (Z) Value(boxed), deopt_id,
1995	speculative_mode);
1996	}
1997	ASSERT(converted != nullptr);
1998	InsertBefore(next: insert_before, instr: converted,
1999	env: (deopt_target != nullptr) ? deopt_target->env() : nullptr,
2000	use_kind: FlowGraph::kValue);
2001	if (is_environment_use) {
2002	use->BindToEnvironment(def: converted);
2003	} else {
2004	use->BindTo(def: converted);
2005	}
2006	}
2007
2008	static bool NeedsRecordBoxing(Definition* def) {
2009	if (def->env_use_list() != nullptr) return true;
2010	for (Value::Iterator it(def->input_use_list()); !it.Done(); it.Advance()) {
2011	Value* use = it.Current();
2012	if (use->instruction()->RequiredInputRepresentation(idx: use->use_index()) !=
2013	kPairOfTagged) {
2014	return true;
2015	}
2016	}
2017	return false;
2018	}
2019
2020	void FlowGraph::InsertRecordBoxing(Definition* def) {
2021	// Insert conversion from unboxed record, which can be only returned
2022	// by a Dart call with a known interface/direct target.
2023	const Function* target = nullptr;
2024	if (auto* call = def->AsStaticCall()) {
2025	target = &(call->function());
2026	} else if (auto* call = def->AsInstanceCallBase()) {
2027	target = &(call->interface_target());
2028	} else if (auto* call = def->AsDispatchTableCall()) {
2029	target = &(call->interface_target());
2030	} else {
2031	UNREACHABLE();
2032	}
2033	ASSERT(target != nullptr && !target->IsNull());
2034
2035	kernel::UnboxingInfoMetadata* unboxing_metadata =
2036	kernel::UnboxingInfoMetadataOf(function: *target, Z);
2037	ASSERT(unboxing_metadata != nullptr);
2038	const RecordShape shape = unboxing_metadata->return_info.record_shape;
2039	ASSERT(shape.num_fields() == 2);
2040
2041	auto* x = new (Z)
2042	ExtractNthOutputInstr(new (Z) Value(def), 0, kTagged, kDynamicCid);
2043	auto* y = new (Z)
2044	ExtractNthOutputInstr(new (Z) Value(def), 1, kTagged, kDynamicCid);
2045	auto* alloc = new (Z)
2046	AllocateSmallRecordInstr(InstructionSource(), shape, new (Z) Value(x),
2047	new (Z) Value(y), nullptr, def->deopt_id());
2048	def->ReplaceUsesWith(other: alloc);
2049	// Uses of 'def' in 'x' and 'y' should not be replaced as 'x' and 'y'
2050	// are not added to the flow graph yet.
2051	ASSERT(x->value()->definition() == def);
2052	ASSERT(y->value()->definition() == def);
2053	Instruction* insert_before = def->next();
2054	ASSERT(insert_before != nullptr);
2055	InsertBefore(next: insert_before, instr: x, env: nullptr, use_kind: FlowGraph::kValue);
2056	InsertBefore(next: insert_before, instr: y, env: nullptr, use_kind: FlowGraph::kValue);
2057	InsertBefore(next: insert_before, instr: alloc, env: def->env(), use_kind: FlowGraph::kValue);
2058	}
2059
2060	void FlowGraph::InsertConversionsFor(Definition* def) {
2061	const Representation from_rep = def->representation();
2062
2063	// Insert boxing of a record once after the definition (if needed)
2064	// in order to avoid multiple allocations.
2065	if (from_rep == kPairOfTagged) {
2066	if (NeedsRecordBoxing(def)) {
2067	InsertRecordBoxing(def);
2068	}
2069	return;
2070	}
2071
2072	for (Value::Iterator it(def->input_use_list()); !it.Done(); it.Advance()) {
2073	ConvertUse(use: it.Current(), from_rep);
2074	}
2075	}
2076
2077	namespace {
2078	class PhiUnboxingHeuristic : public ValueObject {
2079	public:
2080	explicit PhiUnboxingHeuristic(FlowGraph* flow_graph)
2081	: worklist_(flow_graph, 10) {}
2082
2083	void Process(PhiInstr* phi) {
2084	Representation unboxed = phi->representation();
2085
2086	switch (phi->Type()->ToCid()) {
2087	case kDoubleCid:
2088	if (CanUnboxDouble()) {
2089	// Could be UnboxedDouble or UnboxedFloat
2090	unboxed = DetermineIfAnyIncomingUnboxedFloats(phi) ? kUnboxedFloat
2091	: kUnboxedDouble;
2092	#if defined(DEBUG)
2093	if (unboxed == kUnboxedFloat) {
2094	for (auto input : phi->inputs()) {
2095	ASSERT(input->representation() != kUnboxedDouble);
2096	}
2097	}
2098	#endif
2099	}
2100	break;
2101	case kFloat32x4Cid:
2102	if (ShouldInlineSimd()) {
2103	unboxed = kUnboxedFloat32x4;
2104	}
2105	break;
2106	case kInt32x4Cid:
2107	if (ShouldInlineSimd()) {
2108	unboxed = kUnboxedInt32x4;
2109	}
2110	break;
2111	case kFloat64x2Cid:
2112	if (ShouldInlineSimd()) {
2113	unboxed = kUnboxedFloat64x2;
2114	}
2115	break;
2116	}
2117
2118	// If all the inputs are unboxed, leave the Phi unboxed.
2119	if ((unboxed == kTagged) && phi->Type()->IsInt()) {
2120	bool should_unbox = true;
2121	Representation new_representation = kTagged;
2122	for (auto input : phi->inputs()) {
2123	if (input == phi) continue;
2124
2125	if (!IsUnboxedInteger(input->representation())) {
2126	should_unbox = false;
2127	break;
2128	}
2129
2130	if (new_representation == kTagged) {
2131	new_representation = input->representation();
2132	} else if (new_representation != input->representation()) {
2133	new_representation = kNoRepresentation;
2134	}
2135	}
2136
2137	if (should_unbox) {
2138	unboxed =
2139	new_representation != kNoRepresentation ? new_representation
2140	: RangeUtils::Fits(range: phi->range(), size: RangeBoundary::kRangeBoundaryInt32)
2141	? kUnboxedInt32
2142	: kUnboxedInt64;
2143	}
2144	}
2145
2146	// Decide if it is worth to unbox an integer phi.
2147	if ((unboxed == kTagged) && phi->Type()->IsInt() &&
2148	!phi->Type()->can_be_sentinel()) {
2149	#if defined(TARGET_ARCH_IS_64_BIT)
2150	// In AOT mode on 64-bit platforms always unbox integer typed phis
2151	// (similar to how we treat doubles and other boxed numeric types).
2152	// In JIT mode only unbox phis which are not fully known to be Smi.
2153	if (is_aot_ || phi->Type()->ToCid() != kSmiCid) {
2154	unboxed = kUnboxedInt64;
2155	}
2156	#else
2157	// If we are on a 32-bit platform check if there are unboxed values
2158	// flowing into the phi and the phi value itself is flowing into an
2159	// unboxed operation prefer to keep it unboxed.
2160	// We use this heuristic instead of eagerly unboxing all the phis
2161	// because we are concerned about the code size and register pressure.
2162	const bool has_unboxed_incoming_value = HasUnboxedIncomingValue(phi);
2163	const bool flows_into_unboxed_use = FlowsIntoUnboxedUse(phi);
2164
2165	if (has_unboxed_incoming_value && flows_into_unboxed_use) {
2166	unboxed =
2167	RangeUtils::Fits(phi->range(), RangeBoundary::kRangeBoundaryInt32)
2168	? kUnboxedInt32
2169	: kUnboxedInt64;
2170	}
2171	#endif
2172	}
2173
2174	phi->set_representation(unboxed);
2175	}
2176
2177	private:
2178	// Returns [true] if there are UnboxedFloats representation flowing into
2179	// the |phi|.
2180	// This function looks through phis.
2181	bool DetermineIfAnyIncomingUnboxedFloats(PhiInstr* phi) {
2182	worklist_.Clear();
2183	worklist_.Add(phi);
2184	for (intptr_t i = 0; i < worklist_.definitions().length(); i++) {
2185	const auto defn = worklist_.definitions()[i];
2186	for (auto input : defn->inputs()) {
2187	if (input->representation() == kUnboxedFloat) {
2188	return true;
2189	}
2190	if (input->IsPhi()) {
2191	worklist_.Add(input);
2192	}
2193	}
2194	}
2195	return false;
2196	}
2197
2198	// Returns |true| iff there is an unboxed definition among all potential
2199	// definitions that can flow into the |phi|.
2200	// This function looks through phis.
2201	bool HasUnboxedIncomingValue(PhiInstr* phi) {
2202	worklist_.Clear();
2203	worklist_.Add(phi);
2204	for (intptr_t i = 0; i < worklist_.definitions().length(); i++) {
2205	const auto defn = worklist_.definitions()[i];
2206	for (auto input : defn->inputs()) {
2207	if (IsUnboxedInteger(input->representation()) || input->IsBox()) {
2208	return true;
2209	} else if (input->IsPhi()) {
2210	worklist_.Add(input);
2211	}
2212	}
2213	}
2214	return false;
2215	}
2216
2217	// Returns |true| iff |phi| potentially flows into an unboxed use.
2218	// This function looks through phis.
2219	bool FlowsIntoUnboxedUse(PhiInstr* phi) {
2220	worklist_.Clear();
2221	worklist_.Add(phi);
2222	for (intptr_t i = 0; i < worklist_.definitions().length(); i++) {
2223	const auto defn = worklist_.definitions()[i];
2224	for (auto use : defn->input_uses()) {
2225	if (IsUnboxedInteger(use->instruction()->RequiredInputRepresentation(
2226	use->use_index())) ||
2227	use->instruction()->IsUnbox()) {
2228	return true;
2229	} else if (auto phi_use = use->instruction()->AsPhi()) {
2230	worklist_.Add(phi_use);
2231	}
2232	}
2233	}
2234	return false;
2235	}
2236
2237	const bool is_aot_ = CompilerState::Current().is_aot();
2238	DefinitionWorklist worklist_;
2239	};
2240	} // namespace
2241
2242	void FlowGraph::SelectRepresentations() {
2243	// First we decide for each phi if it is beneficial to unbox it. If so, we
2244	// change it's `phi->representation()`
2245	PhiUnboxingHeuristic phi_unboxing_heuristic(this);
2246	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
2247	block_it.Advance()) {
2248	JoinEntryInstr* join_entry = block_it.Current()->AsJoinEntry();
2249	if (join_entry != nullptr) {
2250	for (PhiIterator it(join_entry); !it.Done(); it.Advance()) {
2251	PhiInstr* phi = it.Current();
2252	phi_unboxing_heuristic.Process(phi);
2253	}
2254	}
2255	}
2256
2257	// Process all initial definitions and insert conversions when needed (depends
2258	// on phi unboxing decision above).
2259	for (intptr_t i = 0; i < graph_entry()->initial_definitions()->length();
2260	i++) {
2261	InsertConversionsFor(def: (*graph_entry()->initial_definitions())[i]);
2262	}
2263	for (intptr_t i = 0; i < graph_entry()->SuccessorCount(); ++i) {
2264	auto successor = graph_entry()->SuccessorAt(index: i);
2265	if (auto entry = successor->AsBlockEntryWithInitialDefs()) {
2266	auto& initial_definitions = *entry->initial_definitions();
2267	for (intptr_t j = 0; j < initial_definitions.length(); j++) {
2268	InsertConversionsFor(def: initial_definitions[j]);
2269	}
2270	}
2271	}
2272
2273	// Process all normal definitions and insert conversions when needed (depends
2274	// on phi unboxing decision above).
2275	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
2276	block_it.Advance()) {
2277	BlockEntryInstr* entry = block_it.Current();
2278	if (JoinEntryInstr* join_entry = entry->AsJoinEntry()) {
2279	for (PhiIterator it(join_entry); !it.Done(); it.Advance()) {
2280	PhiInstr* phi = it.Current();
2281	ASSERT(phi != nullptr);
2282	ASSERT(phi->is_alive());
2283	InsertConversionsFor(phi);
2284	}
2285	}
2286	for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
2287	Definition* def = it.Current()->AsDefinition();
2288	if (def != nullptr) {
2289	InsertConversionsFor(def);
2290	}
2291	}
2292	}
2293	}
2294
2295	#if defined(TARGET_ARCH_ARM) || defined(TARGET_ARCH_IA32)
2296	// Smi widening pass is only meaningful on platforms where Smi
2297	// is smaller than 32bit. For now only support it on ARM and ia32.
2298	static bool CanBeWidened(BinarySmiOpInstr* smi_op) {
2299	return BinaryInt32OpInstr::IsSupported(smi_op->op_kind(), smi_op->left(),
2300	smi_op->right());
2301	}
2302
2303	static bool BenefitsFromWidening(BinarySmiOpInstr* smi_op) {
2304	// TODO(vegorov): when shifts with non-constants shift count are supported
2305	// add them here as we save untagging for the count.
2306	switch (smi_op->op_kind()) {
2307	case Token::kMUL:
2308	case Token::kSHR:
2309	case Token::kUSHR:
2310	// For kMUL we save untagging of the argument.
2311	// For kSHR/kUSHR we save tagging of the result.
2312	return true;
2313
2314	default:
2315	return false;
2316	}
2317	}
2318
2319	// Maps an entry block to its closest enveloping loop id, or -1 if none.
2320	static intptr_t LoopId(BlockEntryInstr* block) {
2321	LoopInfo* loop = block->loop_info();
2322	if (loop != nullptr) {
2323	return loop->id();
2324	}
2325	return -1;
2326	}
2327
2328	void FlowGraph::WidenSmiToInt32() {
2329	if (!FLAG_use_smi_widening) {
2330	return;
2331	}
2332
2333	GrowableArray<BinarySmiOpInstr*> candidates;
2334
2335	// Step 1. Collect all instructions that potentially benefit from widening of
2336	// their operands (or their result) into int32 range.
2337	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
2338	block_it.Advance()) {
2339	for (ForwardInstructionIterator instr_it(block_it.Current());
2340	!instr_it.Done(); instr_it.Advance()) {
2341	BinarySmiOpInstr* smi_op = instr_it.Current()->AsBinarySmiOp();
2342	if ((smi_op != nullptr) && smi_op->HasSSATemp() &&
2343	BenefitsFromWidening(smi_op) && CanBeWidened(smi_op)) {
2344	candidates.Add(smi_op);
2345	}
2346	}
2347	}
2348
2349	if (candidates.is_empty()) {
2350	return;
2351	}
2352
2353	// Step 2. For each block in the graph compute which loop it belongs to.
2354	// We will use this information later during computation of the widening's
2355	// gain: we are going to assume that only conversion occurring inside the
2356	// same loop should be counted against the gain, all other conversions
2357	// can be hoisted and thus cost nothing compared to the loop cost itself.
2358	GetLoopHierarchy();
2359
2360	// Step 3. For each candidate transitively collect all other BinarySmiOpInstr
2361	// and PhiInstr that depend on it and that it depends on and count amount of
2362	// untagging operations that we save in assumption that this whole graph of
2363	// values is using kUnboxedInt32 representation instead of kTagged.
2364	// Convert those graphs that have positive gain to kUnboxedInt32.
2365
2366	// BitVector containing SSA indexes of all processed definitions. Used to skip
2367	// those candidates that belong to dependency graph of another candidate.
2368	BitVector* processed = new (Z) BitVector(Z, current_ssa_temp_index());
2369
2370	// Worklist used to collect dependency graph.
2371	DefinitionWorklist worklist(this, candidates.length());
2372	for (intptr_t i = 0; i < candidates.length(); i++) {
2373	BinarySmiOpInstr* op = candidates[i];
2374	if (op->WasEliminated() || processed->Contains(op->ssa_temp_index())) {
2375	continue;
2376	}
2377
2378	if (FLAG_support_il_printer && FLAG_trace_smi_widening) {
2379	THR_Print("analysing candidate: %s\n", op->ToCString());
2380	}
2381	worklist.Clear();
2382	worklist.Add(op);
2383
2384	// Collect dependency graph. Note: more items are added to worklist
2385	// inside this loop.
2386	intptr_t gain = 0;
2387	for (intptr_t j = 0; j < worklist.definitions().length(); j++) {
2388	Definition* defn = worklist.definitions()[j];
2389
2390	if (FLAG_support_il_printer && FLAG_trace_smi_widening) {
2391	THR_Print("> %s\n", defn->ToCString());
2392	}
2393
2394	if (defn->IsBinarySmiOp() &&
2395	BenefitsFromWidening(defn->AsBinarySmiOp())) {
2396	gain++;
2397	if (FLAG_support_il_printer && FLAG_trace_smi_widening) {
2398	THR_Print("^ [%" Pd "] (o) %s\n", gain, defn->ToCString());
2399	}
2400	}
2401
2402	const intptr_t defn_loop = LoopId(defn->GetBlock());
2403
2404	// Process all inputs.
2405	for (intptr_t k = 0; k < defn->InputCount(); k++) {
2406	Definition* input = defn->InputAt(k)->definition();
2407	if (input->IsBinarySmiOp() && CanBeWidened(input->AsBinarySmiOp())) {
2408	worklist.Add(input);
2409	} else if (input->IsPhi() && (input->Type()->ToCid() == kSmiCid)) {
2410	worklist.Add(input);
2411	} else if (input->IsBinaryInt64Op()) {
2412	// Mint operation produces untagged result. We avoid tagging.
2413	gain++;
2414	if (FLAG_support_il_printer && FLAG_trace_smi_widening) {
2415	THR_Print("^ [%" Pd "] (i) %s\n", gain, input->ToCString());
2416	}
2417	} else if (defn_loop == LoopId(input->GetBlock()) &&
2418	(input->Type()->ToCid() == kSmiCid)) {
2419	// Input comes from the same loop, is known to be smi and requires
2420	// untagging.
2421	// TODO(vegorov) this heuristic assumes that values that are not
2422	// known to be smi have to be checked and this check can be
2423	// coalesced with untagging. Start coalescing them.
2424	gain--;
2425	if (FLAG_support_il_printer && FLAG_trace_smi_widening) {
2426	THR_Print("v [%" Pd "] (i) %s\n", gain, input->ToCString());
2427	}
2428	}
2429	}
2430
2431	// Process all uses.
2432	for (Value* use = defn->input_use_list(); use != nullptr;
2433	use = use->next_use()) {
2434	Instruction* instr = use->instruction();
2435	Definition* use_defn = instr->AsDefinition();
2436	if (use_defn == nullptr) {
2437	// We assume that tagging before returning or pushing argument costs
2438	// very little compared to the cost of the return/call itself.
2439	ASSERT(!instr->IsMoveArgument());
2440	if (!instr->IsReturn() &&
2441	(use->use_index() >= instr->ArgumentCount())) {
2442	gain--;
2443	if (FLAG_support_il_printer && FLAG_trace_smi_widening) {
2444	THR_Print("v [%" Pd "] (u) %s\n", gain,
2445	use->instruction()->ToCString());
2446	}
2447	}
2448	continue;
2449	} else if (use_defn->IsBinarySmiOp() &&
2450	CanBeWidened(use_defn->AsBinarySmiOp())) {
2451	worklist.Add(use_defn);
2452	} else if (use_defn->IsPhi() &&
2453	use_defn->AsPhi()->Type()->ToCid() == kSmiCid) {
2454	worklist.Add(use_defn);
2455	} else if (use_defn->IsBinaryInt64Op()) {
2456	// BinaryInt64Op requires untagging of its inputs.
2457	// Converting kUnboxedInt32 to kUnboxedInt64 is essentially zero cost
2458	// sign extension operation.
2459	gain++;
2460	if (FLAG_support_il_printer && FLAG_trace_smi_widening) {
2461	THR_Print("^ [%" Pd "] (u) %s\n", gain,
2462	use->instruction()->ToCString());
2463	}
2464	} else if (defn_loop == LoopId(instr->GetBlock())) {
2465	gain--;
2466	if (FLAG_support_il_printer && FLAG_trace_smi_widening) {
2467	THR_Print("v [%" Pd "] (u) %s\n", gain,
2468	use->instruction()->ToCString());
2469	}
2470	}
2471	}
2472	}
2473
2474	processed->AddAll(worklist.contains_vector());
2475
2476	if (FLAG_support_il_printer && FLAG_trace_smi_widening) {
2477	THR_Print("~ %s gain %" Pd "\n", op->ToCString(), gain);
2478	}
2479
2480	if (gain > 0) {
2481	// We have positive gain from widening. Convert all BinarySmiOpInstr into
2482	// BinaryInt32OpInstr and set representation of all phis to kUnboxedInt32.
2483	for (intptr_t j = 0; j < worklist.definitions().length(); j++) {
2484	Definition* defn = worklist.definitions()[j];
2485	ASSERT(defn->IsPhi() || defn->IsBinarySmiOp());
2486
2487	// Since we widen the integer representation we've to clear out type
2488	// propagation information (e.g. it might no longer be a _Smi).
2489	for (Value::Iterator it(defn->input_use_list()); !it.Done();
2490	it.Advance()) {
2491	it.Current()->SetReachingType(nullptr);
2492	}
2493
2494	if (defn->IsBinarySmiOp()) {
2495	BinarySmiOpInstr* smi_op = defn->AsBinarySmiOp();
2496	BinaryInt32OpInstr* int32_op = new (Z) BinaryInt32OpInstr(
2497	smi_op->op_kind(), smi_op->left()->CopyWithType(),
2498	smi_op->right()->CopyWithType(), smi_op->DeoptimizationTarget());
2499
2500	smi_op->ReplaceWith(int32_op, nullptr);
2501	} else if (defn->IsPhi()) {
2502	defn->AsPhi()->set_representation(kUnboxedInt32);
2503	ASSERT(defn->Type()->IsInt());
2504	}
2505	}
2506	}
2507	}
2508	}
2509	#else
2510	void FlowGraph::WidenSmiToInt32() {
2511	// TODO(vegorov) ideally on 64-bit platforms we would like to narrow smi
2512	// operations to 32-bit where it saves tagging and untagging and allows
2513	// to use shorted (and faster) instructions. But we currently don't
2514	// save enough range information in the ICData to drive this decision.
2515	}
2516	#endif
2517
2518	void FlowGraph::EliminateEnvironments() {
2519	// After this pass we can no longer perform LICM and hoist instructions
2520	// that can deoptimize.
2521
2522	disallow_licm();
2523	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
2524	block_it.Advance()) {
2525	BlockEntryInstr* block = block_it.Current();
2526	if (!block->IsCatchBlockEntry()) {
2527	block->RemoveEnvironment();
2528	}
2529	for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
2530	Instruction* current = it.Current();
2531	if (!current->ComputeCanDeoptimize() &&
2532	!current->ComputeCanDeoptimizeAfterCall() &&
2533	(!current->MayThrow() || !current->GetBlock()->InsideTryBlock())) {
2534	// Instructions that can throw need an environment for optimized
2535	// try-catch.
2536	// TODO(srdjan): --source-lines needs deopt environments to get at
2537	// the code for this instruction, however, leaving the environment
2538	// changes code.
2539	current->RemoveEnvironment();
2540	}
2541	}
2542	}
2543	}
2544
2545	bool FlowGraph::Canonicalize() {
2546	bool changed = false;
2547
2548	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
2549	block_it.Advance()) {
2550	BlockEntryInstr* const block = block_it.Current();
2551	if (auto join = block->AsJoinEntry()) {
2552	for (PhiIterator it(join); !it.Done(); it.Advance()) {
2553	PhiInstr* current = it.Current();
2554	if (current->HasUnmatchedInputRepresentations() &&
2555	(current->SpeculativeModeOfInputs() == Instruction::kGuardInputs)) {
2556	// Can't canonicalize this instruction until all conversions for its
2557	// speculative inputs are inserted.
2558	continue;
2559	}
2560
2561	Definition* replacement = current->Canonicalize(flow_graph: this);
2562	ASSERT(replacement != nullptr);
2563	RELEASE_ASSERT(unmatched_representations_allowed() ||
2564	!replacement->HasUnmatchedInputRepresentations());
2565	if (replacement != current) {
2566	current->ReplaceUsesWith(replacement);
2567	it.RemoveCurrentFromGraph();
2568	changed = true;
2569	}
2570	}
2571	}
2572	for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
2573	Instruction* current = it.Current();
2574	if (current->HasUnmatchedInputRepresentations() &&
2575	(current->SpeculativeModeOfInputs() == Instruction::kGuardInputs)) {
2576	// Can't canonicalize this instruction until all conversions for its
2577	// speculative inputs are inserted.
2578	continue;
2579	}
2580
2581	Instruction* replacement = current->Canonicalize(flow_graph: this);
2582
2583	if (replacement != current) {
2584	// For non-definitions Canonicalize should return either nullptr or
2585	// this.
2586	if (replacement != nullptr) {
2587	ASSERT(current->IsDefinition());
2588	if (!unmatched_representations_allowed()) {
2589	RELEASE_ASSERT(!replacement->HasUnmatchedInputRepresentations());
2590	if ((replacement->representation() != current->representation()) &&
2591	current->AsDefinition()->HasUses()) {
2592	// Can't canonicalize this instruction as unmatched
2593	// representations are not allowed at this point, but
2594	// replacement has a different representation.
2595	continue;
2596	}
2597	}
2598	}
2599	ReplaceCurrentInstruction(iterator: &it, current, replacement);
2600	changed = true;
2601	}
2602	}
2603	}
2604	return changed;
2605	}
2606
2607	void FlowGraph::PopulateWithICData(const Function& function) {
2608	Zone* zone = Thread::Current()->zone();
2609
2610	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
2611	block_it.Advance()) {
2612	ForwardInstructionIterator it(block_it.Current());
2613	for (; !it.Done(); it.Advance()) {
2614	Instruction* instr = it.Current();
2615	if (instr->IsInstanceCall()) {
2616	InstanceCallInstr* call = instr->AsInstanceCall();
2617	if (!call->HasICData()) {
2618	const Array& arguments_descriptor =
2619	Array::Handle(zone, call->GetArgumentsDescriptor());
2620	const ICData& ic_data = ICData::ZoneHandle(
2621	zone,
2622	ICData::New(function, call->function_name(), arguments_descriptor,
2623	call->deopt_id(), call->checked_argument_count(),
2624	ICData::kInstance));
2625	call->set_ic_data(&ic_data);
2626	}
2627	} else if (instr->IsStaticCall()) {
2628	StaticCallInstr* call = instr->AsStaticCall();
2629	if (!call->HasICData()) {
2630	const Array& arguments_descriptor =
2631	Array::Handle(zone, call->GetArgumentsDescriptor());
2632	const Function& target = call->function();
2633	int num_args_checked =
2634	MethodRecognizer::NumArgsCheckedForStaticCall(function: target);
2635	const ICData& ic_data = ICData::ZoneHandle(
2636	zone, ICData::NewForStaticCall(
2637	owner: function, target, arguments_descriptor,
2638	deopt_id: call->deopt_id(), num_args_tested: num_args_checked, rebind_rule: ICData::kStatic));
2639	call->set_ic_data(&ic_data);
2640	}
2641	}
2642	}
2643	}
2644	}
2645
2646	// Optimize (a << b) & c pattern: if c is a positive Smi or zero, then the
2647	// shift can be a truncating Smi shift-left and result is always Smi.
2648	// Merging occurs only per basic-block.
2649	void FlowGraph::TryOptimizePatterns() {
2650	if (!FLAG_truncating_left_shift) return;
2651	GrowableArray<BinarySmiOpInstr*> div_mod_merge;
2652	GrowableArray<InvokeMathCFunctionInstr*> sin_cos_merge;
2653	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
2654	block_it.Advance()) {
2655	// Merging only per basic-block.
2656	div_mod_merge.Clear();
2657	sin_cos_merge.Clear();
2658	ForwardInstructionIterator it(block_it.Current());
2659	for (; !it.Done(); it.Advance()) {
2660	if (it.Current()->IsBinarySmiOp()) {
2661	BinarySmiOpInstr* binop = it.Current()->AsBinarySmiOp();
2662	if (binop->op_kind() == Token::kBIT_AND) {
2663	OptimizeLeftShiftBitAndSmiOp(current_iterator: &it, bit_and_instr: binop, left_instr: binop->left()->definition(),
2664	right_instr: binop->right()->definition());
2665	} else if ((binop->op_kind() == Token::kTRUNCDIV) ||
2666	(binop->op_kind() == Token::kMOD)) {
2667	if (binop->HasUses()) {
2668	div_mod_merge.Add(binop);
2669	}
2670	}
2671	} else if (it.Current()->IsBinaryInt64Op()) {
2672	BinaryInt64OpInstr* mintop = it.Current()->AsBinaryInt64Op();
2673	if (mintop->op_kind() == Token::kBIT_AND) {
2674	OptimizeLeftShiftBitAndSmiOp(current_iterator: &it, bit_and_instr: mintop,
2675	left_instr: mintop->left()->definition(),
2676	right_instr: mintop->right()->definition());
2677	}
2678	} else if (it.Current()->IsInvokeMathCFunction()) {
2679	InvokeMathCFunctionInstr* math_unary =
2680	it.Current()->AsInvokeMathCFunction();
2681	if ((math_unary->recognized_kind() == MethodRecognizer::kMathSin) ||
2682	(math_unary->recognized_kind() == MethodRecognizer::kMathCos)) {
2683	if (math_unary->HasUses()) {
2684	sin_cos_merge.Add(math_unary);
2685	}
2686	}
2687	}
2688	}
2689	TryMergeTruncDivMod(merge_candidates: &div_mod_merge);
2690	}
2691	}
2692
2693	// Returns true if use is dominated by the given instruction.
2694	// Note: uses that occur at instruction itself are not dominated by it.
2695	static bool IsDominatedUse(Instruction* dom, Value* use) {
2696	BlockEntryInstr* dom_block = dom->GetBlock();
2697
2698	Instruction* instr = use->instruction();
2699
2700	PhiInstr* phi = instr->AsPhi();
2701	if (phi != nullptr) {
2702	return dom_block->Dominates(other: phi->block()->PredecessorAt(index: use->use_index()));
2703	}
2704
2705	BlockEntryInstr* use_block = instr->GetBlock();
2706	if (use_block == dom_block) {
2707	// Fast path for the case of block entry.
2708	if (dom_block == dom) return true;
2709
2710	for (Instruction* curr = dom->next(); curr != nullptr;
2711	curr = curr->next()) {
2712	if (curr == instr) return true;
2713	}
2714
2715	return false;
2716	}
2717
2718	return dom_block->Dominates(other: use_block);
2719	}
2720
2721	void FlowGraph::RenameDominatedUses(Definition* def,
2722	Instruction* dom,
2723	Definition* other) {
2724	for (Value::Iterator it(def->input_use_list()); !it.Done(); it.Advance()) {
2725	Value* use = it.Current();
2726	if (IsDominatedUse(dom, use)) {
2727	use->BindTo(def: other);
2728	}
2729	}
2730	}
2731
2732	void FlowGraph::RenameUsesDominatedByRedefinitions() {
2733	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
2734	block_it.Advance()) {
2735	for (ForwardInstructionIterator instr_it(block_it.Current());
2736	!instr_it.Done(); instr_it.Advance()) {
2737	Definition* definition = instr_it.Current()->AsDefinition();
2738	// CheckArrayBound instructions have their own mechanism for ensuring
2739	// proper dependencies, so we don't rewrite those here.
2740	if (definition != nullptr && !definition->IsCheckArrayBound()) {
2741	Value* redefined = definition->RedefinedValue();
2742	if (redefined != nullptr) {
2743	if (!definition->HasSSATemp()) {
2744	AllocateSSAIndex(def: definition);
2745	}
2746	Definition* original = redefined->definition();
2747	RenameDominatedUses(def: original, dom: definition, other: definition);
2748	}
2749	}
2750	}
2751	}
2752	}
2753
2754	static bool IsPositiveOrZeroSmiConst(Definition* d) {
2755	ConstantInstr* const_instr = d->AsConstant();
2756	if ((const_instr != nullptr) && (const_instr->value().IsSmi())) {
2757	return Smi::Cast(obj: const_instr->value()).Value() >= 0;
2758	}
2759	return false;
2760	}
2761
2762	static BinarySmiOpInstr* AsSmiShiftLeftInstruction(Definition* d) {
2763	BinarySmiOpInstr* instr = d->AsBinarySmiOp();
2764	if ((instr != nullptr) && (instr->op_kind() == Token::kSHL)) {
2765	return instr;
2766	}
2767	return nullptr;
2768	}
2769
2770	void FlowGraph::OptimizeLeftShiftBitAndSmiOp(
2771	ForwardInstructionIterator* current_iterator,
2772	Definition* bit_and_instr,
2773	Definition* left_instr,
2774	Definition* right_instr) {
2775	ASSERT(bit_and_instr != nullptr);
2776	ASSERT((left_instr != nullptr) && (right_instr != nullptr));
2777
2778	// Check for pattern, smi_shift_left must be single-use.
2779	bool is_positive_or_zero = IsPositiveOrZeroSmiConst(d: left_instr);
2780	if (!is_positive_or_zero) {
2781	is_positive_or_zero = IsPositiveOrZeroSmiConst(d: right_instr);
2782	}
2783	if (!is_positive_or_zero) return;
2784
2785	BinarySmiOpInstr* smi_shift_left = nullptr;
2786	if (bit_and_instr->InputAt(i: 0)->IsSingleUse()) {
2787	smi_shift_left = AsSmiShiftLeftInstruction(d: left_instr);
2788	}
2789	if ((smi_shift_left == nullptr) &&
2790	(bit_and_instr->InputAt(i: 1)->IsSingleUse())) {
2791	smi_shift_left = AsSmiShiftLeftInstruction(d: right_instr);
2792	}
2793	if (smi_shift_left == nullptr) return;
2794
2795	// Pattern recognized.
2796	smi_shift_left->mark_truncating();
2797	ASSERT(bit_and_instr->IsBinarySmiOp() || bit_and_instr->IsBinaryInt64Op());
2798	if (bit_and_instr->IsBinaryInt64Op()) {
2799	// Replace Mint op with Smi op.
2800	BinarySmiOpInstr* smi_op = new (Z) BinarySmiOpInstr(
2801	Token::kBIT_AND, new (Z) Value(left_instr), new (Z) Value(right_instr),
2802	DeoptId::kNone); // BIT_AND cannot deoptimize.
2803	bit_and_instr->ReplaceWith(other: smi_op, iterator: current_iterator);
2804	}
2805	}
2806
2807	// Dart:
2808	// var x = d % 10;
2809	// var y = d ~/ 10;
2810	// var z = x + y;
2811	//
2812	// IL:
2813	// v4 <- %(v2, v3)
2814	// v5 <- ~/(v2, v3)
2815	// v6 <- +(v4, v5)
2816	//
2817	// IL optimized:
2818	// v4 <- DIVMOD(v2, v3);
2819	// v5 <- LoadIndexed(v4, 0); // ~/ result
2820	// v6 <- LoadIndexed(v4, 1); // % result
2821	// v7 <- +(v5, v6)
2822	// Because of the environment it is important that merged instruction replaces
2823	// first original instruction encountered.
2824	void FlowGraph::TryMergeTruncDivMod(
2825	GrowableArray<BinarySmiOpInstr*>* merge_candidates) {
2826	if (merge_candidates->length() < 2) {
2827	// Need at least a TRUNCDIV and a MOD.
2828	return;
2829	}
2830	for (intptr_t i = 0; i < merge_candidates->length(); i++) {
2831	BinarySmiOpInstr* curr_instr = (*merge_candidates)[i];
2832	if (curr_instr == nullptr) {
2833	// Instruction was merged already.
2834	continue;
2835	}
2836	ASSERT((curr_instr->op_kind() == Token::kTRUNCDIV) ||
2837	(curr_instr->op_kind() == Token::kMOD));
2838	// Check if there is kMOD/kTRUNDIV binop with same inputs.
2839	const Token::Kind other_kind = (curr_instr->op_kind() == Token::kTRUNCDIV)
2840	? Token::kMOD
2841	: Token::kTRUNCDIV;
2842	Definition* left_def = curr_instr->left()->definition();
2843	Definition* right_def = curr_instr->right()->definition();
2844	for (intptr_t k = i + 1; k < merge_candidates->length(); k++) {
2845	BinarySmiOpInstr* other_binop = (*merge_candidates)[k];
2846	// 'other_binop' can be nullptr if it was already merged.
2847	if ((other_binop != nullptr) && (other_binop->op_kind() == other_kind) &&
2848	(other_binop->left()->definition() == left_def) &&
2849	(other_binop->right()->definition() == right_def)) {
2850	(*merge_candidates)[k] = nullptr; // Clear it.
2851	ASSERT(curr_instr->HasUses());
2852	AppendExtractNthOutputForMerged(
2853	instr: curr_instr, ix: TruncDivModInstr::OutputIndexOf(token: curr_instr->op_kind()),
2854	rep: kTagged, cid: kSmiCid);
2855	ASSERT(other_binop->HasUses());
2856	AppendExtractNthOutputForMerged(
2857	instr: other_binop,
2858	ix: TruncDivModInstr::OutputIndexOf(token: other_binop->op_kind()), rep: kTagged,
2859	cid: kSmiCid);
2860
2861	// Replace with TruncDivMod.
2862	TruncDivModInstr* div_mod = new (Z) TruncDivModInstr(
2863	curr_instr->left()->CopyWithType(),
2864	curr_instr->right()->CopyWithType(), curr_instr->deopt_id());
2865	curr_instr->ReplaceWith(other: div_mod, iterator: nullptr);
2866	other_binop->ReplaceUsesWith(other: div_mod);
2867	other_binop->RemoveFromGraph();
2868	// Only one merge possible. Because canonicalization happens later,
2869	// more candidates are possible.
2870	// TODO(srdjan): Allow merging of trunc-div/mod into truncDivMod.
2871	break;
2872	}
2873	}
2874	}
2875	}
2876
2877	void FlowGraph::AppendExtractNthOutputForMerged(Definition* instr,
2878	intptr_t index,
2879	Representation rep,
2880	intptr_t cid) {
2881	ExtractNthOutputInstr* extract =
2882	new (Z) ExtractNthOutputInstr(new (Z) Value(instr), index, rep, cid);
2883	instr->ReplaceUsesWith(other: extract);
2884	InsertAfter(prev: instr, instr: extract, env: nullptr, use_kind: FlowGraph::kValue);
2885	}
2886
2887	//
2888	// Static helpers for the flow graph utilities.
2889	//
2890
2891	static TargetEntryInstr* NewTarget(FlowGraph* graph, Instruction* inherit) {
2892	TargetEntryInstr* target = new (graph->zone())
2893	TargetEntryInstr(graph->allocate_block_id(),
2894	inherit->GetBlock()->try_index(), DeoptId::kNone);
2895	target->InheritDeoptTarget(graph->zone(), inherit);
2896	return target;
2897	}
2898
2899	static JoinEntryInstr* NewJoin(FlowGraph* graph, Instruction* inherit) {
2900	JoinEntryInstr* join = new (graph->zone())
2901	JoinEntryInstr(graph->allocate_block_id(),
2902	inherit->GetBlock()->try_index(), DeoptId::kNone);
2903	join->InheritDeoptTarget(graph->zone(), inherit);
2904	return join;
2905	}
2906
2907	static GotoInstr* NewGoto(FlowGraph* graph,
2908	JoinEntryInstr* target,
2909	Instruction* inherit) {
2910	GotoInstr* got = new (graph->zone()) GotoInstr(target, DeoptId::kNone);
2911	got->InheritDeoptTarget(zone: graph->zone(), other: inherit);
2912	return got;
2913	}
2914
2915	static BranchInstr* NewBranch(FlowGraph* graph,
2916	ComparisonInstr* cmp,
2917	Instruction* inherit) {
2918	BranchInstr* bra = new (graph->zone()) BranchInstr(cmp, DeoptId::kNone);
2919	bra->InheritDeoptTarget(zone: graph->zone(), other: inherit);
2920	return bra;
2921	}
2922
2923	//
2924	// Flow graph utilities.
2925	//
2926
2927	// Constructs new diamond decision at the given instruction.
2928	//
2929	// ENTRY
2930	// instruction
2931	// if (compare)
2932	// / \
2933	// B_TRUE B_FALSE
2934	// \ /
2935	// JOIN
2936	//
2937	JoinEntryInstr* FlowGraph::NewDiamond(Instruction* instruction,
2938	Instruction* inherit,
2939	ComparisonInstr* compare,
2940	TargetEntryInstr** b_true,
2941	TargetEntryInstr** b_false) {
2942	BlockEntryInstr* entry = instruction->GetBlock();
2943
2944	TargetEntryInstr* bt = NewTarget(graph: this, inherit);
2945	TargetEntryInstr* bf = NewTarget(graph: this, inherit);
2946	JoinEntryInstr* join = NewJoin(graph: this, inherit);
2947	GotoInstr* gotot = NewGoto(graph: this, target: join, inherit);
2948	GotoInstr* gotof = NewGoto(graph: this, target: join, inherit);
2949	BranchInstr* bra = NewBranch(graph: this, cmp: compare, inherit);
2950
2951	instruction->AppendInstruction(tail: bra);
2952	entry->set_last_instruction(bra);
2953
2954	*bra->true_successor_address() = bt;
2955	*bra->false_successor_address() = bf;
2956
2957	bt->AppendInstruction(gotot);
2958	bt->set_last_instruction(gotot);
2959
2960	bf->AppendInstruction(gotof);
2961	bf->set_last_instruction(gotof);
2962
2963	// Update dominance relation incrementally.
2964	for (intptr_t i = 0, n = entry->dominated_blocks().length(); i < n; ++i) {
2965	join->AddDominatedBlock(entry->dominated_blocks()[i]);
2966	}
2967	entry->ClearDominatedBlocks();
2968	entry->AddDominatedBlock(bt);
2969	entry->AddDominatedBlock(bf);
2970	entry->AddDominatedBlock(join);
2971
2972	// TODO(ajcbik): update pred/succ/ordering incrementally too.
2973
2974	// Return new blocks.
2975	*b_true = bt;
2976	*b_false = bf;
2977	return join;
2978	}
2979
2980	JoinEntryInstr* FlowGraph::NewDiamond(Instruction* instruction,
2981	Instruction* inherit,
2982	const LogicalAnd& condition,
2983	TargetEntryInstr** b_true,
2984	TargetEntryInstr** b_false) {
2985	// First diamond for first comparison.
2986	TargetEntryInstr* bt = nullptr;
2987	TargetEntryInstr* bf = nullptr;
2988	JoinEntryInstr* mid_point =
2989	NewDiamond(instruction, inherit, compare: condition.oper1, b_true: &bt, b_false: &bf);
2990
2991	// Short-circuit second comparison and connect through phi.
2992	condition.oper2->InsertAfter(bt);
2993	AllocateSSAIndex(def: condition.oper2);
2994	condition.oper2->InheritDeoptTarget(zone: zone(), other: inherit); // must inherit
2995	PhiInstr* phi =
2996	AddPhi(join: mid_point, d1: condition.oper2, d2: GetConstant(object: Bool::False()));
2997	StrictCompareInstr* circuit = new (zone()) StrictCompareInstr(
2998	inherit->source(), Token::kEQ_STRICT, new (zone()) Value(phi),
2999	new (zone()) Value(GetConstant(Bool::True())), false,
3000	DeoptId::kNone); // don't inherit
3001
3002	// Return new blocks through the second diamond.
3003	return NewDiamond(mid_point, inherit, circuit, b_true, b_false);
3004	}
3005
3006	PhiInstr* FlowGraph::AddPhi(JoinEntryInstr* join,
3007	Definition* d1,
3008	Definition* d2) {
3009	PhiInstr* phi = new (zone()) PhiInstr(join, 2);
3010	Value* v1 = new (zone()) Value(d1);
3011	Value* v2 = new (zone()) Value(d2);
3012
3013	AllocateSSAIndex(phi);
3014
3015	phi->mark_alive();
3016	phi->SetInputAt(0, v1);
3017	phi->SetInputAt(1, v2);
3018	d1->AddInputUse(value: v1);
3019	d2->AddInputUse(value: v2);
3020	join->InsertPhi(phi);
3021
3022	return phi;
3023	}
3024
3025	void FlowGraph::InsertMoveArguments() {
3026	intptr_t max_argument_slot_count = 0;
3027	for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
3028	block_it.Advance()) {
3029	thread()->CheckForSafepoint();
3030	for (ForwardInstructionIterator instr_it(block_it.Current());
3031	!instr_it.Done(); instr_it.Advance()) {
3032	Instruction* instruction = instr_it.Current();
3033	const intptr_t arg_count = instruction->ArgumentCount();
3034	if (arg_count == 0) {
3035	continue;
3036	}
3037	MoveArgumentsArray* arguments =
3038	new (Z) MoveArgumentsArray(zone(), arg_count);
3039	arguments->EnsureLength(new_length: arg_count, default_value: nullptr);
3040
3041	intptr_t sp_relative_index = 0;
3042	for (intptr_t i = arg_count - 1; i >= 0; --i) {
3043	Value* arg = instruction->ArgumentValueAt(index: i);
3044	const auto rep = instruction->RequiredInputRepresentation(idx: i);
3045	(*arguments)[i] = new (Z)
3046	MoveArgumentInstr(arg->CopyWithType(Z), rep, sp_relative_index);
3047
3048	static_assert(compiler::target::kIntSpillFactor ==
3049	compiler::target::kDoubleSpillFactor,
3050	"double and int are expected to be of the same size");
3051	RELEASE_ASSERT(rep == kTagged || rep == kUnboxedDouble ||
3052	rep == kUnboxedInt64);
3053	sp_relative_index +=
3054	(rep == kTagged) ? 1 : compiler::target::kIntSpillFactor;
3055	}
3056	max_argument_slot_count =
3057	Utils::Maximum(x: max_argument_slot_count, y: sp_relative_index);
3058
3059	for (auto move_arg : *arguments) {
3060	// Insert all MoveArgument instructions immediately before call.
3061	// MoveArgumentInstr::EmitNativeCode may generate more efficient
3062	// code for subsequent MoveArgument instructions (ARM, ARM64).
3063	InsertBefore(next: instruction, instr: move_arg, /*env=*/nullptr, use_kind: kEffect);
3064	}
3065	instruction->ReplaceInputsWithMoveArguments(move_arguments: arguments);
3066	if (instruction->env() != nullptr) {
3067	instruction->RepairArgumentUsesInEnvironment();
3068	}
3069	}
3070	}
3071	set_max_argument_slot_count(max_argument_slot_count);
3072	}
3073
3074	void FlowGraph::Print(const char* phase) {
3075	FlowGraphPrinter::PrintGraph(phase, flow_graph: this);
3076	}
3077
3078	class SSACompactor : public ValueObject {
3079	public:
3080	SSACompactor(intptr_t num_blocks,
3081	intptr_t num_ssa_vars,
3082	ZoneGrowableArray<Definition*>* detached_defs)
3083	: block_num_(num_blocks),
3084	ssa_num_(num_ssa_vars),
3085	detached_defs_(detached_defs) {
3086	block_num_.EnsureLength(num_blocks, -1);
3087	ssa_num_.EnsureLength(num_ssa_vars, -1);
3088	}
3089
3090	void RenumberGraph(FlowGraph* graph) {
3091	for (auto block : graph->reverse_postorder()) {
3092	block_num_[block->block_id()] = 1;
3093	CollectDetachedMaterializations(block->env());
3094
3095	if (auto* block_with_idefs = block->AsBlockEntryWithInitialDefs()) {
3096	for (Definition* def : *block_with_idefs->initial_definitions()) {
3097	RenumberDefinition(def);
3098	CollectDetachedMaterializations(def->env());
3099	}
3100	}
3101	if (auto* join = block->AsJoinEntry()) {
3102	for (PhiIterator it(join); !it.Done(); it.Advance()) {
3103	RenumberDefinition(it.Current());
3104	}
3105	}
3106	for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
3107	Instruction* instr = it.Current();
3108	if (Definition* def = instr->AsDefinition()) {
3109	RenumberDefinition(def);
3110	}
3111	CollectDetachedMaterializations(instr->env());
3112	}
3113	}
3114	for (auto* def : (*detached_defs_)) {
3115	RenumberDefinition(def);
3116	}
3117	graph->set_current_ssa_temp_index(current_ssa_index_);
3118
3119	// Preserve order between block ids to as predecessors are sorted
3120	// by block ids.
3121	intptr_t current_block_index = 0;
3122	for (intptr_t i = 0, n = block_num_.length(); i < n; ++i) {
3123	if (block_num_[i] >= 0) {
3124	block_num_[i] = current_block_index++;
3125	}
3126	}
3127	for (auto block : graph->reverse_postorder()) {
3128	block->set_block_id(block_num_[block->block_id()]);
3129	}
3130	graph->set_max_block_id(current_block_index - 1);
3131	}
3132
3133	private:
3134	void RenumberDefinition(Definition* def) {
3135	if (def->HasSSATemp()) {
3136	const intptr_t old_index = def->ssa_temp_index();
3137	intptr_t new_index = ssa_num_[old_index];
3138	if (new_index < 0) {
3139	ssa_num_[old_index] = new_index = current_ssa_index_++;
3140	}
3141	def->set_ssa_temp_index(new_index);
3142	}
3143	}
3144
3145	bool IsDetachedDefinition(Definition* def) {
3146	return def->IsMaterializeObject() && (def->next() == nullptr);
3147	}
3148
3149	void AddDetachedDefinition(Definition* def) {
3150	for (intptr_t i = 0, n = detached_defs_->length(); i < n; ++i) {
3151	if ((*detached_defs_)[i] == def) {
3152	return;
3153	}
3154	}
3155	detached_defs_->Add(value: def);
3156	// Follow inputs as detached definitions can reference other
3157	// detached definitions.
3158	for (intptr_t i = 0, n = def->InputCount(); i < n; ++i) {
3159	Definition* input = def->InputAt(i)->definition();
3160	if (IsDetachedDefinition(def: input)) {
3161	AddDetachedDefinition(def: input);
3162	}
3163	}
3164	ASSERT(def->env() == nullptr);
3165	}
3166
3167	void CollectDetachedMaterializations(Environment* env) {
3168	if (env == nullptr) {
3169	return;
3170	}
3171	for (Environment::DeepIterator it(env); !it.Done(); it.Advance()) {
3172	Definition* def = it.CurrentValue()->definition();
3173	if (IsDetachedDefinition(def)) {
3174	AddDetachedDefinition(def);
3175	}
3176	}
3177	}
3178
3179	GrowableArray<intptr_t> block_num_;
3180	GrowableArray<intptr_t> ssa_num_;
3181	intptr_t current_ssa_index_ = 0;
3182	ZoneGrowableArray<Definition*>* detached_defs_;
3183	};
3184
3185	void FlowGraph::CompactSSA(ZoneGrowableArray<Definition*>* detached_defs) {
3186	if (detached_defs == nullptr) {
3187	detached_defs = new (Z) ZoneGrowableArray<Definition*>(Z, 0);
3188	}
3189	SSACompactor compactor(max_block_id() + 1, current_ssa_temp_index(),
3190	detached_defs);
3191	compactor.RenumberGraph(graph: this);
3192	}
3193
3194	} // namespace dart
3195