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
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 @@
}
}
}
+
+ 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::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 @@
// 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 @@
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 @@
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 @@
}
}
-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 @@
// 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) {