Introduce EnvUsePosition for liveness analysis.

Normal and environment use positions are held in separate
lists and the code never mixes them together. By using two
separate classes, we can reduce complexity and avoid an
unnecesary data member, reducing the memory usage.

Tracking allocations for a certain big app, the peak arena
memory usage is
  before:
    MEM: used: 79245960, ...
    SsaLiveness    31221600
  after:
    MEM: used: 78754024, ...
    SsaLiveness    30729664

Test: testrunner.py --host
Bug: 34053922
Change-Id: I02d3c9f564bbe3b1da0e03c33cf7c0f810f235dc

4 files changed, 308 insertions, 43 deletions

diff --git a/compiler/optimizing/register_allocation_resolver.cc b/compiler/optimizing/register_allocation_resolver.cc
index 59523a93a0..8a9c1ccaff 100644
--- a/compiler/optimizing/register_allocation_resolver.cc
+++ b/compiler/optimizing/register_allocation_resolver.cc
@@ -306,7 +306,7 @@ void RegisterAllocationResolver::ConnectSiblings(LiveInterval* interval) {
                         : Location::StackSlot(interval->GetParent()->GetSpillSlot()));
   }
   UsePosition* use = current->GetFirstUse();
-  UsePosition* env_use = current->GetFirstEnvironmentUse();
+  EnvUsePosition* env_use = current->GetFirstEnvironmentUse();
 
   // Walk over all siblings, updating locations of use positions, and
   // connecting them when they are adjacent.
@@ -323,7 +323,6 @@ void RegisterAllocationResolver::ConnectSiblings(LiveInterval* interval) {
         use = use->GetNext();
       }
       while (use != nullptr && use->GetPosition() <= range->GetEnd()) {
-        DCHECK(!use->GetIsEnvironment());
         DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd()));
         if (!use->IsSynthesized()) {
           LocationSummary* locations = use->GetUser()->GetLocations();
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 2227872f76..667afb1ec3 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -912,9 +912,9 @@ TEST_F(RegisterAllocatorTest, SpillInactive) {
   // Create an interval with lifetime holes.
   static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}};
   LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), &allocator, -1, one);
-  first->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, first->first_use_);
-  first->first_use_ = new(&allocator) UsePosition(user, 0, false, 7, first->first_use_);
-  first->first_use_ = new(&allocator) UsePosition(user, 0, false, 6, first->first_use_);
+  first->first_use_ = new(&allocator) UsePosition(user, false, 8, first->first_use_);
+  first->first_use_ = new(&allocator) UsePosition(user, false, 7, first->first_use_);
+  first->first_use_ = new(&allocator) UsePosition(user, false, 6, first->first_use_);
 
   locations = new (&allocator) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall);
   locations->SetOut(Location::RequiresRegister());
@@ -934,9 +934,9 @@ TEST_F(RegisterAllocatorTest, SpillInactive) {
   // before lifetime position 6 yet.
   static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}};
   LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), &allocator, -1, three);
-  third->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, third->first_use_);
-  third->first_use_ = new(&allocator) UsePosition(user, 0, false, 4, third->first_use_);
-  third->first_use_ = new(&allocator) UsePosition(user, 0, false, 3, third->first_use_);
+  third->first_use_ = new(&allocator) UsePosition(user, false, 8, third->first_use_);
+  third->first_use_ = new(&allocator) UsePosition(user, false, 4, third->first_use_);
+  third->first_use_ = new(&allocator) UsePosition(user, false, 3, third->first_use_);
   locations = new (&allocator) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall);
   locations->SetOut(Location::RequiresRegister());
   third = third->SplitAt(3);
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index a239bd50c2..340d0ccefe 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -17,9 +17,10 @@
 #ifndef ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
 #define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
 
-#include "nodes.h"
 #include <iostream>
 
