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