Use off-heap data for class check instructions

runtime/vm/intermediate_language.h

 // 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.
 
 #ifndef RUNTIME_VM_INTERMEDIATE_LANGUAGE_H_
 #define RUNTIME_VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
@@ skipping 538 matching lines @@
 #endif  // !PRODUCT
 
 
 // Represents a mapping from a range of class-ids to a method for a given
 // selector (method name).  Also can contain an indication of how frequently a
 // given method has been called at a call site.  This information can be
 // harvested from the inline caches (ICs).
 struct CidRangeTarget {
   intptr_t cid_start;
   intptr_t cid_end;
-  Function* target;
+  const Function* target;
   intptr_t count;
   CidRangeTarget(intptr_t cid_start_arg,
                  intptr_t cid_end_arg,
-                 Function* target_arg,
+                 const Function* target_arg,
                  intptr_t count_arg)
       : cid_start(cid_start_arg),
         cid_end(cid_end_arg),
         target(target_arg),
         count(count_arg) {
-    ASSERT(target->IsZoneHandle());
+    ASSERT(target == NULL || target->IsZoneHandle());
   }
 };
 
 
 class CallTargets : public ZoneAllocated {

[Vyacheslav Egorov (Google), 2017/05/01 12:21:25]

It feels a bit strange to use CallTargets as a "cid-list" in the ClassCheck. 

There are a lot of information and functionality on this class that make no
sense when it is used for checks and similarly there is information and
functionality that only makes sense for checks.

Maybe we need to split this into two classes now:

// Contains a list of cid-ranges (potentially with frequences, maybe not)
class CidRangeList {
};

// Contains a mapping from cid-ranges to functions.
class CallTargets {
  
};

Now here is an interesting question: whether CallTargets should inherit from
CidRangeList or it should just contain it inside. I think composition is better.

[erikcorry, 2017/05/05 15:15:51]

I tried several things here.  In the end the one that worked best was to have a
class called Cids for class checks.  CallTargets is used for polymorphic
dispatch and inherits from Cids. They both have a growable array of pointers to
CidRange objects (just a cid pair), but in the case of CallTargets the elements
are actually pointing to instances of CallInfo, a subclass of CidRange that
contains target and count information.

  public:
   // Creates the off-heap CallTargets object that reflects the contents
-  // of the on-VM-heap IC data. Also expands the class-ids to neighbouring
-  // classes that inherit the same method.
-  static CallTargets* Create(Zone* zone, const ICData& ic_data);
+  // of the on-VM-heap IC data.
+  static CallTargets* Create(Zone* zone,
+                             const ICData& ic_data,
+                             int argument_number);
+
+  // This variant always uses the IC data for argument 0 (the receiver) and
+  // also expands the class-ids to neighbouring classes that inherit the same
+  // method.
+  static CallTargets* CreateAndExpand(Zone* zone, const ICData& ic_data);
 
   void Add(const CidRangeTarget& target) { cid_ranges_.Add(target); }
 
+  bool Equals(const CallTargets& other) const;
+
+  bool HasClassId(intptr_t cid) const;
+
   CidRangeTarget& operator[](intptr_t index) const {
     return cid_ranges_[index];
   }
 
   CidRangeTarget At(int index) { return cid_ranges_.At(index); }
 
   intptr_t length() const { return cid_ranges_.length(); }
 
   void SetLength(intptr_t len) { cid_ranges_.SetLength(len); }
 
   bool is_empty() const { return cid_ranges_.is_empty(); }
 
   void Sort(int compare(const CidRangeTarget* a, const CidRangeTarget* b)) {
     cid_ranges_.Sort(compare);
   }
 
   intptr_t AggregateCallCount() const;
 
   bool HasSingleTarget() const;
   bool HasSingleRecognizedTarget() const;
-  Function& FirstTarget() const;
-  Function& MostPopularTarget() const;
+  const Function& FirstTarget() const;
+  const Function& MostPopularTarget() const;
   bool IsMonomorphic() const;
   intptr_t MonomorphicReceiverCid() const;
+  bool AreAllChecksImmutable() const;
+  bool HasReceiverClassId(intptr_t cid) const;
+  intptr_t ComputeLowestCid() const;
+  intptr_t ComputeHighestCid() const;
+
 
  private:
+  void MergeIntoRanges();
+  static CallTargets* CreateHelper(Zone* zone,
+                                   const ICData& ic_data,
+                                   int argument_number);
+
   GrowableArray<CidRangeTarget> cid_ranges_;
 };
 
 
 class Instruction : public ZoneAllocated {
  public:
 #define DECLARE_TAG(type) k##type,
   enum Tag { FOR_EACH_INSTRUCTION(DECLARE_TAG) };
 #undef DECLARE_TAG
 
@@ skipping 6965 matching lines @@
   ZoneGrowableArray<Value*>* inputs_;
   MergedMathInstr::Kind kind_;
   DISALLOW_COPY_AND_ASSIGN(MergedMathInstr);
 };
 
 
 class CheckClassInstr : public TemplateInstruction<1, NoThrow> {
  public:
   CheckClassInstr(Value* value,
                   intptr_t deopt_id,
-                  const ICData& unary_checks,
+                  const CallTargets& targets,
                   TokenPosition token_pos);
 
   DECLARE_INSTRUCTION(CheckClass)
 
   virtual bool ComputeCanDeoptimize() const { return true; }
 
   virtual TokenPosition token_pos() const { return token_pos_; }
 
   Value* value() const { return inputs_[0]; }
 
-  const ICData& unary_checks() const { return unary_checks_; }
-
-  const GrowableArray<intptr_t>& cids() const { return cids_; }
+  const CallTargets& targets() const { return targets_; }
 
   virtual Instruction* Canonicalize(FlowGraph* flow_graph);
 
-  bool IsNullCheck() const { return DeoptIfNull() || DeoptIfNotNull(); }
+  bool IsNullCheck() const { return IsDeoptIfNull() || IsDeoptIfNotNull(); }
 
-  bool DeoptIfNull() const;
-  bool DeoptIfNotNull() const;
+  bool IsDeoptIfNull() const;
+  bool IsDeoptIfNotNull() const;
 
   bool IsDenseSwitch() const;
-  static bool IsDenseCidRange(const ICData& unary_checks);
+  static bool IsDenseCidRange(const CallTargets& targets);
   intptr_t ComputeCidMask() const;
-  static bool IsDenseMask(intptr_t mask);
 
   virtual bool AllowsCSE() const { return true; }
   virtual EffectSet Dependencies() const;
   virtual EffectSet Effects() const { return EffectSet::None(); }
   virtual bool AttributesEqual(Instruction* other) const;
 
   bool licm_hoisted() const { return licm_hoisted_; }
   void set_licm_hoisted(bool value) { licm_hoisted_ = value; }
 
   PRINT_OPERANDS_TO_SUPPORT
 
  private:
-  const ICData& unary_checks_;
-  GrowableArray<intptr_t> cids_;  // Sorted, lowest first.
+  const CallTargets& targets_;
   bool licm_hoisted_;
   bool is_dense_switch_;
   const TokenPosition token_pos_;
 
+  int EmitCheckCid(FlowGraphCompiler* compiler,
+                   int bias,
+                   intptr_t cid_start,
+                   intptr_t cid_end,
+                   bool is_last,
+                   Label* is_ok,
+                   Label* deopt,
+                   bool use_near_jump);
+  void EmitDenseSwitch(FlowGraphCompiler* compiler,
+                       intptr_t min,
+                       intptr_t max,
+                       intptr_t mask,
+                       Label* deopt);
+  void EmitNullCheck(FlowGraphCompiler* compiler, Label* deopt);
+
   DISALLOW_COPY_AND_ASSIGN(CheckClassInstr);
 };
 
 
 class CheckSmiInstr : public TemplateInstruction<1, NoThrow, Pure> {
  public:
   CheckSmiInstr(Value* value, intptr_t deopt_id, TokenPosition token_pos)
       : TemplateInstruction(deopt_id),
         token_pos_(token_pos),
         licm_hoisted_(false) {
@@ skipping 466 matching lines @@
   LocationSummary* Name::MakeLocationSummary(Zone* zone, bool opt) const {     \
     UNIMPLEMENTED();                                                           \
     return NULL;                                                               \
   }                                                                            \
   void Name::EmitNativeCode(FlowGraphCompiler* compiler) { UNIMPLEMENTED(); }
 
 
 }  // namespace dart
 
 #endif  // RUNTIME_VM_INTERMEDIATE_LANGUAGE_H_