Range feedback for binary integer operations.

runtime/vm/object.h

 // Copyright (c) 2012, 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.
 
 #ifndef VM_OBJECT_H_
 #define VM_OBJECT_H_
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "platform/utils.h"
@@ skipping 3529 matching lines @@
   RawArray* arguments_descriptor() const {
     return raw_ptr()->args_descriptor_;
   }
 
   intptr_t NumArgsTested() const;
 
   intptr_t deopt_id() const {
     return raw_ptr()->deopt_id_;
   }
 
+  uint32_t range_feedback() const {
+    return raw_ptr()->range_feedback_;
+  }
+
   #define DEOPT_REASONS(V)                                                     \
     V(Unknown)                                                                 \
     V(InstanceGetter)                                                          \
     V(PolymorphicInstanceCallTestFail)                                         \
     V(InstanceCallNoICData)                                                    \
     V(IntegerToDouble)                                                         \
     V(BinarySmiOp)                                                             \
     V(BinaryMintOp)                                                            \
     V(UnaryMintOp)                                                             \
     V(ShiftMintOp)                                                             \
@@ skipping 74 matching lines @@
   }
 
   static intptr_t ic_data_offset() {
     return OFFSET_OF(RawICData, ic_data_);
   }
 
   static intptr_t owner_offset() {
     return OFFSET_OF(RawICData, owner_);
   }
 
+  static intptr_t range_feedback_offset() {
+    return OFFSET_OF(RawICData, range_feedback_);
+  }
+
   // Used for unoptimized static calls when no class-ids are checked.
   void AddTarget(const Function& target) const;
 
   // Adding checks.
 
   // Adds one more class test to ICData. Length of 'classes' must be equal to
   // the number of arguments tested. Use only for num_args_tested > 1.
   void AddCheck(const GrowableArray<intptr_t>& class_ids,
                 const Function& target) const;
   // Adds sorted so that Smi is the first class-id. Use only for
@@ skipping 54 matching lines @@
 
   static intptr_t CountIndexFor(intptr_t num_args) {
     return (num_args + 1);
   }
 
   bool IsUsedAt(intptr_t i) const;
 
   void GetUsedCidsForTwoArgs(GrowableArray<intptr_t>* first,
                              GrowableArray<intptr_t>* second) const;
 
+  // Range feedback tracking functionality.
+
+  // For arithmetic operations we store range information for inputs and the
+  // result. The goal is to discover:
+  //
+  //    - on 32-bit platforms:
+  //         - when Mint operation is actually a int32/uint32 operation;
+  //         - when Smi operation produces non-smi results;
+  //
+  //    - on 64-bit platforms:
+  //         - when Smi operation is actually int32/uint32 operation;
+  //         - when Mint operation produces non-smi results;
+  //
+  enum RangeFeedback {
+    kSmiRange,
+    kInt32Range,
+    kUint32Range,
+    kInt64Range
+  };
+
+  // We use 4 bits per operand/result feedback. Our lattice allows us to
+  // express the following states:
+  //
+  //   - usmi   0000 [used only on 32bit platforms]
+  //   - smi    0001
+  //   - uint31 0010
+  //   - int32  0011
+  //   - uint32 0100
+  //   - int33  x1x1
+  //   - int64  1xxx
+  //
+  // DecodeRangeFeedbackAt() helper maps these states into the RangeFeedback
+  // enumeration.
+  enum {
+    kSignBit = 1 << 0,
+    kInt32Bit = 1 << 1,
+    kUint32Bit = 1 << 2,
+    kInt64Bit = 1 << 3,
+    kBitsPerRangeFeedback = 4,
+    kRangeFeedbackMask = (1 << kBitsPerRangeFeedback) - 1
+  };
+
+  static bool IsValidRangeFeedbackIndex(intptr_t index) {
+    return (0 <= index) && (index < 3);
+  }
+
+  static const char* RangeFeedbackToString(RangeFeedback feedback) {
+    switch (feedback) {
+      case kSmiRange:
+        return "smi";
+      case kInt32Range:
+        return "int32";
+      case kUint32Range:
+        return "uint32";
+      case kInt64Range:
+        return "int64";
+      default:
+        UNREACHABLE();
+        return "?";
+    }
+  }
+
+  // It is only meaningful to interptret range feedback stored in the ICData
+  // when all checks are Mint or Smi.
+  bool HasRangeFeedback() const;
+  RangeFeedback DecodeRangeFeedbackAt(intptr_t idx) const;
+
  private:
   RawArray* ic_data() const {
     return raw_ptr()->ic_data_;
   }
 
   void set_owner(const Function& value) const;
   void set_target_name(const String& value) const;
   void set_arguments_descriptor(const Array& value) const;
   void set_deopt_id(intptr_t value) const;
   void SetNumArgsTested(intptr_t value) const;
   void set_ic_data(const Array& value) const;
   void set_state_bits(uint32_t bits) const;
+  void set_range_feedback(uint32_t feedback);
 
   enum {
     kNumArgsTestedPos = 0,
     kNumArgsTestedSize = 2,
     kDeoptReasonPos = kNumArgsTestedPos + kNumArgsTestedSize,
     kDeoptReasonSize = kDeoptNumReasons,
     kIssuedJSWarningBit = kDeoptReasonPos + kDeoptReasonSize,

[zra, 2014/12/15 16:01:41]

If we didn't need to encode so many deopt reasons, then you could put the range
feedback in state_bits_.

[Vyacheslav Egorov (Google), 2014/12/15 17:20:05]

We actually don't need most of the deopt reasons. They are not used anywhere -
but in printing during deopt itself. Some deopts reasons are recorded and used
in the optimizer to avoid repetitive wrong speculations... With *this* change
we'll can get rid of them, but first we will need to start using range feedback
in the optimizer - and then we can kill those deopt reasons that exist purely to
avoid repetitive deopt.

On ia32 we don't change the size, because there is a one words of padding
already.

It is true however that on 64-bit platforms we will increase ICData size by 2
words with this change, which is *quite* unfortunate. To be honest, somehow I
miscounted words when I was checking this, and now that I verified my
calculations I can see that there is no free space on x64/arm64 inside the
RawICData.

If you have any idea where to fold it into - I am open for suggestions.
Otherwise, I suggest we can do it later once we kill tracking of those deopt
reasons that are not used for anything and free up space.

   };
 
   class NumArgsTestedBits : public BitField<uint32_t,
       kNumArgsTestedPos, kNumArgsTestedSize> {};  // NOLINT
   class DeoptReasonBits : public BitField<uint32_t,
       ICData::kDeoptReasonPos, ICData::kDeoptReasonSize> {};  // NOLINT
   class IssuedJSWarningBit : public BitField<bool, kIssuedJSWarningBit, 1> {};
 
 #if defined(DEBUG)
   // Used in asserts to verify that a check is not added twice.
@@ skipping 3845 matching lines @@
 
 
 RawObject* MegamorphicCache::GetTargetFunction(const Array& array,
                                                intptr_t index) {
   return array.At((index * kEntryLength) + kTargetFunctionIndex);
 }
 
 }  // namespace dart
 
 #endif  // VM_OBJECT_H_