Fix Issue 11047: use binary search instead of linear search to locate a pc-offset in the static cal…

runtime/vm/object.cc

 // 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.
 
 #include "vm/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 7765 matching lines @@
 }
 
 
 void Code::set_object_table(const Array& array) const {
   StorePointer(&raw_ptr()->object_table_, array.raw());
 }
 
 
 void Code::set_static_calls_target_table(const Array& value) const {
   StorePointer(&raw_ptr()->static_calls_target_table_, value.raw());
+#if defined(DEBUG)
+  // Check that the table is sorted by pc offsets.

[Florian Schneider, 2013/06/04 08:36:49]

Maybe I missed something, but where do we sort this table?

[srdjan, 2013/06/04 15:45:27]

Added comment
  // FlowGraphCompiler::AddStaticCallTarget adds pc-offsets to the table while
  // emitting assembly. This guarantees that every succeeding pc-offset is
  // larger than the previously added one.

+  for (intptr_t i = kSCallTableEntryLength;
+      i < value.Length();
+      i += kSCallTableEntryLength) {
+    ASSERT(value.At(i - kSCallTableEntryLength) < value.At(i));
+  }
+#endif  // DEBUG
 }
 
 
 RawDeoptInfo* Code::GetDeoptInfoAtPc(uword pc, intptr_t* deopt_reason) const {
   ASSERT(is_optimized());
   const Instructions& instrs = Instructions::Handle(instructions());
   uword code_entry = instrs.EntryPoint();
   const Array& table = Array::Handle(deopt_info_array());
   ASSERT(!table.IsNull());
   // Linear search for the PC offset matching the target PC.
   intptr_t length = DeoptTable::GetLength(table);
   Smi& offset = Smi::Handle();
   Smi& reason = Smi::Handle();
   DeoptInfo& info = DeoptInfo::Handle();
   for (intptr_t i = 0; i < length; ++i) {
     DeoptTable::GetEntry(table, i, &offset, &info, &reason);
     if (pc == (code_entry + offset.Value())) {
       ASSERT(!info.IsNull());
       *deopt_reason = reason.Value();
       return info.raw();
     }
   }
   *deopt_reason = kDeoptUnknown;
   return DeoptInfo::null();
 }
 
 
+intptr_t Code::BinarySearchInSCallTable(RawObject* key) const {

[siva, 2013/06/03 23:35:35]

Can we change the signature of this function to
intptr_t Code::BinarySearchInSCallTable(intptr_t code_offset);

and move the
RawSmi* raw_code_offset = Smi::New(code_offset);
into this function.

[siva, 2013/06/03 23:38:25]

An even better option might be to pass the pc itself
i.e:
intptr_t Code::BinarySearchInSCallTable(uword pc);

RawSmi* raw_code_offset = Smi::New(pc - EntryPoint());

[srdjan, 2013/06/04 15:45:27]

Done.

[srdjan, 2013/06/04 15:45:27]

Using other suggestion (passing pc).

+  NoGCScope no_gc;
+  const Array& table = Array::Handle(raw_ptr()->static_calls_target_table_);
+  intptr_t imin = 0;
+  intptr_t imax = table.Length() / kSCallTableEntryLength;
+  while (imax >= imin) {
+    const intptr_t imid = ((imax - imin) / 2) + imin;
+    const intptr_t real_index = imid * kSCallTableEntryLength;
+    RawObject* key_in_table = table.At(real_index);

[siva, 2013/06/03 23:35:35]

This can be
RawSmi* key_in_table = Smi::RawCast(table.At(real_index);

[srdjan, 2013/06/04 15:45:27]

Using other suggestion (passing pc).

+    if (key_in_table < key) {
+      imin = imid + 1;
+    } else if (key_in_table > key) {
+      imax = imid - 1;
+    } else {
+      return real_index;
+    }
+  }
+  return -1;
+}
+
+
 RawFunction* Code::GetStaticCallTargetFunctionAt(uword pc) const {
   RawObject* raw_code_offset =
       reinterpret_cast<RawObject*>(Smi::New(pc - EntryPoint()));
+  const intptr_t i = BinarySearchInSCallTable(raw_code_offset);

[siva, 2013/06/03 23:35:35]

This would be just:

const intptr_t i = BinarySearchInSCallTable(pc - EntryPoint());

[siva, 2013/06/03 23:38:25]

And this would be:

const intptr_t i = BinarySearchInSCallTable(pc);

[srdjan, 2013/06/04 15:45:27]

Done.

[srdjan, 2013/06/04 15:45:27]

Using other suggestion (passing pc).

+  if (i < 0) {
+    return Function::null();
+  }
   const Array& array =
       Array::Handle(raw_ptr()->static_calls_target_table_);
-  for (intptr_t i = 0; i < array.Length(); i += kSCallTableEntryLength) {
-    if (array.At(i) == raw_code_offset) {
-      Function& function = Function::Handle();
-      function ^= array.At(i + kSCallTableFunctionEntry);
-      return function.raw();
-    }
-  }
-  return Function::null();
+  Function& function = Function::Handle();
+  function ^= array.At(i + kSCallTableFunctionEntry);
+  return function.raw();
 }
 
 
 void Code::SetStaticCallTargetCodeAt(uword pc, const Code& code) const {
   RawObject* raw_code_offset =
       reinterpret_cast<RawObject*>(Smi::New(pc - EntryPoint()));
   const Array& array =
       Array::Handle(raw_ptr()->static_calls_target_table_);
-  for (intptr_t i = 0; i < array.Length(); i += kSCallTableEntryLength) {
-    if (array.At(i) == raw_code_offset) {
-      ASSERT(code.IsNull() ||
-             (code.function() == array.At(i + kSCallTableFunctionEntry)));
-      array.SetAt(i + kSCallTableCodeEntry, code);
-      return;
-    }
-  }
-  UNREACHABLE();
+  const intptr_t i = BinarySearchInSCallTable(raw_code_offset);

[siva, 2013/06/03 23:35:35]

Ditto here.

[srdjan, 2013/06/04 15:45:27]

Ditto

+  ASSERT(i >= 0);
+  ASSERT(code.IsNull() ||
+         (code.function() == array.At(i + kSCallTableFunctionEntry)));
+  array.SetAt(i + kSCallTableCodeEntry, code);
 }
 
 
 const Code::Comments& Code::comments() const  {
   Comments* comments = new Code::Comments(Array::Handle(raw_ptr()->comments_));
   return *comments;
 }
 
 
 void Code::set_comments(const Code::Comments& comments) const {
@@ skipping 5452 matching lines @@
                                     space);
   return reinterpret_cast<RawWeakProperty*>(raw);
 }
 
 
 const char* WeakProperty::ToCString() const {
   return "_WeakProperty";
 }
 
 }  // namespace dart