blob: 190eab4a2be7323f289cbbe636f802250fcbb915 [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 "compiler_internals.h"
#include "global_value_numbering.h"
#include "utils/scoped_arena_allocator.h"
#include "utils/scoped_arena_containers.h"
namespace art {
class DexFile;
// Enable/disable tracking values stored in the FILLED_NEW_ARRAY result.
static constexpr bool kLocalValueNumberingEnableFilledNewArrayTracking = true;
class LocalValueNumbering {
static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue;
LocalValueNumbering(GlobalValueNumbering* gvn, BasicBlockId id);
BasicBlockId Id() const {
return id_;
bool Equals(const LocalValueNumbering& other) const;
// Set non-static method's "this".
void SetSRegNullChecked(uint16_t s_reg) {
uint16_t value_name = GetOperandValue(s_reg);
bool IsValueNullChecked(uint16_t value_name) const {
return null_checked_.find(value_name) != null_checked_.end();
bool IsSregValue(uint16_t s_reg, uint16_t value_name) const {
auto it = sreg_value_map_.find(s_reg);
if (it != sreg_value_map_.end()) {
return it->second == value_name;
} else {
return gvn_->HasValue(kNoValue, s_reg, kNoValue, kNoValue, value_name);
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_.
uint16_t GetValueNumber(MIR* mir);
// LocalValueNumbering should be allocated on the ArenaStack (or the native stack).
static void* operator new(size_t size, ScopedArenaAllocator* allocator) {
return allocator->Alloc(sizeof(LocalValueNumbering), kArenaAllocMIR);
// Allow delete-expression to destroy a LocalValueNumbering object without deallocation.
static void operator delete(void* ptr) { UNUSED(ptr); }
// A set of value names.
typedef GlobalValueNumbering::ValueNameSet ValueNameSet;
// Field types correspond to the ordering of GET/PUT instructions; this order is the same
// op 0
// op_WIDE 1
// op_OBJECT 2
// op_BOOLEAN 3
// op_BYTE 4
// op_CHAR 5
// op_SHORT 6
static constexpr size_t kFieldTypeCount = 7;
// Key is s_reg, value is value name.
typedef ScopedArenaSafeMap<uint16_t, uint16_t> SregValueMap;
void SetOperandValueImpl(uint16_t s_reg, uint16_t value, SregValueMap* map) {
DCHECK_EQ(map->count(s_reg), 0u) << PrettyMethod(gvn_->cu_->method_idx, *gvn_->cu_->dex_file)
<< " LVN id: " << id_ << ", s_reg: " << s_reg;
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) {
SetOperandValueImpl(s_reg, value, &sreg_value_map_);
uint16_t GetOperandValue(int s_reg) const {
return GetOperandValueImpl(s_reg, &sreg_value_map_);
void SetOperandValueWide(uint16_t s_reg, uint16_t value) {
SetOperandValueImpl(s_reg, value, &sreg_wide_value_map_);
uint16_t GetOperandValueWide(int s_reg) const {
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(ScopedArenaAllocator* allocator)
: memory_version_before_stores(kNoValue),
store_loc_set(std::less<uint16_t>(), allocator->Adapter()),
load_value_map(std::less<uint16_t>(), allocator->Adapter()) {
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);
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 HandlePutObject(MIR* mir);
void HandleEscapingRef(uint16_t base);
uint16_t HandlePhi(MIR* mir);
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 HandleInvokeOrClInit(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();
// Intersect maps as sets. The value type must be equality-comparable.
template <typename Map, Map LocalValueNumbering::* map_ptr>
void IntersectMaps();
// 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 MergeNullChecked(const ValueNameSet::value_type& entry, ValueNameSet::iterator hint);
void MergeSFieldValues(const SFieldToValueMap::value_type& entry,
SFieldToValueMap::iterator hint);
void MergeNonAliasingIFieldValues(const IFieldLocToValueMap::value_type& entry,
IFieldLocToValueMap::iterator hint);
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.
COMPILE_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_[kFieldTypeCount];
uint16_t unresolved_ifield_version_[kFieldTypeCount];
// 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_;
// Reuse one vector for all merges to avoid leaking too much memory on the ArenaStack.
ScopedArenaVector<BasicBlockId> merge_names_;
// Map to identify when different locations merge the same values.
ScopedArenaSafeMap<ScopedArenaVector<BasicBlockId>, uint16_t> merge_map_;
// New memory version for merge, kNoValue if all memory versions matched.
uint16_t merge_new_memory_version_;
} // namespace art