Make RTP::Visit robust against input order
ReferenceTypePropogation::Visit(ArrayRef) relied on the input having a
particular order with known values at the front then topological. This
could cause issues if the list was not properly sorted, causing the
RTP to silently fail. This makes RTP robust against the ordering of
inputs for this function.
Test: ./test.py --host
Bug: 67037140
Change-Id: I03c522ea745f271ce438c82f7c6f3ab476c8249a
diff --git a/compiler/common_compiler_test.cc b/compiler/common_compiler_test.cc
index 4b6a557..535749b 100644
--- a/compiler/common_compiler_test.cc
+++ b/compiler/common_compiler_test.cc
@@ -44,7 +44,7 @@
namespace art {
-std::unique_ptr<CompilerOptions> CommonCompilerTest::CreateCompilerOptions(
+std::unique_ptr<CompilerOptions> CommonCompilerTestImpl::CreateCompilerOptions(
InstructionSet instruction_set, const std::string& variant) {
std::unique_ptr<CompilerOptions> compiler_options = std::make_unique<CompilerOptions>();
compiler_options->instruction_set_ = instruction_set;
@@ -55,10 +55,11 @@
return compiler_options;
}
-CommonCompilerTest::CommonCompilerTest() {}
-CommonCompilerTest::~CommonCompilerTest() {}
+CommonCompilerTestImpl::CommonCompilerTestImpl() {}
+CommonCompilerTestImpl::~CommonCompilerTestImpl() {}
-void CommonCompilerTest::MakeExecutable(ArtMethod* method, const CompiledMethod* compiled_method) {
+void CommonCompilerTestImpl::MakeExecutable(ArtMethod* method,
+ const CompiledMethod* compiled_method) {
CHECK(method != nullptr);
// If the code size is 0 it means the method was skipped due to profile guided compilation.
if (compiled_method != nullptr && compiled_method->GetQuickCode().size() != 0u) {
@@ -96,11 +97,11 @@
} else {
// No code? You must mean to go into the interpreter.
// Or the generic JNI...
- class_linker_->SetEntryPointsToInterpreter(method);
+ GetClassLinker()->SetEntryPointsToInterpreter(method);
}
}
-void CommonCompilerTest::MakeExecutable(const void* code_start, size_t code_length) {
+void CommonCompilerTestImpl::MakeExecutable(const void* code_start, size_t code_length) {
CHECK(code_start != nullptr);
CHECK_NE(code_length, 0U);
uintptr_t data = reinterpret_cast<uintptr_t>(code_start);
@@ -115,22 +116,22 @@
CHECK(FlushCpuCaches(reinterpret_cast<void*>(base), reinterpret_cast<void*>(base + len)));
}
-void CommonCompilerTest::SetUp() {
- CommonRuntimeTest::SetUp();
+void CommonCompilerTestImpl::SetUp() {
{
ScopedObjectAccess soa(Thread::Current());
- runtime_->SetInstructionSet(instruction_set_);
+ Runtime* runtime = GetRuntime();
+ runtime->SetInstructionSet(instruction_set_);
for (uint32_t i = 0; i < static_cast<uint32_t>(CalleeSaveType::kLastCalleeSaveType); ++i) {
CalleeSaveType type = CalleeSaveType(i);
- if (!runtime_->HasCalleeSaveMethod(type)) {
- runtime_->SetCalleeSaveMethod(runtime_->CreateCalleeSaveMethod(), type);
+ if (!runtime->HasCalleeSaveMethod(type)) {
+ runtime->SetCalleeSaveMethod(runtime->CreateCalleeSaveMethod(), type);
}
}
}
}
-void CommonCompilerTest::ApplyInstructionSet() {
+void CommonCompilerTestImpl::ApplyInstructionSet() {
// Copy local instruction_set_ and instruction_set_features_ to *compiler_options_;
CHECK(instruction_set_features_ != nullptr);
if (instruction_set_ == InstructionSet::kThumb2) {
@@ -144,8 +145,8 @@
CHECK(compiler_options_->instruction_set_features_->Equals(instruction_set_features_.get()));
}
-void CommonCompilerTest::OverrideInstructionSetFeatures(InstructionSet instruction_set,
- const std::string& variant) {
+void CommonCompilerTestImpl::OverrideInstructionSetFeatures(InstructionSet instruction_set,
+ const std::string& variant) {
instruction_set_ = instruction_set;
std::string error_msg;
instruction_set_features_ =
@@ -157,33 +158,29 @@
}
}
-void CommonCompilerTest::SetUpRuntimeOptions(RuntimeOptions* options) {
- CommonRuntimeTest::SetUpRuntimeOptions(options);
-
+void CommonCompilerTestImpl::SetUpRuntimeOptionsImpl() {
compiler_options_.reset(new CompilerOptions);
verification_results_.reset(new VerificationResults(compiler_options_.get()));
ApplyInstructionSet();
}
-Compiler::Kind CommonCompilerTest::GetCompilerKind() const {
+Compiler::Kind CommonCompilerTestImpl::GetCompilerKind() const {
return compiler_kind_;
}
-void CommonCompilerTest::SetCompilerKind(Compiler::Kind compiler_kind) {
+void CommonCompilerTestImpl::SetCompilerKind(Compiler::Kind compiler_kind) {
compiler_kind_ = compiler_kind;
}
-void CommonCompilerTest::TearDown() {
+void CommonCompilerTestImpl::TearDown() {
verification_results_.reset();
compiler_options_.reset();
-
- CommonRuntimeTest::TearDown();
}
-void CommonCompilerTest::CompileMethod(ArtMethod* method) {
+void CommonCompilerTestImpl::CompileMethod(ArtMethod* method) {
CHECK(method != nullptr);
- TimingLogger timings("CommonCompilerTest::CompileMethod", false, false);
+ TimingLogger timings("CommonCompilerTestImpl::CompileMethod", false, false);
TimingLogger::ScopedTiming t(__FUNCTION__, &timings);
CompiledMethodStorage storage(/*swap_fd=*/ -1);
CompiledMethod* compiled_method = nullptr;
@@ -194,7 +191,8 @@
std::unique_ptr<Compiler> compiler(
Compiler::Create(*compiler_options_, &storage, compiler_kind_));
const DexFile& dex_file = *method->GetDexFile();
- Handle<mirror::DexCache> dex_cache = hs.NewHandle(class_linker_->FindDexCache(self, dex_file));
+ Handle<mirror::DexCache> dex_cache =
+ hs.NewHandle(GetClassLinker()->FindDexCache(self, dex_file));
Handle<mirror::ClassLoader> class_loader = hs.NewHandle(method->GetClassLoader());
compiler_options_->verification_results_ = verification_results_.get();
if (method->IsNative()) {
@@ -225,37 +223,41 @@
CompiledMethod::ReleaseSwapAllocatedCompiledMethod(&storage, compiled_method);
}
-void CommonCompilerTest::CompileDirectMethod(Handle<mirror::ClassLoader> class_loader,
- const char* class_name, const char* method_name,
- const char* signature) {
+void CommonCompilerTestImpl::CompileDirectMethod(Handle<mirror::ClassLoader> class_loader,
+ const char* class_name,
+ const char* method_name,
+ const char* signature) {
std::string class_descriptor(DotToDescriptor(class_name));
Thread* self = Thread::Current();
+ ClassLinker* class_linker = GetClassLinker();
ObjPtr<mirror::Class> klass =
- class_linker_->FindClass(self, class_descriptor.c_str(), class_loader);
+ class_linker->FindClass(self, class_descriptor.c_str(), class_loader);
CHECK(klass != nullptr) << "Class not found " << class_name;
- auto pointer_size = class_linker_->GetImagePointerSize();
+ auto pointer_size = class_linker->GetImagePointerSize();
ArtMethod* method = klass->FindClassMethod(method_name, signature, pointer_size);
CHECK(method != nullptr && method->IsDirect()) << "Direct method not found: "
<< class_name << "." << method_name << signature;
CompileMethod(method);
}
-void CommonCompilerTest::CompileVirtualMethod(Handle<mirror::ClassLoader> class_loader,
- const char* class_name, const char* method_name,
- const char* signature) {
+void CommonCompilerTestImpl::CompileVirtualMethod(Handle<mirror::ClassLoader> class_loader,
+ const char* class_name,
+ const char* method_name,
+ const char* signature) {
std::string class_descriptor(DotToDescriptor(class_name));
Thread* self = Thread::Current();
+ ClassLinker* class_linker = GetClassLinker();
ObjPtr<mirror::Class> klass =
- class_linker_->FindClass(self, class_descriptor.c_str(), class_loader);
+ class_linker->FindClass(self, class_descriptor.c_str(), class_loader);
CHECK(klass != nullptr) << "Class not found " << class_name;
- auto pointer_size = class_linker_->GetImagePointerSize();
+ auto pointer_size = class_linker->GetImagePointerSize();
ArtMethod* method = klass->FindClassMethod(method_name, signature, pointer_size);
CHECK(method != nullptr && !method->IsDirect()) << "Virtual method not found: "
<< class_name << "." << method_name << signature;
CompileMethod(method);
}
-void CommonCompilerTest::ClearBootImageOption() {
+void CommonCompilerTestImpl::ClearBootImageOption() {
compiler_options_->image_type_ = CompilerOptions::ImageType::kNone;
}
diff --git a/compiler/common_compiler_test.h b/compiler/common_compiler_test.h
index 703e5f8..8317d7f 100644
--- a/compiler/common_compiler_test.h
+++ b/compiler/common_compiler_test.h
@@ -42,13 +42,13 @@
template<class T> class Handle;
-class CommonCompilerTest : public CommonRuntimeTest {
+class CommonCompilerTestImpl {
public:
static std::unique_ptr<CompilerOptions> CreateCompilerOptions(InstructionSet instruction_set,
const std::string& variant);
- CommonCompilerTest();
- ~CommonCompilerTest();
+ CommonCompilerTestImpl();
+ virtual ~CommonCompilerTestImpl();
void MakeExecutable(ArtMethod* method, const CompiledMethod* compiled_method)
REQUIRES_SHARED(Locks::mutator_lock_);
@@ -56,9 +56,9 @@
static void MakeExecutable(const void* code_start, size_t code_length);
protected:
- void SetUp() override;
+ void SetUp();
- void SetUpRuntimeOptions(RuntimeOptions* options) override;
+ void SetUpRuntimeOptionsImpl();
Compiler::Kind GetCompilerKind() const;
void SetCompilerKind(Compiler::Kind compiler_kind);
@@ -67,7 +67,7 @@
return CompilerFilter::kDefaultCompilerFilter;
}
- void TearDown() override;
+ void TearDown();
void CompileMethod(ArtMethod* method) REQUIRES_SHARED(Locks::mutator_lock_);
@@ -95,11 +95,46 @@
std::unique_ptr<CompilerOptions> compiler_options_;
std::unique_ptr<VerificationResults> verification_results_;
+ protected:
+ virtual ClassLinker* GetClassLinker() = 0;
+ virtual Runtime* GetRuntime() = 0;
+
private:
// Chunks must not move their storage after being created - use the node-based std::list.
std::list<std::vector<uint8_t>> header_code_and_maps_chunks_;
};
+template <typename RuntimeBase>
+class CommonCompilerTestBase : public CommonCompilerTestImpl, public RuntimeBase {
+ public:
+ void SetUp() override {
+ RuntimeBase::SetUp();
+ CommonCompilerTestImpl::SetUp();
+ }
+ void SetUpRuntimeOptions(RuntimeOptions* options) override {
+ RuntimeBase::SetUpRuntimeOptions(options);
+ CommonCompilerTestImpl::SetUpRuntimeOptionsImpl();
+ }
+ void TearDown() override {
+ CommonCompilerTestImpl::TearDown();
+ RuntimeBase::TearDown();
+ }
+
+ protected:
+ ClassLinker* GetClassLinker() override {
+ return RuntimeBase::class_linker_;
+ }
+ Runtime* GetRuntime() override {
+ return RuntimeBase::runtime_.get();
+ }
+};
+
+class CommonCompilerTest : public CommonCompilerTestBase<CommonRuntimeTest> {};
+
+template <typename Param>
+class CommonCompilerTestWithParam
+ : public CommonCompilerTestBase<CommonRuntimeTestWithParam<Param>> {};
+
} // namespace art
#endif // ART_COMPILER_COMMON_COMPILER_TEST_H_
diff --git a/compiler/driver/compiler_options.h b/compiler/driver/compiler_options.h
index 7723707..778e789 100644
--- a/compiler/driver/compiler_options.h
+++ b/compiler/driver/compiler_options.h
@@ -496,7 +496,7 @@
friend class Dex2Oat;
friend class DexToDexDecompilerTest;
friend class CommonCompilerDriverTest;
- friend class CommonCompilerTest;
+ friend class CommonCompilerTestImpl;
friend class jit::JitCompiler;
friend class verifier::VerifierDepsTest;
friend class linker::Arm64RelativePatcherTest;
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 5d80690..953329d 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -18,9 +18,10 @@
#include "art_field-inl.h"
#include "art_method-inl.h"
+#include "base/arena_allocator.h"
+#include "base/enums.h"
#include "base/scoped_arena_allocator.h"
#include "base/scoped_arena_containers.h"
-#include "base/enums.h"
#include "class_linker-inl.h"
#include "class_root-inl.h"
#include "handle_scope-inl.h"
@@ -96,6 +97,9 @@
const DexFile& dex_file,
bool is_exact);
+ // Returns true if this is an instruction we might need to recursively update.
+ // The types are (live) Phi, BoundType, ArrayGet, and NullCheck
+ static constexpr bool IsUpdateable(const HInstruction* instr);
void AddToWorklist(HInstruction* instruction);
void AddDependentInstructionsToWorklist(HInstruction* instruction);
@@ -112,6 +116,8 @@
ScopedArenaAllocator allocator_;
ScopedArenaVector<HInstruction*> worklist_;
const bool is_first_run_;
+
+ friend class ReferenceTypePropagation;
};
ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph,
@@ -172,7 +178,18 @@
hint_dex_cache_,
is_first_run_);
for (HInstruction* instruction : instructions) {
+ if (instruction->IsPhi()) {
+ // Need to force phis to recalculate null-ness.
+ instruction->AsPhi()->SetCanBeNull(false);
+ }
+ }
+ for (HInstruction* instruction : instructions) {
instruction->Accept(&visitor);
+ // We don't know if the instruction list is ordered in the same way normal
+ // visiting would be so we need to process every instruction manually.
+ if (RTPVisitor::IsUpdateable(instruction)) {
+ visitor.AddToWorklist(instruction);
+ }
}
visitor.ProcessWorklist();
}
@@ -968,13 +985,17 @@
}
}
+constexpr bool ReferenceTypePropagation::RTPVisitor::IsUpdateable(const HInstruction* instr) {
+ return (instr->IsPhi() && instr->AsPhi()->IsLive()) ||
+ instr->IsBoundType() ||
+ instr->IsNullCheck() ||
+ instr->IsArrayGet();
+}
+
// Re-computes and updates the nullability of the instruction. Returns whether or
// not the nullability was changed.
bool ReferenceTypePropagation::RTPVisitor::UpdateNullability(HInstruction* instr) {
- DCHECK((instr->IsPhi() && instr->AsPhi()->IsLive())
- || instr->IsBoundType()
- || instr->IsNullCheck()
- || instr->IsArrayGet());
+ DCHECK(IsUpdateable(instr));
if (!instr->IsPhi() && !instr->IsBoundType()) {
return false;
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index a6bb80c..889a846 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -83,7 +83,8 @@
// Whether this reference type propagation is the first run we are doing.
const bool is_first_run_;
- friend class ReferenceTypePropagationTest;
+ template<typename T>
+ friend class ReferenceTypePropagationTestBase;
DISALLOW_COPY_AND_ASSIGN(ReferenceTypePropagation);
};
diff --git a/compiler/optimizing/reference_type_propagation_test.cc b/compiler/optimizing/reference_type_propagation_test.cc
index a0d6609..d90567a 100644
--- a/compiler/optimizing/reference_type_propagation_test.cc
+++ b/compiler/optimizing/reference_type_propagation_test.cc
@@ -16,7 +16,11 @@
#include "reference_type_propagation.h"
+#include <random>
+
#include "base/arena_allocator.h"
+#include "base/transform_array_ref.h"
+#include "base/transform_iterator.h"
#include "builder.h"
#include "nodes.h"
#include "object_lock.h"
@@ -24,15 +28,20 @@
namespace art {
+// TODO It would be good to use the following but there is a miniscule amount of
+// chance for flakiness so we'll just use a set seed instead.
+constexpr bool kUseTrueRandomness = false;
+
/**
* Fixture class for unit testing the ReferenceTypePropagation phase. Used to verify the
* functionality of methods and situations that are hard to set up with checker tests.
*/
-class ReferenceTypePropagationTest : public CommonCompilerTest, public OptimizingUnitTestHelper {
+template<typename SuperTest>
+class ReferenceTypePropagationTestBase : public SuperTest, public OptimizingUnitTestHelper {
public:
- ReferenceTypePropagationTest() : graph_(nullptr), propagation_(nullptr) { }
+ ReferenceTypePropagationTestBase() : graph_(nullptr), propagation_(nullptr) { }
- ~ReferenceTypePropagationTest() { }
+ ~ReferenceTypePropagationTestBase() { }
void SetupPropagation(VariableSizedHandleScope* handles) {
graph_ = CreateGraph(handles);
@@ -70,6 +79,95 @@
ReferenceTypePropagation* propagation_;
};
+class ReferenceTypePropagationTest : public ReferenceTypePropagationTestBase<CommonCompilerTest> {};
+
+enum class ShuffleOrder {
+ kTopological,
+ kReverseTopological,
+ kAlmostTopological,
+ kTrueRandom,
+ kRandomSetSeed,
+
+ kRandom = kUseTrueRandomness ? kTrueRandom : kRandomSetSeed,
+};
+
+std::ostream& operator<<(std::ostream& os, ShuffleOrder so) {
+ switch (so) {
+ case ShuffleOrder::kAlmostTopological:
+ return os << "AlmostTopological";
+ case ShuffleOrder::kReverseTopological:
+ return os << "ReverseTopological";
+ case ShuffleOrder::kTopological:
+ return os << "Topological";
+ case ShuffleOrder::kTrueRandom:
+ return os << "TrueRandom";
+ case ShuffleOrder::kRandomSetSeed:
+ return os << "RandomSetSeed";
+ }
+}
+
+template <typename Param>
+class ParamReferenceTypePropagationTest
+ : public ReferenceTypePropagationTestBase<CommonCompilerTestWithParam<Param>> {
+ public:
+ void MutateList(std::vector<HInstruction*>& lst, ShuffleOrder type);
+};
+
+class NonLoopReferenceTypePropagationTestGroup
+ : public ParamReferenceTypePropagationTest<ShuffleOrder> {
+ public:
+ template <typename Func>
+ void RunVisitListTest(Func mutator);
+};
+
+enum class InitialNullState {
+ kAllNull,
+ kAllNonNull,
+ kHalfNull,
+ kTrueRandom,
+ kRandomSetSeed,
+
+ kRandom = kUseTrueRandomness ? kTrueRandom : kRandomSetSeed,
+};
+
+std::ostream& operator<<(std::ostream& os, InitialNullState ni) {
+ switch (ni) {
+ case InitialNullState::kAllNull:
+ return os << "AllNull";
+ case InitialNullState::kAllNonNull:
+ return os << "AllNonNull";
+ case InitialNullState::kHalfNull:
+ return os << "HalfNull";
+ case InitialNullState::kTrueRandom:
+ return os << "TrueRandom";
+ case InitialNullState::kRandomSetSeed:
+ return os << "RandomSetSeed";
+ }
+}
+
+struct LoopOptions {
+ public:
+ using GtestParam = std::tuple<ShuffleOrder, ssize_t, size_t, InitialNullState>;
+ explicit LoopOptions(GtestParam in) {
+ std::tie(shuffle_, null_insertion_, null_phi_arg_, initial_null_state_) = in;
+ }
+
+ ShuffleOrder shuffle_;
+ // Where in the list of phis we put the null. -1 if don't insert
+ ssize_t null_insertion_;
+ // Where in the phi arg-list we put the null.
+ size_t null_phi_arg_;
+ // What to set the initial null-state of all the phis to.
+ InitialNullState initial_null_state_;
+};
+
+class LoopReferenceTypePropagationTestGroup
+ : public ParamReferenceTypePropagationTest<LoopOptions::GtestParam> {
+ public:
+ template <typename Func>
+ void RunVisitListTest(Func mutator);
+};
+
//
// The actual ReferenceTypePropgation unit tests.
//
@@ -157,4 +255,269 @@
EXPECT_TRUE(t7.IsEqual(ObjectType(false)));
}
+// This generates a large graph with a ton of phis including loop-phis. It then
+// calls the 'mutator' function with the list of all the phis and a CanBeNull
+// instruction and then tries to propagate the types. mutator should reorder the
+// list in some way and modify some phis in whatever way it wants. We verify
+// everything worked by making sure every phi has valid type information.
+template <typename Func>
+void LoopReferenceTypePropagationTestGroup::RunVisitListTest(Func mutator) {
+ ScopedObjectAccess soa(Thread::Current());
+ VariableSizedHandleScope handles(soa.Self());
+ SetupPropagation(&handles);
+ // Make a well-connected graph with a lot of edges.
+ constexpr size_t kNumBlocks = 100;
+ constexpr size_t kTestMaxSuccessors = 3;
+ std::vector<std::string> mid_blocks;
+ for (auto i : Range(kNumBlocks)) {
+ std::ostringstream oss;
+ oss << "blk" << i;
+ mid_blocks.push_back(oss.str());
+ }
+ // Create the edge list.
+ std::vector<AdjacencyListGraph::Edge> edges;
+ for (auto cur : Range(kNumBlocks)) {
+ for (auto nxt : Range(cur + 1, std::min(cur + 1 + kTestMaxSuccessors, kNumBlocks))) {
+ edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
+ }
+ }
+ // Add a loop.
+ edges.emplace_back("start", mid_blocks.front());
+ edges.emplace_back(mid_blocks.back(), mid_blocks.front());
+ edges.emplace_back(mid_blocks.front(), "exit");
+
+ AdjacencyListGraph alg(graph_, GetAllocator(), "start", "exit", edges);
+ std::unordered_map<HBasicBlock*, HInstruction*> single_value;
+ HInstruction* maybe_null_val = new (GetAllocator())
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kReference);
+ ASSERT_TRUE(maybe_null_val->CanBeNull());
+ // Setup the entry-block with the type to be propagated.
+ HInstruction* cls =
+ new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ graph_->GetHandleCache()->GetObjectClassHandle(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ single_value[alg.Get(mid_blocks.front())] = new_inst;
+ HBasicBlock* start = alg.Get("start");
+ start->AddInstruction(maybe_null_val);
+ start->AddInstruction(cls);
+ start->AddInstruction(new_inst);
+ new_inst->SetReferenceTypeInfo(ObjectType(true));
+ maybe_null_val->SetReferenceTypeInfo(ObjectType(true));
+ single_value[start] = new_inst;
+
+ // Setup all the other blocks with a single PHI
+ auto range = MakeIterationRange(mid_blocks);
+ auto succ_blocks = MakeTransformRange(range, [&](const auto& sv) { return alg.Get(sv); });
+ for (HBasicBlock* blk : succ_blocks) {
+ HPhi* phi_inst = new (GetAllocator()) HPhi(
+ GetAllocator(), kNoRegNumber, blk->GetPredecessors().size(), DataType::Type::kReference);
+ single_value[blk] = phi_inst;
+ }
+ for (HBasicBlock* blk : succ_blocks) {
+ HInstruction* my_val = single_value[blk];
+ for (const auto& [pred, index] : ZipCount(MakeIterationRange(blk->GetPredecessors()))) {
+ CHECK(single_value[pred] != nullptr) << pred->GetBlockId() << " " << alg.GetName(pred);
+ my_val->SetRawInputAt(index, single_value[pred]);
+ }
+ }
+ for (HBasicBlock* blk : succ_blocks) {
+ CHECK(single_value[blk]->IsPhi()) << blk->GetBlockId();
+ blk->AddPhi(single_value[blk]->AsPhi());
+ }
+ auto vals = MakeTransformRange(succ_blocks, [&](HBasicBlock* blk) {
+ DCHECK(single_value[blk]->IsPhi());
+ return single_value[blk];
+ });
+ std::vector<HInstruction*> ins(vals.begin(), vals.end());
+ CHECK(std::none_of(ins.begin(), ins.end(), [](auto x) { return x == nullptr; }));
+ mutator(ins, maybe_null_val);
+ propagation_->Visit(ArrayRef<HInstruction* const>(ins));
+ bool is_nullable = !maybe_null_val->GetUses().empty();
+ for (auto [blk, i] : single_value) {
+ if (blk == start) {
+ continue;
+ }
+ EXPECT_TRUE(i->GetReferenceTypeInfo().IsValid())
+ << i->GetId() << " blk: " << alg.GetName(i->GetBlock());
+ if (is_nullable) {
+ EXPECT_TRUE(i->CanBeNull());
+ } else {
+ EXPECT_FALSE(i->CanBeNull());
+ }
+ }
+}
+
+// This generates a large graph with a ton of phis. It then calls the 'mutator'
+// function with the list of all the phis and then tries to propagate the types.
+// mutator should reorder the list in some way. We verify everything worked by
+// making sure every phi has valid type information.
+template <typename Func>
+void NonLoopReferenceTypePropagationTestGroup::RunVisitListTest(Func mutator) {
+ ScopedObjectAccess soa(Thread::Current());
+ VariableSizedHandleScope handles(soa.Self());
+ SetupPropagation(&handles);
+ // Make a well-connected graph with a lot of edges.
+ constexpr size_t kNumBlocks = 5000;
+ constexpr size_t kTestMaxSuccessors = 2;
+ std::vector<std::string> mid_blocks;
+ for (auto i : Range(kNumBlocks)) {
+ std::ostringstream oss;
+ oss << "blk" << i;
+ mid_blocks.push_back(oss.str());
+ }
+ // Create the edge list.
+ std::vector<AdjacencyListGraph::Edge> edges;
+ for (auto cur : Range(kNumBlocks)) {
+ for (auto nxt : Range(cur + 1, std::min(cur + 1 + kTestMaxSuccessors, kNumBlocks))) {
+ edges.emplace_back(mid_blocks[cur], mid_blocks[nxt]);
+ }
+ }
+ AdjacencyListGraph alg(graph_, GetAllocator(), mid_blocks.front(), mid_blocks.back(), edges);
+ std::unordered_map<HBasicBlock*, HInstruction*> single_value;
+ // Setup the entry-block with the type to be propagated.
+ HInstruction* cls =
+ new (GetAllocator()) HLoadClass(graph_->GetCurrentMethod(),
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ graph_->GetHandleCache()->GetObjectClassHandle(),
+ false,
+ 0,
+ false);
+ HInstruction* new_inst =
+ new (GetAllocator()) HNewInstance(cls,
+ 0,
+ dex::TypeIndex(10),
+ graph_->GetDexFile(),
+ false,
+ QuickEntrypointEnum::kQuickAllocObjectInitialized);
+ single_value[alg.Get(mid_blocks.front())] = new_inst;
+ HBasicBlock* start = alg.Get(mid_blocks.front());
+ start->AddInstruction(cls);
+ start->AddInstruction(new_inst);
+ new_inst->SetReferenceTypeInfo(ObjectType(true));
+
+ // Setup all the other blocks with a single PHI
+ auto succ_blk_names = MakeIterationRange(mid_blocks.begin() + 1, mid_blocks.end());
+ auto succ_blocks =
+ MakeTransformRange(succ_blk_names, [&](const auto& sv) { return alg.Get(sv); });
+ for (HBasicBlock* blk : succ_blocks) {
+ HPhi* phi_inst = new (GetAllocator()) HPhi(
+ GetAllocator(), kNoRegNumber, blk->GetPredecessors().size(), DataType::Type::kReference);
+ single_value[blk] = phi_inst;
+ }
+ for (HBasicBlock* blk : succ_blocks) {
+ HInstruction* my_val = single_value[blk];
+ for (const auto& [pred, index] : ZipCount(MakeIterationRange(blk->GetPredecessors()))) {
+ my_val->SetRawInputAt(index, single_value[pred]);
+ }
+ blk->AddPhi(my_val->AsPhi());
+ }
+ auto vals = MakeTransformRange(succ_blocks, [&](HBasicBlock* blk) { return single_value[blk]; });
+ std::vector<HInstruction*> ins(vals.begin(), vals.end());
+ graph_->ClearReachabilityInformation();
+ graph_->ComputeReachabilityInformation();
+ mutator(ins);
+ propagation_->Visit(ArrayRef<HInstruction* const>(ins));
+ for (auto [blk, i] : single_value) {
+ if (blk == start) {
+ continue;
+ }
+ EXPECT_TRUE(i->GetReferenceTypeInfo().IsValid())
+ << i->GetId() << " blk: " << alg.GetName(i->GetBlock());
+ }
+}
+
+template <typename Param>
+void ParamReferenceTypePropagationTest<Param>::MutateList(std::vector<HInstruction*>& lst,
+ ShuffleOrder type) {
+ DCHECK(std::none_of(lst.begin(), lst.end(), [](auto* i) { return i == nullptr; }));
+ std::default_random_engine g(type != ShuffleOrder::kTrueRandom ? 42 : std::rand());
+ switch (type) {
+ case ShuffleOrder::kTopological: {
+ // Input is topologically sorted due to the way we create the phis.
+ break;
+ }
+ case ShuffleOrder::kReverseTopological: {
+ std::reverse(lst.begin(), lst.end());
+ break;
+ }
+ case ShuffleOrder::kAlmostTopological: {
+ std::swap(lst.front(), lst.back());
+ break;
+ }
+ case ShuffleOrder::kRandomSetSeed:
+ case ShuffleOrder::kTrueRandom: {
+ std::shuffle(lst.begin(), lst.end(), g);
+ break;
+ }
+ }
+}
+
+TEST_P(LoopReferenceTypePropagationTestGroup, RunVisitTest) {
+ LoopOptions lo(GetParam());
+ std::default_random_engine g(
+ lo.initial_null_state_ != InitialNullState::kTrueRandom ? 42 : std::rand());
+ std::uniform_int_distribution<bool> uid(false, true);
+ RunVisitListTest([&](std::vector<HInstruction*>& lst, HInstruction* null_input) {
+ auto pred_null = false;
+ auto next_null = [&]() {
+ switch (lo.initial_null_state_) {
+ case InitialNullState::kAllNonNull:
+ return false;
+ case InitialNullState::kAllNull:
+ return true;
+ case InitialNullState::kHalfNull:
+ pred_null = !pred_null;
+ return pred_null;
+ case InitialNullState::kRandomSetSeed:
+ case InitialNullState::kTrueRandom:
+ return uid(g);
+ }
+ };
+ HPhi* nulled_phi = lo.null_insertion_ >= 0 ? lst[lo.null_insertion_]->AsPhi() : nullptr;
+ if (nulled_phi != nullptr) {
+ nulled_phi->ReplaceInput(null_input, lo.null_phi_arg_);
+ }
+ MutateList(lst, lo.shuffle_);
+ std::for_each(lst.begin(), lst.end(), [&](HInstruction* ins) {
+ ins->AsPhi()->SetCanBeNull(next_null());
+ });
+ });
+}
+
+INSTANTIATE_TEST_SUITE_P(ReferenceTypePropagationTest,
+ LoopReferenceTypePropagationTestGroup,
+ testing::Combine(testing::Values(ShuffleOrder::kAlmostTopological,
+ ShuffleOrder::kReverseTopological,
+ ShuffleOrder::kTopological,
+ ShuffleOrder::kRandom),
+ testing::Values(-1, 10, 40),
+ testing::Values(0, 1),
+ testing::Values(InitialNullState::kAllNonNull,
+ InitialNullState::kAllNull,
+ InitialNullState::kHalfNull,
+ InitialNullState::kRandom)));
+
+TEST_P(NonLoopReferenceTypePropagationTestGroup, RunVisitTest) {
+ RunVisitListTest([&](std::vector<HInstruction*>& lst) { MutateList(lst, GetParam()); });
+}
+
+INSTANTIATE_TEST_SUITE_P(ReferenceTypePropagationTest,
+ NonLoopReferenceTypePropagationTestGroup,
+ testing::Values(ShuffleOrder::kAlmostTopological,
+ ShuffleOrder::kReverseTopological,
+ ShuffleOrder::kTopological,
+ ShuffleOrder::kRandom));
+
} // namespace art