diff --git a/mlir/lib/Transforms/CSE.cpp b/mlir/lib/Transforms/CSE.cpp
--- a/mlir/lib/Transforms/CSE.cpp
+++ b/mlir/lib/Transforms/CSE.cpp
@@ -115,8 +115,18 @@
   if (auto *existing = knownValues.lookup(op)) {
     // If we find one then replace all uses of the current operation with the
     // existing one and mark it for deletion.
-    op->replaceAllUsesWith(existing);
-    opsToErase.push_back(op);
+    for (unsigned i = 0, e = existing->getNumResults(); i != e; ++i) {
+      auto newResult = existing->getResult(i);
+      op->getResult(i).replaceUsesWithIf(newResult, [&](OpOperand &operand) {
+        // We can only replace an operand in an operation if it has not been
+        // visited yet. This can only happen in regions without strict
+        // dominance, such as graph regions.
+        return !knownValues.count(operand.getOwner());
+      });
+    }
+
+    if (op->use_empty())
+      opsToErase.push_back(op);
 
     // If the existing operation has an unknown location and the current
     // operation doesn't, then set the existing op's location to that of the
diff --git a/mlir/test/Transforms/cse.mlir b/mlir/test/Transforms/cse.mlir
--- a/mlir/test/Transforms/cse.mlir
+++ b/mlir/test/Transforms/cse.mlir
@@ -244,3 +244,24 @@
 
   return %0 : i32
 }
+
+/// This test is checking that CSE gracefully handles values in graph regions
+/// where the use occurs before the def, and one of the defs could be CSE'd with
+/// the other.
+// CHECK-LABEL: @use_before_def
+func @use_before_def() {
+  // CHECK-NEXT: test.graph_region
+  test.graph_region {
+    // CHECK-NEXT: addi %c1_i32, %c1_i32_0
+    %0 = addi %1, %2 : i32
+
+    // CHECK-NEXT: constant 1
+    // CHECK-NEXT: constant 1
+    %1 = constant 1 : i32
+    %2 = constant 1 : i32
+
+    // CHECK-NEXT: "foo.yield"(%0) : (i32) -> ()
+    "foo.yield"(%0) : (i32) -> ()
+  }
+  return
+}