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_TRANSFORMS_BUFFERUTILS_H 15 #define MLIR_TRANSFORMS_BUFFERUTILS_H 16 17 #include "mlir/Analysis/BufferAliasAnalysis.h" 18 #include "mlir/Analysis/Liveness.h" 19 #include "mlir/Dialect/StandardOps/IR/Ops.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 28 /// A simple analysis that detects allocation operations. 29 class BufferPlacementAllocs { 30 public: 31 /// Represents a tuple of allocValue and deallocOperation. 32 using AllocEntry = std::tuple<Value, Operation *>; 33 34 /// Represents a list containing all alloc entries. 35 using AllocEntryList = SmallVector<AllocEntry, 8>; 36 37 /// Get the start operation to place the given alloc value within the 38 /// specified placement block. 39 static Operation *getStartOperation(Value allocValue, Block *placementBlock, 40 const Liveness &liveness); 41 42 /// Find an associated dealloc operation that is linked to the given 43 /// allocation node (if any). 44 static Operation *findDealloc(Value allocValue); 45 46 public: 47 /// Initializes the internal list by discovering all supported allocation 48 /// nodes. 49 BufferPlacementAllocs(Operation *op); 50 51 /// Returns the begin iterator to iterate over all allocations. begin()52 AllocEntryList::const_iterator begin() const { return allocs.begin(); } 53 54 /// Returns the end iterator that can be used in combination with begin. end()55 AllocEntryList::const_iterator end() const { return allocs.end(); } 56 57 /// Returns the begin iterator to iterate over all allocations. begin()58 AllocEntryList::iterator begin() { return allocs.begin(); } 59 60 /// Returns the end iterator that can be used in combination with begin. end()61 AllocEntryList::iterator end() { return allocs.end(); } 62 63 /// Registers a new allocation entry. registerAlloc(const AllocEntry & entry)64 void registerAlloc(const AllocEntry &entry) { allocs.push_back(entry); } 65 66 private: 67 /// Searches for and registers all supported allocation entries. 68 void build(Operation *op); 69 70 private: 71 /// Maps allocation nodes to their associated blocks. 72 AllocEntryList allocs; 73 }; 74 75 /// The base class for all BufferPlacement transformations. 76 class BufferPlacementTransformationBase { 77 public: 78 using ValueSetT = BufferAliasAnalysis::ValueSetT; 79 80 /// Finds a common dominator for the given value while taking the positions 81 /// of the values in the value set into account. It supports dominator and 82 /// post-dominator analyses via template arguments. 83 template <typename DominatorT> findCommonDominator(Value value,const ValueSetT & values,const DominatorT & doms)84 static Block *findCommonDominator(Value value, const ValueSetT &values, 85 const DominatorT &doms) { 86 // Start with the current block the value is defined in. 87 Block *dom = value.getParentBlock(); 88 // Iterate over all aliases and their uses to find a safe placement block 89 // according to the given dominator information. 90 for (Value childValue : values) { 91 for (Operation *user : childValue.getUsers()) { 92 // Move upwards in the dominator tree to find an appropriate 93 // dominator block that takes the current use into account. 94 dom = doms.findNearestCommonDominator(dom, user->getBlock()); 95 } 96 // Take values without any users into account. 97 dom = doms.findNearestCommonDominator(dom, childValue.getParentBlock()); 98 } 99 return dom; 100 } 101 102 /// Returns true if the given operation represents a loop by testing whether 103 /// it implements the `LoopLikeOpInterface` or the `RegionBranchOpInterface`. 104 /// In the case of a `RegionBranchOpInterface`, it checks all region-based 105 /// control-flow edges for cycles. 106 static bool isLoop(Operation *op); 107 108 /// Constructs a new operation base using the given root operation. 109 BufferPlacementTransformationBase(Operation *op); 110 111 protected: 112 /// Alias information that can be updated during the insertion of copies. 113 BufferAliasAnalysis aliases; 114 115 /// Stores all internally managed allocations. 116 BufferPlacementAllocs allocs; 117 118 /// The underlying liveness analysis to compute fine grained information 119 /// about alloc and dealloc positions. 120 Liveness liveness; 121 }; 122 123 } // end namespace mlir 124 125 #endif // MLIR_TRANSFORMS_BUFFERUTILS_H 126