Fix and rewrite local value numbering.
Fix memory versioning to take aliasing and method calls
into account. Use more instructions for the null check
elimination. Return the local value name of the register
defined by the instruction if applicable.
Change-Id: I4560bc680ae1ad553a7a00fa092c937e3da9fbbe
diff --git a/compiler/dex/local_value_numbering.h b/compiler/dex/local_value_numbering.h
index 33ca8f1..348bedc 100644
--- a/compiler/dex/local_value_numbering.h
+++ b/compiler/dex/local_value_numbering.h
@@ -24,16 +24,78 @@
namespace art {
-// Key is s_reg, value is value name.
-typedef SafeMap<uint16_t, uint16_t> SregValueMap;
-// Key is concatenation of quad, value is value name.
-typedef SafeMap<uint64_t, uint16_t> ValueMap;
-// Key represents a memory address, value is generation.
-typedef SafeMap<uint32_t, uint16_t> MemoryVersionMap;
+class DexFile;
class LocalValueNumbering {
+ private:
+ // Field types correspond to the ordering of GET/PUT instructions; this order is the same
+ // for IGET, IPUT, SGET, SPUT, AGET and APUT:
+ // 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;
+
+ // FieldReference represents either a unique resolved field or all unresolved fields together.
+ struct FieldReference {
+ const DexFile* dex_file;
+ uint16_t field_idx;
+ };
+
+ 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;
+ }
+ };
+
+ struct MemoryVersionKey {
+ uint16_t base;
+ uint16_t field_id;
+ uint16_t type;
+ };
+
+ struct MemoryVersionKeyComparator {
+ bool operator()(const MemoryVersionKey& lhs, const MemoryVersionKey& rhs) const {
+ if (lhs.base != rhs.base) {
+ return lhs.base < rhs.base;
+ }
+ if (lhs.field_id != rhs.field_id) {
+ return lhs.field_id < rhs.field_id;
+ }
+ return lhs.type < rhs.type;
+ }
+ };
+
+ // Key is s_reg, value is value name.
+ typedef SafeMap<uint16_t, uint16_t> SregValueMap;
+ // Key is concatenation of opcode, operand1, operand2 and modifier, value is value name.
+ typedef SafeMap<uint64_t, uint16_t> ValueMap;
+ // Key represents a memory address, value is generation.
+ typedef SafeMap<MemoryVersionKey, uint16_t, MemoryVersionKeyComparator> MemoryVersionMap;
+ // Maps field key to field id for resolved fields.
+ typedef SafeMap<FieldReference, uint32_t, FieldReferenceComparator> FieldIndexMap;
+
public:
- explicit LocalValueNumbering(CompilationUnit* cu) : cu_(cu) {}
+ explicit LocalValueNumbering(CompilationUnit* cu)
+ : cu_(cu),
+ sreg_value_map_(),
+ sreg_wide_value_map_(),
+ value_map_(),
+ next_memory_version_(1u),
+ global_memory_version_(0u),
+ memory_version_map_(),
+ field_index_map_(),
+ non_aliasing_refs_(),
+ null_checked_() {
+ std::fill_n(unresolved_sfield_version_, kFieldTypeCount, 0u);
+ std::fill_n(unresolved_ifield_version_, kFieldTypeCount, 0u);
+ }
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 |
@@ -59,29 +121,6 @@
return (it != value_map_.end());
};
- uint16_t GetMemoryVersion(uint16_t base, uint16_t field) {
- uint32_t key = (base << 16) | field;
- uint16_t res;
- MemoryVersionMap::iterator it = memory_version_map_.find(key);
- if (it == memory_version_map_.end()) {
- res = 0;
- memory_version_map_.Put(key, res);
- } else {
- res = it->second;
- }
- return res;
- };
-
- void AdvanceMemoryVersion(uint16_t base, uint16_t field) {
- uint32_t key = (base << 16) | field;
- MemoryVersionMap::iterator it = memory_version_map_.find(key);
- if (it == memory_version_map_.end()) {
- memory_version_map_.Put(key, 0);
- } else {
- it->second++;
- }
- };
-
void SetOperandValue(uint16_t s_reg, uint16_t value) {
SregValueMap::iterator it = sreg_value_map_.find(s_reg);
if (it != sreg_value_map_.end()) {
@@ -129,11 +168,28 @@
uint16_t GetValueNumber(MIR* mir);
private:
+ uint16_t GetFieldId(const DexFile* dex_file, uint16_t field_idx);
+ void AdvanceGlobalMemory();
+ uint16_t GetMemoryVersion(uint16_t base, uint16_t field, uint16_t type);
+ uint16_t AdvanceMemoryVersion(uint16_t base, uint16_t field, uint16_t type);
+ uint16_t MarkNonAliasingNonNull(MIR* mir);
+ void MakeArgsAliasing(MIR* mir);
+ void HandleNullCheck(MIR* mir, uint16_t reg);
+ void HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index);
+ void HandlePutObject(MIR* mir);
+
CompilationUnit* const cu_;
SregValueMap sreg_value_map_;
SregValueMap sreg_wide_value_map_;
ValueMap value_map_;
+ uint16_t next_memory_version_;
+ uint16_t global_memory_version_;
+ uint16_t unresolved_sfield_version_[kFieldTypeCount];
+ uint16_t unresolved_ifield_version_[kFieldTypeCount];
MemoryVersionMap memory_version_map_;
+ FieldIndexMap field_index_map_;
+ // Value names of references to objects that cannot be reached through a different value name.
+ std::set<uint16_t> non_aliasing_refs_;
std::set<uint16_t> null_checked_;
};