blob: dff5e27521a036c9a26ede1ff5e39e367c2161e3 [file] [log] [blame]
* Copyright (C) 2012 The Android Open Source Project
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* See the License for the specific language governing permissions and
* limitations under the License.
#include <memory>
#include "base/arena_object.h"
#include "base/logging.h"
#include "dex_instruction_utils.h"
#include "global_value_numbering.h"
namespace art {
class DexFile;
// Enable/disable tracking values stored in the FILLED_NEW_ARRAY result.
static constexpr bool kLocalValueNumberingEnableFilledNewArrayTracking = true;
class LocalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue;
LocalValueNumbering(GlobalValueNumbering* gvn, BasicBlockId id, ScopedArenaAllocator* allocator);
BasicBlockId Id() const {
return id_;
bool Equals(const LocalValueNumbering& other) const;
bool IsValueNullChecked(uint16_t value_name) const {
return null_checked_.find(value_name) != null_checked_.end();
bool IsValueDivZeroChecked(uint16_t value_name) const {
return div_zero_checked_.find(value_name) != div_zero_checked_.end();
uint16_t GetSregValue(uint16_t s_reg) const {
return GetSregValueImpl(s_reg, &sreg_value_map_);
uint16_t GetSregValueWide(uint16_t s_reg) const {
return GetSregValueImpl(s_reg, &sreg_wide_value_map_);
// Get the starting value number for a given dalvik register.
uint16_t GetStartingVregValueNumber(int v_reg) const {
return GetStartingVregValueNumberImpl(v_reg, false);
// Get the starting value number for a given wide dalvik register.
uint16_t GetStartingVregValueNumberWide(int v_reg) const {
return GetStartingVregValueNumberImpl(v_reg, true);
enum MergeType {
kReturnMerge, // RETURN or PHI+RETURN. Merge only sreg maps.
void MergeOne(const LocalValueNumbering& other, MergeType merge_type);
void Merge(MergeType merge_type); // Merge gvn_->merge_lvns_.
void PrepareEntryBlock();
uint16_t GetValueNumber(MIR* mir);
// A set of value names.
typedef GlobalValueNumbering::ValueNameSet ValueNameSet;
// Key is s_reg, value is value name.
typedef ScopedArenaSafeMap<uint16_t, uint16_t> SregValueMap;
uint16_t GetEndingVregValueNumberImpl(int v_reg, bool wide) const;
uint16_t GetStartingVregValueNumberImpl(int v_reg, bool wide) const;
uint16_t GetSregValueImpl(int s_reg, const SregValueMap* map) const {
uint16_t res = kNoValue;
auto lb = map->find(s_reg);
if (lb != map->end()) {
res = lb->second;
} else {
res = gvn_->FindValue(kNoValue, s_reg, kNoValue, kNoValue);
return res;
void SetOperandValueImpl(uint16_t s_reg, uint16_t value, SregValueMap* map) {
DCHECK_EQ(map->count(s_reg), 0u);
map->Put(s_reg, value);
uint16_t GetOperandValueImpl(int s_reg, const SregValueMap* map) const {
uint16_t res = kNoValue;
auto lb = map->find(s_reg);
if (lb != map->end()) {
res = lb->second;
} else {
// Using the original value; s_reg refers to an input reg.
res = gvn_->LookupValue(kNoValue, s_reg, kNoValue, kNoValue);
return res;
void SetOperandValue(uint16_t s_reg, uint16_t value) {
DCHECK_EQ(sreg_wide_value_map_.count(s_reg), 0u);
SetOperandValueImpl(s_reg, value, &sreg_value_map_);
uint16_t GetOperandValue(int s_reg) const {
DCHECK_EQ(sreg_wide_value_map_.count(s_reg), 0u);
return GetOperandValueImpl(s_reg, &sreg_value_map_);
void SetOperandValueWide(uint16_t s_reg, uint16_t value) {
DCHECK_EQ(sreg_value_map_.count(s_reg), 0u);
SetOperandValueImpl(s_reg, value, &sreg_wide_value_map_);
uint16_t GetOperandValueWide(int s_reg) const {
DCHECK_EQ(sreg_value_map_.count(s_reg), 0u);
return GetOperandValueImpl(s_reg, &sreg_wide_value_map_);
struct RangeCheckKey {
uint16_t array;
uint16_t index;
// NOTE: Can't define this at namespace scope for a private struct.
bool operator==(const RangeCheckKey& other) const {
return array == other.array && index == other.index;
struct RangeCheckKeyComparator {
bool operator()(const RangeCheckKey& lhs, const RangeCheckKey& rhs) const {
if (lhs.array != rhs.array) {
return lhs.array < rhs.array;
return lhs.index < rhs.index;
typedef ScopedArenaSet<RangeCheckKey, RangeCheckKeyComparator> RangeCheckSet;
// Maps instance field "location" (derived from base, field_id and type) to value name.
typedef ScopedArenaSafeMap<uint16_t, uint16_t> IFieldLocToValueMap;
// Maps static field id to value name
typedef ScopedArenaSafeMap<uint16_t, uint16_t> SFieldToValueMap;
struct EscapedIFieldClobberKey {
uint16_t base; // Or array.
uint16_t type;
uint16_t field_id; // None (kNoValue) for arrays and unresolved instance field stores.
// NOTE: Can't define this at namespace scope for a private struct.
bool operator==(const EscapedIFieldClobberKey& other) const {
return base == other.base && type == other.type && field_id == other.field_id;
struct EscapedIFieldClobberKeyComparator {
bool operator()(const EscapedIFieldClobberKey& lhs, const EscapedIFieldClobberKey& rhs) const {
// Compare base first. This makes sequential iteration respect the order of base.
if (lhs.base != rhs.base) {
return lhs.base < rhs.base;
// Compare type second. This makes the type-clobber entries (field_id == kNoValue) last
// for given base and type and makes it easy to prune unnecessary entries when merging
// escaped_ifield_clobber_set_ from multiple LVNs.
if (lhs.type != rhs.type) {
return lhs.type < rhs.type;
return lhs.field_id < rhs.field_id;
typedef ScopedArenaSet<EscapedIFieldClobberKey, EscapedIFieldClobberKeyComparator>
struct EscapedArrayClobberKey {
uint16_t base;
uint16_t type;
// NOTE: Can't define this at namespace scope for a private struct.
bool operator==(const EscapedArrayClobberKey& other) const {
return base == other.base && type == other.type;
struct EscapedArrayClobberKeyComparator {
bool operator()(const EscapedArrayClobberKey& lhs, const EscapedArrayClobberKey& rhs) const {
// Compare base first. This makes sequential iteration respect the order of base.
if (lhs.base != rhs.base) {
return lhs.base < rhs.base;
return lhs.type < rhs.type;
// Clobber set for previously non-aliasing array refs that escaped.
typedef ScopedArenaSet<EscapedArrayClobberKey, EscapedArrayClobberKeyComparator>
// Known location values for an aliasing set. The set can be tied to one of:
// 1. Instance field. The locations are aliasing references used to access the field.
// 2. Non-aliasing array reference. The locations are indexes to the array.
// 3. Aliasing array type. The locations are (reference, index) pair ids assigned by GVN.
// In each case we keep track of the last stored value, if any, and the set of locations
// where it was stored. We also keep track of all values known for the current write state
// (load_value_map), which can be known either because they have been loaded since the last
// store or because they contained the last_stored_value before the store and thus could not
// have changed as a result.
struct AliasingValues {
explicit AliasingValues(LocalValueNumbering* lvn)
: memory_version_before_stores(kNoValue),
store_loc_set(std::less<uint16_t>(), lvn->null_checked_.get_allocator()),
load_value_map(std::less<uint16_t>(), lvn->null_checked_.get_allocator()) {
uint16_t memory_version_before_stores; // kNoValue if start version for the field.
uint16_t last_stored_value; // Last stored value name, kNoValue if none.
ValueNameSet store_loc_set; // Where was last_stored_value stored.
// Maps refs (other than stored_to) to currently known values for this field other. On write,
// anything that differs from the written value is removed as it may be overwritten.
uint16_t last_load_memory_version; // kNoValue if not known.
ScopedArenaSafeMap<uint16_t, uint16_t> load_value_map;
// NOTE: Can't define this at namespace scope for a private struct.
bool operator==(const AliasingValues& other) const {
return memory_version_before_stores == other.memory_version_before_stores &&
last_load_memory_version == other.last_load_memory_version &&
last_stored_value == other.last_stored_value &&
store_loc_set == other.store_loc_set &&
load_value_map == other.load_value_map;
// Maps instance field id to AliasingValues, locations are object refs.
typedef ScopedArenaSafeMap<uint16_t, AliasingValues> AliasingIFieldValuesMap;
// Maps non-aliasing array reference to AliasingValues, locations are array indexes.
typedef ScopedArenaSafeMap<uint16_t, AliasingValues> NonAliasingArrayValuesMap;
// Maps aliasing array type to AliasingValues, locations are (array, index) pair ids.
typedef ScopedArenaSafeMap<uint16_t, AliasingValues> AliasingArrayValuesMap;
// Helper classes defining versions for updating and merging the AliasingValues maps above.
class AliasingIFieldVersions;
class NonAliasingArrayVersions;
class AliasingArrayVersions;
template <typename Map>
AliasingValues* GetAliasingValues(Map* map, const typename Map::key_type& key);
template <typename Versions, typename KeyType>
void UpdateAliasingValuesLoadVersion(const KeyType& key, AliasingValues* values);
template <typename Versions, typename Map>
static uint16_t AliasingValuesMergeGet(GlobalValueNumbering* gvn,
const LocalValueNumbering* lvn,
Map* map, const typename Map::key_type& key,
uint16_t location);
template <typename Versions, typename Map>
uint16_t HandleAliasingValuesGet(Map* map, const typename Map::key_type& key,
uint16_t location);
template <typename Versions, typename Map>
bool HandleAliasingValuesPut(Map* map, const typename Map::key_type& key,
uint16_t location, uint16_t value);
template <typename K>
void CopyAliasingValuesMap(ScopedArenaSafeMap<K, AliasingValues>* dest,
const ScopedArenaSafeMap<K, AliasingValues>& src);
uint16_t MarkNonAliasingNonNull(MIR* mir);
bool IsNonAliasing(uint16_t reg) const;
bool IsNonAliasingIField(uint16_t reg, uint16_t field_id, uint16_t type) const;
bool IsNonAliasingArray(uint16_t reg, uint16_t type) const;
void HandleNullCheck(MIR* mir, uint16_t reg);
void HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index);
void HandleDivZeroCheck(MIR* mir, uint16_t reg);
void HandlePutObject(MIR* mir);
void HandleEscapingRef(uint16_t base);
void HandleInvokeArgs(const MIR* mir, const LocalValueNumbering* mir_lvn);
uint16_t HandlePhi(MIR* mir);
uint16_t HandleConst(MIR* mir, uint32_t value);
uint16_t HandleConstWide(MIR* mir, uint64_t value);
uint16_t HandleAGet(MIR* mir, uint16_t opcode);
void HandleAPut(MIR* mir, uint16_t opcode);
uint16_t HandleIGet(MIR* mir, uint16_t opcode);
void HandleIPut(MIR* mir, uint16_t opcode);
uint16_t HandleSGet(MIR* mir, uint16_t opcode);
void HandleSPut(MIR* mir, uint16_t opcode);
void RemoveSFieldsForType(uint16_t type);
void HandleInvokeOrClInitOrAcquireOp(MIR* mir);
bool SameMemoryVersion(const LocalValueNumbering& other) const;
uint16_t NewMemoryVersion(uint16_t* new_version);
void MergeMemoryVersions(bool clobbered_catch);
void PruneNonAliasingRefsForCatch();
template <typename Set, Set LocalValueNumbering::* set_ptr>
void IntersectSets();
void CopyLiveSregValues(SregValueMap* dest, const SregValueMap& src);
// Intersect SSA reg value maps as sets, ignore dead regs.
template <SregValueMap LocalValueNumbering::* map_ptr>
void IntersectSregValueMaps();
// Intersect maps as sets. The value type must be equality-comparable.
template <typename Map>
static void InPlaceIntersectMaps(Map* work_map, const Map& other_map);
template <typename Set, Set LocalValueNumbering::*set_ptr, void (LocalValueNumbering::*MergeFn)(
const typename Set::value_type& entry, typename Set::iterator hint)>
void MergeSets();
void IntersectAliasingValueLocations(AliasingValues* work_values, const AliasingValues* values);
void MergeEscapedRefs(const ValueNameSet::value_type& entry, ValueNameSet::iterator hint);
void MergeEscapedIFieldTypeClobberSets(const EscapedIFieldClobberSet::value_type& entry,
EscapedIFieldClobberSet::iterator hint);
void MergeEscapedIFieldClobberSets(const EscapedIFieldClobberSet::value_type& entry,
EscapedIFieldClobberSet::iterator hint);
void MergeEscapedArrayClobberSets(const EscapedArrayClobberSet::value_type& entry,
EscapedArrayClobberSet::iterator hint);
void MergeSFieldValues(const SFieldToValueMap::value_type& entry,
SFieldToValueMap::iterator hint);
void MergeNonAliasingIFieldValues(const IFieldLocToValueMap::value_type& entry,
IFieldLocToValueMap::iterator hint);
void MergeNullChecked();
void MergeDivZeroChecked();
template <typename Map, Map LocalValueNumbering::*map_ptr, typename Versions>
void MergeAliasingValues(const typename Map::value_type& entry, typename Map::iterator hint);
GlobalValueNumbering* gvn_;
// We're using the block id as a 16-bit operand value for some lookups.
static_assert(sizeof(BasicBlockId) == sizeof(uint16_t), "BasicBlockId must be 16 bit");
BasicBlockId id_;
SregValueMap sreg_value_map_;
SregValueMap sreg_wide_value_map_;
SFieldToValueMap sfield_value_map_;
IFieldLocToValueMap non_aliasing_ifield_value_map_;
AliasingIFieldValuesMap aliasing_ifield_value_map_;
NonAliasingArrayValuesMap non_aliasing_array_value_map_;
AliasingArrayValuesMap aliasing_array_value_map_;
// Data for dealing with memory clobbering and store/load aliasing.
uint16_t global_memory_version_;
uint16_t unresolved_sfield_version_[kDexMemAccessTypeCount];
uint16_t unresolved_ifield_version_[kDexMemAccessTypeCount];
// Value names of references to objects that cannot be reached through a different value name.
ValueNameSet non_aliasing_refs_;
// Previously non-aliasing refs that escaped but can still be used for non-aliasing AGET/IGET.
ValueNameSet escaped_refs_;
// Blacklists for cases where escaped_refs_ can't be used.
EscapedIFieldClobberSet escaped_ifield_clobber_set_;
EscapedArrayClobberSet escaped_array_clobber_set_;
// Range check and null check elimination.
RangeCheckSet range_checked_;
ValueNameSet null_checked_;
ValueNameSet div_zero_checked_;
// Reuse one vector for all merges to avoid leaking too much memory on the ArenaStack.
mutable ScopedArenaVector<uint16_t> merge_names_;
// Map to identify when different locations merge the same values.
ScopedArenaSafeMap<ScopedArenaVector<uint16_t>, uint16_t> merge_map_;
// New memory version for merge, kNoValue if all memory versions matched.
uint16_t merge_new_memory_version_;
} // namespace art