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