summaryrefslogtreecommitdiffstats
path: root/contrib/llvm/lib/CodeGen/TailDuplication.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/lib/CodeGen/TailDuplication.cpp')
-rw-r--r--contrib/llvm/lib/CodeGen/TailDuplication.cpp115
1 files changed, 64 insertions, 51 deletions
diff --git a/contrib/llvm/lib/CodeGen/TailDuplication.cpp b/contrib/llvm/lib/CodeGen/TailDuplication.cpp
index 237460c..d2fbf53 100644
--- a/contrib/llvm/lib/CodeGen/TailDuplication.cpp
+++ b/contrib/llvm/lib/CodeGen/TailDuplication.cpp
@@ -59,7 +59,7 @@ TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden);
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;
@@ -69,11 +69,11 @@ namespace {
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:
@@ -161,7 +161,7 @@ void TailDuplicatePass::getAnalysisUsage(AnalysisUsage &AU) const {
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();
@@ -207,7 +207,7 @@ static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {
}
}
-/// TailDuplicateAndUpdate - Tail duplicate the block and cleanup.
+/// Tail duplicate the block and cleanup.
bool
TailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB,
bool IsSimple,
@@ -310,9 +310,9 @@ TailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB,
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;
@@ -322,7 +322,7 @@ bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) {
}
for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
- MachineBasicBlock *MBB = I++;
+ MachineBasicBlock *MBB = &*I++;
if (NumTails == TailDupLimit)
break;
@@ -375,8 +375,7 @@ static void getRegsUsedByPHIs(const MachineBasicBlock &BB,
}
}
-/// 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);
@@ -390,9 +389,8 @@ void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
}
}
-/// 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,
@@ -422,7 +420,7 @@ void TailDuplicatePass::ProcessPHI(
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,
@@ -459,9 +457,9 @@ void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI,
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,
@@ -545,7 +543,7 @@ TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
}
}
-/// 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,
@@ -563,6 +561,7 @@ TailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF,
// compensate for the duplication.
unsigned MaxDuplicateCount;
if (TailDuplicateSize.getNumOccurrences() == 0 &&
+ // FIXME: Use Function::optForSize().
MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize))
MaxDuplicateCount = 1;
else
@@ -584,30 +583,51 @@ TailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF,
// 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;
@@ -620,7 +640,7 @@ TailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF,
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)
@@ -636,22 +656,16 @@ TailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) {
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;
@@ -680,7 +694,7 @@ TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB,
PE = Preds.end(); PI != PE; ++PI) {
MachineBasicBlock *PredBB = *PI;
- if (PredBB->getLandingPadSuccessor())
+ if (PredBB->hasEHPadSuccessor())
continue;
if (bothUsedInPHI(*PredBB, Succs))
@@ -696,7 +710,7 @@ TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB,
<< "From simple Succ: " << *TailBB);
MachineBasicBlock *NewTarget = *TailBB->succ_begin();
- MachineBasicBlock *NextBB = std::next(MachineFunction::iterator(PredBB));
+ MachineBasicBlock *NextBB = &*std::next(PredBB->getIterator());
// Make PredFBB explicit.
if (PredCond.empty())
@@ -731,19 +745,19 @@ TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB,
if (PredTBB)
TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc());
- uint32_t Weight = MBPI->getEdgeWeight(PredBB, TailBB);
- PredBB->removeSuccessor(TailBB);
- unsigned NumSuccessors = PredBB->succ_size();
- assert(NumSuccessors <= 1);
- if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget)
- PredBB->addSuccessor(NewTarget, Weight);
+ if (!PredBB->isSuccessor(NewTarget))
+ PredBB->replaceSuccessor(TailBB, NewTarget);
+ else {
+ PredBB->removeSuccessor(TailBB, true);
+ assert(PredBB->succ_size() <= 1);
+ }
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,
@@ -798,13 +812,12 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB,
RS->enterBasicBlock(PredBB);
if (!PredBB->empty())
RS->forward(std::prev(PredBB->end()));
- for (MachineBasicBlock::livein_iterator I = TailBB->livein_begin(),
- E = TailBB->livein_end(); I != E; ++I) {
- if (!RS->isRegUsed(*I, false))
+ 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);
}
}
@@ -845,7 +858,7 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB,
"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, MBPI->getEdgeWeight(TailBB, I));
+ PredBB->addSuccessor(*I, MBPI->getEdgeProbability(TailBB, I));
Changed = true;
++NumTailDups;
@@ -854,7 +867,7 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB,
// 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 = std::prev(MachineFunction::iterator(TailBB));
+ 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
@@ -960,8 +973,8 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB,
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);
OpenPOWER on IntegriCloud