RemoveDeadValues.cpp | Explore in Territory

//===- RemoveDeadValues.cpp - Remove Dead Values --------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// The goal of this pass is optimization (reducing runtime) by removing
// unnecessary instructions. Unlike other passes that rely on local information
// gathered from patterns to accomplish optimization, this pass uses a full
// analysis of the IR, specifically, liveness analysis, and is thus more
// powerful.
//
// Currently, this pass performs the following optimizations:
// (A) Removes function arguments that are not live,
// (B) Removes function return values that are not live across all callers of
// the function,
// (C) Removes unneccesary operands, results, region arguments, and region
// terminator operands of region branch ops, and,
// (D) Removes simple and region branch ops that have all non-live results and
// don't affect memory in any way,
//
// iff
//
// the IR doesn't have any non-function symbol ops, non-call symbol user ops and
// branch ops.
//
// Here, a "simple op" refers to an op that isn't a symbol op, symbol-user op,
// region branch op, branch op, region branch terminator op, or return-like.
//
//===----------------------------------------------------------------------===//

#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
#include "mlir/Analysis/DataFlow/LivenessAnalysis.h"
#include "mlir/IR/Attributes.h"
#include "mlir/IR/Builders.h"
#include "mlir/IR/BuiltinAttributes.h"
#include "mlir/IR/Dialect.h"
#include "mlir/IR/IRMapping.h"
#include "mlir/IR/OperationSupport.h"
#include "mlir/IR/SymbolTable.h"
#include "mlir/IR/Value.h"
#include "mlir/IR/ValueRange.h"
#include "mlir/IR/Visitors.h"
#include "mlir/Interfaces/CallInterfaces.h"
#include "mlir/Interfaces/ControlFlowInterfaces.h"
#include "mlir/Interfaces/FunctionInterfaces.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
#include "mlir/Pass/Pass.h"
#include "mlir/Support/LLVM.h"
#include "mlir/Transforms/FoldUtils.h"
#include "mlir/Transforms/Passes.h"
#include "llvm/ADT/STLExtras.h"
#include <cassert>
#include <cstddef>
#include <memory>
#include <optional>
#include <vector>

namespace mlir {
#define GEN_PASS_DEF_REMOVEDEADVALUES
#include "mlir/Transforms/Passes.h.inc"
} // namespace mlir

usingnamespacemlir;
usingnamespacemlir::dataflow;

//===----------------------------------------------------------------------===//
// RemoveDeadValues Pass
//===----------------------------------------------------------------------===//

namespace {

// Some helper functions...

/// Return true iff at least one value in `values` is live, given the liveness
/// information in `la`.
static bool hasLive(ValueRange values, RunLivenessAnalysis &la) { … }

/// Return a BitVector of size `values.size()` where its i-th bit is 1 iff the
/// i-th value in `values` is live, given the liveness information in `la`.
static BitVector markLives(ValueRange values, RunLivenessAnalysis &la) { … }

/// Drop the uses of the i-th result of `op` and then erase it iff toErase[i]
/// is 1.
static void dropUsesAndEraseResults(Operation *op, BitVector toErase) { … }

/// Convert a list of `Operand`s to a list of `OpOperand`s.
static SmallVector<OpOperand *> operandsToOpOperands(OperandRange operands) { … }

/// Clean a simple op `op`, given the liveness analysis information in `la`.
/// Here, cleaning means:
///   (1) Dropping all its uses, AND
///   (2) Erasing it
/// iff it has no memory effects and none of its results are live.
///
/// It is assumed that `op` is simple. Here, a simple op is one which isn't a
/// symbol op, a symbol-user op, a region branch op, a branch op, a region
/// branch terminator op, or return-like.
static void cleanSimpleOp(Operation *op, RunLivenessAnalysis &la) { … }

/// Clean a function-like op `funcOp`, given the liveness information in `la`
/// and the IR in `module`. Here, cleaning means:
///   (1) Dropping the uses of its unnecessary (non-live) arguments,
///   (2) Erasing these arguments,
///   (3) Erasing their corresponding operands from its callers,
///   (4) Erasing its unnecessary terminator operands (return values that are
///   non-live across all callers),
///   (5) Dropping the uses of these return values from its callers, AND
///   (6) Erasing these return values
/// iff it is not public or declaration.
static void cleanFuncOp(FunctionOpInterface funcOp, Operation *module,
                        RunLivenessAnalysis &la) { … }

/// Clean a region branch op `regionBranchOp`, given the liveness information in
/// `la`. Here, cleaning means:
///   (1') Dropping all its uses, AND
///   (2') Erasing it
/// if it has no memory effects and none of its results are live, AND
///   (1) Erasing its unnecessary operands (operands that are forwarded to
///   unneccesary results and arguments),
///   (2) Cleaning each of its regions,
///   (3) Dropping the uses of its unnecessary results (results that are
///   forwarded from unnecessary operands and terminator operands), AND
///   (4) Erasing these results
/// otherwise.
/// Note that here, cleaning a region means:
///   (2.a) Dropping the uses of its unnecessary arguments (arguments that are
///   forwarded from unneccesary operands and terminator operands),
///   (2.b) Erasing these arguments, AND
///   (2.c) Erasing its unnecessary terminator operands (terminator operands
///   that are forwarded to unneccesary results and arguments).
/// It is important to note that values in this op flow from operands and
/// terminator operands (successor operands) to arguments and results (successor
/// inputs).
static void cleanRegionBranchOp(RegionBranchOpInterface regionBranchOp,
                                RunLivenessAnalysis &la) { … }

struct RemoveDeadValues : public impl::RemoveDeadValuesBase<RemoveDeadValues> { … };
} // namespace

void RemoveDeadValues::runOnOperation() { … }

std::unique_ptr<Pass> mlir::createRemoveDeadValuesPass() { … }
llvm/mlir/lib/Transforms/RemoveDeadValues.cpp
