ART: Refactor SsaBuilder for more precise typing info
This reverts commit 68289a531484d26214e09f1eadd9833531a3bc3c.
Now uses Primitive::Is64BitType instead of Primitive::ComponentSize
because it was incorrectly optimized by GCC.
Bug: 26208284
Bug: 24252151
Bug: 24252100
Bug: 22538329
Bug: 25786318
Change-Id: Ib39f3da2b92bc5be5d76f4240a77567d82c6bebe
diff --git a/compiler/Android.mk b/compiler/Android.mk
index bdd9a84..f0bf499 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -92,7 +92,6 @@
optimizing/parallel_move_resolver.cc \
optimizing/pc_relative_fixups_x86.cc \
optimizing/prepare_for_register_allocation.cc \
- optimizing/primitive_type_propagation.cc \
optimizing/reference_type_propagation.cc \
optimizing/register_allocator.cc \
optimizing/sharpening.cc \
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 4c3f66a..dc75ff1 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1590,15 +1590,18 @@
HGraph* graph = GetGraph();
HInstruction* zero;
switch (type) {
- case Primitive::Type::kPrimNot: zero = graph->GetNullConstant(); break;
- case Primitive::Type::kPrimFloat: zero = graph->GetFloatConstant(0); break;
- case Primitive::Type::kPrimDouble: zero = graph->GetDoubleConstant(0); break;
+ case Primitive::kPrimNot: zero = graph->GetNullConstant(); break;
+ case Primitive::kPrimFloat: zero = graph->GetFloatConstant(0); break;
+ case Primitive::kPrimDouble: zero = graph->GetDoubleConstant(0); break;
default: zero = graph->GetConstant(type, 0); break;
}
HPhi* phi = new (graph->GetArena())
HPhi(graph->GetArena(), kNoRegNumber, /*number_of_inputs*/ 2, HPhi::ToPhiType(type));
phi->SetRawInputAt(0, instruction);
phi->SetRawInputAt(1, zero);
+ if (type == Primitive::kPrimNot) {
+ phi->SetReferenceTypeInfo(instruction->GetReferenceTypeInfo());
+ }
new_preheader->AddPhi(phi);
return phi;
}
diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc
index e469c8d..a8f65bf 100644
--- a/compiler/optimizing/constant_folding_test.cc
+++ b/compiler/optimizing/constant_folding_test.cc
@@ -32,7 +32,7 @@
/**
* Fixture class for the constant folding and dce tests.
*/
-class ConstantFoldingTest : public testing::Test {
+class ConstantFoldingTest : public CommonCompilerTest {
public:
ConstantFoldingTest() : pool_(), allocator_(&pool_) {
graph_ = CreateGraph(&allocator_);
@@ -56,7 +56,7 @@
const std::string& expected_after_dce,
std::function<void(HGraph*)> check_after_cf) {
ASSERT_NE(graph_, nullptr);
- graph_->TryBuildingSsa();
+ TransformToSsa(graph_);
StringPrettyPrinter printer_before(graph_);
printer_before.VisitInsertionOrder();
diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc
index 2c6a1ef..f0f98ef 100644
--- a/compiler/optimizing/dead_code_elimination_test.cc
+++ b/compiler/optimizing/dead_code_elimination_test.cc
@@ -26,6 +26,8 @@
namespace art {
+class DeadCodeEliminationTest : public CommonCompilerTest {};
+
static void TestCode(const uint16_t* data,
const std::string& expected_before,
const std::string& expected_after) {
@@ -34,7 +36,7 @@
HGraph* graph = CreateCFG(&allocator, data);
ASSERT_NE(graph, nullptr);
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
StringPrettyPrinter printer_before(graph);
printer_before.VisitInsertionOrder();
@@ -55,7 +57,6 @@
ASSERT_EQ(actual_after, expected_after);
}
-
/**
* Small three-register program.
*
@@ -69,7 +70,7 @@
* L1: v2 <- v0 + v1 5. add-int v2, v0, v1
* return-void 7. return
*/
-TEST(DeadCodeElimination, AdditionAndConditionalJump) {
+TEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) {
const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 1 << 8 | 1 << 12,
Instruction::CONST_4 | 0 << 8 | 0 << 12,
@@ -131,7 +132,7 @@
* L3: v2 <- v1 + 4 11. add-int/lit16 v2, v1, #+4
* return 13. return-void
*/
-TEST(DeadCodeElimination, AdditionsAndInconditionalJumps) {
+TEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) {
const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 0 << 8 | 0 << 12,
Instruction::CONST_4 | 1 << 8 | 1 << 12,
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index dfc363f..f3c1dbe 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -24,6 +24,7 @@
#include "base/arena_containers.h"
#include "base/bit_vector-inl.h"
#include "base/stringprintf.h"
+#include "handle_scope-inl.h"
namespace art {
@@ -594,6 +595,17 @@
}
}
}
+
+ // Ensure that reference type instructions have reference type info.
+ if (instruction->GetType() == Primitive::kPrimNot) {
+ ScopedObjectAccess soa(Thread::Current());
+ if (!instruction->GetReferenceTypeInfo().IsValid()) {
+ AddError(StringPrintf("Reference type instruction %s:%d does not have "
+ "valid reference type information.",
+ instruction->DebugName(),
+ instruction->GetId()));
+ }
+ }
}
static Primitive::Type PrimitiveKind(Primitive::Type type) {
diff --git a/compiler/optimizing/graph_checker_test.cc b/compiler/optimizing/graph_checker_test.cc
index fee56c7..d10df4c 100644
--- a/compiler/optimizing/graph_checker_test.cc
+++ b/compiler/optimizing/graph_checker_test.cc
@@ -17,8 +17,6 @@
#include "graph_checker.h"
#include "optimizing_unit_test.h"
-#include "gtest/gtest.h"
-
namespace art {
/**
@@ -43,7 +41,6 @@
return graph;
}
-
static void TestCode(const uint16_t* data) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
@@ -61,8 +58,7 @@
HGraph* graph = CreateCFG(&allocator, data);
ASSERT_NE(graph, nullptr);
- graph->BuildDominatorTree();
- graph->TransformToSsa();
+ TransformToSsa(graph);
SSAChecker ssa_checker(graph);
ssa_checker.Run();
@@ -145,7 +141,9 @@
ASSERT_FALSE(graph_checker.IsValid());
}
-TEST(SSAChecker, SSAPhi) {
+class SSACheckerTest : public CommonCompilerTest {};
+
+TEST_F(SSACheckerTest, SSAPhi) {
// This code creates one Phi function during the conversion to SSA form.
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index e9fdb84..5f1328f 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -30,6 +30,7 @@
#include "optimization.h"
#include "reference_type_propagation.h"
#include "register_allocator.h"
+#include "ssa_builder.h"
#include "ssa_liveness_analysis.h"
#include "utils/assembler.h"
@@ -505,7 +506,7 @@
} else {
StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId();
}
- } else if ((IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName)
+ } else if ((IsPass(SsaBuilder::kSsaBuilderPassName)
|| IsPass(HInliner::kInlinerPassName))
&& (instruction->GetType() == Primitive::kPrimNot)) {
ReferenceTypeInfo info = instruction->IsLoadClass()
@@ -519,21 +520,15 @@
StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha;
} else if (instruction->IsLoadClass()) {
StartAttributeStream("klass") << "unresolved";
- } else if (instruction->IsNullConstant()) {
+ } else {
// The NullConstant may be added to the graph during other passes that happen between
// ReferenceTypePropagation and Inliner (e.g. InstructionSimplifier). If the inliner
// doesn't run or doesn't inline anything, the NullConstant remains untyped.
// So we should check NullConstants for validity only after reference type propagation.
- //
- // Note: The infrastructure to properly type NullConstants everywhere is to complex to add
- // for the benefits.
- StartAttributeStream("klass") << "not_set";
- DCHECK(!is_after_pass_
- || !IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName))
- << " Expected a valid rti after reference type propagation";
- } else {
- DCHECK(!is_after_pass_)
- << "Expected a valid rti after reference type propagation";
+ DCHECK(graph_in_bad_state_ ||
+ (!is_after_pass_ && IsPass(SsaBuilder::kSsaBuilderPassName)))
+ << instruction->DebugName() << instruction->GetId() << " has invalid rti "
+ << (is_after_pass_ ? "after" : "before") << " pass " << pass_name_;
}
}
if (disasm_info_ != nullptr) {
diff --git a/compiler/optimizing/gvn_test.cc b/compiler/optimizing/gvn_test.cc
index 78cb7d4..1f4eaf3 100644
--- a/compiler/optimizing/gvn_test.cc
+++ b/compiler/optimizing/gvn_test.cc
@@ -21,11 +21,11 @@
#include "optimizing_unit_test.h"
#include "side_effects_analysis.h"
-#include "gtest/gtest.h"
-
namespace art {
-TEST(GVNTest, LocalFieldElimination) {
+class GVNTest : public CommonCompilerTest {};
+
+TEST_F(GVNTest, LocalFieldElimination) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
ScopedNullHandle<mirror::DexCache> dex_cache;
@@ -100,7 +100,7 @@
ASSERT_EQ(different_offset->GetBlock(), block);
ASSERT_EQ(use_after_kill->GetBlock(), block);
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
GVNOptimization(graph, side_effects).Run();
@@ -110,7 +110,7 @@
ASSERT_EQ(use_after_kill->GetBlock(), block);
}
-TEST(GVNTest, GlobalFieldElimination) {
+TEST_F(GVNTest, GlobalFieldElimination) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
ScopedNullHandle<mirror::DexCache> dex_cache;
@@ -182,7 +182,7 @@
0));
join->AddInstruction(new (&allocator) HExit());
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
GVNOptimization(graph, side_effects).Run();
@@ -193,7 +193,7 @@
ASSERT_TRUE(join->GetFirstInstruction()->IsExit());
}
-TEST(GVNTest, LoopFieldElimination) {
+TEST_F(GVNTest, LoopFieldElimination) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
ScopedNullHandle<mirror::DexCache> dex_cache;
@@ -288,7 +288,7 @@
ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
ASSERT_EQ(field_get_in_exit->GetBlock(), exit);
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
{
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
@@ -316,7 +316,7 @@
}
// Test that inner loops affect the side effects of the outer loop.
-TEST(GVNTest, LoopSideEffects) {
+TEST_F(GVNTest, LoopSideEffects) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
ScopedNullHandle<mirror::DexCache> dex_cache;
@@ -364,7 +364,7 @@
inner_loop_exit->AddInstruction(new (&allocator) HGoto());
outer_loop_exit->AddInstruction(new (&allocator) HExit());
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn(
*outer_loop_header->GetLoopInformation()));
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 5de94f4..776c115 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -18,7 +18,6 @@
#include "base/arena_allocator.h"
#include "builder.h"
-#include "gtest/gtest.h"
#include "induction_var_analysis.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
@@ -28,7 +27,7 @@
/**
* Fixture class for the InductionVarAnalysis tests.
*/
-class InductionVarAnalysisTest : public testing::Test {
+class InductionVarAnalysisTest : public CommonCompilerTest {
public:
InductionVarAnalysisTest() : pool_(), allocator_(&pool_) {
graph_ = CreateGraph(&allocator_);
@@ -102,6 +101,7 @@
basic_[d] = new (&allocator_) HLocal(d);
entry_->AddInstruction(basic_[d]);
loop_preheader_[d]->AddInstruction(new (&allocator_) HStoreLocal(basic_[d], constant0_));
+ loop_preheader_[d]->AddInstruction(new (&allocator_) HGoto());
HInstruction* load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt);
loop_header_[d]->AddInstruction(load);
HInstruction* compare = new (&allocator_) HLessThan(load, constant100_);
@@ -168,7 +168,7 @@
// Performs InductionVarAnalysis (after proper set up).
void PerformInductionVarAnalysis() {
- ASSERT_TRUE(graph_->TryBuildingSsa());
+ TransformToSsa(graph_);
iva_ = new (&allocator_) HInductionVarAnalysis(graph_);
iva_->Run();
}
@@ -212,7 +212,7 @@
// ..
// }
BuildLoopNest(10);
- ASSERT_TRUE(graph_->TryBuildingSsa());
+ TransformToSsa(graph_);
ASSERT_EQ(entry_->GetLoopInformation(), nullptr);
for (int d = 0; d < 1; d++) {
ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(),
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index 5c0bdd7..eda9c01 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -16,7 +16,6 @@
#include "base/arena_allocator.h"
#include "builder.h"
-#include "gtest/gtest.h"
#include "induction_var_analysis.h"
#include "induction_var_range.h"
#include "nodes.h"
@@ -29,7 +28,7 @@
/**
* Fixture class for the InductionVarRange tests.
*/
-class InductionVarRangeTest : public testing::Test {
+class InductionVarRangeTest : public CommonCompilerTest {
public:
InductionVarRangeTest()
: pool_(),
@@ -113,7 +112,7 @@
/** Constructs SSA and performs induction variable analysis. */
void PerformInductionVarAnalysis() {
- ASSERT_TRUE(graph_->TryBuildingSsa());
+ TransformToSsa(graph_);
iva_->Run();
}
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 9842137..0e50416 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -33,6 +33,7 @@
#include "reference_type_propagation.h"
#include "register_allocator.h"
#include "sharpening.h"
+#include "ssa_builder.h"
#include "ssa_phi_elimination.h"
#include "scoped_thread_state_change.h"
#include "thread.h"
@@ -526,7 +527,7 @@
return false;
}
- if (!callee_graph->TryBuildingSsa()) {
+ if (callee_graph->TryBuildingSsa(handles_) != kBuildSsaSuccess) {
VLOG(compiler) << "Method " << PrettyMethod(method_index, callee_dex_file)
<< " could not be transformed to SSA";
return false;
@@ -561,14 +562,12 @@
// Run simple optimizations on the graph.
HDeadCodeElimination dce(callee_graph, stats_);
HConstantFolding fold(callee_graph);
- ReferenceTypePropagation type_propagation(callee_graph, handles_);
HSharpening sharpening(callee_graph, codegen_, dex_compilation_unit, compiler_driver_);
InstructionSimplifier simplify(callee_graph, stats_);
IntrinsicsRecognizer intrinsics(callee_graph, compiler_driver_);
HOptimization* optimizations[] = {
&intrinsics,
- &type_propagation,
&sharpening,
&simplify,
&fold,
@@ -689,42 +688,36 @@
DCHECK_EQ(graph_, return_replacement->GetBlock()->GetGraph());
}
- // When merging the graph we might create a new NullConstant in the caller graph which does
- // not have the chance to be typed. We assign the correct type here so that we can keep the
- // assertion that every reference has a valid type. This also simplifies checks along the way.
- HNullConstant* null_constant = graph_->GetNullConstant();
- if (!null_constant->GetReferenceTypeInfo().IsValid()) {
- ReferenceTypeInfo::TypeHandle obj_handle =
- handles_->NewHandle(class_linker->GetClassRoot(ClassLinker::kJavaLangObject));
- null_constant->SetReferenceTypeInfo(
- ReferenceTypeInfo::Create(obj_handle, false /* is_exact */));
- }
-
// Check the integrity of reference types and run another type propagation if needed.
- if ((return_replacement != nullptr)
- && (return_replacement->GetType() == Primitive::kPrimNot)) {
- if (!return_replacement->GetReferenceTypeInfo().IsValid()) {
- // Make sure that we have a valid type for the return. We may get an invalid one when
- // we inline invokes with multiple branches and create a Phi for the result.
- // TODO: we could be more precise by merging the phi inputs but that requires
- // some functionality from the reference type propagation.
- DCHECK(return_replacement->IsPhi());
- size_t pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
- ReferenceTypeInfo::TypeHandle return_handle =
- handles_->NewHandle(resolved_method->GetReturnType(true /* resolve */, pointer_size));
- return_replacement->SetReferenceTypeInfo(ReferenceTypeInfo::Create(
- return_handle, return_handle->CannotBeAssignedFromOtherTypes() /* is_exact */));
- }
+ if (return_replacement != nullptr) {
+ if (return_replacement->GetType() == Primitive::kPrimNot) {
+ if (!return_replacement->GetReferenceTypeInfo().IsValid()) {
+ // Make sure that we have a valid type for the return. We may get an invalid one when
+ // we inline invokes with multiple branches and create a Phi for the result.
+ // TODO: we could be more precise by merging the phi inputs but that requires
+ // some functionality from the reference type propagation.
+ DCHECK(return_replacement->IsPhi());
+ size_t pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
+ ReferenceTypeInfo::TypeHandle return_handle =
+ handles_->NewHandle(resolved_method->GetReturnType(true /* resolve */, pointer_size));
+ return_replacement->SetReferenceTypeInfo(ReferenceTypeInfo::Create(
+ return_handle, return_handle->CannotBeAssignedFromOtherTypes() /* is_exact */));
+ }
- if (do_rtp) {
- // If the return type is a refinement of the declared type run the type propagation again.
- ReferenceTypeInfo return_rti = return_replacement->GetReferenceTypeInfo();
- ReferenceTypeInfo invoke_rti = invoke_instruction->GetReferenceTypeInfo();
- if (invoke_rti.IsStrictSupertypeOf(return_rti)
- || (return_rti.IsExact() && !invoke_rti.IsExact())
- || !return_replacement->CanBeNull()) {
- ReferenceTypePropagation rtp_fixup(graph_, handles_);
- rtp_fixup.Run();
+ if (do_rtp) {
+ // If the return type is a refinement of the declared type run the type propagation again.
+ ReferenceTypeInfo return_rti = return_replacement->GetReferenceTypeInfo();
+ ReferenceTypeInfo invoke_rti = invoke_instruction->GetReferenceTypeInfo();
+ if (invoke_rti.IsStrictSupertypeOf(return_rti)
+ || (return_rti.IsExact() && !invoke_rti.IsExact())
+ || !return_replacement->CanBeNull()) {
+ ReferenceTypePropagation(graph_, handles_).Run();
+ }
+ }
+ } else if (return_replacement->IsInstanceOf()) {
+ if (do_rtp) {
+ // Inlining InstanceOf into an If may put a tighter bound on reference types.
+ ReferenceTypePropagation(graph_, handles_).Run();
}
}
}
diff --git a/compiler/optimizing/licm_test.cc b/compiler/optimizing/licm_test.cc
index 9ad003c..aa60fd6 100644
--- a/compiler/optimizing/licm_test.cc
+++ b/compiler/optimizing/licm_test.cc
@@ -16,7 +16,6 @@
#include "base/arena_allocator.h"
#include "builder.h"
-#include "gtest/gtest.h"
#include "licm.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
@@ -27,7 +26,7 @@
/**
* Fixture class for the LICM tests.
*/
-class LICMTest : public testing::Test {
+class LICMTest : public CommonCompilerTest {
public:
LICMTest() : pool_(), allocator_(&pool_) {
graph_ = CreateGraph(&allocator_);
@@ -70,16 +69,16 @@
loop_preheader_->AddInstruction(new (&allocator_) HGoto());
loop_header_->AddInstruction(new (&allocator_) HIf(parameter_));
loop_body_->AddInstruction(new (&allocator_) HGoto());
+ return_->AddInstruction(new (&allocator_) HReturnVoid());
exit_->AddInstruction(new (&allocator_) HExit());
}
// Performs LICM optimizations (after proper set up).
void PerformLICM() {
- ASSERT_TRUE(graph_->TryBuildingSsa());
+ TransformToSsa(graph_);
SideEffectsAnalysis side_effects(graph_);
side_effects.Run();
- LICM licm(graph_, side_effects);
- licm.Run();
+ LICM(graph_, side_effects).Run();
}
// General building fields.
@@ -169,10 +168,10 @@
// Populate the loop with instructions: set/get array with different types.
HInstruction* get_array = new (&allocator_) HArrayGet(
- parameter_, constant_, Primitive::kPrimLong, 0);
+ parameter_, constant_, Primitive::kPrimByte, 0);
loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction());
HInstruction* set_array = new (&allocator_) HArraySet(
- parameter_, constant_, constant_, Primitive::kPrimInt, 0);
+ parameter_, constant_, constant_, Primitive::kPrimShort, 0);
loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction());
EXPECT_EQ(get_array->GetBlock(), loop_body_);
@@ -187,10 +186,10 @@
// Populate the loop with instructions: set/get array with same types.
HInstruction* get_array = new (&allocator_) HArrayGet(
- parameter_, constant_, Primitive::kPrimLong, 0);
+ parameter_, constant_, Primitive::kPrimByte, 0);
loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction());
HInstruction* set_array = new (&allocator_) HArraySet(
- parameter_, get_array, constant_, Primitive::kPrimLong, 0);
+ parameter_, get_array, constant_, Primitive::kPrimByte, 0);
loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction());
EXPECT_EQ(get_array->GetBlock(), loop_body_);
diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc
index a059766..ed275b1 100644
--- a/compiler/optimizing/linearize_test.cc
+++ b/compiler/optimizing/linearize_test.cc
@@ -29,13 +29,12 @@
#include "nodes.h"
#include "optimizing_unit_test.h"
#include "pretty_printer.h"
-#include "ssa_builder.h"
#include "ssa_liveness_analysis.h"
-#include "gtest/gtest.h"
-
namespace art {
+class LinearizeTest : public CommonCompilerTest {};
+
template <size_t number_of_blocks>
static void TestCode(const uint16_t* data, const uint32_t (&expected_order)[number_of_blocks]) {
ArenaPool pool;
@@ -46,7 +45,7 @@
bool graph_built = builder.BuildGraph(*item);
ASSERT_TRUE(graph_built);
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
std::unique_ptr<const X86InstructionSetFeatures> features_x86(
X86InstructionSetFeatures::FromCppDefines());
@@ -60,7 +59,7 @@
}
}
-TEST(LinearizeTest, CFG1) {
+TEST_F(LinearizeTest, CFG1) {
// Structure of this graph (+ are back edges)
// Block0
// |
@@ -85,7 +84,7 @@
TestCode(data, blocks);
}
-TEST(LinearizeTest, CFG2) {
+TEST_F(LinearizeTest, CFG2) {
// Structure of this graph (+ are back edges)
// Block0
// |
@@ -110,7 +109,7 @@
TestCode(data, blocks);
}
-TEST(LinearizeTest, CFG3) {
+TEST_F(LinearizeTest, CFG3) {
// Structure of this graph (+ are back edges)
// Block0
// |
@@ -137,7 +136,7 @@
TestCode(data, blocks);
}
-TEST(LinearizeTest, CFG4) {
+TEST_F(LinearizeTest, CFG4) {
/* Structure of this graph (+ are back edges)
// Block0
// |
@@ -167,7 +166,7 @@
TestCode(data, blocks);
}
-TEST(LinearizeTest, CFG5) {
+TEST_F(LinearizeTest, CFG5) {
/* Structure of this graph (+ are back edges)
// Block0
// |
@@ -197,7 +196,7 @@
TestCode(data, blocks);
}
-TEST(LinearizeTest, CFG6) {
+TEST_F(LinearizeTest, CFG6) {
// Block0
// |
// Block1
@@ -223,7 +222,7 @@
TestCode(data, blocks);
}
-TEST(LinearizeTest, CFG7) {
+TEST_F(LinearizeTest, CFG7) {
// Structure of this graph (+ are back edges)
// Block0
// |
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index 7f67560..926f939 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -27,10 +27,10 @@
#include "prepare_for_register_allocation.h"
#include "ssa_liveness_analysis.h"
-#include "gtest/gtest.h"
-
namespace art {
+class LiveRangesTest : public CommonCompilerTest {};
+
static HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) {
HGraph* graph = CreateGraph(allocator);
HGraphBuilder builder(graph);
@@ -39,13 +39,13 @@
// Suspend checks implementation may change in the future, and this test relies
// on how instructions are ordered.
RemoveSuspendChecks(graph);
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
// `Inline` conditions into ifs.
PrepareForRegisterAllocation(graph).Run();
return graph;
}
-TEST(LiveRangesTest, CFG1) {
+TEST_F(LiveRangesTest, CFG1) {
/*
* Test the following snippet:
* return 0;
@@ -83,7 +83,7 @@
ASSERT_TRUE(range->GetNext() == nullptr);
}
-TEST(LiveRangesTest, CFG2) {
+TEST_F(LiveRangesTest, CFG2) {
/*
* Test the following snippet:
* var a = 0;
@@ -131,7 +131,7 @@
ASSERT_TRUE(range->GetNext() == nullptr);
}
-TEST(LiveRangesTest, CFG3) {
+TEST_F(LiveRangesTest, CFG3) {
/*
* Test the following snippet:
* var a = 0;
@@ -204,7 +204,7 @@
ASSERT_TRUE(range->GetNext() == nullptr);
}
-TEST(LiveRangesTest, Loop1) {
+TEST_F(LiveRangesTest, Loop1) {
/*
* Test the following snippet:
* var a = 0;
@@ -284,7 +284,7 @@
ASSERT_TRUE(range->GetNext() == nullptr);
}
-TEST(LiveRangesTest, Loop2) {
+TEST_F(LiveRangesTest, Loop2) {
/*
* Test the following snippet:
* var a = 0;
@@ -360,7 +360,7 @@
ASSERT_TRUE(range->GetNext() == nullptr);
}
-TEST(LiveRangesTest, CFG4) {
+TEST_F(LiveRangesTest, CFG4) {
/*
* Test the following snippet:
* var a = 0;
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
index 9d7d0b6..7736eed 100644
--- a/compiler/optimizing/liveness_test.cc
+++ b/compiler/optimizing/liveness_test.cc
@@ -27,10 +27,10 @@
#include "prepare_for_register_allocation.h"
#include "ssa_liveness_analysis.h"
-#include "gtest/gtest.h"
-
namespace art {
+class LivenessTest : public CommonCompilerTest {};
+
static void DumpBitVector(BitVector* vector,
std::ostream& buffer,
size_t count,
@@ -51,7 +51,7 @@
const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
bool graph_built = builder.BuildGraph(*item);
ASSERT_TRUE(graph_built);
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
// `Inline` conditions into ifs.
PrepareForRegisterAllocation(graph).Run();
std::unique_ptr<const X86InstructionSetFeatures> features_x86(
@@ -75,7 +75,7 @@
ASSERT_STREQ(expected, buffer.str().c_str());
}
-TEST(LivenessTest, CFG1) {
+TEST_F(LivenessTest, CFG1) {
const char* expected =
"Block 0\n"
" live in: (0)\n"
@@ -98,7 +98,7 @@
TestCode(data, expected);
}
-TEST(LivenessTest, CFG2) {
+TEST_F(LivenessTest, CFG2) {
const char* expected =
"Block 0\n"
" live in: (0)\n"
@@ -120,7 +120,7 @@
TestCode(data, expected);
}
-TEST(LivenessTest, CFG3) {
+TEST_F(LivenessTest, CFG3) {
const char* expected =
"Block 0\n" // entry block
" live in: (000)\n"
@@ -149,7 +149,7 @@
TestCode(data, expected);
}
-TEST(LivenessTest, CFG4) {
+TEST_F(LivenessTest, CFG4) {
// var a;
// if (0 == 0) {
// a = 5;
@@ -197,7 +197,7 @@
TestCode(data, expected);
}
-TEST(LivenessTest, CFG5) {
+TEST_F(LivenessTest, CFG5) {
// var a = 0;
// if (0 == 0) {
// } else {
@@ -242,7 +242,7 @@
TestCode(data, expected);
}
-TEST(LivenessTest, Loop1) {
+TEST_F(LivenessTest, Loop1) {
// Simple loop with one preheader and one back edge.
// var a = 0;
// while (a == a) {
@@ -288,7 +288,7 @@
TestCode(data, expected);
}
-TEST(LivenessTest, Loop3) {
+TEST_F(LivenessTest, Loop3) {
// Test that the returned value stays live in a preceding loop.
// var a = 0;
// while (a == a) {
@@ -335,7 +335,7 @@
}
-TEST(LivenessTest, Loop4) {
+TEST_F(LivenessTest, Loop4) {
// Make sure we support a preheader of a loop not being the first predecessor
// in the predecessor list of the header.
// var a = 0;
@@ -387,7 +387,7 @@
TestCode(data, expected);
}
-TEST(LivenessTest, Loop5) {
+TEST_F(LivenessTest, Loop5) {
// Make sure we create a preheader of a loop when a header originally has two
// incoming blocks and one back edge.
// Bitsets are made of:
@@ -443,7 +443,7 @@
TestCode(data, expected);
}
-TEST(LivenessTest, Loop6) {
+TEST_F(LivenessTest, Loop6) {
// Bitsets are made of:
// (constant0, constant4, constant5, phi in block 2)
const char* expected =
@@ -494,7 +494,7 @@
}
-TEST(LivenessTest, Loop7) {
+TEST_F(LivenessTest, Loop7) {
// Bitsets are made of:
// (constant0, constant4, constant5, phi in block 2, phi in block 6)
const char* expected =
@@ -548,7 +548,7 @@
TestCode(data, expected);
}
-TEST(LivenessTest, Loop8) {
+TEST_F(LivenessTest, Loop8) {
// var a = 0;
// while (a == a) {
// a = a + a;
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index a9a2493..fc12224 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -198,10 +198,38 @@
}
}
-void HGraph::TransformToSsa() {
- DCHECK(!reverse_post_order_.empty());
- SsaBuilder ssa_builder(this);
- ssa_builder.BuildSsa();
+BuildSsaResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) {
+ BuildDominatorTree();
+
+ // The SSA builder requires loops to all be natural. Specifically, the dead phi
+ // elimination phase checks the consistency of the graph when doing a post-order
+ // visit for eliminating dead phis: a dead phi can only have loop header phi
+ // users remaining when being visited.
+ BuildSsaResult result = AnalyzeNaturalLoops();
+ if (result != kBuildSsaSuccess) {
+ return result;
+ }
+
+ // Precompute per-block try membership before entering the SSA builder,
+ // which needs the information to build catch block phis from values of
+ // locals at throwing instructions inside try blocks.
+ ComputeTryBlockInformation();
+
+ // Create the inexact Object reference type and store it in the HGraph.
+ ScopedObjectAccess soa(Thread::Current());
+ ClassLinker* linker = Runtime::Current()->GetClassLinker();
+ inexact_object_rti_ = ReferenceTypeInfo::Create(
+ handles->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangObject)),
+ /* is_exact */ false);
+
+ // Tranforms graph to SSA form.
+ result = SsaBuilder(this, handles).BuildSsa();
+ if (result != kBuildSsaSuccess) {
+ return result;
+ }
+
+ in_ssa_form_ = true;
+ return kBuildSsaSuccess;
}
HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) {
@@ -410,7 +438,7 @@
}
}
-bool HGraph::AnalyzeNaturalLoops() const {
+BuildSsaResult HGraph::AnalyzeNaturalLoops() const {
// Order does not matter.
for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
@@ -418,16 +446,16 @@
if (block->IsCatchBlock()) {
// TODO: Dealing with exceptional back edges could be tricky because
// they only approximate the real control flow. Bail out for now.
- return false;
+ return kBuildSsaFailThrowCatchLoop;
}
HLoopInformation* info = block->GetLoopInformation();
if (!info->Populate()) {
// Abort if the loop is non natural. We currently bailout in such cases.
- return false;
+ return kBuildSsaFailNonNaturalLoop;
}
}
}
- return true;
+ return kBuildSsaSuccess;
}
void HGraph::InsertConstant(HConstant* constant) {
@@ -446,8 +474,13 @@
// id and/or any invariants the graph is assuming when adding new instructions.
if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) {
cached_null_constant_ = new (arena_) HNullConstant(dex_pc);
+ cached_null_constant_->SetReferenceTypeInfo(inexact_object_rti_);
InsertConstant(cached_null_constant_);
}
+ if (kIsDebugBuild) {
+ ScopedObjectAccess soa(Thread::Current());
+ DCHECK(cached_null_constant_->GetReferenceTypeInfo().IsValid());
+ }
return cached_null_constant_;
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index ddd215d..5b072cf 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -98,6 +98,13 @@
kCondAE, // >=
};
+enum BuildSsaResult {
+ kBuildSsaFailNonNaturalLoop,
+ kBuildSsaFailThrowCatchLoop,
+ kBuildSsaFailAmbiguousArrayGet,
+ kBuildSsaSuccess,
+};
+
class HInstructionList : public ValueObject {
public:
HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {}
@@ -143,6 +150,122 @@
DISALLOW_COPY_AND_ASSIGN(HInstructionList);
};
+class ReferenceTypeInfo : ValueObject {
+ public:
+ typedef Handle<mirror::Class> TypeHandle;
+
+ static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) {
+ // The constructor will check that the type_handle is valid.
+ return ReferenceTypeInfo(type_handle, is_exact);
+ }
+
+ static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); }
+
+ static bool IsValidHandle(TypeHandle handle) SHARED_REQUIRES(Locks::mutator_lock_) {
+ return handle.GetReference() != nullptr;
+ }
+
+ bool IsValid() const SHARED_REQUIRES(Locks::mutator_lock_) {
+ return IsValidHandle(type_handle_);
+ }
+
+ bool IsExact() const { return is_exact_; }
+
+ bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ return GetTypeHandle()->IsObjectClass();
+ }
+
+ bool IsStringClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ return GetTypeHandle()->IsStringClass();
+ }
+
+ bool IsObjectArray() const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ return IsArrayClass() && GetTypeHandle()->GetComponentType()->IsObjectClass();
+ }
+
+ bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ return GetTypeHandle()->IsInterface();
+ }
+
+ bool IsArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ return GetTypeHandle()->IsArrayClass();
+ }
+
+ bool IsPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ return GetTypeHandle()->IsPrimitiveArray();
+ }
+
+ bool IsNonPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ return GetTypeHandle()->IsArrayClass() && !GetTypeHandle()->IsPrimitiveArray();
+ }
+
+ bool CanArrayHold(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ if (!IsExact()) return false;
+ if (!IsArrayClass()) return false;
+ return GetTypeHandle()->GetComponentType()->IsAssignableFrom(rti.GetTypeHandle().Get());
+ }
+
+ bool CanArrayHoldValuesOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ if (!IsExact()) return false;
+ if (!IsArrayClass()) return false;
+ if (!rti.IsArrayClass()) return false;
+ return GetTypeHandle()->GetComponentType()->IsAssignableFrom(
+ rti.GetTypeHandle()->GetComponentType());
+ }
+
+ Handle<mirror::Class> GetTypeHandle() const { return type_handle_; }
+
+ bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ DCHECK(rti.IsValid());
+ return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get());
+ }
+
+ bool IsStrictSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) {
+ DCHECK(IsValid());
+ DCHECK(rti.IsValid());
+ return GetTypeHandle().Get() != rti.GetTypeHandle().Get() &&
+ GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get());
+ }
+
+ // Returns true if the type information provide the same amount of details.
+ // Note that it does not mean that the instructions have the same actual type
+ // (because the type can be the result of a merge).
+ bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) {
+ if (!IsValid() && !rti.IsValid()) {
+ // Invalid types are equal.
+ return true;
+ }
+ if (!IsValid() || !rti.IsValid()) {
+ // One is valid, the other not.
+ return false;
+ }
+ return IsExact() == rti.IsExact()
+ && GetTypeHandle().Get() == rti.GetTypeHandle().Get();
+ }
+
+ private:
+ ReferenceTypeInfo();
+ ReferenceTypeInfo(TypeHandle type_handle, bool is_exact);
+
+ // The class of the object.
+ TypeHandle type_handle_;
+ // Whether or not the type is exact or a superclass of the actual type.
+ // Whether or not we have any information about this type.
+ bool is_exact_;
+};
+
+std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs);
+
// Control-flow graph of a method. Contains a list of basic blocks.
class HGraph : public ArenaObject<kArenaAllocGraph> {
public:
@@ -179,7 +302,8 @@
cached_float_constants_(std::less<int32_t>(), arena->Adapter(kArenaAllocConstantsMap)),
cached_long_constants_(std::less<int64_t>(), arena->Adapter(kArenaAllocConstantsMap)),
cached_double_constants_(std::less<int64_t>(), arena->Adapter(kArenaAllocConstantsMap)),
- cached_current_method_(nullptr) {
+ cached_current_method_(nullptr),
+ inexact_object_rti_(ReferenceTypeInfo::CreateInvalid()) {
blocks_.reserve(kDefaultNumberOfBlocks);
}
@@ -197,36 +321,23 @@
void AddBlock(HBasicBlock* block);
- // Try building the SSA form of this graph, with dominance computation and loop
- // recognition. Returns whether it was successful in doing all these steps.
- bool TryBuildingSsa() {
- BuildDominatorTree();
- // The SSA builder requires loops to all be natural. Specifically, the dead phi
- // elimination phase checks the consistency of the graph when doing a post-order
- // visit for eliminating dead phis: a dead phi can only have loop header phi
- // users remaining when being visited.
- if (!AnalyzeNaturalLoops()) return false;
- // Precompute per-block try membership before entering the SSA builder,
- // which needs the information to build catch block phis from values of
- // locals at throwing instructions inside try blocks.
- ComputeTryBlockInformation();
- TransformToSsa();
- in_ssa_form_ = true;
- return true;
- }
+ // Try building the SSA form of this graph, with dominance computation and
+ // loop recognition. Returns a code specifying that it was successful or the
+ // reason for failure.
+ BuildSsaResult TryBuildingSsa(StackHandleScopeCollection* handles);
void ComputeDominanceInformation();
void ClearDominanceInformation();
void BuildDominatorTree();
- void TransformToSsa();
void SimplifyCFG();
void SimplifyCatchBlocks();
- // Analyze all natural loops in this graph. Returns false if one
- // loop is not natural, that is the header does not dominate the
- // back edge.
- bool AnalyzeNaturalLoops() const;
+ // Analyze all natural loops in this graph. Returns a code specifying that it
+ // was successful or the reason for failure. The method will fail if a loop
+ // is not natural, that is the header does not dominate a back edge, or if it
+ // is a throw-catch loop, i.e. the header is a catch block.
+ BuildSsaResult AnalyzeNaturalLoops() const;
// Iterate over blocks to compute try block membership. Needs reverse post
// order and loop information.
@@ -487,6 +598,10 @@
// (such as when the superclass could not be found).
ArtMethod* art_method_;
+ // Keep the RTI of inexact Object to avoid having to pass stack handle
+ // collection pointer to passes which may create NullConstant.
+ ReferenceTypeInfo inexact_object_rti_;
+
friend class SsaBuilder; // For caching constants.
friend class SsaLivenessAnalysis; // For the linear order.
ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1);
@@ -1681,122 +1796,6 @@
DISALLOW_COPY_AND_ASSIGN(HEnvironment);
};
-class ReferenceTypeInfo : ValueObject {
- public:
- typedef Handle<mirror::Class> TypeHandle;
-
- static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) {
- // The constructor will check that the type_handle is valid.
- return ReferenceTypeInfo(type_handle, is_exact);
- }
-
- static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); }
-
- static bool IsValidHandle(TypeHandle handle) SHARED_REQUIRES(Locks::mutator_lock_) {
- return handle.GetReference() != nullptr;
- }
-
- bool IsValid() const SHARED_REQUIRES(Locks::mutator_lock_) {
- return IsValidHandle(type_handle_);
- }
-
- bool IsExact() const { return is_exact_; }
-
- bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- return GetTypeHandle()->IsObjectClass();
- }
-
- bool IsStringClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- return GetTypeHandle()->IsStringClass();
- }
-
- bool IsObjectArray() const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- return IsArrayClass() && GetTypeHandle()->GetComponentType()->IsObjectClass();
- }
-
- bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- return GetTypeHandle()->IsInterface();
- }
-
- bool IsArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- return GetTypeHandle()->IsArrayClass();
- }
-
- bool IsPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- return GetTypeHandle()->IsPrimitiveArray();
- }
-
- bool IsNonPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- return GetTypeHandle()->IsArrayClass() && !GetTypeHandle()->IsPrimitiveArray();
- }
-
- bool CanArrayHold(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- if (!IsExact()) return false;
- if (!IsArrayClass()) return false;
- return GetTypeHandle()->GetComponentType()->IsAssignableFrom(rti.GetTypeHandle().Get());
- }
-
- bool CanArrayHoldValuesOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- if (!IsExact()) return false;
- if (!IsArrayClass()) return false;
- if (!rti.IsArrayClass()) return false;
- return GetTypeHandle()->GetComponentType()->IsAssignableFrom(
- rti.GetTypeHandle()->GetComponentType());
- }
-
- Handle<mirror::Class> GetTypeHandle() const { return type_handle_; }
-
- bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- DCHECK(rti.IsValid());
- return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get());
- }
-
- bool IsStrictSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) {
- DCHECK(IsValid());
- DCHECK(rti.IsValid());
- return GetTypeHandle().Get() != rti.GetTypeHandle().Get() &&
- GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get());
- }
-
- // Returns true if the type information provide the same amount of details.
- // Note that it does not mean that the instructions have the same actual type
- // (because the type can be the result of a merge).
- bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) {
- if (!IsValid() && !rti.IsValid()) {
- // Invalid types are equal.
- return true;
- }
- if (!IsValid() || !rti.IsValid()) {
- // One is valid, the other not.
- return false;
- }
- return IsExact() == rti.IsExact()
- && GetTypeHandle().Get() == rti.GetTypeHandle().Get();
- }
-
- private:
- ReferenceTypeInfo();
- ReferenceTypeInfo(TypeHandle type_handle, bool is_exact);
-
- // The class of the object.
- TypeHandle type_handle_;
- // Whether or not the type is exact or a superclass of the actual type.
- // Whether or not we have any information about this type.
- bool is_exact_;
-};
-
-std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs);
-
class HInstruction : public ArenaObject<kArenaAllocInstruction> {
public:
HInstruction(SideEffects side_effects, uint32_t dex_pc)
@@ -4462,7 +4461,16 @@
void RemoveInputAt(size_t index);
Primitive::Type GetType() const OVERRIDE { return type_; }
- void SetType(Primitive::Type type) { type_ = type; }
+ void SetType(Primitive::Type new_type) {
+ // Make sure that only valid type changes occur. The following are allowed:
+ // (1) int -> float/ref (primitive type propagation),
+ // (2) long -> double (primitive type propagation).
+ DCHECK(type_ == new_type ||
+ (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimFloat) ||
+ (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimNot) ||
+ (type_ == Primitive::kPrimLong && new_type == Primitive::kPrimDouble));
+ type_ = new_type;
+ }
bool CanBeNull() const OVERRIDE { return can_be_null_; }
void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; }
@@ -4702,7 +4710,21 @@
return false;
}
- void SetType(Primitive::Type type) { type_ = type; }
+ bool IsEquivalentOf(HArrayGet* other) const {
+ bool result = (GetDexPc() == other->GetDexPc());
+ if (kIsDebugBuild && result) {
+ DCHECK_EQ(GetBlock(), other->GetBlock());
+ DCHECK_EQ(GetArray(), other->GetArray());
+ DCHECK_EQ(GetIndex(), other->GetIndex());
+ if (Primitive::IsIntOrLongType(GetType())) {
+ DCHECK(Primitive::IsFloatingPointType(other->GetType()));
+ } else {
+ DCHECK(Primitive::IsFloatingPointType(GetType()));
+ DCHECK(Primitive::IsIntOrLongType(other->GetType()));
+ }
+ }
+ return result;
+ }
HInstruction* GetArray() const { return InputAt(0); }
HInstruction* GetIndex() const { return InputAt(1); }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index dd1d193..3de870e 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -501,11 +501,8 @@
CompilerDriver* driver,
OptimizingCompilerStats* stats,
const DexCompilationUnit& dex_compilation_unit,
- PassObserver* pass_observer) {
- ScopedObjectAccess soa(Thread::Current());
- StackHandleScopeCollection handles(soa.Self());
- ScopedThreadSuspension sts(soa.Self(), kNative);
-
+ PassObserver* pass_observer,
+ StackHandleScopeCollection* handles) {
ArenaAllocator* arena = graph->GetArena();
HDeadCodeElimination* dce1 = new (arena) HDeadCodeElimination(
graph, stats, HDeadCodeElimination::kInitialDeadCodeEliminationPassName);
@@ -522,29 +519,23 @@
LoadStoreElimination* lse = new (arena) LoadStoreElimination(graph, *side_effects);
HInductionVarAnalysis* induction = new (arena) HInductionVarAnalysis(graph);
BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, *side_effects, induction);
- ReferenceTypePropagation* type_propagation =
- new (arena) ReferenceTypePropagation(graph, &handles);
HSharpening* sharpening = new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver);
InstructionSimplifier* simplify2 = new (arena) InstructionSimplifier(
- graph, stats, "instruction_simplifier_after_types");
- InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier(
graph, stats, "instruction_simplifier_after_bce");
- InstructionSimplifier* simplify4 = new (arena) InstructionSimplifier(
+ InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier(
graph, stats, "instruction_simplifier_before_codegen");
IntrinsicsRecognizer* intrinsics = new (arena) IntrinsicsRecognizer(graph, driver);
HOptimization* optimizations1[] = {
intrinsics,
+ sharpening,
fold1,
simplify1,
- type_propagation,
- sharpening,
dce1,
- simplify2
};
RunOptimizations(optimizations1, arraysize(optimizations1), pass_observer);
- MaybeRunInliner(graph, codegen, driver, stats, dex_compilation_unit, pass_observer, &handles);
+ MaybeRunInliner(graph, codegen, driver, stats, dex_compilation_unit, pass_observer, handles);
HOptimization* optimizations2[] = {
// BooleanSimplifier depends on the InstructionSimplifier removing
@@ -557,13 +548,13 @@
induction,
bce,
fold3, // evaluates code generated by dynamic bce
- simplify3,
+ simplify2,
lse,
dce2,
// The codegen has a few assumptions that only the instruction simplifier
// can satisfy. For example, the code generator does not expect to see a
// HTypeConversion from a type to the same type.
- simplify4,
+ simplify3,
};
RunOptimizations(optimizations2, arraysize(optimizations2), pass_observer);
@@ -768,14 +759,29 @@
}
VLOG(compiler) << "Optimizing " << pass_observer.GetMethodName();
+
if (run_optimizations_) {
+ ScopedObjectAccess soa(Thread::Current());
+ StackHandleScopeCollection handles(soa.Self());
+ ScopedThreadSuspension sts(soa.Self(), kNative);
+
{
PassScope scope(SsaBuilder::kSsaBuilderPassName, &pass_observer);
- if (!graph->TryBuildingSsa()) {
- // We could not transform the graph to SSA, bailout.
- LOG(INFO) << "Skipping compilation of " << pass_observer.GetMethodName()
- << ": it contains a non natural loop";
- MaybeRecordStat(MethodCompilationStat::kNotCompiledCannotBuildSSA);
+ BuildSsaResult result = graph->TryBuildingSsa(&handles);
+ if (result != kBuildSsaSuccess) {
+ switch (result) {
+ case kBuildSsaFailNonNaturalLoop:
+ MaybeRecordStat(MethodCompilationStat::kNotCompiledNonNaturalLoop);
+ break;
+ case kBuildSsaFailThrowCatchLoop:
+ MaybeRecordStat(MethodCompilationStat::kNotCompiledThrowCatchLoop);
+ break;
+ case kBuildSsaFailAmbiguousArrayGet:
+ MaybeRecordStat(MethodCompilationStat::kNotCompiledAmbiguousArrayGet);
+ break;
+ case kBuildSsaSuccess:
+ UNREACHABLE();
+ }
pass_observer.SetGraphInBadState();
return nullptr;
}
@@ -786,7 +792,8 @@
compiler_driver,
compilation_stats_.get(),
dex_compilation_unit,
- &pass_observer);
+ &pass_observer,
+ &handles);
codegen->CompileOptimized(code_allocator);
} else {
codegen->CompileBaseline(code_allocator);
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index 6296eed..4713514 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -38,7 +38,9 @@
kRemovedDeadInstruction,
kRemovedNullCheck,
kNotCompiledBranchOutsideMethodCode,
- kNotCompiledCannotBuildSSA,
+ kNotCompiledNonNaturalLoop,
+ kNotCompiledThrowCatchLoop,
+ kNotCompiledAmbiguousArrayGet,
kNotCompiledHugeMethod,
kNotCompiledLargeMethodNoBranches,
kNotCompiledMalformedOpcode,
@@ -104,7 +106,9 @@
case kRemovedDeadInstruction: name = "RemovedDeadInstruction"; break;
case kRemovedNullCheck: name = "RemovedNullCheck"; break;
case kNotCompiledBranchOutsideMethodCode: name = "NotCompiledBranchOutsideMethodCode"; break;
- case kNotCompiledCannotBuildSSA : name = "NotCompiledCannotBuildSSA"; break;
+ case kNotCompiledNonNaturalLoop : name = "NotCompiledNonNaturalLoop"; break;
+ case kNotCompiledThrowCatchLoop : name = "NotCompiledThrowCatchLoop"; break;
+ case kNotCompiledAmbiguousArrayGet : name = "NotCompiledAmbiguousArrayGet"; break;
case kNotCompiledHugeMethod : name = "NotCompiledHugeMethod"; break;
case kNotCompiledLargeMethodNoBranches : name = "NotCompiledLargeMethodNoBranches"; break;
case kNotCompiledMalformedOpcode : name = "NotCompiledMalformedOpcode"; break;
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 350f0b1..af3a005 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -19,9 +19,13 @@
#include "nodes.h"
#include "builder.h"
+#include "common_compiler_test.h"
#include "compiler/dex/pass_manager.h"
#include "dex_file.h"
#include "dex_instruction.h"
+#include "handle_scope-inl.h"
+#include "scoped_thread_state_change.h"
+#include "ssa_builder.h"
#include "ssa_liveness_analysis.h"
#include "gtest/gtest.h"
@@ -42,7 +46,6 @@
#define FIVE_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(5, __VA_ARGS__)
#define SIX_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(6, __VA_ARGS__)
-
LiveInterval* BuildInterval(const size_t ranges[][2],
size_t number_of_ranges,
ArenaAllocator* allocator,
@@ -111,6 +114,12 @@
return instruction->GetBlock() == nullptr;
}
+inline void TransformToSsa(HGraph* graph) {
+ ScopedObjectAccess soa(Thread::Current());
+ StackHandleScopeCollection handles(soa.Self());
+ EXPECT_EQ(graph->TryBuildingSsa(&handles), kBuildSsaSuccess);
+}
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_
diff --git a/compiler/optimizing/primitive_type_propagation.cc b/compiler/optimizing/primitive_type_propagation.cc
deleted file mode 100644
index bde54ee..0000000
--- a/compiler/optimizing/primitive_type_propagation.cc
+++ /dev/null
@@ -1,133 +0,0 @@
-/*
- * Copyright (C) 2014 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 "primitive_type_propagation.h"
-
-#include "nodes.h"
-#include "ssa_builder.h"
-
-namespace art {
-
-static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) {
- // We trust the verifier has already done the necessary checking.
- switch (existing) {
- case Primitive::kPrimFloat:
- case Primitive::kPrimDouble:
- case Primitive::kPrimNot:
- return existing;
- default:
- // Phis are initialized with a void type, so if we are asked
- // to merge with a void type, we should use the existing one.
- return new_type == Primitive::kPrimVoid
- ? existing
- : HPhi::ToPhiType(new_type);
- }
-}
-
-// Re-compute and update the type of the instruction. Returns
-// whether or not the type was changed.
-bool PrimitiveTypePropagation::UpdateType(HPhi* phi) {
- DCHECK(phi->IsLive());
- Primitive::Type existing = phi->GetType();
-
- Primitive::Type new_type = existing;
- for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
- Primitive::Type input_type = phi->InputAt(i)->GetType();
- new_type = MergeTypes(new_type, input_type);
- }
- phi->SetType(new_type);
-
- if (new_type == Primitive::kPrimDouble
- || new_type == Primitive::kPrimFloat
- || new_type == Primitive::kPrimNot) {
- // If the phi is of floating point type, we need to update its inputs to that
- // type. For inputs that are phis, we need to recompute their types.
- for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
- HInstruction* input = phi->InputAt(i);
- if (input->GetType() != new_type) {
- HInstruction* equivalent = (new_type == Primitive::kPrimNot)
- ? SsaBuilder::GetReferenceTypeEquivalent(input)
- : SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, new_type);
- phi->ReplaceInput(equivalent, i);
- if (equivalent->IsPhi()) {
- AddToWorklist(equivalent->AsPhi());
- } else if (equivalent == input) {
- // The input has changed its type. It can be an input of other phis,
- // so we need to put phi users in the work list.
- AddDependentInstructionsToWorklist(equivalent);
- }
- }
- }
- }
-
- return existing != new_type;
-}
-
-void PrimitiveTypePropagation::Run() {
- for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
- VisitBasicBlock(it.Current());
- }
- ProcessWorklist();
-}
-
-void PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) {
- if (block->IsLoopHeader()) {
- for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
- HPhi* phi = it.Current()->AsPhi();
- if (phi->IsLive()) {
- AddToWorklist(phi);
- }
- }
- } else {
- for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
- // Eagerly compute the type of the phi, for quicker convergence. Note
- // that we don't need to add users to the worklist because we are
- // doing a reverse post-order visit, therefore either the phi users are
- // non-loop phi and will be visited later in the visit, or are loop-phis,
- // and they are already in the work list.
- HPhi* phi = it.Current()->AsPhi();
- if (phi->IsLive()) {
- UpdateType(phi);
- }
- }
- }
-}
-
-void PrimitiveTypePropagation::ProcessWorklist() {
- while (!worklist_.empty()) {
- HPhi* instruction = worklist_.back();
- worklist_.pop_back();
- if (UpdateType(instruction)) {
- AddDependentInstructionsToWorklist(instruction);
- }
- }
-}
-
-void PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) {
- DCHECK(instruction->IsLive());
- worklist_.push_back(instruction);
-}
-
-void PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
- for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
- HPhi* phi = it.Current()->GetUser()->AsPhi();
- if (phi != nullptr && phi->IsLive() && phi->GetType() != instruction->GetType()) {
- AddToWorklist(phi);
- }
- }
-}
-
-} // namespace art
diff --git a/compiler/optimizing/primitive_type_propagation.h b/compiler/optimizing/primitive_type_propagation.h
deleted file mode 100644
index 212fcfc..0000000
--- a/compiler/optimizing/primitive_type_propagation.h
+++ /dev/null
@@ -1,52 +0,0 @@
-/*
- * Copyright (C) 2014 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_PRIMITIVE_TYPE_PROPAGATION_H_
-#define ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_
-
-#include "base/arena_containers.h"
-#include "nodes.h"
-
-namespace art {
-
-// Compute and propagate primitive types of phis in the graph.
-class PrimitiveTypePropagation : public ValueObject {
- public:
- explicit PrimitiveTypePropagation(HGraph* graph)
- : graph_(graph), worklist_(graph->GetArena()->Adapter(kArenaAllocPrimitiveTypePropagation)) {
- worklist_.reserve(kDefaultWorklistSize);
- }
-
- void Run();
-
- private:
- void VisitBasicBlock(HBasicBlock* block);
- void ProcessWorklist();
- void AddToWorklist(HPhi* phi);
- void AddDependentInstructionsToWorklist(HInstruction* instruction);
- bool UpdateType(HPhi* phi);
-
- HGraph* const graph_;
- ArenaVector<HPhi*> worklist_;
-
- static constexpr size_t kDefaultWorklistSize = 8;
-
- DISALLOW_COPY_AND_ASSIGN(PrimitiveTypePropagation);
-};
-
-} // namespace art
-
-#endif // ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index fea903d..94a297c 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -40,7 +40,6 @@
throwable_class_handle_(throwable_class_handle),
worklist_(worklist) {}
- void VisitNullConstant(HNullConstant* null_constant) OVERRIDE;
void VisitNewInstance(HNewInstance* new_instance) OVERRIDE;
void VisitLoadClass(HLoadClass* load_class) OVERRIDE;
void VisitClinitCheck(HClinitCheck* clinit_check) OVERRIDE;
@@ -71,8 +70,6 @@
ReferenceTypeInfo::TypeHandle string_class_handle_;
ReferenceTypeInfo::TypeHandle throwable_class_handle_;
ArenaVector<HInstruction*>* worklist_;
-
- static constexpr size_t kDefaultWorklistSize = 8;
};
ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph,
@@ -171,9 +168,13 @@
ScopedObjectAccess soa(Thread::Current());
for (HReversePostOrderIterator block_it(*graph); !block_it.Done(); block_it.Advance()) {
for (HInstructionIterator it(block_it.Current()->GetPhis()); !it.Done(); it.Advance()) {
- HInstruction* instr = it.Current();
- if (instr->GetType() == Primitive::kPrimNot && !instr->GetReferenceTypeInfo().IsValid()) {
- fn(instr);
+ HPhi* phi = it.Current()->AsPhi();
+ // Note that the graph may contain dead phis when run from the SsaBuilder.
+ // Skip those as they might have a type conflict and will be removed anyway.
+ if (phi->IsLive() &&
+ phi->GetType() == Primitive::kPrimNot &&
+ !phi->GetReferenceTypeInfo().IsValid()) {
+ fn(phi);
}
}
for (HInstructionIterator it(block_it.Current()->GetInstructions()); !it.Done(); it.Advance()) {
@@ -376,6 +377,75 @@
}
}
+// Returns true if one of the patterns below has been recognized. If so, the
+// InstanceOf instruction together with the true branch of `ifInstruction` will
+// be returned using the out parameters.
+// Recognized patterns:
+// (1) patterns equivalent to `if (obj instanceof X)`
+// (a) InstanceOf -> Equal to 1 -> If
+// (b) InstanceOf -> NotEqual to 0 -> If
+// (c) InstanceOf -> If
+// (2) patterns equivalent to `if (!(obj instanceof X))`
+// (a) InstanceOf -> Equal to 0 -> If
+// (b) InstanceOf -> NotEqual to 1 -> If
+// (c) InstanceOf -> BooleanNot -> If
+static bool MatchIfInstanceOf(HIf* ifInstruction,
+ /* out */ HInstanceOf** instanceOf,
+ /* out */ HBasicBlock** trueBranch) {
+ HInstruction* input = ifInstruction->InputAt(0);
+
+ if (input->IsEqual()) {
+ HInstruction* rhs = input->AsEqual()->GetConstantRight();
+ if (rhs != nullptr) {
+ HInstruction* lhs = input->AsEqual()->GetLeastConstantLeft();
+ if (lhs->IsInstanceOf() && rhs->IsIntConstant()) {
+ if (rhs->AsIntConstant()->IsOne()) {
+ // Case (1a)
+ *trueBranch = ifInstruction->IfTrueSuccessor();
+ } else {
+ // Case (2a)
+ DCHECK(rhs->AsIntConstant()->IsZero());
+ *trueBranch = ifInstruction->IfFalseSuccessor();
+ }
+ *instanceOf = lhs->AsInstanceOf();
+ return true;
+ }
+ }
+ } else if (input->IsNotEqual()) {
+ HInstruction* rhs = input->AsNotEqual()->GetConstantRight();
+ if (rhs != nullptr) {
+ HInstruction* lhs = input->AsNotEqual()->GetLeastConstantLeft();
+ if (lhs->IsInstanceOf() && rhs->IsIntConstant()) {
+ if (rhs->AsIntConstant()->IsZero()) {
+ // Case (1b)
+ *trueBranch = ifInstruction->IfTrueSuccessor();
+ } else {
+ // Case (2b)
+ DCHECK(rhs->AsIntConstant()->IsOne());
+ *trueBranch = ifInstruction->IfFalseSuccessor();
+ }
+ *instanceOf = lhs->AsInstanceOf();
+ return true;
+ }
+ }
+ } else if (input->IsInstanceOf()) {
+ // Case (1c)
+ *instanceOf = input->AsInstanceOf();
+ *trueBranch = ifInstruction->IfTrueSuccessor();
+ return true;
+ } else if (input->IsBooleanNot()) {
+ HInstruction* not_input = input->InputAt(0);
+ if (not_input->IsInstanceOf()) {
+ // Case (2c)
+ *instanceOf = not_input->AsInstanceOf();
+ *trueBranch = ifInstruction->IfFalseSuccessor();
+ return true;
+ }
+ }
+
+ return false;
+}
+
// Detects if `block` is the True block for the pattern
// `if (x instanceof ClassX) { }`
// If that's the case insert an HBoundType instruction to bound the type of `x`
@@ -385,22 +455,11 @@
if (ifInstruction == nullptr) {
return;
}
- HInstruction* ifInput = ifInstruction->InputAt(0);
- HInstruction* instanceOf = nullptr;
- HBasicBlock* instanceOfTrueBlock = nullptr;
- // The instruction simplifier has transformed:
- // - `if (a instanceof A)` into an HIf with an HInstanceOf input
- // - `if (!(a instanceof A)` into an HIf with an HBooleanNot input (which in turn
- // has an HInstanceOf input)
- // So we should not see the usual HEqual here.
- if (ifInput->IsInstanceOf()) {
- instanceOf = ifInput;
- instanceOfTrueBlock = ifInstruction->IfTrueSuccessor();
- } else if (ifInput->IsBooleanNot() && ifInput->InputAt(0)->IsInstanceOf()) {
- instanceOf = ifInput->InputAt(0);
- instanceOfTrueBlock = ifInstruction->IfFalseSuccessor();
- } else {
+ // Try to recognize common `if (instanceof)` and `if (!instanceof)` patterns.
+ HInstanceOf* instanceOf = nullptr;
+ HBasicBlock* instanceOfTrueBlock = nullptr;
+ if (!MatchIfInstanceOf(ifInstruction, &instanceOf, &instanceOfTrueBlock)) {
return;
}
@@ -505,13 +564,6 @@
SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx), is_exact);
}
-void RTPVisitor::VisitNullConstant(HNullConstant* instr) {
- // TODO: The null constant could be bound contextually (e.g. based on return statements)
- // to a more precise type.
- instr->SetReferenceTypeInfo(
- ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false));
-}
-
void RTPVisitor::VisitNewInstance(HNewInstance* instr) {
UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true);
}
@@ -523,7 +575,11 @@
static mirror::Class* GetClassFromDexCache(Thread* self, const DexFile& dex_file, uint16_t type_idx)
SHARED_REQUIRES(Locks::mutator_lock_) {
mirror::DexCache* dex_cache =
- Runtime::Current()->GetClassLinker()->FindDexCache(self, dex_file, false);
+ Runtime::Current()->GetClassLinker()->FindDexCache(self, dex_file, /* allow_failure */ true);
+ if (dex_cache == nullptr) {
+ // Dex cache could not be found. This should only happen during gtests.
+ return nullptr;
+ }
// Get type from dex cache assuming it was populated by the verifier.
return dex_cache->GetResolvedType(type_idx);
}
@@ -540,17 +596,24 @@
void RTPVisitor::UpdateFieldAccessTypeInfo(HInstruction* instr,
const FieldInfo& info) {
- // The field index is unknown only during tests.
- if (instr->GetType() != Primitive::kPrimNot || info.GetFieldIndex() == kUnknownFieldIndex) {
+ if (instr->GetType() != Primitive::kPrimNot) {
return;
}
ScopedObjectAccess soa(Thread::Current());
- ClassLinker* cl = Runtime::Current()->GetClassLinker();
- ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), info.GetDexCache().Get());
- // TODO: There are certain cases where we can't resolve the field.
- // b/21914925 is open to keep track of a repro case for this issue.
- mirror::Class* klass = (field == nullptr) ? nullptr : field->GetType<false>();
+ mirror::Class* klass = nullptr;
+
+ // The field index is unknown only during tests.
+ if (info.GetFieldIndex() != kUnknownFieldIndex) {
+ ClassLinker* cl = Runtime::Current()->GetClassLinker();
+ ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), info.GetDexCache().Get());
+ // TODO: There are certain cases where we can't resolve the field.
+ // b/21914925 is open to keep track of a repro case for this issue.
+ if (field != nullptr) {
+ klass = field->GetType<false>();
+ }
+ }
+
SetClassAsTypeInfo(instr, klass, /* is_exact */ false);
}
@@ -666,7 +729,7 @@
}
void ReferenceTypePropagation::VisitPhi(HPhi* phi) {
- if (phi->GetType() != Primitive::kPrimNot) {
+ if (phi->IsDead() || phi->GetType() != Primitive::kPrimNot) {
return;
}
@@ -824,6 +887,8 @@
// NullConstant inputs are ignored during merging as they do not provide any useful information.
// If all the inputs are NullConstants then the type of the phi will be set to Object.
void ReferenceTypePropagation::UpdatePhi(HPhi* instr) {
+ DCHECK(instr->IsLive());
+
size_t input_count = instr->InputCount();
size_t first_input_index_not_null = 0;
while (first_input_index_not_null < input_count &&
@@ -868,7 +933,7 @@
// Re-computes and updates the nullability of the instruction. Returns whether or
// not the nullability was changed.
bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) {
- DCHECK(instr->IsPhi()
+ DCHECK((instr->IsPhi() && instr->AsPhi()->IsLive())
|| instr->IsBoundType()
|| instr->IsNullCheck()
|| instr->IsArrayGet());
@@ -916,7 +981,7 @@
void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
HInstruction* user = it.Current()->GetUser();
- if (user->IsPhi()
+ if ((user->IsPhi() && user->AsPhi()->IsLive())
|| user->IsBoundType()
|| user->IsNullCheck()
|| (user->IsArrayGet() && (user->GetType() == Primitive::kPrimNot))) {
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 8706854..306a457 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -28,13 +28,13 @@
#include "ssa_liveness_analysis.h"
#include "ssa_phi_elimination.h"
-#include "gtest/gtest.h"
-
namespace art {
// Note: the register allocator tests rely on the fact that constants have live
// intervals and registers get allocated to them.
+class RegisterAllocatorTest : public CommonCompilerTest {};
+
static bool Check(const uint16_t* data) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
@@ -42,7 +42,7 @@
HGraphBuilder builder(graph);
const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
builder.BuildGraph(*item);
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
std::unique_ptr<const X86InstructionSetFeatures> features_x86(
X86InstructionSetFeatures::FromCppDefines());
x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
@@ -57,7 +57,7 @@
* Unit testing of RegisterAllocator::ValidateIntervals. Register allocator
* tests are based on this validation method.
*/
-TEST(RegisterAllocatorTest, ValidateIntervals) {
+TEST_F(RegisterAllocatorTest, ValidateIntervals) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
HGraph* graph = CreateGraph(&allocator);
@@ -146,7 +146,7 @@
}
}
-TEST(RegisterAllocatorTest, CFG1) {
+TEST_F(RegisterAllocatorTest, CFG1) {
/*
* Test the following snippet:
* return 0;
@@ -166,7 +166,7 @@
ASSERT_TRUE(Check(data));
}
-TEST(RegisterAllocatorTest, Loop1) {
+TEST_F(RegisterAllocatorTest, Loop1) {
/*
* Test the following snippet:
* int a = 0;
@@ -205,7 +205,7 @@
ASSERT_TRUE(Check(data));
}
-TEST(RegisterAllocatorTest, Loop2) {
+TEST_F(RegisterAllocatorTest, Loop2) {
/*
* Test the following snippet:
* int a = 0;
@@ -259,11 +259,11 @@
HGraphBuilder builder(graph);
const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
builder.BuildGraph(*item);
- graph->TryBuildingSsa();
+ TransformToSsa(graph);
return graph;
}
-TEST(RegisterAllocatorTest, Loop3) {
+TEST_F(RegisterAllocatorTest, Loop3) {
/*
* Test the following snippet:
* int a = 0
@@ -326,7 +326,7 @@
ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister());
}
-TEST(RegisterAllocatorTest, FirstRegisterUse) {
+TEST_F(RegisterAllocatorTest, FirstRegisterUse) {
const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::XOR_INT_LIT8 | 1 << 8, 1 << 8,
@@ -366,7 +366,7 @@
ASSERT_EQ(new_interval->FirstRegisterUse(), last_xor->GetLifetimePosition());
}
-TEST(RegisterAllocatorTest, DeadPhi) {
+TEST_F(RegisterAllocatorTest, DeadPhi) {
/* Test for a dead loop phi taking as back-edge input a phi that also has
* this loop phi as input. Walking backwards in SsaDeadPhiElimination
* does not solve the problem because the loop phi will be visited last.
@@ -407,7 +407,7 @@
* that share the same register. It should split the interval it is currently
* allocating for at the minimum lifetime position between the two inactive intervals.
*/
-TEST(RegisterAllocatorTest, FreeUntil) {
+TEST_F(RegisterAllocatorTest, FreeUntil) {
const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::RETURN);
@@ -539,7 +539,7 @@
return graph;
}
-TEST(RegisterAllocatorTest, PhiHint) {
+TEST_F(RegisterAllocatorTest, PhiHint) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
HPhi *phi;
@@ -658,7 +658,7 @@
return graph;
}
-TEST(RegisterAllocatorTest, ExpectedInRegisterHint) {
+TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
HInstruction *field, *ret;
@@ -726,7 +726,7 @@
return graph;
}
-TEST(RegisterAllocatorTest, SameAsFirstInputHint) {
+TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
HInstruction *first_sub, *second_sub;
@@ -795,7 +795,7 @@
return graph;
}
-TEST(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) {
+TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
HInstruction *div;
@@ -819,7 +819,7 @@
// Test a bug in the register allocator, where allocating a blocked
// register would lead to spilling an inactive interval at the wrong
// position.
-TEST(RegisterAllocatorTest, SpillInactive) {
+TEST_F(RegisterAllocatorTest, SpillInactive) {
ArenaPool pool;
// Create a synthesized graph to please the register_allocator and
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 9e6cfbe..9e869e1 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -17,214 +17,11 @@
#include "ssa_builder.h"
#include "nodes.h"
-#include "primitive_type_propagation.h"
+#include "reference_type_propagation.h"
#include "ssa_phi_elimination.h"
namespace art {
-// Returns whether this is a loop header phi which was eagerly created but later
-// found inconsistent due to the vreg being undefined in one of its predecessors.
-// Such phi is marked dead and should be ignored until its removal in SsaPhiElimination.
-static bool IsUndefinedLoopHeaderPhi(HPhi* phi) {
- return phi->IsLoopHeaderPhi() && phi->InputCount() != phi->GetBlock()->GetPredecessors().size();
-}
-
-/**
- * A debuggable application may require to reviving phis, to ensure their
- * associated DEX register is available to a debugger. This class implements
- * the logic for statement (c) of the SsaBuilder (see ssa_builder.h). It
- * also makes sure that phis with incompatible input types are not revived
- * (statement (b) of the SsaBuilder).
- *
- * This phase must be run after detecting dead phis through the
- * DeadPhiElimination phase, and before deleting the dead phis.
- */
-class DeadPhiHandling : public ValueObject {
- public:
- explicit DeadPhiHandling(HGraph* graph)
- : graph_(graph), worklist_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) {
- worklist_.reserve(kDefaultWorklistSize);
- }
-
- void Run();
-
- private:
- void VisitBasicBlock(HBasicBlock* block);
- void ProcessWorklist();
- void AddToWorklist(HPhi* phi);
- void AddDependentInstructionsToWorklist(HPhi* phi);
- bool UpdateType(HPhi* phi);
-
- HGraph* const graph_;
- ArenaVector<HPhi*> worklist_;
-
- static constexpr size_t kDefaultWorklistSize = 8;
-
- DISALLOW_COPY_AND_ASSIGN(DeadPhiHandling);
-};
-
-static bool HasConflictingEquivalent(HPhi* phi) {
- if (phi->GetNext() == nullptr) {
- return false;
- }
- HPhi* next = phi->GetNext()->AsPhi();
- if (next->GetRegNumber() == phi->GetRegNumber()) {
- if (next->GetType() == Primitive::kPrimVoid) {
- // We only get a void type for an equivalent phi we processed and found out
- // it was conflicting.
- return true;
- } else {
- // Go to the next phi, in case it is also an equivalent.
- return HasConflictingEquivalent(next);
- }
- }
- return false;
-}
-
-bool DeadPhiHandling::UpdateType(HPhi* phi) {
- if (phi->IsDead()) {
- // Phi was rendered dead while waiting in the worklist because it was replaced
- // with an equivalent.
- return false;
- }
-
- Primitive::Type existing = phi->GetType();
-
- bool conflict = false;
- Primitive::Type new_type = existing;
- for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
- HInstruction* input = phi->InputAt(i);
- if (input->IsPhi() && input->AsPhi()->IsDead()) {
- // We are doing a reverse post order visit of the graph, reviving
- // phis that have environment uses and updating their types. If an
- // input is a phi, and it is dead (because its input types are
- // conflicting), this phi must be marked dead as well.
- conflict = true;
- break;
- }
- Primitive::Type input_type = HPhi::ToPhiType(input->GetType());
-
- // The only acceptable transitions are:
- // - From void to typed: first time we update the type of this phi.
- // - From int to reference (or reference to int): the phi has to change
- // to reference type. If the integer input cannot be converted to a
- // reference input, the phi will remain dead.
- if (new_type == Primitive::kPrimVoid) {
- new_type = input_type;
- } else if (new_type == Primitive::kPrimNot && input_type == Primitive::kPrimInt) {
- if (input->IsPhi() && HasConflictingEquivalent(input->AsPhi())) {
- // If we already asked for an equivalent of the input phi, but that equivalent
- // ended up conflicting, make this phi conflicting too.
- conflict = true;
- break;
- }
- HInstruction* equivalent = SsaBuilder::GetReferenceTypeEquivalent(input);
- if (equivalent == nullptr) {
- conflict = true;
- break;
- }
- phi->ReplaceInput(equivalent, i);
- if (equivalent->IsPhi()) {
- DCHECK_EQ(equivalent->GetType(), Primitive::kPrimNot);
- // We created a new phi, but that phi has the same inputs as the old phi. We
- // add it to the worklist to ensure its inputs can also be converted to reference.
- // If not, it will remain dead, and the algorithm will make the current phi dead
- // as well.
- equivalent->AsPhi()->SetLive();
- AddToWorklist(equivalent->AsPhi());
- }
- } else if (new_type == Primitive::kPrimInt && input_type == Primitive::kPrimNot) {
- new_type = Primitive::kPrimNot;
- // Start over, we may request reference equivalents for the inputs of the phi.
- i = -1;
- } else if (new_type != input_type) {
- conflict = true;
- break;
- }
- }
-
- if (conflict) {
- phi->SetType(Primitive::kPrimVoid);
- phi->SetDead();
- return true;
- } else if (existing == new_type) {
- return false;
- }
-
- DCHECK(phi->IsLive());
- phi->SetType(new_type);
-
- // There might exist a `new_type` equivalent of `phi` already. In that case,
- // we replace the equivalent with the, now live, `phi`.
- HPhi* equivalent = phi->GetNextEquivalentPhiWithSameType();
- if (equivalent != nullptr) {
- // There cannot be more than two equivalents with the same type.
- DCHECK(equivalent->GetNextEquivalentPhiWithSameType() == nullptr);
- // If doing fix-point iteration, the equivalent might be in `worklist_`.
- // Setting it dead will make UpdateType skip it.
- equivalent->SetDead();
- equivalent->ReplaceWith(phi);
- }
-
- return true;
-}
-
-void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) {
- for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
- HPhi* phi = it.Current()->AsPhi();
- if (IsUndefinedLoopHeaderPhi(phi)) {
- DCHECK(phi->IsDead());
- continue;
- }
- if (phi->IsDead() && phi->HasEnvironmentUses()) {
- phi->SetLive();
- if (block->IsLoopHeader()) {
- // Loop phis must have a type to guarantee convergence of the algorithm.
- DCHECK_NE(phi->GetType(), Primitive::kPrimVoid);
- AddToWorklist(phi);
- } else {
- // Because we are doing a reverse post order visit, all inputs of
- // this phi have been visited and therefore had their (initial) type set.
- UpdateType(phi);
- }
- }
- }
-}
-
-void DeadPhiHandling::ProcessWorklist() {
- while (!worklist_.empty()) {
- HPhi* instruction = worklist_.back();
- worklist_.pop_back();
- // Note that the same equivalent phi can be added multiple times in the work list, if
- // used by multiple phis. The first call to `UpdateType` will know whether the phi is
- // dead or live.
- if (instruction->IsLive() && UpdateType(instruction)) {
- AddDependentInstructionsToWorklist(instruction);
- }
- }
-}
-
-void DeadPhiHandling::AddToWorklist(HPhi* instruction) {
- DCHECK(instruction->IsLive());
- worklist_.push_back(instruction);
-}
-
-void DeadPhiHandling::AddDependentInstructionsToWorklist(HPhi* instruction) {
- for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
- HPhi* phi = it.Current()->GetUser()->AsPhi();
- if (phi != nullptr && !phi->IsDead()) {
- AddToWorklist(phi);
- }
- }
-}
-
-void DeadPhiHandling::Run() {
- for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
- VisitBasicBlock(it.Current());
- }
- ProcessWorklist();
-}
-
void SsaBuilder::SetLoopHeaderPhiInputs() {
for (size_t i = loop_headers_.size(); i > 0; --i) {
HBasicBlock* block = loop_headers_[i - 1];
@@ -285,10 +82,11 @@
HPhi* phi = it.Current()->AsPhi();
HPhi* next = phi->GetNextEquivalentPhiWithSameType();
if (next != nullptr) {
- // Make sure we do not replace a live phi with a dead phi. A live phi has been
- // handled by the type propagation phase, unlike a dead phi.
+ // Make sure we do not replace a live phi with a dead phi. A live phi
+ // has been handled by the type propagation phase, unlike a dead phi.
if (next->IsLive()) {
phi->ReplaceWith(next);
+ phi->SetDead();
} else {
next->ReplaceWith(phi);
}
@@ -300,64 +98,7 @@
}
}
-void SsaBuilder::BuildSsa() {
- // 1) Visit in reverse post order. We need to have all predecessors of a block visited
- // (with the exception of loops) in order to create the right environment for that
- // block. For loops, we create phis whose inputs will be set in 2).
- for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
- VisitBasicBlock(it.Current());
- }
-
- // 2) Set inputs of loop phis.
- SetLoopHeaderPhiInputs();
-
- // 3) Mark dead phis. This will mark phis that are only used by environments:
- // at the DEX level, the type of these phis does not need to be consistent, but
- // our code generator will complain if the inputs of a phi do not have the same
- // type. The marking allows the type propagation to know which phis it needs
- // to handle. We mark but do not eliminate: the elimination will be done in
- // step 9).
- SsaDeadPhiElimination dead_phis_for_type_propagation(GetGraph());
- dead_phis_for_type_propagation.MarkDeadPhis();
-
- // 4) Propagate types of phis. At this point, phis are typed void in the general
- // case, or float/double/reference when we created an equivalent phi. So we
- // need to propagate the types across phis to give them a correct type.
- PrimitiveTypePropagation type_propagation(GetGraph());
- type_propagation.Run();
-
- // 5) When creating equivalent phis we copy the inputs of the original phi which
- // may be improperly typed. This was fixed during the type propagation in 4) but
- // as a result we may end up with two equivalent phis with the same type for
- // the same dex register. This pass cleans them up.
- EquivalentPhisCleanup();
-
- // 6) Mark dead phis again. Step 4) may have introduced new phis.
- // Step 5) might enable the death of new phis.
- SsaDeadPhiElimination dead_phis(GetGraph());
- dead_phis.MarkDeadPhis();
-
- // 7) Now that the graph is correctly typed, we can get rid of redundant phis.
- // Note that we cannot do this phase before type propagation, otherwise
- // we could get rid of phi equivalents, whose presence is a requirement for the
- // type propagation phase. Note that this is to satisfy statement (a) of the
- // SsaBuilder (see ssa_builder.h).
- SsaRedundantPhiElimination redundant_phi(GetGraph());
- redundant_phi.Run();
-
- // 8) Fix the type for null constants which are part of an equality comparison.
- // We need to do this after redundant phi elimination, to ensure the only cases
- // that we can see are reference comparison against 0. The redundant phi
- // elimination ensures we do not see a phi taking two 0 constants in a HEqual
- // or HNotEqual.
- FixNullConstantType();
-
- // 9) Make sure environments use the right phi "equivalent": a phi marked dead
- // can have a phi equivalent that is not dead. We must therefore update
- // all environment uses of the dead phi to use its equivalent. Note that there
- // can be multiple phis for the same Dex register that are live (for example
- // when merging constants), in which case it is OK for the environments
- // to just reference one.
+void SsaBuilder::FixEnvironmentPhis() {
for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) {
@@ -378,24 +119,345 @@
phi->ReplaceWith(next);
}
}
+}
- // 10) Deal with phis to guarantee liveness of phis in case of a debuggable
- // application. This is for satisfying statement (c) of the SsaBuilder
- // (see ssa_builder.h).
- if (GetGraph()->IsDebuggable()) {
- DeadPhiHandling dead_phi_handler(GetGraph());
- dead_phi_handler.Run();
+static void AddDependentInstructionsToWorklist(HInstruction* instruction,
+ ArenaVector<HPhi*>* worklist) {
+ // If `instruction` is a dead phi, type conflict was just identified. All its
+ // live phi users, and transitively users of those users, therefore need to be
+ // marked dead/conflicting too, so we add them to the worklist. Otherwise we
+ // add users whose type does not match and needs to be updated.
+ bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead();
+ for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
+ HInstruction* user = it.Current()->GetUser();
+ if (user->IsPhi() && user->AsPhi()->IsLive()) {
+ if (add_all_live_phis || user->GetType() != instruction->GetType()) {
+ worklist->push_back(user->AsPhi());
+ }
+ }
+ }
+}
+
+// Find a candidate primitive type for `phi` by merging the type of its inputs.
+// Return false if conflict is identified.
+static bool TypePhiFromInputs(HPhi* phi) {
+ Primitive::Type common_type = phi->GetType();
+
+ for (HInputIterator it(phi); !it.Done(); it.Advance()) {
+ HInstruction* input = it.Current();
+ if (input->IsPhi() && input->AsPhi()->IsDead()) {
+ // Phis are constructed live so if an input is a dead phi, it must have
+ // been made dead due to type conflict. Mark this phi conflicting too.
+ return false;
+ }
+
+ Primitive::Type input_type = HPhi::ToPhiType(input->GetType());
+ if (common_type == input_type) {
+ // No change in type.
+ } else if (Primitive::ComponentSize(common_type) != Primitive::ComponentSize(input_type)) {
+ // Types are of different sizes, e.g. int vs. long. Must be a conflict.
+ return false;
+ } else if (Primitive::IsIntegralType(common_type)) {
+ // Previous inputs were integral, this one is not but is of the same size.
+ // This does not imply conflict since some bytecode instruction types are
+ // ambiguous. TypeInputsOfPhi will either type them or detect a conflict.
+ DCHECK(Primitive::IsFloatingPointType(input_type) || input_type == Primitive::kPrimNot);
+ common_type = input_type;
+ } else if (Primitive::IsIntegralType(input_type)) {
+ // Input is integral, common type is not. Same as in the previous case, if
+ // there is a conflict, it will be detected during TypeInputsOfPhi.
+ DCHECK(Primitive::IsFloatingPointType(common_type) || common_type == Primitive::kPrimNot);
+ } else {
+ // Combining float and reference types. Clearly a conflict.
+ DCHECK((common_type == Primitive::kPrimFloat && input_type == Primitive::kPrimNot) ||
+ (common_type == Primitive::kPrimNot && input_type == Primitive::kPrimFloat));
+ return false;
+ }
}
- // 11) Now that the right phis are used for the environments, and we
- // have potentially revive dead phis in case of a debuggable application,
- // we can eliminate phis we do not need. Regardless of the debuggable status,
- // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h),
- // as well as for the code generation, which does not deal with phis of conflicting
- // input types.
- dead_phis.EliminateDeadPhis();
+ // We have found a candidate type for the phi. Set it and return true. We may
+ // still discover conflict whilst typing the individual inputs in TypeInputsOfPhi.
+ phi->SetType(common_type);
+ return true;
+}
- // 12) Clear locals.
+// Replace inputs of `phi` to match its type. Return false if conflict is identified.
+bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) {
+ Primitive::Type common_type = phi->GetType();
+ if (common_type == Primitive::kPrimVoid || Primitive::IsIntegralType(common_type)) {
+ // Phi either contains only other untyped phis (common_type == kPrimVoid),
+ // or `common_type` is integral and we do not need to retype ambiguous inputs
+ // because they are always constructed with the integral type candidate.
+ if (kIsDebugBuild) {
+ for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
+ HInstruction* input = phi->InputAt(i);
+ if (common_type == Primitive::kPrimVoid) {
+ DCHECK(input->IsPhi() && input->GetType() == Primitive::kPrimVoid);
+ } else {
+ DCHECK((input->IsPhi() && input->GetType() == Primitive::kPrimVoid) ||
+ HPhi::ToPhiType(input->GetType()) == common_type);
+ }
+ }
+ }
+ // Inputs did not need to be replaced, hence no conflict. Report success.
+ return true;
+ } else {
+ DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type));
+ for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
+ HInstruction* input = phi->InputAt(i);
+ if (input->GetType() != common_type) {
+ // Input type does not match phi's type. Try to retype the input or
+ // generate a suitably typed equivalent.
+ HInstruction* equivalent = (common_type == Primitive::kPrimNot)
+ ? GetReferenceTypeEquivalent(input)
+ : GetFloatOrDoubleEquivalent(input, common_type);
+ if (equivalent == nullptr) {
+ // Input could not be typed. Report conflict.
+ return false;
+ }
+ // Make sure the input did not change its type and we do not need to
+ // update its users.
+ DCHECK_NE(input, equivalent);
+
+ phi->ReplaceInput(equivalent, i);
+ if (equivalent->IsPhi()) {
+ worklist->push_back(equivalent->AsPhi());
+ }
+ }
+ }
+ // All inputs either matched the type of the phi or we successfully replaced
+ // them with a suitable equivalent. Report success.
+ return true;
+ }
+}
+
+// Attempt to set the primitive type of `phi` to match its inputs. Return whether
+// it was changed by the algorithm or not.
+bool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist) {
+ DCHECK(phi->IsLive());
+ Primitive::Type original_type = phi->GetType();
+
+ // Try to type the phi in two stages:
+ // (1) find a candidate type for the phi by merging types of all its inputs,
+ // (2) try to type the phi's inputs to that candidate type.
+ // Either of these stages may detect a type conflict and fail, in which case
+ // we immediately abort.
+ if (!TypePhiFromInputs(phi) || !TypeInputsOfPhi(phi, worklist)) {
+ // Conflict detected. Mark the phi dead and return true because it changed.
+ phi->SetDead();
+ return true;
+ }
+
+ // Return true if the type of the phi has changed.
+ return phi->GetType() != original_type;
+}
+
+void SsaBuilder::RunPrimitiveTypePropagation() {
+ ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter());
+
+ for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ if (block->IsLoopHeader()) {
+ for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+ HPhi* phi = phi_it.Current()->AsPhi();
+ if (phi->IsLive()) {
+ worklist.push_back(phi);
+ }
+ }
+ } else {
+ for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+ // Eagerly compute the type of the phi, for quicker convergence. Note
+ // that we don't need to add users to the worklist because we are
+ // doing a reverse post-order visit, therefore either the phi users are
+ // non-loop phi and will be visited later in the visit, or are loop-phis,
+ // and they are already in the work list.
+ HPhi* phi = phi_it.Current()->AsPhi();
+ if (phi->IsLive()) {
+ UpdatePrimitiveType(phi, &worklist);
+ }
+ }
+ }
+ }
+
+ ProcessPrimitiveTypePropagationWorklist(&worklist);
+ EquivalentPhisCleanup();
+}
+
+void SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist) {
+ // Process worklist
+ while (!worklist->empty()) {
+ HPhi* phi = worklist->back();
+ worklist->pop_back();
+ // The phi could have been made dead as a result of conflicts while in the
+ // worklist. If it is now dead, there is no point in updating its type.
+ if (phi->IsLive() && UpdatePrimitiveType(phi, worklist)) {
+ AddDependentInstructionsToWorklist(phi, worklist);
+ }
+ }
+}
+
+static HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
+ Primitive::Type type = aget->GetType();
+ DCHECK(Primitive::IsIntOrLongType(type));
+ HArrayGet* next = aget->GetNext()->AsArrayGet();
+ return (next != nullptr && next->IsEquivalentOf(aget)) ? next : nullptr;
+}
+
+static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
+ Primitive::Type type = aget->GetType();
+ DCHECK(Primitive::IsIntOrLongType(type));
+ DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr);
+
+ HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetArena()) HArrayGet(
+ aget->GetArray(),
+ aget->GetIndex(),
+ type == Primitive::kPrimInt ? Primitive::kPrimFloat : Primitive::kPrimDouble,
+ aget->GetDexPc());
+ aget->GetBlock()->InsertInstructionAfter(equivalent, aget);
+ return equivalent;
+}
+
+// Returns true if the array input of `aget` is either of type int[] or long[].
+// Should only be called on ArrayGets with ambiguous type (int/float, long/double)
+// on arrays which were typed to an array class by RTP.
+static bool IsArrayGetOnIntegralArray(HArrayGet* aget) SHARED_REQUIRES(Locks::mutator_lock_) {
+ ReferenceTypeInfo array_type = aget->GetArray()->GetReferenceTypeInfo();
+ DCHECK(array_type.IsPrimitiveArrayClass());
+ ReferenceTypeInfo::TypeHandle array_type_handle = array_type.GetTypeHandle();
+
+ bool is_integral_type;
+ if (Primitive::Is64BitType(aget->GetType())) {
+ is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveLong();
+ DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveDouble());
+ } else {
+ is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveInt();
+ DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveFloat());
+ }
+ return is_integral_type;
+}
+
+bool SsaBuilder::FixAmbiguousArrayGets() {
+ if (ambiguous_agets_.empty()) {
+ return true;
+ }
+
+ // The wrong ArrayGet equivalent may still have Phi uses coming from ArraySet
+ // uses (because they are untyped) and environment uses (if --debuggable).
+ // After resolving all ambiguous ArrayGets, we will re-run primitive type
+ // propagation on the Phis which need to be updated.
+ ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter());
+
+ {
+ ScopedObjectAccess soa(Thread::Current());
+
+ for (HArrayGet* aget_int : ambiguous_agets_) {
+ if (!aget_int->GetArray()->GetReferenceTypeInfo().IsPrimitiveArrayClass()) {
+ // RTP did not type the input array. Bail.
+ return false;
+ }
+
+ HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int);
+ if (IsArrayGetOnIntegralArray(aget_int)) {
+ if (aget_float != nullptr) {
+ // There is a float/double equivalent. We must replace it and re-run
+ // primitive type propagation on all dependent instructions.
+ aget_float->ReplaceWith(aget_int);
+ aget_float->GetBlock()->RemoveInstruction(aget_float);
+ AddDependentInstructionsToWorklist(aget_int, &worklist);
+ }
+ } else {
+ if (aget_float == nullptr) {
+ // This is a float/double ArrayGet but there were no typed uses which
+ // would create the typed equivalent. Create it now.
+ aget_float = CreateFloatOrDoubleEquivalentOfArrayGet(aget_int);
+ }
+ // Replace the original int/long instruction. Note that it may have phi
+ // uses, environment uses, as well as real uses (from untyped ArraySets).
+ // We need to re-run primitive type propagation on its dependent instructions.
+ aget_int->ReplaceWith(aget_float);
+ aget_int->GetBlock()->RemoveInstruction(aget_int);
+ AddDependentInstructionsToWorklist(aget_float, &worklist);
+ }
+ }
+ }
+
+ // Set a flag stating that types of ArrayGets have been resolved. This is used
+ // by GetFloatOrDoubleEquivalentOfArrayGet to report conflict.
+ agets_fixed_ = true;
+
+ if (!worklist.empty()) {
+ ProcessPrimitiveTypePropagationWorklist(&worklist);
+ EquivalentPhisCleanup();
+ }
+
+ return true;
+}
+
+BuildSsaResult SsaBuilder::BuildSsa() {
+ // 1) Visit in reverse post order. We need to have all predecessors of a block
+ // visited (with the exception of loops) in order to create the right environment
+ // for that block. For loops, we create phis whose inputs will be set in 2).
+ for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
+ VisitBasicBlock(it.Current());
+ }
+
+ // 2) Set inputs of loop header phis.
+ SetLoopHeaderPhiInputs();
+
+ // 3) Propagate types of phis. At this point, phis are typed void in the general
+ // case, or float/double/reference if we created an equivalent phi. So we need
+ // to propagate the types across phis to give them a correct type. If a type
+ // conflict is detected in this stage, the phi is marked dead.
+ RunPrimitiveTypePropagation();
+
+ // 4) Now that the correct primitive types have been assigned, we can get rid
+ // of redundant phis. Note that we cannot do this phase before type propagation,
+ // otherwise we could get rid of phi equivalents, whose presence is a requirement
+ // for the type propagation phase. Note that this is to satisfy statement (a)
+ // of the SsaBuilder (see ssa_builder.h).
+ SsaRedundantPhiElimination(GetGraph()).Run();
+
+ // 5) Fix the type for null constants which are part of an equality comparison.
+ // We need to do this after redundant phi elimination, to ensure the only cases
+ // that we can see are reference comparison against 0. The redundant phi
+ // elimination ensures we do not see a phi taking two 0 constants in a HEqual
+ // or HNotEqual.
+ FixNullConstantType();
+
+ // 6) Compute type of reference type instructions. The pass assumes that
+ // NullConstant has been fixed up.
+ ReferenceTypePropagation(GetGraph(), handles_).Run();
+
+ // 7) Step 1) duplicated ArrayGet instructions with ambiguous type (int/float
+ // or long/double). Now that RTP computed the type of the array input, the
+ // ambiguity can be resolved and the correct equivalent kept.
+ if (!FixAmbiguousArrayGets()) {
+ return kBuildSsaFailAmbiguousArrayGet;
+ }
+
+ // 8) Mark dead phis. This will mark phis which are not used by instructions
+ // or other live phis. If compiling as debuggable code, phis will also be kept
+ // live if they have an environment use.
+ SsaDeadPhiElimination dead_phi_elimimation(GetGraph());
+ dead_phi_elimimation.MarkDeadPhis();
+
+ // 9) Make sure environments use the right phi equivalent: a phi marked dead
+ // can have a phi equivalent that is not dead. In that case we have to replace
+ // it with the live equivalent because deoptimization and try/catch rely on
+ // environments containing values of all live vregs at that point. Note that
+ // there can be multiple phis for the same Dex register that are live
+ // (for example when merging constants), in which case it is okay for the
+ // environments to just reference one.
+ FixEnvironmentPhis();
+
+ // 10) Now that the right phis are used for the environments, we can eliminate
+ // phis we do not need. Regardless of the debuggable status, this phase is
+ /// necessary for statement (b) of the SsaBuilder (see ssa_builder.h), as well
+ // as for the code generation, which does not deal with phis of conflicting
+ // input types.
+ dead_phi_elimimation.EliminateDeadPhis();
+
+ // 11) Clear locals.
for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions());
!it.Done();
it.Advance()) {
@@ -404,6 +466,8 @@
current->GetBlock()->RemoveInstruction(current);
}
}
+
+ return kBuildSsaSuccess;
}
ArenaVector<HInstruction*>* SsaBuilder::GetLocalsFor(HBasicBlock* block) {
@@ -591,6 +655,8 @@
* phi with a floating point / reference type.
*/
HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) {
+ DCHECK(phi->IsLive()) << "Cannot get equivalent of a dead phi since it would create a live one.";
+
// We place the floating point /reference phi next to this phi.
HInstruction* next = phi->GetNext();
if (next != nullptr
@@ -606,35 +672,50 @@
ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena();
HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type);
for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
- // Copy the inputs. Note that the graph may not be correctly typed by doing this copy,
- // but the type propagation phase will fix it.
+ // Copy the inputs. Note that the graph may not be correctly typed
+ // by doing this copy, but the type propagation phase will fix it.
new_phi->SetRawInputAt(i, phi->InputAt(i));
}
phi->GetBlock()->InsertPhiAfter(new_phi, phi);
+ DCHECK(new_phi->IsLive());
return new_phi;
} else {
+ // An existing equivalent was found. If it is dead, conflict was previously
+ // identified and we return nullptr instead.
HPhi* next_phi = next->AsPhi();
DCHECK_EQ(next_phi->GetType(), type);
- if (next_phi->IsDead()) {
- // TODO(dbrazdil): Remove this SetLive (we should not need to revive phis)
- // once we stop running MarkDeadPhis before PrimitiveTypePropagation. This
- // cannot revive undefined loop header phis because they cannot have uses.
- DCHECK(!IsUndefinedLoopHeaderPhi(next_phi));
- next_phi->SetLive();
- }
- return next_phi;
+ return next_phi->IsLive() ? next_phi : nullptr;
}
}
-HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user,
- HInstruction* value,
- Primitive::Type type) {
+HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) {
+ DCHECK(Primitive::IsIntegralType(aget->GetType()));
+
+ if (!Primitive::IsIntOrLongType(aget->GetType())) {
+ // Cannot type boolean, char, byte, short to float/double.
+ return nullptr;
+ }
+
+ DCHECK(ContainsElement(ambiguous_agets_, aget));
+ if (agets_fixed_) {
+ // This used to be an ambiguous ArrayGet but its type has been resolved to
+ // int/long. Requesting a float/double equivalent should lead to a conflict.
+ if (kIsDebugBuild) {
+ ScopedObjectAccess soa(Thread::Current());
+ DCHECK(IsArrayGetOnIntegralArray(aget));
+ }
+ return nullptr;
+ } else {
+ // This is an ambiguous ArrayGet which has not been resolved yet. Return an
+ // equivalent float/double instruction to use until it is resolved.
+ HArrayGet* equivalent = FindFloatOrDoubleEquivalentOfArrayGet(aget);
+ return (equivalent == nullptr) ? CreateFloatOrDoubleEquivalentOfArrayGet(aget) : equivalent;
+ }
+}
+
+HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primitive::Type type) {
if (value->IsArrayGet()) {
- // The verifier has checked that values in arrays cannot be used for both
- // floating point and non-floating point operations. It is therefore safe to just
- // change the type of the operation.
- value->AsArrayGet()->SetType(type);
- return value;
+ return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet());
} else if (value->IsLongConstant()) {
return GetDoubleEquivalent(value->AsLongConstant());
} else if (value->IsIntConstant()) {
@@ -642,12 +723,7 @@
} else if (value->IsPhi()) {
return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type);
} else {
- // For other instructions, we assume the verifier has checked that the dex format is correctly
- // typed and the value in a dex register will not be used for both floating point and
- // non-floating point operations. So the only reason an instruction would want a floating
- // point equivalent is for an unused phi that will be removed by the dead phi elimination phase.
- DCHECK(user->IsPhi()) << "is actually " << user->DebugName() << " (" << user->GetId() << ")";
- return value;
+ return nullptr;
}
}
@@ -662,15 +738,17 @@
}
void SsaBuilder::VisitLoadLocal(HLoadLocal* load) {
+ Primitive::Type load_type = load->GetType();
HInstruction* value = (*current_locals_)[load->GetLocal()->GetRegNumber()];
// If the operation requests a specific type, we make sure its input is of that type.
- if (load->GetType() != value->GetType()) {
- if (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble) {
- value = GetFloatOrDoubleEquivalent(load, value, load->GetType());
- } else if (load->GetType() == Primitive::kPrimNot) {
+ if (load_type != value->GetType()) {
+ if (load_type == Primitive::kPrimFloat || load_type == Primitive::kPrimDouble) {
+ value = GetFloatOrDoubleEquivalent(value, load_type);
+ } else if (load_type == Primitive::kPrimNot) {
value = GetReferenceTypeEquivalent(value);
}
}
+
load->ReplaceWith(value);
load->GetBlock()->RemoveInstruction(load);
}
@@ -760,4 +838,13 @@
temp->GetBlock()->RemoveInstruction(temp);
}
+void SsaBuilder::VisitArrayGet(HArrayGet* aget) {
+ Primitive::Type type = aget->GetType();
+ DCHECK(!Primitive::IsFloatingPointType(type));
+ if (Primitive::IsIntOrLongType(type)) {
+ ambiguous_agets_.push_back(aget);
+ }
+ VisitInstruction(aget);
+}
+
} // namespace art
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index dcce5e4..ed6f5ca 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -49,17 +49,20 @@
*/
class SsaBuilder : public HGraphVisitor {
public:
- explicit SsaBuilder(HGraph* graph)
+ explicit SsaBuilder(HGraph* graph, StackHandleScopeCollection* handles)
: HGraphVisitor(graph),
+ handles_(handles),
+ agets_fixed_(false),
current_locals_(nullptr),
loop_headers_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)),
+ ambiguous_agets_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)),
locals_for_(graph->GetBlocks().size(),
ArenaVector<HInstruction*>(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)),
graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) {
loop_headers_.reserve(kDefaultNumberOfLoops);
}
- void BuildSsa();
+ BuildSsaResult BuildSsa();
// Returns locals vector for `block`. If it is a catch block, the vector will be
// prepopulated with catch phis for vregs which are defined in `current_locals_`.
@@ -71,23 +74,38 @@
void VisitStoreLocal(HStoreLocal* store);
void VisitInstruction(HInstruction* instruction);
void VisitTemporary(HTemporary* instruction);
-
- static HInstruction* GetFloatOrDoubleEquivalent(HInstruction* user,
- HInstruction* instruction,
- Primitive::Type type);
-
- static HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction);
+ void VisitArrayGet(HArrayGet* aget);
static constexpr const char* kSsaBuilderPassName = "ssa_builder";
private:
void SetLoopHeaderPhiInputs();
+ void FixEnvironmentPhis();
void FixNullConstantType();
void EquivalentPhisCleanup();
+ void RunPrimitiveTypePropagation();
- static HFloatConstant* GetFloatEquivalent(HIntConstant* constant);
- static HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant);
- static HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type);
+ // Attempts to resolve types of aget and aget-wide instructions from reference
+ // type information on the input array. Returns false if the type of the array
+ // is unknown.
+ bool FixAmbiguousArrayGets();
+
+ bool TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist);
+ bool UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist);
+ void ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist);
+
+ HInstruction* GetFloatOrDoubleEquivalent(HInstruction* instruction, Primitive::Type type);
+ HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction);
+
+ HFloatConstant* GetFloatEquivalent(HIntConstant* constant);
+ HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant);
+ HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type);
+ HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget);
+
+ StackHandleScopeCollection* const handles_;
+
+ // True if types of ambiguous ArrayGets have been resolved.
+ bool agets_fixed_;
// Locals for the current block being visited.
ArenaVector<HInstruction*>* current_locals_;
@@ -96,6 +114,8 @@
// over these blocks to set the inputs of their phis.
ArenaVector<HBasicBlock*> loop_headers_;
+ ArenaVector<HArrayGet*> ambiguous_agets_;
+
// HEnvironment for each block.
ArenaVector<ArenaVector<HInstruction*>> locals_for_;
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index a3219dc..63aba88 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -40,15 +40,17 @@
continue;
}
- bool has_non_phi_use = false;
- for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
- if (!use_it.Current()->GetUser()->IsPhi()) {
- has_non_phi_use = true;
- break;
+ bool keep_alive = (graph_->IsDebuggable() && phi->HasEnvironmentUses());
+ if (!keep_alive) {
+ for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
+ if (!use_it.Current()->GetUser()->IsPhi()) {
+ keep_alive = true;
+ break;
+ }
}
}
- if (has_non_phi_use) {
+ if (keep_alive) {
worklist_.push_back(phi);
} else {
phi->SetDead();
@@ -94,8 +96,8 @@
for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done();
use_it.Advance()) {
HInstruction* user = use_it.Current()->GetUser();
- DCHECK(user->IsLoopHeaderPhi()) << user->GetId();
- DCHECK(user->AsPhi()->IsDead()) << user->GetId();
+ DCHECK(user->IsLoopHeaderPhi());
+ DCHECK(user->AsPhi()->IsDead());
}
}
// Remove the phi from use lists of its inputs.
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index 024278f..d2885a8 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -28,6 +28,8 @@
namespace art {
+class SsaTest : public CommonCompilerTest {};
+
class SsaPrettyPrinter : public HPrettyPrinter {
public:
explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}
@@ -83,11 +85,10 @@
bool graph_built = builder.BuildGraph(*item);
ASSERT_TRUE(graph_built);
- graph->BuildDominatorTree();
+ TransformToSsa(graph);
// Suspend checks implementation may change in the future, and this test relies
// on how instructions are ordered.
RemoveSuspendChecks(graph);
- graph->TransformToSsa();
ReNumberInstructions(graph);
// Test that phis had their type set.
@@ -103,7 +104,7 @@
ASSERT_STREQ(expected, printer.str().c_str());
}
-TEST(SsaTest, CFG1) {
+TEST_F(SsaTest, CFG1) {
// Test that we get rid of loads and stores.
const char* expected =
"BasicBlock 0, succ: 1\n"
@@ -131,7 +132,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, CFG2) {
+TEST_F(SsaTest, CFG2) {
// Test that we create a phi for the join block of an if control flow instruction
// when there is only code in the else branch.
const char* expected =
@@ -162,7 +163,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, CFG3) {
+TEST_F(SsaTest, CFG3) {
// Test that we create a phi for the join block of an if control flow instruction
// when both branches update a local.
const char* expected =
@@ -195,7 +196,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, Loop1) {
+TEST_F(SsaTest, Loop1) {
// Test that we create a phi for an initialized local at entry of a loop.
const char* expected =
"BasicBlock 0, succ: 1\n"
@@ -228,7 +229,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, Loop2) {
+TEST_F(SsaTest, Loop2) {
// Simple loop with one preheader and one back edge.
const char* expected =
"BasicBlock 0, succ: 1\n"
@@ -258,7 +259,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, Loop3) {
+TEST_F(SsaTest, Loop3) {
// Test that a local not yet defined at the entry of a loop is handled properly.
const char* expected =
"BasicBlock 0, succ: 1\n"
@@ -290,7 +291,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, Loop4) {
+TEST_F(SsaTest, Loop4) {
// Make sure we support a preheader of a loop not being the first predecessor
// in the predecessor list of the header.
const char* expected =
@@ -325,7 +326,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, Loop5) {
+TEST_F(SsaTest, Loop5) {
// Make sure we create a preheader of a loop when a header originally has two
// incoming blocks and one back edge.
const char* expected =
@@ -367,7 +368,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, Loop6) {
+TEST_F(SsaTest, Loop6) {
// Test a loop with one preheader and two back edges (e.g. continue).
const char* expected =
"BasicBlock 0, succ: 1\n"
@@ -406,7 +407,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, Loop7) {
+TEST_F(SsaTest, Loop7) {
// Test a loop with one preheader, one back edge, and two exit edges (e.g. break).
const char* expected =
"BasicBlock 0, succ: 1\n"
@@ -448,7 +449,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, DeadLocal) {
+TEST_F(SsaTest, DeadLocal) {
// Test that we correctly handle a local not being used.
const char* expected =
"BasicBlock 0, succ: 1\n"
@@ -466,7 +467,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, LocalInIf) {
+TEST_F(SsaTest, LocalInIf) {
// Test that we do not create a phi in the join block when one predecessor
// does not update the local.
const char* expected =
@@ -496,7 +497,7 @@
TestCode(data, expected);
}
-TEST(SsaTest, MultiplePredecessors) {
+TEST_F(SsaTest, MultiplePredecessors) {
// Test that we do not create a phi when one predecessor
// does not update the local.
const char* expected =