1 /*
2  * Copyright (C) 2013 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_DEX_QUICK_DEX_FILE_METHOD_INLINER_H_
18 #define ART_COMPILER_DEX_QUICK_DEX_FILE_METHOD_INLINER_H_
19 
20 #include <stdint.h>
21 #include "base/mutex.h"
22 #include "base/macros.h"
23 #include "safe_map.h"
24 #include "dex/compiler_enums.h"
25 #include "dex_file.h"
26 #include "quick/inline_method_analyser.h"
27 
28 namespace art {
29 
30 namespace verifier {
31 class MethodVerifier;
32 }  // namespace verifier
33 
34 class BasicBlock;
35 struct CallInfo;
36 class MIR;
37 class MIRGraph;
38 class Mir2Lir;
39 
40 /**
41  * Handles inlining of methods from a particular DexFile.
42  *
43  * Intrinsics are a special case of inline methods. The DexFile indices for
44  * all the supported intrinsic methods are looked up once by the FindIntrinsics
45  * function and cached by this class for quick lookup by the method index.
46  *
47  * TODO: Detect short methods (at least getters, setters and empty functions)
48  * from the verifier and mark them for inlining. Inline these methods early
49  * during compilation to allow further optimizations. Similarly, provide
50  * additional information about intrinsics to the early phases of compilation.
51  */
52 class DexFileMethodInliner {
53   public:
54     DexFileMethodInliner();
55     ~DexFileMethodInliner();
56 
57     /**
58      * Analyse method code to determine if the method is a candidate for inlining.
59      * If it is, record its data for later.
60      *
61      * @param verifier the method verifier holding data about the method to analyse.
62      * @return true if the method is a candidate for inlining, false otherwise.
63      */
64     bool AnalyseMethodCode(verifier::MethodVerifier* verifier)
65         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) LOCKS_EXCLUDED(lock_);
66 
67     /**
68      * Check whether a particular method index corresponds to an intrinsic or special function.
69      */
70     InlineMethodFlags IsIntrinsicOrSpecial(uint32_t method_index) LOCKS_EXCLUDED(lock_);
71 
72     /**
73      * Check whether a particular method index corresponds to an intrinsic function.
74      */
75     bool IsIntrinsic(uint32_t method_index, InlineMethod* intrinsic) LOCKS_EXCLUDED(lock_);
76 
77     /**
78      * Generate code for an intrinsic function invocation.
79      */
80     bool GenIntrinsic(Mir2Lir* backend, CallInfo* info) LOCKS_EXCLUDED(lock_);
81 
82     /**
83      * Check whether a particular method index corresponds to a special function.
84      */
85     bool IsSpecial(uint32_t method_index) LOCKS_EXCLUDED(lock_);
86 
87     /**
88      * Generate code for a special function.
89      */
90     bool GenSpecial(Mir2Lir* backend, uint32_t method_idx) LOCKS_EXCLUDED(lock_);
91 
92     /**
93      * Try to inline an invoke.
94      */
95     bool GenInline(MIRGraph* mir_graph, BasicBlock* bb, MIR* invoke, uint32_t method_idx)
96         LOCKS_EXCLUDED(lock_);
97 
98     /**
99      * Gets the thread pointer entrypoint offset for a string init method index and pointer size.
100      */
101     uint32_t GetOffsetForStringInit(uint32_t method_index, size_t pointer_size)
102         LOCKS_EXCLUDED(lock_);
103 
104     /**
105      * Check whether a particular method index is a string init.
106      */
107     bool IsStringInitMethodIndex(uint32_t method_index) LOCKS_EXCLUDED(lock_);
108 
109     /**
110      * To avoid multiple lookups of a class by its descriptor, we cache its
111      * type index in the IndexCache. These are the indexes into the IndexCache
112      * class_indexes array.
113      */
114     enum ClassCacheIndex : uint8_t {  // unit8_t to save space, make larger if needed
115       kClassCacheFirst = 0,
116       kClassCacheBoolean = kClassCacheFirst,
117       kClassCacheByte,
118       kClassCacheChar,
119       kClassCacheShort,
120       kClassCacheInt,
121       kClassCacheLong,
122       kClassCacheFloat,
123       kClassCacheDouble,
124       kClassCacheVoid,
125       kClassCacheJavaLangByteArray,
126       kClassCacheJavaLangCharArray,
127       kClassCacheJavaLangIntArray,
128       kClassCacheJavaLangObject,
129       kClassCacheJavaLangRefReference,
130       kClassCacheJavaLangString,
131       kClassCacheJavaLangStringBuffer,
132       kClassCacheJavaLangStringBuilder,
133       kClassCacheJavaLangStringFactory,
134       kClassCacheJavaLangDouble,
135       kClassCacheJavaLangFloat,
136       kClassCacheJavaLangInteger,
137       kClassCacheJavaLangLong,
138       kClassCacheJavaLangShort,
139       kClassCacheJavaLangMath,
140       kClassCacheJavaLangStrictMath,
141       kClassCacheJavaLangThread,
142       kClassCacheJavaNioCharsetCharset,
143       kClassCacheLibcoreIoMemory,
144       kClassCacheSunMiscUnsafe,
145       kClassCacheJavaLangSystem,
146       kClassCacheLast
147     };
148 
149     /**
150      * To avoid multiple lookups of a method name string, we cache its string
151      * index in the IndexCache. These are the indexes into the IndexCache
152      * name_indexes array.
153      */
154     enum NameCacheIndex : uint8_t {  // unit8_t to save space, make larger if needed
155       kNameCacheFirst = 0,
156       kNameCacheReverse =  kNameCacheFirst,
157       kNameCacheReverseBytes,
158       kNameCacheDoubleToRawLongBits,
159       kNameCacheLongBitsToDouble,
160       kNameCacheFloatToRawIntBits,
161       kNameCacheIntBitsToFloat,
162       kNameCacheAbs,
163       kNameCacheMax,
164       kNameCacheMin,
165       kNameCacheSqrt,
166       kNameCacheCeil,
167       kNameCacheFloor,
168       kNameCacheRint,
169       kNameCacheRound,
170       kNameCacheReferenceGetReferent,
171       kNameCacheCharAt,
172       kNameCacheCompareTo,
173       kNameCacheGetCharsNoCheck,
174       kNameCacheIsEmpty,
175       kNameCacheIndexOf,
176       kNameCacheLength,
177       kNameCacheInit,
178       kNameCacheNewStringFromBytes,
179       kNameCacheNewStringFromChars,
180       kNameCacheNewStringFromString,
181       kNameCacheCurrentThread,
182       kNameCachePeekByte,
183       kNameCachePeekIntNative,
184       kNameCachePeekLongNative,
185       kNameCachePeekShortNative,
186       kNameCachePokeByte,
187       kNameCachePokeIntNative,
188       kNameCachePokeLongNative,
189       kNameCachePokeShortNative,
190       kNameCacheCompareAndSwapInt,
191       kNameCacheCompareAndSwapLong,
192       kNameCacheCompareAndSwapObject,
193       kNameCacheGetInt,
194       kNameCacheGetIntVolatile,
195       kNameCachePutInt,
196       kNameCachePutIntVolatile,
197       kNameCachePutOrderedInt,
198       kNameCacheGetLong,
199       kNameCacheGetLongVolatile,
200       kNameCachePutLong,
201       kNameCachePutLongVolatile,
202       kNameCachePutOrderedLong,
203       kNameCacheGetObject,
204       kNameCacheGetObjectVolatile,
205       kNameCachePutObject,
206       kNameCachePutObjectVolatile,
207       kNameCachePutOrderedObject,
208       kNameCacheArrayCopy,
209       kNameCacheLast
210     };
211 
212     /**
213      * To avoid multiple lookups of a method signature, we cache its proto
214      * index in the IndexCache. These are the indexes into the IndexCache
215      * proto_indexes array.
216      */
217     enum ProtoCacheIndex : uint8_t {  // unit8_t to save space, make larger if needed
218       kProtoCacheFirst = 0,
219       kProtoCacheI_I = kProtoCacheFirst,
220       kProtoCacheJ_J,
221       kProtoCacheS_S,
222       kProtoCacheD_D,
223       kProtoCacheDD_D,
224       kProtoCacheF_F,
225       kProtoCacheFF_F,
226       kProtoCacheD_J,
227       kProtoCacheJ_D,
228       kProtoCacheF_I,
229       kProtoCacheI_F,
230       kProtoCacheII_I,
231       kProtoCacheI_C,
232       kProtoCacheString_I,
233       kProtoCache_Z,
234       kProtoCache_I,
235       kProtoCache_Object,
236       kProtoCache_Thread,
237       kProtoCacheJ_B,
238       kProtoCacheJ_I,
239       kProtoCacheJ_S,
240       kProtoCacheJB_V,
241       kProtoCacheJI_V,
242       kProtoCacheJJ_J,
243       kProtoCacheJJ_V,
244       kProtoCacheJS_V,
245       kProtoCacheObjectJII_Z,
246       kProtoCacheObjectJJJ_Z,
247       kProtoCacheObjectJObjectObject_Z,
248       kProtoCacheObjectJ_I,
249       kProtoCacheObjectJI_V,
250       kProtoCacheObjectJ_J,
251       kProtoCacheObjectJJ_V,
252       kProtoCacheObjectJ_Object,
253       kProtoCacheObjectJObject_V,
254       kProtoCacheCharArrayICharArrayII_V,
255       kProtoCacheIICharArrayI_V,
256       kProtoCacheByteArrayIII_String,
257       kProtoCacheIICharArray_String,
258       kProtoCacheString_String,
259       kProtoCache_V,
260       kProtoCacheByteArray_V,
261       kProtoCacheByteArrayI_V,
262       kProtoCacheByteArrayII_V,
263       kProtoCacheByteArrayIII_V,
264       kProtoCacheByteArrayIIString_V,
265       kProtoCacheByteArrayString_V,
266       kProtoCacheByteArrayIICharset_V,
267       kProtoCacheByteArrayCharset_V,
268       kProtoCacheCharArray_V,
269       kProtoCacheCharArrayII_V,
270       kProtoCacheIICharArray_V,
271       kProtoCacheIntArrayII_V,
272       kProtoCacheString_V,
273       kProtoCacheStringBuffer_V,
274       kProtoCacheStringBuilder_V,
275       kProtoCacheLast
276     };
277 
278   private:
279     /**
280      * The maximum number of method parameters we support in the ProtoDef.
281      */
282     static constexpr uint32_t kProtoMaxParams = 6;
283 
284     /**
285      * The method signature (proto) definition using cached class indexes.
286      * The return_type and params are used with the IndexCache to look up
287      * appropriate class indexes to be passed to DexFile::FindProtoId().
288      */
289     struct ProtoDef {
290       ClassCacheIndex return_type;
291       uint8_t param_count;
292       ClassCacheIndex params[kProtoMaxParams];
293     };
294 
295     /**
296      * The method definition using cached class, name and proto indexes.
297      * The class index, method name index and proto index are used with
298      * IndexCache to look up appropriate parameters for DexFile::FindMethodId().
299      */
300     struct MethodDef {
301       ClassCacheIndex declaring_class;
302       NameCacheIndex name;
303       ProtoCacheIndex proto;
304     };
305 
306     /**
307      * The definition of an intrinsic function binds the method definition
308      * to an Intrinsic.
309      */
310     struct IntrinsicDef {
311       MethodDef method_def;
312       InlineMethod intrinsic;
313     };
314 
315     /**
316      * Cache for class, method name and method signature indexes used during
317      * intrinsic function lookup to avoid multiple lookups of the same items.
318      *
319      * Many classes have multiple intrinsics and/or they are used in multiple
320      * method signatures and we want to avoid repeated lookups since they are
321      * not exactly cheap. The method names and method signatures are sometimes
322      * reused and therefore cached as well.
323      */
324     struct IndexCache {
325       IndexCache();
326 
327       uint32_t class_indexes[kClassCacheLast - kClassCacheFirst];
328       uint32_t name_indexes[kNameCacheLast - kNameCacheFirst];
329       uint32_t proto_indexes[kProtoCacheLast - kProtoCacheFirst];
330     };
331 
332     static const char* const kClassCacheNames[];
333     static const char* const kNameCacheNames[];
334     static const ProtoDef kProtoCacheDefs[];
335     static const IntrinsicDef kIntrinsicMethods[];
336 
337     static const uint32_t kIndexNotFound = static_cast<uint32_t>(-1);
338     static const uint32_t kIndexUnresolved = static_cast<uint32_t>(-2);
339 
340     static uint32_t FindClassIndex(const DexFile* dex_file, IndexCache* cache,
341                                    ClassCacheIndex index);
342     static uint32_t FindNameIndex(const DexFile* dex_file, IndexCache* cache,
343                                   NameCacheIndex index);
344     static uint32_t FindProtoIndex(const DexFile* dex_file, IndexCache* cache,
345                                    ProtoCacheIndex index);
346     static uint32_t FindMethodIndex(const DexFile* dex_file, IndexCache* cache,
347                                     const MethodDef& method_def);
348 
349     /**
350      * Find all known intrinsic methods in the dex_file and cache their indices.
351      *
352      * Only DexFileToMethodInlinerMap may call this function to initialize the inliner.
353      */
354     void FindIntrinsics(const DexFile* dex_file) EXCLUSIVE_LOCKS_REQUIRED(lock_);
355 
356     friend class DexFileToMethodInlinerMap;
357 
358     bool AddInlineMethod(int32_t method_idx, const InlineMethod& method) LOCKS_EXCLUDED(lock_);
359 
360     static bool GenInlineConst(MIRGraph* mir_graph, BasicBlock* bb, MIR* invoke,
361                                MIR* move_result, const InlineMethod& method);
362     static bool GenInlineReturnArg(MIRGraph* mir_graph, BasicBlock* bb, MIR* invoke,
363                                    MIR* move_result, const InlineMethod& method);
364     static bool GenInlineIGet(MIRGraph* mir_graph, BasicBlock* bb, MIR* invoke,
365                               MIR* move_result, const InlineMethod& method);
366     static bool GenInlineIPut(MIRGraph* mir_graph, BasicBlock* bb, MIR* invoke,
367                               MIR* move_result, const InlineMethod& method);
368 
369     ReaderWriterMutex lock_;
370     /*
371      * Maps method indexes (for the particular DexFile) to Intrinsic defintions.
372      */
373     SafeMap<uint32_t, InlineMethod> inline_methods_ GUARDED_BY(lock_);
374     const DexFile* dex_file_;
375 
376     DISALLOW_COPY_AND_ASSIGN(DexFileMethodInliner);
377 };
378 
379 }  // namespace art
380 
381 #endif  // ART_COMPILER_DEX_QUICK_DEX_FILE_METHOD_INLINER_H_
382