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