Home | History | Annotate | Download | only in compiler 
      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/compiler/js-builtin-reducer.h"
      6 #include "src/compiler/js-graph.h"
      7 #include "src/compiler/node-matchers.h"
      8 #include "src/compiler/node-properties.h"
      9 #include "src/compiler/simplified-operator.h"
     10 #include "src/objects-inl.h"
     11 #include "src/type-cache.h"
     12 #include "src/types.h"
     13 
     14 namespace v8 {
     15 namespace internal {
     16 namespace compiler {
     17 
     18 
     19 // Helper class to access JSCallFunction nodes that are potential candidates
     20 // for reduction when they have a BuiltinFunctionId associated with them.
     21 class JSCallReduction {
     22  public:
     23   explicit JSCallReduction(Node* node) : node_(node) {}
     24 
     25   // Determines whether the node is a JSCallFunction operation that targets a
     26   // constant callee being a well-known builtin with a BuiltinFunctionId.
     27   bool HasBuiltinFunctionId() {
     28     if (node_->opcode() != IrOpcode::kJSCallFunction) return false;
     29     HeapObjectMatcher m(NodeProperties::GetValueInput(node_, 0));
     30     if (!m.HasValue() || !m.Value()->IsJSFunction()) return false;
     31     Handle<JSFunction> function = Handle<JSFunction>::cast(m.Value());
     32     return function->shared()->HasBuiltinFunctionId();
     33   }
     34 
     35   // Retrieves the BuiltinFunctionId as described above.
     36   BuiltinFunctionId GetBuiltinFunctionId() {
     37     DCHECK_EQ(IrOpcode::kJSCallFunction, node_->opcode());
     38     HeapObjectMatcher m(NodeProperties::GetValueInput(node_, 0));
     39     Handle<JSFunction> function = Handle<JSFunction>::cast(m.Value());
     40     return function->shared()->builtin_function_id();
     41   }
     42 
     43   // Determines whether the call takes zero inputs.
     44   bool InputsMatchZero() { return GetJSCallArity() == 0; }
     45 
     46   // Determines whether the call takes one input of the given type.
     47   bool InputsMatchOne(Type* t1) {
     48     return GetJSCallArity() == 1 &&
     49            NodeProperties::GetType(GetJSCallInput(0))->Is(t1);
     50   }
     51 
     52   // Determines whether the call takes two inputs of the given types.
     53   bool InputsMatchTwo(Type* t1, Type* t2) {
     54     return GetJSCallArity() == 2 &&
     55            NodeProperties::GetType(GetJSCallInput(0))->Is(t1) &&
     56            NodeProperties::GetType(GetJSCallInput(1))->Is(t2);
     57   }
     58 
     59   // Determines whether the call takes inputs all of the given type.
     60   bool InputsMatchAll(Type* t) {
     61     for (int i = 0; i < GetJSCallArity(); i++) {
     62       if (!NodeProperties::GetType(GetJSCallInput(i))->Is(t)) {
     63         return false;
     64       }
     65     }
     66     return true;
     67   }
     68 
     69   Node* left() { return GetJSCallInput(0); }
     70   Node* right() { return GetJSCallInput(1); }
     71 
     72   int GetJSCallArity() {
     73     DCHECK_EQ(IrOpcode::kJSCallFunction, node_->opcode());
     74     // Skip first (i.e. callee) and second (i.e. receiver) operand.
     75     return node_->op()->ValueInputCount() - 2;
     76   }
     77 
     78   Node* GetJSCallInput(int index) {
     79     DCHECK_EQ(IrOpcode::kJSCallFunction, node_->opcode());
     80     DCHECK_LT(index, GetJSCallArity());
     81     // Skip first (i.e. callee) and second (i.e. receiver) operand.
     82     return NodeProperties::GetValueInput(node_, index + 2);
     83   }
     84 
     85  private:
     86   Node* node_;
     87 };
     88 
     89 JSBuiltinReducer::JSBuiltinReducer(Editor* editor, JSGraph* jsgraph)
     90     : AdvancedReducer(editor),
     91       jsgraph_(jsgraph),
     92       type_cache_(TypeCache::Get()) {}
     93 
     94 // ES6 section 20.2.2.1 Math.abs ( x )
     95 Reduction JSBuiltinReducer::ReduceMathAbs(Node* node) {
     96   JSCallReduction r(node);
     97   if (r.InputsMatchOne(Type::PlainPrimitive())) {
     98     // Math.abs(a:plain-primitive) -> NumberAbs(ToNumber(a))
     99     Node* input = ToNumber(r.GetJSCallInput(0));
    100     Node* value = graph()->NewNode(simplified()->NumberAbs(), input);
    101     return Replace(value);
    102   }
    103   return NoChange();
    104 }
    105 
    106 // ES6 section 20.2.2.6 Math.atan ( x )
    107 Reduction JSBuiltinReducer::ReduceMathAtan(Node* node) {
    108   JSCallReduction r(node);
    109   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    110     // Math.atan(a:plain-primitive) -> NumberAtan(ToNumber(a))
    111     Node* input = ToNumber(r.GetJSCallInput(0));
    112     Node* value = graph()->NewNode(simplified()->NumberAtan(), input);
    113     return Replace(value);
    114   }
    115   return NoChange();
    116 }
    117 
    118 // ES6 section 20.2.2.8 Math.atan2 ( y, x )
    119 Reduction JSBuiltinReducer::ReduceMathAtan2(Node* node) {
    120   JSCallReduction r(node);
    121   if (r.InputsMatchTwo(Type::PlainPrimitive(), Type::PlainPrimitive())) {
    122     // Math.atan2(a:plain-primitive,
    123     //            b:plain-primitive) -> NumberAtan2(ToNumber(a),
    124     //                                              ToNumber(b))
    125     Node* left = ToNumber(r.left());
    126     Node* right = ToNumber(r.right());
    127     Node* value = graph()->NewNode(simplified()->NumberAtan2(), left, right);
    128     return Replace(value);
    129   }
    130   return NoChange();
    131 }
    132 
    133 // ES6 section 20.2.2.7 Math.atanh ( x )
    134 Reduction JSBuiltinReducer::ReduceMathAtanh(Node* node) {
    135   JSCallReduction r(node);
    136   if (r.InputsMatchOne(Type::Number())) {
    137     // Math.atanh(a:number) -> NumberAtanh(a)
    138     Node* value = graph()->NewNode(simplified()->NumberAtanh(), r.left());
    139     return Replace(value);
    140   }
    141   return NoChange();
    142 }
    143 
    144 // ES6 section 20.2.2.10 Math.ceil ( x )
    145 Reduction JSBuiltinReducer::ReduceMathCeil(Node* node) {
    146   JSCallReduction r(node);
    147   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    148     // Math.ceil(a:plain-primitive) -> NumberCeil(ToNumber(a))
    149     Node* input = ToNumber(r.GetJSCallInput(0));
    150     Node* value = graph()->NewNode(simplified()->NumberCeil(), input);
    151     return Replace(value);
    152   }
    153   return NoChange();
    154 }
    155 
    156 // ES6 section 20.2.2.11 Math.clz32 ( x )
    157 Reduction JSBuiltinReducer::ReduceMathClz32(Node* node) {
    158   JSCallReduction r(node);
    159   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    160     // Math.clz32(a:plain-primitive) -> NumberClz32(ToUint32(a))
    161     Node* input = ToUint32(r.GetJSCallInput(0));
    162     Node* value = graph()->NewNode(simplified()->NumberClz32(), input);
    163     return Replace(value);
    164   }
    165   return NoChange();
    166 }
    167 
    168 // ES6 section 20.2.2.12 Math.cos ( x )
    169 Reduction JSBuiltinReducer::ReduceMathCos(Node* node) {
    170   JSCallReduction r(node);
    171   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    172     // Math.cos(a:plain-primitive) -> NumberCos(ToNumber(a))
    173     Node* input = ToNumber(r.GetJSCallInput(0));
    174     Node* value = graph()->NewNode(simplified()->NumberCos(), input);
    175     return Replace(value);
    176   }
    177   return NoChange();
    178 }
    179 
    180 // ES6 section 20.2.2.14 Math.exp ( x )
    181 Reduction JSBuiltinReducer::ReduceMathExp(Node* node) {
    182   JSCallReduction r(node);
    183   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    184     // Math.exp(a:plain-primitive) -> NumberExp(ToNumber(a))
    185     Node* input = ToNumber(r.GetJSCallInput(0));
    186     Node* value = graph()->NewNode(simplified()->NumberExp(), input);
    187     return Replace(value);
    188   }
    189   return NoChange();
    190 }
    191 
    192 // ES6 section 20.2.2.15 Math.expm1 ( x )
    193 Reduction JSBuiltinReducer::ReduceMathExpm1(Node* node) {
    194   JSCallReduction r(node);
    195   if (r.InputsMatchOne(Type::Number())) {
    196     // Math.expm1(a:number) -> NumberExpm1(a)
    197     Node* value = graph()->NewNode(simplified()->NumberExpm1(), r.left());
    198     return Replace(value);
    199   }
    200   return NoChange();
    201 }
    202 
    203 // ES6 section 20.2.2.16 Math.floor ( x )
    204 Reduction JSBuiltinReducer::ReduceMathFloor(Node* node) {
    205   JSCallReduction r(node);
    206   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    207     // Math.floor(a:plain-primitive) -> NumberFloor(ToNumber(a))
    208     Node* input = ToNumber(r.GetJSCallInput(0));
    209     Node* value = graph()->NewNode(simplified()->NumberFloor(), input);
    210     return Replace(value);
    211   }
    212   return NoChange();
    213 }
    214 
    215 // ES6 section 20.2.2.17 Math.fround ( x )
    216 Reduction JSBuiltinReducer::ReduceMathFround(Node* node) {
    217   JSCallReduction r(node);
    218   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    219     // Math.fround(a:plain-primitive) -> NumberFround(ToNumber(a))
    220     Node* input = ToNumber(r.GetJSCallInput(0));
    221     Node* value = graph()->NewNode(simplified()->NumberFround(), input);
    222     return Replace(value);
    223   }
    224   return NoChange();
    225 }
    226 
    227 // ES6 section 20.2.2.19 Math.imul ( x, y )
    228 Reduction JSBuiltinReducer::ReduceMathImul(Node* node) {
    229   JSCallReduction r(node);
    230   if (r.InputsMatchTwo(Type::PlainPrimitive(), Type::PlainPrimitive())) {
    231     // Math.imul(a:plain-primitive,
    232     //           b:plain-primitive) -> NumberImul(ToUint32(a),
    233     //                                            ToUint32(b))
    234     Node* left = ToUint32(r.left());
    235     Node* right = ToUint32(r.right());
    236     Node* value = graph()->NewNode(simplified()->NumberImul(), left, right);
    237     return Replace(value);
    238   }
    239   return NoChange();
    240 }
    241 
    242 // ES6 section 20.2.2.20 Math.log ( x )
    243 Reduction JSBuiltinReducer::ReduceMathLog(Node* node) {
    244   JSCallReduction r(node);
    245   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    246     // Math.log(a:plain-primitive) -> NumberLog(ToNumber(a))
    247     Node* input = ToNumber(r.GetJSCallInput(0));
    248     Node* value = graph()->NewNode(simplified()->NumberLog(), input);
    249     return Replace(value);
    250   }
    251   return NoChange();
    252 }
    253 
    254 // ES6 section 20.2.2.21 Math.log1p ( x )
    255 Reduction JSBuiltinReducer::ReduceMathLog1p(Node* node) {
    256   JSCallReduction r(node);
    257   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    258     // Math.log1p(a:plain-primitive) -> NumberLog1p(ToNumber(a))
    259     Node* input = ToNumber(r.GetJSCallInput(0));
    260     Node* value = graph()->NewNode(simplified()->NumberLog1p(), input);
    261     return Replace(value);
    262   }
    263   return NoChange();
    264 }
    265 
    266 // ES6 section 20.2.2.22 Math.log10 ( x )
    267 Reduction JSBuiltinReducer::ReduceMathLog10(Node* node) {
    268   JSCallReduction r(node);
    269   if (r.InputsMatchOne(Type::Number())) {
    270     // Math.log10(a:number) -> NumberLog10(a)
    271     Node* value = graph()->NewNode(simplified()->NumberLog10(), r.left());
    272     return Replace(value);
    273   }
    274   return NoChange();
    275 }
    276 
    277 // ES6 section 20.2.2.23 Math.log2 ( x )
    278 Reduction JSBuiltinReducer::ReduceMathLog2(Node* node) {
    279   JSCallReduction r(node);
    280   if (r.InputsMatchOne(Type::Number())) {
    281     // Math.log2(a:number) -> NumberLog(a)
    282     Node* value = graph()->NewNode(simplified()->NumberLog2(), r.left());
    283     return Replace(value);
    284   }
    285   return NoChange();
    286 }
    287 
    288 // ES6 section 20.2.2.24 Math.max ( value1, value2, ...values )
    289 Reduction JSBuiltinReducer::ReduceMathMax(Node* node) {
    290   JSCallReduction r(node);
    291   if (r.InputsMatchZero()) {
    292     // Math.max() -> -Infinity
    293     return Replace(jsgraph()->Constant(-V8_INFINITY));
    294   }
    295   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    296     // Math.max(a:plain-primitive) -> ToNumber(a)
    297     Node* value = ToNumber(r.GetJSCallInput(0));
    298     return Replace(value);
    299   }
    300   if (r.InputsMatchAll(Type::Integral32())) {
    301     // Math.max(a:int32, b:int32, ...)
    302     Node* value = r.GetJSCallInput(0);
    303     for (int i = 1; i < r.GetJSCallArity(); i++) {
    304       Node* const input = r.GetJSCallInput(i);
    305       value = graph()->NewNode(
    306           common()->Select(MachineRepresentation::kNone),
    307           graph()->NewNode(simplified()->NumberLessThan(), input, value), value,
    308           input);
    309     }
    310     return Replace(value);
    311   }
    312   return NoChange();
    313 }
    314 
    315 // ES6 section 20.2.2.25 Math.min ( value1, value2, ...values )
    316 Reduction JSBuiltinReducer::ReduceMathMin(Node* node) {
    317   JSCallReduction r(node);
    318   if (r.InputsMatchZero()) {
    319     // Math.min() -> Infinity
    320     return Replace(jsgraph()->Constant(V8_INFINITY));
    321   }
    322   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    323     // Math.min(a:plain-primitive) -> ToNumber(a)
    324     Node* value = ToNumber(r.GetJSCallInput(0));
    325     return Replace(value);
    326   }
    327   if (r.InputsMatchAll(Type::Integral32())) {
    328     // Math.min(a:int32, b:int32, ...)
    329     Node* value = r.GetJSCallInput(0);
    330     for (int i = 1; i < r.GetJSCallArity(); i++) {
    331       Node* const input = r.GetJSCallInput(i);
    332       value = graph()->NewNode(
    333           common()->Select(MachineRepresentation::kNone),
    334           graph()->NewNode(simplified()->NumberLessThan(), input, value), input,
    335           value);
    336     }
    337     return Replace(value);
    338   }
    339   return NoChange();
    340 }
    341 
    342 // ES6 section 20.2.2.28 Math.round ( x )
    343 Reduction JSBuiltinReducer::ReduceMathRound(Node* node) {
    344   JSCallReduction r(node);
    345   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    346     // Math.round(a:plain-primitive) -> NumberRound(ToNumber(a))
    347     Node* input = ToNumber(r.GetJSCallInput(0));
    348     Node* value = graph()->NewNode(simplified()->NumberRound(), input);
    349     return Replace(value);
    350   }
    351   return NoChange();
    352 }
    353 
    354 // ES6 section 20.2.2.9 Math.cbrt ( x )
    355 Reduction JSBuiltinReducer::ReduceMathCbrt(Node* node) {
    356   JSCallReduction r(node);
    357   if (r.InputsMatchOne(Type::Number())) {
    358     // Math.cbrt(a:number) -> NumberCbrt(a)
    359     Node* value = graph()->NewNode(simplified()->NumberCbrt(), r.left());
    360     return Replace(value);
    361   }
    362   return NoChange();
    363 }
    364 
    365 // ES6 section 20.2.2.30 Math.sin ( x )
    366 Reduction JSBuiltinReducer::ReduceMathSin(Node* node) {
    367   JSCallReduction r(node);
    368   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    369     // Math.sin(a:plain-primitive) -> NumberSin(ToNumber(a))
    370     Node* input = ToNumber(r.GetJSCallInput(0));
    371     Node* value = graph()->NewNode(simplified()->NumberSin(), input);
    372     return Replace(value);
    373   }
    374   return NoChange();
    375 }
    376 
    377 // ES6 section 20.2.2.32 Math.sqrt ( x )
    378 Reduction JSBuiltinReducer::ReduceMathSqrt(Node* node) {
    379   JSCallReduction r(node);
    380   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    381     // Math.sqrt(a:plain-primitive) -> NumberSqrt(ToNumber(a))
    382     Node* input = ToNumber(r.GetJSCallInput(0));
    383     Node* value = graph()->NewNode(simplified()->NumberSqrt(), input);
    384     return Replace(value);
    385   }
    386   return NoChange();
    387 }
    388 
    389 // ES6 section 20.2.2.33 Math.tan ( x )
    390 Reduction JSBuiltinReducer::ReduceMathTan(Node* node) {
    391   JSCallReduction r(node);
    392   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    393     // Math.tan(a:plain-primitive) -> NumberTan(ToNumber(a))
    394     Node* input = ToNumber(r.GetJSCallInput(0));
    395     Node* value = graph()->NewNode(simplified()->NumberTan(), input);
    396     return Replace(value);
    397   }
    398   return NoChange();
    399 }
    400 
    401 // ES6 section 20.2.2.35 Math.trunc ( x )
    402 Reduction JSBuiltinReducer::ReduceMathTrunc(Node* node) {
    403   JSCallReduction r(node);
    404   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    405     // Math.trunc(a:plain-primitive) -> NumberTrunc(ToNumber(a))
    406     Node* input = ToNumber(r.GetJSCallInput(0));
    407     Node* value = graph()->NewNode(simplified()->NumberTrunc(), input);
    408     return Replace(value);
    409   }
    410   return NoChange();
    411 }
    412 
    413 // ES6 section 21.1.2.1 String.fromCharCode ( ...codeUnits )
    414 Reduction JSBuiltinReducer::ReduceStringFromCharCode(Node* node) {
    415   JSCallReduction r(node);
    416   if (r.InputsMatchOne(Type::PlainPrimitive())) {
    417     // String.fromCharCode(a:plain-primitive) -> StringFromCharCode(a)
    418     Node* input = ToNumber(r.GetJSCallInput(0));
    419     Node* value = graph()->NewNode(simplified()->StringFromCharCode(), input);
    420     return Replace(value);
    421   }
    422   return NoChange();
    423 }
    424 
    425 Reduction JSBuiltinReducer::Reduce(Node* node) {
    426   Reduction reduction = NoChange();
    427   JSCallReduction r(node);
    428 
    429   // Dispatch according to the BuiltinFunctionId if present.
    430   if (!r.HasBuiltinFunctionId()) return NoChange();
    431   switch (r.GetBuiltinFunctionId()) {
    432     case kMathAbs:
    433       reduction = ReduceMathAbs(node);
    434       break;
    435     case kMathAtan:
    436       reduction = ReduceMathAtan(node);
    437       break;
    438     case kMathAtan2:
    439       reduction = ReduceMathAtan2(node);
    440       break;
    441     case kMathAtanh:
    442       reduction = ReduceMathAtanh(node);
    443       break;
    444     case kMathClz32:
    445       reduction = ReduceMathClz32(node);
    446       break;
    447     case kMathCeil:
    448       reduction = ReduceMathCeil(node);
    449       break;
    450     case kMathCos:
    451       reduction = ReduceMathCos(node);
    452       break;
    453     case kMathExp:
    454       reduction = ReduceMathExp(node);
    455       break;
    456     case kMathExpm1:
    457       reduction = ReduceMathExpm1(node);
    458       break;
    459     case kMathFloor:
    460       reduction = ReduceMathFloor(node);
    461       break;
    462     case kMathFround:
    463       reduction = ReduceMathFround(node);
    464       break;
    465     case kMathImul:
    466       reduction = ReduceMathImul(node);
    467       break;
    468     case kMathLog:
    469       reduction = ReduceMathLog(node);
    470       break;
    471     case kMathLog1p:
    472       reduction = ReduceMathLog1p(node);
    473       break;
    474     case kMathLog10:
    475       reduction = ReduceMathLog10(node);
    476       break;
    477     case kMathLog2:
    478       reduction = ReduceMathLog2(node);
    479       break;
    480     case kMathMax:
    481       reduction = ReduceMathMax(node);
    482       break;
    483     case kMathMin:
    484       reduction = ReduceMathMin(node);
    485       break;
    486     case kMathCbrt:
    487       reduction = ReduceMathCbrt(node);
    488       break;
    489     case kMathRound:
    490       reduction = ReduceMathRound(node);
    491       break;
    492     case kMathSin:
    493       reduction = ReduceMathSin(node);
    494       break;
    495     case kMathSqrt:
    496       reduction = ReduceMathSqrt(node);
    497       break;
    498     case kMathTan:
    499       reduction = ReduceMathTan(node);
    500       break;
    501     case kMathTrunc:
    502       reduction = ReduceMathTrunc(node);
    503       break;
    504     case kStringFromCharCode:
    505       reduction = ReduceStringFromCharCode(node);
    506       break;
    507     default:
    508       break;
    509   }
    510 
    511   // Replace builtin call assuming replacement nodes are pure values that don't
    512   // produce an effect. Replaces {node} with {reduction} and relaxes effects.
    513   if (reduction.Changed()) ReplaceWithValue(node, reduction.replacement());
    514 
    515   return reduction;
    516 }
    517 
    518 Node* JSBuiltinReducer::ToNumber(Node* input) {
    519   Type* input_type = NodeProperties::GetType(input);
    520   if (input_type->Is(Type::Number())) return input;
    521   return graph()->NewNode(simplified()->PlainPrimitiveToNumber(), input);
    522 }
    523 
    524 Node* JSBuiltinReducer::ToUint32(Node* input) {
    525   input = ToNumber(input);
    526   Type* input_type = NodeProperties::GetType(input);
    527   if (input_type->Is(Type::Unsigned32())) return input;
    528   return graph()->NewNode(simplified()->NumberToUint32(), input);
    529 }
    530 
    531 Graph* JSBuiltinReducer::graph() const { return jsgraph()->graph(); }
    532 
    533 
    534 Isolate* JSBuiltinReducer::isolate() const { return jsgraph()->isolate(); }
    535 
    536 
    537 CommonOperatorBuilder* JSBuiltinReducer::common() const {
    538   return jsgraph()->common();
    539 }
    540 
    541 
    542 SimplifiedOperatorBuilder* JSBuiltinReducer::simplified() const {
    543   return jsgraph()->simplified();
    544 }
    545 
    546 }  // namespace compiler
    547 }  // namespace internal
    548 }  // namespace v8
    549