[spirv-reader] Support OpPhi

For each OpPhi, make a variable to carry values from predecessor blocks
to the OpPhi.  Declare the variable at the smallest scope enclosing all
the predecessor blocks (where we write to it), and the OpPhi (where we
read from it).

Bug: tint:3
Change-Id: I7898b4b903d9ee1a25a7466e3c5aaf6840550e2d
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/24181
Reviewed-by: dan sinclair <dsinclair@google.com>
diff --git a/src/reader/spirv/function.cc b/src/reader/spirv/function.cc
index 1fe4614..f8360b9 100644
--- a/src/reader/spirv/function.cc
+++ b/src/reader/spirv/function.cc
@@ -412,8 +412,9 @@
 BlockInfo::~BlockInfo() = default;
 
 DefInfo::DefInfo(const spvtools::opt::Instruction& def_inst,
-                 uint32_t the_block_pos)
-    : inst(def_inst), block_pos(the_block_pos) {}
+                 uint32_t the_block_pos,
+                 size_t the_index)
+    : inst(def_inst), block_pos(the_block_pos), index(the_index) {}
 
 DefInfo::~DefInfo() = default;
 
@@ -628,7 +629,6 @@
     return false;
   }
 
-  // TODO(dneto): register phis
   RegisterValuesNeedingNamedOrHoistedDefinition();
 
   if (!EmitFunctionVariables()) {
@@ -2367,8 +2367,18 @@
     return true;
   }
 
