ba0e4af50f
Almost all dead code is found in the first iteration. In LLVM lit tests, 461931 instructions were deleted in the first iteration and 2 in the second. In a 3-stage build of llvm, 1305507 instructions were deleted in the first iteration and 0 in the second. Added code to detect when another DCE iteration is needed. Number of DCE iterations will almost always be reduced from 2 to 1. --------- Signed-off-by: John Lu <John.Lu@amd.com>
130 lines
4.2 KiB
C++
130 lines
4.2 KiB
C++
//===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===//
|
|
//
|
|
// 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 is an extremely simple MachineInstr-level dead-code-elimination pass.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "llvm/CodeGen/DeadMachineInstructionElim.h"
|
|
#include "llvm/ADT/PostOrderIterator.h"
|
|
#include "llvm/ADT/Statistic.h"
|
|
#include "llvm/CodeGen/LiveRegUnits.h"
|
|
#include "llvm/CodeGen/MachineFunctionPass.h"
|
|
#include "llvm/CodeGen/MachineRegisterInfo.h"
|
|
#include "llvm/CodeGen/TargetSubtargetInfo.h"
|
|
#include "llvm/InitializePasses.h"
|
|
#include "llvm/Pass.h"
|
|
#include "llvm/Support/Debug.h"
|
|
#include "llvm/Support/raw_ostream.h"
|
|
|
|
using namespace llvm;
|
|
|
|
#define DEBUG_TYPE "dead-mi-elimination"
|
|
|
|
STATISTIC(NumDeletes, "Number of dead instructions deleted");
|
|
|
|
namespace {
|
|
class DeadMachineInstructionElimImpl {
|
|
const MachineRegisterInfo *MRI = nullptr;
|
|
const TargetInstrInfo *TII = nullptr;
|
|
LiveRegUnits LivePhysRegs;
|
|
|
|
public:
|
|
bool runImpl(MachineFunction &MF);
|
|
|
|
private:
|
|
bool eliminateDeadMI(MachineFunction &MF, bool &NeedAnotherIteration);
|
|
};
|
|
|
|
class DeadMachineInstructionElim : public MachineFunctionPass {
|
|
public:
|
|
static char ID; // Pass identification, replacement for typeid
|
|
|
|
DeadMachineInstructionElim() : MachineFunctionPass(ID) {}
|
|
|
|
bool runOnMachineFunction(MachineFunction &MF) override {
|
|
if (skipFunction(MF.getFunction()))
|
|
return false;
|
|
return DeadMachineInstructionElimImpl().runImpl(MF);
|
|
}
|
|
|
|
void getAnalysisUsage(AnalysisUsage &AU) const override {
|
|
AU.setPreservesCFG();
|
|
MachineFunctionPass::getAnalysisUsage(AU);
|
|
}
|
|
};
|
|
} // namespace
|
|
|
|
PreservedAnalyses
|
|
DeadMachineInstructionElimPass::run(MachineFunction &MF,
|
|
MachineFunctionAnalysisManager &) {
|
|
if (!DeadMachineInstructionElimImpl().runImpl(MF))
|
|
return PreservedAnalyses::all();
|
|
PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
|
|
PA.preserveSet<CFGAnalyses>();
|
|
return PA;
|
|
}
|
|
|
|
char DeadMachineInstructionElim::ID = 0;
|
|
char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID;
|
|
|
|
INITIALIZE_PASS(DeadMachineInstructionElim, DEBUG_TYPE,
|
|
"Remove dead machine instructions", false, false)
|
|
|
|
bool DeadMachineInstructionElimImpl::runImpl(MachineFunction &MF) {
|
|
MRI = &MF.getRegInfo();
|
|
|
|
const TargetSubtargetInfo &ST = MF.getSubtarget();
|
|
TII = ST.getInstrInfo();
|
|
LivePhysRegs.init(*ST.getRegisterInfo());
|
|
|
|
bool NeedAnotherIteration;
|
|
bool AnyChanges = eliminateDeadMI(MF, NeedAnotherIteration);
|
|
while (NeedAnotherIteration)
|
|
eliminateDeadMI(MF, NeedAnotherIteration);
|
|
return AnyChanges;
|
|
}
|
|
|
|
bool DeadMachineInstructionElimImpl::eliminateDeadMI(
|
|
MachineFunction &MF, bool &NeedAnotherIteration) {
|
|
bool AnyChanges = false;
|
|
SmallPtrSet<MachineBasicBlock *, 4> NeedsProcessing;
|
|
|
|
// Loop over all instructions in all blocks, from bottom to top, so that it's
|
|
// more likely that chains of dependent but ultimately dead instructions will
|
|
// be cleaned up.
|
|
for (MachineBasicBlock *MBB : post_order(&MF)) {
|
|
LivePhysRegs.addLiveOuts(*MBB);
|
|
NeedsProcessing.erase(MBB);
|
|
|
|
// Now scan the instructions and delete dead ones, tracking physreg
|
|
// liveness as we go.
|
|
for (MachineInstr &MI : make_early_inc_range(reverse(*MBB))) {
|
|
// If the instruction is dead, delete it!
|
|
if (MI.isDead(*MRI, &LivePhysRegs)) {
|
|
if (MI.isPHI()) {
|
|
for (MachineBasicBlock *P : MBB->predecessors())
|
|
NeedsProcessing.insert(P);
|
|
}
|
|
LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << MI);
|
|
// It is possible that some DBG_VALUE instructions refer to this
|
|
// instruction. They will be deleted in the live debug variable
|
|
// analysis.
|
|
MI.eraseFromParent();
|
|
AnyChanges = true;
|
|
++NumDeletes;
|
|
continue;
|
|
}
|
|
LivePhysRegs.stepBackward(MI);
|
|
}
|
|
}
|
|
LivePhysRegs.clear();
|
|
NeedAnotherIteration = !NeedsProcessing.empty();
|
|
return AnyChanges;
|
|
}
|