1 /* 2 * Copyright (C) 2014 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_COMPILER_OPTIMIZING_INLINER_H_ 18 #define ART_COMPILER_OPTIMIZING_INLINER_H_ 19 20 #include "base/macros.h" 21 #include "dex/dex_file_types.h" 22 #include "dex/invoke_type.h" 23 #include "jit/profiling_info.h" 24 #include "optimization.h" 25 #include "profile/profile_compilation_info.h" 26 27 namespace art HIDDEN { 28 29 class CodeGenerator; 30 class DexCompilationUnit; 31 class HGraph; 32 class HInvoke; 33 class OptimizingCompilerStats; 34 35 class HInliner : public HOptimization { 36 public: 37 HInliner(HGraph* outer_graph, 38 HGraph* outermost_graph, 39 CodeGenerator* codegen, 40 const DexCompilationUnit& outer_compilation_unit, 41 const DexCompilationUnit& caller_compilation_unit, 42 OptimizingCompilerStats* stats, 43 size_t total_number_of_dex_registers, 44 size_t total_number_of_instructions, 45 HInliner* parent, 46 size_t depth, 47 bool try_catch_inlining_allowed, 48 const char* name = kInlinerPassName) HOptimization(outer_graph,name,stats)49 : HOptimization(outer_graph, name, stats), 50 outermost_graph_(outermost_graph), 51 outer_compilation_unit_(outer_compilation_unit), 52 caller_compilation_unit_(caller_compilation_unit), 53 codegen_(codegen), 54 total_number_of_dex_registers_(total_number_of_dex_registers), 55 total_number_of_instructions_(total_number_of_instructions), 56 parent_(parent), 57 depth_(depth), 58 inlining_budget_(0), 59 try_catch_inlining_allowed_(try_catch_inlining_allowed), 60 inline_stats_(nullptr) {} 61 62 bool Run() override; 63 64 static constexpr const char* kInlinerPassName = "inliner"; 65 66 private: 67 enum InlineCacheType { 68 kInlineCacheNoData = 0, 69 kInlineCacheUninitialized = 1, 70 kInlineCacheMonomorphic = 2, 71 kInlineCachePolymorphic = 3, 72 kInlineCacheMegamorphic = 4, 73 kInlineCacheMissingTypes = 5 74 }; 75 76 bool TryInline(HInvoke* invoke_instruction); 77 78 // Try to inline `resolved_method` in place of `invoke_instruction`. `do_rtp` is whether 79 // reference type propagation can run after the inlining. If the inlining is successful, this 80 // method will replace and remove the `invoke_instruction`. 81 bool TryInlineAndReplace(HInvoke* invoke_instruction, 82 ArtMethod* resolved_method, 83 ReferenceTypeInfo receiver_type, 84 bool do_rtp, 85 bool is_speculative) 86 REQUIRES_SHARED(Locks::mutator_lock_); 87 88 bool TryBuildAndInline(HInvoke* invoke_instruction, 89 ArtMethod* resolved_method, 90 ReferenceTypeInfo receiver_type, 91 HInstruction** return_replacement, 92 bool is_speculative) 93 REQUIRES_SHARED(Locks::mutator_lock_); 94 95 bool TryBuildAndInlineHelper(HInvoke* invoke_instruction, 96 ArtMethod* resolved_method, 97 ReferenceTypeInfo receiver_type, 98 HInstruction** return_replacement, 99 bool is_speculative) 100 REQUIRES_SHARED(Locks::mutator_lock_); 101 102 // Substitutes parameters in the callee graph with their values from the caller. 103 void SubstituteArguments(HGraph* callee_graph, 104 HInvoke* invoke_instruction, 105 ReferenceTypeInfo receiver_type, 106 const DexCompilationUnit& dex_compilation_unit) 107 REQUIRES_SHARED(Locks::mutator_lock_); 108 109 // Run simple optimizations on `callee_graph`. 110 void RunOptimizations(HGraph* callee_graph, 111 const dex::CodeItem* code_item, 112 const DexCompilationUnit& dex_compilation_unit, 113 bool try_catch_inlining_allowed_for_recursive_inline) 114 REQUIRES_SHARED(Locks::mutator_lock_); 115 116 // Try to recognize known simple patterns and replace invoke call with appropriate instructions. 117 bool TryPatternSubstitution(HInvoke* invoke_instruction, 118 ArtMethod* method, 119 HInstruction** return_replacement) 120 REQUIRES_SHARED(Locks::mutator_lock_); 121 122 // Returns whether inlining is allowed based on ART semantics. 123 bool IsInliningAllowed(art::ArtMethod* method, const CodeItemDataAccessor& accessor) const 124 REQUIRES_SHARED(Locks::mutator_lock_); 125 126 127 // Returns whether ART supports inlining this method. 128 // 129 // Some methods are not supported because they have features for which inlining 130 // is not implemented. For example, we do not currently support inlining throw 131 // instructions into a try block. 132 bool IsInliningSupported(const HInvoke* invoke_instruction, 133 art::ArtMethod* method, 134 const CodeItemDataAccessor& accessor) const 135 REQUIRES_SHARED(Locks::mutator_lock_); 136 137 // Returns whether inlining is encouraged. 138 // 139 // For example, this checks whether the function has grown too large and 140 // inlining should be prevented. 141 bool IsInliningEncouraged(const HInvoke* invoke_instruction, 142 art::ArtMethod* method, 143 const CodeItemDataAccessor& accessor) const 144 REQUIRES_SHARED(Locks::mutator_lock_); 145 146 // Inspects the body of a method (callee_graph) and returns whether it can be 147 // inlined. 148 // 149 // This checks for instructions and constructs that we do not support 150 // inlining, such as inlining a throw instruction into a try block. 151 bool CanInlineBody(const HGraph* callee_graph, 152 HInvoke* invoke, 153 size_t* out_number_of_instructions, 154 bool is_speculative) const 155 REQUIRES_SHARED(Locks::mutator_lock_); 156 157 // Create a new HInstanceFieldGet. 158 HInstanceFieldGet* CreateInstanceFieldGet(uint32_t field_index, 159 ArtMethod* referrer, 160 HInstruction* obj); 161 // Create a new HInstanceFieldSet. 162 HInstanceFieldSet* CreateInstanceFieldSet(uint32_t field_index, 163 ArtMethod* referrer, 164 HInstruction* obj, 165 HInstruction* value, 166 bool* is_final = nullptr); 167 168 // Try inlining the invoke instruction using inline caches. 169 bool TryInlineFromInlineCache(HInvoke* invoke_instruction) 170 REQUIRES_SHARED(Locks::mutator_lock_); 171 172 // Try inlining the invoke instruction using CHA. 173 bool TryInlineFromCHA(HInvoke* invoke_instruction) 174 REQUIRES_SHARED(Locks::mutator_lock_); 175 176 // When we fail inlining `invoke_instruction`, we will try to devirtualize the 177 // call. 178 bool TryDevirtualize(HInvoke* invoke_instruction, 179 ArtMethod* method, 180 HInvoke** replacement) 181 REQUIRES_SHARED(Locks::mutator_lock_); 182 183 // Try getting the inline cache from JIT code cache. 184 // Return true if the inline cache was successfully allocated and the 185 // invoke info was found in the profile info. 186 InlineCacheType GetInlineCacheJIT( 187 HInvoke* invoke_instruction, 188 /*out*/StackHandleScope<InlineCache::kIndividualCacheSize>* classes) 189 REQUIRES_SHARED(Locks::mutator_lock_); 190 191 // Try getting the inline cache from AOT offline profile. 192 // Return true if the inline cache was successfully allocated and the 193 // invoke info was found in the profile info. 194 InlineCacheType GetInlineCacheAOT( 195 HInvoke* invoke_instruction, 196 /*out*/StackHandleScope<InlineCache::kIndividualCacheSize>* classes) 197 REQUIRES_SHARED(Locks::mutator_lock_); 198 199 // Compute the inline cache type. 200 static InlineCacheType GetInlineCacheType( 201 const StackHandleScope<InlineCache::kIndividualCacheSize>& classes) 202 REQUIRES_SHARED(Locks::mutator_lock_); 203 204 // Try to inline the target of a monomorphic call. If successful, the code 205 // in the graph will look like: 206 // if (receiver.getClass() != ic.GetMonomorphicType()) deopt 207 // ... // inlined code 208 bool TryInlineMonomorphicCall(HInvoke* invoke_instruction, 209 const StackHandleScope<InlineCache::kIndividualCacheSize>& classes) 210 REQUIRES_SHARED(Locks::mutator_lock_); 211 212 // Try to inline targets of a polymorphic call. 213 bool TryInlinePolymorphicCall(HInvoke* invoke_instruction, 214 const StackHandleScope<InlineCache::kIndividualCacheSize>& classes) 215 REQUIRES_SHARED(Locks::mutator_lock_); 216 217 bool TryInlinePolymorphicCallToSameTarget( 218 HInvoke* invoke_instruction, 219 const StackHandleScope<InlineCache::kIndividualCacheSize>& classes) 220 REQUIRES_SHARED(Locks::mutator_lock_); 221 222 // Returns whether or not we should use only polymorphic inlining with no deoptimizations. 223 bool UseOnlyPolymorphicInliningWithNoDeopt(); 224 225 // Try CHA-based devirtualization to change virtual method calls into 226 // direct calls. 227 // Returns the actual method that resolved_method can be devirtualized to. 228 ArtMethod* FindMethodFromCHA(ArtMethod* resolved_method) 229 REQUIRES_SHARED(Locks::mutator_lock_); 230 231 // Add a CHA guard for a CHA-based devirtualized call. A CHA guard checks a 232 // should_deoptimize flag and if it's true, does deoptimization. 233 void AddCHAGuard(HInstruction* invoke_instruction, 234 uint32_t dex_pc, 235 HInstruction* cursor, 236 HBasicBlock* bb_cursor); 237 238 HInstanceFieldGet* BuildGetReceiverClass(ClassLinker* class_linker, 239 HInstruction* receiver, 240 uint32_t dex_pc) const 241 REQUIRES_SHARED(Locks::mutator_lock_); 242 243 void MaybeRunReferenceTypePropagation(HInstruction* replacement, 244 HInvoke* invoke_instruction) 245 REQUIRES_SHARED(Locks::mutator_lock_); 246 247 void FixUpReturnReferenceType(ArtMethod* resolved_method, HInstruction* return_replacement) 248 REQUIRES_SHARED(Locks::mutator_lock_); 249 250 bool ArgumentTypesMoreSpecific(HInvoke* invoke_instruction, ArtMethod* resolved_method) 251 REQUIRES_SHARED(Locks::mutator_lock_); 252 253 bool ReturnTypeMoreSpecific(HInstruction* return_replacement, HInvoke* invoke_instruction) 254 REQUIRES_SHARED(Locks::mutator_lock_); 255 256 // Add a type guard on the given `receiver`. This will add to the graph: 257 // i0 = HFieldGet(receiver, klass) 258 // i1 = HLoadClass(class_index, is_referrer) 259 // i2 = HNotEqual(i0, i1) 260 // 261 // And if `with_deoptimization` is true: 262 // HDeoptimize(i2) 263 // 264 // The method returns the `HNotEqual`, that will be used for polymorphic inlining. 265 HInstruction* AddTypeGuard(HInstruction* receiver, 266 HInstruction* cursor, 267 HBasicBlock* bb_cursor, 268 dex::TypeIndex class_index, 269 Handle<mirror::Class> klass, 270 HInstruction* invoke_instruction, 271 bool with_deoptimization) 272 REQUIRES_SHARED(Locks::mutator_lock_); 273 274 /* 275 * Ad-hoc implementation for implementing a diamond pattern in the graph for 276 * polymorphic inlining: 277 * 1) `compare` becomes the input of the new `HIf`. 278 * 2) Everything up until `invoke_instruction` is in the then branch (could 279 * contain multiple blocks). 280 * 3) `invoke_instruction` is moved to the otherwise block. 281 * 4) If `return_replacement` is not null, the merge block will have 282 * a phi whose inputs are `return_replacement` and `invoke_instruction`. 283 * 284 * Before: 285 * Block1 286 * compare 287 * ... 288 * invoke_instruction 289 * 290 * After: 291 * Block1 292 * compare 293 * if 294 * / \ 295 * / \ 296 * Then block Otherwise block 297 * ... invoke_instruction 298 * \ / 299 * \ / 300 * Merge block 301 * phi(return_replacement, invoke_instruction) 302 */ 303 void CreateDiamondPatternForPolymorphicInline(HInstruction* compare, 304 HInstruction* return_replacement, 305 HInstruction* invoke_instruction); 306 307 // Update the inlining budget based on `total_number_of_instructions_`. 308 void UpdateInliningBudget(); 309 310 // Count the number of calls of `method` being inlined recursively. 311 size_t CountRecursiveCallsOf(ArtMethod* method) const; 312 313 // Pretty-print for spaces during logging. 314 std::string DepthString(int line) const; 315 316 HGraph* const outermost_graph_; 317 const DexCompilationUnit& outer_compilation_unit_; 318 const DexCompilationUnit& caller_compilation_unit_; 319 CodeGenerator* const codegen_; 320 const size_t total_number_of_dex_registers_; 321 size_t total_number_of_instructions_; 322 323 // The 'parent' inliner, that means the inlinigng optimization that requested 324 // `graph_` to be inlined. 325 const HInliner* const parent_; 326 const size_t depth_; 327 328 // The budget left for inlining, in number of instructions. 329 size_t inlining_budget_; 330 331 // States if we are allowing try catch inlining to occur at this particular instance of inlining. 332 bool try_catch_inlining_allowed_; 333 334 // Used to record stats about optimizations on the inlined graph. 335 // If the inlining is successful, these stats are merged to the caller graph's stats. 336 OptimizingCompilerStats* inline_stats_; 337 338 DISALLOW_COPY_AND_ASSIGN(HInliner); 339 }; 340 341 } // namespace art 342 343 #endif // ART_COMPILER_OPTIMIZING_INLINER_H_ 344