-  // Emit declarations of hoisted variables.
-  for (auto id : block_info.hoisted_ids) {
+  // Returns the given list of local definition IDs, sorted by their index.
+  auto sorted_by_index = [this](const std::vector<uint32_t>& ids) {
+    auto sorted = ids;
+    std::stable_sort(sorted.begin(), sorted.end(),
+                     [this](const uint32_t lhs, const uint32_t rhs) {
+                       return GetDefInfo(lhs)->index < GetDefInfo(rhs)->index;
+                     });
+    return sorted;
+  };
+
+  // Emit declarations of hoisted variables, in index order.
+  for (auto id : sorted_by_index(block_info.hoisted_ids)) {
     const auto* def_inst = def_use_mgr_->GetDef(id);
     assert(def_inst);
     AddStatement(
@@ -2378,11 +2388,22 @@
     // Save this as an already-named value.
     identifier_values_.insert(id);
   }
+  // Emit declarations of phi state variables, in index order.
+  for (auto id : sorted_by_index(block_info.phis_needing_state_vars)) {
+    const auto* def_inst = def_use_mgr_->GetDef(id);
+    assert(def_inst);
+    const auto phi_var_name = GetDefInfo(id)->phi_var;
+    assert(!phi_var_name.empty());
+    auto var = std::make_unique<ast::Variable>(
+        phi_var_name, ast::StorageClass::kFunction,
+        parser_impl_.ConvertType(def_inst->type_id()));
+    AddStatement(std::make_unique<ast::VariableDeclStatement>(std::move(var)));
+  }
 
+  // Emit regular statements.
   const spvtools::opt::BasicBlock& bb = *(block_info.basic_block);
   const auto* terminator = bb.terminator();
   const auto* merge = bb.GetMergeInst();  // Might be nullptr
-  // Emit regular statements.
   for (auto& inst : bb) {
     if (&inst == terminator || &inst == merge || inst.opcode() == SpvOpLabel ||
         inst.opcode() == SpvOpVariable) {
@@ -2392,6 +2413,26 @@
       return false;
     }
   }
+
+  // Emit assignments to carry values to phi nodes in potential destinations.
+  // Do it in index order.
+  if (!block_info.phi_assignments.empty()) {
+    auto sorted = block_info.phi_assignments;
+    std::stable_sort(sorted.begin(), sorted.end(),
+                     [this](const BlockInfo::PhiAssignment& lhs,
+                            const BlockInfo::PhiAssignment& rhs) {
+                       return GetDefInfo(lhs.phi_id)->index <
+                              GetDefInfo(rhs.phi_id)->index;
+                     });
+    for (auto assignment : block_info.phi_assignments) {
+      const auto var_name = GetDefInfo(assignment.phi_id)->phi_var;
+      auto expr = MakeExpression(assignment.value);
+      AddStatement(std::make_unique<ast::AssignmentStatement>(
+          std::make_unique<ast::IdentifierExpression>(var_name),
+          std::move(expr.expr)));
+    }
+  }
+
   *already_emitted = true;
   return true;
 }
@@ -2482,6 +2523,13 @@
       // a new named constant definition.
       return EmitConstDefOrWriteToHoistedVar(
           inst, MakeExpression(inst.GetSingleWordInOperand(0)));
+    case SpvOpPhi: {
+      // Emit a read from the associated state variable.
+      auto expr = TypedExpression(
+          parser_impl_.ConvertType(inst.type_id()),
+          std::make_unique<ast::IdentifierExpression>(def_info->phi_var));
+      return EmitConstDefOrWriteToHoistedVar(inst, std::move(expr));
+    }
     case SpvOpFunctionCall:
       // TODO(dneto): Fill this out.  Make this pass, for existing tests
       return success();
@@ -2917,6 +2965,7 @@
 
 void FunctionEmitter::RegisterValuesNeedingNamedOrHoistedDefinition() {
   // Create a DefInfo for each value definition in this function.
+  size_t index = 0;
   for (auto block_id : block_order_) {
     const auto* block_info = GetBlockInfo(block_id);
     const auto block_pos = block_info->pos;
@@ -2925,7 +2974,8 @@
       if ((result_id == 0) || inst.opcode() == SpvOpLabel) {
         continue;
       }
-      def_info_[result_id] = std::make_unique<DefInfo>(inst, block_pos);
+      def_info_[result_id] = std::make_unique<DefInfo>(inst, block_pos, index);
+      index++;
     }
   }
 
@@ -2936,8 +2986,8 @@
     if (inst.opcode() == SpvOpVectorShuffle) {
       // We might access the vector operands multiple times. Make sure they
       // are evaluated only once.
-      for (auto index : std::array<uint32_t, 2>{0, 1}) {
-        auto id = inst.GetSingleWordInOperand(index);
+      for (auto vector_arg : std::array<uint32_t, 2>{0, 1}) {
+        auto id = inst.GetSingleWordInOperand(vector_arg);
         auto* operand_def = GetDefInfo(id);
         if (operand_def) {
           operand_def->requires_named_const_def = true;
@@ -2946,8 +2996,7 @@
     }
   }
 
-  // Scan uses of locally defined IDs, to determine the block position
-  // of its last use.
+  // Scan uses of locally defined IDs, in function block order.
   for (auto block_id : block_order_) {
     const auto* block_info = GetBlockInfo(block_id);
     const auto block_pos = block_info->pos;
@@ -2960,13 +3009,55 @@
           def_info->last_use_pos = std::max(def_info->last_use_pos, block_pos);
         }
       });
+
+      if (inst.opcode() == SpvOpPhi) {
+        // Declare a name for the variable used to carry values to a phi.
+        const auto phi_id = inst.result_id();
+        auto* phi_def_info = GetDefInfo(phi_id);
+        phi_def_info->phi_var =
+            namer_.MakeDerivedName(namer_.Name(phi_id) + "_phi");
+        // Track all the places where we need to mention the variable,
+        // so we can place its declaration.  First, record the location of
+        // the read from the variable.
+        uint32_t first_pos = block_pos;
+        uint32_t last_pos = block_pos;
+        // Record the assignments that will propagate values from predecessor
+        // blocks.
+        for (uint32_t i = 0; i + 1 < inst.NumInOperands(); i += 2) {
+          const uint32_t value_id = inst.GetSingleWordInOperand(i);
+          const uint32_t pred_block_id = inst.GetSingleWordInOperand(i + 1);
+          auto* pred_block_info = GetBlockInfo(pred_block_id);
+          // The predecessor might not be in the block order at all, so we
+          // need this guard.
+          if (pred_block_info) {
+            // Record the assignment that needs to occur at the end
+            // of the predecessor block.
+            pred_block_info->phi_assignments.push_back({phi_id, value_id});
+            first_pos = std::min(first_pos, pred_block_info->pos);
+            last_pos = std::min(last_pos, pred_block_info->pos);
+          }
+        }
+
+        // Schedule the declaration of the state variable.
+        const auto* enclosing_construct =
+            GetSmallestEnclosingConstruct(first_pos, last_pos);
+        GetBlockInfo(enclosing_construct->begin_id)
+            ->phis_needing_state_vars.push_back(phi_id);
+      }
     }
   }
 
-  // For an ID defined in this function, if it is used in a different construct
-  // than its definition, then it needs a named constant definition.  Otherwise
-  // we might sink an expensive computation into control flow, and hence change
-  // performance.
+  // For an ID defined in this function, determine if its evaluation and
+  // potential declaration needs special handling:
+  // - Compensate for the fact that dominance does not map directly to scope.
+  //   A definition could dominate its use, but a named definition in WGSL
+  //   at the location of the definition could go out of scope by the time
+  //   you reach the use.  In that case, we hoist the definition to a basic
+  //   block at the smallest scope enclosing both the definition and all
+  //   its uses.
+  // - If value is used in a different construct than its definition, then it
+  //   needs a named constant definition.  Otherwise we might sink an
+  //   expensive computation into control flow, and hence change performance.
   for (auto& id_def_info_pair : def_info_) {
     const auto def_id = id_def_info_pair.first;
     auto* def_info = id_def_info_pair.second.get();
@@ -2974,24 +3065,19 @@
       // There is no need to adjust the location of the declaration.
       continue;
     }
+    // The first use must be the at the SSA definition, because block order
+    // respects dominance.
+    const auto first_pos = def_info->block_pos;
     const auto last_use_pos = def_info->last_use_pos;
 
     const auto* const def_in_construct =
-        GetBlockInfo(block_order_[def_info->block_pos])->construct;
+        GetBlockInfo(block_order_[first_pos])->construct;
     const auto* const construct_with_last_use =
         GetBlockInfo(block_order_[last_use_pos])->construct;
 
-    // Find the smallest structured construct that encloses the definition
-    // and all its uses.
-    const auto* enclosing_construct = def_in_construct;
-    while (enclosing_construct &&
-           !enclosing_construct->ContainsPos(last_use_pos)) {
-      enclosing_construct = enclosing_construct->parent;
-    }
-    // At worst, we go all the way out to the function construct.
-    assert(enclosing_construct != nullptr);
-
     if (def_in_construct != construct_with_last_use) {
+      const auto* enclosing_construct =
+          GetSmallestEnclosingConstruct(first_pos, last_use_pos);
       if (enclosing_construct == def_in_construct) {
         // We can use a plain 'const' definition.
         def_info->requires_named_const_def = true;
@@ -3006,6 +3092,21 @@
   }
 }
 
