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