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_ANALYSIS_BUFFERVIEWFLOWANALYSIS_H 10 #define MLIR_ANALYSIS_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 57 /// Removes the given values from all alias sets. 58 void remove(const SmallPtrSetImpl<Value> &aliasValues); 59 60 private: 61 /// This function constructs a mapping from values to its immediate 62 /// dependencies. 63 void build(Operation *op); 64 65 /// Maps values to all immediate dependencies this value can have. 66 ValueMapT dependencies; 67 }; 68 69 } // namespace mlir 70 71 #endif // MLIR_ANALYSIS_BUFFERVIEWFLOWANALYSIS_H 72