blob: cd0f90b411f0a155e5522e1978abb7c383933bb9 [file] [log] [blame]
//===- CSE.cpp - Common Sub-expression Elimination ------------------------===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// This transformation pass performs a simple common sub-expression elimination
// algorithm on operations within a region.
#include "mlir/Transforms/Passes.h"
#include "mlir/IR/Dominance.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
#include "mlir/Pass/Pass.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/ScopedHashTable.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/RecyclingAllocator.h"
#include <deque>
namespace mlir {
#include "mlir/Transforms/"
} // namespace mlir
using namespace mlir;
namespace {
struct SimpleOperationInfo : public llvm::DenseMapInfo<Operation *> {
static unsigned getHashValue(const Operation *opC) {
return OperationEquivalence::computeHash(
const_cast<Operation *>(opC),
static bool isEqual(const Operation *lhsC, const Operation *rhsC) {
auto *lhs = const_cast<Operation *>(lhsC);
auto *rhs = const_cast<Operation *>(rhsC);
if (lhs == rhs)
return true;
if (lhs == getTombstoneKey() || lhs == getEmptyKey() ||
rhs == getTombstoneKey() || rhs == getEmptyKey())
return false;
// If op has no regions, operation equivalence w.r.t operands alone is
// enough.
if (lhs->getNumRegions() == 0 && rhs->getNumRegions() == 0) {
return OperationEquivalence::isEquivalentTo(
const_cast<Operation *>(lhsC), const_cast<Operation *>(rhsC),
// If lhs or rhs does not have a single region with a single block, they
// aren't CSEed for now.
if (lhs->getNumRegions() != 1 || rhs->getNumRegions() != 1 ||
!llvm::hasSingleElement(lhs->getRegion(0)) ||
return false;
// Compare the two blocks.
Block &lhsBlock = lhs->getRegion(0).front();
Block &rhsBlock = rhs->getRegion(0).front();
// Don't CSE if number of arguments differ.
if (lhsBlock.getNumArguments() != rhsBlock.getNumArguments())
return false;
// Map to store `Value`s from `lhsBlock` that are equivalent to `Value`s in
// `rhsBlock`. `Value`s from `lhsBlock` are the key.
DenseMap<Value, Value> areEquivalentValues;
for (auto bbArgs : llvm::zip(lhs->getRegion(0).getArguments(),
rhs->getRegion(0).getArguments())) {
areEquivalentValues[std::get<0>(bbArgs)] = std::get<1>(bbArgs);
// Helper function to get the parent operation.
auto getParent = [](Value v) -> Operation * {
if (auto blockArg = v.dyn_cast<BlockArgument>())
return blockArg.getParentBlock()->getParentOp();
return v.getDefiningOp()->getParentOp();
// Callback to compare if operands of ops in the region of `lhs` and `rhs`
// are equivalent.
auto mapOperands = [&](Value lhsValue, Value rhsValue) -> LogicalResult {
if (lhsValue == rhsValue)
return success();
if (areEquivalentValues.lookup(lhsValue) == rhsValue)
return success();
return failure();
// Callback to compare if results of ops in the region of `lhs` and `rhs`
// are equivalent.
auto mapResults = [&](Value lhsResult, Value rhsResult) -> LogicalResult {
if (getParent(lhsResult) == lhs && getParent(rhsResult) == rhs) {
auto insertion = areEquivalentValues.insert({lhsResult, rhsResult});
return success(insertion.first->second == rhsResult);
return success();
return OperationEquivalence::isEquivalentTo(
const_cast<Operation *>(lhsC), const_cast<Operation *>(rhsC),
mapOperands, mapResults, OperationEquivalence::IgnoreLocations);
} // namespace
namespace {
/// Simple common sub-expression elimination.
struct CSE : public impl::CSEBase<CSE> {
/// Shared implementation of operation elimination and scoped map definitions.
using AllocatorTy = llvm::RecyclingAllocator<
llvm::ScopedHashTableVal<Operation *, Operation *>>;
using ScopedMapTy = llvm::ScopedHashTable<Operation *, Operation *,
SimpleOperationInfo, AllocatorTy>;
/// Cache holding MemoryEffects information between two operations. The first
/// operation is stored has the key. The second operation is stored inside a
/// pair in the value. The pair also hold the MemoryEffects between those
/// two operations. If the MemoryEffects is nullptr then we assume there is
/// no operation with MemoryEffects::Write between the two operations.
using MemEffectsCache =
DenseMap<Operation *, std::pair<Operation *, MemoryEffects::Effect *>>;
/// Represents a single entry in the depth first traversal of a CFG.
struct CFGStackNode {
CFGStackNode(ScopedMapTy &knownValues, DominanceInfoNode *node)
: scope(knownValues), node(node), childIterator(node->begin()) {}
/// Scope for the known values.
ScopedMapTy::ScopeTy scope;
DominanceInfoNode *node;
DominanceInfoNode::const_iterator childIterator;
/// If this node has been fully processed yet or not.
bool processed = false;
/// Attempt to eliminate a redundant operation. Returns success if the
/// operation was marked for removal, failure otherwise.
LogicalResult simplifyOperation(ScopedMapTy &knownValues, Operation *op,
bool hasSSADominance);
void simplifyBlock(ScopedMapTy &knownValues, Block *bb, bool hasSSADominance);
void simplifyRegion(ScopedMapTy &knownValues, Region &region);
void runOnOperation() override;
void replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op,
Operation *existing, bool hasSSADominance);
/// Check if there is side-effecting operations other than the given effect
/// between the two operations.
bool hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp);
/// Operations marked as dead and to be erased.
std::vector<Operation *> opsToErase;
DominanceInfo *domInfo = nullptr;
MemEffectsCache memEffectsCache;
} // namespace
void CSE::replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op,
Operation *existing, bool hasSSADominance) {
// If we find one then replace all uses of the current operation with the
// existing one and mark it for deletion. We can only replace an operand in
// an operation if it has not been visited yet.
if (hasSSADominance) {
// If the region has SSA dominance, then we are guaranteed to have not
// visited any use of the current operation.
} else {
// When the region does not have SSA dominance, we need to check if we
// have visited a use before replacing any use.
for (auto it : llvm::zip(op->getResults(), existing->getResults())) {
std::get<1>(it), [&](OpOperand &operand) {
return !knownValues.count(operand.getOwner());
// There may be some remaining uses of the operation.
if (op->use_empty())
// If the existing operation has an unknown location and the current
// operation doesn't, then set the existing op's location to that of the
// current op.
if (existing->getLoc().isa<UnknownLoc>() && !op->getLoc().isa<UnknownLoc>())
bool CSE::hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp) {
assert(fromOp->getBlock() == toOp->getBlock());
isa<MemoryEffectOpInterface>(fromOp) &&
cast<MemoryEffectOpInterface>(fromOp).hasEffect<MemoryEffects::Read>() &&
isa<MemoryEffectOpInterface>(toOp) &&
Operation *nextOp = fromOp->getNextNode();
auto result =
memEffectsCache.try_emplace(fromOp, std::make_pair(fromOp, nullptr));
if (result.second) {
auto memEffectsCachePair = result.first->second;
if (memEffectsCachePair.second == nullptr) {
// No MemoryEffects::Write has been detected until the cached operation.
// Continue looking from the cached operation to toOp.
nextOp = memEffectsCachePair.first;
} else {
// MemoryEffects::Write has been detected before so there is no need to
// check further.
return true;
while (nextOp && nextOp != toOp) {
auto nextOpMemEffects = dyn_cast<MemoryEffectOpInterface>(nextOp);
// TODO: Do we need to handle other effects generically?
// If the operation does not implement the MemoryEffectOpInterface we
// conservatively assumes it writes.
if ((nextOpMemEffects &&
nextOpMemEffects.hasEffect<MemoryEffects::Write>()) ||
!nextOpMemEffects) {
result.first->second =
std::make_pair(nextOp, MemoryEffects::Write::get());
return true;
nextOp = nextOp->getNextNode();
result.first->second = std::make_pair(toOp, nullptr);
return false;
/// Attempt to eliminate a redundant operation.
LogicalResult CSE::simplifyOperation(ScopedMapTy &knownValues, Operation *op,
bool hasSSADominance) {
// Don't simplify terminator operations.
if (op->hasTrait<OpTrait::IsTerminator>())
return failure();
// If the operation is already trivially dead just add it to the erase list.
if (isOpTriviallyDead(op)) {
return success();
// Don't simplify operations with nested blocks. We don't currently model
// equality comparisons correctly among other things. It is also unclear
// whether we would want to CSE such operations.
if (op->getNumRegions() != 0 &&
(op->getNumRegions() != 1 || !llvm::hasSingleElement(op->getRegion(0))))
return failure();
// Some simple use case of operation with memory side-effect are dealt with
// here. Operations with no side-effect are done after.
if (!isMemoryEffectFree(op)) {
auto memEffects = dyn_cast<MemoryEffectOpInterface>(op);
// TODO: Only basic use case for operations with MemoryEffects::Read can be
// eleminated now. More work needs to be done for more complicated patterns
// and other side-effects.
if (!memEffects || !memEffects.onlyHasEffect<MemoryEffects::Read>())
return failure();
// Look for an existing definition for the operation.
if (auto *existing = knownValues.lookup(op)) {
if (existing->getBlock() == op->getBlock() &&
!hasOtherSideEffectingOpInBetween(existing, op)) {
// The operation that can be deleted has been reach with no
// side-effecting operations in between the existing operation and
// this one so we can remove the duplicate.
replaceUsesAndDelete(knownValues, op, existing, hasSSADominance);
return success();
knownValues.insert(op, op);
return failure();
// Look for an existing definition for the operation.
if (auto *existing = knownValues.lookup(op)) {
replaceUsesAndDelete(knownValues, op, existing, hasSSADominance);
return success();
// Otherwise, we add this operation to the known values map.
knownValues.insert(op, op);
return failure();
void CSE::simplifyBlock(ScopedMapTy &knownValues, Block *bb,
bool hasSSADominance) {
for (auto &op : *bb) {
// Most operations don't have regions, so fast path that case.
if (op.getNumRegions() != 0) {
// If this operation is isolated above, we can't process nested regions
// with the given 'knownValues' map. This would cause the insertion of
// implicit captures in explicit capture only regions.
if (op.mightHaveTrait<OpTrait::IsIsolatedFromAbove>()) {
ScopedMapTy nestedKnownValues;
for (auto &region : op.getRegions())
simplifyRegion(nestedKnownValues, region);
} else {
// Otherwise, process nested regions normally.
for (auto &region : op.getRegions())
simplifyRegion(knownValues, region);
// If the operation is simplified, we don't process any held regions.
if (succeeded(simplifyOperation(knownValues, &op, hasSSADominance)))
// Clear the MemoryEffects cache since its usage is by block only.
void CSE::simplifyRegion(ScopedMapTy &knownValues, Region &region) {
// If the region is empty there is nothing to do.
if (region.empty())
bool hasSSADominance = domInfo->hasSSADominance(&region);
// If the region only contains one block, then simplify it directly.
if (region.hasOneBlock()) {
ScopedMapTy::ScopeTy scope(knownValues);
simplifyBlock(knownValues, &region.front(), hasSSADominance);
// If the region does not have dominanceInfo, then skip it.
// TODO: Regions without SSA dominance should define a different
// traversal order which is appropriate and can be used here.
if (!hasSSADominance)
// Note, deque is being used here because there was significant performance
// gains over vector when the container becomes very large due to the
// specific access patterns. If/when these performance issues are no
// longer a problem we can change this to vector. For more information see
// the llvm mailing list discussion on this:
std::deque<std::unique_ptr<CFGStackNode>> stack;
// Process the nodes of the dom tree for this region.
knownValues, domInfo->getRootNode(&region)));
while (!stack.empty()) {
auto &currentNode = stack.back();
// Check to see if we need to process this node.
if (!currentNode->processed) {
currentNode->processed = true;
simplifyBlock(knownValues, currentNode->node->getBlock(),
// Otherwise, check to see if we need to process a child node.
if (currentNode->childIterator != currentNode->node->end()) {
auto *childNode = *(currentNode->childIterator++);
std::make_unique<CFGStackNode>(knownValues, childNode));
} else {
// Finally, if the node and all of its children have been processed
// then we delete the node.
void CSE::runOnOperation() {
/// A scoped hash table of defining operations within a region.
ScopedMapTy knownValues;
domInfo = &getAnalysis<DominanceInfo>();
Operation *rootOp = getOperation();
for (auto &region : rootOp->getRegions())
simplifyRegion(knownValues, region);
// If no operations were erased, then we mark all analyses as preserved.
if (opsToErase.empty())
return markAllAnalysesPreserved();
/// Erase any operations that were marked as dead during simplification.
for (auto *op : opsToErase)
// We currently don't remove region operations, so mark dominance as
// preserved.
markAnalysesPreserved<DominanceInfo, PostDominanceInfo>();
domInfo = nullptr;
std::unique_ptr<Pass> mlir::createCSEPass() { return std::make_unique<CSE>(); }