Subzero: Validate phi instructions after CFG construction. It checks that each phi label corresponds to an incoming edge, and that each incoming edge has a corresponding phi label. It does not check that duplicate incoming edges get the same phi value. Performance impact is minimal (~0.2%) despite the O(N^2) implementation. BUG= https://code.google.com/p/nativeclient/issues/detail?id=4304 R=jpp@chromium.org Review URL: https://codereview.chromium.org/1351433002 .

diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 57f216f..ed60abb 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp

@@ -232,6 +232,10 @@
     }
   }
   Nodes.resize(Dest);
+
+  TimerMarker T(TimerStack::TT_phiValidation, this);
+  for (CfgNode *Node : Nodes)
+    Node->validatePhis();
 }
 
 void Cfg::renumberInstructions() {

diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index cb8d97e..0ccc6ea 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp

@@ -80,6 +80,46 @@
   OutEdges = Insts.rbegin()->getTerminatorEdges();
 }
 
+// Validate each Phi instruction in the node with respect to control flow.  For
+// every phi argument, its label must appear in the predecessor list.  For each
+// predecessor, there must be a phi argument with that label.  We don't check
+// that phi arguments with the same label have the same value.
+void CfgNode::validatePhis() {
+  for (Inst &Instr : Phis) {
+    auto *Phi = llvm::cast<InstPhi>(&Instr);
+    // We do a simple O(N^2) algorithm to check for consistency.  Even so, it
+    // shows up as only about 0.2% of the total translation time.  But if
+    // necessary, we could improve the complexity by using a hash table to count
+    // how many times each node is referenced in the Phi instruction, and how
+    // many times each node is referenced in the incoming edge list, and compare
+    // the two for equality.
+    for (SizeT i = 0; i < Phi->getSrcSize(); ++i) {
+      CfgNode *Label = Phi->getLabel(i);
+      bool Found = false;
+      for (CfgNode *InNode : getInEdges()) {
+        if (InNode == Label) {
+          Found = true;
+          break;
+        }
+      }
+      if (!Found)
+        llvm::report_fatal_error("Phi error: label for bad incoming edge");
+    }
+    for (CfgNode *InNode : getInEdges()) {
+      bool Found = false;
+      for (SizeT i = 0; i < Phi->getSrcSize(); ++i) {
+        CfgNode *Label = Phi->getLabel(i);
+        if (InNode == Label) {
+          Found = true;
+          break;
+        }
+      }
+      if (!Found)
+        llvm::report_fatal_error("Phi error: missing label for incoming edge");
+    }
+  }
+}
+
 // This does part 1 of Phi lowering, by creating a new dest variable
 // for each Phi instruction, replacing the Phi instruction's dest with
 // that variable, and adding an explicit assignment of the old dest to

diff --git a/src/IceCfgNode.h b/src/IceCfgNode.h
index 63f2c62..a4744db 100644
--- a/src/IceCfgNode.h
+++ b/src/IceCfgNode.h

@@ -90,6 +90,7 @@
   CfgNode *splitIncomingEdge(CfgNode *Pred, SizeT InEdgeIndex);
   /// @}
 
+  void validatePhis();
   void placePhiLoads();
   void placePhiStores();
   void deletePhis();

diff --git a/src/IceTimerTree.def b/src/IceTimerTree.def
index 9bcc53c..6db9fbc 100644
--- a/src/IceTimerTree.def
+++ b/src/IceTimerTree.def

@@ -46,6 +46,7 @@
   X(parseModule)               \
   X(parseModuleValuesymtabs)   \
   X(parseTypes)                \
+  X(phiValidation)             \
   X(placePhiLoads)             \
   X(placePhiStores)            \
   X(regAlloc)                  \

diff --git a/tests_lit/llvm2ice_tests/Input/phi-invalid.tbc b/tests_lit/llvm2ice_tests/Input/phi-invalid.tbc
new file mode 100644
index 0000000..bb9d59e
--- /dev/null
+++ b/tests_lit/llvm2ice_tests/Input/phi-invalid.tbc

@@ -0,0 +1,55 @@
+65535,8,2;
+1,1;
+65535,17,2;
+1,5;
+7,32;
+2;
+7,1;
+21,0,1;
+21,0,1,0;
+65534;
+8,3,0,0,0;
+8,4,0,0,0;
+65535,19,2;
+5,0;
+65534;
+65535,14,2;
+1,0,76,111,111,112,67,97,114,114,105,101,100,68,101,112;
+1,1,66,97,99,107,66,114,97,110,99,104;
+65534;
+65535,12,2;
+1,2;
+65535,11,2;
+1,0;
+4,2;
+4,4;
+65534;
+2,2,1,0;
+11,1;
+43,6,0;
+16,0,2,0,3,0;
+2,1,4,0;
+11,1;
+65534;
+65535,12,2;
+1,7;
+65535,11,2;
+1,2;
+4,3;
+65534;
+11,4;
+43,7,0;
+2,2,4294967293,0;
+11,6;
+43,8,0;
+2,3,4294967293,0;
+11,6;
+2,4,4294967295,0;
+11,6;
+2,5,5,0;
+11,1,5,5;
+2,1,6,0;
+11,2,3,6;
+10;
+65534;
+65534;

diff --git a/tests_lit/llvm2ice_tests/phi_invalid.test b/tests_lit/llvm2ice_tests/phi_invalid.test
new file mode 100644
index 0000000..198de4c
--- /dev/null
+++ b/tests_lit/llvm2ice_tests/phi_invalid.test

@@ -0,0 +1,7 @@
+; Test that a bad phi instruction is caught.
+; https://code.google.com/p/nativeclient/issues/detail?id=4304
+
+RUN: %p2i --expect-fail --tbc -i %p/Input/phi-invalid.tbc --insts 2>&1 \
+RUN:        | FileCheck --check-prefix=BADPHI %s
+
+; BADPHI: Phi error: