X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FBranchFolding.cpp;h=5eb32f18b8a7eb05bf9fc8fc579ba086398846f2;hb=8d36360b15d9fad9833c86df71d047a7b99881bb;hp=f990e10086431173b017c85a6171942b3440c648;hpb=cdb417eadaf122a374da7b685d55c961bef3d01e;p=oota-llvm.git diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index f990e100864..5eb32f18b8a 100644 --- a/lib/CodeGen/BranchFolding.cpp +++ b/lib/CodeGen/BranchFolding.cpp @@ -21,6 +21,7 @@ #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" @@ -96,7 +97,7 @@ bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) { // 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(), getAnalysis()); @@ -133,6 +134,7 @@ void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { // Remove the block. MF->erase(MBB); + FuncletMembership.erase(MBB); } /// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def @@ -220,6 +222,9 @@ bool BranchFolder::OptimizeFunction(MachineFunction &MF, MadeChange |= OptimizeImpDefsBlock(&MBB); } + // Recalculate funclet membership. + FuncletMembership = getFuncletMembership(MF); + bool MadeChangeThisIteration = true; while (MadeChangeThisIteration) { MadeChangeThisIteration = TailMergeBlocks(MF); @@ -427,7 +432,7 @@ MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, 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); @@ -446,6 +451,11 @@ MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, // 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; } @@ -480,7 +490,7 @@ static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, 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); @@ -550,14 +560,23 @@ static unsigned CountTerminators(MachineBasicBlock *MBB, /// 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 &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; @@ -634,7 +653,8 @@ unsigned BranchFolder::ComputeSameTails(unsigned CurHash, if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(), minCommonTailLength, CommonTailLen, TrialBBI1, TrialBBI2, - SuccBB, PredBB)) { + SuccBB, PredBB, + FuncletMembership)) { if (CommonTailLen > maxCommonTailLength) { SameTails.clear(); maxCommonTailLength = CommonTailLen; @@ -840,8 +860,8 @@ bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, // 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. @@ -957,8 +977,8 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { I != E; ++I) { if (I->pred_size() < 2) continue; SmallPtrSet 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) @@ -976,7 +996,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { continue; // Skip blocks which may jump to a landing pad. Can't tail merge these. - if (PBB->getLandingPadSuccessor()) + if (PBB->hasEHPadSuccessor()) continue; MachineBasicBlock *TBB = nullptr, *FBB = nullptr; @@ -989,18 +1009,21 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { 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; @@ -1041,7 +1064,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { // 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); @@ -1097,10 +1120,12 @@ bool BranchFolder::OptimizeBranches(MachineFunction &MF) { // 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. @@ -1110,6 +1135,7 @@ bool BranchFolder::OptimizeBranches(MachineFunction &MF) { ++NumDeadBlocks; } } + return MadeChange; } @@ -1166,14 +1192,25 @@ bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { 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; @@ -1189,12 +1226,12 @@ ReoptimizeBlock: // 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; @@ -1332,7 +1369,7 @@ ReoptimizeBlock: 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; @@ -1472,7 +1509,6 @@ ReoptimizeBlock: // 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 PredCond; if (PredBB != MBB && !PredBB->canFallThrough() && @@ -1490,8 +1526,7 @@ ReoptimizeBlock: // 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()); } @@ -1506,7 +1541,7 @@ ReoptimizeBlock: // 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, @@ -1528,8 +1563,8 @@ ReoptimizeBlock: SmallVector PrevCond; 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; } @@ -1548,7 +1583,7 @@ ReoptimizeBlock: 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); }