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