Fix validator SSA check: Phi can use its own value sometimes

Defer removal of a Phi's result id from the undefined-forward-reference
set until after you've scanned the arguments.  The reordering is only
significant for Phi.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/415

3 files changed, 54 insertions, 8 deletions

diff --git a/CHANGES b/CHANGES
index 6b04d8e1..fedfa0bf 100644
--- a/CHANGES
+++ b/CHANGES
@@ -4,6 +4,8 @@ v2016.5-dev 2016-09-12
  - Partial fixes:
    #359: Add Emacs helper for automatically diassembling/assembling a SPIR-V
      binary on file load/save.
+ - Fixes:
+   #415: Validator: Phi can use its own value in some cases.
 
 v2016.4 2016-09-01
  - Relicensed under Apache 2.0
diff --git a/source/validate_id.cpp b/source/validate_id.cpp
index a3e91fb3..ecc22467 100644
--- a/source/validate_id.cpp
+++ b/source/validate_id.cpp
@@ -2352,6 +2352,7 @@ function<bool(unsigned)> getCanBeForwardDeclaredFunction(SpvOp opcode) {
       break;
 
     case SpvOpFunctionCall:
+      // The Function parameter.
       out = [](unsigned index) { return index == 2; };
       break;
 
@@ -2360,16 +2361,19 @@ function<bool(unsigned)> getCanBeForwardDeclaredFunction(SpvOp opcode) {
       break;
 
     case SpvOpEnqueueKernel:
+      // The Invoke parameter.
       out = [](unsigned index) { return index == 8; };
       break;
 
     case SpvOpGetKernelNDrangeSubGroupCount:
     case SpvOpGetKernelNDrangeMaxSubGroupSize:
+      // The Invoke parameter.
       out = [](unsigned index) { return index == 3; };
       break;
 
     case SpvOpGetKernelWorkGroupSize:
     case SpvOpGetKernelPreferredWorkGroupSizeMultiple:
+      // The Invoke parameter.
       out = [](unsigned index) { return index == 2; };
       break;
 
@@ -2479,31 +2483,45 @@ spv_result_t IdPass(ValidationState_t& _,
   auto can_have_forward_declared_ids =
       getCanBeForwardDeclaredFunction(static_cast<SpvOp>(inst->opcode));
 
+  // Keep track of a result id defined by this instruction.  0 means it
+  // does not define an id.
+  uint32_t result_id = 0;
+
   for (unsigned i = 0; i < inst->num_operands; i++) {
     const spv_parsed_operand_t& operand = inst->operands[i];
     const spv_operand_type_t& type = operand.type;
-    const uint32_t* operand_ptr = inst->words + operand.offset;
+    // We only care about Id operands, which are a single word.
+    const uint32_t operand_word = inst->words[operand.offset];
 
     auto ret = SPV_ERROR_INTERNAL;
     switch (type) {
       case SPV_OPERAND_TYPE_RESULT_ID:
-        // NOTE: Multiple Id definitions are being checked by the binary parser
-        // NOTE: result Id is added *after* all of the other Ids have been
-        // checked to avoid premature use in the same instruction
-        _.RemoveIfForwardDeclared(*operand_ptr);
+        // NOTE: Multiple Id definitions are being checked by the binary parser.
+        //
+        // Defer undefined-forward-reference removal until after we've analyzed
+        // the remaining operands to this instruction.  Deferral only matters
+        // for
+        // OpPhi since it's the only case where it defines its own forward
+        // reference.  Other instructions that can have forward references
+        // either don't define a value or the forward reference is to a function
+        // Id (and hence defined outside of a function body).
+        result_id = operand_word;
+        // NOTE: The result Id is added (in RegisterInstruction) *after* all of
+        // the other Ids have been checked to avoid premature use in the same
+        // instruction.
         ret = SPV_SUCCESS;
         break;
       case SPV_OPERAND_TYPE_ID:
       case SPV_OPERAND_TYPE_TYPE_ID:
       case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
       case SPV_OPERAND_TYPE_SCOPE_ID:
-        if (_.IsDefinedId(*operand_ptr)) {
+        if (_.IsDefinedId(operand_word)) {
           ret = SPV_SUCCESS;
         } else if (can_have_forward_declared_ids(i)) {
-          ret = _.ForwardDeclareId(*operand_ptr);
+          ret = _.ForwardDeclareId(operand_word);
         } else {
           ret = _.diag(SPV_ERROR_INVALID_ID) << "ID "
-                                             << _.getIdName(*operand_ptr)
+                                             << _.getIdName(operand_word)
                                              << " has not been defined";
         }
         break;
@@ -2515,6 +2533,9 @@ spv_result_t IdPass(ValidationState_t& _,
       return ret;
     }
   }
+  if (result_id) {
+    _.RemoveIfForwardDeclared(result_id);
+  }
   _.RegisterInstruction(*inst);
   return SPV_SUCCESS;
 }
diff --git a/test/val/Validate.SSA.cpp b/test/val/Validate.SSA.cpp
index 9b748879..d37b6461 100644
--- a/test/val/Validate.SSA.cpp
+++ b/test/val/Validate.SSA.cpp
@@ -1185,6 +1185,29 @@ TEST_F(ValidateSSA, PhiUseMayComeFromNonDominatingBlockGood) {
   ASSERT_EQ(SPV_SUCCESS, ValidateInstructions()) << getDiagnosticString();
 }
 
+TEST_F(ValidateSSA, PhiUsesItsOwnDefinitionGood) {
+  // See https://github.com/KhronosGroup/SPIRV-Tools/issues/415
+  //
+  // Non-phi instructions can't use their own definitions, as
+  // already checked in test DominateUsageSameInstructionBad.
+  string str = kHeader + "OpName %loop \"loop\"\n" +
+               "OpName %value \"value\"\n" + kBasicTypes +
+               R"(
+%func        = OpFunction %voidt None %vfunct
+%entry       = OpLabel
+               OpBranch %loop
+
+%loop        = OpLabel
+%value       = OpPhi %boolt %false %entry %value %loop
+               OpBranch %loop
+
+               OpFunctionEnd
+)";
+
+  CompileSuccessfully(str);
+  ASSERT_EQ(SPV_SUCCESS, ValidateInstructions()) << getDiagnosticString();
+}
+
 TEST_F(ValidateSSA, PhiVariableDefNotDominatedByParentBlockBad) {
   string str = kHeader + "OpName %if_true \"if_true\"\n" +
                "OpName %if_false \"if_false\"\n" + "OpName %exit \"exit\"\n" +