Line data Source code
1 : // Copyright 2016 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/typed-optimization.h"
6 :
7 : #include "src/compilation-dependencies.h"
8 : #include "src/compiler/js-graph.h"
9 : #include "src/compiler/node-properties.h"
10 : #include "src/compiler/simplified-operator.h"
11 : #include "src/compiler/type-cache.h"
12 : #include "src/isolate-inl.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 : namespace compiler {
17 :
18 443514 : TypedOptimization::TypedOptimization(Editor* editor,
19 : CompilationDependencies* dependencies,
20 : JSGraph* jsgraph)
21 : : AdvancedReducer(editor),
22 : dependencies_(dependencies),
23 : jsgraph_(jsgraph),
24 443514 : true_type_(Type::HeapConstant(factory()->true_value(), graph()->zone())),
25 : false_type_(
26 443516 : Type::HeapConstant(factory()->false_value(), graph()->zone())),
27 1330545 : type_cache_(TypeCache::Get()) {}
28 :
29 887030 : TypedOptimization::~TypedOptimization() {}
30 :
31 63377566 : Reduction TypedOptimization::Reduce(Node* node) {
32 : // Check if the output type is a singleton. In that case we already know the
33 : // result value and can simply replace the node if it's eliminable.
34 78066498 : if (!NodeProperties::IsConstant(node) && NodeProperties::IsTyped(node) &&
35 : node->op()->HasProperty(Operator::kEliminatable)) {
36 : // TODO(v8:5303): We must not eliminate FinishRegion here. This special
37 : // case can be removed once we have separate operators for value and
38 : // effect regions.
39 14515079 : if (node->opcode() == IrOpcode::kFinishRegion) return NoChange();
40 : // We can only constant-fold nodes here, that are known to not cause any
41 : // side-effect, may it be a JavaScript observable side-effect or a possible
42 : // eager deoptimization exit (i.e. {node} has an operator that doesn't have
43 : // the Operator::kNoDeopt property).
44 : Type* upper = NodeProperties::GetType(node);
45 14283375 : if (upper->IsInhabited()) {
46 14283055 : if (upper->IsHeapConstant()) {
47 : Node* replacement =
48 60968 : jsgraph()->Constant(upper->AsHeapConstant()->Value());
49 119063 : ReplaceWithValue(node, replacement);
50 : return Changed(replacement);
51 14222084 : } else if (upper->Is(Type::MinusZero())) {
52 30 : Node* replacement = jsgraph()->Constant(factory()->minus_zero_value());
53 : ReplaceWithValue(node, replacement);
54 : return Changed(replacement);
55 14222053 : } else if (upper->Is(Type::NaN())) {
56 644 : Node* replacement = jsgraph()->NaNConstant();
57 : ReplaceWithValue(node, replacement);
58 : return Changed(replacement);
59 14221412 : } else if (upper->Is(Type::Null())) {
60 1 : Node* replacement = jsgraph()->NullConstant();
61 : ReplaceWithValue(node, replacement);
62 : return Changed(replacement);
63 14634073 : } else if (upper->Is(Type::PlainNumber()) &&
64 412671 : upper->Min() == upper->Max()) {
65 114838 : Node* replacement = jsgraph()->Constant(upper->Min());
66 : ReplaceWithValue(node, replacement);
67 : return Changed(replacement);
68 14163979 : } else if (upper->Is(Type::Undefined())) {
69 1 : Node* replacement = jsgraph()->UndefinedConstant();
70 : ReplaceWithValue(node, replacement);
71 : return Changed(replacement);
72 : }
73 : }
74 : }
75 31453876 : switch (node->opcode()) {
76 : case IrOpcode::kCheckHeapObject:
77 44341 : return ReduceCheckHeapObject(node);
78 : case IrOpcode::kCheckNotTaggedHole:
79 952 : return ReduceCheckNotTaggedHole(node);
80 : case IrOpcode::kCheckMaps:
81 83195 : return ReduceCheckMaps(node);
82 : case IrOpcode::kCheckNumber:
83 1733 : return ReduceCheckNumber(node);
84 : case IrOpcode::kCheckString:
85 4487 : return ReduceCheckString(node);
86 : case IrOpcode::kCheckSeqString:
87 2416 : return ReduceCheckSeqString(node);
88 : case IrOpcode::kCheckEqualsInternalizedString:
89 88 : return ReduceCheckEqualsInternalizedString(node);
90 : case IrOpcode::kCheckEqualsSymbol:
91 34 : return ReduceCheckEqualsSymbol(node);
92 : case IrOpcode::kLoadField:
93 1223481 : return ReduceLoadField(node);
94 : case IrOpcode::kNumberCeil:
95 : case IrOpcode::kNumberRound:
96 : case IrOpcode::kNumberTrunc:
97 6821 : return ReduceNumberRoundop(node);
98 : case IrOpcode::kNumberFloor:
99 9261 : return ReduceNumberFloor(node);
100 : case IrOpcode::kNumberToUint8Clamped:
101 578 : return ReduceNumberToUint8Clamped(node);
102 : case IrOpcode::kPhi:
103 326211 : return ReducePhi(node);
104 : case IrOpcode::kReferenceEqual:
105 222133 : return ReduceReferenceEqual(node);
106 : case IrOpcode::kSelect:
107 17231 : return ReduceSelect(node);
108 : case IrOpcode::kTypeOf:
109 36979 : return ReduceTypeOf(node);
110 : case IrOpcode::kToBoolean:
111 84848 : return ReduceToBoolean(node);
112 : case IrOpcode::kSpeculativeToNumber:
113 24142 : return ReduceSpeculativeToNumber(node);
114 : default:
115 : break;
116 : }
117 : return NoChange();
118 : }
119 :
120 : namespace {
121 :
122 89636 : MaybeHandle<Map> GetStableMapFromObjectType(Type* object_type) {
123 89636 : if (object_type->IsHeapConstant()) {
124 : Handle<Map> object_map(object_type->AsHeapConstant()->Value()->map());
125 5872 : if (object_map->is_stable()) return object_map;
126 : }
127 88237 : return MaybeHandle<Map>();
128 : }
129 :
130 : } // namespace
131 :
132 44341 : Reduction TypedOptimization::ReduceCheckHeapObject(Node* node) {
133 44341 : Node* const input = NodeProperties::GetValueInput(node, 0);
134 : Type* const input_type = NodeProperties::GetType(input);
135 44341 : if (!input_type->Maybe(Type::SignedSmall())) {
136 6419 : ReplaceWithValue(node, input);
137 : return Replace(input);
138 : }
139 : return NoChange();
140 : }
141 :
142 952 : Reduction TypedOptimization::ReduceCheckNotTaggedHole(Node* node) {
143 952 : Node* const input = NodeProperties::GetValueInput(node, 0);
144 : Type* const input_type = NodeProperties::GetType(input);
145 952 : if (!input_type->Maybe(Type::Hole())) {
146 0 : ReplaceWithValue(node, input);
147 : return Replace(input);
148 : }
149 : return NoChange();
150 : }
151 :
152 84538 : Reduction TypedOptimization::ReduceCheckMaps(Node* node) {
153 : // The CheckMaps(o, ...map...) can be eliminated if map is stable,
154 : // o has type Constant(object) and map == object->map, and either
155 : // (1) map cannot transition further, or
156 : // (2) we can add a code dependency on the stability of map
157 : // (to guard the Constant type information).
158 83195 : Node* const object = NodeProperties::GetValueInput(node, 0);
159 : Type* const object_type = NodeProperties::GetType(object);
160 83195 : Node* const effect = NodeProperties::GetEffectInput(node);
161 : Handle<Map> object_map;
162 166390 : if (GetStableMapFromObjectType(object_type).ToHandle(&object_map)) {
163 2686 : for (int i = 1; i < node->op()->ValueInputCount(); ++i) {
164 0 : Node* const map = NodeProperties::GetValueInput(node, i);
165 : Type* const map_type = NodeProperties::GetType(map);
166 0 : if (map_type->IsHeapConstant() &&
167 : map_type->AsHeapConstant()->Value().is_identical_to(object_map)) {
168 0 : if (object_map->CanTransition()) {
169 0 : dependencies()->AssumeMapStable(object_map);
170 : }
171 : return Replace(effect);
172 : }
173 : }
174 : }
175 : return NoChange();
176 : }
177 :
178 1733 : Reduction TypedOptimization::ReduceCheckNumber(Node* node) {
179 1733 : Node* const input = NodeProperties::GetValueInput(node, 0);
180 : Type* const input_type = NodeProperties::GetType(input);
181 1733 : if (input_type->Is(Type::Number())) {
182 1314 : ReplaceWithValue(node, input);
183 : return Replace(input);
184 : }
185 : return NoChange();
186 : }
187 :
188 4487 : Reduction TypedOptimization::ReduceCheckString(Node* node) {
189 4487 : Node* const input = NodeProperties::GetValueInput(node, 0);
190 : Type* const input_type = NodeProperties::GetType(input);
191 4487 : if (input_type->Is(Type::String())) {
192 358 : ReplaceWithValue(node, input);
193 : return Replace(input);
194 : }
195 : return NoChange();
196 : }
197 :
198 2416 : Reduction TypedOptimization::ReduceCheckSeqString(Node* node) {
199 2416 : Node* const input = NodeProperties::GetValueInput(node, 0);
200 : Type* const input_type = NodeProperties::GetType(input);
201 2416 : if (input_type->Is(Type::SeqString())) {
202 377 : ReplaceWithValue(node, input);
203 : return Replace(input);
204 : }
205 : return NoChange();
206 : }
207 :
208 88 : Reduction TypedOptimization::ReduceCheckEqualsInternalizedString(Node* node) {
209 88 : Node* const exp = NodeProperties::GetValueInput(node, 0);
210 : Type* const exp_type = NodeProperties::GetType(exp);
211 88 : Node* const val = NodeProperties::GetValueInput(node, 1);
212 : Type* const val_type = NodeProperties::GetType(val);
213 88 : Node* const effect = NodeProperties::GetEffectInput(node);
214 88 : if (val_type->Is(exp_type)) return Replace(effect);
215 : // TODO(turbofan): Should we also try to optimize the
216 : // non-internalized String case for {val} here?
217 : return NoChange();
218 : }
219 :
220 34 : Reduction TypedOptimization::ReduceCheckEqualsSymbol(Node* node) {
221 34 : Node* const exp = NodeProperties::GetValueInput(node, 0);
222 : Type* const exp_type = NodeProperties::GetType(exp);
223 34 : Node* const val = NodeProperties::GetValueInput(node, 1);
224 : Type* const val_type = NodeProperties::GetType(val);
225 34 : Node* const effect = NodeProperties::GetEffectInput(node);
226 34 : if (val_type->Is(exp_type)) return Replace(effect);
227 : return NoChange();
228 : }
229 :
230 2447074 : Reduction TypedOptimization::ReduceLoadField(Node* node) {
231 1223481 : Node* const object = NodeProperties::GetValueInput(node, 0);
232 : Type* const object_type = NodeProperties::GetType(object);
233 1223481 : FieldAccess const& access = FieldAccessOf(node->op());
234 1223481 : if (access.base_is_tagged == kTaggedBase &&
235 : access.offset == HeapObject::kMapOffset) {
236 : // We can replace LoadField[Map](o) with map if is stable, and
237 : // o has type Constant(object) and map == object->map, and either
238 : // (1) map cannot transition further, or
239 : // (2) deoptimization is enabled and we can add a code dependency on the
240 : // stability of map (to guard the Constant type information).
241 : Handle<Map> object_map;
242 12882 : if (GetStableMapFromObjectType(object_type).ToHandle(&object_map)) {
243 56 : if (object_map->CanTransition()) {
244 56 : dependencies()->AssumeMapStable(object_map);
245 : }
246 56 : Node* const value = jsgraph()->HeapConstant(object_map);
247 56 : ReplaceWithValue(node, value);
248 : return Replace(value);
249 : }
250 : }
251 : return NoChange();
252 : }
253 :
254 9261 : Reduction TypedOptimization::ReduceNumberFloor(Node* node) {
255 9724 : Node* const input = NodeProperties::GetValueInput(node, 0);
256 : Type* const input_type = NodeProperties::GetType(input);
257 18522 : if (input_type->Is(type_cache_.kIntegerOrMinusZeroOrNaN)) {
258 : return Replace(input);
259 : }
260 18953 : if (input_type->Is(Type::PlainNumber()) &&
261 455 : (input->opcode() == IrOpcode::kNumberDivide ||
262 : input->opcode() == IrOpcode::kSpeculativeNumberDivide)) {
263 416 : Node* const lhs = NodeProperties::GetValueInput(input, 0);
264 : Type* const lhs_type = NodeProperties::GetType(lhs);
265 416 : Node* const rhs = NodeProperties::GetValueInput(input, 1);
266 : Type* const rhs_type = NodeProperties::GetType(rhs);
267 432 : if (lhs_type->Is(Type::Unsigned32()) && rhs_type->Is(Type::Unsigned32())) {
268 : // We can replace
269 : //
270 : // NumberFloor(NumberDivide(lhs: unsigned32,
271 : // rhs: unsigned32)): plain-number
272 : //
273 : // with
274 : //
275 : // NumberToUint32(NumberDivide(lhs, rhs))
276 : //
277 : // and just smash the type of the {lhs} on the {node},
278 : // as the truncated result must be in the same range as
279 : // {lhs} since {rhs} cannot be less than 1 (due to the
280 : // plain-number type constraint on the {node}).
281 16 : NodeProperties::ChangeOp(node, simplified()->NumberToUint32());
282 : NodeProperties::SetType(node, lhs_type);
283 : return Changed(node);
284 : }
285 : }
286 : return NoChange();
287 : }
288 :
289 6821 : Reduction TypedOptimization::ReduceNumberRoundop(Node* node) {
290 6821 : Node* const input = NodeProperties::GetValueInput(node, 0);
291 : Type* const input_type = NodeProperties::GetType(input);
292 13642 : if (input_type->Is(type_cache_.kIntegerOrMinusZeroOrNaN)) {
293 : return Replace(input);
294 : }
295 : return NoChange();
296 : }
297 :
298 578 : Reduction TypedOptimization::ReduceNumberToUint8Clamped(Node* node) {
299 578 : Node* const input = NodeProperties::GetValueInput(node, 0);
300 : Type* const input_type = NodeProperties::GetType(input);
301 1156 : if (input_type->Is(type_cache_.kUint8)) {
302 : return Replace(input);
303 : }
304 : return NoChange();
305 : }
306 :
307 326211 : Reduction TypedOptimization::ReducePhi(Node* node) {
308 : // Try to narrow the type of the Phi {node}, which might be more precise now
309 : // after lowering based on types, i.e. a SpeculativeNumberAdd has a more
310 : // precise type than the JSAdd that was in the graph when the Typer was run.
311 : DCHECK_EQ(IrOpcode::kPhi, node->opcode());
312 326211 : int arity = node->op()->ValueInputCount();
313 : Type* type = NodeProperties::GetType(node->InputAt(0));
314 978588 : for (int i = 1; i < arity; ++i) {
315 : type = Type::Union(type, NodeProperties::GetType(node->InputAt(i)),
316 1304754 : graph()->zone());
317 : }
318 : Type* const node_type = NodeProperties::GetType(node);
319 326211 : if (!node_type->Is(type)) {
320 6626 : type = Type::Intersect(node_type, type, graph()->zone());
321 : NodeProperties::SetType(node, type);
322 : return Changed(node);
323 : }
324 : return NoChange();
325 : }
326 :
327 274864 : Reduction TypedOptimization::ReduceReferenceEqual(Node* node) {
328 : DCHECK_EQ(IrOpcode::kReferenceEqual, node->opcode());
329 222133 : Node* const lhs = NodeProperties::GetValueInput(node, 0);
330 222133 : Node* const rhs = NodeProperties::GetValueInput(node, 1);
331 : Type* const lhs_type = NodeProperties::GetType(lhs);
332 : Type* const rhs_type = NodeProperties::GetType(rhs);
333 222133 : if (!lhs_type->Maybe(rhs_type)) {
334 26369 : Node* replacement = jsgraph()->FalseConstant();
335 : // Make sure we do not widen the type.
336 26369 : if (NodeProperties::GetType(replacement)
337 : ->Is(NodeProperties::GetType(node))) {
338 26362 : return Replace(jsgraph()->FalseConstant());
339 : }
340 : }
341 : return NoChange();
342 : }
343 :
344 17231 : Reduction TypedOptimization::ReduceSelect(Node* node) {
345 : DCHECK_EQ(IrOpcode::kSelect, node->opcode());
346 17231 : Node* const condition = NodeProperties::GetValueInput(node, 0);
347 : Type* const condition_type = NodeProperties::GetType(condition);
348 17231 : Node* const vtrue = NodeProperties::GetValueInput(node, 1);
349 : Type* const vtrue_type = NodeProperties::GetType(vtrue);
350 17231 : Node* const vfalse = NodeProperties::GetValueInput(node, 2);
351 : Type* const vfalse_type = NodeProperties::GetType(vfalse);
352 34462 : if (condition_type->Is(true_type_)) {
353 : // Select(condition:true, vtrue, vfalse) => vtrue
354 : return Replace(vtrue);
355 : }
356 33716 : if (condition_type->Is(false_type_)) {
357 : // Select(condition:false, vtrue, vfalse) => vfalse
358 : return Replace(vfalse);
359 : }
360 32685 : if (vtrue_type->Is(true_type_) && vfalse_type->Is(false_type_)) {
361 : // Select(condition, vtrue:true, vfalse:false) => condition
362 : return Replace(condition);
363 : }
364 27703 : if (vtrue_type->Is(false_type_) && vfalse_type->Is(true_type_)) {
365 : // Select(condition, vtrue:false, vfalse:true) => BooleanNot(condition)
366 0 : node->TrimInputCount(1);
367 0 : NodeProperties::ChangeOp(node, simplified()->BooleanNot());
368 : return Changed(node);
369 : }
370 : // Try to narrow the type of the Select {node}, which might be more precise
371 : // now after lowering based on types.
372 13355 : Type* type = Type::Union(vtrue_type, vfalse_type, graph()->zone());
373 : Type* const node_type = NodeProperties::GetType(node);
374 13355 : if (!node_type->Is(type)) {
375 637 : type = Type::Intersect(node_type, type, graph()->zone());
376 : NodeProperties::SetType(node, type);
377 : return Changed(node);
378 : }
379 : return NoChange();
380 : }
381 :
382 24142 : Reduction TypedOptimization::ReduceSpeculativeToNumber(Node* node) {
383 : DCHECK_EQ(IrOpcode::kSpeculativeToNumber, node->opcode());
384 24142 : Node* const input = NodeProperties::GetValueInput(node, 0);
385 : Type* const input_type = NodeProperties::GetType(input);
386 24142 : if (input_type->Is(Type::Number())) {
387 : // SpeculativeToNumber(x:number) => x
388 16302 : ReplaceWithValue(node, input);
389 : return Replace(input);
390 : }
391 : return NoChange();
392 : }
393 :
394 53132 : Reduction TypedOptimization::ReduceTypeOf(Node* node) {
395 : Node* const input = node->InputAt(0);
396 : Type* const type = NodeProperties::GetType(input);
397 : Factory* const f = factory();
398 36979 : if (type->Is(Type::Boolean())) {
399 2602 : return Replace(jsgraph()->Constant(f->boolean_string()));
400 34377 : } else if (type->Is(Type::Number())) {
401 10486 : return Replace(jsgraph()->Constant(f->number_string()));
402 23891 : } else if (type->Is(Type::String())) {
403 1152 : return Replace(jsgraph()->Constant(f->string_string()));
404 22739 : } else if (type->Is(Type::Symbol())) {
405 0 : return Replace(jsgraph()->Constant(f->symbol_string()));
406 22739 : } else if (type->Is(Type::OtherUndetectableOrUndefined())) {
407 250 : return Replace(jsgraph()->Constant(f->undefined_string()));
408 22489 : } else if (type->Is(Type::NonCallableOrNull())) {
409 1613 : return Replace(jsgraph()->Constant(f->object_string()));
410 20876 : } else if (type->Is(Type::Function())) {
411 50 : return Replace(jsgraph()->Constant(f->function_string()));
412 20826 : } else if (type->IsHeapConstant()) {
413 : return Replace(jsgraph()->Constant(
414 0 : Object::TypeOf(isolate(), type->AsHeapConstant()->Value())));
415 : }
416 :
417 : return NoChange();
418 : }
419 :
420 87428 : Reduction TypedOptimization::ReduceToBoolean(Node* node) {
421 : Node* const input = node->InputAt(0);
422 : Type* const input_type = NodeProperties::GetType(input);
423 84848 : if (input_type->Is(Type::Boolean())) {
424 : // ToBoolean(x:boolean) => x
425 : return Replace(input);
426 57633 : } else if (input_type->Is(Type::OrderedNumber())) {
427 : // SToBoolean(x:ordered-number) => BooleanNot(NumberEqual(x,#0))
428 : node->ReplaceInput(0, graph()->NewNode(simplified()->NumberEqual(), input,
429 7623 : jsgraph()->ZeroConstant()));
430 2541 : node->TrimInputCount(1);
431 2541 : NodeProperties::ChangeOp(node, simplified()->BooleanNot());
432 : return Changed(node);
433 55092 : } else if (input_type->Is(Type::Number())) {
434 : // ToBoolean(x:number) => NumberToBoolean(x)
435 197 : node->TrimInputCount(1);
436 197 : NodeProperties::ChangeOp(node, simplified()->NumberToBoolean());
437 : return Changed(node);
438 54895 : } else if (input_type->Is(Type::DetectableReceiverOrNull())) {
439 : // ToBoolean(x:detectable receiver \/ null)
440 : // => BooleanNot(ReferenceEqual(x,#null))
441 : node->ReplaceInput(0, graph()->NewNode(simplified()->ReferenceEqual(),
442 54 : input, jsgraph()->NullConstant()));
443 18 : node->TrimInputCount(1);
444 18 : NodeProperties::ChangeOp(node, simplified()->BooleanNot());
445 : return Changed(node);
446 54877 : } else if (input_type->Is(Type::ReceiverOrNullOrUndefined())) {
447 : // ToBoolean(x:receiver \/ null \/ undefined)
448 : // => BooleanNot(ObjectIsUndetectable(x))
449 : node->ReplaceInput(
450 144 : 0, graph()->NewNode(simplified()->ObjectIsUndetectable(), input));
451 72 : node->TrimInputCount(1);
452 72 : NodeProperties::ChangeOp(node, simplified()->BooleanNot());
453 : return Changed(node);
454 54805 : } else if (input_type->Is(Type::String())) {
455 : // ToBoolean(x:string) => BooleanNot(ReferenceEqual(x,""))
456 : node->ReplaceInput(0,
457 : graph()->NewNode(simplified()->ReferenceEqual(), input,
458 63 : jsgraph()->EmptyStringConstant()));
459 21 : node->TrimInputCount(1);
460 21 : NodeProperties::ChangeOp(node, simplified()->BooleanNot());
461 : return Changed(node);
462 : }
463 : return NoChange();
464 : }
465 :
466 0 : Factory* TypedOptimization::factory() const { return isolate()->factory(); }
467 :
468 1562677 : Graph* TypedOptimization::graph() const { return jsgraph()->graph(); }
469 :
470 924039 : Isolate* TypedOptimization::isolate() const { return jsgraph()->isolate(); }
471 :
472 5517 : SimplifiedOperatorBuilder* TypedOptimization::simplified() const {
473 5517 : return jsgraph()->simplified();
474 : }
475 :
476 : } // namespace compiler
477 : } // namespace internal
478 : } // namespace v8
|
