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