diff options
47 files changed, 1277 insertions, 366 deletions
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk index fdfd94c5c0..ff41736a35 100644 --- a/build/Android.gtest.mk +++ b/build/Android.gtest.mk @@ -29,6 +29,7 @@ GTEST_DEX_DIRECTORIES := \ GetMethodSignature \ Instrumentation \ Interfaces \ + Lookup \ Main \ MultiDex \ MultiDexModifiedSecondary \ @@ -78,6 +79,7 @@ ART_GTEST_proxy_test_DEX_DEPS := Interfaces ART_GTEST_reflection_test_DEX_DEPS := Main NonStaticLeafMethods StaticLeafMethods ART_GTEST_stub_test_DEX_DEPS := AllFields ART_GTEST_transaction_test_DEX_DEPS := Transaction +ART_GTEST_type_lookup_table_test_DEX_DEPS := Lookup # The elf writer test has dependencies on core.oat. ART_GTEST_elf_writer_test_HOST_DEPS := $(HOST_CORE_IMAGE_default_no-pic_64) $(HOST_CORE_IMAGE_default_no-pic_32) @@ -220,6 +222,7 @@ RUNTIME_GTEST_COMMON_SRC_FILES := \ runtime/reference_table_test.cc \ runtime/thread_pool_test.cc \ runtime/transaction_test.cc \ + runtime/type_lookup_table_test.cc \ runtime/utf_test.cc \ runtime/utils_test.cc \ runtime/verifier/method_verifier_test.cc \ diff --git a/compiler/dex/quick/gen_common.cc b/compiler/dex/quick/gen_common.cc index 5da72147b0..2b60a51e22 100644 --- a/compiler/dex/quick/gen_common.cc +++ b/compiler/dex/quick/gen_common.cc @@ -1104,11 +1104,7 @@ void Mir2Lir::GenNewInstance(uint32_t type_idx, RegLocation rl_dest) { // access because the verifier was unable to? const DexFile* dex_file = cu_->dex_file; CompilerDriver* driver = cu_->compiler_driver; - bool finalizable; - if (driver->CanAccessInstantiableTypeWithoutChecks(cu_->method_idx, - *dex_file, - type_idx, - &finalizable)) { + if (driver->CanAccessInstantiableTypeWithoutChecks(cu_->method_idx, *dex_file, type_idx)) { bool is_type_initialized; bool use_direct_type_ptr; uintptr_t direct_type_ptr; diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc index fa3598e291..8750aa8e4e 100644 --- a/compiler/driver/compiler_driver.cc +++ b/compiler/driver/compiler_driver.cc @@ -1247,8 +1247,7 @@ bool CompilerDriver::CanAccessTypeWithoutChecks(uint32_t referrer_idx, const Dex bool CompilerDriver::CanAccessInstantiableTypeWithoutChecks(uint32_t referrer_idx, const DexFile& dex_file, - uint32_t type_idx, - bool* finalizable) { + uint32_t type_idx) { ScopedObjectAccess soa(Thread::Current()); mirror::DexCache* dex_cache = Runtime::Current()->GetClassLinker()->FindDexCache( soa.Self(), dex_file, false); @@ -1256,11 +1255,8 @@ bool CompilerDriver::CanAccessInstantiableTypeWithoutChecks(uint32_t referrer_id mirror::Class* resolved_class = dex_cache->GetResolvedType(type_idx); if (resolved_class == nullptr) { stats_->TypeNeedsAccessCheck(); - // Be conservative. - *finalizable = true; return false; // Unknown class needs access checks. } - *finalizable = resolved_class->IsFinalizable(); const DexFile::MethodId& method_id = dex_file.GetMethodId(referrer_idx); mirror::Class* referrer_class = dex_cache->GetResolvedType(method_id.class_idx_); if (referrer_class == nullptr) { diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h index 15806b5579..485cdcfb1b 100644 --- a/compiler/driver/compiler_driver.h +++ b/compiler/driver/compiler_driver.h @@ -200,10 +200,8 @@ class CompilerDriver { REQUIRES(!Locks::mutator_lock_); // Are runtime access and instantiable checks necessary in the code? - bool CanAccessInstantiableTypeWithoutChecks(uint32_t referrer_idx, - const DexFile& dex_file, - uint32_t type_idx, - bool* finalizable) + bool CanAccessInstantiableTypeWithoutChecks(uint32_t referrer_idx, const DexFile& dex_file, + uint32_t type_idx) REQUIRES(!Locks::mutator_lock_); bool CanEmbedTypeInCode(const DexFile& dex_file, uint32_t type_idx, diff --git a/compiler/oat_writer.cc b/compiler/oat_writer.cc index dcb23bf1ec..c7b8884214 100644 --- a/compiler/oat_writer.cc +++ b/compiler/oat_writer.cc @@ -33,6 +33,7 @@ #include "driver/compiler_options.h" #include "gc/space/image_space.h" #include "gc/space/space.h" +#include "handle_scope-inl.h" #include "image_writer.h" #include "linker/relative_patcher.h" #include "mirror/array.h" @@ -44,7 +45,7 @@ #include "output_stream.h" #include "safe_map.h" #include "scoped_thread_state_change.h" -#include "handle_scope-inl.h" +#include "type_lookup_table.h" #include "utils/dex_cache_arrays_layout-inl.h" #include "verifier/method_verifier.h" @@ -107,6 +108,9 @@ OatWriter::OatWriter(const std::vector<const DexFile*>& dex_files, size_oat_class_status_(0), size_oat_class_method_bitmaps_(0), size_oat_class_method_offsets_(0), + size_oat_lookup_table_alignment_(0), + size_oat_lookup_table_offset_(0), + size_oat_lookup_table_(0), method_offset_map_() { CHECK(key_value_store != nullptr); @@ -129,6 +133,10 @@ OatWriter::OatWriter(const std::vector<const DexFile*>& dex_files, offset = InitDexFiles(offset); } { + TimingLogger::ScopedTiming split("InitLookupTables", timings); + offset = InitLookupTables(offset); + } + { TimingLogger::ScopedTiming split("InitOatClasses", timings); offset = InitOatClasses(offset); } @@ -322,7 +330,8 @@ class OatWriter::InitOatClassesMethodVisitor : public DexMethodVisitor { return true; } - bool VisitMethod(size_t class_def_method_index ATTRIBUTE_UNUSED, const ClassDataItemIterator& it) { + bool VisitMethod(size_t class_def_method_index ATTRIBUTE_UNUSED, + const ClassDataItemIterator& it) { // Fill in the compiled_methods_ array for methods that have a // CompiledMethod. We track the number of non-null entries in // num_non_null_compiled_methods_ since we only want to allocate @@ -1043,11 +1052,29 @@ size_t OatWriter::InitDexFiles(size_t offset) { oat_dex_files_[i]->dex_file_offset_ = offset; const DexFile* dex_file = (*dex_files_)[i]; + + // Initialize type lookup table + oat_dex_files_[i]->lookup_table_ = dex_file->GetTypeLookupTable(); + offset += dex_file->GetHeader().file_size_; } return offset; } +size_t OatWriter::InitLookupTables(size_t offset) { + for (OatDexFile* oat_dex_file : oat_dex_files_) { + if (oat_dex_file->lookup_table_ != nullptr) { + uint32_t aligned_offset = RoundUp(offset, 4); + oat_dex_file->lookup_table_offset_ = aligned_offset; + size_oat_lookup_table_alignment_ += aligned_offset - offset; + offset = aligned_offset + oat_dex_file->lookup_table_->RawDataLength(); + } else { + oat_dex_file->lookup_table_offset_ = 0; + } + } + return offset; +} + size_t OatWriter::InitOatClasses(size_t offset) { // calculate the offsets within OatDexFiles to OatClasses InitOatClassesMethodVisitor visitor(this, offset); @@ -1256,6 +1283,9 @@ bool OatWriter::WriteCode(OutputStream* out) { DO_STAT(size_oat_class_status_); DO_STAT(size_oat_class_method_bitmaps_); DO_STAT(size_oat_class_method_offsets_); + DO_STAT(size_oat_lookup_table_alignment_); + DO_STAT(size_oat_lookup_table_offset_); + DO_STAT(size_oat_lookup_table_); #undef DO_STAT VLOG(compiler) << "size_total=" << PrettySize(size_total) << " (" << size_total << "B)"; \ @@ -1309,6 +1339,9 @@ bool OatWriter::WriteTables(OutputStream* out, const size_t file_offset) { } size_dex_file_ += dex_file->GetHeader().file_size_; } + if (!WriteLookupTables(out, file_offset)) { + return false; + } for (size_t i = 0; i != oat_classes_.size(); ++i) { if (!oat_classes_[i]->Write(this, out, file_offset)) { PLOG(ERROR) << "Failed to write oat methods information to " << out->GetLocation(); @@ -1318,6 +1351,35 @@ bool OatWriter::WriteTables(OutputStream* out, const size_t file_offset) { return true; } +bool OatWriter::WriteLookupTables(OutputStream* out, const size_t file_offset) { + for (size_t i = 0; i < oat_dex_files_.size(); ++i) { + const uint32_t lookup_table_offset = oat_dex_files_[i]->lookup_table_offset_; + const TypeLookupTable* table = oat_dex_files_[i]->lookup_table_; + DCHECK_EQ(lookup_table_offset == 0, table == nullptr); + if (lookup_table_offset == 0) { + continue; + } + const uint32_t expected_offset = file_offset + lookup_table_offset; + off_t actual_offset = out->Seek(expected_offset, kSeekSet); + if (static_cast<uint32_t>(actual_offset) != expected_offset) { + const DexFile* dex_file = (*dex_files_)[i]; + PLOG(ERROR) << "Failed to seek to lookup table section. Actual: " << actual_offset + << " Expected: " << expected_offset << " File: " << dex_file->GetLocation(); + return false; + } + if (table != nullptr) { + if (!out->WriteFully(table->RawData(), table->RawDataLength())) { + const DexFile* dex_file = (*dex_files_)[i]; + PLOG(ERROR) << "Failed to write lookup table for " << dex_file->GetLocation() + << " to " << out->GetLocation(); + return false; + } + size_oat_lookup_table_ += table->RawDataLength(); + } + } + return true; +} + size_t OatWriter::WriteMaps(OutputStream* out, const size_t file_offset, size_t relative_offset) { #define VISIT(VisitorType) \ do { \ @@ -1425,6 +1487,7 @@ OatWriter::OatDexFile::OatDexFile(size_t offset, const DexFile& dex_file) { dex_file_location_data_ = reinterpret_cast<const uint8_t*>(location.data()); dex_file_location_checksum_ = dex_file.GetLocationChecksum(); dex_file_offset_ = 0; + lookup_table_offset_ = 0; methods_offsets_.resize(dex_file.NumClassDefs()); } @@ -1433,6 +1496,7 @@ size_t OatWriter::OatDexFile::SizeOf() const { + dex_file_location_size_ + sizeof(dex_file_location_checksum_) + sizeof(dex_file_offset_) + + sizeof(lookup_table_offset_) + (sizeof(methods_offsets_[0]) * methods_offsets_.size()); } @@ -1441,6 +1505,10 @@ void OatWriter::OatDexFile::UpdateChecksum(OatHeader* oat_header) const { oat_header->UpdateChecksum(dex_file_location_data_, dex_file_location_size_); oat_header->UpdateChecksum(&dex_file_location_checksum_, sizeof(dex_file_location_checksum_)); oat_header->UpdateChecksum(&dex_file_offset_, sizeof(dex_file_offset_)); + oat_header->UpdateChecksum(&lookup_table_offset_, sizeof(lookup_table_offset_)); + if (lookup_table_ != nullptr) { + oat_header->UpdateChecksum(lookup_table_->RawData(), lookup_table_->RawDataLength()); + } oat_header->UpdateChecksum(&methods_offsets_[0], sizeof(methods_offsets_[0]) * methods_offsets_.size()); } @@ -1469,6 +1537,11 @@ bool OatWriter::OatDexFile::Write(OatWriter* oat_writer, return false; } oat_writer->size_oat_dex_file_offset_ += sizeof(dex_file_offset_); + if (!out->WriteFully(&lookup_table_offset_, sizeof(lookup_table_offset_))) { + PLOG(ERROR) << "Failed to write lookup table offset to " << out->GetLocation(); + return false; + } + oat_writer->size_oat_lookup_table_offset_ += sizeof(lookup_table_offset_); if (!out->WriteFully(&methods_offsets_[0], sizeof(methods_offsets_[0]) * methods_offsets_.size())) { PLOG(ERROR) << "Failed to write methods offsets to " << out->GetLocation(); diff --git a/compiler/oat_writer.h b/compiler/oat_writer.h index d6cb65bd64..f2fe048174 100644 --- a/compiler/oat_writer.h +++ b/compiler/oat_writer.h @@ -24,8 +24,8 @@ #include "linker/relative_patcher.h" // For linker::RelativePatcherTargetProvider. #include "mem_map.h" #include "method_reference.h" -#include "oat.h" #include "mirror/class.h" +#include "oat.h" #include "safe_map.h" namespace art { @@ -36,6 +36,7 @@ class CompilerDriver; class ImageWriter; class OutputStream; class TimingLogger; +class TypeLookupTable; // OatHeader variable length with count of D OatDexFiles // @@ -49,6 +50,11 @@ class TimingLogger; // ... // Dex[D] // +// TypeLookupTable[0] one descriptor to class def index hash table for each OatDexFile. +// TypeLookupTable[1] +// ... +// TypeLookupTable[D] +// // OatClass[0] one variable sized OatClass for each of C DexFile::ClassDefs // OatClass[1] contains OatClass entries with class status, offsets to code, etc. // ... @@ -168,6 +174,7 @@ class OatWriter { size_t InitOatHeader(); size_t InitOatDexFiles(size_t offset); + size_t InitLookupTables(size_t offset); size_t InitDexFiles(size_t offset); size_t InitOatClasses(size_t offset); size_t InitOatMaps(size_t offset); @@ -177,6 +184,7 @@ class OatWriter { SHARED_REQUIRES(Locks::mutator_lock_); bool WriteTables(OutputStream* out, const size_t file_offset); + bool WriteLookupTables(OutputStream* out, const size_t file_offset); size_t WriteMaps(OutputStream* out, const size_t file_offset, size_t relative_offset); size_t WriteCode(OutputStream* out, const size_t file_offset, size_t relative_offset); size_t WriteCodeDexFiles(OutputStream* out, const size_t file_offset, size_t relative_offset); @@ -199,6 +207,8 @@ class OatWriter { const uint8_t* dex_file_location_data_; uint32_t dex_file_location_checksum_; uint32_t dex_file_offset_; + uint32_t lookup_table_offset_; + TypeLookupTable* lookup_table_; // Owned by the dex file. std::vector<uint32_t> methods_offsets_; private: @@ -333,6 +343,9 @@ class OatWriter { uint32_t size_oat_class_status_; uint32_t size_oat_class_method_bitmaps_; uint32_t size_oat_class_method_offsets_; + uint32_t size_oat_lookup_table_alignment_; + uint32_t size_oat_lookup_table_offset_; + uint32_t size_oat_lookup_table_; std::unique_ptr<linker::RelativePatcher> relative_patcher_; diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc index ee5b929875..ed193c7b61 100644 --- a/compiler/optimizing/builder.cc +++ b/compiler/optimizing/builder.cc @@ -1455,8 +1455,7 @@ void HGraphBuilder::BuildFilledNewArray(uint32_t dex_pc, uint32_t* args, uint32_t register_index) { HInstruction* length = graph_->GetIntConstant(number_of_vreg_arguments, dex_pc); - bool finalizable; - QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index, &finalizable) + QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index) ? kQuickAllocArrayWithAccessCheck : kQuickAllocArray; HInstruction* object = new (arena_) HNewArray(length, @@ -1636,9 +1635,9 @@ void HGraphBuilder::BuildTypeCheck(const Instruction& instruction, } } -bool HGraphBuilder::NeedsAccessCheck(uint32_t type_index, bool* finalizable) const { +bool HGraphBuilder::NeedsAccessCheck(uint32_t type_index) const { return !compiler_driver_->CanAccessInstantiableTypeWithoutChecks( - dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index, finalizable); + dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index); } void HGraphBuilder::BuildSwitchJumpTable(const SwitchTable& table, @@ -2515,9 +2514,7 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32 current_block_->AddInstruction(fake_string); UpdateLocal(register_index, fake_string, dex_pc); } else { - bool finalizable; - bool can_throw = NeedsAccessCheck(type_index, &finalizable); - QuickEntrypointEnum entrypoint = can_throw + QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index) ? kQuickAllocObjectWithAccessCheck : kQuickAllocObject; @@ -2526,8 +2523,6 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32 dex_pc, type_index, *dex_compilation_unit_->GetDexFile(), - can_throw, - finalizable, entrypoint)); UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction(), dex_pc); } @@ -2537,8 +2532,7 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32 case Instruction::NEW_ARRAY: { uint16_t type_index = instruction.VRegC_22c(); HInstruction* length = LoadLocal(instruction.VRegB_22c(), Primitive::kPrimInt, dex_pc); - bool finalizable; - QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index, &finalizable) + QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index) ? kQuickAllocArrayWithAccessCheck : kQuickAllocArray; current_block_->AddInstruction(new (arena_) HNewArray(length, diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h index 0f64489d98..9eaa4b62c5 100644 --- a/compiler/optimizing/builder.h +++ b/compiler/optimizing/builder.h @@ -138,7 +138,7 @@ class HGraphBuilder : public ValueObject { HInstruction* LoadLocal(uint32_t register_index, Primitive::Type type, uint32_t dex_pc) const; void PotentiallyAddSuspendCheck(HBasicBlock* target, uint32_t dex_pc); void InitializeParameters(uint16_t number_of_parameters); - bool NeedsAccessCheck(uint32_t type_index, bool* finalizable) const; + bool NeedsAccessCheck(uint32_t type_index) const; template<typename T> void Unop_12x(const Instruction& instruction, Primitive::Type type, uint32_t dex_pc); diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc index e0aa4ff489..57452cc076 100644 --- a/compiler/optimizing/constant_folding.cc +++ b/compiler/optimizing/constant_folding.cc @@ -27,6 +27,11 @@ class InstructionWithAbsorbingInputSimplifier : public HGraphVisitor { private: void VisitShift(HBinaryOperation* shift); + void VisitAbove(HAbove* instruction) OVERRIDE; + void VisitAboveOrEqual(HAboveOrEqual* instruction) OVERRIDE; + void VisitBelow(HBelow* instruction) OVERRIDE; + void VisitBelowOrEqual(HBelowOrEqual* instruction) OVERRIDE; + void VisitAnd(HAnd* instruction) OVERRIDE; void VisitCompare(HCompare* instruction) OVERRIDE; void VisitMul(HMul* instruction) OVERRIDE; @@ -105,6 +110,54 @@ void InstructionWithAbsorbingInputSimplifier::VisitShift(HBinaryOperation* instr } } +void InstructionWithAbsorbingInputSimplifier::VisitAbove(HAbove* instruction) { + if (instruction->GetLeft()->IsConstant() && + instruction->GetLeft()->AsConstant()->IsZero()) { + // Replace code looking like + // ABOVE dst, 0, src // unsigned 0 > src is always false + // with + // CONSTANT false + instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 0)); + instruction->GetBlock()->RemoveInstruction(instruction); + } +} + +void InstructionWithAbsorbingInputSimplifier::VisitAboveOrEqual(HAboveOrEqual* instruction) { + if (instruction->GetRight()->IsConstant() && + instruction->GetRight()->AsConstant()->IsZero()) { + // Replace code looking like + // ABOVE_OR_EQUAL dst, src, 0 // unsigned src >= 0 is always true + // with + // CONSTANT true + instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 1)); + instruction->GetBlock()->RemoveInstruction(instruction); + } +} + +void InstructionWithAbsorbingInputSimplifier::VisitBelow(HBelow* instruction) { + if (instruction->GetRight()->IsConstant() && + instruction->GetRight()->AsConstant()->IsZero()) { + // Replace code looking like + // BELOW dst, src, 0 // unsigned src < 0 is always false + // with + // CONSTANT false + instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 0)); + instruction->GetBlock()->RemoveInstruction(instruction); + } +} + +void InstructionWithAbsorbingInputSimplifier::VisitBelowOrEqual(HBelowOrEqual* instruction) { + if (instruction->GetLeft()->IsConstant() && + instruction->GetLeft()->AsConstant()->IsZero()) { + // Replace code looking like + // BELOW_OR_EQUAL dst, 0, src // unsigned 0 <= src is always true + // with + // CONSTANT true + instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 1)); + instruction->GetBlock()->RemoveInstruction(instruction); + } +} + void InstructionWithAbsorbingInputSimplifier::VisitAnd(HAnd* instruction) { HConstant* input_cst = instruction->GetConstantRight(); if ((input_cst != nullptr) && input_cst->IsZero()) { diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc index 2feb75cc9f..e469c8d6d0 100644 --- a/compiler/optimizing/constant_folding_test.cc +++ b/compiler/optimizing/constant_folding_test.cc @@ -29,50 +29,70 @@ namespace art { -static void TestCode(const uint16_t* data, - const std::string& expected_before, - const std::string& expected_after_cf, - const std::string& expected_after_dce, - std::function<void(HGraph*)> check_after_cf, - Primitive::Type return_type = Primitive::kPrimInt) { - ArenaPool pool; - ArenaAllocator allocator(&pool); - HGraph* graph = CreateCFG(&allocator, data, return_type); - ASSERT_NE(graph, nullptr); - - graph->TryBuildingSsa(); - - StringPrettyPrinter printer_before(graph); - printer_before.VisitInsertionOrder(); - std::string actual_before = printer_before.str(); - ASSERT_EQ(expected_before, actual_before); - - std::unique_ptr<const X86InstructionSetFeatures> features_x86( - X86InstructionSetFeatures::FromCppDefines()); - x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions()); - HConstantFolding(graph).Run(); - SSAChecker ssa_checker_cf(graph); - ssa_checker_cf.Run(); - ASSERT_TRUE(ssa_checker_cf.IsValid()); - - StringPrettyPrinter printer_after_cf(graph); - printer_after_cf.VisitInsertionOrder(); - std::string actual_after_cf = printer_after_cf.str(); - ASSERT_EQ(expected_after_cf, actual_after_cf); - - check_after_cf(graph); - - HDeadCodeElimination(graph).Run(); - SSAChecker ssa_checker_dce(graph); - ssa_checker_dce.Run(); - ASSERT_TRUE(ssa_checker_dce.IsValid()); - - StringPrettyPrinter printer_after_dce(graph); - printer_after_dce.VisitInsertionOrder(); - std::string actual_after_dce = printer_after_dce.str(); - ASSERT_EQ(expected_after_dce, actual_after_dce); -} - +/** + * Fixture class for the constant folding and dce tests. + */ +class ConstantFoldingTest : public testing::Test { + public: + ConstantFoldingTest() : pool_(), allocator_(&pool_) { + graph_ = CreateGraph(&allocator_); + } + + void TestCode(const uint16_t* data, + const std::string& expected_before, + const std::string& expected_after_cf, + const std::string& expected_after_dce, + std::function<void(HGraph*)> check_after_cf, + Primitive::Type return_type = Primitive::kPrimInt) { + graph_ = CreateCFG(&allocator_, data, return_type); + TestCodeOnReadyGraph(expected_before, + expected_after_cf, + expected_after_dce, + check_after_cf); + } + + void TestCodeOnReadyGraph(const std::string& expected_before, + const std::string& expected_after_cf, + const std::string& expected_after_dce, + std::function<void(HGraph*)> check_after_cf) { + ASSERT_NE(graph_, nullptr); + graph_->TryBuildingSsa(); + + StringPrettyPrinter printer_before(graph_); + printer_before.VisitInsertionOrder(); + std::string actual_before = printer_before.str(); + EXPECT_EQ(expected_before, actual_before); + + std::unique_ptr<const X86InstructionSetFeatures> features_x86( + X86InstructionSetFeatures::FromCppDefines()); + x86::CodeGeneratorX86 codegenX86(graph_, *features_x86.get(), CompilerOptions()); + HConstantFolding(graph_).Run(); + SSAChecker ssa_checker_cf(graph_); + ssa_checker_cf.Run(); + ASSERT_TRUE(ssa_checker_cf.IsValid()); + + StringPrettyPrinter printer_after_cf(graph_); + printer_after_cf.VisitInsertionOrder(); + std::string actual_after_cf = printer_after_cf.str(); + EXPECT_EQ(expected_after_cf, actual_after_cf); + + check_after_cf(graph_); + + HDeadCodeElimination(graph_).Run(); + SSAChecker ssa_checker_dce(graph_); + ssa_checker_dce.Run(); + ASSERT_TRUE(ssa_checker_dce.IsValid()); + + StringPrettyPrinter printer_after_dce(graph_); + printer_after_dce.VisitInsertionOrder(); + std::string actual_after_dce = printer_after_dce.str(); + EXPECT_EQ(expected_after_dce, actual_after_dce); + } + + ArenaPool pool_; + ArenaAllocator allocator_; + HGraph* graph_; +}; /** * Tiny three-register program exercising int constant folding on negation. @@ -84,7 +104,7 @@ static void TestCode(const uint16_t* data, * v1 <- -v0 1. neg-int v1, v0 * return v1 2. return v1 */ -TEST(ConstantFolding, IntConstantFoldingNegation) { +TEST_F(ConstantFoldingTest, IntConstantFoldingNegation) { const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 << 8 | 1 << 12, Instruction::NEG_INT | 1 << 8 | 0 << 12, @@ -141,7 +161,7 @@ TEST(ConstantFolding, IntConstantFoldingNegation) { * (v2, v3) <- -(v0, v1) 1. neg-long v2, v0 * return (v2, v3) 2. return-wide v2 */ -TEST(ConstantFolding, LongConstantFoldingNegation) { +TEST_F(ConstantFoldingTest, LongConstantFoldingNegation) { const int64_t input = INT64_C(4294967296); // 2^32 const uint16_t word0 = Low16Bits(Low32Bits(input)); // LSW. const uint16_t word1 = High16Bits(Low32Bits(input)); @@ -205,7 +225,7 @@ TEST(ConstantFolding, LongConstantFoldingNegation) { * v2 <- v0 + v1 2. add-int v2, v0, v1 * return v2 4. return v2 */ -TEST(ConstantFolding, IntConstantFoldingOnAddition1) { +TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition1) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 << 8 | 1 << 12, Instruction::CONST_4 | 1 << 8 | 2 << 12, @@ -271,7 +291,7 @@ TEST(ConstantFolding, IntConstantFoldingOnAddition1) { * v2 <- v0 + v1 6. add-int v2, v0, v1 * return v2 8. return v2 */ -TEST(ConstantFolding, IntConstantFoldingOnAddition2) { +TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition2) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 << 8 | 1 << 12, Instruction::CONST_4 | 1 << 8 | 2 << 12, @@ -357,7 +377,7 @@ TEST(ConstantFolding, IntConstantFoldingOnAddition2) { * v2 <- v0 - v1 2. sub-int v2, v0, v1 * return v2 4. return v2 */ -TEST(ConstantFolding, IntConstantFoldingOnSubtraction) { +TEST_F(ConstantFoldingTest, IntConstantFoldingOnSubtraction) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 << 8 | 3 << 12, Instruction::CONST_4 | 1 << 8 | 2 << 12, @@ -421,7 +441,7 @@ TEST(ConstantFolding, IntConstantFoldingOnSubtraction) { * (v0, v1) + (v1, v2) 4. add-long v4, v0, v2 * return (v4, v5) 6. return-wide v4 */ -TEST(ConstantFolding, LongConstantFoldingOnAddition) { +TEST_F(ConstantFoldingTest, LongConstantFoldingOnAddition) { const uint16_t data[] = SIX_REGISTERS_CODE_ITEM( Instruction::CONST_WIDE_16 | 0 << 8, 1, Instruction::CONST_WIDE_16 | 2 << 8, 2, @@ -486,7 +506,7 @@ TEST(ConstantFolding, LongConstantFoldingOnAddition) { * (v0, v1) - (v1, v2) 4. sub-long v4, v0, v2 * return (v4, v5) 6. return-wide v4 */ -TEST(ConstantFolding, LongConstantFoldingOnSubtraction) { +TEST_F(ConstantFoldingTest, LongConstantFoldingOnSubtraction) { const uint16_t data[] = SIX_REGISTERS_CODE_ITEM( Instruction::CONST_WIDE_16 | 0 << 8, 3, Instruction::CONST_WIDE_16 | 2 << 8, 2, @@ -560,7 +580,7 @@ TEST(ConstantFolding, LongConstantFoldingOnSubtraction) { * L3: v2 <- v1 + 8 11. add-int/lit16 v2, v1, #+8 * return v2 13. return v2 */ -TEST(ConstantFolding, IntConstantFoldingAndJumps) { +TEST_F(ConstantFoldingTest, IntConstantFoldingAndJumps) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 << 8 | 1 << 12, Instruction::CONST_4 | 1 << 8 | 2 << 12, @@ -656,7 +676,6 @@ TEST(ConstantFolding, IntConstantFoldingAndJumps) { check_after_cf); } - /** * Three-register program with a constant (static) condition. * @@ -670,7 +689,7 @@ TEST(ConstantFolding, IntConstantFoldingAndJumps) { * L1: v2 <- v0 + v1 5. add-int v2, v0, v1 * return-void 7. return */ -TEST(ConstantFolding, ConstantCondition) { +TEST_F(ConstantFoldingTest, ConstantCondition) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 1 << 8 | 1 << 12, Instruction::CONST_4 | 0 << 8 | 0 << 12, @@ -732,4 +751,109 @@ TEST(ConstantFolding, ConstantCondition) { check_after_cf); } +/** + * Unsigned comparisons with zero. Since these instructions are not present + * in the bytecode, we need to set up the graph explicitly. + */ +TEST_F(ConstantFoldingTest, UnsignedComparisonsWithZero) { + graph_ = CreateGraph(&allocator_); + HBasicBlock* entry_block = new (&allocator_) HBasicBlock(graph_); + graph_->AddBlock(entry_block); + graph_->SetEntryBlock(entry_block); + HBasicBlock* block = new (&allocator_) HBasicBlock(graph_); + graph_->AddBlock(block); + HBasicBlock* exit_block = new (&allocator_) HBasicBlock(graph_); + graph_->AddBlock(exit_block); + graph_->SetExitBlock(exit_block); + entry_block->AddSuccessor(block); + block->AddSuccessor(exit_block); + + // Make various unsigned comparisons with zero against a parameter. + HInstruction* parameter = new (&allocator_) HParameterValue( + graph_->GetDexFile(), 0, 0, Primitive::kPrimInt, true); + entry_block->AddInstruction(parameter); + HInstruction* zero = graph_->GetIntConstant(0); + HInstruction* last; + block->AddInstruction(last = new (&allocator_) HAbove(zero, parameter)); + block->AddInstruction(new (&allocator_) HDeoptimize(last, 0)); + block->AddInstruction(last = new (&allocator_) HAbove(parameter, zero)); + block->AddInstruction(new (&allocator_) HDeoptimize(last, 0)); + block->AddInstruction(last = new (&allocator_) HAboveOrEqual(zero, parameter)); + block->AddInstruction(new (&allocator_) HDeoptimize(last, 0)); + block->AddInstruction(last = new (&allocator_) HAboveOrEqual(parameter, zero)); + block->AddInstruction(new (&allocator_) HDeoptimize(last, 0)); + block->AddInstruction(last = new (&allocator_) HBelow(zero, parameter)); + block->AddInstruction(new (&allocator_) HDeoptimize(last, 0)); + block->AddInstruction(last = new (&allocator_) HBelow(parameter, zero)); + block->AddInstruction(new (&allocator_) HDeoptimize(last, 0)); + block->AddInstruction(last = new (&allocator_) HBelowOrEqual(zero, parameter)); + block->AddInstruction(new (&allocator_) HDeoptimize(last, 0)); + block->AddInstruction(last = new (&allocator_) HBelowOrEqual(parameter, zero)); + block->AddInstruction(new (&allocator_) HDeoptimize(last, 0)); + + entry_block->AddInstruction(new (&allocator_) HGoto()); + block->AddInstruction(new (&allocator_) HReturn(zero)); + exit_block->AddInstruction(new (&allocator_) HExit()); + + const std::string expected_before = + "BasicBlock 0, succ: 1\n" + " 0: ParameterValue [16, 14, 12, 10, 8, 6, 4, 2]\n" + " 1: IntConstant [19, 16, 14, 12, 10, 8, 6, 4, 2]\n" + " 18: Goto 1\n" + "BasicBlock 1, pred: 0, succ: 2\n" + " 2: Above(1, 0) [3]\n" + " 3: Deoptimize(2)\n" + " 4: Above(0, 1) [5]\n" + " 5: Deoptimize(4)\n" + " 6: AboveOrEqual(1, 0) [7]\n" + " 7: Deoptimize(6)\n" + " 8: AboveOrEqual(0, 1) [9]\n" + " 9: Deoptimize(8)\n" + " 10: Below(1, 0) [11]\n" + " 11: Deoptimize(10)\n" + " 12: Below(0, 1) [13]\n" + " 13: Deoptimize(12)\n" + " 14: BelowOrEqual(1, 0) [15]\n" + " 15: Deoptimize(14)\n" + " 16: BelowOrEqual(0, 1) [17]\n" + " 17: Deoptimize(16)\n" + " 19: Return(1)\n" + "BasicBlock 2, pred: 1\n" + " 20: Exit\n"; + + const std::string expected_after_cf = + "BasicBlock 0, succ: 1\n" + " 0: ParameterValue [16, 10, 6, 4]\n" + " 1: IntConstant [13, 3, 19, 16, 10, 6, 4]\n" + " 21: IntConstant [15, 9]\n" + " 18: Goto 1\n" + "BasicBlock 1, pred: 0, succ: 2\n" + " 3: Deoptimize(1)\n" + " 4: Above(0, 1) [5]\n" + " 5: Deoptimize(4)\n" + " 6: AboveOrEqual(1, 0) [7]\n" + " 7: Deoptimize(6)\n" + " 9: Deoptimize(21)\n" + " 10: Below(1, 0) [11]\n" + " 11: Deoptimize(10)\n" + " 13: Deoptimize(1)\n" + " 15: Deoptimize(21)\n" + " 16: BelowOrEqual(0, 1) [17]\n" + " 17: Deoptimize(16)\n" + " 19: Return(1)\n" + "BasicBlock 2, pred: 1\n" + " 20: Exit\n"; + + const std::string expected_after_dce = expected_after_cf; + + auto check_after_cf = [](HGraph* graph) { + CHECK(graph != nullptr); + }; + + TestCodeOnReadyGraph(expected_before, + expected_after_cf, + expected_after_dce, + check_after_cf); +} + } // namespace art diff --git a/compiler/optimizing/intrinsics_mips64.cc b/compiler/optimizing/intrinsics_mips64.cc index 0ab0b80396..05c7eb02d9 100644 --- a/compiler/optimizing/intrinsics_mips64.cc +++ b/compiler/optimizing/intrinsics_mips64.cc @@ -1227,6 +1227,91 @@ void IntrinsicCodeGeneratorMIPS64::VisitUnsafePutLongVolatile(HInvoke* invoke) { GenUnsafePut(invoke->GetLocations(), Primitive::kPrimLong, true, false, codegen_); } +static void CreateIntIntIntIntIntToInt(ArenaAllocator* arena, HInvoke* invoke) { + LocationSummary* locations = new (arena) LocationSummary(invoke, + LocationSummary::kNoCall, + kIntrinsified); + locations->SetInAt(0, Location::NoLocation()); // Unused receiver. + locations->SetInAt(1, Location::RequiresRegister()); + locations->SetInAt(2, Location::RequiresRegister()); + locations->SetInAt(3, Location::RequiresRegister()); + locations->SetInAt(4, Location::RequiresRegister()); + + locations->SetOut(Location::RequiresRegister()); +} + +static void GenCas(LocationSummary* locations, Primitive::Type type, CodeGeneratorMIPS64* codegen) { + Mips64Assembler* assembler = codegen->GetAssembler(); + GpuRegister base = locations->InAt(1).AsRegister<GpuRegister>(); + GpuRegister offset = locations->InAt(2).AsRegister<GpuRegister>(); + GpuRegister expected = locations->InAt(3).AsRegister<GpuRegister>(); + GpuRegister value = locations->InAt(4).AsRegister<GpuRegister>(); + GpuRegister out = locations->Out().AsRegister<GpuRegister>(); + + DCHECK_NE(base, out); + DCHECK_NE(offset, out); + DCHECK_NE(expected, out); + + // do { + // tmp_value = [tmp_ptr] - expected; + // } while (tmp_value == 0 && failure([tmp_ptr] <- r_new_value)); + // result = tmp_value != 0; + + Label loop_head, exit_loop; + __ Daddu(TMP, base, offset); + __ Sync(0); + __ Bind(&loop_head); + if (type == Primitive::kPrimLong) { + __ Lld(out, TMP); + } else { + __ Ll(out, TMP); + } + __ Dsubu(out, out, expected); // If we didn't get the 'expected' + __ Sltiu(out, out, 1); // value, set 'out' to false, and + __ Beqzc(out, &exit_loop); // return. + __ Move(out, value); // Use 'out' for the 'store conditional' instruction. + // If we use 'value' directly, we would lose 'value' + // in the case that the store fails. Whether the + // store succeeds, or fails, it will load the + // correct boolean value into the 'out' register. + if (type == Primitive::kPrimLong) { + __ Scd(out, TMP); + } else { + __ Sc(out, TMP); + } + __ Beqzc(out, &loop_head); // If we couldn't do the read-modify-write + // cycle atomically then retry. + __ Bind(&exit_loop); + __ Sync(0); +} + +// boolean sun.misc.Unsafe.compareAndSwapInt(Object o, long offset, int expected, int x) +void IntrinsicLocationsBuilderMIPS64::VisitUnsafeCASInt(HInvoke* invoke) { + CreateIntIntIntIntIntToInt(arena_, invoke); +} + +void IntrinsicCodeGeneratorMIPS64::VisitUnsafeCASInt(HInvoke* invoke) { + GenCas(invoke->GetLocations(), Primitive::kPrimInt, codegen_); +} + +// boolean sun.misc.Unsafe.compareAndSwapLong(Object o, long offset, long expected, long x) +void IntrinsicLocationsBuilderMIPS64::VisitUnsafeCASLong(HInvoke* invoke) { + CreateIntIntIntIntIntToInt(arena_, invoke); +} + +void IntrinsicCodeGeneratorMIPS64::VisitUnsafeCASLong(HInvoke* invoke) { + GenCas(invoke->GetLocations(), Primitive::kPrimLong, codegen_); +} + +// boolean sun.misc.Unsafe.compareAndSwapObject(Object o, long offset, Object expected, Object x) +void IntrinsicLocationsBuilderMIPS64::VisitUnsafeCASObject(HInvoke* invoke) { + CreateIntIntIntIntIntToInt(arena_, invoke); +} + +void IntrinsicCodeGeneratorMIPS64::VisitUnsafeCASObject(HInvoke* invoke) { + GenCas(invoke->GetLocations(), Primitive::kPrimNot, codegen_); +} + // char java.lang.String.charAt(int index) void IntrinsicLocationsBuilderMIPS64::VisitStringCharAt(HInvoke* invoke) { LocationSummary* locations = new (arena_) LocationSummary(invoke, @@ -1502,9 +1587,6 @@ void IntrinsicCodeGeneratorMIPS64::Visit ## Name(HInvoke* invoke ATTRIBUTE_UNUSE UNIMPLEMENTED_INTRINSIC(MathRoundDouble) UNIMPLEMENTED_INTRINSIC(MathRoundFloat) -UNIMPLEMENTED_INTRINSIC(UnsafeCASInt) -UNIMPLEMENTED_INTRINSIC(UnsafeCASLong) -UNIMPLEMENTED_INTRINSIC(UnsafeCASObject) UNIMPLEMENTED_INTRINSIC(StringEquals) UNIMPLEMENTED_INTRINSIC(ReferenceGetReferent) diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc index c38bbe3477..27442d487e 100644 --- a/compiler/optimizing/licm.cc +++ b/compiler/optimizing/licm.cc @@ -122,6 +122,9 @@ void LICM::Run() { if (instruction->NeedsEnvironment()) { UpdateLoopPhisIn(instruction->GetEnvironment(), loop_info); } + // Move instruction into the pre header. Note that this cannot move + // a throwing instruction out of its try block since these are hoisted + // only from the header block (and TryBoundary would start a new block). instruction->MoveBefore(pre_header->GetLastInstruction()); } else if (instruction->CanThrow()) { // If `instruction` can throw, we cannot move further instructions diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc index aa9c315ddd..90f28e511e 100644 --- a/compiler/optimizing/load_store_elimination.cc +++ b/compiler/optimizing/load_store_elimination.cc @@ -695,12 +695,8 @@ class LSEVisitor : public HGraphVisitor { } else { redundant_store = true; } - HNewInstance* new_instance = ref_info->GetReference()->AsNewInstance(); - DCHECK(new_instance != nullptr); - if (new_instance->IsFinalizable()) { - // Finalizable objects escape globally. Need to keep the store. - redundant_store = false; - } + // TODO: eliminate the store if the singleton object is not finalizable. + redundant_store = false; } if (redundant_store) { removed_instructions_.push_back(instruction); @@ -838,9 +834,7 @@ class LSEVisitor : public HGraphVisitor { return; } if (!heap_location_collector_.MayDeoptimize() && - ref_info->IsSingletonAndNotReturned() && - !new_instance->IsFinalizable() && - !new_instance->CanThrow()) { + ref_info->IsSingletonAndNotReturned()) { // The allocation might be eliminated. singleton_new_instances_.push_back(new_instance); } diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 8b28ff91d4..f825e50fe1 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -1140,6 +1140,14 @@ std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& } void HInstruction::MoveBefore(HInstruction* cursor) { + if (kIsDebugBuild && CanThrowIntoCatchBlock()) { + // Make sure we are not moving a throwing instruction out of its try block. + DCHECK(cursor->GetBlock()->IsTryBlock()); + const HTryBoundary& current_try = block_->GetTryCatchInformation()->GetTryEntry(); + const HTryBoundary& cursor_try = cursor->GetBlock()->GetTryCatchInformation()->GetTryEntry(); + DCHECK(cursor_try.HasSameExceptionHandlersAs(current_try)); + } + next_->previous_ = previous_; if (previous_ != nullptr) { previous_->next_ = next_; diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 0565c9a1cb..7df586692b 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -3601,14 +3601,10 @@ class HNewInstance : public HExpression<1> { uint32_t dex_pc, uint16_t type_index, const DexFile& dex_file, - bool can_throw, - bool finalizable, QuickEntrypointEnum entrypoint) : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc), type_index_(type_index), dex_file_(dex_file), - can_throw_(can_throw), - finalizable_(finalizable), entrypoint_(entrypoint) { SetRawInputAt(0, current_method); } @@ -3618,11 +3614,11 @@ class HNewInstance : public HExpression<1> { // Calls runtime so needs an environment. bool NeedsEnvironment() const OVERRIDE { return true; } - - // It may throw when called on type that's not instantiable/accessible. - bool CanThrow() const OVERRIDE { return can_throw_; } - - bool IsFinalizable() const { return finalizable_; } + // It may throw when called on: + // - interfaces + // - abstract/innaccessible/unknown classes + // TODO: optimize when possible. + bool CanThrow() const OVERRIDE { return true; } bool CanBeNull() const OVERRIDE { return false; } @@ -3633,8 +3629,6 @@ class HNewInstance : public HExpression<1> { private: const uint16_t type_index_; const DexFile& dex_file_; - const bool can_throw_; - const bool finalizable_; const QuickEntrypointEnum entrypoint_; DISALLOW_COPY_AND_ASSIGN(HNewInstance); diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 6632f95ebe..98acc34378 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -494,43 +494,31 @@ static void RunOptimizations(HGraph* graph, // TODO: Update passes incompatible with try/catch so we have the same // pipeline for all methods. - if (graph->HasTryCatch()) { - HOptimization* optimizations2[] = { - side_effects, - gvn, - dce2, - // The codegen has a few assumptions that only the instruction simplifier - // can satisfy. For example, the code generator does not expect to see a - // HTypeConversion from a type to the same type. - simplify4, - }; - - RunOptimizations(optimizations2, arraysize(optimizations2), pass_observer); - } else { + if (!graph->HasTryCatch()) { MaybeRunInliner(graph, codegen, driver, stats, dex_compilation_unit, pass_observer, handles); - - HOptimization* optimizations2[] = { - // BooleanSimplifier depends on the InstructionSimplifier removing - // redundant suspend checks to recognize empty blocks. - boolean_simplify, - fold2, // TODO: if we don't inline we can also skip fold2. - side_effects, - gvn, - licm, - induction, - bce, - simplify3, - lse, - dce2, - // The codegen has a few assumptions that only the instruction simplifier - // can satisfy. For example, the code generator does not expect to see a - // HTypeConversion from a type to the same type. - simplify4, - }; - - RunOptimizations(optimizations2, arraysize(optimizations2), pass_observer); } + HOptimization* optimizations2[] = { + // BooleanSimplifier depends on the InstructionSimplifier removing + // redundant suspend checks to recognize empty blocks. + boolean_simplify, + fold2, // TODO: if we don't inline we can also skip fold2. + side_effects, + gvn, + licm, + induction, + bce, + simplify3, + lse, + dce2, + // The codegen has a few assumptions that only the instruction simplifier + // can satisfy. For example, the code generator does not expect to see a + // HTypeConversion from a type to the same type. + simplify4, + }; + + RunOptimizations(optimizations2, arraysize(optimizations2), pass_observer); + RunArchOptimizations(driver->GetInstructionSet(), graph, stats, pass_observer); } diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc index 384b8794c1..af0bb65ccd 100644 --- a/dex2oat/dex2oat.cc +++ b/dex2oat/dex2oat.cc @@ -1410,6 +1410,7 @@ class Dex2Oat FINAL { ScopedObjectAccess soa(self); dex_caches_.push_back(soa.AddLocalReference<jobject>( class_linker->RegisterDexFile(*dex_file, Runtime::Current()->GetLinearAlloc()))); + dex_file->CreateTypeLookupTable(); } // If we use a swap file, ensure we are above the threshold to make it necessary. diff --git a/runtime/Android.mk b/runtime/Android.mk index 09d73119e6..1fdffe3e17 100644 --- a/runtime/Android.mk +++ b/runtime/Android.mk @@ -47,6 +47,7 @@ LIBART_COMMON_SRC_FILES := \ dex_file_verifier.cc \ dex_instruction.cc \ elf_file.cc \ + fault_handler.cc \ gc/allocation_record.cc \ gc/allocator/dlmalloc.cc \ gc/allocator/rosalloc.cc \ @@ -162,6 +163,7 @@ LIBART_COMMON_SRC_FILES := \ os_linux.cc \ parsed_options.cc \ primitive.cc \ + profiler.cc \ quick_exception_handler.cc \ quick/inline_method_analyser.cc \ reference_table.cc \ @@ -176,8 +178,7 @@ LIBART_COMMON_SRC_FILES := \ thread_pool.cc \ trace.cc \ transaction.cc \ - profiler.cc \ - fault_handler.cc \ + type_lookup_table.cc \ utf.cc \ utils.cc \ verifier/dex_gc_map.cc \ diff --git a/runtime/debugger.cc b/runtime/debugger.cc index b17b76e2ea..7117be9a54 100644 --- a/runtime/debugger.cc +++ b/runtime/debugger.cc @@ -69,29 +69,26 @@ static uint16_t CappedAllocRecordCount(size_t alloc_record_count) { return alloc_record_count; } -class Breakpoint { +class Breakpoint : public ValueObject { public: - Breakpoint(ArtMethod* method, uint32_t dex_pc, - DeoptimizationRequest::Kind deoptimization_kind) - SHARED_REQUIRES(Locks::mutator_lock_) - : method_(nullptr), dex_pc_(dex_pc), deoptimization_kind_(deoptimization_kind) { + Breakpoint(ArtMethod* method, uint32_t dex_pc, DeoptimizationRequest::Kind deoptimization_kind) + : method_(method), + dex_pc_(dex_pc), + deoptimization_kind_(deoptimization_kind) { CHECK(deoptimization_kind_ == DeoptimizationRequest::kNothing || deoptimization_kind_ == DeoptimizationRequest::kSelectiveDeoptimization || deoptimization_kind_ == DeoptimizationRequest::kFullDeoptimization); - ScopedObjectAccessUnchecked soa(Thread::Current()); - method_ = soa.EncodeMethod(method); } Breakpoint(const Breakpoint& other) SHARED_REQUIRES(Locks::mutator_lock_) - : method_(nullptr), dex_pc_(other.dex_pc_), - deoptimization_kind_(other.deoptimization_kind_) { - ScopedObjectAccessUnchecked soa(Thread::Current()); - method_ = soa.EncodeMethod(other.Method()); - } + : method_(other.method_), + dex_pc_(other.dex_pc_), + deoptimization_kind_(other.deoptimization_kind_) {} - ArtMethod* Method() const SHARED_REQUIRES(Locks::mutator_lock_) { - ScopedObjectAccessUnchecked soa(Thread::Current()); - return soa.DecodeMethod(method_); + // Method() is called from root visiting, do not use ScopedObjectAccess here or it can cause + // GC to deadlock if another thread tries to call SuspendAll while the GC is in a runnable state. + ArtMethod* Method() const { + return method_; } uint32_t DexPc() const { @@ -104,7 +101,7 @@ class Breakpoint { private: // The location of this breakpoint. - jmethodID method_; + ArtMethod* method_; uint32_t dex_pc_; // Indicates whether breakpoint needs full deoptimization or selective deoptimization. diff --git a/runtime/dex_file.cc b/runtime/dex_file.cc index ae62e2bfe1..b3ca6ac131 100644 --- a/runtime/dex_file.cc +++ b/runtime/dex_file.cc @@ -37,6 +37,7 @@ #include "dex_file-inl.h" #include "dex_file_verifier.h" #include "globals.h" +#include "handle_scope-inl.h" #include "leb128.h" #include "mirror/field.h" #include "mirror/method.h" @@ -44,8 +45,8 @@ #include "os.h" #include "reflection.h" #include "safe_map.h" -#include "handle_scope-inl.h" #include "thread.h" +#include "type_lookup_table.h" #include "utf-inl.h" #include "utils.h" #include "well_known_classes.h" @@ -414,11 +415,19 @@ DexFile::DexFile(const uint8_t* base, size_t size, method_ids_(reinterpret_cast<const MethodId*>(base + header_->method_ids_off_)), proto_ids_(reinterpret_cast<const ProtoId*>(base + header_->proto_ids_off_)), class_defs_(reinterpret_cast<const ClassDef*>(base + header_->class_defs_off_)), - find_class_def_misses_(0), - class_def_index_(nullptr), oat_dex_file_(oat_dex_file) { CHECK(begin_ != nullptr) << GetLocation(); CHECK_GT(size_, 0U) << GetLocation(); + const uint8_t* lookup_data = (oat_dex_file != nullptr) + ? oat_dex_file->GetLookupTableData() + : nullptr; + if (lookup_data != nullptr) { + if (lookup_data + TypeLookupTable::RawDataLength(*this) > oat_dex_file->GetOatFile()->End()) { + LOG(WARNING) << "found truncated lookup table in " << GetLocation(); + } else { + lookup_table_.reset(TypeLookupTable::Open(lookup_data, *this)); + } + } } DexFile::~DexFile() { @@ -426,8 +435,6 @@ DexFile::~DexFile() { // that's only called after DetachCurrentThread, which means there's no JNIEnv. We could // re-attach, but cleaning up these global references is not obviously useful. It's not as if // the global reference table is otherwise empty! - // Remove the index if one were created. - delete class_def_index_.LoadRelaxed(); } bool DexFile::Init(std::string* error_msg) { @@ -477,50 +484,25 @@ uint32_t DexFile::GetVersion() const { const DexFile::ClassDef* DexFile::FindClassDef(const char* descriptor, size_t hash) const { DCHECK_EQ(ComputeModifiedUtf8Hash(descriptor), hash); - // If we have an index lookup the descriptor via that as its constant time to search. - Index* index = class_def_index_.LoadSequentiallyConsistent(); - if (index != nullptr) { - auto it = index->FindWithHash(descriptor, hash); - return (it == index->end()) ? nullptr : it->second; + if (LIKELY(lookup_table_ != nullptr)) { + const uint32_t class_def_idx = lookup_table_->Lookup(descriptor, hash); + return (class_def_idx != DexFile::kDexNoIndex) ? &GetClassDef(class_def_idx) : nullptr; } + // Fast path for rate no class defs case. - uint32_t num_class_defs = NumClassDefs(); + const uint32_t num_class_defs = NumClassDefs(); if (num_class_defs == 0) { return nullptr; } - // Search for class def with 2 binary searches and then a linear search. - const StringId* string_id = FindStringId(descriptor); - if (string_id != nullptr) { - const TypeId* type_id = FindTypeId(GetIndexForStringId(*string_id)); - if (type_id != nullptr) { - uint16_t type_idx = GetIndexForTypeId(*type_id); - for (size_t i = 0; i < num_class_defs; ++i) { - const ClassDef& class_def = GetClassDef(i); - if (class_def.class_idx_ == type_idx) { - return &class_def; - } - } - } - } - // A miss. If we've had kMaxFailedDexClassDefLookups misses then build an index to speed things - // up. This isn't done eagerly at construction as construction is not performed in multi-threaded - // sections of tools like dex2oat. If we're lazy we hopefully increase the chance of balancing - // out which thread builds the index. - const uint32_t kMaxFailedDexClassDefLookups = 100; - uint32_t old_misses = find_class_def_misses_.FetchAndAddSequentiallyConsistent(1); - if (old_misses == kMaxFailedDexClassDefLookups) { - // Are we the ones moving the miss count past the max? Sanity check the index doesn't exist. - CHECK(class_def_index_.LoadSequentiallyConsistent() == nullptr); - // Build the index. - index = new Index(); - for (uint32_t i = 0; i < num_class_defs; ++i) { + const TypeId* type_id = FindTypeId(descriptor); + if (type_id != nullptr) { + uint16_t type_idx = GetIndexForTypeId(*type_id); + for (size_t i = 0; i < num_class_defs; ++i) { const ClassDef& class_def = GetClassDef(i); - const char* class_descriptor = GetClassDescriptor(class_def); - index->Insert(std::make_pair(class_descriptor, &class_def)); + if (class_def.class_idx_ == type_idx) { + return &class_def; + } } - // Sanity check the index still doesn't exist, only 1 thread should build it. - CHECK(class_def_index_.LoadSequentiallyConsistent() == nullptr); - class_def_index_.StoreSequentiallyConsistent(index); } return nullptr; } @@ -625,6 +607,26 @@ const DexFile::StringId* DexFile::FindStringId(const char* string) const { return nullptr; } +const DexFile::TypeId* DexFile::FindTypeId(const char* string) const { + int32_t lo = 0; + int32_t hi = NumTypeIds() - 1; + while (hi >= lo) { + int32_t mid = (hi + lo) / 2; + const TypeId& type_id = GetTypeId(mid); + const DexFile::StringId& str_id = GetStringId(type_id.descriptor_idx_); + const char* str = GetStringData(str_id); + int compare = CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(string, str); + if (compare > 0) { + lo = mid + 1; + } else if (compare < 0) { + hi = mid - 1; + } else { + return &type_id; + } + } + return nullptr; +} + const DexFile::StringId* DexFile::FindStringId(const uint16_t* string, size_t length) const { int32_t lo = 0; int32_t hi = NumStringIds() - 1; @@ -697,6 +699,10 @@ const DexFile::ProtoId* DexFile::FindProtoId(uint16_t return_type_idx, return nullptr; } +void DexFile::CreateTypeLookupTable() const { + lookup_table_.reset(TypeLookupTable::Create(*this)); +} + // Given a signature place the type ids into the given vector bool DexFile::CreateTypeList(const StringPiece& signature, uint16_t* return_type_idx, std::vector<uint16_t>* param_type_idxs) const { diff --git a/runtime/dex_file.h b/runtime/dex_file.h index 47e5c124ff..e7877b2e78 100644 --- a/runtime/dex_file.h +++ b/runtime/dex_file.h @@ -51,6 +51,7 @@ class OatDexFile; class Signature; template<class T> class Handle; class StringPiece; +class TypeLookupTable; class ZipArchive; // TODO: move all of the macro functionality into the DexCache class. @@ -532,6 +533,8 @@ class DexFile { // Looks up a string id for a given modified utf8 string. const StringId* FindStringId(const char* string) const; + const TypeId* FindTypeId(const char* string) const; + // Looks up a string id for a given utf16 string. const StringId* FindStringId(const uint16_t* string, size_t length) const; @@ -1139,6 +1142,12 @@ class DexFile { return oat_dex_file_; } + TypeLookupTable* GetTypeLookupTable() const { + return lookup_table_.get(); + } + + void CreateTypeLookupTable() const; + private: // Opens a .dex file static std::unique_ptr<const DexFile> OpenFile(int fd, const char* location, @@ -1237,44 +1246,11 @@ class DexFile { // Points to the base of the class definition list. const ClassDef* const class_defs_; - // Number of misses finding a class def from a descriptor. - mutable Atomic<uint32_t> find_class_def_misses_; - - struct UTF16EmptyFn { - void MakeEmpty(std::pair<const char*, const ClassDef*>& pair) const { - pair.first = nullptr; - pair.second = nullptr; - } - bool IsEmpty(const std::pair<const char*, const ClassDef*>& pair) const { - if (pair.first == nullptr) { - DCHECK(pair.second == nullptr); - return true; - } - return false; - } - }; - struct UTF16HashCmp { - // Hash function. - size_t operator()(const char* key) const { - return ComputeModifiedUtf8Hash(key); - } - // std::equal function. - bool operator()(const char* a, const char* b) const { - return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(a, b) == 0; - } - }; - using Index = HashMap<const char*, - const ClassDef*, - UTF16EmptyFn, - UTF16HashCmp, - UTF16HashCmp, - std::allocator<std::pair<const char*, const ClassDef*>>>; - mutable Atomic<Index*> class_def_index_; - // If this dex file was loaded from an oat file, oat_dex_file_ contains a // pointer to the OatDexFile it was loaded from. Otherwise oat_dex_file_ is // null. const OatDexFile* oat_dex_file_; + mutable std::unique_ptr<TypeLookupTable> lookup_table_; friend class DexFileVerifierTest; }; diff --git a/runtime/gc/accounting/space_bitmap-inl.h b/runtime/gc/accounting/space_bitmap-inl.h index 006d2c7d30..3be7181df2 100644 --- a/runtime/gc/accounting/space_bitmap-inl.h +++ b/runtime/gc/accounting/space_bitmap-inl.h @@ -46,7 +46,7 @@ inline bool SpaceBitmap<kAlignment>::AtomicTestAndSet(const mirror::Object* obj) DCHECK(Test(obj)); return true; } - } while (!atomic_entry->CompareExchangeWeakSequentiallyConsistent(old_word, old_word | mask)); + } while (!atomic_entry->CompareExchangeWeakRelaxed(old_word, old_word | mask)); DCHECK(Test(obj)); return false; } diff --git a/runtime/gc/collector/concurrent_copying.cc b/runtime/gc/collector/concurrent_copying.cc index e433b8d908..20e775c7aa 100644 --- a/runtime/gc/collector/concurrent_copying.cc +++ b/runtime/gc/collector/concurrent_copying.cc @@ -339,9 +339,7 @@ class EmptyCheckpoint : public Closure { << thread->GetState() << " thread " << thread << " self " << self; // If thread is a running mutator, then act on behalf of the garbage collector. // See the code in ThreadList::RunCheckpoint. - if (thread->GetState() == kRunnable) { - concurrent_copying_->GetBarrier().Pass(self); - } + concurrent_copying_->GetBarrier().Pass(self); } private: @@ -514,9 +512,7 @@ class DisableMarkingCheckpoint : public Closure { thread->SetIsGcMarking(false); // If thread is a running mutator, then act on behalf of the garbage collector. // See the code in ThreadList::RunCheckpoint. - if (thread->GetState() == kRunnable) { - concurrent_copying_->GetBarrier().Pass(self); - } + concurrent_copying_->GetBarrier().Pass(self); } private: @@ -937,9 +933,7 @@ class RevokeThreadLocalMarkStackCheckpoint : public Closure { } // If thread is a running mutator, then act on behalf of the garbage collector. // See the code in ThreadList::RunCheckpoint. - if (thread->GetState() == kRunnable) { - concurrent_copying_->GetBarrier().Pass(self); - } + concurrent_copying_->GetBarrier().Pass(self); } private: @@ -1670,7 +1664,7 @@ inline void ConcurrentCopying::Process(mirror::Object* obj, MemberOffset offset) // It was updated by the mutator. break; } - } while (!obj->CasFieldWeakSequentiallyConsistentObjectWithoutWriteBarrier< + } while (!obj->CasFieldWeakRelaxedObjectWithoutWriteBarrier< false, false, kVerifyNone>(offset, expected_ref, new_ref)); } @@ -1695,7 +1689,7 @@ void ConcurrentCopying::VisitRoots( // It was updated by the mutator. break; } - } while (!addr->CompareExchangeWeakSequentiallyConsistent(expected_ref, new_ref)); + } while (!addr->CompareExchangeWeakRelaxed(expected_ref, new_ref)); } } @@ -1716,7 +1710,7 @@ void ConcurrentCopying::MarkRoot(mirror::CompressedReference<mirror::Object>* ro // It was updated by the mutator. break; } - } while (!addr->CompareExchangeWeakSequentiallyConsistent(expected_ref, new_ref)); + } while (!addr->CompareExchangeWeakRelaxed(expected_ref, new_ref)); } } diff --git a/runtime/gc/collector/mark_sweep.cc b/runtime/gc/collector/mark_sweep.cc index 77a288ba68..db516a0a87 100644 --- a/runtime/gc/collector/mark_sweep.cc +++ b/runtime/gc/collector/mark_sweep.cc @@ -1146,9 +1146,7 @@ class CheckpointMarkThreadRoots : public Closure, public RootVisitor { } // If thread is a running mutator, then act on behalf of the garbage collector. // See the code in ThreadList::RunCheckpoint. - if (thread->GetState() == kRunnable) { - mark_sweep_->GetBarrier().Pass(self); - } + mark_sweep_->GetBarrier().Pass(self); } private: diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc index 1d385252f9..ab931429d0 100644 --- a/runtime/gc/heap.cc +++ b/runtime/gc/heap.cc @@ -1291,9 +1291,7 @@ class TrimIndirectReferenceTableClosure : public Closure { ATRACE_END(); // If thread is a running mutator, then act on behalf of the trim thread. // See the code in ThreadList::RunCheckpoint. - if (thread->GetState() == kRunnable) { - barrier_->Pass(Thread::Current()); - } + barrier_->Pass(Thread::Current()); } private: diff --git a/runtime/jit/jit_code_cache.cc b/runtime/jit/jit_code_cache.cc index 60568b2f77..cfccec87cf 100644 --- a/runtime/jit/jit_code_cache.cc +++ b/runtime/jit/jit_code_cache.cc @@ -369,9 +369,7 @@ class MarkCodeClosure FINAL : public Closure { DCHECK(thread == Thread::Current() || thread->IsSuspended()); MarkCodeVisitor visitor(thread, code_cache_); visitor.WalkStack(); - if (thread->GetState() == kRunnable) { - barrier_->Pass(Thread::Current()); - } + barrier_->Pass(Thread::Current()); } private: diff --git a/runtime/mirror/object-inl.h b/runtime/mirror/object-inl.h index 90180c545b..5c12091ecb 100644 --- a/runtime/mirror/object-inl.h +++ b/runtime/mirror/object-inl.h @@ -95,6 +95,12 @@ inline bool Object::CasLockWordWeakRelaxed(LockWord old_val, LockWord new_val) { OFFSET_OF_OBJECT_MEMBER(Object, monitor_), old_val.GetValue(), new_val.GetValue()); } +inline bool Object::CasLockWordWeakRelease(LockWord old_val, LockWord new_val) { + // Force use of non-transactional mode and do not check. + return CasFieldWeakRelease32<false, false>( + OFFSET_OF_OBJECT_MEMBER(Object, monitor_), old_val.GetValue(), new_val.GetValue()); +} + inline uint32_t Object::GetLockOwnerThreadId() { return Monitor::GetLockOwnerThreadId(this); } @@ -175,7 +181,10 @@ inline bool Object::AtomicSetReadBarrierPointer(Object* expected_rb_ptr, Object* static_cast<uint32_t>(reinterpret_cast<uintptr_t>(expected_rb_ptr))); new_lw = lw; new_lw.SetReadBarrierState(static_cast<uint32_t>(reinterpret_cast<uintptr_t>(rb_ptr))); - } while (!CasLockWordWeakSequentiallyConsistent(expected_lw, new_lw)); + // This CAS is a CAS release so that when GC updates all the fields of an object and then + // changes the object from gray to black, the field updates (stores) will be visible (won't be + // reordered after this CAS.) + } while (!CasLockWordWeakRelease(expected_lw, new_lw)); return true; #elif USE_BROOKS_READ_BARRIER DCHECK(kUseBrooksReadBarrier); @@ -671,6 +680,24 @@ inline bool Object::CasFieldWeakRelaxed32(MemberOffset field_offset, } template<bool kTransactionActive, bool kCheckTransaction, VerifyObjectFlags kVerifyFlags> +inline bool Object::CasFieldWeakRelease32(MemberOffset field_offset, + int32_t old_value, int32_t new_value) { + if (kCheckTransaction) { + DCHECK_EQ(kTransactionActive, Runtime::Current()->IsActiveTransaction()); + } + if (kTransactionActive) { + Runtime::Current()->RecordWriteField32(this, field_offset, old_value, true); + } + if (kVerifyFlags & kVerifyThis) { + VerifyObject(this); + } + uint8_t* raw_addr = reinterpret_cast<uint8_t*>(this) + field_offset.Int32Value(); + AtomicInteger* atomic_addr = reinterpret_cast<AtomicInteger*>(raw_addr); + + return atomic_addr->CompareExchangeWeakRelease(old_value, new_value); +} + +template<bool kTransactionActive, bool kCheckTransaction, VerifyObjectFlags kVerifyFlags> inline bool Object::CasFieldStrongSequentiallyConsistent32(MemberOffset field_offset, int32_t old_value, int32_t new_value) { if (kCheckTransaction) { @@ -944,6 +971,62 @@ inline bool Object::CasFieldStrongSequentiallyConsistentObjectWithoutWriteBarrie return success; } +template<bool kTransactionActive, bool kCheckTransaction, VerifyObjectFlags kVerifyFlags> +inline bool Object::CasFieldWeakRelaxedObjectWithoutWriteBarrier( + MemberOffset field_offset, Object* old_value, Object* new_value) { + if (kCheckTransaction) { + DCHECK_EQ(kTransactionActive, Runtime::Current()->IsActiveTransaction()); + } + if (kVerifyFlags & kVerifyThis) { + VerifyObject(this); + } + if (kVerifyFlags & kVerifyWrites) { + VerifyObject(new_value); + } + if (kVerifyFlags & kVerifyReads) { + VerifyObject(old_value); + } + if (kTransactionActive) { + Runtime::Current()->RecordWriteFieldReference(this, field_offset, old_value, true); + } + HeapReference<Object> old_ref(HeapReference<Object>::FromMirrorPtr(old_value)); + HeapReference<Object> new_ref(HeapReference<Object>::FromMirrorPtr(new_value)); + uint8_t* raw_addr = reinterpret_cast<uint8_t*>(this) + field_offset.Int32Value(); + Atomic<uint32_t>* atomic_addr = reinterpret_cast<Atomic<uint32_t>*>(raw_addr); + + bool success = atomic_addr->CompareExchangeWeakRelaxed(old_ref.reference_, + new_ref.reference_); + return success; +} + +template<bool kTransactionActive, bool kCheckTransaction, VerifyObjectFlags kVerifyFlags> +inline bool Object::CasFieldStrongRelaxedObjectWithoutWriteBarrier( + MemberOffset field_offset, Object* old_value, Object* new_value) { + if (kCheckTransaction) { + DCHECK_EQ(kTransactionActive, Runtime::Current()->IsActiveTransaction()); + } + if (kVerifyFlags & kVerifyThis) { + VerifyObject(this); + } + if (kVerifyFlags & kVerifyWrites) { + VerifyObject(new_value); + } + if (kVerifyFlags & kVerifyReads) { + VerifyObject(old_value); + } + if (kTransactionActive) { + Runtime::Current()->RecordWriteFieldReference(this, field_offset, old_value, true); + } + HeapReference<Object> old_ref(HeapReference<Object>::FromMirrorPtr(old_value)); + HeapReference<Object> new_ref(HeapReference<Object>::FromMirrorPtr(new_value)); + uint8_t* raw_addr = reinterpret_cast<uint8_t*>(this) + field_offset.Int32Value(); + Atomic<uint32_t>* atomic_addr = reinterpret_cast<Atomic<uint32_t>*>(raw_addr); + + bool success = atomic_addr->CompareExchangeStrongRelaxed(old_ref.reference_, + new_ref.reference_); + return success; +} + template<bool kIsStatic, typename Visitor> inline void Object::VisitFieldsReferences(uint32_t ref_offsets, const Visitor& visitor) { if (!kIsStatic && (ref_offsets != mirror::Class::kClassWalkSuper)) { diff --git a/runtime/mirror/object.h b/runtime/mirror/object.h index f75b8aeef4..022f31dc53 100644 --- a/runtime/mirror/object.h +++ b/runtime/mirror/object.h @@ -135,6 +135,8 @@ class MANAGED LOCKABLE Object { SHARED_REQUIRES(Locks::mutator_lock_); bool CasLockWordWeakRelaxed(LockWord old_val, LockWord new_val) SHARED_REQUIRES(Locks::mutator_lock_); + bool CasLockWordWeakRelease(LockWord old_val, LockWord new_val) + SHARED_REQUIRES(Locks::mutator_lock_); uint32_t GetLockOwnerThreadId(); mirror::Object* MonitorEnter(Thread* self) @@ -276,7 +278,6 @@ class MANAGED LOCKABLE Object { Object* old_value, Object* new_value) SHARED_REQUIRES(Locks::mutator_lock_); - template<bool kTransactionActive, bool kCheckTransaction = true, VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags> bool CasFieldStrongSequentiallyConsistentObject(MemberOffset field_offset, Object* old_value, @@ -288,6 +289,18 @@ class MANAGED LOCKABLE Object { Object* old_value, Object* new_value) SHARED_REQUIRES(Locks::mutator_lock_); + template<bool kTransactionActive, bool kCheckTransaction = true, + VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags> + bool CasFieldWeakRelaxedObjectWithoutWriteBarrier(MemberOffset field_offset, + Object* old_value, + Object* new_value) + SHARED_REQUIRES(Locks::mutator_lock_); + template<bool kTransactionActive, bool kCheckTransaction = true, + VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags> + bool CasFieldStrongRelaxedObjectWithoutWriteBarrier(MemberOffset field_offset, + Object* old_value, + Object* new_value) + SHARED_REQUIRES(Locks::mutator_lock_); template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags> HeapReference<Object>* GetFieldObjectReferenceAddr(MemberOffset field_offset); @@ -396,6 +409,12 @@ class MANAGED LOCKABLE Object { template<bool kTransactionActive, bool kCheckTransaction = true, VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags> + bool CasFieldWeakRelease32(MemberOffset field_offset, int32_t old_value, + int32_t new_value) ALWAYS_INLINE + SHARED_REQUIRES(Locks::mutator_lock_); + + template<bool kTransactionActive, bool kCheckTransaction = true, + VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags> bool CasFieldStrongSequentiallyConsistent32(MemberOffset field_offset, int32_t old_value, int32_t new_value) ALWAYS_INLINE SHARED_REQUIRES(Locks::mutator_lock_); diff --git a/runtime/oat.h b/runtime/oat.h index 276e7f3ea5..5b780c38f8 100644 --- a/runtime/oat.h +++ b/runtime/oat.h @@ -31,7 +31,7 @@ class InstructionSetFeatures; class PACKED(4) OatHeader { public: static constexpr uint8_t kOatMagic[] = { 'o', 'a', 't', '\n' }; - static constexpr uint8_t kOatVersion[] = { '0', '7', '2', '\0' }; + static constexpr uint8_t kOatVersion[] = { '0', '7', '3', '\0' }; static constexpr const char* kImageLocationKey = "image-location"; static constexpr const char* kDex2OatCmdLineKey = "dex2oat-cmdline"; diff --git a/runtime/oat_file.cc b/runtime/oat_file.cc index a162a4ea72..680f4ac027 100644 --- a/runtime/oat_file.cc +++ b/runtime/oat_file.cc @@ -547,6 +547,25 @@ bool OatFile::Setup(const char* abs_dex_location, std::string* error_msg) { return false; } const DexFile::Header* header = reinterpret_cast<const DexFile::Header*>(dex_file_pointer); + + if (UNLIKELY(oat > End())) { + *error_msg = StringPrintf("In oat file '%s' found OatDexFile #%zd for '%s' with truncated " + "lookup table offset", GetLocation().c_str(), i, + dex_file_location.c_str()); + return false; + } + uint32_t lookup_table_offset = *reinterpret_cast<const uint32_t*>(oat); + oat += sizeof(lookup_table_offset); + if (Begin() + lookup_table_offset > End()) { + *error_msg = StringPrintf("In oat file '%s' found OatDexFile #%zd for '%s' with truncated " + "lookup table", GetLocation().c_str(), i, + dex_file_location.c_str()); + return false; + } + const uint8_t* lookup_table_data = lookup_table_offset != 0u + ? Begin() + lookup_table_offset + : nullptr; + const uint32_t* methods_offsets_pointer = reinterpret_cast<const uint32_t*>(oat); oat += (sizeof(*methods_offsets_pointer) * header->class_defs_size_); @@ -586,6 +605,7 @@ bool OatFile::Setup(const char* abs_dex_location, std::string* error_msg) { canonical_location, dex_file_checksum, dex_file_pointer, + lookup_table_data, methods_offsets_pointer, current_dex_cache_arrays); oat_dex_files_storage_.push_back(oat_dex_file); @@ -709,6 +729,7 @@ OatFile::OatDexFile::OatDexFile(const OatFile* oat_file, const std::string& canonical_dex_file_location, uint32_t dex_file_location_checksum, const uint8_t* dex_file_pointer, + const uint8_t* lookup_table_data, const uint32_t* oat_class_offsets_pointer, uint8_t* dex_cache_arrays) : oat_file_(oat_file), @@ -716,6 +737,7 @@ OatFile::OatDexFile::OatDexFile(const OatFile* oat_file, canonical_dex_file_location_(canonical_dex_file_location), dex_file_location_checksum_(dex_file_location_checksum), dex_file_pointer_(dex_file_pointer), + lookup_table_data_(lookup_table_data), oat_class_offsets_pointer_(oat_class_offsets_pointer), dex_cache_arrays_(dex_cache_arrays) {} diff --git a/runtime/oat_file.h b/runtime/oat_file.h index 6acdf86208..0a77654903 100644 --- a/runtime/oat_file.h +++ b/runtime/oat_file.h @@ -400,6 +400,10 @@ class OatDexFile FINAL { return dex_cache_arrays_; } + const uint8_t* GetLookupTableData() const { + return lookup_table_data_; + } + ~OatDexFile(); private: @@ -408,6 +412,7 @@ class OatDexFile FINAL { const std::string& canonical_dex_file_location, uint32_t dex_file_checksum, const uint8_t* dex_file_pointer, + const uint8_t* lookup_table_data, const uint32_t* oat_class_offsets_pointer, uint8_t* dex_cache_arrays); @@ -416,6 +421,7 @@ class OatDexFile FINAL { const std::string canonical_dex_file_location_; const uint32_t dex_file_location_checksum_; const uint8_t* const dex_file_pointer_; + const uint8_t* lookup_table_data_; const uint32_t* const oat_class_offsets_pointer_; uint8_t* const dex_cache_arrays_; diff --git a/runtime/quick_exception_handler.cc b/runtime/quick_exception_handler.cc index 53b4f3a3b5..1552318c1e 100644 --- a/runtime/quick_exception_handler.cc +++ b/runtime/quick_exception_handler.cc @@ -372,9 +372,14 @@ class DeoptimizeStackVisitor FINAL : public StackVisitor { StackMapEncoding encoding = code_info.ExtractEncoding(); StackMap stack_map = code_info.GetStackMapForNativePcOffset(native_pc_offset, encoding); const size_t number_of_vregs = m->GetCodeItem()->registers_size_; - DexRegisterMap vreg_map = code_info.GetDexRegisterMapOf(stack_map, encoding, number_of_vregs); MemoryRegion stack_mask = stack_map.GetStackMask(encoding); uint32_t register_mask = stack_map.GetRegisterMask(encoding); + DexRegisterMap vreg_map = IsInInlinedFrame() + ? code_info.GetDexRegisterMapAtDepth(GetCurrentInliningDepth() - 1, + code_info.GetInlineInfoOf(stack_map, encoding), + encoding, + number_of_vregs) + : code_info.GetDexRegisterMapOf(stack_map, encoding, number_of_vregs); for (uint16_t vreg = 0; vreg < number_of_vregs; ++vreg) { if (updated_vregs != nullptr && updated_vregs[vreg]) { diff --git a/runtime/read_barrier-inl.h b/runtime/read_barrier-inl.h index 85ac4aab96..4998a6a478 100644 --- a/runtime/read_barrier-inl.h +++ b/runtime/read_barrier-inl.h @@ -63,7 +63,7 @@ inline MirrorType* ReadBarrier::Barrier( ref = reinterpret_cast<MirrorType*>(Mark(old_ref)); // Update the field atomically. This may fail if mutator updates before us, but it's ok. if (ref != old_ref) { - obj->CasFieldStrongSequentiallyConsistentObjectWithoutWriteBarrier<false, false>( + obj->CasFieldStrongRelaxedObjectWithoutWriteBarrier<false, false>( offset, old_ref, ref); } } @@ -101,7 +101,7 @@ inline MirrorType* ReadBarrier::BarrierForRoot(MirrorType** root, // Update the field atomically. This may fail if mutator updates before us, but it's ok. if (ref != old_ref) { Atomic<mirror::Object*>* atomic_root = reinterpret_cast<Atomic<mirror::Object*>*>(root); - atomic_root->CompareExchangeStrongSequentiallyConsistent(old_ref, ref); + atomic_root->CompareExchangeStrongRelaxed(old_ref, ref); } } AssertToSpaceInvariant(gc_root_source, ref); @@ -140,7 +140,7 @@ inline MirrorType* ReadBarrier::BarrierForRoot(mirror::CompressedReference<Mirro if (new_ref.AsMirrorPtr() != old_ref.AsMirrorPtr()) { auto* atomic_root = reinterpret_cast<Atomic<mirror::CompressedReference<MirrorType>>*>(root); - atomic_root->CompareExchangeStrongSequentiallyConsistent(old_ref, new_ref); + atomic_root->CompareExchangeStrongRelaxed(old_ref, new_ref); } } AssertToSpaceInvariant(gc_root_source, ref); diff --git a/runtime/stack.h b/runtime/stack.h index 1276b244e7..aa7b6160fe 100644 --- a/runtime/stack.h +++ b/runtime/stack.h @@ -698,6 +698,10 @@ class StackVisitor { return current_inlining_depth_ != 0; } + size_t GetCurrentInliningDepth() const { + return current_inlining_depth_; + } + uintptr_t GetCurrentQuickFramePc() const { return cur_quick_frame_pc_; } diff --git a/runtime/thread_list.cc b/runtime/thread_list.cc index bdd5d1099c..dcf9601b4b 100644 --- a/runtime/thread_list.cc +++ b/runtime/thread_list.cc @@ -60,8 +60,11 @@ static constexpr useconds_t kThreadSuspendMaxYieldUs = 3000; static constexpr useconds_t kThreadSuspendMaxSleepUs = 5000; ThreadList::ThreadList() - : suspend_all_count_(0), debug_suspend_all_count_(0), unregistering_count_(0), - suspend_all_historam_("suspend all histogram", 16, 64), long_suspend_(false) { + : suspend_all_count_(0), + debug_suspend_all_count_(0), + unregistering_count_(0), + suspend_all_historam_("suspend all histogram", 16, 64), + long_suspend_(false) { CHECK(Monitor::IsValidLockWord(LockWord::FromThinLockId(kMaxThreadId, 1, 0U))); } @@ -195,9 +198,7 @@ class DumpCheckpoint FINAL : public Closure { MutexLock mu(self, *Locks::logging_lock_); *os_ << local_os.str(); } - if (thread->GetState() == kRunnable) { - barrier_.Pass(self); - } + barrier_.Pass(self); } void WaitForThreadsToRunThroughCheckpoint(size_t threads_running_checkpoint) { @@ -285,12 +286,12 @@ size_t ThreadList::RunCheckpoint(Closure* checkpoint_function) { // manually called. MutexLock mu(self, *Locks::thread_list_lock_); MutexLock mu2(self, *Locks::thread_suspend_count_lock_); + count = list_.size(); for (const auto& thread : list_) { if (thread != self) { while (true) { if (thread->RequestCheckpoint(checkpoint_function)) { // This thread will run its checkpoint some time in the near future. - count++; break; } else { // We are probably suspended, try to make sure that we stay suspended. @@ -383,7 +384,8 @@ size_t ThreadList::RunCheckpointOnRunnableThreads(Closure* checkpoint_function) // from-space to to-space refs. Used to synchronize threads at a point // to mark the initiation of marking while maintaining the to-space // invariant. -size_t ThreadList::FlipThreadRoots(Closure* thread_flip_visitor, Closure* flip_callback, +size_t ThreadList::FlipThreadRoots(Closure* thread_flip_visitor, + Closure* flip_callback, gc::collector::GarbageCollector* collector) { TimingLogger::ScopedTiming split("ThreadListFlip", collector->GetTimings()); const uint64_t start_time = NanoTime(); @@ -511,7 +513,9 @@ void ThreadList::SuspendAll(const char* cause, bool long_suspend) { // Debugger thread might be set to kRunnable for a short period of time after the // SuspendAllInternal. This is safe because it will be set back to suspended state before // the SuspendAll returns. -void ThreadList::SuspendAllInternal(Thread* self, Thread* ignore1, Thread* ignore2, +void ThreadList::SuspendAllInternal(Thread* self, + Thread* ignore1, + Thread* ignore2, bool debug_suspend) { Locks::mutator_lock_->AssertNotExclusiveHeld(self); Locks::thread_list_lock_->AssertNotHeld(self); @@ -700,12 +704,14 @@ void ThreadList::Resume(Thread* thread, bool for_debugger) { VLOG(threads) << "Resume(" << reinterpret_cast<void*>(thread) << ") complete"; } -static void ThreadSuspendByPeerWarning(Thread* self, LogSeverity severity, const char* message, +static void ThreadSuspendByPeerWarning(Thread* self, + LogSeverity severity, + const char* message, jobject peer) { JNIEnvExt* env = self->GetJniEnv(); ScopedLocalRef<jstring> - scoped_name_string(env, (jstring)env->GetObjectField( - peer, WellKnownClasses::java_lang_Thread_name)); + scoped_name_string(env, static_cast<jstring>(env->GetObjectField( + peer, WellKnownClasses::java_lang_Thread_name))); ScopedUtfChars scoped_name_chars(env, scoped_name_string.get()); if (scoped_name_chars.c_str() == nullptr) { LOG(severity) << message << ": " << peer; @@ -715,8 +721,10 @@ static void ThreadSuspendByPeerWarning(Thread* self, LogSeverity severity, const } } -Thread* ThreadList::SuspendThreadByPeer(jobject peer, bool request_suspension, - bool debug_suspension, bool* timed_out) { +Thread* ThreadList::SuspendThreadByPeer(jobject peer, + bool request_suspension, + bool debug_suspension, + bool* timed_out) { const uint64_t start_time = NanoTime(); useconds_t sleep_us = kThreadSuspendInitialSleepUs; *timed_out = false; @@ -813,12 +821,14 @@ Thread* ThreadList::SuspendThreadByPeer(jobject peer, bool request_suspension, } } -static void ThreadSuspendByThreadIdWarning(LogSeverity severity, const char* message, +static void ThreadSuspendByThreadIdWarning(LogSeverity severity, + const char* message, uint32_t thread_id) { LOG(severity) << StringPrintf("%s: %d", message, thread_id); } -Thread* ThreadList::SuspendThreadByThreadId(uint32_t thread_id, bool debug_suspension, +Thread* ThreadList::SuspendThreadByThreadId(uint32_t thread_id, + bool debug_suspension, bool* timed_out) { const uint64_t start_time = NanoTime(); useconds_t sleep_us = kThreadSuspendInitialSleepUs; diff --git a/runtime/thread_list.h b/runtime/thread_list.h index c727432977..07ea10dbea 100644 --- a/runtime/thread_list.h +++ b/runtime/thread_list.h @@ -55,8 +55,8 @@ class ThreadList { // Thread suspension support. void ResumeAll() - UNLOCK_FUNCTION(Locks::mutator_lock_) - REQUIRES(!Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); + REQUIRES(!Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_) + UNLOCK_FUNCTION(Locks::mutator_lock_); void Resume(Thread* thread, bool for_debugger = false) REQUIRES(!Locks::thread_suspend_count_lock_); @@ -76,7 +76,8 @@ class ThreadList { // is set to true. Thread* SuspendThreadByPeer(jobject peer, bool request_suspension, bool debug_suspension, bool* timed_out) - REQUIRES(!Locks::mutator_lock_, !Locks::thread_list_lock_, + REQUIRES(!Locks::mutator_lock_, + !Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); // Suspend a thread using its thread id, typically used by lock/monitor inflation. Returns the @@ -84,14 +85,16 @@ class ThreadList { // the thread terminating. Note that as thread ids are recycled this may not suspend the expected // thread, that may be terminating. If the suspension times out then *timeout is set to true. Thread* SuspendThreadByThreadId(uint32_t thread_id, bool debug_suspension, bool* timed_out) - REQUIRES(!Locks::mutator_lock_, !Locks::thread_list_lock_, + REQUIRES(!Locks::mutator_lock_, + !Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); // Find an already suspended thread (or self) by its id. Thread* FindThreadByThreadId(uint32_t thin_lock_id); // Run a checkpoint on threads, running threads are not suspended but run the checkpoint inside - // of the suspend check. Returns how many checkpoints we should expect to run. + // of the suspend check. Returns how many checkpoints that are expected to run, including for + // already suspended threads for b/24191051. size_t RunCheckpoint(Closure* checkpoint_function) REQUIRES(!Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); @@ -100,14 +103,17 @@ class ThreadList { // Flip thread roots from from-space refs to to-space refs. Used by // the concurrent copying collector. - size_t FlipThreadRoots(Closure* thread_flip_visitor, Closure* flip_callback, + size_t FlipThreadRoots(Closure* thread_flip_visitor, + Closure* flip_callback, gc::collector::GarbageCollector* collector) - REQUIRES(!Locks::mutator_lock_, !Locks::thread_list_lock_, + REQUIRES(!Locks::mutator_lock_, + !Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); // Suspends all threads void SuspendAllForDebugger() - REQUIRES(!Locks::mutator_lock_, !Locks::thread_list_lock_, + REQUIRES(!Locks::mutator_lock_, + !Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); void SuspendSelfForDebugger() @@ -126,10 +132,14 @@ class ThreadList { // Add/remove current thread from list. void Register(Thread* self) - REQUIRES(Locks::runtime_shutdown_lock_, !Locks::mutator_lock_, !Locks::thread_list_lock_, + REQUIRES(Locks::runtime_shutdown_lock_) + REQUIRES(!Locks::mutator_lock_, + !Locks::thread_list_lock_, + !Locks::thread_suspend_count_lock_); + void Unregister(Thread* self) + REQUIRES(!Locks::mutator_lock_, + !Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); - void Unregister(Thread* self) REQUIRES(!Locks::mutator_lock_, !Locks::thread_list_lock_, - !Locks::thread_suspend_count_lock_); void VisitRoots(RootVisitor* visitor) const SHARED_REQUIRES(Locks::mutator_lock_); @@ -159,7 +169,9 @@ class ThreadList { void WaitForOtherNonDaemonThreadsToExit() REQUIRES(!Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); - void SuspendAllInternal(Thread* self, Thread* ignore1, Thread* ignore2 = nullptr, + void SuspendAllInternal(Thread* self, + Thread* ignore1, + Thread* ignore2 = nullptr, bool debug_suspend = false) REQUIRES(!Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); @@ -200,8 +212,8 @@ class ScopedSuspendAll : public ValueObject { !Locks::mutator_lock_); // No REQUIRES(mutator_lock_) since the unlock function already asserts this. ~ScopedSuspendAll() - UNLOCK_FUNCTION(Locks::mutator_lock_) - REQUIRES(!Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_); + REQUIRES(!Locks::thread_list_lock_, !Locks::thread_suspend_count_lock_) + UNLOCK_FUNCTION(Locks::mutator_lock_); }; } // namespace art diff --git a/runtime/type_lookup_table.cc b/runtime/type_lookup_table.cc new file mode 100644 index 0000000000..0d40bb7be4 --- /dev/null +++ b/runtime/type_lookup_table.cc @@ -0,0 +1,131 @@ +/* + * Copyright (C) 2015 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 "type_lookup_table.h" + +#include "dex_file-inl.h" +#include "utf-inl.h" +#include "utils.h" + +#include <memory> +#include <cstring> + +namespace art { + +static uint16_t MakeData(uint16_t class_def_idx, uint32_t hash, uint32_t mask) { + uint16_t hash_mask = static_cast<uint16_t>(~mask); + return (static_cast<uint16_t>(hash) & hash_mask) | class_def_idx; +} + +TypeLookupTable::~TypeLookupTable() { + if (!owns_entries_) { + // We don't actually own the entries, don't let the unique_ptr release them. + entries_.release(); + } +} + +uint32_t TypeLookupTable::RawDataLength() const { + return RawDataLength(dex_file_); +} + +uint32_t TypeLookupTable::RawDataLength(const DexFile& dex_file) { + return RoundUpToPowerOfTwo(dex_file.NumClassDefs()) * sizeof(Entry); +} + +TypeLookupTable* TypeLookupTable::Create(const DexFile& dex_file) { + const uint32_t num_class_defs = dex_file.NumClassDefs(); + return (num_class_defs == 0 || num_class_defs > std::numeric_limits<uint16_t>::max()) + ? nullptr + : new TypeLookupTable(dex_file); +} + +TypeLookupTable* TypeLookupTable::Open(const uint8_t* raw_data, const DexFile& dex_file) { + return new TypeLookupTable(raw_data, dex_file); +} + +TypeLookupTable::TypeLookupTable(const DexFile& dex_file) + : dex_file_(dex_file), + mask_(RoundUpToPowerOfTwo(dex_file.NumClassDefs()) - 1), + entries_(new Entry[mask_ + 1]), + owns_entries_(true) { + std::vector<uint16_t> conflict_class_defs; + // The first stage. Put elements on their initial positions. If an initial position is already + // occupied then delay the insertion of the element to the second stage to reduce probing + // distance. + for (size_t i = 0; i < dex_file.NumClassDefs(); ++i) { + const DexFile::ClassDef& class_def = dex_file.GetClassDef(i); + const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_); + const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_); + const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id)); + Entry entry; + entry.str_offset = str_id.string_data_off_; + entry.data = MakeData(i, hash, GetSizeMask()); + if (!SetOnInitialPos(entry, hash)) { + conflict_class_defs.push_back(i); + } + } + // The second stage. The initial position of these elements had a collision. Put these elements + // into the nearest free cells and link them together by updating next_pos_delta. + for (uint16_t class_def_idx : conflict_class_defs) { + const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_idx); + const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_); + const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_); + const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id)); + Entry entry; + entry.str_offset = str_id.string_data_off_; + entry.data = MakeData(class_def_idx, hash, GetSizeMask()); + Insert(entry, hash); + } +} + +TypeLookupTable::TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file) + : dex_file_(dex_file), + mask_(RoundUpToPowerOfTwo(dex_file.NumClassDefs()) - 1), + entries_(reinterpret_cast<Entry*>(const_cast<uint8_t*>(raw_data))), + owns_entries_(false) {} + +bool TypeLookupTable::SetOnInitialPos(const Entry& entry, uint32_t hash) { + const uint32_t pos = hash & GetSizeMask(); + if (!entries_[pos].IsEmpty()) { + return false; + } + entries_[pos] = entry; + entries_[pos].next_pos_delta = 0; + return true; +} + +void TypeLookupTable::Insert(const Entry& entry, uint32_t hash) { + uint32_t pos = FindLastEntryInBucket(hash & GetSizeMask()); + uint32_t next_pos = (pos + 1) & GetSizeMask(); + while (!entries_[next_pos].IsEmpty()) { + next_pos = (next_pos + 1) & GetSizeMask(); + } + const uint32_t delta = (next_pos >= pos) ? (next_pos - pos) : (next_pos + Size() - pos); + entries_[pos].next_pos_delta = delta; + entries_[next_pos] = entry; + entries_[next_pos].next_pos_delta = 0; +} + +uint32_t TypeLookupTable::FindLastEntryInBucket(uint32_t pos) const { + const Entry* entry = &entries_[pos]; + while (!entry->IsLast()) { + pos = (pos + entry->next_pos_delta) & GetSizeMask(); + entry = &entries_[pos]; + } + return pos; +} + +} // namespace art diff --git a/runtime/type_lookup_table.h b/runtime/type_lookup_table.h new file mode 100644 index 0000000000..3c2295c428 --- /dev/null +++ b/runtime/type_lookup_table.h @@ -0,0 +1,162 @@ +/* + * Copyright (C) 2015 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_RUNTIME_TYPE_LOOKUP_TABLE_H_ +#define ART_RUNTIME_TYPE_LOOKUP_TABLE_H_ + +#include "dex_file.h" +#include "leb128.h" +#include "utf.h" + +namespace art { + +/** + * TypeLookupTable used to find class_def_idx by class descriptor quickly. + * Implementation of TypeLookupTable is based on hash table. + * This class instantiated at compile time by calling Create() method and written into OAT file. + * At runtime, the raw data is read from memory-mapped file by calling Open() method. The table + * memory remains clean. + */ +class TypeLookupTable { + public: + ~TypeLookupTable(); + + // Return the number of buckets in the lookup table. + uint32_t Size() const { + return mask_ + 1; + } + + // Method search class_def_idx by class descriptor and it's hash. + // If no data found then the method returns DexFile::kDexNoIndex + ALWAYS_INLINE uint32_t Lookup(const char* str, uint32_t hash) const { + uint32_t pos = hash & GetSizeMask(); + // Thanks to special insertion algorithm, the element at position pos can be empty or start of + // bucket. + const Entry* entry = &entries_[pos]; + while (!entry->IsEmpty()) { + if (CmpHashBits(entry->data, hash) && IsStringsEquals(str, entry->str_offset)) { + return GetClassDefIdx(entry->data); + } + if (entry->IsLast()) { + return DexFile::kDexNoIndex; + } + pos = (pos + entry->next_pos_delta) & GetSizeMask(); + entry = &entries_[pos]; + } + return DexFile::kDexNoIndex; + } + + // Method creates lookup table for dex file + static TypeLookupTable* Create(const DexFile& dex_file); + + // Method opens lookup table from binary data. Lookup table does not owns binary data. + static TypeLookupTable* Open(const uint8_t* raw_data, const DexFile& dex_file); + + // Method returns pointer to binary data of lookup table. Used by the oat writer. + const uint8_t* RawData() const { + return reinterpret_cast<const uint8_t*>(entries_.get()); + } + + // Method returns length of binary data. Used by the oat writer. + uint32_t RawDataLength() const; + + // Method returns length of binary data for the specified dex file. + static uint32_t RawDataLength(const DexFile& dex_file); + + private: + /** + * To find element we need to compare strings. + * It is faster to compare first hashes and then strings itself. + * But we have no full hash of element of table. But we can use 2 ideas. + * 1. All minor bits of hash inside one bucket are equals. + * 2. If dex file contains N classes and size of hash table is 2^n (where N <= 2^n) + * then 16-n bits are free. So we can encode part of element's hash into these bits. + * So hash of element can be divided on three parts: + * XXXX XXXX XXXX YYYY YZZZ ZZZZ ZZZZZ + * Z - a part of hash encoded in bucket (these bits of has are same for all elements in bucket) - + * n bits + * Y - a part of hash that we can write into free 16-n bits (because only n bits used to store + * class_def_idx) + * X - a part of has that we can't use without increasing increase + * So the data element of Entry used to store class_def_idx and part of hash of the entry. + */ + struct Entry { + uint32_t str_offset; + uint16_t data; + uint16_t next_pos_delta; + + Entry() : str_offset(0), data(0), next_pos_delta(0) {} + + bool IsEmpty() const { + return str_offset == 0; + } + + bool IsLast() const { + return next_pos_delta == 0; + } + }; + + // Construct from a dex file. + explicit TypeLookupTable(const DexFile& dex_file); + + // Construct from a dex file with existing data. + TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file); + + bool IsStringsEquals(const char* str, uint32_t str_offset) const { + const uint8_t* ptr = dex_file_.Begin() + str_offset; + // Skip string length. + DecodeUnsignedLeb128(&ptr); + return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues( + str, reinterpret_cast<const char*>(ptr)) == 0; + } + + // Method extracts hash bits from element's data and compare them with + // the corresponding bits of the specified hash + bool CmpHashBits(uint32_t data, uint32_t hash) const { + uint32_t mask = static_cast<uint16_t>(~GetSizeMask()); + return (hash & mask) == (data & mask); + } + + uint32_t GetClassDefIdx(uint32_t data) const { + return data & mask_; + } + + uint32_t GetSizeMask() const { + return mask_; + } + + // Attempt to set an entry on it's hash' slot. If there is alrady something there, return false. + // Otherwise return true. + bool SetOnInitialPos(const Entry& entry, uint32_t hash); + + // Insert an entry, probes until there is an empty slot. + void Insert(const Entry& entry, uint32_t hash); + + // Find the last entry in a chain. + uint32_t FindLastEntryInBucket(uint32_t cur_pos) const; + + const DexFile& dex_file_; + const uint32_t mask_; + std::unique_ptr<Entry[]> entries_; + // owns_entries_ specifies if the lookup table owns the entries_ array. + const bool owns_entries_; + + DISALLOW_IMPLICIT_CONSTRUCTORS(TypeLookupTable); +}; + +} // namespace art + +#endif // ART_RUNTIME_TYPE_LOOKUP_TABLE_H_ diff --git a/runtime/type_lookup_table_test.cc b/runtime/type_lookup_table_test.cc new file mode 100644 index 0000000000..7f500cc9a1 --- /dev/null +++ b/runtime/type_lookup_table_test.cc @@ -0,0 +1,86 @@ +/* + * Copyright (C) 2011 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 <memory> + +#include "common_runtime_test.h" +#include "dex_file-inl.h" +#include "scoped_thread_state_change.h" +#include "type_lookup_table.h" +#include "utf-inl.h" + +namespace art { + +class TypeLookupTableTest : public CommonRuntimeTest { + public: + size_t kDexNoIndex = DexFile::kDexNoIndex; // Make copy to prevent linking errors. +}; + +TEST_F(TypeLookupTableTest, CreateLookupTable) { + ScopedObjectAccess soa(Thread::Current()); + std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup")); + std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file)); + ASSERT_NE(nullptr, table.get()); + ASSERT_NE(nullptr, table->RawData()); + ASSERT_EQ(32U, table->RawDataLength()); +} + +TEST_F(TypeLookupTableTest, FindNonExistingClassWithoutCollisions) { + ScopedObjectAccess soa(Thread::Current()); + std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup")); + std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file)); + ASSERT_NE(nullptr, table.get()); + const char* descriptor = "LBA;"; + size_t hash = ComputeModifiedUtf8Hash(descriptor); + uint32_t class_def_idx = table->Lookup(descriptor, hash); + ASSERT_EQ(kDexNoIndex, class_def_idx); +} + +TEST_F(TypeLookupTableTest, FindNonExistingClassWithCollisions) { + ScopedObjectAccess soa(Thread::Current()); + std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup")); + std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file)); + ASSERT_NE(nullptr, table.get()); + const char* descriptor = "LDA;"; + size_t hash = ComputeModifiedUtf8Hash(descriptor); + uint32_t class_def_idx = table->Lookup(descriptor, hash); + ASSERT_EQ(kDexNoIndex, class_def_idx); +} + +TEST_F(TypeLookupTableTest, FindClassNoCollisions) { + ScopedObjectAccess soa(Thread::Current()); + std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup")); + std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file)); + ASSERT_NE(nullptr, table.get()); + const char* descriptor = "LC;"; + size_t hash = ComputeModifiedUtf8Hash(descriptor); + uint32_t class_def_idx = table->Lookup(descriptor, hash); + ASSERT_EQ(2U, class_def_idx); +} + +TEST_F(TypeLookupTableTest, FindClassWithCollisions) { + ScopedObjectAccess soa(Thread::Current()); + std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup")); + std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file)); + ASSERT_NE(nullptr, table.get()); + const char* descriptor = "LAB;"; + size_t hash = ComputeModifiedUtf8Hash(descriptor); + uint32_t class_def_idx = table->Lookup(descriptor, hash); + ASSERT_EQ(1U, class_def_idx); +} + +} // namespace art diff --git a/test/530-checker-lse/src/Main.java b/test/530-checker-lse/src/Main.java index 924ff6773f..c766aaa6c9 100644 --- a/test/530-checker-lse/src/Main.java +++ b/test/530-checker-lse/src/Main.java @@ -22,7 +22,7 @@ class Circle { return radius * radius * Math.PI; } private double radius; -} +}; class TestClass { TestClass() { @@ -36,29 +36,16 @@ class TestClass { volatile int k; TestClass next; static int si; -} +}; class SubTestClass extends TestClass { int k; -} +}; class TestClass2 { int i; int j; -} - -class Finalizable { - static boolean sVisited = false; - static final int VALUE = 0xbeef; - int i; - - protected void finalize() { - if (i != VALUE) { - System.out.println("Where is the beef?"); - } - sVisited = true; - } -} +}; public class Main { @@ -69,7 +56,7 @@ public class Main { /// CHECK-START: double Main.calcCircleArea(double) load_store_elimination (after) /// CHECK: NewInstance - /// CHECK-NOT: InstanceFieldSet + /// CHECK: InstanceFieldSet /// CHECK-NOT: InstanceFieldGet static double calcCircleArea(double radius) { @@ -130,7 +117,7 @@ public class Main { /// CHECK: InstanceFieldGet /// CHECK: InstanceFieldSet /// CHECK: NewInstance - /// CHECK-NOT: InstanceFieldSet + /// CHECK: InstanceFieldSet /// CHECK-NOT: InstanceFieldGet // A new allocation shouldn't alias with pre-existing values. @@ -236,7 +223,7 @@ public class Main { /// CHECK-START: int Main.test8() load_store_elimination (after) /// CHECK: NewInstance - /// CHECK-NOT: InstanceFieldSet + /// CHECK: InstanceFieldSet /// CHECK: InvokeVirtual /// CHECK-NOT: NullCheck /// CHECK-NOT: InstanceFieldGet @@ -394,8 +381,8 @@ public class Main { /// CHECK-START: int Main.test16() load_store_elimination (after) /// CHECK: NewInstance - /// CHECK-NOT: InstanceFieldSet - /// CHECK-NOT: InstanceFieldGet + /// CHECK-NOT: StaticFieldSet + /// CHECK-NOT: StaticFieldGet // Test inlined constructor. static int test16() { @@ -411,8 +398,8 @@ public class Main { /// CHECK-START: int Main.test17() load_store_elimination (after) /// CHECK: <<Const0:i\d+>> IntConstant 0 /// CHECK: NewInstance - /// CHECK-NOT: InstanceFieldSet - /// CHECK-NOT: InstanceFieldGet + /// CHECK-NOT: StaticFieldSet + /// CHECK-NOT: StaticFieldGet /// CHECK: Return [<<Const0>>] // Test getting default value. @@ -468,55 +455,6 @@ public class Main { return obj; } - /// CHECK-START: void Main.testFinalizable() load_store_elimination (before) - /// CHECK: NewInstance - /// CHECK: InstanceFieldSet - - /// CHECK-START: void Main.testFinalizable() load_store_elimination (after) - /// CHECK: NewInstance - /// CHECK: InstanceFieldSet - - // Allocations and stores into finalizable objects cannot be eliminated. - static void testFinalizable() { - Finalizable finalizable = new Finalizable(); - finalizable.i = Finalizable.VALUE; - } - - static java.lang.ref.WeakReference<Object> getWeakReference() { - return new java.lang.ref.WeakReference<>(new Object()); - } - - static void testFinalizableByForcingGc() { - testFinalizable(); - java.lang.ref.WeakReference<Object> reference = getWeakReference(); - - Runtime runtime = Runtime.getRuntime(); - for (int i = 0; i < 20; ++i) { - runtime.gc(); - System.runFinalization(); - try { - Thread.sleep(1); - } catch (InterruptedException e) { - throw new AssertionError(e); - } - - // Check to see if the weak reference has been garbage collected. - if (reference.get() == null) { - // A little bit more sleep time to make sure. - try { - Thread.sleep(100); - } catch (InterruptedException e) { - throw new AssertionError(e); - } - if (!Finalizable.sVisited) { - System.out.println("finalize() not called."); - } - return; - } - } - System.out.println("testFinalizableByForcingGc() failed to force gc."); - } - public static void assertIntEquals(int expected, int result) { if (expected != result) { throw new Error("Expected: " + expected + ", found: " + result); @@ -570,6 +508,5 @@ public class Main { float[] fa2 = { 1.8f }; assertFloatEquals(test19(fa1, fa2), 1.8f); assertFloatEquals(test20().i, 0); - testFinalizableByForcingGc(); } } diff --git a/test/541-regression-inlined-deopt/expected.txt b/test/541-regression-inlined-deopt/expected.txt new file mode 100644 index 0000000000..e69de29bb2 --- /dev/null +++ b/test/541-regression-inlined-deopt/expected.txt diff --git a/test/541-regression-inlined-deopt/info.txt b/test/541-regression-inlined-deopt/info.txt new file mode 100644 index 0000000000..209588fe05 --- /dev/null +++ b/test/541-regression-inlined-deopt/info.txt @@ -0,0 +1,4 @@ +Regression test for deopt from optimized code which would use the top-level +stack map for deopting inlined frames. Test case is written in smali for full +control over vregs because the previous test 449 would pass because the vreg +maps at the various inlining depths were similar. diff --git a/test/541-regression-inlined-deopt/smali/TestCase.smali b/test/541-regression-inlined-deopt/smali/TestCase.smali new file mode 100644 index 0000000000..a109775dfe --- /dev/null +++ b/test/541-regression-inlined-deopt/smali/TestCase.smali @@ -0,0 +1,55 @@ +# Copyright (C) 2015 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. + +.class public LTestCase; +.super Ljava/lang/Object; + +.method private static $inline$depth1([I)V + .registers 3 + + # Expects array in v2. + + const v0, 0x0 + + const v1, 0x3 + aput v0, p0, v1 + + const v1, 0x4 + aput v0, p0, v1 + + return-void +.end method + +.method private static $inline$depth0([I)V + .registers 1 + + # Expects array in v0. + + invoke-static {p0}, LTestCase;->$inline$depth1([I)V + return-void +.end method + +.method public static foo()V + .registers 10 + + # Create a new array short enough to throw AIOOB in $inline$depth1. + # Make sure the reference is not stored in the same vreg as used by + # the inlined methods. + + const v5, 0x3 + new-array v6, v5, [I + + invoke-static {v6}, LTestCase;->$inline$depth0([I)V + return-void +.end method diff --git a/test/541-regression-inlined-deopt/src/Main.java b/test/541-regression-inlined-deopt/src/Main.java new file mode 100644 index 0000000000..fa79590e65 --- /dev/null +++ b/test/541-regression-inlined-deopt/src/Main.java @@ -0,0 +1,36 @@ +/* + * Copyright (C) 2015 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. + */ + +import java.lang.reflect.*; + +public class Main { + + // Workaround for b/18051191. + class InnerClass {} + + public static void main(String[] args) throws Throwable { + try { + Class<?> c = Class.forName("TestCase"); + Method m = c.getMethod("foo"); + m.invoke(null, (Object[]) null); + } catch (InvocationTargetException ex) { + // Code should have thrown AIOOB. + if (!(ex.getCause() instanceof ArrayIndexOutOfBoundsException)) { + throw ex; + } + } + } +} diff --git a/test/Lookup/A.java b/test/Lookup/A.java new file mode 100644 index 0000000000..666ba181d9 --- /dev/null +++ b/test/Lookup/A.java @@ -0,0 +1,17 @@ +/* + * Copyright (C) 2011 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. + */ + +class A {} diff --git a/test/Lookup/AB.java b/test/Lookup/AB.java new file mode 100644 index 0000000000..b231708111 --- /dev/null +++ b/test/Lookup/AB.java @@ -0,0 +1,17 @@ +/* + * Copyright (C) 2011 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. + */ + +class AB {} diff --git a/test/Lookup/C.java b/test/Lookup/C.java new file mode 100644 index 0000000000..5b90069262 --- /dev/null +++ b/test/Lookup/C.java @@ -0,0 +1,17 @@ +/* + * Copyright (C) 2011 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. + */ + +class C {} |