1 // Copyright 2014 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/codegen/tick-counter.h"
6 #include "src/compiler/compilation-dependencies.h"
7 #include "src/compiler/js-graph.h"
8 #include "src/compiler/js-heap-broker.h"
9 #include "src/compiler/js-heap-copy-reducer.h"
10 #include "src/compiler/js-typed-lowering.h"
11 #include "src/compiler/machine-operator.h"
12 #include "src/compiler/node-properties.h"
13 #include "src/compiler/opcodes.h"
14 #include "src/compiler/operator-properties.h"
15 #include "src/compiler/simplified-operator.h"
16 #include "src/compiler/typer.h"
17 #include "src/execution/isolate.h"
18 #include "src/heap/factory-inl.h"
19 #include "src/objects/objects.h"
20 #include "test/cctest/cctest.h"
21 
22 namespace v8 {
23 namespace internal {
24 namespace compiler {
25 
26 class JSTypedLoweringTester : public HandleAndZoneScope {
27  public:
JSTypedLoweringTester(int num_parameters=0)28   explicit JSTypedLoweringTester(int num_parameters = 0)
29       : HandleAndZoneScope(kCompressGraphZone),
30         isolate(main_isolate()),
31         canonical(isolate),
32         js_heap_broker(isolate, main_zone()),
33         binop(nullptr),
34         unop(nullptr),
35         javascript(main_zone()),
36         machine(main_zone()),
37         simplified(main_zone()),
38         common(main_zone()),
39         graph(main_zone()),
40         typer(&js_heap_broker, Typer::kNoFlags, &graph, &tick_counter),
41         context_node(nullptr),
42         deps(&js_heap_broker, main_zone()) {
43     graph.SetStart(graph.NewNode(common.Start(num_parameters)));
44     graph.SetEnd(graph.NewNode(common.End(1), graph.start()));
45     typer.Run();
46   }
47 
48   Isolate* isolate;
49   TickCounter tick_counter;
50   CanonicalHandleScope canonical;
51   JSHeapBroker js_heap_broker;
52   const Operator* binop;
53   const Operator* unop;
54   JSOperatorBuilder javascript;
55   MachineOperatorBuilder machine;
56   SimplifiedOperatorBuilder simplified;
57   CommonOperatorBuilder common;
58   Graph graph;
59   Typer typer;
60   Node* context_node;
61   CompilationDependencies deps;
62 
Parameter(Type t,int32_t index=0)63   Node* Parameter(Type t, int32_t index = 0) {
64     Node* n = graph.NewNode(common.Parameter(index), graph.start());
65     NodeProperties::SetType(n, t);
66     return n;
67   }
68 
UndefinedConstant()69   Node* UndefinedConstant() {
70     Handle<HeapObject> value = isolate->factory()->undefined_value();
71     return graph.NewNode(common.HeapConstant(value));
72   }
73 
HeapConstant(Handle<HeapObject> constant)74   Node* HeapConstant(Handle<HeapObject> constant) {
75     return graph.NewNode(common.HeapConstant(constant));
76   }
77 
EmptyFrameState(Node * context)78   Node* EmptyFrameState(Node* context) {
79     Node* parameters =
80         graph.NewNode(common.StateValues(0, SparseInputMask::Dense()));
81     Node* locals =
82         graph.NewNode(common.StateValues(0, SparseInputMask::Dense()));
83     Node* stack =
84         graph.NewNode(common.StateValues(0, SparseInputMask::Dense()));
85 
86     Node* state_node = graph.NewNode(
87         common.FrameState(BytecodeOffset::None(),
88                           OutputFrameStateCombine::Ignore(), nullptr),
89         parameters, locals, stack, context, UndefinedConstant(), graph.start());
90 
91     return state_node;
92   }
93 
reduce(Node * node)94   Node* reduce(Node* node) {
95     JSHeapCopyReducer heap_copy_reducer(&js_heap_broker);
96     CHECK(!heap_copy_reducer.Reduce(node).Changed());
97     JSGraph jsgraph(main_isolate(), &graph, &common, &javascript, &simplified,
98                     &machine);
99     GraphReducer graph_reducer(main_zone(), &graph, &tick_counter,
100                                &js_heap_broker);
101     JSTypedLowering reducer(&graph_reducer, &jsgraph, &js_heap_broker,
102                             main_zone());
103     Reduction reduction = reducer.Reduce(node);
104     if (reduction.Changed()) return reduction.replacement();
105     return node;
106   }
107 
start()108   Node* start() { return graph.start(); }
109 
context()110   Node* context() {
111     if (context_node == nullptr) {
112       context_node = graph.NewNode(common.Parameter(-1), graph.start());
113     }
114     return context_node;
115   }
116 
control()117   Node* control() { return start(); }
118 
CheckBinop(IrOpcode::Value expected,Node * node)119   void CheckBinop(IrOpcode::Value expected, Node* node) {
120     CHECK_EQ(expected, node->opcode());
121   }
122 
CheckBinop(const Operator * expected,Node * node)123   void CheckBinop(const Operator* expected, Node* node) {
124     CHECK_EQ(expected->opcode(), node->op()->opcode());
125   }
126 
ReduceUnop(const Operator * op,Type input_type)127   Node* ReduceUnop(const Operator* op, Type input_type) {
128     return reduce(Unop(op, Parameter(input_type)));
129   }
130 
ReduceBinop(const Operator * op,Type left_type,Type right_type)131   Node* ReduceBinop(const Operator* op, Type left_type, Type right_type) {
132     return reduce(Binop(op, Parameter(left_type, 0), Parameter(right_type, 1)));
133   }
134 
Binop(const Operator * op,Node * left,Node * right)135   Node* Binop(const Operator* op, Node* left, Node* right) {
136     // JS binops also require context, effect, and control
137     std::vector<Node*> inputs;
138     inputs.push_back(left);
139     inputs.push_back(right);
140     if (JSOperator::IsBinaryWithFeedback(op->opcode())) {
141       inputs.push_back(UndefinedConstant());  // Feedback vector.
142     }
143     if (OperatorProperties::HasContextInput(op)) {
144       inputs.push_back(context());
145     }
146     for (int i = 0; i < OperatorProperties::GetFrameStateInputCount(op); i++) {
147       inputs.push_back(EmptyFrameState(context()));
148     }
149     if (op->EffectInputCount() > 0) {
150       inputs.push_back(start());
151     }
152     if (op->ControlInputCount() > 0) {
153       inputs.push_back(control());
154     }
155     return graph.NewNode(op, static_cast<int>(inputs.size()),
156                          &(inputs.front()));
157   }
158 
Unop(const Operator * op,Node * input)159   Node* Unop(const Operator* op, Node* input) {
160     DCHECK(!JSOperator::IsUnaryWithFeedback(op->opcode()));
161     // JS unops also require context, effect, and control
162     if (OperatorProperties::GetFrameStateInputCount(op) > 0) {
163       CHECK_EQ(1, OperatorProperties::GetFrameStateInputCount(op));
164       return graph.NewNode(op, input, context(), EmptyFrameState(context()),
165                            start(), control());
166     } else {
167       return graph.NewNode(op, input, context(), start(), control());
168     }
169   }
170 
UseForEffect(Node * node)171   Node* UseForEffect(Node* node) {
172     Node* merge = graph.NewNode(common.Merge(1), start());
173     return graph.NewNode(common.EffectPhi(1), node, merge);
174   }
175 
CheckEffectInput(Node * effect,Node * use)176   void CheckEffectInput(Node* effect, Node* use) {
177     CHECK_EQ(effect, NodeProperties::GetEffectInput(use));
178   }
179 
CheckNumberConstant(double expected,Node * result)180   void CheckNumberConstant(double expected, Node* result) {
181     CHECK_EQ(IrOpcode::kNumberConstant, result->opcode());
182     CHECK_EQ(expected, OpParameter<double>(result->op()));
183   }
184 
CheckNaN(Node * result)185   void CheckNaN(Node* result) {
186     CHECK_EQ(IrOpcode::kNumberConstant, result->opcode());
187     double value = OpParameter<double>(result->op());
188     CHECK(std::isnan(value));
189   }
190 
CheckTrue(Node * result)191   void CheckTrue(Node* result) {
192     CheckHandle(isolate->factory()->true_value(), result);
193   }
194 
CheckFalse(Node * result)195   void CheckFalse(Node* result) {
196     CheckHandle(isolate->factory()->false_value(), result);
197   }
198 
CheckHandle(Handle<HeapObject> expected,Node * result)199   void CheckHandle(Handle<HeapObject> expected, Node* result) {
200     CHECK_EQ(IrOpcode::kHeapConstant, result->opcode());
201     Handle<HeapObject> value = HeapConstantOf(result->op());
202     CHECK_EQ(*expected, *value);
203   }
204 };
205 
206 static Type kStringTypes[] = {Type::InternalizedString(), Type::String()};
207 
208 static Type kInt32Types[] = {Type::UnsignedSmall(), Type::Negative32(),
209                              Type::Unsigned31(),    Type::SignedSmall(),
210                              Type::Signed32(),      Type::Unsigned32(),
211                              Type::Integral32()};
212 
213 static Type kNumberTypes[] = {
214     Type::UnsignedSmall(), Type::Negative32(),  Type::Unsigned31(),
215     Type::SignedSmall(),   Type::Signed32(),    Type::Unsigned32(),
216     Type::Integral32(),    Type::MinusZero(),   Type::NaN(),
217     Type::OrderedNumber(), Type::PlainNumber(), Type::Number()};
218 
I32Type(bool is_signed)219 static Type I32Type(bool is_signed) {
220   return is_signed ? Type::Signed32() : Type::Unsigned32();
221 }
222 
223 
NumberToI32(bool is_signed)224 static IrOpcode::Value NumberToI32(bool is_signed) {
225   return is_signed ? IrOpcode::kNumberToInt32 : IrOpcode::kNumberToUint32;
226 }
227 
228 namespace {
229 
FeedbackSourceWithOneBinarySlot(JSTypedLoweringTester * R)230 FeedbackSource FeedbackSourceWithOneBinarySlot(JSTypedLoweringTester* R) {
231   return FeedbackSource{FeedbackVector::NewWithOneBinarySlotForTesting(
232                             R->main_zone(), R->main_isolate()),
233                         FeedbackSlot{0}};
234 }
235 
FeedbackSourceWithOneCompareSlot(JSTypedLoweringTester * R)236 FeedbackSource FeedbackSourceWithOneCompareSlot(JSTypedLoweringTester* R) {
237   return FeedbackSource{FeedbackVector::NewWithOneCompareSlotForTesting(
238                             R->main_zone(), R->main_isolate()),
239                         FeedbackSlot{0}};
240 }
241 
242 }  // namespace
243 
TEST(StringBinops)244 TEST(StringBinops) {
245   JSTypedLoweringTester R;
246 
247   for (size_t i = 0; i < arraysize(kStringTypes); ++i) {
248     Node* p0 = R.Parameter(kStringTypes[i], 0);
249 
250     for (size_t j = 0; j < arraysize(kStringTypes); ++j) {
251       Node* p1 = R.Parameter(kStringTypes[j], 1);
252 
253       Node* add = R.Binop(R.javascript.Add(FeedbackSourceWithOneBinarySlot(&R)),
254                           p0, p1);
255       Node* r = R.reduce(add);
256 
257       R.CheckBinop(IrOpcode::kStringConcat, r);
258       CHECK_EQ(p0, r->InputAt(1));
259       CHECK_EQ(p1, r->InputAt(2));
260     }
261   }
262 }
263 
TEST(AddNumber1)264 TEST(AddNumber1) {
265   JSTypedLoweringTester R;
266   for (size_t i = 0; i < arraysize(kNumberTypes); ++i) {
267     Node* p0 = R.Parameter(kNumberTypes[i], 0);
268     Node* p1 = R.Parameter(kNumberTypes[i], 1);
269     Node* add =
270         R.Binop(R.javascript.Add(FeedbackSourceWithOneBinarySlot(&R)), p0, p1);
271     Node* r = R.reduce(add);
272 
273     R.CheckBinop(IrOpcode::kNumberAdd, r);
274     CHECK_EQ(p0, r->InputAt(0));
275     CHECK_EQ(p1, r->InputAt(1));
276   }
277 }
278 
TEST(NumberBinops)279 TEST(NumberBinops) {
280   JSTypedLoweringTester R;
281   FeedbackSource feedback_source = FeedbackSourceWithOneBinarySlot(&R);
282   const Operator* ops[] = {
283       R.javascript.Add(feedback_source),      R.simplified.NumberAdd(),
284       R.javascript.Subtract(feedback_source), R.simplified.NumberSubtract(),
285       R.javascript.Multiply(feedback_source), R.simplified.NumberMultiply(),
286       R.javascript.Divide(feedback_source),   R.simplified.NumberDivide(),
287       R.javascript.Modulus(feedback_source),  R.simplified.NumberModulus(),
288   };
289 
290   for (size_t i = 0; i < arraysize(kNumberTypes); ++i) {
291     Node* p0 = R.Parameter(kNumberTypes[i], 0);
292 
293     for (size_t j = 0; j < arraysize(kNumberTypes); ++j) {
294       Node* p1 = R.Parameter(kNumberTypes[j], 1);
295 
296       for (size_t k = 0; k < arraysize(ops); k += 2) {
297         Node* add = R.Binop(ops[k], p0, p1);
298         Node* r = R.reduce(add);
299 
300         R.CheckBinop(ops[k + 1], r);
301         CHECK_EQ(p0, r->InputAt(0));
302         CHECK_EQ(p1, r->InputAt(1));
303       }
304     }
305   }
306 }
307 
308 
CheckToI32(Node * old_input,Node * new_input,bool is_signed)309 static void CheckToI32(Node* old_input, Node* new_input, bool is_signed) {
310   Type old_type = NodeProperties::GetType(old_input);
311   Type new_type = NodeProperties::GetType(new_input);
312   Type expected_type = I32Type(is_signed);
313   CHECK(new_type.Is(expected_type));
314   if (old_type.Is(expected_type)) {
315     CHECK_EQ(old_input, new_input);
316   } else if (new_input->opcode() == IrOpcode::kNumberConstant) {
317     double v = OpParameter<double>(new_input->op());
318     double e = static_cast<double>(is_signed ? FastD2I(v) : FastD2UI(v));
319     CHECK_EQ(e, v);
320   }
321 }
322 
323 
324 // A helper class for testing lowering of bitwise shift operators.
325 class JSBitwiseShiftTypedLoweringTester : public JSTypedLoweringTester {
326  public:
JSBitwiseShiftTypedLoweringTester()327   JSBitwiseShiftTypedLoweringTester() : JSTypedLoweringTester() {
328     int i = 0;
329     FeedbackSource feedback_source = FeedbackSourceWithOneBinarySlot(this);
330     set(i++, javascript.ShiftLeft(feedback_source), true);
331     set(i++, simplified.NumberShiftLeft(), false);
332     set(i++, javascript.ShiftRight(feedback_source), true);
333     set(i++, simplified.NumberShiftRight(), false);
334     set(i++, javascript.ShiftRightLogical(feedback_source), false);
335     set(i++, simplified.NumberShiftRightLogical(), false);
336   }
337   static const int kNumberOps = 6;
338   const Operator* ops[kNumberOps];
339   bool signedness[kNumberOps];
340 
341  private:
set(int idx,const Operator * op,bool s)342   void set(int idx, const Operator* op, bool s) {
343     ops[idx] = op;
344     signedness[idx] = s;
345   }
346 };
347 
348 
TEST(Int32BitwiseShifts)349 TEST(Int32BitwiseShifts) {
350   JSBitwiseShiftTypedLoweringTester R;
351 
352   Type types[] = {
353       Type::SignedSmall(), Type::UnsignedSmall(), Type::Negative32(),
354       Type::Unsigned31(),  Type::Unsigned32(),    Type::Signed32(),
355       Type::MinusZero(),   Type::NaN(),           Type::Undefined(),
356       Type::Null(),        Type::Boolean(),       Type::Number(),
357       Type::PlainNumber(), Type::String()};
358 
359   for (size_t i = 0; i < arraysize(types); ++i) {
360     Node* p0 = R.Parameter(types[i], 0);
361 
362     for (size_t j = 0; j < arraysize(types); ++j) {
363       Node* p1 = R.Parameter(types[j], 1);
364 
365       for (int k = 0; k < R.kNumberOps; k += 2) {
366         Node* add = R.Binop(R.ops[k], p0, p1);
367         Node* r = R.reduce(add);
368 
369         R.CheckBinop(R.ops[k + 1], r);
370         Node* r0 = r->InputAt(0);
371         Node* r1 = r->InputAt(1);
372 
373         CheckToI32(p0, r0, R.signedness[k]);
374         CheckToI32(p1, r1, false);
375       }
376     }
377   }
378 }
379 
380 
381 // A helper class for testing lowering of bitwise operators.
382 class JSBitwiseTypedLoweringTester : public JSTypedLoweringTester {
383  public:
JSBitwiseTypedLoweringTester()384   JSBitwiseTypedLoweringTester() : JSTypedLoweringTester() {
385     int i = 0;
386     FeedbackSource feedback_source = FeedbackSourceWithOneBinarySlot(this);
387     set(i++, javascript.BitwiseOr(feedback_source), true);
388     set(i++, simplified.NumberBitwiseOr(), true);
389     set(i++, javascript.BitwiseXor(feedback_source), true);
390     set(i++, simplified.NumberBitwiseXor(), true);
391     set(i++, javascript.BitwiseAnd(feedback_source), true);
392     set(i++, simplified.NumberBitwiseAnd(), true);
393   }
394   static const int kNumberOps = 6;
395   const Operator* ops[kNumberOps];
396   bool signedness[kNumberOps];
397 
398  private:
set(int idx,const Operator * op,bool s)399   void set(int idx, const Operator* op, bool s) {
400     ops[idx] = op;
401     signedness[idx] = s;
402   }
403 };
404 
405 
TEST(Int32BitwiseBinops)406 TEST(Int32BitwiseBinops) {
407   JSBitwiseTypedLoweringTester R;
408 
409   Type types[] = {
410       Type::SignedSmall(),   Type::UnsignedSmall(), Type::Unsigned32(),
411       Type::Signed32(),      Type::MinusZero(),     Type::NaN(),
412       Type::OrderedNumber(), Type::PlainNumber(),   Type::Undefined(),
413       Type::Null(),          Type::Boolean(),       Type::Number(),
414       Type::String()};
415 
416   for (size_t i = 0; i < arraysize(types); ++i) {
417     Node* p0 = R.Parameter(types[i], 0);
418 
419     for (size_t j = 0; j < arraysize(types); ++j) {
420       Node* p1 = R.Parameter(types[j], 1);
421 
422       for (int k = 0; k < R.kNumberOps; k += 2) {
423         Node* add = R.Binop(R.ops[k], p0, p1);
424         Node* r = R.reduce(add);
425 
426         R.CheckBinop(R.ops[k + 1], r);
427 
428         CheckToI32(p0, r->InputAt(0), R.signedness[k]);
429         CheckToI32(p1, r->InputAt(1), R.signedness[k + 1]);
430       }
431     }
432   }
433 }
434 
435 
TEST(JSToNumber1)436 TEST(JSToNumber1) {
437   JSTypedLoweringTester R;
438   const Operator* ton = R.javascript.ToNumber();
439 
440   for (size_t i = 0; i < arraysize(kNumberTypes); i++) {  // ToNumber(number)
441     Node* r = R.ReduceUnop(ton, kNumberTypes[i]);
442     CHECK_EQ(IrOpcode::kParameter, r->opcode());
443   }
444 
445   {  // ToNumber(undefined)
446     Node* r = R.ReduceUnop(ton, Type::Undefined());
447     R.CheckNaN(r);
448   }
449 
450   {  // ToNumber(null)
451     Node* r = R.ReduceUnop(ton, Type::Null());
452     R.CheckNumberConstant(0.0, r);
453   }
454 }
455 
456 
TEST(JSToNumber_replacement)457 TEST(JSToNumber_replacement) {
458   JSTypedLoweringTester R;
459 
460   Type types[] = {Type::Null(), Type::Undefined(), Type::Number()};
461 
462   for (size_t i = 0; i < arraysize(types); i++) {
463     Node* n = R.Parameter(types[i]);
464     Node* c =
465         R.graph.NewNode(R.javascript.ToNumber(), n, R.context(),
466                         R.EmptyFrameState(R.context()), R.start(), R.start());
467     Node* effect_use = R.UseForEffect(c);
468     Node* add = R.graph.NewNode(R.simplified.ReferenceEqual(), n, c);
469 
470     R.CheckEffectInput(c, effect_use);
471     Node* r = R.reduce(c);
472 
473     if (types[i].Is(Type::Number())) {
474       CHECK_EQ(n, r);
475     } else {
476       CHECK_EQ(IrOpcode::kNumberConstant, r->opcode());
477     }
478 
479     CHECK_EQ(n, add->InputAt(0));
480     CHECK_EQ(r, add->InputAt(1));
481     R.CheckEffectInput(R.start(), effect_use);
482   }
483 }
484 
485 
TEST(JSToNumberOfConstant)486 TEST(JSToNumberOfConstant) {
487   JSTypedLoweringTester R;
488 
489   const Operator* ops[] = {R.common.NumberConstant(0),
490                            R.common.NumberConstant(-1),
491                            R.common.NumberConstant(0.1)};
492 
493   for (size_t i = 0; i < arraysize(ops); i++) {
494     Node* n = R.graph.NewNode(ops[i]);
495     Node* convert = R.Unop(R.javascript.ToNumber(), n);
496     Node* r = R.reduce(convert);
497     // Note that either outcome below is correct. It only depends on whether
498     // the types of constants are eagerly computed or only computed by the
499     // typing pass.
500     if (NodeProperties::GetType(n).Is(Type::Number())) {
501       // If number constants are eagerly typed, then reduction should
502       // remove the ToNumber.
503       CHECK_EQ(n, r);
504     } else {
505       // Otherwise, type-based lowering should only look at the type, and
506       // *not* try to constant fold.
507       CHECK_EQ(convert, r);
508     }
509   }
510 }
511 
512 
TEST(JSToNumberOfNumberOrOtherPrimitive)513 TEST(JSToNumberOfNumberOrOtherPrimitive) {
514   JSTypedLoweringTester R;
515   Type others[] = {Type::Undefined(), Type::Null(), Type::Boolean(),
516                    Type::String()};
517 
518   for (size_t i = 0; i < arraysize(others); i++) {
519     Type t = Type::Union(Type::Number(), others[i], R.main_zone());
520     Node* r = R.ReduceUnop(R.javascript.ToNumber(), t);
521     CHECK_EQ(IrOpcode::kPlainPrimitiveToNumber, r->opcode());
522   }
523 }
524 
525 
TEST(JSToString1)526 TEST(JSToString1) {
527   JSTypedLoweringTester R;
528 
529   for (size_t i = 0; i < arraysize(kStringTypes); i++) {
530     Node* r = R.ReduceUnop(R.javascript.ToString(), kStringTypes[i]);
531     CHECK_EQ(IrOpcode::kParameter, r->opcode());
532   }
533 
534   const Operator* op = R.javascript.ToString();
535 
536   {  // ToString(undefined) => "undefined"
537     Node* r = R.ReduceUnop(op, Type::Undefined());
538     R.CheckHandle(R.isolate->factory()->undefined_string(), r);
539   }
540 
541   {  // ToString(null) => "null"
542     Node* r = R.ReduceUnop(op, Type::Null());
543     R.CheckHandle(R.isolate->factory()->null_string(), r);
544   }
545 
546   {  // ToString(boolean)
547     Node* r = R.ReduceUnop(op, Type::Boolean());
548     CHECK_EQ(IrOpcode::kSelect, r->opcode());
549   }
550 
551   {  // ToString(number)
552     Node* r = R.ReduceUnop(op, Type::Number());
553     CHECK_EQ(IrOpcode::kNumberToString, r->opcode());
554   }
555 
556   {  // ToString(string)
557     Node* r = R.ReduceUnop(op, Type::String());
558     CHECK_EQ(IrOpcode::kParameter, r->opcode());  // No-op
559   }
560 
561   {  // ToString(object)
562     Node* r = R.ReduceUnop(op, Type::Object());
563     CHECK_EQ(IrOpcode::kJSToString, r->opcode());  // No reduction.
564   }
565 }
566 
567 
TEST(JSToString_replacement)568 TEST(JSToString_replacement) {
569   JSTypedLoweringTester R;
570 
571   Type types[] = {Type::Null(), Type::Undefined(), Type::String()};
572 
573   for (size_t i = 0; i < arraysize(types); i++) {
574     Node* n = R.Parameter(types[i]);
575     Node* c =
576         R.graph.NewNode(R.javascript.ToString(), n, R.context(),
577                         R.EmptyFrameState(R.context()), R.start(), R.start());
578     Node* effect_use = R.UseForEffect(c);
579     Node* add = R.graph.NewNode(R.simplified.ReferenceEqual(), n, c);
580 
581     R.CheckEffectInput(c, effect_use);
582     Node* r = R.reduce(c);
583 
584     if (types[i].Is(Type::String())) {
585       CHECK_EQ(n, r);
586     } else {
587       CHECK_EQ(IrOpcode::kHeapConstant, r->opcode());
588     }
589 
590     CHECK_EQ(n, add->InputAt(0));
591     CHECK_EQ(r, add->InputAt(1));
592     R.CheckEffectInput(R.start(), effect_use);
593   }
594 }
595 
TEST(StringComparison)596 TEST(StringComparison) {
597   JSTypedLoweringTester R;
598   FeedbackSource feedback_source = FeedbackSourceWithOneCompareSlot(&R);
599 
600   const Operator* ops[] = {R.javascript.LessThan(feedback_source),
601                            R.simplified.StringLessThan(),
602                            R.javascript.LessThanOrEqual(feedback_source),
603                            R.simplified.StringLessThanOrEqual(),
604                            R.javascript.GreaterThan(feedback_source),
605                            R.simplified.StringLessThan(),
606                            R.javascript.GreaterThanOrEqual(feedback_source),
607                            R.simplified.StringLessThanOrEqual()};
608 
609   for (size_t i = 0; i < arraysize(kStringTypes); i++) {
610     Node* p0 = R.Parameter(kStringTypes[i], 0);
611     for (size_t j = 0; j < arraysize(kStringTypes); j++) {
612       Node* p1 = R.Parameter(kStringTypes[j], 1);
613 
614       for (size_t k = 0; k < arraysize(ops); k += 2) {
615         Node* cmp = R.Binop(ops[k], p0, p1);
616         Node* r = R.reduce(cmp);
617 
618         R.CheckBinop(ops[k + 1], r);
619         if (k >= 4) {
620           // GreaterThan and GreaterThanOrEqual commute the inputs
621           // and use the LessThan and LessThanOrEqual operators.
622           CHECK_EQ(p1, r->InputAt(0));
623           CHECK_EQ(p0, r->InputAt(1));
624         } else {
625           CHECK_EQ(p0, r->InputAt(0));
626           CHECK_EQ(p1, r->InputAt(1));
627         }
628       }
629     }
630   }
631 }
632 
633 
CheckIsConvertedToNumber(Node * val,Node * converted)634 static void CheckIsConvertedToNumber(Node* val, Node* converted) {
635   if (NodeProperties::GetType(val).Is(Type::Number())) {
636     CHECK_EQ(val, converted);
637   } else {
638     if (converted->opcode() == IrOpcode::kNumberConstant) return;
639     CHECK(IrOpcode::kJSToNumber == converted->opcode() ||
640           IrOpcode::kJSToNumberConvertBigInt == converted->opcode());
641     CHECK_EQ(val, converted->InputAt(0));
642   }
643 }
644 
TEST(NumberComparison)645 TEST(NumberComparison) {
646   JSTypedLoweringTester R;
647   FeedbackSource feedback_source = FeedbackSourceWithOneCompareSlot(&R);
648 
649   const Operator* ops[] = {R.javascript.LessThan(feedback_source),
650                            R.simplified.NumberLessThan(),
651                            R.javascript.LessThanOrEqual(feedback_source),
652                            R.simplified.NumberLessThanOrEqual(),
653                            R.javascript.GreaterThan(feedback_source),
654                            R.simplified.NumberLessThan(),
655                            R.javascript.GreaterThanOrEqual(feedback_source),
656                            R.simplified.NumberLessThanOrEqual()};
657 
658   Node* const p0 = R.Parameter(Type::Number(), 0);
659   Node* const p1 = R.Parameter(Type::Number(), 1);
660 
661   for (size_t k = 0; k < arraysize(ops); k += 2) {
662     Node* cmp = R.Binop(ops[k], p0, p1);
663     Node* r = R.reduce(cmp);
664 
665     R.CheckBinop(ops[k + 1], r);
666     if (k >= 4) {
667       // GreaterThan and GreaterThanOrEqual commute the inputs
668       // and use the LessThan and LessThanOrEqual operators.
669       CheckIsConvertedToNumber(p1, r->InputAt(0));
670       CheckIsConvertedToNumber(p0, r->InputAt(1));
671     } else {
672       CheckIsConvertedToNumber(p0, r->InputAt(0));
673       CheckIsConvertedToNumber(p1, r->InputAt(1));
674     }
675   }
676 }
677 
TEST(MixedComparison1)678 TEST(MixedComparison1) {
679   JSTypedLoweringTester R;
680   FeedbackSource feedback_source = FeedbackSourceWithOneCompareSlot(&R);
681 
682   Type types[] = {Type::Number(), Type::String(),
683                   Type::Union(Type::Number(), Type::String(), R.main_zone())};
684 
685   for (size_t i = 0; i < arraysize(types); i++) {
686     Node* p0 = R.Parameter(types[i], 0);
687 
688     for (size_t j = 0; j < arraysize(types); j++) {
689       Node* p1 = R.Parameter(types[j], 1);
690       {
691         const Operator* less_than = R.javascript.LessThan(feedback_source);
692         Node* cmp = R.Binop(less_than, p0, p1);
693         Node* r = R.reduce(cmp);
694         if (types[i].Is(Type::String()) && types[j].Is(Type::String())) {
695           R.CheckBinop(R.simplified.StringLessThan(), r);
696         } else if ((types[i].Is(Type::Number()) &&
697                     types[j].Is(Type::Number())) ||
698                    (!types[i].Maybe(Type::String()) ||
699                     !types[j].Maybe(Type::String()))) {
700           R.CheckBinop(R.simplified.NumberLessThan(), r);
701         } else {
702           // No reduction of mixed types.
703           CHECK_EQ(r->op(), less_than);
704         }
705       }
706     }
707   }
708 }
709 
TEST(RemoveToNumberEffects)710 TEST(RemoveToNumberEffects) {
711   JSTypedLoweringTester R;
712 
713   FeedbackSource feedback_source = FeedbackSourceWithOneBinarySlot(&R);
714   Node* feedback = R.UndefinedConstant();
715   Node* effect_use = nullptr;
716   Node* zero = R.graph.NewNode(R.common.NumberConstant(0));
717   for (int i = 0; i < 10; i++) {
718     Node* p0 = R.Parameter(Type::Number());
719     Node* ton = R.Unop(R.javascript.ToNumber(), p0);
720     Node* frame_state = R.EmptyFrameState(R.context());
721     effect_use = nullptr;
722 
723     switch (i) {
724       case 0:
725         CHECK_EQ(1, OperatorProperties::GetFrameStateInputCount(
726                         R.javascript.ToNumber()));
727         effect_use = R.graph.NewNode(R.javascript.ToNumber(), p0, R.context(),
728                                      frame_state, ton, R.start());
729         break;
730       case 1:
731         CHECK_EQ(1, OperatorProperties::GetFrameStateInputCount(
732                         R.javascript.ToNumber()));
733         effect_use = R.graph.NewNode(R.javascript.ToNumber(), ton, R.context(),
734                                      frame_state, ton, R.start());
735         break;
736       case 2:
737         effect_use = R.graph.NewNode(R.common.EffectPhi(1), ton, R.start());
738         break;
739       case 3:
740         effect_use =
741             R.graph.NewNode(R.javascript.Add(feedback_source), ton, ton,
742                             feedback, R.context(), frame_state, ton, R.start());
743         break;
744       case 4:
745         effect_use =
746             R.graph.NewNode(R.javascript.Add(feedback_source), p0, p0, feedback,
747                             R.context(), frame_state, ton, R.start());
748         break;
749       case 5:
750         effect_use =
751             R.graph.NewNode(R.common.Return(), zero, p0, ton, R.start());
752         break;
753       case 6:
754         effect_use =
755             R.graph.NewNode(R.common.Return(), zero, ton, ton, R.start());
756     }
757 
758     R.CheckEffectInput(R.start(), ton);
759     if (effect_use != nullptr) R.CheckEffectInput(ton, effect_use);
760 
761     Node* r = R.reduce(ton);
762     CHECK_EQ(p0, r);
763     CHECK_NE(R.start(), r);
764 
765     if (effect_use != nullptr) {
766       R.CheckEffectInput(R.start(), effect_use);
767       // Check that value uses of ToNumber() do not go to start().
768       for (int j = 0; j < effect_use->op()->ValueInputCount(); j++) {
769         CHECK_NE(R.start(), effect_use->InputAt(j));
770       }
771     }
772   }
773 
774   CHECK(!effect_use);  // should have done all cases above.
775 }
776 
777 
778 // Helper class for testing the reduction of a single binop.
779 class BinopEffectsTester {
780  public:
BinopEffectsTester(const Operator * op,Type t0,Type t1)781   BinopEffectsTester(const Operator* op, Type t0, Type t1)
782       : R(0),
783         p0(R.Parameter(t0, 0)),
784         p1(R.Parameter(t1, 1)),
785         binop(R.Binop(op, p0, p1)),
786         effect_use(R.graph.NewNode(R.common.EffectPhi(1), binop, R.start())) {
787     // Effects should be ordered start -> binop -> effect_use
788     R.CheckEffectInput(R.start(), binop);
789     R.CheckEffectInput(binop, effect_use);
790     result = R.reduce(binop);
791   }
792 
793   JSTypedLoweringTester R;
794   Node* p0;
795   Node* p1;
796   Node* binop;
797   Node* effect_use;
798   Node* result;
799 
CheckEffectsRemoved()800   void CheckEffectsRemoved() { R.CheckEffectInput(R.start(), effect_use); }
801 
CheckEffectOrdering(Node * n0)802   void CheckEffectOrdering(Node* n0) {
803     R.CheckEffectInput(R.start(), n0);
804     R.CheckEffectInput(n0, effect_use);
805   }
806 
CheckEffectOrdering(Node * n0,Node * n1)807   void CheckEffectOrdering(Node* n0, Node* n1) {
808     R.CheckEffectInput(R.start(), n0);
809     R.CheckEffectInput(n0, n1);
810     R.CheckEffectInput(n1, effect_use);
811   }
812 
CheckConvertedInput(IrOpcode::Value opcode,int which,bool effects)813   Node* CheckConvertedInput(IrOpcode::Value opcode, int which, bool effects) {
814     return CheckConverted(opcode, result->InputAt(which), effects);
815   }
816 
CheckConverted(IrOpcode::Value opcode,Node * node,bool effects)817   Node* CheckConverted(IrOpcode::Value opcode, Node* node, bool effects) {
818     CHECK_EQ(opcode, node->opcode());
819     if (effects) {
820       CHECK_LT(0, node->op()->EffectInputCount());
821     } else {
822       CHECK_EQ(0, node->op()->EffectInputCount());
823     }
824     return node;
825   }
826 
CheckNoOp(int which)827   Node* CheckNoOp(int which) {
828     CHECK_EQ(which == 0 ? p0 : p1, result->InputAt(which));
829     return result->InputAt(which);
830   }
831 };
832 
833 
834 // Helper function for strict and non-strict equality reductions.
CheckEqualityReduction(JSTypedLoweringTester * R,bool strict,Node * l,Node * r,IrOpcode::Value expected)835 void CheckEqualityReduction(JSTypedLoweringTester* R, bool strict, Node* l,
836                             Node* r, IrOpcode::Value expected) {
837   FeedbackSource feedback_source = FeedbackSourceWithOneCompareSlot(R);
838   for (int j = 0; j < 2; j++) {
839     Node* p0 = j == 0 ? l : r;
840     Node* p1 = j == 1 ? l : r;
841 
842     {
843       const Operator* op = strict ? R->javascript.StrictEqual(feedback_source)
844                                   : R->javascript.Equal(feedback_source);
845       Node* eq = R->Binop(op, p0, p1);
846       Node* reduced = R->reduce(eq);
847       R->CheckBinop(expected, reduced);
848     }
849   }
850 }
851 
852 
TEST(EqualityForNumbers)853 TEST(EqualityForNumbers) {
854   JSTypedLoweringTester R;
855 
856   Type simple_number_types[] = {Type::UnsignedSmall(), Type::SignedSmall(),
857                                 Type::Signed32(), Type::Unsigned32(),
858                                 Type::Number()};
859 
860   for (size_t i = 0; i < arraysize(simple_number_types); ++i) {
861     Node* p0 = R.Parameter(simple_number_types[i], 0);
862 
863     for (size_t j = 0; j < arraysize(simple_number_types); ++j) {
864       Node* p1 = R.Parameter(simple_number_types[j], 1);
865 
866       CheckEqualityReduction(&R, true, p0, p1, IrOpcode::kNumberEqual);
867       CheckEqualityReduction(&R, false, p0, p1, IrOpcode::kNumberEqual);
868     }
869   }
870 }
871 
872 
TEST(StrictEqualityForRefEqualTypes)873 TEST(StrictEqualityForRefEqualTypes) {
874   JSTypedLoweringTester R;
875 
876   Type types[] = {Type::Undefined(), Type::Null(), Type::Boolean(),
877                   Type::Object(), Type::Receiver()};
878 
879   Node* p0 = R.Parameter(Type::Any());
880   for (size_t i = 0; i < arraysize(types); i++) {
881     Node* p1 = R.Parameter(types[i]);
882     CheckEqualityReduction(&R, true, p0, p1, IrOpcode::kReferenceEqual);
883   }
884 }
885 
TEST(StrictEqualityForUnique)886 TEST(StrictEqualityForUnique) {
887   JSTypedLoweringTester R;
888 
889   Node* p0 = R.Parameter(Type::Unique());
890   Node* p1 = R.Parameter(Type::Unique());
891   CheckEqualityReduction(&R, true, p0, p1, IrOpcode::kReferenceEqual);
892   CheckEqualityReduction(&R, true, p1, p0, IrOpcode::kReferenceEqual);
893 }
894 
TEST(StringEquality)895 TEST(StringEquality) {
896   JSTypedLoweringTester R;
897   Node* p0 = R.Parameter(Type::String());
898   Node* p1 = R.Parameter(Type::String());
899 
900   CheckEqualityReduction(&R, true, p0, p1, IrOpcode::kStringEqual);
901   CheckEqualityReduction(&R, false, p0, p1, IrOpcode::kStringEqual);
902 }
903 
TEST(RemovePureNumberBinopEffects)904 TEST(RemovePureNumberBinopEffects) {
905   JSTypedLoweringTester R;
906   FeedbackSource binary_source = FeedbackSourceWithOneBinarySlot(&R);
907   FeedbackSource compare_source = FeedbackSourceWithOneCompareSlot(&R);
908 
909   const Operator* ops[] = {
910       R.javascript.Equal(compare_source),
911       R.simplified.NumberEqual(),
912       R.javascript.Add(binary_source),
913       R.simplified.NumberAdd(),
914       R.javascript.Subtract(binary_source),
915       R.simplified.NumberSubtract(),
916       R.javascript.Multiply(binary_source),
917       R.simplified.NumberMultiply(),
918       R.javascript.Divide(binary_source),
919       R.simplified.NumberDivide(),
920       R.javascript.Modulus(binary_source),
921       R.simplified.NumberModulus(),
922       R.javascript.LessThan(compare_source),
923       R.simplified.NumberLessThan(),
924       R.javascript.LessThanOrEqual(compare_source),
925       R.simplified.NumberLessThanOrEqual(),
926   };
927 
928   for (size_t j = 0; j < arraysize(ops); j += 2) {
929     BinopEffectsTester B(ops[j], Type::Number(), Type::Number());
930     CHECK_EQ(ops[j + 1]->opcode(), B.result->op()->opcode());
931 
932     B.R.CheckBinop(B.result->opcode(), B.result);
933 
934     B.CheckNoOp(0);
935     B.CheckNoOp(1);
936 
937     B.CheckEffectsRemoved();
938   }
939 }
940 
TEST(Int32BinopEffects)941 TEST(Int32BinopEffects) {
942   JSBitwiseTypedLoweringTester R;
943   for (int j = 0; j < R.kNumberOps; j += 2) {
944     bool signed_left = R.signedness[j], signed_right = R.signedness[j + 1];
945     BinopEffectsTester B(R.ops[j], I32Type(signed_left), I32Type(signed_right));
946     CHECK_EQ(R.ops[j + 1]->opcode(), B.result->op()->opcode());
947 
948     B.R.CheckBinop(B.result->opcode(), B.result);
949 
950     B.CheckNoOp(0);
951     B.CheckNoOp(1);
952 
953     B.CheckEffectsRemoved();
954   }
955 
956   for (int j = 0; j < R.kNumberOps; j += 2) {
957     bool signed_left = R.signedness[j], signed_right = R.signedness[j + 1];
958     BinopEffectsTester B(R.ops[j], Type::Number(), Type::Number());
959     CHECK_EQ(R.ops[j + 1]->opcode(), B.result->op()->opcode());
960 
961     B.R.CheckBinop(B.result->opcode(), B.result);
962 
963     B.CheckConvertedInput(NumberToI32(signed_left), 0, false);
964     B.CheckConvertedInput(NumberToI32(signed_right), 1, false);
965 
966     B.CheckEffectsRemoved();
967   }
968 
969   for (int j = 0; j < R.kNumberOps; j += 2) {
970     bool signed_left = R.signedness[j];
971     BinopEffectsTester B(R.ops[j], Type::Number(), Type::Boolean());
972 
973     B.R.CheckBinop(B.result->opcode(), B.result);
974 
975     B.CheckConvertedInput(NumberToI32(signed_left), 0, false);
976     B.CheckConvertedInput(IrOpcode::kPlainPrimitiveToNumber, 1, false);
977 
978     B.CheckEffectsRemoved();
979   }
980 
981   for (int j = 0; j < R.kNumberOps; j += 2) {
982     bool signed_right = R.signedness[j + 1];
983     BinopEffectsTester B(R.ops[j], Type::Boolean(), Type::Number());
984 
985     B.R.CheckBinop(B.result->opcode(), B.result);
986 
987     B.CheckConvertedInput(IrOpcode::kPlainPrimitiveToNumber, 0, false);
988     B.CheckConvertedInput(NumberToI32(signed_right), 1, false);
989 
990     B.CheckEffectsRemoved();
991   }
992 
993   for (int j = 0; j < R.kNumberOps; j += 2) {
994     BinopEffectsTester B(R.ops[j], Type::Boolean(), Type::Boolean());
995 
996     B.R.CheckBinop(B.result->opcode(), B.result);
997 
998     B.CheckConvertedInput(IrOpcode::kPlainPrimitiveToNumber, 0, false);
999     B.CheckConvertedInput(IrOpcode::kPlainPrimitiveToNumber, 1, false);
1000 
1001     B.CheckEffectsRemoved();
1002   }
1003 }
1004 
TEST(Int32AddNarrowing)1005 TEST(Int32AddNarrowing) {
1006   {
1007     JSBitwiseTypedLoweringTester R;
1008 
1009     for (int o = 0; o < R.kNumberOps; o += 2) {
1010       for (size_t i = 0; i < arraysize(kInt32Types); i++) {
1011         Node* n0 = R.Parameter(kInt32Types[i]);
1012         for (size_t j = 0; j < arraysize(kInt32Types); j++) {
1013           Node* n1 = R.Parameter(kInt32Types[j]);
1014           Node* one = R.graph.NewNode(R.common.NumberConstant(1));
1015 
1016           for (int l = 0; l < 2; l++) {
1017             Node* add_node = R.Binop(R.simplified.NumberAdd(), n0, n1);
1018             Node* or_node =
1019                 R.Binop(R.ops[o], l ? add_node : one, l ? one : add_node);
1020             Node* r = R.reduce(or_node);
1021 
1022             CHECK_EQ(R.ops[o + 1]->opcode(), r->op()->opcode());
1023             CHECK_EQ(IrOpcode::kNumberAdd, add_node->opcode());
1024           }
1025         }
1026       }
1027     }
1028   }
1029   {
1030     JSBitwiseShiftTypedLoweringTester R;
1031 
1032     for (int o = 0; o < R.kNumberOps; o += 2) {
1033       for (size_t i = 0; i < arraysize(kInt32Types); i++) {
1034         Node* n0 = R.Parameter(kInt32Types[i]);
1035         for (size_t j = 0; j < arraysize(kInt32Types); j++) {
1036           Node* n1 = R.Parameter(kInt32Types[j]);
1037           Node* one = R.graph.NewNode(R.common.NumberConstant(1));
1038 
1039           for (int l = 0; l < 2; l++) {
1040             Node* add_node = R.Binop(R.simplified.NumberAdd(), n0, n1);
1041             Node* or_node =
1042                 R.Binop(R.ops[o], l ? add_node : one, l ? one : add_node);
1043             Node* r = R.reduce(or_node);
1044 
1045             CHECK_EQ(R.ops[o + 1]->opcode(), r->op()->opcode());
1046             CHECK_EQ(IrOpcode::kNumberAdd, add_node->opcode());
1047           }
1048         }
1049       }
1050     }
1051   }
1052   {
1053     JSBitwiseTypedLoweringTester R;
1054 
1055     for (int o = 0; o < R.kNumberOps; o += 2) {
1056       Node* n0 = R.Parameter(I32Type(R.signedness[o]));
1057       Node* n1 = R.Parameter(I32Type(R.signedness[o + 1]));
1058       Node* one = R.graph.NewNode(R.common.NumberConstant(1));
1059 
1060       Node* add_node = R.Binop(R.simplified.NumberAdd(), n0, n1);
1061       Node* or_node = R.Binop(R.ops[o], add_node, one);
1062       Node* other_use = R.Binop(R.simplified.NumberAdd(), add_node, one);
1063       Node* r = R.reduce(or_node);
1064       CHECK_EQ(R.ops[o + 1]->opcode(), r->op()->opcode());
1065       CHECK_EQ(IrOpcode::kNumberAdd, add_node->opcode());
1066       // Conversion to int32 should be done.
1067       CheckToI32(add_node, r->InputAt(0), R.signedness[o]);
1068       CheckToI32(one, r->InputAt(1), R.signedness[o + 1]);
1069       // The other use should also not be touched.
1070       CHECK_EQ(add_node, other_use->InputAt(0));
1071       CHECK_EQ(one, other_use->InputAt(1));
1072     }
1073   }
1074 }
1075 
TEST(Int32Comparisons)1076 TEST(Int32Comparisons) {
1077   JSTypedLoweringTester R;
1078   FeedbackSource feedback_source = FeedbackSourceWithOneCompareSlot(&R);
1079 
1080   struct Entry {
1081     const Operator* js_op;
1082     const Operator* num_op;
1083     bool commute;
1084   };
1085 
1086   Entry ops[] = {{R.javascript.LessThan(feedback_source),
1087                   R.simplified.NumberLessThan(), false},
1088                  {R.javascript.LessThanOrEqual(feedback_source),
1089                   R.simplified.NumberLessThanOrEqual(), false},
1090                  {R.javascript.GreaterThan(feedback_source),
1091                   R.simplified.NumberLessThan(), true},
1092                  {R.javascript.GreaterThanOrEqual(feedback_source),
1093                   R.simplified.NumberLessThanOrEqual(), true}};
1094 
1095   for (size_t o = 0; o < arraysize(ops); o++) {
1096     for (size_t i = 0; i < arraysize(kNumberTypes); i++) {
1097       Type t0 = kNumberTypes[i];
1098       Node* p0 = R.Parameter(t0, 0);
1099 
1100       for (size_t j = 0; j < arraysize(kNumberTypes); j++) {
1101         Type t1 = kNumberTypes[j];
1102         Node* p1 = R.Parameter(t1, 1);
1103 
1104         Node* cmp = R.Binop(ops[o].js_op, p0, p1);
1105         Node* r = R.reduce(cmp);
1106 
1107         R.CheckBinop(ops[o].num_op, r);
1108         if (ops[o].commute) {
1109           CHECK_EQ(p1, r->InputAt(0));
1110           CHECK_EQ(p0, r->InputAt(1));
1111         } else {
1112           CHECK_EQ(p0, r->InputAt(0));
1113           CHECK_EQ(p1, r->InputAt(1));
1114         }
1115       }
1116     }
1117   }
1118 }
1119 
1120 }  // namespace compiler
1121 }  // namespace internal
1122 }  // namespace v8
1123