| /* |
| * 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 |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "local_value_numbering.h" |
| |
| #include "mir_field_info.h" |
| #include "mir_graph.h" |
| |
| namespace art { |
| |
| namespace { // anonymous namespace |
| |
| // Operations used for value map keys instead of actual opcode. |
| static constexpr uint16_t kInvokeMemoryVersionBumpOp = Instruction::INVOKE_DIRECT; |
| static constexpr uint16_t kUnresolvedSFieldOp = Instruction::SPUT; |
| static constexpr uint16_t kResolvedSFieldOp = Instruction::SGET; |
| static constexpr uint16_t kUnresolvedIFieldOp = Instruction::IPUT; |
| static constexpr uint16_t kNonAliasingIFieldOp = Instruction::IGET; |
| static constexpr uint16_t kAliasingIFieldOp = Instruction::IGET_WIDE; |
| static constexpr uint16_t kAliasingIFieldStartVersionOp = Instruction::IGET_WIDE; |
| static constexpr uint16_t kAliasingIFieldBumpVersionOp = Instruction::IGET_OBJECT; |
| static constexpr uint16_t kArrayAccessLocOp = Instruction::APUT; |
| static constexpr uint16_t kNonAliasingArrayOp = Instruction::AGET; |
| static constexpr uint16_t kNonAliasingArrayStartVersionOp = Instruction::AGET_WIDE; |
| static constexpr uint16_t kAliasingArrayOp = Instruction::AGET_OBJECT; |
| static constexpr uint16_t kAliasingArrayMemoryVersionOp = Instruction::AGET_BOOLEAN; |
| static constexpr uint16_t kAliasingArrayBumpVersionOp = Instruction::AGET_BYTE; |
| |
| } // anonymous namespace |
| |
| LocalValueNumbering::LocalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator) |
| : cu_(cu), |
| last_value_(0u), |
| sreg_value_map_(std::less<uint16_t>(), allocator->Adapter()), |
| sreg_wide_value_map_(std::less<uint16_t>(), allocator->Adapter()), |
| value_map_(std::less<uint64_t>(), allocator->Adapter()), |
| global_memory_version_(0u), |
| aliasing_ifield_version_map_(std::less<uint16_t>(), allocator->Adapter()), |
| non_aliasing_array_version_map_(std::less<uint16_t>(), allocator->Adapter()), |
| field_index_map_(FieldReferenceComparator(), allocator->Adapter()), |
| non_aliasing_refs_(std::less<uint16_t>(), allocator->Adapter()), |
| non_aliasing_ifields_(NonAliasingIFieldKeyComparator(), allocator->Adapter()), |
| escaped_array_refs_(EscapedArrayKeyComparator(), allocator->Adapter()), |
| range_checked_(RangeCheckKeyComparator() , allocator->Adapter()), |
| null_checked_(std::less<uint16_t>(), allocator->Adapter()) { |
| std::fill_n(unresolved_sfield_version_, kFieldTypeCount, 0u); |
| std::fill_n(unresolved_ifield_version_, kFieldTypeCount, 0u); |
| std::fill_n(aliasing_array_version_, kFieldTypeCount, 0u); |
| } |
| |
| uint16_t LocalValueNumbering::GetFieldId(const MirFieldInfo& field_info) { |
| FieldReference key = { field_info.DeclaringDexFile(), field_info.DeclaringFieldIndex() }; |
| auto it = field_index_map_.find(key); |
| if (it != field_index_map_.end()) { |
| return it->second; |
| } |
| uint16_t id = field_index_map_.size(); |
| field_index_map_.Put(key, id); |
| return id; |
| } |
| |
| uint16_t LocalValueNumbering::MarkNonAliasingNonNull(MIR* mir) { |
| uint16_t res = GetOperandValue(mir->ssa_rep->defs[0]); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| DCHECK(null_checked_.find(res) == null_checked_.end()); |
| null_checked_.insert(res); |
| non_aliasing_refs_.insert(res); |
| return res; |
| } |
| |
| bool LocalValueNumbering::IsNonAliasing(uint16_t reg) { |
| return non_aliasing_refs_.find(reg) != non_aliasing_refs_.end(); |
| } |
| |
| bool LocalValueNumbering::IsNonAliasingIField(uint16_t reg, uint16_t field_id, uint16_t type) { |
| if (IsNonAliasing(reg)) { |
| return true; |
| } |
| NonAliasingIFieldKey key = { reg, field_id, type }; |
| return non_aliasing_ifields_.count(key) != 0u; |
| } |
| |
| bool LocalValueNumbering::IsNonAliasingArray(uint16_t reg, uint16_t type) { |
| if (IsNonAliasing(reg)) { |
| return true; |
| } |
| EscapedArrayKey key = { reg, type }; |
| return escaped_array_refs_.count(key) != 0u; |
| } |
| |
| |
| void LocalValueNumbering::HandleNullCheck(MIR* mir, uint16_t reg) { |
| auto lb = null_checked_.lower_bound(reg); |
| if (lb != null_checked_.end() && *lb == reg) { |
| if (LIKELY(Good())) { |
| if (cu_->verbose) { |
| LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset; |
| } |
| mir->optimization_flags |= MIR_IGNORE_NULL_CHECK; |
| } |
| } else { |
| null_checked_.insert(lb, reg); |
| } |
| } |
| |
| void LocalValueNumbering::HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index) { |
| RangeCheckKey key = { array, index }; |
| auto lb = range_checked_.lower_bound(key); |
| if (lb != range_checked_.end() && !RangeCheckKeyComparator()(key, *lb)) { |
| if (LIKELY(Good())) { |
| if (cu_->verbose) { |
| LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset; |
| } |
| mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK; |
| } |
| } else { |
| // Mark range check completed. |
| range_checked_.insert(lb, key); |
| } |
| } |
| |
| void LocalValueNumbering::HandlePutObject(MIR* mir) { |
| // If we're storing a non-aliasing reference, stop tracking it as non-aliasing now. |
| uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]); |
| HandleEscapingRef(base); |
| } |
| |
| void LocalValueNumbering::HandleEscapingRef(uint16_t base) { |
| auto it = non_aliasing_refs_.find(base); |
| if (it != non_aliasing_refs_.end()) { |
| uint64_t iget_key = BuildKey(Instruction::IGET, base, 0u, 0u); |
| for (auto iget_it = value_map_.lower_bound(iget_key), iget_end = value_map_.end(); |
| iget_it != iget_end && EqualOpAndOperand1(iget_it->first, iget_key); ++iget_it) { |
| uint16_t field_id = ExtractOperand2(iget_it->first); |
| uint16_t type = ExtractModifier(iget_it->first); |
| NonAliasingIFieldKey key = { base, field_id, type }; |
| non_aliasing_ifields_.insert(key); |
| } |
| uint64_t aget_key = BuildKey(kNonAliasingArrayStartVersionOp, base, 0u, 0u); |
| auto aget_it = value_map_.lower_bound(aget_key); |
| if (aget_it != value_map_.end() && EqualOpAndOperand1(aget_key, aget_it->first)) { |
| DCHECK_EQ(ExtractOperand2(aget_it->first), kNoValue); |
| uint16_t type = ExtractModifier(aget_it->first); |
| EscapedArrayKey key = { base, type }; |
| escaped_array_refs_.insert(key); |
| } |
| non_aliasing_refs_.erase(it); |
| } |
| } |
| |
| uint16_t LocalValueNumbering::HandleAGet(MIR* mir, uint16_t opcode) { |
| // uint16_t type = opcode - Instruction::AGET; |
| uint16_t array = GetOperandValue(mir->ssa_rep->uses[0]); |
| HandleNullCheck(mir, array); |
| uint16_t index = GetOperandValue(mir->ssa_rep->uses[1]); |
| HandleRangeCheck(mir, array, index); |
| uint16_t type = opcode - Instruction::AGET; |
| // Establish value number for loaded register. |
| uint16_t res; |
| if (IsNonAliasingArray(array, type)) { |
| // Get the start version that accounts for aliasing within the array (different index names). |
| uint16_t start_version = LookupValue(kNonAliasingArrayStartVersionOp, array, kNoValue, type); |
| // Find the current version from the non_aliasing_array_version_map_. |
| uint16_t memory_version = start_version; |
| auto it = non_aliasing_array_version_map_.find(start_version); |
| if (it != non_aliasing_array_version_map_.end()) { |
| memory_version = it->second; |
| } else { |
| // Just use the start_version. |
| } |
| res = LookupValue(kNonAliasingArrayOp, array, index, memory_version); |
| } else { |
| // Get the memory version of aliased array accesses of this type. |
| uint16_t memory_version = LookupValue(kAliasingArrayMemoryVersionOp, global_memory_version_, |
| aliasing_array_version_[type], kNoValue); |
| res = LookupValue(kAliasingArrayOp, array, index, memory_version); |
| } |
| if (opcode == Instruction::AGET_WIDE) { |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } else { |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| } |
| return res; |
| } |
| |
| void LocalValueNumbering::HandleAPut(MIR* mir, uint16_t opcode) { |
| int array_idx = (opcode == Instruction::APUT_WIDE) ? 2 : 1; |
| int index_idx = array_idx + 1; |
| uint16_t array = GetOperandValue(mir->ssa_rep->uses[array_idx]); |
| HandleNullCheck(mir, array); |
| uint16_t index = GetOperandValue(mir->ssa_rep->uses[index_idx]); |
| HandleRangeCheck(mir, array, index); |
| |
| uint16_t type = opcode - Instruction::APUT; |
| uint16_t value = (opcode == Instruction::APUT_WIDE) |
| ? GetOperandValueWide(mir->ssa_rep->uses[0]) |
| : GetOperandValue(mir->ssa_rep->uses[0]); |
| if (IsNonAliasing(array)) { |
| // Get the start version that accounts for aliasing within the array (different index values). |
| uint16_t start_version = LookupValue(kNonAliasingArrayStartVersionOp, array, kNoValue, type); |
| auto it = non_aliasing_array_version_map_.find(start_version); |
| uint16_t memory_version = start_version; |
| if (it != non_aliasing_array_version_map_.end()) { |
| memory_version = it->second; |
| } |
| // We need to take 4 values (array, index, memory_version, value) into account for bumping |
| // the memory version but the key can take only 3. Merge array and index into a location. |
| uint16_t array_access_location = LookupValue(kArrayAccessLocOp, array, index, kNoValue); |
| // Bump the version, adding to the chain. |
| memory_version = LookupValue(kAliasingArrayBumpVersionOp, memory_version, |
| array_access_location, value); |
| non_aliasing_array_version_map_.Overwrite(start_version, memory_version); |
| StoreValue(kNonAliasingArrayOp, array, index, memory_version, value); |
| } else { |
| // Get the memory version based on global_memory_version_ and aliasing_array_version_[type]. |
| uint16_t memory_version = LookupValue(kAliasingArrayMemoryVersionOp, global_memory_version_, |
| aliasing_array_version_[type], kNoValue); |
| if (HasValue(kAliasingArrayOp, array, index, memory_version, value)) { |
| // This APUT can be eliminated, it stores the same value that's already in the field. |
| // TODO: Eliminate the APUT. |
| return; |
| } |
| // We need to take 4 values (array, index, memory_version, value) into account for bumping |
| // the memory version but the key can take only 3. Merge array and index into a location. |
| uint16_t array_access_location = LookupValue(kArrayAccessLocOp, array, index, kNoValue); |
| // Bump the version, adding to the chain. |
| uint16_t bumped_version = LookupValue(kAliasingArrayBumpVersionOp, memory_version, |
| array_access_location, value); |
| aliasing_array_version_[type] = bumped_version; |
| memory_version = LookupValue(kAliasingArrayMemoryVersionOp, global_memory_version_, |
| bumped_version, kNoValue); |
| StoreValue(kAliasingArrayOp, array, index, memory_version, value); |
| |
| // Clear escaped array refs for this type. |
| EscapedArrayKey array_key = { type, 0u }; |
| auto it = escaped_array_refs_.lower_bound(array_key), end = escaped_array_refs_.end(); |
| while (it != end && it->type == type) { |
| it = escaped_array_refs_.erase(it); |
| } |
| } |
| } |
| |
| uint16_t LocalValueNumbering::HandleIGet(MIR* mir, uint16_t opcode) { |
| uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]); |
| HandleNullCheck(mir, base); |
| const MirFieldInfo& field_info = cu_->mir_graph->GetIFieldLoweringInfo(mir); |
| uint16_t res; |
| if (!field_info.IsResolved() || field_info.IsVolatile()) { |
| // Volatile fields always get a new memory version; field id is irrelevant. |
| // Unresolved fields may be volatile, so handle them as such to be safe. |
| // Use result s_reg - will be unique. |
| res = LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue); |
| } else { |
| uint16_t type = opcode - Instruction::IGET; |
| uint16_t field_id = GetFieldId(field_info); |
| if (IsNonAliasingIField(base, field_id, type)) { |
| res = LookupValue(kNonAliasingIFieldOp, base, field_id, type); |
| } else { |
| // Get the start version that accounts for aliasing with unresolved fields of the same type |
| // and make it unique for the field by including the field_id. |
| uint16_t start_version = LookupValue(kAliasingIFieldStartVersionOp, global_memory_version_, |
| unresolved_ifield_version_[type], field_id); |
| // Find the current version from the aliasing_ifield_version_map_. |
| uint16_t memory_version = start_version; |
| auto version_it = aliasing_ifield_version_map_.find(start_version); |
| if (version_it != aliasing_ifield_version_map_.end()) { |
| memory_version = version_it->second; |
| } else { |
| // Just use the start_version. |
| } |
| res = LookupValue(kAliasingIFieldOp, base, field_id, memory_version); |
| } |
| } |
| if (opcode == Instruction::IGET_WIDE) { |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } else { |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| } |
| return res; |
| } |
| |
| void LocalValueNumbering::HandleIPut(MIR* mir, uint16_t opcode) { |
| uint16_t type = opcode - Instruction::IPUT; |
| int base_reg = (opcode == Instruction::IPUT_WIDE) ? 2 : 1; |
| uint16_t base = GetOperandValue(mir->ssa_rep->uses[base_reg]); |
| HandleNullCheck(mir, base); |
| const MirFieldInfo& field_info = cu_->mir_graph->GetIFieldLoweringInfo(mir); |
| if (!field_info.IsResolved()) { |
| // Unresolved fields always alias with everything of the same type. |
| // Use mir->offset as modifier; without elaborate inlining, it will be unique. |
| unresolved_ifield_version_[type] = |
| LookupValue(kUnresolvedIFieldOp, kNoValue, kNoValue, mir->offset); |
| |
| // Treat fields of escaped references of the same type as potentially modified. |
| NonAliasingIFieldKey key = { type, 0u, 0u }; // lowest possible key of this type. |
| auto it = non_aliasing_ifields_.lower_bound(key), end = non_aliasing_ifields_.end(); |
| while (it != end && it->type == type) { |
| it = non_aliasing_ifields_.erase(it); |
| } |
| } else if (field_info.IsVolatile()) { |
| // Nothing to do, resolved volatile fields always get a new memory version anyway and |
| // can't alias with resolved non-volatile fields. |
| } else { |
| uint16_t field_id = GetFieldId(field_info); |
| uint16_t value = (opcode == Instruction::IPUT_WIDE) |
| ? GetOperandValueWide(mir->ssa_rep->uses[0]) |
| : GetOperandValue(mir->ssa_rep->uses[0]); |
| if (IsNonAliasing(base)) { |
| StoreValue(kNonAliasingIFieldOp, base, field_id, type, value); |
| } else { |
| // Get the start version that accounts for aliasing with unresolved fields of the same type |
| // and make it unique for the field by including the field_id. |
| uint16_t start_version = LookupValue(kAliasingIFieldStartVersionOp, global_memory_version_, |
| unresolved_ifield_version_[type], field_id); |
| // Find the old version from the aliasing_ifield_version_map_. |
| uint16_t old_version = start_version; |
| auto version_it = aliasing_ifield_version_map_.find(start_version); |
| if (version_it != aliasing_ifield_version_map_.end()) { |
| old_version = version_it->second; |
| } |
| // Check if the field currently contains the value, making this a NOP. |
| if (HasValue(kAliasingIFieldOp, base, field_id, old_version, value)) { |
| // This IPUT can be eliminated, it stores the same value that's already in the field. |
| // TODO: Eliminate the IPUT. |
| return; |
| } |
| // Bump the version, adding to the chain started by start_version. |
| uint16_t memory_version = LookupValue(kAliasingIFieldBumpVersionOp, old_version, base, value); |
| // Update the aliasing_ifield_version_map_ so that HandleIGet() can get the memory_version |
| // without knowing the values used to build the chain. |
| aliasing_ifield_version_map_.Overwrite(start_version, memory_version); |
| StoreValue(kAliasingIFieldOp, base, field_id, memory_version, value); |
| |
| // Clear non-aliasing fields for this field_id. |
| NonAliasingIFieldKey field_key = { type, field_id, 0u }; |
| auto it = non_aliasing_ifields_.lower_bound(field_key), end = non_aliasing_ifields_.end(); |
| while (it != end && it->field_id == field_id) { |
| DCHECK_EQ(type, it->type); |
| it = non_aliasing_ifields_.erase(it); |
| } |
| } |
| } |
| } |
| |
| uint16_t LocalValueNumbering::HandleSGet(MIR* mir, uint16_t opcode) { |
| const MirFieldInfo& field_info = cu_->mir_graph->GetSFieldLoweringInfo(mir); |
| uint16_t res; |
| if (!field_info.IsResolved() || field_info.IsVolatile()) { |
| // Volatile fields always get a new memory version; field id is irrelevant. |
| // Unresolved fields may be volatile, so handle them as such to be safe. |
| // Use result s_reg - will be unique. |
| res = LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue); |
| } else { |
| uint16_t field_id = GetFieldId(field_info); |
| // Resolved non-volatile static fields can alias with non-resolved fields of the same type, |
| // so we need to use unresolved_sfield_version_[type] in addition to global_memory_version_ |
| // to determine the version of the field. |
| uint16_t type = opcode - Instruction::SGET; |
| res = LookupValue(kResolvedSFieldOp, field_id, |
| unresolved_sfield_version_[type], global_memory_version_); |
| } |
| if (opcode == Instruction::SGET_WIDE) { |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } else { |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| } |
| return res; |
| } |
| |
| void LocalValueNumbering::HandleSPut(MIR* mir, uint16_t opcode) { |
| uint16_t type = opcode - Instruction::SPUT; |
| const MirFieldInfo& field_info = cu_->mir_graph->GetSFieldLoweringInfo(mir); |
| if (!field_info.IsResolved()) { |
| // Unresolved fields always alias with everything of the same type. |
| // Use mir->offset as modifier; without elaborate inlining, it will be unique. |
| unresolved_sfield_version_[type] = |
| LookupValue(kUnresolvedSFieldOp, kNoValue, kNoValue, mir->offset); |
| } else if (field_info.IsVolatile()) { |
| // Nothing to do, resolved volatile fields always get a new memory version anyway and |
| // can't alias with resolved non-volatile fields. |
| } else { |
| uint16_t field_id = GetFieldId(field_info); |
| uint16_t value = (opcode == Instruction::SPUT_WIDE) |
| ? GetOperandValueWide(mir->ssa_rep->uses[0]) |
| : GetOperandValue(mir->ssa_rep->uses[0]); |
| // Resolved non-volatile static fields can alias with non-resolved fields of the same type, |
| // so we need to use unresolved_sfield_version_[type] in addition to global_memory_version_ |
| // to determine the version of the field. |
| uint16_t type = opcode - Instruction::SGET; |
| StoreValue(kResolvedSFieldOp, field_id, |
| unresolved_sfield_version_[type], global_memory_version_, value); |
| } |
| } |
| |
| uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) { |
| uint16_t res = kNoValue; |
| uint16_t opcode = mir->dalvikInsn.opcode; |
| switch (opcode) { |
| case Instruction::NOP: |
| case Instruction::RETURN_VOID: |
| case Instruction::RETURN: |
| case Instruction::RETURN_OBJECT: |
| case Instruction::RETURN_WIDE: |
| case Instruction::MONITOR_ENTER: |
| case Instruction::MONITOR_EXIT: |
| case Instruction::GOTO: |
| case Instruction::GOTO_16: |
| case Instruction::GOTO_32: |
| case Instruction::CHECK_CAST: |
| case Instruction::THROW: |
| case Instruction::FILL_ARRAY_DATA: |
| case Instruction::PACKED_SWITCH: |
| case Instruction::SPARSE_SWITCH: |
| case Instruction::IF_EQ: |
| case Instruction::IF_NE: |
| case Instruction::IF_LT: |
| case Instruction::IF_GE: |
| case Instruction::IF_GT: |
| case Instruction::IF_LE: |
| case Instruction::IF_EQZ: |
| case Instruction::IF_NEZ: |
| case Instruction::IF_LTZ: |
| case Instruction::IF_GEZ: |
| case Instruction::IF_GTZ: |
| case Instruction::IF_LEZ: |
| case kMirOpFusedCmplFloat: |
| case kMirOpFusedCmpgFloat: |
| case kMirOpFusedCmplDouble: |
| case kMirOpFusedCmpgDouble: |
| case kMirOpFusedCmpLong: |
| // Nothing defined - take no action. |
| break; |
| |
| case Instruction::FILLED_NEW_ARRAY: |
| case Instruction::FILLED_NEW_ARRAY_RANGE: |
| // Nothing defined but the result will be unique and non-null. |
| if (mir->next != nullptr && mir->next->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) { |
| MarkNonAliasingNonNull(mir->next); |
| // TUNING: We could track value names stored in the array. |
| // The MOVE_RESULT_OBJECT will be processed next and we'll return the value name then. |
| } |
| // All args escaped (if references). |
| for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) { |
| uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]); |
| HandleEscapingRef(reg); |
| } |
| break; |
| |
| case Instruction::INVOKE_DIRECT: |
| case Instruction::INVOKE_DIRECT_RANGE: |
| case Instruction::INVOKE_VIRTUAL: |
| case Instruction::INVOKE_VIRTUAL_RANGE: |
| case Instruction::INVOKE_SUPER: |
| case Instruction::INVOKE_SUPER_RANGE: |
| case Instruction::INVOKE_INTERFACE: |
| case Instruction::INVOKE_INTERFACE_RANGE: { |
| // Nothing defined but handle the null check. |
| uint16_t reg = GetOperandValue(mir->ssa_rep->uses[0]); |
| HandleNullCheck(mir, reg); |
| } |
| // Intentional fall-through. |
| case Instruction::INVOKE_STATIC: |
| case Instruction::INVOKE_STATIC_RANGE: |
| if ((mir->optimization_flags & MIR_INLINED) == 0) { |
| // Use mir->offset as modifier; without elaborate inlining, it will be unique. |
| global_memory_version_ = LookupValue(kInvokeMemoryVersionBumpOp, 0u, 0u, mir->offset); |
| // Make ref args aliasing. |
| for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) { |
| uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]); |
| non_aliasing_refs_.erase(reg); |
| } |
| // All fields of escaped references need to be treated as potentially modified. |
| non_aliasing_ifields_.clear(); |
| // Array elements may also have been modified via escaped array refs. |
| escaped_array_refs_.clear(); |
| } |
| break; |
| |
| case Instruction::MOVE_RESULT: |
| case Instruction::MOVE_RESULT_OBJECT: |
| case Instruction::INSTANCE_OF: |
| // 1 result, treat as unique each time, use result s_reg - will be unique. |
| res = GetOperandValue(mir->ssa_rep->defs[0]); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| break; |
| case Instruction::MOVE_EXCEPTION: |
| case Instruction::NEW_INSTANCE: |
| case Instruction::CONST_CLASS: |
| case Instruction::NEW_ARRAY: |
| // 1 result, treat as unique each time, use result s_reg - will be unique. |
| res = MarkNonAliasingNonNull(mir); |
| break; |
| case Instruction::CONST_STRING: |
| case Instruction::CONST_STRING_JUMBO: |
| // These strings are internalized, so assign value based on the string pool index. |
| res = LookupValue(Instruction::CONST_STRING, Low16Bits(mir->dalvikInsn.vB), |
| High16Bits(mir->dalvikInsn.vB), 0); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| null_checked_.insert(res); // May already be there. |
| // NOTE: Hacking the contents of an internalized string via reflection is possible |
| // but the behavior is undefined. Therefore, we consider the string constant and |
| // the reference non-aliasing. |
| // TUNING: We could keep this property even if the reference "escapes". |
| non_aliasing_refs_.insert(res); // May already be there. |
| break; |
| case Instruction::MOVE_RESULT_WIDE: |
| // 1 wide result, treat as unique each time, use result s_reg - will be unique. |
| res = GetOperandValueWide(mir->ssa_rep->defs[0]); |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| break; |
| |
| case kMirOpPhi: |
| /* |
| * Because we'll only see phi nodes at the beginning of an extended basic block, |
| * we can ignore them. Revisit if we shift to global value numbering. |
| */ |
| break; |
| |
| case Instruction::MOVE: |
| case Instruction::MOVE_OBJECT: |
| case Instruction::MOVE_16: |
| case Instruction::MOVE_OBJECT_16: |
| case Instruction::MOVE_FROM16: |
| case Instruction::MOVE_OBJECT_FROM16: |
| case kMirOpCopy: |
| // Just copy value number of source to value number of result. |
| res = GetOperandValue(mir->ssa_rep->uses[0]); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| break; |
| |
| case Instruction::MOVE_WIDE: |
| case Instruction::MOVE_WIDE_16: |
| case Instruction::MOVE_WIDE_FROM16: |
| // Just copy value number of source to value number of result. |
| res = GetOperandValueWide(mir->ssa_rep->uses[0]); |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| break; |
| |
| case Instruction::CONST: |
| case Instruction::CONST_4: |
| case Instruction::CONST_16: |
| res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB), |
| High16Bits(mir->dalvikInsn.vB), 0); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| break; |
| |
| case Instruction::CONST_HIGH16: |
| res = LookupValue(Instruction::CONST, 0, mir->dalvikInsn.vB, 0); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| break; |
| |
| case Instruction::CONST_WIDE_16: |
| case Instruction::CONST_WIDE_32: { |
| uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB), |
| High16Bits(mir->dalvikInsn.vB >> 16), 1); |
| uint16_t high_res; |
| if (mir->dalvikInsn.vB & 0x80000000) { |
| high_res = LookupValue(Instruction::CONST, 0xffff, 0xffff, 2); |
| } else { |
| high_res = LookupValue(Instruction::CONST, 0, 0, 2); |
| } |
| res = LookupValue(Instruction::CONST, low_res, high_res, 3); |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::CONST_WIDE: { |
| uint32_t low_word = Low32Bits(mir->dalvikInsn.vB_wide); |
| uint32_t high_word = High32Bits(mir->dalvikInsn.vB_wide); |
| uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(low_word), |
| High16Bits(low_word), 1); |
| uint16_t high_res = LookupValue(Instruction::CONST, Low16Bits(high_word), |
| High16Bits(high_word), 2); |
| res = LookupValue(Instruction::CONST, low_res, high_res, 3); |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::CONST_WIDE_HIGH16: { |
| uint16_t low_res = LookupValue(Instruction::CONST, 0, 0, 1); |
| uint16_t high_res = LookupValue(Instruction::CONST, 0, Low16Bits(mir->dalvikInsn.vB), 2); |
| res = LookupValue(Instruction::CONST, low_res, high_res, 3); |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::ARRAY_LENGTH: |
| case Instruction::NEG_INT: |
| case Instruction::NOT_INT: |
| case Instruction::NEG_FLOAT: |
| case Instruction::INT_TO_BYTE: |
| case Instruction::INT_TO_SHORT: |
| case Instruction::INT_TO_CHAR: |
| case Instruction::INT_TO_FLOAT: |
| case Instruction::FLOAT_TO_INT: { |
| // res = op + 1 operand |
| uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); |
| res = LookupValue(opcode, operand1, kNoValue, kNoValue); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::LONG_TO_FLOAT: |
| case Instruction::LONG_TO_INT: |
| case Instruction::DOUBLE_TO_FLOAT: |
| case Instruction::DOUBLE_TO_INT: { |
| // res = op + 1 wide operand |
| uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); |
| res = LookupValue(opcode, operand1, kNoValue, kNoValue); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| |
| case Instruction::DOUBLE_TO_LONG: |
| case Instruction::LONG_TO_DOUBLE: |
| case Instruction::NEG_LONG: |
| case Instruction::NOT_LONG: |
| case Instruction::NEG_DOUBLE: { |
| // wide res = op + 1 wide operand |
| uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); |
| res = LookupValue(opcode, operand1, kNoValue, kNoValue); |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::FLOAT_TO_DOUBLE: |
| case Instruction::FLOAT_TO_LONG: |
| case Instruction::INT_TO_DOUBLE: |
| case Instruction::INT_TO_LONG: { |
| // wide res = op + 1 operand |
| uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); |
| res = LookupValue(opcode, operand1, kNoValue, kNoValue); |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::CMPL_DOUBLE: |
| case Instruction::CMPG_DOUBLE: |
| case Instruction::CMP_LONG: { |
| // res = op + 2 wide operands |
| uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); |
| uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]); |
| res = LookupValue(opcode, operand1, operand2, kNoValue); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::CMPG_FLOAT: |
| case Instruction::CMPL_FLOAT: |
| case Instruction::ADD_INT: |
| case Instruction::ADD_INT_2ADDR: |
| case Instruction::MUL_INT: |
| case Instruction::MUL_INT_2ADDR: |
| case Instruction::AND_INT: |
| case Instruction::AND_INT_2ADDR: |
| case Instruction::OR_INT: |
| case Instruction::OR_INT_2ADDR: |
| case Instruction::XOR_INT: |
| case Instruction::XOR_INT_2ADDR: |
| case Instruction::SUB_INT: |
| case Instruction::SUB_INT_2ADDR: |
| case Instruction::DIV_INT: |
| case Instruction::DIV_INT_2ADDR: |
| case Instruction::REM_INT: |
| case Instruction::REM_INT_2ADDR: |
| case Instruction::SHL_INT: |
| case Instruction::SHL_INT_2ADDR: |
| case Instruction::SHR_INT: |
| case Instruction::SHR_INT_2ADDR: |
| case Instruction::USHR_INT: |
| case Instruction::USHR_INT_2ADDR: { |
| // res = op + 2 operands |
| uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); |
| uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]); |
| res = LookupValue(opcode, operand1, operand2, kNoValue); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::ADD_LONG: |
| case Instruction::SUB_LONG: |
| case Instruction::MUL_LONG: |
| case Instruction::DIV_LONG: |
| case Instruction::REM_LONG: |
| case Instruction::AND_LONG: |
| case Instruction::OR_LONG: |
| case Instruction::XOR_LONG: |
| case Instruction::ADD_LONG_2ADDR: |
| case Instruction::SUB_LONG_2ADDR: |
| case Instruction::MUL_LONG_2ADDR: |
| case Instruction::DIV_LONG_2ADDR: |
| case Instruction::REM_LONG_2ADDR: |
| case Instruction::AND_LONG_2ADDR: |
| case Instruction::OR_LONG_2ADDR: |
| case Instruction::XOR_LONG_2ADDR: |
| case Instruction::ADD_DOUBLE: |
| case Instruction::SUB_DOUBLE: |
| case Instruction::MUL_DOUBLE: |
| case Instruction::DIV_DOUBLE: |
| case Instruction::REM_DOUBLE: |
| case Instruction::ADD_DOUBLE_2ADDR: |
| case Instruction::SUB_DOUBLE_2ADDR: |
| case Instruction::MUL_DOUBLE_2ADDR: |
| case Instruction::DIV_DOUBLE_2ADDR: |
| case Instruction::REM_DOUBLE_2ADDR: { |
| // wide res = op + 2 wide operands |
| uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); |
| uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]); |
| res = LookupValue(opcode, operand1, operand2, kNoValue); |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::SHL_LONG: |
| case Instruction::SHR_LONG: |
| case Instruction::USHR_LONG: |
| case Instruction::SHL_LONG_2ADDR: |
| case Instruction::SHR_LONG_2ADDR: |
| case Instruction::USHR_LONG_2ADDR: { |
| // wide res = op + 1 wide operand + 1 operand |
| uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); |
| uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[2]); |
| res = LookupValue(opcode, operand1, operand2, kNoValue); |
| SetOperandValueWide(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::ADD_FLOAT: |
| case Instruction::SUB_FLOAT: |
| case Instruction::MUL_FLOAT: |
| case Instruction::DIV_FLOAT: |
| case Instruction::REM_FLOAT: |
| case Instruction::ADD_FLOAT_2ADDR: |
| case Instruction::SUB_FLOAT_2ADDR: |
| case Instruction::MUL_FLOAT_2ADDR: |
| case Instruction::DIV_FLOAT_2ADDR: |
| case Instruction::REM_FLOAT_2ADDR: { |
| // res = op + 2 operands |
| uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); |
| uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]); |
| res = LookupValue(opcode, operand1, operand2, kNoValue); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::RSUB_INT: |
| case Instruction::ADD_INT_LIT16: |
| case Instruction::MUL_INT_LIT16: |
| case Instruction::DIV_INT_LIT16: |
| case Instruction::REM_INT_LIT16: |
| case Instruction::AND_INT_LIT16: |
| case Instruction::OR_INT_LIT16: |
| case Instruction::XOR_INT_LIT16: |
| case Instruction::ADD_INT_LIT8: |
| case Instruction::RSUB_INT_LIT8: |
| case Instruction::MUL_INT_LIT8: |
| case Instruction::DIV_INT_LIT8: |
| case Instruction::REM_INT_LIT8: |
| case Instruction::AND_INT_LIT8: |
| case Instruction::OR_INT_LIT8: |
| case Instruction::XOR_INT_LIT8: |
| case Instruction::SHL_INT_LIT8: |
| case Instruction::SHR_INT_LIT8: |
| case Instruction::USHR_INT_LIT8: { |
| // Same as res = op + 2 operands, except use vC as operand 2 |
| uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); |
| uint16_t operand2 = LookupValue(Instruction::CONST, mir->dalvikInsn.vC, 0, 0); |
| res = LookupValue(opcode, operand1, operand2, kNoValue); |
| SetOperandValue(mir->ssa_rep->defs[0], res); |
| } |
| break; |
| |
| case Instruction::AGET_OBJECT: |
| case Instruction::AGET: |
| case Instruction::AGET_WIDE: |
| case Instruction::AGET_BOOLEAN: |
| case Instruction::AGET_BYTE: |
| case Instruction::AGET_CHAR: |
| case Instruction::AGET_SHORT: |
| res = HandleAGet(mir, opcode); |
| break; |
| |
| case Instruction::APUT_OBJECT: |
| HandlePutObject(mir); |
| // Intentional fall-through. |
| case Instruction::APUT: |
| case Instruction::APUT_WIDE: |
| case Instruction::APUT_BYTE: |
| case Instruction::APUT_BOOLEAN: |
| case Instruction::APUT_SHORT: |
| case Instruction::APUT_CHAR: |
| HandleAPut(mir, opcode); |
| break; |
| |
| case Instruction::IGET_OBJECT: |
| case Instruction::IGET: |
| case Instruction::IGET_WIDE: |
| case Instruction::IGET_BOOLEAN: |
| case Instruction::IGET_BYTE: |
| case Instruction::IGET_CHAR: |
| case Instruction::IGET_SHORT: |
| res = HandleIGet(mir, opcode); |
| break; |
| |
| case Instruction::IPUT_OBJECT: |
| HandlePutObject(mir); |
| // Intentional fall-through. |
| case Instruction::IPUT: |
| case Instruction::IPUT_WIDE: |
| case Instruction::IPUT_BOOLEAN: |
| case Instruction::IPUT_BYTE: |
| case Instruction::IPUT_CHAR: |
| case Instruction::IPUT_SHORT: |
| HandleIPut(mir, opcode); |
| break; |
| |
| case Instruction::SGET_OBJECT: |
| case Instruction::SGET: |
| case Instruction::SGET_WIDE: |
| case Instruction::SGET_BOOLEAN: |
| case Instruction::SGET_BYTE: |
| case Instruction::SGET_CHAR: |
| case Instruction::SGET_SHORT: |
| res = HandleSGet(mir, opcode); |
| break; |
| |
| case Instruction::SPUT_OBJECT: |
| HandlePutObject(mir); |
| // Intentional fall-through. |
| case Instruction::SPUT: |
| case Instruction::SPUT_WIDE: |
| case Instruction::SPUT_BOOLEAN: |
| case Instruction::SPUT_BYTE: |
| case Instruction::SPUT_CHAR: |
| case Instruction::SPUT_SHORT: |
| HandleSPut(mir, opcode); |
| break; |
| } |
| return res; |
| } |
| |
| } // namespace art |