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
25namespace art {
26
27class ArenaBitVector;
28class BasicBlock;
29struct CompilationUnit;
30class DexFile;
31class MirFieldInfo;
32class MirMethodInfo;
33class MIR;
34class 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 */
67class 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 {
76    static Type Unknown() {
77      return Type(0u);
78    }
79
80    static Type NonArrayRefType() {
81      return Type(kFlagLowWord | kFlagNarrow | kFlagRef);
82    }
83
84    static Type ArtMethodType(bool wide) {
85      return Type(kFlagLowWord | kFlagRef | (wide ? kFlagWide : kFlagNarrow));
86    }
87
88    static Type ObjectArrayType() {
89      return Type(kFlagNarrow | kFlagRef | kFlagLowWord |
90                  (1u << kBitArrayDepthStart) | kFlagArrayNarrow | kFlagArrayRef);
91    }
92
93    static Type WideArrayType() {
94      // Core or FP unknown.
95      return Type(kFlagNarrow | kFlagRef | kFlagLowWord |
96                  (1u << kBitArrayDepthStart) | kFlagArrayWide);
97    }
98
99    static Type NarrowArrayType() {
100      // Core or FP unknown.
101      return Type(kFlagNarrow | kFlagRef | kFlagLowWord |
102                  (1u << kBitArrayDepthStart) | kFlagArrayNarrow);
103    }
104
105    static Type NarrowCoreArrayType() {
106      return Type(kFlagNarrow | kFlagRef | kFlagLowWord |
107                  (1u << kBitArrayDepthStart) | kFlagArrayNarrow | kFlagArrayCore);
108    }
109
110    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
119    bool IsDefined() {
120      return raw_bits_ != 0u;
121    }
122
123    bool SizeConflict() const {
124      // NOTE: Ignore array element conflicts that don't propagate to direct conflicts.
125      return (Wide() && Narrow()) || (HighWord() && LowWord());
126    }
127
128    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
133    void MarkSizeConflict() {
134      SetBits(kFlagLowWord | kFlagHighWord);
135    }
136
137    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
142    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.
154    bool NonNull() const {
155      return IsBitSet(kFlagNonNull);
156    }
157
158    bool Wide() const {
159      return IsBitSet(kFlagWide);
160    }
161
162    bool Narrow() const {
163      return IsBitSet(kFlagNarrow);
164    }
165
166    bool Fp() const {
167      return IsBitSet(kFlagFp);
168    }
169
170    bool Core() const {
171      return IsBitSet(kFlagCore);
172    }
173
174    bool Ref() const {
175      return IsBitSet(kFlagRef);
176    }
177
178    bool LowWord() const {
179      return IsBitSet(kFlagLowWord);
180    }
181
182    bool HighWord() const {
183      return IsBitSet(kFlagHighWord);
184    }
185
186    uint32_t ArrayDepth() const {
187      return raw_bits_ >> kBitArrayDepthStart;
188    }
189
190    Type NestedType() const {
191      DCHECK_NE(ArrayDepth(), 0u);
192      return Type(kFlagLowWord | ((raw_bits_ & kMaskArrayWideAndType) >> kArrayTypeShift));
193    }
194
195    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
201    void SetWide() {
202      SetBits(kFlagWide);
203    }
204
205    void SetNarrow() {
206      SetBits(kFlagNarrow);
207    }
208
209    void SetFp() {
210      SetBits(kFlagFp);
211    }
212
213    void SetCore() {
214      SetBits(kFlagCore);
215    }
216
217    void SetRef() {
218      SetBits(kFlagRef);
219    }
220
221    void SetLowWord() {
222      SetBits(kFlagLowWord);
223    }
224
225    void SetHighWord() {
226      SetBits(kFlagHighWord);
227    }
228
229    Type ToHighWord() const {
230      DCHECK_EQ(raw_bits_ & (kMaskWide | kMaskWord), kFlagWide | kFlagLowWord);
231      return Type(raw_bits_ ^ (kFlagLowWord | kFlagHighWord));
232    }
233
234    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
241    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.
250    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.
264    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.
269    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
331    explicit Type(uint32_t raw_bits) : raw_bits_(raw_bits) { }
332
333    bool IsBitSet(uint32_t flag) const {
334      return (raw_bits_ & flag) != 0u;
335    }
336
337    void SetBits(uint32_t flags) {
338      raw_bits_ |= flags;
339    }
340
341    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
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