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