mlir/test/lib/Analysis/TestMemRefDependenceCheck.cpp

   1 //===- TestMemRefDependenceCheck.cpp - Test dep analysis ------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements a pass to run pair-wise memref access dependence checks.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h"
  14 #include "mlir/Dialect/Affine/Analysis/AffineStructures.h"
  15 #include "mlir/Dialect/Affine/Analysis/Utils.h"
  16 #include "mlir/Dialect/Affine/IR/AffineOps.h"
  17 #include "mlir/IR/Builders.h"
  18 #include "mlir/Pass/Pass.h"
  19 #include "llvm/Support/Debug.h"
  20
  21 #define DEBUG_TYPE "test-memref-dependence-check"
  22
  23 using namespace mlir;
  24
  25 namespace {
  26
  27 // TODO: Add common surrounding loop depth-wise dependence checks.
  28 /// Checks dependences between all pairs of memref accesses in a Function.
  29 struct TestMemRefDependenceCheck
  30     : public PassWrapper<TestMemRefDependenceCheck, OperationPass<>> {
  31   MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestMemRefDependenceCheck)
  32
  33   StringRef getArgument() const final { return "test-memref-dependence-check"; }
  34   StringRef getDescription() const final {
  35     return "Checks dependences between all pairs of memref accesses.";
  36   }
  37   SmallVector<Operation *, 4> loadsAndStores;
  38   void runOnOperation() override;
  39 };
  40
  41 } // namespace
  42
  43 // Returns a result string which represents the direction vector (if there was
  44 // a dependence), returns the string "false" otherwise.
  45 static std::string
  46 getDirectionVectorStr(bool ret, unsigned numCommonLoops, unsigned loopNestDepth,
  47                       ArrayRef<DependenceComponent> dependenceComponents) {
  48   if (!ret)
  49     return "false";
  50   if (dependenceComponents.empty() || loopNestDepth > numCommonLoops)
  51     return "true";
  52   std::string result;
  53   for (const auto &dependenceComponent : dependenceComponents) {
  54     std::string lbStr = "-inf";
  55     if (dependenceComponent.lb.has_value() &&
  56         *dependenceComponent.lb != std::numeric_limits<int64_t>::min())
  57       lbStr = std::to_string(*dependenceComponent.lb);
  58
  59     std::string ubStr = "+inf";
  60     if (dependenceComponent.ub.has_value() &&
  61         *dependenceComponent.ub != std::numeric_limits<int64_t>::max())
  62       ubStr = std::to_string(*dependenceComponent.ub);
  63
  64     result += "[" + lbStr + ", " + ubStr + "]";
  65   }
  66   return result;
  67 }
  68
  69 // For each access in 'loadsAndStores', runs a dependence check between this
  70 // "source" access and all subsequent "destination" accesses in
  71 // 'loadsAndStores'. Emits the result of the dependence check as a note with
  72 // the source access.
  73 static void checkDependences(ArrayRef<Operation *> loadsAndStores) {
  74   for (unsigned i = 0, e = loadsAndStores.size(); i < e; ++i) {
  75     auto *srcOpInst = loadsAndStores[i];
  76     MemRefAccess srcAccess(srcOpInst);
  77     for (unsigned j = 0; j < e; ++j) {
  78       auto *dstOpInst = loadsAndStores[j];
  79       MemRefAccess dstAccess(dstOpInst);
  80
  81       unsigned numCommonLoops =
  82           getNumCommonSurroundingLoops(*srcOpInst, *dstOpInst);
  83       for (unsigned d = 1; d <= numCommonLoops + 1; ++d) {
  84         FlatAffineValueConstraints dependenceConstraints;
  85         SmallVector<DependenceComponent, 2> dependenceComponents;
  86         DependenceResult result = checkMemrefAccessDependence(
  87             srcAccess, dstAccess, d, &dependenceConstraints,
  88             &dependenceComponents);
  89         if (result.value == DependenceResult::Failure) {
  90           srcOpInst->emitError("dependence check failed");
  91         } else {
  92           bool ret = hasDependence(result);
  93           // TODO: Print dependence type (i.e. RAW, etc) and print
  94           // distance vectors as: ([2, 3], [0, 10]). Also, shorten distance
  95           // vectors from ([1, 1], [3, 3]) to (1, 3).
  96           srcOpInst->emitRemark("dependence from ")
  97               << i << " to " << j << " at depth " << d << " = "
  98               << getDirectionVectorStr(ret, numCommonLoops, d,
  99                                        dependenceComponents);
 100         }
 101       }
 102     }
 103   }
 104 }
 105
 106 /// Walks the operation adding load and store ops to 'loadsAndStores'. Runs
 107 /// pair-wise dependence checks.
 108 void TestMemRefDependenceCheck::runOnOperation() {
 109   // Collect the loads and stores within the function.
 110   loadsAndStores.clear();
 111   getOperation()->walk([&](Operation *op) {
 112     if (isa<AffineLoadOp, AffineStoreOp>(op))
 113       loadsAndStores.push_back(op);
 114   });
 115
 116   checkDependences(loadsAndStores);
 117 }
 118
 119 namespace mlir {
 120 namespace test {
 121 void registerTestMemRefDependenceCheck() {
 122   PassRegistration<TestMemRefDependenceCheck>();
 123 }
 124 } // namespace test
 125 } // namespace mlir