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 isDeafAfter = liveness.isDeadAfter(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 `value` is not live after `operation`.
78   bool isDeadAfter(Value value, Operation *operation) const;
79 
80   /// Dumps the liveness information in a human readable format.
81   void dump() const;
82 
83   /// Dumps the liveness information to the given stream.
84   void print(raw_ostream &os) const;
85 
86 private:
87   /// Initializes the internal mappings.
88   void build();
89 
90 private:
91   /// The operation this analysis was constructed from.
92   Operation *operation;
93 
94   /// Maps blocks to internal liveness information.
95   BlockMapT blockMapping;
96 };
97 
98 /// This class represents liveness information on block level.
99 class LivenessBlockInfo {
100 public:
101   /// A typedef declaration of a value set.
102   using ValueSetT = Liveness::ValueSetT;
103 
104 public:
105   /// Returns the underlying block.
getBlock()106   Block *getBlock() const { return block; }
107 
108   /// Returns all values that are live at the beginning
109   /// of the block (unordered).
in()110   const ValueSetT &in() const { return inValues; }
111 
112   /// Returns all values that are live at the end
113   /// of the block (unordered).
out()114   const ValueSetT &out() const { return outValues; }
115 
116   /// Returns true if the given value is in the live-in set.
117   bool isLiveIn(Value value) const;
118 
119   /// Returns true if the given value is in the live-out set.
120   bool isLiveOut(Value value) const;
121 
122   /// Gets the start operation for the given value. This is the first operation
123   /// the given value is considered to be live. This could either be the start
124   /// operation of the current block (in case the value is live-in) or the
125   /// operation that defines the given value (must be referenced in this block).
126   Operation *getStartOperation(Value value) const;
127 
128   /// Gets the end operation for the given value using the start operation
129   /// provided (must be referenced in this block).
130   Operation *getEndOperation(Value value, Operation *startOperation) const;
131 
132 private:
133   /// The underlying block.
134   Block *block;
135 
136   /// The set of all live in values.
137   ValueSetT inValues;
138 
139   /// The set of all live out values.
140   ValueSetT outValues;
141 
142   friend class Liveness;
143 };
144 
145 } // end namespace mlir
146 
147 #endif // MLIR_ANALYSIS_LIVENESS_H
148