• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
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 
20 #include <unordered_map>
21 #include <unordered_set>
22 
23 #include "base/enums.h"
24 #include "base/locks.h"
25 #include "handle.h"
26 #include "mirror/class.h"
27 #include "oat_quick_method_header.h"
28 
29 namespace art {
30 
31 class ArtMethod;
32 class LinearAlloc;
33 
34 /**
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  */
80 class 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 
ClassHierarchyAnalysis()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.
100   const ListOfDependentPairs& GetDependents(ArtMethod* method) REQUIRES(Locks::cha_lock_);
101 
102   // Remove dependency tracking for compiled code that assumes that
103   // `method` has single-implementation.
104   void RemoveAllDependenciesFor(ArtMethod* method) REQUIRES(Locks::cha_lock_);
105 
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 
113   // 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 
124   // Update CHA info for methods that `klass` overrides, after loading `klass`.
125   void UpdateAfterLoadingOf(Handle<mirror::Class> klass) REQUIRES_SHARED(Locks::mutator_lock_);
126 
127   // 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 
132  private:
133   void InitSingleImplementationFlag(Handle<mirror::Class> klass,
134                                     ArtMethod* method,
135                                     PointerSize pointer_size)
136       REQUIRES_SHARED(Locks::mutator_lock_);
137 
138   // Check/update single-implementation info when one virtual method
139   // overrides another.
140   // `virtual_method` in `klass` overrides `method_in_super`.
141   // This may invalidate some assumptions on single-implementation.
142   // Append methods that should have their single-implementation flag invalidated
143   // to `invalidated_single_impl_methods`.
144   void CheckVirtualMethodSingleImplementationInfo(
145       Handle<mirror::Class> klass,
146       ArtMethod* virtual_method,
147       ArtMethod* method_in_super,
148       std::unordered_set<ArtMethod*>& invalidated_single_impl_methods,
149       PointerSize pointer_size)
150       REQUIRES_SHARED(Locks::mutator_lock_);
151 
152   // 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 
169   // 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.
171   std::unordered_map<ArtMethod*, ListOfDependentPairs> cha_dependency_map_
172     GUARDED_BY(Locks::cha_lock_);
173 
174   DISALLOW_COPY_AND_ASSIGN(ClassHierarchyAnalysis);
175 };
176 
177 }  // namespace art
178 
179 #endif  // ART_RUNTIME_CHA_H_
180