1 files changed, 62 insertions, 0 deletions
diff --git a/mlir/lib/Analysis/Utils.cpp b/mlir/lib/Analysis/Utils.cpp
new file mode 100644
index 00000000000..20aac12d5e2
--- /dev/null
+++ b/mlir/lib/Analysis/Utils.cpp
@@ -0,0 +1,62 @@
+//===- Utils.cpp ---- Misc utilities for analysis -------------------------===//
+//
+// Copyright 2019 The MLIR Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+// =============================================================================
+//
+// This file implements miscellaneous analysis routines for non-loop IR
+// structures.
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Analysis/Utils.h"
+
+#include "mlir/IR/Statements.h"
+
+using namespace mlir;
+
+/// Returns true if statement 'a' properly dominates statement b.
+bool mlir::properlyDominates(const Statement &a, const Statement &b) {
+  if (&a == &b)
+    return false;
+
+  if (a.findFunction() != b.findFunction())
+    return false;
+
+  if (a.getBlock() == b.getBlock()) {
+    // Do a linear scan to determine whether b comes after a.
+    auto aIter = StmtBlock::const_iterator(a);
+    auto bIter = StmtBlock::const_iterator(b);
+    auto aBlockStart = a.getBlock()->begin();
+    while (bIter != aBlockStart) {
+      --bIter;
+      if (aIter == bIter)
+        return true;
+    }
+    return false;
+  }
+
+  // Traverse up b's hierarchy to check if b's block is contained in a's.
+  if (const auto *bAncestor = a.getBlock()->findAncestorStmtInBlock(b))
+    // a and bAncestor are in the same block; check if the former dominates it.
+    return dominates(a, *bAncestor);
+
+  // b's block is not contained in A.
+  return false;
+}
+
+/// Returns true if statement A dominates statement B.
+bool mlir::dominates(const Statement &a, const Statement &b) {
+  return &a == &b || properlyDominates(a, b);
+}