local_value_numbering.cc revision b19955d3c8fbd9588f7e17299e559d02938154b6 
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#include "local_value_numbering.h"
18
19#include "global_value_numbering.h"
20#include "mir_field_info.h"
21#include "mir_graph.h"
22
23namespace art {
24
25namespace {  // anonymous namespace
26
27// Operations used for value map keys instead of actual opcode.
28static constexpr uint16_t kInvokeMemoryVersionBumpOp = Instruction::INVOKE_VIRTUAL;
29static constexpr uint16_t kUnresolvedSFieldOp = Instruction::SGET;
30static constexpr uint16_t kResolvedSFieldOp = Instruction::SGET_WIDE;
31static constexpr uint16_t kUnresolvedIFieldOp = Instruction::IGET;
32static constexpr uint16_t kNonAliasingIFieldLocOp = Instruction::IGET_WIDE;
33static constexpr uint16_t kNonAliasingIFieldInitialOp = Instruction::IGET_OBJECT;
34static constexpr uint16_t kAliasingIFieldOp = Instruction::IGET_BOOLEAN;
35static constexpr uint16_t kAliasingIFieldStartVersionOp = Instruction::IGET_BYTE;
36static constexpr uint16_t kAliasingIFieldBumpVersionOp = Instruction::IGET_CHAR;
37static constexpr uint16_t kNonAliasingArrayOp = Instruction::AGET;
38static constexpr uint16_t kNonAliasingArrayStartVersionOp = Instruction::AGET_WIDE;
39static constexpr uint16_t kNonAliasingArrayBumpVersionOp = Instruction::AGET_OBJECT;
40static constexpr uint16_t kAliasingArrayOp = Instruction::AGET_BOOLEAN;
41static constexpr uint16_t kAliasingArrayStartVersionOp = Instruction::AGET_BYTE;
42static constexpr uint16_t kAliasingArrayBumpVersionOp = Instruction::AGET_CHAR;
43static constexpr uint16_t kMergeBlockMemoryVersionBumpOp = Instruction::INVOKE_VIRTUAL_RANGE;
44static constexpr uint16_t kMergeBlockAliasingIFieldVersionBumpOp = Instruction::IPUT;
45static constexpr uint16_t kMergeBlockAliasingIFieldMergeLocationOp = Instruction::IPUT_WIDE;
46static constexpr uint16_t kMergeBlockNonAliasingArrayVersionBumpOp = Instruction::APUT;
47static constexpr uint16_t kMergeBlockNonAliasingArrayMergeLocationOp = Instruction::APUT_WIDE;
48static constexpr uint16_t kMergeBlockAliasingArrayVersionBumpOp = Instruction::APUT_OBJECT;
49static constexpr uint16_t kMergeBlockAliasingArrayMergeLocationOp = Instruction::APUT_BOOLEAN;
50static constexpr uint16_t kMergeBlockNonAliasingIFieldVersionBumpOp = Instruction::APUT_BYTE;
51static constexpr uint16_t kMergeBlockSFieldVersionBumpOp = Instruction::APUT_CHAR;
52
53}  // anonymous namespace
54
55class LocalValueNumbering::AliasingIFieldVersions {
56 public:
57  static uint16_t StartMemoryVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn,
58                                     uint16_t field_id) {
59    uint16_t type = gvn->GetFieldType(field_id);
60    return gvn->LookupValue(kAliasingIFieldStartVersionOp, field_id,
61                            lvn->global_memory_version_, lvn->unresolved_ifield_version_[type]);
62  }
63
64  static uint16_t BumpMemoryVersion(GlobalValueNumbering* gvn, uint16_t old_version,
65                                    uint16_t store_ref_set_id, uint16_t stored_value) {
66    return gvn->LookupValue(kAliasingIFieldBumpVersionOp, old_version,
67                            store_ref_set_id, stored_value);
68  }
69
70  static uint16_t LookupGlobalValue(GlobalValueNumbering* gvn,
71                                    uint16_t field_id, uint16_t base, uint16_t memory_version) {
72    return gvn->LookupValue(kAliasingIFieldOp, field_id, base, memory_version);
73  }
74
75  static uint16_t LookupMergeValue(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn,
76                                   uint16_t field_id, uint16_t base) {
77    // If the base/field_id is non-aliasing in lvn, use the non-aliasing value.
78    uint16_t type = gvn->GetFieldType(field_id);
79    if (lvn->IsNonAliasingIField(base, field_id, type)) {
80      uint16_t loc = gvn->LookupValue(kNonAliasingIFieldLocOp, base, field_id, type);
81      auto lb = lvn->non_aliasing_ifield_value_map_.find(loc);
82      return (lb != lvn->non_aliasing_ifield_value_map_.end())
83          ? lb->second
84          : gvn->LookupValue(kNonAliasingIFieldInitialOp, loc, kNoValue, kNoValue);
85    }
86    return AliasingValuesMergeGet<AliasingIFieldVersions>(
87        gvn, lvn, &lvn->aliasing_ifield_value_map_, field_id, base);
88  }
89
90  static bool HasNewBaseVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn,
91                                uint16_t field_id) {
92    uint16_t type = gvn->GetFieldType(field_id);
93    return lvn->unresolved_ifield_version_[type] == lvn->merge_new_memory_version_ ||
94        lvn->global_memory_version_ == lvn->merge_new_memory_version_;
95  }
96
97  static uint16_t LookupMergeBlockValue(GlobalValueNumbering* gvn, uint16_t lvn_id,
98                                        uint16_t field_id) {
99    return gvn->LookupValue(kMergeBlockAliasingIFieldVersionBumpOp, field_id, kNoValue, lvn_id);
100  }
101
102  static uint16_t LookupMergeLocationValue(GlobalValueNumbering* gvn, uint16_t lvn_id,
103                                           uint16_t field_id, uint16_t base) {
104    return gvn->LookupValue(kMergeBlockAliasingIFieldMergeLocationOp, field_id, base, lvn_id);
105  }
106};
107
108class LocalValueNumbering::NonAliasingArrayVersions {
109 public:
110  static uint16_t StartMemoryVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn,
111                                     uint16_t array) {
112    return gvn->LookupValue(kNonAliasingArrayStartVersionOp, array, kNoValue, kNoValue);
113  }
114
115  static uint16_t BumpMemoryVersion(GlobalValueNumbering* gvn, uint16_t old_version,
116                                    uint16_t store_ref_set_id, uint16_t stored_value) {
117    return gvn->LookupValue(kNonAliasingArrayBumpVersionOp, old_version,
118                            store_ref_set_id, stored_value);
119  }
120
121  static uint16_t LookupGlobalValue(GlobalValueNumbering* gvn,
122                                    uint16_t array, uint16_t index, uint16_t memory_version) {
123    return gvn->LookupValue(kNonAliasingArrayOp, array, index, memory_version);
124  }
125
126  static uint16_t LookupMergeValue(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn,
127                                   uint16_t array, uint16_t index) {
128    return AliasingValuesMergeGet<NonAliasingArrayVersions>(
129        gvn, lvn, &lvn->non_aliasing_array_value_map_, array, index);
130  }
131
132  static bool HasNewBaseVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn,
133                                uint16_t array) {
134    return false;  // Not affected by global_memory_version_.
135  }
136
137  static uint16_t LookupMergeBlockValue(GlobalValueNumbering* gvn, uint16_t lvn_id,
138                                        uint16_t array) {
139    return gvn->LookupValue(kMergeBlockNonAliasingArrayVersionBumpOp, array, kNoValue, lvn_id);
140  }
141
142  static uint16_t LookupMergeLocationValue(GlobalValueNumbering* gvn, uint16_t lvn_id,
143                                           uint16_t array, uint16_t index) {
144    return gvn->LookupValue(kMergeBlockNonAliasingArrayMergeLocationOp, array, index, lvn_id);
145  }
146};
147
148class LocalValueNumbering::AliasingArrayVersions {
149 public:
150  static uint16_t StartMemoryVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn,
151                                     uint16_t type) {
152    return gvn->LookupValue(kAliasingArrayStartVersionOp, type, lvn->global_memory_version_,
153                            kNoValue);
154  }
155
156  static uint16_t BumpMemoryVersion(GlobalValueNumbering* gvn, uint16_t old_version,
157                                    uint16_t store_ref_set_id, uint16_t stored_value) {
158    return gvn->LookupValue(kAliasingArrayBumpVersionOp, old_version,
159                            store_ref_set_id, stored_value);
160  }
161
162  static uint16_t LookupGlobalValue(GlobalValueNumbering* gvn,
163                                    uint16_t type, uint16_t location, uint16_t memory_version) {
164    return gvn->LookupValue(kAliasingArrayOp, type, location, memory_version);
165  }
166
167  static uint16_t LookupMergeValue(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn,
168                                   uint16_t type, uint16_t location) {
169    // If the location is non-aliasing in lvn, use the non-aliasing value.
170    uint16_t array = gvn->GetArrayLocationBase(location);
171    if (lvn->IsNonAliasingArray(array, type)) {
172      uint16_t index = gvn->GetArrayLocationIndex(location);
173      return NonAliasingArrayVersions::LookupMergeValue(gvn, lvn, array, index);
174    }
175    return AliasingValuesMergeGet<AliasingArrayVersions>(
176        gvn, lvn, &lvn->aliasing_array_value_map_, type, location);
177  }
178
179  static bool HasNewBaseVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn,
180                                uint16_t type) {
181    return lvn->global_memory_version_ == lvn->merge_new_memory_version_;
182  }
183
184  static uint16_t LookupMergeBlockValue(GlobalValueNumbering* gvn, uint16_t lvn_id,
185                                        uint16_t type) {
186    return gvn->LookupValue(kMergeBlockAliasingArrayVersionBumpOp, type, kNoValue, lvn_id);
187  }
188
189  static uint16_t LookupMergeLocationValue(GlobalValueNumbering* gvn, uint16_t lvn_id,
190                                           uint16_t type, uint16_t location) {
191    return gvn->LookupValue(kMergeBlockAliasingArrayMergeLocationOp, type, location, lvn_id);
192  }
193};
194
195template <typename Map>
196LocalValueNumbering::AliasingValues* LocalValueNumbering::GetAliasingValues(
197    Map* map, const typename Map::key_type& key) {
198  auto lb = map->lower_bound(key);
199  if (lb == map->end() || map->key_comp()(key, lb->first)) {
200    lb = map->PutBefore(lb, key, AliasingValues(this));
201  }
202  return &lb->second;
203}
204
205template <typename Versions, typename KeyType>
206void LocalValueNumbering::UpdateAliasingValuesLoadVersion(const KeyType& key,
207                                                          AliasingValues* values) {
208  if (values->last_load_memory_version == kNoValue) {
209    // Get the start version that accounts for aliasing with unresolved fields of the same
210    // type and make it unique for the field by including the field_id.
211    uint16_t memory_version = values->memory_version_before_stores;
212    if (memory_version == kNoValue) {
213      memory_version = Versions::StartMemoryVersion(gvn_, this, key);
214    }
215    if (!values->store_loc_set.empty()) {
216      uint16_t ref_set_id = gvn_->GetRefSetId(values->store_loc_set);
217      memory_version = Versions::BumpMemoryVersion(gvn_, memory_version, ref_set_id,
218                                                   values->last_stored_value);
219    }
220    values->last_load_memory_version = memory_version;
221  }
222}
223
224template <typename Versions, typename Map>
225uint16_t LocalValueNumbering::AliasingValuesMergeGet(GlobalValueNumbering* gvn,
226                                                     const LocalValueNumbering* lvn,
227                                                     Map* map, const typename Map::key_type& key,
228                                                     uint16_t location) {
229  // Retrieve the value name that we would get from
230  //   const_cast<LocalValueNumbering*>(lvn)->HandleAliasingValueGet(map. key, location)
231  // but don't modify the map.
232  uint16_t value_name;
233  auto it = map->find(key);
234  if (it == map->end()) {
235    uint16_t start_version = Versions::StartMemoryVersion(gvn, lvn, key);
236    value_name = Versions::LookupGlobalValue(gvn, key, location, start_version);
237  } else if (it->second.store_loc_set.count(location) != 0u) {
238    value_name = it->second.last_stored_value;
239  } else {
240    auto load_it = it->second.load_value_map.find(location);
241    if (load_it != it->second.load_value_map.end()) {
242      value_name = load_it->second;
243    } else {
244      value_name = Versions::LookupGlobalValue(gvn, key, location, it->second.last_load_memory_version);
245    }
246  }
247  return value_name;
248}
249
250template <typename Versions, typename Map>
251uint16_t LocalValueNumbering::HandleAliasingValuesGet(Map* map, const typename Map::key_type& key,
252                                                      uint16_t location) {
253  // Retrieve the value name for IGET/SGET/AGET, update the map with new value if any.
254  uint16_t res;
255  AliasingValues* values = GetAliasingValues(map, key);
256  if (values->store_loc_set.count(location) != 0u) {
257    res = values->last_stored_value;
258  } else {
259    UpdateAliasingValuesLoadVersion<Versions>(key, values);
260    auto lb = values->load_value_map.lower_bound(location);
261    if (lb != values->load_value_map.end() && lb->first == location) {
262      res = lb->second;
263    } else {
264      res = Versions::LookupGlobalValue(gvn_, key, location, values->last_load_memory_version);
265      values->load_value_map.PutBefore(lb, location, res);
266    }
267  }
268  return res;
269}
270
271template <typename Versions, typename Map>
272bool LocalValueNumbering::HandleAliasingValuesPut(Map* map, const typename Map::key_type& key,
273                                                  uint16_t location, uint16_t value) {
274  AliasingValues* values = GetAliasingValues(map, key);
275  auto load_values_it = values->load_value_map.find(location);
276  if (load_values_it != values->load_value_map.end() && load_values_it->second == value) {
277    // This insn can be eliminated, it stores the same value that's already in the field.
278    return false;
279  }
280  if (value == values->last_stored_value) {
281    auto store_loc_lb = values->store_loc_set.lower_bound(location);
282    if (store_loc_lb != values->store_loc_set.end() && *store_loc_lb == location) {
283      // This insn can be eliminated, it stores the same value that's already in the field.
284      return false;
285    }
286    values->store_loc_set.emplace_hint(store_loc_lb, location);
287  } else {
288    UpdateAliasingValuesLoadVersion<Versions>(key, values);
289    values->memory_version_before_stores = values->last_load_memory_version;
290    values->last_stored_value = value;
291    values->store_loc_set.clear();
292    values->store_loc_set.insert(location);
293  }
294  // Clear the last load memory version and remove all potentially overwritten values.
295  values->last_load_memory_version = kNoValue;
296  auto it = values->load_value_map.begin(), end = values->load_value_map.end();
297  while (it != end) {
298    if (it->second == value) {
299      ++it;
300    } else {
301      it = values->load_value_map.erase(it);
302    }
303  }
304  return true;
305}
306
307template <typename K>
308void LocalValueNumbering::CopyAliasingValuesMap(ScopedArenaSafeMap<K, AliasingValues>* dest,
309                                                const ScopedArenaSafeMap<K, AliasingValues>& src) {
310  // We need each new AliasingValues (or rather its map members) to be constructed
311  // with our allocator, rather than the allocator of the source.
312  for (const auto& entry : src) {
313    auto it = dest->PutBefore(dest->end(), entry.first, AliasingValues(this));
314    it->second = entry.second;  // Map assignments preserve current allocator.
315  }
316}
317
318LocalValueNumbering::LocalValueNumbering(GlobalValueNumbering* gvn, uint16_t id,
319                                         ScopedArenaAllocator* allocator)
320    : gvn_(gvn),
321      id_(id),
322      sreg_value_map_(std::less<uint16_t>(), allocator->Adapter()),
323      sreg_wide_value_map_(std::less<uint16_t>(), allocator->Adapter()),
324      sfield_value_map_(std::less<uint16_t>(), allocator->Adapter()),
325      non_aliasing_ifield_value_map_(std::less<uint16_t>(), allocator->Adapter()),
326      aliasing_ifield_value_map_(std::less<uint16_t>(), allocator->Adapter()),
327      non_aliasing_array_value_map_(std::less<uint16_t>(), allocator->Adapter()),
328      aliasing_array_value_map_(std::less<uint16_t>(), allocator->Adapter()),
329      global_memory_version_(0u),
330      non_aliasing_refs_(std::less<uint16_t>(), allocator->Adapter()),
331      escaped_refs_(std::less<uint16_t>(), allocator->Adapter()),
332      escaped_ifield_clobber_set_(EscapedIFieldClobberKeyComparator(), allocator->Adapter()),
333      escaped_array_clobber_set_(EscapedArrayClobberKeyComparator(), allocator->Adapter()),
334      range_checked_(RangeCheckKeyComparator() , allocator->Adapter()),
335      null_checked_(std::less<uint16_t>(), allocator->Adapter()),
336      merge_names_(allocator->Adapter()),
337      merge_map_(std::less<ScopedArenaVector<BasicBlockId>>(), allocator->Adapter()),
338      merge_new_memory_version_(kNoValue) {
339  std::fill_n(unresolved_sfield_version_, kFieldTypeCount, 0u);
340  std::fill_n(unresolved_ifield_version_, kFieldTypeCount, 0u);
341}
342
343bool LocalValueNumbering::Equals(const LocalValueNumbering& other) const {
344  DCHECK(gvn_ == other.gvn_);
345  // Compare the maps/sets and memory versions.
346  return sreg_value_map_ == other.sreg_value_map_ &&
347      sreg_wide_value_map_ == other.sreg_wide_value_map_ &&
348      sfield_value_map_ == other.sfield_value_map_ &&
349      non_aliasing_ifield_value_map_ == other.non_aliasing_ifield_value_map_ &&
350      aliasing_ifield_value_map_ == other.aliasing_ifield_value_map_ &&
351      non_aliasing_array_value_map_ == other.non_aliasing_array_value_map_ &&
352      aliasing_array_value_map_ == other.aliasing_array_value_map_ &&
353      SameMemoryVersion(other) &&
354      non_aliasing_refs_ == other.non_aliasing_refs_ &&
355      escaped_refs_ == other.escaped_refs_ &&
356      escaped_ifield_clobber_set_ == other.escaped_ifield_clobber_set_ &&
357      escaped_array_clobber_set_ == other.escaped_array_clobber_set_ &&
358      range_checked_ == other.range_checked_ &&
359      null_checked_ == other.null_checked_;
360}
361
362void LocalValueNumbering::MergeOne(const LocalValueNumbering& other, MergeType merge_type) {
363  CopyLiveSregValues(&sreg_value_map_, other.sreg_value_map_);
364  CopyLiveSregValues(&sreg_wide_value_map_, other.sreg_wide_value_map_);
365
366  if (merge_type == kReturnMerge) {
367    // RETURN or PHI+RETURN. We need only sreg value maps.
368    return;
369  }
370
371  non_aliasing_ifield_value_map_ = other.non_aliasing_ifield_value_map_;
372  CopyAliasingValuesMap(&non_aliasing_array_value_map_, other.non_aliasing_array_value_map_);
373  non_aliasing_refs_ = other.non_aliasing_refs_;
374  range_checked_ = other.range_checked_;
375  null_checked_ = other.null_checked_;
376
377  if (merge_type == kCatchMerge) {
378    // Memory is clobbered. Use new memory version and don't merge aliasing locations.
379    global_memory_version_ = NewMemoryVersion(&merge_new_memory_version_);
380    std::fill_n(unresolved_sfield_version_, kFieldTypeCount, global_memory_version_);
381    std::fill_n(unresolved_ifield_version_, kFieldTypeCount, global_memory_version_);
382    PruneNonAliasingRefsForCatch();
383    return;
384  }
385
386  DCHECK(merge_type == kNormalMerge);
387  global_memory_version_ = other.global_memory_version_;
388  std::copy_n(other.unresolved_ifield_version_, kFieldTypeCount, unresolved_ifield_version_);
389  std::copy_n(other.unresolved_sfield_version_, kFieldTypeCount, unresolved_sfield_version_);
390  sfield_value_map_ = other.sfield_value_map_;
391  CopyAliasingValuesMap(&aliasing_ifield_value_map_, other.aliasing_ifield_value_map_);
392  CopyAliasingValuesMap(&aliasing_array_value_map_, other.aliasing_array_value_map_);
393  escaped_refs_ = other.escaped_refs_;
394  escaped_ifield_clobber_set_ = other.escaped_ifield_clobber_set_;
395  escaped_array_clobber_set_ = other.escaped_array_clobber_set_;
396}
397
398bool LocalValueNumbering::SameMemoryVersion(const LocalValueNumbering& other) const {
399  return
400      global_memory_version_ == other.global_memory_version_ &&
401      std::equal(unresolved_ifield_version_, unresolved_ifield_version_ + kFieldTypeCount,
402                 other.unresolved_ifield_version_) &&
403      std::equal(unresolved_sfield_version_, unresolved_sfield_version_ + kFieldTypeCount,
404                 other.unresolved_sfield_version_);
405}
406
407uint16_t LocalValueNumbering::NewMemoryVersion(uint16_t* new_version) {
408  if (*new_version == kNoValue) {
409    *new_version = gvn_->LookupValue(kMergeBlockMemoryVersionBumpOp, 0u, 0u, id_);
410  }
411  return *new_version;
412}
413
414void LocalValueNumbering::MergeMemoryVersions(bool clobbered_catch) {
415  DCHECK_GE(gvn_->merge_lvns_.size(), 2u);
416  const LocalValueNumbering* cmp = gvn_->merge_lvns_[0];
417  // Check if the global version has changed.
418  bool new_global_version = clobbered_catch;
419  if (!new_global_version) {
420    for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
421      if (lvn->global_memory_version_ != cmp->global_memory_version_) {
422        // Use a new version for everything.
423        new_global_version = true;
424        break;
425      }
426    }
427  }
428  if (new_global_version) {
429    global_memory_version_ = NewMemoryVersion(&merge_new_memory_version_);
430    std::fill_n(unresolved_sfield_version_, kFieldTypeCount, merge_new_memory_version_);
431    std::fill_n(unresolved_ifield_version_, kFieldTypeCount, merge_new_memory_version_);
432  } else {
433    // Initialize with a copy of memory versions from the comparison LVN.
434    global_memory_version_ = cmp->global_memory_version_;
435    std::copy_n(cmp->unresolved_ifield_version_, kFieldTypeCount, unresolved_ifield_version_);
436    std::copy_n(cmp->unresolved_sfield_version_, kFieldTypeCount, unresolved_sfield_version_);
437    for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
438      if (lvn == cmp) {
439        continue;
440      }
441      for (size_t i = 0; i != kFieldTypeCount; ++i) {
442        if (lvn->unresolved_ifield_version_[i] != cmp->unresolved_ifield_version_[i]) {
443          unresolved_ifield_version_[i] = NewMemoryVersion(&merge_new_memory_version_);
444        }
445        if (lvn->unresolved_sfield_version_[i] != cmp->unresolved_sfield_version_[i]) {
446          unresolved_sfield_version_[i] = NewMemoryVersion(&merge_new_memory_version_);
447        }
448      }
449    }
450  }
451}
452
453void LocalValueNumbering::PruneNonAliasingRefsForCatch() {
454  for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
455    const BasicBlock* bb = gvn_->GetBasicBlock(lvn->Id());
456    if (UNLIKELY(bb->taken == id_) || UNLIKELY(bb->fall_through == id_)) {
457      // Non-exceptional path to a catch handler means that the catch block was actually
458      // empty and all exceptional paths lead to the shared path after that empty block.
459      continue;
460    }
461    DCHECK_EQ(bb->taken, kNullBlock);
462    DCHECK_NE(bb->fall_through, kNullBlock);
463    const BasicBlock* fall_through_bb = gvn_->GetBasicBlock(bb->fall_through);
464    const MIR* mir = fall_through_bb->first_mir_insn;
465    DCHECK(mir != nullptr);
466    // Only INVOKEs can leak and clobber non-aliasing references if they throw.
467    if ((Instruction::FlagsOf(mir->dalvikInsn.opcode) & Instruction::kInvoke) != 0) {
468      for (uint16_t i = 0u; i != mir->ssa_rep->num_uses; ++i) {
469        uint16_t value_name = lvn->GetOperandValue(mir->ssa_rep->uses[i]);
470        non_aliasing_refs_.erase(value_name);
471      }
472    }
473  }
474}
475
476
477template <typename Set, Set LocalValueNumbering::* set_ptr>
478void LocalValueNumbering::IntersectSets() {
479  DCHECK_GE(gvn_->merge_lvns_.size(), 2u);
480
481  // Find the LVN with the least entries in the set.
482  const LocalValueNumbering* least_entries_lvn = gvn_->merge_lvns_[0];
483  for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
484    if ((lvn->*set_ptr).size() < (least_entries_lvn->*set_ptr).size()) {
485      least_entries_lvn = lvn;
486    }
487  }
488
489  // For each key check if it's in all the LVNs.
490  for (const auto& key : least_entries_lvn->*set_ptr) {
491    bool checked = true;
492    for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
493      if (lvn != least_entries_lvn && (lvn->*set_ptr).count(key) == 0u) {
494        checked = false;
495        break;
496      }
497    }
498    if (checked) {
499      (this->*set_ptr).emplace_hint((this->*set_ptr).end(), key);
500    }
501  }
502}
503
504void LocalValueNumbering::CopyLiveSregValues(SregValueMap* dest, const SregValueMap& src) {
505  auto dest_end = dest->end();
506  ArenaBitVector* live_in_v = gvn_->GetMirGraph()->GetBasicBlock(id_)->data_flow_info->live_in_v;
507  DCHECK(live_in_v != nullptr);
508  for (const auto& entry : src) {
509    bool live = live_in_v->IsBitSet(gvn_->GetMirGraph()->SRegToVReg(entry.first));
510    if (live) {
511      dest->PutBefore(dest_end, entry.first, entry.second);
512    }
513  }
514}
515
516template <LocalValueNumbering::SregValueMap LocalValueNumbering::* map_ptr>
517void LocalValueNumbering::IntersectSregValueMaps() {
518  DCHECK_GE(gvn_->merge_lvns_.size(), 2u);
519
520  // Find the LVN with the least entries in the set.
521  const LocalValueNumbering* least_entries_lvn = gvn_->merge_lvns_[0];
522  for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
523    if ((lvn->*map_ptr).size() < (least_entries_lvn->*map_ptr).size()) {
524      least_entries_lvn = lvn;
525    }
526  }
527
528  // For each key check if it's in all the LVNs.
529  ArenaBitVector* live_in_v = gvn_->GetMirGraph()->GetBasicBlock(id_)->data_flow_info->live_in_v;
530  DCHECK(live_in_v != nullptr);
531  for (const auto& entry : least_entries_lvn->*map_ptr) {
532    bool live_and_same = live_in_v->IsBitSet(gvn_->GetMirGraph()->SRegToVReg(entry.first));
533    if (live_and_same) {
534      for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
535        if (lvn != least_entries_lvn) {
536          auto it = (lvn->*map_ptr).find(entry.first);
537          if (it == (lvn->*map_ptr).end() || !(it->second == entry.second)) {
538            live_and_same = false;
539            break;
540          }
541        }
542      }
543    }
544    if (live_and_same) {
545      (this->*map_ptr).PutBefore((this->*map_ptr).end(), entry.first, entry.second);
546    }
547  }
548}
549
550// Intersect maps as sets. The value type must be equality-comparable.
551template <typename Map>
552void LocalValueNumbering::InPlaceIntersectMaps(Map* work_map, const Map& other_map) {
553  auto work_it = work_map->begin(), work_end = work_map->end();
554  auto cmp = work_map->value_comp();
555  for (const auto& entry : other_map) {
556    while (work_it != work_end &&
557        (cmp(*work_it, entry) ||
558         (!cmp(entry, *work_it) && !(work_it->second == entry.second)))) {
559      work_it = work_map->erase(work_it);
560    }
561    if (work_it == work_end) {
562      return;
563    }
564    ++work_it;
565  }
566}
567
568template <typename Set, Set LocalValueNumbering::*set_ptr, void (LocalValueNumbering::*MergeFn)(
569    const typename Set::value_type& entry, typename Set::iterator hint)>
570void LocalValueNumbering::MergeSets() {
571  auto cmp = (this->*set_ptr).value_comp();
572  for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
573    auto my_it = (this->*set_ptr).begin(), my_end = (this->*set_ptr).end();
574    for (const auto& entry : lvn->*set_ptr) {
575      while (my_it != my_end && cmp(*my_it, entry)) {
576        ++my_it;
577      }
578      if (my_it != my_end && !cmp(entry, *my_it)) {
579        // Already handled.
580        ++my_it;
581      } else {
582        // Merge values for this field_id.
583        (this->*MergeFn)(entry, my_it);  // my_it remains valid across inserts to std::set/SafeMap.
584      }
585    }
586  }
587}
588
589void LocalValueNumbering::IntersectAliasingValueLocations(AliasingValues* work_values,
590                                                          const AliasingValues* values) {
591  auto cmp = work_values->load_value_map.key_comp();
592  auto work_it = work_values->load_value_map.begin(), work_end = work_values->load_value_map.end();
593  auto store_it = values->store_loc_set.begin(), store_end = values->store_loc_set.end();
594  auto load_it = values->load_value_map.begin(), load_end = values->load_value_map.end();
595  while (store_it != store_end || load_it != load_end) {
596    uint16_t loc;
597    if (store_it != store_end && (load_it == load_end || *store_it < load_it->first)) {
598      loc = *store_it;
599      ++store_it;
600    } else {
601      loc = load_it->first;
602      ++load_it;
603      DCHECK(store_it == store_end || cmp(loc, *store_it));
604    }
605    while (work_it != work_end && cmp(work_it->first, loc)) {
606      work_it = work_values->load_value_map.erase(work_it);
607    }
608    if (work_it != work_end && !cmp(loc, work_it->first)) {
609      // The location matches, keep it.
610      ++work_it;
611    }
612  }
613  while (work_it != work_end) {
614    work_it = work_values->load_value_map.erase(work_it);
615  }
616}
617
618void LocalValueNumbering::MergeEscapedRefs(const ValueNameSet::value_type& entry,
619                                           ValueNameSet::iterator hint) {
620  // See if the ref is either escaped or non-aliasing in each predecessor.
621  bool is_escaped = true;
622  for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
623    if (lvn->non_aliasing_refs_.count(entry) == 0u &&
624        lvn->escaped_refs_.count(entry) == 0u) {
625      is_escaped = false;
626      break;
627    }
628  }
629  if (is_escaped) {
630    escaped_refs_.emplace_hint(hint, entry);
631  }
632}
633
634void LocalValueNumbering::MergeEscapedIFieldTypeClobberSets(
635    const EscapedIFieldClobberSet::value_type& entry, EscapedIFieldClobberSet::iterator hint) {
636  // Insert only type-clobber entries (field_id == kNoValue) of escaped refs.
637  if (entry.field_id == kNoValue && escaped_refs_.count(entry.base) != 0u) {
638    escaped_ifield_clobber_set_.emplace_hint(hint, entry);
639  }
640}
641
642void LocalValueNumbering::MergeEscapedIFieldClobberSets(
643    const EscapedIFieldClobberSet::value_type& entry, EscapedIFieldClobberSet::iterator hint) {
644  // Insert only those entries of escaped refs that are not overridden by a type clobber.
645  if (!(hint == escaped_ifield_clobber_set_.end() &&
646        hint->base == entry.base && hint->type == entry.type) &&
647      escaped_refs_.count(entry.base) != 0u) {
648    escaped_ifield_clobber_set_.emplace_hint(hint, entry);
649  }
650}
651
652void LocalValueNumbering::MergeEscapedArrayClobberSets(
653    const EscapedArrayClobberSet::value_type& entry, EscapedArrayClobberSet::iterator hint) {
654  if (escaped_refs_.count(entry.base) != 0u) {
655    escaped_array_clobber_set_.emplace_hint(hint, entry);
656  }
657}
658
659void LocalValueNumbering::MergeNullChecked(const ValueNameSet::value_type& entry,
660                                           ValueNameSet::iterator hint) {
661  // Merge null_checked_ for this ref.
662  merge_names_.clear();
663  merge_names_.resize(gvn_->merge_lvns_.size(), entry);
664  if (gvn_->NullCheckedInAllPredecessors(merge_names_)) {
665    null_checked_.insert(hint, entry);
666  }
667}
668
669void LocalValueNumbering::MergeSFieldValues(const SFieldToValueMap::value_type& entry,
670                                            SFieldToValueMap::iterator hint) {
671  uint16_t field_id = entry.first;
672  merge_names_.clear();
673  uint16_t value_name = kNoValue;
674  bool same_values = true;
675  for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
676    // Get the value name as in HandleSGet() but don't modify *lvn.
677    auto it = lvn->sfield_value_map_.find(field_id);
678    if (it != lvn->sfield_value_map_.end()) {
679      value_name = it->second;
680    } else {
681      uint16_t type = gvn_->GetFieldType(field_id);
682      value_name = gvn_->LookupValue(kResolvedSFieldOp, field_id,
683                                     lvn->unresolved_sfield_version_[type],
684                                     lvn->global_memory_version_);
685    }
686
687    same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back());
688    merge_names_.push_back(value_name);
689  }
690  if (same_values) {
691    // value_name already contains the result.
692  } else {
693    auto lb = merge_map_.lower_bound(merge_names_);
694    if (lb != merge_map_.end() && !merge_map_.key_comp()(merge_names_, lb->first)) {
695      value_name = lb->second;
696    } else {
697      value_name = gvn_->LookupValue(kMergeBlockSFieldVersionBumpOp, field_id, id_, kNoValue);
698      merge_map_.PutBefore(lb, merge_names_, value_name);
699      if (gvn_->NullCheckedInAllPredecessors(merge_names_)) {
700        null_checked_.insert(value_name);
701      }
702    }
703  }
704  sfield_value_map_.PutBefore(hint, field_id, value_name);
705}
706
707void LocalValueNumbering::MergeNonAliasingIFieldValues(const IFieldLocToValueMap::value_type& entry,
708                                                       IFieldLocToValueMap::iterator hint) {
709  uint16_t field_loc = entry.first;
710  merge_names_.clear();
711  uint16_t value_name = kNoValue;
712  bool same_values = true;
713  for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
714    // Get the value name as in HandleIGet() but don't modify *lvn.
715    auto it = lvn->non_aliasing_ifield_value_map_.find(field_loc);
716    if (it != lvn->non_aliasing_ifield_value_map_.end()) {
717      value_name = it->second;
718    } else {
719      value_name = gvn_->LookupValue(kNonAliasingIFieldInitialOp, field_loc, kNoValue, kNoValue);
720    }
721
722    same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back());
723    merge_names_.push_back(value_name);
724  }
725  if (same_values) {
726    // value_name already contains the result.
727  } else {
728    auto lb = merge_map_.lower_bound(merge_names_);
729    if (lb != merge_map_.end() && !merge_map_.key_comp()(merge_names_, lb->first)) {
730      value_name = lb->second;
731    } else {
732      value_name = gvn_->LookupValue(kMergeBlockNonAliasingIFieldVersionBumpOp, field_loc,
733                                     id_, kNoValue);
734      merge_map_.PutBefore(lb, merge_names_, value_name);
735      if (gvn_->NullCheckedInAllPredecessors(merge_names_)) {
736        null_checked_.insert(value_name);
737      }
738    }
739  }
740  non_aliasing_ifield_value_map_.PutBefore(hint, field_loc, value_name);
741}
742
743template <typename Map, Map LocalValueNumbering::*map_ptr, typename Versions>
744void LocalValueNumbering::MergeAliasingValues(const typename Map::value_type& entry,
745                                              typename Map::iterator hint) {
746  const typename Map::key_type& key = entry.first;
747
748  auto it = (this->*map_ptr).PutBefore(hint, key, AliasingValues(this));
749  AliasingValues* my_values = &it->second;
750
751  const AliasingValues* cmp_values = nullptr;
752  bool same_version = !Versions::HasNewBaseVersion(gvn_, this, key);
753  uint16_t load_memory_version_for_same_version = kNoValue;
754  if (same_version) {
755    // Find the first non-null values.
756    for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
757      auto it = (lvn->*map_ptr).find(key);
758      if (it != (lvn->*map_ptr).end()) {
759        cmp_values = &it->second;
760        break;
761      }
762    }
763    DCHECK(cmp_values != nullptr);  // There must be at least one non-null values.
764
765    // Check if we have identical memory versions, i.e. the global memory version, unresolved
766    // field version and the values' memory_version_before_stores, last_stored_value
767    // and store_loc_set are identical.
768    for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
769      auto it = (lvn->*map_ptr).find(key);
770      if (it == (lvn->*map_ptr).end()) {
771        if (cmp_values->memory_version_before_stores != kNoValue) {
772          same_version = false;
773          break;
774        }
775      } else if (cmp_values->last_stored_value != it->second.last_stored_value ||
776          cmp_values->memory_version_before_stores != it->second.memory_version_before_stores ||
777          cmp_values->store_loc_set != it->second.store_loc_set) {
778        same_version = false;
779        break;
780      } else if (it->second.last_load_memory_version != kNoValue) {
781        DCHECK(load_memory_version_for_same_version == kNoValue ||
782               load_memory_version_for_same_version == it->second.last_load_memory_version);
783        load_memory_version_for_same_version = it->second.last_load_memory_version;
784      }
785    }
786  }
787
788  if (same_version) {
789    // Copy the identical values.
790    my_values->memory_version_before_stores = cmp_values->memory_version_before_stores;
791    my_values->last_stored_value = cmp_values->last_stored_value;
792    my_values->store_loc_set = cmp_values->store_loc_set;
793    my_values->last_load_memory_version = load_memory_version_for_same_version;
794    // Merge load values seen in all incoming arcs (i.e. an intersection).
795    if (!cmp_values->load_value_map.empty()) {
796      my_values->load_value_map = cmp_values->load_value_map;
797      for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
798        auto it = (lvn->*map_ptr).find(key);
799        if (it == (lvn->*map_ptr).end() || it->second.load_value_map.empty()) {
800          my_values->load_value_map.clear();
801          break;
802        }
803        InPlaceIntersectMaps(&my_values->load_value_map, it->second.load_value_map);
804        if (my_values->load_value_map.empty()) {
805          break;
806        }
807      }
808    }
809  } else {
810    // Bump version number for the merge.
811    my_values->memory_version_before_stores = my_values->last_load_memory_version =
812        Versions::LookupMergeBlockValue(gvn_, id_, key);
813
814    // Calculate the locations that have been either read from or written to in each incoming LVN.
815    bool first_lvn = true;
816    for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
817      auto it = (lvn->*map_ptr).find(key);
818      if (it == (lvn->*map_ptr).end()) {
819        my_values->load_value_map.clear();
820        break;
821      }
822      if (first_lvn) {
823        first_lvn = false;
824        // Copy the first LVN's locations. Values will be overwritten later.
825        my_values->load_value_map = it->second.load_value_map;
826        for (uint16_t location : it->second.store_loc_set) {
827          my_values->load_value_map.Put(location, 0u);
828        }
829      } else {
830        IntersectAliasingValueLocations(my_values, &it->second);
831      }
832    }
833    // Calculate merged values for the intersection.
834    for (auto& load_value_entry : my_values->load_value_map) {
835      uint16_t location = load_value_entry.first;
836      bool same_values = true;
837      uint16_t value_name = kNoValue;
838      merge_names_.clear();
839      for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
840        value_name = Versions::LookupMergeValue(gvn_, lvn, key, location);
841        same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back());
842        merge_names_.push_back(value_name);
843      }
844      if (same_values) {
845        // value_name already contains the result.
846      } else {
847        auto lb = merge_map_.lower_bound(merge_names_);
848        if (lb != merge_map_.end() && !merge_map_.key_comp()(merge_names_, lb->first)) {
849          value_name = lb->second;
850        } else {
851          // NOTE: In addition to the key and id_ which don't change on an LVN recalculation
852          // during GVN, we also add location which can actually change on recalculation, so the
853          // value_name below may change. This could lead to an infinite loop if the location
854          // value name always changed when the refereced value name changes. However, given that
855          // we assign unique value names for other merges, such as Phis, such a dependency is
856          // not possible in a well-formed SSA graph.
857          value_name = Versions::LookupMergeLocationValue(gvn_, id_, key, location);
858          merge_map_.PutBefore(lb, merge_names_, value_name);
859          if (gvn_->NullCheckedInAllPredecessors(merge_names_)) {
860            null_checked_.insert(value_name);
861          }
862        }
863      }
864      load_value_entry.second = value_name;
865    }
866  }
867}
868
869void LocalValueNumbering::Merge(MergeType merge_type) {
870  DCHECK_GE(gvn_->merge_lvns_.size(), 2u);
871
872  IntersectSregValueMaps<&LocalValueNumbering::sreg_value_map_>();
873  IntersectSregValueMaps<&LocalValueNumbering::sreg_wide_value_map_>();
874  if (merge_type == kReturnMerge) {
875    // RETURN or PHI+RETURN. We need only sreg value maps.
876    return;
877  }
878
879  MergeMemoryVersions(merge_type == kCatchMerge);
880
881  // Merge non-aliasing maps/sets.
882  IntersectSets<ValueNameSet, &LocalValueNumbering::non_aliasing_refs_>();
883  if (!non_aliasing_refs_.empty() && merge_type == kCatchMerge) {
884    PruneNonAliasingRefsForCatch();
885  }
886  if (!non_aliasing_refs_.empty()) {
887    MergeSets<IFieldLocToValueMap, &LocalValueNumbering::non_aliasing_ifield_value_map_,
888              &LocalValueNumbering::MergeNonAliasingIFieldValues>();
889    MergeSets<NonAliasingArrayValuesMap, &LocalValueNumbering::non_aliasing_array_value_map_,
890              &LocalValueNumbering::MergeAliasingValues<
891                  NonAliasingArrayValuesMap, &LocalValueNumbering::non_aliasing_array_value_map_,
892                  NonAliasingArrayVersions>>();
893  }
894
895  // We won't do anything complicated for range checks, just calculate the intersection.
896  IntersectSets<RangeCheckSet, &LocalValueNumbering::range_checked_>();
897
898  // Merge null_checked_. We may later insert more, such as merged object field values.
899  MergeSets<ValueNameSet, &LocalValueNumbering::null_checked_,
900            &LocalValueNumbering::MergeNullChecked>();
901
902  if (merge_type == kCatchMerge) {
903    // Memory is clobbered. New memory version already created, don't merge aliasing locations.
904    return;
905  }
906
907  DCHECK(merge_type == kNormalMerge);
908
909  // Merge escaped refs and clobber sets.
910  MergeSets<ValueNameSet, &LocalValueNumbering::escaped_refs_,
911            &LocalValueNumbering::MergeEscapedRefs>();
912  if (!escaped_refs_.empty()) {
913    MergeSets<EscapedIFieldClobberSet, &LocalValueNumbering::escaped_ifield_clobber_set_,
914              &LocalValueNumbering::MergeEscapedIFieldTypeClobberSets>();
915    MergeSets<EscapedIFieldClobberSet, &LocalValueNumbering::escaped_ifield_clobber_set_,
916              &LocalValueNumbering::MergeEscapedIFieldClobberSets>();
917    MergeSets<EscapedArrayClobberSet, &LocalValueNumbering::escaped_array_clobber_set_,
918              &LocalValueNumbering::MergeEscapedArrayClobberSets>();
919  }
920
921  MergeSets<SFieldToValueMap, &LocalValueNumbering::sfield_value_map_,
922            &LocalValueNumbering::MergeSFieldValues>();
923  MergeSets<AliasingIFieldValuesMap, &LocalValueNumbering::aliasing_ifield_value_map_,
924            &LocalValueNumbering::MergeAliasingValues<
925                AliasingIFieldValuesMap, &LocalValueNumbering::aliasing_ifield_value_map_,
926                AliasingIFieldVersions>>();
927  MergeSets<AliasingArrayValuesMap, &LocalValueNumbering::aliasing_array_value_map_,
928            &LocalValueNumbering::MergeAliasingValues<
929                AliasingArrayValuesMap, &LocalValueNumbering::aliasing_array_value_map_,
930                AliasingArrayVersions>>();
931}
932
933uint16_t LocalValueNumbering::MarkNonAliasingNonNull(MIR* mir) {
934  uint16_t res = GetOperandValue(mir->ssa_rep->defs[0]);
935  DCHECK(null_checked_.find(res) == null_checked_.end());
936  null_checked_.insert(res);
937  non_aliasing_refs_.insert(res);
938  return res;
939}
940
941bool LocalValueNumbering::IsNonAliasing(uint16_t reg) const {
942  return non_aliasing_refs_.find(reg) != non_aliasing_refs_.end();
943}
944
945bool LocalValueNumbering::IsNonAliasingIField(uint16_t reg, uint16_t field_id,
946                                              uint16_t type) const {
947  if (IsNonAliasing(reg)) {
948    return true;
949  }
950  if (escaped_refs_.find(reg) == escaped_refs_.end()) {
951    return false;
952  }
953  // Check for IPUTs to unresolved fields.
954  EscapedIFieldClobberKey key1 = { reg, type, kNoValue };
955  if (escaped_ifield_clobber_set_.find(key1) != escaped_ifield_clobber_set_.end()) {
956    return false;
957  }
958  // Check for aliased IPUTs to the same field.
959  EscapedIFieldClobberKey key2 = { reg, type, field_id };
960  return escaped_ifield_clobber_set_.find(key2) == escaped_ifield_clobber_set_.end();
961}
962
963bool LocalValueNumbering::IsNonAliasingArray(uint16_t reg, uint16_t type) const {
964  if (IsNonAliasing(reg)) {
965    return true;
966  }
967  if (escaped_refs_.count(reg) == 0u) {
968    return false;
969  }
970  // Check for aliased APUTs.
971  EscapedArrayClobberKey key = { reg, type };
972  return escaped_array_clobber_set_.find(key) == escaped_array_clobber_set_.end();
973}
974
975void LocalValueNumbering::HandleNullCheck(MIR* mir, uint16_t reg) {
976  auto lb = null_checked_.lower_bound(reg);
977  if (lb != null_checked_.end() && *lb == reg) {
978    if (LIKELY(gvn_->CanModify())) {
979      if (gvn_->GetCompilationUnit()->verbose) {
980        LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset;
981      }
982      mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
983    }
984  } else {
985    null_checked_.insert(lb, reg);
986  }
987}
988
989void LocalValueNumbering::HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index) {
990  RangeCheckKey key = { array, index };
991  auto lb = range_checked_.lower_bound(key);
992  if (lb != range_checked_.end() && !RangeCheckKeyComparator()(key, *lb)) {
993    if (LIKELY(gvn_->CanModify())) {
994      if (gvn_->GetCompilationUnit()->verbose) {
995        LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset;
996      }
997      mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK;
998    }
999  } else {
1000    // Mark range check completed.
1001    range_checked_.insert(lb, key);
1002  }
1003}
1004
1005void LocalValueNumbering::HandlePutObject(MIR* mir) {
1006  // If we're storing a non-aliasing reference, stop tracking it as non-aliasing now.
1007  uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]);
1008  HandleEscapingRef(base);
1009}
1010
1011void LocalValueNumbering::HandleEscapingRef(uint16_t base) {
1012  auto it = non_aliasing_refs_.find(base);
1013  if (it != non_aliasing_refs_.end()) {
1014    non_aliasing_refs_.erase(it);
1015    escaped_refs_.insert(base);
1016  }
1017}
1018
1019uint16_t LocalValueNumbering::HandlePhi(MIR* mir) {
1020  if (gvn_->merge_lvns_.empty()) {
1021    // Running LVN without a full GVN?
1022    return kNoValue;
1023  }
1024  int16_t num_uses = mir->ssa_rep->num_uses;
1025  int32_t* uses = mir->ssa_rep->uses;
1026  // Try to find out if this is merging wide regs.
1027  if (mir->ssa_rep->defs[0] != 0 &&
1028      sreg_wide_value_map_.count(mir->ssa_rep->defs[0] - 1) != 0u) {
1029    // This is the high part of a wide reg. Ignore the Phi.
1030    return kNoValue;
1031  }
1032  bool wide = false;
1033  for (int16_t i = 0; i != num_uses; ++i) {
1034    if (sreg_wide_value_map_.count(uses[i]) != 0u) {
1035      wide = true;
1036      break;
1037    }
1038  }
1039  // Iterate over *merge_lvns_ and skip incoming sregs for BBs without associated LVN.
1040  uint16_t value_name = kNoValue;
1041  merge_names_.clear();
1042  BasicBlockId* incoming = mir->meta.phi_incoming;
1043  int16_t pos = 0;
1044  bool same_values = true;
1045  for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
1046    DCHECK_LT(pos, mir->ssa_rep->num_uses);
1047    while (incoming[pos] != lvn->Id()) {
1048      ++pos;
1049      DCHECK_LT(pos, mir->ssa_rep->num_uses);
1050    }
1051    int s_reg = uses[pos];
1052    ++pos;
1053    value_name = wide ? lvn->GetOperandValueWide(s_reg) : lvn->GetOperandValue(s_reg);
1054
1055    same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back());
1056    merge_names_.push_back(value_name);
1057  }
1058  if (same_values) {
1059    // value_name already contains the result.
1060  } else {
1061    auto lb = merge_map_.lower_bound(merge_names_);
1062    if (lb != merge_map_.end() && !merge_map_.key_comp()(merge_names_, lb->first)) {
1063      value_name = lb->second;
1064    } else {
1065      value_name = gvn_->LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue);
1066      merge_map_.PutBefore(lb, merge_names_, value_name);
1067      if (!wide && gvn_->NullCheckedInAllPredecessors(merge_names_)) {
1068        null_checked_.insert(value_name);
1069      }
1070    }
1071  }
1072  if (wide) {
1073    SetOperandValueWide(mir->ssa_rep->defs[0], value_name);
1074  } else {
1075    SetOperandValue(mir->ssa_rep->defs[0], value_name);
1076  }
1077  return value_name;
1078}
1079
1080uint16_t LocalValueNumbering::HandleAGet(MIR* mir, uint16_t opcode) {
1081  // uint16_t type = opcode - Instruction::AGET;
1082  uint16_t array = GetOperandValue(mir->ssa_rep->uses[0]);
1083  HandleNullCheck(mir, array);
1084  uint16_t index = GetOperandValue(mir->ssa_rep->uses[1]);
1085  HandleRangeCheck(mir, array, index);
1086  uint16_t type = opcode - Instruction::AGET;
1087  // Establish value number for loaded register.
1088  uint16_t res;
1089  if (IsNonAliasingArray(array, type)) {
1090    res = HandleAliasingValuesGet<NonAliasingArrayVersions>(&non_aliasing_array_value_map_,
1091                                                            array, index);
1092  } else {
1093    uint16_t location = gvn_->GetArrayLocation(array, index);
1094    res = HandleAliasingValuesGet<AliasingArrayVersions>(&aliasing_array_value_map_,
1095                                                         type, location);
1096  }
1097  if (opcode == Instruction::AGET_WIDE) {
1098    SetOperandValueWide(mir->ssa_rep->defs[0], res);
1099  } else {
1100    SetOperandValue(mir->ssa_rep->defs[0], res);
1101  }
1102  return res;
1103}
1104
1105void LocalValueNumbering::HandleAPut(MIR* mir, uint16_t opcode) {
1106  int array_idx = (opcode == Instruction::APUT_WIDE) ? 2 : 1;
1107  int index_idx = array_idx + 1;
1108  uint16_t array = GetOperandValue(mir->ssa_rep->uses[array_idx]);
1109  HandleNullCheck(mir, array);
1110  uint16_t index = GetOperandValue(mir->ssa_rep->uses[index_idx]);
1111  HandleRangeCheck(mir, array, index);
1112
1113  uint16_t type = opcode - Instruction::APUT;
1114  uint16_t value = (opcode == Instruction::APUT_WIDE)
1115                   ? GetOperandValueWide(mir->ssa_rep->uses[0])
1116                   : GetOperandValue(mir->ssa_rep->uses[0]);
1117  if (IsNonAliasing(array)) {
1118    bool put_is_live = HandleAliasingValuesPut<NonAliasingArrayVersions>(
1119        &non_aliasing_array_value_map_, array, index, value);
1120    if (!put_is_live) {
1121      // This APUT can be eliminated, it stores the same value that's already in the field.
1122      // TODO: Eliminate the APUT.
1123      return;
1124    }
1125  } else {
1126    uint16_t location = gvn_->GetArrayLocation(array, index);
1127    bool put_is_live = HandleAliasingValuesPut<AliasingArrayVersions>(
1128        &aliasing_array_value_map_, type, location, value);
1129    if (!put_is_live) {
1130      // This APUT can be eliminated, it stores the same value that's already in the field.
1131      // TODO: Eliminate the APUT.
1132      return;
1133    }
1134
1135    // Clobber all escaped array refs for this type.
1136    for (uint16_t escaped_array : escaped_refs_) {
1137      EscapedArrayClobberKey clobber_key = { escaped_array, type };
1138      escaped_array_clobber_set_.insert(clobber_key);
1139    }
1140  }
1141}
1142
1143uint16_t LocalValueNumbering::HandleIGet(MIR* mir, uint16_t opcode) {
1144  uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]);
1145  HandleNullCheck(mir, base);
1146  const MirFieldInfo& field_info = gvn_->GetMirGraph()->GetIFieldLoweringInfo(mir);
1147  uint16_t res;
1148  if (!field_info.IsResolved() || field_info.IsVolatile()) {
1149    // Volatile fields always get a new memory version; field id is irrelevant.
1150    // Unresolved fields may be volatile, so handle them as such to be safe.
1151    // Use result s_reg - will be unique.
1152    res = gvn_->LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue);
1153  } else {
1154    uint16_t type = opcode - Instruction::IGET;
1155    uint16_t field_id = gvn_->GetFieldId(field_info, type);
1156    if (IsNonAliasingIField(base, field_id, type)) {
1157      uint16_t loc = gvn_->LookupValue(kNonAliasingIFieldLocOp, base, field_id, type);
1158      auto lb = non_aliasing_ifield_value_map_.lower_bound(loc);
1159      if (lb != non_aliasing_ifield_value_map_.end() && lb->first == loc) {
1160        res = lb->second;
1161      } else {
1162        res = gvn_->LookupValue(kNonAliasingIFieldInitialOp, loc, kNoValue, kNoValue);
1163        non_aliasing_ifield_value_map_.PutBefore(lb, loc, res);
1164      }
1165    } else {
1166      res = HandleAliasingValuesGet<AliasingIFieldVersions>(&aliasing_ifield_value_map_,
1167                                                            field_id, base);
1168    }
1169  }
1170  if (opcode == Instruction::IGET_WIDE) {
1171    SetOperandValueWide(mir->ssa_rep->defs[0], res);
1172  } else {
1173    SetOperandValue(mir->ssa_rep->defs[0], res);
1174  }
1175  return res;
1176}
1177
1178void LocalValueNumbering::HandleIPut(MIR* mir, uint16_t opcode) {
1179  uint16_t type = opcode - Instruction::IPUT;
1180  int base_reg = (opcode == Instruction::IPUT_WIDE) ? 2 : 1;
1181  uint16_t base = GetOperandValue(mir->ssa_rep->uses[base_reg]);
1182  HandleNullCheck(mir, base);
1183  const MirFieldInfo& field_info = gvn_->GetMirGraph()->GetIFieldLoweringInfo(mir);
1184  if (!field_info.IsResolved()) {
1185    // Unresolved fields always alias with everything of the same type.
1186    // Use mir->offset as modifier; without elaborate inlining, it will be unique.
1187    unresolved_ifield_version_[type] =
1188        gvn_->LookupValue(kUnresolvedIFieldOp, kNoValue, kNoValue, mir->offset);
1189
1190    // For simplicity, treat base as escaped now.
1191    HandleEscapingRef(base);
1192
1193    // Clobber all fields of escaped references of the same type.
1194    for (uint16_t escaped_ref : escaped_refs_) {
1195      EscapedIFieldClobberKey clobber_key = { escaped_ref, type, kNoValue };
1196      escaped_ifield_clobber_set_.insert(clobber_key);
1197    }
1198
1199    // Aliasing fields of the same type may have been overwritten.
1200    auto it = aliasing_ifield_value_map_.begin(), end = aliasing_ifield_value_map_.end();
1201    while (it != end) {
1202      if (gvn_->GetFieldType(it->first) != type) {
1203        ++it;
1204      } else {
1205        it = aliasing_ifield_value_map_.erase(it);
1206      }
1207    }
1208  } else if (field_info.IsVolatile()) {
1209    // Nothing to do, resolved volatile fields always get a new memory version anyway and
1210    // can't alias with resolved non-volatile fields.
1211  } else {
1212    uint16_t field_id = gvn_->GetFieldId(field_info, type);
1213    uint16_t value = (opcode == Instruction::IPUT_WIDE)
1214                     ? GetOperandValueWide(mir->ssa_rep->uses[0])
1215                     : GetOperandValue(mir->ssa_rep->uses[0]);
1216    if (IsNonAliasing(base)) {
1217      uint16_t loc = gvn_->LookupValue(kNonAliasingIFieldLocOp, base, field_id, type);
1218      auto lb = non_aliasing_ifield_value_map_.lower_bound(loc);
1219      if (lb != non_aliasing_ifield_value_map_.end() && lb->first == loc) {
1220        if (lb->second == value) {
1221          // This IPUT can be eliminated, it stores the same value that's already in the field.
1222          // TODO: Eliminate the IPUT.
1223          return;
1224        }
1225        lb->second = value;  // Overwrite.
1226      } else {
1227        non_aliasing_ifield_value_map_.PutBefore(lb, loc, value);
1228      }
1229    } else {
1230      bool put_is_live = HandleAliasingValuesPut<AliasingIFieldVersions>(
1231          &aliasing_ifield_value_map_, field_id, base, value);
1232      if (!put_is_live) {
1233        // This IPUT can be eliminated, it stores the same value that's already in the field.
1234        // TODO: Eliminate the IPUT.
1235        return;
1236      }
1237
1238      // Clobber all fields of escaped references for this field.
1239      for (uint16_t escaped_ref : escaped_refs_) {
1240        EscapedIFieldClobberKey clobber_key = { escaped_ref, type, field_id };
1241        escaped_ifield_clobber_set_.insert(clobber_key);
1242      }
1243    }
1244  }
1245}
1246
1247uint16_t LocalValueNumbering::HandleSGet(MIR* mir, uint16_t opcode) {
1248  const MirSFieldLoweringInfo& field_info = gvn_->GetMirGraph()->GetSFieldLoweringInfo(mir);
1249  if (!field_info.IsInitialized() && (mir->optimization_flags & MIR_IGNORE_CLINIT_CHECK) == 0) {
1250    // Class initialization can call arbitrary functions, we need to wipe aliasing values.
1251    HandleInvokeOrClInit(mir);
1252  }
1253  uint16_t res;
1254  if (!field_info.IsResolved() || field_info.IsVolatile()) {
1255    // Volatile fields always get a new memory version; field id is irrelevant.
1256    // Unresolved fields may be volatile, so handle them as such to be safe.
1257    // Use result s_reg - will be unique.
1258    res = gvn_->LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue);
1259  } else {
1260    uint16_t type = opcode - Instruction::SGET;
1261    uint16_t field_id = gvn_->GetFieldId(field_info, type);
1262    auto lb = sfield_value_map_.lower_bound(field_id);
1263    if (lb != sfield_value_map_.end() && lb->first == field_id) {
1264      res = lb->second;
1265    } else {
1266      // Resolved non-volatile static fields can alias with non-resolved fields of the same type,
1267      // so we need to use unresolved_sfield_version_[type] in addition to global_memory_version_
1268      // to determine the version of the field.
1269      res = gvn_->LookupValue(kResolvedSFieldOp, field_id,
1270                              unresolved_sfield_version_[type], global_memory_version_);
1271      sfield_value_map_.PutBefore(lb, field_id, res);
1272    }
1273  }
1274  if (opcode == Instruction::SGET_WIDE) {
1275    SetOperandValueWide(mir->ssa_rep->defs[0], res);
1276  } else {
1277    SetOperandValue(mir->ssa_rep->defs[0], res);
1278  }
1279  return res;
1280}
1281
1282void LocalValueNumbering::HandleSPut(MIR* mir, uint16_t opcode) {
1283  const MirSFieldLoweringInfo& field_info = gvn_->GetMirGraph()->GetSFieldLoweringInfo(mir);
1284  if (!field_info.IsInitialized() && (mir->optimization_flags & MIR_IGNORE_CLINIT_CHECK) == 0) {
1285    // Class initialization can call arbitrary functions, we need to wipe aliasing values.
1286    HandleInvokeOrClInit(mir);
1287  }
1288  uint16_t type = opcode - Instruction::SPUT;
1289  if (!field_info.IsResolved()) {
1290    // Unresolved fields always alias with everything of the same type.
1291    // Use mir->offset as modifier; without elaborate inlining, it will be unique.
1292    unresolved_sfield_version_[type] =
1293        gvn_->LookupValue(kUnresolvedSFieldOp, kNoValue, kNoValue, mir->offset);
1294    RemoveSFieldsForType(type);
1295  } else if (field_info.IsVolatile()) {
1296    // Nothing to do, resolved volatile fields always get a new memory version anyway and
1297    // can't alias with resolved non-volatile fields.
1298  } else {
1299    uint16_t field_id = gvn_->GetFieldId(field_info, type);
1300    uint16_t value = (opcode == Instruction::SPUT_WIDE)
1301                     ? GetOperandValueWide(mir->ssa_rep->uses[0])
1302                     : GetOperandValue(mir->ssa_rep->uses[0]);
1303    // Resolved non-volatile static fields can alias with non-resolved fields of the same type,
1304    // so we need to use unresolved_sfield_version_[type] in addition to global_memory_version_
1305    // to determine the version of the field.
1306    auto lb = sfield_value_map_.lower_bound(field_id);
1307    if (lb != sfield_value_map_.end() && lb->first == field_id) {
1308      if (lb->second == value) {
1309        // This SPUT can be eliminated, it stores the same value that's already in the field.
1310        // TODO: Eliminate the SPUT.
1311        return;
1312      }
1313      lb->second = value;  // Overwrite.
1314    } else {
1315      sfield_value_map_.PutBefore(lb, field_id, value);
1316    }
1317  }
1318}
1319
1320void LocalValueNumbering::RemoveSFieldsForType(uint16_t type) {
1321  // Erase all static fields of this type from the sfield_value_map_.
1322  for (auto it = sfield_value_map_.begin(), end = sfield_value_map_.end(); it != end; ) {
1323    if (gvn_->GetFieldType(it->first) == type) {
1324      it = sfield_value_map_.erase(it);
1325    } else {
1326      ++it;
1327    }
1328  }
1329}
1330
1331void LocalValueNumbering::HandleInvokeOrClInit(MIR* mir) {
1332  // Use mir->offset as modifier; without elaborate inlining, it will be unique.
1333  global_memory_version_ =
1334      gvn_->LookupValue(kInvokeMemoryVersionBumpOp, 0u, 0u, mir->offset);
1335  // All static fields and instance fields and array elements of aliasing references,
1336  // including escaped references, may have been modified.
1337  sfield_value_map_.clear();
1338  aliasing_ifield_value_map_.clear();
1339  aliasing_array_value_map_.clear();
1340  escaped_refs_.clear();
1341  escaped_ifield_clobber_set_.clear();
1342  escaped_array_clobber_set_.clear();
1343}
1344
1345uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) {
1346  uint16_t res = kNoValue;
1347  uint16_t opcode = mir->dalvikInsn.opcode;
1348  switch (opcode) {
1349    case Instruction::NOP:
1350    case Instruction::RETURN_VOID:
1351    case Instruction::RETURN:
1352    case Instruction::RETURN_OBJECT:
1353    case Instruction::RETURN_WIDE:
1354    case Instruction::GOTO:
1355    case Instruction::GOTO_16:
1356    case Instruction::GOTO_32:
1357    case Instruction::CHECK_CAST:
1358    case Instruction::THROW:
1359    case Instruction::FILL_ARRAY_DATA:
1360    case Instruction::PACKED_SWITCH:
1361    case Instruction::SPARSE_SWITCH:
1362    case Instruction::IF_EQ:
1363    case Instruction::IF_NE:
1364    case Instruction::IF_LT:
1365    case Instruction::IF_GE:
1366    case Instruction::IF_GT:
1367    case Instruction::IF_LE:
1368    case Instruction::IF_EQZ:
1369    case Instruction::IF_NEZ:
1370    case Instruction::IF_LTZ:
1371    case Instruction::IF_GEZ:
1372    case Instruction::IF_GTZ:
1373    case Instruction::IF_LEZ:
1374    case kMirOpFusedCmplFloat:
1375    case kMirOpFusedCmpgFloat:
1376    case kMirOpFusedCmplDouble:
1377    case kMirOpFusedCmpgDouble:
1378    case kMirOpFusedCmpLong:
1379      // Nothing defined - take no action.
1380      break;
1381
1382    case Instruction::MONITOR_ENTER:
1383      HandleNullCheck(mir, GetOperandValue(mir->ssa_rep->uses[0]));
1384      // NOTE: Keeping all aliasing values intact. Programs that rely on loads/stores of the
1385      // same non-volatile locations outside and inside a synchronized block being different
1386      // contain races that we cannot fix.
1387      break;
1388
1389    case Instruction::MONITOR_EXIT:
1390      HandleNullCheck(mir, GetOperandValue(mir->ssa_rep->uses[0]));
1391      // If we're running GVN and CanModify(), uneliminated null check indicates bytecode error.
1392      if ((gvn_->GetCompilationUnit()->disable_opt & (1u << kGlobalValueNumbering)) == 0u &&
1393          gvn_->CanModify() && (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0) {
1394        LOG(WARNING) << "Bytecode error: MONITOR_EXIT is still null checked at 0x" << std::hex
1395            << mir->offset << " in " << PrettyMethod(gvn_->cu_->method_idx, *gvn_->cu_->dex_file);
1396      }
1397      break;
1398
1399    case Instruction::FILLED_NEW_ARRAY:
1400    case Instruction::FILLED_NEW_ARRAY_RANGE:
1401      // Nothing defined but the result will be unique and non-null.
1402      if (mir->next != nullptr && mir->next->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
1403        uint16_t array = MarkNonAliasingNonNull(mir->next);
1404        // Do not SetOperandValue(), we'll do that when we process the MOVE_RESULT_OBJECT.
1405        if (kLocalValueNumberingEnableFilledNewArrayTracking && mir->ssa_rep->num_uses != 0u) {
1406          AliasingValues* values = GetAliasingValues(&non_aliasing_array_value_map_, array);
1407          // Clear the value if we got a merged version in a loop.
1408          *values = AliasingValues(this);
1409          for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) {
1410            DCHECK_EQ(High16Bits(i), 0u);
1411            uint16_t index = gvn_->LookupValue(Instruction::CONST, i, 0u, 0);
1412            uint16_t value = GetOperandValue(mir->ssa_rep->uses[i]);
1413            values->load_value_map.Put(index, value);
1414            RangeCheckKey key = { array, index };
1415            range_checked_.insert(key);
1416          }
1417        }
1418        // The MOVE_RESULT_OBJECT will be processed next and we'll return the value name then.
1419      }
1420      // All args escaped (if references).
1421      for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) {
1422        uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]);
1423        HandleEscapingRef(reg);
1424      }
1425      break;
1426
1427    case Instruction::INVOKE_DIRECT:
1428    case Instruction::INVOKE_DIRECT_RANGE:
1429    case Instruction::INVOKE_VIRTUAL:
1430    case Instruction::INVOKE_VIRTUAL_RANGE:
1431    case Instruction::INVOKE_SUPER:
1432    case Instruction::INVOKE_SUPER_RANGE:
1433    case Instruction::INVOKE_INTERFACE:
1434    case Instruction::INVOKE_INTERFACE_RANGE: {
1435        // Nothing defined but handle the null check.
1436        uint16_t reg = GetOperandValue(mir->ssa_rep->uses[0]);
1437        HandleNullCheck(mir, reg);
1438      }
1439      // Intentional fall-through.
1440    case Instruction::INVOKE_STATIC:
1441    case Instruction::INVOKE_STATIC_RANGE:
1442      if ((mir->optimization_flags & MIR_INLINED) == 0) {
1443        // Make ref args aliasing.
1444        for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) {
1445          uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]);
1446          non_aliasing_refs_.erase(reg);
1447        }
1448        HandleInvokeOrClInit(mir);
1449      }
1450      break;
1451
1452    case Instruction::MOVE_RESULT:
1453    case Instruction::MOVE_RESULT_OBJECT:
1454    case Instruction::INSTANCE_OF:
1455      // 1 result, treat as unique each time, use result s_reg - will be unique.
1456      res = GetOperandValue(mir->ssa_rep->defs[0]);
1457      SetOperandValue(mir->ssa_rep->defs[0], res);
1458      break;
1459    case Instruction::MOVE_EXCEPTION:
1460    case Instruction::NEW_INSTANCE:
1461    case Instruction::CONST_CLASS:
1462    case Instruction::NEW_ARRAY:
1463      // 1 result, treat as unique each time, use result s_reg - will be unique.
1464      res = MarkNonAliasingNonNull(mir);
1465      SetOperandValue(mir->ssa_rep->defs[0], res);
1466      break;
1467    case Instruction::CONST_STRING:
1468    case Instruction::CONST_STRING_JUMBO:
1469      // These strings are internalized, so assign value based on the string pool index.
1470      res = gvn_->LookupValue(Instruction::CONST_STRING, Low16Bits(mir->dalvikInsn.vB),
1471                              High16Bits(mir->dalvikInsn.vB), 0);
1472      SetOperandValue(mir->ssa_rep->defs[0], res);
1473      null_checked_.insert(res);  // May already be there.
1474      // NOTE: Hacking the contents of an internalized string via reflection is possible
1475      // but the behavior is undefined. Therefore, we consider the string constant and
1476      // the reference non-aliasing.
1477      // TUNING: We could keep this property even if the reference "escapes".
1478      non_aliasing_refs_.insert(res);  // May already be there.
1479      break;
1480    case Instruction::MOVE_RESULT_WIDE:
1481      // 1 wide result, treat as unique each time, use result s_reg - will be unique.
1482      res = GetOperandValueWide(mir->ssa_rep->defs[0]);
1483      SetOperandValueWide(mir->ssa_rep->defs[0], res);
1484      break;
1485
1486    case kMirOpPhi:
1487      res = HandlePhi(mir);
1488      break;
1489
1490    case Instruction::MOVE:
1491    case Instruction::MOVE_OBJECT:
1492    case Instruction::MOVE_16:
1493    case Instruction::MOVE_OBJECT_16:
1494    case Instruction::MOVE_FROM16:
1495    case Instruction::MOVE_OBJECT_FROM16:
1496    case kMirOpCopy:
1497      // Just copy value number of source to value number of result.
1498      res = GetOperandValue(mir->ssa_rep->uses[0]);
1499      SetOperandValue(mir->ssa_rep->defs[0], res);
1500      break;
1501
1502    case Instruction::MOVE_WIDE:
1503    case Instruction::MOVE_WIDE_16:
1504    case Instruction::MOVE_WIDE_FROM16:
1505      // Just copy value number of source to value number of result.
1506      res = GetOperandValueWide(mir->ssa_rep->uses[0]);
1507      SetOperandValueWide(mir->ssa_rep->defs[0], res);
1508      break;
1509
1510    case Instruction::CONST:
1511    case Instruction::CONST_4:
1512    case Instruction::CONST_16:
1513      res = gvn_->LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB),
1514                              High16Bits(mir->dalvikInsn.vB), 0);
1515      SetOperandValue(mir->ssa_rep->defs[0], res);
1516      break;
1517
1518    case Instruction::CONST_HIGH16:
1519      res = gvn_->LookupValue(Instruction::CONST, 0, mir->dalvikInsn.vB, 0);
1520      SetOperandValue(mir->ssa_rep->defs[0], res);
1521      break;
1522
1523    case Instruction::CONST_WIDE_16:
1524    case Instruction::CONST_WIDE_32: {
1525        uint16_t low_res = gvn_->LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB),
1526                                             High16Bits(mir->dalvikInsn.vB >> 16), 1);
1527        uint16_t high_res;
1528        if (mir->dalvikInsn.vB & 0x80000000) {
1529          high_res = gvn_->LookupValue(Instruction::CONST, 0xffff, 0xffff, 2);
1530        } else {
1531          high_res = gvn_->LookupValue(Instruction::CONST, 0, 0, 2);
1532        }
1533        res = gvn_->LookupValue(Instruction::CONST, low_res, high_res, 3);
1534        SetOperandValueWide(mir->ssa_rep->defs[0], res);
1535      }
1536      break;
1537
1538    case Instruction::CONST_WIDE: {
1539        uint32_t low_word = Low32Bits(mir->dalvikInsn.vB_wide);
1540        uint32_t high_word = High32Bits(mir->dalvikInsn.vB_wide);
1541        uint16_t low_res = gvn_->LookupValue(Instruction::CONST, Low16Bits(low_word),
1542                                             High16Bits(low_word), 1);
1543        uint16_t high_res = gvn_->LookupValue(Instruction::CONST, Low16Bits(high_word),
1544                                              High16Bits(high_word), 2);
1545        res = gvn_->LookupValue(Instruction::CONST, low_res, high_res, 3);
1546        SetOperandValueWide(mir->ssa_rep->defs[0], res);
1547      }
1548      break;
1549
1550    case Instruction::CONST_WIDE_HIGH16: {
1551        uint16_t low_res = gvn_->LookupValue(Instruction::CONST, 0, 0, 1);
1552        uint16_t high_res = gvn_->LookupValue(Instruction::CONST, 0,
1553                                              Low16Bits(mir->dalvikInsn.vB), 2);
1554        res = gvn_->LookupValue(Instruction::CONST, low_res, high_res, 3);
1555        SetOperandValueWide(mir->ssa_rep->defs[0], res);
1556      }
1557      break;
1558
1559    case Instruction::ARRAY_LENGTH: {
1560        // Handle the null check.
1561        uint16_t reg = GetOperandValue(mir->ssa_rep->uses[0]);
1562        HandleNullCheck(mir, reg);
1563      }
1564      // Intentional fall-through.
1565    case Instruction::NEG_INT:
1566    case Instruction::NOT_INT:
1567    case Instruction::NEG_FLOAT:
1568    case Instruction::INT_TO_BYTE:
1569    case Instruction::INT_TO_SHORT:
1570    case Instruction::INT_TO_CHAR:
1571    case Instruction::INT_TO_FLOAT:
1572    case Instruction::FLOAT_TO_INT: {
1573        // res = op + 1 operand
1574        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
1575        res = gvn_->LookupValue(opcode, operand1, kNoValue, kNoValue);
1576        SetOperandValue(mir->ssa_rep->defs[0], res);
1577      }
1578      break;
1579
1580    case Instruction::LONG_TO_FLOAT:
1581    case Instruction::LONG_TO_INT:
1582    case Instruction::DOUBLE_TO_FLOAT:
1583    case Instruction::DOUBLE_TO_INT: {
1584        // res = op + 1 wide operand
1585        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
1586        res = gvn_->LookupValue(opcode, operand1, kNoValue, kNoValue);
1587        SetOperandValue(mir->ssa_rep->defs[0], res);
1588      }
1589      break;
1590
1591
1592    case Instruction::DOUBLE_TO_LONG:
1593    case Instruction::LONG_TO_DOUBLE:
1594    case Instruction::NEG_LONG:
1595    case Instruction::NOT_LONG:
1596    case Instruction::NEG_DOUBLE: {
1597        // wide res = op + 1 wide operand
1598        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
1599        res = gvn_->LookupValue(opcode, operand1, kNoValue, kNoValue);
1600        SetOperandValueWide(mir->ssa_rep->defs[0], res);
1601      }
1602      break;
1603
1604    case Instruction::FLOAT_TO_DOUBLE:
1605    case Instruction::FLOAT_TO_LONG:
1606    case Instruction::INT_TO_DOUBLE:
1607    case Instruction::INT_TO_LONG: {
1608        // wide res = op + 1 operand
1609        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
1610        res = gvn_->LookupValue(opcode, operand1, kNoValue, kNoValue);
1611        SetOperandValueWide(mir->ssa_rep->defs[0], res);
1612      }
1613      break;
1614
1615    case Instruction::CMPL_DOUBLE:
1616    case Instruction::CMPG_DOUBLE:
1617    case Instruction::CMP_LONG: {
1618        // res = op + 2 wide operands
1619        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
1620        uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]);
1621        res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue);
1622        SetOperandValue(mir->ssa_rep->defs[0], res);
1623      }
1624      break;
1625
1626    case Instruction::CMPG_FLOAT:
1627    case Instruction::CMPL_FLOAT:
1628    case Instruction::ADD_INT:
1629    case Instruction::ADD_INT_2ADDR:
1630    case Instruction::MUL_INT:
1631    case Instruction::MUL_INT_2ADDR:
1632    case Instruction::AND_INT:
1633    case Instruction::AND_INT_2ADDR:
1634    case Instruction::OR_INT:
1635    case Instruction::OR_INT_2ADDR:
1636    case Instruction::XOR_INT:
1637    case Instruction::XOR_INT_2ADDR:
1638    case Instruction::SUB_INT:
1639    case Instruction::SUB_INT_2ADDR:
1640    case Instruction::DIV_INT:
1641    case Instruction::DIV_INT_2ADDR:
1642    case Instruction::REM_INT:
1643    case Instruction::REM_INT_2ADDR:
1644    case Instruction::SHL_INT:
1645    case Instruction::SHL_INT_2ADDR:
1646    case Instruction::SHR_INT:
1647    case Instruction::SHR_INT_2ADDR:
1648    case Instruction::USHR_INT:
1649    case Instruction::USHR_INT_2ADDR: {
1650        // res = op + 2 operands
1651        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
1652        uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]);
1653        res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue);
1654        SetOperandValue(mir->ssa_rep->defs[0], res);
1655      }
1656      break;
1657
1658    case Instruction::ADD_LONG:
1659    case Instruction::SUB_LONG:
1660    case Instruction::MUL_LONG:
1661    case Instruction::DIV_LONG:
1662    case Instruction::REM_LONG:
1663    case Instruction::AND_LONG:
1664    case Instruction::OR_LONG:
1665    case Instruction::XOR_LONG:
1666    case Instruction::ADD_LONG_2ADDR:
1667    case Instruction::SUB_LONG_2ADDR:
1668    case Instruction::MUL_LONG_2ADDR:
1669    case Instruction::DIV_LONG_2ADDR:
1670    case Instruction::REM_LONG_2ADDR:
1671    case Instruction::AND_LONG_2ADDR:
1672    case Instruction::OR_LONG_2ADDR:
1673    case Instruction::XOR_LONG_2ADDR:
1674    case Instruction::ADD_DOUBLE:
1675    case Instruction::SUB_DOUBLE:
1676    case Instruction::MUL_DOUBLE:
1677    case Instruction::DIV_DOUBLE:
1678    case Instruction::REM_DOUBLE:
1679    case Instruction::ADD_DOUBLE_2ADDR:
1680    case Instruction::SUB_DOUBLE_2ADDR:
1681    case Instruction::MUL_DOUBLE_2ADDR:
1682    case Instruction::DIV_DOUBLE_2ADDR:
1683    case Instruction::REM_DOUBLE_2ADDR: {
1684        // wide res = op + 2 wide operands
1685        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
1686        uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]);
1687        res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue);
1688        SetOperandValueWide(mir->ssa_rep->defs[0], res);
1689      }
1690      break;
1691
1692    case Instruction::SHL_LONG:
1693    case Instruction::SHR_LONG:
1694    case Instruction::USHR_LONG:
1695    case Instruction::SHL_LONG_2ADDR:
1696    case Instruction::SHR_LONG_2ADDR:
1697    case Instruction::USHR_LONG_2ADDR: {
1698        // wide res = op + 1 wide operand + 1 operand
1699        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
1700        uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[2]);
1701        res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue);
1702        SetOperandValueWide(mir->ssa_rep->defs[0], res);
1703      }
1704      break;
1705
1706    case Instruction::ADD_FLOAT:
1707    case Instruction::SUB_FLOAT:
1708    case Instruction::MUL_FLOAT:
1709    case Instruction::DIV_FLOAT:
1710    case Instruction::REM_FLOAT:
1711    case Instruction::ADD_FLOAT_2ADDR:
1712    case Instruction::SUB_FLOAT_2ADDR:
1713    case Instruction::MUL_FLOAT_2ADDR:
1714    case Instruction::DIV_FLOAT_2ADDR:
1715    case Instruction::REM_FLOAT_2ADDR: {
1716        // res = op + 2 operands
1717        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
1718        uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]);
1719        res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue);
1720        SetOperandValue(mir->ssa_rep->defs[0], res);
1721      }
1722      break;
1723
1724    case Instruction::RSUB_INT:
1725    case Instruction::ADD_INT_LIT16:
1726    case Instruction::MUL_INT_LIT16:
1727    case Instruction::DIV_INT_LIT16:
1728    case Instruction::REM_INT_LIT16:
1729    case Instruction::AND_INT_LIT16:
1730    case Instruction::OR_INT_LIT16:
1731    case Instruction::XOR_INT_LIT16:
1732    case Instruction::ADD_INT_LIT8:
1733    case Instruction::RSUB_INT_LIT8:
1734    case Instruction::MUL_INT_LIT8:
1735    case Instruction::DIV_INT_LIT8:
1736    case Instruction::REM_INT_LIT8:
1737    case Instruction::AND_INT_LIT8:
1738    case Instruction::OR_INT_LIT8:
1739    case Instruction::XOR_INT_LIT8:
1740    case Instruction::SHL_INT_LIT8:
1741    case Instruction::SHR_INT_LIT8:
1742    case Instruction::USHR_INT_LIT8: {
1743        // Same as res = op + 2 operands, except use vC as operand 2
1744        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
1745        uint16_t operand2 = gvn_->LookupValue(Instruction::CONST, mir->dalvikInsn.vC, 0, 0);
1746        res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue);
1747        SetOperandValue(mir->ssa_rep->defs[0], res);
1748      }
1749      break;
1750
1751    case Instruction::AGET_OBJECT:
1752    case Instruction::AGET:
1753    case Instruction::AGET_WIDE:
1754    case Instruction::AGET_BOOLEAN:
1755    case Instruction::AGET_BYTE:
1756    case Instruction::AGET_CHAR:
1757    case Instruction::AGET_SHORT:
1758      res = HandleAGet(mir, opcode);
1759      break;
1760
1761    case Instruction::APUT_OBJECT:
1762      HandlePutObject(mir);
1763      // Intentional fall-through.
1764    case Instruction::APUT:
1765    case Instruction::APUT_WIDE:
1766    case Instruction::APUT_BYTE:
1767    case Instruction::APUT_BOOLEAN:
1768    case Instruction::APUT_SHORT:
1769    case Instruction::APUT_CHAR:
1770      HandleAPut(mir, opcode);
1771      break;
1772
1773    case Instruction::IGET_OBJECT:
1774    case Instruction::IGET:
1775    case Instruction::IGET_WIDE:
1776    case Instruction::IGET_BOOLEAN:
1777    case Instruction::IGET_BYTE:
1778    case Instruction::IGET_CHAR:
1779    case Instruction::IGET_SHORT:
1780      res = HandleIGet(mir, opcode);
1781      break;
1782
1783    case Instruction::IPUT_OBJECT:
1784      HandlePutObject(mir);
1785      // Intentional fall-through.
1786    case Instruction::IPUT:
1787    case Instruction::IPUT_WIDE:
1788    case Instruction::IPUT_BOOLEAN:
1789    case Instruction::IPUT_BYTE:
1790    case Instruction::IPUT_CHAR:
1791    case Instruction::IPUT_SHORT:
1792      HandleIPut(mir, opcode);
1793      break;
1794
1795    case Instruction::SGET_OBJECT:
1796    case Instruction::SGET:
1797    case Instruction::SGET_WIDE:
1798    case Instruction::SGET_BOOLEAN:
1799    case Instruction::SGET_BYTE:
1800    case Instruction::SGET_CHAR:
1801    case Instruction::SGET_SHORT:
1802      res = HandleSGet(mir, opcode);
1803      break;
1804
1805    case Instruction::SPUT_OBJECT:
1806      HandlePutObject(mir);
1807      // Intentional fall-through.
1808    case Instruction::SPUT:
1809    case Instruction::SPUT_WIDE:
1810    case Instruction::SPUT_BOOLEAN:
1811    case Instruction::SPUT_BYTE:
1812    case Instruction::SPUT_CHAR:
1813    case Instruction::SPUT_SHORT:
1814      HandleSPut(mir, opcode);
1815      break;
1816  }
1817  return res;
1818}
1819
1820}    // namespace art
1821