Initial steps towards cleaning up integer arithmetic IR.

runtime/vm/intermediate_language.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
@@ skipping 284 matching lines @@
 
 
 bool MathMinMaxInstr::AttributesEqual(Instruction* other) const {
   MathMinMaxInstr* other_op = other->AsMathMinMax();
   ASSERT(other_op != NULL);
   return (op_kind() == other_op->op_kind()) &&
       (result_cid() == other_op->result_cid());
 }
 
 
-bool BinarySmiOpInstr::AttributesEqual(Instruction* other) const {
-  BinarySmiOpInstr* other_op = other->AsBinarySmiOp();
-  ASSERT(other_op != NULL);
+bool BinaryIntegerOpInstr::AttributesEqual(Instruction* other) const {
+  ASSERT(other->tag() == tag());
+  BinaryIntegerOpInstr* other_op = static_cast<BinaryIntegerOpInstr*>(other);

[srdjan, 2014/09/11 17:38:11]

other->AsBinary... ?

   return (op_kind() == other_op->op_kind()) &&
-      (overflow_ == other_op->overflow_) &&
-      (is_truncating_ == other_op->is_truncating_);
+      (can_overflow() == other_op->can_overflow()) &&
+      (is_truncating() == other_op->is_truncating());
 }
 
 
-bool BinaryInt32OpInstr::AttributesEqual(Instruction* other) const {
-  BinaryInt32OpInstr* other_op = other->AsBinaryInt32Op();
-  ASSERT(other_op != NULL);
-  return (op_kind() == other_op->op_kind()) &&
-      (overflow_ == other_op->overflow_) &&
-      (is_truncating_ == other_op->is_truncating_);
-}
-
-
 EffectSet LoadFieldInstr::Dependencies() const {
   return immutable_ ? EffectSet::None() : EffectSet::All();
 }
 
 
 bool LoadFieldInstr::AttributesEqual(Instruction* other) const {
   LoadFieldInstr* other_load = other->AsLoadField();
   ASSERT(other_load != NULL);
   if (field() != NULL) {
     return (other_load->field() != NULL) &&
@@ skipping 869 matching lines @@
       return false;
 
     case Token::kSHL:
       return true;
 
     case Token::kMOD: {
       UNREACHABLE();
     }
 
     default:
-      return overflow_;
+      return can_overflow();
   }
 }
 
 
 bool BinarySmiOpInstr::CanDeoptimize() const {
   if (FLAG_throw_on_javascript_int_overflow && (Smi::kBits > 32)) {
     // If Smi's are bigger than 32-bits, then the instruction could deoptimize
     // if the result is too big.
     return true;
   }
   switch (op_kind()) {
     case Token::kBIT_AND:
     case Token::kBIT_OR:
     case Token::kBIT_XOR:
       return false;
     case Token::kSHR: {
       // Can't deopt if shift-count is known positive.
       Range* right_range = this->right()->definition()->range();
       return (right_range == NULL) || !right_range->IsPositive();
     }
     case Token::kSHL: {
       Range* right_range = this->right()->definition()->range();
-      if ((right_range != NULL) && IsTruncating()) {
+      if ((right_range != NULL) && !can_overflow()) {
         // Can deoptimize if right can be negative.
         return !right_range->IsPositive();
       }
       return true;
     }
     case Token::kMOD: {
       Range* right_range = this->right()->definition()->range();
       return (right_range == NULL) || right_range->Overlaps(0, 0);
     }
     default:
-      return overflow_;
+      return can_overflow();
   }
 }
 
 
-bool BinarySmiOpInstr::RightIsPowerOfTwoConstant() const {
+bool BinaryIntegerOpInstr::RightIsPowerOfTwoConstant() const {
   if (!right()->definition()->IsConstant()) return false;
   const Object& constant = right()->definition()->AsConstant()->value();
   if (!constant.IsSmi()) return false;
   const intptr_t int_value = Smi::Cast(constant).Value();
   return Utils::IsPowerOfTwo(Utils::Abs(int_value));
 }
 
 
+

[srdjan, 2014/09/11 17:38:11]

Two lines instead of three

 static bool ToIntegerConstant(Value* value, int64_t* result) {
   if (!value->BindsToConstant()) {
     if (value->definition()->IsUnboxDouble()) {
       return ToIntegerConstant(value->definition()->AsUnboxDouble()->value(),
                                result);
     }
     return false;
   }
 
   const Object& constant = value->BoundConstant();
   if (constant.IsDouble()) {
     const Double& double_constant = Double::Cast(constant);
     *result = static_cast<int64_t>(double_constant.value());
     return (static_cast<double>(*result) == double_constant.value());
   } else if (constant.IsSmi()) {
     *result = Smi::Cast(constant).Value();
     return true;
   } else if (constant.IsMint()) {
     *result = Mint::Cast(constant).value();
     return true;
   }
 
   return false;
 }
 
 
-static Definition* CanonicalizeCommutativeArithmetic(
+static Definition* CanonicalizeCommutativeDoubleArithmetic(
     Token::Kind op,
-    intptr_t cid,
     Value* left,
-    Value* right,
-    int64_t mask = static_cast<int64_t>(0xFFFFFFFFFFFFFFFFLL)) {
-  ASSERT((cid == kSmiCid) || (cid == kDoubleCid) || (cid == kMintCid));
-
+    Value* right) {
   int64_t left_value;
   if (!ToIntegerConstant(left, &left_value)) {
     return NULL;
   }
 
-  // Apply truncation mask to left_value.
-  left_value &= mask;
-
+  // Can't apply 0.0 * x -> 0.0 equivalence to double operation because
+  // 0.0 * NaN is NaN not 0.0.
+  // Can't apply 0.0 + x -> x to double because 0.0 + (-0.0) is 0.0 not -0.0.
   switch (op) {
     case Token::kMUL:
       if (left_value == 1) {
-        if ((cid == kDoubleCid) &&
-            (right->definition()->representation() != kUnboxedDouble)) {
+        if (right->definition()->representation() != kUnboxedDouble) {
           // Can't yet apply the equivalence because representation selection
           // did not run yet. We need it to guarantee that right value is
           // correctly coerced to double. The second canonicalization pass
           // will apply this equivalence.
           return NULL;
         } else {
           return right->definition();
         }
-      } else if ((left_value == 0) && (cid != kDoubleCid)) {
-        // Can't apply this equivalence to double operation because
-        // 0.0 * NaN is NaN not 0.0.
-        return left->definition();
-      }
-      break;
-    case Token::kADD:
-      if ((left_value == 0) && (cid != kDoubleCid)) {
-        // Can't apply this equivalence to double operations because
-        // 0.0 + (-0.0) is 0.0 not -0.0.
-        return right->definition();
-      }
-      break;
-    case Token::kBIT_AND:
-      ASSERT(cid != kDoubleCid);
-      if (left_value == 0) {
-        return left->definition();
-      } else if (left_value == mask) {
-        return right->definition();
-      }
-      break;
-    case Token::kBIT_OR:
-      ASSERT(cid != kDoubleCid);
-      if (left_value == 0) {
-        return right->definition();
-      } else if (left_value == mask) {
-        return left->definition();
-      }
-      break;
-    case Token::kBIT_XOR:
-      ASSERT(cid != kDoubleCid);
-      if (left_value == 0) {
-        return right->definition();
       }
       break;
     default:
       break;
   }
 
   return NULL;
 }
 
 
@@ skipping 24 matching lines @@
 Definition* FloatToDoubleInstr::Canonicalize(FlowGraph* flow_graph) {
   return HasUses() ? this : NULL;
 }
 
 
 Definition* BinaryDoubleOpInstr::Canonicalize(FlowGraph* flow_graph) {
   if (!HasUses()) return NULL;
 
   Definition* result = NULL;
 
-  result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                             kDoubleCid,
-                                             left(),
-                                             right());
-  if (result == NULL) {
-    result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                               kDoubleCid,
-                                               right(),
-                                               left());
-  }
+  result = CanonicalizeCommutativeDoubleArithmetic(op_kind(), left(), right());
   if (result != NULL) {
     return result;
   }
+
+  result = CanonicalizeCommutativeDoubleArithmetic(op_kind(), right(), left());
+  if (result != NULL) {
+    return result;
+  }
 
   if ((op_kind() == Token::kMUL) &&
       (left()->definition() == right()->definition())) {
     MathUnaryInstr* math_unary =
         new MathUnaryInstr(MathUnaryInstr::kDoubleSquare,
                            new Value(left()->definition()),
                            DeoptimizationTarget());
     flow_graph->InsertBefore(this, math_unary, env(), FlowGraph::kValue);
     return math_unary;
   }
 
   return this;
 }
 
 
-Definition* BinarySmiOpInstr::Canonicalize(FlowGraph* flow_graph) {
-  Definition* result = NULL;
-
-  result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                             kSmiCid,
-                                             left(),
-                                             right());
-  if (result != NULL) {
-    return result;
-  }
-
-  result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                             kSmiCid,
-                                             right(),
-                                             left());
-  if (result != NULL) {
-    return result;
+static bool IsCommutative(Token::Kind op) {
+  switch (op) {
+    case Token::kMUL:
+    case Token::kADD:
+    case Token::kBIT_AND:
+    case Token::kBIT_OR:
+    case Token::kBIT_XOR:
+      return true;
+    default:
+      return false;
+  }
+}
+
+
+static intptr_t RepresentationBits(Representation r) {
+  switch (r) {
+    case kTagged:
+      return kBitsPerWord - 1;
+    case kUnboxedInt32:
+    case kUnboxedUint32:
+      return 32;
+    case kUnboxedMint:
+      return 64;
+    default:
+      UNREACHABLE();
+      return 0;
+  }
+}
+
+
+static int64_t RepresentationMask(Representation r) {
+  return static_cast<int64_t>(
+    static_cast<uint64_t>(-1) >> (64 - RepresentationBits(r)));

[srdjan, 2014/09/11 17:38:11]

4 spaces indent

+}
+
+
+UnaryIntegerOpInstr* UnaryIntegerOpInstr::Make(Representation representation,
+                                               Token::Kind op_kind,
+                                               Value* value,
+                                               intptr_t deopt_id,
+                                               Range* range) {
+  UnaryIntegerOpInstr* op = NULL;
+  switch (representation) {
+    case kTagged:
+      op = new UnarySmiOpInstr(op_kind, value, deopt_id);
+      break;
+

[Cutch, 2014/09/11 17:41:53]

remove blank lines

+    case kUnboxedInt32:
+      return NULL;
+
+    case kUnboxedUint32:
+      op = new UnaryUint32OpInstr(op_kind, value, deopt_id);
+      break;
+
+    case kUnboxedMint:
+      op = new UnaryMintOpInstr(op_kind, value, deopt_id);
+      break;
+
+    default:
+      UNREACHABLE();
+      return NULL;
+  }
+
+  if (op == NULL) {
+    return op;
+  }

[srdjan, 2014/09/11 17:38:11]

Instead you could add return NULL to default (remove UNREACHABLE)

[Vyacheslav Egorov (Google), 2014/09/11 19:50:47]

I would like to ensure that we don't forget to update this place when we
introduce new integer representation (if ever :))

+
+  if (!Range::IsUnknown(range)) {
+    op->set_range(*range);
+  }
+
+  ASSERT(op->representation() == representation);
+  return op;
+}
+
+
+BinaryIntegerOpInstr* BinaryIntegerOpInstr::Make(Representation representation,
+                                                 Token::Kind op_kind,
+                                                 Value* left,
+                                                 Value* right,
+                                                 intptr_t deopt_id,
+                                                 bool can_overflow,
+                                                 bool is_truncating,
+                                                 Range* range) {
+  BinaryIntegerOpInstr* op = NULL;
+  switch (representation) {
+    case kTagged:
+      op = new BinarySmiOpInstr(op_kind, left, right, deopt_id);
+      break;
+

[Cutch, 2014/09/11 17:41:53]

ditto

+    case kUnboxedInt32:
+      if (!BinaryInt32OpInstr::IsSupported(op_kind, left, right)) {
+        return NULL;
+      }
+      op = new BinaryInt32OpInstr(op_kind, left, right, deopt_id);
+      break;
+
+    case kUnboxedUint32:
+      if ((op_kind == Token::kSHR) || (op_kind == Token::kSHL)) {
+        op = new ShiftUint32OpInstr(op_kind, left, right, deopt_id);
+      } else {
+        op = new BinaryUint32OpInstr(op_kind, left, right, deopt_id);
+      }
+      break;
+
+    case kUnboxedMint:
+      if ((op_kind == Token::kSHR) || (op_kind == Token::kSHL)) {
+        op = new ShiftMintOpInstr(op_kind, left, right, deopt_id);
+      } else {
+        op = new BinaryMintOpInstr(op_kind, left, right, deopt_id);
+      }
+      break;
+
+    default:
+      UNREACHABLE();
+      return NULL;
+  }
+
+  if (!Range::IsUnknown(range)) {
+    op->set_range(*range);
+  }
+
+  op->set_can_overflow(can_overflow);
+  if (is_truncating) {
+    op->mark_truncating();
+  }
+
+  ASSERT(op->representation() == representation);
+  return op;
+}
+
+
+RawInteger* BinaryIntegerOpInstr::Evaluate(const Integer& left,
+                                           const Integer& right) const {
+  Integer& result = Integer::Handle();
+
+  switch (op_kind()) {
+    case Token::kTRUNCDIV:
+    case Token::kMOD:
+      // Check right value for zero.
+      if (right.AsInt64Value() == 0) {
+        break;  // Will throw.
+      }
+      // Fall through.
+    case Token::kADD:
+    case Token::kSUB:
+    case Token::kMUL: {
+      result = left.ArithmeticOp(op_kind(), right);
+      break;
+    }
+    case Token::kSHL:
+    case Token::kSHR:
+      if (left.IsSmi() && right.IsSmi() && (Smi::Cast(right).Value() >= 0)) {
+        result = Smi::Cast(left).ShiftOp(op_kind(), Smi::Cast(right));
+      }
+      break;
+    case Token::kBIT_AND:
+    case Token::kBIT_OR:
+    case Token::kBIT_XOR: {
+      result = left.BitOp(op_kind(), right);
+      break;
+    }
+    case Token::kDIV:
+      break;
+    default:
+      UNREACHABLE();
+  }
+
+  if (!result.IsNull()) {
+    if (is_truncating()) {
+      int64_t truncated = result.AsTruncatedInt64Value();
+      truncated &= RepresentationMask(representation());
+      result = Integer::New(truncated);
+    }
+    result ^= result.CheckAndCanonicalize(NULL);
+  }
+
+  return result.raw();
+}
+
+
+Definition* BinaryIntegerOpInstr::Canonicalize(FlowGraph* flow_graph) {
+  // If both operands are constants evaluate this expression. Might
+  // occur due to load forwarding after constant propagation pass
+  // have already been run.
+  if (left()->BindsToConstant() &&
+      left()->BoundConstant().IsInteger() &&
+      right()->BindsToConstant() &&
+      right()->BoundConstant().IsInteger()) {
+    const Integer& result = Integer::Handle(
+        Evaluate(Integer::Cast(left()->BoundConstant()),
+                 Integer::Cast(right()->BoundConstant())));
+    if (!result.IsNull()) {
+      return flow_graph->GetConstant(result);
+    }
+  }
+
+  if (left()->BindsToConstant() &&
+      !right()->BindsToConstant() &&
+      IsCommutative(op_kind())) {
+    Value* l = left();
+    Value* r = right();
+    SetInputAt(0, r);
+    SetInputAt(1, l);
+  }
+
+  int64_t rhs;
+  if (!ToIntegerConstant(right(), &rhs)) {
+    return this;
+  }
+
+  const int64_t range_mask = RepresentationMask(representation());
+  if (is_truncating()) {
+    switch (op_kind()) {
+      case Token::kMUL:
+      case Token::kSUB:
+      case Token::kADD:
+      case Token::kBIT_AND:
+      case Token::kBIT_OR:
+      case Token::kBIT_XOR:
+        rhs = (rhs & range_mask);
+        break;
+      default:
+        break;
+    }
+  }
+
+  switch (op_kind()) {
+    case Token::kMUL:
+      if (rhs == 1) {
+        return left()->definition();
+      } else if (rhs == 0) {
+        return right()->definition();
+      } else if (rhs == 2) {
+        ConstantInstr* constant_1 =
+            flow_graph->GetConstant(Smi::Handle(Smi::New(1)));
+        BinaryIntegerOpInstr* shift =
+            BinaryIntegerOpInstr::Make(representation(),
+                                       Token::kSHL,
+                                       left()->CopyWithType(),
+                                       new Value(constant_1),
+                                       deopt_id_,
+                                       can_overflow(),
+                                       is_truncating(),
+                                       range());
+        if (shift != NULL) {
+          flow_graph->InsertBefore(this, shift, env(), FlowGraph::kValue);
+          return shift;
+        }
+      }
+
+      break;
+    case Token::kADD:
+      if (rhs == 0) {
+        return left()->definition();
+      }
+      break;
+    case Token::kBIT_AND:
+      if (rhs == 0) {
+        return right()->definition();
+      } else if (rhs == range_mask) {
+        return left()->definition();
+      }
+      break;
+    case Token::kBIT_OR:
+      if (rhs == 0) {
+        return left()->definition();
+      } else if (rhs == range_mask) {
+        return right()->definition();
+      }
+      break;
+    case Token::kBIT_XOR:
+      if (rhs == 0) {
+        return left()->definition();
+      } else if (rhs == range_mask) {
+        UnaryIntegerOpInstr* bit_not =
+            UnaryIntegerOpInstr::Make(representation(),
+                                      Token::kBIT_NOT,
+                                      left()->CopyWithType(),
+                                      deopt_id_,
+                                      range());
+        if (bit_not != NULL) {
+          flow_graph->InsertBefore(this, bit_not, env(), FlowGraph::kValue);
+          return bit_not;
+        }
+      }
+      break;
+
+    case Token::kSUB:
+      if (rhs == 0) {
+        return left()->definition();
+      }
+      break;
+
+    case Token::kTRUNCDIV:
+      if (rhs == 1) {
+        return left()->definition();
+      } else if (rhs == -1) {
+        UnaryIntegerOpInstr* negation =
+            UnaryIntegerOpInstr::Make(representation(),
+                                      Token::kNEGATE,
+                                      left()->CopyWithType(),
+                                      deopt_id_,
+                                      range());
+        if (negation != NULL) {
+          flow_graph->InsertBefore(this, negation, env(), FlowGraph::kValue);
+          return negation;
+        }
+      }
+      break;
+
+    case Token::kSHR:
+      if (rhs == 0) {
+        return left()->definition();
+      } else if (rhs < 0) {
+        DeoptimizeInstr* deopt =
+            new DeoptimizeInstr(ICData::kDeoptBinarySmiOp, deopt_id_);
+        flow_graph->InsertBefore(this, deopt, env(), FlowGraph::kEffect);
+        return flow_graph->GetConstant(Smi::Handle(Smi::New(0)));
+      }
+      break;
+
+    case Token::kSHL: {
+      const intptr_t kMaxShift = RepresentationBits(representation()) - 1;
+      if (rhs == 0) {
+        return left()->definition();
+      } else if ((rhs < 0) || (rhs >= kMaxShift)) {
+        if ((rhs < 0) || !is_truncating()) {
+          DeoptimizeInstr* deopt =
+              new DeoptimizeInstr(ICData::kDeoptBinarySmiOp, deopt_id_);
+          flow_graph->InsertBefore(this, deopt, env(), FlowGraph::kEffect);
+        }
+        return flow_graph->GetConstant(Smi::Handle(Smi::New(0)));
+      }
+      break;
+    }
+
+    default:
+      break;
   }
 
   return this;
-}
-
-
-Definition* BinaryMintOpInstr::Canonicalize(FlowGraph* flow_graph) {
-  Definition* result = NULL;
-
-  result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                             kMintCid,
-                                             left(),
-                                             right());
-  if (result != NULL) {
-    return result;
-  }
-
-  result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                             kMintCid,
-                                             right(),
-                                             left());
-  if (result != NULL) {
-    return result;
-  }
-
-  return this;
-}
-
-
-Definition* BinaryUint32OpInstr::Canonicalize(FlowGraph* flow_graph) {
-  Definition* result = NULL;
-
-  const int64_t truncation_mask = static_cast<int64_t>(0xFFFFFFFF);
-
-  result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                             kMintCid,
-                                             left(),
-                                             right(),
-                                             truncation_mask);
-  if (result != NULL) {
-    return result;
-  }
-
-  result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                             kMintCid,
-                                             right(),
-                                             left(),
-                                             truncation_mask);
-  if (result != NULL) {
-    return result;
-  }
-
-  return this;
-}
-
-
-Definition* BinaryInt32OpInstr::Canonicalize(FlowGraph* flow_graph) {
-  Definition* result = NULL;
-
-  result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                             kSmiCid,
-                                             left(),
-                                             right());
-  if (result != NULL) {
-    return result;
-  }
-
-  result = CanonicalizeCommutativeArithmetic(op_kind(),
-                                             kSmiCid,
-                                             right(),
-                                             left());
-  if (result != NULL) {
-    return result;
-  }
-
-  return this;
 }
 
 
 // Optimizations that eliminate or simplify individual instructions.
 Instruction* Instruction::Canonicalize(FlowGraph* flow_graph) {
   return this;
 }
 
 
 Definition* Definition::Canonicalize(FlowGraph* flow_graph) {
@@ skipping 1133 matching lines @@
 void AssertAssignableInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
   compiler->GenerateAssertAssignable(token_pos(),
                                      deopt_id(),
                                      dst_type(),
                                      dst_name(),
                                      locs());
   ASSERT(locs()->in(0).reg() == locs()->out(0).reg());
 }
 
 
+LocationSummary* DeoptimizeInstr::MakeLocationSummary(Isolate* isolate,
+                                                      bool opt) const {
+  return new(isolate) LocationSummary(isolate, 0, 0, LocationSummary::kNoCall);
+}
+
+
+void DeoptimizeInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
+  __ Jump(compiler->AddDeoptStub(deopt_id(), deopt_reason_));
+}
+
+
 Environment* Environment::From(Isolate* isolate,
                                const GrowableArray<Definition*>& definitions,
                                intptr_t fixed_parameter_count,
                                const ParsedFunction* parsed_function) {
   Environment* env =
       new(isolate) Environment(definitions.length(),
                                fixed_parameter_count,
                                Isolate::kNoDeoptId,
                                parsed_function,
                                NULL);
@@ skipping 439 matching lines @@
     case Token::kTRUNCDIV: return 0;
     case Token::kMOD: return 1;
     default: UNIMPLEMENTED(); return -1;
   }
 }
 
 
 #undef __
 
 }  // namespace dart