Global Value Numbering.
Implement the Global Value Numbering for optimization
purposes. Use it for the null check and range check
elimination as the LVN used to do.
The order of evaluation of basic blocks needs improving as
we currently fail to recognize some obviously identical
values in methods with more than one loop. (There are three
disabled tests that check this. This is just a missed
optimization, not a correctness issue.)
Change-Id: I0d0ce16b2495b5a3b17ad1b2b32931cd69f5a25a
diff --git a/compiler/dex/local_value_numbering.h b/compiler/dex/local_value_numbering.h
index 45700df..190eab4 100644
--- a/compiler/dex/local_value_numbering.h
+++ b/compiler/dex/local_value_numbering.h
@@ -20,17 +20,57 @@
#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;
-class MirFieldInfo;
+
+// Enable/disable tracking values stored in the FILLED_NEW_ARRAY result.
+static constexpr bool kLocalValueNumberingEnableFilledNewArrayTracking = true;
class LocalValueNumbering {
+ private:
+ static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue;
+
public:
- LocalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator);
+ 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);
+ null_checked_.insert(value_name);
+ }
+
+ 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 {
+ kNormalMerge,
+ kCatchMerge,
+ 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);
@@ -42,13 +82,9 @@
// Allow delete-expression to destroy a LocalValueNumbering object without deallocation.
static void operator delete(void* ptr) { UNUSED(ptr); }
- // Checks that the value names didn't overflow.
- bool Good() const {
- return last_value_ < kNoValue;
- }
-
private:
- static constexpr uint16_t kNoValue = 0xffffu;
+ // A set of value names.
+ typedef GlobalValueNumbering::ValueNameSet ValueNameSet;
// Field types correspond to the ordering of GET/PUT instructions; this order is the same
// for IGET, IPUT, SGET, SPUT, AGET and APUT:
@@ -61,27 +97,51 @@
// op_SHORT 6
static constexpr size_t kFieldTypeCount = 7;
- // FieldReference represents a unique resolved field.
- struct FieldReference {
- const DexFile* dex_file;
- uint16_t field_idx;
- };
+ // Key is s_reg, value is value name.
+ typedef ScopedArenaSafeMap<uint16_t, uint16_t> SregValueMap;
- struct FieldReferenceComparator {
- bool operator()(const FieldReference& lhs, const FieldReference& rhs) const {
- if (lhs.field_idx != rhs.field_idx) {
- return lhs.field_idx < rhs.field_idx;
- }
- return lhs.dex_file < rhs.dex_file;
+ 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_);
};
- // Maps field key to field id for resolved fields.
- typedef ScopedArenaSafeMap<FieldReference, uint32_t, FieldReferenceComparator> FieldIndexMap;
+ 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 {
@@ -95,211 +155,233 @@
typedef ScopedArenaSet<RangeCheckKey, RangeCheckKeyComparator> RangeCheckSet;
- typedef ScopedArenaSafeMap<uint16_t, uint16_t> AliasingIFieldVersionMap;
- typedef ScopedArenaSafeMap<uint16_t, uint16_t> NonAliasingArrayVersionMap;
+ // Maps instance field "location" (derived from base, field_id and type) to value name.
+ typedef ScopedArenaSafeMap<uint16_t, uint16_t> IFieldLocToValueMap;
- struct NonAliasingIFieldKey {
- uint16_t base;
- uint16_t field_id;
+ // 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 NonAliasingIFieldKeyComparator {
- bool operator()(const NonAliasingIFieldKey& lhs, const NonAliasingIFieldKey& rhs) const {
- // Compare the type first. This allows iterating across all the entries for a certain type
- // as needed when we need to purge them for an unresolved field IPUT.
+ 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;
}
- // Compare the field second. This allows iterating across all the entries for a certain
- // field as needed when we need to purge them for an aliasing field IPUT.
- if (lhs.field_id != rhs.field_id) {
- return lhs.field_id < rhs.field_id;
- }
- // Compare the base last.
- return lhs.base < rhs.base;
+ return lhs.field_id < rhs.field_id;
}
};
- // Set of instance fields still holding non-aliased values after the base has been stored.
- typedef ScopedArenaSet<NonAliasingIFieldKey, NonAliasingIFieldKeyComparator> NonAliasingFieldSet;
+ typedef ScopedArenaSet<EscapedIFieldClobberKey, EscapedIFieldClobberKeyComparator>
+ EscapedIFieldClobberSet;
- struct EscapedArrayKey {
+ 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 EscapedArrayKeyComparator {
- bool operator()(const EscapedArrayKey& lhs, const EscapedArrayKey& rhs) const {
- // Compare the type first. This allows iterating across all the entries for a certain type
- // as needed when we need to purge them for an unresolved field APUT.
- if (lhs.type != rhs.type) {
- return lhs.type < rhs.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;
}
- // Compare the base last.
- return lhs.base < rhs.base;
+ return lhs.type < rhs.type;
}
};
- // Set of previously non-aliasing array refs that escaped.
- typedef ScopedArenaSet<EscapedArrayKey, EscapedArrayKeyComparator> EscapedArraySet;
+ // Clobber set for previously non-aliasing array refs that escaped.
+ typedef ScopedArenaSet<EscapedArrayClobberKey, EscapedArrayClobberKeyComparator>
+ EscapedArrayClobberSet;
- // Key is s_reg, value is value name.
- typedef ScopedArenaSafeMap<uint16_t, uint16_t> SregValueMap;
- // Key is concatenation of opcode, operand1, operand2 and modifier, value is value name.
- typedef ScopedArenaSafeMap<uint64_t, uint16_t> ValueMap;
- // Key represents a memory address, value is generation.
- // A set of value names.
- typedef ScopedArenaSet<uint16_t> ValueNameSet;
-
- static uint64_t BuildKey(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
- return (static_cast<uint64_t>(op) << 48 | static_cast<uint64_t>(operand1) << 32 |
- static_cast<uint64_t>(operand2) << 16 | static_cast<uint64_t>(modifier));
- };
-
- static uint16_t ExtractOp(uint64_t key) {
- return static_cast<uint16_t>(key >> 48);
- }
-
- static uint16_t ExtractOperand1(uint64_t key) {
- return static_cast<uint16_t>(key >> 32);
- }
-
- static uint16_t ExtractOperand2(uint64_t key) {
- return static_cast<uint16_t>(key >> 16);
- }
-
- static uint16_t ExtractModifier(uint64_t key) {
- return static_cast<uint16_t>(key);
- }
-
- static bool EqualOpAndOperand1(uint64_t key1, uint64_t key2) {
- return static_cast<uint32_t>(key1 >> 32) == static_cast<uint32_t>(key2 >> 32);
- }
-
- uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
- uint16_t res;
- uint64_t key = BuildKey(op, operand1, operand2, modifier);
- ValueMap::iterator it = value_map_.find(key);
- if (it != value_map_.end()) {
- res = it->second;
- } else {
- ++last_value_;
- res = last_value_;
- value_map_.Put(key, res);
+ // 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),
+ last_stored_value(kNoValue),
+ store_loc_set(std::less<uint16_t>(), allocator->Adapter()),
+ last_load_memory_version(kNoValue),
+ load_value_map(std::less<uint16_t>(), allocator->Adapter()) {
}
- return res;
- };
- void StoreValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier,
- uint16_t value) {
- uint64_t key = BuildKey(op, operand1, operand2, modifier);
- value_map_.Overwrite(key, value);
- }
+ 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.
- bool HasValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier,
- uint16_t value) const {
- uint64_t key = BuildKey(op, operand1, operand2, modifier);
- ValueMap::const_iterator it = value_map_.find(key);
- return (it != value_map_.end() && it->second == value);
- };
+ // 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;
- bool ValueExists(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) const {
- uint64_t key = BuildKey(op, operand1, operand2, modifier);
- ValueMap::const_iterator it = value_map_.find(key);
- return (it != value_map_.end());
- };
-
- void SetOperandValue(uint16_t s_reg, uint16_t value) {
- SregValueMap::iterator it = sreg_value_map_.find(s_reg);
- if (it != sreg_value_map_.end()) {
- DCHECK_EQ(it->second, value);
- } else {
- sreg_value_map_.Put(s_reg, value);
+ // 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;
}
};
- uint16_t GetOperandValue(int s_reg) {
- uint16_t res = kNoValue;
- SregValueMap::iterator it = sreg_value_map_.find(s_reg);
- if (it != sreg_value_map_.end()) {
- res = it->second;
- } else {
- // First use
- res = LookupValue(kNoValue, s_reg, kNoValue, kNoValue);
- sreg_value_map_.Put(s_reg, res);
- }
- return res;
- };
+ // Maps instance field id to AliasingValues, locations are object refs.
+ typedef ScopedArenaSafeMap<uint16_t, AliasingValues> AliasingIFieldValuesMap;
- void SetOperandValueWide(uint16_t s_reg, uint16_t value) {
- SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg);
- if (it != sreg_wide_value_map_.end()) {
- DCHECK_EQ(it->second, value);
- } else {
- sreg_wide_value_map_.Put(s_reg, value);
- }
- };
+ // Maps non-aliasing array reference to AliasingValues, locations are array indexes.
+ typedef ScopedArenaSafeMap<uint16_t, AliasingValues> NonAliasingArrayValuesMap;
- uint16_t GetOperandValueWide(int s_reg) {
- uint16_t res = kNoValue;
- SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg);
- if (it != sreg_wide_value_map_.end()) {
- res = it->second;
- } else {
- // First use
- res = LookupValue(kNoValue, s_reg, kNoValue, kNoValue);
- sreg_wide_value_map_.Put(s_reg, res);
- }
- return res;
- };
+ // Maps aliasing array type to AliasingValues, locations are (array, index) pair ids.
+ typedef ScopedArenaSafeMap<uint16_t, AliasingValues> AliasingArrayValuesMap;
- uint16_t GetFieldId(const MirFieldInfo& field_info);
+ // 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);
- bool IsNonAliasingIField(uint16_t reg, uint16_t field_id, uint16_t type);
- bool IsNonAliasingArray(uint16_t reg, uint16_t type);
+ 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);
- CompilationUnit* const cu_;
+ bool SameMemoryVersion(const LocalValueNumbering& other) const;
- // We have 32-bit last_value_ so that we can detect when we run out of value names, see Good().
- // We usually don't check Good() until the end of LVN unless we're about to modify code.
- uint32_t last_value_;
+ 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_;
- ValueMap 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];
- uint16_t aliasing_array_version_[kFieldTypeCount];
- AliasingIFieldVersionMap aliasing_ifield_version_map_;
- NonAliasingArrayVersionMap non_aliasing_array_version_map_;
- FieldIndexMap field_index_map_;
// Value names of references to objects that cannot be reached through a different value name.
ValueNameSet non_aliasing_refs_;
- // Instance fields still holding non-aliased values after the base has escaped.
- NonAliasingFieldSet non_aliasing_ifields_;
- // Previously non-aliasing array refs that escaped but can still be used for non-aliasing AGET.
- EscapedArraySet escaped_array_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_;
+
DISALLOW_COPY_AND_ASSIGN(LocalValueNumbering);
};