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

6 files changed, 474 insertions, 52 deletions

diff --git a/compiler/common_compiler_test.cc b/compiler/common_compiler_test.cc
index 4b6a557455..535749b530 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 @@ std::unique_ptr<CompilerOptions> CommonCompilerTest::CreateCompilerOptions(
   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 @@ void CommonCompilerTest::MakeExecutable(ArtMethod* method, const CompiledMethod*
   } 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 @@ void CommonCompilerTest::MakeExecutable(const void* code_start, size_t code_leng
   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 @@ void CommonCompilerTest::ApplyInstructionSet() {
   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::OverrideInstructionSetFeatures(InstructionSet instructi
   }
 }
 
-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 @@ void CommonCompilerTest::CompileMethod(ArtMethod* method) {
     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 @@ void CommonCompilerTest::CompileMethod(ArtMethod* method) {
   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 703e5f8523..8317d7f48a 100644
--- a/compiler/common_compiler_test.h
+++ b/compiler/common_compiler_test.h
@@ -42,13 +42,13 @@ class VerificationResults;
 
 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 @@ class CommonCompilerTest : public CommonRuntimeTest {
   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 @@ class CommonCompilerTest : public CommonRuntimeTest {
     return CompilerFilter::kDefaultCompilerFilter;
   }
 
-  void TearDown() override;
+  void TearDown();
 
   void CompileMethod(ArtMethod* method) REQUIRES_SHARED(Locks::mutator_lock_);
 
@@ -95,11 +95,46 @@ class CommonCompilerTest : public CommonRuntimeTest {
   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 77237078f8..778e7899b3 100644
--- a/compiler/driver/compiler_options.h
+++ b/compiler/driver/compiler_options.h
@@ -496,7 +496,7 @@ class CompilerOptions final {
   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 5d8069056e..953329d5b2 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 @@ class ReferenceTypePropagation::RTPVisitor : public HGraphDelegateVisitor {
                                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 @@ class ReferenceTypePropagation::RTPVisitor : public HGraphDelegateVisitor {
   ScopedArenaAllocator allocator_;
   ScopedArenaVector<HInstruction*> worklist_;
   const bool is_first_run_;
+
+  friend class ReferenceTypePropagation;
 };
 
 ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph,
@@ -172,7 +178,18 @@ void ReferenceTypePropagation::Visit(ArrayRef<HInstruction* const> instructions)
                      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 @@ void ReferenceTypePropagation::RTPVisitor::UpdatePhi(HPhi* instr) {
   }
 }
 
+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 a6bb80c776..889a8465e0 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -83,7 +83,8 @@ class ReferenceTypePropagation : public HOptimization {
   // 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 a0d66093d2..d90567ae7e 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 @@ class ReferenceTypePropagationTest : public CommonCompilerTest, public Optimizin
   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 @@ TEST_F(ReferenceTypePropagationTest, MergeValidTypes) {
   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