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 #include "inliner.h"
18 
19 #include "art_method-inl.h"
20 #include "builder.h"
21 #include "class_linker.h"
22 #include "constant_folding.h"
23 #include "dead_code_elimination.h"
24 #include "driver/compiler_driver-inl.h"
25 #include "driver/compiler_options.h"
26 #include "driver/dex_compilation_unit.h"
27 #include "instruction_simplifier.h"
28 #include "mirror/class_loader.h"
29 #include "mirror/dex_cache.h"
30 #include "nodes.h"
31 #include "optimizing_compiler.h"
32 #include "register_allocator.h"
33 #include "ssa_phi_elimination.h"
34 #include "scoped_thread_state_change.h"
35 #include "thread.h"
36 #include "dex/verified_method.h"
37 #include "dex/verification_results.h"
38 
39 namespace art {
40 
Run()41 void HInliner::Run() {
42   const CompilerOptions& compiler_options = compiler_driver_->GetCompilerOptions();
43   if ((compiler_options.GetInlineDepthLimit() == 0)
44       || (compiler_options.GetInlineMaxCodeUnits() == 0)) {
45     return;
46   }
47   if (graph_->IsDebuggable()) {
48     // For simplicity, we currently never inline when the graph is debuggable. This avoids
49     // doing some logic in the runtime to discover if a method could have been inlined.
50     return;
51   }
52   const GrowableArray<HBasicBlock*>& blocks = graph_->GetReversePostOrder();
53   for (size_t i = 0; i < blocks.Size(); ++i) {
54     HBasicBlock* block = blocks.Get(i);
55     for (HInstruction* instruction = block->GetFirstInstruction(); instruction != nullptr;) {
56       HInstruction* next = instruction->GetNext();
57       HInvokeStaticOrDirect* call = instruction->AsInvokeStaticOrDirect();
58       // As long as the call is not intrinsified, it is worth trying to inline.
59       if (call != nullptr && call->GetIntrinsic() == Intrinsics::kNone) {
60         // We use the original invoke type to ensure the resolution of the called method
61         // works properly.
62         if (!TryInline(call, call->GetDexMethodIndex())) {
63           if (kIsDebugBuild && IsCompilingWithCoreImage()) {
64             std::string callee_name =
65                 PrettyMethod(call->GetDexMethodIndex(), *outer_compilation_unit_.GetDexFile());
66             bool should_inline = callee_name.find("$inline$") != std::string::npos;
67             CHECK(!should_inline) << "Could not inline " << callee_name;
68           }
69         }
70       }
71       instruction = next;
72     }
73   }
74 }
75 
TryInline(HInvoke * invoke_instruction,uint32_t method_index) const76 bool HInliner::TryInline(HInvoke* invoke_instruction, uint32_t method_index) const {
77   ScopedObjectAccess soa(Thread::Current());
78   const DexFile& caller_dex_file = *caller_compilation_unit_.GetDexFile();
79   VLOG(compiler) << "Try inlining " << PrettyMethod(method_index, caller_dex_file);
80 
81   ClassLinker* class_linker = caller_compilation_unit_.GetClassLinker();
82   // We can query the dex cache directly. The verifier has populated it already.
83   ArtMethod* resolved_method = class_linker->FindDexCache(caller_dex_file)->GetResolvedMethod(
84       method_index, class_linker->GetImagePointerSize());
85 
86   if (resolved_method == nullptr) {
87     // Method cannot be resolved if it is in another dex file we do not have access to.
88     VLOG(compiler) << "Method cannot be resolved " << PrettyMethod(method_index, caller_dex_file);
89     return false;
90   }
91 
92   bool can_use_dex_cache = true;
93   const DexFile& outer_dex_file = *outer_compilation_unit_.GetDexFile();
94   if (resolved_method->GetDexFile()->GetLocation().compare(outer_dex_file.GetLocation()) != 0) {
95     can_use_dex_cache = false;
96   }
97 
98   const DexFile::CodeItem* code_item = resolved_method->GetCodeItem();
99 
100   if (code_item == nullptr) {
101     VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
102                    << " is not inlined because it is native";
103     return false;
104   }
105 
106   size_t inline_max_code_units = compiler_driver_->GetCompilerOptions().GetInlineMaxCodeUnits();
107   if (code_item->insns_size_in_code_units_ > inline_max_code_units) {
108     VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
109                    << " is too big to inline";
110     return false;
111   }
112 
113   if (code_item->tries_size_ != 0) {
114     VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
115                    << " is not inlined because of try block";
116     return false;
117   }
118 
119   uint16_t class_def_idx = resolved_method->GetDeclaringClass()->GetDexClassDefIndex();
120   if (!compiler_driver_->IsMethodVerifiedWithoutFailures(
121         resolved_method->GetDexMethodIndex(), class_def_idx, *resolved_method->GetDexFile())) {
122     VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
123                    << " couldn't be verified, so it cannot be inlined";
124     return false;
125   }
126 
127   if (resolved_method->ShouldNotInline()) {
128     VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
129                    << " was already flagged as non inlineable";
130     return false;
131   }
132 
133   if (invoke_instruction->IsInvokeStaticOrDirect() &&
134       invoke_instruction->AsInvokeStaticOrDirect()->IsStaticWithImplicitClinitCheck()) {
135     // Case of a static method that cannot be inlined because it implicitly
136     // requires an initialization check of its declaring class.
137     VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
138                    << " is not inlined because it is static and requires a clinit"
139                    << " check that cannot be emitted due to Dex cache limitations";
140     return false;
141   }
142 
143   if (!TryBuildAndInline(resolved_method, invoke_instruction, method_index, can_use_dex_cache)) {
144     return false;
145   }
146 
147   VLOG(compiler) << "Successfully inlined " << PrettyMethod(method_index, caller_dex_file);
148   MaybeRecordStat(kInlinedInvoke);
149   return true;
150 }
151 
TryBuildAndInline(ArtMethod * resolved_method,HInvoke * invoke_instruction,uint32_t method_index,bool can_use_dex_cache) const152 bool HInliner::TryBuildAndInline(ArtMethod* resolved_method,
153                                  HInvoke* invoke_instruction,
154                                  uint32_t method_index,
155                                  bool can_use_dex_cache) const {
156   ScopedObjectAccess soa(Thread::Current());
157   const DexFile::CodeItem* code_item = resolved_method->GetCodeItem();
158   const DexFile& caller_dex_file = *caller_compilation_unit_.GetDexFile();
159 
160   DexCompilationUnit dex_compilation_unit(
161     nullptr,
162     caller_compilation_unit_.GetClassLoader(),
163     caller_compilation_unit_.GetClassLinker(),
164     *resolved_method->GetDexFile(),
165     code_item,
166     resolved_method->GetDeclaringClass()->GetDexClassDefIndex(),
167     resolved_method->GetDexMethodIndex(),
168     resolved_method->GetAccessFlags(),
169     nullptr);
170 
171   HGraph* callee_graph = new (graph_->GetArena()) HGraph(
172       graph_->GetArena(),
173       caller_dex_file,
174       method_index,
175       compiler_driver_->GetInstructionSet(),
176       graph_->IsDebuggable(),
177       graph_->GetCurrentInstructionId());
178 
179   OptimizingCompilerStats inline_stats;
180   HGraphBuilder builder(callee_graph,
181                         &dex_compilation_unit,
182                         &outer_compilation_unit_,
183                         resolved_method->GetDexFile(),
184                         compiler_driver_,
185                         &inline_stats);
186 
187   if (!builder.BuildGraph(*code_item)) {
188     VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
189                    << " could not be built, so cannot be inlined";
190     // There could be multiple reasons why the graph could not be built, including
191     // unaccessible methods/fields due to using a different dex cache. We do not mark
192     // the method as non-inlineable so that other callers can still try to inline it.
193     return false;
194   }
195 
196   if (!RegisterAllocator::CanAllocateRegistersFor(*callee_graph,
197                                                   compiler_driver_->GetInstructionSet())) {
198     VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
199                    << " cannot be inlined because of the register allocator";
200     resolved_method->SetShouldNotInline();
201     return false;
202   }
203 
204   if (!callee_graph->TryBuildingSsa()) {
205     VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
206                    << " could not be transformed to SSA";
207     resolved_method->SetShouldNotInline();
208     return false;
209   }
210 
211   // Run simple optimizations on the graph.
212   HDeadCodeElimination dce(callee_graph, stats_);
213   HConstantFolding fold(callee_graph);
214   InstructionSimplifier simplify(callee_graph, stats_);
215 
216   HOptimization* optimizations[] = {
217     &dce,
218     &fold,
219     &simplify,
220   };
221 
222   for (size_t i = 0; i < arraysize(optimizations); ++i) {
223     HOptimization* optimization = optimizations[i];
224     optimization->Run();
225   }
226 
227   if (depth_ + 1 < compiler_driver_->GetCompilerOptions().GetInlineDepthLimit()) {
228     HInliner inliner(callee_graph,
229                      outer_compilation_unit_,
230                      dex_compilation_unit,
231                      compiler_driver_,
232                      stats_,
233                      depth_ + 1);
234     inliner.Run();
235   }
236 
237   HReversePostOrderIterator it(*callee_graph);
238   it.Advance();  // Past the entry block, it does not contain instructions that prevent inlining.
239   for (; !it.Done(); it.Advance()) {
240     HBasicBlock* block = it.Current();
241     if (block->IsLoopHeader()) {
242       VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
243                      << " could not be inlined because it contains a loop";
244       resolved_method->SetShouldNotInline();
245       return false;
246     }
247 
248     for (HInstructionIterator instr_it(block->GetInstructions());
249          !instr_it.Done();
250          instr_it.Advance()) {
251       HInstruction* current = instr_it.Current();
252       if (current->IsSuspendCheck()) {
253         continue;
254       }
255 
256       if (current->CanThrow()) {
257         VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
258                        << " could not be inlined because " << current->DebugName()
259                        << " can throw";
260         return false;
261       }
262 
263       if (current->NeedsEnvironment()) {
264         VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
265                        << " could not be inlined because " << current->DebugName()
266                        << " needs an environment";
267         return false;
268       }
269 
270       if (!can_use_dex_cache && current->NeedsDexCache()) {
271         VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file)
272                        << " could not be inlined because " << current->DebugName()
273                        << " it is in a different dex file and requires access to the dex cache";
274         // Do not flag the method as not-inlineable. A caller within the same
275         // dex file could still successfully inline it.
276         return false;
277       }
278     }
279   }
280 
281   callee_graph->InlineInto(graph_, invoke_instruction);
282 
283   if (callee_graph->HasBoundsChecks()) {
284     graph_->SetHasBoundsChecks(true);
285   }
286 
287   return true;
288 }
289 
290 }  // namespace art
291