7feb816ed0
This enables NewPM ports since it removes multiple pass dependencies on `TargetPassConfig` which we don't want to port to the NewPM. It looks like no derived classes of Combiner actually use this pointer, and it is also unused in the Combiner class.
352 lines
11 KiB
C++
352 lines
11 KiB
C++
//===-- lib/CodeGen/GlobalISel/Combiner.cpp -------------------------------===//
|
|
//
|
|
// 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 file constains common code to combine machine functions at generic
|
|
// level.
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "llvm/CodeGen/GlobalISel/Combiner.h"
|
|
#include "llvm/ADT/PostOrderIterator.h"
|
|
#include "llvm/ADT/SetVector.h"
|
|
#include "llvm/ADT/Statistic.h"
|
|
#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
|
|
#include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
|
|
#include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
|
|
#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
|
|
#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
|
|
#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
|
|
#include "llvm/CodeGen/GlobalISel/Utils.h"
|
|
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
|
|
#include "llvm/Support/Debug.h"
|
|
|
|
#define DEBUG_TYPE "gi-combiner"
|
|
|
|
using namespace llvm;
|
|
|
|
STATISTIC(NumOneIteration, "Number of functions with one iteration");
|
|
STATISTIC(NumTwoIterations, "Number of functions with two iterations");
|
|
STATISTIC(NumThreeOrMoreIterations,
|
|
"Number of functions with three or more iterations");
|
|
|
|
namespace llvm {
|
|
cl::OptionCategory GICombinerOptionCategory(
|
|
"GlobalISel Combiner",
|
|
"Control the rules which are enabled. These options all take a comma "
|
|
"separated list of rules to disable and may be specified by number "
|
|
"or number range (e.g. 1-10)."
|
|
#ifndef NDEBUG
|
|
" They may also be specified by name."
|
|
#endif
|
|
);
|
|
} // end namespace llvm
|
|
|
|
/// This class acts as the glue that joins the CombinerHelper to the overall
|
|
/// Combine algorithm. The CombinerHelper is intended to report the
|
|
/// modifications it makes to the MIR to the GISelChangeObserver and the
|
|
/// observer subclass will act on these events.
|
|
class Combiner::WorkListMaintainer : public GISelChangeObserver {
|
|
protected:
|
|
#ifndef NDEBUG
|
|
/// The instructions that have been created but we want to report once they
|
|
/// have their operands. This is only maintained if debug output is requested.
|
|
SmallSetVector<const MachineInstr *, 32> CreatedInstrs;
|
|
#endif
|
|
using Level = CombinerInfo::ObserverLevel;
|
|
|
|
public:
|
|
static std::unique_ptr<WorkListMaintainer>
|
|
create(Level Lvl, WorkListTy &WorkList, MachineRegisterInfo &MRI);
|
|
|
|
~WorkListMaintainer() override = default;
|
|
|
|
void reportFullyCreatedInstrs() {
|
|
LLVM_DEBUG({
|
|
for (auto *MI : CreatedInstrs) {
|
|
dbgs() << "Created: " << *MI;
|
|
}
|
|
CreatedInstrs.clear();
|
|
});
|
|
}
|
|
|
|
virtual void reset() = 0;
|
|
virtual void appliedCombine() = 0;
|
|
};
|
|
|
|
/// A configurable WorkListMaintainer implementation.
|
|
/// The ObserverLevel determines how the WorkListMaintainer reacts to MIR
|
|
/// changes.
|
|
template <CombinerInfo::ObserverLevel Lvl>
|
|
class Combiner::WorkListMaintainerImpl : public Combiner::WorkListMaintainer {
|
|
WorkListTy &WorkList;
|
|
MachineRegisterInfo &MRI;
|
|
|
|
// Defer handling these instructions until the combine finishes.
|
|
SmallSetVector<MachineInstr *, 32> DeferList;
|
|
|
|
// Track VRegs that (might) have lost a use.
|
|
SmallSetVector<Register, 32> LostUses;
|
|
|
|
public:
|
|
WorkListMaintainerImpl(WorkListTy &WorkList, MachineRegisterInfo &MRI)
|
|
: WorkList(WorkList), MRI(MRI) {}
|
|
|
|
~WorkListMaintainerImpl() override = default;
|
|
|
|
void reset() override {
|
|
DeferList.clear();
|
|
LostUses.clear();
|
|
}
|
|
|
|
void erasingInstr(MachineInstr &MI) override {
|
|
// MI will become dangling, remove it from all lists.
|
|
LLVM_DEBUG(dbgs() << "Erasing: " << MI; CreatedInstrs.remove(&MI));
|
|
WorkList.remove(&MI);
|
|
if constexpr (Lvl != Level::Basic) {
|
|
DeferList.remove(&MI);
|
|
noteLostUses(MI);
|
|
}
|
|
}
|
|
|
|
void createdInstr(MachineInstr &MI) override {
|
|
LLVM_DEBUG(dbgs() << "Creating: " << MI; CreatedInstrs.insert(&MI));
|
|
if constexpr (Lvl == Level::Basic)
|
|
WorkList.insert(&MI);
|
|
else
|
|
// Defer handling newly created instructions, because they don't have
|
|
// operands yet. We also insert them into the WorkList in reverse
|
|
// order so that they will be combined top down.
|
|
DeferList.insert(&MI);
|
|
}
|
|
|
|
void changingInstr(MachineInstr &MI) override {
|
|
LLVM_DEBUG(dbgs() << "Changing: " << MI);
|
|
// Some uses might get dropped when MI is changed.
|
|
// For now, overapproximate by assuming all uses will be dropped.
|
|
// TODO: Is a more precise heuristic or manual tracking of use count
|
|
// decrements worth it?
|
|
if constexpr (Lvl != Level::Basic)
|
|
noteLostUses(MI);
|
|
}
|
|
|
|
void changedInstr(MachineInstr &MI) override {
|
|
LLVM_DEBUG(dbgs() << "Changed: " << MI);
|
|
if constexpr (Lvl == Level::Basic)
|
|
WorkList.insert(&MI);
|
|
else
|
|
// Defer this for DCE
|
|
DeferList.insert(&MI);
|
|
}
|
|
|
|
// Only track changes during the combine and then walk the def/use-chains once
|
|
// the combine is finished, because:
|
|
// - instructions might have multiple defs during the combine.
|
|
// - use counts aren't accurate during the combine.
|
|
void appliedCombine() override {
|
|
if constexpr (Lvl == Level::Basic)
|
|
return;
|
|
|
|
// DCE deferred instructions and add them to the WorkList bottom up.
|
|
while (!DeferList.empty()) {
|
|
MachineInstr &MI = *DeferList.pop_back_val();
|
|
if (tryDCE(MI, MRI))
|
|
continue;
|
|
|
|
if constexpr (Lvl >= Level::SinglePass)
|
|
addUsersToWorkList(MI);
|
|
|
|
WorkList.insert(&MI);
|
|
}
|
|
|
|
// Handle instructions that have lost a user.
|
|
while (!LostUses.empty()) {
|
|
Register Use = LostUses.pop_back_val();
|
|
MachineInstr *UseMI = MRI.getVRegDef(Use);
|
|
if (!UseMI)
|
|
continue;
|
|
|
|
// If DCE succeeds, UseMI's uses are added back to LostUses by
|
|
// erasingInstr.
|
|
if (tryDCE(*UseMI, MRI))
|
|
continue;
|
|
|
|
if constexpr (Lvl >= Level::SinglePass) {
|
|
// OneUse checks are relatively common, so we might be able to combine
|
|
// the single remaining user of this Reg.
|
|
if (MRI.hasOneNonDBGUser(Use))
|
|
WorkList.insert(&*MRI.use_instr_nodbg_begin(Use));
|
|
|
|
WorkList.insert(UseMI);
|
|
}
|
|
}
|
|
}
|
|
|
|
void noteLostUses(MachineInstr &MI) {
|
|
for (auto &Use : MI.explicit_uses()) {
|
|
if (!Use.isReg() || !Use.getReg().isVirtual())
|
|
continue;
|
|
LostUses.insert(Use.getReg());
|
|
}
|
|
}
|
|
|
|
void addUsersToWorkList(MachineInstr &MI) {
|
|
for (auto &Def : MI.defs()) {
|
|
Register DefReg = Def.getReg();
|
|
if (!DefReg.isVirtual())
|
|
continue;
|
|
for (auto &UseMI : MRI.use_nodbg_instructions(DefReg)) {
|
|
WorkList.insert(&UseMI);
|
|
}
|
|
}
|
|
}
|
|
};
|
|
|
|
std::unique_ptr<Combiner::WorkListMaintainer>
|
|
Combiner::WorkListMaintainer::create(Level Lvl, WorkListTy &WorkList,
|
|
MachineRegisterInfo &MRI) {
|
|
switch (Lvl) {
|
|
case Level::Basic:
|
|
return std::make_unique<WorkListMaintainerImpl<Level::Basic>>(WorkList,
|
|
MRI);
|
|
case Level::DCE:
|
|
return std::make_unique<WorkListMaintainerImpl<Level::DCE>>(WorkList, MRI);
|
|
case Level::SinglePass:
|
|
return std::make_unique<WorkListMaintainerImpl<Level::SinglePass>>(WorkList,
|
|
MRI);
|
|
}
|
|
llvm_unreachable("Illegal ObserverLevel");
|
|
}
|
|
|
|
Combiner::Combiner(MachineFunction &MF, const CombinerInfo &CInfo,
|
|
GISelValueTracking *VT, GISelCSEInfo *CSEInfo)
|
|
: Builder(CSEInfo ? std::make_unique<CSEMIRBuilder>()
|
|
: std::make_unique<MachineIRBuilder>()),
|
|
WLObserver(WorkListMaintainer::create(CInfo.ObserverLvl, WorkList,
|
|
MF.getRegInfo())),
|
|
ObserverWrapper(std::make_unique<GISelObserverWrapper>()), CInfo(CInfo),
|
|
Observer(*ObserverWrapper), B(*Builder), MF(MF), MRI(MF.getRegInfo()),
|
|
VT(VT), CSEInfo(CSEInfo) {
|
|
// Setup builder.
|
|
B.setMF(MF);
|
|
if (CSEInfo)
|
|
B.setCSEInfo(CSEInfo);
|
|
|
|
B.setChangeObserver(*ObserverWrapper);
|
|
}
|
|
|
|
Combiner::~Combiner() = default;
|
|
|
|
bool Combiner::tryDCE(MachineInstr &MI, MachineRegisterInfo &MRI) {
|
|
if (!isTriviallyDead(MI, MRI))
|
|
return false;
|
|
LLVM_DEBUG(dbgs() << "Dead: " << MI);
|
|
llvm::salvageDebugInfo(MRI, MI);
|
|
MI.eraseFromParent();
|
|
return true;
|
|
}
|
|
|
|
bool Combiner::combineMachineInstrs() {
|
|
// If the ISel pipeline failed, do not bother running this pass.
|
|
// FIXME: Should this be here or in individual combiner passes.
|
|
if (MF.getProperties().hasFailedISel())
|
|
return false;
|
|
|
|
// We can't call this in the constructor because the derived class is
|
|
// uninitialized at that time.
|
|
if (!HasSetupMF) {
|
|
HasSetupMF = true;
|
|
setupMF(MF, VT);
|
|
}
|
|
|
|
LLVM_DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
|
|
|
|
MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
|
|
|
|
bool MFChanged = false;
|
|
bool Changed;
|
|
|
|
unsigned Iteration = 0;
|
|
while (true) {
|
|
++Iteration;
|
|
LLVM_DEBUG(dbgs() << "\n\nCombiner iteration #" << Iteration << '\n');
|
|
|
|
Changed = false;
|
|
WorkList.clear();
|
|
WLObserver->reset();
|
|
ObserverWrapper->clearObservers();
|
|
if (CSEInfo)
|
|
ObserverWrapper->addObserver(CSEInfo);
|
|
|
|
// If Observer-based DCE is enabled, perform full DCE only before the first
|
|
// iteration.
|
|
bool EnableDCE = CInfo.ObserverLvl >= CombinerInfo::ObserverLevel::DCE
|
|
? CInfo.EnableFullDCE && Iteration == 1
|
|
: CInfo.EnableFullDCE;
|
|
|
|
// Collect all instructions. Do a post order traversal for basic blocks and
|
|
// insert with list bottom up, so while we pop_back_val, we'll traverse top
|
|
// down RPOT.
|
|
RAIIMFObsDelInstaller DelInstall(MF, *ObserverWrapper);
|
|
for (MachineBasicBlock *MBB : post_order(&MF)) {
|
|
for (MachineInstr &CurMI :
|
|
llvm::make_early_inc_range(llvm::reverse(*MBB))) {
|
|
// Erase dead insts before even adding to the list.
|
|
if (EnableDCE && tryDCE(CurMI, MRI))
|
|
continue;
|
|
WorkList.deferred_insert(&CurMI);
|
|
}
|
|
}
|
|
WorkList.finalize();
|
|
|
|
// Only notify WLObserver during actual combines
|
|
ObserverWrapper->addObserver(WLObserver.get());
|
|
// Main Loop. Process the instructions here.
|
|
while (!WorkList.empty()) {
|
|
MachineInstr &CurrInst = *WorkList.pop_back_val();
|
|
LLVM_DEBUG(dbgs() << "\nTry combining " << CurrInst);
|
|
bool AppliedCombine = tryCombineAll(CurrInst);
|
|
LLVM_DEBUG(WLObserver->reportFullyCreatedInstrs());
|
|
Changed |= AppliedCombine;
|
|
if (AppliedCombine)
|
|
WLObserver->appliedCombine();
|
|
}
|
|
MFChanged |= Changed;
|
|
|
|
if (!Changed) {
|
|
LLVM_DEBUG(dbgs() << "\nCombiner reached fixed-point after iteration #"
|
|
<< Iteration << '\n');
|
|
break;
|
|
}
|
|
// Iterate until a fixed-point is reached if MaxIterations == 0,
|
|
// otherwise limit the number of iterations.
|
|
if (CInfo.MaxIterations && Iteration >= CInfo.MaxIterations) {
|
|
LLVM_DEBUG(
|
|
dbgs() << "\nCombiner reached iteration limit after iteration #"
|
|
<< Iteration << '\n');
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (Iteration == 1)
|
|
++NumOneIteration;
|
|
else if (Iteration == 2)
|
|
++NumTwoIterations;
|
|
else
|
|
++NumThreeOrMoreIterations;
|
|
|
|
#ifndef NDEBUG
|
|
if (CSEInfo) {
|
|
if (auto E = CSEInfo->verify()) {
|
|
errs() << E << '\n';
|
|
assert(false && "CSEInfo is not consistent. Likely missing calls to "
|
|
"observer on mutations.");
|
|
}
|
|
}
|
|
#endif
|
|
return MFChanged;
|
|
}
|