Dissociate uses with environment uses.

They are most of the times in the way when iterating. They
also complicate the logic of (future) back edge uses.

Change-Id: I152595d9913073fe901b267ca623fa0fe7432484

3 files changed, 62 insertions, 38 deletions

diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 0fdf051957..a8d006f104 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1455,6 +1455,7 @@ void RegisterAllocator::ConnectSiblings(LiveInterval* interval) {
                         : Location::StackSlot(interval->GetParent()->GetSpillSlot()));
   }
   UsePosition* use = current->GetFirstUse();
+  UsePosition* env_use = current->GetFirstEnvironmentUse();
 
   // Walk over all siblings, updating locations of use positions, and
   // connecting them when they are adjacent.
@@ -1466,32 +1467,39 @@ void RegisterAllocator::ConnectSiblings(LiveInterval* interval) {
 
     LiveRange* range = current->GetFirstRange();
     while (range != nullptr) {
-      while (use != nullptr && use->GetPosition() < range->GetStart()) {
-        DCHECK(use->GetIsEnvironment());
-        use = use->GetNext();
-      }
+      DCHECK(use == nullptr || use->GetPosition() >= range->GetStart());
       while (use != nullptr && use->GetPosition() <= range->GetEnd()) {
+        DCHECK(!use->GetIsEnvironment());
         DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd()));
         LocationSummary* locations = use->GetUser()->GetLocations();
-        if (use->GetIsEnvironment()) {
-          locations->SetEnvironmentAt(use->GetInputIndex(), source);
-        } else {
-          Location expected_location = locations->InAt(use->GetInputIndex());
-          // The expected (actual) location may be invalid in case the input is unused. Currently
-          // this only happens for intrinsics.
-          if (expected_location.IsValid()) {
-            if (expected_location.IsUnallocated()) {
-              locations->SetInAt(use->GetInputIndex(), source);
-            } else if (!expected_location.IsConstant()) {
-              AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location);
-            }
-          } else {
-            DCHECK(use->GetUser()->IsInvoke());
-            DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
+        Location expected_location = locations->InAt(use->GetInputIndex());
+        // The expected (actual) location may be invalid in case the input is unused. Currently
+        // this only happens for intrinsics.
+        if (expected_location.IsValid()) {
+          if (expected_location.IsUnallocated()) {
+            locations->SetInAt(use->GetInputIndex(), source);
+          } else if (!expected_location.IsConstant()) {
+            AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location);
           }
+        } else {
+          DCHECK(use->GetUser()->IsInvoke());
+          DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
         }
         use = use->GetNext();
       }
+
+      // Walk over the environment uses, and update their locations.
+      while (env_use != nullptr && env_use->GetPosition() < range->GetStart()) {
+        env_use = env_use->GetNext();
+      }
+
+      while (env_use != nullptr && env_use->GetPosition() <= range->GetEnd()) {
+        DCHECK(current->CoversSlow(env_use->GetPosition()) || (env_use->GetPosition() == range->GetEnd()));
+        LocationSummary* locations = env_use->GetUser()->GetLocations();
+        locations->SetEnvironmentAt(env_use->GetInputIndex(), source);
+        env_use = env_use->GetNext();
+      }
+
       range = range->GetNext();
     }
 
@@ -1553,14 +1561,7 @@ void RegisterAllocator::ConnectSiblings(LiveInterval* interval) {
     current = next_sibling;
   } while (current != nullptr);
 
