diff options
32 files changed, 760 insertions, 1395 deletions
diff --git a/compiler/Android.bp b/compiler/Android.bp index e1d382f6f4..eff4955d44 100644 --- a/compiler/Android.bp +++ b/compiler/Android.bp @@ -161,7 +161,6 @@ art_cc_defaults { "utils/x86/assembler_x86.cc", "utils/x86/jni_macro_assembler_x86.cc", "utils/x86/managed_register_x86.cc", - "optimizing/instruction_simplifier_x86.cc", ], }, x86_64: { 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_vector_x86.cc b/compiler/optimizing/code_generator_vector_x86.cc index 58808769e2..086ae07a06 100644 --- a/compiler/optimizing/code_generator_vector_x86.cc +++ b/compiler/optimizing/code_generator_vector_x86.cc @@ -1125,59 +1125,13 @@ static void CreateVecAccumLocations(ArenaAllocator* allocator, HVecOperation* in } } -void LocationsBuilderX86::VisitVecMultiplyAccumulate(HVecMultiplyAccumulate* instr) { - LocationSummary* locations = new (GetGraph()->GetAllocator()) LocationSummary(instr); - switch (instr->GetPackedType()) { - case DataType::Type::kFloat32: - case DataType::Type::kFloat64: - locations->SetInAt( - HVecMultiplyAccumulate::kInputAccumulatorIndex, Location::RequiresFpuRegister()); - locations->SetInAt( - HVecMultiplyAccumulate::kInputMulLeftIndex, Location::RequiresFpuRegister()); - locations->SetInAt( - HVecMultiplyAccumulate::kInputMulRightIndex, Location::RequiresFpuRegister()); - DCHECK_EQ(HVecMultiplyAccumulate::kInputAccumulatorIndex, 0); - locations->SetOut(Location::SameAsFirstInput()); - break; - default: - // VecMultiplyAccumulate is supported only for single and - // double precision floating points. Hence integral types - // are still not converted. - LOG(FATAL) << "Unsupported SIMD Type"; - } +void LocationsBuilderX86::VisitVecMultiplyAccumulate(HVecMultiplyAccumulate* instruction) { + CreateVecAccumLocations(GetGraph()->GetAllocator(), instruction); } -void InstructionCodeGeneratorX86::VisitVecMultiplyAccumulate(HVecMultiplyAccumulate* instr) { - LocationSummary* locations = instr->GetLocations(); - DCHECK(locations->InAt(0).Equals(locations->Out())); - XmmRegister accumulator = locations->InAt( - HVecMultiplyAccumulate::kInputAccumulatorIndex).AsFpuRegister<XmmRegister>(); - XmmRegister mul_left = locations->InAt( - HVecMultiplyAccumulate::kInputMulLeftIndex).AsFpuRegister<XmmRegister>(); - XmmRegister mul_right = locations->InAt( - HVecMultiplyAccumulate::kInputMulRightIndex).AsFpuRegister<XmmRegister>(); - switch (instr->GetPackedType()) { - case DataType::Type::kFloat32: - DCHECK_EQ(4u, instr->GetVectorLength()); - if (instr->GetOpKind() == HInstruction::InstructionKind::kAdd) - __ vfmadd231ps(accumulator, mul_left, mul_right); - else - __ vfmsub231ps(accumulator, mul_left, mul_right); - break; - case DataType::Type::kFloat64: - DCHECK_EQ(2u, instr->GetVectorLength()); - if (instr->GetOpKind() == HInstruction::InstructionKind::kAdd) - __ vfmadd231pd(accumulator, mul_left, mul_right); - else - __ vfmsub231pd(accumulator, mul_left, mul_right); - break; - default: - - // VecMultiplyAccumulate is supported only for single and - // double precision floating points. Hence integral types - // are still not converted. - LOG(FATAL) << "Unsupported SIMD Type"; - } +void InstructionCodeGeneratorX86::VisitVecMultiplyAccumulate(HVecMultiplyAccumulate* instruction) { + // TODO: pmaddwd? + LOG(FATAL) << "No SIMD for " << instruction->GetId(); } void LocationsBuilderX86::VisitVecSADAccumulate(HVecSADAccumulate* instruction) { diff --git a/compiler/optimizing/code_generator_vector_x86_64.cc b/compiler/optimizing/code_generator_vector_x86_64.cc index 4795e86933..4d31ab68d1 100644 --- a/compiler/optimizing/code_generator_vector_x86_64.cc +++ b/compiler/optimizing/code_generator_vector_x86_64.cc @@ -1098,61 +1098,13 @@ static void CreateVecAccumLocations(ArenaAllocator* allocator, HVecOperation* in } } -void LocationsBuilderX86_64::VisitVecMultiplyAccumulate(HVecMultiplyAccumulate* instr) { - LocationSummary* locations = new (GetGraph()->GetAllocator()) LocationSummary(instr); - switch (instr->GetPackedType()) { - case DataType::Type::kFloat32: - case DataType::Type::kFloat64: - locations->SetInAt( - HVecMultiplyAccumulate::kInputAccumulatorIndex, Location::RequiresFpuRegister()); - locations->SetInAt( - HVecMultiplyAccumulate::kInputMulLeftIndex, Location::RequiresFpuRegister()); - locations->SetInAt( - HVecMultiplyAccumulate::kInputMulRightIndex, Location::RequiresFpuRegister()); - DCHECK_EQ(HVecMultiplyAccumulate::kInputAccumulatorIndex, 0); - locations->SetOut(Location::SameAsFirstInput()); - break; - default: - // VecMultiplyAccumulate is supported only for single and - // double precision floating points. Hence integral types - // are still not converted. - LOG(FATAL) << "Unsupported SIMD type"; - } +void LocationsBuilderX86_64::VisitVecMultiplyAccumulate(HVecMultiplyAccumulate* instruction) { + CreateVecAccumLocations(GetGraph()->GetAllocator(), instruction); } - -void InstructionCodeGeneratorX86_64::VisitVecMultiplyAccumulate(HVecMultiplyAccumulate* instr) { - LocationSummary* locations = instr->GetLocations(); - DCHECK(locations->InAt(0).Equals(locations->Out())); - XmmRegister accumulator = locations->InAt( - HVecMultiplyAccumulate::kInputAccumulatorIndex).AsFpuRegister<XmmRegister>(); - XmmRegister mul_left = locations->InAt( - HVecMultiplyAccumulate::kInputMulLeftIndex).AsFpuRegister<XmmRegister>(); - XmmRegister mul_right = locations->InAt( - HVecMultiplyAccumulate::kInputMulRightIndex).AsFpuRegister<XmmRegister>(); - - switch (instr->GetPackedType()) { - case DataType::Type::kFloat32: - DCHECK_EQ(4u, instr->GetVectorLength()); - if (instr->GetOpKind() == HInstruction::InstructionKind::kAdd) - __ vfmadd231ps(accumulator, mul_left, mul_right); - else - __ vfmsub231ps(accumulator, mul_left, mul_right); - break; - case DataType::Type::kFloat64: - DCHECK_EQ(2u, instr->GetVectorLength()); - if (instr->GetOpKind() == HInstruction::InstructionKind::kAdd) - __ vfmadd231pd(accumulator, mul_left, mul_right); - else - __ vfmsub231pd(accumulator, mul_left, mul_right); - break; - default: - - // VecMultiplyAccumulate is supported only for single and - // double precision floating points. Hence integral types - // are still not converted. - LOG(FATAL) << "Unsupported SIMD Type"; - } +void InstructionCodeGeneratorX86_64::VisitVecMultiplyAccumulate(HVecMultiplyAccumulate* instruction) { + // TODO: pmaddwd? + LOG(FATAL) << "No SIMD for " << instruction->GetId(); } void LocationsBuilderX86_64::VisitVecSADAccumulate(HVecSADAccumulate* instruction) { diff --git a/compiler/optimizing/instruction_simplifier_x86.cc b/compiler/optimizing/instruction_simplifier_x86.cc deleted file mode 100644 index b3f67d6e84..0000000000 --- a/compiler/optimizing/instruction_simplifier_x86.cc +++ /dev/null @@ -1,149 +0,0 @@ -/* - * Copyright (C) 2018 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 "instruction_simplifier_x86.h" -#include "arch/x86/instruction_set_features_x86.h" -#include "mirror/array-inl.h" -#include "code_generator.h" - - -namespace art { - -namespace x86 { - -class InstructionSimplifierX86Visitor : public HGraphVisitor { - public: - InstructionSimplifierX86Visitor(HGraph* graph, - CodeGeneratorX86 *codegen, - OptimizingCompilerStats* stats) - : HGraphVisitor(graph), codegen_(codegen), stats_(stats) {} - - private: - void RecordSimplification() { - MaybeRecordStat(stats_, MethodCompilationStat::kInstructionSimplificationsArch); - } - - bool HasCpuFeatureFlag() { - return (codegen_->GetInstructionSetFeatures().HasAVX2()); - } - - /** - * This simplifier uses a special-purpose BB visitor. - * (1) No need to visit Phi nodes. - * (2) Since statements can be removed in a "forward" fashion, - * the visitor should test if each statement is still there. - */ - void VisitBasicBlock(HBasicBlock* block) OVERRIDE { - // TODO: fragile iteration, provide more robust iterators? - for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { - HInstruction* instruction = it.Current(); - if (instruction->IsInBlock()) { - instruction->Accept(this); - } - } - } - - bool TryGenerateVecMultiplyAccumulate(HVecMul* mul); - void VisitVecMul(HVecMul* instruction) OVERRIDE; - - CodeGeneratorX86* codegen_; - OptimizingCompilerStats* stats_; -}; - -/* generic expressions for FMA -a = (b * c) + a -a = (b * c) – a -*/ -bool InstructionSimplifierX86Visitor::TryGenerateVecMultiplyAccumulate(HVecMul* mul) { - if (!(mul->GetPackedType() == DataType::Type::kFloat32 || - mul->GetPackedType() == DataType::Type::kFloat64)) { - return false; - } - ArenaAllocator* allocator = mul->GetBlock()->GetGraph()->GetAllocator(); - if (mul->HasOnlyOneNonEnvironmentUse()) { - HInstruction* use = mul->GetUses().front().GetUser(); - if (use->IsVecAdd() || use->IsVecSub()) { - // Replace code looking like - // VECMUL tmp, x, y - // VECADD dst, acc, tmp or VECADD dst, tmp, acc - // or - // VECSUB dst, tmp, acc - // with - // VECMULACC dst, acc, x, y - - // Note that we do not want to (unconditionally) perform the merge when the - // multiplication has multiple uses and it can be merged in all of them. - // Multiple uses could happen on the same control-flow path, and we would - // then increase the amount of work. In the future we could try to evaluate - // whether all uses are on different control-flow paths (using dominance and - // reverse-dominance information) and only perform the merge when they are. - HInstruction* accumulator = nullptr; - HVecBinaryOperation* binop = use->AsVecBinaryOperation(); - HInstruction* binop_left = binop->GetLeft(); - HInstruction* binop_right = binop->GetRight(); - DCHECK_NE(binop_left, binop_right); - if (use->IsVecSub()) { - if (binop_left == mul) { - accumulator = binop_right; - } - } else { - // VecAdd - if (binop_right == mul) { - accumulator = binop_left; - } else { - DCHECK_EQ(binop_left, mul); - accumulator = binop_right; - } - } - HInstruction::InstructionKind kind = - use->IsVecAdd() ? HInstruction::kAdd : HInstruction::kSub; - - if (accumulator != nullptr) { - HVecMultiplyAccumulate* mulacc = - new (allocator) HVecMultiplyAccumulate(allocator, - kind, - accumulator, - mul->GetLeft(), - mul->GetRight(), - binop->GetPackedType(), - binop->GetVectorLength(), - binop->GetDexPc()); - binop->GetBlock()->ReplaceAndRemoveInstructionWith(binop, mulacc); - DCHECK(!mul->HasUses()); - mul->GetBlock()->RemoveInstruction(mul); - return true; - } - } - } - return false; -} - -void InstructionSimplifierX86Visitor::VisitVecMul(HVecMul* instruction) { - if (HasCpuFeatureFlag()) { - if (TryGenerateVecMultiplyAccumulate(instruction)) { - RecordSimplification(); - } - } -} - -bool InstructionSimplifierX86::Run() { - InstructionSimplifierX86Visitor visitor(graph_, codegen_, stats_); - visitor.VisitReversePostOrder(); - return true; -} - -} // namespace x86 -} // namespace art diff --git a/compiler/optimizing/instruction_simplifier_x86.h b/compiler/optimizing/instruction_simplifier_x86.h deleted file mode 100644 index 1fb199f728..0000000000 --- a/compiler/optimizing/instruction_simplifier_x86.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * Copyright (C) 2018 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef ART_COMPILER_OPTIMIZING_INSTRUCTION_SIMPLIFIER_X86_H_ -#define ART_COMPILER_OPTIMIZING_INSTRUCTION_SIMPLIFIER_X86_H_ - -#include "nodes.h" -#include "optimization.h" -#include "code_generator_x86.h" - -namespace art { -namespace x86 { - -class InstructionSimplifierX86 : public HOptimization { - public: - InstructionSimplifierX86(HGraph* graph, CodeGenerator* codegen, OptimizingCompilerStats* stats) - : HOptimization(graph, kInstructionSimplifierX86PassName, stats), - codegen_(down_cast<CodeGeneratorX86*>(codegen)) {} - - static constexpr const char* kInstructionSimplifierX86PassName = "instruction_simplifier_x86"; - - bool Run() OVERRIDE; - - private: - CodeGeneratorX86* codegen_; -}; - -} // namespace x86 -} // namespace art - -#endif // ART_COMPILER_OPTIMIZING_INSTRUCTION_SIMPLIFIER_X86_H_ diff --git a/compiler/optimizing/nodes_vector.h b/compiler/optimizing/nodes_vector.h index b4f9993ad6..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,15 +956,14 @@ 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); } - static constexpr int kInputAccumulatorIndex = 0; - static constexpr int kInputMulLeftIndex = 1; - static constexpr int kInputMulRightIndex = 2; - bool CanBeMoved() const OVERRIDE { return true; } bool InstructionDataEquals(const HInstruction* other) const OVERRIDE { diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc index 3c803ab627..142ddb5fbb 100644 --- a/compiler/optimizing/optimization.cc +++ b/compiler/optimizing/optimization.cc @@ -28,7 +28,6 @@ #endif #ifdef ART_ENABLE_CODEGEN_x86 #include "pc_relative_fixups_x86.h" -#include "instruction_simplifier_x86.h" #endif #if defined(ART_ENABLE_CODEGEN_x86) || defined(ART_ENABLE_CODEGEN_x86_64) #include "x86_memory_gen.h" @@ -122,8 +121,6 @@ const char* OptimizationPassName(OptimizationPass pass) { #if defined(ART_ENABLE_CODEGEN_x86) || defined(ART_ENABLE_CODEGEN_x86_64) case OptimizationPass::kX86MemoryOperandGeneration: return x86::X86MemoryOperandGeneration::kX86MemoryOperandGenerationPassName; - case OptimizationPass::kInstructionSimplifierX86: - return x86::InstructionSimplifierX86::kInstructionSimplifierX86PassName; #endif case OptimizationPass::kNone: LOG(FATAL) << "kNone does not represent an actual pass"; @@ -166,7 +163,6 @@ OptimizationPass OptimizationPassByName(const std::string& pass_name) { #ifdef ART_ENABLE_CODEGEN_x86 X(OptimizationPass::kPcRelativeFixupsX86); X(OptimizationPass::kX86MemoryOperandGeneration); - X(OptimizationPass::kInstructionSimplifierX86); #endif LOG(FATAL) << "Cannot find optimization " << pass_name; UNREACHABLE(); @@ -327,10 +323,6 @@ ArenaVector<HOptimization*> ConstructOptimizations( DCHECK(alt_name == nullptr) << "arch-specific pass does not support alternative name"; opt = new (allocator) x86::X86MemoryOperandGeneration(graph, codegen, stats); break; - case OptimizationPass::kInstructionSimplifierX86: - DCHECK(alt_name == nullptr) << "arch-specific pass does not support alternative name"; - opt = new (allocator) x86::InstructionSimplifierX86(graph, codegen, stats); - break; #endif case OptimizationPass::kNone: LOG(FATAL) << "kNone does not represent an actual pass"; diff --git a/compiler/optimizing/optimization.h b/compiler/optimizing/optimization.h index a9fafa0864..88b283cebf 100644 --- a/compiler/optimizing/optimization.h +++ b/compiler/optimizing/optimization.h @@ -101,7 +101,6 @@ enum class OptimizationPass { #endif #if defined(ART_ENABLE_CODEGEN_x86) || defined(ART_ENABLE_CODEGEN_x86_64) kX86MemoryOperandGeneration, - kInstructionSimplifierX86, #endif kNone, kLast = kNone diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index f4bafcbef0..2f530a911a 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -531,8 +531,7 @@ bool OptimizingCompiler::RunArchOptimizations(HGraph* graph, OptDef(OptimizationPass::kSideEffectsAnalysis), OptDef(OptimizationPass::kGlobalValueNumbering, "GVN$after_arch"), OptDef(OptimizationPass::kPcRelativeFixupsX86), - OptDef(OptimizationPass::kX86MemoryOperandGeneration), - OptDef(OptimizationPass::kInstructionSimplifierX86) + OptDef(OptimizationPass::kX86MemoryOperandGeneration) }; return RunOptimizations(graph, codegen, @@ -547,8 +546,7 @@ bool OptimizingCompiler::RunArchOptimizations(HGraph* graph, OptimizationDef x86_64_optimizations[] = { OptDef(OptimizationPass::kSideEffectsAnalysis), OptDef(OptimizationPass::kGlobalValueNumbering, "GVN$after_arch"), - OptDef(OptimizationPass::kX86MemoryOperandGeneration), - OptDef(OptimizationPass::kInstructionSimplifierX86) + OptDef(OptimizationPass::kX86MemoryOperandGeneration) }; return RunOptimizations(graph, codegen, 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/compiler/utils/x86/assembler_x86.cc b/compiler/utils/x86/assembler_x86.cc index c2ce03b1f2..86f9010ea3 100644 --- a/compiler/utils/x86/assembler_x86.cc +++ b/compiler/utils/x86/assembler_x86.cc @@ -525,58 +525,6 @@ void X86Assembler::divss(XmmRegister dst, const Address& src) { EmitOperand(dst, src); } -void X86Assembler::vfmadd231ps(XmmRegister acc, XmmRegister mul_left, XmmRegister mul_right) { - AssemblerBuffer::EnsureCapacity ensured(&buffer_); - uint8_t byte_zero = EmitVexByteZero(false /*is_two_byte*/); - uint8_t byte_one = EmitVexByte1(false, false, false, 2); - uint8_t byte_two = EmitVexByte2(false, 128, X86ManagedRegister::FromXmmRegister(mul_left), 1); - EmitUint8(byte_zero); - EmitUint8(byte_one); - EmitUint8(byte_two); - // Opcode field. - EmitUint8(0xB8); - EmitXmmRegisterOperand(acc, mul_right); -} - -void X86Assembler::vfmsub231ps(XmmRegister acc, XmmRegister mul_left, XmmRegister mul_right) { - AssemblerBuffer::EnsureCapacity ensured(&buffer_); - uint8_t byte_zero = EmitVexByteZero(false /*is_two_byte*/); - uint8_t byte_one = EmitVexByte1(false, false, false, 2); - uint8_t byte_two = EmitVexByte2(false, 128, X86ManagedRegister::FromXmmRegister(mul_left), 1); - EmitUint8(byte_zero); - EmitUint8(byte_one); - EmitUint8(byte_two); - // Opcode field. - EmitUint8(0xBA); - EmitXmmRegisterOperand(acc, mul_right); -} - -void X86Assembler::vfmadd231pd(XmmRegister acc, XmmRegister mul_left, XmmRegister mul_right) { - AssemblerBuffer::EnsureCapacity ensured(&buffer_); - uint8_t byte_zero = EmitVexByteZero(false /*is_two_byte*/); - uint8_t byte_one = EmitVexByte1(false, false, false, 2); - uint8_t byte_two = EmitVexByte2(true, 128, X86ManagedRegister::FromXmmRegister(mul_left), 1); - EmitUint8(byte_zero); - EmitUint8(byte_one); - EmitUint8(byte_two); - // Opcode field. - EmitUint8(0xB8); - EmitXmmRegisterOperand(acc, mul_right); -} - -void X86Assembler::vfmsub231pd(XmmRegister acc, XmmRegister mul_left, XmmRegister mul_right) { - AssemblerBuffer::EnsureCapacity ensured(&buffer_); - uint8_t byte_zero = EmitVexByteZero(false /*is_two_byte*/); - uint8_t byte_one = EmitVexByte1(false, false, false, 2); - uint8_t byte_two = EmitVexByte2(true, 128, X86ManagedRegister::FromXmmRegister(mul_left), 1); - EmitUint8(byte_zero); - EmitUint8(byte_one); - EmitUint8(byte_two); - // Opcode field. - EmitUint8(0xBA); - EmitXmmRegisterOperand(acc, mul_right); -} - void X86Assembler::addps(XmmRegister dst, XmmRegister src) { AssemblerBuffer::EnsureCapacity ensured(&buffer_); @@ -2950,99 +2898,6 @@ void X86Assembler::EmitLabelLink(NearLabel* label) { } -uint8_t X86Assembler::EmitVexByteZero(bool is_two_byte) { - uint8_t vex_zero = 0xC0; - if (!is_two_byte) { - vex_zero |= 0xC4; - } else { - vex_zero |= 0xC5; - } - return vex_zero; -} - -uint8_t X86Assembler::EmitVexByte1(bool r, bool x, bool b, int mmmmm ) { - // VEX Byte 1. - uint8_t vex_prefix = 0; - if (!r) { - vex_prefix |= 0x80; // VEX.R . - } - if (!x) { - vex_prefix |= 0x40; // VEX.X . - } - if (!b) { - vex_prefix |= 0x20; // VEX.B . - } - - // VEX.mmmmm. - switch (mmmmm) { - case 1: - // Implied 0F leading opcode byte. - vex_prefix |= 0x01; - break; - case 2: - // Implied leading 0F 38 opcode byte. - vex_prefix |= 0x02; - break; - case 3: - // Implied leading OF 3A opcode byte. - vex_prefix |= 0x03; - break; - default: - LOG(FATAL) << "unknown opcode bytes"; - } - return vex_prefix; -} - -uint8_t X86Assembler::EmitVexByte2(bool w, int l, X86ManagedRegister operand, int pp) { - uint8_t vex_prefix = 0; - // VEX Byte 2. - if (w) { - vex_prefix |= 0x80; - } - - // VEX.vvvv. - if (operand.IsXmmRegister()) { - XmmRegister vvvv = operand.AsXmmRegister(); - int inverted_reg = 15-static_cast<int>(vvvv); - uint8_t reg = static_cast<uint8_t>(inverted_reg); - vex_prefix |= ((reg & 0x0F) << 3); - } else if (operand.IsCpuRegister()) { - Register vvvv = operand.AsCpuRegister(); - int inverted_reg = 15 - static_cast<int>(vvvv); - uint8_t reg = static_cast<uint8_t>(inverted_reg); - vex_prefix |= ((reg & 0x0F) << 3); - } - - // VEX.L. - if (l == 256) { - vex_prefix |= 0x04; - } - - // VEX.pp. - switch (pp) { - case 0: - // SIMD Pefix - None. - vex_prefix |= 0x00; - break; - case 1: - // SIMD Prefix - 66. - vex_prefix |= 0x01; - break; - case 2: - // SIMD Prefix - F3. - vex_prefix |= 0x02; - break; - case 3: - // SIMD Prefix - F2. - vex_prefix |= 0x03; - break; - default: - LOG(FATAL) << "unknown SIMD Prefix"; - } - - return vex_prefix; -} - void X86Assembler::EmitGenericShift(int reg_or_opcode, const Operand& operand, const Immediate& imm) { diff --git a/compiler/utils/x86/assembler_x86.h b/compiler/utils/x86/assembler_x86.h index 8c9ce82687..e42c4c986a 100644 --- a/compiler/utils/x86/assembler_x86.h +++ b/compiler/utils/x86/assembler_x86.h @@ -397,12 +397,6 @@ class X86Assembler FINAL : public Assembler { void divss(XmmRegister dst, XmmRegister src); void divss(XmmRegister dst, const Address& src); - // FMA Mac Instructions - void vfmadd231ps(XmmRegister dst, XmmRegister src1, XmmRegister src2); - void vfmadd231pd(XmmRegister dst, XmmRegister src1, XmmRegister src2); - void vfmsub231ps(XmmRegister dst, XmmRegister src1, XmmRegister src2); - void vfmsub231pd(XmmRegister dst, XmmRegister src1, XmmRegister src2); - void addps(XmmRegister dst, XmmRegister src); // no addr variant (for now) void subps(XmmRegister dst, XmmRegister src); void mulps(XmmRegister dst, XmmRegister src); @@ -840,11 +834,6 @@ class X86Assembler FINAL : public Assembler { void EmitLabelLink(Label* label); void EmitLabelLink(NearLabel* label); - // Emit a 3 byte VEX Prefix - uint8_t EmitVexByteZero(bool is_two_byte); - uint8_t EmitVexByte1(bool r, bool x, bool b, int mmmmm); - uint8_t EmitVexByte2(bool w , int l , X86ManagedRegister vvv, int pp); - void EmitGenericShift(int rm, const Operand& operand, const Immediate& imm); void EmitGenericShift(int rm, const Operand& operand, Register shifter); diff --git a/compiler/utils/x86_64/assembler_x86_64.cc b/compiler/utils/x86_64/assembler_x86_64.cc index 9983eaeeea..bd31561937 100644 --- a/compiler/utils/x86_64/assembler_x86_64.cc +++ b/compiler/utils/x86_64/assembler_x86_64.cc @@ -603,56 +603,6 @@ void X86_64Assembler::divss(XmmRegister dst, const Address& src) { } -void X86_64Assembler::vfmadd231ps(XmmRegister acc, XmmRegister mul_left, XmmRegister mul_right) { - AssemblerBuffer::EnsureCapacity ensured(&buffer_); - uint8_t byte_zero = EmitVexByteZero(false /*is_two_byte*/); - uint8_t byte_one = EmitVexByte1(acc.NeedsRex(), false, mul_right.NeedsRex(), 2); - uint8_t byte_two = EmitVexByte2(false, 128, X86_64ManagedRegister::FromXmmRegister(mul_left.AsFloatRegister()), 1); - EmitUint8(byte_zero); - EmitUint8(byte_one); - EmitUint8(byte_two); - // Opcode field. - EmitUint8(0xB8); - EmitXmmRegisterOperand(acc.LowBits(), mul_right); -} - - -void X86_64Assembler::vfmsub231ps(XmmRegister acc, XmmRegister mul_left, XmmRegister mul_right) { - AssemblerBuffer::EnsureCapacity ensured(&buffer_); - uint8_t byte_zero = EmitVexByteZero(false /*is_two_byte*/); - uint8_t byte_one = EmitVexByte1(acc.NeedsRex(), false, mul_right.NeedsRex(), 2); - uint8_t byte_two = EmitVexByte2(false, 128, X86_64ManagedRegister::FromXmmRegister(mul_left.AsFloatRegister()), 1); - EmitUint8(byte_zero); - EmitUint8(byte_one); - EmitUint8(byte_two); - // Opcode field - EmitUint8(0xBA); - EmitXmmRegisterOperand(acc.LowBits(), mul_right); -} - -void X86_64Assembler::vfmadd231pd(XmmRegister acc, XmmRegister mul_left, XmmRegister mul_right) { - AssemblerBuffer::EnsureCapacity ensured(&buffer_); - uint8_t byte_zero = EmitVexByteZero(false /*is_two_byte*/); - uint8_t byte_one = EmitVexByte1(acc.NeedsRex(), false, mul_right.NeedsRex(), 2); - uint8_t byte_two = EmitVexByte2(true, 128, X86_64ManagedRegister::FromXmmRegister(mul_left.AsFloatRegister()), 1); - EmitUint8(byte_zero); - EmitUint8(byte_one); - EmitUint8(byte_two); - EmitUint8(0xB8); - EmitXmmRegisterOperand(acc.LowBits(), mul_right); -} - -void X86_64Assembler::vfmsub231pd(XmmRegister acc, XmmRegister mul_left, XmmRegister mul_right) { - AssemblerBuffer::EnsureCapacity ensured(&buffer_); - uint8_t byte_zero = EmitVexByteZero(false /*is_two_byte*/); - uint8_t byte_one = EmitVexByte1(acc.NeedsRex(), false, mul_right.NeedsRex(), 2); - uint8_t byte_two = EmitVexByte2(true, 128, X86_64ManagedRegister::FromXmmRegister(mul_left.AsFloatRegister()), 1); - EmitUint8(byte_zero); - EmitUint8(byte_one); - EmitUint8(byte_two); - EmitUint8(0xBA); - EmitXmmRegisterOperand(acc.LowBits(), mul_right); -} void X86_64Assembler::addps(XmmRegister dst, XmmRegister src) { AssemblerBuffer::EnsureCapacity ensured(&buffer_); EmitOptionalRex32(dst, src); @@ -3594,98 +3544,6 @@ void X86_64Assembler::EmitLabelLink(NearLabel* label) { label->LinkTo(position); } -uint8_t X86_64Assembler::EmitVexByteZero(bool is_two_byte) { - uint8_t vex_zero = 0xC0; - if (!is_two_byte) { - vex_zero |= 0xC4; - } else { - vex_zero |= 0xC5; - } - return vex_zero; -} - -uint8_t X86_64Assembler::EmitVexByte1(bool r, bool x, bool b, int mmmmm) { - // VEX Byte 1. - uint8_t vex_prefix = 0; - if (!r) { - vex_prefix |= 0x80; // VEX.R . - } - if (!x) { - vex_prefix |= 0x40; // VEX.X . - } - if (!b) { - vex_prefix |= 0x20; // VEX.B . - } - - // VEX.mmmmm. - switch (mmmmm) { - case 1: - // Implied 0F leading opcode byte. - vex_prefix |= 0x01; - break; - case 2: - // Implied leading 0F 38 opcode byte. - vex_prefix |= 0x02; - break; - case 3: - // Implied leading OF 3A opcode byte. - vex_prefix |= 0x03; - break; - default: - LOG(FATAL) << "unknown opcode bytes"; - } - - return vex_prefix; -} - -uint8_t X86_64Assembler::EmitVexByte2(bool w, int l, X86_64ManagedRegister operand, int pp) { - // VEX Byte 2. - uint8_t vex_prefix = 0; - if (w) { - vex_prefix |= 0x80; - } - // VEX.vvvv. - if (operand.IsXmmRegister()) { - XmmRegister vvvv = operand.AsXmmRegister(); - int inverted_reg = 15-static_cast<int>(vvvv.AsFloatRegister()); - uint8_t reg = static_cast<uint8_t>(inverted_reg); - vex_prefix |= ((reg & 0x0F) << 3); - } else if (operand.IsCpuRegister()) { - CpuRegister vvvv = operand.AsCpuRegister(); - int inverted_reg = 15 - static_cast<int>(vvvv.AsRegister()); - uint8_t reg = static_cast<uint8_t>(inverted_reg); - vex_prefix |= ((reg & 0x0F) << 3); - } - - // VEX.L. - if (l == 256) { - vex_prefix |= 0x04; - } - - // VEX.pp. - switch (pp) { - case 0: - // SIMD Pefix - None. - vex_prefix |= 0x00; - break; - case 1: - // SIMD Prefix - 66. - vex_prefix |= 0x01; - break; - case 2: - // SIMD Prefix - F3. - vex_prefix |= 0x02; - break; - case 3: - // SIMD Prefix - F2. - vex_prefix |= 0x03; - break; - default: - LOG(FATAL) << "unknown SIMD Prefix"; - } - - return vex_prefix; -} void X86_64Assembler::EmitGenericShift(bool wide, int reg_or_opcode, diff --git a/compiler/utils/x86_64/assembler_x86_64.h b/compiler/utils/x86_64/assembler_x86_64.h index d5779aa786..e4d72a7ba2 100644 --- a/compiler/utils/x86_64/assembler_x86_64.h +++ b/compiler/utils/x86_64/assembler_x86_64.h @@ -436,16 +436,6 @@ class X86_64Assembler FINAL : public Assembler { void divss(XmmRegister dst, XmmRegister src); void divss(XmmRegister dst, const Address& src); - // Mac Instructions - // For reference look at the Instruction reference volume 2C. - // The below URL is broken down in two lines. - // https://www.intel.com/content/www/us/en/architecture-and-technology/ - // 64-ia-32-architectures-software-developer-vol-2c-manual.html - void vfmadd231ps(XmmRegister acc, XmmRegister left, XmmRegister right); - void vfmadd231pd(XmmRegister acc, XmmRegister left, XmmRegister right); - void vfmsub231ps(XmmRegister acc, XmmRegister left, XmmRegister right); - void vfmsub231pd(XmmRegister acc, XmmRegister left, XmmRegister right); - void addps(XmmRegister dst, XmmRegister src); // no addr variant (for now) void subps(XmmRegister dst, XmmRegister src); void mulps(XmmRegister dst, XmmRegister src); @@ -931,11 +921,6 @@ class X86_64Assembler FINAL : public Assembler { void EmitLabelLink(Label* label); void EmitLabelLink(NearLabel* label); - // Emit a 3 byte VEX Prefix. - uint8_t EmitVexByteZero(bool is_two_byte); - uint8_t EmitVexByte1(bool r, bool x, bool b, int mmmmm); - uint8_t EmitVexByte2(bool w , int l , X86_64ManagedRegister operand, int pp); - void EmitGenericShift(bool wide, int rm, CpuRegister reg, const Immediate& imm); void EmitGenericShift(bool wide, int rm, CpuRegister operand, CpuRegister shifter); diff --git a/runtime/Android.bp b/runtime/Android.bp index 6ec626591a..8411982b30 100644 --- a/runtime/Android.bp +++ b/runtime/Android.bp @@ -31,7 +31,6 @@ libart_cc_defaults { "aot_class_linker.cc", "art_field.cc", "art_method.cc", - "backtrace_helper.cc", "barrier.cc", "base/mem_map_arena_pool.cc", "base/mutex.cc", diff --git a/runtime/arch/x86/instruction_set_features_x86.cc b/runtime/arch/x86/instruction_set_features_x86.cc index 745e925611..98462512da 100644 --- a/runtime/arch/x86/instruction_set_features_x86.cc +++ b/runtime/arch/x86/instruction_set_features_x86.cc @@ -35,7 +35,6 @@ static constexpr const char* x86_known_variants[] = { "atom", "sandybridge", "silvermont", - "kabylake" }; static constexpr const char* x86_variants_with_ssse3[] = { @@ -47,27 +46,16 @@ static constexpr const char* x86_variants_with_ssse3[] = { static constexpr const char* x86_variants_with_sse4_1[] = { "sandybridge", "silvermont", - "kabylake" }; static constexpr const char* x86_variants_with_sse4_2[] = { "sandybridge", "silvermont", - "kabylake" }; static constexpr const char* x86_variants_with_popcnt[] = { "sandybridge", "silvermont", - "kabylake" -}; - -static constexpr const char* x86_variants_with_avx[] = { - "kabylake", -}; - -static constexpr const char* x86_variants_with_avx2[] = { - "kabylake", }; X86FeaturesUniquePtr X86InstructionSetFeatures::Create(bool x86_64, @@ -105,12 +93,9 @@ X86FeaturesUniquePtr X86InstructionSetFeatures::FromVariant( bool has_SSE4_2 = FindVariantInArray(x86_variants_with_sse4_2, arraysize(x86_variants_with_sse4_2), variant); - bool has_AVX = FindVariantInArray(x86_variants_with_avx, - arraysize(x86_variants_with_avx), - variant); - bool has_AVX2 = FindVariantInArray(x86_variants_with_avx2, - arraysize(x86_variants_with_avx2), - variant); + bool has_AVX = false; + bool has_AVX2 = false; + bool has_POPCNT = FindVariantInArray(x86_variants_with_popcnt, arraysize(x86_variants_with_popcnt), variant); diff --git a/runtime/arch/x86/instruction_set_features_x86.h b/runtime/arch/x86/instruction_set_features_x86.h index f5974cc2e1..57cf4b2741 100644 --- a/runtime/arch/x86/instruction_set_features_x86.h +++ b/runtime/arch/x86/instruction_set_features_x86.h @@ -67,8 +67,6 @@ class X86InstructionSetFeatures : public InstructionSetFeatures { bool HasPopCnt() const { return has_POPCNT_; } - bool HasAVX2() const { return has_AVX2_; } - protected: // Parse a string of the form "ssse3" adding these to a new InstructionSetFeatures. virtual std::unique_ptr<const InstructionSetFeatures> diff --git a/runtime/backtrace_helper.cc b/runtime/backtrace_helper.cc deleted file mode 100644 index c2c0ceeaee..0000000000 --- a/runtime/backtrace_helper.cc +++ /dev/null @@ -1,76 +0,0 @@ -/* - * Copyright (C) 2018 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 "backtrace_helper.h" - -#if defined(__linux__) - -#include <backtrace/Backtrace.h> -#include <backtrace/BacktraceMap.h> - -#include <unistd.h> -#include <sys/types.h> - -#else - -// For UNUSED -#include "base/macros.h" - -#endif - -namespace art { - -// We only really support libbacktrace on linux which is unfortunate but since this is only for -// gcstress this isn't a huge deal. -#if defined(__linux__) - -void BacktraceCollector::Collect() { - std::unique_ptr<BacktraceMap> map(BacktraceMap::Create(getpid())); - // We don't care about the function names. Turning this off makes everything significantly faster. - map->SetResolveNames(false); - std::unique_ptr<Backtrace> backtrace(Backtrace::Create(BACKTRACE_CURRENT_PROCESS, - BACKTRACE_CURRENT_THREAD, - map.get())); - backtrace->SetSkipFrames(true); - if (!backtrace->Unwind(skip_count_, nullptr)) { - return; - } - for (Backtrace::const_iterator it = backtrace->begin(); - max_depth_ > num_frames_ && it != backtrace->end(); - ++it) { - out_frames_[num_frames_++] = static_cast<uintptr_t>(it->pc); - } -} - -#else - -#pragma clang diagnostic push -#pragma clang diagnostic warning "-W#warnings" -#warning "Backtrace collector is not implemented. GCStress cannot be used." -#pragma clang diagnostic pop - -// We only have an implementation for linux. On other plaforms just return nothing. This is not -// really correct but we only use this for hashing and gcstress so it's not too big a deal. -void BacktraceCollector::Collect() { - UNUSED(skip_count_); - UNUSED(out_frames_); - UNUSED(max_depth_); - num_frames_ = 0; -} - -#endif - -} // namespace art diff --git a/runtime/backtrace_helper.h b/runtime/backtrace_helper.h index 8eda3fa0a1..ace118c50b 100644 --- a/runtime/backtrace_helper.h +++ b/runtime/backtrace_helper.h @@ -17,12 +17,11 @@ #ifndef ART_RUNTIME_BACKTRACE_HELPER_H_ #define ART_RUNTIME_BACKTRACE_HELPER_H_ -#include <stddef.h> -#include <stdint.h> +#include <unwind.h> namespace art { -// Using libbacktrace +// Based on debug malloc logic from libc/bionic/debug_stacktrace.cpp. class BacktraceCollector { public: BacktraceCollector(uintptr_t* out_frames, size_t max_depth, size_t skip_count) @@ -33,9 +32,25 @@ class BacktraceCollector { } // Collect the backtrace, do not call more than once. - void Collect(); + void Collect() { + _Unwind_Backtrace(&Callback, this); + } private: + static _Unwind_Reason_Code Callback(_Unwind_Context* context, void* arg) { + auto* const state = reinterpret_cast<BacktraceCollector*>(arg); + const uintptr_t ip = _Unwind_GetIP(context); + // The first stack frame is get_backtrace itself. Skip it. + if (ip != 0 && state->skip_count_ > 0) { + --state->skip_count_; + return _URC_NO_REASON; + } + // ip may be off for ARM but it shouldn't matter since we only use it for hashing. + state->out_frames_[state->num_frames_] = ip; + state->num_frames_++; + return state->num_frames_ >= state->max_depth_ ? _URC_END_OF_STACK : _URC_NO_REASON; + } + uintptr_t* const out_frames_ = nullptr; size_t num_frames_ = 0u; const size_t max_depth_ = 0u; 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/tools/ahat/etc/ahat_api.txt b/tools/ahat/etc/ahat_api.txt index f60c1a84fa..8c7ff641fe 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); } 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 20f368f4ff..a321ec0785 100644 --- a/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java +++ b/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java @@ -82,7 +82,6 @@ public abstract class AhatInstance implements Diffable<AhatInstance>, void initialize(AhatHeap heap, Site site, AhatClassObj classObj) { mHeap = heap; mSite = site; - site.addInstance(this); mClassObj = classObj; } 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 d9c7a19431..12d3755784 100644 --- a/tools/ahat/src/main/com/android/ahat/heapdump/AhatSnapshot.java +++ b/tools/ahat/src/main/com/android/ahat/heapdump/AhatSnapshot.java @@ -47,15 +47,19 @@ public class AhatSnapshot implements Diffable<AhatSnapshot> { mHeaps = heaps; mRootSite = rootSite; - // Update registered native allocation size. - for (AhatInstance cleaner : mInstances) { - AhatInstance.RegisteredNativeAllocation nra = cleaner.asRegisteredNativeAllocation(); + AhatInstance.computeReachability(mSuperRoot, progress, mInstances.size()); + + for (AhatInstance inst : mInstances) { + // Add this instance to its site. + inst.getSite().addInstance(inst); + + // Update registered native allocation size. + AhatInstance.RegisteredNativeAllocation nra = inst.asRegisteredNativeAllocation(); if (nra != null) { nra.referent.addRegisteredNativeSize(nra.size); } } - AhatInstance.computeReachability(mSuperRoot, progress, mInstances.size()); DominatorsComputation.computeDominators(mSuperRoot, progress, mInstances.size()); AhatInstance.computeRetainedSize(mSuperRoot, mHeaps.size()); 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"); |