#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
const MachineBranchProbabilityInfo *MBPI;
MachineRegisterInfo *MRI;
+ LivePhysRegs Redefs;
+ LivePhysRegs DontKill;
+
bool PreRegAlloc;
bool MadeChange;
int FnNum;
void PredicateBlock(BBInfo &BBI,
MachineBasicBlock::iterator E,
SmallVectorImpl<MachineOperand> &Cond,
- SmallSet<unsigned, 4> &Redefs,
SmallSet<unsigned, 4> *LaterRedefs = 0);
void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
SmallVectorImpl<MachineOperand> &Cond,
- SmallSet<unsigned, 4> &Redefs,
bool IgnoreBr = false);
void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true);
BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
}
-/// InitPredRedefs / UpdatePredRedefs - Defs by predicated instructions are
-/// modeled as read + write (sort like two-address instructions). These
-/// routines track register liveness and add implicit uses to if-converted
-/// instructions to conform to the model.
-static void InitPredRedefs(MachineBasicBlock *BB, SmallSet<unsigned,4> &Redefs,
- const TargetRegisterInfo *TRI) {
- for (MachineBasicBlock::livein_iterator I = BB->livein_begin(),
- E = BB->livein_end(); I != E; ++I) {
- unsigned Reg = *I;
- for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
- SubRegs.isValid(); ++SubRegs)
- Redefs.insert(*SubRegs);
- }
-}
-
-static void UpdatePredRedefs(MachineInstr *MI, SmallSet<unsigned,4> &Redefs,
- const TargetRegisterInfo *TRI,
- bool AddImpUse = false) {
- SmallVector<unsigned, 4> Defs;
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- const MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg())
+/// 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 = MO.getReg();
- if (!Reg)
+ unsigned Reg = Ops->getReg();
+ if (Reg == 0)
continue;
- if (MO.isDef())
- Defs.push_back(Reg);
- else if (MO.isKill()) {
- for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
- SubRegs.isValid(); ++SubRegs)
- Redefs.erase(*SubRegs);
- }
+ Redefs.removeReg(Reg);
}
- MachineInstrBuilder MIB(*MI->getParent()->getParent(), MI);
- for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
- unsigned Reg = Defs[i];
- if (!Redefs.insert(Reg)) {
- if (AddImpUse)
- // Treat predicated update as read + write.
- MIB.addReg(Reg, RegState::Implicit | RegState::Undef);
- } else {
- for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
- Redefs.insert(*SubRegs);
- }
+ 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);
}
}
-static void UpdatePredRedefs(MachineBasicBlock::iterator I,
- MachineBasicBlock::iterator E,
- SmallSet<unsigned,4> &Redefs,
- const TargetRegisterInfo *TRI) {
- while (I != E) {
- UpdatePredRedefs(I, Redefs, TRI);
- ++I;
+/**
+ * Remove kill flags from operands with a registers in the @p DontKill set.
+ */
+static void RemoveKills(MachineInstr &MI, const LivePhysRegs &DontKill) {
+ for (MIBundleOperands O(&MI); O.isValid(); ++O) {
+ if (!O->isReg() || !O->isKill())
+ continue;
+ if (DontKill.contains(O->getReg()))
+ O->setIsKill(false);
}
}
+/**
+ * Walks a range of machine instructions and removes kill flags for registers
+ * in the @p DontKill set.
+ */
+static void RemoveKills(MachineBasicBlock::iterator I,
+ MachineBasicBlock::iterator E,
+ const LivePhysRegs &DontKill,
+ const MCRegisterInfo &MCRI) {
+ for ( ; I != E; ++I)
+ RemoveKills(*I, DontKill);
+}
+
/// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
///
bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
// Initialize liveins to the first BB. These are potentiall redefined by
// predicated instructions.
- SmallSet<unsigned, 4> Redefs;
- InitPredRedefs(CvtBBI->BB, Redefs, TRI);
- InitPredRedefs(NextBBI->BB, Redefs, TRI);
+ Redefs.init(TRI);
+ Redefs.addLiveIns(CvtBBI->BB);
+ Redefs.addLiveIns(NextBBI->BB);
+
+ // Compute a set of registers which must not be killed by instructions in
+ // BB1: This is everything live-in to BB2.
+ DontKill.init(TRI);
+ DontKill.addLiveIns(NextBBI->BB);
if (CvtBBI->BB->pred_size() > 1) {
BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
// Copy instructions in the true block, predicate them, and add them to
// the entry block.
- CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs);
+ CopyAndPredicateBlock(BBI, *CvtBBI, Cond);
// RemoveExtraEdges won't work if the block has an unanalyzable branch, so
// explicitly remove CvtBBI as a successor.
BBI.BB->removeSuccessor(CvtBBI->BB);
} else {
- PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
+ RemoveKills(CvtBBI->BB->begin(), CvtBBI->BB->end(), DontKill, *TRI);
+ PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
// Merge converted block into entry block.
BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
return true;
}
+/// Scale down weights to fit into uint32_t. NewTrue is the new weight
+/// for successor TrueBB, and NewFalse is the new weight for successor
+/// FalseBB.
+static void ScaleWeights(uint64_t NewTrue, uint64_t NewFalse,
+ MachineBasicBlock *MBB,
+ const MachineBasicBlock *TrueBB,
+ const MachineBasicBlock *FalseBB,
+ const MachineBranchProbabilityInfo *MBPI) {
+ uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
+ uint32_t Scale = (NewMax / UINT32_MAX) + 1;
+ for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
+ SE = MBB->succ_end();
+ SI != SE; ++SI) {
+ if (*SI == TrueBB)
+ MBB->setSuccWeight(SI, (uint32_t)(NewTrue / Scale));
+ else if (*SI == FalseBB)
+ MBB->setSuccWeight(SI, (uint32_t)(NewFalse / Scale));
+ else
+ MBB->setSuccWeight(SI, MBPI->getEdgeWeight(MBB, SI) / Scale);
+ }
+}
+
/// IfConvertTriangle - If convert a triangle sub-CFG.
///
bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
// Initialize liveins to the first BB. These are potentially redefined by
// predicated instructions.
- SmallSet<unsigned, 4> Redefs;
- InitPredRedefs(CvtBBI->BB, Redefs, TRI);
- InitPredRedefs(NextBBI->BB, Redefs, TRI);
+ Redefs.init(TRI);
+ Redefs.addLiveIns(CvtBBI->BB);
+ Redefs.addLiveIns(NextBBI->BB);
+
+ DontKill.clear();
bool HasEarlyExit = CvtBBI->FalseBB != NULL;
+ uint64_t CvtNext = 0, CvtFalse = 0, SumWeight = 0;
+ uint32_t WeightScale = 0;
+ if (HasEarlyExit) {
+ // Get weights before modifying CvtBBI->BB.
+ CvtNext = MBPI->getEdgeWeight(CvtBBI->BB, NextBBI->BB);
+ CvtFalse = MBPI->getEdgeWeight(CvtBBI->BB, CvtBBI->FalseBB);
+ 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
// the entry block.
- CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs, true);
+ CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
// RemoveExtraEdges won't work if the block has an unanalyzable branch, so
// explicitly remove CvtBBI as a successor.
} else {
// Predicate the 'true' block after removing its branch.
CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
- PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
+ PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
// Now merge the entry of the triangle with the true block.
BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
llvm_unreachable("Unable to reverse branch condition!");
TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond, dl);
BBI.BB->addSuccessor(CvtBBI->FalseBB);
+ // Update the edge weight for both CvtBBI->FalseBB and NextBBI.
+ // New_Weight(BBI.BB, NextBBI->BB) =
+ // Weight(BBI.BB, NextBBI->BB) * getSumForBlock(CvtBBI->BB) +
+ // Weight(BBI.BB, CvtBBI->BB) * Weight(CvtBBI->BB, NextBBI->BB)
+ // New_Weight(BBI.BB, CvtBBI->FalseBB) =
+ // Weight(BBI.BB, CvtBBI->BB) * Weight(CvtBBI->BB, CvtBBI->FalseBB)
+
+ uint64_t BBNext = MBPI->getEdgeWeight(BBI.BB, NextBBI->BB);
+ uint64_t BBCvt = MBPI->getEdgeWeight(BBI.BB, CvtBBI->BB);
+
+ uint64_t NewNext = BBNext * SumWeight + (BBCvt * CvtNext) / WeightScale;
+ uint64_t NewFalse = (BBCvt * CvtFalse) / WeightScale;
+ // We need to scale down all weights of BBI.BB to fit uint32_t.
+ // Here BBI.BB is connected to CvtBBI->FalseBB and will fall through to
+ // the next block.
+ ScaleWeights(NewNext, NewFalse, BBI.BB, getNextBlock(BBI.BB),
+ CvtBBI->FalseBB, MBPI);
}
// Merge in the 'false' block if the 'false' block has no other
// Initialize liveins to the first BB. These are potentially redefined by
// predicated instructions.
- SmallSet<unsigned, 4> Redefs;
- InitPredRedefs(BBI1->BB, Redefs, TRI);
+ Redefs.init(TRI);
+ Redefs.addLiveIns(BBI1->BB);
// Remove the duplicated instructions at the beginnings of both paths.
MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
--NumDups1;
}
- UpdatePredRedefs(BBI1->BB->begin(), DI1, Redefs, TRI);
+ // Compute a set of registers which must not be killed by instructions in BB1:
+ // This is everything used+live in BB2 after the duplicated instructions. We
+ // can compute this set by simulating liveness backwards from the end of BB2.
+ DontKill.init(TRI);
+ for (MachineBasicBlock::reverse_iterator I = BBI2->BB->rbegin(),
+ E = MachineBasicBlock::reverse_iterator(DI2); I != E; ++I) {
+ DontKill.stepBackward(*I);
+ }
+
+ for (MachineBasicBlock::const_iterator I = BBI1->BB->begin(), E = DI1; I != E;
+ ++I) {
+ Redefs.stepForward(*I);
+ }
BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
BBI2->BB->erase(BBI2->BB->begin(), DI2);
}
BBI1->BB->erase(DI1, BBI1->BB->end());
+ // Kill flags in the true block for registers living into the false block
+ // must be removed.
+ RemoveKills(BBI1->BB->begin(), BBI1->BB->end(), DontKill, *TRI);
+
// Remove 'false' block branch and find the last instruction to predicate.
BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
DI2 = BBI2->BB->end();
}
// Predicate the 'true' block.
- PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, Redefs, &RedefsByFalse);
+ PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, &RedefsByFalse);
// Predicate the 'false' block.
- PredicateBlock(*BBI2, DI2, *Cond2, Redefs);
+ PredicateBlock(*BBI2, DI2, *Cond2);
// Merge the true block into the entry of the diamond.
MergeBlocks(BBI, *BBI1, TailBB == 0);
void IfConverter::PredicateBlock(BBInfo &BBI,
MachineBasicBlock::iterator E,
SmallVectorImpl<MachineOperand> &Cond,
- SmallSet<unsigned, 4> &Redefs,
SmallSet<unsigned, 4> *LaterRedefs) {
bool AnyUnpred = false;
bool MaySpec = LaterRedefs != 0;
// If the predicated instruction now redefines a register as the result of
// if-conversion, add an implicit kill.
- UpdatePredRedefs(I, Redefs, TRI, true);
+ UpdatePredRedefs(I, Redefs);
}
std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
/// the destination block. Skip end of block branches if IgnoreBr is true.
void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
SmallVectorImpl<MachineOperand> &Cond,
- SmallSet<unsigned, 4> &Redefs,
bool IgnoreBr) {
MachineFunction &MF = *ToBBI.BB->getParent();
// If the predicated instruction now redefines a register as the result of
// if-conversion, add an implicit kill.
- UpdatePredRedefs(MI, Redefs, TRI, true);
+ UpdatePredRedefs(MI, Redefs);
+
+ // Some kill flags may not be correct anymore.
+ if (!DontKill.empty())
+ RemoveKills(*MI, DontKill);
}
if (!IgnoreBr) {
projects / oota-llvm.git / blobdiff