diff options
Diffstat (limited to 'compiler/utils')
22 files changed, 591 insertions, 1412 deletions
diff --git a/compiler/utils/arm/assembler_arm.h b/compiler/utils/arm/assembler_arm.h index 3084e6e2b6..ee5811c3c0 100644 --- a/compiler/utils/arm/assembler_arm.h +++ b/compiler/utils/arm/assembler_arm.h @@ -246,7 +246,7 @@ class Address : public ValueObject { NegPostIndex = (0|0|0) << 21 // negative post-indexed with writeback }; - Address(Register rn, int32_t offset = 0, Mode am = Offset) : rn_(rn), rm_(R0), + explicit Address(Register rn, int32_t offset = 0, Mode am = Offset) : rn_(rn), rm_(R0), offset_(offset), am_(am), is_immed_offset_(true), shift_(LSL) { } @@ -763,6 +763,9 @@ class ArmAssembler : public Assembler { virtual void PushList(RegList regs, Condition cond = AL) = 0; virtual void PopList(RegList regs, Condition cond = AL) = 0; + virtual void StoreList(RegList regs, size_t stack_offset) = 0; + virtual void LoadList(RegList regs, size_t stack_offset) = 0; + virtual void Mov(Register rd, Register rm, Condition cond = AL) = 0; // Convenience shift instructions. Use mov instruction with shifter operand diff --git a/compiler/utils/arm/assembler_thumb2.cc b/compiler/utils/arm/assembler_thumb2.cc index ebdfc98554..2269ba2d20 100644 --- a/compiler/utils/arm/assembler_thumb2.cc +++ b/compiler/utils/arm/assembler_thumb2.cc @@ -2018,6 +2018,45 @@ inline size_t Thumb2Assembler::Fixup::IncreaseSize(Size new_size) { return adjustment; } +bool Thumb2Assembler::Fixup::IsCandidateForEmitEarly() const { + DCHECK(size_ == original_size_); + if (target_ == kUnresolved) { + return false; + } + // GetOffset() does not depend on current_code_size for branches, only for literals. + constexpr uint32_t current_code_size = 0u; + switch (GetSize()) { + case kBranch16Bit: + return IsInt(cond_ != AL ? 9 : 12, GetOffset(current_code_size)); + case kBranch32Bit: + // We don't support conditional branches beyond +-1MiB + // or unconditional branches beyond +-16MiB. + return true; + + case kCbxz16Bit: + return IsUint<7>(GetOffset(current_code_size)); + case kCbxz32Bit: + return IsInt<9>(GetOffset(current_code_size)); + case kCbxz48Bit: + // We don't support conditional branches beyond +-1MiB. + return true; + + case kLiteral1KiB: + case kLiteral4KiB: + case kLiteral64KiB: + case kLiteral1MiB: + case kLiteralFar: + case kLiteralAddr1KiB: + case kLiteralAddr4KiB: + case kLiteralAddr64KiB: + case kLiteralAddrFar: + case kLongOrFPLiteral1KiB: + case kLongOrFPLiteral64KiB: + case kLongOrFPLiteralFar: + return false; + } +} + uint32_t Thumb2Assembler::Fixup::AdjustSizeIfNeeded(uint32_t current_code_size) { uint32_t old_code_size = current_code_size; switch (GetSize()) { @@ -3333,6 +3372,30 @@ void Thumb2Assembler::PopList(RegList regs, Condition cond) { ldm(IA_W, SP, regs, cond); } +void Thumb2Assembler::StoreList(RegList regs, size_t stack_offset) { + DCHECK_NE(regs, 0u); + DCHECK_EQ(regs & (1u << IP), 0u); + if (IsPowerOfTwo(regs)) { + Register reg = static_cast<Register>(CTZ(static_cast<uint32_t>(regs))); + str(reg, Address(SP, stack_offset)); + } else { + add(IP, SP, ShifterOperand(stack_offset)); + stm(IA, IP, regs); + } +} + +void Thumb2Assembler::LoadList(RegList regs, size_t stack_offset) { + DCHECK_NE(regs, 0u); + DCHECK_EQ(regs & (1u << IP), 0u); + if (IsPowerOfTwo(regs)) { + Register reg = static_cast<Register>(CTZ(static_cast<uint32_t>(regs))); + ldr(reg, Address(SP, stack_offset)); + } else { + Register lowest_reg = static_cast<Register>(CTZ(static_cast<uint32_t>(regs))); + add(lowest_reg, SP, ShifterOperand(stack_offset)); + ldm(IA, lowest_reg, regs); + } +} void Thumb2Assembler::Mov(Register rd, Register rm, Condition cond) { if (cond != AL || rd != rm) { @@ -3343,6 +3406,30 @@ void Thumb2Assembler::Mov(Register rd, Register rm, Condition cond) { void Thumb2Assembler::Bind(Label* label) { BindLabel(label, buffer_.Size()); + + // Try to emit some Fixups now to reduce the memory needed during the branch fixup later. + while (!fixups_.empty() && fixups_.back().IsCandidateForEmitEarly()) { + const Fixup& last_fixup = fixups_.back(); + // Fixups are ordered by location, so the candidate can surely be emitted if it is + // a forward branch. If it's a backward branch, it may go over any number of other + // fixups. We could check for any number of emit early candidates but we want this + // heuristics to be quick, so check just one. + uint32_t target = last_fixup.GetTarget(); + if (target < last_fixup.GetLocation() && + fixups_.size() >= 2u && + fixups_[fixups_.size() - 2u].GetLocation() >= target) { + const Fixup& prev_fixup = fixups_[fixups_.size() - 2u]; + if (!prev_fixup.IsCandidateForEmitEarly()) { + break; + } + uint32_t min_target = std::min(target, prev_fixup.GetTarget()); + if (fixups_.size() >= 3u && fixups_[fixups_.size() - 3u].GetLocation() >= min_target) { + break; + } + } + last_fixup.Emit(&buffer_, buffer_.Size()); + fixups_.pop_back(); + } } diff --git a/compiler/utils/arm/assembler_thumb2.h b/compiler/utils/arm/assembler_thumb2.h index 13f3becb6d..1c495aa7a7 100644 --- a/compiler/utils/arm/assembler_thumb2.h +++ b/compiler/utils/arm/assembler_thumb2.h @@ -22,11 +22,11 @@ #include <vector> #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/logging.h" #include "constants_arm.h" #include "utils/arm/managed_register_arm.h" #include "utils/arm/assembler_arm.h" -#include "utils/array_ref.h" #include "offsets.h" namespace art { @@ -293,6 +293,8 @@ class Thumb2Assembler FINAL : public ArmAssembler { void PushList(RegList regs, Condition cond = AL) OVERRIDE; void PopList(RegList regs, Condition cond = AL) OVERRIDE; + void StoreList(RegList regs, size_t stack_offset) OVERRIDE; + void LoadList(RegList regs, size_t stack_offset) OVERRIDE; void Mov(Register rd, Register rm, Condition cond = AL) OVERRIDE; @@ -573,6 +575,10 @@ class Thumb2Assembler FINAL : public ArmAssembler { return location_; } + uint32_t GetTarget() const { + return target_; + } + uint32_t GetAdjustment() const { return adjustment_; } @@ -592,6 +598,11 @@ class Thumb2Assembler FINAL : public ArmAssembler { target_ = target; } + // Branches with bound targets that are in range can be emitted early. + // However, the caller still needs to check if the branch doesn't go over + // another Fixup that's not ready to be emitted. + bool IsCandidateForEmitEarly() const; + // Check if the current size is OK for current location_, target_ and adjustment_. // If not, increase the size. Return the size increase, 0 if unchanged. // If the target if after this Fixup, also add the difference to adjustment_, diff --git a/compiler/utils/arm/jni_macro_assembler_arm_vixl.cc b/compiler/utils/arm/jni_macro_assembler_arm_vixl.cc index a03dd74657..14d29c4f1a 100644 --- a/compiler/utils/arm/jni_macro_assembler_arm_vixl.cc +++ b/compiler/utils/arm/jni_macro_assembler_arm_vixl.cc @@ -314,11 +314,21 @@ void ArmVIXLJNIMacroAssembler::Move(ManagedRegister m_dst, CHECK(src.IsCoreRegister()) << src; ___ Mov(dst.AsVIXLRegister(), src.AsVIXLRegister()); } else if (dst.IsDRegister()) { - CHECK(src.IsDRegister()) << src; - ___ Vmov(F64, dst.AsVIXLDRegister(), src.AsVIXLDRegister()); + if (src.IsDRegister()) { + ___ Vmov(F64, dst.AsVIXLDRegister(), src.AsVIXLDRegister()); + } else { + // VMOV Dn, Rlo, Rhi (Dn = {Rlo, Rhi}) + CHECK(src.IsRegisterPair()) << src; + ___ Vmov(dst.AsVIXLDRegister(), src.AsVIXLRegisterPairLow(), src.AsVIXLRegisterPairHigh()); + } } else if (dst.IsSRegister()) { - CHECK(src.IsSRegister()) << src; - ___ Vmov(F32, dst.AsVIXLSRegister(), src.AsVIXLSRegister()); + if (src.IsSRegister()) { + ___ Vmov(F32, dst.AsVIXLSRegister(), src.AsVIXLSRegister()); + } else { + // VMOV Sn, Rn (Sn = Rn) + CHECK(src.IsCoreRegister()) << src; + ___ Vmov(dst.AsVIXLSRegister(), src.AsVIXLRegister()); + } } else { CHECK(dst.IsRegisterPair()) << dst; CHECK(src.IsRegisterPair()) << src; diff --git a/compiler/utils/array_ref.h b/compiler/utils/array_ref.h deleted file mode 100644 index 8dc9ab4a5e..0000000000 --- a/compiler/utils/array_ref.h +++ /dev/null @@ -1,200 +0,0 @@ -/* - * Copyright (C) 2014 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. - */ - -#ifndef ART_COMPILER_UTILS_ARRAY_REF_H_ -#define ART_COMPILER_UTILS_ARRAY_REF_H_ - -#include <type_traits> -#include <vector> - -#include "base/logging.h" - -namespace art { - -/** - * @brief A container that references an array. - * - * @details The template class ArrayRef provides a container that references - * an external array. This external array must remain alive while the ArrayRef - * object is in use. The external array may be a std::vector<>-backed storage - * or any other contiguous chunk of memory but that memory must remain valid, - * i.e. the std::vector<> must not be resized for example. - * - * Except for copy/assign and insert/erase/capacity functions, the interface - * is essentially the same as std::vector<>. Since we don't want to throw - * exceptions, at() is also excluded. - */ -template <typename T> -class ArrayRef { - public: - typedef T value_type; - typedef T& reference; - typedef const T& const_reference; - typedef T* pointer; - typedef const T* const_pointer; - typedef T* iterator; - typedef const T* const_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - typedef ptrdiff_t difference_type; - typedef size_t size_type; - - // Constructors. - - constexpr ArrayRef() - : array_(nullptr), size_(0u) { - } - - template <size_t size> - explicit constexpr ArrayRef(T (&array)[size]) - : array_(array), size_(size) { - } - - template <typename U, - size_t size, - typename = typename std::enable_if<std::is_same<T, const U>::value>::type> - explicit constexpr ArrayRef(U (&array)[size]) - : array_(array), size_(size) { - } - - constexpr ArrayRef(T* array_in, size_t size_in) - : array_(array_in), size_(size_in) { - } - - template <typename Vector, - typename = typename std::enable_if< - std::is_same<typename Vector::value_type, value_type>::value>::type> - explicit ArrayRef(Vector& v) - : array_(v.data()), size_(v.size()) { - } - - template <typename Vector, - typename = typename std::enable_if< - std::is_same< - typename std::add_const<typename Vector::value_type>::type, - value_type>::value>::type> - explicit ArrayRef(const Vector& v) - : array_(v.data()), size_(v.size()) { - } - - ArrayRef(const ArrayRef&) = default; - - // Assignment operators. - - ArrayRef& operator=(const ArrayRef& other) { - array_ = other.array_; - size_ = other.size_; - return *this; - } - - template <typename U> - typename std::enable_if<std::is_same<T, const U>::value, ArrayRef>::type& - operator=(const ArrayRef<U>& other) { - return *this = ArrayRef(other); - } - - // Destructor. - ~ArrayRef() = default; - - // Iterators. - iterator begin() { return array_; } - const_iterator begin() const { return array_; } - const_iterator cbegin() const { return array_; } - iterator end() { return array_ + size_; } - const_iterator end() const { return array_ + size_; } - const_iterator cend() const { return array_ + size_; } - reverse_iterator rbegin() { return reverse_iterator(end()); } - const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } - const_reverse_iterator crbegin() const { return const_reverse_iterator(cend()); } - reverse_iterator rend() { return reverse_iterator(begin()); } - const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } - const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); } - - // Size. - size_type size() const { return size_; } - bool empty() const { return size() == 0u; } - - // Element access. NOTE: Not providing at(). - - reference operator[](size_type n) { - DCHECK_LT(n, size_); - return array_[n]; - } - - const_reference operator[](size_type n) const { - DCHECK_LT(n, size_); - return array_[n]; - } - - reference front() { - DCHECK_NE(size_, 0u); - return array_[0]; - } - - const_reference front() const { - DCHECK_NE(size_, 0u); - return array_[0]; - } - - reference back() { - DCHECK_NE(size_, 0u); - return array_[size_ - 1u]; - } - - const_reference back() const { - DCHECK_NE(size_, 0u); - return array_[size_ - 1u]; - } - - value_type* data() { return array_; } - const value_type* data() const { return array_; } - - ArrayRef SubArray(size_type pos) { - return SubArray(pos, size() - pos); - } - ArrayRef<const T> SubArray(size_type pos) const { - return SubArray(pos, size() - pos); - } - ArrayRef SubArray(size_type pos, size_type length) { - DCHECK_LE(pos, size()); - DCHECK_LE(length, size() - pos); - return ArrayRef(data() + pos, length); - } - ArrayRef<const T> SubArray(size_type pos, size_type length) const { - DCHECK_LE(pos, size()); - DCHECK_LE(length, size() - pos); - return ArrayRef<const T>(data() + pos, length); - } - - private: - T* array_; - size_t size_; -}; - -template <typename T> -bool operator==(const ArrayRef<T>& lhs, const ArrayRef<T>& rhs) { - return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin()); -} - -template <typename T> -bool operator!=(const ArrayRef<T>& lhs, const ArrayRef<T>& rhs) { - return !(lhs == rhs); -} - -} // namespace art - - -#endif // ART_COMPILER_UTILS_ARRAY_REF_H_ diff --git a/compiler/utils/assembler.h b/compiler/utils/assembler.h index b616057e79..314ff8cf7a 100644 --- a/compiler/utils/assembler.h +++ b/compiler/utils/assembler.h @@ -24,6 +24,7 @@ #include "arm/constants_arm.h" #include "base/arena_allocator.h" #include "base/arena_object.h" +#include "base/array_ref.h" #include "base/enums.h" #include "base/logging.h" #include "base/macros.h" @@ -33,7 +34,6 @@ #include "memory_region.h" #include "mips/constants_mips.h" #include "offsets.h" -#include "utils/array_ref.h" #include "x86/constants_x86.h" #include "x86_64/constants_x86_64.h" diff --git a/compiler/utils/dedupe_set_test.cc b/compiler/utils/dedupe_set_test.cc index 60a891d6a2..4c0979e0b7 100644 --- a/compiler/utils/dedupe_set_test.cc +++ b/compiler/utils/dedupe_set_test.cc @@ -20,10 +20,10 @@ #include <cstdio> #include <vector> +#include "base/array_ref.h" #include "dedupe_set-inl.h" #include "gtest/gtest.h" #include "thread-inl.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/utils/intrusive_forward_list.h b/compiler/utils/intrusive_forward_list.h index ec2c08722c..b5fc2f2456 100644 --- a/compiler/utils/intrusive_forward_list.h +++ b/compiler/utils/intrusive_forward_list.h @@ -59,7 +59,7 @@ class IntrusiveForwardListIterator : public std::iterator<std::forward_iterator_ // Conversion from iterator to const_iterator. template <typename OtherT, typename = typename std::enable_if<std::is_same<T, const OtherT>::value>::type> - IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT, HookTraits>& src) + IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT, HookTraits>& src) // NOLINT, implicit : hook_(src.hook_) { } // Iteration. diff --git a/compiler/utils/jni_macro_assembler.h b/compiler/utils/jni_macro_assembler.h index 6f45bd62db..0119ae9bfb 100644 --- a/compiler/utils/jni_macro_assembler.h +++ b/compiler/utils/jni_macro_assembler.h @@ -22,12 +22,12 @@ #include "arch/instruction_set.h" #include "base/arena_allocator.h" #include "base/arena_object.h" +#include "base/array_ref.h" #include "base/enums.h" #include "base/logging.h" #include "base/macros.h" #include "managed_register.h" #include "offsets.h" -#include "utils/array_ref.h" namespace art { diff --git a/compiler/utils/mips/assembler_mips.cc b/compiler/utils/mips/assembler_mips.cc index 4b580b620f..b972c70eb9 100644 --- a/compiler/utils/mips/assembler_mips.cc +++ b/compiler/utils/mips/assembler_mips.cc @@ -230,12 +230,14 @@ void MipsAssembler::FinalizeCode() { DsFsmCommitLabel(); SetReorder(false); EmitLiterals(); + ReserveJumpTableSpace(); PromoteBranches(); } void MipsAssembler::FinalizeInstructions(const MemoryRegion& region) { size_t number_of_delayed_adjust_pcs = cfi().NumberOfDelayedAdvancePCs(); EmitBranches(); + EmitJumpTables(); Assembler::FinalizeInstructions(region); PatchCFI(number_of_delayed_adjust_pcs); } @@ -1724,47 +1726,68 @@ void MipsAssembler::Branch::InitShortOrLong(MipsAssembler::Branch::OffsetBits of type_ = (offset_size <= branch_info_[short_type].offset_size) ? short_type : long_type; } -void MipsAssembler::Branch::InitializeType(bool is_call, bool is_literal, bool is_r6) { - CHECK_EQ(is_call && is_literal, false); +void MipsAssembler::Branch::InitializeType(Type initial_type, bool is_r6) { OffsetBits offset_size = GetOffsetSizeNeeded(location_, target_); if (is_r6) { // R6 - if (is_literal) { - CHECK(!IsResolved()); - type_ = kR6Literal; - } else if (is_call) { - InitShortOrLong(offset_size, kR6Call, kR6LongCall); - } else { - switch (condition_) { - case kUncond: - InitShortOrLong(offset_size, kR6UncondBranch, kR6LongUncondBranch); - break; - case kCondEQZ: - case kCondNEZ: - // Special case for beqzc/bnezc with longer offset than in other b<cond>c instructions. - type_ = (offset_size <= kOffset23) ? kR6CondBranch : kR6LongCondBranch; - break; - default: - InitShortOrLong(offset_size, kR6CondBranch, kR6LongCondBranch); - break; - } + switch (initial_type) { + case kLabel: + CHECK(!IsResolved()); + type_ = kR6Label; + break; + case kLiteral: + CHECK(!IsResolved()); + type_ = kR6Literal; + break; + case kCall: + InitShortOrLong(offset_size, kR6Call, kR6LongCall); + break; + case kCondBranch: + switch (condition_) { + case kUncond: + InitShortOrLong(offset_size, kR6UncondBranch, kR6LongUncondBranch); + break; + case kCondEQZ: + case kCondNEZ: + // Special case for beqzc/bnezc with longer offset than in other b<cond>c instructions. + type_ = (offset_size <= kOffset23) ? kR6CondBranch : kR6LongCondBranch; + break; + default: + InitShortOrLong(offset_size, kR6CondBranch, kR6LongCondBranch); + break; + } + break; + default: + LOG(FATAL) << "Unexpected branch type " << initial_type; + UNREACHABLE(); } } else { // R2 - if (is_literal) { - CHECK(!IsResolved()); - type_ = kLiteral; - } else if (is_call) { - InitShortOrLong(offset_size, kCall, kLongCall); - } else { - switch (condition_) { - case kUncond: - InitShortOrLong(offset_size, kUncondBranch, kLongUncondBranch); - break; - default: - InitShortOrLong(offset_size, kCondBranch, kLongCondBranch); - break; - } + switch (initial_type) { + case kLabel: + CHECK(!IsResolved()); + type_ = kLabel; + break; + case kLiteral: + CHECK(!IsResolved()); + type_ = kLiteral; + break; + case kCall: + InitShortOrLong(offset_size, kCall, kLongCall); + break; + case kCondBranch: + switch (condition_) { + case kUncond: + InitShortOrLong(offset_size, kUncondBranch, kLongUncondBranch); + break; + default: + InitShortOrLong(offset_size, kCondBranch, kLongCondBranch); + break; + } + break; + default: + LOG(FATAL) << "Unexpected branch type " << initial_type; + UNREACHABLE(); } } old_type_ = type_; @@ -1804,7 +1827,7 @@ MipsAssembler::Branch::Branch(bool is_r6, uint32_t location, uint32_t target, bo rhs_reg_(0), condition_(kUncond), delayed_instruction_(kUnfilledDelaySlot) { - InitializeType(is_call, /* is_literal */ false, is_r6); + InitializeType((is_call ? kCall : kCondBranch), is_r6); } MipsAssembler::Branch::Branch(bool is_r6, @@ -1862,10 +1885,14 @@ MipsAssembler::Branch::Branch(bool is_r6, // Branch condition is always true, make the branch unconditional. condition_ = kUncond; } - InitializeType(/* is_call */ false, /* is_literal */ false, is_r6); + InitializeType(kCondBranch, is_r6); } -MipsAssembler::Branch::Branch(bool is_r6, uint32_t location, Register dest_reg, Register base_reg) +MipsAssembler::Branch::Branch(bool is_r6, + uint32_t location, + Register dest_reg, + Register base_reg, + Type label_or_literal_type) : old_location_(location), location_(location), target_(kUnresolved), @@ -1879,7 +1906,7 @@ MipsAssembler::Branch::Branch(bool is_r6, uint32_t location, Register dest_reg, } else { CHECK_NE(base_reg, ZERO); } - InitializeType(/* is_call */ false, /* is_literal */ true, is_r6); + InitializeType(label_or_literal_type, is_r6); } MipsAssembler::BranchCondition MipsAssembler::Branch::OppositeCondition( @@ -2007,12 +2034,16 @@ bool MipsAssembler::Branch::IsLong() const { case kUncondBranch: case kCondBranch: case kCall: + // R2 near label. + case kLabel: // R2 near literal. case kLiteral: // R6 short branches. case kR6UncondBranch: case kR6CondBranch: case kR6Call: + // R6 near label. + case kR6Label: // R6 near literal. case kR6Literal: return false; @@ -2020,12 +2051,16 @@ bool MipsAssembler::Branch::IsLong() const { case kLongUncondBranch: case kLongCondBranch: case kLongCall: + // R2 far label. + case kFarLabel: // R2 far literal. case kFarLiteral: // R6 long branches. case kR6LongUncondBranch: case kR6LongCondBranch: case kR6LongCall: + // R6 far label. + case kR6FarLabel: // R6 far literal. case kR6FarLiteral: return true; @@ -2096,6 +2131,10 @@ void MipsAssembler::Branch::PromoteToLong() { case kCall: type_ = kLongCall; break; + // R2 near label. + case kLabel: + type_ = kFarLabel; + break; // R2 near literal. case kLiteral: type_ = kFarLiteral; @@ -2110,6 +2149,10 @@ void MipsAssembler::Branch::PromoteToLong() { case kR6Call: type_ = kR6LongCall; break; + // R6 near label. + case kR6Label: + type_ = kR6FarLabel; + break; // R6 near literal. case kR6Literal: type_ = kR6FarLiteral; @@ -2123,6 +2166,8 @@ void MipsAssembler::Branch::PromoteToLong() { uint32_t MipsAssembler::GetBranchLocationOrPcRelBase(const MipsAssembler::Branch* branch) const { switch (branch->GetType()) { + case Branch::kLabel: + case Branch::kFarLabel: case Branch::kLiteral: case Branch::kFarLiteral: return GetLabelLocation(&pc_rel_base_label_); @@ -2132,7 +2177,7 @@ uint32_t MipsAssembler::GetBranchLocationOrPcRelBase(const MipsAssembler::Branch } uint32_t MipsAssembler::Branch::PromoteIfNeeded(uint32_t location, uint32_t max_short_distance) { - // `location` is either `GetLabelLocation(&pc_rel_base_label_)` for R2 literals or + // `location` is either `GetLabelLocation(&pc_rel_base_label_)` for R2 labels/literals or // `this->GetLocation()` for everything else. // If the branch is still unresolved or already long, nothing to do. if (IsLong() || !IsResolved()) { @@ -2170,6 +2215,8 @@ uint32_t MipsAssembler::Branch::GetOffsetLocation() const { uint32_t MipsAssembler::GetBranchOrPcRelBaseForEncoding(const MipsAssembler::Branch* branch) const { switch (branch->GetType()) { + case Branch::kLabel: + case Branch::kFarLabel: case Branch::kLiteral: case Branch::kFarLiteral: return GetLabelLocation(&pc_rel_base_label_); @@ -2180,7 +2227,7 @@ uint32_t MipsAssembler::GetBranchOrPcRelBaseForEncoding(const MipsAssembler::Bra } uint32_t MipsAssembler::Branch::GetOffset(uint32_t location) const { - // `location` is either `GetLabelLocation(&pc_rel_base_label_)` for R2 literals or + // `location` is either `GetLabelLocation(&pc_rel_base_label_)` for R2 labels/literals or // `this->GetOffsetLocation() + branch_info_[this->GetType()].pc_org * sizeof(uint32_t)` // for everything else. CHECK(IsResolved()); @@ -2457,6 +2504,13 @@ void MipsAssembler::Call(MipsLabel* label) { FinalizeLabeledBranch(label); } +void MipsAssembler::LoadLabelAddress(Register dest_reg, Register base_reg, MipsLabel* label) { + // Label address loads are treated as pseudo branches since they require very similar handling. + DCHECK(!label->IsBound()); + branches_.emplace_back(IsR6(), buffer_.Size(), dest_reg, base_reg, Branch::kLabel); + FinalizeLabeledBranch(label); +} + Literal* MipsAssembler::NewLiteral(size_t size, const uint8_t* data) { DCHECK(size == 4u || size == 8u) << size; literals_.emplace_back(size, data); @@ -2468,13 +2522,17 @@ void MipsAssembler::LoadLiteral(Register dest_reg, Register base_reg, Literal* l DCHECK_EQ(literal->GetSize(), 4u); MipsLabel* label = literal->GetLabel(); DCHECK(!label->IsBound()); - branches_.emplace_back(IsR6(), - buffer_.Size(), - dest_reg, - base_reg); + branches_.emplace_back(IsR6(), buffer_.Size(), dest_reg, base_reg, Branch::kLiteral); FinalizeLabeledBranch(label); } +JumpTable* MipsAssembler::CreateJumpTable(std::vector<MipsLabel*>&& labels) { + jump_tables_.emplace_back(std::move(labels)); + JumpTable* table = &jump_tables_.back(); + DCHECK(!table->GetLabel()->IsBound()); + return table; +} + void MipsAssembler::EmitLiterals() { if (!literals_.empty()) { // We don't support byte and half-word literals. @@ -2491,6 +2549,60 @@ void MipsAssembler::EmitLiterals() { } } +void MipsAssembler::ReserveJumpTableSpace() { + if (!jump_tables_.empty()) { + for (JumpTable& table : jump_tables_) { + MipsLabel* label = table.GetLabel(); + Bind(label); + + // Bulk ensure capacity, as this may be large. + size_t orig_size = buffer_.Size(); + size_t required_capacity = orig_size + table.GetSize(); + if (required_capacity > buffer_.Capacity()) { + buffer_.ExtendCapacity(required_capacity); + } +#ifndef NDEBUG + buffer_.has_ensured_capacity_ = true; +#endif + + // Fill the space with dummy data as the data is not final + // until the branches have been promoted. And we shouldn't + // be moving uninitialized data during branch promotion. + for (size_t cnt = table.GetData().size(), i = 0; i < cnt; i++) { + buffer_.Emit<uint32_t>(0x1abe1234u); + } + +#ifndef NDEBUG + buffer_.has_ensured_capacity_ = false; +#endif + } + } +} + +void MipsAssembler::EmitJumpTables() { + if (!jump_tables_.empty()) { + CHECK(!overwriting_); + // Switch from appending instructions at the end of the buffer to overwriting + // existing instructions (here, jump tables) in the buffer. + overwriting_ = true; + + for (JumpTable& table : jump_tables_) { + MipsLabel* table_label = table.GetLabel(); + uint32_t start = GetLabelLocation(table_label); + overwrite_location_ = start; + + for (MipsLabel* target : table.GetData()) { + CHECK_EQ(buffer_.Load<uint32_t>(overwrite_location_), 0x1abe1234u); + // The table will contain target addresses relative to the table start. + uint32_t offset = GetLabelLocation(target) - start; + Emit(offset); + } + } + + overwriting_ = false; + } +} + void MipsAssembler::PromoteBranches() { // Promote short branches to long as necessary. bool changed; @@ -2539,12 +2651,16 @@ const MipsAssembler::Branch::BranchInfo MipsAssembler::Branch::branch_info_[] = { 2, 0, 1, MipsAssembler::Branch::kOffset18, 2 }, // kUncondBranch { 2, 0, 1, MipsAssembler::Branch::kOffset18, 2 }, // kCondBranch { 2, 0, 1, MipsAssembler::Branch::kOffset18, 2 }, // kCall + // R2 near label. + { 1, 0, 0, MipsAssembler::Branch::kOffset16, 0 }, // kLabel // R2 near literal. { 1, 0, 0, MipsAssembler::Branch::kOffset16, 0 }, // kLiteral // R2 long branches. { 9, 3, 1, MipsAssembler::Branch::kOffset32, 0 }, // kLongUncondBranch { 10, 4, 1, MipsAssembler::Branch::kOffset32, 0 }, // kLongCondBranch { 6, 1, 1, MipsAssembler::Branch::kOffset32, 0 }, // kLongCall + // R2 far label. + { 3, 0, 0, MipsAssembler::Branch::kOffset32, 0 }, // kFarLabel // R2 far literal. { 3, 0, 0, MipsAssembler::Branch::kOffset32, 0 }, // kFarLiteral // R6 short branches. @@ -2552,12 +2668,16 @@ const MipsAssembler::Branch::BranchInfo MipsAssembler::Branch::branch_info_[] = { 2, 0, 1, MipsAssembler::Branch::kOffset18, 2 }, // kR6CondBranch // Exception: kOffset23 for beqzc/bnezc. { 1, 0, 1, MipsAssembler::Branch::kOffset28, 2 }, // kR6Call + // R6 near label. + { 1, 0, 0, MipsAssembler::Branch::kOffset21, 2 }, // kR6Label // R6 near literal. { 1, 0, 0, MipsAssembler::Branch::kOffset21, 2 }, // kR6Literal // R6 long branches. { 2, 0, 0, MipsAssembler::Branch::kOffset32, 0 }, // kR6LongUncondBranch { 3, 1, 0, MipsAssembler::Branch::kOffset32, 0 }, // kR6LongCondBranch { 2, 0, 0, MipsAssembler::Branch::kOffset32, 0 }, // kR6LongCall + // R6 far label. + { 2, 0, 0, MipsAssembler::Branch::kOffset32, 0 }, // kR6FarLabel // R6 far literal. { 2, 0, 0, MipsAssembler::Branch::kOffset32, 0 }, // kR6FarLiteral }; @@ -2614,6 +2734,12 @@ void MipsAssembler::EmitBranch(MipsAssembler::Branch* branch) { Emit(delayed_instruction); break; + // R2 near label. + case Branch::kLabel: + DCHECK_EQ(delayed_instruction, Branch::kUnfilledDelaySlot); + CHECK_EQ(overwrite_location_, branch->GetOffsetLocation()); + Addiu(lhs, rhs, offset); + break; // R2 near literal. case Branch::kLiteral: DCHECK_EQ(delayed_instruction, Branch::kUnfilledDelaySlot); @@ -2691,6 +2817,14 @@ void MipsAssembler::EmitBranch(MipsAssembler::Branch* branch) { Nop(); break; + // R2 far label. + case Branch::kFarLabel: + DCHECK_EQ(delayed_instruction, Branch::kUnfilledDelaySlot); + CHECK_EQ(overwrite_location_, branch->GetOffsetLocation()); + Lui(AT, High16Bits(offset)); + Ori(AT, AT, Low16Bits(offset)); + Addu(lhs, AT, rhs); + break; // R2 far literal. case Branch::kFarLiteral: DCHECK_EQ(delayed_instruction, Branch::kUnfilledDelaySlot); @@ -2725,6 +2859,12 @@ void MipsAssembler::EmitBranch(MipsAssembler::Branch* branch) { Balc(offset); break; + // R6 near label. + case Branch::kR6Label: + DCHECK_EQ(delayed_instruction, Branch::kUnfilledDelaySlot); + CHECK_EQ(overwrite_location_, branch->GetOffsetLocation()); + Addiupc(lhs, offset); + break; // R6 near literal. case Branch::kR6Literal: DCHECK_EQ(delayed_instruction, Branch::kUnfilledDelaySlot); @@ -2759,6 +2899,14 @@ void MipsAssembler::EmitBranch(MipsAssembler::Branch* branch) { Jialc(AT, Low16Bits(offset)); break; + // R6 far label. + case Branch::kR6FarLabel: + DCHECK_EQ(delayed_instruction, Branch::kUnfilledDelaySlot); + offset += (offset & 0x8000) << 1; // Account for sign extension in addiu. + CHECK_EQ(overwrite_location_, branch->GetOffsetLocation()); + Auipc(AT, High16Bits(offset)); + Addiu(lhs, AT, Low16Bits(offset)); + break; // R6 far literal. case Branch::kR6FarLiteral: DCHECK_EQ(delayed_instruction, Branch::kUnfilledDelaySlot); diff --git a/compiler/utils/mips/assembler_mips.h b/compiler/utils/mips/assembler_mips.h index d50c439418..e1255f7f23 100644 --- a/compiler/utils/mips/assembler_mips.h +++ b/compiler/utils/mips/assembler_mips.h @@ -126,6 +126,36 @@ class Literal { DISALLOW_COPY_AND_ASSIGN(Literal); }; +// Jump table: table of labels emitted after the literals. Similar to literals. +class JumpTable { + public: + explicit JumpTable(std::vector<MipsLabel*>&& labels) + : label_(), labels_(std::move(labels)) { + } + + uint32_t GetSize() const { + return static_cast<uint32_t>(labels_.size()) * sizeof(uint32_t); + } + + const std::vector<MipsLabel*>& GetData() const { + return labels_; + } + + MipsLabel* GetLabel() { + return &label_; + } + + const MipsLabel* GetLabel() const { + return &label_; + } + + private: + MipsLabel label_; + std::vector<MipsLabel*> labels_; + + DISALLOW_COPY_AND_ASSIGN(JumpTable); +}; + // Slowpath entered when Thread::Current()->_exception is non-null. class MipsExceptionSlowPath { public: @@ -158,6 +188,7 @@ class MipsAssembler FINAL : public Assembler, public JNIMacroAssembler<PointerSi ds_fsm_state_(kExpectingLabel), ds_fsm_target_pc_(0), literals_(arena->Adapter(kArenaAllocAssembler)), + jump_tables_(arena->Adapter(kArenaAllocAssembler)), last_position_adjustment_(0), last_old_position_(0), last_branch_id_(0), @@ -465,46 +496,61 @@ class MipsAssembler FINAL : public Assembler, public JNIMacroAssembler<PointerSi public: template <typename ImplicitNullChecker = NoImplicitNullChecker> - void StoreConst32ToOffset(int32_t value, - Register base, - int32_t offset, - Register temp, - ImplicitNullChecker null_checker = NoImplicitNullChecker()) { + void StoreConstToOffset(StoreOperandType type, + int64_t value, + Register base, + int32_t offset, + Register temp, + ImplicitNullChecker null_checker = NoImplicitNullChecker()) { + // We permit `base` and `temp` to coincide (however, we check that neither is AT), + // in which case the `base` register may be overwritten in the process. CHECK_NE(temp, AT); // Must not use AT as temp, so as not to overwrite the adjusted base. - AdjustBaseAndOffset(base, offset, /* is_doubleword */ false); - if (value == 0) { - temp = ZERO; - } else { - LoadConst32(temp, value); - } - Sw(temp, base, offset); - null_checker(); - } - - template <typename ImplicitNullChecker = NoImplicitNullChecker> - void StoreConst64ToOffset(int64_t value, - Register base, - int32_t offset, - Register temp, - ImplicitNullChecker null_checker = NoImplicitNullChecker()) { - CHECK_NE(temp, AT); // Must not use AT as temp, so as not to overwrite the adjusted base. - AdjustBaseAndOffset(base, offset, /* is_doubleword */ true); + AdjustBaseAndOffset(base, offset, /* is_doubleword */ (type == kStoreDoubleword)); uint32_t low = Low32Bits(value); uint32_t high = High32Bits(value); + Register reg; + // If the adjustment left `base` unchanged and equal to `temp`, we can't use `temp` + // to load and hold the value but we can use AT instead as AT hasn't been used yet. + // Otherwise, `temp` can be used for the value. And if `temp` is the same as the + // original `base` (that is, `base` prior to the adjustment), the original `base` + // register will be overwritten. + if (base == temp) { + temp = AT; + } if (low == 0) { - Sw(ZERO, base, offset); + reg = ZERO; } else { - LoadConst32(temp, low); - Sw(temp, base, offset); + reg = temp; + LoadConst32(reg, low); } - null_checker(); - if (high == 0) { - Sw(ZERO, base, offset + kMipsWordSize); - } else { - if (high != low) { - LoadConst32(temp, high); - } - Sw(temp, base, offset + kMipsWordSize); + switch (type) { + case kStoreByte: + Sb(reg, base, offset); + break; + case kStoreHalfword: + Sh(reg, base, offset); + break; + case kStoreWord: + Sw(reg, base, offset); + break; + case kStoreDoubleword: + Sw(reg, base, offset); + null_checker(); + if (high == 0) { + reg = ZERO; + } else { + reg = temp; + if (high != low) { + LoadConst32(reg, high); + } + } + Sw(reg, base, offset + kMipsWordSize); + break; + default: + LOG(FATAL) << "UNREACHABLE"; + } + if (type != kStoreDoubleword) { + null_checker(); } } @@ -685,6 +731,11 @@ class MipsAssembler FINAL : public Assembler, public JNIMacroAssembler<PointerSi return NewLiteral(sizeof(value), reinterpret_cast<const uint8_t*>(&value)); } + // Load label address using the base register (for R2 only) or using PC-relative loads + // (for R6 only; base_reg must be ZERO). To be used with data labels in the literal / + // jump table area only and not with regular code labels. + void LoadLabelAddress(Register dest_reg, Register base_reg, MipsLabel* label); + // Create a new literal with the given data. Literal* NewLiteral(size_t size, const uint8_t* data); @@ -692,6 +743,12 @@ class MipsAssembler FINAL : public Assembler, public JNIMacroAssembler<PointerSi // (for R6 only; base_reg must be ZERO). void LoadLiteral(Register dest_reg, Register base_reg, Literal* literal); + // Create a jump table for the given labels that will be emitted when finalizing. + // When the table is emitted, offsets will be relative to the location of the table. + // The table location is determined by the location of its label (the label precedes + // the table data) and should be loaded using LoadLabelAddress(). + JumpTable* CreateJumpTable(std::vector<MipsLabel*>&& labels); + // // Overridden common assembler high-level functionality. // @@ -935,24 +992,32 @@ class MipsAssembler FINAL : public Assembler, public JNIMacroAssembler<PointerSi kUncondBranch, kCondBranch, kCall, + // R2 near label. + kLabel, // R2 near literal. kLiteral, // R2 long branches. kLongUncondBranch, kLongCondBranch, kLongCall, + // R2 far label. + kFarLabel, // R2 far literal. kFarLiteral, // R6 short branches. kR6UncondBranch, kR6CondBranch, kR6Call, + // R6 near label. + kR6Label, // R6 near literal. kR6Literal, // R6 long branches. kR6LongUncondBranch, kR6LongCondBranch, kR6LongCall, + // R6 far label. + kR6FarLabel, // R6 far literal. kR6FarLiteral, }; @@ -1009,8 +1074,12 @@ class MipsAssembler FINAL : public Assembler, public JNIMacroAssembler<PointerSi BranchCondition condition, Register lhs_reg, Register rhs_reg); - // Literal. - Branch(bool is_r6, uint32_t location, Register dest_reg, Register base_reg); + // Label address (in literal area) or literal. + Branch(bool is_r6, + uint32_t location, + Register dest_reg, + Register base_reg, + Type label_or_literal_type); // Some conditional branches with lhs = rhs are effectively NOPs, while some // others are effectively unconditional. MIPSR6 conditional branches require lhs != rhs. @@ -1105,7 +1174,7 @@ class MipsAssembler FINAL : public Assembler, public JNIMacroAssembler<PointerSi private: // Completes branch construction by determining and recording its type. - void InitializeType(bool is_call, bool is_literal, bool is_r6); + void InitializeType(Type initial_type, bool is_r6); // Helper for the above. void InitShortOrLong(OffsetBits ofs_size, Type short_type, Type long_type); @@ -1178,6 +1247,8 @@ class MipsAssembler FINAL : public Assembler, public JNIMacroAssembler<PointerSi uint32_t GetBranchOrPcRelBaseForEncoding(const MipsAssembler::Branch* branch) const; void EmitLiterals(); + void ReserveJumpTableSpace(); + void EmitJumpTables(); void PromoteBranches(); void EmitBranch(Branch* branch); void EmitBranches(); @@ -1227,6 +1298,9 @@ class MipsAssembler FINAL : public Assembler, public JNIMacroAssembler<PointerSi // without invalidating pointers and references to existing elements. ArenaDeque<Literal> literals_; + // Jump table list. + ArenaDeque<JumpTable> jump_tables_; + // There's no PC-relative addressing on MIPS32R2. So, in order to access literals relative to PC // we get PC using the NAL instruction. This label marks the position within the assembler buffer // that PC (from NAL) points to. diff --git a/compiler/utils/mips/assembler_mips32r6_test.cc b/compiler/utils/mips/assembler_mips32r6_test.cc index fabb0962fb..750a94df02 100644 --- a/compiler/utils/mips/assembler_mips32r6_test.cc +++ b/compiler/utils/mips/assembler_mips32r6_test.cc @@ -309,6 +309,12 @@ TEST_F(AssemblerMIPS32r6Test, Lwpc) { DriverStr(RepeatRIb(&mips::MipsAssembler::Lwpc, 19, code), "Lwpc"); } +TEST_F(AssemblerMIPS32r6Test, Addiupc) { + // The comment from the Lwpc() test applies to this Addiupc() test as well. + const char* code = ".set imm, {imm}\naddiupc ${reg}, (imm - ((imm & 0x40000) << 1)) << 2"; + DriverStr(RepeatRIb(&mips::MipsAssembler::Addiupc, 19, code), "Addiupc"); +} + TEST_F(AssemblerMIPS32r6Test, Bitswap) { DriverStr(RepeatRR(&mips::MipsAssembler::Bitswap, "bitswap ${reg1}, ${reg2}"), "bitswap"); } @@ -635,6 +641,40 @@ TEST_F(AssemblerMIPS32r6Test, StoreDToOffset) { DriverStr(expected, "StoreDToOffset"); } +TEST_F(AssemblerMIPS32r6Test, LoadFarthestNearLabelAddress) { + mips::MipsLabel label; + __ LoadLabelAddress(mips::V0, mips::ZERO, &label); + constexpr size_t kAdduCount = 0x3FFDE; + for (size_t i = 0; i != kAdduCount; ++i) { + __ Addu(mips::ZERO, mips::ZERO, mips::ZERO); + } + __ Bind(&label); + + std::string expected = + "lapc $v0, 1f\n" + + RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") + + "1:\n"; + DriverStr(expected, "LoadFarthestNearLabelAddress"); +} + +TEST_F(AssemblerMIPS32r6Test, LoadNearestFarLabelAddress) { + mips::MipsLabel label; + __ LoadLabelAddress(mips::V0, mips::ZERO, &label); + constexpr size_t kAdduCount = 0x3FFDF; + for (size_t i = 0; i != kAdduCount; ++i) { + __ Addu(mips::ZERO, mips::ZERO, mips::ZERO); + } + __ Bind(&label); + + std::string expected = + "1:\n" + "auipc $at, %hi(2f - 1b)\n" + "addiu $v0, $at, %lo(2f - 1b)\n" + + RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") + + "2:\n"; + DriverStr(expected, "LoadNearestFarLabelAddress"); +} + TEST_F(AssemblerMIPS32r6Test, LoadFarthestNearLiteral) { mips::Literal* literal = __ NewLiteral<uint32_t>(0x12345678); __ LoadLiteral(mips::V0, mips::ZERO, literal); @@ -811,8 +851,7 @@ TEST_F(AssemblerMIPS32r6Test, LongBranchReorder) { DriverStr(expected, "LongBeqc"); } -// TODO: MipsAssembler::Addiupc -// MipsAssembler::Bc +// TODO: MipsAssembler::Bc // MipsAssembler::Jic // MipsAssembler::Jialc // MipsAssembler::Bltc diff --git a/compiler/utils/mips/assembler_mips_test.cc b/compiler/utils/mips/assembler_mips_test.cc index 708bc3d50d..a9abf2f86e 100644 --- a/compiler/utils/mips/assembler_mips_test.cc +++ b/compiler/utils/mips/assembler_mips_test.cc @@ -1977,6 +1977,85 @@ TEST_F(AssemblerMIPSTest, StoreDToOffset) { DriverStr(expected, "StoreDToOffset"); } +TEST_F(AssemblerMIPSTest, StoreConstToOffset) { + __ StoreConstToOffset(mips::kStoreByte, 0xFF, mips::A1, +0, mips::T8); + __ StoreConstToOffset(mips::kStoreHalfword, 0xFFFF, mips::A1, +0, mips::T8); + __ StoreConstToOffset(mips::kStoreWord, 0x12345678, mips::A1, +0, mips::T8); + __ StoreConstToOffset(mips::kStoreDoubleword, 0x123456789ABCDEF0, mips::A1, +0, mips::T8); + + __ StoreConstToOffset(mips::kStoreByte, 0, mips::A1, +0, mips::T8); + __ StoreConstToOffset(mips::kStoreHalfword, 0, mips::A1, +0, mips::T8); + __ StoreConstToOffset(mips::kStoreWord, 0, mips::A1, +0, mips::T8); + __ StoreConstToOffset(mips::kStoreDoubleword, 0, mips::A1, +0, mips::T8); + + __ StoreConstToOffset(mips::kStoreDoubleword, 0x1234567812345678, mips::A1, +0, mips::T8); + __ StoreConstToOffset(mips::kStoreDoubleword, 0x1234567800000000, mips::A1, +0, mips::T8); + __ StoreConstToOffset(mips::kStoreDoubleword, 0x0000000012345678, mips::A1, +0, mips::T8); + + __ StoreConstToOffset(mips::kStoreWord, 0, mips::T8, +0, mips::T8); + __ StoreConstToOffset(mips::kStoreWord, 0x12345678, mips::T8, +0, mips::T8); + + __ StoreConstToOffset(mips::kStoreWord, 0, mips::A1, -0xFFF0, mips::T8); + __ StoreConstToOffset(mips::kStoreWord, 0x12345678, mips::A1, +0xFFF0, mips::T8); + + __ StoreConstToOffset(mips::kStoreWord, 0, mips::T8, -0xFFF0, mips::T8); + __ StoreConstToOffset(mips::kStoreWord, 0x12345678, mips::T8, +0xFFF0, mips::T8); + + const char* expected = + "ori $t8, $zero, 0xFF\n" + "sb $t8, 0($a1)\n" + "ori $t8, $zero, 0xFFFF\n" + "sh $t8, 0($a1)\n" + "lui $t8, 0x1234\n" + "ori $t8, $t8, 0x5678\n" + "sw $t8, 0($a1)\n" + "lui $t8, 0x9ABC\n" + "ori $t8, $t8, 0xDEF0\n" + "sw $t8, 0($a1)\n" + "lui $t8, 0x1234\n" + "ori $t8, $t8, 0x5678\n" + "sw $t8, 4($a1)\n" + + "sb $zero, 0($a1)\n" + "sh $zero, 0($a1)\n" + "sw $zero, 0($a1)\n" + "sw $zero, 0($a1)\n" + "sw $zero, 4($a1)\n" + + "lui $t8, 0x1234\n" + "ori $t8, $t8, 0x5678\n" + "sw $t8, 0($a1)\n" + "sw $t8, 4($a1)\n" + "sw $zero, 0($a1)\n" + "lui $t8, 0x1234\n" + "ori $t8, $t8, 0x5678\n" + "sw $t8, 4($a1)\n" + "lui $t8, 0x1234\n" + "ori $t8, $t8, 0x5678\n" + "sw $t8, 0($a1)\n" + "sw $zero, 4($a1)\n" + + "sw $zero, 0($t8)\n" + "lui $at, 0x1234\n" + "ori $at, $at, 0x5678\n" + "sw $at, 0($t8)\n" + + "addiu $at, $a1, -0x7FF8\n" + "sw $zero, -0x7FF8($at)\n" + "addiu $at, $a1, 0x7FF8\n" + "lui $t8, 0x1234\n" + "ori $t8, $t8, 0x5678\n" + "sw $t8, 0x7FF8($at)\n" + + "addiu $at, $t8, -0x7FF8\n" + "sw $zero, -0x7FF8($at)\n" + "addiu $at, $t8, 0x7FF8\n" + "lui $t8, 0x1234\n" + "ori $t8, $t8, 0x5678\n" + "sw $t8, 0x7FF8($at)\n"; + DriverStr(expected, "StoreConstToOffset"); +} + TEST_F(AssemblerMIPSTest, B) { mips::MipsLabel label1, label2; __ B(&label1); @@ -2307,6 +2386,44 @@ TEST_F(AssemblerMIPSTest, LoadConst32) { DriverStr(expected, "LoadConst32"); } +TEST_F(AssemblerMIPSTest, LoadFarthestNearLabelAddress) { + mips::MipsLabel label; + __ BindPcRelBaseLabel(); + __ LoadLabelAddress(mips::V0, mips::V1, &label); + constexpr size_t kAddiuCount = 0x1FDE; + for (size_t i = 0; i != kAddiuCount; ++i) { + __ Addiu(mips::A0, mips::A1, 0); + } + __ Bind(&label); + + std::string expected = + "1:\n" + "addiu $v0, $v1, %lo(2f - 1b)\n" + + RepeatInsn(kAddiuCount, "addiu $a0, $a1, %hi(2f - 1b)\n") + + "2:\n"; + DriverStr(expected, "LoadFarthestNearLabelAddress"); +} + +TEST_F(AssemblerMIPSTest, LoadNearestFarLabelAddress) { + mips::MipsLabel label; + __ BindPcRelBaseLabel(); + __ LoadLabelAddress(mips::V0, mips::V1, &label); + constexpr size_t kAdduCount = 0x1FDF; + for (size_t i = 0; i != kAdduCount; ++i) { + __ Addu(mips::ZERO, mips::ZERO, mips::ZERO); + } + __ Bind(&label); + + std::string expected = + "1:\n" + "lui $at, %hi(2f - 1b)\n" + "ori $at, $at, %lo(2f - 1b)\n" + "addu $v0, $at, $v1\n" + + RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") + + "2:\n"; + DriverStr(expected, "LoadNearestFarLabelAddress"); +} + TEST_F(AssemblerMIPSTest, LoadFarthestNearLiteral) { mips::Literal* literal = __ NewLiteral<uint32_t>(0x12345678); __ BindPcRelBaseLabel(); diff --git a/compiler/utils/swap_space.h b/compiler/utils/swap_space.h index bf06675d72..9600907278 100644 --- a/compiler/utils/swap_space.h +++ b/compiler/utils/swap_space.h @@ -114,7 +114,8 @@ class SwapAllocator<void> { explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {} template <typename U> - SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {} + SwapAllocator(const SwapAllocator<U>& other) // NOLINT, implicit + : swap_space_(other.swap_space_) {} SwapAllocator(const SwapAllocator& other) = default; SwapAllocator& operator=(const SwapAllocator& other) = default; @@ -149,7 +150,8 @@ class SwapAllocator { explicit SwapAllocator(SwapSpace* swap_space) : swap_space_(swap_space) {} template <typename U> - SwapAllocator(const SwapAllocator<U>& other) : swap_space_(other.swap_space_) {} + SwapAllocator(const SwapAllocator<U>& other) // NOLINT, implicit + : swap_space_(other.swap_space_) {} SwapAllocator(const SwapAllocator& other) = default; SwapAllocator& operator=(const SwapAllocator& other) = default; diff --git a/compiler/utils/transform_array_ref.h b/compiler/utils/transform_array_ref.h deleted file mode 100644 index a6da34fb40..0000000000 --- a/compiler/utils/transform_array_ref.h +++ /dev/null @@ -1,196 +0,0 @@ -/* - * Copyright (C) 2016 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. - */ - -#ifndef ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_ -#define ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_ - -#include <type_traits> - -#include "utils/array_ref.h" -#include "utils/transform_iterator.h" - -namespace art { - -/** - * @brief An ArrayRef<> wrapper that uses a transformation function for element access. - */ -template <typename BaseType, typename Function> -class TransformArrayRef { - private: - using Iter = TransformIterator<typename ArrayRef<BaseType>::iterator, Function>; - - // The Function may take a non-const reference, so const_iterator may not exist. - using FallbackConstIter = std::iterator<std::random_access_iterator_tag, void, void, void, void>; - using PreferredConstIter = - TransformIterator<typename ArrayRef<BaseType>::const_iterator, Function>; - template <typename F, typename = typename std::result_of<F(const BaseType&)>::type> - static PreferredConstIter ConstIterHelper(int&); - template <typename F> - static FallbackConstIter ConstIterHelper(const int&); - - using ConstIter = decltype(ConstIterHelper<Function>(*reinterpret_cast<int*>(0))); - - public: - using value_type = typename Iter::value_type; - using reference = typename Iter::reference; - using const_reference = typename ConstIter::reference; - using pointer = typename Iter::pointer; - using const_pointer = typename ConstIter::pointer; - using iterator = Iter; - using const_iterator = typename std::conditional< - std::is_same<ConstIter, FallbackConstIter>::value, - void, - ConstIter>::type; - using reverse_iterator = std::reverse_iterator<Iter>; - using const_reverse_iterator = typename std::conditional< - std::is_same<ConstIter, FallbackConstIter>::value, - void, - std::reverse_iterator<ConstIter>>::type; - using difference_type = typename ArrayRef<BaseType>::difference_type; - using size_type = typename ArrayRef<BaseType>::size_type; - - // Constructors. - - TransformArrayRef(const TransformArrayRef& other) = default; - - template <typename OtherBT> - TransformArrayRef(const ArrayRef<OtherBT>& base, Function fn) - : data_(base, fn) { } - - template <typename OtherBT, - typename = typename std::enable_if<std::is_same<BaseType, const OtherBT>::value>::type> - TransformArrayRef(const TransformArrayRef<OtherBT, Function>& other) - : TransformArrayRef(other.base(), other.GetFunction()) { } - - // Assignment operators. - - TransformArrayRef& operator=(const TransformArrayRef& other) = default; - - template <typename OtherBT, - typename = typename std::enable_if<std::is_same<BaseType, const OtherBT>::value>::type> - TransformArrayRef& operator=(const TransformArrayRef<OtherBT, Function>& other) { - return *this = TransformArrayRef(other.base(), other.GetFunction()); - } - - // Destructor. - ~TransformArrayRef() = default; - - // Iterators. - iterator begin() { return MakeIterator(base().begin()); } - const_iterator begin() const { return MakeIterator(base().cbegin()); } - const_iterator cbegin() const { return MakeIterator(base().cbegin()); } - iterator end() { return MakeIterator(base().end()); } - const_iterator end() const { MakeIterator(base().cend()); } - const_iterator cend() const { return MakeIterator(base().cend()); } - reverse_iterator rbegin() { return reverse_iterator(end()); } - const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } - const_reverse_iterator crbegin() const { return const_reverse_iterator(cend()); } - reverse_iterator rend() { return reverse_iterator(begin()); } - const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } - const_reverse_iterator crend() const { return const_reverse_iterator(cbegin()); } - - // Size. - size_type size() const { return base().size(); } - bool empty() const { return base().empty(); } - - // Element access. NOTE: Not providing data(). - - reference operator[](size_type n) { return GetFunction()(base()[n]); } - const_reference operator[](size_type n) const { return GetFunction()(base()[n]); } - - reference front() { return GetFunction()(base().front()); } - const_reference front() const { return GetFunction()(base().front()); } - - reference back() { return GetFunction()(base().back()); } - const_reference back() const { return GetFunction()(base().back()); } - - TransformArrayRef SubArray(size_type pos) { - return TransformArrayRef(base().subarray(pos), GetFunction()); - } - TransformArrayRef SubArray(size_type pos) const { - return TransformArrayRef(base().subarray(pos), GetFunction()); - } - TransformArrayRef SubArray(size_type pos, size_type length) const { - return TransformArrayRef(base().subarray(pos, length), GetFunction()); - } - - // Retrieve the base ArrayRef<>. - ArrayRef<BaseType> base() { - return data_.base_; - } - ArrayRef<const BaseType> base() const { - return ArrayRef<const BaseType>(data_.base_); - } - - private: - // Allow EBO for state-less Function. - struct Data : Function { - public: - Data(ArrayRef<BaseType> base, Function fn) : Function(fn), base_(base) { } - - ArrayRef<BaseType> base_; - }; - - const Function& GetFunction() const { - return static_cast<const Function&>(data_); - } - - template <typename BaseIterator> - auto MakeIterator(BaseIterator base) const { - return MakeTransformIterator(base, GetFunction()); - } - - Data data_; - - template <typename OtherBT, typename OtherFunction> - friend class TransformArrayRef; -}; - -template <typename BaseType, typename Function> -bool operator==(const TransformArrayRef<BaseType, Function>& lhs, - const TransformArrayRef<BaseType, Function>& rhs) { - return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin()); -} - -template <typename BaseType, typename Function> -bool operator!=(const TransformArrayRef<BaseType, Function>& lhs, - const TransformArrayRef<BaseType, Function>& rhs) { - return !(lhs == rhs); -} - -template <typename ValueType, typename Function> -TransformArrayRef<ValueType, Function> MakeTransformArrayRef( - ArrayRef<ValueType> container, Function f) { - return TransformArrayRef<ValueType, Function>(container, f); -} - -template <typename Container, typename Function> -TransformArrayRef<typename Container::value_type, Function> MakeTransformArrayRef( - Container& container, Function f) { - return TransformArrayRef<typename Container::value_type, Function>( - ArrayRef<typename Container::value_type>(container.data(), container.size()), f); -} - -template <typename Container, typename Function> -TransformArrayRef<const typename Container::value_type, Function> MakeTransformArrayRef( - const Container& container, Function f) { - return TransformArrayRef<const typename Container::value_type, Function>( - ArrayRef<const typename Container::value_type>(container.data(), container.size()), f); -} - -} // namespace art - -#endif // ART_COMPILER_UTILS_TRANSFORM_ARRAY_REF_H_ diff --git a/compiler/utils/transform_array_ref_test.cc b/compiler/utils/transform_array_ref_test.cc deleted file mode 100644 index 8d71fd7179..0000000000 --- a/compiler/utils/transform_array_ref_test.cc +++ /dev/null @@ -1,207 +0,0 @@ -/* - * Copyright (C) 2016 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 <algorithm> -#include <vector> - -#include "gtest/gtest.h" - -#include "utils/transform_array_ref.h" - -namespace art { - -namespace { // anonymous namespace - -struct ValueHolder { - // Deliberately not explicit. - ValueHolder(int v) : value(v) { } // NOLINT - int value; -}; - -ATTRIBUTE_UNUSED bool operator==(const ValueHolder& lhs, const ValueHolder& rhs) { - return lhs.value == rhs.value; -} - -} // anonymous namespace - -TEST(TransformArrayRef, ConstRefAdd1) { - auto add1 = [](const ValueHolder& h) { return h.value + 1; }; // NOLINT [readability/braces] - std::vector<ValueHolder> input({ 7, 6, 4, 0 }); - std::vector<int> output; - - auto taref = MakeTransformArrayRef(input, add1); - using TarefIter = decltype(taref)::iterator; - using ConstTarefIter = decltype(taref)::const_iterator; - static_assert(std::is_same<int, decltype(taref)::value_type>::value, "value_type"); - static_assert(std::is_same<TarefIter, decltype(taref)::pointer>::value, "pointer"); - static_assert(std::is_same<int, decltype(taref)::reference>::value, "reference"); - static_assert(std::is_same<ConstTarefIter, decltype(taref)::const_pointer>::value, - "const_pointer"); - static_assert(std::is_same<int, decltype(taref)::const_reference>::value, "const_reference"); - - std::copy(taref.begin(), taref.end(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 8, 7, 5, 1 }), output); - output.clear(); - - std::copy(taref.cbegin(), taref.cend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 8, 7, 5, 1 }), output); - output.clear(); - - std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 5, 7, 8 }), output); - output.clear(); - - std::copy(taref.crbegin(), taref.crend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 5, 7, 8 }), output); - output.clear(); - - ASSERT_EQ(input.size(), taref.size()); - ASSERT_EQ(input.empty(), taref.empty()); - ASSERT_EQ(input.front().value + 1, taref.front()); - ASSERT_EQ(input.back().value + 1, taref.back()); - - for (size_t i = 0; i != input.size(); ++i) { - ASSERT_EQ(input[i].value + 1, taref[i]); - } -} - -TEST(TransformArrayRef, NonConstRefSub1) { - auto sub1 = [](ValueHolder& h) { return h.value - 1; }; // NOLINT [readability/braces] - std::vector<ValueHolder> input({ 4, 4, 5, 7, 10 }); - std::vector<int> output; - - auto taref = MakeTransformArrayRef(input, sub1); - using TarefIter = decltype(taref)::iterator; - static_assert(std::is_same<void, decltype(taref)::const_iterator>::value, "const_iterator"); - static_assert(std::is_same<int, decltype(taref)::value_type>::value, "value_type"); - static_assert(std::is_same<TarefIter, decltype(taref)::pointer>::value, "pointer"); - static_assert(std::is_same<int, decltype(taref)::reference>::value, "reference"); - static_assert(std::is_same<void, decltype(taref)::const_pointer>::value, "const_pointer"); - static_assert(std::is_same<void, decltype(taref)::const_reference>::value, "const_reference"); - - std::copy(taref.begin(), taref.end(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 3, 3, 4, 6, 9 }), output); - output.clear(); - - std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 9, 6, 4, 3, 3 }), output); - output.clear(); - - ASSERT_EQ(input.size(), taref.size()); - ASSERT_EQ(input.empty(), taref.empty()); - ASSERT_EQ(input.front().value - 1, taref.front()); - ASSERT_EQ(input.back().value - 1, taref.back()); - - for (size_t i = 0; i != input.size(); ++i) { - ASSERT_EQ(input[i].value - 1, taref[i]); - } -} - -TEST(TransformArrayRef, ConstAndNonConstRef) { - struct Ref { - int& operator()(ValueHolder& h) const { return h.value; } - const int& operator()(const ValueHolder& h) const { return h.value; } - }; - Ref ref; - std::vector<ValueHolder> input({ 1, 0, 1, 0, 3, 1 }); - std::vector<int> output; - - auto taref = MakeTransformArrayRef(input, ref); - static_assert(std::is_same<int, decltype(taref)::value_type>::value, "value_type"); - static_assert(std::is_same<int*, decltype(taref)::pointer>::value, "pointer"); - static_assert(std::is_same<int&, decltype(taref)::reference>::value, "reference"); - static_assert(std::is_same<const int*, decltype(taref)::const_pointer>::value, "const_pointer"); - static_assert(std::is_same<const int&, decltype(taref)::const_reference>::value, - "const_reference"); - - std::copy(taref.begin(), taref.end(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 0, 1, 0, 3, 1 }), output); - output.clear(); - - std::copy(taref.cbegin(), taref.cend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 0, 1, 0, 3, 1 }), output); - output.clear(); - - std::copy(taref.rbegin(), taref.rend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 3, 0, 1, 0, 1 }), output); - output.clear(); - - std::copy(taref.crbegin(), taref.crend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 3, 0, 1, 0, 1 }), output); - output.clear(); - - ASSERT_EQ(input.size(), taref.size()); - ASSERT_EQ(input.empty(), taref.empty()); - ASSERT_EQ(input.front().value, taref.front()); - ASSERT_EQ(input.back().value, taref.back()); - - for (size_t i = 0; i != input.size(); ++i) { - ASSERT_EQ(input[i].value, taref[i]); - } - - // Test writing through the transform iterator. - std::vector<int> transform_input({ 24, 37, 11, 71 }); - std::vector<ValueHolder> transformed(transform_input.size(), 0); - taref = MakeTransformArrayRef(transformed, ref); - for (size_t i = 0; i != transform_input.size(); ++i) { - taref[i] = transform_input[i]; - } - ASSERT_EQ(std::vector<ValueHolder>({ 24, 37, 11, 71 }), transformed); - - const std::vector<ValueHolder>& cinput = input; - - auto ctaref = MakeTransformArrayRef(cinput, ref); - static_assert(std::is_same<int, decltype(ctaref)::value_type>::value, "value_type"); - static_assert(std::is_same<const int*, decltype(ctaref)::pointer>::value, "pointer"); - static_assert(std::is_same<const int&, decltype(ctaref)::reference>::value, "reference"); - static_assert(std::is_same<const int*, decltype(ctaref)::const_pointer>::value, "const_pointer"); - static_assert(std::is_same<const int&, decltype(ctaref)::const_reference>::value, - "const_reference"); - - std::copy(ctaref.begin(), ctaref.end(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 0, 1, 0, 3, 1 }), output); - output.clear(); - - std::copy(ctaref.cbegin(), ctaref.cend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 0, 1, 0, 3, 1 }), output); - output.clear(); - - std::copy(ctaref.rbegin(), ctaref.rend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 3, 0, 1, 0, 1 }), output); - output.clear(); - - std::copy(ctaref.crbegin(), ctaref.crend(), std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 3, 0, 1, 0, 1 }), output); - output.clear(); - - ASSERT_EQ(cinput.size(), ctaref.size()); - ASSERT_EQ(cinput.empty(), ctaref.empty()); - ASSERT_EQ(cinput.front().value, ctaref.front()); - ASSERT_EQ(cinput.back().value, ctaref.back()); - - for (size_t i = 0; i != cinput.size(); ++i) { - ASSERT_EQ(cinput[i].value, ctaref[i]); - } - - // Test conversion adding const. - decltype(ctaref) ctaref2 = taref; - ASSERT_EQ(taref.size(), ctaref2.size()); - for (size_t i = 0; i != taref.size(); ++i) { - ASSERT_EQ(taref[i], ctaref2[i]); - } -} - -} // namespace art diff --git a/compiler/utils/transform_iterator.h b/compiler/utils/transform_iterator.h deleted file mode 100644 index 3bc9046408..0000000000 --- a/compiler/utils/transform_iterator.h +++ /dev/null @@ -1,178 +0,0 @@ -/* - * Copyright (C) 2016 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. - */ - -#ifndef ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_ -#define ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_ - -#include <iterator> -#include <type_traits> - -#include "base/iteration_range.h" - -namespace art { - -// The transform iterator transforms values from the base iterator with a given -// transformation function. It can serve as a replacement for std::transform(), i.e. -// std::copy(MakeTransformIterator(begin, f), MakeTransformIterator(end, f), out) -// is equivalent to -// std::transform(begin, end, f) -// If the function returns an l-value reference or a wrapper that supports assignment, -// the TransformIterator can be used also as an output iterator, i.e. -// std::copy(begin, end, MakeTransformIterator(out, f)) -// is equivalent to -// for (auto it = begin; it != end; ++it) { -// f(*out++) = *it; -// } -template <typename BaseIterator, typename Function> -class TransformIterator { - private: - static_assert(std::is_base_of< - std::input_iterator_tag, - typename std::iterator_traits<BaseIterator>::iterator_category>::value, - "Transform iterator base must be an input iterator."); - - using InputType = typename std::iterator_traits<BaseIterator>::reference; - using ResultType = typename std::result_of<Function(InputType)>::type; - - public: - using iterator_category = typename std::iterator_traits<BaseIterator>::iterator_category; - using value_type = - typename std::remove_const<typename std::remove_reference<ResultType>::type>::type; - using difference_type = typename std::iterator_traits<BaseIterator>::difference_type; - using pointer = typename std::conditional< - std::is_reference<ResultType>::value, - typename std::add_pointer<typename std::remove_reference<ResultType>::type>::type, - TransformIterator>::type; - using reference = ResultType; - - TransformIterator(BaseIterator base, Function fn) - : data_(base, fn) { } - - template <typename OtherBI> - TransformIterator(const TransformIterator<OtherBI, Function>& other) - : data_(other.base(), other.GetFunction()) { - } - - TransformIterator& operator++() { - ++data_.base_; - return *this; - } - - TransformIterator& operator++(int) { - TransformIterator tmp(*this); - ++*this; - return tmp; - } - - TransformIterator& operator--() { - static_assert( - std::is_base_of<std::bidirectional_iterator_tag, - typename std::iterator_traits<BaseIterator>::iterator_category>::value, - "BaseIterator must be bidirectional iterator to use operator--()"); - --data_.base_; - return *this; - } - - TransformIterator& operator--(int) { - TransformIterator tmp(*this); - --*this; - return tmp; - } - - reference operator*() const { - return GetFunction()(*base()); - } - - reference operator[](difference_type n) const { - static_assert( - std::is_base_of<std::random_access_iterator_tag, - typename std::iterator_traits<BaseIterator>::iterator_category>::value, - "BaseIterator must be random access iterator to use operator[]"); - return GetFunction()(base()[n]); - } - - TransformIterator operator+(difference_type n) const { - static_assert( - std::is_base_of<std::random_access_iterator_tag, - typename std::iterator_traits<BaseIterator>::iterator_category>::value, - "BaseIterator must be random access iterator to use operator+"); - return TransformIterator(base() + n, GetFunction()); - } - - TransformIterator operator-(difference_type n) const { - static_assert( - std::is_base_of<std::random_access_iterator_tag, - typename std::iterator_traits<BaseIterator>::iterator_category>::value, - "BaseIterator must be random access iterator to use operator-"); - return TransformIterator(base() - n, GetFunction()); - } - - difference_type operator-(const TransformIterator& other) const { - static_assert( - std::is_base_of<std::random_access_iterator_tag, - typename std::iterator_traits<BaseIterator>::iterator_category>::value, - "BaseIterator must be random access iterator to use operator-"); - return base() - other.base(); - } - - // Retrieve the base iterator. - BaseIterator base() const { - return data_.base_; - } - - // Retrieve the transformation function. - const Function& GetFunction() const { - return static_cast<const Function&>(data_); - } - - private: - // Allow EBO for state-less Function. - struct Data : Function { - public: - Data(BaseIterator base, Function fn) : Function(fn), base_(base) { } - - BaseIterator base_; - }; - - Data data_; -}; - -template <typename BaseIterator1, typename BaseIterator2, typename Function> -bool operator==(const TransformIterator<BaseIterator1, Function>& lhs, - const TransformIterator<BaseIterator2, Function>& rhs) { - return lhs.base() == rhs.base(); -} - -template <typename BaseIterator1, typename BaseIterator2, typename Function> -bool operator!=(const TransformIterator<BaseIterator1, Function>& lhs, - const TransformIterator<BaseIterator2, Function>& rhs) { - return !(lhs == rhs); -} - -template <typename BaseIterator, typename Function> -TransformIterator<BaseIterator, Function> MakeTransformIterator(BaseIterator base, Function f) { - return TransformIterator<BaseIterator, Function>(base, f); -} - -template <typename BaseRange, typename Function> -auto MakeTransformRange(BaseRange& range, Function f) { - return MakeIterationRange(MakeTransformIterator(range.begin(), f), - MakeTransformIterator(range.end(), f)); -} - -} // namespace art - -#endif // ART_COMPILER_UTILS_TRANSFORM_ITERATOR_H_ diff --git a/compiler/utils/transform_iterator_test.cc b/compiler/utils/transform_iterator_test.cc deleted file mode 100644 index 57ff0a62ac..0000000000 --- a/compiler/utils/transform_iterator_test.cc +++ /dev/null @@ -1,531 +0,0 @@ -/* - * Copyright (C) 2016 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 <algorithm> -#include <forward_list> -#include <list> -#include <type_traits> -#include <vector> - -#include "gtest/gtest.h" - -#include "utils/transform_iterator.h" - -namespace art { - -namespace { // anonymous namespace - -struct ValueHolder { - // Deliberately not explicit. - ValueHolder(int v) : value(v) { } // NOLINT - int value; -}; - -bool operator==(const ValueHolder& lhs, const ValueHolder& rhs) { - return lhs.value == rhs.value; -} - -} // anonymous namespace - -TEST(TransformIterator, VectorAdd1) { - auto add1 = [](const ValueHolder& h) { return h.value + 1; }; // NOLINT [readability/braces] - std::vector<ValueHolder> input({ 1, 7, 3, 8 }); - std::vector<int> output; - - using vector_titer = decltype(MakeTransformIterator(input.begin(), add1)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_titer::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type"); - static_assert(std::is_same<vector_titer, vector_titer::pointer>::value, "pointer"); - static_assert(std::is_same<int, vector_titer::reference>::value, "reference"); - - using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), add1)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_ctiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type"); - static_assert(std::is_same<vector_ctiter, vector_ctiter::pointer>::value, "pointer"); - static_assert(std::is_same<int, vector_ctiter::reference>::value, "reference"); - - using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), add1)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_rtiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type"); - static_assert(std::is_same<vector_rtiter, vector_rtiter::pointer>::value, "pointer"); - static_assert(std::is_same<int, vector_rtiter::reference>::value, "reference"); - - using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), add1)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_crtiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type"); - static_assert(std::is_same<vector_crtiter, vector_crtiter::pointer>::value, "pointer"); - static_assert(std::is_same<int, vector_crtiter::reference>::value, "reference"); - - std::copy(MakeTransformIterator(input.begin(), add1), - MakeTransformIterator(input.end(), add1), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 2, 8, 4, 9 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.cbegin(), add1), - MakeTransformIterator(input.cend(), add1), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 2, 8, 4, 9 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.rbegin(), add1), - MakeTransformIterator(input.rend(), add1), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 9, 4, 8, 2 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.crbegin(), add1), - MakeTransformIterator(input.crend(), add1), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 9, 4, 8, 2 }), output); - output.clear(); - - for (size_t i = 0; i != input.size(); ++i) { - ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.begin(), add1)[i]); - ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.cbegin(), add1)[i]); - ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u); - ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.rbegin(), add1)[index_from_rbegin]); - ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.crbegin(), add1)[index_from_rbegin]); - ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i); - ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.end(), add1)[index_from_end]); - ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.cend(), add1)[index_from_end]); - ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i); - ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.rend(), add1)[index_from_rend]); - ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.crend(), add1)[index_from_rend]); - - ASSERT_EQ(MakeTransformIterator(input.begin(), add1) + i, - MakeTransformIterator(input.begin() + i, add1)); - ASSERT_EQ(MakeTransformIterator(input.cbegin(), add1) + i, - MakeTransformIterator(input.cbegin() + i, add1)); - ASSERT_EQ(MakeTransformIterator(input.rbegin(), add1) + i, - MakeTransformIterator(input.rbegin() + i, add1)); - ASSERT_EQ(MakeTransformIterator(input.crbegin(), add1) + i, - MakeTransformIterator(input.crbegin() + i, add1)); - ASSERT_EQ(MakeTransformIterator(input.end(), add1) - i, - MakeTransformIterator(input.end() - i, add1)); - ASSERT_EQ(MakeTransformIterator(input.cend(), add1) - i, - MakeTransformIterator(input.cend() - i, add1)); - ASSERT_EQ(MakeTransformIterator(input.rend(), add1) - i, - MakeTransformIterator(input.rend() - i, add1)); - ASSERT_EQ(MakeTransformIterator(input.crend(), add1) - i, - MakeTransformIterator(input.crend() - i, add1)); - } - ASSERT_EQ(input.end(), - (MakeTransformIterator(input.begin(), add1) + input.size()).base()); - ASSERT_EQ(MakeTransformIterator(input.end(), add1) - MakeTransformIterator(input.begin(), add1), - static_cast<ptrdiff_t>(input.size())); - - // Test iterator->const_iterator conversion and comparison. - auto it = MakeTransformIterator(input.begin(), add1); - decltype(MakeTransformIterator(input.cbegin(), add1)) cit = it; - static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different"); - ASSERT_EQ(it, cit); - auto rit = MakeTransformIterator(input.rbegin(), add1); - decltype(MakeTransformIterator(input.crbegin(), add1)) crit(rit); - static_assert(!std::is_same<decltype(rit), decltype(crit)>::value, "Types must be different"); - ASSERT_EQ(rit, crit); -} - -TEST(TransformIterator, ListSub1) { - auto sub1 = [](const ValueHolder& h) { return h.value - 1; }; // NOLINT [readability/braces] - std::list<ValueHolder> input({ 2, 3, 5, 7, 11 }); - std::vector<int> output; - - using list_titer = decltype(MakeTransformIterator(input.begin(), sub1)); - static_assert(std::is_same<std::bidirectional_iterator_tag, - list_titer::iterator_category>::value, "category"); - static_assert(std::is_same<int, list_titer::value_type>::value, "value_type"); - static_assert(std::is_same<list_titer, list_titer::pointer>::value, "pointer"); - static_assert(std::is_same<int, list_titer::reference>::value, "reference"); - - using list_ctiter = decltype(MakeTransformIterator(input.cbegin(), sub1)); - static_assert(std::is_same<std::bidirectional_iterator_tag, - list_ctiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, list_ctiter::value_type>::value, "value_type"); - static_assert(std::is_same<list_ctiter, list_ctiter::pointer>::value, "pointer"); - static_assert(std::is_same<int, list_ctiter::reference>::value, "reference"); - - using list_rtiter = decltype(MakeTransformIterator(input.rbegin(), sub1)); - static_assert(std::is_same<std::bidirectional_iterator_tag, - list_rtiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, list_rtiter::value_type>::value, "value_type"); - static_assert(std::is_same<list_rtiter, list_rtiter::pointer>::value, "pointer"); - static_assert(std::is_same<int, list_rtiter::reference>::value, "reference"); - - using list_crtiter = decltype(MakeTransformIterator(input.crbegin(), sub1)); - static_assert(std::is_same<std::bidirectional_iterator_tag, - list_crtiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, list_crtiter::value_type>::value, "value_type"); - static_assert(std::is_same<list_crtiter, list_crtiter::pointer>::value, "pointer"); - static_assert(std::is_same<int, list_crtiter::reference>::value, "reference"); - - std::copy(MakeTransformIterator(input.begin(), sub1), - MakeTransformIterator(input.end(), sub1), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 2, 4, 6, 10 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.cbegin(), sub1), - MakeTransformIterator(input.cend(), sub1), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 1, 2, 4, 6, 10 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.rbegin(), sub1), - MakeTransformIterator(input.rend(), sub1), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 10, 6, 4, 2, 1 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.crbegin(), sub1), - MakeTransformIterator(input.crend(), sub1), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 10, 6, 4, 2, 1 }), output); - output.clear(); - - // Test iterator->const_iterator conversion and comparison. - auto it = MakeTransformIterator(input.begin(), sub1); - decltype(MakeTransformIterator(input.cbegin(), sub1)) cit = it; - static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different"); - ASSERT_EQ(it, cit); -} - -TEST(TransformIterator, ForwardListSub1) { - auto mul3 = [](const ValueHolder& h) { return h.value * 3; }; // NOLINT [readability/braces] - std::forward_list<ValueHolder> input({ 1, 1, 2, 3, 5, 8 }); - std::vector<int> output; - - using flist_titer = decltype(MakeTransformIterator(input.begin(), mul3)); - static_assert(std::is_same<std::forward_iterator_tag, - flist_titer::iterator_category>::value, "category"); - static_assert(std::is_same<int, flist_titer::value_type>::value, "value_type"); - static_assert(std::is_same<flist_titer, flist_titer::pointer>::value, "pointer"); - static_assert(std::is_same<int, flist_titer::reference>::value, "reference"); - - using flist_ctiter = decltype(MakeTransformIterator(input.cbegin(), mul3)); - static_assert(std::is_same<std::forward_iterator_tag, - flist_ctiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, flist_ctiter::value_type>::value, "value_type"); - static_assert(std::is_same<flist_ctiter, flist_ctiter::pointer>::value, "pointer"); - static_assert(std::is_same<int, flist_ctiter::reference>::value, "reference"); - - std::copy(MakeTransformIterator(input.begin(), mul3), - MakeTransformIterator(input.end(), mul3), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 3, 3, 6, 9, 15, 24 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.cbegin(), mul3), - MakeTransformIterator(input.cend(), mul3), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 3, 3, 6, 9, 15, 24 }), output); - output.clear(); - - // Test iterator->const_iterator conversion and comparison. - auto it = MakeTransformIterator(input.begin(), mul3); - decltype(MakeTransformIterator(input.cbegin(), mul3)) cit = it; - static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different"); - ASSERT_EQ(it, cit); -} - -TEST(TransformIterator, VectorConstReference) { - auto ref = [](const ValueHolder& h) -> const int& { return h.value; }; // NOLINT [readability/braces] - std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 }); - std::vector<int> output; - - using vector_titer = decltype(MakeTransformIterator(input.begin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_titer::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type"); - static_assert(std::is_same<const int*, vector_titer::pointer>::value, "pointer"); - static_assert(std::is_same<const int&, vector_titer::reference>::value, "reference"); - - using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_ctiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type"); - static_assert(std::is_same<const int*, vector_ctiter::pointer>::value, "pointer"); - static_assert(std::is_same<const int&, vector_ctiter::reference>::value, "reference"); - - using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_rtiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type"); - static_assert(std::is_same<const int*, vector_rtiter::pointer>::value, "pointer"); - static_assert(std::is_same<const int&, vector_rtiter::reference>::value, "reference"); - - using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_crtiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type"); - static_assert(std::is_same<const int*, vector_crtiter::pointer>::value, "pointer"); - static_assert(std::is_same<const int&, vector_crtiter::reference>::value, "reference"); - - std::copy(MakeTransformIterator(input.begin(), ref), - MakeTransformIterator(input.end(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.cbegin(), ref), - MakeTransformIterator(input.cend(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.rbegin(), ref), - MakeTransformIterator(input.rend(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.crbegin(), ref), - MakeTransformIterator(input.crend(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output); - output.clear(); - - for (size_t i = 0; i != input.size(); ++i) { - ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.cbegin(), ref)[i]); - ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.crbegin(), ref)[index_from_rbegin]); - ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.cend(), ref)[index_from_end]); - ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.crend(), ref)[index_from_rend]); - - ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i, - MakeTransformIterator(input.begin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.cbegin(), ref) + i, - MakeTransformIterator(input.cbegin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i, - MakeTransformIterator(input.rbegin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.crbegin(), ref) + i, - MakeTransformIterator(input.crbegin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i, - MakeTransformIterator(input.end() - i, ref)); - ASSERT_EQ(MakeTransformIterator(input.cend(), ref) - i, - MakeTransformIterator(input.cend() - i, ref)); - ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i, - MakeTransformIterator(input.rend() - i, ref)); - ASSERT_EQ(MakeTransformIterator(input.crend(), ref) - i, - MakeTransformIterator(input.crend() - i, ref)); - } - ASSERT_EQ(input.end(), - (MakeTransformIterator(input.begin(), ref) + input.size()).base()); - ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref), - static_cast<ptrdiff_t>(input.size())); -} - -TEST(TransformIterator, VectorNonConstReference) { - auto ref = [](ValueHolder& h) -> int& { return h.value; }; // NOLINT [readability/braces] - std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 }); - std::vector<int> output; - - using vector_titer = decltype(MakeTransformIterator(input.begin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_titer::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type"); - static_assert(std::is_same<int*, vector_titer::pointer>::value, "pointer"); - static_assert(std::is_same<int&, vector_titer::reference>::value, "reference"); - - using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_rtiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type"); - static_assert(std::is_same<int*, vector_rtiter::pointer>::value, "pointer"); - static_assert(std::is_same<int&, vector_rtiter::reference>::value, "reference"); - - std::copy(MakeTransformIterator(input.begin(), ref), - MakeTransformIterator(input.end(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.rbegin(), ref), - MakeTransformIterator(input.rend(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output); - output.clear(); - - for (size_t i = 0; i != input.size(); ++i) { - ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]); - ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]); - ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]); - ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]); - - ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i, - MakeTransformIterator(input.begin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i, - MakeTransformIterator(input.rbegin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i, - MakeTransformIterator(input.end() - i, ref)); - ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i, - MakeTransformIterator(input.rend() - i, ref)); - } - ASSERT_EQ(input.end(), - (MakeTransformIterator(input.begin(), ref) + input.size()).base()); - ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref), - static_cast<ptrdiff_t>(input.size())); - - // Test writing through the transform iterator. - std::list<int> transform_input({ 1, -1, 2, -2, 3, -3 }); - std::vector<ValueHolder> transformed(transform_input.size(), 0); - std::transform(transform_input.begin(), - transform_input.end(), - MakeTransformIterator(transformed.begin(), ref), - [](int v) { return -2 * v; }); - ASSERT_EQ(std::vector<ValueHolder>({ -2, 2, -4, 4, -6, 6 }), transformed); -} - -TEST(TransformIterator, VectorConstAndNonConstReference) { - struct Ref { - int& operator()(ValueHolder& h) const { return h.value; } - const int& operator()(const ValueHolder& h) const { return h.value; } - }; - Ref ref; - std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 }); - std::vector<int> output; - - using vector_titer = decltype(MakeTransformIterator(input.begin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_titer::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type"); - static_assert(std::is_same<int*, vector_titer::pointer>::value, "pointer"); - static_assert(std::is_same<int&, vector_titer::reference>::value, "reference"); - - using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_ctiter::iterator_category>::value, "category"); - // static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type"); - static_assert(std::is_same<const int*, vector_ctiter::pointer>::value, "pointer"); - static_assert(std::is_same<const int&, vector_ctiter::reference>::value, "reference"); - - using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_rtiter::iterator_category>::value, "category"); - static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type"); - static_assert(std::is_same<int*, vector_rtiter::pointer>::value, "pointer"); - static_assert(std::is_same<int&, vector_rtiter::reference>::value, "reference"); - - using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref)); - static_assert(std::is_same<std::random_access_iterator_tag, - vector_crtiter::iterator_category>::value, "category"); - // static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type"); - static_assert(std::is_same<const int*, vector_crtiter::pointer>::value, "pointer"); - static_assert(std::is_same<const int&, vector_crtiter::reference>::value, "reference"); - - std::copy(MakeTransformIterator(input.begin(), ref), - MakeTransformIterator(input.end(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.cbegin(), ref), - MakeTransformIterator(input.cend(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.rbegin(), ref), - MakeTransformIterator(input.rend(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output); - output.clear(); - - std::copy(MakeTransformIterator(input.crbegin(), ref), - MakeTransformIterator(input.crend(), ref), - std::back_inserter(output)); - ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output); - output.clear(); - - for (size_t i = 0; i != input.size(); ++i) { - ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.cbegin(), ref)[i]); - ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.crbegin(), ref)[index_from_rbegin]); - ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.cend(), ref)[index_from_end]); - ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]); - ASSERT_EQ(input[i].value, MakeTransformIterator(input.crend(), ref)[index_from_rend]); - - ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i, - MakeTransformIterator(input.begin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.cbegin(), ref) + i, - MakeTransformIterator(input.cbegin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i, - MakeTransformIterator(input.rbegin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.crbegin(), ref) + i, - MakeTransformIterator(input.crbegin() + i, ref)); - ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i, - MakeTransformIterator(input.end() - i, ref)); - ASSERT_EQ(MakeTransformIterator(input.cend(), ref) - i, - MakeTransformIterator(input.cend() - i, ref)); - ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i, - MakeTransformIterator(input.rend() - i, ref)); - ASSERT_EQ(MakeTransformIterator(input.crend(), ref) - i, - MakeTransformIterator(input.crend() - i, ref)); - } - ASSERT_EQ(input.end(), - (MakeTransformIterator(input.begin(), ref) + input.size()).base()); - ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref), - static_cast<ptrdiff_t>(input.size())); - - // Test iterator->const_iterator conversion and comparison. - auto it = MakeTransformIterator(input.begin(), ref); - decltype(MakeTransformIterator(input.cbegin(), ref)) cit = it; - static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different"); - ASSERT_EQ(it, cit); - auto rit = MakeTransformIterator(input.rbegin(), ref); - decltype(MakeTransformIterator(input.crbegin(), ref)) crit(rit); - static_assert(!std::is_same<decltype(rit), decltype(crit)>::value, "Types must be different"); - ASSERT_EQ(rit, crit); - - // Test writing through the transform iterator. - std::list<int> transform_input({ 42, 73, 11, 17 }); - std::vector<ValueHolder> transformed(transform_input.size(), 0); - std::transform(transform_input.begin(), - transform_input.end(), - MakeTransformIterator(transformed.begin(), ref), - [](int v) { return -v; }); - ASSERT_EQ(std::vector<ValueHolder>({ -42, -73, -11, -17 }), transformed); -} - -TEST(TransformIterator, TransformRange) { - auto ref = [](ValueHolder& h) -> int& { return h.value; }; // NOLINT [readability/braces] - std::vector<ValueHolder> data({ 1, 0, 1, 3, 1, 0 }); - - for (int& v : MakeTransformRange(data, ref)) { - v += 11; - } - ASSERT_EQ(std::vector<ValueHolder>({ 12, 11, 12, 14, 12, 11 }), data); -} - -} // namespace art diff --git a/compiler/utils/x86/assembler_x86.h b/compiler/utils/x86/assembler_x86.h index 9738784d45..114986b3e7 100644 --- a/compiler/utils/x86/assembler_x86.h +++ b/compiler/utils/x86/assembler_x86.h @@ -20,6 +20,7 @@ #include <vector> #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/bit_utils.h" #include "base/enums.h" #include "base/macros.h" @@ -27,7 +28,6 @@ #include "globals.h" #include "managed_register_x86.h" #include "offsets.h" -#include "utils/array_ref.h" #include "utils/assembler.h" namespace art { diff --git a/compiler/utils/x86/jni_macro_assembler_x86.h b/compiler/utils/x86/jni_macro_assembler_x86.h index 3f07ede865..015584cbc1 100644 --- a/compiler/utils/x86/jni_macro_assembler_x86.h +++ b/compiler/utils/x86/jni_macro_assembler_x86.h @@ -21,10 +21,10 @@ #include "assembler_x86.h" #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/enums.h" #include "base/macros.h" #include "offsets.h" -#include "utils/array_ref.h" #include "utils/jni_macro_assembler.h" namespace art { diff --git a/compiler/utils/x86_64/assembler_x86_64.h b/compiler/utils/x86_64/assembler_x86_64.h index fdd3aa9317..acad86d161 100644 --- a/compiler/utils/x86_64/assembler_x86_64.h +++ b/compiler/utils/x86_64/assembler_x86_64.h @@ -20,13 +20,13 @@ #include <vector> #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/bit_utils.h" #include "base/macros.h" #include "constants_x86_64.h" #include "globals.h" #include "managed_register_x86_64.h" #include "offsets.h" -#include "utils/array_ref.h" #include "utils/assembler.h" #include "utils/jni_macro_assembler.h" diff --git a/compiler/utils/x86_64/jni_macro_assembler_x86_64.h b/compiler/utils/x86_64/jni_macro_assembler_x86_64.h index cc4e57c999..9107f3c422 100644 --- a/compiler/utils/x86_64/jni_macro_assembler_x86_64.h +++ b/compiler/utils/x86_64/jni_macro_assembler_x86_64.h @@ -21,10 +21,10 @@ #include "assembler_x86_64.h" #include "base/arena_containers.h" +#include "base/array_ref.h" #include "base/enums.h" #include "base/macros.h" #include "offsets.h" -#include "utils/array_ref.h" #include "utils/assembler.h" #include "utils/jni_macro_assembler.h" |