diff --git a/mlir/lib/Transforms/Utils/RegionUtils.cpp b/mlir/lib/Transforms/Utils/RegionUtils.cpp
--- a/mlir/lib/Transforms/Utils/RegionUtils.cpp
+++ b/mlir/lib/Transforms/Utils/RegionUtils.cpp
@@ -312,21 +312,18 @@
     if (region.empty())
       continue;
 
-    // We do the deletion in an order that deletes all uses before deleting
-    // defs.
-    // MLIR's SSA structural invariants guarantee that except for block
-    // arguments, the use-def graph is acyclic, so this is possible with a
-    // single walk of ops and then a final pass to clean up block arguments.
-    //
-    // To do this, we visit ops in an order that visits domtree children
-    // before domtree parents. A CFG post-order (with reverse iteration with a
-    // block) satisfies that without needing an explicit domtree calculation.
+    // Delete every operation that is not live. Graph regions may have cycles
+    // in the use-def graph, so we must explicitly dropAllUses() from each
+    // operation as we erase it. Visiting the operations in post-order
+    // guarantees that in SSA CFG regions value uses are removed before defs,
+    // which makes dropAllUses() a no-op.
     for (Block *block : llvm::post_order(&region.front())) {
       eraseTerminatorSuccessorOperands(block->getTerminator(), liveMap);
       for (Operation &childOp :
            llvm::make_early_inc_range(llvm::reverse(block->getOperations()))) {
         if (!liveMap.wasProvenLive(&childOp)) {
           erasedAnything = true;
+          childOp.dropAllUses();
           childOp.erase();
         } else {
           erasedAnything |=
diff --git a/mlir/test/Transforms/canonicalize-dce.mlir b/mlir/test/Transforms/canonicalize-dce.mlir
--- a/mlir/test/Transforms/canonicalize-dce.mlir
+++ b/mlir/test/Transforms/canonicalize-dce.mlir
@@ -156,3 +156,20 @@
   "foo.print"(%t4) : (tensor<4xf32>) -> ()
   return
 }
+
+// -----
+
+// Test case: Test values with use-def cycles are deleted properly.
+
+// CHECK:      func @f()
+// CHECK-NEXT:   test.graph_region
+// CHECK-NEXT:     "test.terminator"() : () -> ()
+
+func @f() {
+  test.graph_region {
+    %0 = "math.exp"(%1) : (f32) -> f32
+    %1 = "math.exp"(%0) : (f32) -> f32
+    "test.terminator"() : ()->()
+  }
+  return
+}