1 //===- BufferViewFlowAnalysis.h - Buffer dependency analysis ---*- 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 #ifndef MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_BUFFERVIEWFLOWANALYSIS_H 10 #define MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_BUFFERVIEWFLOWANALYSIS_H 11 12 #include "mlir/IR/Operation.h" 13 #include "llvm/ADT/SmallPtrSet.h" 14 15 namespace mlir { 16 17 /// A straight-forward alias analysis which ensures that all dependencies of all 18 /// values will be determined. This is a requirement for the BufferPlacement 19 /// class since you need to determine safe positions to place alloc and 20 /// deallocs. This alias analysis only finds aliases that might have been 21 /// created on top of the specified view. To find all aliases, resolve the 22 /// intial alloc/argument value. 23 class BufferViewFlowAnalysis { 24 public: 25 using ValueSetT = SmallPtrSet<Value, 16>; 26 using ValueMapT = llvm::DenseMap<Value, ValueSetT>; 27 28 /// Constructs a new alias analysis using the op provided. 29 BufferViewFlowAnalysis(Operation *op); 30 31 /// Find all immediate dependencies this value could potentially have. find(Value value)32 ValueMapT::const_iterator find(Value value) const { 33 return dependencies.find(value); 34 } 35 36 /// Returns the begin iterator to iterate over all dependencies. begin()37 ValueMapT::const_iterator begin() const { return dependencies.begin(); } 38 39 /// Returns the end iterator that can be used in combination with find. end()40 ValueMapT::const_iterator end() const { return dependencies.end(); } 41 42 /// Find all immediate and indirect views upon this value. This will find all 43 /// dependencies on this value that can potentially be later in the execution 44 /// of the program, but will not return values that this alias might have been 45 /// created from (such as if the value is created by a subview, this will not 46 /// return the parent view if there is no cyclic behavior). Note that the 47 /// resulting set will also contain the value provided as it is an alias of 48 /// itself. 49 /// 50 /// A = * 51 /// B = subview(A) 52 /// C = B 53 /// 54 /// Results in resolve(B) returning {B, C} 55 ValueSetT resolve(Value value) const; 56 ValueSetT resolveReverse(Value value) const; 57 58 /// Removes the given values from all alias sets. 59 void remove(const SetVector<Value> &aliasValues); 60 61 /// Replaces all occurrences of 'from' in the internal datastructures with 62 /// 'to'. This is useful when the defining operation of a value has to be 63 /// re-built because additional results have to be added or the types of 64 /// results have to be changed. 65 void rename(Value from, Value to); 66 67 /// Returns "true" if the given value may be a terminal. 68 bool mayBeTerminalBuffer(Value value) const; 69 70 private: 71 /// This function constructs a mapping from values to its immediate 72 /// dependencies. 73 void build(Operation *op); 74 75 /// Maps values to all immediate dependencies this value can have. 76 ValueMapT dependencies; 77 ValueMapT reverseDependencies; 78 79 /// A set of all SSA values that may be terminal buffers. 80 DenseSet<Value> terminals; 81 }; 82 83 /// An is-same-buffer analysis that checks if two SSA values belong to the same 84 /// buffer allocation or not. 85 class BufferOriginAnalysis { 86 public: 87 BufferOriginAnalysis(Operation *op); 88 89 /// Return "true" if `v1` and `v2` originate from the same buffer allocation. 90 /// Return "false" if `v1` and `v2` originate from different allocations. 91 /// Return "nullopt" if we do not know for sure. 92 /// 93 /// Example 1: isSameAllocation(%0, %1) == true 94 /// ``` 95 /// %0 = memref.alloc() 96 /// %1 = memref.subview %0 97 /// ``` 98 /// 99 /// Example 2: isSameAllocation(%0, %1) == false 100 /// ``` 101 /// %0 = memref.alloc() 102 /// %1 = memref.alloc() 103 /// ``` 104 /// 105 /// Example 3: isSameAllocation(%0, %2) == nullopt 106 /// ``` 107 /// %0 = memref.alloc() 108 /// %1 = memref.alloc() 109 /// %2 = arith.select %c, %0, %1 110 /// ``` 111 std::optional<bool> isSameAllocation(Value v1, Value v2); 112 113 private: 114 BufferViewFlowAnalysis analysis; 115 }; 116 117 } // namespace mlir 118 119 #endif // MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_BUFFERVIEWFLOWANALYSIS_H 120