//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "tailduplication"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/DenseSet.h"
-#include "llvm/ADT/OwningPtr.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
using namespace llvm;
+#define DEBUG_TYPE "tailduplication"
+
STATISTIC(NumTails , "Number of tails duplicated");
STATISTIC(NumTailDups , "Number of tail duplicated blocks");
STATISTIC(NumInstrDups , "Additional instructions due to tail duplication");
typedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy;
namespace {
- /// TailDuplicatePass - Perform tail duplication.
+ /// Perform tail duplication.
class TailDuplicatePass : public MachineFunctionPass {
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
+ const MachineBranchProbabilityInfo *MBPI;
MachineModuleInfo *MMI;
MachineRegisterInfo *MRI;
- OwningPtr<RegScavenger> RS;
+ std::unique_ptr<RegScavenger> RS;
bool PreRegAlloc;
- // SSAUpdateVRs - A list of virtual registers for which to update SSA form.
+ // A list of virtual registers for which to update SSA form.
SmallVector<unsigned, 16> SSAUpdateVRs;
- // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of
- // source virtual registers.
+ // For each virtual register in SSAUpdateVals keep a list of source virtual
+ // registers.
DenseMap<unsigned, AvailableValsTy> SSAUpdateVals;
public:
explicit TailDuplicatePass() :
MachineFunctionPass(ID), PreRegAlloc(false) {}
- virtual bool runOnMachineFunction(MachineFunction &MF);
+ bool runOnMachineFunction(MachineFunction &MF) override;
+
+ void getAnalysisUsage(AnalysisUsage &AU) const override;
private:
void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
false, false)
bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) {
- TII = MF.getTarget().getInstrInfo();
- TRI = MF.getTarget().getRegisterInfo();
+ if (skipOptnoneFunction(*MF.getFunction()))
+ return false;
+
+ TII = MF.getSubtarget().getInstrInfo();
+ TRI = MF.getSubtarget().getRegisterInfo();
MRI = &MF.getRegInfo();
MMI = getAnalysisIfAvailable<MachineModuleInfo>();
+ MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
+
PreRegAlloc = MRI->isSSA();
RS.reset();
if (MRI->tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF))
return MadeChange;
}
+void TailDuplicatePass::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<MachineBranchProbabilityInfo>();
+ MachineFunctionPass::getAnalysisUsage(AU);
+}
+
static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {
for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) {
- MachineBasicBlock *MBB = I;
+ MachineBasicBlock *MBB = &*I;
SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(),
MBB->pred_end());
MachineBasicBlock::iterator MI = MBB->begin();
dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;
dbgs() << " missing input from predecessor BB#"
<< PredBB->getNumber() << '\n';
- llvm_unreachable(0);
+ llvm_unreachable(nullptr);
}
}
<< ": " << *MI;
dbgs() << " extra input from predecessor BB#"
<< PHIBB->getNumber() << '\n';
- llvm_unreachable(0);
+ llvm_unreachable(nullptr);
}
if (PHIBB->getNumber() < 0) {
dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;
dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n';
- llvm_unreachable(0);
+ llvm_unreachable(nullptr);
}
}
++MI;
}
}
-/// TailDuplicateAndUpdate - Tail duplicate the block and cleanup.
+/// Tail duplicate the block and cleanup.
bool
TailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB,
bool IsSimple,
// If the original definition is still around, add it as an available
// value.
MachineInstr *DefMI = MRI->getVRegDef(VReg);
- MachineBasicBlock *DefBB = 0;
+ MachineBasicBlock *DefBB = nullptr;
if (DefMI) {
DefBB = DefMI->getParent();
SSAUpdate.AddAvailableValue(DefBB, VReg);
// Rewrite uses that are outside of the original def's block.
MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg);
while (UI != MRI->use_end()) {
- MachineOperand &UseMO = UI.getOperand();
- MachineInstr *UseMI = &*UI;
+ MachineOperand &UseMO = *UI;
+ MachineInstr *UseMI = UseMO.getParent();
++UI;
if (UseMI->isDebugValue()) {
// SSAUpdate can replace the use with an undef. That creates
return true;
}
-/// TailDuplicateBlocks - Look for small blocks that are unconditionally
-/// branched to and do not fall through. Tail-duplicate their instructions
-/// into their predecessors to eliminate (dynamic) branches.
+/// Look for small blocks that are unconditionally branched to and do not fall
+/// through. Tail-duplicate their instructions into their predecessors to
+/// eliminate (dynamic) branches.
bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) {
bool MadeChange = false;
}
for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
- MachineBasicBlock *MBB = I++;
+ MachineBasicBlock *MBB = &*I++;
if (NumTails == TailDupLimit)
break;
static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB,
const MachineRegisterInfo *MRI) {
- for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
- UE = MRI->use_end(); UI != UE; ++UI) {
- MachineInstr *UseMI = &*UI;
- if (UseMI->isDebugValue())
+ for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
+ if (UseMI.isDebugValue())
continue;
- if (UseMI->getParent() != BB)
+ if (UseMI.getParent() != BB)
return true;
}
return false;
// block (which is why we need to copy the information).
static void getRegsUsedByPHIs(const MachineBasicBlock &BB,
DenseSet<unsigned> *UsedByPhi) {
- for(MachineBasicBlock::const_iterator I = BB.begin(), E = BB.end();
- I != E; ++I) {
- const MachineInstr &MI = *I;
+ for (const auto &MI : BB) {
if (!MI.isPHI())
break;
for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
}
}
-/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for
-/// SSA update.
+/// Add a definition and source virtual registers pair for SSA update.
void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
MachineBasicBlock *BB) {
DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg);
}
}
-/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB.
-/// Remember the source register that's contributed by PredBB and update SSA
-/// update map.
+/// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the
+/// source register that's contributed by PredBB and update SSA update map.
void TailDuplicatePass::ProcessPHI(
MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,
DenseMap<unsigned, unsigned> &LocalVRMap,
MI->eraseFromParent();
}
-/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update
+/// Duplicate a TailBB instruction to PredBB and update
/// the source operands due to earlier PHI translation.
void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI,
MachineBasicBlock *TailBB,
DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg);
if (VI != LocalVRMap.end()) {
MO.setReg(VI->second);
+ // Clear any kill flags from this operand. The new register could have
+ // uses after this one, so kills are not valid here.
+ MO.setIsKill(false);
MRI->constrainRegClass(VI->second, MRI->getRegClass(Reg));
}
}
PredBB->insert(PredBB->instr_end(), NewMI);
}
-/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor
-/// blocks, the successors have gained new predecessors. Update the PHI
-/// instructions in them accordingly.
+/// After FromBB is tail duplicated into its predecessor blocks, the successors
+/// have gained new predecessors. Update the PHI instructions in them
+/// accordingly.
void
TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
SmallVectorImpl<MachineBasicBlock *> &TDBBs,
}
}
-/// shouldTailDuplicate - Determine if it is profitable to duplicate this block.
+/// Determine if it is profitable to duplicate this block.
bool
TailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF,
bool IsSimple,
// compensate for the duplication.
unsigned MaxDuplicateCount;
if (TailDuplicateSize.getNumOccurrences() == 0 &&
- MF.getFunction()->getAttributes().
- hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize))
+ // FIXME: Use Function::optForSize().
+ MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize))
MaxDuplicateCount = 1;
else
MaxDuplicateCount = TailDuplicateSize;
// Check the instructions in the block to determine whether tail-duplication
// is invalid or unlikely to be profitable.
unsigned InstrCount = 0;
- for (MachineBasicBlock::iterator I = TailBB.begin(); I != TailBB.end(); ++I) {
+ for (MachineInstr &MI : TailBB) {
// Non-duplicable things shouldn't be tail-duplicated.
- if (I->isNotDuplicable())
+ if (MI.isNotDuplicable())
return false;
// Do not duplicate 'return' instructions if this is a pre-regalloc run.
// A return may expand into a lot more instructions (e.g. reload of callee
// saved registers) after PEI.
- if (PreRegAlloc && I->isReturn())
+ if (PreRegAlloc && MI.isReturn())
return false;
// Avoid duplicating calls before register allocation. Calls presents a
// barrier to register allocation so duplicating them may end up increasing
// spills.
- if (PreRegAlloc && I->isCall())
+ if (PreRegAlloc && MI.isCall())
return false;
- if (!I->isPHI() && !I->isDebugValue())
+ if (!MI.isPHI() && !MI.isDebugValue())
InstrCount += 1;
if (InstrCount > MaxDuplicateCount)
return false;
}
+ // Check if any of the successors of TailBB has a PHI node in which the
+ // value corresponding to TailBB uses a subregister.
+ // If a phi node uses a register paired with a subregister, the actual
+ // "value type" of the phi may differ from the type of the register without
+ // any subregisters. Due to a bug, tail duplication may add a new operand
+ // without a necessary subregister, producing an invalid code. This is
+ // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll.
+ // Disable tail duplication for this case for now, until the problem is
+ // fixed.
+ for (auto SB : TailBB.successors()) {
+ for (auto &I : *SB) {
+ if (!I.isPHI())
+ break;
+ unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
+ assert(Idx != 0);
+ MachineOperand &PU = I.getOperand(Idx);
+ if (PU.getSubReg() != 0)
+ return false;
+ }
+ }
+
if (HasIndirectbr && PreRegAlloc)
return true;
return canCompletelyDuplicateBB(TailBB);
}
-/// isSimpleBB - True if this BB has only one unconditional jump.
+/// True if this BB has only one unconditional jump.
bool
TailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) {
if (TailBB->succ_size() != 1)
return false;
if (TailBB->pred_empty())
return false;
- MachineBasicBlock::iterator I = TailBB->begin();
- MachineBasicBlock::iterator E = TailBB->end();
- while (I != E && I->isDebugValue())
- ++I;
- if (I == E)
+ MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr();
+ if (I == TailBB->end())
return true;
return I->isUnconditionalBranch();
}
static bool
bothUsedInPHI(const MachineBasicBlock &A,
SmallPtrSet<MachineBasicBlock*, 8> SuccsB) {
- for (MachineBasicBlock::const_succ_iterator SI = A.succ_begin(),
- SE = A.succ_end(); SI != SE; ++SI) {
- MachineBasicBlock *BB = *SI;
+ for (MachineBasicBlock *BB : A.successors())
if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI())
return true;
- }
return false;
}
bool
TailDuplicatePass::canCompletelyDuplicateBB(MachineBasicBlock &BB) {
- for (MachineBasicBlock::pred_iterator PI = BB.pred_begin(),
- PE = BB.pred_end(); PI != PE; ++PI) {
- MachineBasicBlock *PredBB = *PI;
-
+ for (MachineBasicBlock *PredBB : BB.predecessors()) {
if (PredBB->succ_size() > 1)
return false;
- MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL;
+ MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
SmallVector<MachineOperand, 4> PredCond;
if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true))
return false;
PE = Preds.end(); PI != PE; ++PI) {
MachineBasicBlock *PredBB = *PI;
- if (PredBB->getLandingPadSuccessor())
+ if (PredBB->hasEHPadSuccessor())
continue;
if (bothUsedInPHI(*PredBB, Succs))
continue;
- MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL;
+ MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
SmallVector<MachineOperand, 4> PredCond;
if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true))
continue;
<< "From simple Succ: " << *TailBB);
MachineBasicBlock *NewTarget = *TailBB->succ_begin();
- MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(PredBB));
+ MachineBasicBlock *NextBB = &*std::next(PredBB->getIterator());
// Make PredFBB explicit.
if (PredCond.empty())
// Make the branch unconditional if possible
if (PredTBB == PredFBB) {
PredCond.clear();
- PredFBB = NULL;
+ PredFBB = nullptr;
}
// Avoid adding fall through branches.
if (PredFBB == NextBB)
- PredFBB = NULL;
- if (PredTBB == NextBB && PredFBB == NULL)
- PredTBB = NULL;
+ PredFBB = nullptr;
+ if (PredTBB == NextBB && PredFBB == nullptr)
+ PredTBB = nullptr;
TII->RemoveBranch(*PredBB);
if (PredTBB)
TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc());
+ auto Prob = MBPI->getEdgeProbability(PredBB, TailBB);
PredBB->removeSuccessor(TailBB);
unsigned NumSuccessors = PredBB->succ_size();
assert(NumSuccessors <= 1);
if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget)
- PredBB->addSuccessor(NewTarget);
+ PredBB->addSuccessor(NewTarget, Prob);
TDBBs.push_back(PredBB);
}
return Changed;
}
-/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each
+/// If it is profitable, duplicate TailBB's contents in each
/// of its predecessors.
bool
TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB,
// Update PredBB livein.
RS->enterBasicBlock(PredBB);
if (!PredBB->empty())
- RS->forward(prior(PredBB->end()));
- BitVector RegsLiveAtExit(TRI->getNumRegs());
- RS->getRegsUsed(RegsLiveAtExit, false);
- for (MachineBasicBlock::livein_iterator I = TailBB->livein_begin(),
- E = TailBB->livein_end(); I != E; ++I) {
- if (!RegsLiveAtExit[*I])
+ RS->forward(std::prev(PredBB->end()));
+ for (const auto &LI : TailBB->liveins()) {
+ if (!RS->isRegUsed(LI.PhysReg, false))
// If a register is previously livein to the tail but it's not live
// at the end of predecessor BB, then it should be added to its
// livein list.
- PredBB->addLiveIn(*I);
+ PredBB->addLiveIn(LI);
}
}
"TailDuplicate called on block with multiple successors!");
for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(),
E = TailBB->succ_end(); I != E; ++I)
- PredBB->addSuccessor(*I);
+ PredBB->addSuccessor(*I, MBPI->getEdgeProbability(TailBB, I));
Changed = true;
++NumTailDups;
// If TailBB was duplicated into all its predecessors except for the prior
// block, which falls through unconditionally, move the contents of this
// block into the prior block.
- MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB));
- MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
+ MachineBasicBlock *PrevBB = &*std::prev(TailBB->getIterator());
+ MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
SmallVector<MachineOperand, 4> PriorCond;
// This has to check PrevBB->succ_size() because EH edges are ignored by
// AnalyzeBranch.
return Changed;
}
-/// RemoveDeadBlock - Remove the specified dead machine basic block from the
-/// function, updating the CFG.
+/// Remove the specified dead machine basic block from the function, updating
+/// the CFG.
void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) {
assert(MBB->pred_empty() && "MBB must be dead!");
DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
projects / oota-llvm.git / blobdiff