1 //===- Liveness.h - Liveness analysis for MLIR ------------------*- 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 contains an analysis for computing liveness information from a 10 // given top-level operation. The current version of the analysis uses a 11 // traditional algorithm to resolve detailed live-range information about all 12 // values within the specified regions. It is also possible to query liveness 13 // information on block level. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #ifndef MLIR_ANALYSIS_LIVENESS_H 18 #define MLIR_ANALYSIS_LIVENESS_H 19 20 #include <vector> 21 22 #include "mlir/Support/LLVM.h" 23 #include "llvm/ADT/ArrayRef.h" 24 #include "llvm/ADT/DenseMap.h" 25 #include "llvm/ADT/SmallPtrSet.h" 26 27 namespace mlir { 28 29 class Block; 30 class LivenessBlockInfo; 31 class Operation; 32 class Region; 33 class Value; 34 35 /// Represents an analysis for computing liveness information from a 36 /// given top-level operation. The analysis iterates over all associated 37 /// regions that are attached to the given top-level operation. It 38 /// computes liveness information for every value and block that are 39 /// included in the mentioned regions. It relies on a fixpoint iteration 40 /// to compute all live-in and live-out values of all included blocks. 41 /// Sample usage: 42 /// Liveness liveness(topLevelOp); 43 /// auto &allInValues = liveness.getLiveIn(block); 44 /// auto &allOutValues = liveness.getLiveOut(block); 45 /// auto allOperationsInWhichValueIsLive = liveness.resolveLiveness(value); 46 /// bool lastUse = liveness.isLastUse(value, operation); 47 class Liveness { 48 public: 49 using OperationListT = std::vector<Operation *>; 50 using BlockMapT = DenseMap<Block *, LivenessBlockInfo>; 51 using ValueSetT = SmallPtrSet<Value, 16>; 52 53 public: 54 /// Creates a new Liveness analysis that computes liveness 55 /// information for all associated regions. 56 Liveness(Operation *op); 57 58 /// Returns the operation this analysis was constructed from. getOperation()59 Operation *getOperation() const { return operation; } 60 61 /// Gets liveness info (if any) for the given value. 62 /// This includes all operations in which the given value is live. 63 /// Note that the operations in this list are not ordered and the current 64 /// implementation is computationally expensive (as it iterates over all 65 /// blocks in which the given value is live). 66 OperationListT resolveLiveness(Value value) const; 67 68 /// Gets liveness info (if any) for the block. 69 const LivenessBlockInfo *getLiveness(Block *block) const; 70 71 /// Returns a reference to a set containing live-in values (unordered). 72 const ValueSetT &getLiveIn(Block *block) const; 73 74 /// Returns a reference to a set containing live-out values (unordered). 75 const ValueSetT &getLiveOut(Block *block) const; 76 77 /// Returns true if the given operation represent the last use of the 78 /// given value. 79 bool isLastUse(Value value, Operation *operation) const; 80 81 /// Dumps the liveness information in a human readable format. 82 void dump() const; 83 84 /// Dumps the liveness information to the given stream. 85 void print(raw_ostream &os) const; 86 87 private: 88 /// Initializes the internal mappings. 89 void build(); 90 91 private: 92 /// The operation this analysis was constructed from. 93 Operation *operation; 94 95 /// Maps blocks to internal liveness information. 96 BlockMapT blockMapping; 97 }; 98 99 /// This class represents liveness information on block level. 100 class LivenessBlockInfo { 101 public: 102 /// A typedef declaration of a value set. 103 using ValueSetT = Liveness::ValueSetT; 104 105 public: 106 /// Returns the underlying block. getBlock()107 Block *getBlock() const { return block; } 108 109 /// Returns all values that are live at the beginning 110 /// of the block (unordered). in()111 const ValueSetT &in() const { return inValues; } 112 113 /// Returns all values that are live at the end 114 /// of the block (unordered). out()115 const ValueSetT &out() const { return outValues; } 116 117 /// Returns true if the given value is in the live-in set. 118 bool isLiveIn(Value value) const; 119 120 /// Returns true if the given value is in the live-out set. 121 bool isLiveOut(Value value) const; 122 123 /// Gets the start operation for the given value. This is the first operation 124 /// the given value is considered to be live. This could either be the start 125 /// operation of the current block (in case the value is live-in) or the 126 /// operation that defines the given value (must be referenced in this block). 127 Operation *getStartOperation(Value value) const; 128 129 /// Gets the end operation for the given value using the start operation 130 /// provided (must be referenced in this block). 131 Operation *getEndOperation(Value value, Operation *startOperation) const; 132 133 private: 134 /// The underlying block. 135 Block *block; 136 137 /// The set of all live in values. 138 ValueSetT inValues; 139 140 /// The set of all live out values. 141 ValueSetT outValues; 142 143 friend class Liveness; 144 }; 145 146 } // end namespace mlir 147 148 #endif // MLIR_ANALYSIS_LIVENESS_H 149