+const Construct* FunctionEmitter::GetSmallestEnclosingConstruct(
+    uint32_t first_pos,
+    uint32_t last_pos) const {
+  const auto* enclosing_construct =
+      GetBlockInfo(block_order_[first_pos])->construct;
+  assert(enclosing_construct != nullptr);
+  // Constructs are strictly nesting, so follow parent pointers
+  while (enclosing_construct && !enclosing_construct->ContainsPos(last_pos)) {
+    enclosing_construct = enclosing_construct->parent;
+  }
+  // At worst, we go all the way out to the function construct.
+  assert(enclosing_construct != nullptr);
+  return enclosing_construct;
+}
+
 TypedExpression FunctionEmitter::MakeNumericConversion(
     const spvtools::opt::Instruction& inst) {
   const auto opcode = inst.opcode();
diff --git a/src/reader/spirv/function.h b/src/reader/spirv/function.h
index 40e23c2..068657a 100644
--- a/src/reader/spirv/function.h
+++ b/src/reader/spirv/function.h
@@ -162,6 +162,21 @@
   /// hoisted variable.  See the |requires_hoisted_def| member of
   /// DefInfo for an explanation.
   std::vector<uint32_t> hoisted_ids;
+
+  /// A PhiAssignment represents the assignment of a value to the state
+  /// variable associated with an OpPhi in a successor block.
+  struct PhiAssignment {
+    /// The ID of an OpPhi receiving a value from this basic block.
+    uint32_t phi_id;
+    /// The the value carried to the given OpPhi.
+    uint32_t value;
+  };
+  /// If this basic block branches to a visited basic block containing phis,
+  /// then this is the list of writes to the variables associated those phis.
+  std::vector<PhiAssignment> phi_assignments;
+  /// The IDs of OpPhi instructions which require their associated state
+  /// variable to be declared in this basic block.
+  std::vector<uint32_t> phis_needing_state_vars;
 };
 
 inline std::ostream& operator<<(std::ostream& o, const BlockInfo& bi) {
@@ -182,7 +197,10 @@
   /// Constructor.
   /// @param def_inst the SPIR-V instruction defining the ID
   /// @param block_pos the position of the basic block where the ID is defined.
-  DefInfo(const spvtools::opt::Instruction& def_inst, uint32_t block_pos);
+  /// @param index an ordering index for this local definition
+  DefInfo(const spvtools::opt::Instruction& def_inst,
+          uint32_t block_pos,
+          size_t index);
   /// Destructor.
   ~DefInfo();
 
@@ -192,6 +210,10 @@
   /// order.  See method |FunctionEmitter::ComputeBlockOrderAndPositions|
   const uint32_t block_pos = 0;
 
+  /// An index for uniquely and deterministically ordering all DefInfo records
+  /// in a function.
+  const size_t index = 0;
+
   /// The number of uses of this ID.
   uint32_t num_uses = 0;
 
@@ -217,6 +239,11 @@
   /// TODO(dneto): This works for constants of storable type, but not, for
   /// example, pointers.
   bool requires_hoisted_def = false;
+
+  /// If the definition is an OpPhi, then |phi_var| is the name of the
+  /// variable that stores the value carried from parent basic blocks into
+  // the basic block containing the OpPhi. Otherwise this is the empty string.
+  std::string phi_var;
 };
 
 inline std::ostream& operator<<(std::ostream& o, const DefInfo& di) {
@@ -226,6 +253,7 @@
     << " last_use_pos: " << di.last_use_pos << " requires_named_const_def: "
     << (di.requires_named_const_def ? "true" : "false")
     << " requires_hoisted_def: " << (di.requires_hoisted_def ? "true" : "false")
+    << " phi_var: '" << di.phi_var << "'"
     << "}";
   return o;
 }
@@ -572,6 +600,15 @@
     return where->second.get();
   }
 
+  /// Returns the most deeply nested structured construct which encloses
+  /// both block positions. Each position must be a valid index into the
+  /// function block order array.
+  /// @param first_pos the first block position
+  /// @param last_pos the last block position
+  /// @returns the smallest construct containing both positions
+  const Construct* GetSmallestEnclosingConstruct(uint32_t first_pos,
+                                                 uint32_t last_pos) const;
+
  private:
   /// @returns the store type for the OpVariable instruction, or
   /// null on failure.
diff --git a/src/reader/spirv/function_var_test.cc b/src/reader/spirv/function_var_test.cc
index 85ac938..6693ae7 100644
--- a/src/reader/spirv/function_var_test.cc
+++ b/src/reader/spirv/function_var_test.cc
@@ -929,6 +929,539 @@
 )")) << ToString(fe.ast_body());
 }
 
