Merge "ART: Delete code optimizing a%1 and a%-1 from InstructionCodeGeneratorARM64"
diff --git a/compiler/Android.bp b/compiler/Android.bp
index e1d382f..eff4955 100644
--- a/compiler/Android.bp
+++ b/compiler/Android.bp
@@ -161,7 +161,6 @@
"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 074f249..0ebf4be 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 @@
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 5880876..086ae07 100644
--- a/compiler/optimizing/code_generator_vector_x86.cc
+++ b/compiler/optimizing/code_generator_vector_x86.cc
@@ -1125,59 +1125,13 @@
}
}
-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 4795e86..4d31ab6 100644
--- a/compiler/optimizing/code_generator_vector_x86_64.cc
+++ b/compiler/optimizing/code_generator_vector_x86_64.cc
@@ -1098,61 +1098,13 @@
}
}
-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 b3f67d6..0000000
--- 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 1fb199f..0000000
--- 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 b4f9993..95fb5ab 100644
--- a/compiler/optimizing/nodes_vector.h
+++ b/compiler/optimizing/nodes_vector.h
@@ -931,6 +931,9 @@
// 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 @@
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 3c803ab..142ddb5 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 @@
#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 @@
#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 @@
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 a9fafa0..88b283c 100644
--- a/compiler/optimizing/optimization.h
+++ b/compiler/optimizing/optimization.h
@@ -101,7 +101,6 @@
#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 f4bafcb..2f530a9 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -531,8 +531,7 @@
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 @@
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 3e1a36d..a65fbcc 100644
--- a/compiler/optimizing/stack_map_stream.cc
+++ b/compiler/optimizing/stack_map_stream.cc
@@ -156,26 +156,6 @@
}
}
-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 @@
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 ed865b1..203c2cd 100644
--- a/compiler/optimizing/stack_map_stream.h
+++ b/compiler/optimizing/stack_map_stream.h
@@ -42,7 +42,6 @@
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 @@
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 @@
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 9ed90a4..42f9789 100644
--- a/compiler/optimizing/stack_map_test.cc
+++ b/compiler/optimizing/stack_map_test.cc
@@ -758,56 +758,4 @@
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 c2ce03b..86f9010 100644
--- a/compiler/utils/x86/assembler_x86.cc
+++ b/compiler/utils/x86/assembler_x86.cc
@@ -525,58 +525,6 @@
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 @@
}
-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 8c9ce82..e42c4c9 100644
--- a/compiler/utils/x86/assembler_x86.h
+++ b/compiler/utils/x86/assembler_x86.h
@@ -397,12 +397,6 @@
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 @@
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 9983eae..bd31561 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::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 @@
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 d5779aa..e4d72a7 100644
--- a/compiler/utils/x86_64/assembler_x86_64.h
+++ b/compiler/utils/x86_64/assembler_x86_64.h
@@ -436,16 +436,6 @@
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 @@
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 6ec6265..8411982 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -31,7 +31,6 @@
"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 745e925..9846251 100644
--- a/runtime/arch/x86/instruction_set_features_x86.cc
+++ b/runtime/arch/x86/instruction_set_features_x86.cc
@@ -35,7 +35,6 @@
"atom",
"sandybridge",
"silvermont",
- "kabylake"
};
static constexpr const char* x86_variants_with_ssse3[] = {
@@ -47,27 +46,16 @@
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 @@
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 f5974cc..57cf4b2 100644
--- a/runtime/arch/x86/instruction_set_features_x86.h
+++ b/runtime/arch/x86/instruction_set_features_x86.h
@@ -67,8 +67,6 @@
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 c2c0cee..0000000
--- 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 8eda3fa..ace118c 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 @@
}
// 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 379292d..505e183 100644
--- a/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc
+++ b/runtime/entrypoints/quick/quick_trampoline_entrypoints.cc
@@ -357,30 +357,6 @@
}
}
- 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 @@
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 @@
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 ef2a5d7..f8ec665 100644
--- a/runtime/oat.h
+++ b/runtime/oat.h
@@ -32,8 +32,8 @@
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 7e46eb7..9fa9d84 100644
--- a/runtime/stack_map.cc
+++ b/runtime/stack_map.cc
@@ -41,7 +41,6 @@
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 @@
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 @@
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 2f2053a..26b95b0 100644
--- a/runtime/stack_map.h
+++ b/runtime/stack_map.h
@@ -208,22 +208,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 @@
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 @@
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 @@
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 f60c1a8..8c7ff64 100644
--- a/tools/ahat/etc/ahat_api.txt
+++ b/tools/ahat/etc/ahat_api.txt
@@ -8,7 +8,20 @@
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 0000000..dda0e83
--- /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 903211e..7ab52cb 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 @@
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 @@
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 @@
* @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);
- }
- }
- }
- }
- 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;
- }
- }
+ Dominators.Graph<Node> graph = new Dominators.Graph<Node>() {
+ @Override
+ public void setDominatorsComputationState(Node node, Object state) {
+ node.setDominatorsComputationState(state);
}
- // 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 Object getDominatorsComputationState(Node node) {
+ return node.getDominatorsComputationState();
}
- 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 Iterable<? extends Node> getReferencesForDominators(Node node) {
+ return node.getReferencesForDominators();
}
- }
- }
- // 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);
- }
+ @Override
+ public void setDominator(Node node, Node dominator) {
+ node.setDominator(dominator);
+ }
+ };
- // 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 20f368f..a321ec0 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 @@
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 d9c7a19..12d3755 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 @@
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 d9af363..955b59f 100644
--- a/tools/ahat/src/test/com/android/ahat/DominatorsTest.java
+++ b/tools/ahat/src/test/com/android/ahat/DominatorsTest.java
@@ -16,15 +16,298 @@
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 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<>();
+
+ @Override
+ public void setDominatorsComputationState(String node, Object state) {
+ states.put(node, state);
+ }
+
+ @Override public Object getDominatorsComputationState(String node) {
+ return states.get(node);
+ }
+
+ @Override
+ public Collection<String> getReferencesForDominators(String node) {
+ return depends.get(node);
+ }
+
+ @Override
+ public void setDominator(String node, String dominator) {
+ dominators.put(node, dominator);
+ }
+
+ /**
+ * Define a node in the graph, including all its outgoing edges.
+ */
+ public void node(String src, String... dsts) {
+ depends.put(src, Arrays.asList(dsts));
+ }
+
+ /**
+ * Get the computed dominator for a given node.
+ */
+ public String dom(String node) {
+ return dominators.get(node);
+ }
+ }
+
+ @Test
+ public void singleNode() {
+ // --> n
+ // Trivial case.
+ 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.
+ Graph graph = new Graph();
+ graph.node("parent", "child");
+ graph.node("child");
+ new Dominators(graph).computeDominators("parent");
+
+ assertEquals("parent", graph.dom("child"));
+ }
+
+ @Test
+ public void reachableTwoWays() {
+ // /-> right -->\
+ // --> parent child
+ // \-> left --->/
+ // The child node can be reached either by right or by left.
+ 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
+ public void reachableDirectAndIndirect() {
+ // /-> right -->\
+ // --> parent -----------> child
+ // The child node can be reached either by right or parent.
+ 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.
+ 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
+ public void childSelfLoop() {
+ // --> parent --> child -\
+ // \<---/
+ // The child points back to itself.
+ Graph graph = new Graph();
+ graph.node("parent", "child");
+ graph.node("child", "child");
+ new Dominators(graph).computeDominators("parent");
+
+ assertEquals("parent", graph.dom("child"));
+ }
+
+ @Test
+ public void singleEntryLoop() {
+ // --> parent --> a --> b --> c -\
+ // \<------------/
+ // There is a loop in the graph, with only one way into the loop.
+ 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
+ public void multiEntryLoop() {
+ // --> parent --> right --> a --> b ----\
+ // \ \<-- c <---/
+ // \--> left --->--------/
+ // There is a loop in the graph, with two different ways to enter the
+ // loop.
+ 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
+ public void dominatorOverwrite() {
+ // /---------> right <--\
+ // --> parent --> child <--/ /
+ // \---> left ---------/
+ // Test a strange case where we have had trouble in the past with a
+ // 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'.
+ 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.
+ Graph graph = new Graph();
+ String root = "end";
+ graph.node(root);
+
+ for (int i = 0; i < 10000; ++i) {
+ String child = root;
+ root = "n" + i;
+ graph.node(root, child);
+ }
+
+ new Dominators(graph).computeDominators(root);
+ }
+
+ @Test
+ public void hiddenRevisit() {
+ // /-> left ---->---------\
+ // --> parent \---> a --> b --> c
+ // \-> right -/
+ // Test a case we have had trouble in the past.
+ // When a's dominator is updated from left to parent, that should trigger
+ // all reachable children's dominators to be updated too. In particular,
+ // c's dominator should be updated, even though b's dominator is
+ // unchanged.
+ 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
+ public void preUndominatedUpdate() {
+ // /--------->--------\
+ // / /---->----\
+ // --> p -> a --> b --> c --> d --> e
+ // \---------->----------/
+ // Test a case we have had trouble in the past.
+ // The candidate dominator for e is revised from d to a, then d is shown
+ // 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.
+ 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
+ public void twiceRevisit() {
+ // /---->---\
+ // / /--> f -->-\
+ // --> a --> b -->--x---> c --> d
+ // \----------->----/
+ // A regression test for a bug where we failed to ever revisit a node more
+ // than once. The node c is revisited a first time to bring its dominator
+ // 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>();
@@ -65,248 +348,13 @@
}
@Test
- public void singleNode() {
- // --> n
- // Trivial case.
- Node n = new Node("n");
- n.computeDominators();
- }
-
- @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);
-
- parent.computeDominators();
- assertEquals(parent, child.dominator);
- }
-
- @Test
- public void reachableTwoWays() {
- // /-> right -->\
- // --> 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);
- }
-
- @Test
- public void reachableDirectAndIndirect() {
- // /-> 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);
- }
-
- @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);
- }
-
- @Test
- public void childSelfLoop() {
- // --> 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);
-
- parent.computeDominators();
- assertEquals(parent, child.dominator);
- }
-
- @Test
- public void singleEntryLoop() {
- // --> 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);
- }
-
- @Test
- public void multiEntryLoop() {
- // --> parent --> right --> a --> b ----\
- // \ \<-- c <---/
- // \--> 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);
- }
-
- @Test
- public void dominatorOverwrite() {
- // /---------> right <--\
- // --> parent --> child <--/ /
- // \---> left ---------/
- // Test a strange case where we have had trouble in the past with a
- // 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);
- }
-
- @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;
- for (int i = 0; i < 10000; ++i) {
- Node node = new Node("n" + i);
- curr.depends.add(node);
- curr = node;
- }
-
- root.computeDominators();
- }
-
- @Test
- public void hiddenRevisit() {
- // /-> left ---->---------\
- // --> parent \---> a --> b --> c
- // \-> right -/
- // Test a case we have had trouble in the past.
- // When a's dominator is updated from left to parent, that should trigger
- // 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);
- }
-
- @Test
- public void preUndominatedUpdate() {
- // /--------->--------\
- // / /---->----\
- // --> p -> a --> b --> c --> d --> e
- // \---------->----------/
- // Test a case we have had trouble in the past.
- // The candidate dominator for e is revised from d to a, then d is shown
- // 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);
- }
-
- @Test
- public void twiceRevisit() {
+ public void twiceRevisitOldApi() {
// /---->---\
// / /--> f -->-\
// --> a --> b -->--x---> c --> d
// \----------->----/
- // A regression test for a bug where we failed to ever revisit a node more
- // than once. The node c is revisited a first time to bring its dominator
- // 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.
+ // 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");