local_value_numbering.h revision f418f3227e0001c8d75257ceff0c248cc406d81a
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#ifndef ART_COMPILER_DEX_LOCAL_VALUE_NUMBERING_H_ 18#define ART_COMPILER_DEX_LOCAL_VALUE_NUMBERING_H_ 19 20#include <memory> 21 22#include "compiler_internals.h" 23#include "utils/scoped_arena_allocator.h" 24#include "utils/scoped_arena_containers.h" 25 26namespace art { 27 28class DexFile; 29class MirFieldInfo; 30 31class LocalValueNumbering { 32 public: 33 LocalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator); 34 35 uint16_t GetValueNumber(MIR* mir); 36 37 // LocalValueNumbering should be allocated on the ArenaStack (or the native stack). 38 static void* operator new(size_t size, ScopedArenaAllocator* allocator) { 39 return allocator->Alloc(sizeof(LocalValueNumbering), kArenaAllocMIR); 40 } 41 42 // Allow delete-expression to destroy a LocalValueNumbering object without deallocation. 43 static void operator delete(void* ptr) { UNUSED(ptr); } 44 45 // Checks that the value names didn't overflow. 46 bool Good() const { 47 return last_value_ < kNoValue; 48 } 49 50 private: 51 static constexpr uint16_t kNoValue = 0xffffu; 52 53 // Field types correspond to the ordering of GET/PUT instructions; this order is the same 54 // for IGET, IPUT, SGET, SPUT, AGET and APUT: 55 // op 0 56 // op_WIDE 1 57 // op_OBJECT 2 58 // op_BOOLEAN 3 59 // op_BYTE 4 60 // op_CHAR 5 61 // op_SHORT 6 62 static constexpr size_t kFieldTypeCount = 7; 63 64 // FieldReference represents a unique resolved field. 65 struct FieldReference { 66 const DexFile* dex_file; 67 uint16_t field_idx; 68 }; 69 70 struct FieldReferenceComparator { 71 bool operator()(const FieldReference& lhs, const FieldReference& rhs) const { 72 if (lhs.field_idx != rhs.field_idx) { 73 return lhs.field_idx < rhs.field_idx; 74 } 75 return lhs.dex_file < rhs.dex_file; 76 } 77 }; 78 79 // Maps field key to field id for resolved fields. 80 typedef ScopedArenaSafeMap<FieldReference, uint32_t, FieldReferenceComparator> FieldIndexMap; 81 82 struct RangeCheckKey { 83 uint16_t array; 84 uint16_t index; 85 }; 86 87 struct RangeCheckKeyComparator { 88 bool operator()(const RangeCheckKey& lhs, const RangeCheckKey& rhs) const { 89 if (lhs.array != rhs.array) { 90 return lhs.array < rhs.array; 91 } 92 return lhs.index < rhs.index; 93 } 94 }; 95 96 typedef ScopedArenaSet<RangeCheckKey, RangeCheckKeyComparator> RangeCheckSet; 97 98 typedef ScopedArenaSafeMap<uint16_t, uint16_t> AliasingIFieldVersionMap; 99 typedef ScopedArenaSafeMap<uint16_t, uint16_t> NonAliasingArrayVersionMap; 100 101 struct NonAliasingIFieldKey { 102 uint16_t base; 103 uint16_t field_id; 104 uint16_t type; 105 }; 106 107 struct NonAliasingIFieldKeyComparator { 108 bool operator()(const NonAliasingIFieldKey& lhs, const NonAliasingIFieldKey& rhs) const { 109 // Compare the type first. This allows iterating across all the entries for a certain type 110 // as needed when we need to purge them for an unresolved field IPUT. 111 if (lhs.type != rhs.type) { 112 return lhs.type < rhs.type; 113 } 114 // Compare the field second. This allows iterating across all the entries for a certain 115 // field as needed when we need to purge them for an aliasing field IPUT. 116 if (lhs.field_id != rhs.field_id) { 117 return lhs.field_id < rhs.field_id; 118 } 119 // Compare the base last. 120 return lhs.base < rhs.base; 121 } 122 }; 123 124 // Set of instance fields still holding non-aliased values after the base has been stored. 125 typedef ScopedArenaSet<NonAliasingIFieldKey, NonAliasingIFieldKeyComparator> NonAliasingFieldSet; 126 127 struct EscapedArrayKey { 128 uint16_t base; 129 uint16_t type; 130 }; 131 132 struct EscapedArrayKeyComparator { 133 bool operator()(const EscapedArrayKey& lhs, const EscapedArrayKey& rhs) const { 134 // Compare the type first. This allows iterating across all the entries for a certain type 135 // as needed when we need to purge them for an unresolved field APUT. 136 if (lhs.type != rhs.type) { 137 return lhs.type < rhs.type; 138 } 139 // Compare the base last. 140 return lhs.base < rhs.base; 141 } 142 }; 143 144 // Set of previously non-aliasing array refs that escaped. 145 typedef ScopedArenaSet<EscapedArrayKey, EscapedArrayKeyComparator> EscapedArraySet; 146 147 // Key is s_reg, value is value name. 148 typedef ScopedArenaSafeMap<uint16_t, uint16_t> SregValueMap; 149 // Key is concatenation of opcode, operand1, operand2 and modifier, value is value name. 150 typedef ScopedArenaSafeMap<uint64_t, uint16_t> ValueMap; 151 // Key represents a memory address, value is generation. 152 // A set of value names. 153 typedef ScopedArenaSet<uint16_t> ValueNameSet; 154 155 static uint64_t BuildKey(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) { 156 return (static_cast<uint64_t>(op) << 48 | static_cast<uint64_t>(operand1) << 32 | 157 static_cast<uint64_t>(operand2) << 16 | static_cast<uint64_t>(modifier)); 158 }; 159 160 static uint16_t ExtractOp(uint64_t key) { 161 return static_cast<uint16_t>(key >> 48); 162 } 163 164 static uint16_t ExtractOperand1(uint64_t key) { 165 return static_cast<uint16_t>(key >> 32); 166 } 167 168 static uint16_t ExtractOperand2(uint64_t key) { 169 return static_cast<uint16_t>(key >> 16); 170 } 171 172 static uint16_t ExtractModifier(uint64_t key) { 173 return static_cast<uint16_t>(key); 174 } 175 176 static bool EqualOpAndOperand1(uint64_t key1, uint64_t key2) { 177 return static_cast<uint32_t>(key1 >> 32) == static_cast<uint32_t>(key2 >> 32); 178 } 179 180 uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) { 181 uint16_t res; 182 uint64_t key = BuildKey(op, operand1, operand2, modifier); 183 ValueMap::iterator it = value_map_.find(key); 184 if (it != value_map_.end()) { 185 res = it->second; 186 } else { 187 ++last_value_; 188 res = last_value_; 189 value_map_.Put(key, res); 190 } 191 return res; 192 }; 193 194 void StoreValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier, 195 uint16_t value) { 196 uint64_t key = BuildKey(op, operand1, operand2, modifier); 197 value_map_.Overwrite(key, value); 198 } 199 200 bool HasValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier, 201 uint16_t value) const { 202 uint64_t key = BuildKey(op, operand1, operand2, modifier); 203 ValueMap::const_iterator it = value_map_.find(key); 204 return (it != value_map_.end() && it->second == value); 205 }; 206 207 bool ValueExists(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) const { 208 uint64_t key = BuildKey(op, operand1, operand2, modifier); 209 ValueMap::const_iterator it = value_map_.find(key); 210 return (it != value_map_.end()); 211 }; 212 213 void SetOperandValue(uint16_t s_reg, uint16_t value) { 214 SregValueMap::iterator it = sreg_value_map_.find(s_reg); 215 if (it != sreg_value_map_.end()) { 216 DCHECK_EQ(it->second, value); 217 } else { 218 sreg_value_map_.Put(s_reg, value); 219 } 220 }; 221 222 uint16_t GetOperandValue(int s_reg) { 223 uint16_t res = kNoValue; 224 SregValueMap::iterator it = sreg_value_map_.find(s_reg); 225 if (it != sreg_value_map_.end()) { 226 res = it->second; 227 } else { 228 // First use 229 res = LookupValue(kNoValue, s_reg, kNoValue, kNoValue); 230 sreg_value_map_.Put(s_reg, res); 231 } 232 return res; 233 }; 234 235 void SetOperandValueWide(uint16_t s_reg, uint16_t value) { 236 SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg); 237 if (it != sreg_wide_value_map_.end()) { 238 DCHECK_EQ(it->second, value); 239 } else { 240 sreg_wide_value_map_.Put(s_reg, value); 241 } 242 }; 243 244 uint16_t GetOperandValueWide(int s_reg) { 245 uint16_t res = kNoValue; 246 SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg); 247 if (it != sreg_wide_value_map_.end()) { 248 res = it->second; 249 } else { 250 // First use 251 res = LookupValue(kNoValue, s_reg, kNoValue, kNoValue); 252 sreg_wide_value_map_.Put(s_reg, res); 253 } 254 return res; 255 }; 256 257 uint16_t GetFieldId(const MirFieldInfo& field_info); 258 uint16_t MarkNonAliasingNonNull(MIR* mir); 259 bool IsNonAliasing(uint16_t reg); 260 bool IsNonAliasingIField(uint16_t reg, uint16_t field_id, uint16_t type); 261 bool IsNonAliasingArray(uint16_t reg, uint16_t type); 262 void HandleNullCheck(MIR* mir, uint16_t reg); 263 void HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index); 264 void HandlePutObject(MIR* mir); 265 void HandleEscapingRef(uint16_t base); 266 uint16_t HandleAGet(MIR* mir, uint16_t opcode); 267 void HandleAPut(MIR* mir, uint16_t opcode); 268 uint16_t HandleIGet(MIR* mir, uint16_t opcode); 269 void HandleIPut(MIR* mir, uint16_t opcode); 270 uint16_t HandleSGet(MIR* mir, uint16_t opcode); 271 void HandleSPut(MIR* mir, uint16_t opcode); 272 void HandleInvokeOrClInit(MIR* mir); 273 274 CompilationUnit* const cu_; 275 276 // We have 32-bit last_value_ so that we can detect when we run out of value names, see Good(). 277 // We usually don't check Good() until the end of LVN unless we're about to modify code. 278 uint32_t last_value_; 279 280 SregValueMap sreg_value_map_; 281 SregValueMap sreg_wide_value_map_; 282 ValueMap value_map_; 283 284 // Data for dealing with memory clobbering and store/load aliasing. 285 uint16_t global_memory_version_; 286 uint16_t unresolved_sfield_version_[kFieldTypeCount]; 287 uint16_t unresolved_ifield_version_[kFieldTypeCount]; 288 uint16_t aliasing_array_version_[kFieldTypeCount]; 289 AliasingIFieldVersionMap aliasing_ifield_version_map_; 290 NonAliasingArrayVersionMap non_aliasing_array_version_map_; 291 FieldIndexMap field_index_map_; 292 // Value names of references to objects that cannot be reached through a different value name. 293 ValueNameSet non_aliasing_refs_; 294 // Instance fields still holding non-aliased values after the base has escaped. 295 NonAliasingFieldSet non_aliasing_ifields_; 296 // Previously non-aliasing array refs that escaped but can still be used for non-aliasing AGET. 297 EscapedArraySet escaped_array_refs_; 298 299 // Range check and null check elimination. 300 RangeCheckSet range_checked_; 301 ValueNameSet null_checked_; 302 303 DISALLOW_COPY_AND_ASSIGN(LocalValueNumbering); 304}; 305 306} // namespace art 307 308#endif // ART_COMPILER_DEX_LOCAL_VALUE_NUMBERING_H_ 309