1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
//===- DenseAnalysis.cpp - Dense data-flow analysis -----------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "mlir/Analysis/DataFlow/DenseAnalysis.h"
#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
#include "mlir/Interfaces/CallInterfaces.h"
#include "mlir/Interfaces/ControlFlowInterfaces.h"
using namespace mlir;
using namespace mlir::dataflow;
//===----------------------------------------------------------------------===//
// AbstractDenseDataFlowAnalysis
//===----------------------------------------------------------------------===//
LogicalResult AbstractDenseDataFlowAnalysis::initialize(Operation *top) {
// Visit every operation and block.
processOperation(top);
for (Region ®ion : top->getRegions()) {
for (Block &block : region) {
visitBlock(&block);
for (Operation &op : block)
if (failed(initialize(&op)))
return failure();
}
}
return success();
}
LogicalResult AbstractDenseDataFlowAnalysis::visit(ProgramPoint point) {
if (auto *op = point.dyn_cast<Operation *>())
processOperation(op);
else if (auto *block = point.dyn_cast<Block *>())
visitBlock(block);
else
return failure();
return success();
}
void AbstractDenseDataFlowAnalysis::processOperation(Operation *op) {
// If the containing block is not executable, bail out.
if (!getOrCreateFor<Executable>(op, op->getBlock())->isLive())
return;
// Get the dense lattice to update.
AbstractDenseLattice *after = getLattice(op);
// If this op implements region control-flow, then control-flow dictates its
// transfer function.
if (auto branch = dyn_cast<RegionBranchOpInterface>(op))
return visitRegionBranchOperation(op, branch, after);
// If this is a call operation, then join its lattices across known return
// sites.
if (auto call = dyn_cast<CallOpInterface>(op)) {
const auto *predecessors = getOrCreateFor<PredecessorState>(op, call);
// If not all return sites are known, then conservatively assume we can't
// reason about the data-flow.
if (!predecessors->allPredecessorsKnown())
return setToEntryState(after);
for (Operation *predecessor : predecessors->getKnownPredecessors())
join(after, *getLatticeFor(op, predecessor));
return;
}
// Get the dense state before the execution of the op.
const AbstractDenseLattice *before;
if (Operation *prev = op->getPrevNode())
before = getLatticeFor(op, prev);
else
before = getLatticeFor(op, op->getBlock());
// Invoke the operation transfer function.
visitOperationImpl(op, *before, after);
}
void AbstractDenseDataFlowAnalysis::visitBlock(Block *block) {
// If the block is not executable, bail out.
if (!getOrCreateFor<Executable>(block, block)->isLive())
return;
// Get the dense lattice to update.
AbstractDenseLattice *after = getLattice(block);
// The dense lattices of entry blocks are set by region control-flow or the
// callgraph.
if (block->isEntryBlock()) {
// Check if this block is the entry block of a callable region.
auto callable = dyn_cast<CallableOpInterface>(block->getParentOp());
if (callable && callable.getCallableRegion() == block->getParent()) {
const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
// If not all callsites are known, conservatively mark all lattices as
// having reached their pessimistic fixpoints.
if (!callsites->allPredecessorsKnown())
return setToEntryState(after);
for (Operation *callsite : callsites->getKnownPredecessors()) {
// Get the dense lattice before the callsite.
if (Operation *prev = callsite->getPrevNode())
join(after, *getLatticeFor(block, prev));
else
join(after, *getLatticeFor(block, callsite->getBlock()));
}
return;
}
// Check if we can reason about the control-flow.
if (auto branch = dyn_cast<RegionBranchOpInterface>(block->getParentOp()))
return visitRegionBranchOperation(block, branch, after);
// Otherwise, we can't reason about the data-flow.
return setToEntryState(after);
}
// Join the state with the state after the block's predecessors.
for (Block::pred_iterator it = block->pred_begin(), e = block->pred_end();
it != e; ++it) {
// Skip control edges that aren't executable.
Block *predecessor = *it;
if (!getOrCreateFor<Executable>(
block, getProgramPoint<CFGEdge>(predecessor, block))
->isLive())
continue;
// Merge in the state from the predecessor's terminator.
join(after, *getLatticeFor(block, predecessor->getTerminator()));
}
}
void AbstractDenseDataFlowAnalysis::visitRegionBranchOperation(
ProgramPoint point, RegionBranchOpInterface branch,
AbstractDenseLattice *after) {
// Get the terminator predecessors.
const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
assert(predecessors->allPredecessorsKnown() &&
"unexpected unresolved region successors");
for (Operation *op : predecessors->getKnownPredecessors()) {
const AbstractDenseLattice *before;
// If the predecessor is the parent, get the state before the parent.
if (op == branch) {
if (Operation *prev = op->getPrevNode())
before = getLatticeFor(point, prev);
else
before = getLatticeFor(point, op->getBlock());
// Otherwise, get the state after the terminator.
} else {
before = getLatticeFor(point, op);
}
join(after, *before);
}
}
const AbstractDenseLattice *
AbstractDenseDataFlowAnalysis::getLatticeFor(ProgramPoint dependent,
ProgramPoint point) {
AbstractDenseLattice *state = getLattice(point);
addDependency(state, dependent);
return state;
}
|