+#include "nodes.h"
+
 namespace art {
 
 class CodeGenerator;
@@ -103,21 +104,20 @@ class LiveRange FINAL : public ArenaObject<kArenaAllocSsaLiveness> {
  */
 class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
  public:
-  UsePosition(HInstruction* user,
-              HEnvironment* environment,
-              size_t input_index,
-              size_t position,
-              UsePosition* next)
+  UsePosition(HInstruction* user, size_t input_index, size_t position, UsePosition* next)
       : user_(user),
-        environment_(environment),
         input_index_(input_index),
         position_(position),
         next_(next) {
-    DCHECK(environment == nullptr || user == nullptr);
     DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
   }
 
-  static constexpr size_t kNoInput = -1;
+  explicit UsePosition(size_t position)
+      : user_(nullptr),
+        input_index_(kNoInput),
+        position_(dchecked_integral_cast<uint32_t>(position)),
+        next_(nullptr) {
+  }
 
   size_t GetPosition() const { return position_; }
 
@@ -125,9 +125,7 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
   void SetNext(UsePosition* next) { next_ = next; }
 
   HInstruction* GetUser() const { return user_; }
-  HEnvironment* GetEnvironment() const { return environment_; }
 
-  bool GetIsEnvironment() const { return environment_ != nullptr; }
   bool IsSynthesized() const { return user_ == nullptr; }
 
   size_t GetInputIndex() const { return input_index_; }
@@ -142,20 +140,20 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
 
   UsePosition* Dup(ArenaAllocator* allocator) const {
     return new (allocator) UsePosition(
-        user_, environment_, input_index_, position_,
+        user_, input_index_, position_,
         next_ == nullptr ? nullptr : next_->Dup(allocator));
   }
 
   bool RequiresRegister() const {
-    if (GetIsEnvironment()) return false;
     if (IsSynthesized()) return false;
     Location location = GetUser()->GetLocations()->InAt(GetInputIndex());
     return location.IsUnallocated() && location.RequiresRegisterKind();
   }
 
  private:
+  static constexpr uint32_t kNoInput = static_cast<uint32_t>(-1);
+
   HInstruction* const user_;
-  HEnvironment* const environment_;
   const size_t input_index_;
   const size_t position_;
   UsePosition* next_;
@@ -163,6 +161,50 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
   DISALLOW_COPY_AND_ASSIGN(UsePosition);
 };
 
+/**
+ * An environment use position represents a live interval for environment use at a given position.
+ */
+class EnvUsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
+ public:
+  EnvUsePosition(HEnvironment* environment,
+                 size_t input_index,
+                 size_t position,
+                 EnvUsePosition* next)
+      : environment_(environment),
+        input_index_(input_index),
+        position_(position),
+        next_(next) {
+    DCHECK(environment != nullptr);
+    DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
+  }
+
+  size_t GetPosition() const { return position_; }
+
+  EnvUsePosition* GetNext() const { return next_; }
+  void SetNext(EnvUsePosition* next) { next_ = next; }
+
+  HEnvironment* GetEnvironment() const { return environment_; }
+  size_t GetInputIndex() const { return input_index_; }
+
+  void Dump(std::ostream& stream) const {
+    stream << position_;
+  }
+
+  EnvUsePosition* Dup(ArenaAllocator* allocator) const {
+    return new (allocator) EnvUsePosition(
+        environment_, input_index_, position_,
+        next_ == nullptr ? nullptr : next_->Dup(allocator));
+  }
+
+ private:
+  HEnvironment* const environment_;
+  const size_t input_index_;
+  const size_t position_;
+  EnvUsePosition* next_;
+
+  DISALLOW_COPY_AND_ASSIGN(EnvUsePosition);
+};
+
 class SafepointPosition : public ArenaObject<kArenaAllocSsaLiveness> {
  public:
   explicit SafepointPosition(HInstruction* instruction)
@@ -227,7 +269,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
     DCHECK(first_env_use_ == nullptr) << "A temporary cannot have environment user";
     size_t position = instruction->GetLifetimePosition();
     first_use_ = new (allocator_) UsePosition(
-        instruction, /* environment */ nullptr, temp_index, position, first_use_);
+        instruction, temp_index, position, first_use_);
     AddRange(position, position + 1);
   }
 
