#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/Analysis.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
// TailMerge can create jump into if branches that make CFG irreducible for
// HW that requires structurized CFG.
bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
- PassConfig->getEnableTailMerge();
+ PassConfig->getEnableTailMerge();
BranchFolder Folder(EnableTailMerge, /*CommonHoist=*/true,
getAnalysis<MachineBlockFrequencyInfo>(),
getAnalysis<MachineBranchProbabilityInfo>());
// Remove the block.
MF->erase(MBB);
+ FuncletMembership.erase(MBB);
}
/// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def
MadeChange |= OptimizeImpDefsBlock(&MBB);
}
+ // Recalculate funclet membership.
+ FuncletMembership = getFuncletMembership(MF);
+
bool MadeChangeThisIteration = true;
while (MadeChangeThisIteration) {
MadeChangeThisIteration = TailMergeBlocks(MF);
}
// Back past possible debugging pseudos at beginning of block. This matters
// when one block differs from the other only by whether debugging pseudos
- // are present at the beginning. (This way, the various checks later for
+ // are present at the beginning. (This way, the various checks later for
// I1==MBB1->begin() work as expected.)
if (I1 == MBB1->begin() && I2 != MBB2->begin()) {
--I2;
MachineFunction &MF = *CurMBB.getParent();
// Create the fall-through block.
- MachineFunction::iterator MBBI = &CurMBB;
+ MachineFunction::iterator MBBI = CurMBB.getIterator();
MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(BB);
CurMBB.getParent()->insert(++MBBI, NewMBB);
// For targets that use the register scavenger, we must maintain LiveIns.
MaintainLiveIns(&CurMBB, NewMBB);
+ // Add the new block to the funclet.
+ const auto &FuncletI = FuncletMembership.find(&CurMBB);
+ if (FuncletI != FuncletMembership.end())
+ FuncletMembership[NewMBB] = FuncletI->second;
+
return NewMBB;
}
DebugLoc dl; // FIXME: this is nowhere
if (I != MF->end() &&
!TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {
- MachineBasicBlock *NextBB = I;
+ MachineBasicBlock *NextBB = &*I;
if (TBB == NextBB && !Cond.empty() && !FBB) {
if (!TII->ReverseBranchCondition(Cond)) {
TII->RemoveBranch(*CurMBB);
/// and decide if it would be profitable to merge those tails. Return the
/// length of the common tail and iterators to the first common instruction
/// in each block.
-static bool ProfitableToMerge(MachineBasicBlock *MBB1,
- MachineBasicBlock *MBB2,
- unsigned minCommonTailLength,
- unsigned &CommonTailLen,
- MachineBasicBlock::iterator &I1,
- MachineBasicBlock::iterator &I2,
- MachineBasicBlock *SuccBB,
- MachineBasicBlock *PredBB) {
+static bool
+ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2,
+ unsigned minCommonTailLength, unsigned &CommonTailLen,
+ MachineBasicBlock::iterator &I1,
+ MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB,
+ MachineBasicBlock *PredBB,
+ DenseMap<const MachineBasicBlock *, int> &FuncletMembership) {
+ // It is never profitable to tail-merge blocks from two different funclets.
+ if (!FuncletMembership.empty()) {
+ auto Funclet1 = FuncletMembership.find(MBB1);
+ assert(Funclet1 != FuncletMembership.end());
+ auto Funclet2 = FuncletMembership.find(MBB2);
+ assert(Funclet2 != FuncletMembership.end());
+ if (Funclet1->second != Funclet2->second)
+ return false;
+ }
+
CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
if (CommonTailLen == 0)
return false;
// branch instruction, which is likely to be smaller than the 2
// instructions that would be deleted in the merge.
MachineFunction *MF = MBB1->getParent();
- if (EffectiveTailLen >= 2 && MF->getFunction()->optForSize() &&
- (I1 == MBB1->begin() || I2 == MBB2->begin()))
- return true;
-
- return false;
+ return EffectiveTailLen >= 2 && MF->getFunction()->optForSize() &&
+ (I1 == MBB1->begin() || I2 == MBB2->begin());
}
/// ComputeSameTails - Look through all the blocks in MergePotentials that have
if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
minCommonTailLength,
CommonTailLen, TrialBBI1, TrialBBI2,
- SuccBB, PredBB)) {
+ SuccBB, PredBB,
+ FuncletMembership)) {
if (CommonTailLen > maxCommonTailLength) {
SameTails.clear();
maxCommonTailLength = CommonTailLen;
// block, which we can't jump to), we can treat all blocks with this same
// tail at once. Use PredBB if that is one of the possibilities, as that
// will not introduce any extra branches.
- MachineBasicBlock *EntryBB = MergePotentials.begin()->getBlock()->
- getParent()->begin();
+ MachineBasicBlock *EntryBB =
+ &MergePotentials.front().getBlock()->getParent()->front();
unsigned commonTailIndex = SameTails.size();
// If there are two blocks, check to see if one can be made to fall through
// into the other.
I != E; ++I) {
if (I->pred_size() < 2) continue;
SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;
- MachineBasicBlock *IBB = I;
- MachineBasicBlock *PredBB = std::prev(I);
+ MachineBasicBlock *IBB = &*I;
+ MachineBasicBlock *PredBB = &*std::prev(I);
MergePotentials.clear();
for (MachineBasicBlock *PBB : I->predecessors()) {
if (MergePotentials.size() == TailMergeThreshold)
if (TII->ReverseBranchCondition(NewCond))
continue;
// This is the QBB case described above
- if (!FBB)
- FBB = std::next(MachineFunction::iterator(PBB));
+ if (!FBB) {
+ auto Next = ++PBB->getIterator();
+ if (Next != MF.end())
+ FBB = &*Next;
+ }
}
// Failing case: the only way IBB can be reached from PBB is via
// exception handling. Happens for landing pads. Would be nice to have
// a bit in the edge so we didn't have to do all this.
if (IBB->isEHPad()) {
- MachineFunction::iterator IP = PBB; IP++;
+ MachineFunction::iterator IP = ++PBB->getIterator();
MachineBasicBlock *PredNextBB = nullptr;
if (IP != MF.end())
- PredNextBB = IP;
+ PredNextBB = &*IP;
if (!TBB) {
if (IBB != PredNextBB) // fallthrough
continue;
// Reinsert an unconditional branch if needed. The 1 below can occur as a
// result of removing blocks in TryTailMergeBlocks.
- PredBB = std::prev(I); // this may have been changed in TryTailMergeBlocks
+ PredBB = &*std::prev(I); // this may have been changed in TryTailMergeBlocks
if (MergePotentials.size() == 1 &&
MergePotentials.begin()->getBlock() != PredBB)
FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
if (TailMBB.succ_size() <= 1)
return;
- auto MaxEdgeFreq = *std::max_element(EdgeFreqLs.begin(), EdgeFreqLs.end());
- uint64_t Scale = MaxEdgeFreq.getFrequency() / UINT32_MAX + 1;
+ auto SumEdgeFreq =
+ std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0))
+ .getFrequency();
auto EdgeFreq = EdgeFreqLs.begin();
- for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
- SuccI != SuccE; ++SuccI, ++EdgeFreq)
- TailMBB.setSuccWeight(SuccI, EdgeFreq->getFrequency() / Scale);
+ if (SumEdgeFreq > 0) {
+ for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
+ SuccI != SuccE; ++SuccI, ++EdgeFreq) {
+ auto Prob = BranchProbability::getBranchProbability(
+ EdgeFreq->getFrequency(), SumEdgeFreq);
+ TailMBB.setSuccProbability(SuccI, Prob);
+ }
+ }
}
//===----------------------------------------------------------------------===//
// Make sure blocks are numbered in order
MF.RenumberBlocks();
+ // Renumbering blocks alters funclet membership, recalculate it.
+ FuncletMembership = getFuncletMembership(MF);
for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
I != E; ) {
- MachineBasicBlock *MBB = I++;
+ MachineBasicBlock *MBB = &*I++;
MadeChange |= OptimizeBlock(MBB);
// If it is dead, remove it.
++NumDeadBlocks;
}
}
+
return MadeChange;
}
MachineFunction &MF = *MBB->getParent();
ReoptimizeBlock:
- MachineFunction::iterator FallThrough = MBB;
+ MachineFunction::iterator FallThrough = MBB->getIterator();
++FallThrough;
+ // Make sure MBB and FallThrough belong to the same funclet.
+ bool SameFunclet = true;
+ if (!FuncletMembership.empty() && FallThrough != MF.end()) {
+ auto MBBFunclet = FuncletMembership.find(MBB);
+ assert(MBBFunclet != FuncletMembership.end());
+ auto FallThroughFunclet = FuncletMembership.find(&*FallThrough);
+ assert(FallThroughFunclet != FuncletMembership.end());
+ SameFunclet = MBBFunclet->second == FallThroughFunclet->second;
+ }
+
// If this block is empty, make everyone use its fall-through, not the block
// explicitly. Landing pads should not do this since the landing-pad table
// points to this block. Blocks with their addresses taken shouldn't be
// optimized away.
- if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken()) {
+ if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&
+ SameFunclet) {
// Dead block? Leave for cleanup later.
if (MBB->pred_empty()) return MadeChange;
// instead.
while (!MBB->pred_empty()) {
MachineBasicBlock *Pred = *(MBB->pred_end()-1);
- Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);
+ Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);
}
// If MBB was the target of a jump table, update jump tables to go to the
// fallthrough instead.
if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
- MJTI->ReplaceMBBInJumpTables(MBB, FallThrough);
+ MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);
MadeChange = true;
}
return MadeChange;
TII->InsertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);
// Move this block to the end of the function.
- MBB->moveAfter(--MF.end());
+ MBB->moveAfter(&MF.back());
MadeChange = true;
++NumBranchOpts;
return MadeChange;
// other blocks across it.
if (CurTBB && CurCond.empty() && !CurFBB &&
IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
- !MBB->hasAddressTaken()) {
+ !MBB->hasAddressTaken() && !MBB->isEHPad()) {
DebugLoc dl = getBranchDebugLoc(*MBB);
// This block may contain just an unconditional branch. Because there can
// be 'non-branch terminators' in the block, try removing the branch and
// throughs, move this block right after it.
for (MachineBasicBlock *PredBB : MBB->predecessors()) {
// Analyze the branch at the end of the pred.
- MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
SmallVector<MachineOperand, 4> PredCond;
if (PredBB != MBB && !PredBB->canFallThrough() &&
// B elsewhere
// next:
if (CurFallsThru) {
- MachineBasicBlock *NextBB =
- std::next(MachineFunction::iterator(MBB));
+ MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());
CurCond.clear();
TII->InsertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());
}
// Check all successors to see if we can move this block before it.
for (MachineBasicBlock *SuccBB : MBB->successors()) {
// Analyze the branch at the end of the block before the succ.
- MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev;
+ MachineFunction::iterator SuccPrev = --SuccBB->getIterator();
// If this block doesn't already fall-through to that successor, and if
// the succ doesn't already have a block that can fall through into it,
// removed, move this block to the end of the function.
MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
SmallVector<MachineOperand, 4> PrevCond;
+ // We're looking for cases where PrevBB could possibly fall through to
+ // FallThrough, but if FallThrough is an EH pad that wouldn't be useful
+ // so here we skip over any EH pads so we might have a chance to find
+ // a branch target from PrevBB.
+ while (FallThrough != MF.end() && FallThrough->isEHPad())
+ ++FallThrough;
+ // Now check to see if the current block is sitting between PrevBB and
+ // a block to which it could fall through.
if (FallThrough != MF.end() &&
!TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
- PrevBB.isSuccessor(FallThrough)) {
- MBB->moveAfter(--MF.end());
+ PrevBB.isSuccessor(&*FallThrough)) {
+ MBB->moveAfter(&MF.back());
MadeChange = true;
return MadeChange;
}
bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
bool MadeChange = false;
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ) {
- MachineBasicBlock *MBB = I++;
+ MachineBasicBlock *MBB = &*I++;
MadeChange |= HoistCommonCodeInSuccs(MBB);
}
projects / oota-llvm.git / blobdiff