Update the remaining input index of phis after deleting an input.

bug:20715803
bug:20690906

Change-Id: Iaf08f0c30d629e766be2b04815dc3e38b6e7ff35

6 files changed, 95 insertions, 4 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index dc3124b35..8ea8f3cd7 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -170,7 +170,8 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
     }
   }
 
-  // Ensure the uses of `instruction` are defined in a block of the graph.
+  // Ensure the uses of `instruction` are defined in a block of the graph,
+  // and the entry in the use list is consistent.
   for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
        !use_it.Done(); use_it.Advance()) {
     HInstruction* use = use_it.Current()->GetUser();
@@ -184,6 +185,27 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
                             use->GetId(),
                             instruction->GetId()));
     }
+    size_t use_index = use_it.Current()->GetIndex();
+    if ((use_index >= use->InputCount()) || (use->InputAt(use_index) != instruction)) {
+      AddError(StringPrintf("User %s:%d of instruction %d has a wrong "
+                            "UseListNode index.",
+                            use->DebugName(),
+                            use->GetId(),
+                            instruction->GetId()));
+    }
+  }
+
+  // Ensure the environment uses entries are consistent.
+  for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses());
+       !use_it.Done(); use_it.Advance()) {
+    HEnvironment* use = use_it.Current()->GetUser();
+    size_t use_index = use_it.Current()->GetIndex();
+    if ((use_index >= use->Size()) || (use->GetInstructionAt(use_index) != instruction)) {
+      AddError(StringPrintf("Environment user of %s:%d has a wrong "
+                            "UseListNode index.",
+                            instruction->DebugName(),
+                            instruction->GetId()));
+    }
   }
 
   // Ensure 'instruction' has pointers to its inputs' use entries.
@@ -191,7 +213,11 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
     HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i);
     HInstruction* input = input_record.GetInstruction();
     HUseListNode<HInstruction*>* use_node = input_record.GetUseNode();
-    if (use_node == nullptr || !input->GetUses().Contains(use_node)) {
+    size_t use_index = use_node->GetIndex();
+    if ((use_node == nullptr)
+        || !input->GetUses().Contains(use_node)
+        || (use_index >= e)
+        || (use_index != i)) {
       AddError(StringPrintf("Instruction %s:%d has an invalid pointer to use entry "
                             "at input %u (%s:%d).",
                             instruction->DebugName(),
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index f07f4c759..d3ee77094 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -712,6 +712,9 @@ void HPhi::AddInput(HInstruction* input) {
 void HPhi::RemoveInputAt(size_t index) {
   RemoveAsUserOfInput(index);
   inputs_.DeleteAt(index);
+  for (size_t i = index, e = InputCount(); i < e; ++i) {
+    InputRecordAt(i).GetUseNode()->SetIndex(i);
+  }
 }
 
 #define DEFINE_ACCEPT(name, super)                                             \
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 50eecffc5..63f3c95c7 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -850,13 +850,14 @@ class HUseListNode : public ArenaObject<kArenaAllocMisc> {
   HUseListNode* GetNext() const { return next_; }
   T GetUser() const { return user_; }
   size_t GetIndex() const { return index_; }
+  void SetIndex(size_t index) { index_ = index; }
 
  private:
   HUseListNode(T user, size_t index)
       : user_(user), index_(index), prev_(nullptr), next_(nullptr) {}
 
   T const user_;
-  const size_t index_;
+  size_t index_;
   HUseListNode<T>* prev_;
   HUseListNode<T>* next_;
 
@@ -1090,7 +1091,7 @@ class HEnvironment : public ArenaObject<kArenaAllocMisc> {
 
   GrowableArray<HUserRecord<HEnvironment*> > vregs_;
 
-  friend HInstruction;
+  friend class HInstruction;
 
   DISALLOW_COPY_AND_ASSIGN(HEnvironment);
 };
diff --git a/test/483-dce-block/expected.txt b/test/483-dce-block/expected.txt
new file mode 100644
index 000000000..ef4862580
--- /dev/null
+++ b/test/483-dce-block/expected.txt
@@ -0,0 +1 @@
+class Main
diff --git a/test/483-dce-block/info.txt b/test/483-dce-block/info.txt
new file mode 100644
index 000000000..3db88ab22
--- /dev/null
+++ b/test/483-dce-block/info.txt
@@ -0,0 +1,2 @@
+Regression test for optimizing that used to crash
+compiling the `foo` method.
diff --git a/test/483-dce-block/src/Main.java b/test/483-dce-block/src/Main.java
new file mode 100644
index 000000000..2f66a74d5
--- /dev/null
+++ b/test/483-dce-block/src/Main.java
@@ -0,0 +1,58 @@
+/*
+ * 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.
+ */
+
+public class Main {
+  public static void foo(Object o, int a) {
+    Object result = null;
+    if (o instanceof Main) {
+      // The compiler optimizes the type of `o` by introducing
+      // a `HBoundType` in this block.
+      while (a != 3) {
+        if (a == 2) {
+          a++;
+          result = o;
+          continue;
+        } else if (willInline()) {
+          // This block will be detected as dead after inlining.
+          result = new Object();
+          continue;
+        }
+        result = new Object();
+      }
+      // The compiler produces a phi at the back edge for `result`.
+      // Before dead block elimination, the phi has three inputs:
+      // result = (new Object(), new Object(), HBoundType)
+      //
+      // After dead block elimination, the phi has now two inputs:
+      // result = (new Object(), HBoundType)
+      //
+      // Our internal data structure for linking users and inputs expect
+      // the input index stored in that data structure to be the index
+      // in the inputs array. So the index before dead block elimination
+      // of the `HBoundType` would be 2. Dead block elimination must update
+      // that index to be 1.
+    }
+    System.out.println(result.getClass());
+  }
+
+  public static boolean willInline() {
+    return false;
+  }
+
+  public static void main(String[] args) {
+    foo(new Main(), 2);
+  }
+}