+TEST_F(SpvParserTest, EmitStatement_Phi_SingleBlockLoopIndex) {
+  auto assembly = Preamble() + R"(
+     %pty = OpTypePointer Private %uint
+     %1 = OpVariable %pty Private
+     %boolpty = OpTypePointer Private %bool
+     %7 = OpVariable %boolpty Private
+     %8 = OpVariable %boolpty Private
+
+     %100 = OpFunction %void None %voidfn
+
+     %5 = OpLabel
+     OpBranch %10
+
+     ; Use an outer loop to show we put the new variable in the
+     ; smallest enclosing scope.
+     %10 = OpLabel
+     %101 = OpLoad %bool %7
+     %102 = OpLoad %bool %8
+     OpLoopMerge %99 %89 None
+     OpBranchConditional %101 %99 %20
+
+     %20 = OpLabel
+     %2 = OpPhi %uint %uint_0 %10 %4 %20  ; gets computed value
+     %3 = OpPhi %uint %uint_1 %10 %3 %20  ; gets itself
+     %4 = OpIAdd %uint %2 %uint_1
+     OpLoopMerge %89 %20 None
+     OpBranchConditional %102 %89 %20
+
+     %89 = OpLabel
+     OpBranch %10
+
+     %99 = OpLabel
+     OpReturn
+
+     OpFunctionEnd
+  )";
+  auto* p = parser(test::Assemble(assembly));
+  ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << assembly;
+  FunctionEmitter fe(p, *spirv_function(100));
+  EXPECT_TRUE(fe.EmitBody()) << p->error();
+
+  EXPECT_THAT(ToString(fe.ast_body()), Eq(R"(Loop{
+  VariableDeclStatement{
+    Variable{
+      x_2_phi
+      function
+      __u32
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_3_phi
+      function
+      __u32
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_101
+      none
+      __bool
+      {
+        Identifier{x_7}
+      }
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_102
+      none
+      __bool
+      {
+        Identifier{x_8}
+      }
+    }
+  }
+  Assignment{
+    Identifier{x_2_phi}
+    ScalarConstructor{0}
+  }
+  Assignment{
+    Identifier{x_3_phi}
+    ScalarConstructor{1}
+  }
+  If{
+    (
+      Identifier{x_101}
+    )
+    {
+      Break{}
+    }
+  }
+  Loop{
+    VariableDeclStatement{
+      Variable{
+        x_2
+        none
+        __u32
+        {
+          Identifier{x_2_phi}
+        }
+      }
+    }
+    VariableDeclStatement{
+      Variable{
+        x_3
+        none
+        __u32
+        {
+          Identifier{x_3_phi}
+        }
+      }
+    }
+    Assignment{
+      Identifier{x_2_phi}
+      Binary{
+        Identifier{x_2}
+        add
+        ScalarConstructor{1}
+      }
+    }
+    Assignment{
+      Identifier{x_3_phi}
+      Identifier{x_3}
+    }
+    If{
+      (
+        Identifier{x_102}
+      )
+      {
+        Break{}
+      }
+    }
+  }
+}
+Return{}
+)")) << ToString(fe.ast_body());
+}
+
+TEST_F(SpvParserTest, EmitStatement_Phi_MultiBlockLoopIndex) {
+  auto assembly = Preamble() + R"(
+     %pty = OpTypePointer Private %uint
+     %1 = OpVariable %pty Private
+     %boolpty = OpTypePointer Private %bool
+     %7 = OpVariable %boolpty Private
+     %8 = OpVariable %boolpty Private
+
+     %100 = OpFunction %void None %voidfn
+
+     %5 = OpLabel
+     OpBranch %10
+
+     ; Use an outer loop to show we put the new variable in the
+     ; smallest enclosing scope.
+     %10 = OpLabel
+     %101 = OpLoad %bool %7
+     %102 = OpLoad %bool %8
+     OpLoopMerge %99 %89 None
+     OpBranchConditional %101 %99 %20
+
+     %20 = OpLabel
+     %2 = OpPhi %uint %uint_0 %10 %4 %30  ; gets computed value
+     %3 = OpPhi %uint %uint_1 %10 %3 %30  ; gets itself
+     OpLoopMerge %89 %30 None
+     OpBranchConditional %102 %89 %30
+
+     %30 = OpLabel
+     %4 = OpIAdd %uint %2 %uint_1
+     OpBranch %20
+
+     %89 = OpLabel
+     OpBranch %10
+
+     %99 = OpLabel
+     OpReturn
+
+     OpFunctionEnd
+  )";
+  auto* p = parser(test::Assemble(assembly));
+  ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << assembly;
+  FunctionEmitter fe(p, *spirv_function(100));
+  EXPECT_TRUE(fe.EmitBody()) << p->error();
+
+  EXPECT_THAT(ToString(fe.ast_body()), Eq(R"(Loop{
+  VariableDeclStatement{
+    Variable{
+      x_2
+      function
+      __u32
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_4
+      function
+      __u32
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_2_phi
+      function
+      __u32
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_3_phi
+      function
+      __u32
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_101
+      none
+      __bool
+      {
+        Identifier{x_7}
+      }
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_102
+      none
+      __bool
+      {
+        Identifier{x_8}
+      }
+    }
+  }
+  Assignment{
+    Identifier{x_2_phi}
+    ScalarConstructor{0}
+  }
+  Assignment{
+    Identifier{x_3_phi}
+    ScalarConstructor{1}
+  }
+  If{
+    (
+      Identifier{x_101}
+    )
+    {
+      Break{}
+    }
+  }
+  Loop{
+    Assignment{
+      Identifier{x_2}
+      Identifier{x_2_phi}
+    }
+    VariableDeclStatement{
+      Variable{
+        x_3
+        none
+        __u32
+        {
+          Identifier{x_3_phi}
+        }
+      }
+    }
+    If{
+      (
+        Identifier{x_102}
+      )
+      {
+        Break{}
+      }
+    }
+    continuing {
+      Assignment{
+        Identifier{x_4}
+        Binary{
+          Identifier{x_2}
+          add
+          ScalarConstructor{1}
+        }
+      }
+      Assignment{
+        Identifier{x_2_phi}
+        Identifier{x_4}
+      }
+      Assignment{
+        Identifier{x_3_phi}
+        Identifier{x_3}
+      }
+    }
+  }
+}
+Return{}
+)")) << ToString(fe.ast_body());
+}
+
+TEST_F(SpvParserTest, EmitStatement_Phi_FromElseAndThen) {
+  auto assembly = Preamble() + R"(
+     %pty = OpTypePointer Private %uint
+     %1 = OpVariable %pty Private
+     %boolpty = OpTypePointer Private %bool
+     %7 = OpVariable %boolpty Private
+     %8 = OpVariable %boolpty Private
+
+     %100 = OpFunction %void None %voidfn
+
+     %5 = OpLabel
+     %101 = OpLoad %bool %7
+     %102 = OpLoad %bool %8
+     OpBranch %10
+
+     ; Use an outer loop to show we put the new variable in the
+     ; smallest enclosing scope.
+     %10 = OpLabel
+     OpLoopMerge %99 %89 None
+     OpBranchConditional %101 %99 %20
+
+     %20 = OpLabel ; if seleciton
+     OpSelectionMerge %89 None
+     OpBranchConditional %102 %30 %40
+
+     %30 = OpLabel
+     OpBranch %89
+
+     %40 = OpLabel
+     OpBranch %89
+
+     %89 = OpLabel
+     %2 = OpPhi %uint %uint_0 %30 %uint_1 %40
+     OpStore %1 %2
+     OpBranch %10
+
+     %99 = OpLabel
+     OpReturn
+
+     OpFunctionEnd
+  )";
+  auto* p = parser(test::Assemble(assembly));
+  ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << assembly;
+  FunctionEmitter fe(p, *spirv_function(100));
+  EXPECT_TRUE(fe.EmitBody()) << p->error();
+
+  EXPECT_THAT(ToString(fe.ast_body()), Eq(R"(VariableDeclStatement{
+  Variable{
+    x_101
+    none
+    __bool
+    {
+      Identifier{x_7}
+    }
+  }
+}
+VariableDeclStatement{
+  Variable{
+    x_102
+    none
+    __bool
+    {
+      Identifier{x_8}
+    }
+  }
+}
+Loop{
+  If{
+    (
+      Identifier{x_101}
+    )
+    {
+      Break{}
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_2_phi
+      function
+      __u32
+    }
+  }
+  If{
+    (
+      Identifier{x_102}
+    )
+    {
+      Assignment{
+        Identifier{x_2_phi}
+        ScalarConstructor{0}
+      }
+      Continue{}
+    }
+  }
+  Else{
+    {
+      Assignment{
+        Identifier{x_2_phi}
+        ScalarConstructor{1}
+      }
+    }
+  }
+  continuing {
+    VariableDeclStatement{
+      Variable{
+        x_2
+        none
+        __u32
+        {
+          Identifier{x_2_phi}
+        }
+      }
+    }
+    Assignment{
+      Identifier{x_1}
+      Identifier{x_2}
+    }
+  }
+}
+Return{}
+)")) << ToString(fe.ast_body());
+}
+
+TEST_F(SpvParserTest, EmitStatement_Phi_FromHeaderAndThen) {
+  auto assembly = Preamble() + R"(
+     %pty = OpTypePointer Private %uint
+     %1 = OpVariable %pty Private
+     %boolpty = OpTypePointer Private %bool
+     %7 = OpVariable %boolpty Private
+     %8 = OpVariable %boolpty Private
+
+     %100 = OpFunction %void None %voidfn
+
+     %5 = OpLabel
+     %101 = OpLoad %bool %7
+     %102 = OpLoad %bool %8
+     OpBranch %10
+
+     ; Use an outer loop to show we put the new variable in the
+     ; smallest enclosing scope.
+     %10 = OpLabel
+     OpLoopMerge %99 %89 None
+     OpBranchConditional %101 %99 %20
+
+     %20 = OpLabel ; if seleciton
+     OpSelectionMerge %89 None
+     OpBranchConditional %102 %30 %89
+
+     %30 = OpLabel
+     OpBranch %89
+
+     %89 = OpLabel
+     %2 = OpPhi %uint %uint_0 %20 %uint_1 %30
+     OpStore %1 %2
+     OpBranch %10
+
+     %99 = OpLabel
+     OpReturn
+
+     OpFunctionEnd
+  )";
+  auto* p = parser(test::Assemble(assembly));
+  ASSERT_TRUE(p->BuildAndParseInternalModuleExceptFunctions()) << assembly;
+  FunctionEmitter fe(p, *spirv_function(100));
+  EXPECT_TRUE(fe.EmitBody()) << p->error();
+
+  EXPECT_THAT(ToString(fe.ast_body()), Eq(R"(VariableDeclStatement{
+  Variable{
+    x_101
+    none
+    __bool
+    {
+      Identifier{x_7}
+    }
+  }
+}
+VariableDeclStatement{
+  Variable{
+    x_102
+    none
+    __bool
+    {
+      Identifier{x_8}
+    }
+  }
+}
+Loop{
+  If{
+    (
+      Identifier{x_101}
+    )
+    {
+      Break{}
+    }
+  }
+  VariableDeclStatement{
+    Variable{
+      x_2_phi
+      function
+      __u32
+    }
+  }
+  Assignment{
+    Identifier{x_2_phi}
+    ScalarConstructor{0}
+  }
+  If{
+    (
+      Identifier{x_102}
+    )
+    {
+      Assignment{
+        Identifier{x_2_phi}
+        ScalarConstructor{1}
+      }
+    }
+  }
+  continuing {
+    VariableDeclStatement{
+      Variable{
+        x_2
+        none
+        __u32
+        {
+          Identifier{x_2_phi}
+        }
+      }
+    }
+    Assignment{
+      Identifier{x_1}
+      Identifier{x_2}
+    }
+  }
+}
+Return{}
+)")) << ToString(fe.ast_body());
+}
+
 }  // namespace
 }  // namespace spirv
 }  // namespace reader