local_value_numbering.h revision f59f18b2bd5432bb083205680c69fe64aaf60f39 
1/*
2 * Copyright (C) 2012 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_LOCAL_VALUE_NUMBERING_H_
18#define ART_COMPILER_DEX_LOCAL_VALUE_NUMBERING_H_
19
20#include "compiler_internals.h"
21
22#define NO_VALUE 0xffff
23#define ARRAY_REF 0xfffe
24
25namespace art {
26
27class DexFile;
28
29class LocalValueNumbering {
30 private:
31  // Field types correspond to the ordering of GET/PUT instructions; this order is the same
32  // for IGET, IPUT, SGET, SPUT, AGET and APUT:
33  // op         0
34  // op_WIDE    1
35  // op_OBJECT  2
36  // op_BOOLEAN 3
37  // op_BYTE    4
38  // op_CHAR    5
39  // op_SHORT   6
40  static constexpr size_t kFieldTypeCount = 7;
41
42  // FieldReference represents either a unique resolved field or all unresolved fields together.
43  struct FieldReference {
44    const DexFile* dex_file;
45    uint16_t field_idx;
46  };
47
48  struct FieldReferenceComparator {
49    bool operator()(const FieldReference& lhs, const FieldReference& rhs) const {
50      if (lhs.field_idx != rhs.field_idx) {
51        return lhs.field_idx < rhs.field_idx;
52      }
53      return lhs.dex_file < rhs.dex_file;
54    }
55  };
56
57  struct MemoryVersionKey {
58    uint16_t base;
59    uint16_t field_id;
60    uint16_t type;
61  };
62
63  struct MemoryVersionKeyComparator {
64    bool operator()(const MemoryVersionKey& lhs, const MemoryVersionKey& rhs) const {
65      if (lhs.base != rhs.base) {
66        return lhs.base < rhs.base;
67      }
68      if (lhs.field_id != rhs.field_id) {
69        return lhs.field_id < rhs.field_id;
70      }
71      return lhs.type < rhs.type;
72    }
73  };
74
75  // Key is s_reg, value is value name.
76  typedef SafeMap<uint16_t, uint16_t> SregValueMap;
77  // Key is concatenation of opcode, operand1, operand2 and modifier, value is value name.
78  typedef SafeMap<uint64_t, uint16_t> ValueMap;
79  // Key represents a memory address, value is generation.
80  typedef SafeMap<MemoryVersionKey, uint16_t, MemoryVersionKeyComparator> MemoryVersionMap;
81  // Maps field key to field id for resolved fields.
82  typedef SafeMap<FieldReference, uint32_t, FieldReferenceComparator> FieldIndexMap;
83
84 public:
85  explicit LocalValueNumbering(CompilationUnit* cu)
86      : cu_(cu),
87        sreg_value_map_(),
88        sreg_wide_value_map_(),
89        value_map_(),
90        next_memory_version_(1u),
91        global_memory_version_(0u),
92        memory_version_map_(),
93        field_index_map_(),
94        non_aliasing_refs_(),
95        null_checked_() {
96    std::fill_n(unresolved_sfield_version_, kFieldTypeCount, 0u);
97    std::fill_n(unresolved_ifield_version_, kFieldTypeCount, 0u);
98  }
99
100  static uint64_t BuildKey(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
101    return (static_cast<uint64_t>(op) << 48 | static_cast<uint64_t>(operand1) << 32 |
102            static_cast<uint64_t>(operand2) << 16 | static_cast<uint64_t>(modifier));
103  };
104
105  uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
106    uint16_t res;
107    uint64_t key = BuildKey(op, operand1, operand2, modifier);
108    ValueMap::iterator it = value_map_.find(key);
109    if (it != value_map_.end()) {
110      res = it->second;
111    } else {
112      res = value_map_.size() + 1;
113      value_map_.Put(key, res);
114    }
115    return res;
116  };
117
118  bool ValueExists(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) const {
119    uint64_t key = BuildKey(op, operand1, operand2, modifier);
120    ValueMap::const_iterator it = value_map_.find(key);
121    return (it != value_map_.end());
122  };
123
124  void SetOperandValue(uint16_t s_reg, uint16_t value) {
125    SregValueMap::iterator it = sreg_value_map_.find(s_reg);
126    if (it != sreg_value_map_.end()) {
127      DCHECK_EQ(it->second, value);
128    } else {
129      sreg_value_map_.Put(s_reg, value);
130    }
131  };
132
133  uint16_t GetOperandValue(int s_reg) {
134    uint16_t res = NO_VALUE;
135    SregValueMap::iterator it = sreg_value_map_.find(s_reg);
136    if (it != sreg_value_map_.end()) {
137      res = it->second;
138    } else {
139      // First use
140      res = LookupValue(NO_VALUE, s_reg, NO_VALUE, NO_VALUE);
141      sreg_value_map_.Put(s_reg, res);
142    }
143    return res;
144  };
145
146  void SetOperandValueWide(uint16_t s_reg, uint16_t value) {
147    SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg);
148    if (it != sreg_wide_value_map_.end()) {
149      DCHECK_EQ(it->second, value);
150    } else {
151      sreg_wide_value_map_.Put(s_reg, value);
152    }
153  };
154
155  uint16_t GetOperandValueWide(int s_reg) {
156    uint16_t res = NO_VALUE;
157    SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg);
158    if (it != sreg_wide_value_map_.end()) {
159      res = it->second;
160    } else {
161      // First use
162      res = LookupValue(NO_VALUE, s_reg, NO_VALUE, NO_VALUE);
163      sreg_wide_value_map_.Put(s_reg, res);
164    }
165    return res;
166  };
167
168  uint16_t GetValueNumber(MIR* mir);
169
170 private:
171  uint16_t GetFieldId(const DexFile* dex_file, uint16_t field_idx);
172  void AdvanceGlobalMemory();
173  uint16_t GetMemoryVersion(uint16_t base, uint16_t field, uint16_t type);
174  uint16_t AdvanceMemoryVersion(uint16_t base, uint16_t field, uint16_t type);
175  uint16_t MarkNonAliasingNonNull(MIR* mir);
176  void MakeArgsAliasing(MIR* mir);
177  void HandleNullCheck(MIR* mir, uint16_t reg);
178  void HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index);
179  void HandlePutObject(MIR* mir);
180
181  CompilationUnit* const cu_;
182  SregValueMap sreg_value_map_;
183  SregValueMap sreg_wide_value_map_;
184  ValueMap value_map_;
185  uint16_t next_memory_version_;
186  uint16_t global_memory_version_;
187  uint16_t unresolved_sfield_version_[kFieldTypeCount];
188  uint16_t unresolved_ifield_version_[kFieldTypeCount];
189  MemoryVersionMap memory_version_map_;
190  FieldIndexMap field_index_map_;
191  // Value names of references to objects that cannot be reached through a different value name.
192  std::set<uint16_t> non_aliasing_refs_;
193  std::set<uint16_t> null_checked_;
194};
195
196}  // namespace art
197
198#endif  // ART_COMPILER_DEX_LOCAL_VALUE_NUMBERING_H_
199