1 //===- SymbolDCE.cpp - Pass to delete dead symbols ------------------------===//
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 an algorithm for eliminating symbol operations that are
10 // known to be dead.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "PassDetail.h"
15 #include "mlir/Transforms/Passes.h"
16
17 using namespace mlir;
18
19 namespace {
20 struct SymbolDCE : public SymbolDCEBase<SymbolDCE> {
21 void runOnOperation() override;
22
23 /// Compute the liveness of the symbols within the given symbol table.
24 /// `symbolTableIsHidden` is true if this symbol table is known to be
25 /// unaccessible from operations in its parent regions.
26 LogicalResult computeLiveness(Operation *symbolTableOp,
27 SymbolTableCollection &symbolTable,
28 bool symbolTableIsHidden,
29 DenseSet<Operation *> &liveSymbols);
30 };
31 } // end anonymous namespace
32
runOnOperation()33 void SymbolDCE::runOnOperation() {
34 Operation *symbolTableOp = getOperation();
35
36 // SymbolDCE should only be run on operations that define a symbol table.
37 if (!symbolTableOp->hasTrait<OpTrait::SymbolTable>()) {
38 symbolTableOp->emitOpError()
39 << " was scheduled to run under SymbolDCE, but does not define a "
40 "symbol table";
41 return signalPassFailure();
42 }
43
44 // A flag that signals if the top level symbol table is hidden, i.e. not
45 // accessible from parent scopes.
46 bool symbolTableIsHidden = true;
47 SymbolOpInterface symbol = dyn_cast<SymbolOpInterface>(symbolTableOp);
48 if (symbolTableOp->getParentOp() && symbol)
49 symbolTableIsHidden = symbol.isPrivate();
50
51 // Compute the set of live symbols within the symbol table.
52 DenseSet<Operation *> liveSymbols;
53 SymbolTableCollection symbolTable;
54 if (failed(computeLiveness(symbolTableOp, symbolTable, symbolTableIsHidden,
55 liveSymbols)))
56 return signalPassFailure();
57
58 // After computing the liveness, delete all of the symbols that were found to
59 // be dead.
60 symbolTableOp->walk([&](Operation *nestedSymbolTable) {
61 if (!nestedSymbolTable->hasTrait<OpTrait::SymbolTable>())
62 return;
63 for (auto &block : nestedSymbolTable->getRegion(0)) {
64 for (Operation &op : llvm::make_early_inc_range(block)) {
65 if (isa<SymbolOpInterface>(&op) && !liveSymbols.count(&op))
66 op.erase();
67 }
68 }
69 });
70 }
71
72 /// Compute the liveness of the symbols within the given symbol table.
73 /// `symbolTableIsHidden` is true if this symbol table is known to be
74 /// unaccessible from operations in its parent regions.
computeLiveness(Operation * symbolTableOp,SymbolTableCollection & symbolTable,bool symbolTableIsHidden,DenseSet<Operation * > & liveSymbols)75 LogicalResult SymbolDCE::computeLiveness(Operation *symbolTableOp,
76 SymbolTableCollection &symbolTable,
77 bool symbolTableIsHidden,
78 DenseSet<Operation *> &liveSymbols) {
79 // A worklist of live operations to propagate uses from.
80 SmallVector<Operation *, 16> worklist;
81
82 // Walk the symbols within the current symbol table, marking the symbols that
83 // are known to be live.
84 for (auto &block : symbolTableOp->getRegion(0)) {
85 // Add all non-symbols or symbols that can't be discarded.
86 for (Operation &op : block) {
87 SymbolOpInterface symbol = dyn_cast<SymbolOpInterface>(&op);
88 if (!symbol) {
89 worklist.push_back(&op);
90 continue;
91 }
92 bool isDiscardable = (symbolTableIsHidden || symbol.isPrivate()) &&
93 symbol.canDiscardOnUseEmpty();
94 if (!isDiscardable && liveSymbols.insert(&op).second)
95 worklist.push_back(&op);
96 }
97 }
98
99 // Process the set of symbols that were known to be live, adding new symbols
100 // that are referenced within.
101 while (!worklist.empty()) {
102 Operation *op = worklist.pop_back_val();
103
104 // If this is a symbol table, recursively compute its liveness.
105 if (op->hasTrait<OpTrait::SymbolTable>()) {
106 // The internal symbol table is hidden if the parent is, if its not a
107 // symbol, or if it is a private symbol.
108 SymbolOpInterface symbol = dyn_cast<SymbolOpInterface>(op);
109 bool symIsHidden = symbolTableIsHidden || !symbol || symbol.isPrivate();
110 if (failed(computeLiveness(op, symbolTable, symIsHidden, liveSymbols)))
111 return failure();
112 }
113
114 // Collect the uses held by this operation.
115 Optional<SymbolTable::UseRange> uses = SymbolTable::getSymbolUses(op);
116 if (!uses) {
117 return op->emitError()
118 << "operation contains potentially unknown symbol table, "
119 "meaning that we can't reliable compute symbol uses";
120 }
121
122 SmallVector<Operation *, 4> resolvedSymbols;
123 for (const SymbolTable::SymbolUse &use : *uses) {
124 // Lookup the symbols referenced by this use.
125 resolvedSymbols.clear();
126 if (failed(symbolTable.lookupSymbolIn(
127 op->getParentOp(), use.getSymbolRef(), resolvedSymbols))) {
128 return use.getUser()->emitError()
129 << "unable to resolve reference to symbol "
130 << use.getSymbolRef();
131 }
132
133 // Mark each of the resolved symbols as live.
134 for (Operation *resolvedSymbol : resolvedSymbols)
135 if (liveSymbols.insert(resolvedSymbol).second)
136 worklist.push_back(resolvedSymbol);
137 }
138 }
139
140 return success();
141 }
142
createSymbolDCEPass()143 std::unique_ptr<Pass> mlir::createSymbolDCEPass() {
144 return std::make_unique<SymbolDCE>();
145 }
146