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