diff --git a/mlir/lib/Dialect/LLVMIR/IR/LLVMDialect.cpp b/mlir/lib/Dialect/LLVMIR/IR/LLVMDialect.cpp
--- a/mlir/lib/Dialect/LLVMIR/IR/LLVMDialect.cpp
+++ b/mlir/lib/Dialect/LLVMIR/IR/LLVMDialect.cpp
@@ -2490,10 +2490,17 @@
   // Add new graph node corresponding to `symbol`
   // defined by a TBAA operation.
   void addNodeDefinition(StringAttr symbol) {
+    assert(root.operands.empty() &&
+           "adding more elements to the DenseMap when there are already "
+           "pointers to its elements can lead to their invalidation");
     TBAAGraphNode &node = nodeMap[symbol];
     assert(node.symbol.empty() && "node is already in the graph");
     node.symbol = symbol;
-    root.operands.push_back(&node);
+  }
+
+  void fillRootOperands() {
+    for (auto &[key, node] : nodeMap)
+      root.operands.push_back(&node);
   }
 
   // Get a pointer to TBAAGraphNode corresponding
@@ -2541,7 +2548,7 @@
   // for detecting cycles in the TBAA graph, which is illegal.
   TBAAGraph tbaaGraph;
 
-  for (Operation &op : body.getOps())
+  for (Operation &op : body.getOps()) {
     if (isa<LLVM::TBAARootMetadataOp>(op) ||
         isa<LLVM::TBAATypeDescriptorOp>(op)) {
       StringAttr symbolDef = cast<SymbolOpInterface>(op).getNameAttr();
@@ -2550,6 +2557,11 @@
     } else if (auto tagOp = dyn_cast<LLVM::TBAATagOp>(op)) {
       tbaaGraph.addNodeDefinition(tagOp.getSymNameAttr());
     }
+  }
+
+  // Fill the graph operands once all nodes were added. Otherwise, reallocation
+  // can lead to pointer invalidation.
+  tbaaGraph.fillRootOperands();
 
   // Verify that TBAA metadata operations refer symbols
   // from definedGraphSymbols only. Note that TBAATagOp