diff --git a/src/resolver/dependency_graph.cc b/src/resolver/dependency_graph.cc
index 4cfb45d..947be99 100644
--- a/src/resolver/dependency_graph.cc
+++ b/src/resolver/dependency_graph.cc
@@ -305,8 +305,8 @@
             auto global_it = globals_.find(ident->symbol);
             if (global_it != globals_.end() &&
                 node == global_it->second->node) {
-              ResolveGlobalDependency(ident, ident->symbol, "identifier",
-                                      "references");
+              AddGlobalDependency(ident, ident->symbol, "identifier",
+                                  "references");
             } else {
               graph_.resolved_symbols.emplace(ident, node);
             }
@@ -314,9 +314,9 @@
           if (auto* call = expr->As<ast::CallExpression>()) {
             if (call->target.name) {
               if (!IsIntrinsic(call->target.name->symbol)) {
-                ResolveGlobalDependency(call->target.name,
-                                        call->target.name->symbol, "function",
-                                        "calls");
+                AddGlobalDependency(call->target.name,
+                                    call->target.name->symbol, "function",
+                                    "calls");
                 graph_.resolved_symbols.emplace(
                     call,
                     utils::Lookup(graph_.resolved_symbols, call->target.name));
@@ -357,7 +357,7 @@
       return;
     }
     if (auto* tn = ty->As<ast::TypeName>()) {
-      ResolveGlobalDependency(tn, tn->name, "type", "references");
+      AddGlobalDependency(tn, tn->name, "type", "references");
       return;
     }
     if (auto* vec = ty->As<ast::Vector>()) {
@@ -415,10 +415,10 @@
   }
 
   /// Adds the dependency to the currently processed global
-  void ResolveGlobalDependency(const ast::Node* from,
-                               Symbol to,
-                               const char* use,
-                               const char* action) {
+  void AddGlobalDependency(const ast::Node* from,
+                           Symbol to,
+                           const char* use,
+                           const char* action) {
     auto global_it = globals_.find(to);
     if (global_it != globals_.end()) {
       auto* global = global_it->second;
@@ -482,9 +482,8 @@
     // Sort the globals into dependency order
     SortGlobals();
 
-#if TINT_DUMP_DEPENDENCY_GRAPH
+    // Dump the dependency graph if TINT_DUMP_DEPENDENCY_GRAPH is non-zero
     DumpDependencyGraph();
-#endif
 
     if (!allow_out_of_order_decls) {
       // Prevent out-of-order declarations.
@@ -630,16 +629,26 @@
               return false;
             }
             if (sorted_.contains(g->node)) {
-              return false;  // Visited this global already.
+              // Visited this global already.
+              // stack was pushed, but exit() will not be called when we return
+              // false, so pop here.
+              stack.pop_back();
+              return false;
             }
             return true;
           },
-          [&](const Global* g) {  // Exit
+          [&](const Global* g) {  // Exit. Only called if Enter returned true.
             sorted_.add(g->node);
             stack.pop_back();
           });
 
       sorted_.add(global->node);
+
+      if (!stack.empty()) {
+        // Each stack.push() must have a corresponding stack.pop_back().
+        TINT_ICE(Resolver, diagnostics_)
+            << "stack not empty after returning from TraverseDependencies()";
+      }
     }
   }
 
@@ -720,25 +729,28 @@
     }
   }
 
-#if TINT_DUMP_DEPENDENCY_GRAPH
   void DumpDependencyGraph() {
+#if TINT_DUMP_DEPENDENCY_GRAPH == 0
+    if ((true)) {
+      return;
+    }
+#endif  // TINT_DUMP_DEPENDENCY_GRAPH
     printf("=========================\n");
     printf("------ declaration ------ \n");
     for (auto* global : declaration_order_) {
       printf("%s\n", NameOf(global->node).c_str());
     }
     printf("------ dependencies ------ \n");
-    for (auto* node : sorted) {
+    for (auto* node : sorted_) {
       auto symbol = SymbolOf(node);
-      auto* global = globals.at(symbol);
-      printf("%s depends on:\n", symbols.NameFor(symbol).c_str());
-      for (auto& dep : global->deps) {
-        printf("  %s\n", NameOf(dep.global->node).c_str());
+      auto* global = globals_.at(symbol);
+      printf("%s depends on:\n", symbols_.NameFor(symbol).c_str());
+      for (auto* dep : global->deps) {
+        printf("  %s\n", NameOf(dep->node).c_str());
       }
     }
     printf("=========================\n");
   }
-#endif  // TINT_DUMP_DEPENDENCY_GRAPH
 
   /// Program symbols
   const SymbolTable& symbols_;
diff --git a/src/resolver/dependency_graph_test.cc b/src/resolver/dependency_graph_test.cc
index e222b43..5fd048d 100644
--- a/src/resolver/dependency_graph_test.cc
+++ b/src/resolver/dependency_graph_test.cc
@@ -1339,6 +1339,19 @@
   Build();
 }
 
+// Reproduces an unbalanced stack push / pop bug in
+// DependencyAnalysis::SortGlobals(), found by clusterfuzz.
+// See: crbug.com/chromium/1273451
+TEST_F(ResolverDependencyGraphTraversalTest, chromium_1273451) {
+  Structure("A", {Member("a", ty.i32())});
+  Structure("B", {Member("b", ty.i32())});
+  Func("f", {Param("a", ty.type_name("A"))}, ty.type_name("B"),
+       {
+           Return(Construct(ty.type_name("B"))),
+       });
+  Build();
+}
+
 }  // namespace ast_traversal
 
 }  // namespace
