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 /**
35  * Handles inlining of methods from a particular DexFile.
36  *
37  * Intrinsics are a special case of inline methods. The DexFile indices for
38  * all the supported intrinsic methods are looked up once by the FindIntrinsics
39  * function and cached by this class for quick lookup by the method index.
40  *
41  * TODO: Detect short methods (at least getters, setters and empty functions)
42  * from the verifier and mark them for inlining. Inline these methods early
43  * during compilation to allow further optimizations. Similarly, provide
44  * additional information about intrinsics to the early phases of compilation.
45  */
46 class DexFileMethodInliner {
47   public:
48     DexFileMethodInliner();
49     ~DexFileMethodInliner();
50 
51     /**
52      * Analyse method code to determine if the method is a candidate for inlining.
53      * If it is, record its data for later.
54      *
55      * @param verifier the method verifier holding data about the method to analyse.
56      * @return true if the method is a candidate for inlining, false otherwise.
57      */
58     bool AnalyseMethodCode(verifier::MethodVerifier* verifier)
59         SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!lock_);
60 
61     /**
62      * Check whether a particular method index corresponds to an intrinsic or special function.
63      */
64     InlineMethodFlags IsIntrinsicOrSpecial(uint32_t method_index) REQUIRES(!lock_);
65 
66     /**
67      * Check whether a particular method index corresponds to an intrinsic function.
68      */
69     bool IsIntrinsic(uint32_t method_index, InlineMethod* intrinsic) REQUIRES(!lock_);
70 
71     /**
72      * Check whether a particular method index corresponds to a special function.
73      */
74     bool IsSpecial(uint32_t method_index) REQUIRES(!lock_);
75 
76     /**
77      * Gets the thread pointer entrypoint offset for a string init method index and pointer size.
78      */
79     uint32_t GetOffsetForStringInit(uint32_t method_index, size_t pointer_size)
80         REQUIRES(!lock_);
81 
82     /**
83      * Check whether a particular method index is a string init.
84      */
85     bool IsStringInitMethodIndex(uint32_t method_index) REQUIRES(!lock_);
86 
87     /**
88      * To avoid multiple lookups of a class by its descriptor, we cache its
89      * type index in the IndexCache. These are the indexes into the IndexCache
90      * class_indexes array.
91      */
92     enum ClassCacheIndex : uint8_t {  // unit8_t to save space, make larger if needed
93       kClassCacheFirst = 0,
94       kClassCacheBoolean = kClassCacheFirst,
95       kClassCacheByte,
96       kClassCacheChar,
97       kClassCacheShort,
98       kClassCacheInt,
99       kClassCacheLong,
100       kClassCacheFloat,
101       kClassCacheDouble,
102       kClassCacheVoid,
103       kClassCacheJavaLangByteArray,
104       kClassCacheJavaLangCharArray,
105       kClassCacheJavaLangIntArray,
106       kClassCacheJavaLangObject,
107       kClassCacheJavaLangRefReference,
108       kClassCacheJavaLangString,
109       kClassCacheJavaLangStringBuffer,
110       kClassCacheJavaLangStringBuilder,
111       kClassCacheJavaLangStringFactory,
112       kClassCacheJavaLangDouble,
113       kClassCacheJavaLangFloat,
114       kClassCacheJavaLangInteger,
115       kClassCacheJavaLangLong,
116       kClassCacheJavaLangShort,
117       kClassCacheJavaLangMath,
118       kClassCacheJavaLangStrictMath,
119       kClassCacheJavaLangThread,
120       kClassCacheJavaNioCharsetCharset,
121       kClassCacheLibcoreIoMemory,
122       kClassCacheSunMiscUnsafe,
123       kClassCacheJavaLangSystem,
124       kClassCacheLast
125     };
126 
127     /**
128      * To avoid multiple lookups of a method name string, we cache its string
129      * index in the IndexCache. These are the indexes into the IndexCache
130      * name_indexes array.
131      */
132     enum NameCacheIndex : uint8_t {  // unit8_t to save space, make larger if needed
133       kNameCacheFirst = 0,
134       kNameCacheReverse =  kNameCacheFirst,
135       kNameCacheReverseBytes,
136       kNameCacheDoubleToRawLongBits,
137       kNameCacheLongBitsToDouble,
138       kNameCacheFloatToRawIntBits,
139       kNameCacheIntBitsToFloat,
140       kNameCacheAbs,
141       kNameCacheMax,
142       kNameCacheMin,
143       kNameCacheCos,
144       kNameCacheSin,
145       kNameCacheAcos,
146       kNameCacheAsin,
147       kNameCacheAtan,
148       kNameCacheAtan2,
149       kNameCacheCbrt,
150       kNameCacheCosh,
151       kNameCacheExp,
152       kNameCacheExpm1,
153       kNameCacheHypot,
154       kNameCacheLog,
155       kNameCacheLog10,
156       kNameCacheNextAfter,
157       kNameCacheSinh,
158       kNameCacheTan,
159       kNameCacheTanh,
160       kNameCacheSqrt,
161       kNameCacheCeil,
162       kNameCacheFloor,
163       kNameCacheRint,
164       kNameCacheRound,
165       kNameCacheReferenceGetReferent,
166       kNameCacheCharAt,
167       kNameCacheCompareTo,
168       kNameCacheEquals,
169       kNameCacheGetCharsNoCheck,
170       kNameCacheIsEmpty,
171       kNameCacheFloatToIntBits,
172       kNameCacheDoubleToLongBits,
173       kNameCacheIsInfinite,
174       kNameCacheIsNaN,
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       kNameCacheGetAndAddInt,
209       kNameCacheGetAndAddLong,
210       kNameCacheGetAndSetInt,
211       kNameCacheGetAndSetLong,
212       kNameCacheGetAndSetObject,
213       kNameCacheLoadFence,
214       kNameCacheStoreFence,
215       kNameCacheFullFence,
216       kNameCacheArrayCopy,
217       kNameCacheBitCount,
218       kNameCacheCompare,
219       kNameCacheHighestOneBit,
220       kNameCacheLowestOneBit,
221       kNameCacheNumberOfLeadingZeros,
222       kNameCacheNumberOfTrailingZeros,
223       kNameCacheRotateRight,
224       kNameCacheRotateLeft,
225       kNameCacheSignum,
226       kNameCacheLast
227     };
228 
229     /**
230      * To avoid multiple lookups of a method signature, we cache its proto
231      * index in the IndexCache. These are the indexes into the IndexCache
232      * proto_indexes array.
233      */
234     enum ProtoCacheIndex : uint8_t {  // unit8_t to save space, make larger if needed
235       kProtoCacheFirst = 0,
236       kProtoCacheI_I = kProtoCacheFirst,
237       kProtoCacheJ_J,
238       kProtoCacheS_S,
239       kProtoCacheD_D,
240       kProtoCacheDD_D,
241       kProtoCacheF_F,
242       kProtoCacheFF_F,
243       kProtoCacheD_J,
244       kProtoCacheD_Z,
245       kProtoCacheJ_D,
246       kProtoCacheF_I,
247       kProtoCacheF_Z,
248       kProtoCacheI_F,
249       kProtoCacheII_I,
250       kProtoCacheI_C,
251       kProtoCacheString_I,
252       kProtoCache_Z,
253       kProtoCache_I,
254       kProtoCache_Object,
255       kProtoCache_Thread,
256       kProtoCacheJ_B,
257       kProtoCacheJ_I,
258       kProtoCacheJ_S,
259       kProtoCacheJB_V,
260       kProtoCacheJI_V,
261       kProtoCacheJJ_J,
262       kProtoCacheJJ_I,
263       kProtoCacheJJ_V,
264       kProtoCacheJS_V,
265       kProtoCacheObject_Z,
266       kProtoCacheJI_J,
267       kProtoCacheObjectJII_Z,
268       kProtoCacheObjectJJJ_Z,
269       kProtoCacheObjectJObjectObject_Z,
270       kProtoCacheObjectJ_I,
271       kProtoCacheObjectJI_I,
272       kProtoCacheObjectJI_V,
273       kProtoCacheObjectJ_J,
274       kProtoCacheObjectJJ_J,
275       kProtoCacheObjectJJ_V,
276       kProtoCacheObjectJ_Object,
277       kProtoCacheObjectJObject_V,
278       kProtoCacheObjectJObject_Object,
279       kProtoCacheCharArrayICharArrayII_V,
280       kProtoCacheObjectIObjectII_V,
281       kProtoCacheIICharArrayI_V,
282       kProtoCacheByteArrayIII_String,
283       kProtoCacheIICharArray_String,
284       kProtoCacheString_String,
285       kProtoCache_V,
286       kProtoCacheByteArray_V,
287       kProtoCacheByteArrayI_V,
288       kProtoCacheByteArrayII_V,
289       kProtoCacheByteArrayIII_V,
290       kProtoCacheByteArrayIIString_V,
291       kProtoCacheByteArrayString_V,
292       kProtoCacheByteArrayIICharset_V,
293       kProtoCacheByteArrayCharset_V,
294       kProtoCacheCharArray_V,
295       kProtoCacheCharArrayII_V,
296       kProtoCacheIICharArray_V,
297       kProtoCacheIntArrayII_V,
298       kProtoCacheString_V,
299       kProtoCacheStringBuffer_V,
300       kProtoCacheStringBuilder_V,
301       kProtoCacheLast
302     };
303 
304   private:
305     /**
306      * The maximum number of method parameters we support in the ProtoDef.
307      */
308     static constexpr uint32_t kProtoMaxParams = 6;
309 
310     /**
311      * The method signature (proto) definition using cached class indexes.
312      * The return_type and params are used with the IndexCache to look up
313      * appropriate class indexes to be passed to DexFile::FindProtoId().
314      */
315     struct ProtoDef {
316       ClassCacheIndex return_type;
317       uint8_t param_count;
318       ClassCacheIndex params[kProtoMaxParams];
319     };
320 
321     /**
322      * The method definition using cached class, name and proto indexes.
323      * The class index, method name index and proto index are used with
324      * IndexCache to look up appropriate parameters for DexFile::FindMethodId().
325      */
326     struct MethodDef {
327       ClassCacheIndex declaring_class;
328       NameCacheIndex name;
329       ProtoCacheIndex proto;
330     };
331 
332     /**
333      * The definition of an intrinsic function binds the method definition
334      * to an Intrinsic.
335      */
336     struct IntrinsicDef {
337       MethodDef method_def;
338       InlineMethod intrinsic;
339     };
340 
341     /**
342      * Cache for class, method name and method signature indexes used during
343      * intrinsic function lookup to avoid multiple lookups of the same items.
344      *
345      * Many classes have multiple intrinsics and/or they are used in multiple
346      * method signatures and we want to avoid repeated lookups since they are
347      * not exactly cheap. The method names and method signatures are sometimes
348      * reused and therefore cached as well.
349      */
350     struct IndexCache {
351       IndexCache();
352 
353       uint32_t class_indexes[kClassCacheLast - kClassCacheFirst];
354       uint32_t name_indexes[kNameCacheLast - kNameCacheFirst];
355       uint32_t proto_indexes[kProtoCacheLast - kProtoCacheFirst];
356     };
357 
358     static const char* const kClassCacheNames[];
359     static const char* const kNameCacheNames[];
360     static const ProtoDef kProtoCacheDefs[];
361     static const IntrinsicDef kIntrinsicMethods[];
362 
363     static const uint32_t kIndexNotFound = static_cast<uint32_t>(-1);
364     static const uint32_t kIndexUnresolved = static_cast<uint32_t>(-2);
365 
366     static uint32_t FindClassIndex(const DexFile* dex_file, IndexCache* cache,
367                                    ClassCacheIndex index);
368     static uint32_t FindNameIndex(const DexFile* dex_file, IndexCache* cache,
369                                   NameCacheIndex index);
370     static uint32_t FindProtoIndex(const DexFile* dex_file, IndexCache* cache,
371                                    ProtoCacheIndex index);
372     static uint32_t FindMethodIndex(const DexFile* dex_file, IndexCache* cache,
373                                     const MethodDef& method_def);
374 
375     /**
376      * Find all known intrinsic methods in the dex_file and cache their indices.
377      *
378      * Only DexFileToMethodInlinerMap may call this function to initialize the inliner.
379      */
380     void FindIntrinsics(const DexFile* dex_file) REQUIRES(lock_);
381 
382     friend class DexFileToMethodInlinerMap;
383 
384     bool AddInlineMethod(int32_t method_idx, const InlineMethod& method) REQUIRES(!lock_);
385 
386     ReaderWriterMutex lock_;
387     /*
388      * Maps method indexes (for the particular DexFile) to Intrinsic defintions.
389      */
390     SafeMap<uint32_t, InlineMethod> inline_methods_ GUARDED_BY(lock_);
391     const DexFile* dex_file_;
392 
393     DISALLOW_COPY_AND_ASSIGN(DexFileMethodInliner);
394 };
395 
396 }  // namespace art
397 
398 #endif  // ART_COMPILER_DEX_QUICK_DEX_FILE_METHOD_INLINER_H_
399