1 //===- BufferUtils.h - Buffer optimization utilities ------------*- C++ -*-===//
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 provides utilities for passes optimizing code that has already
10 // been converted to buffers.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_BUFFERUTILS_H
15 #define MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_BUFFERUTILS_H
16 
17 #include "mlir/Analysis/BufferViewFlowAnalysis.h"
18 #include "mlir/Analysis/Liveness.h"
19 #include "mlir/Dialect/Arithmetic/IR/Arithmetic.h"
20 #include "mlir/IR/Builders.h"
21 #include "mlir/IR/BuiltinOps.h"
22 #include "mlir/IR/Dominance.h"
23 #include "mlir/IR/Operation.h"
24 #include "mlir/Transforms/DialectConversion.h"
25 
26 namespace mlir {
27 namespace memref {
28 class GlobalOp;
29 } // namespace memref
30 
31 namespace bufferization {
32 
33 /// A simple analysis that detects allocation operations.
34 class BufferPlacementAllocs {
35 public:
36   /// Represents a tuple of allocValue and deallocOperation.
37   using AllocEntry = std::tuple<Value, Operation *>;
38 
39   /// Represents a list containing all alloc entries.
40   using AllocEntryList = SmallVector<AllocEntry, 8>;
41 
42   /// Get the start operation to place the given alloc value within the
43   /// specified placement block.
44   static Operation *getStartOperation(Value allocValue, Block *placementBlock,
45                                       const Liveness &liveness);
46 
47 public:
48   /// Initializes the internal list by discovering all supported allocation
49   /// nodes.
50   BufferPlacementAllocs(Operation *op);
51 
52   /// Returns the begin iterator to iterate over all allocations.
begin()53   AllocEntryList::const_iterator begin() const { return allocs.begin(); }
54 
55   /// Returns the end iterator that can be used in combination with begin.
end()56   AllocEntryList::const_iterator end() const { return allocs.end(); }
57 
58   /// Returns the begin iterator to iterate over all allocations.
begin()59   AllocEntryList::iterator begin() { return allocs.begin(); }
60 
61   /// Returns the end iterator that can be used in combination with begin.
end()62   AllocEntryList::iterator end() { return allocs.end(); }
63 
64   /// Registers a new allocation entry.
registerAlloc(const AllocEntry & entry)65   void registerAlloc(const AllocEntry &entry) { allocs.push_back(entry); }
66 
67 private:
68   /// Searches for and registers all supported allocation entries.
69   void build(Operation *op);
70 
71 private:
72   /// Maps allocation nodes to their associated blocks.
73   AllocEntryList allocs;
74 };
75 
76 /// The base class for all BufferPlacement transformations.
77 class BufferPlacementTransformationBase {
78 public:
79   using ValueSetT = BufferViewFlowAnalysis::ValueSetT;
80 
81   /// Finds a common dominator for the given value while taking the positions
82   /// of the values in the value set into account. It supports dominator and
83   /// post-dominator analyses via template arguments.
84   template <typename DominatorT>
findCommonDominator(Value value,const ValueSetT & values,const DominatorT & doms)85   static Block *findCommonDominator(Value value, const ValueSetT &values,
86                                     const DominatorT &doms) {
87     // Start with the current block the value is defined in.
88     Block *dom = value.getParentBlock();
89     // Iterate over all aliases and their uses to find a safe placement block
90     // according to the given dominator information.
91     for (Value childValue : values) {
92       for (Operation *user : childValue.getUsers()) {
93         // Move upwards in the dominator tree to find an appropriate
94         // dominator block that takes the current use into account.
95         dom = doms.findNearestCommonDominator(dom, user->getBlock());
96       }
97       // Take values without any users into account.
98       dom = doms.findNearestCommonDominator(dom, childValue.getParentBlock());
99     }
100     return dom;
101   }
102 
103   /// Returns true if the given operation represents a loop by testing whether
104   /// it implements the `LoopLikeOpInterface` or the `RegionBranchOpInterface`.
105   /// In the case of a `RegionBranchOpInterface`, it checks all region-based
106   /// control-flow edges for cycles.
107   static bool isLoop(Operation *op);
108 
109   /// Constructs a new operation base using the given root operation.
110   BufferPlacementTransformationBase(Operation *op);
111 
112 protected:
113   /// Alias information that can be updated during the insertion of copies.
114   BufferViewFlowAnalysis aliases;
115 
116   /// Stores all internally managed allocations.
117   BufferPlacementAllocs allocs;
118 
119   /// The underlying liveness analysis to compute fine grained information
120   /// about alloc and dealloc positions.
121   Liveness liveness;
122 };
123 
124 // Create a global op for the given tensor-valued constant in the program.
125 // Globals are created lazily at the top of the enclosing ModuleOp with pretty
126 // names. Duplicates are avoided.
127 FailureOr<memref::GlobalOp> getGlobalFor(arith::ConstantOp constantOp,
128                                          uint64_t alignment);
129 
130 } // namespace bufferization
131 } // namespace mlir
132 
133 #endif // MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_BUFFERUTILS_H
134