diff --git a/src/utils/unique_vector.h b/src/utils/unique_vector.h
index 5cb754d..f64ed07 100644
--- a/src/utils/unique_vector.h
+++ b/src/utils/unique_vector.h
@@ -71,6 +71,9 @@
   /// @returns the element at the index `i`
   const T& operator[](size_t i) const { return vector[i]; }
 
+  /// @returns true if the vector is empty
+  size_t empty() const { return vector.empty(); }
+
   /// @returns the number of items in the vector
   size_t size() const { return vector.size(); }
 
diff --git a/src/utils/unique_vector_test.cc b/src/utils/unique_vector_test.cc
index fc16784..3ec78fa 100644
--- a/src/utils/unique_vector_test.cc
+++ b/src/utils/unique_vector_test.cc
@@ -24,12 +24,14 @@
 TEST(UniqueVectorTest, Empty) {
   UniqueVector<int> unique_vec;
   EXPECT_EQ(unique_vec.size(), 0u);
+  EXPECT_EQ(unique_vec.empty(), true);
   EXPECT_EQ(unique_vec.begin(), unique_vec.end());
 }
 
 TEST(UniqueVectorTest, MoveConstructor) {
   UniqueVector<int> unique_vec(std::vector<int>{0, 3, 2, 1, 2});
   EXPECT_EQ(unique_vec.size(), 4u);
+  EXPECT_EQ(unique_vec.empty(), false);
   EXPECT_EQ(unique_vec[0], 0);
   EXPECT_EQ(unique_vec[1], 3);
   EXPECT_EQ(unique_vec[2], 2);
@@ -42,6 +44,7 @@
   unique_vec.add(1);
   unique_vec.add(2);
   EXPECT_EQ(unique_vec.size(), 3u);
+  EXPECT_EQ(unique_vec.empty(), false);
   int i = 0;
   for (auto n : unique_vec) {
     EXPECT_EQ(n, i);
@@ -65,6 +68,7 @@
   unique_vec.add(1);
   unique_vec.add(2);
   EXPECT_EQ(unique_vec.size(), 3u);
+  EXPECT_EQ(unique_vec.empty(), false);
   int i = 0;
   for (auto n : unique_vec) {
     EXPECT_EQ(n, i);
@@ -90,6 +94,7 @@
 
   const std::vector<int>& vec = unique_vec;
   EXPECT_EQ(vec.size(), 3u);
+  EXPECT_EQ(unique_vec.empty(), false);
   int i = 0;
   for (auto n : vec) {
     EXPECT_EQ(n, i);
@@ -109,18 +114,30 @@
 
   EXPECT_EQ(unique_vec.pop_back(), 1);
   EXPECT_EQ(unique_vec.size(), 2u);
+  EXPECT_EQ(unique_vec.empty(), false);
   EXPECT_EQ(unique_vec[0], 0);
   EXPECT_EQ(unique_vec[1], 2);
 
   EXPECT_EQ(unique_vec.pop_back(), 2);
   EXPECT_EQ(unique_vec.size(), 1u);
+  EXPECT_EQ(unique_vec.empty(), false);
   EXPECT_EQ(unique_vec[0], 0);
 
   unique_vec.add(1);
 
   EXPECT_EQ(unique_vec.size(), 2u);
+  EXPECT_EQ(unique_vec.empty(), false);
   EXPECT_EQ(unique_vec[0], 0);
   EXPECT_EQ(unique_vec[1], 1);
+
+  EXPECT_EQ(unique_vec.pop_back(), 1);
+  EXPECT_EQ(unique_vec.size(), 1u);
+  EXPECT_EQ(unique_vec.empty(), false);
+  EXPECT_EQ(unique_vec[0], 0);
+
+  EXPECT_EQ(unique_vec.pop_back(), 0);
+  EXPECT_EQ(unique_vec.size(), 0u);
+  EXPECT_EQ(unique_vec.empty(), true);
 }
 
 }  // namespace
diff --git a/test/bug/chromium/1273451.wgsl b/test/bug/chromium/1273451.wgsl
new file mode 100644
index 0000000..2289c10
--- /dev/null
+++ b/test/bug/chromium/1273451.wgsl
@@ -0,0 +1,11 @@
+struct A {
+  a : i32;
+};
+
+struct B {
+  b : i32;
+};
+
+fn f(a : A) -> B {
+  return B();
+}