Fix user-build on fugu.

Calling Delete on an array shifts the elements, so when iterating
over inactives and removing entries we need to decrement for
the found interval, but also its potential other half. The code
used to not decrement for the other half

Change-Id: Idcb1533643c11a37ed4f459fe88aaef208a4bfd6

6 files changed, 131 insertions, 39 deletions

diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index cecc210..efb98f0 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -851,6 +851,23 @@ bool RegisterAllocator::TrySplitNonPairOrUnalignedPairIntervalAt(size_t position
   return false;
 }
 
+bool RegisterAllocator::PotentiallyRemoveOtherHalf(LiveInterval* interval,
+                                                   GrowableArray<LiveInterval*>* intervals,
+                                                   size_t index) {
+  if (interval->IsLowInterval()) {
+    DCHECK_EQ(intervals->Get(index), interval->GetHighInterval());
+    intervals->DeleteAt(index);
+    return true;
+  } else if (interval->IsHighInterval()) {
+    DCHECK_GT(index, 0u);
+    DCHECK_EQ(intervals->Get(index - 1), interval->GetLowInterval());
+    intervals->DeleteAt(index - 1);
+    return true;
+  } else {
+    return false;
+  }
+}
+
 // Find the register that is used the last, and spill the interval
 // that holds it. If the first use of `current` is after that register
 // we spill `current` instead.
@@ -974,33 +991,17 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
       if (active->GetRegister() == reg) {
         DCHECK(!active->IsFixed());
         LiveInterval* split = Split(active, current->GetStart());
-        active_.DeleteAt(i);
         if (split != active) {
           handled_.Add(active);
         }
+        active_.DeleteAt(i);
+        PotentiallyRemoveOtherHalf(active, &active_, i);
         AddSorted(unhandled_, split);
-
-        if (active->IsLowInterval() || active->IsHighInterval()) {
-          LiveInterval* other_half = active->IsLowInterval()
-              ? active->GetHighInterval()
-              : active->GetLowInterval();
-          // We also need to remove the other half from the list of actives.
-          bool found = false;
-          for (size_t j = 0; j < active_.Size(); ++j) {
-            if (active_.Get(j) == other_half) {
-              found = true;
-              active_.DeleteAt(j);
-              handled_.Add(other_half);
-              break;
-            }
-          }
-          DCHECK(found);
-        }
         break;
       }
     }
 
-    for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
+    for (size_t i = 0; i < inactive_.Size(); ++i) {
       LiveInterval* inactive = inactive_.Get(i);
       if (inactive->GetRegister() == reg) {
         if (!current->IsSplit() && !inactive->IsFixed()) {
@@ -1024,29 +1025,14 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
             // If it's inactive, it must start before the current interval.
             DCHECK_NE(split, inactive);
             inactive_.DeleteAt(i);
+            if (PotentiallyRemoveOtherHalf(inactive, &inactive_, i) && inactive->IsHighInterval()) {
+              // We have removed an entry prior to `inactive`. So we need to decrement.
+              --i;
+            }
+            // Decrement because we have removed `inactive` from the list.
             --i;
-            --e;
             handled_.Add(inactive);
             AddSorted(unhandled_, split);
-
-            if (inactive->IsLowInterval() || inactive->IsHighInterval()) {
-              LiveInterval* other_half = inactive->IsLowInterval()
-                  ? inactive->GetHighInterval()
-                  : inactive->GetLowInterval();
-
-              // We also need to remove the other half from the list of inactives.
-              bool found = false;
-              for (size_t j = 0; j < inactive_.Size(); ++j) {
-                if (inactive_.Get(j) == other_half) {
-                  found = true;
-                  inactive_.DeleteAt(j);
-                  --e;
-                  handled_.Add(other_half);
-                  break;
-                }
-              }
-              DCHECK(found);
-            }
           }
         }
       }
diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h
index fcc6112..717be75 100644
--- a/compiler/optimizing/register_allocator.h
+++ b/compiler/optimizing/register_allocator.h
@@ -144,6 +144,13 @@ class RegisterAllocator {
                                                 size_t first_register_use,
                                                 size_t* next_use);
 
+  // If `interval` has another half, remove it from the list of `intervals`.
+  // `index` holds the index at which `interval` is in `intervals`.
+  // Returns whether there is another half.
+  bool PotentiallyRemoveOtherHalf(LiveInterval* interval,
+                                  GrowableArray<LiveInterval*>* intervals,
+                                  size_t index);
+
   ArenaAllocator* const allocator_;
   CodeGenerator* const codegen_;
   const SsaLivenessAnalysis& liveness_;
diff --git a/test/467-regalloc-pair/expected.txt b/test/467-regalloc-pair/expected.txt
new file mode 100644
index 0000000..da39d9d
--- /dev/null
+++ b/test/467-regalloc-pair/expected.txt
@@ -0,0 +1 @@
+In interface
diff --git a/test/467-regalloc-pair/info.txt b/test/467-regalloc-pair/info.txt
new file mode 100644
index 0000000..882a29c
--- /dev/null
+++ b/test/467-regalloc-pair/info.txt
@@ -0,0 +1,2 @@
+Regression test for optimizing's register allocator
+that used to trip when compiling TestCase.testCase on x86.
diff --git a/test/467-regalloc-pair/smali/TestCase.smali b/test/467-regalloc-pair/smali/TestCase.smali
new file mode 100644
index 0000000..a3101fe
--- /dev/null
+++ b/test/467-regalloc-pair/smali/TestCase.smali
@@ -0,0 +1,59 @@
+# Copyright (C) 2015 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.
+
+.class public LTestCase;
+
+.super Ljava/lang/Object;
+
+.method public static testCase([BLMain;)V
+    .registers 12
+    const/4 v2, 0
+    array-length v0, v10
+    div-int/lit8 v0, v0, 7
+    invoke-static {v2, v0}, Ljava/lang/Math;->max(II)I
+    move-result v7
+    move v6, v2
+    move v3, v2
+    :label5
+    if-ge v6, v7, :label1
+    const-wide/16 v0, 0
+    move-wide v4, v0
+    move v1, v2
+    move v0, v3
+    :label4
+    const/4 v3, 6
+    if-ge v1, v3, :label2
+    const/16 v3, 8
+    shl-long/2addr v4, v3
+    add-int/lit8 v3, v0, 1
+    aget-byte v0, v10, v0
+    if-gez v0, :label3
+    add-int/lit16 v0, v0, 256
+    :label3
+    int-to-long v8, v0
+    or-long/2addr v4, v8
+    add-int/lit8 v0, v1, 1
+    move v1, v0
+    move v0, v3
+    goto :label4
+    :label2
+    add-int/lit8 v3, v0, 1
+    aget-byte v0, v10, v0
+    invoke-interface {v11, v4, v5, v0}, LItf;->invokeInterface(JI)V
+    add-int/lit8 v0, v6, 1
+    move v6, v0
+    goto :label5
+    :label1
+    return-void
+.end method
diff --git a/test/467-regalloc-pair/src/Main.java b/test/467-regalloc-pair/src/Main.java
new file mode 100644
index 0000000..aac07fd
--- /dev/null
+++ b/test/467-regalloc-pair/src/Main.java
@@ -0,0 +1,37 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+import java.lang.reflect.Method;
+
+interface Itf {
+  public void invokeInterface(long l, int i);
+}
+
+public class Main implements Itf {
+
+  // Workaround for b/18051191.
+  class InnerClass {}
+
+  public static void main(String[] args) throws Exception {
+    Class<?> c = Class.forName("TestCase");
+    Method m = c.getMethod("testCase", byte[].class, Main.class);
+    m.invoke(null, new byte[] { 0, 1, 2, 3, 4, 5, 6, 7 }, new Main());
+  }
+
+  public void invokeInterface(long l, int i) {
+    System.out.println("In interface");
+  }
+}