1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/megamorphic_cache_table.h"
6
7#include <stdlib.h>
8#include "vm/compiler/jit/compiler.h"
9#include "vm/object.h"
10#include "vm/object_store.h"
11#include "vm/stub_code.h"
12#include "vm/symbols.h"
13
14namespace dart {
15
16MegamorphicCachePtr MegamorphicCacheTable::Lookup(Thread* thread,
17 const String& name,
18 const Array& descriptor) {
19 Isolate* isolate = thread->isolate();
20 // Multiple compilation threads could access this lookup.
21 SafepointMutexLocker ml(isolate->megamorphic_mutex());
22 ASSERT(name.IsSymbol());
23 // TODO(rmacnak): ASSERT(descriptor.IsCanonical());
24
25 // TODO(rmacnak): Make a proper hashtable a la symbol table.
26 GrowableObjectArray& table = GrowableObjectArray::Handle(
27 isolate->object_store()->megamorphic_cache_table());
28 MegamorphicCache& cache = MegamorphicCache::Handle();
29 if (table.IsNull()) {
30 table = GrowableObjectArray::New(Heap::kOld);
31 isolate->object_store()->set_megamorphic_cache_table(table);
32 } else {
33 for (intptr_t i = 0; i < table.Length(); i++) {
34 cache ^= table.At(i);
35 if ((cache.target_name() == name.raw()) &&
36 (cache.arguments_descriptor() == descriptor.raw())) {
37 return cache.raw();
38 }
39 }
40 }
41
42 cache = MegamorphicCache::New(name, descriptor);
43 table.Add(cache, Heap::kOld);
44 return cache.raw();
45}
46
47void MegamorphicCacheTable::PrintSizes(Isolate* isolate) {
48 StackZone zone(Thread::Current());
49 intptr_t size = 0;
50 MegamorphicCache& cache = MegamorphicCache::Handle();
51 Array& buckets = Array::Handle();
52 const GrowableObjectArray& table = GrowableObjectArray::Handle(
53 isolate->object_store()->megamorphic_cache_table());
54 if (table.IsNull()) return;
55 intptr_t max_size = 0;
56 for (intptr_t i = 0; i < table.Length(); i++) {
57 cache ^= table.At(i);
58 buckets = cache.buckets();
59 size += MegamorphicCache::InstanceSize();
60 size += Array::InstanceSize(buckets.Length());
61 if (buckets.Length() > max_size) {
62 max_size = buckets.Length();
63 }
64 }
65 OS::PrintErr("%" Pd " megamorphic caches using %" Pd "KB.\n", table.Length(),
66 size / 1024);
67
68 intptr_t* probe_counts = new intptr_t[max_size];
69 intptr_t entry_count = 0;
70 intptr_t max_probe_count = 0;
71 for (intptr_t i = 0; i < max_size; i++) {
72 probe_counts[i] = 0;
73 }
74 for (intptr_t i = 0; i < table.Length(); i++) {
75 cache ^= table.At(i);
76 buckets = cache.buckets();
77 intptr_t mask = cache.mask();
78 intptr_t capacity = mask + 1;
79 for (intptr_t j = 0; j < capacity; j++) {
80 intptr_t class_id =
81 Smi::Value(Smi::RawCast(cache.GetClassId(buckets, j)));
82 if (class_id != kIllegalCid) {
83 intptr_t probe_count = 0;
84 intptr_t probe_index =
85 (class_id * MegamorphicCache::kSpreadFactor) & mask;
86 intptr_t probe_cid;
87 while (true) {
88 probe_count++;
89 probe_cid =
90 Smi::Value(Smi::RawCast(cache.GetClassId(buckets, probe_index)));
91 if (probe_cid == class_id) {
92 break;
93 }
94 probe_index = (probe_index + 1) & mask;
95 }
96 probe_counts[probe_count]++;
97 if (probe_count > max_probe_count) {
98 max_probe_count = probe_count;
99 }
100 entry_count++;
101 }
102 }
103 }
104 intptr_t cumulative_entries = 0;
105 for (intptr_t i = 0; i <= max_probe_count; i++) {
106 cumulative_entries += probe_counts[i];
107 OS::PrintErr("Megamorphic probe %" Pd ": %" Pd " (%lf)\n", i,
108 probe_counts[i],
109 static_cast<double>(cumulative_entries) /
110 static_cast<double>(entry_count));
111 }
112 delete[] probe_counts;
113}
114
115} // namespace dart
116