@@ -276,7 +318,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
       }
       DCHECK(first_use_->GetPosition() + 1 == position);
       UsePosition* new_use = new (allocator_) UsePosition(
-          instruction, nullptr /* environment */, input_index, position, cursor->GetNext());
+          instruction, input_index, position, cursor->GetNext());
       cursor->SetNext(new_use);
       if (first_range_->GetEnd() == first_use_->GetPosition()) {
         first_range_->end_ = position;
@@ -285,11 +327,11 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
     }
 
     if (is_environment) {
-      first_env_use_ = new (allocator_) UsePosition(
-          nullptr /* instruction */, environment, input_index, position, first_env_use_);
+      first_env_use_ = new (allocator_) EnvUsePosition(
+          environment, input_index, position, first_env_use_);
     } else {
       first_use_ = new (allocator_) UsePosition(
-          instruction, nullptr /* environment */, input_index, position, first_use_);
+          instruction, input_index, position, first_use_);
     }
 
     if (is_environment && !keep_alive) {
@@ -328,7 +370,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
       AddBackEdgeUses(*block);
     }
     first_use_ = new (allocator_) UsePosition(
-        instruction, /* environment */ nullptr, input_index, block->GetLifetimeEnd(), first_use_);
+        instruction, input_index, block->GetLifetimeEnd(), first_use_);
   }
 
   ALWAYS_INLINE void AddRange(size_t start, size_t end) {
@@ -538,7 +580,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
     return first_use_;
   }
 
-  UsePosition* GetFirstEnvironmentUse() const {
+  EnvUsePosition* GetFirstEnvironmentUse() const {
     return first_env_use_;
   }
 
@@ -676,7 +718,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
       current = current->GetNext();
     }
     stream << "}, uses: { ";
-    UsePosition* use = first_use_;
+    const UsePosition* use = first_use_;
     if (use != nullptr) {
       do {
         use->Dump(stream);
@@ -684,12 +726,12 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
       } while ((use = use->GetNext()) != nullptr);
     }
     stream << "}, { ";
-    use = first_env_use_;
-    if (use != nullptr) {
+    const EnvUsePosition* env_use = first_env_use_;
+    if (env_use != nullptr) {
       do {
-        use->Dump(stream);
+        env_use->Dump(stream);
         stream << " ";
-      } while ((use = use->GetNext()) != nullptr);
+      } while ((env_use = env_use->GetNext()) != nullptr);
     }
     stream << "}";
     stream << " is_fixed: " << is_fixed_ << ", is_split: " << IsSplit();
@@ -1015,12 +1057,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
       DCHECK(last_in_new_list == nullptr ||
              back_edge_use_position > last_in_new_list->GetPosition());
 
