Reland r38116: Improve receiver class check in polymorphic inlining.

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/bigint_operations.h"
 #include "vm/bit_vector.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 77 matching lines @@
   }
   return AttributesEqual(other);
 }
 
 
 bool Value::Equals(Value* other) const {
   return definition() == other->definition();
 }
 
 
+static int LowestFirst(const intptr_t* a, const intptr_t* b) {
+  return *a - *b;
+}
+
+
 CheckClassInstr::CheckClassInstr(Value* value,
                                  intptr_t deopt_id,
                                  const ICData& unary_checks,
                                  intptr_t token_pos)
-    : unary_checks_(unary_checks), licm_hoisted_(false), token_pos_(token_pos) {
+    : unary_checks_(unary_checks),
+      cids_(unary_checks.NumberOfChecks()),
+      licm_hoisted_(false),
+      token_pos_(token_pos) {
   ASSERT(unary_checks.IsZoneHandle());
   // Expected useful check data.
   ASSERT(!unary_checks_.IsNull());
   ASSERT(unary_checks_.NumberOfChecks() > 0);
   ASSERT(unary_checks_.NumArgsTested() == 1);
   SetInputAt(0, value);
   deopt_id_ = deopt_id;
   // Otherwise use CheckSmiInstr.
   ASSERT((unary_checks_.NumberOfChecks() != 1) ||
          (unary_checks_.GetReceiverClassIdAt(0) != kSmiCid));
+  for (intptr_t i = 0; i < unary_checks.NumberOfChecks(); ++i) {
+    cids_.Add(unary_checks.GetReceiverClassIdAt(i));
+  }
+  cids_.Sort(LowestFirst);
 }
 
 
 bool CheckClassInstr::AttributesEqual(Instruction* other) const {
   CheckClassInstr* other_check = other->AsCheckClass();
   ASSERT(other_check != NULL);
   if (unary_checks().NumberOfChecks() !=
       other_check->unary_checks().NumberOfChecks()) {
     return false;
   }
@@ skipping 10 matching lines @@
 
 EffectSet CheckClassInstr::Dependencies() const {
   // Externalization of strings via the API can change the class-id.
   const bool externalizable =
       unary_checks().HasReceiverClassId(kOneByteStringCid) ||
       unary_checks().HasReceiverClassId(kTwoByteStringCid);
   return externalizable ? EffectSet::Externalization() : EffectSet::None();
 }
 
 
+EffectSet CheckClassIdInstr::Dependencies() const {
+  // Externalization of strings via the API can change the class-id.
+  const bool externalizable =
+      cid_ == kOneByteStringCid || cid_ == kTwoByteStringCid;
+  return externalizable ? EffectSet::Externalization() : EffectSet::None();
+}
+
+
 bool CheckClassInstr::IsNullCheck() const {
   if (unary_checks().NumberOfChecks() != 1) {
     return false;
   }
   CompileType* in_type = value()->Type();
   const intptr_t cid = unary_checks().GetCidAt(0);
   // Performance check: use CheckSmiInstr instead.
   ASSERT(cid != kSmiCid);
   return in_type->is_nullable() && (in_type->ToNullableCid() == cid);
 }
 
 
+bool CheckClassInstr::IsDenseSwitch() const {
+  if (unary_checks().GetReceiverClassIdAt(0) == kSmiCid) return false;
+  if (cids_.length() > 2 &&
+      cids_[cids_.length() - 1] - cids_[0] < kBitsPerWord) {
+    return true;
+  }
+  return false;
+}
+
+
+intptr_t CheckClassInstr::ComputeCidMask() const {
+  ASSERT(IsDenseSwitch());
+  intptr_t mask = 0;
+  for (intptr_t i = 0; i < cids_.length(); ++i) {
+    mask |= 1 << (cids_[i] - cids_[0]);
+  }
+  return mask;
+}
+
+
+bool CheckClassInstr::IsDenseMask(intptr_t mask) {
+  // Returns true if the mask is a continuos sequence of ones in its binary
+  // representation (i.e. no holes)
+  return mask == -1 || Utils::IsPowerOfTwo(mask + 1);
+}
+
+
 bool LoadFieldInstr::IsUnboxedLoad() const {
   return FLAG_unbox_numeric_fields
       && (field() != NULL)
       && field()->IsUnboxedField();
 }
 
 
 bool LoadFieldInstr::IsPotentialUnboxedLoad() const {
   return FLAG_unbox_numeric_fields
       && (field() != NULL)
@@ skipping 1791 matching lines @@
 Instruction* CheckClassInstr::Canonicalize(FlowGraph* flow_graph) {
   const intptr_t value_cid = value()->Type()->ToCid();
   if (value_cid == kDynamicCid) {
     return this;
   }
 
   return unary_checks().HasReceiverClassId(value_cid) ? NULL : this;
 }
 
 
+Instruction* CheckClassIdInstr::Canonicalize(FlowGraph* flow_graph) {
+  if (value()->BindsToConstant()) {

[Vyacheslav Egorov (Google), 2014/07/11 11:50:24]

does BindsToConstant() see through to OriginalDefinition?

note: constant folding of LoadClassId instruction does not take externalization
into account. we need to fix this.

[Florian Schneider, 2014/07/14 12:13:46]

No, we run Canonicalize after removing Redefinitions though.
 
Yes.

+    const Object& constant_value = value()->BoundConstant();
+    if (constant_value.IsSmi() &&
+        Smi::Cast(constant_value).Value() == cid_) {
+      return NULL;
+    }
+  }
+  return this;
+}
+
+
 Instruction* GuardFieldClassInstr::Canonicalize(FlowGraph* flow_graph) {
   if (field().guarded_cid() == kDynamicCid) {
     return NULL;  // Nothing to guard.
   }
 
   if (field().is_nullable() && value()->Type()->IsNull()) {
     return NULL;
   }
 
   const intptr_t cid = field().is_nullable() ? value()->Type()->ToNullableCid()
@@ skipping 502 matching lines @@
   if (IsConstant()) return *this;
   return Add(Range::ConstantMax(symbol()->range()),
              RangeBoundary::FromConstant(offset_),
              PositiveInfinity());
 }
 
 
 RangeBoundary RangeBoundary::Add(const RangeBoundary& a,
                                  const RangeBoundary& b,
                                  const RangeBoundary& overflow) {
+  if (a.IsInfinity() || b.IsInfinity()) return overflow;
+
   ASSERT(a.IsConstant() && b.IsConstant());
-
   if (Utils::WillAddOverflow(a.ConstantValue(), b.ConstantValue())) {
     return overflow;
   }
 
   int64_t result = a.ConstantValue() + b.ConstantValue();
 
   return RangeBoundary::FromConstant(result);
 }
 
 
 RangeBoundary RangeBoundary::Sub(const RangeBoundary& a,
                                  const RangeBoundary& b,
                                  const RangeBoundary& overflow) {
+  if (a.IsInfinity() || b.IsInfinity()) return overflow;
   ASSERT(a.IsConstant() && b.IsConstant());
-
   if (Utils::WillSubOverflow(a.ConstantValue(), b.ConstantValue())) {
     return overflow;
   }
 
   int64_t result = a.ConstantValue() - b.ConstantValue();
 
   return RangeBoundary::FromConstant(result);
 }
 
 
@@ skipping 1460 matching lines @@
     case Token::kTRUNCDIV: return 0;
     case Token::kMOD: return 1;
     default: UNIMPLEMENTED(); return -1;
   }
 }
 
 
 #undef __
 
 }  // namespace dart