#define DEBUG_TYPE "branchfolding"
#include "BranchFolding.h"
-#include "llvm/Function.h"
-#include "llvm/CodeGen/Passes.h"
-#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterScavenging.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/IR/Function.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/ADT/SmallSet.h"
-#include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/STLExtras.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetRegisterInfo.h"
#include <algorithm>
using namespace llvm;
static char ID;
explicit BranchFolderPass(): MachineFunctionPass(ID) {}
- virtual bool runOnMachineFunction(MachineFunction &MF);
+ bool runOnMachineFunction(MachineFunction &MF) override;
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<TargetPassConfig>();
MachineFunctionPass::getAnalysisUsage(AU);
}
bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
- BranchFolder Folder(PassConfig->getEnableTailMerge(), /*CommonHoist=*/true);
+ // TailMerge can create jump into if branches that make CFG irreducible for
+ // HW that requires structurized CFG.
+ bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
+ PassConfig->getEnableTailMerge();
+ BranchFolder Folder(EnableTailMerge, /*CommonHoist=*/true);
return Folder.OptimizeFunction(MF,
MF.getTarget().getInstrInfo(),
MF.getTarget().getRegisterInfo(),
if (!I->isImplicitDef())
break;
unsigned Reg = I->getOperand(0).getReg();
- ImpDefRegs.insert(Reg);
- for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
+ for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
+ SubRegs.isValid(); ++SubRegs)
ImpDefRegs.insert(*SubRegs);
++I;
}
if (I1 == MBB1->begin() && I2 != MBB2->begin()) {
--I2;
while (I2->isDebugValue()) {
- if (I2 == MBB2->begin()) {
+ if (I2 == MBB2->begin())
return TailLen;
- }
--I2;
}
++I2;
if (RS) {
RS->enterBasicBlock(CurMBB);
if (!CurMBB->empty())
- RS->forward(prior(CurMBB->end()));
+ RS->forward(std::prev(CurMBB->end()));
BitVector RegsLiveAtExit(TRI->getNumRegs());
RS->getRegsUsed(RegsLiveAtExit, false);
for (unsigned int i = 0, e = TRI->getNumRegs(); i != e; i++)
/// MBB so that the part before the iterator falls into the part starting at the
/// iterator. This returns the new MBB.
MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
- MachineBasicBlock::iterator BBI1) {
+ MachineBasicBlock::iterator BBI1,
+ const BasicBlock *BB) {
if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))
return 0;
// Create the fall-through block.
MachineFunction::iterator MBBI = &CurMBB;
- MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(CurMBB.getBasicBlock());
+ MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(BB);
CurMBB.getParent()->insert(++MBBI, NewMBB);
// Move all the successors of this block to the specified block.
static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
const TargetInstrInfo *TII) {
MachineFunction *MF = CurMBB->getParent();
- MachineFunction::iterator I = llvm::next(MachineFunction::iterator(CurMBB));
+ MachineFunction::iterator I = std::next(MachineFunction::iterator(CurMBB));
MachineBasicBlock *TBB = 0, *FBB = 0;
SmallVector<MachineOperand, 4> Cond;
DebugLoc dl; // FIXME: this is nowhere
BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const {
if (getHash() < o.getHash())
return true;
- else if (getHash() > o.getHash())
+ if (getHash() > o.getHash())
return false;
- else if (getBlock()->getNumber() < o.getBlock()->getNumber())
+ if (getBlock()->getNumber() < o.getBlock()->getNumber())
return true;
- else if (getBlock()->getNumber() > o.getBlock()->getNumber())
+ if (getBlock()->getNumber() > o.getBlock()->getNumber())
return false;
- else {
- // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
- // an object with itself.
+ // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
+ // an object with itself.
#ifndef _GLIBCXX_DEBUG
- llvm_unreachable("Predecessor appears twice");
+ llvm_unreachable("Predecessor appears twice");
#else
- return false;
+ return false;
#endif
- }
}
/// CountTerminators - Count the number of terminators in the given
// instructions that would be deleted in the merge.
MachineFunction *MF = MBB1->getParent();
if (EffectiveTailLen >= 2 &&
- MF->getFunction()->hasFnAttr(Attribute::OptimizeForSize) &&
+ MF->getFunction()->getAttributes().
+ hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize) &&
(I1 == MBB1->begin() || I2 == MBB2->begin()))
return true;
unsigned maxCommonTailLength = 0U;
SameTails.clear();
MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
- MPIterator HighestMPIter = prior(MergePotentials.end());
- for (MPIterator CurMPIter = prior(MergePotentials.end()),
+ MPIterator HighestMPIter = std::prev(MergePotentials.end());
+ for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
B = MergePotentials.begin();
- CurMPIter != B && CurMPIter->getHash() == CurHash;
- --CurMPIter) {
- for (MPIterator I = prior(CurMPIter); I->getHash() == CurHash ; --I) {
+ CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {
+ for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {
unsigned CommonTailLen;
if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
minCommonTailLength,
MachineBasicBlock *SuccBB,
MachineBasicBlock *PredBB) {
MPIterator CurMPIter, B;
- for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin();
- CurMPIter->getHash() == CurHash;
- --CurMPIter) {
+ for (CurMPIter = std::prev(MergePotentials.end()),
+ B = MergePotentials.begin();
+ CurMPIter->getHash() == CurHash; --CurMPIter) {
// Put the unconditional branch back, if we need one.
MachineBasicBlock *CurMBB = CurMPIter->getBlock();
if (SuccBB && CurMBB != PredBB)
/// CreateCommonTailOnlyBlock - None of the blocks to be tail-merged consist
/// only of the common tail. Create a block that does by splitting one.
bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
+ MachineBasicBlock *SuccBB,
unsigned maxCommonTailLength,
unsigned &commonTailIndex) {
commonTailIndex = 0;
DEBUG(dbgs() << "\nSplitting BB#" << MBB->getNumber() << ", size "
<< maxCommonTailLength);
- MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI);
+ // If the split block unconditionally falls-thru to SuccBB, it will be
+ // merged. In control flow terms it should then take SuccBB's name. e.g. If
+ // SuccBB is an inner loop, the common tail is still part of the inner loop.
+ const BasicBlock *BB = (SuccBB && MBB->succ_size() == 1) ?
+ SuccBB->getBasicBlock() : MBB->getBasicBlock();
+ MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI, BB);
if (!newMBB) {
DEBUG(dbgs() << "... failed!");
return false;
!SameTails[commonTailIndex].tailIsWholeBlock())) {
// None of the blocks consist entirely of the common tail.
// Split a block so that one does.
- if (!CreateCommonTailOnlyBlock(PredBB,
+ if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,
maxCommonTailLength, commonTailIndex)) {
RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
continue;
// a compile-time infinite loop repeatedly doing and undoing the same
// transformations.)
- for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end();
+ for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
I != E; ++I) {
if (I->pred_size() < 2) continue;
SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;
MachineBasicBlock *IBB = I;
- MachineBasicBlock *PredBB = prior(I);
+ MachineBasicBlock *PredBB = std::prev(I);
MergePotentials.clear();
for (MachineBasicBlock::pred_iterator P = I->pred_begin(),
E2 = I->pred_end();
continue;
// This is the QBB case described above
if (!FBB)
- FBB = llvm::next(MachineFunction::iterator(PBB));
+ FBB = std::next(MachineFunction::iterator(PBB));
}
// Failing case: the only way IBB can be reached from PBB is via
// Reinsert an unconditional branch if needed. The 1 below can occur as a
// result of removing blocks in TryTailMergeBlocks.
- PredBB = prior(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);
// Make sure blocks are numbered in order
MF.RenumberBlocks();
- for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end();
+ for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
I != E; ) {
MachineBasicBlock *MBB = I++;
MadeChange |= OptimizeBlock(MBB);
// Check to see if we can simplify the terminator of the block before this
// one.
- MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));
+ MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
SmallVector<MachineOperand, 4> PriorCond;
// B elsewhere
// next:
if (CurFallsThru) {
- MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB));
+ MachineBasicBlock *NextBB =
+ std::next(MachineFunction::iterator(MBB));
CurCond.clear();
TII->InsertBranch(*MBB, NextBB, 0, CurCond, DebugLoc());
}
// branch from condition setting instruction.
MachineBasicBlock::iterator PI = Loc;
--PI;
- while (PI != MBB->begin() && Loc->isDebugValue())
+ while (PI != MBB->begin() && PI->isDebugValue())
--PI;
bool IsDef = false;
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
Uses.insert(*AI);
} else {
- if (Uses.count(Reg)) {
- Uses.erase(Reg);
+ if (Uses.erase(Reg)) {
for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
Uses.erase(*SubRegs); // Use sub-registers to be conservative
}
projects / oota-llvm.git / blobdiff