//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "ifcvt"
#include "llvm/CodeGen/Passes.h"
#include "BranchFolding.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LivePhysRegs.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
-#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
-#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
using namespace llvm;
+#define DEBUG_TYPE "ifcvt"
+
// Hidden options for help debugging.
static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
const TargetLoweringBase *TLI;
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
+ const MachineBlockFrequencyInfo *MBFI;
const MachineBranchProbabilityInfo *MBPI;
MachineRegisterInfo *MRI;
bool PreRegAlloc;
bool MadeChange;
int FnNum;
+ std::function<bool(const Function &)> PredicateFtor;
+
public:
static char ID;
- IfConverter() : MachineFunctionPass(ID), FnNum(-1) {
+ IfConverter(std::function<bool(const Function &)> Ftor = nullptr)
+ : MachineFunctionPass(ID), FnNum(-1), PredicateFtor(Ftor) {
initializeIfConverterPass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.addRequired<MachineBlockFrequencyInfo>();
AU.addRequired<MachineBranchProbabilityInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
return true;
else if (Incr1 == Incr2) {
// Favors subsumption.
- if (C1->NeedSubsumption == false && C2->NeedSubsumption == true)
+ if (!C1->NeedSubsumption && C2->NeedSubsumption)
return true;
else if (C1->NeedSubsumption == C2->NeedSubsumption) {
// Favors diamond over triangle, etc.
};
char IfConverter::ID = 0;
-}
+} // namespace
char &llvm::IfConverterID = IfConverter::ID;
INITIALIZE_PASS_END(IfConverter, "if-converter", "If Converter", false, false)
bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
- TLI = MF.getTarget().getTargetLowering();
- TII = MF.getTarget().getInstrInfo();
- TRI = MF.getTarget().getRegisterInfo();
+ if (PredicateFtor && !PredicateFtor(*MF.getFunction()))
+ return false;
+
+ const TargetSubtargetInfo &ST = MF.getSubtarget();
+ TLI = ST.getTargetLowering();
+ TII = ST.getInstrInfo();
+ TRI = ST.getRegisterInfo();
+ MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
MRI = &MF.getRegInfo();
-
- const TargetSubtargetInfo &ST =
- MF.getTarget().getSubtarget<TargetSubtargetInfo>();
- SchedModel.init(*ST.getSchedModel(), &ST, TII);
+ SchedModel.init(ST.getSchedModel(), &ST, TII);
if (!TII) return false;
bool BFChange = false;
if (!PreRegAlloc) {
// Tail merge tend to expose more if-conversion opportunities.
- BranchFolder BF(true, false);
- BFChange = BF.OptimizeFunction(MF, TII,
- MF.getTarget().getRegisterInfo(),
+ BranchFolder BF(true, false, *MBFI, *MBPI);
+ BFChange = BF.OptimizeFunction(MF, TII, ST.getRegisterInfo(),
getAnalysisIfAvailable<MachineModuleInfo>());
}
BBAnalysis.clear();
if (MadeChange && IfCvtBranchFold) {
- BranchFolder BF(false, false);
- BF.OptimizeFunction(MF, TII,
- MF.getTarget().getRegisterInfo(),
+ BranchFolder BF(false, false, *MBFI, *MBPI);
+ BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(),
getAnalysisIfAvailable<MachineModuleInfo>());
}
if (BBI.IsDone || BBI.IsUnpredicable)
return false;
+ // If it is already predicated but we couldn't analyze its terminator, the
+ // latter might fallthrough, but we can't determine where to.
+ // Conservatively avoid if-converting again.
+ if (BBI.Predicate.size() && !BBI.IsBrAnalyzable)
+ return false;
+
// If it is already predicated, check if the new predicate subsumes
// its predicate.
if (BBI.Predicate.size() && !TII->SubsumesPredicate(Pred, BBI.Predicate))
/// to determine if it can be if-converted. If predecessor is already enqueued,
/// dequeue it!
void IfConverter::InvalidatePreds(MachineBasicBlock *BB) {
- for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
- E = BB->pred_end(); PI != E; ++PI) {
- BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
+ for (const auto &Predecessor : BB->predecessors()) {
+ BBInfo &PBBI = BBAnalysis[Predecessor->getNumber()];
if (PBBI.IsDone || PBBI.BB == BB)
continue;
PBBI.IsAnalyzed = false;
/// Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all
/// values defined in MI which are not live/used by MI.
static void UpdatePredRedefs(MachineInstr *MI, LivePhysRegs &Redefs) {
- for (ConstMIBundleOperands Ops(MI); Ops.isValid(); ++Ops) {
- if (!Ops->isReg() || !Ops->isKill())
- continue;
- unsigned Reg = Ops->getReg();
- if (Reg == 0)
+ SmallVector<std::pair<unsigned, const MachineOperand*>, 4> Clobbers;
+ Redefs.stepForward(*MI, Clobbers);
+
+ // Now add the implicit uses for each of the clobbered values.
+ for (auto Reg : Clobbers) {
+ // FIXME: Const cast here is nasty, but better than making StepForward
+ // take a mutable instruction instead of const.
+ MachineOperand &Op = const_cast<MachineOperand&>(*Reg.second);
+ MachineInstr *OpMI = Op.getParent();
+ MachineInstrBuilder MIB(*OpMI->getParent()->getParent(), OpMI);
+ if (Op.isRegMask()) {
+ // First handle regmasks. They clobber any entries in the mask which
+ // means that we need a def for those registers.
+ MIB.addReg(Reg.first, RegState::Implicit | RegState::Undef);
+
+ // We also need to add an implicit def of this register for the later
+ // use to read from.
+ // For the register allocator to have allocated a register clobbered
+ // by the call which is used later, it must be the case that
+ // the call doesn't return.
+ MIB.addReg(Reg.first, RegState::Implicit | RegState::Define);
continue;
- Redefs.removeReg(Reg);
- }
- for (MIBundleOperands Ops(MI); Ops.isValid(); ++Ops) {
- if (!Ops->isReg() || !Ops->isDef())
- continue;
- unsigned Reg = Ops->getReg();
- if (Reg == 0 || Redefs.contains(Reg))
- continue;
- Redefs.addReg(Reg);
-
- MachineOperand &Op = *Ops;
- MachineInstr *MI = Op.getParent();
- MachineInstrBuilder MIB(*MI->getParent()->getParent(), MI);
- MIB.addReg(Reg, RegState::Implicit | RegState::Undef);
+ }
+ assert(Op.isReg() && "Register operand required");
+ if (Op.isDead()) {
+ // If we found a dead def, but it needs to be live, then remove the dead
+ // flag.
+ if (Redefs.contains(Op.getReg()))
+ Op.setIsDead(false);
+ }
+ MIB.addReg(Reg.first, RegState::Implicit | RegState::Undef);
}
}
bool HasEarlyExit = CvtBBI->FalseBB != nullptr;
uint64_t CvtNext = 0, CvtFalse = 0, BBNext = 0, BBCvt = 0, SumWeight = 0;
uint32_t WeightScale = 0;
+
if (HasEarlyExit) {
// Get weights before modifying CvtBBI->BB and BBI.BB.
CvtNext = MBPI->getEdgeWeight(CvtBBI->BB, NextBBI->BB);
BBCvt = MBPI->getEdgeWeight(BBI.BB, CvtBBI->BB);
SumWeight = MBPI->getSumForBlock(CvtBBI->BB, WeightScale);
}
+
if (CvtBBI->BB->pred_size() > 1) {
BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
// Copy instructions in the true block, predicate them, and add them to
for (MachineBasicBlock::const_iterator I = BBI1->BB->begin(), E = DI1; I != E;
++I) {
- Redefs.stepForward(*I);
+ SmallVector<std::pair<unsigned, const MachineOperand*>, 4> IgnoredClobbers;
+ Redefs.stepForward(*I, IgnoredClobbers);
}
BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
BBI2->BB->erase(BBI2->BB->begin(), DI2);
}
static bool MaySpeculate(const MachineInstr *MI,
- SmallSet<unsigned, 4> &LaterRedefs,
- const TargetInstrInfo *TII) {
+ SmallSet<unsigned, 4> &LaterRedefs) {
bool SawStore = true;
- if (!MI->isSafeToMove(TII, nullptr, SawStore))
+ if (!MI->isSafeToMove(nullptr, SawStore))
return false;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
// It may be possible not to predicate an instruction if it's the 'true'
// side of a diamond and the 'false' side may re-define the instruction's
// defs.
- if (MaySpec && MaySpeculate(I, *LaterRedefs, TII)) {
+ if (MaySpec && MaySpeculate(I, *LaterRedefs)) {
AnyUnpred = true;
continue;
}
UpdatePredRedefs(I, Redefs);
}
- std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
+ BBI.Predicate.append(Cond.begin(), Cond.end());
BBI.IsAnalyzed = false;
BBI.NonPredSize = 0;
}
}
- std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
- std::back_inserter(ToBBI.Predicate));
- std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));
+ ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
+ ToBBI.Predicate.append(Cond.begin(), Cond.end());
ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
ToBBI.IsAnalyzed = false;
if (NBB && !FromBBI.BB->isSuccessor(NBB))
FromBBI.BB->addSuccessor(NBB);
- std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
- std::back_inserter(ToBBI.Predicate));
+ ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
FromBBI.Predicate.clear();
ToBBI.NonPredSize += FromBBI.NonPredSize;
ToBBI.IsAnalyzed = false;
FromBBI.IsAnalyzed = false;
}
+
+FunctionPass *
+llvm::createIfConverter(std::function<bool(const Function &)> Ftor) {
+ return new IfConverter(Ftor);
+}