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