MachineCSE.cpp | Explore in Territory

//===- MachineCSE.cpp - Machine Common Subexpression Elimination Pass -----===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This pass performs global common subexpression elimination on machine
// instructions using a scoped hash table based value numbering scheme. It
// must be run while the machine function is still in SSA form.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/MachineCSE.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/ScopedHashTable.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCRegister.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/RecyclingAllocator.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <iterator>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumCoalesces, "Number of copies coalesced");
STATISTIC(NumCSEs,      "Number of common subexpression eliminated");
STATISTIC(NumPREs,      "Number of partial redundant expression"
                        " transformed to fully redundant");
STATISTIC(NumPhysCSEs,
          "Number of physreg referencing common subexpr eliminated");
STATISTIC(NumCrossBBCSEs,
          "Number of cross-MBB physreg referencing CS eliminated");
STATISTIC(NumCommutes,  "Number of copies coalesced after commuting");

// Threshold to avoid excessive cost to compute isProfitableToCSE.
static cl::opt<int>
    CSUsesThreshold("csuses-threshold", cl::Hidden, cl::init(1024),
                    cl::desc("Threshold for the size of CSUses"));

static cl::opt<bool> AggressiveMachineCSE(
    "aggressive-machine-cse", cl::Hidden, cl::init(false),
    cl::desc("Override the profitability heuristics for Machine CSE"));

namespace {

class MachineCSEImpl { … };

class MachineCSELegacy : public MachineFunctionPass { … };
} // end anonymous namespace

char MachineCSELegacy::ID = …;

char &llvm::MachineCSELegacyID = …;

INITIALIZE_PASS_BEGIN(MachineCSELegacy, DEBUG_TYPE,
                      "Machine Common Subexpression Elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_END(MachineCSELegacy, DEBUG_TYPE,
                    "Machine Common Subexpression Elimination", false, false)

/// The source register of a COPY machine instruction can be propagated to all
/// its users, and this propagation could increase the probability of finding
/// common subexpressions. If the COPY has only one user, the COPY itself can
/// be removed.
bool MachineCSEImpl::PerformTrivialCopyPropagation(MachineInstr *MI,
                                                   MachineBasicBlock *MBB) { … }

bool MachineCSEImpl::isPhysDefTriviallyDead(
    MCRegister Reg, MachineBasicBlock::const_iterator I,
    MachineBasicBlock::const_iterator E) const { … }

static bool isCallerPreservedOrConstPhysReg(MCRegister Reg,
                                            const MachineOperand &MO,
                                            const MachineFunction &MF,
                                            const TargetRegisterInfo &TRI,
                                            const TargetInstrInfo &TII) { … }

/// hasLivePhysRegDefUses - Return true if the specified instruction read/write
/// physical registers (except for dead defs of physical registers). It also
/// returns the physical register def by reference if it's the only one and the
/// instruction does not uses a physical register.
bool MachineCSEImpl::hasLivePhysRegDefUses(const MachineInstr *MI,
                                           const MachineBasicBlock *MBB,
                                           SmallSet<MCRegister, 8> &PhysRefs,
                                           PhysDefVector &PhysDefs,
                                           bool &PhysUseDef) const { … }

bool MachineCSEImpl::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
                                      SmallSet<MCRegister, 8> &PhysRefs,
                                      PhysDefVector &PhysDefs,
                                      bool &NonLocal) const { … }

bool MachineCSEImpl::isCSECandidate(MachineInstr *MI) { … }

/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
/// common expression that defines Reg. CSBB is basic block where CSReg is
/// defined.
bool MachineCSEImpl::isProfitableToCSE(Register CSReg, Register Reg,
                                       MachineBasicBlock *CSBB,
                                       MachineInstr *MI) { … }

void MachineCSEImpl::EnterScope(MachineBasicBlock *MBB) { … }

void MachineCSEImpl::ExitScope(MachineBasicBlock *MBB) { … }

bool MachineCSEImpl::ProcessBlockCSE(MachineBasicBlock *MBB) { … }

/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
/// dominator tree node if its a leaf or all of its children are done. Walk
/// up the dominator tree to destroy ancestors which are now done.
void MachineCSEImpl::ExitScopeIfDone(
    MachineDomTreeNode *Node,
    DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren) { … }

bool MachineCSEImpl::PerformCSE(MachineDomTreeNode *Node) { … }

// We use stronger checks for PRE candidate rather than for CSE ones to embrace
// checks inside ProcessBlockCSE(), not only inside isCSECandidate(). This helps
// to exclude instrs created by PRE that won't be CSEed later.
bool MachineCSEImpl::isPRECandidate(MachineInstr *MI,
                                    SmallSet<MCRegister, 8> &PhysRefs) { … }

bool MachineCSEImpl::ProcessBlockPRE(MachineDominatorTree *DT,
                                     MachineBasicBlock *MBB) { … }

// This simple PRE (partial redundancy elimination) pass doesn't actually
// eliminate partial redundancy but transforms it to full redundancy,
// anticipating that the next CSE step will eliminate this created redundancy.
// If CSE doesn't eliminate this, than created instruction will remain dead
// and eliminated later by Remove Dead Machine Instructions pass.
bool MachineCSEImpl::PerformSimplePRE(MachineDominatorTree *DT) { … }

bool MachineCSEImpl::isProfitableToHoistInto(MachineBasicBlock *CandidateBB,
                                             MachineBasicBlock *MBB,
                                             MachineBasicBlock *MBB1) { … }

void MachineCSEImpl::releaseMemory() { … }

bool MachineCSEImpl::run(MachineFunction &MF) { … }

PreservedAnalyses MachineCSEPass::run(MachineFunction &MF,
                                      MachineFunctionAnalysisManager &MFAM) { … }

bool MachineCSELegacy::runOnMachineFunction(MachineFunction &MF) { … }
llvm/llvm/lib/CodeGen/MachineCSE.cpp
