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/compiler/cha.h"
6#include "vm/class_table.h"
7#include "vm/flags.h"
8#include "vm/object.h"
9#include "vm/raw_object.h"
10#include "vm/visitor.h"
11
12namespace dart {
13
14void CHA::AddToGuardedClasses(const Class& cls, intptr_t subclass_count) {
15 for (intptr_t i = 0; i < guarded_classes_.length(); i++) {
16 if (guarded_classes_[i].cls->raw() == cls.raw()) {
17 return;
18 }
19 }
20 GuardedClassInfo info = {&Class::ZoneHandle(thread_->zone(), cls.raw()),
21 subclass_count};
22 guarded_classes_.Add(info);
23 return;
24}
25
26bool CHA::IsGuardedClass(intptr_t cid) const {
27 for (intptr_t i = 0; i < guarded_classes_.length(); ++i) {
28 if (guarded_classes_[i].cls->id() == cid) return true;
29 }
30 return false;
31}
32
33bool CHA::HasSubclasses(const Class& cls) {
34 ASSERT(!cls.IsNull());
35 ASSERT(cls.id() >= kInstanceCid);
36 // Can't track dependencies for classes on the VM heap since those are
37 // read-only.
38 // TODO(fschneider): Enable tracking of CHA dependent code for VM heap
39 // classes.
40 if (cls.InVMIsolateHeap()) return true;
41
42 if (cls.IsObjectClass()) {
43 // Class Object has subclasses, although we do not keep track of them.
44 return true;
45 }
46 const GrowableObjectArray& direct_subclasses =
47 GrowableObjectArray::Handle(cls.direct_subclasses());
48 return !direct_subclasses.IsNull() && (direct_subclasses.Length() > 0);
49}
50
51bool CHA::HasSubclasses(intptr_t cid) const {
52 const ClassTable& class_table = *thread_->isolate()->class_table();
53 Class& cls = Class::Handle(thread_->zone(), class_table.At(cid));
54 return HasSubclasses(cls);
55}
56
57bool CHA::ConcreteSubclasses(const Class& cls,
58 GrowableArray<intptr_t>* class_ids) {
59 if (cls.InVMIsolateHeap()) return false;
60 if (cls.IsObjectClass()) return false;
61
62 if (!cls.is_abstract()) {
63 class_ids->Add(cls.id());
64 }
65
66 const GrowableObjectArray& direct_subclasses =
67 GrowableObjectArray::Handle(cls.direct_subclasses());
68 if (direct_subclasses.IsNull()) {
69 return true;
70 }
71 Class& subclass = Class::Handle();
72 for (intptr_t i = 0; i < direct_subclasses.Length(); i++) {
73 subclass ^= direct_subclasses.At(i);
74 if (!ConcreteSubclasses(subclass, class_ids)) {
75 return false;
76 }
77 }
78 return true;
79}
80
81bool CHA::IsImplemented(const Class& cls) {
82 // Function type aliases have different type checking rules.
83 ASSERT(!cls.IsTypedefClass());
84 // Can't track dependencies for classes on the VM heap since those are
85 // read-only.
86 // TODO(fschneider): Enable tracking of CHA dependent code for VM heap
87 // classes.
88 if (cls.InVMIsolateHeap()) return true;
89
90 return cls.is_implemented();
91}
92
93static intptr_t CountFinalizedSubclasses(Thread* thread, const Class& cls) {
94 intptr_t count = 0;
95 const GrowableObjectArray& cls_direct_subclasses =
96 GrowableObjectArray::Handle(thread->zone(), cls.direct_subclasses());
97 if (cls_direct_subclasses.IsNull()) return count;
98 Class& direct_subclass = Class::Handle(thread->zone());
99 for (intptr_t i = 0; i < cls_direct_subclasses.Length(); i++) {
100 direct_subclass ^= cls_direct_subclasses.At(i);
101 // Unfinalized classes are treated as non-existent for CHA purposes,
102 // as that means that no instance of that class exists at runtime.
103 if (!direct_subclass.is_finalized()) {
104 continue;
105 }
106
107 count += 1 + CountFinalizedSubclasses(thread, direct_subclass);
108 }
109 return count;
110}
111
112bool CHA::IsConsistentWithCurrentHierarchy() const {
113 for (intptr_t i = 0; i < guarded_classes_.length(); i++) {
114 const intptr_t subclass_count =
115 CountFinalizedSubclasses(thread_, *guarded_classes_[i].cls);
116 if (guarded_classes_[i].subclass_count != subclass_count) {
117 return false;
118 }
119 }
120 return true;
121}
122
123bool CHA::HasOverride(const Class& cls,
124 const String& function_name,
125 intptr_t* subclasses_count) {
126 // Can't track dependencies for classes on the VM heap since those are
127 // read-only.
128 // TODO(fschneider): Enable tracking of CHA dependent code for VM heap
129 // classes.
130 if (cls.InVMIsolateHeap()) return true;
131
132 // Subclasses of Object are not tracked by CHA. Safely assume that overrides
133 // exist.
134 if (cls.IsObjectClass()) {
135 return true;
136 }
137
138 const GrowableObjectArray& cls_direct_subclasses =
139 GrowableObjectArray::Handle(thread_->zone(), cls.direct_subclasses());
140 if (cls_direct_subclasses.IsNull()) {
141 return false;
142 }
143 Class& direct_subclass = Class::Handle(thread_->zone());
144 for (intptr_t i = 0; i < cls_direct_subclasses.Length(); i++) {
145 direct_subclass ^= cls_direct_subclasses.At(i);
146 // Unfinalized classes are treated as non-existent for CHA purposes,
147 // as that means that no instance of that class exists at runtime.
148 if (!direct_subclass.is_finalized()) {
149 continue;
150 }
151
152 if (direct_subclass.LookupDynamicFunction(function_name) !=
153 Function::null()) {
154 return true;
155 }
156
157 if (HasOverride(direct_subclass, function_name, subclasses_count)) {
158 return true;
159 }
160
161 (*subclasses_count)++;
162 }
163
164 return false;
165}
166
167void CHA::RegisterDependencies(const Code& code) const {
168 for (intptr_t i = 0; i < guarded_classes_.length(); ++i) {
169 guarded_classes_[i].cls->RegisterCHACode(code);
170 }
171}
172
173} // namespace dart
174