1 /*
2  * Copyright (C) 2015 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_TYPE_INFERENCE_H_
18 #define ART_COMPILER_DEX_TYPE_INFERENCE_H_
19 
20 #include "base/bit_utils.h"
21 #include "base/logging.h"
22 #include "base/arena_object.h"
23 #include "base/scoped_arena_containers.h"
24 
25 namespace art {
26 
27 class ArenaBitVector;
28 class BasicBlock;
29 struct CompilationUnit;
30 class DexFile;
31 class MirFieldInfo;
32 class MirMethodInfo;
33 class MIR;
34 class MIRGraph;
35 
36 /**
37  * @brief Determine the type of SSA registers.
38  *
39  * @details
40  * Because Dalvik's bytecode is not fully typed, we have to do some work to figure
41  * out the sreg type.  For some operations it is clear based on the opcode (i.e.
42  * ADD_FLOAT v0, v1, v2), but for others (MOVE), we may never know the "real" type.
43  *
44  * We perform the type inference operation in two phases:
45  *   1. First, we make one pass over all insns in the topological sort order and
46  *      extract known type information from all insns for their defs and uses.
47  *   2. Then we repeatedly go through the graph to process insns that can propagate
48  *      types from inputs to outputs and vice versa. These insns are just the MOVEs,
49  *      AGET/APUTs, IF_ccs and Phis (including pseudo-Phis, see below).
50  *
51  * Since the main purpose is to determine the basic FP/core/reference type, we don't
52  * need to record the precise reference type, we only record the array type to determine
53  * the result types of agets and source type of aputs.
54  *
55  * One complication is the check-cast instruction that effectively defines a new
56  * virtual register that has a different type than the original sreg. We need to
57  * track these virtual sregs and insert pseudo-phis where they merge.
58  *
59  * Another problems is with null references. The same zero constant can be used
60  * as differently typed null and moved around with move-object which would normally
61  * be an ill-formed assignment. So we need to keep track of values that can be null
62  * and values that cannot.
63  *
64  * Note that it's possible to have the same sreg show multiple defined types because dx
65  * treats constants as untyped bit patterns. We disable register promotion in that case.
66  */
67 class TypeInference : public DeletableArenaObject<kArenaAllocMisc> {
68  public:
69   TypeInference(MIRGraph* mir_graph, ScopedArenaAllocator* alloc);
70 
71   bool Apply(BasicBlock* bb);
72   void Finish();
73 
74  private:
75   struct Type {
UnknownType76     static Type Unknown() {
77       return Type(0u);
78     }
79 
NonArrayRefTypeType80     static Type NonArrayRefType() {
81       return Type(kFlagLowWord | kFlagNarrow | kFlagRef);
82     }
83 
ArtMethodTypeType84     static Type ArtMethodType(bool wide) {
85       return Type(kFlagLowWord | kFlagRef | (wide ? kFlagWide : kFlagNarrow));
86     }
87 
ObjectArrayTypeType88     static Type ObjectArrayType() {
89       return Type(kFlagNarrow | kFlagRef | kFlagLowWord |
90                   (1u << kBitArrayDepthStart) | kFlagArrayNarrow | kFlagArrayRef);
91     }
92 
WideArrayTypeType93     static Type WideArrayType() {
94       // Core or FP unknown.
95       return Type(kFlagNarrow | kFlagRef | kFlagLowWord |
96                   (1u << kBitArrayDepthStart) | kFlagArrayWide);
97     }
98 
NarrowArrayTypeType99     static Type NarrowArrayType() {
100       // Core or FP unknown.
101       return Type(kFlagNarrow | kFlagRef | kFlagLowWord |
102                   (1u << kBitArrayDepthStart) | kFlagArrayNarrow);
103     }
104 
NarrowCoreArrayTypeType105     static Type NarrowCoreArrayType() {
106       return Type(kFlagNarrow | kFlagRef | kFlagLowWord |
107                   (1u << kBitArrayDepthStart) | kFlagArrayNarrow | kFlagArrayCore);
108     }
109 
UnknownArrayTypeType110     static Type UnknownArrayType() {
111       return Type(kFlagNarrow | kFlagRef | kFlagLowWord | (1u << kBitArrayDepthStart));
112     }
113 
114     static Type ArrayType(uint32_t array_depth, Type nested_type);
115     static Type ArrayTypeFromComponent(Type component_type);
116     static Type ShortyType(char shorty);
117     static Type DexType(const DexFile* dex_file, uint32_t type_idx);
118 
IsDefinedType119     bool IsDefined() {
120       return raw_bits_ != 0u;
121     }
122 
SizeConflictType123     bool SizeConflict() const {
124       // NOTE: Ignore array element conflicts that don't propagate to direct conflicts.
125       return (Wide() && Narrow()) || (HighWord() && LowWord());
126     }
127 
TypeConflictType128     bool TypeConflict() const {
129       // NOTE: Ignore array element conflicts that don't propagate to direct conflicts.
130       return (raw_bits_ & kMaskType) != 0u && !IsPowerOfTwo(raw_bits_ & kMaskType);  // 2+ bits.
131     }
132 
MarkSizeConflictType133     void MarkSizeConflict() {
134       SetBits(kFlagLowWord | kFlagHighWord);
135     }
136 
MarkTypeConflictType137     void MarkTypeConflict() {
138       // Mark all three type bits so that merging any other type bits will not change this type.
139       SetBits(kFlagFp | kFlagCore | kFlagRef);
140     }
141 
CheckPureRefType142     void CheckPureRef() const {
143       DCHECK_EQ(raw_bits_ & (kMaskWideAndType | kMaskWord), kFlagNarrow | kFlagRef | kFlagLowWord);
144     }
145 
146     // If reference, don't treat as possible null and require precise type.
147     //
148     // References without this flag are allowed to have a type conflict and their
149     // type will not be propagated down. However, for simplicity we allow propagation
150     // of other flags up as it will affect only other null references; should those
151     // references be marked non-null later, we would have to do it anyway.
152     // NOTE: This is a negative "non-null" flag rather then a positive "is-null"
153     // to simplify merging together with other non-array flags.
NonNullType154     bool NonNull() const {
155       return IsBitSet(kFlagNonNull);
156     }
157 
WideType158     bool Wide() const {
159       return IsBitSet(kFlagWide);
160     }
161 
NarrowType162     bool Narrow() const {
163       return IsBitSet(kFlagNarrow);
164     }
165 
FpType166     bool Fp() const {
167       return IsBitSet(kFlagFp);
168     }
169 
CoreType170     bool Core() const {
171       return IsBitSet(kFlagCore);
172     }
173 
RefType174     bool Ref() const {
175       return IsBitSet(kFlagRef);
176     }
177 
LowWordType178     bool LowWord() const {
179       return IsBitSet(kFlagLowWord);
180     }
181 
HighWordType182     bool HighWord() const {
183       return IsBitSet(kFlagHighWord);
184     }
185 
ArrayDepthType186     uint32_t ArrayDepth() const {
187       return raw_bits_ >> kBitArrayDepthStart;
188     }
189 
NestedTypeType190     Type NestedType() const {
191       DCHECK_NE(ArrayDepth(), 0u);
192       return Type(kFlagLowWord | ((raw_bits_ & kMaskArrayWideAndType) >> kArrayTypeShift));
193     }
194 
ComponentTypeType195     Type ComponentType() const {
196       DCHECK_NE(ArrayDepth(), 0u);
197       Type temp(raw_bits_ - (1u << kBitArrayDepthStart));  // array_depth - 1u;
198       return (temp.ArrayDepth() != 0u) ? temp.AsNull() : NestedType();
199     }
200 
SetWideType201     void SetWide() {
202       SetBits(kFlagWide);
203     }
204 
SetNarrowType205     void SetNarrow() {
206       SetBits(kFlagNarrow);
207     }
208 
SetFpType209     void SetFp() {
210       SetBits(kFlagFp);
211     }
212 
SetCoreType213     void SetCore() {
214       SetBits(kFlagCore);
215     }
216 
SetRefType217     void SetRef() {
218       SetBits(kFlagRef);
219     }
220 
SetLowWordType221     void SetLowWord() {
222       SetBits(kFlagLowWord);
223     }
224 
SetHighWordType225     void SetHighWord() {
226       SetBits(kFlagHighWord);
227     }
228 
ToHighWordType229     Type ToHighWord() const {
230       DCHECK_EQ(raw_bits_ & (kMaskWide | kMaskWord), kFlagWide | kFlagLowWord);
231       return Type(raw_bits_ ^ (kFlagLowWord | kFlagHighWord));
232     }
233 
MergeHighWordType234     bool MergeHighWord(Type low_word_type) {
235       // NOTE: low_word_type may be also Narrow() or HighWord().
236       DCHECK(low_word_type.Wide() && low_word_type.LowWord());
237       return MergeBits(Type(low_word_type.raw_bits_ | kFlagHighWord),
238                        kMaskWideAndType | kFlagHighWord);
239     }
240 
CopyType241     bool Copy(Type type) {
242       if (raw_bits_ != type.raw_bits_) {
243         raw_bits_ = type.raw_bits_;
244         return true;
245       }
246       return false;
247     }
248 
249     // Merge non-array flags.
MergeNonArrayFlagsType250     bool MergeNonArrayFlags(Type src_type) {
251       return MergeBits(src_type, kMaskNonArray);
252     }
253 
254     // Merge array flags for conflict.
255     bool MergeArrayConflict(Type src_type);
256 
257     // Merge all flags.
258     bool MergeStrong(Type src_type);
259 
260     // Merge all flags.
261     bool MergeWeak(Type src_type);
262 
263     // Get the same type but mark that it should not be treated as null.
AsNonNullType264     Type AsNonNull() const {
265       return Type(raw_bits_ | kFlagNonNull);
266     }
267 
268     // Get the same type but mark that it can be treated as null.
AsNullType269     Type AsNull() const {
270       return Type(raw_bits_ & ~kFlagNonNull);
271     }
272 
273    private:
274     enum FlagBits {
275       kBitNonNull = 0,
276       kBitWide,
277       kBitNarrow,
278       kBitFp,
279       kBitCore,
280       kBitRef,
281       kBitLowWord,
282       kBitHighWord,
283       kBitArrayWide,
284       kBitArrayNarrow,
285       kBitArrayFp,
286       kBitArrayCore,
287       kBitArrayRef,
288       kBitArrayDepthStart,
289     };
290     static constexpr size_t kArrayDepthBits = sizeof(uint32_t) * 8u - kBitArrayDepthStart;
291 
292     static constexpr uint32_t kFlagNonNull = 1u << kBitNonNull;
293     static constexpr uint32_t kFlagWide = 1u << kBitWide;
294     static constexpr uint32_t kFlagNarrow = 1u << kBitNarrow;
295     static constexpr uint32_t kFlagFp = 1u << kBitFp;
296     static constexpr uint32_t kFlagCore = 1u << kBitCore;
297     static constexpr uint32_t kFlagRef = 1u << kBitRef;
298     static constexpr uint32_t kFlagLowWord = 1u << kBitLowWord;
299     static constexpr uint32_t kFlagHighWord = 1u << kBitHighWord;
300     static constexpr uint32_t kFlagArrayWide = 1u << kBitArrayWide;
301     static constexpr uint32_t kFlagArrayNarrow = 1u << kBitArrayNarrow;
302     static constexpr uint32_t kFlagArrayFp = 1u << kBitArrayFp;
303     static constexpr uint32_t kFlagArrayCore = 1u << kBitArrayCore;
304     static constexpr uint32_t kFlagArrayRef = 1u << kBitArrayRef;
305 
306     static constexpr uint32_t kMaskWide = kFlagWide | kFlagNarrow;
307     static constexpr uint32_t kMaskType = kFlagFp | kFlagCore | kFlagRef;
308     static constexpr uint32_t kMaskWord = kFlagLowWord | kFlagHighWord;
309     static constexpr uint32_t kMaskArrayWide = kFlagArrayWide | kFlagArrayNarrow;
310     static constexpr uint32_t kMaskArrayType = kFlagArrayFp | kFlagArrayCore | kFlagArrayRef;
311     static constexpr uint32_t kMaskWideAndType = kMaskWide | kMaskType;
312     static constexpr uint32_t kMaskArrayWideAndType = kMaskArrayWide | kMaskArrayType;
313 
314     static constexpr size_t kArrayTypeShift = kBitArrayWide - kBitWide;
315     static_assert(kArrayTypeShift == kBitArrayNarrow - kBitNarrow, "shift mismatch");
316     static_assert(kArrayTypeShift == kBitArrayFp - kBitFp, "shift mismatch");
317     static_assert(kArrayTypeShift == kBitArrayCore - kBitCore, "shift mismatch");
318     static_assert(kArrayTypeShift == kBitArrayRef - kBitRef, "shift mismatch");
319     static_assert((kMaskWide << kArrayTypeShift) == kMaskArrayWide, "shift mismatch");
320     static_assert((kMaskType << kArrayTypeShift) == kMaskArrayType, "shift mismatch");
321     static_assert((kMaskWideAndType << kArrayTypeShift) == kMaskArrayWideAndType, "shift mismatch");
322 
323     static constexpr uint32_t kMaskArrayDepth = static_cast<uint32_t>(-1) << kBitArrayDepthStart;
324     static constexpr uint32_t kMaskNonArray = ~(kMaskArrayWideAndType | kMaskArrayDepth);
325 
326     // The maximum representable array depth. If we exceed the maximum (which can happen
327     // only with an absurd nested array type in a dex file which would presumably cause
328     // OOM while being resolved), we can report false conflicts.
329     static constexpr uint32_t kMaxArrayDepth = static_cast<uint32_t>(-1) >> kBitArrayDepthStart;
330 
TypeType331     explicit Type(uint32_t raw_bits) : raw_bits_(raw_bits) { }
332 
IsBitSetType333     bool IsBitSet(uint32_t flag) const {
334       return (raw_bits_ & flag) != 0u;
335     }
336 
SetBitsType337     void SetBits(uint32_t flags) {
338       raw_bits_ |= flags;
339     }
340 
MergeBitsType341     bool MergeBits(Type src_type, uint32_t mask) {
342       uint32_t new_bits = raw_bits_ | (src_type.raw_bits_ & mask);
343       if (new_bits != raw_bits_) {
344         raw_bits_ = new_bits;
345         return true;
346       }
347       return false;
348     }
349 
350     uint32_t raw_bits_;
351   };
352 
353   struct MethodSignature {
354     Type return_type;
355     size_t num_params;
356     Type* param_types;
357   };
358 
359   struct SplitSRegData {
360     int32_t current_mod_s_reg;
361     int32_t* starting_mod_s_reg;        // Indexed by BasicBlock::id.
362     int32_t* ending_mod_s_reg;          // Indexed by BasicBlock::id.
363 
364     // NOTE: Before AddPseudoPhis(), def_phi_blocks_ marks the blocks
365     // with check-casts and the block with the original SSA reg.
366     // After AddPseudoPhis(), it marks blocks with pseudo-phis.
367     ArenaBitVector* def_phi_blocks_;    // Indexed by BasicBlock::id.
368   };
369 
370   class CheckCastData : public DeletableArenaObject<kArenaAllocMisc> {
371    public:
372     CheckCastData(MIRGraph* mir_graph, ScopedArenaAllocator* alloc);
373 
NumSRegs()374     size_t NumSRegs() const {
375       return num_sregs_;
376     }
377 
378     void AddCheckCast(MIR* check_cast, Type type);
379     void AddPseudoPhis();
380     void InitializeCheckCastSRegs(Type* sregs) const;
381     void MergeCheckCastConflicts(Type* sregs) const;
382     void MarkPseudoPhiBlocks(uint64_t* bb_df_attrs) const;
383 
384     void Start(BasicBlock* bb);
385     bool ProcessPseudoPhis(BasicBlock* bb, Type* sregs);
386     void ProcessCheckCast(MIR* mir);
387 
388     SplitSRegData* GetSplitSRegData(int32_t s_reg);
389 
390    private:
391     BasicBlock* FindDefBlock(MIR* check_cast);
392     BasicBlock* FindTopologicallyEarliestPredecessor(BasicBlock* bb);
393     bool IsSRegLiveAtStart(BasicBlock* bb, int v_reg, int32_t s_reg);
394 
395     MIRGraph* const mir_graph_;
396     ScopedArenaAllocator* const alloc_;
397     const size_t num_blocks_;
398     size_t num_sregs_;
399 
400     // Map check-cast mir to special sreg and type.
401     struct CheckCastMapValue {
402       int32_t modified_s_reg;
403       Type type;
404     };
405     ScopedArenaSafeMap<MIR*, CheckCastMapValue> check_cast_map_;
406     ScopedArenaSafeMap<int32_t, SplitSRegData> split_sreg_data_;
407   };
408 
409   static Type FieldType(const DexFile* dex_file, uint32_t field_idx);
410   static Type* PrepareIFieldTypes(const DexFile* dex_file, MIRGraph* mir_graph,
411                                   ScopedArenaAllocator* alloc);
412   static Type* PrepareSFieldTypes(const DexFile* dex_file, MIRGraph* mir_graph,
413                                   ScopedArenaAllocator* alloc);
414   static MethodSignature Signature(const DexFile* dex_file, uint32_t method_idx, bool is_static,
415                                    ScopedArenaAllocator* alloc);
416   static MethodSignature* PrepareSignatures(const DexFile* dex_file, MIRGraph* mir_graph,
417                                             ScopedArenaAllocator* alloc);
418   static CheckCastData* InitializeCheckCastData(MIRGraph* mir_graph, ScopedArenaAllocator* alloc);
419 
420   void InitializeSRegs();
421 
422   int32_t ModifiedSReg(int32_t s_reg);
423   int32_t PhiInputModifiedSReg(int32_t s_reg, BasicBlock* bb, size_t pred_idx);
424 
425   bool UpdateSRegFromLowWordType(int32_t mod_s_reg, Type low_word_type);
426 
427   MIRGraph* const mir_graph_;
428   CompilationUnit* const cu_;
429 
430   // The type inference propagates types also backwards but this must not happen across
431   // check-cast. So we need to effectively split an SSA reg into two at check-cast and
432   // keep track of the types separately.
433   std::unique_ptr<CheckCastData> check_cast_data_;
434 
435   size_t num_sregs_;      // Number of SSA regs or modified SSA regs, see check-cast.
436   const Type* const ifields_;                 // Indexed by MIR::meta::ifield_lowering_info.
437   const Type* const sfields_;                 // Indexed by MIR::meta::sfield_lowering_info.
438   const MethodSignature* const signatures_;   // Indexed by MIR::meta::method_lowering_info.
439   const MethodSignature current_method_signature_;
440   Type* const sregs_;     // Indexed by SSA reg or modified SSA reg, see check-cast.
441   uint64_t* const bb_df_attrs_;               // Indexed by BasicBlock::id.
442 
443   friend class TypeInferenceTest;
444 };
445 
446 }  // namespace art
447 
448 #endif  // ART_COMPILER_DEX_TYPE_INFERENCE_H_
449