Add loop- and phi-related checks in the optimizing compiler.

- Ensure the pre-header block is first in the list of
  predecessors of a loop header.
- Ensure the loop header has only two predecessors and that
  only the second one is the back edge.
- Ensure there is only one back edge per loop.
- Ensure the first input of a phi is not itself.
- Ensure the number of phi inputs is the same as the number
  of its predecessors.
- Ensure phi input at index I either comes from the Ith
  predecessor or from a block that dominates this
  predecessor.

Change-Id: I4db5c68cfbc9b74d2d03125753d0143ece625378

4 files changed, 110 insertions, 7 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index ad9ed0c..b05090b 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -158,6 +158,60 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
       }
     }
   }
+
+  if (block->IsLoopHeader()) {
+    CheckLoop(block);
+  }
+}
+
+void SSAChecker::CheckLoop(HBasicBlock* loop_header) {
+  int id = loop_header->GetBlockId();
+
+  // Ensure the pre-header block is first in the list of
+  // predecessors of a loop header.
+  if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
+    std::stringstream error;
+    error << "Loop pre-header is not the first predecessor of the loop header "
+          << id << ".";
+    errors_.Insert(error.str());
+  }
+
+  // Ensure the loop header has only two predecessors and that only the
+  // second one is a back edge.
+  if (loop_header->GetPredecessors().Size() < 2) {
+    std::stringstream error;
+    error << "Loop header " << id << " has less than two predecessors.";
+    errors_.Insert(error.str());
+  } else if (loop_header->GetPredecessors().Size() > 2) {
+    std::stringstream error;
+    error << "Loop header " << id << " has more than two predecessors.";
+    errors_.Insert(error.str());
+  } else {
+    HLoopInformation* loop_information = loop_header->GetLoopInformation();
+    HBasicBlock* first_predecessor = loop_header->GetPredecessors().Get(0);
+    if (loop_information->IsBackEdge(first_predecessor)) {
+      std::stringstream error;
+      error << "First predecessor of loop header " << id << " is a back edge.";
+      errors_.Insert(error.str());
+    }
+    HBasicBlock* second_predecessor = loop_header->GetPredecessors().Get(1);
+    if (!loop_information->IsBackEdge(second_predecessor)) {
+      std::stringstream error;
+      error << "Second predecessor of loop header " << id
+            << " is not a back edge.";
+      errors_.Insert(error.str());
+    }
+  }
+
+  // Ensure there is only one back edge per loop.
+  size_t num_back_edges =
+    loop_header->GetLoopInformation()->GetBackEdges().Size();
+  if (num_back_edges != 1) {
+      std::stringstream error;
+      error << "Loop defined by header " << id << " has "
+            << num_back_edges << " back edge(s).";
+      errors_.Insert(error.str());
+  }
 }
 
 void SSAChecker::VisitInstruction(HInstruction* instruction) {
@@ -180,4 +234,48 @@ void SSAChecker::VisitInstruction(HInstruction* instruction) {
   }
 }
 
+void SSAChecker::VisitPhi(HPhi* phi) {
+  VisitInstruction(phi);
+
+  // Ensure the first input of a phi is not itself.
+  if (phi->InputAt(0) == phi) {
+      std::stringstream error;
+      error << "Loop phi " << phi->GetId()
+            << " in block " << phi->GetBlock()->GetBlockId()
+            << " is its own first input.";
+      errors_.Insert(error.str());
+  }
+
+  // Ensure the number of phi inputs is the same as the number of
+  // its predecessors.
+  const GrowableArray<HBasicBlock*>& predecessors =
+    phi->GetBlock()->GetPredecessors();
+  if (phi->InputCount() != predecessors.Size()) {
+    std::stringstream error;
+    error << "Phi " << phi->GetId()
+          << " in block " << phi->GetBlock()->GetBlockId()
+          << " has " << phi->InputCount() << " inputs, but block "
+          << phi->GetBlock()->GetBlockId() << " has "
+          << predecessors.Size() << " predecessors.";
+    errors_.Insert(error.str());
+  } else {
+    // Ensure phi input at index I either comes from the Ith
+    // predecessor or from a block that dominates this predecessor.
+    for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
+      HInstruction* input = phi->InputAt(i);
+      HBasicBlock* predecessor = predecessors.Get(i);
+      if (!(input->GetBlock() == predecessor
+            || input->GetBlock()->Dominates(predecessor))) {
+        std::stringstream error;
+        error << "Input " << input->GetId() << " at index " << i
+              << " of phi " << phi->GetId()
+              << " from block " << phi->GetBlock()->GetBlockId()
+              << " is not defined in predecessor number " << i
+              << " nor in a block dominating it.";
+        errors_.Insert(error.str());
+      }
+    }
+  }
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 8ddd399..34a770b 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -67,9 +67,12 @@ class SSAChecker : public GraphChecker {
 
   // Perform SSA form checks on `block`.
   virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
+  // Loop-related checks from block `loop_header`.
+  void CheckLoop(HBasicBlock* loop_header);
 
-  // Perform SSA form checks on `instruction`.
+  // Perform SSA form checks on instructions.
   virtual void VisitInstruction(HInstruction* instruction) OVERRIDE;
+  virtual void VisitPhi(HPhi* phi) OVERRIDE;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(SSAChecker);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index af173c8..6b21326 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -383,6 +383,12 @@ class HBasicBlock : public ArenaObject {
     return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
   }
 
+  bool IsLoopPreHeaderFirstPredecessor() const {
+    DCHECK(IsLoopHeader());
+    DCHECK(!GetPredecessors().IsEmpty());
+    return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader();
+  }
+
   HLoopInformation* GetLoopInformation() const {
     return loop_information_;
   }
@@ -606,7 +612,7 @@ class HInstruction : public ArenaObject {
   bool IsInLoop() const { return block_->IsInLoop(); }
   bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
 
-  virtual size_t InputCount() const  = 0;
+  virtual size_t InputCount() const = 0;
   virtual HInstruction* InputAt(size_t i) const = 0;
 
   virtual void Accept(HGraphVisitor* visitor) = 0;
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index d541a62..e02a182 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -83,10 +83,6 @@ void SsaDeadPhiElimination::Run() {
   }
 }
 
-static bool LoopPreHeaderIsFirstPredecessor(HBasicBlock* block) {
-  return block->GetPredecessors().Get(0) == block->GetLoopInformation()->GetPreHeader();
-}
-
 void SsaRedundantPhiElimination::Run() {
   // Add all phis in the worklist.
   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
@@ -109,7 +105,7 @@ void SsaRedundantPhiElimination::Run() {
     // A loop phi cannot have itself as the first phi. Note that this
     // check relies on our simplification pass ensuring the pre-header
     // block is first in the list of predecessors of the loop header.
-    DCHECK(!phi->IsLoopHeaderPhi() || LoopPreHeaderIsFirstPredecessor(phi->GetBlock()));
+    DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor());
     DCHECK_NE(phi, candidate);
 
     for (size_t i = 1; i < phi->InputCount(); ++i) {