1 //===- CSE.cpp - Common Sub-expression Elimination ------------------------===//
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 transformation pass performs a simple common sub-expression elimination
10 // algorithm on operations within a region.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "PassDetail.h"
15 #include "mlir/Analysis/Dominance.h"
16 #include "mlir/Pass/Pass.h"
17 #include "mlir/Transforms/Passes.h"
18 #include "mlir/Transforms/Utils.h"
19 #include "llvm/ADT/DenseMapInfo.h"
20 #include "llvm/ADT/Hashing.h"
21 #include "llvm/ADT/ScopedHashTable.h"
22 #include "llvm/Support/Allocator.h"
23 #include "llvm/Support/RecyclingAllocator.h"
24 #include <deque>
25 
26 using namespace mlir;
27 
28 namespace {
29 // TODO(riverriddle) Handle commutative operations.
30 struct SimpleOperationInfo : public llvm::DenseMapInfo<Operation *> {
31   static unsigned getHashValue(const Operation *opC) {
32     auto *op = const_cast<Operation *>(opC);
33     // Hash the operations based upon their:
34     //   - Operation Name
35     //   - Attributes
36     //   - Result Types
37     //   - Operands
38     return llvm::hash_combine(
39         op->getName(), op->getAttrList().getDictionary(), op->getResultTypes(),
40         llvm::hash_combine_range(op->operand_begin(), op->operand_end()));
41   }
42   static bool isEqual(const Operation *lhsC, const Operation *rhsC) {
43     auto *lhs = const_cast<Operation *>(lhsC);
44     auto *rhs = const_cast<Operation *>(rhsC);
45     if (lhs == rhs)
46       return true;
47     if (lhs == getTombstoneKey() || lhs == getEmptyKey() ||
48         rhs == getTombstoneKey() || rhs == getEmptyKey())
49       return false;
50 
51     // Compare the operation name.
52     if (lhs->getName() != rhs->getName())
53       return false;
54     // Check operand and result type counts.
55     if (lhs->getNumOperands() != rhs->getNumOperands() ||
56         lhs->getNumResults() != rhs->getNumResults())
57       return false;
58     // Compare attributes.
59     if (lhs->getAttrList() != rhs->getAttrList())
60       return false;
61     // Compare operands.
62     if (!std::equal(lhs->operand_begin(), lhs->operand_end(),
63                     rhs->operand_begin()))
64       return false;
65     // Compare result types.
66     return std::equal(lhs->result_type_begin(), lhs->result_type_end(),
67                       rhs->result_type_begin());
68   }
69 };
70 } // end anonymous namespace
71 
72 namespace {
73 /// Simple common sub-expression elimination.
74 struct CSE : public CSEBase<CSE> {
75   /// Shared implementation of operation elimination and scoped map definitions.
76   using AllocatorTy = llvm::RecyclingAllocator<
77       llvm::BumpPtrAllocator,
78       llvm::ScopedHashTableVal<Operation *, Operation *>>;
79   using ScopedMapTy = llvm::ScopedHashTable<Operation *, Operation *,
80                                             SimpleOperationInfo, AllocatorTy>;
81 
82   /// Represents a single entry in the depth first traversal of a CFG.
83   struct CFGStackNode {
84     CFGStackNode(ScopedMapTy &knownValues, DominanceInfoNode *node)
85         : scope(knownValues), node(node), childIterator(node->begin()),
86           processed(false) {}
87 
88     /// Scope for the known values.
89     ScopedMapTy::ScopeTy scope;
90 
91     DominanceInfoNode *node;
92     DominanceInfoNode::iterator childIterator;
93 
94     /// If this node has been fully processed yet or not.
95     bool processed;
96   };
97 
98   /// Attempt to eliminate a redundant operation. Returns success if the
99   /// operation was marked for removal, failure otherwise.
100   LogicalResult simplifyOperation(ScopedMapTy &knownValues, Operation *op);
101 
102   void simplifyBlock(ScopedMapTy &knownValues, DominanceInfo &domInfo,
103                      Block *bb);
104   void simplifyRegion(ScopedMapTy &knownValues, DominanceInfo &domInfo,
105                       Region &region);
106 
107   void runOnOperation() override;
108 
109 private:
110   /// Operations marked as dead and to be erased.
111   std::vector<Operation *> opsToErase;
112 };
113 } // end anonymous namespace
114 
115 /// Attempt to eliminate a redundant operation.
116 LogicalResult CSE::simplifyOperation(ScopedMapTy &knownValues, Operation *op) {
117   // Don't simplify terminator operations.
118   if (op->isKnownTerminator())
119     return failure();
120 
121   // If the operation is already trivially dead just add it to the erase list.
122   if (isOpTriviallyDead(op)) {
123     opsToErase.push_back(op);
124     ++numDCE;
125     return success();
126   }
127 
128   // Don't simplify operations with nested blocks. We don't currently model
129   // equality comparisons correctly among other things. It is also unclear
130   // whether we would want to CSE such operations.
131   if (op->getNumRegions() != 0)
132     return failure();
133 
134   // TODO(riverriddle) We currently only eliminate non side-effecting
135   // operations.
136   if (!MemoryEffectOpInterface::hasNoEffect(op))
137     return failure();
138 
139   // Look for an existing definition for the operation.
140   if (auto *existing = knownValues.lookup(op)) {
141     // If we find one then replace all uses of the current operation with the
142     // existing one and mark it for deletion.
143     op->replaceAllUsesWith(existing);
144     opsToErase.push_back(op);
145 
146     // If the existing operation has an unknown location and the current
147     // operation doesn't, then set the existing op's location to that of the
148     // current op.
149     if (existing->getLoc().isa<UnknownLoc>() &&
150         !op->getLoc().isa<UnknownLoc>()) {
151       existing->setLoc(op->getLoc());
152     }
153 
154     ++numCSE;
155     return success();
156   }
157 
158   // Otherwise, we add this operation to the known values map.
159   knownValues.insert(op, op);
160   return failure();
161 }
162 
163 void CSE::simplifyBlock(ScopedMapTy &knownValues, DominanceInfo &domInfo,
164                         Block *bb) {
165   for (auto &inst : *bb) {
166     // If the operation is simplified, we don't process any held regions.
167     if (succeeded(simplifyOperation(knownValues, &inst)))
168       continue;
169 
170     // If this operation is isolated above, we can't process nested regions with
171     // the given 'knownValues' map. This would cause the insertion of implicit
172     // captures in explicit capture only regions.
173     if (!inst.isRegistered() || inst.isKnownIsolatedFromAbove()) {
174       ScopedMapTy nestedKnownValues;
175       for (auto &region : inst.getRegions())
176         simplifyRegion(nestedKnownValues, domInfo, region);
177       continue;
178     }
179 
180     // Otherwise, process nested regions normally.
181     for (auto &region : inst.getRegions())
182       simplifyRegion(knownValues, domInfo, region);
183   }
184 }
185 
186 void CSE::simplifyRegion(ScopedMapTy &knownValues, DominanceInfo &domInfo,
187                          Region &region) {
188   // If the region is empty there is nothing to do.
189   if (region.empty())
190     return;
191 
192   // If the region only contains one block, then simplify it directly.
193   if (std::next(region.begin()) == region.end()) {
194     ScopedMapTy::ScopeTy scope(knownValues);
195     simplifyBlock(knownValues, domInfo, &region.front());
196     return;
197   }
198 
199   // Note, deque is being used here because there was significant performance
200   // gains over vector when the container becomes very large due to the
201   // specific access patterns. If/when these performance issues are no
202   // longer a problem we can change this to vector. For more information see
203   // the llvm mailing list discussion on this:
204   // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
205   std::deque<std::unique_ptr<CFGStackNode>> stack;
206 
207   // Process the nodes of the dom tree for this region.
208   stack.emplace_back(std::make_unique<CFGStackNode>(
209       knownValues, domInfo.getRootNode(&region)));
210 
211   while (!stack.empty()) {
212     auto &currentNode = stack.back();
213 
214     // Check to see if we need to process this node.
215     if (!currentNode->processed) {
216       currentNode->processed = true;
217       simplifyBlock(knownValues, domInfo, currentNode->node->getBlock());
218     }
219 
220     // Otherwise, check to see if we need to process a child node.
221     if (currentNode->childIterator != currentNode->node->end()) {
222       auto *childNode = *(currentNode->childIterator++);
223       stack.emplace_back(
224           std::make_unique<CFGStackNode>(knownValues, childNode));
225     } else {
226       // Finally, if the node and all of its children have been processed
227       // then we delete the node.
228       stack.pop_back();
229     }
230   }
231 }
232 
233 void CSE::runOnOperation() {
234   /// A scoped hash table of defining operations within a region.
235   ScopedMapTy knownValues;
236 
237   DominanceInfo &domInfo = getAnalysis<DominanceInfo>();
238   for (Region &region : getOperation()->getRegions())
239     simplifyRegion(knownValues, domInfo, region);
240 
241   // If no operations were erased, then we mark all analyses as preserved.
242   if (opsToErase.empty())
243     return markAllAnalysesPreserved();
244 
245   /// Erase any operations that were marked as dead during simplification.
246   for (auto *op : opsToErase)
247     op->erase();
248   opsToErase.clear();
249 
250   // We currently don't remove region operations, so mark dominance as
251   // preserved.
252   markAnalysesPreserved<DominanceInfo, PostDominanceInfo>();
253 }
254 
255 std::unique_ptr<Pass> mlir::createCSEPass() { return std::make_unique<CSE>(); }
256