diff --git a/mlir/lib/Dialect/Affine/Transforms/LoopTiling.cpp b/mlir/lib/Dialect/Affine/Transforms/LoopTiling.cpp
--- a/mlir/lib/Dialect/Affine/Transforms/LoopTiling.cpp
+++ b/mlir/lib/Dialect/Affine/Transforms/LoopTiling.cpp
@@ -157,6 +157,83 @@
   }
 }
 
+LogicalResult checkTilingLegality(MutableArrayRef<mlir::AffineForOp> origLoops,
+                                  ArrayRef<unsigned> tileSizes) {
+  // We assume that all the forOp's in origLoops are tiled.
+  assert(!origLoops.empty() && "no original loops provided");
+
+  // We first find out all dependences we intend to check.
+  SmallVector<Operation *, 8> loadAndStoreOpInsts;
+  origLoops[0].getOperation()->walk([&](Operation *opInst) {
+    if (isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst))
+      loadAndStoreOpInsts.push_back(opInst);
+  });
+
+  unsigned numOps = loadAndStoreOpInsts.size();
+  for (unsigned d = 1; d <= origLoops.size() + 1; ++d) {
+    for (unsigned i = 0; i < numOps; ++i) {
+      auto *srcOpInst = loadAndStoreOpInsts[i];
+      MemRefAccess srcAccess(srcOpInst);
+      for (unsigned j = 0; j < numOps; ++j) {
+        auto *dstOpInst = loadAndStoreOpInsts[j];
+        MemRefAccess dstAccess(dstOpInst);
+
+        FlatAffineConstraints dependenceConstraints;
+        DependenceResult result = checkMemrefAccessDependence(
+            srcAccess, dstAccess, d, &dependenceConstraints, nullptr);
+
+        // Skip if there is no dependence in this case
+        if (!hasDependence(result))
+          continue;
+
+        // Now we need to add tiling constraints -
+        // Since currently we don't explicitly model the tiling hyperplane
+        // we simply assume that affine tranformation is:
+        // f(x) = x floordiv tileSize
+
+        // Iterate every tile size, which corresponds to a specific loop IV.
+        for (uint64_t t = 0; t < tileSizes.size(); ++t) {
+          auto cst = dependenceConstraints.clone();
+
+          auto tileSize = tileSizes[t];
+          // add local variable for both src and dst
+          SmallVector<int64_t, 8> srcDividend, dstDividend;
+          // set the corresponding dim column to 1, others to zero
+          for (unsigned i = 0; i < cst->getNumCols(); ++i)
+            srcDividend.push_back(static_cast<uint64_t>(i == t));
+          cst->addLocalFloorDiv(srcDividend, tileSize);
+          for (unsigned i = 0; i < cst->getNumCols(); ++i)
+            dstDividend.push_back(
+                static_cast<uint64_t>(i == t + srcAccess.indices.size()));
+          cst->addLocalFloorDiv(dstDividend, tileSize);
+
+          // Finally we try to test whether the legality constraint is
+          // satisfied. Here we put the inequality that depicts the illegal
+          // condition into the contraint system, and check whether the set
+          // becomes empty.
+          // If so, it means there is no dependence violated. Otherwise, we
+          // should return failure.
+          SmallVector<int64_t, 8> inEq;
+          inEq.resize(cst->getNumCols());
+          for (unsigned i = 0; i < cst->getNumDimAndSymbolIds(); i++)
+            inEq[i] = 0;
+          inEq[cst->getNumDimAndSymbolIds()] = 1;
+          inEq[cst->getNumDimAndSymbolIds() + 1] = -1;
+          inEq[cst->getNumDimAndSymbolIds() + 2] = -1;
+
+          cst->addInequality(inEq);
+          cst->dump();
+          if (!cst->isEmpty()) {
+            return failure();
+          }
+        }
+      }
+    }
+  }
+
+  return success();
+};
+
 /// Tiles the specified band of perfectly nested loops creating tile-space loops
 /// and intra-tile loops. A band is a contiguous set of loops.
 //  TODO: handle non hyper-rectangular spaces.
@@ -172,6 +249,11 @@
 
   auto origLoops = input;
 
+  // Perform tiling legality test
+  if (failed(checkTilingLegality(origLoops, tileSizes))) {
+    origLoops[0].emitRemark("tiled code is illegal in dependence.");
+  }
+
   AffineForOp rootAffineForOp = origLoops[0];
   auto loc = rootAffineForOp.getLoc();
   // Note that width is at least one since band isn't empty.
diff --git a/mlir/test/Dialect/Affine/loop-tiling-dependence.mlir b/mlir/test/Dialect/Affine/loop-tiling-dependence.mlir
new file mode 100644
--- /dev/null
+++ b/mlir/test/Dialect/Affine/loop-tiling-dependence.mlir
@@ -0,0 +1,35 @@
+// RUN: mlir-opt %s  -split-input-file -affine-loop-tile="tile-size=32" -verify-diagnostics | FileCheck %s
+
+// -----
+
+// CHECK-LABEL: func @simple_for
+func @simple_for() {
+  %0 = alloc() : memref<64xf32>
+
+  affine.for %i = 0 to 64 {
+    %1 = affine.load %0[%i] : memref<64xf32>
+    %2 = addf %1, %1 : f32
+    affine.store %2, %0[%i] : memref<64xf32>
+  }
+
+  return 
+}
+
+// -----
+
+// CHECK-LABEL: func @diagonal_dependence
+func @diagonal_dependence() {
+  %A = alloc() : memref<64x64xf32>
+
+  affine.for %i = 0 to 64 {
+    // expected-remark@above {{tiled code is illegal in dependence}}
+    affine.for %j = 0 to 64 {
+      %0 = affine.load %A[%j, %i] : memref<64x64xf32>
+      %1 = affine.load %A[%i, %j - 1] : memref<64x64xf32>
+      %2 = addf %0, %1 : f32
+      affine.store %2, %A[%i, %j] : memref<64x64xf32>
+    }
+  }
+
+  return 
+}