summaryrefslogtreecommitdiff
path: root/compiler
diff options
context:
space:
mode:
Diffstat (limited to 'compiler')
-rw-r--r--compiler/dex/verified_method.cc2
-rw-r--r--compiler/dex/verified_method.h2
-rw-r--r--compiler/dwarf/dwarf_test.cc4
-rw-r--r--compiler/image_writer.cc190
-rw-r--r--compiler/image_writer.h26
-rw-r--r--compiler/optimizing/bounds_check_elimination.cc598
-rw-r--r--compiler/optimizing/bounds_check_elimination_test.cc53
-rw-r--r--compiler/optimizing/nodes.cc75
-rw-r--r--compiler/optimizing/nodes.h37
9 files changed, 717 insertions, 270 deletions
diff --git a/compiler/dex/verified_method.cc b/compiler/dex/verified_method.cc
index ac7a4a7758..6d485986f6 100644
--- a/compiler/dex/verified_method.cc
+++ b/compiler/dex/verified_method.cc
@@ -98,7 +98,7 @@ bool VerifiedMethod::GenerateGcMap(verifier::MethodVerifier* method_verifier) {
}
size_t ref_bitmap_bytes = RoundUp(ref_bitmap_bits, kBitsPerByte) / kBitsPerByte;
// There are 2 bytes to encode the number of entries.
- if (num_entries >= 65536) {
+ if (num_entries > std::numeric_limits<uint16_t>::max()) {
LOG(WARNING) << "Cannot encode GC map for method with " << num_entries << " entries: "
<< PrettyMethod(method_verifier->GetMethodReference().dex_method_index,
*method_verifier->GetMethodReference().dex_file);
diff --git a/compiler/dex/verified_method.h b/compiler/dex/verified_method.h
index 242e3dfe6e..07f9a9bd9f 100644
--- a/compiler/dex/verified_method.h
+++ b/compiler/dex/verified_method.h
@@ -120,7 +120,7 @@ class VerifiedMethod {
DequickenMap dequicken_map_;
SafeCastSet safe_cast_set_;
- bool has_verification_failures_;
+ bool has_verification_failures_ = false;
// Copy of mapping generated by verifier of dex PCs of string init invocations
// to the set of other registers that the receiver has been copied into.
diff --git a/compiler/dwarf/dwarf_test.cc b/compiler/dwarf/dwarf_test.cc
index 4971f0ef10..4d423d007f 100644
--- a/compiler/dwarf/dwarf_test.cc
+++ b/compiler/dwarf/dwarf_test.cc
@@ -26,11 +26,11 @@
namespace art {
namespace dwarf {
-constexpr CFIFormat kCFIFormat = DW_DEBUG_FRAME_FORMAT;
-
// Run the tests only on host since we need objdump.
#ifndef HAVE_ANDROID_OS
+constexpr CFIFormat kCFIFormat = DW_DEBUG_FRAME_FORMAT;
+
TEST_F(DwarfTest, DebugFrame) {
const bool is64bit = false;
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index 32bde8e3b4..73e121f1cd 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -110,10 +110,6 @@ bool ImageWriter::PrepareImageAddressSpace() {
CheckNoDexObjects();
}
- if (!AllocMemory()) {
- return false;
- }
-
if (kIsDebugBuild) {
ScopedObjectAccess soa(Thread::Current());
CheckNonImageClassesRemoved();
@@ -123,6 +119,12 @@ bool ImageWriter::PrepareImageAddressSpace() {
CalculateNewObjectOffsets();
Thread::Current()->TransitionFromRunnableToSuspended(kNative);
+ // This needs to happen after CalculateNewObjectOffsets since it relies on intern_table_bytes_ and
+ // bin size sums being calculated.
+ if (!AllocMemory()) {
+ return false;
+ }
+
return true;
}
@@ -205,7 +207,7 @@ bool ImageWriter::Write(const std::string& image_filename,
}
// Write out the image bitmap at the page aligned start of the image end.
- const auto& bitmap_section = image_header->GetImageSection(ImageHeader::kSectionImageBitmap);
+ const ImageSection& bitmap_section = image_header->GetImageSection(ImageHeader::kSectionImageBitmap);
CHECK_ALIGNED(bitmap_section.Offset(), kPageSize);
if (!image_file->Write(reinterpret_cast<char*>(image_bitmap_->Begin()),
bitmap_section.Size(), bitmap_section.Offset())) {
@@ -222,26 +224,10 @@ bool ImageWriter::Write(const std::string& image_filename,
return true;
}
-void ImageWriter::SetImageOffset(mirror::Object* object,
- ImageWriter::BinSlot bin_slot,
- size_t offset) {
+void ImageWriter::SetImageOffset(mirror::Object* object, size_t offset) {
DCHECK(object != nullptr);
DCHECK_NE(offset, 0U);
- mirror::Object* obj = reinterpret_cast<mirror::Object*>(image_->Begin() + offset);
- DCHECK_ALIGNED(obj, kObjectAlignment);
- static size_t max_offset = 0;
- max_offset = std::max(max_offset, offset);
- image_bitmap_->Set(obj); // Mark the obj as mutated, since we will end up changing it.
- {
- // Remember the object-inside-of-the-image's hash code so we can restore it after the copy.
- auto hash_it = saved_hashes_map_.find(bin_slot);
- if (hash_it != saved_hashes_map_.end()) {
- std::pair<BinSlot, uint32_t> slot_hash = *hash_it;
- saved_hashes_.push_back(std::make_pair(obj, slot_hash.second));
- saved_hashes_map_.erase(hash_it);
- }
- }
// The object is already deflated from when we set the bin slot. Just overwrite the lock word.
object->SetLockWord(LockWord::FromForwardingAddress(offset), false);
DCHECK_EQ(object->GetLockWord(false).ReadBarrierState(), 0u);
@@ -262,7 +248,7 @@ void ImageWriter::AssignImageOffset(mirror::Object* object, ImageWriter::BinSlot
size_t new_offset = image_objects_offset_begin_ + previous_bin_sizes + bin_slot.GetIndex();
DCHECK_ALIGNED(new_offset, kObjectAlignment);
- SetImageOffset(object, bin_slot, new_offset);
+ SetImageOffset(object, new_offset);
DCHECK_LT(new_offset, image_end_);
}
@@ -302,14 +288,14 @@ void ImageWriter::SetImageBinSlot(mirror::Object* object, BinSlot bin_slot) {
// No hash, don't need to save it.
break;
case LockWord::kHashCode:
- saved_hashes_map_[bin_slot] = lw.GetHashCode();
+ DCHECK(saved_hashcode_map_.find(object) == saved_hashcode_map_.end());
+ saved_hashcode_map_.emplace(object, lw.GetHashCode());
break;
default:
LOG(FATAL) << "Unreachable.";
UNREACHABLE();
}
- object->SetLockWord(LockWord::FromForwardingAddress(static_cast<uint32_t>(bin_slot)),
- false);
+ object->SetLockWord(LockWord::FromForwardingAddress(bin_slot.Uint32Value()), false);
DCHECK_EQ(object->GetLockWord(false).ReadBarrierState(), 0u);
DCHECK(IsImageBinSlotAssigned(object));
}
@@ -487,11 +473,8 @@ void ImageWriter::AssignImageBinSlot(mirror::Object* object) {
++bin_slot_count_[bin];
- DCHECK_LT(GetBinSizeSum(), image_->Size());
-
// Grow the image closer to the end by the object we just assigned.
image_end_ += offset_delta;
- DCHECK_LT(image_end_, image_->Size());
}
bool ImageWriter::WillMethodBeDirty(ArtMethod* m) const {
@@ -535,10 +518,8 @@ ImageWriter::BinSlot ImageWriter::GetImageBinSlot(mirror::Object* object) const
}
bool ImageWriter::AllocMemory() {
- auto* runtime = Runtime::Current();
- const size_t heap_size = runtime->GetHeap()->GetTotalMemory();
- // Add linear alloc usage since we need to have room for the ArtFields.
- const size_t length = RoundUp(heap_size + runtime->GetLinearAlloc()->GetUsedMemory(), kPageSize);
+ const size_t length = RoundUp(image_objects_offset_begin_ + GetBinSizeSum() + intern_table_bytes_,
+ kPageSize);
std::string error_msg;
image_.reset(MemMap::MapAnonymous("image writer image", nullptr, length, PROT_READ | PROT_WRITE,
false, false, &error_msg));
@@ -547,9 +528,10 @@ bool ImageWriter::AllocMemory() {
return false;
}
- // Create the image bitmap.
- image_bitmap_.reset(gc::accounting::ContinuousSpaceBitmap::Create("image bitmap", image_->Begin(),
- RoundUp(length, kPageSize)));
+ // Create the image bitmap, only needs to cover mirror object section which is up to image_end_.
+ CHECK_LE(image_end_, length);
+ image_bitmap_.reset(gc::accounting::ContinuousSpaceBitmap::Create(
+ "image bitmap", image_->Begin(), RoundUp(image_end_, kPageSize)));
if (image_bitmap_.get() == nullptr) {
LOG(ERROR) << "Failed to allocate memory for image bitmap";
return false;
@@ -569,42 +551,6 @@ bool ImageWriter::ComputeLazyFieldsForClassesVisitor(Class* c, void* /*arg*/) {
return true;
}
-// Collect all the java.lang.String in the heap and put them in the output strings_ array.
-class StringCollector {
- public:
- StringCollector(Handle<mirror::ObjectArray<mirror::String>> strings, size_t index)
- : strings_(strings), index_(index) {
- }
- static void Callback(Object* obj, void* arg) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
- auto* collector = reinterpret_cast<StringCollector*>(arg);
- if (obj->GetClass()->IsStringClass()) {
- collector->strings_->SetWithoutChecks<false>(collector->index_++, obj->AsString());
- }
- }
- size_t GetIndex() const {
- return index_;
- }
-
- private:
- Handle<mirror::ObjectArray<mirror::String>> strings_;
- size_t index_;
-};
-
-// Compare strings based on length, used for sorting strings by length / reverse length.
-class LexicographicalStringComparator {
- public:
- bool operator()(const mirror::HeapReference<mirror::String>& lhs,
- const mirror::HeapReference<mirror::String>& rhs) const
- SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
- mirror::String* lhs_s = lhs.AsMirrorPtr();
- mirror::String* rhs_s = rhs.AsMirrorPtr();
- uint16_t* lhs_begin = lhs_s->GetValue();
- uint16_t* rhs_begin = rhs_s->GetValue();
- return std::lexicographical_compare(lhs_begin, lhs_begin + lhs_s->GetLength(),
- rhs_begin, rhs_begin + rhs_s->GetLength());
- }
-};
-
void ImageWriter::ComputeEagerResolvedStringsCallback(Object* obj, void* arg ATTRIBUTE_UNUSED) {
if (!obj->GetClass()->IsStringClass()) {
return;
@@ -769,7 +715,8 @@ void ImageWriter::CalculateObjectBinSlots(Object* obj) {
DCHECK_EQ(obj, obj->AsString()->Intern());
return;
}
- mirror::String* const interned = obj->AsString()->Intern();
+ mirror::String* const interned = Runtime::Current()->GetInternTable()->InternStrong(
+ obj->AsString()->Intern());
if (obj != interned) {
if (!IsImageBinSlotAssigned(interned)) {
// interned obj is after us, allocate its location early
@@ -965,7 +912,6 @@ void ImageWriter::CalculateNewObjectOffsets() {
// know where image_roots is going to end up
image_end_ += RoundUp(sizeof(ImageHeader), kObjectAlignment); // 64-bit-alignment
- DCHECK_LT(image_end_, image_->Size());
image_objects_offset_begin_ = image_end_;
// Prepare bin slots for dex cache arrays.
PrepareDexCacheArraySlots();
@@ -997,7 +943,6 @@ void ImageWriter::CalculateNewObjectOffsets() {
// Transform each object's bin slot into an offset which will be used to do the final copy.
heap->VisitObjects(UnbinObjectsIntoOffsetCallback, this);
- DCHECK(saved_hashes_map_.empty()); // All binslot hashes should've been put into vector by now.
DCHECK_EQ(image_end_, GetBinSizeSum(kBinMirrorCount) + image_objects_offset_begin_);
@@ -1010,6 +955,11 @@ void ImageWriter::CalculateNewObjectOffsets() {
bin_slot_previous_sizes_[native_reloc.bin_type];
}
+ // Calculate how big the intern table will be after being serialized.
+ auto* const intern_table = Runtime::Current()->GetInternTable();
+ CHECK_EQ(intern_table->WeakSize(), 0u) << " should have strong interned all the strings";
+ intern_table_bytes_ = intern_table->WriteToMemory(nullptr);
+
// Note that image_end_ is left at end of used mirror object section.
}
@@ -1039,6 +989,10 @@ void ImageWriter::CreateHeader(size_t oat_loaded_size, size_t oat_data_offset) {
CHECK_EQ(image_objects_offset_begin_ + bin_slot_previous_sizes_[kBinArtMethodClean],
methods_section->Offset());
cur_pos = methods_section->End();
+ // Calculate the size of the interned strings.
+ auto* interned_strings_section = &sections[ImageHeader::kSectionInternedStrings];
+ *interned_strings_section = ImageSection(cur_pos, intern_table_bytes_);
+ cur_pos = interned_strings_section->End();
// Finally bitmap section.
const size_t bitmap_bytes = image_bitmap_->Size();
auto* bitmap_section = &sections[ImageHeader::kSectionImageBitmap];
@@ -1046,16 +1000,19 @@ void ImageWriter::CreateHeader(size_t oat_loaded_size, size_t oat_data_offset) {
cur_pos = bitmap_section->End();
if (kIsDebugBuild) {
size_t idx = 0;
- for (auto& section : sections) {
+ for (const ImageSection& section : sections) {
LOG(INFO) << static_cast<ImageHeader::ImageSections>(idx) << " " << section;
++idx;
}
LOG(INFO) << "Methods: clean=" << clean_methods_ << " dirty=" << dirty_methods_;
}
+ const size_t image_end = static_cast<uint32_t>(interned_strings_section->End());
+ CHECK_EQ(AlignUp(image_begin_ + image_end, kPageSize), oat_file_begin) <<
+ "Oat file should be right after the image.";
// Create the header.
new (image_->Begin()) ImageHeader(
- PointerToLowMemUInt32(image_begin_), static_cast<uint32_t>(methods_section->End()), sections,
- image_roots_address_, oat_file_->GetOatHeader().GetChecksum(),
+ PointerToLowMemUInt32(image_begin_), image_end,
+ sections, image_roots_address_, oat_file_->GetOatHeader().GetChecksum(),
PointerToLowMemUInt32(oat_file_begin), PointerToLowMemUInt32(oat_data_begin_),
PointerToLowMemUInt32(oat_data_end), PointerToLowMemUInt32(oat_file_end), target_ptr_size_,
compile_pic_);
@@ -1068,6 +1025,37 @@ ArtMethod* ImageWriter::GetImageMethodAddress(ArtMethod* method) {
return reinterpret_cast<ArtMethod*>(image_begin_ + it->second.offset);
}
+class FixupRootVisitor : public RootVisitor {
+ public:
+ explicit FixupRootVisitor(ImageWriter* image_writer) : image_writer_(image_writer) {
+ }
+
+ void VisitRoots(mirror::Object*** roots, size_t count, const RootInfo& info ATTRIBUTE_UNUSED)
+ OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+ for (size_t i = 0; i < count; ++i) {
+ *roots[i] = ImageAddress(*roots[i]);
+ }
+ }
+
+ void VisitRoots(mirror::CompressedReference<mirror::Object>** roots, size_t count,
+ const RootInfo& info ATTRIBUTE_UNUSED)
+ OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+ for (size_t i = 0; i < count; ++i) {
+ roots[i]->Assign(ImageAddress(roots[i]->AsMirrorPtr()));
+ }
+ }
+
+ private:
+ ImageWriter* const image_writer_;
+
+ mirror::Object* ImageAddress(mirror::Object* obj) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+ const size_t offset = image_writer_->GetImageOffset(obj);
+ auto* const dest = reinterpret_cast<Object*>(image_writer_->image_begin_ + offset);
+ VLOG(compiler) << "Update root from " << obj << " to " << dest;
+ return dest;
+ }
+};
+
void ImageWriter::CopyAndFixupNativeData() {
// Copy ArtFields and methods to their locations and update the array for convenience.
for (auto& pair : native_object_reloc_) {
@@ -1088,7 +1076,7 @@ void ImageWriter::CopyAndFixupNativeData() {
}
// Fixup the image method roots.
auto* image_header = reinterpret_cast<ImageHeader*>(image_->Begin());
- const auto& methods_section = image_header->GetMethodsSection();
+ const ImageSection& methods_section = image_header->GetMethodsSection();
for (size_t i = 0; i < ImageHeader::kImageMethodsCount; ++i) {
auto* m = image_methods_[i];
CHECK(m != nullptr);
@@ -1101,18 +1089,35 @@ void ImageWriter::CopyAndFixupNativeData() {
auto* dest = reinterpret_cast<ArtMethod*>(image_begin_ + it->second.offset);
image_header->SetImageMethod(static_cast<ImageHeader::ImageMethod>(i), dest);
}
+ // Write the intern table into the image.
+ const ImageSection& intern_table_section = image_header->GetImageSection(
+ ImageHeader::kSectionInternedStrings);
+ InternTable* const intern_table = Runtime::Current()->GetInternTable();
+ uint8_t* const memory_ptr = image_->Begin() + intern_table_section.Offset();
+ const size_t intern_table_bytes = intern_table->WriteToMemory(memory_ptr);
+ // Fixup the pointers in the newly written intern table to contain image addresses.
+ InternTable temp_table;
+ // Note that we require that ReadFromMemory does not make an internal copy of the elements so that
+ // the VisitRoots() will update the memory directly rather than the copies.
+ // This also relies on visit roots not doing any verification which could fail after we update
+ // the roots to be the image addresses.
+ temp_table.ReadFromMemory(memory_ptr);
+ CHECK_EQ(temp_table.Size(), intern_table->Size());
+ FixupRootVisitor visitor(this);
+ temp_table.VisitRoots(&visitor, kVisitRootFlagAllRoots);
+ CHECK_EQ(intern_table_bytes, intern_table_bytes_);
}
void ImageWriter::CopyAndFixupObjects() {
gc::Heap* heap = Runtime::Current()->GetHeap();
heap->VisitObjects(CopyAndFixupObjectsCallback, this);
// Fix up the object previously had hash codes.
- for (const std::pair<mirror::Object*, uint32_t>& hash_pair : saved_hashes_) {
+ for (const auto& hash_pair : saved_hashcode_map_) {
Object* obj = hash_pair.first;
DCHECK_EQ(obj->GetLockWord<kVerifyNone>(false).ReadBarrierState(), 0U);
obj->SetLockWord<kVerifyNone>(LockWord::FromHashCode(hash_pair.second, 0U), false);
}
- saved_hashes_.clear();
+ saved_hashcode_map_.clear();
}
void ImageWriter::CopyAndFixupObjectsCallback(Object* obj, void* arg) {
@@ -1155,18 +1160,22 @@ void ImageWriter::FixupPointerArray(mirror::Object* dst, mirror::PointerArray* a
}
void ImageWriter::CopyAndFixupObject(Object* obj) {
- // see GetLocalAddress for similar computation
size_t offset = GetImageOffset(obj);
auto* dst = reinterpret_cast<Object*>(image_->Begin() + offset);
- const uint8_t* src = reinterpret_cast<const uint8_t*>(obj);
+ DCHECK_LT(offset, image_end_);
+ const auto* src = reinterpret_cast<const uint8_t*>(obj);
+
+ image_bitmap_->Set(dst); // Mark the obj as live.
- size_t n = obj->SizeOf();
+ const size_t n = obj->SizeOf();
DCHECK_LE(offset + n, image_->Size());
memcpy(dst, src, n);
// Write in a hash code of objects which have inflated monitors or a hash code in their monitor
// word.
- dst->SetLockWord(LockWord::Default(), false);
+ const auto it = saved_hashcode_map_.find(obj);
+ dst->SetLockWord(it != saved_hashcode_map_.end() ?
+ LockWord::FromHashCode(it->second, 0u) : LockWord::Default(), false);
FixupObject(obj, dst);
}
@@ -1176,7 +1185,7 @@ class FixupVisitor {
FixupVisitor(ImageWriter* image_writer, Object* copy) : image_writer_(image_writer), copy_(copy) {
}
- void operator()(Object* obj, MemberOffset offset, bool /*is_static*/) const
+ void operator()(Object* obj, MemberOffset offset, bool is_static ATTRIBUTE_UNUSED) const
EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_) {
Object* ref = obj->GetFieldObject<Object, kVerifyNone>(offset);
// Use SetFieldObjectWithoutWriteBarrier to avoid card marking since we are writing to the
@@ -1186,7 +1195,7 @@ class FixupVisitor {
}
// java.lang.ref.Reference visitor.
- void operator()(mirror::Class* /*klass*/, mirror::Reference* ref) const
+ void operator()(mirror::Class* klass ATTRIBUTE_UNUSED, mirror::Reference* ref) const
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
copy_->SetFieldObjectWithoutWriteBarrier<false, true, kVerifyNone>(
@@ -1490,4 +1499,11 @@ uint32_t ImageWriter::BinSlot::GetIndex() const {
return lockword_ & ~kBinMask;
}
+uint8_t* ImageWriter::GetOatFileBegin() const {
+ DCHECK_GT(intern_table_bytes_, 0u);
+ return image_begin_ + RoundUp(
+ image_end_ + bin_slot_sizes_[kBinArtField] + bin_slot_sizes_[kBinArtMethodDirty] +
+ bin_slot_sizes_[kBinArtMethodClean] + intern_table_bytes_, kPageSize);
+}
+
} // namespace art
diff --git a/compiler/image_writer.h b/compiler/image_writer.h
index a35d6ad9c9..9d45ce2bd4 100644
--- a/compiler/image_writer.h
+++ b/compiler/image_writer.h
@@ -54,7 +54,7 @@ class ImageWriter FINAL {
quick_to_interpreter_bridge_offset_(0), compile_pic_(compile_pic),
target_ptr_size_(InstructionSetPointerSize(compiler_driver_.GetInstructionSet())),
bin_slot_sizes_(), bin_slot_previous_sizes_(), bin_slot_count_(),
- dirty_methods_(0u), clean_methods_(0u) {
+ intern_table_bytes_(0u), dirty_methods_(0u), clean_methods_(0u) {
CHECK_NE(image_begin, 0U);
std::fill(image_methods_, image_methods_ + arraysize(image_methods_), nullptr);
}
@@ -84,11 +84,7 @@ class ImageWriter FINAL {
image_begin_ + RoundUp(sizeof(ImageHeader), kObjectAlignment) + it->second + offset);
}
- uint8_t* GetOatFileBegin() const {
- return image_begin_ + RoundUp(
- image_end_ + bin_slot_sizes_[kBinArtField] + bin_slot_sizes_[kBinArtMethodDirty] +
- bin_slot_sizes_[kBinArtMethodClean], kPageSize);
- }
+ uint8_t* GetOatFileBegin() const;
bool Write(const std::string& image_filename, const std::string& oat_filename,
const std::string& oat_location)
@@ -158,7 +154,7 @@ class ImageWriter FINAL {
// The offset in bytes from the beginning of the bin. Aligned to object size.
uint32_t GetIndex() const;
// Pack into a single uint32_t, for storing into a lock word.
- explicit operator uint32_t() const { return lockword_; }
+ uint32_t Uint32Value() const { return lockword_; }
// Comparison operator for map support
bool operator<(const BinSlot& other) const { return lockword_ < other.lockword_; }
@@ -170,7 +166,7 @@ class ImageWriter FINAL {
// We use the lock word to store the offset of the object in the image.
void AssignImageOffset(mirror::Object* object, BinSlot bin_slot)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
- void SetImageOffset(mirror::Object* object, BinSlot bin_slot, size_t offset)
+ void SetImageOffset(mirror::Object* object, size_t offset)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
bool IsImageOffsetAssigned(mirror::Object* object) const
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
@@ -330,11 +326,9 @@ class ImageWriter FINAL {
// The start offsets of the dex cache arrays.
SafeMap<const DexFile*, size_t> dex_cache_array_starts_;
- // Saved hashes (objects are inside of the image so that they don't move).
- std::vector<std::pair<mirror::Object*, uint32_t>> saved_hashes_;
-
- // Saved hashes (objects are bin slots to inside of the image, not yet allocated an address).
- std::map<BinSlot, uint32_t> saved_hashes_map_;
+ // Saved hash codes. We use these to restore lockwords which were temporarily used to have
+ // forwarding addresses as well as copying over hash codes.
+ std::unordered_map<mirror::Object*, uint32_t> saved_hashcode_map_;
// Beginning target oat address for the pointers from the output image to its oat file.
const uint8_t* oat_data_begin_;
@@ -360,6 +354,9 @@ class ImageWriter FINAL {
size_t bin_slot_previous_sizes_[kBinSize]; // Number of bytes in previous bins.
size_t bin_slot_count_[kBinSize]; // Number of objects in a bin
+ // Cached size of the intern table for when we allocate memory.
+ size_t intern_table_bytes_;
+
// ArtField, ArtMethod relocating map. These are allocated as array of structs but we want to
// have one entry per art field for convenience. ArtFields are placed right after the end of the
// image objects (aka sum of bin_slot_sizes_). ArtMethods are placed right after the ArtFields.
@@ -376,8 +373,9 @@ class ImageWriter FINAL {
uint64_t dirty_methods_;
uint64_t clean_methods_;
- friend class FixupVisitor;
friend class FixupClassVisitor;
+ friend class FixupRootVisitor;
+ friend class FixupVisitor;
DISALLOW_COPY_AND_ASSIGN(ImageWriter);
};
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index b2b54965b5..9d5e3fdca1 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -126,11 +126,14 @@ class ValueBound : public ValueObject {
return instruction_ == bound.instruction_ && constant_ == bound.constant_;
}
- static HInstruction* FromArrayLengthToNewArrayIfPossible(HInstruction* instruction) {
- // Null check on the NewArray should have been eliminated by instruction
- // simplifier already.
- if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) {
- return instruction->InputAt(0)->AsNewArray();
+ static HInstruction* FromArrayLengthToArray(HInstruction* instruction) {
+ DCHECK(instruction->IsArrayLength() || instruction->IsNewArray());
+ if (instruction->IsArrayLength()) {
+ HInstruction* input = instruction->InputAt(0);
+ if (input->IsNullCheck()) {
+ input = input->AsNullCheck()->InputAt(0);
+ }
+ return input;
}
return instruction;
}
@@ -146,8 +149,9 @@ class ValueBound : public ValueObject {
// Some bounds are created with HNewArray* as the instruction instead
// of HArrayLength*. They are treated the same.
- instruction1 = FromArrayLengthToNewArrayIfPossible(instruction1);
- instruction2 = FromArrayLengthToNewArrayIfPossible(instruction2);
+ // HArrayLength with the same array input are considered equal also.
+ instruction1 = FromArrayLengthToArray(instruction1);
+ instruction2 = FromArrayLengthToArray(instruction2);
return instruction1 == instruction2;
}
@@ -271,7 +275,7 @@ class ArrayAccessInsideLoopFinder : public ValueObject {
// Loop header of loop_info. Exiting loop is normal.
return false;
}
- const GrowableArray<HBasicBlock*> successors = block->GetSuccessors();
+ const GrowableArray<HBasicBlock*>& successors = block->GetSuccessors();
for (size_t i = 0; i < successors.Size(); i++) {
if (!loop_info->Contains(*successors.Get(i))) {
// One of the successors exits the loop.
@@ -293,8 +297,14 @@ class ArrayAccessInsideLoopFinder : public ValueObject {
void Run() {
HLoopInformation* loop_info = induction_variable_->GetBlock()->GetLoopInformation();
- for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
- HBasicBlock* block = it_loop.Current();
+ HBlocksInLoopReversePostOrderIterator it_loop(*loop_info);
+ HBasicBlock* block = it_loop.Current();
+ DCHECK(block == induction_variable_->GetBlock());
+ // Skip loop header. Since narrowed value range of a MonotonicValueRange only
+ // applies to the loop body (after the test at the end of the loop header).
+ it_loop.Advance();
+ for (; !it_loop.Done(); it_loop.Advance()) {
+ block = it_loop.Current();
DCHECK(block->IsInLoop());
if (!DominatesAllBackEdges(block, loop_info)) {
// In order not to trigger deoptimization unnecessarily, make sure
@@ -308,30 +318,35 @@ class ArrayAccessInsideLoopFinder : public ValueObject {
// that the loop will loop through the full monotonic value range from
// initial_ to end_. So adding deoptimization might be too aggressive and can
// trigger deoptimization unnecessarily even if the loop won't actually throw
- // AIOOBE. Otherwise, the loop induction variable is going to cover the full
- // monotonic value range from initial_ to end_, and deoptimizations are added
- // iff the loop will throw AIOOBE.
+ // AIOOBE.
found_array_length_ = nullptr;
return;
}
for (HInstruction* instruction = block->GetFirstInstruction();
instruction != nullptr;
instruction = instruction->GetNext()) {
- if (!instruction->IsArrayGet() && !instruction->IsArraySet()) {
+ if (!instruction->IsBoundsCheck()) {
continue;
}
- HInstruction* index = instruction->InputAt(1);
- if (!index->IsBoundsCheck()) {
+
+ HInstruction* length_value = instruction->InputAt(1);
+ if (length_value->IsIntConstant()) {
+ // TODO: may optimize for constant case.
continue;
}
- HArrayLength* array_length = index->InputAt(1)->AsArrayLength();
- if (array_length == nullptr) {
- DCHECK(index->InputAt(1)->IsIntConstant());
- // TODO: may optimize for constant case.
+ DCHECK(!length_value->IsPhi());
+ if (length_value->IsPhi()) {
+ // Outer loop shouldn't collect bounds checks inside inner
+ // loop because the inner loop body doen't dominate
+ // outer loop's back edges. However just to be on the safe side,
+ // if there are any such cases, we just skip over them.
continue;
}
+ DCHECK(length_value->IsArrayLength());
+ HArrayLength* array_length = length_value->AsArrayLength();
+
HInstruction* array = array_length->InputAt(0);
if (array->IsNullCheck()) {
array = array->AsNullCheck()->InputAt(0);
@@ -347,7 +362,7 @@ class ArrayAccessInsideLoopFinder : public ValueObject {
continue;
}
- index = index->AsBoundsCheck()->InputAt(0);
+ HInstruction* index = instruction->AsBoundsCheck()->InputAt(0);
HInstruction* left = index;
int32_t right = 0;
if (left == induction_variable_ ||
@@ -375,7 +390,7 @@ class ArrayAccessInsideLoopFinder : public ValueObject {
// The instruction that corresponds to a MonotonicValueRange.
HInstruction* induction_variable_;
- // The array length of the array that's accessed inside the loop.
+ // The array length of the array that's accessed inside the loop body.
HArrayLength* found_array_length_;
// The lowest and highest constant offsets relative to induction variable
@@ -411,6 +426,8 @@ class ValueRange : public ArenaObject<kArenaAllocMisc> {
ValueBound GetLower() const { return lower_; }
ValueBound GetUpper() const { return upper_; }
+ bool IsConstantValueRange() { return lower_.IsConstant() && upper_.IsConstant(); }
+
// If it's certain that this value range fits in other_range.
virtual bool FitsIn(ValueRange* other_range) const {
if (other_range == nullptr) {
@@ -495,13 +512,30 @@ class MonotonicValueRange : public ValueRange {
ValueBound GetBound() const { return bound_; }
void SetEnd(HInstruction* end) { end_ = end; }
void SetInclusive(bool inclusive) { inclusive_ = inclusive; }
- HBasicBlock* GetLoopHead() const {
+ HBasicBlock* GetLoopHeader() const {
DCHECK(induction_variable_->GetBlock()->IsLoopHeader());
return induction_variable_->GetBlock();
}
MonotonicValueRange* AsMonotonicValueRange() OVERRIDE { return this; }
+ HBasicBlock* GetLoopHeaderSuccesorInLoop() {
+ HBasicBlock* header = GetLoopHeader();
+ HInstruction* instruction = header->GetLastInstruction();
+ DCHECK(instruction->IsIf());
+ HIf* h_if = instruction->AsIf();
+ HLoopInformation* loop_info = header->GetLoopInformation();
+ bool true_successor_in_loop = loop_info->Contains(*h_if->IfTrueSuccessor());
+ bool false_successor_in_loop = loop_info->Contains(*h_if->IfFalseSuccessor());
+
+ // Just in case it's some strange loop structure.
+ if (true_successor_in_loop && false_successor_in_loop) {
+ return nullptr;
+ }
+ DCHECK(true_successor_in_loop || false_successor_in_loop);
+ return false_successor_in_loop ? h_if->IfFalseSuccessor() : h_if->IfTrueSuccessor();
+ }
+
// If it's certain that this value range fits in other_range.
bool FitsIn(ValueRange* other_range) const OVERRIDE {
if (other_range == nullptr) {
@@ -593,12 +627,114 @@ class MonotonicValueRange : public ValueRange {
}
}
+ // Try to add HDeoptimize's in the loop pre-header first to narrow this range.
+ // For example, this loop:
+ //
+ // for (int i = start; i < end; i++) {
+ // array[i - 1] = array[i] + array[i + 1];
+ // }
+ //
+ // will be transformed to:
+ //
+ // int array_length_in_loop_body_if_needed;
+ // if (start >= end) {
+ // array_length_in_loop_body_if_needed = 0;
+ // } else {
+ // if (start < 1) deoptimize();
+ // if (array == null) deoptimize();
+ // array_length = array.length;
+ // if (end > array_length - 1) deoptimize;
+ // array_length_in_loop_body_if_needed = array_length;
+ // }
+ // for (int i = start; i < end; i++) {
+ // // No more null check and bounds check.
+ // // array.length value is replaced with array_length_in_loop_body_if_needed
+ // // in the loop body.
+ // array[i - 1] = array[i] + array[i + 1];
+ // }
+ //
+ // We basically first go through the loop body and find those array accesses whose
+ // index is at a constant offset from the induction variable ('i' in the above example),
+ // and update offset_low and offset_high along the way. We then add the following
+ // deoptimizations in the loop pre-header (suppose end is not inclusive).
+ // if (start < -offset_low) deoptimize();
+ // if (end >= array.length - offset_high) deoptimize();
+ // It might be necessary to first hoist array.length (and the null check on it) out of
+ // the loop with another deoptimization.
+ //
+ // In order not to trigger deoptimization unnecessarily, we want to make a strong
+ // guarantee that no deoptimization is triggered if the loop body itself doesn't
+ // throw AIOOBE. (It's the same as saying if deoptimization is triggered, the loop
+ // body must throw AIOOBE).
+ // This is achieved by the following:
+ // 1) We only process loops that iterate through the full monotonic range from
+ // initial_ to end_. We do the following checks to make sure that's the case:
+ // a) The loop doesn't have early exit (via break, return, etc.)
+ // b) The increment_ is 1/-1. An increment of 2, for example, may skip end_.
+ // 2) We only collect array accesses of blocks in the loop body that dominate
+ // all loop back edges, these array accesses are guaranteed to happen
+ // at each loop iteration.
+ // With 1) and 2), if the loop body doesn't throw AIOOBE, collected array accesses
+ // when the induction variable is at initial_ and end_ must be in a legal range.
+ // Since the added deoptimizations are basically checking the induction variable
+ // at initial_ and end_ values, no deoptimization will be triggered either.
+ //
+ // A special case is the loop body isn't entered at all. In that case, we may still
+ // add deoptimization due to the analysis described above. In order not to trigger
+ // deoptimization, we do a test between initial_ and end_ first and skip over
+ // the added deoptimization.
+ ValueRange* NarrowWithDeoptimization() {
+ if (increment_ != 1 && increment_ != -1) {
+ // In order not to trigger deoptimization unnecessarily, we want to
+ // make sure the loop iterates through the full range from initial_ to
+ // end_ so that boundaries are covered by the loop. An increment of 2,
+ // for example, may skip end_.
+ return this;
+ }
+
+ if (end_ == nullptr) {
+ // No full info to add deoptimization.
+ return this;
+ }
+
+ HBasicBlock* header = induction_variable_->GetBlock();
+ DCHECK(header->IsLoopHeader());
+ HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
+ if (!initial_->GetBlock()->Dominates(pre_header) ||
+ !end_->GetBlock()->Dominates(pre_header)) {
+ // Can't add a check in loop pre-header if the value isn't available there.
+ return this;
+ }
+
+ ArrayAccessInsideLoopFinder finder(induction_variable_);
+
+ if (!finder.HasFoundArrayLength()) {
+ // No array access was found inside the loop that can benefit
+ // from deoptimization.
+ return this;
+ }
+
+ if (!AddDeoptimization(finder)) {
+ return this;
+ }
+
+ // After added deoptimizations, induction variable fits in
+ // [-offset_low, array.length-1-offset_high], adjusted with collected offsets.
+ ValueBound lower = ValueBound(0, -finder.GetOffsetLow());
+ ValueBound upper = ValueBound(finder.GetFoundArrayLength(), -1 - finder.GetOffsetHigh());
+ // We've narrowed the range after added deoptimizations.
+ return new (GetAllocator()) ValueRange(GetAllocator(), lower, upper);
+ }
+
// Returns true if adding a (constant >= value) check for deoptimization
// is allowed and will benefit compiled code.
- bool CanAddDeoptimizationConstant(HInstruction* value,
- int32_t constant,
- bool* is_proven) {
+ bool CanAddDeoptimizationConstant(HInstruction* value, int32_t constant, bool* is_proven) {
*is_proven = false;
+ HBasicBlock* header = induction_variable_->GetBlock();
+ DCHECK(header->IsLoopHeader());
+ HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
+ DCHECK(value->GetBlock()->Dominates(pre_header));
+
// See if we can prove the relationship first.
if (value->IsIntConstant()) {
if (value->AsIntConstant()->GetValue() >= constant) {
@@ -615,22 +751,118 @@ class MonotonicValueRange : public ValueRange {
return true;
}
+ // Try to filter out cases that the loop entry test will never be true.
+ bool LoopEntryTestUseful() {
+ if (initial_->IsIntConstant() && end_->IsIntConstant()) {
+ int32_t initial_val = initial_->AsIntConstant()->GetValue();
+ int32_t end_val = end_->AsIntConstant()->GetValue();
+ if (increment_ == 1) {
+ if (inclusive_) {
+ return initial_val > end_val;
+ } else {
+ return initial_val >= end_val;
+ }
+ } else {
+ DCHECK_EQ(increment_, -1);
+ if (inclusive_) {
+ return initial_val < end_val;
+ } else {
+ return initial_val <= end_val;
+ }
+ }
+ }
+ return true;
+ }
+
+ // Returns the block for adding deoptimization.
+ HBasicBlock* TransformLoopForDeoptimizationIfNeeded() {
+ HBasicBlock* header = induction_variable_->GetBlock();
+ DCHECK(header->IsLoopHeader());
+ HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
+ // Deoptimization is only added when both initial_ and end_ are defined
+ // before the loop.
+ DCHECK(initial_->GetBlock()->Dominates(pre_header));
+ DCHECK(end_->GetBlock()->Dominates(pre_header));
+
+ // If it can be proven the loop body is definitely entered (unless exception
+ // is thrown in the loop header for which triggering deoptimization is fine),
+ // there is no need for tranforming the loop. In that case, deoptimization
+ // will just be added in the loop pre-header.
+ if (!LoopEntryTestUseful()) {
+ return pre_header;
+ }
+
+ HGraph* graph = header->GetGraph();
+ graph->TransformLoopHeaderForBCE(header);
+ HBasicBlock* new_pre_header = header->GetDominator();
+ DCHECK(new_pre_header == header->GetLoopInformation()->GetPreHeader());
+ HBasicBlock* if_block = new_pre_header->GetDominator();
+ HBasicBlock* dummy_block = if_block->GetSuccessors().Get(0); // True successor.
+ HBasicBlock* deopt_block = if_block->GetSuccessors().Get(1); // False successor.
+
+ dummy_block->AddInstruction(new (graph->GetArena()) HGoto());
+ deopt_block->AddInstruction(new (graph->GetArena()) HGoto());
+ new_pre_header->AddInstruction(new (graph->GetArena()) HGoto());
+ return deopt_block;
+ }
+
+ // Adds a test between initial_ and end_ to see if the loop body is entered.
+ // If the loop body isn't entered at all, it jumps to the loop pre-header (after
+ // transformation) to avoid any deoptimization.
+ void AddLoopBodyEntryTest() {
+ HBasicBlock* header = induction_variable_->GetBlock();
+ DCHECK(header->IsLoopHeader());
+ HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
+ HBasicBlock* if_block = pre_header->GetDominator();
+ HGraph* graph = header->GetGraph();
+
+ HCondition* cond;
+ if (increment_ == 1) {
+ if (inclusive_) {
+ cond = new (graph->GetArena()) HGreaterThan(initial_, end_);
+ } else {
+ cond = new (graph->GetArena()) HGreaterThanOrEqual(initial_, end_);
+ }
+ } else {
+ DCHECK_EQ(increment_, -1);
+ if (inclusive_) {
+ cond = new (graph->GetArena()) HLessThan(initial_, end_);
+ } else {
+ cond = new (graph->GetArena()) HLessThanOrEqual(initial_, end_);
+ }
+ }
+ HIf* h_if = new (graph->GetArena()) HIf(cond);
+ if_block->AddInstruction(cond);
+ if_block->AddInstruction(h_if);
+ }
+
// Adds a check that (value >= constant), and HDeoptimize otherwise.
void AddDeoptimizationConstant(HInstruction* value,
- int32_t constant) {
- HBasicBlock* block = induction_variable_->GetBlock();
- DCHECK(block->IsLoopHeader());
- HGraph* graph = block->GetGraph();
- HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
- HSuspendCheck* suspend_check = block->GetLoopInformation()->GetSuspendCheck();
+ int32_t constant,
+ HBasicBlock* deopt_block,
+ bool loop_entry_test_block_added) {
+ HBasicBlock* header = induction_variable_->GetBlock();
+ DCHECK(header->IsLoopHeader());
+ HBasicBlock* pre_header = header->GetDominator();
+ if (loop_entry_test_block_added) {
+ DCHECK(deopt_block->GetSuccessors().Get(0) == pre_header);
+ } else {
+ DCHECK(deopt_block == pre_header);
+ }
+ HGraph* graph = header->GetGraph();
+ HSuspendCheck* suspend_check = header->GetLoopInformation()->GetSuspendCheck();
+ if (loop_entry_test_block_added) {
+ DCHECK_EQ(deopt_block, header->GetDominator()->GetDominator()->GetSuccessors().Get(1));
+ }
+
HIntConstant* const_instr = graph->GetIntConstant(constant);
HCondition* cond = new (graph->GetArena()) HLessThan(value, const_instr);
HDeoptimize* deoptimize = new (graph->GetArena())
HDeoptimize(cond, suspend_check->GetDexPc());
- pre_header->InsertInstructionBefore(cond, pre_header->GetLastInstruction());
- pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction());
+ deopt_block->InsertInstructionBefore(cond, deopt_block->GetLastInstruction());
+ deopt_block->InsertInstructionBefore(deoptimize, deopt_block->GetLastInstruction());
deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
- suspend_check->GetEnvironment(), block);
+ suspend_check->GetEnvironment(), header);
}
// Returns true if adding a (value <= array_length + offset) check for deoptimization
@@ -640,6 +872,26 @@ class MonotonicValueRange : public ValueRange {
int32_t offset,
bool* is_proven) {
*is_proven = false;
+ HBasicBlock* header = induction_variable_->GetBlock();
+ DCHECK(header->IsLoopHeader());
+ HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
+ DCHECK(value->GetBlock()->Dominates(pre_header));
+
+ if (array_length->GetBlock() == header) {
+ // array_length_in_loop_body_if_needed only has correct value when the loop
+ // body is entered. We bail out in this case. Usually array_length defined
+ // in the loop header is already hoisted by licm.
+ return false;
+ } else {
+ // array_length is defined either before the loop header already, or in
+ // the loop body since it's used in the loop body. If it's defined in the loop body,
+ // a phi array_length_in_loop_body_if_needed is used to replace it. In that case,
+ // all the uses of array_length must be dominated by its definition in the loop
+ // body. array_length_in_loop_body_if_needed is guaranteed to be the same as
+ // array_length once the loop body is entered so all the uses of the phi will
+ // use the correct value.
+ }
+
if (offset > 0) {
// There might be overflow issue.
// TODO: handle this, possibly with some distance relationship between
@@ -667,56 +919,99 @@ class MonotonicValueRange : public ValueRange {
// Adds a check that (value <= array_length + offset), and HDeoptimize otherwise.
void AddDeoptimizationArrayLength(HInstruction* value,
HArrayLength* array_length,
- int32_t offset) {
- HBasicBlock* block = induction_variable_->GetBlock();
- DCHECK(block->IsLoopHeader());
- HGraph* graph = block->GetGraph();
- HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
- HSuspendCheck* suspend_check = block->GetLoopInformation()->GetSuspendCheck();
+ int32_t offset,
+ HBasicBlock* deopt_block,
+ bool loop_entry_test_block_added) {
+ HBasicBlock* header = induction_variable_->GetBlock();
+ DCHECK(header->IsLoopHeader());
+ HBasicBlock* pre_header = header->GetDominator();
+ if (loop_entry_test_block_added) {
+ DCHECK(deopt_block->GetSuccessors().Get(0) == pre_header);
+ } else {
+ DCHECK(deopt_block == pre_header);
+ }
+ HGraph* graph = header->GetGraph();
+ HSuspendCheck* suspend_check = header->GetLoopInformation()->GetSuspendCheck();
// We may need to hoist null-check and array_length out of loop first.
- if (!array_length->GetBlock()->Dominates(pre_header)) {
+ if (!array_length->GetBlock()->Dominates(deopt_block)) {
+ // array_length must be defined in the loop body.
+ DCHECK(header->GetLoopInformation()->Contains(*array_length->GetBlock()));
+ DCHECK(array_length->GetBlock() != header);
+
HInstruction* array = array_length->InputAt(0);
HNullCheck* null_check = array->AsNullCheck();
if (null_check != nullptr) {
array = null_check->InputAt(0);
}
- // We've already made sure array is defined before the loop when collecting
+ // We've already made sure the array is defined before the loop when collecting
// array accesses for the loop.
- DCHECK(array->GetBlock()->Dominates(pre_header));
- if (null_check != nullptr && !null_check->GetBlock()->Dominates(pre_header)) {
+ DCHECK(array->GetBlock()->Dominates(deopt_block));
+ if (null_check != nullptr && !null_check->GetBlock()->Dominates(deopt_block)) {
// Hoist null check out of loop with a deoptimization.
HNullConstant* null_constant = graph->GetNullConstant();
HCondition* null_check_cond = new (graph->GetArena()) HEqual(array, null_constant);
// TODO: for one dex_pc, share the same deoptimization slow path.
HDeoptimize* null_check_deoptimize = new (graph->GetArena())
HDeoptimize(null_check_cond, suspend_check->GetDexPc());
- pre_header->InsertInstructionBefore(null_check_cond, pre_header->GetLastInstruction());
- pre_header->InsertInstructionBefore(
- null_check_deoptimize, pre_header->GetLastInstruction());
+ deopt_block->InsertInstructionBefore(
+ null_check_cond, deopt_block->GetLastInstruction());
+ deopt_block->InsertInstructionBefore(
+ null_check_deoptimize, deopt_block->GetLastInstruction());
// Eliminate null check in the loop.
null_check->ReplaceWith(array);
null_check->GetBlock()->RemoveInstruction(null_check);
null_check_deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
- suspend_check->GetEnvironment(), block);
+ suspend_check->GetEnvironment(), header);
}
- // Hoist array_length out of loop.
- array_length->MoveBefore(pre_header->GetLastInstruction());
+
+ HArrayLength* new_array_length = new (graph->GetArena()) HArrayLength(array);
+ deopt_block->InsertInstructionBefore(new_array_length, deopt_block->GetLastInstruction());
+
+ if (loop_entry_test_block_added) {
+ // Replace array_length defined inside the loop body with a phi
+ // array_length_in_loop_body_if_needed. This is a synthetic phi so there is
+ // no vreg number for it.
+ HPhi* phi = new (graph->GetArena()) HPhi(
+ graph->GetArena(), kNoRegNumber, 2, Primitive::kPrimInt);
+ // Set to 0 if the loop body isn't entered.
+ phi->SetRawInputAt(0, graph->GetIntConstant(0));
+ // Set to array.length if the loop body is entered.
+ phi->SetRawInputAt(1, new_array_length);
+ pre_header->AddPhi(phi);
+ array_length->ReplaceWith(phi);
+ // Make sure phi is only used after the loop body is entered.
+ if (kIsDebugBuild) {
+ for (HUseIterator<HInstruction*> it(phi->GetUses());
+ !it.Done();
+ it.Advance()) {
+ HInstruction* user = it.Current()->GetUser();
+ DCHECK(GetLoopHeaderSuccesorInLoop()->Dominates(user->GetBlock()));
+ }
+ }
+ } else {
+ array_length->ReplaceWith(new_array_length);
+ }
+
+ array_length->GetBlock()->RemoveInstruction(array_length);
+ // Use new_array_length for deopt.
+ array_length = new_array_length;
}
- HIntConstant* offset_instr = graph->GetIntConstant(offset);
- HAdd* add = new (graph->GetArena()) HAdd(Primitive::kPrimInt, array_length, offset_instr);
- HCondition* cond = new (graph->GetArena()) HGreaterThan(value, add);
- HDeoptimize* deoptimize = new (graph->GetArena())
- HDeoptimize(cond, suspend_check->GetDexPc());
- pre_header->InsertInstructionBefore(add, pre_header->GetLastInstruction());
- pre_header->InsertInstructionBefore(cond, pre_header->GetLastInstruction());
- pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction());
- deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
- suspend_check->GetEnvironment(), block);
+ HInstruction* added = array_length;
+ if (offset != 0) {
+ HIntConstant* offset_instr = graph->GetIntConstant(offset);
+ added = new (graph->GetArena()) HAdd(Primitive::kPrimInt, array_length, offset_instr);
+ deopt_block->InsertInstructionBefore(added, deopt_block->GetLastInstruction());
+ }
+ HCondition* cond = new (graph->GetArena()) HGreaterThan(value, added);
+ HDeoptimize* deopt = new (graph->GetArena()) HDeoptimize(cond, suspend_check->GetDexPc());
+ deopt_block->InsertInstructionBefore(cond, deopt_block->GetLastInstruction());
+ deopt_block->InsertInstructionBefore(deopt, deopt_block->GetLastInstruction());
+ deopt->CopyEnvironmentFromWithLoopPhiAdjustment(suspend_check->GetEnvironment(), header);
}
- // Add deoptimizations in loop pre-header with the collected array access
+ // Adds deoptimizations in loop pre-header with the collected array access
// data so that value ranges can be established in loop body.
// Returns true if deoptimizations are successfully added, or if it's proven
// it's not necessary.
@@ -733,70 +1028,60 @@ class MonotonicValueRange : public ValueRange {
return false;
}
+ HBasicBlock* deopt_block;
+ bool loop_entry_test_block_added = false;
bool is_constant_proven, is_length_proven;
+
+ HInstruction* const_comparing_instruction;
+ int32_t const_compared_to;
+ HInstruction* array_length_comparing_instruction;
+ int32_t array_length_offset;
if (increment_ == 1) {
// Increasing from initial_ to end_.
- int32_t offset = inclusive_ ? -offset_high - 1 : -offset_high;
- if (CanAddDeoptimizationConstant(initial_, -offset_low, &is_constant_proven) &&
- CanAddDeoptimizationArrayLength(end_, array_length, offset, &is_length_proven)) {
- if (!is_constant_proven) {
- AddDeoptimizationConstant(initial_, -offset_low);
- }
- if (!is_length_proven) {
- AddDeoptimizationArrayLength(end_, array_length, offset);
+ const_comparing_instruction = initial_;
+ const_compared_to = -offset_low;
+ array_length_comparing_instruction = end_;
+ array_length_offset = inclusive_ ? -offset_high - 1 : -offset_high;
+ } else {
+ const_comparing_instruction = end_;
+ const_compared_to = inclusive_ ? -offset_low : -offset_low - 1;
+ array_length_comparing_instruction = initial_;
+ array_length_offset = -offset_high - 1;
+ }
+
+ if (CanAddDeoptimizationConstant(const_comparing_instruction,
+ const_compared_to,
+ &is_constant_proven) &&
+ CanAddDeoptimizationArrayLength(array_length_comparing_instruction,
+ array_length,
+ array_length_offset,
+ &is_length_proven)) {
+ if (!is_constant_proven || !is_length_proven) {
+ deopt_block = TransformLoopForDeoptimizationIfNeeded();
+ loop_entry_test_block_added = (deopt_block != pre_header);
+ if (loop_entry_test_block_added) {
+ // Loop body may be entered.
+ AddLoopBodyEntryTest();
}
- return true;
}
- } else if (increment_ == -1) {
- // Decreasing from initial_ to end_.
- int32_t constant = inclusive_ ? -offset_low : -offset_low - 1;
- if (CanAddDeoptimizationConstant(end_, constant, &is_constant_proven) &&
- CanAddDeoptimizationArrayLength(
- initial_, array_length, -offset_high - 1, &is_length_proven)) {
- if (!is_constant_proven) {
- AddDeoptimizationConstant(end_, constant);
- }
- if (!is_length_proven) {
- AddDeoptimizationArrayLength(initial_, array_length, -offset_high - 1);
- }
- return true;
+ if (!is_constant_proven) {
+ AddDeoptimizationConstant(const_comparing_instruction,
+ const_compared_to,
+ deopt_block,
+ loop_entry_test_block_added);
+ }
+ if (!is_length_proven) {
+ AddDeoptimizationArrayLength(array_length_comparing_instruction,
+ array_length,
+ array_length_offset,
+ deopt_block,
+ loop_entry_test_block_added);
}
+ return true;
}
return false;
}
- // Try to add HDeoptimize's in the loop pre-header first to narrow this range.
- ValueRange* NarrowWithDeoptimization() {
- if (increment_ != 1 && increment_ != -1) {
- // TODO: possibly handle overflow/underflow issues with deoptimization.
- return this;
- }
-
- if (end_ == nullptr) {
- // No full info to add deoptimization.
- return this;
- }
-
- ArrayAccessInsideLoopFinder finder(induction_variable_);
-
- if (!finder.HasFoundArrayLength()) {
- // No array access was found inside the loop that can benefit
- // from deoptimization.
- return this;
- }
-
- if (!AddDeoptimization(finder)) {
- return this;
- }
-
- // After added deoptimizations, induction variable fits in
- // [-offset_low, array.length-1-offset_high], adjusted with collected offsets.
- ValueBound lower = ValueBound(0, -finder.GetOffsetLow());
- ValueBound upper = ValueBound(finder.GetFoundArrayLength(), -1 - finder.GetOffsetHigh());
- // We've narrowed the range after added deoptimizations.
- return new (GetAllocator()) ValueRange(GetAllocator(), lower, upper);
- }
-
private:
HPhi* const induction_variable_; // Induction variable for this monotonic value range.
HInstruction* const initial_; // Initial value.
@@ -819,12 +1104,17 @@ class BCEVisitor : public HGraphVisitor {
// it's likely some AIOOBE will be thrown.
static constexpr int32_t kMaxConstantForAddingDeoptimize = INT_MAX - 1024 * 1024;
+ // Added blocks for loop body entry test.
+ bool IsAddedBlock(HBasicBlock* block) const {
+ return block->GetBlockId() >= initial_block_size_;
+ }
+
explicit BCEVisitor(HGraph* graph)
- : HGraphVisitor(graph),
- maps_(graph->GetBlocks().Size()),
- need_to_revisit_block_(false) {}
+ : HGraphVisitor(graph), maps_(graph->GetBlocks().Size()),
+ need_to_revisit_block_(false), initial_block_size_(graph->GetBlocks().Size()) {}
void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
+ DCHECK(!IsAddedBlock(block));
first_constant_index_bounds_check_map_.clear();
HGraphVisitor::VisitBasicBlock(block);
if (need_to_revisit_block_) {
@@ -839,6 +1129,10 @@ class BCEVisitor : public HGraphVisitor {
private:
// Return the map of proven value ranges at the beginning of a basic block.
ArenaSafeMap<int, ValueRange*>* GetValueRangeMap(HBasicBlock* basic_block) {
+ if (IsAddedBlock(basic_block)) {
+ // Added blocks don't keep value ranges.
+ return nullptr;
+ }
int block_id = basic_block->GetBlockId();
if (maps_.at(block_id) == nullptr) {
std::unique_ptr<ArenaSafeMap<int, ValueRange*>> map(
@@ -853,8 +1147,12 @@ class BCEVisitor : public HGraphVisitor {
ValueRange* LookupValueRange(HInstruction* instruction, HBasicBlock* basic_block) {
while (basic_block != nullptr) {
ArenaSafeMap<int, ValueRange*>* map = GetValueRangeMap(basic_block);
- if (map->find(instruction->GetId()) != map->end()) {
- return map->Get(instruction->GetId());
+ if (map != nullptr) {
+ if (map->find(instruction->GetId()) != map->end()) {
+ return map->Get(instruction->GetId());
+ }
+ } else {
+ DCHECK(IsAddedBlock(basic_block));
}
basic_block = basic_block->GetDominator();
}
@@ -971,7 +1269,7 @@ class BCEVisitor : public HGraphVisitor {
if (left_range != nullptr) {
left_monotonic_range = left_range->AsMonotonicValueRange();
if (left_monotonic_range != nullptr) {
- HBasicBlock* loop_head = left_monotonic_range->GetLoopHead();
+ HBasicBlock* loop_head = left_monotonic_range->GetLoopHeader();
if (instruction->GetBlock() != loop_head) {
// For monotonic value range, don't handle `instruction`
// if it's not defined in the loop header.
@@ -1013,7 +1311,7 @@ class BCEVisitor : public HGraphVisitor {
// Update the info for monotonic value range.
if (left_monotonic_range->GetInductionVariable() == left &&
left_monotonic_range->GetIncrement() < 0 &&
- block == left_monotonic_range->GetLoopHead() &&
+ block == left_monotonic_range->GetLoopHeader() &&
instruction->IfFalseSuccessor()->GetLoopInformation() == block->GetLoopInformation()) {
left_monotonic_range->SetEnd(right);
left_monotonic_range->SetInclusive(cond == kCondLT);
@@ -1047,7 +1345,7 @@ class BCEVisitor : public HGraphVisitor {
// Update the info for monotonic value range.
if (left_monotonic_range->GetInductionVariable() == left &&
left_monotonic_range->GetIncrement() > 0 &&
- block == left_monotonic_range->GetLoopHead() &&
+ block == left_monotonic_range->GetLoopHeader() &&
instruction->IfFalseSuccessor()->GetLoopInformation() == block->GetLoopInformation()) {
left_monotonic_range->SetEnd(right);
left_monotonic_range->SetInclusive(cond == kCondGT);
@@ -1083,7 +1381,16 @@ class BCEVisitor : public HGraphVisitor {
HBasicBlock* block = bounds_check->GetBlock();
HInstruction* index = bounds_check->InputAt(0);
HInstruction* array_length = bounds_check->InputAt(1);
- DCHECK(array_length->IsIntConstant() || array_length->IsArrayLength());
+ DCHECK(array_length->IsIntConstant() ||
+ array_length->IsArrayLength() ||
+ array_length->IsPhi());
+
+ if (array_length->IsPhi()) {
+ // Input 1 of the phi contains the real array.length once the loop body is
+ // entered. That value will be used for bound analysis. The graph is still
+ // strickly in SSA form.
+ array_length = array_length->AsPhi()->InputAt(1)->AsArrayLength();
+ }
if (!index->IsIntConstant()) {
ValueRange* index_range = LookupValueRange(index, block);
@@ -1238,25 +1545,26 @@ class BCEVisitor : public HGraphVisitor {
}
if (left_range->IsMonotonicValueRange() &&
- block == left_range->AsMonotonicValueRange()->GetLoopHead()) {
+ block == left_range->AsMonotonicValueRange()->GetLoopHeader()) {
// The comparison is for an induction variable in the loop header.
DCHECK(left == left_range->AsMonotonicValueRange()->GetInductionVariable());
- HBasicBlock* loop_body_successor;
- if (LIKELY(block->GetLoopInformation()->
- Contains(*instruction->IfFalseSuccessor()))) {
- loop_body_successor = instruction->IfFalseSuccessor();
- } else {
- loop_body_successor = instruction->IfTrueSuccessor();
+ HBasicBlock* loop_body_successor =
+ left_range->AsMonotonicValueRange()->GetLoopHeaderSuccesorInLoop();
+ if (loop_body_successor == nullptr) {
+ // In case it's some strange loop structure.
+ return;
}
ValueRange* new_left_range = LookupValueRange(left, loop_body_successor);
- if (new_left_range == left_range) {
+ if ((new_left_range == left_range) ||
+ // Range narrowed with deoptimization is usually more useful than
+ // a constant range.
+ new_left_range->IsConstantValueRange()) {
// We are not successful in narrowing the monotonic value range to
// a regular value range. Try using deoptimization.
new_left_range = left_range->AsMonotonicValueRange()->
NarrowWithDeoptimization();
if (new_left_range != left_range) {
- GetValueRangeMap(instruction->IfFalseSuccessor())->
- Overwrite(left->GetId(), new_left_range);
+ GetValueRangeMap(loop_body_successor)->Overwrite(left->GetId(), new_left_range);
}
}
}
@@ -1511,6 +1819,9 @@ class BCEVisitor : public HGraphVisitor {
// eliminate those bounds checks.
bool need_to_revisit_block_;
+ // Initial number of blocks.
+ int32_t initial_block_size_;
+
DISALLOW_COPY_AND_ASSIGN(BCEVisitor);
};
@@ -1527,7 +1838,22 @@ void BoundsCheckElimination::Run() {
// value can be narrowed further down in the dominator tree.
//
// TODO: only visit blocks that dominate some array accesses.
- visitor.VisitReversePostOrder();
+ HBasicBlock* last_visited_block = nullptr;
+ for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* current = it.Current();
+ if (current == last_visited_block) {
+ // We may insert blocks into the reverse post order list when processing
+ // a loop header. Don't process it again.
+ DCHECK(current->IsLoopHeader());
+ continue;
+ }
+ if (visitor.IsAddedBlock(current)) {
+ // Skip added blocks. Their effects are already taken care of.
+ continue;
+ }
+ visitor.VisitBasicBlock(current);
+ last_visited_block = current;
+ }
}
} // namespace art
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index e383ec664b..4701bddd48 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -440,22 +440,16 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) {
HInstruction* bounds_check = nullptr;
HGraph* graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
- ASSERT_FALSE(IsRemoved(bounds_check));
-
- // This time add gvn. Need gvn to eliminate the second
- // HArrayLength which uses the null check as its input.
- graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1);
- graph->BuildDominatorTree();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
- bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
// for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 1);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
@@ -464,6 +458,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) {
// for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, -1, 1);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
bounds_check_elimination_with_initial_minus_1.Run();
@@ -472,6 +467,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) {
// for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1, kCondGT);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
bounds_check_elimination_with_greater_than.Run();
@@ -481,6 +477,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) {
// array[i] = 10; // Can't eliminate due to overflow concern. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 2);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_increment_2(graph);
bounds_check_elimination_with_increment_2.Run();
@@ -489,6 +486,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) {
// for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 2);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_increment_2_from_1(graph);
bounds_check_elimination_with_increment_2_from_1.Run();
@@ -579,22 +577,16 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) {
HInstruction* bounds_check = nullptr;
HGraph* graph = BuildSSAGraph2(&allocator, &bounds_check, 0);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
- ASSERT_FALSE(IsRemoved(bounds_check));
-
- // This time add gvn. Need gvn to eliminate the second
- // HArrayLength which uses the null check as its input.
- graph = BuildSSAGraph2(&allocator, &bounds_check, 0);
- graph->BuildDominatorTree();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
- bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
// for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, 1);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
@@ -603,6 +595,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) {
// for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, -1);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
bounds_check_elimination_with_initial_minus_1.Run();
@@ -611,6 +604,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) {
// for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -1, kCondLT);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_less_than(graph);
bounds_check_elimination_with_less_than.Run();
@@ -619,6 +613,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) {
// for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -2);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_increment_minus_2(graph);
bounds_check_elimination_increment_minus_2.Run();
@@ -710,15 +705,17 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
HInstruction* bounds_check = nullptr;
HGraph* graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGE);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
- bounds_check_elimination_after_gvn.Run();
+ BoundsCheckElimination bounds_check_elimination(graph);
+ bounds_check_elimination.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
// int[] array = new int[10];
// for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
@@ -728,6 +725,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
// for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
bounds_check_elimination_with_greater_than.Run();
@@ -737,6 +735,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
// for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_increment_8(graph);
bounds_check_elimination_increment_8.Run();
@@ -828,22 +827,16 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination4) {
HInstruction* bounds_check = nullptr;
HGraph* graph = BuildSSAGraph4(&allocator, &bounds_check, 0);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
- ASSERT_FALSE(IsRemoved(bounds_check));
-
- // This time add gvn. Need gvn to eliminate the second
- // HArrayLength which uses the null check as its input.
- graph = BuildSSAGraph4(&allocator, &bounds_check, 0);
- graph->BuildDominatorTree();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
- bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
// for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
graph = BuildSSAGraph4(&allocator, &bounds_check, 1);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
@@ -852,6 +845,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination4) {
// for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. }
graph = BuildSSAGraph4(&allocator, &bounds_check, 0, kCondGT);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
bounds_check_elimination_with_greater_than.Run();
@@ -1027,6 +1021,7 @@ TEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
outer_body_add->AddSuccessor(outer_header);
graph->BuildDominatorTree();
+ graph->AnalyzeNaturalLoops();
RunSimplifierAndGvn(graph);
// gvn should remove the same bounds check.
ASSERT_FALSE(IsRemoved(bounds_check1));
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index cd91d2c87b..4baa05c80c 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1510,6 +1510,81 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
invoke->GetBlock()->RemoveInstruction(invoke);
}
+/*
+ * Loop will be transformed to:
+ * old_pre_header
+ * |
+ * if_block
+ * / \
+ * dummy_block deopt_block
+ * \ /
+ * new_pre_header
+ * |
+ * header
+ */
+void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) {
+ DCHECK(header->IsLoopHeader());
+ HBasicBlock* pre_header = header->GetDominator();
+
+ // Need this to avoid critical edge.
+ HBasicBlock* if_block = new (arena_) HBasicBlock(this, header->GetDexPc());
+ // Need this to avoid critical edge.
+ HBasicBlock* dummy_block = new (arena_) HBasicBlock(this, header->GetDexPc());
+ HBasicBlock* deopt_block = new (arena_) HBasicBlock(this, header->GetDexPc());
+ HBasicBlock* new_pre_header = new (arena_) HBasicBlock(this, header->GetDexPc());
+ AddBlock(if_block);
+ AddBlock(dummy_block);
+ AddBlock(deopt_block);
+ AddBlock(new_pre_header);
+
+ header->ReplacePredecessor(pre_header, new_pre_header);
+ pre_header->successors_.Reset();
+ pre_header->dominated_blocks_.Reset();
+
+ pre_header->AddSuccessor(if_block);
+ if_block->AddSuccessor(dummy_block); // True successor
+ if_block->AddSuccessor(deopt_block); // False successor
+ dummy_block->AddSuccessor(new_pre_header);
+ deopt_block->AddSuccessor(new_pre_header);
+
+ pre_header->dominated_blocks_.Add(if_block);
+ if_block->SetDominator(pre_header);
+ if_block->dominated_blocks_.Add(dummy_block);
+ dummy_block->SetDominator(if_block);
+ if_block->dominated_blocks_.Add(deopt_block);
+ deopt_block->SetDominator(if_block);
+ if_block->dominated_blocks_.Add(new_pre_header);
+ new_pre_header->SetDominator(if_block);
+ new_pre_header->dominated_blocks_.Add(header);
+ header->SetDominator(new_pre_header);
+
+ size_t index_of_header = 0;
+ while (reverse_post_order_.Get(index_of_header) != header) {
+ index_of_header++;
+ }
+ MakeRoomFor(&reverse_post_order_, 4, index_of_header - 1);
+ reverse_post_order_.Put(index_of_header++, if_block);
+ reverse_post_order_.Put(index_of_header++, dummy_block);
+ reverse_post_order_.Put(index_of_header++, deopt_block);
+ reverse_post_order_.Put(index_of_header++, new_pre_header);
+
+ HLoopInformation* info = pre_header->GetLoopInformation();
+ if (info != nullptr) {
+ if_block->SetLoopInformation(info);
+ dummy_block->SetLoopInformation(info);
+ deopt_block->SetLoopInformation(info);
+ new_pre_header->SetLoopInformation(info);
+ for (HLoopInformationOutwardIterator loop_it(*pre_header);
+ !loop_it.Done();
+ loop_it.Advance()) {
+ loop_it.Current()->Add(if_block);
+ loop_it.Current()->Add(dummy_block);
+ loop_it.Current()->Add(deopt_block);
+ loop_it.Current()->Add(new_pre_header);
+ }
+ }
+}
+
std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) {
ScopedObjectAccess soa(Thread::Current());
os << "["
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 5f128a7072..126b3b9879 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -195,6 +195,10 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
// Inline this graph in `outer_graph`, replacing the given `invoke` instruction.
void InlineInto(HGraph* outer_graph, HInvoke* invoke);
+ // Need to add a couple of blocks to test if the loop body is entered and
+ // put deoptimization instructions, etc.
+ void TransformLoopHeaderForBCE(HBasicBlock* header);
+
// Removes `block` from the graph.
void DeleteDeadBlock(HBasicBlock* block);
@@ -4264,6 +4268,39 @@ class HBlocksInLoopIterator : public ValueObject {
DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator);
};
+// Iterator over the blocks that art part of the loop. Includes blocks part
+// of an inner loop. The order in which the blocks are iterated is reverse
+// post order.
+class HBlocksInLoopReversePostOrderIterator : public ValueObject {
+ public:
+ explicit HBlocksInLoopReversePostOrderIterator(const HLoopInformation& info)
+ : blocks_in_loop_(info.GetBlocks()),
+ blocks_(info.GetHeader()->GetGraph()->GetReversePostOrder()),
+ index_(0) {
+ if (!blocks_in_loop_.IsBitSet(blocks_.Get(index_)->GetBlockId())) {
+ Advance();
+ }
+ }
+
+ bool Done() const { return index_ == blocks_.Size(); }
+ HBasicBlock* Current() const { return blocks_.Get(index_); }
+ void Advance() {
+ ++index_;
+ for (size_t e = blocks_.Size(); index_ < e; ++index_) {
+ if (blocks_in_loop_.IsBitSet(blocks_.Get(index_)->GetBlockId())) {
+ break;
+ }
+ }
+ }
+
+ private:
+ const BitVector& blocks_in_loop_;
+ const GrowableArray<HBasicBlock*>& blocks_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopReversePostOrderIterator);
+};
+
inline int64_t Int64FromConstant(HConstant* constant) {
DCHECK(constant->IsIntConstant() || constant->IsLongConstant());
return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue()
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-12-31 06:17:18 +0000