-      UsePosition* new_use = new (allocator_) UsePosition(
-          /* user */ nullptr,
-          /* environment */ nullptr,
-          UsePosition::kNoInput,
-          back_edge_use_position,
-          /* next */ nullptr);
+      UsePosition* new_use = new (allocator_) UsePosition(back_edge_use_position);
 
       if (last_in_new_list != nullptr) {
         // Going outward. The latest created use needs to point to the new use.
@@ -1056,7 +1093,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
 
   // Uses of this interval. Note that this linked list is shared amongst siblings.
   UsePosition* first_use_;
-  UsePosition* first_env_use_;
+  EnvUsePosition* first_env_use_;
 
   // The instruction type this interval corresponds to.
   const Primitive::Type type_;
@@ -1210,8 +1247,7 @@ class SsaLivenessAnalysis : public ValueObject {
 
   // Returns whether `instruction` in an HEnvironment held by `env_holder`
   // should be kept live by the HEnvironment.
-  static bool ShouldBeLiveForEnvironment(HInstruction* env_holder,
-                                         HInstruction* instruction) {
+  static bool ShouldBeLiveForEnvironment(HInstruction* env_holder, HInstruction* instruction) {
     if (instruction == nullptr) return false;
     // A value that's not live in compiled code may still be needed in interpreter,
     // due to code motion, etc.
diff --git a/compiler/optimizing/ssa_liveness_analysis_test.cc b/compiler/optimizing/ssa_liveness_analysis_test.cc
new file mode 100644
index 0000000000..cc48d3196b
--- /dev/null
+++ b/compiler/optimizing/ssa_liveness_analysis_test.cc
@@ -0,0 +1,230 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "arch/instruction_set.h"
+#include "arch/instruction_set_features.h"
+#include "base/arena_allocator.h"
+#include "base/arena_containers.h"
+#include "driver/compiler_options.h"
+#include "code_generator.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "ssa_liveness_analysis.h"
+
+namespace art {
+
+class SsaLivenessAnalysisTest : public testing::Test {
+ public:
+  SsaLivenessAnalysisTest()
+      : pool_(),
+        allocator_(&pool_),
+        graph_(CreateGraph(&allocator_)),
+        instruction_set_(kRuntimeISA) {
+    std::string error_msg;
+    instruction_set_features_ =
+        InstructionSetFeatures::FromVariant(instruction_set_, "default", &error_msg);
+    codegen_ = CodeGenerator::Create(graph_,
+                                     instruction_set_,
+                                     *instruction_set_features_,
+                                     CompilerOptions());
+    CHECK(codegen_ != nullptr) << instruction_set_ << " is not a supported target architecture.";
+    // Create entry block.
+    entry_ = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(entry_);
+    graph_->SetEntryBlock(entry_);
+  }
+
+ protected:
+  HBasicBlock* CreateSuccessor(HBasicBlock* block) {
+    HGraph* graph = block->GetGraph();
+    HBasicBlock* successor = new (&allocator_) HBasicBlock(graph);
+    graph->AddBlock(successor);
+    block->AddSuccessor(successor);
+    return successor;
+  }
+
+  ArenaPool pool_;
+  ArenaAllocator allocator_;
+  HGraph* graph_;
+  InstructionSet instruction_set_;
+  std::unique_ptr<const InstructionSetFeatures> instruction_set_features_;
+  std::unique_ptr<CodeGenerator> codegen_;
+  HBasicBlock* entry_;
+};
+
+TEST_F(SsaLivenessAnalysisTest, TestReturnArg) {
+  HInstruction* arg = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);
+  entry_->AddInstruction(arg);
+
+  HBasicBlock* block = CreateSuccessor(entry_);
+  HInstruction* ret = new (&allocator_) HReturn(arg);
+  block->AddInstruction(ret);
+  block->AddInstruction(new (&allocator_) HExit());
+
+  graph_->BuildDominatorTree();
+  SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get());
+  ssa_analysis.Analyze();
+
+  std::ostringstream arg_dump;
+  arg->GetLiveInterval()->Dump(arg_dump);
+  EXPECT_STREQ("ranges: { [2,6) }, uses: { 6 }, { } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
+               arg_dump.str().c_str());
+}
+
+TEST_F(SsaLivenessAnalysisTest, TestAput) {
+  HInstruction* array = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
+  HInstruction* index = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(1), 1, Primitive::kPrimInt);
+  HInstruction* value = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(2), 2, Primitive::kPrimInt);
+  HInstruction* extra_arg1 = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(3), 3, Primitive::kPrimInt);
+  HInstruction* extra_arg2 = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(4), 4, Primitive::kPrimNot);
+  ArenaVector<HInstruction*> args({ array, index, value, extra_arg1, extra_arg2 },
+                                  allocator_.Adapter());
+  for (HInstruction* insn : args) {
+    entry_->AddInstruction(insn);
+  }
+
+  HBasicBlock* block = CreateSuccessor(entry_);
+  HInstruction* null_check = new (&allocator_) HNullCheck(array, 0);
+  block->AddInstruction(null_check);
+  HEnvironment* null_check_env = new (&allocator_) HEnvironment(&allocator_,
+                                                                /* number_of_vregs */ 5,
+                                                                /* method */ nullptr,
+                                                                /* dex_pc */ 0u,
+                                                                null_check);
+  null_check_env->CopyFrom(args);
+  null_check->SetRawEnvironment(null_check_env);
+  HInstruction* length = new (&allocator_) HArrayLength(array, 0);
+  block->AddInstruction(length);
+  HInstruction* bounds_check = new (&allocator_) HBoundsCheck(index, length, /* dex_pc */ 0u);
+  block->AddInstruction(bounds_check);
+  HEnvironment* bounds_check_env = new (&allocator_) HEnvironment(&allocator_,
+                                                                  /* number_of_vregs */ 5,
+                                                                  /* method */ nullptr,
+                                                                  /* dex_pc */ 0u,
+                                                                  bounds_check);
+  bounds_check_env->CopyFrom(args);
+  bounds_check->SetRawEnvironment(bounds_check_env);
+  HInstruction* array_set =
+      new (&allocator_) HArraySet(array, index, value, Primitive::kPrimInt, /* dex_pc */ 0);
+  block->AddInstruction(array_set);
+
+  graph_->BuildDominatorTree();
+  SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get());
+  ssa_analysis.Analyze();
+
+  EXPECT_FALSE(graph_->IsDebuggable());
+  EXPECT_EQ(18u, bounds_check->GetLifetimePosition());
+  static const char* const expected[] = {
+      "ranges: { [2,21) }, uses: { 15 17 21 }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 "
+          "is_high: 0",
+      "ranges: { [4,21) }, uses: { 19 21 }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 "
+          "is_high: 0",
+      "ranges: { [6,21) }, uses: { 21 }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 "
+          "is_high: 0",
+      // Environment uses do not keep the non-reference argument alive.
+      "ranges: { [8,10) }, uses: { }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
+      // Environment uses keep the reference argument alive.
+      "ranges: { [10,19) }, uses: { }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
+  };
+  ASSERT_EQ(arraysize(expected), args.size());
+  size_t arg_index = 0u;
+  for (HInstruction* arg : args) {
+    std::ostringstream arg_dump;
+    arg->GetLiveInterval()->Dump(arg_dump);
+    EXPECT_STREQ(expected[arg_index], arg_dump.str().c_str()) << arg_index;
+    ++arg_index;
+  }
+}
+
+TEST_F(SsaLivenessAnalysisTest, TestDeoptimize) {
+  HInstruction* array = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
+  HInstruction* index = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(1), 1, Primitive::kPrimInt);
+  HInstruction* value = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(2), 2, Primitive::kPrimInt);
+  HInstruction* extra_arg1 = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(3), 3, Primitive::kPrimInt);
+  HInstruction* extra_arg2 = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), dex::TypeIndex(4), 4, Primitive::kPrimNot);
+  ArenaVector<HInstruction*> args({ array, index, value, extra_arg1, extra_arg2 },
+                                  allocator_.Adapter());
+  for (HInstruction* insn : args) {
+    entry_->AddInstruction(insn);
+  }
+
+  HBasicBlock* block = CreateSuccessor(entry_);
+  HInstruction* null_check = new (&allocator_) HNullCheck(array, 0);
+  block->AddInstruction(null_check);
+  HEnvironment* null_check_env = new (&allocator_) HEnvironment(&allocator_,
+                                                                /* number_of_vregs */ 5,
+                                                                /* method */ nullptr,
+                                                                /* dex_pc */ 0u,
+                                                                null_check);
+  null_check_env->CopyFrom(args);
+  null_check->SetRawEnvironment(null_check_env);
+  HInstruction* length = new (&allocator_) HArrayLength(array, 0);
+  block->AddInstruction(length);
+  // Use HAboveOrEqual+HDeoptimize as the bounds check.
+  HInstruction* ae = new (&allocator_) HAboveOrEqual(index, length);
+  block->AddInstruction(ae);
+  HInstruction* deoptimize = new(&allocator_) HDeoptimize(ae, /* dex_pc */ 0u);
+  block->AddInstruction(deoptimize);
+  HEnvironment* deoptimize_env = new (&allocator_) HEnvironment(&allocator_,
+                                                                  /* number_of_vregs */ 5,
+                                                                  /* method */ nullptr,
+                                                                  /* dex_pc */ 0u,
+                                                                  deoptimize);
+  deoptimize_env->CopyFrom(args);
+  deoptimize->SetRawEnvironment(deoptimize_env);
+  HInstruction* array_set =
+      new (&allocator_) HArraySet(array, index, value, Primitive::kPrimInt, /* dex_pc */ 0);
+  block->AddInstruction(array_set);
+
+  graph_->BuildDominatorTree();
+  SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get());
+  ssa_analysis.Analyze();
+
+  EXPECT_FALSE(graph_->IsDebuggable());
+  EXPECT_EQ(20u, deoptimize->GetLifetimePosition());
+  static const char* const expected[] = {
+      "ranges: { [2,23) }, uses: { 15 17 23 }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 "
+          "is_high: 0",
+      "ranges: { [4,23) }, uses: { 19 23 }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 "
+          "is_high: 0",
+      "ranges: { [6,23) }, uses: { 23 }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
+      // Environment use in HDeoptimize keeps even the non-reference argument alive.
+      "ranges: { [8,21) }, uses: { }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
+      // Environment uses keep the reference argument alive.
+      "ranges: { [10,21) }, uses: { }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0",
+  };
+  ASSERT_EQ(arraysize(expected), args.size());
+  size_t arg_index = 0u;
+  for (HInstruction* arg : args) {
+    std::ostringstream arg_dump;
+    arg->GetLiveInterval()->Dump(arg_dump);
+    EXPECT_STREQ(expected[arg_index], arg_dump.str().c_str()) << arg_index;
+    ++arg_index;
+  }
+}
+
+}  // namespace art