diff options
20 files changed, 856 insertions, 701 deletions
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc index 074f249fe1..0ebf4bec0a 100644 --- a/compiler/optimizing/code_generator.cc +++ b/compiler/optimizing/code_generator.cc @@ -70,9 +70,6 @@ namespace art { -// If true, we record the static and direct invokes in the invoke infos. -static constexpr bool kEnableDexLayoutOptimizations = false; - // Return whether a location is consistent with a type. static bool CheckType(DataType::Type type, Location location) { if (location.IsFpuRegister() @@ -1136,15 +1133,6 @@ void CodeGenerator::RecordPcInfo(HInstruction* instruction, locations->GetStackMask(), kind); EmitEnvironment(environment, slow_path); - // Record invoke info, the common case for the trampoline is super and static invokes. Only - // record these to reduce oat file size. - if (kEnableDexLayoutOptimizations) { - if (instruction->IsInvokeStaticOrDirect()) { - HInvoke* const invoke = instruction->AsInvokeStaticOrDirect(); - DCHECK(environment != nullptr); - stack_map_stream->AddInvoke(invoke->GetInvokeType(), invoke->GetDexMethodIndex()); - } - } stack_map_stream->EndStackMapEntry(); if (osr) { diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc index d1c83ce625..02c995a833 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -5678,14 +5678,6 @@ void InstructionCodeGeneratorARM64::GenerateIntRemForPower2Denom(HRem *instructi } } -void InstructionCodeGeneratorARM64::GenerateIntRemForOneOrMinusOneDenom(HRem *instruction) { - int64_t imm = Int64FromLocation(instruction->GetLocations()->InAt(1)); - DCHECK(imm == 1 || imm == -1) << imm; - - Register out = OutputRegister(instruction); - __ Mov(out, 0); -} - void InstructionCodeGeneratorARM64::GenerateIntRemForConstDenom(HRem *instruction) { int64_t imm = Int64FromLocation(instruction->GetLocations()->InAt(1)); @@ -5695,10 +5687,12 @@ void InstructionCodeGeneratorARM64::GenerateIntRemForConstDenom(HRem *instructio return; } - if (imm == 1 || imm == -1) { - // TODO: These cases need to be optimized in InstructionSimplifier - GenerateIntRemForOneOrMinusOneDenom(instruction); - } else if (IsPowerOfTwo(AbsOrMin(imm))) { + if (IsPowerOfTwo(AbsOrMin(imm))) { + // Cases imm == -1 or imm == 1 are handled in constant folding by + // InstructionWithAbsorbingInputSimplifier. + // If the cases have survided till code generation they are handled in + // GenerateIntRemForPower2Denom becauses -1 and 1 are the power of 2 (2^0). + // The correct code is generated for them, just more instructions. GenerateIntRemForPower2Denom(instruction); } else { DCHECK(imm < -2 || imm > 2) << imm; diff --git a/compiler/optimizing/code_generator_arm64.h b/compiler/optimizing/code_generator_arm64.h index c44fa48066..93bab3180c 100644 --- a/compiler/optimizing/code_generator_arm64.h +++ b/compiler/optimizing/code_generator_arm64.h @@ -327,7 +327,6 @@ class InstructionCodeGeneratorARM64 : public InstructionCodeGenerator { void GenerateIntDivForPower2Denom(HDiv *instruction); void GenerateIntRem(HRem* instruction); void GenerateIntRemForConstDenom(HRem *instruction); - void GenerateIntRemForOneOrMinusOneDenom(HRem *instruction); void GenerateIntRemForPower2Denom(HRem *instruction); void HandleGoto(HInstruction* got, HBasicBlock* successor); diff --git a/compiler/optimizing/nodes_vector.h b/compiler/optimizing/nodes_vector.h index c5e9a8d036..95fb5ab76a 100644 --- a/compiler/optimizing/nodes_vector.h +++ b/compiler/optimizing/nodes_vector.h @@ -931,6 +931,9 @@ class HVecSetScalars FINAL : public HVecOperation { // Multiplies every component in the two vectors, adds the result vector to the accumulator vector, // viz. [ a1, .. , an ] + [ x1, .. , xn ] * [ y1, .. , yn ] = [ a1 + x1 * y1, .. , an + xn * yn ]. +// For floating point types, Java rounding behavior must be preserved; the products are rounded to +// the proper precision before being added. "Fused" multiply-add operations available on several +// architectures are not usable since they would violate Java language rules. class HVecMultiplyAccumulate FINAL : public HVecOperation { public: HVecMultiplyAccumulate(ArenaAllocator* allocator, @@ -953,6 +956,9 @@ class HVecMultiplyAccumulate FINAL : public HVecOperation { DCHECK(HasConsistentPackedTypes(accumulator, packed_type)); DCHECK(HasConsistentPackedTypes(mul_left, packed_type)); DCHECK(HasConsistentPackedTypes(mul_right, packed_type)); + // Remove the following if we add an architecture that supports floating point multiply-add + // with Java-compatible rounding. + DCHECK(DataType::IsIntegralType(packed_type)); SetRawInputAt(0, accumulator); SetRawInputAt(1, mul_left); SetRawInputAt(2, mul_right); diff --git a/compiler/optimizing/stack_map_stream.cc b/compiler/optimizing/stack_map_stream.cc index 3e1a36dc9b..a65fbcc514 100644 --- a/compiler/optimizing/stack_map_stream.cc +++ b/compiler/optimizing/stack_map_stream.cc @@ -156,26 +156,6 @@ void StackMapStream::EndStackMapEntry() { } } -void StackMapStream::AddInvoke(InvokeType invoke_type, uint32_t dex_method_index) { - uint32_t packed_native_pc = current_stack_map_[StackMap::kPackedNativePc]; - size_t invoke_info_index = invoke_infos_.size(); - BitTableBuilder<InvokeInfo>::Entry entry; - entry[InvokeInfo::kPackedNativePc] = packed_native_pc; - entry[InvokeInfo::kInvokeType] = invoke_type; - entry[InvokeInfo::kMethodInfoIndex] = method_infos_.Dedup({dex_method_index}); - invoke_infos_.Add(entry); - - if (kVerifyStackMaps) { - dchecks_.emplace_back([=](const CodeInfo& code_info) { - InvokeInfo invoke_info = code_info.GetInvokeInfo(invoke_info_index); - CHECK_EQ(invoke_info.GetNativePcOffset(instruction_set_), - StackMap::UnpackNativePc(packed_native_pc, instruction_set_)); - CHECK_EQ(invoke_info.GetInvokeType(), invoke_type); - CHECK_EQ(method_infos_[invoke_info.GetMethodInfoIndex()][0], dex_method_index); - }); - } -} - void StackMapStream::BeginInlineInfoEntry(ArtMethod* method, uint32_t dex_pc, uint32_t num_dex_registers, @@ -333,7 +313,6 @@ size_t StackMapStream::PrepareForFillIn() { stack_maps_.Encode(out); register_masks_.Encode(out); stack_masks_.Encode(out); - invoke_infos_.Encode(out); inline_infos_.Encode(out); dex_register_masks_.Encode(out); dex_register_maps_.Encode(out); diff --git a/compiler/optimizing/stack_map_stream.h b/compiler/optimizing/stack_map_stream.h index ed865b12f7..203c2cdf84 100644 --- a/compiler/optimizing/stack_map_stream.h +++ b/compiler/optimizing/stack_map_stream.h @@ -42,7 +42,6 @@ class StackMapStream : public ValueObject { stack_maps_(allocator), register_masks_(allocator), stack_masks_(allocator), - invoke_infos_(allocator), inline_infos_(allocator), dex_register_masks_(allocator), dex_register_maps_(allocator), @@ -76,8 +75,6 @@ class StackMapStream : public ValueObject { current_dex_registers_.push_back(DexRegisterLocation(kind, value)); } - void AddInvoke(InvokeType type, uint32_t dex_method_index); - void BeginInlineInfoEntry(ArtMethod* method, uint32_t dex_pc, uint32_t num_dex_registers, @@ -112,7 +109,6 @@ class StackMapStream : public ValueObject { BitTableBuilder<StackMap> stack_maps_; BitTableBuilder<RegisterMask> register_masks_; BitmapTableBuilder stack_masks_; - BitTableBuilder<InvokeInfo> invoke_infos_; BitTableBuilder<InlineInfo> inline_infos_; BitmapTableBuilder dex_register_masks_; BitTableBuilder<MaskInfo> dex_register_maps_; diff --git a/compiler/optimizing/stack_map_test.cc b/compiler/optimizing/stack_map_test.cc index 9ed90a4839..42f978988f 100644 --- a/compiler/optimizing/stack_map_test.cc +++ b/compiler/optimizing/stack_map_test.cc @@ -758,56 +758,4 @@ TEST(StackMapTest, TestDeduplicateStackMask) { stack_map2.GetStackMaskIndex()); } -TEST(StackMapTest, TestInvokeInfo) { - MallocArenaPool pool; - ArenaStack arena_stack(&pool); - ScopedArenaAllocator allocator(&arena_stack); - StackMapStream stream(&allocator, kRuntimeISA); - stream.BeginMethod(32, 0, 0, 0); - - ArenaBitVector sp_mask(&allocator, 0, true); - sp_mask.SetBit(1); - stream.BeginStackMapEntry(0, 4 * kPcAlign, 0x3, &sp_mask); - stream.AddInvoke(kSuper, 1); - stream.EndStackMapEntry(); - stream.BeginStackMapEntry(0, 8 * kPcAlign, 0x3, &sp_mask); - stream.AddInvoke(kStatic, 3); - stream.EndStackMapEntry(); - stream.BeginStackMapEntry(0, 16 * kPcAlign, 0x3, &sp_mask); - stream.AddInvoke(kDirect, 65535); - stream.EndStackMapEntry(); - - stream.EndMethod(); - const size_t code_info_size = stream.PrepareForFillIn(); - MemoryRegion code_info_region(allocator.Alloc(code_info_size, kArenaAllocMisc), code_info_size); - stream.FillInCodeInfo(code_info_region); - - const size_t method_info_size = stream.ComputeMethodInfoSize(); - MemoryRegion method_info_region(allocator.Alloc(method_info_size, kArenaAllocMisc), - method_info_size); - stream.FillInMethodInfo(method_info_region); - - CodeInfo code_info(code_info_region); - MethodInfo method_info(method_info_region.begin()); - ASSERT_EQ(3u, code_info.GetNumberOfStackMaps()); - - InvokeInfo invoke1(code_info.GetInvokeInfoForNativePcOffset(4 * kPcAlign)); - InvokeInfo invoke2(code_info.GetInvokeInfoForNativePcOffset(8 * kPcAlign)); - InvokeInfo invoke3(code_info.GetInvokeInfoForNativePcOffset(16 * kPcAlign)); - InvokeInfo invoke_invalid(code_info.GetInvokeInfoForNativePcOffset(12)); - EXPECT_FALSE(invoke_invalid.IsValid()); // No entry for that index. - EXPECT_TRUE(invoke1.IsValid()); - EXPECT_TRUE(invoke2.IsValid()); - EXPECT_TRUE(invoke3.IsValid()); - EXPECT_EQ(invoke1.GetInvokeType(), kSuper); - EXPECT_EQ(invoke1.GetMethodIndex(method_info), 1u); - EXPECT_EQ(invoke1.GetNativePcOffset(kRuntimeISA), 4u * kPcAlign); - EXPECT_EQ(invoke2.GetInvokeType(), kStatic); - EXPECT_EQ(invoke2.GetMethodIndex(method_info), 3u); - EXPECT_EQ(invoke2.GetNativePcOffset(kRuntimeISA), 8u * kPcAlign); - EXPECT_EQ(invoke3.GetInvokeType(), kDirect); - EXPECT_EQ(invoke3.GetMethodIndex(method_info), 65535u); - EXPECT_EQ(invoke3.GetNativePcOffset(kRuntimeISA), 16u * kPcAlign); -} - } // namespace art diff --git a/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc b/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc index 379292db71..505e183ced 100644 --- a/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc +++ b/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc @@ -357,30 +357,6 @@ class QuickArgumentVisitor { } } - static bool GetInvokeType(ArtMethod** sp, InvokeType* invoke_type, uint32_t* dex_method_index) - REQUIRES_SHARED(Locks::mutator_lock_) { - DCHECK((*sp)->IsCalleeSaveMethod()); - constexpr size_t callee_frame_size = - RuntimeCalleeSaveFrame::GetFrameSize(CalleeSaveType::kSaveRefsAndArgs); - ArtMethod** caller_sp = reinterpret_cast<ArtMethod**>( - reinterpret_cast<uintptr_t>(sp) + callee_frame_size); - uintptr_t outer_pc = QuickArgumentVisitor::GetCallingPc(sp); - const OatQuickMethodHeader* current_code = (*caller_sp)->GetOatQuickMethodHeader(outer_pc); - if (!current_code->IsOptimized()) { - return false; - } - uintptr_t outer_pc_offset = current_code->NativeQuickPcOffset(outer_pc); - CodeInfo code_info(current_code); - MethodInfo method_info = current_code->GetOptimizedMethodInfo(); - InvokeInfo invoke(code_info.GetInvokeInfoForNativePcOffset(outer_pc_offset)); - if (invoke.IsValid()) { - *invoke_type = static_cast<InvokeType>(invoke.GetInvokeType()); - *dex_method_index = invoke.GetMethodIndex(method_info); - return true; - } - return false; - } - // For the given quick ref and args quick frame, return the caller's PC. static uintptr_t GetCallingPc(ArtMethod** sp) REQUIRES_SHARED(Locks::mutator_lock_) { DCHECK((*sp)->IsCalleeSaveMethod()); @@ -1333,14 +1309,7 @@ extern "C" const void* artQuickResolutionTrampoline( caller = QuickArgumentVisitor::GetCallingMethod(sp); called_method.dex_file = caller->GetDexFile(); - InvokeType stack_map_invoke_type; - uint32_t stack_map_dex_method_idx; - const bool found_stack_map = QuickArgumentVisitor::GetInvokeType(sp, - &stack_map_invoke_type, - &stack_map_dex_method_idx); - // For debug builds, we make sure both of the paths are consistent by also looking at the dex - // code. - if (!found_stack_map || kIsDebugBuild) { + { uint32_t dex_pc = QuickArgumentVisitor::GetCallingDexPc(sp); CodeItemInstructionAccessor accessor(caller->DexInstructions()); CHECK_LT(dex_pc, accessor.InsnsSizeInCodeUnits()); @@ -1394,23 +1363,8 @@ extern "C" const void* artQuickResolutionTrampoline( UNREACHABLE(); } called_method.index = (is_range) ? instr.VRegB_3rc() : instr.VRegB_35c(); - // Check that the invoke matches what we expected, note that this path only happens for debug - // builds. - if (found_stack_map) { - DCHECK_EQ(stack_map_invoke_type, invoke_type); - if (invoke_type != kSuper) { - // Super may be sharpened. - DCHECK_EQ(stack_map_dex_method_idx, called_method.index) - << called_method.dex_file->PrettyMethod(stack_map_dex_method_idx) << " " - << called_method.PrettyMethod(); - } - } else { - VLOG(dex) << "Accessed dex file for invoke " << invoke_type << " " - << called_method.index; - } - } else { - invoke_type = stack_map_invoke_type; - called_method.index = stack_map_dex_method_idx; + VLOG(dex) << "Accessed dex file for invoke " << invoke_type << " " + << called_method.index; } } else { invoke_type = kStatic; diff --git a/runtime/oat.h b/runtime/oat.h index ef2a5d72ed..f8ec665683 100644 --- a/runtime/oat.h +++ b/runtime/oat.h @@ -32,8 +32,8 @@ class InstructionSetFeatures; class PACKED(4) OatHeader { public: static constexpr uint8_t kOatMagic[] = { 'o', 'a', 't', '\n' }; - // Last oat version changed reason: Added AllocStringObject Quick Entrypoint. - static constexpr uint8_t kOatVersion[] = { '1', '5', '3', '\0' }; + // Last oat version changed reason: Remove InvokeInfo from stack maps. + static constexpr uint8_t kOatVersion[] = { '1', '5', '4', '\0' }; static constexpr const char* kImageLocationKey = "image-location"; static constexpr const char* kDex2OatCmdLineKey = "dex2oat-cmdline"; diff --git a/runtime/stack_map.cc b/runtime/stack_map.cc index 7e46eb7e47..9fa9d84993 100644 --- a/runtime/stack_map.cc +++ b/runtime/stack_map.cc @@ -41,7 +41,6 @@ void CodeInfo::Decode(const uint8_t* data) { stack_maps_.Decode(reader); register_masks_.Decode(reader); stack_masks_.Decode(reader); - invoke_infos_.Decode(reader); inline_infos_.Decode(reader); dex_register_masks_.Decode(reader); dex_register_maps_.Decode(reader); @@ -155,7 +154,6 @@ void CodeInfo::AddSizeStats(/*out*/ Stats* parent) const { AddTableSizeStats<StackMap>("StackMaps", stack_maps_, stats); AddTableSizeStats<RegisterMask>("RegisterMasks", register_masks_, stats); AddTableSizeStats<MaskInfo>("StackMasks", stack_masks_, stats); - AddTableSizeStats<InvokeInfo>("InvokeInfos", invoke_infos_, stats); AddTableSizeStats<InlineInfo>("InlineInfos", inline_infos_, stats); AddTableSizeStats<MaskInfo>("DexRegisterMasks", dex_register_masks_, stats); AddTableSizeStats<DexRegisterMapInfo>("DexRegisterMaps", dex_register_maps_, stats); @@ -224,7 +222,6 @@ void CodeInfo::Dump(VariableIndentationOutputStream* vios, DumpTable<StackMap>(vios, "StackMaps", stack_maps_, verbose); DumpTable<RegisterMask>(vios, "RegisterMasks", register_masks_, verbose); DumpTable<MaskInfo>(vios, "StackMasks", stack_masks_, verbose, true /* is_mask */); - DumpTable<InvokeInfo>(vios, "InvokeInfos", invoke_infos_, verbose); DumpTable<InlineInfo>(vios, "InlineInfos", inline_infos_, verbose); DumpTable<MaskInfo>(vios, "DexRegisterMasks", dex_register_masks_, verbose, true /* is_mask */); DumpTable<DexRegisterMapInfo>(vios, "DexRegisterMaps", dex_register_maps_, verbose); diff --git a/runtime/stack_map.h b/runtime/stack_map.h index 2f2053a52a..26b95b0c2b 100644 --- a/runtime/stack_map.h +++ b/runtime/stack_map.h @@ -208,22 +208,6 @@ class InlineInfo : public BitTableAccessor<6> { const MethodInfo& method_info) const; }; -class InvokeInfo : public BitTableAccessor<3> { - public: - BIT_TABLE_HEADER() - BIT_TABLE_COLUMN(0, PackedNativePc) - BIT_TABLE_COLUMN(1, InvokeType) - BIT_TABLE_COLUMN(2, MethodInfoIndex) - - ALWAYS_INLINE uint32_t GetNativePcOffset(InstructionSet instruction_set) const { - return StackMap::UnpackNativePc(GetPackedNativePc(), instruction_set); - } - - uint32_t GetMethodIndex(MethodInfo method_info) const { - return method_info.GetMethodIndex(GetMethodInfoIndex()); - } -}; - class MaskInfo : public BitTableAccessor<1> { public: BIT_TABLE_HEADER() @@ -338,10 +322,6 @@ class CodeInfo { return stack_maps_.NumRows(); } - InvokeInfo GetInvokeInfo(size_t index) const { - return invoke_infos_.GetRow(index); - } - ALWAYS_INLINE DexRegisterMap GetDexRegisterMapOf(StackMap stack_map) const { if (stack_map.HasDexRegisterMap()) { DexRegisterMap map(number_of_dex_registers_, DexRegisterLocation::Invalid()); @@ -413,15 +393,6 @@ class CodeInfo { StackMap GetStackMapForNativePcOffset(uint32_t pc, InstructionSet isa = kRuntimeISA) const; - InvokeInfo GetInvokeInfoForNativePcOffset(uint32_t native_pc_offset) { - for (InvokeInfo item : invoke_infos_) { - if (item.GetNativePcOffset(kRuntimeISA) == native_pc_offset) { - return item; - } - } - return invoke_infos_.GetInvalidRow(); - } - // Dump this CodeInfo object on `vios`. // `code_offset` is the (absolute) native PC of the compiled method. void Dump(VariableIndentationOutputStream* vios, @@ -459,7 +430,6 @@ class CodeInfo { BitTable<StackMap> stack_maps_; BitTable<RegisterMask> register_masks_; BitTable<MaskInfo> stack_masks_; - BitTable<InvokeInfo> invoke_infos_; BitTable<InlineInfo> inline_infos_; BitTable<MaskInfo> dex_register_masks_; BitTable<DexRegisterMapInfo> dex_register_maps_; diff --git a/test/411-optimizing-arith/src/RemTest.java b/test/411-optimizing-arith/src/RemTest.java index 1b31f63569..287f5d8799 100644 --- a/test/411-optimizing-arith/src/RemTest.java +++ b/test/411-optimizing-arith/src/RemTest.java @@ -89,6 +89,34 @@ public class RemTest { expectDivisionByZero(5L); expectDivisionByZero(Long.MAX_VALUE); expectDivisionByZero(Long.MIN_VALUE); + + expectEquals(0, $noinline$RemLoaded1(0)); + expectEquals(0, $noinline$RemLoaded1(1)); + expectEquals(0, $noinline$RemLoaded1(-1)); + expectEquals(0, $noinline$RemLoaded1(12345)); + expectEquals(0, $noinline$RemLoaded1(Integer.MAX_VALUE)); + expectEquals(0, $noinline$RemLoaded1(Integer.MIN_VALUE)); + + expectEquals(0, $noinline$RemLoadedN1(0)); + expectEquals(0, $noinline$RemLoadedN1(1)); + expectEquals(0, $noinline$RemLoadedN1(-1)); + expectEquals(0, $noinline$RemLoadedN1(12345)); + expectEquals(0, $noinline$RemLoadedN1(Integer.MAX_VALUE)); + expectEquals(0, $noinline$RemLoadedN1(Integer.MIN_VALUE)); + + expectEquals(0L, $noinline$RemLoaded1(0L)); + expectEquals(0L, $noinline$RemLoaded1(1L)); + expectEquals(0L, $noinline$RemLoaded1(-1L)); + expectEquals(0L, $noinline$RemLoaded1(12345L)); + expectEquals(0L, $noinline$RemLoaded1(Long.MAX_VALUE)); + expectEquals(0L, $noinline$RemLoaded1(Long.MIN_VALUE)); + + expectEquals(0L, $noinline$RemLoadedN1(0L)); + expectEquals(0L, $noinline$RemLoadedN1(1L)); + expectEquals(0L, $noinline$RemLoadedN1(-1L)); + expectEquals(0L, $noinline$RemLoadedN1(12345L)); + expectEquals(0L, $noinline$RemLoadedN1(Long.MAX_VALUE)); + expectEquals(0L, $noinline$RemLoadedN1(Long.MIN_VALUE)); } static int $opt$Rem(int a, int b) { @@ -99,6 +127,26 @@ public class RemTest { return a % 0; } + static int $noinline$RemLoaded1(int a) { + int[] v = {25, 1}; + return a % v[1]; + } + + static int $noinline$RemLoadedN1(int a) { + int [] v = {25, -1}; + return a % v[1]; + } + + static long $noinline$RemLoaded1(long a) { + long[] v = {25, 1}; + return a % v[1]; + } + + static long $noinline$RemLoadedN1(long a) { + long [] v = {25, -1}; + return a % v[1]; + } + // Modulo by literals != 0 should not generate checks. static int $opt$RemConst(int a) { return a % 4; diff --git a/test/442-checker-constant-folding/src/Main.java b/test/442-checker-constant-folding/src/Main.java index fcc3c1a852..3d9294304d 100644 --- a/test/442-checker-constant-folding/src/Main.java +++ b/test/442-checker-constant-folding/src/Main.java @@ -1150,6 +1150,41 @@ public class Main { return arg % 1; } + /// CHECK-START: int Main.RemN1(int) constant_folding (before) + /// CHECK-DAG: <<Arg:i\d+>> ParameterValue + /// CHECK-DAG: <<ConstN1:i\d+>> IntConstant -1 + /// CHECK-DAG: <<Rem:i\d+>> Rem [<<Arg>>,<<ConstN1>>] + /// CHECK-DAG: Return [<<Rem>>] + + /// CHECK-START: int Main.RemN1(int) constant_folding (after) + /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 + /// CHECK-DAG: Return [<<Const0>>] + + /// CHECK-START: int Main.RemN1(int) constant_folding (after) + /// CHECK-NOT: Rem + + public static int RemN1(int arg) { + return arg % -1; + } + + /// CHECK-START: long Main.Rem1(long) constant_folding (before) + /// CHECK-DAG: <<Arg:j\d+>> ParameterValue + /// CHECK-DAG: <<Const1:j\d+>> LongConstant 1 + /// CHECK-DAG: <<DivZeroCheck:j\d+>> DivZeroCheck [<<Const1>>] + /// CHECK-DAG: <<Rem:j\d+>> Rem [<<Arg>>,<<DivZeroCheck>>] + /// CHECK-DAG: Return [<<Rem>>] + + /// CHECK-START: long Main.Rem1(long) constant_folding (after) + /// CHECK-DAG: <<Const0:j\d+>> LongConstant 0 + /// CHECK-DAG: Return [<<Const0>>] + + /// CHECK-START: long Main.Rem1(long) constant_folding (after) + /// CHECK-NOT: Rem + + public static long Rem1(long arg) { + return arg % 1; + } + /// CHECK-START: long Main.RemN1(long) constant_folding (before) /// CHECK-DAG: <<Arg:j\d+>> ParameterValue /// CHECK-DAG: <<ConstN1:j\d+>> LongConstant -1 @@ -1597,7 +1632,26 @@ public class Main { assertIntEquals(-1, OrAllOnes(arbitrary)); assertLongEquals(0, Rem0(arbitrary)); assertIntEquals(0, Rem1(arbitrary)); + assertIntEquals(0, Rem1(0)); + assertIntEquals(0, Rem1(-1)); + assertIntEquals(0, Rem1(Integer.MAX_VALUE)); + assertIntEquals(0, Rem1(Integer.MIN_VALUE)); + assertIntEquals(0, RemN1(arbitrary)); + assertIntEquals(0, RemN1(0)); + assertIntEquals(0, RemN1(-1)); + assertIntEquals(0, RemN1(Integer.MAX_VALUE)); + assertIntEquals(0, RemN1(Integer.MIN_VALUE)); + assertIntEquals(0, RemN1(arbitrary)); + assertLongEquals(0, Rem1((long)arbitrary)); + assertLongEquals(0, Rem1(0L)); + assertLongEquals(0, Rem1(-1L)); + assertLongEquals(0, Rem1(Long.MAX_VALUE)); + assertLongEquals(0, Rem1(Long.MIN_VALUE)); assertLongEquals(0, RemN1(arbitrary)); + assertLongEquals(0, RemN1(0L)); + assertLongEquals(0, RemN1(-1L)); + assertLongEquals(0, RemN1(Long.MAX_VALUE)); + assertLongEquals(0, RemN1(Long.MIN_VALUE)); assertIntEquals(0, Shl0(arbitrary)); assertLongEquals(0, ShlLong0WithInt(arbitrary)); assertLongEquals(0, Shr0(arbitrary)); diff --git a/tools/ahat/etc/ahat_api.txt b/tools/ahat/etc/ahat_api.txt index f60c1a84fa..c30d501aaf 100644 --- a/tools/ahat/etc/ahat_api.txt +++ b/tools/ahat/etc/ahat_api.txt @@ -8,7 +8,20 @@ package com.android.ahat { package com.android.ahat.dominators { - public class DominatorsComputation { + public class Dominators<Node> { + ctor public Dominators(com.android.ahat.dominators.Dominators.Graph); + method public void computeDominators(Node); + method public com.android.ahat.dominators.Dominators progress(com.android.ahat.progress.Progress, long); + } + + public static abstract interface Dominators.Graph<Node> { + method public abstract java.lang.Object getDominatorsComputationState(Node); + method public abstract java.lang.Iterable<? extends Node> getReferencesForDominators(Node); + method public abstract void setDominator(Node, Node); + method public abstract void setDominatorsComputationState(Node, java.lang.Object); + } + + public deprecated class DominatorsComputation { method public static void computeDominators(com.android.ahat.dominators.DominatorsComputation.Node); method public static void computeDominators(com.android.ahat.dominators.DominatorsComputation.Node, com.android.ahat.progress.Progress, long); } @@ -50,7 +63,7 @@ package com.android.ahat.heapdump { method public boolean isPlaceHolder(); } - public abstract class AhatInstance implements com.android.ahat.heapdump.Diffable com.android.ahat.dominators.DominatorsComputation.Node { + public abstract class AhatInstance implements com.android.ahat.heapdump.Diffable { method public com.android.ahat.heapdump.AhatArrayInstance asArrayInstance(); method public java.awt.image.BufferedImage asBitmap(); method public com.android.ahat.heapdump.AhatClassInstance asClassInstance(); @@ -64,7 +77,6 @@ package com.android.ahat.heapdump { method public com.android.ahat.heapdump.AhatClassObj getClassObj(); method public java.lang.String getDexCacheLocation(int); method public java.util.List<com.android.ahat.heapdump.AhatInstance> getDominated(); - method public java.lang.Object getDominatorsComputationState(); method public com.android.ahat.heapdump.Value getField(java.lang.String); method public deprecated java.util.List<com.android.ahat.heapdump.AhatInstance> getHardReverseReferences(); method public com.android.ahat.heapdump.AhatHeap getHeap(); @@ -73,7 +85,6 @@ package com.android.ahat.heapdump { method public java.util.List<com.android.ahat.heapdump.PathElement> getPathFromGcRoot(); method public com.android.ahat.heapdump.Reachability getReachability(); method public com.android.ahat.heapdump.AhatInstance getRefField(java.lang.String); - method public java.lang.Iterable<? extends com.android.ahat.dominators.DominatorsComputation.Node> getReferencesForDominators(); method public com.android.ahat.heapdump.AhatInstance getReferent(); method public com.android.ahat.heapdump.Size getRetainedSize(com.android.ahat.heapdump.AhatHeap); method public java.util.List<com.android.ahat.heapdump.AhatInstance> getReverseReferences(); @@ -90,8 +101,6 @@ package com.android.ahat.heapdump { method public boolean isStronglyReachable(); method public boolean isUnreachable(); method public deprecated boolean isWeaklyReachable(); - method public void setDominator(com.android.ahat.dominators.DominatorsComputation.Node); - method public void setDominatorsComputationState(java.lang.Object); method public abstract java.lang.String toString(); } diff --git a/tools/ahat/src/main/com/android/ahat/dominators/Dominators.java b/tools/ahat/src/main/com/android/ahat/dominators/Dominators.java new file mode 100644 index 0000000000..dda0e830bd --- /dev/null +++ b/tools/ahat/src/main/com/android/ahat/dominators/Dominators.java @@ -0,0 +1,476 @@ +/* + * Copyright (C) 2017 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. + */ + +package com.android.ahat.dominators; + +import com.android.ahat.progress.NullProgress; +import com.android.ahat.progress.Progress; +import java.util.ArrayDeque; +import java.util.Arrays; +import java.util.Deque; +import java.util.Queue; + +/** + * Computes the immediate dominators of a directed graph. It can be used with + * any directed graph data structure that implements the + * {@link Dominators.Graph} interface and has some root node with no incoming + * edges. + */ +public class Dominators<Node> { + private final Graph<Node> graph; + + private Progress progress = new NullProgress(); + private long numNodes = 0; + + /** + * Interface for a directed graph to perform immediate dominators + * computation on. + * The dominators computation can be used with directed graph data + * structures that implement this <code>Graph</code> interface. To use the + * dominators computation on your graph, you must make the following + * functionality available to the dominators computation: + * <ul> + * <li>Efficiently mapping from node to associated internal dominators + * computation state using the + * {@link #setDominatorsComputationState setDominatorsComputationState} and + * {@link #getDominatorsComputationState getDominatorsComputationState} methods. + * <li>Iterating over all outgoing edges of an node using the + * {@link #getReferencesForDominators getReferencesForDominators} method. + * <li>Setting the computed dominator for a node using the + * {@link #setDominator setDominator} method. + * </ul> + */ + public interface Graph<Node> { + /** + * Associates the given dominator state with the given node. Subsequent + * calls to + * {@link #getDominatorsComputationState getDominatorsComputationState} on + * this node should return the state given here. At the conclusion of the + * dominators computation, this method will be called for + * each node with <code>state</code> set to null. + * + * @param node the node to associate dominator state + * @param state the dominator state to associate with the node + */ + void setDominatorsComputationState(Node node, Object state); + + /** + * Returns the dominator state most recently associated with the given node + * by a call to {@link #setDominatorsComputationState setDominatorsComputationState}. + * If <code>setDominatorsComputationState</code> has not yet been called + * on this node for this dominators computation, this method should return + * null. + * + * @param node the node to get the dominator state for + * @return the associated dominator state + */ + Object getDominatorsComputationState(Node node); + + /** + * Returns a collection of nodes referenced from the given node, for the + * purposes of computing dominators. This method will be called at most + * once for each node reachable from the root node of the dominators + * computation. + * + * @param node the node to get the references for + * @return an iterable collection of the nodes with an incoming edge from + * the node. + */ + Iterable<? extends Node> getReferencesForDominators(Node node); + + /** + * Sets the dominator for the given node based on the results of the + * dominators computation. + * + * @param node the node to set the dominator for + * @param dominator the computed immediate dominator of the node + */ + void setDominator(Node node, Node dominator); + } + + /** + * Construct an object to do dominators computation on the given graph. + * + * @param graph the graph to compute the dominators of + */ + public Dominators(Graph graph) { + this.graph = graph; + } + + /** + * Sets up a progress tracker for the dominators computation. + * + * @param progress the progress tracker to use + * @param numNodes an upper bound on the number of nodes in the graph + * @return this Dominators object + */ + public Dominators progress(Progress progress, long numNodes) { + this.progress = progress; + this.numNodes = numNodes; + return this; + } + + // NodeS is information associated with a particular node for the + // purposes of computing dominators. + // By convention we use the suffix 'S' to name instances of NodeS. + private static class NodeS { + // The node that this NodeS is associated with. + public Object node; + + // Unique identifier for this node, in increasing order based on the order + // this node was visited in a depth first search from the root. In + // particular, given nodes A and B, if A.id > B.id, then A cannot be a + // dominator of B. + public long id; + + // The largest id of all nodes reachable from this node. + // If foo.id > this.maxReachableId, then foo is not reachable from this + // node. + public long maxReachableId; + + // The set of ids of nodes that have references to this node. + public IdSet inRefIds = new IdSet(); + + // The current candidate dominator for this node. + // The true immediate dominator of this node must have id <= domS.id. + public NodeS domS; + + // The previous candidate dominator for this node. + // Invariant: + // * There are no nodes xS reachable from this node on a path of nodes + // with increasing ids (not counting xS.id) for which + // this.id > xS.domS.id > this.oldDomS.id. + // This ensures that when all nodes xS satisfy xS.domS == xS.oldDomS, we + // have found the true immediate dominator of each node. + // + // Note: We only use this field to tell if this node is scheduled to be + // revisited. We could replace it with a boolean to save space, but it + // probably doesn't save that much space and it's easier to explain the + // algorithm if we can refer to this field. + public NodeS oldDomS; + + // The set of nodes that this node is the candidate immediate dominator + // of. More precisely, the set of nodes xS such that xS.domS == this. + public NodeSet dominated = new NodeSet(); + + // The set of nodes that this node is the old candidate immediate + // dominator of that need to be revisited. Specifically, the set of nodes + // xS such that: + // xS.oldDomS == this && xS.oldDomS != xS.domS. + // + // The empty set is represented as null instead of an empty NodeSet to + // save memory. + // Invariant: + // If revisit != null, this node is on the global list of nodes to be + // revisited. + public NodeSet revisit = null; + + // Distance from the root to this node. Used for purposes of tracking + // progress only. + public long depth; + } + + // A collection of node ids. + private static class IdSet { + private int size = 0; + private long[] ids = new long[4]; + + // Adds an id to the set. + public void add(long id) { + if (size == ids.length) { + ids = Arrays.copyOf(ids, size * 2); + } + ids[size++] = id; + } + + // Returns the most recent id added to the set. Behavior is undefined if + // the set is empty. + public long last() { + assert size != 0; + return ids[size - 1]; + } + + // Returns true if the set contains an id in the range [low, high] + // inclusive, false otherwise. + public boolean hasIdInRange(long low, long high) { + for (int i = 0; i < size; ++i) { + if (low <= ids[i] && ids[i] <= high) { + return true; + } + } + return false; + } + } + + // An unordered set of nodes data structure supporting efficient iteration + // over elements. The bulk of the time spent in the dominators algorithm is + // iterating over these sets. Using an array to store the set provides + // noticable performance improvements over ArrayList or a linked list. + private static class NodeSet { + public int size = 0; + public NodeS[] nodes = new NodeS[4]; + + public void add(NodeS nodeS) { + if (size == nodes.length) { + nodes = Arrays.copyOf(nodes, size * 2); + } + nodes[size++] = nodeS; + } + + public void remove(NodeS nodeS) { + for (int i = 0; i < size; ++i) { + if (nodes[i] == nodeS) { + remove(i); + break; + } + } + } + + public void remove(int index) { + nodes[index] = nodes[--size]; + nodes[size] = null; + } + } + + // A reference from a source node to a destination node to be processed + // during the initial depth-first traversal of nodes. + // + // Also used as a marker to indicate when the depth-first traversal has been + // completed for a node. In that case, srcS is the node depth-first + // traversal has been completed for, and dst will be set to null. + private static class Link<Node> { + public final NodeS srcS; + public final Node dst; + + // Constructor for a reference from srcS to dst. + public Link(NodeS srcS, Node dst) { + this.srcS = srcS; + this.dst = dst; + } + + // Constructor for a marker indicating depth-first traversal has been + // completed for srcS. + public Link(NodeS srcS) { + this.srcS = srcS; + this.dst = null; + } + } + + /** + * Computes the immediate dominators of all nodes reachable from the <code>root</code> node. + * There must not be any incoming references to the <code>root</code> node. + * <p> + * The result of this function is to call the {@link Graph#setDominator} + * function on every node reachable from the root node. + * + * @param root the root node of the dominators computation + */ + public void computeDominators(Node root) { + long id = 0; + + // The set of nodes xS such that xS.revisit != null. + // Use a Queue instead of a Set because performance will be better. We + // avoid adding nodes already on the queue by checking + // xS == null before adding the node to the queue. + Queue<NodeS> revisit = new ArrayDeque<NodeS>(); + + // Set up the root node specially. + NodeS rootS = new NodeS(); + rootS.node = root; + rootS.id = id++; + rootS.depth = 0; + graph.setDominatorsComputationState(root, rootS); + + Deque<Link<Node>> dfs = new ArrayDeque<Link<Node>>(); + dfs.push(new Link(rootS)); + for (Node child : graph.getReferencesForDominators(root)) { + dfs.push(new Link(rootS, child)); + } + + // workBound is an upper bound on the amount of work required in the + // second phase of dominators computation, used solely for the purposes of + // tracking progress. + long workBound = 0; + + // 1. Do a depth first search of the nodes, label them with ids and come + // up with initial candidate dominators for them. + progress.start("Initializing dominators", numNodes); + while (!dfs.isEmpty()) { + Link<Node> link = dfs.pop(); + + if (link.dst == null) { + // This is the marker link indicating we have now visited all + // nodes reachable from link.srcS. + link.srcS.maxReachableId = id - 1; + progress.advance(); + } else { + NodeS dstS = (NodeS)graph.getDominatorsComputationState(link.dst); + if (dstS == null) { + // We are seeing the destination node for the first time. + // The candidate dominator is the source node. + dstS = new NodeS(); + graph.setDominatorsComputationState(link.dst, dstS); + + dstS.node = link.dst; + dstS.id = id++; + dstS.inRefIds.add(link.srcS.id); + dstS.domS = link.srcS; + dstS.domS.dominated.add(dstS); + dstS.oldDomS = link.srcS; + dstS.depth = link.srcS.depth + 1; + + dfs.push(new Link<>(dstS)); + for (Node child : graph.getReferencesForDominators(link.dst)) { + dfs.push(new Link<>(dstS, child)); + } + } else { + // We have seen the destination node before. Update the state based + // on the new potential dominator. + if (dstS.inRefIds.size == 1) { + workBound += dstS.oldDomS.depth; + } + + long seenid = dstS.inRefIds.last(); + dstS.inRefIds.add(link.srcS.id); + + // Go up the dominator chain until we reach a node we haven't already + // seen with a path to dstS. + NodeS xS = link.srcS; + while (xS.id > seenid) { + xS = xS.domS; + } + + // The new dominator for dstS must have an id less than the node we + // just reached. Pull the dominator for dstS up its dominator + // chain until we find a suitable new dominator for dstS. + long domid = xS.id; + if (dstS.domS.id > domid) { + // Mark the node as needing to be revisited. + if (dstS.domS == dstS.oldDomS) { + if (dstS.oldDomS.revisit == null) { + dstS.oldDomS.revisit = new NodeSet(); + revisit.add(dstS.oldDomS); + } + dstS.oldDomS.revisit.add(dstS); + } + + // Update the node's candidate dominator. + dstS.domS.dominated.remove(dstS); + do { + dstS.domS = dstS.domS.domS; + } while (dstS.domS.id > domid); + dstS.domS.dominated.add(dstS); + } + } + } + } + progress.done(); + + // 2. Continue revisiting nodes until every node satisfies the requirement + // that domS.id == oldDomS.id. + progress.start("Resolving dominators", workBound); + while (!revisit.isEmpty()) { + NodeS oldDomS = revisit.poll(); + assert oldDomS.revisit != null; + + NodeSet nodes = oldDomS.revisit; + oldDomS.revisit = null; + + // Search for pairs of nodes nodeS, xS for which + // nodeS.id > xS.domS.id > nodeS.oldDomS.id + // and there is a path of nodes with increasing ids from nodeS to xS. + // In that case, xS.domS must be wrong, because there is a path to xS + // from the root that does not go through xS.domS: + // * There is a path from the root to nodeS.oldDomS that doesn't go + // through xS.domS. Otherwise xS.domS would be a dominator of + // nodeS.oldDomS, but it can't be because xS.domS.id > nodeS.oldDomS.id. + // * There is a path from nodeS.oldDomS to nodeS that doesn't go through + // xS.domS, because xS.domS is not a dominator of nodeS. + // * There is a path from nodeS to xS that doesn't go through xS.domS, + // because we have a path of increasing ids from nodeS to xS, none of + // which can have an id smaller than nodeS as xS.domS does. + for (int i = 0; i < oldDomS.dominated.size; ++i) { + NodeS xS = oldDomS.dominated.nodes[i]; + for (int j = 0; j < nodes.size; ++j) { + NodeS nodeS = nodes.nodes[j]; + assert nodeS.oldDomS == oldDomS; + if (isReachableAscending(nodeS, xS)) { + // Update the dominator for xS. + if (xS.domS == xS.oldDomS) { + if (xS.oldDomS.revisit == null) { + xS.oldDomS.revisit = new NodeSet(); + revisit.add(xS.oldDomS); + } + xS.oldDomS.revisit.add(xS); + } + oldDomS.dominated.remove(i--); + xS.domS = nodeS.domS; + xS.domS.dominated.add(xS); + break; + } + } + } + + // We can now safely update oldDomS for each of the nodes nodeS while + // preserving the oldDomS invariant. + for (int i = 0; i < nodes.size; ++i) { + NodeS nodeS = nodes.nodes[i]; + nodeS.oldDomS = oldDomS.oldDomS; + if (nodeS.oldDomS != nodeS.domS) { + if (nodeS.oldDomS.revisit == null) { + nodeS.oldDomS.revisit = new NodeSet(); + revisit.add(nodeS.oldDomS); + } + nodeS.oldDomS.revisit.add(nodeS); + } + } + progress.advance((oldDomS.depth - oldDomS.oldDomS.depth) * nodes.size); + } + progress.done(); + + + // 3. We have figured out the correct dominator for each node. Notify the + // user of the results by doing one last traversal of the nodes. + assert revisit.isEmpty(); + revisit.add(rootS); + while (!revisit.isEmpty()) { + NodeS nodeS = revisit.poll(); + assert nodeS.domS == nodeS.oldDomS; + assert nodeS.revisit == null; + graph.setDominatorsComputationState((Node)nodeS.node, null); + for (int i = 0; i < nodeS.dominated.size; ++i) { + NodeS xS = nodeS.dominated.nodes[i]; + graph.setDominator((Node)xS.node, (Node)nodeS.node); + revisit.add(xS); + } + } + } + + // Returns true if there is a path from srcS to dstS of nodes with ascending + // ids (not including dstS.id). + private static boolean isReachableAscending(NodeS srcS, NodeS dstS) { + if (dstS.id < srcS.id) { + // The first time we saw dstS was before we saw srcS. See if srcS is on + // the source chain for any nodes with direct references to dstS. + return dstS.inRefIds.hasIdInRange(srcS.id, srcS.maxReachableId); + } + + // Otherwise dstS is only reachable from srcS on a node with ascending ids + // if it was visited for the first time while performing the depth-first + // traversal of srcS. + return dstS.id <= srcS.maxReachableId; + } +} diff --git a/tools/ahat/src/main/com/android/ahat/dominators/DominatorsComputation.java b/tools/ahat/src/main/com/android/ahat/dominators/DominatorsComputation.java index 903211eb50..7ab52cb604 100644 --- a/tools/ahat/src/main/com/android/ahat/dominators/DominatorsComputation.java +++ b/tools/ahat/src/main/com/android/ahat/dominators/DominatorsComputation.java @@ -18,18 +18,16 @@ package com.android.ahat.dominators; import com.android.ahat.progress.NullProgress; import com.android.ahat.progress.Progress; -import java.util.ArrayDeque; -import java.util.Arrays; -import java.util.Deque; -import java.util.Queue; /** * Provides a static method for computing the immediate dominators of a * directed graph. It can be used with any directed graph data structure * that implements the {@link DominatorsComputation.Node} interface and has * some root node with no incoming edges. + * + * @deprecated Use {@link Dominators} class instead, which has a nicer interface. */ -public class DominatorsComputation { +@Deprecated public class DominatorsComputation { private DominatorsComputation() { } @@ -94,152 +92,6 @@ public class DominatorsComputation { void setDominator(Node dominator); } - // NodeS is information associated with a particular node for the - // purposes of computing dominators. - // By convention we use the suffix 'S' to name instances of NodeS. - private static class NodeS { - // The node that this NodeS is associated with. - public Node node; - - // Unique identifier for this node, in increasing order based on the order - // this node was visited in a depth first search from the root. In - // particular, given nodes A and B, if A.id > B.id, then A cannot be a - // dominator of B. - public long id; - - // The largest id of all nodes reachable from this node. - // If foo.id > this.maxReachableId, then foo is not reachable from this - // node. - public long maxReachableId; - - // The set of ids of nodes that have references to this node. - public IdSet inRefIds = new IdSet(); - - // The current candidate dominator for this node. - // The true immediate dominator of this node must have id <= domS.id. - public NodeS domS; - - // The previous candidate dominator for this node. - // Invariant: - // * There are no nodes xS reachable from this node on a path of nodes - // with increasing ids (not counting xS.id) for which - // this.id > xS.domS.id > this.oldDomS.id. - // This ensures that when all nodes xS satisfy xS.domS == xS.oldDomS, we - // have found the true immediate dominator of each node. - // - // Note: We only use this field to tell if this node is scheduled to be - // revisited. We could replace it with a boolean to save space, but it - // probably doesn't save that much space and it's easier to explain the - // algorithm if we can refer to this field. - public NodeS oldDomS; - - // The set of nodes that this node is the candidate immediate dominator - // of. More precisely, the set of nodes xS such that xS.domS == this. - public NodeSet dominated = new NodeSet(); - - // The set of nodes that this node is the old candidate immediate - // dominator of that need to be revisited. Specifically, the set of nodes - // xS such that: - // xS.oldDomS == this && xS.oldDomS != xS.domS. - // - // The empty set is represented as null instead of an empty NodeSet to - // save memory. - // Invariant: - // If revisit != null, this node is on the global list of nodes to be - // revisited. - public NodeSet revisit = null; - - // Distance from the root to this node. Used for purposes of tracking - // progress only. - public long depth; - } - - // A collection of node ids. - private static class IdSet { - private int size = 0; - private long[] ids = new long[4]; - - // Adds an id to the set. - public void add(long id) { - if (size == ids.length) { - ids = Arrays.copyOf(ids, size * 2); - } - ids[size++] = id; - } - - // Returns the most recent id added to the set. Behavior is undefined if - // the set is empty. - public long last() { - assert size != 0; - return ids[size - 1]; - } - - // Returns true if the set contains an id in the range [low, high] - // inclusive, false otherwise. - public boolean hasIdInRange(long low, long high) { - for (int i = 0; i < size; ++i) { - if (low <= ids[i] && ids[i] <= high) { - return true; - } - } - return false; - } - } - - // An unordered set of nodes data structure supporting efficient iteration - // over elements. The bulk of the time spent in the dominators algorithm is - // iterating over these sets. Using an array to store the set provides - // noticable performance improvements over ArrayList or a linked list. - private static class NodeSet { - public int size = 0; - public NodeS[] nodes = new NodeS[4]; - - public void add(NodeS nodeS) { - if (size == nodes.length) { - nodes = Arrays.copyOf(nodes, size * 2); - } - nodes[size++] = nodeS; - } - - public void remove(NodeS nodeS) { - for (int i = 0; i < size; ++i) { - if (nodes[i] == nodeS) { - remove(i); - break; - } - } - } - - public void remove(int index) { - nodes[index] = nodes[--size]; - nodes[size] = null; - } - } - - // A reference from a source node to a destination node to be processed - // during the initial depth-first traversal of nodes. - // - // Also used as a marker to indicate when the depth-first traversal has been - // completed for a node. In that case, srcS is the node depth-first - // traversal has been completed for, and dst will be set to null. - private static class Link { - public final NodeS srcS; - public final Node dst; - - // Constructor for a reference from srcS to dst. - public Link(NodeS srcS, Node dst) { - this.srcS = srcS; - this.dst = dst; - } - - // Constructor for a marker indicating depth-first traversal has been - // completed for srcS. - public Link(NodeS srcS) { - this.srcS = srcS; - this.dst = null; - } - } - /** * Computes the immediate dominators of all nodes reachable from the <code>root</code> node. * There must not be any incoming references to the <code>root</code> node. @@ -268,198 +120,28 @@ public class DominatorsComputation { * @see Node */ public static void computeDominators(Node root, Progress progress, long numNodes) { - long id = 0; - - // The set of nodes xS such that xS.revisit != null. - // Use a Queue instead of a Set because performance will be better. We - // avoid adding nodes already on the queue by checking - // xS == null before adding the node to the queue. - Queue<NodeS> revisit = new ArrayDeque<NodeS>(); - - // Set up the root node specially. - NodeS rootS = new NodeS(); - rootS.node = root; - rootS.id = id++; - rootS.depth = 0; - root.setDominatorsComputationState(rootS); - - Deque<Link> dfs = new ArrayDeque<Link>(); - dfs.push(new Link(rootS)); - for (Node child : root.getReferencesForDominators()) { - dfs.push(new Link(rootS, child)); - } - - // workBound is an upper bound on the amount of work required in the - // second phase of dominators computation, used solely for the purposes of - // tracking progress. - long workBound = 0; - - // 1. Do a depth first search of the nodes, label them with ids and come - // up with initial candidate dominators for them. - progress.start("Initializing dominators", numNodes); - while (!dfs.isEmpty()) { - Link link = dfs.pop(); - - if (link.dst == null) { - // This is the marker link indicating we have now visited all - // nodes reachable from link.srcS. - link.srcS.maxReachableId = id - 1; - progress.advance(); - } else { - NodeS dstS = (NodeS)link.dst.getDominatorsComputationState(); - if (dstS == null) { - // We are seeing the destination node for the first time. - // The candidate dominator is the source node. - dstS = new NodeS(); - link.dst.setDominatorsComputationState(dstS); - - dstS.node = link.dst; - dstS.id = id++; - dstS.inRefIds.add(link.srcS.id); - dstS.domS = link.srcS; - dstS.domS.dominated.add(dstS); - dstS.oldDomS = link.srcS; - dstS.depth = link.srcS.depth + 1; - - dfs.push(new Link(dstS)); - for (Node child : link.dst.getReferencesForDominators()) { - dfs.push(new Link(dstS, child)); - } - } else { - // We have seen the destination node before. Update the state based - // on the new potential dominator. - if (dstS.inRefIds.size == 1) { - workBound += dstS.oldDomS.depth; - } - - long seenid = dstS.inRefIds.last(); - dstS.inRefIds.add(link.srcS.id); - - // Go up the dominator chain until we reach a node we haven't already - // seen with a path to dstS. - NodeS xS = link.srcS; - while (xS.id > seenid) { - xS = xS.domS; - } - - // The new dominator for dstS must have an id less than the node we - // just reached. Pull the dominator for dstS up its dominator - // chain until we find a suitable new dominator for dstS. - long domid = xS.id; - if (dstS.domS.id > domid) { - // Mark the node as needing to be revisited. - if (dstS.domS == dstS.oldDomS) { - if (dstS.oldDomS.revisit == null) { - dstS.oldDomS.revisit = new NodeSet(); - revisit.add(dstS.oldDomS); - } - dstS.oldDomS.revisit.add(dstS); - } - - // Update the node's candidate dominator. - dstS.domS.dominated.remove(dstS); - do { - dstS.domS = dstS.domS.domS; - } while (dstS.domS.id > domid); - dstS.domS.dominated.add(dstS); - } - } + Dominators.Graph<Node> graph = new Dominators.Graph<Node>() { + @Override + public void setDominatorsComputationState(Node node, Object state) { + node.setDominatorsComputationState(state); } - } - progress.done(); - // 2. Continue revisiting nodes until every node satisfies the requirement - // that domS.id == oldDomS.id. - progress.start("Resolving dominators", workBound); - while (!revisit.isEmpty()) { - NodeS oldDomS = revisit.poll(); - assert oldDomS.revisit != null; - - NodeSet nodes = oldDomS.revisit; - oldDomS.revisit = null; - - // Search for pairs of nodes nodeS, xS for which - // nodeS.id > xS.domS.id > nodeS.oldDomS.id - // and there is a path of nodes with increasing ids from nodeS to xS. - // In that case, xS.domS must be wrong, because there is a path to xS - // from the root that does not go through xS.domS: - // * There is a path from the root to nodeS.oldDomS that doesn't go - // through xS.domS. Otherwise xS.domS would be a dominator of - // nodeS.oldDomS, but it can't be because xS.domS.id > nodeS.oldDomS.id. - // * There is a path from nodeS.oldDomS to nodeS that doesn't go through - // xS.domS, because xS.domS is not a dominator of nodeS. - // * There is a path from nodeS to xS that doesn't go through xS.domS, - // because we have a path of increasing ids from nodeS to xS, none of - // which can have an id smaller than nodeS as xS.domS does. - for (int i = 0; i < oldDomS.dominated.size; ++i) { - NodeS xS = oldDomS.dominated.nodes[i]; - for (int j = 0; j < nodes.size; ++j) { - NodeS nodeS = nodes.nodes[j]; - assert nodeS.oldDomS == oldDomS; - if (isReachableAscending(nodeS, xS)) { - // Update the dominator for xS. - if (xS.domS == xS.oldDomS) { - if (xS.oldDomS.revisit == null) { - xS.oldDomS.revisit = new NodeSet(); - revisit.add(xS.oldDomS); - } - xS.oldDomS.revisit.add(xS); - } - oldDomS.dominated.remove(i--); - xS.domS = nodeS.domS; - xS.domS.dominated.add(xS); - break; - } - } + @Override + public Object getDominatorsComputationState(Node node) { + return node.getDominatorsComputationState(); } - // We can now safely update oldDomS for each of the nodes nodeS while - // preserving the oldDomS invariant. - for (int i = 0; i < nodes.size; ++i) { - NodeS nodeS = nodes.nodes[i]; - nodeS.oldDomS = oldDomS.oldDomS; - if (nodeS.oldDomS != nodeS.domS) { - if (nodeS.oldDomS.revisit == null) { - nodeS.oldDomS.revisit = new NodeSet(); - revisit.add(nodeS.oldDomS); - } - nodeS.oldDomS.revisit.add(nodeS); - } + @Override + public Iterable<? extends Node> getReferencesForDominators(Node node) { + return node.getReferencesForDominators(); } - progress.advance((oldDomS.depth - oldDomS.oldDomS.depth) * nodes.size); - } - progress.done(); - - // 3. We have figured out the correct dominator for each node. Notify the - // user of the results by doing one last traversal of the nodes. - assert revisit.isEmpty(); - revisit.add(rootS); - while (!revisit.isEmpty()) { - NodeS nodeS = revisit.poll(); - assert nodeS.domS == nodeS.oldDomS; - assert nodeS.revisit == null; - nodeS.node.setDominatorsComputationState(null); - for (int i = 0; i < nodeS.dominated.size; ++i) { - NodeS xS = nodeS.dominated.nodes[i]; - xS.node.setDominator(nodeS.node); - revisit.add(xS); + @Override + public void setDominator(Node node, Node dominator) { + node.setDominator(dominator); } - } - } - - // Returns true if there is a path from srcS to dstS of nodes with ascending - // ids (not including dstS.id). - private static boolean isReachableAscending(NodeS srcS, NodeS dstS) { - if (dstS.id < srcS.id) { - // The first time we saw dstS was before we saw srcS. See if srcS is on - // the source chain for any nodes with direct references to dstS. - return dstS.inRefIds.hasIdInRange(srcS.id, srcS.maxReachableId); - } + }; - // Otherwise dstS is only reachable from srcS on a node with ascending ids - // if it was visited for the first time while performing the depth-first - // traversal of srcS. - return dstS.id <= srcS.maxReachableId; + new Dominators(graph).progress(progress, numNodes).computeDominators(root); } } diff --git a/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java b/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java index a321ec0785..b13117c637 100644 --- a/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java +++ b/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java @@ -16,7 +16,6 @@ package com.android.ahat.heapdump; -import com.android.ahat.dominators.DominatorsComputation; import com.android.ahat.progress.Progress; import java.awt.image.BufferedImage; import java.util.ArrayDeque; @@ -33,8 +32,7 @@ import java.util.Queue; * kinds of Java instances, including normal Java objects, class objects, and * arrays. */ -public abstract class AhatInstance implements Diffable<AhatInstance>, - DominatorsComputation.Node { +public abstract class AhatInstance implements Diffable<AhatInstance> { // The id of this instance from the heap dump. private final long mId; @@ -739,24 +737,12 @@ public abstract class AhatInstance implements Diffable<AhatInstance>, } } - @Override - public void setDominatorsComputationState(Object state) { - setTemporaryUserData(state); - } - - @Override - public Object getDominatorsComputationState() { - return getTemporaryUserData(); - } - - @Override - public Iterable<? extends DominatorsComputation.Node> getReferencesForDominators() { + Iterable<AhatInstance> getReferencesForDominators() { return new DominatorReferenceIterator(getReferences()); } - @Override - public void setDominator(DominatorsComputation.Node dominator) { - mImmediateDominator = (AhatInstance)dominator; + void setDominator(AhatInstance dominator) { + mImmediateDominator = dominator; mImmediateDominator.mDominated.add(this); } } diff --git a/tools/ahat/src/main/com/android/ahat/heapdump/AhatSnapshot.java b/tools/ahat/src/main/com/android/ahat/heapdump/AhatSnapshot.java index 12d3755784..1b83d699b7 100644 --- a/tools/ahat/src/main/com/android/ahat/heapdump/AhatSnapshot.java +++ b/tools/ahat/src/main/com/android/ahat/heapdump/AhatSnapshot.java @@ -16,7 +16,7 @@ package com.android.ahat.heapdump; -import com.android.ahat.dominators.DominatorsComputation; +import com.android.ahat.dominators.Dominators; import com.android.ahat.progress.Progress; import java.util.List; @@ -60,7 +60,29 @@ public class AhatSnapshot implements Diffable<AhatSnapshot> { } } - DominatorsComputation.computeDominators(mSuperRoot, progress, mInstances.size()); + Dominators.Graph<AhatInstance> graph = new Dominators.Graph<AhatInstance>() { + @Override + public void setDominatorsComputationState(AhatInstance node, Object state) { + node.setTemporaryUserData(state); + } + + @Override + public Object getDominatorsComputationState(AhatInstance node) { + return node.getTemporaryUserData(); + } + + @Override + public Iterable<? extends AhatInstance> getReferencesForDominators(AhatInstance node) { + return node.getReferencesForDominators(); + } + + @Override + public void setDominator(AhatInstance node, AhatInstance dominator) { + node.setDominator(dominator); + } + }; + new Dominators(graph).progress(progress, mInstances.size()).computeDominators(mSuperRoot); + AhatInstance.computeRetainedSize(mSuperRoot, mHeaps.size()); for (AhatHeap heap : mHeaps) { diff --git a/tools/ahat/src/main/com/android/ahat/heapdump/SuperRoot.java b/tools/ahat/src/main/com/android/ahat/heapdump/SuperRoot.java index d06df900fb..a871c7e075 100644 --- a/tools/ahat/src/main/com/android/ahat/heapdump/SuperRoot.java +++ b/tools/ahat/src/main/com/android/ahat/heapdump/SuperRoot.java @@ -16,12 +16,11 @@ package com.android.ahat.heapdump; -import com.android.ahat.dominators.DominatorsComputation; import java.util.AbstractList; import java.util.ArrayList; import java.util.List; -class SuperRoot extends AhatInstance implements DominatorsComputation.Node { +class SuperRoot extends AhatInstance { private List<AhatInstance> mRoots = new ArrayList<AhatInstance>(); private Object mDominatorsComputationState; diff --git a/tools/ahat/src/test/com/android/ahat/DominatorsTest.java b/tools/ahat/src/test/com/android/ahat/DominatorsTest.java index d9af363659..955b59fb4e 100644 --- a/tools/ahat/src/test/com/android/ahat/DominatorsTest.java +++ b/tools/ahat/src/test/com/android/ahat/DominatorsTest.java @@ -16,51 +16,55 @@ package com.android.ahat; +import com.android.ahat.dominators.Dominators; import com.android.ahat.dominators.DominatorsComputation; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; +import java.util.HashMap; import java.util.List; +import java.util.Map; import org.junit.Test; import static org.junit.Assert.assertEquals; public class DominatorsTest { - private static class Node implements DominatorsComputation.Node { - public String name; - public List<Node> depends = new ArrayList<Node>(); - public Node dominator; - private Object dominatorsComputationState; - public Node(String name) { - this.name = name; - } + private static class Graph implements Dominators.Graph<String> { + private Map<String, Object> states = new HashMap<>(); + private Map<String, Collection<String>> depends = new HashMap<>(); + private Map<String, String> dominators = new HashMap<>(); - public void computeDominators() { - DominatorsComputation.computeDominators(this); + @Override + public void setDominatorsComputationState(String node, Object state) { + states.put(node, state); } - public String toString() { - return name; + @Override public Object getDominatorsComputationState(String node) { + return states.get(node); } @Override - public void setDominatorsComputationState(Object state) { - dominatorsComputationState = state; + public Collection<String> getReferencesForDominators(String node) { + return depends.get(node); } @Override - public Object getDominatorsComputationState() { - return dominatorsComputationState; + public void setDominator(String node, String dominator) { + dominators.put(node, dominator); } - @Override - public Collection<Node> getReferencesForDominators() { - return depends; + /** + * Define a node in the graph, including all its outgoing edges. + */ + public void node(String src, String... dsts) { + depends.put(src, Arrays.asList(dsts)); } - @Override - public void setDominator(DominatorsComputation.Node dominator) { - this.dominator = (Node)dominator; + /** + * Get the computed dominator for a given node. + */ + public String dom(String node) { + return dominators.get(node); } } @@ -68,20 +72,21 @@ public class DominatorsTest { public void singleNode() { // --> n // Trivial case. - Node n = new Node("n"); - n.computeDominators(); + Graph graph = new Graph(); + graph.node("n"); + new Dominators(graph).computeDominators("n"); } @Test public void parentWithChild() { // --> parent --> child // The child node is dominated by the parent. - Node parent = new Node("parent"); - Node child = new Node("child"); - parent.depends = Arrays.asList(child); + Graph graph = new Graph(); + graph.node("parent", "child"); + graph.node("child"); + new Dominators(graph).computeDominators("parent"); - parent.computeDominators(); - assertEquals(parent, child.dominator); + assertEquals("parent", graph.dom("child")); } @Test @@ -90,18 +95,16 @@ public class DominatorsTest { // --> parent child // \-> left --->/ // The child node can be reached either by right or by left. - Node parent = new Node("parent"); - Node right = new Node("right"); - Node left = new Node("left"); - Node child = new Node("child"); - parent.depends = Arrays.asList(left, right); - right.depends = Arrays.asList(child); - left.depends = Arrays.asList(child); - - parent.computeDominators(); - assertEquals(parent, left.dominator); - assertEquals(parent, right.dominator); - assertEquals(parent, child.dominator); + Graph graph = new Graph(); + graph.node("parent", "left", "right"); + graph.node("right", "child"); + graph.node("left", "child"); + graph.node("child"); + new Dominators(graph).computeDominators("parent"); + + assertEquals("parent", graph.dom("left")); + assertEquals("parent", graph.dom("right")); + assertEquals("parent", graph.dom("child")); } @Test @@ -109,30 +112,28 @@ public class DominatorsTest { // /-> right -->\ // --> parent -----------> child // The child node can be reached either by right or parent. - Node parent = new Node("parent"); - Node right = new Node("right"); - Node child = new Node("child"); - parent.depends = Arrays.asList(right, child); - right.depends = Arrays.asList(child); - - parent.computeDominators(); - assertEquals(parent, child.dominator); - assertEquals(parent, right.dominator); + Graph graph = new Graph(); + graph.node("parent", "right", "child"); + graph.node("right", "child"); + graph.node("child"); + new Dominators(graph).computeDominators("parent"); + + assertEquals("parent", graph.dom("child")); + assertEquals("parent", graph.dom("right")); } @Test public void subDominator() { // --> parent --> middle --> child // The child is dominated by an internal node. - Node parent = new Node("parent"); - Node middle = new Node("middle"); - Node child = new Node("child"); - parent.depends = Arrays.asList(middle); - middle.depends = Arrays.asList(child); - - parent.computeDominators(); - assertEquals(parent, middle.dominator); - assertEquals(middle, child.dominator); + Graph graph = new Graph(); + graph.node("parent", "middle"); + graph.node("middle", "child"); + graph.node("child"); + new Dominators(graph).computeDominators("parent"); + + assertEquals("parent", graph.dom("middle")); + assertEquals("middle", graph.dom("child")); } @Test @@ -140,13 +141,12 @@ public class DominatorsTest { // --> parent --> child -\ // \<---/ // The child points back to itself. - Node parent = new Node("parent"); - Node child = new Node("child"); - parent.depends = Arrays.asList(child); - child.depends = Arrays.asList(child); + Graph graph = new Graph(); + graph.node("parent", "child"); + graph.node("child", "child"); + new Dominators(graph).computeDominators("parent"); - parent.computeDominators(); - assertEquals(parent, child.dominator); + assertEquals("parent", graph.dom("child")); } @Test @@ -154,19 +154,16 @@ public class DominatorsTest { // --> parent --> a --> b --> c -\ // \<------------/ // There is a loop in the graph, with only one way into the loop. - Node parent = new Node("parent"); - Node a = new Node("a"); - Node b = new Node("b"); - Node c = new Node("c"); - parent.depends = Arrays.asList(a); - a.depends = Arrays.asList(b); - b.depends = Arrays.asList(c); - c.depends = Arrays.asList(a); - - parent.computeDominators(); - assertEquals(parent, a.dominator); - assertEquals(a, b.dominator); - assertEquals(b, c.dominator); + Graph graph = new Graph(); + graph.node("parent", "a"); + graph.node("a", "b"); + graph.node("b", "c"); + graph.node("c", "a"); + new Dominators(graph).computeDominators("parent"); + + assertEquals("parent", graph.dom("a")); + assertEquals("a", graph.dom("b")); + assertEquals("b", graph.dom("c")); } @Test @@ -176,25 +173,20 @@ public class DominatorsTest { // \--> left --->--------/ // There is a loop in the graph, with two different ways to enter the // loop. - Node parent = new Node("parent"); - Node left = new Node("left"); - Node right = new Node("right"); - Node a = new Node("a"); - Node b = new Node("b"); - Node c = new Node("c"); - parent.depends = Arrays.asList(left, right); - right.depends = Arrays.asList(a); - left.depends = Arrays.asList(c); - a.depends = Arrays.asList(b); - b.depends = Arrays.asList(c); - c.depends = Arrays.asList(a); - - parent.computeDominators(); - assertEquals(parent, right.dominator); - assertEquals(parent, left.dominator); - assertEquals(parent, a.dominator); - assertEquals(parent, c.dominator); - assertEquals(a, b.dominator); + Graph graph = new Graph(); + graph.node("parent", "left", "right"); + graph.node("left", "c"); + graph.node("right", "a"); + graph.node("a", "b"); + graph.node("b", "c"); + graph.node("c", "a"); + new Dominators(graph).computeDominators("parent"); + + assertEquals("parent", graph.dom("right")); + assertEquals("parent", graph.dom("left")); + assertEquals("parent", graph.dom("a")); + assertEquals("parent", graph.dom("c")); + assertEquals("a", graph.dom("b")); } @Test @@ -206,33 +198,33 @@ public class DominatorsTest { // dominator getting improperly overwritten. The relevant features of this // case are: 'child' is visited after 'right', 'child' is dominated by // 'parent', and 'parent' revisits 'right' after visiting 'child'. - Node parent = new Node("parent"); - Node right = new Node("right"); - Node left = new Node("left"); - Node child = new Node("child"); - parent.depends = Arrays.asList(left, child, right); - left.depends = Arrays.asList(right); - right.depends = Arrays.asList(child); - - parent.computeDominators(); - assertEquals(parent, left.dominator); - assertEquals(parent, child.dominator); - assertEquals(parent, right.dominator); + Graph graph = new Graph(); + graph.node("parent", "left", "child", "right"); + graph.node("right", "child"); + graph.node("left", "right"); + graph.node("child"); + new Dominators(graph).computeDominators("parent"); + + assertEquals("parent", graph.dom("left")); + assertEquals("parent", graph.dom("child")); + assertEquals("parent", graph.dom("right")); } @Test public void stackOverflow() { // --> a --> b --> ... --> N // Verify we don't smash the stack for deep chains. - Node root = new Node("root"); - Node curr = root; + Graph graph = new Graph(); + String root = "end"; + graph.node(root); + for (int i = 0; i < 10000; ++i) { - Node node = new Node("n" + i); - curr.depends.add(node); - curr = node; + String child = root; + root = "n" + i; + graph.node(root, child); } - root.computeDominators(); + new Dominators(graph).computeDominators(root); } @Test @@ -245,24 +237,20 @@ public class DominatorsTest { // all reachable children's dominators to be updated too. In particular, // c's dominator should be updated, even though b's dominator is // unchanged. - Node parent = new Node("parent"); - Node right = new Node("right"); - Node left = new Node("left"); - Node a = new Node("a"); - Node b = new Node("b"); - Node c = new Node("c"); - parent.depends = Arrays.asList(right, left); - left.depends = Arrays.asList(a, c); - right.depends = Arrays.asList(a); - a.depends = Arrays.asList(b); - b.depends = Arrays.asList(c); - - parent.computeDominators(); - assertEquals(parent, left.dominator); - assertEquals(parent, right.dominator); - assertEquals(parent, a.dominator); - assertEquals(parent, c.dominator); - assertEquals(a, b.dominator); + Graph graph = new Graph(); + graph.node("parent", "right", "left"); + graph.node("right", "a"); + graph.node("left", "a", "c"); + graph.node("a", "b"); + graph.node("b", "c"); + graph.node("c"); + new Dominators(graph).computeDominators("parent"); + + assertEquals("parent", graph.dom("left")); + assertEquals("parent", graph.dom("right")); + assertEquals("parent", graph.dom("a")); + assertEquals("parent", graph.dom("c")); + assertEquals("a", graph.dom("b")); } @Test @@ -276,24 +264,20 @@ public class DominatorsTest { // to be reachable from p. Make sure that causes e's dominator to be // refined again from a to p. The extra nodes are there to ensure the // necessary scheduling to expose the bug we had. - Node p = new Node("p"); - Node a = new Node("a"); - Node b = new Node("b"); - Node c = new Node("c"); - Node d = new Node("d"); - Node e = new Node("e"); - p.depends = Arrays.asList(d, a); - a.depends = Arrays.asList(e, b); - b.depends = Arrays.asList(d, c); - c.depends = Arrays.asList(d); - d.depends = Arrays.asList(e); - - p.computeDominators(); - assertEquals(p, a.dominator); - assertEquals(a, b.dominator); - assertEquals(b, c.dominator); - assertEquals(p, d.dominator); - assertEquals(p, e.dominator); + Graph graph = new Graph(); + graph.node("p", "d", "a"); + graph.node("a", "e", "b"); + graph.node("b", "d", "c"); + graph.node("c", "d"); + graph.node("d", "e"); + graph.node("e"); + new Dominators(graph).computeDominators("p"); + + assertEquals("p", graph.dom("a")); + assertEquals("a", graph.dom("b")); + assertEquals("b", graph.dom("c")); + assertEquals("p", graph.dom("d")); + assertEquals("p", graph.dom("e")); } @Test @@ -307,6 +291,70 @@ public class DominatorsTest { // up to b. c needs to be revisited again after the dominator for f is // pulled up to a, and that revisit of c is necessary to ensure the // dominator for d is pulled up to a. + Graph graph = new Graph(); + graph.node("a", "f", "b"); + graph.node("b", "f", "d", "x"); + graph.node("x", "c"); + graph.node("c", "d"); + graph.node("d"); + graph.node("f", "c"); + new Dominators(graph).computeDominators("a"); + + assertEquals("a", graph.dom("b")); + assertEquals("b", graph.dom("x")); + assertEquals("a", graph.dom("c")); + assertEquals("a", graph.dom("d")); + assertEquals("a", graph.dom("f")); + } + + // Test the old dominators API. + private static class Node implements DominatorsComputation.Node { + public String name; + public List<Node> depends = new ArrayList<Node>(); + public Node dominator; + private Object dominatorsComputationState; + + public Node(String name) { + this.name = name; + } + + public void computeDominators() { + DominatorsComputation.computeDominators(this); + } + + public String toString() { + return name; + } + + @Override + public void setDominatorsComputationState(Object state) { + dominatorsComputationState = state; + } + + @Override + public Object getDominatorsComputationState() { + return dominatorsComputationState; + } + + @Override + public Collection<Node> getReferencesForDominators() { + return depends; + } + + @Override + public void setDominator(DominatorsComputation.Node dominator) { + this.dominator = (Node)dominator; + } + } + + @Test + public void twiceRevisitOldApi() { + // /---->---\ + // / /--> f -->-\ + // --> a --> b -->--x---> c --> d + // \----------->----/ + // Run the twiceRevisit test using the user api version of computing + // dominators. Node a = new Node("a"); Node b = new Node("b"); Node x = new Node("x"); |