1// Copyright (c) 2016, 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_REDUNDANCY_ELIMINATION_H_
6#define RUNTIME_VM_COMPILER_BACKEND_REDUNDANCY_ELIMINATION_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/compiler/backend/flow_graph.h"
13#include "vm/compiler/backend/il.h"
14
15namespace dart {
16
17class CSEInstructionMap;
18
19class AllocationSinking : public ZoneAllocated {
20 public:
21 explicit AllocationSinking(FlowGraph* flow_graph)
22 : flow_graph_(flow_graph), candidates_(5), materializations_(5) {}
23
24 const GrowableArray<Definition*>& candidates() const { return candidates_; }
25
26 // Find the materialization inserted for the given allocation
27 // at the given exit.
28 MaterializeObjectInstr* MaterializationFor(Definition* alloc,
29 Instruction* exit);
30
31 void Optimize();
32
33 void DetachMaterializations();
34
35 private:
36 // Helper class to collect deoptimization exits that might need to
37 // rematerialize an object: that is either instructions that reference
38 // this object explicitly in their deoptimization environment or
39 // reference some other allocation sinking candidate that points to
40 // this object.
41 class ExitsCollector : public ValueObject {
42 public:
43 ExitsCollector() : exits_(10), worklist_(3) {}
44
45 const GrowableArray<Instruction*>& exits() const { return exits_; }
46
47 void CollectTransitively(Definition* alloc);
48
49 private:
50 // Collect immediate uses of this object in the environments.
51 // If this object is stored into other allocation sinking candidates
52 // put them onto worklist so that CollectTransitively will process them.
53 void Collect(Definition* alloc);
54
55 GrowableArray<Instruction*> exits_;
56 GrowableArray<Definition*> worklist_;
57 };
58
59 void CollectCandidates();
60
61 void NormalizeMaterializations();
62
63 void RemoveUnusedMaterializations();
64
65 void DiscoverFailedCandidates();
66
67 void InsertMaterializations(Definition* alloc);
68
69 void CreateMaterializationAt(Instruction* exit,
70 Definition* alloc,
71 const ZoneGrowableArray<const Slot*>& fields);
72
73 void EliminateAllocation(Definition* alloc);
74
75 Isolate* isolate() const { return flow_graph_->isolate(); }
76 Zone* zone() const { return flow_graph_->zone(); }
77
78 FlowGraph* flow_graph_;
79
80 GrowableArray<Definition*> candidates_;
81 GrowableArray<MaterializeObjectInstr*> materializations_;
82
83 ExitsCollector exits_collector_;
84};
85
86// A simple common subexpression elimination based
87// on the dominator tree.
88class DominatorBasedCSE : public AllStatic {
89 public:
90 // Return true, if the optimization changed the flow graph.
91 // False, if nothing changed.
92 static bool Optimize(FlowGraph* graph);
93
94 private:
95 static bool OptimizeRecursive(FlowGraph* graph,
96 BlockEntryInstr* entry,
97 CSEInstructionMap* map);
98};
99
100class DeadStoreElimination : public AllStatic {
101 public:
102 static void Optimize(FlowGraph* graph);
103};
104
105class DeadCodeElimination : public AllStatic {
106 public:
107 // Discover phis that have no real (non-phi) uses and don't escape into
108 // deoptimization environments and eliminate them.
109 static void EliminateDeadPhis(FlowGraph* graph);
110
111 // Remove phis that are not marked alive from the graph.
112 static void RemoveDeadAndRedundantPhisFromTheGraph(FlowGraph* graph);
113
114 // Remove instructions which do not have any effect.
115 static void EliminateDeadCode(FlowGraph* graph);
116};
117
118// Optimize spill stores inside try-blocks by identifying values that always
119// contain a single known constant at catch block entry.
120// If is_aot is passed then this optimization can assume that no deoptimization
121// can occur and environments assigned to instructions are only used to
122// compute try/catch sync moves.
123void OptimizeCatchEntryStates(FlowGraph* flow_graph, bool is_aot);
124
125// Loop invariant code motion.
126class LICM : public ValueObject {
127 public:
128 explicit LICM(FlowGraph* flow_graph);
129
130 void Optimize();
131
132 void OptimisticallySpecializeSmiPhis();
133
134 private:
135 FlowGraph* flow_graph() const { return flow_graph_; }
136
137 void Hoist(ForwardInstructionIterator* it,
138 BlockEntryInstr* pre_header,
139 Instruction* current);
140
141 void TrySpecializeSmiPhi(PhiInstr* phi,
142 BlockEntryInstr* header,
143 BlockEntryInstr* pre_header);
144
145 FlowGraph* const flow_graph_;
146};
147
148// Move allocations down to their first use. Improves write barrier elimination.
149class DelayAllocations : public AllStatic {
150 public:
151 static void Optimize(FlowGraph* graph);
152
153 private:
154 static Instruction* DominantUse(Definition* def);
155 static bool IsOneTimeUse(Instruction* use, Definition* def);
156};
157
158class CheckStackOverflowElimination : public AllStatic {
159 public:
160 // For leaf functions with only a single [StackOverflowInstr] we remove it.
161 static void EliminateStackOverflow(FlowGraph* graph);
162};
163
164} // namespace dart
165
166#endif // RUNTIME_VM_COMPILER_BACKEND_REDUNDANCY_ELIMINATION_H_
167