diff --git a/mlir/lib/Analysis/DataFlowAnalysis.cpp b/mlir/lib/Analysis/DataFlowAnalysis.cpp
--- a/mlir/lib/Analysis/DataFlowAnalysis.cpp
+++ b/mlir/lib/Analysis/DataFlowAnalysis.cpp
@@ -722,8 +722,7 @@
 }
 
 void ForwardDataFlowSolver::markEdgeExecutable(Block *from, Block *to) {
-  if (!executableEdges.insert(std::make_pair(from, to)).second)
-    return;
+  executableEdges.insert(std::make_pair(from, to));
 
   // Mark the destination as executable, and reprocess its arguments if it was
   // already executable.
diff --git a/mlir/test/Transforms/sccp.mlir b/mlir/test/Transforms/sccp.mlir
--- a/mlir/test/Transforms/sccp.mlir
+++ b/mlir/test/Transforms/sccp.mlir
@@ -178,3 +178,23 @@
 
   return %arg : i32
 }
+
+// Check that we reprocess executable edges when information changes.
+
+// CHECK-LABEL: func @recheck_executable_edge
+func @recheck_executable_edge(%cond0: i1) -> (i1, i1) {
+  %true = constant true
+  %false = constant false
+  cond_br %cond0, ^bb_1a, ^bb2(%false : i1)
+^bb_1a:
+  br ^bb2(%true : i1)
+
+^bb2(%x: i1):
+  // CHECK: ^bb2(%[[X:.*]]: i1):
+  br ^bb3(%x : i1)
+
+^bb3(%y: i1):
+  // CHECK: ^bb3(%[[Y:.*]]: i1):
+  // CHECK: return %[[X]], %[[Y]]
+  return %x, %y : i1, i1
+}