1 // Copyright 2015 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "src/compiler/escape-analysis-reducer.h"
6 
7 #include "src/compiler/all-nodes.h"
8 #include "src/compiler/js-graph.h"
9 #include "src/counters.h"
10 
11 namespace v8 {
12 namespace internal {
13 namespace compiler {
14 
15 #ifdef DEBUG
16 #define TRACE(...)                                    \
17   do {                                                \
18     if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
19   } while (false)
20 #else
21 #define TRACE(...)
22 #endif  // DEBUG
23 
EscapeAnalysisReducer(Editor * editor,JSGraph * jsgraph,EscapeAnalysis * escape_analysis,Zone * zone)24 EscapeAnalysisReducer::EscapeAnalysisReducer(Editor* editor, JSGraph* jsgraph,
25                                              EscapeAnalysis* escape_analysis,
26                                              Zone* zone)
27     : AdvancedReducer(editor),
28       jsgraph_(jsgraph),
29       escape_analysis_(escape_analysis),
30       zone_(zone),
31       fully_reduced_(static_cast<int>(jsgraph->graph()->NodeCount() * 2), zone),
32       exists_virtual_allocate_(escape_analysis->ExistsVirtualAllocate()) {}
33 
Reduce(Node * node)34 Reduction EscapeAnalysisReducer::Reduce(Node* node) {
35   if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
36       fully_reduced_.Contains(node->id())) {
37     return NoChange();
38   }
39 
40   switch (node->opcode()) {
41     case IrOpcode::kLoadField:
42     case IrOpcode::kLoadElement:
43       return ReduceLoad(node);
44     case IrOpcode::kStoreField:
45     case IrOpcode::kStoreElement:
46       return ReduceStore(node);
47     case IrOpcode::kAllocate:
48       return ReduceAllocate(node);
49     case IrOpcode::kFinishRegion:
50       return ReduceFinishRegion(node);
51     case IrOpcode::kReferenceEqual:
52       return ReduceReferenceEqual(node);
53     case IrOpcode::kObjectIsSmi:
54       return ReduceObjectIsSmi(node);
55     // FrameStates and Value nodes are preprocessed here,
56     // and visited via ReduceFrameStateUses from their user nodes.
57     case IrOpcode::kFrameState:
58     case IrOpcode::kStateValues: {
59       if (node->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
60           fully_reduced_.Contains(node->id())) {
61         break;
62       }
63       bool depends_on_object_state = false;
64       for (int i = 0; i < node->InputCount(); i++) {
65         Node* input = node->InputAt(i);
66         switch (input->opcode()) {
67           case IrOpcode::kAllocate:
68           case IrOpcode::kFinishRegion:
69             depends_on_object_state =
70                 depends_on_object_state || escape_analysis()->IsVirtual(input);
71             break;
72           case IrOpcode::kFrameState:
73           case IrOpcode::kStateValues:
74             depends_on_object_state =
75                 depends_on_object_state ||
76                 input->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
77                 !fully_reduced_.Contains(input->id());
78             break;
79           default:
80             break;
81         }
82       }
83       if (!depends_on_object_state) {
84         fully_reduced_.Add(node->id());
85       }
86       return NoChange();
87     }
88     default:
89       // TODO(sigurds): Change this to GetFrameStateInputCount once
90       // it is working. For now we use EffectInputCount > 0 to determine
91       // whether a node might have a frame state input.
92       if (exists_virtual_allocate_ && node->op()->EffectInputCount() > 0) {
93         return ReduceFrameStateUses(node);
94       }
95       break;
96   }
97   return NoChange();
98 }
99 
100 namespace {
101 
MaybeGuard(JSGraph * jsgraph,Node * original,Node * replacement)102 Node* MaybeGuard(JSGraph* jsgraph, Node* original, Node* replacement) {
103   // We might need to guard the replacement if the type of the {replacement}
104   // node is not in a sub-type relation to the type of the the {original} node.
105   Type* const replacement_type = NodeProperties::GetType(replacement);
106   Type* const original_type = NodeProperties::GetType(original);
107   if (!replacement_type->Is(original_type)) {
108     Node* const control = NodeProperties::GetControlInput(original);
109     replacement = jsgraph->graph()->NewNode(
110         jsgraph->common()->TypeGuard(original_type), replacement, control);
111   }
112   return replacement;
113 }
114 
115 }  // namespace
116 
ReduceLoad(Node * node)117 Reduction EscapeAnalysisReducer::ReduceLoad(Node* node) {
118   DCHECK(node->opcode() == IrOpcode::kLoadField ||
119          node->opcode() == IrOpcode::kLoadElement);
120   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
121     fully_reduced_.Add(node->id());
122   }
123   if (escape_analysis()->IsVirtual(NodeProperties::GetValueInput(node, 0))) {
124     if (Node* rep = escape_analysis()->GetReplacement(node)) {
125       isolate()->counters()->turbo_escape_loads_replaced()->Increment();
126       TRACE("Replaced #%d (%s) with #%d (%s)\n", node->id(),
127             node->op()->mnemonic(), rep->id(), rep->op()->mnemonic());
128       rep = MaybeGuard(jsgraph(), node, rep);
129       ReplaceWithValue(node, rep);
130       return Replace(rep);
131     }
132   }
133   return NoChange();
134 }
135 
136 
ReduceStore(Node * node)137 Reduction EscapeAnalysisReducer::ReduceStore(Node* node) {
138   DCHECK(node->opcode() == IrOpcode::kStoreField ||
139          node->opcode() == IrOpcode::kStoreElement);
140   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
141     fully_reduced_.Add(node->id());
142   }
143   if (escape_analysis()->IsVirtual(NodeProperties::GetValueInput(node, 0))) {
144     TRACE("Removed #%d (%s) from effect chain\n", node->id(),
145           node->op()->mnemonic());
146     RelaxEffectsAndControls(node);
147     return Changed(node);
148   }
149   return NoChange();
150 }
151 
152 
ReduceAllocate(Node * node)153 Reduction EscapeAnalysisReducer::ReduceAllocate(Node* node) {
154   DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
155   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
156     fully_reduced_.Add(node->id());
157   }
158   if (escape_analysis()->IsVirtual(node)) {
159     RelaxEffectsAndControls(node);
160     isolate()->counters()->turbo_escape_allocs_replaced()->Increment();
161     TRACE("Removed allocate #%d from effect chain\n", node->id());
162     return Changed(node);
163   }
164   return NoChange();
165 }
166 
167 
ReduceFinishRegion(Node * node)168 Reduction EscapeAnalysisReducer::ReduceFinishRegion(Node* node) {
169   DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
170   Node* effect = NodeProperties::GetEffectInput(node, 0);
171   if (effect->opcode() == IrOpcode::kBeginRegion) {
172     // We only add it now to remove empty Begin/Finish region pairs
173     // in the process.
174     if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
175       fully_reduced_.Add(node->id());
176     }
177     RelaxEffectsAndControls(effect);
178     RelaxEffectsAndControls(node);
179 #ifdef DEBUG
180     if (FLAG_trace_turbo_escape) {
181       PrintF("Removed region #%d / #%d from effect chain,", effect->id(),
182              node->id());
183       PrintF(" %d user(s) of #%d remain(s):", node->UseCount(), node->id());
184       for (Edge edge : node->use_edges()) {
185         PrintF(" #%d", edge.from()->id());
186       }
187       PrintF("\n");
188     }
189 #endif  // DEBUG
190     return Changed(node);
191   }
192   return NoChange();
193 }
194 
195 
ReduceReferenceEqual(Node * node)196 Reduction EscapeAnalysisReducer::ReduceReferenceEqual(Node* node) {
197   DCHECK_EQ(node->opcode(), IrOpcode::kReferenceEqual);
198   Node* left = NodeProperties::GetValueInput(node, 0);
199   Node* right = NodeProperties::GetValueInput(node, 1);
200   if (escape_analysis()->IsVirtual(left)) {
201     if (escape_analysis()->IsVirtual(right) &&
202         escape_analysis()->CompareVirtualObjects(left, right)) {
203       ReplaceWithValue(node, jsgraph()->TrueConstant());
204       TRACE("Replaced ref eq #%d with true\n", node->id());
205       Replace(jsgraph()->TrueConstant());
206     }
207     // Right-hand side is not a virtual object, or a different one.
208     ReplaceWithValue(node, jsgraph()->FalseConstant());
209     TRACE("Replaced ref eq #%d with false\n", node->id());
210     return Replace(jsgraph()->FalseConstant());
211   } else if (escape_analysis()->IsVirtual(right)) {
212     // Left-hand side is not a virtual object.
213     ReplaceWithValue(node, jsgraph()->FalseConstant());
214     TRACE("Replaced ref eq #%d with false\n", node->id());
215     return Replace(jsgraph()->FalseConstant());
216   }
217   return NoChange();
218 }
219 
220 
ReduceObjectIsSmi(Node * node)221 Reduction EscapeAnalysisReducer::ReduceObjectIsSmi(Node* node) {
222   DCHECK_EQ(node->opcode(), IrOpcode::kObjectIsSmi);
223   Node* input = NodeProperties::GetValueInput(node, 0);
224   if (escape_analysis()->IsVirtual(input)) {
225     ReplaceWithValue(node, jsgraph()->FalseConstant());
226     TRACE("Replaced ObjectIsSmi #%d with false\n", node->id());
227     return Replace(jsgraph()->FalseConstant());
228   }
229   return NoChange();
230 }
231 
232 
ReduceFrameStateUses(Node * node)233 Reduction EscapeAnalysisReducer::ReduceFrameStateUses(Node* node) {
234   DCHECK_GE(node->op()->EffectInputCount(), 1);
235   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
236     fully_reduced_.Add(node->id());
237   }
238   bool changed = false;
239   for (int i = 0; i < node->InputCount(); ++i) {
240     Node* input = node->InputAt(i);
241     if (input->opcode() == IrOpcode::kFrameState) {
242       if (Node* ret = ReduceDeoptState(input, node, false)) {
243         node->ReplaceInput(i, ret);
244         changed = true;
245       }
246     }
247   }
248   if (changed) {
249     return Changed(node);
250   }
251   return NoChange();
252 }
253 
254 
255 // Returns the clone if it duplicated the node, and null otherwise.
ReduceDeoptState(Node * node,Node * effect,bool multiple_users)256 Node* EscapeAnalysisReducer::ReduceDeoptState(Node* node, Node* effect,
257                                               bool multiple_users) {
258   DCHECK(node->opcode() == IrOpcode::kFrameState ||
259          node->opcode() == IrOpcode::kStateValues);
260   if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
261       fully_reduced_.Contains(node->id())) {
262     return nullptr;
263   }
264   TRACE("Reducing %s %d\n", node->op()->mnemonic(), node->id());
265   Node* clone = nullptr;
266   bool node_multiused = node->UseCount() > 1;
267   bool multiple_users_rec = multiple_users || node_multiused;
268   for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
269     Node* input = NodeProperties::GetValueInput(node, i);
270     if (input->opcode() == IrOpcode::kStateValues) {
271       if (Node* ret = ReduceDeoptState(input, effect, multiple_users_rec)) {
272         if (node_multiused || (multiple_users && !clone)) {
273           TRACE("  Cloning #%d", node->id());
274           node = clone = jsgraph()->graph()->CloneNode(node);
275           TRACE(" to #%d\n", node->id());
276           node_multiused = false;
277         }
278         NodeProperties::ReplaceValueInput(node, ret, i);
279       }
280     } else {
281       if (Node* ret = ReduceStateValueInput(node, i, effect, node_multiused,
282                                             clone, multiple_users)) {
283         DCHECK_NULL(clone);
284         node_multiused = false;  // Don't clone anymore.
285         node = clone = ret;
286       }
287     }
288   }
289   if (node->opcode() == IrOpcode::kFrameState) {
290     Node* outer_frame_state = NodeProperties::GetFrameStateInput(node);
291     if (outer_frame_state->opcode() == IrOpcode::kFrameState) {
292       if (Node* ret =
293               ReduceDeoptState(outer_frame_state, effect, multiple_users_rec)) {
294         if (node_multiused || (multiple_users && !clone)) {
295           TRACE("    Cloning #%d", node->id());
296           node = clone = jsgraph()->graph()->CloneNode(node);
297           TRACE(" to #%d\n", node->id());
298         }
299         NodeProperties::ReplaceFrameStateInput(node, ret);
300       }
301     }
302   }
303   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
304     fully_reduced_.Add(node->id());
305   }
306   return clone;
307 }
308 
309 
310 // Returns the clone if it duplicated the node, and null otherwise.
ReduceStateValueInput(Node * node,int node_index,Node * effect,bool node_multiused,bool already_cloned,bool multiple_users)311 Node* EscapeAnalysisReducer::ReduceStateValueInput(Node* node, int node_index,
312                                                    Node* effect,
313                                                    bool node_multiused,
314                                                    bool already_cloned,
315                                                    bool multiple_users) {
316   Node* input = NodeProperties::GetValueInput(node, node_index);
317   if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
318       fully_reduced_.Contains(node->id())) {
319     return nullptr;
320   }
321   TRACE("Reducing State Input #%d (%s)\n", input->id(),
322         input->op()->mnemonic());
323   Node* clone = nullptr;
324   if (input->opcode() == IrOpcode::kFinishRegion ||
325       input->opcode() == IrOpcode::kAllocate) {
326     if (escape_analysis()->IsVirtual(input)) {
327       if (escape_analysis()->IsCyclicObjectState(effect, input)) {
328         // TODO(mstarzinger): Represent cyclic object states differently to
329         // ensure the scheduler can properly handle such object states.
330         compilation_failed_ = true;
331         return nullptr;
332       }
333       if (Node* object_state =
334               escape_analysis()->GetOrCreateObjectState(effect, input)) {
335         if (node_multiused || (multiple_users && !already_cloned)) {
336           TRACE("Cloning #%d", node->id());
337           node = clone = jsgraph()->graph()->CloneNode(node);
338           TRACE(" to #%d\n", node->id());
339           node_multiused = false;
340           already_cloned = true;
341         }
342         NodeProperties::ReplaceValueInput(node, object_state, node_index);
343         TRACE("Replaced state #%d input #%d with object state #%d\n",
344               node->id(), input->id(), object_state->id());
345       } else {
346         TRACE("No object state replacement for #%d at effect #%d available.\n",
347               input->id(), effect->id());
348         UNREACHABLE();
349       }
350     }
351   }
352   return clone;
353 }
354 
355 
VerifyReplacement() const356 void EscapeAnalysisReducer::VerifyReplacement() const {
357 #ifdef DEBUG
358   AllNodes all(zone(), jsgraph()->graph());
359   for (Node* node : all.reachable) {
360     if (node->opcode() == IrOpcode::kAllocate) {
361       CHECK(!escape_analysis_->IsVirtual(node));
362     }
363   }
364 #endif  // DEBUG
365 }
366 
isolate() const367 Isolate* EscapeAnalysisReducer::isolate() const { return jsgraph_->isolate(); }
368 
369 }  // namespace compiler
370 }  // namespace internal
371 }  // namespace v8
372