-  if (kIsDebugBuild) {
-    // Following uses can only be environment uses. The location for
-    // these environments will be none.
-    while (use != nullptr) {
-      DCHECK(use->GetIsEnvironment());
-      use = use->GetNext();
-    }
-  }
+  DCHECK(use == nullptr);
 }
 
 void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index ea0e7c3712..b674f746b6 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -341,7 +341,7 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until) const {
   size_t end = GetEnd();
   while (use != nullptr && use->GetPosition() <= end) {
     size_t use_position = use->GetPosition();
-    if (use_position >= start && !use->GetIsEnvironment()) {
+    if (use_position >= start) {
       HInstruction* user = use->GetUser();
       size_t input_index = use->GetInputIndex();
       if (user->IsPhi()) {
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 97254edb5e..b95276afd7 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -219,6 +219,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
   void AddTempUse(HInstruction* instruction, size_t temp_index) {
     DCHECK(IsTemp());
     DCHECK(first_use_ == nullptr) << "A temporary can only have one user";
+    DCHECK(first_env_use_ == nullptr) << "A temporary cannot have environment user";
     size_t position = instruction->GetLifetimePosition();
     first_use_ = new (allocator_) UsePosition(
         instruction, temp_index, /* is_environment */ false, position, first_use_);
@@ -265,8 +266,13 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
       return;
     }
 
-    first_use_ = new (allocator_) UsePosition(
-        instruction, input_index, is_environment, position, first_use_);
+    if (is_environment) {
+      first_env_use_ = new (allocator_) UsePosition(
+          instruction, input_index, is_environment, position, first_env_use_);
+    } else {
+      first_use_ = new (allocator_) UsePosition(
+          instruction, input_index, is_environment, position, first_use_);
+    }
 
     if (is_environment && !keep_alive) {
       // If this environment use does not keep the instruction live, it does not
@@ -477,7 +483,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
     size_t end = GetEnd();
     while (use != nullptr && use->GetPosition() <= end) {
       size_t use_position = use->GetPosition();
-      if (use_position > position && !use->GetIsEnvironment()) {
+      if (use_position > position) {
         Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
         if (location.IsUnallocated()
             && (location.GetPolicy() == Location::kRequiresRegister
@@ -508,12 +514,10 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
     UsePosition* use = first_use_;
     size_t end = GetEnd();
     while (use != nullptr && use->GetPosition() <= end) {
-      if (!use->GetIsEnvironment()) {
-        Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
-        size_t use_position = use->GetPosition();
-        if (use_position > position && location.IsValid()) {
-          return use_position;
-        }
+      Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
+      size_t use_position = use->GetPosition();
+      if (use_position > position && location.IsValid()) {
+        return use_position;
       }
       use = use->GetNext();
     }
@@ -524,6 +528,10 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
     return first_use_;
   }
 
+  UsePosition* GetFirstEnvironmentUse() const {
+    return first_env_use_;
+  }
+
   Primitive::Type GetType() const {
     return type_;
   }
@@ -577,6 +585,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
     new_interval->parent_ = parent_;
 
     new_interval->first_use_ = first_use_;
+    new_interval->first_env_use_ = first_env_use_;
     LiveRange* current = first_range_;
     LiveRange* previous = nullptr;
     // Iterate over the ranges, and either find a range that covers this position, or
@@ -655,10 +664,18 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
         stream << " ";
       } while ((use = use->GetNext()) != nullptr);
     }
+    stream << "}, {";
+    use = first_env_use_;
+    if (use != nullptr) {
+      do {
+        use->Dump(stream);
+        stream << " ";
+      } while ((use = use->GetNext()) != nullptr);
+    }
     stream << "}";
     stream << " is_fixed: " << is_fixed_ << ", is_split: " << IsSplit();
-    stream << " is_high: " << IsHighInterval();
     stream << " is_low: " << IsLowInterval();
+    stream << " is_high: " << IsHighInterval();
   }
 
   LiveInterval* GetNextSibling() const { return next_sibling_; }
@@ -754,6 +771,10 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
     if (first_use_ != nullptr) {
       high_or_low_interval_->first_use_ = first_use_->Dup(allocator_);
     }
+
+    if (first_env_use_ != nullptr) {
+      high_or_low_interval_->first_env_use_ = first_env_use_->Dup(allocator_);
+    }
   }
 
   // Returns whether an interval, when it is non-split, is using
@@ -851,6 +872,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
         first_safepoint_(nullptr),
         last_safepoint_(nullptr),
         first_use_(nullptr),
+        first_env_use_(nullptr),
         type_(type),
         next_sibling_(nullptr),
         parent_(this),
@@ -905,6 +927,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
 
   // Uses of this interval. Note that this linked list is shared amongst siblings.
   UsePosition* first_use_;
+  UsePosition* first_env_use_;
 
   // The instruction type this interval corresponds to.
   const Primitive::Type type_;