1// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_COMPILER_BACKEND_FLOW_GRAPH_H_
6#define RUNTIME_VM_COMPILER_BACKEND_FLOW_GRAPH_H_
7
8#if defined(DART_PRECOMPILED_RUNTIME)
9#error "AOT runtime should not use compiler sources (including header files)"
10#endif // defined(DART_PRECOMPILED_RUNTIME)
11
12#include "vm/bit_vector.h"
13#include "vm/compiler/backend/il.h"
14#include "vm/growable_array.h"
15#include "vm/hash_map.h"
16#include "vm/parser.h"
17#include "vm/thread.h"
18
19namespace dart {
20
21class LoopHierarchy;
22class VariableLivenessAnalysis;
23
24namespace compiler {
25class GraphIntrinsifier;
26}
27
28class BlockIterator : public ValueObject {
29 public:
30 explicit BlockIterator(const GrowableArray<BlockEntryInstr*>& block_order)
31 : block_order_(block_order), current_(0) {}
32
33 BlockIterator(const BlockIterator& other)
34 : ValueObject(),
35 block_order_(other.block_order_),
36 current_(other.current_) {}
37
38 void Advance() {
39 ASSERT(!Done());
40 current_++;
41 }
42
43 bool Done() const { return current_ >= block_order_.length(); }
44
45 BlockEntryInstr* Current() const { return block_order_[current_]; }
46
47 private:
48 const GrowableArray<BlockEntryInstr*>& block_order_;
49 intptr_t current_;
50};
51
52struct ConstantAndRepresentation {
53 const Object& constant;
54 Representation representation;
55};
56
57struct ConstantPoolTrait {
58 typedef ConstantInstr* Value;
59 typedef ConstantAndRepresentation Key;
60 typedef ConstantInstr* Pair;
61
62 static Key KeyOf(Pair kv) {
63 return ConstantAndRepresentation{.constant: kv->value(), .representation: kv->representation()};
64 }
65
66 static Value ValueOf(Pair kv) { return kv; }
67
68 static inline uword Hash(Key key) {
69 if (key.constant.IsSmi()) {
70 return Smi::Cast(obj: key.constant).Value();
71 }
72 if (key.constant.IsDouble()) {
73 return static_cast<intptr_t>(bit_cast<int32_t, float>(
74 source: static_cast<float>(Double::Cast(obj: key.constant).value())));
75 }
76 if (key.constant.IsMint()) {
77 return static_cast<intptr_t>(Mint::Cast(obj: key.constant).value());
78 }
79 if (key.constant.IsString()) {
80 return String::Cast(obj: key.constant).Hash();
81 }
82 return key.constant.GetClassId();
83 }
84
85 static inline bool IsKeyEqual(Pair kv, Key key) {
86 return (kv->value().ptr() == key.constant.ptr()) &&
87 (kv->representation() == key.representation);
88 }
89};
90
91struct PrologueInfo {
92 // The first blockid used for prologue building. This information can be used
93 // by the inliner for budget calculations: The prologue code falls away when
94 // inlining, so we should not include it in the budget.
95 intptr_t min_block_id;
96
97 // The last blockid used for prologue building. This information can be used
98 // by the inliner for budget calculations: The prologue code falls away when
99 // inlining, so we should not include it in the budget.
100 intptr_t max_block_id;
101
102 PrologueInfo(intptr_t min, intptr_t max)
103 : min_block_id(min), max_block_id(max) {}
104
105 bool Contains(intptr_t block_id) const {
106 return min_block_id <= block_id && block_id <= max_block_id;
107 }
108};
109
110// Class to encapsulate the construction and manipulation of the flow graph.
111class FlowGraph : public ZoneAllocated {
112 public:
113 FlowGraph(const ParsedFunction& parsed_function,
114 GraphEntryInstr* graph_entry,
115 intptr_t max_block_id,
116 PrologueInfo prologue_info);
117
118 // Function properties.
119 const ParsedFunction& parsed_function() const { return parsed_function_; }
120 const Function& function() const { return parsed_function_.function(); }
121
122 void Print(const char* phase = "unknown");
123
124 // The number of directly accessable parameters (above the frame pointer).
125 // All other parameters can only be indirectly loaded via metadata found in
126 // the arguments descriptor.
127 intptr_t num_direct_parameters() const { return num_direct_parameters_; }
128
129 // The number of words on the stack used by the direct parameters.
130 intptr_t direct_parameters_size() const { return direct_parameters_size_; }
131
132 // The number of variables (or boxes) which code can load from / store to.
133 // The SSA renaming will insert phi's for them (and only them - i.e. there
134 // will be no phi insertion for [LocalVariable]s pointing to the expression
135 // stack!).
136 intptr_t variable_count() const {
137 return num_direct_parameters_ + parsed_function_.num_stack_locals();
138 }
139
140 // The number of variables during OSR, which may include stack slots
141 // that pass in initial contents for the expression stack.
142 intptr_t osr_variable_count() const {
143 ASSERT(IsCompiledForOsr());
144 return variable_count() + graph_entry()->osr_entry()->stack_depth();
145 }
146
147 // This function returns the offset (in words) of the [index]th
148 // parameter, relative to the first parameter.
149 // If [last_slot] is true it gives the offset of the last slot of that
150 // location, otherwise it returns the first one.
151 static intptr_t ParameterOffsetAt(const Function& function,
152 intptr_t index,
153 bool last_slot = true);
154
155 static Representation ParameterRepresentationAt(const Function& function,
156 intptr_t index);
157
158 static Representation ReturnRepresentationOf(const Function& function);
159
160 // The number of variables (or boxes) inside the functions frame - meaning
161 // below the frame pointer. This does not include the expression stack.
162 intptr_t num_stack_locals() const {
163 return parsed_function_.num_stack_locals();
164 }
165
166 bool IsIrregexpFunction() const { return function().IsIrregexpFunction(); }
167
168 LocalVariable* SuspendStateVar() const {
169 return parsed_function().suspend_state_var();
170 }
171
172 intptr_t SuspendStateEnvIndex() const { return EnvIndex(variable: SuspendStateVar()); }
173
174 LocalVariable* CurrentContextVar() const {
175 return parsed_function().current_context_var();
176 }
177
178 intptr_t CurrentContextEnvIndex() const {
179 return EnvIndex(variable: parsed_function().current_context_var());
180 }
181
182 intptr_t RawTypeArgumentEnvIndex() const {
183 return EnvIndex(variable: parsed_function().RawTypeArgumentsVariable());
184 }
185
186 intptr_t ArgumentDescriptorEnvIndex() const {
187 return EnvIndex(variable: parsed_function().arg_desc_var());
188 }
189
190 intptr_t EnvIndex(const LocalVariable* variable) const {
191 ASSERT(!variable->is_captured());
192 return num_direct_parameters_ - variable->index().value();
193 }
194
195 // Context and :suspend_state variables are never pruned and
196 // artificially kept alive.
197 bool IsImmortalVariable(intptr_t env_index) const {
198 return (env_index == CurrentContextEnvIndex()) ||
199 (SuspendStateVar() != nullptr &&
200 env_index == SuspendStateEnvIndex());
201 }
202
203 // Flow graph orders.
204 const GrowableArray<BlockEntryInstr*>& preorder() const { return preorder_; }
205 const GrowableArray<BlockEntryInstr*>& postorder() const {
206 return postorder_;
207 }
208 const GrowableArray<BlockEntryInstr*>& reverse_postorder() const {
209 return reverse_postorder_;
210 }
211 const GrowableArray<BlockEntryInstr*>& optimized_block_order() const {
212 return optimized_block_order_;
213 }
214 static bool ShouldReorderBlocks(const Function& function, bool is_optimized);
215 GrowableArray<BlockEntryInstr*>* CodegenBlockOrder(bool is_optimized);
216
217 // Iterators.
218 BlockIterator reverse_postorder_iterator() const {
219 return BlockIterator(reverse_postorder());
220 }
221 BlockIterator postorder_iterator() const {
222 return BlockIterator(postorder());
223 }
224
225 void EnsureSSATempIndex(Definition* defn, Definition* replacement);
226
227 void ReplaceCurrentInstruction(ForwardInstructionIterator* iterator,
228 Instruction* current,
229 Instruction* replacement);
230
231 Instruction* CreateCheckClass(Definition* to_check,
232 const Cids& cids,
233 intptr_t deopt_id,
234 const InstructionSource& source);
235
236 Definition* CreateCheckBound(Definition* length,
237 Definition* index,
238 intptr_t deopt_id);
239
240 void AddExactnessGuard(InstanceCallInstr* call, intptr_t receiver_cid);
241
242 intptr_t current_ssa_temp_index() const { return current_ssa_temp_index_; }
243 void set_current_ssa_temp_index(intptr_t index) {
244 current_ssa_temp_index_ = index;
245 }
246
247 intptr_t max_vreg() const {
248 return current_ssa_temp_index() * kMaxLocationCount;
249 }
250
251 enum class ToCheck { kNoCheck, kCheckNull, kCheckCid };
252
253 // Uses CHA to determine if the called method can be overridden.
254 // Return value indicates that the call needs no check at all,
255 // just a null check, or a full class check.
256 ToCheck CheckForInstanceCall(InstanceCallInstr* call,
257 UntaggedFunction::Kind kind) const;
258
259 Thread* thread() const { return thread_; }
260 Zone* zone() const { return thread()->zone(); }
261 IsolateGroup* isolate_group() const { return thread()->isolate_group(); }
262
263 intptr_t max_block_id() const { return max_block_id_; }
264 void set_max_block_id(intptr_t id) { max_block_id_ = id; }
265 intptr_t allocate_block_id() { return ++max_block_id_; }
266
267 GraphEntryInstr* graph_entry() const { return graph_entry_; }
268
269 ConstantInstr* constant_null() const { return constant_null_; }
270
271 ConstantInstr* constant_dead() const { return constant_dead_; }
272
273 void AllocateSSAIndex(Definition* def) {
274 def->set_ssa_temp_index(current_ssa_temp_index_);
275 current_ssa_temp_index_++;
276 }
277
278 intptr_t InstructionCount() const;
279
280 // Returns the definition for the object from the constant pool if
281 // one exists, otherwise returns nullptr.
282 ConstantInstr* GetExistingConstant(
283 const Object& object,
284 Representation representation = kTagged) const;
285
286 // Always returns a definition for the object from the constant pool,
287 // allocating one if it doesn't already exist.
288 ConstantInstr* GetConstant(const Object& object,
289 Representation representation = kTagged);
290
291 void AddToGraphInitialDefinitions(Definition* defn);
292 void AddToInitialDefinitions(BlockEntryWithInitialDefs* entry,
293 Definition* defn);
294
295 // Tries to create a constant definition with the given value which can be
296 // used to replace the given operation. Ensures that the representation of
297 // the replacement matches the representation of the original definition.
298 // If the given value can't be represented using matching representation
299 // then returns op itself.
300 Definition* TryCreateConstantReplacementFor(Definition* op,
301 const Object& value);
302
303 // Returns true if the given constant value can be represented in the given
304 // representation.
305 static bool IsConstantRepresentable(const Object& value,
306 Representation target_rep,
307 bool tagged_value_must_be_smi);
308
309 enum UseKind { kEffect, kValue };
310
311 void InsertBefore(Instruction* next,
312 Instruction* instr,
313 Environment* env,
314 UseKind use_kind) {
315 InsertAfter(prev: next->previous(), instr, env, use_kind);
316 }
317 void InsertSpeculativeBefore(Instruction* next,
318 Instruction* instr,
319 Environment* env,
320 UseKind use_kind) {
321 InsertSpeculativeAfter(prev: next->previous(), instr, env, use_kind);
322 }
323 void InsertAfter(Instruction* prev,
324 Instruction* instr,
325 Environment* env,
326 UseKind use_kind);
327
328 // Inserts a speculative [instr] after existing [prev] instruction.
329 //
330 // If the inserted [instr] deopts eagerly or lazily we will always continue in
331 // unoptimized code at before-call using the given [env].
332 //
333 // This is mainly used during inlining / call specializing when replacing
334 // calls with N specialized instructions where the inserted [1..N[
335 // instructions cannot continue in unoptimized code after-call since they
336 // would miss instructions following the one that lazy-deopted.
337 //
338 // For example specializing an instance call to an implicit field setter
339 //
340 // InstanceCall:<id>(v0, set:<name>, args = [v1])
341 //
342 // to
343 //
344 // v2 <- AssertAssignable:<id>(v1, ...)
345 // StoreField(v0, v2)
346 //
347 // If the [AssertAssignable] causes a lazy-deopt on return, we'll have to
348 // *re-try* the implicit setter call in unoptimized mode, i.e. lazy deopt to
349 // before-call (otherwise - if we continued after-call - the
350 // StoreField would not be performed).
351 void InsertSpeculativeAfter(Instruction* prev,
352 Instruction* instr,
353 Environment* env,
354 UseKind use_kind);
355 Instruction* AppendTo(Instruction* prev,
356 Instruction* instr,
357 Environment* env,
358 UseKind use_kind);
359 Instruction* AppendSpeculativeTo(Instruction* prev,
360 Instruction* instr,
361 Environment* env,
362 UseKind use_kind);
363
364 // Operations on the flow graph.
365 void ComputeSSA(ZoneGrowableArray<Definition*>* inlining_parameters);
366
367 // Verification method for debugging.
368 bool VerifyRedefinitions();
369
370 void DiscoverBlocks();
371
372 void MergeBlocks();
373
374 // Insert a redefinition of an original definition after prev and rename all
375 // dominated uses of the original. If an equivalent redefinition is already
376 // present, nothing is inserted.
377 // Returns the redefinition, if a redefinition was inserted, nullptr
378 // otherwise.
379 RedefinitionInstr* EnsureRedefinition(Instruction* prev,
380 Definition* original,
381 CompileType compile_type);
382
383 // Remove the redefinition instructions inserted to inhibit code motion.
384 void RemoveRedefinitions(bool keep_checks = false);
385
386 // Insert MoveArgument instructions and remove explicit def-use
387 // relations between calls and their arguments.
388 //
389 // Compute the maximum number of arguments.
390 void InsertMoveArguments();
391
392 // Copy deoptimization target from one instruction to another if we still
393 // have to keep deoptimization environment at gotos for LICM purposes.
394 void CopyDeoptTarget(Instruction* to, Instruction* from) {
395 if (is_licm_allowed()) {
396 to->InheritDeoptTarget(zone: zone(), other: from);
397 }
398 }
399
400 // Returns true if every Goto in the graph is expected to have a
401 // deoptimization environment and can be used as deoptimization target
402 // for hoisted instructions.
403 bool is_licm_allowed() const { return licm_allowed_; }
404
405 // Stop preserving environments on Goto instructions. LICM is not allowed
406 // after this point.
407 void disallow_licm() { licm_allowed_ = false; }
408
409 // Returns true if mismatch in input/output representations is allowed.
410 bool unmatched_representations_allowed() const {
411 return unmatched_representations_allowed_;
412 }
413
414 // After the last SelectRepresentations pass all further transformations
415 // should maintain matching input/output representations.
416 void disallow_unmatched_representations() {
417 unmatched_representations_allowed_ = false;
418 }
419
420 // Returns true if this flow graph was built for a huge method
421 // and certain optimizations should be disabled.
422 bool is_huge_method() const { return huge_method_; }
423 // Mark this flow graph as huge and disable certain optimizations.
424 void mark_huge_method() { huge_method_ = true; }
425
426 PrologueInfo prologue_info() const { return prologue_info_; }
427
428 // Computes the loop hierarchy of the flow graph on demand.
429 const LoopHierarchy& GetLoopHierarchy() {
430 if (loop_hierarchy_ == nullptr) {
431 loop_hierarchy_ = ComputeLoops();
432 }
433 return loop_hierarchy();
434 }
435
436 const LoopHierarchy& loop_hierarchy() const { return *loop_hierarchy_; }
437
438 // Resets the loop hierarchy of the flow graph. Use this to
439 // force a recomputation of loop detection by the next call
440 // to GetLoopHierarchy() (note that this does not immediately
441 // reset the loop_info fields of block entries, although
442 // these will be overwritten by that next call).
443 void ResetLoopHierarchy() {
444 loop_hierarchy_ = nullptr;
445 loop_invariant_loads_ = nullptr;
446 }
447
448 // Per loop header invariant loads sets. Each set contains load id for
449 // those loads that are not affected by anything in the loop and can be
450 // hoisted out. Sets are computed by LoadOptimizer.
451 ZoneGrowableArray<BitVector*>* loop_invariant_loads() const {
452 return loop_invariant_loads_;
453 }
454 void set_loop_invariant_loads(
455 ZoneGrowableArray<BitVector*>* loop_invariant_loads) {
456 loop_invariant_loads_ = loop_invariant_loads;
457 }
458
459 bool IsCompiledForOsr() const { return graph_entry()->IsCompiledForOsr(); }
460
461 BitVector* captured_parameters() const { return captured_parameters_; }
462
463 intptr_t inlining_id() const { return inlining_id_; }
464 void set_inlining_id(intptr_t value) { inlining_id_ = value; }
465
466 // Returns true if any instructions were canonicalized away.
467 bool Canonicalize();
468
469 // Attaches new ICData's to static/instance calls which don't already have
470 // them.
471 void PopulateWithICData(const Function& function);
472
473 void SelectRepresentations();
474
475 void WidenSmiToInt32();
476
477 // Remove environments from the instructions which do not deoptimize.
478 void EliminateEnvironments();
479
480 bool IsReceiver(Definition* def) const;
481
482 // Optimize (a << b) & c pattern: if c is a positive Smi or zero, then the
483 // shift can be a truncating Smi shift-left and result is always Smi.
484 // Merge instructions (only per basic-block).
485 void TryOptimizePatterns();
486
487 // Replaces uses that are dominated by dom of 'def' with 'other'.
488 // Note: uses that occur at instruction dom itself are not dominated by it.
489 static void RenameDominatedUses(Definition* def,
490 Instruction* dom,
491 Definition* other);
492
493 // Renames uses of redefined values to make sure that uses of redefined
494 // values that are dominated by a redefinition are renamed.
495 void RenameUsesDominatedByRedefinitions();
496
497 bool should_print() const { return should_print_; }
498 const uint8_t* compiler_pass_filters() const {
499 return compiler_pass_filters_;
500 }
501
502 //
503 // High-level utilities.
504 //
505
506 // Logical-AND (for use in short-circuit diamond).
507 struct LogicalAnd {
508 LogicalAnd(ComparisonInstr* x, ComparisonInstr* y) : oper1(x), oper2(y) {}
509 ComparisonInstr* oper1;
510 ComparisonInstr* oper2;
511 };
512
513 // Constructs a diamond control flow at the instruction, inheriting
514 // properties from inherit and using the given compare. Returns the
515 // join (and true/false blocks in out parameters). Updates dominance
516 // relation, but not the succ/pred ordering on block.
517 JoinEntryInstr* NewDiamond(Instruction* instruction,
518 Instruction* inherit,
519 ComparisonInstr* compare,
520 TargetEntryInstr** block_true,
521 TargetEntryInstr** block_false);
522
523 // As above, but with a short-circuit on two comparisons.
524 JoinEntryInstr* NewDiamond(Instruction* instruction,
525 Instruction* inherit,
526 const LogicalAnd& condition,
527 TargetEntryInstr** block_true,
528 TargetEntryInstr** block_false);
529
530 // Adds a 2-way phi.
531 PhiInstr* AddPhi(JoinEntryInstr* join, Definition* d1, Definition* d2);
532
533 // SSA transformation methods and fields.
534 void ComputeDominators(GrowableArray<BitVector*>* dominance_frontier);
535
536 void CreateCommonConstants();
537
538 const Array& coverage_array() const { return *coverage_array_; }
539 void set_coverage_array(const Array& array) { coverage_array_ = &array; }
540
541 // Renumbers SSA values and basic blocks to make numbering dense.
542 // Preserves order among block ids.
543 //
544 // Also collects definitions which are detached from the flow graph
545 // but still referenced (currently only MaterializeObject instructions
546 // can be detached).
547 void CompactSSA(ZoneGrowableArray<Definition*>* detached_defs = nullptr);
548
549 // Maximum number of word-sized slots needed for outgoing arguments.
550 intptr_t max_argument_slot_count() const {
551 RELEASE_ASSERT(max_argument_slot_count_ >= 0);
552 return max_argument_slot_count_;
553 }
554 void set_max_argument_slot_count(intptr_t count) {
555 RELEASE_ASSERT(max_argument_slot_count_ == -1);
556 max_argument_slot_count_ = count;
557 }
558
559 private:
560 friend class FlowGraphCompiler; // TODO(ajcbik): restructure
561 friend class FlowGraphChecker;
562 friend class IfConverter;
563 friend class BranchSimplifier;
564 friend class ConstantPropagator;
565 friend class DeadCodeElimination;
566 friend class compiler::GraphIntrinsifier;
567
568 void CompressPath(intptr_t start_index,
569 intptr_t current_index,
570 GrowableArray<intptr_t>* parent,
571 GrowableArray<intptr_t>* label);
572
573 void AddSyntheticPhis(BlockEntryInstr* block);
574
575 void Rename(GrowableArray<PhiInstr*>* live_phis,
576 VariableLivenessAnalysis* variable_liveness,
577 ZoneGrowableArray<Definition*>* inlining_parameters);
578 void RenameRecursive(BlockEntryInstr* block_entry,
579 GrowableArray<Definition*>* env,
580 GrowableArray<PhiInstr*>* live_phis,
581 VariableLivenessAnalysis* variable_liveness,
582 ZoneGrowableArray<Definition*>* inlining_parameters);
583#if defined(DEBUG)
584 // Validates no phis are missing on join entry instructions.
585 void ValidatePhis();
586#endif // defined(DEBUG)
587
588 void PopulateEnvironmentFromFunctionEntry(
589 FunctionEntryInstr* function_entry,
590 GrowableArray<Definition*>* env,
591 GrowableArray<PhiInstr*>* live_phis,
592 VariableLivenessAnalysis* variable_liveness,
593 ZoneGrowableArray<Definition*>* inlining_parameters);
594
595 void PopulateEnvironmentFromOsrEntry(OsrEntryInstr* osr_entry,
596 GrowableArray<Definition*>* env);
597
598 void PopulateEnvironmentFromCatchEntry(CatchBlockEntryInstr* catch_entry,
599 GrowableArray<Definition*>* env);
600
601 void AttachEnvironment(Instruction* instr, GrowableArray<Definition*>* env);
602
603 void InsertPhis(const GrowableArray<BlockEntryInstr*>& preorder,
604 const GrowableArray<BitVector*>& assigned_vars,
605 const GrowableArray<BitVector*>& dom_frontier,
606 GrowableArray<PhiInstr*>* live_phis);
607
608 void RemoveDeadPhis(GrowableArray<PhiInstr*>* live_phis);
609
610 void ReplacePredecessor(BlockEntryInstr* old_block,
611 BlockEntryInstr* new_block);
612
613 // Finds the blocks in the natural loop for the back edge m->n. The
614 // algorithm is described in "Advanced Compiler Design & Implementation"
615 // (Muchnick) p192. Returns a BitVector indexed by block pre-order
616 // number where each bit indicates membership in the loop.
617 BitVector* FindLoopBlocks(BlockEntryInstr* m, BlockEntryInstr* n) const;
618
619 // Finds the natural loops in the flow graph and attaches the loop
620 // information to each entry block. Returns the loop hierarchy.
621 LoopHierarchy* ComputeLoops() const;
622
623 void InsertConversionsFor(Definition* def);
624 void ConvertUse(Value* use, Representation from);
625 void InsertConversion(Representation from,
626 Representation to,
627 Value* use,
628 bool is_environment_use);
629
630 // Insert allocation of a record instance for [def]
631 // which returns an unboxed record.
632 void InsertRecordBoxing(Definition* def);
633
634 void ComputeIsReceiver(PhiInstr* phi) const;
635 void ComputeIsReceiverRecursive(PhiInstr* phi,
636 GrowableArray<PhiInstr*>* unmark) const;
637
638 void OptimizeLeftShiftBitAndSmiOp(
639 ForwardInstructionIterator* current_iterator,
640 Definition* bit_and_instr,
641 Definition* left_instr,
642 Definition* right_instr);
643
644 void TryMergeTruncDivMod(GrowableArray<BinarySmiOpInstr*>* merge_candidates);
645
646 void AppendExtractNthOutputForMerged(Definition* instr,
647 intptr_t ix,
648 Representation rep,
649 intptr_t cid);
650
651 Thread* thread_;
652
653 // DiscoverBlocks computes parent_ and assigned_vars_ which are then used
654 // if/when computing SSA.
655 GrowableArray<intptr_t> parent_;
656
657 intptr_t current_ssa_temp_index_;
658 intptr_t max_block_id_;
659
660 // Flow graph fields.
661 const ParsedFunction& parsed_function_;
662 intptr_t num_direct_parameters_;
663 intptr_t direct_parameters_size_;
664 GraphEntryInstr* graph_entry_;
665 GrowableArray<BlockEntryInstr*> preorder_;
666 GrowableArray<BlockEntryInstr*> postorder_;
667 GrowableArray<BlockEntryInstr*> reverse_postorder_;
668 GrowableArray<BlockEntryInstr*> optimized_block_order_;
669 ConstantInstr* constant_null_;
670 ConstantInstr* constant_dead_;
671
672 bool licm_allowed_;
673 bool unmatched_representations_allowed_ = true;
674 bool huge_method_ = false;
675
676 const PrologueInfo prologue_info_;
677
678 // Loop related fields.
679 LoopHierarchy* loop_hierarchy_;
680 ZoneGrowableArray<BitVector*>* loop_invariant_loads_;
681
682 DirectChainedHashMap<ConstantPoolTrait> constant_instr_pool_;
683 BitVector* captured_parameters_;
684
685 intptr_t inlining_id_;
686 bool should_print_;
687 uint8_t* compiler_pass_filters_ = nullptr;
688
689 intptr_t max_argument_slot_count_ = -1;
690
691 const Array* coverage_array_ = &Array::empty_array();
692};
693
694class LivenessAnalysis : public ValueObject {
695 public:
696 LivenessAnalysis(intptr_t variable_count,
697 const GrowableArray<BlockEntryInstr*>& postorder);
698
699 void Analyze();
700
701 virtual ~LivenessAnalysis() {}
702
703 BitVector* GetLiveInSetAt(intptr_t postorder_number) const {
704 return live_in_[postorder_number];
705 }
706
707 BitVector* GetLiveOutSetAt(intptr_t postorder_number) const {
708 return live_out_[postorder_number];
709 }
710
711 BitVector* GetLiveInSet(BlockEntryInstr* block) const {
712 return GetLiveInSetAt(postorder_number: block->postorder_number());
713 }
714
715 BitVector* GetKillSet(BlockEntryInstr* block) const {
716 return kill_[block->postorder_number()];
717 }
718
719 BitVector* GetLiveOutSet(BlockEntryInstr* block) const {
720 return GetLiveOutSetAt(postorder_number: block->postorder_number());
721 }
722
723 // Print results of liveness analysis.
724 void Dump();
725
726 protected:
727 // Compute initial values for live-out, kill and live-in sets.
728 virtual void ComputeInitialSets() = 0;
729
730 // Update live-out set for the given block: live-out should contain
731 // all values that are live-in for block's successors.
732 // Returns true if live-out set was changed.
733 bool UpdateLiveOut(const BlockEntryInstr& instr);
734
735 // Update live-in set for the given block: live-in should contain
736 // all values that are live-out from the block and are not defined
737 // by this block.
738 // Returns true if live-in set was changed.
739 bool UpdateLiveIn(const BlockEntryInstr& instr);
740
741 // Perform fix-point iteration updating live-out and live-in sets
742 // for blocks until they stop changing.
743 void ComputeLiveInAndLiveOutSets();
744
745 Zone* zone() const { return zone_; }
746
747 Zone* zone_;
748
749 const intptr_t variable_count_;
750
751 const GrowableArray<BlockEntryInstr*>& postorder_;
752
753 // Live-out sets for each block. They contain indices of variables
754 // that are live out from this block. That is values that were (1) either
755 // defined in this block or live into it, and (2) that are used in some
756 // successor block.
757 GrowableArray<BitVector*> live_out_;
758
759 // Kill sets for each block. They contain indices of variables that
760 // are defined by this block.
761 GrowableArray<BitVector*> kill_;
762
763 // Live-in sets for each block. They contain indices of variables
764 // that are used by this block or its successors.
765 GrowableArray<BitVector*> live_in_;
766};
767
768class DefinitionWorklist : public ValueObject {
769 public:
770 DefinitionWorklist(FlowGraph* flow_graph, intptr_t initial_capacity)
771 : defs_(initial_capacity),
772 contains_vector_(new BitVector(flow_graph->zone(),
773 flow_graph->current_ssa_temp_index())) {}
774
775 void Add(Definition* defn) {
776 if (!Contains(defn)) {
777 defs_.Add(defn);
778 contains_vector_->Add(i: defn->ssa_temp_index());
779 }
780 }
781
782 bool Contains(Definition* defn) const {
783 return (defn->ssa_temp_index() >= 0) &&
784 contains_vector_->Contains(i: defn->ssa_temp_index());
785 }
786
787 bool IsEmpty() const { return defs_.is_empty(); }
788
789 Definition* RemoveLast() {
790 Definition* defn = defs_.RemoveLast();
791 contains_vector_->Remove(i: defn->ssa_temp_index());
792 return defn;
793 }
794
795 const GrowableArray<Definition*>& definitions() const { return defs_; }
796 BitVector* contains_vector() const { return contains_vector_; }
797
798 void Clear() {
799 defs_.TruncateTo(0);
800 contains_vector_->Clear();
801 }
802
803 private:
804 GrowableArray<Definition*> defs_;
805 BitVector* contains_vector_;
806};
807
808} // namespace dart
809
810#endif // RUNTIME_VM_COMPILER_BACKEND_FLOW_GRAPH_H_
811

source code of dart_sdk/runtime/vm/compiler/backend/flow_graph.h