1//===- LivenessAnalysis.h - Liveness 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// This file implements liveness analysis using the sparse backward data-flow
10// analysis framework. Theoretically, liveness analysis assigns liveness to each
11// (value, program point) pair in the program and it is thus a dense analysis.
12// However, since values are immutable in MLIR, a sparse analysis, which will
13// assign liveness to each value in the program, suffices here.
14//
15// Liveness analysis has many applications. It can be used to avoid the
16// computation of extraneous operations that have no effect on the memory or the
17// final output of a program. It can also be used to optimize register
18// allocation. Both of these applications help achieve one very important goal:
19// reducing runtime.
20//
21//===----------------------------------------------------------------------===//
22
23#ifndef MLIR_ANALYSIS_DATAFLOW_LIVENESSANALYSIS_H
24#define MLIR_ANALYSIS_DATAFLOW_LIVENESSANALYSIS_H
25
26#include <mlir/Analysis/DataFlow/SparseAnalysis.h>
27#include <optional>
28
29namespace mlir::dataflow {
30
31//===----------------------------------------------------------------------===//
32// Liveness
33//===----------------------------------------------------------------------===//
34
35/// This lattice represents, for a given value, whether or not it is "live".
36///
37/// A value is considered "live" iff it:
38/// (1) has memory effects OR
39/// (2) is returned by a public function OR
40/// (3) is used to compute a value of type (1) or (2).
41/// It is also to be noted that a value could be of multiple types (1/2/3) at
42/// the same time.
43///
44/// A value "has memory effects" iff it:
45/// (1.a) is an operand of an op with memory effects OR
46/// (1.b) is a non-forwarded branch operand and its branch op could take the
47/// control to a block that has an op with memory effects OR
48/// (1.c) is a non-forwarded call operand.
49///
50/// A value `A` is said to be "used to compute" value `B` iff `B` cannot be
51/// computed in the absence of `A`. Thus, in this implementation, we say that
52/// value `A` is used to compute value `B` iff:
53/// (3.a) `B` is a result of an op with operand `A` OR
54/// (3.b) `A` is used to compute some value `C` and `C` is used to compute
55/// `B`.
56struct Liveness : public AbstractSparseLattice {
57 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(Liveness)
58 using AbstractSparseLattice::AbstractSparseLattice;
59
60 void print(raw_ostream &os) const override;
61
62 ChangeResult markLive();
63
64 ChangeResult meet(const AbstractSparseLattice &other) override;
65
66 // At the beginning of the analysis, everything is marked "not live" and as
67 // the analysis progresses, values are marked "live" if they are found to be
68 // live.
69 bool isLive = false;
70};
71
72//===----------------------------------------------------------------------===//
73// LivenessAnalysis
74//===----------------------------------------------------------------------===//
75
76/// An analysis that, by going backwards along the dataflow graph, annotates
77/// each value with a boolean storing true iff it is "live".
78class LivenessAnalysis : public SparseBackwardDataFlowAnalysis<Liveness> {
79public:
80 using SparseBackwardDataFlowAnalysis::SparseBackwardDataFlowAnalysis;
81
82 LogicalResult visitOperation(Operation *op, ArrayRef<Liveness *> operands,
83 ArrayRef<const Liveness *> results) override;
84
85 void visitBranchOperand(OpOperand &operand) override;
86
87 void visitCallOperand(OpOperand &operand) override;
88
89 void setToExitState(Liveness *lattice) override;
90};
91
92//===----------------------------------------------------------------------===//
93// RunLivenessAnalysis
94//===----------------------------------------------------------------------===//
95
96/// Runs liveness analysis on the IR defined by `op`.
97struct RunLivenessAnalysis {
98public:
99 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(RunLivenessAnalysis)
100
101 RunLivenessAnalysis(Operation *op);
102
103 const Liveness *getLiveness(Value val);
104
105private:
106 /// Stores the result of the liveness analysis that was run.
107 DataFlowSolver solver;
108};
109
110} // end namespace mlir::dataflow
111
112#endif // MLIR_ANALYSIS_DATAFLOW_LIVENESSANALYSIS_H
113

source code of mlir/include/mlir/Analysis/DataFlow/LivenessAnalysis.h