1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
/*
* Copyright (C) 2016 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ART_RUNTIME_CHA_H_
#define ART_RUNTIME_CHA_H_
#include <unordered_map>
#include <unordered_set>
#include "base/enums.h"
#include "base/mutex.h"
#include "handle.h"
#include "mirror/class.h"
#include "oat_quick_method_header.h"
namespace art {
class ArtMethod;
class LinearAlloc;
/**
* Class Hierarchy Analysis (CHA) tries to devirtualize virtual calls into
* direct calls based on the info generated by analyzing class hierarchies.
* If a class is not subclassed, or even if it's subclassed but one of its
* virtual methods isn't overridden, a virtual call for that method can be
* changed into a direct call.
*
* Each virtual method carries a single-implementation status. The status is
* incrementally maintained at the end of class linking time when method
* overriding takes effect.
*
* Compiler takes advantage of the single-implementation info of a
* method. If a method A has the single-implementation flag set, the compiler
* devirtualizes the virtual call for method A into a direct call, and
* further try to inline the direct call as a result. The compiler will
* also register a dependency that the compiled code depends on the
* assumption that method A has single-implementation status.
*
* When single-implementation info is updated at the end of class linking,
* and if method A's single-implementation status is invalidated, all compiled
* code that depends on the assumption that method A has single-implementation
* status need to be invalidated. Method entrypoints that have this dependency
* will be updated as a result. Method A can later be recompiled with less
* aggressive assumptions.
*
* For live compiled code that's on stack, deoptmization will be initiated
* to force the invalidated compiled code into interpreter mode to guarantee
* correctness. The deoptimization mechanism used is a hybrid of
* synchronous and asynchronous deoptimization. The synchronous deoptimization
* part checks a hidden local variable flag for the method, and if true,
* initiates deoptimization. The asynchronous deoptimization part issues a
* checkpoint that walks the stack and for any compiled code on the stack
* that should be deoptimized, set the hidden local variable value to be true.
*
* A cha_lock_ needs to be held for updating single-implementation status,
* and registering/unregistering CHA dependencies. Registering CHA dependency
* and making compiled code visible also need to be atomic. Otherwise, we
* may miss invalidating CHA dependents or making compiled code visible even
* after it is invalidated. Care needs to be taken between cha_lock_ and
* JitCodeCache::lock_ to guarantee the atomicity.
*
* We base our CHA on dynamically linked class profiles instead of doing static
* analysis. Static analysis can be too aggressive due to dynamic class loading
* at runtime, and too conservative since some classes may not be really loaded
* at runtime.
*/
class ClassHierarchyAnalysis {
public:
// Types for recording CHA dependencies.
// For invalidating CHA dependency, we need to know both the ArtMethod and
// the method header. If the ArtMethod has compiled code with the method header
// as the entrypoint, we update the entrypoint to the interpreter bridge.
// We will also deoptimize frames that are currently executing the code of
// the method header.
typedef std::pair<ArtMethod*, OatQuickMethodHeader*> MethodAndMethodHeaderPair;
typedef std::vector<MethodAndMethodHeaderPair> ListOfDependentPairs;
ClassHierarchyAnalysis() {}
// Add a dependency that compiled code with `dependent_header` for `dependent_method`
// assumes that virtual `method` has single-implementation.
void AddDependency(ArtMethod* method,
ArtMethod* dependent_method,
OatQuickMethodHeader* dependent_header) REQUIRES(Locks::cha_lock_);
// Return compiled code that assumes that `method` has single-implementation.
const ListOfDependentPairs& GetDependents(ArtMethod* method) REQUIRES(Locks::cha_lock_);
// Remove dependency tracking for compiled code that assumes that
// `method` has single-implementation.
void RemoveAllDependenciesFor(ArtMethod* method) REQUIRES(Locks::cha_lock_);
// Remove from cha_dependency_map_ all entries that contain OatQuickMethodHeader from
// the given `method_headers` set.
// This is used when some compiled code is freed.
void RemoveDependentsWithMethodHeaders(
const std::unordered_set<OatQuickMethodHeader*>& method_headers)
REQUIRES(Locks::cha_lock_);
// If a given class belongs to a linear allocation that is about to be deleted, in all its
// superclasses and superinterfaces reset SingleImplementation fields of their methods
// that might be affected by the deletion.
// The method is intended to be called during GC before ReclaimPhase, since it gets info from
// Java objects that are going to be collected.
// For the same reason it's important to access objects without read barrier to not revive them.
void ResetSingleImplementationInHierarchy(ObjPtr<mirror::Class> klass,
const LinearAlloc* alloc,
PointerSize pointer_size)
const REQUIRES_SHARED(Locks::mutator_lock_);
// Update CHA info for methods that `klass` overrides, after loading `klass`.
void UpdateAfterLoadingOf(Handle<mirror::Class> klass) REQUIRES_SHARED(Locks::mutator_lock_);
// Remove all of the dependencies for a linear allocator. This is called when dex cache unloading
// occurs.
void RemoveDependenciesForLinearAlloc(const LinearAlloc* linear_alloc)
REQUIRES(!Locks::cha_lock_);
private:
void InitSingleImplementationFlag(Handle<mirror::Class> klass,
ArtMethod* method,
PointerSize pointer_size)
REQUIRES_SHARED(Locks::mutator_lock_);
// Check/update single-implementation info when one virtual method
// overrides another.
// `virtual_method` in `klass` overrides `method_in_super`.
// This may invalidate some assumptions on single-implementation.
// Append methods that should have their single-implementation flag invalidated
// to `invalidated_single_impl_methods`.
void CheckVirtualMethodSingleImplementationInfo(
Handle<mirror::Class> klass,
ArtMethod* virtual_method,
ArtMethod* method_in_super,
std::unordered_set<ArtMethod*>& invalidated_single_impl_methods,
PointerSize pointer_size)
REQUIRES_SHARED(Locks::mutator_lock_);
// Check/update single-implementation info when one method
// implements an interface method.
// `implementation_method` in `klass` implements `interface_method`.
// Append `interface_method` to `invalidated_single_impl_methods`
// if `interface_method` gets a new implementation.
void CheckInterfaceMethodSingleImplementationInfo(
Handle<mirror::Class> klass,
ArtMethod* interface_method,
ArtMethod* implementation_method,
std::unordered_set<ArtMethod*>& invalidated_single_impl_methods,
PointerSize pointer_size)
REQUIRES_SHARED(Locks::mutator_lock_);
void InvalidateSingleImplementationMethods(
std::unordered_set<ArtMethod*>& invalidated_single_impl_methods)
REQUIRES_SHARED(Locks::mutator_lock_);
// A map that maps a method to a set of compiled code that assumes that method has a
// single implementation, which is used to do CHA-based devirtualization.
std::unordered_map<ArtMethod*, ListOfDependentPairs> cha_dependency_map_
GUARDED_BY(Locks::cha_lock_);
DISALLOW_COPY_AND_ASSIGN(ClassHierarchyAnalysis);
};
} // namespace art
#endif // ART_RUNTIME_CHA_H_
|
