X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FBranchFolding.cpp;h=60e8b52dff83e5866b72a2d54ef10135649f09b7;hb=cd52a7a381a73c53ec4ef517ad87f19808cb1a28;hp=95f0fa584b2c12986fcaade591b88b8ce26bfcf3;hpb=4ba844388c586ee40871a52dc9d6eab883fde1b7;p=oota-llvm.git diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index 95f0fa584b2..60e8b52dff8 100644 --- a/lib/CodeGen/BranchFolding.cpp +++ b/lib/CodeGen/BranchFolding.cpp @@ -16,13 +16,15 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "branchfolding" #include "BranchFolding.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineJumpTableInfo.h" +#include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" @@ -33,11 +35,13 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include using namespace llvm; +#define DEBUG_TYPE "branchfolding" + STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); STATISTIC(NumBranchOpts, "Number of branches optimized"); STATISTIC(NumTailMerge , "Number of block tails merged"); @@ -69,6 +73,8 @@ namespace { bool runOnMachineFunction(MachineFunction &MF) override; void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); AU.addRequired(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -90,22 +96,24 @@ bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) { // 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(), + BranchFolder Folder(EnableTailMerge, /*CommonHoist=*/true, + getAnalysis(), + getAnalysis()); + return Folder.OptimizeFunction(MF, MF.getSubtarget().getInstrInfo(), + MF.getSubtarget().getRegisterInfo(), getAnalysisIfAvailable()); } - -BranchFolder::BranchFolder(bool defaultEnableTailMerge, bool CommonHoist) { +BranchFolder::BranchFolder(bool defaultEnableTailMerge, bool CommonHoist, + const MachineBlockFrequencyInfo &FreqInfo, + const MachineBranchProbabilityInfo &ProbInfo) + : EnableHoistCommonCode(CommonHoist), MBBFreqInfo(FreqInfo), + MBPI(ProbInfo) { switch (FlagEnableTailMerge) { case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break; case cl::BOU_TRUE: EnableTailMerge = true; break; case cl::BOU_FALSE: EnableTailMerge = false; break; } - - EnableHoistCommonCode = CommonHoist; } /// RemoveDeadBlock - Remove the specified dead machine basic block from the @@ -265,8 +273,12 @@ static unsigned HashMachineInstr(const MachineInstr *MI) { // Merge in bits from the operand if easy. unsigned OperandHash = 0; switch (Op.getType()) { - case MachineOperand::MO_Register: OperandHash = Op.getReg(); break; - case MachineOperand::MO_Immediate: OperandHash = Op.getImm(); break; + case MachineOperand::MO_Register: + OperandHash = Op.getReg(); + break; + case MachineOperand::MO_Immediate: + OperandHash = Op.getImm(); + break; case MachineOperand::MO_MachineBasicBlock: OperandHash = Op.getMBB()->getNumber(); break; @@ -281,10 +293,11 @@ static unsigned HashMachineInstr(const MachineInstr *MI) { // pull in the offset. OperandHash = Op.getOffset(); break; - default: break; + default: + break; } - Hash += ((OperandHash << 3) | Op.getType()) << (i&31); + Hash += ((OperandHash << 3) | Op.getType()) << (i & 31); } return Hash; } @@ -293,13 +306,13 @@ static unsigned HashMachineInstr(const MachineInstr *MI) { static unsigned HashEndOfMBB(const MachineBasicBlock *MBB) { MachineBasicBlock::const_iterator I = MBB->end(); if (I == MBB->begin()) - return 0; // Empty MBB. + return 0; // Empty MBB. --I; // Skip debug info so it will not affect codegen. while (I->isDebugValue()) { - if (I==MBB->begin()) - return 0; // MBB empty except for debug info. + if (I == MBB->begin()) + return 0; // MBB empty except for debug info. --I; } @@ -387,10 +400,8 @@ void BranchFolder::MaintainLiveIns(MachineBasicBlock *CurMBB, RS->enterBasicBlock(CurMBB); if (!CurMBB->empty()) 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++) - if (RegsLiveAtExit[i]) + for (unsigned int i = 1, e = TRI->getNumRegs(); i != e; i++) + if (RS->isRegUsed(i, false)) NewMBB->addLiveIn(i); } } @@ -434,6 +445,9 @@ MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, // Splice the code over. NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end()); + // NewMBB inherits CurMBB's block frequency. + MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB)); + // For targets that use the register scavenger, we must maintain LiveIns. MaintainLiveIns(&CurMBB, NewMBB); @@ -503,6 +517,21 @@ BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const { #endif } +BlockFrequency +BranchFolder::MBFIWrapper::getBlockFreq(const MachineBasicBlock *MBB) const { + auto I = MergedBBFreq.find(MBB); + + if (I != MergedBBFreq.end()) + return I->second; + + return MBFI.getBlockFreq(MBB); +} + +void BranchFolder::MBFIWrapper::setBlockFreq(const MachineBasicBlock *MBB, + BlockFrequency F) { + MergedBBFreq[MBB] = F; +} + /// CountTerminators - Count the number of terminators in the given /// block and set I to the position of the first non-terminator, if there /// is one, or MBB->end() otherwise. @@ -578,8 +607,7 @@ static bool ProfitableToMerge(MachineBasicBlock *MBB1, // instructions that would be deleted in the merge. MachineFunction *MF = MBB1->getParent(); if (EffectiveTailLen >= 2 && - MF->getFunction()->getAttributes(). - hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize) && + MF->getFunction()->hasFnAttribute(Attribute::OptimizeForSize) && (I1 == MBB1->begin() || I2 == MBB2->begin())) return true; @@ -705,6 +733,62 @@ bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, return true; } +static bool hasIdenticalMMOs(const MachineInstr *MI1, const MachineInstr *MI2) { + auto I1 = MI1->memoperands_begin(), E1 = MI1->memoperands_end(); + auto I2 = MI2->memoperands_begin(), E2 = MI2->memoperands_end(); + if ((E1 - I1) != (E2 - I2)) + return false; + for (; I1 != E1; ++I1, ++I2) { + if (**I1 != **I2) + return false; + } + return true; +} + +static void +removeMMOsFromMemoryOperations(MachineBasicBlock::iterator MBBIStartPos, + MachineBasicBlock &MBBCommon) { + // Remove MMOs from memory operations in the common block + // when they do not match the ones from the block being tail-merged. + // This ensures later passes conservatively compute dependencies. + MachineBasicBlock *MBB = MBBIStartPos->getParent(); + // Note CommonTailLen does not necessarily matches the size of + // the common BB nor all its instructions because of debug + // instructions differences. + unsigned CommonTailLen = 0; + for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos) + ++CommonTailLen; + + MachineBasicBlock::reverse_iterator MBBI = MBB->rbegin(); + MachineBasicBlock::reverse_iterator MBBIE = MBB->rend(); + MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin(); + MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend(); + + while (CommonTailLen--) { + assert(MBBI != MBBIE && "Reached BB end within common tail length!"); + (void)MBBIE; + + if (MBBI->isDebugValue()) { + ++MBBI; + continue; + } + + while ((MBBICommon != MBBIECommon) && MBBICommon->isDebugValue()) + ++MBBICommon; + + assert(MBBICommon != MBBIECommon && + "Reached BB end within common tail length!"); + assert(MBBICommon->isIdenticalTo(&*MBBI) && "Expected matching MIIs!"); + + if (MBBICommon->mayLoad() || MBBICommon->mayStore()) + if (!hasIdenticalMMOs(&*MBBI, &*MBBICommon)) + MBBICommon->clearMemRefs(); + + ++MBBI; + ++MBBICommon; + } +} + // See if any of the blocks in MergePotentials (which all have a common single // successor, or all have no successor) can be tail-merged. If there is a // successor, any blocks in MergePotentials that are not tail-merged and @@ -739,7 +823,7 @@ bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, // Sort by hash value so that blocks with identical end sequences sort // together. - std::stable_sort(MergePotentials.begin(), MergePotentials.end()); + array_pod_sort(MergePotentials.begin(), MergePotentials.end()); // Walk through equivalence sets looking for actual exact matches. while (MergePotentials.size() > 1) { @@ -805,6 +889,10 @@ bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, } MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock(); + + // Recompute commont tail MBB's edge weights and block frequency. + setCommonTailEdgeWeights(*MBB); + // MBB is common tail. Adjust all other BB's to jump to this one. // Traversal must be forwards so erases work. DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber() @@ -814,6 +902,8 @@ bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, continue; DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber() << (i == e-1 ? "" : ", ")); + // Remove MMOs from memory operations as needed. + removeMMOsFromMemoryOperations(SameTails[i].getTailStartPos(), *MBB); // Hack the end off BB i, making it jump to BB commonTailIndex instead. ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB); // BB i is no longer a predecessor of SuccBB; remove it from the worklist. @@ -889,7 +979,7 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { continue; // Visit each predecessor only once. - if (!UniquePreds.insert(PBB)) + if (!UniquePreds.insert(PBB).second) continue; // Skip blocks which may jump to a landing pad. Can't tail merge these. @@ -967,6 +1057,44 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { return MadeChange; } +void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) { + SmallVector EdgeFreqLs(TailMBB.succ_size()); + BlockFrequency AccumulatedMBBFreq; + + // Aggregate edge frequency of successor edge j: + // edgeFreq(j) = sum (freq(bb) * edgeProb(bb, j)), + // where bb is a basic block that is in SameTails. + for (const auto &Src : SameTails) { + const MachineBasicBlock *SrcMBB = Src.getBlock(); + BlockFrequency BlockFreq = MBBFreqInfo.getBlockFreq(SrcMBB); + AccumulatedMBBFreq += BlockFreq; + + // It is not necessary to recompute edge weights if TailBB has less than two + // successors. + if (TailMBB.succ_size() <= 1) + continue; + + auto EdgeFreq = EdgeFreqLs.begin(); + + for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end(); + SuccI != SuccE; ++SuccI, ++EdgeFreq) + *EdgeFreq += BlockFreq * MBPI.getEdgeProbability(SrcMBB, *SuccI); + } + + MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq); + + if (TailMBB.succ_size() <= 1) + return; + + auto MaxEdgeFreq = *std::max_element(EdgeFreqLs.begin(), EdgeFreqLs.end()); + uint64_t Scale = MaxEdgeFreq.getFrequency() / UINT32_MAX + 1; + auto EdgeFreq = EdgeFreqLs.begin(); + + for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end(); + SuccI != SuccE; ++SuccI, ++EdgeFreq) + TailMBB.setSuccWeight(SuccI, EdgeFreq->getFrequency() / Scale); +} + //===----------------------------------------------------------------------===// // Branch Optimization //===----------------------------------------------------------------------===// @@ -1080,6 +1208,11 @@ ReoptimizeBlock: if (FallThrough == MF.end()) { // TODO: Simplify preds to not branch here if possible! + } else if (FallThrough->isLandingPad()) { + // Don't rewrite to a landing pad fallthough. That could lead to the case + // where a BB jumps to more than one landing pad. + // TODO: Is it ever worth rewriting predecessors which don't already + // jump to a landing pad, and so can safely jump to the fallthrough? } else { // Rewrite all predecessors of the old block to go to the fallthrough // instead. @@ -1504,10 +1637,17 @@ MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB, if (MO.isUse()) { for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) Uses.insert(*AI); - } else if (!MO.isDead()) - // Don't try to hoist code in the rare case the terminator defines a - // register that is later used. - return MBB->end(); + } else { + if (!MO.isDead()) + // Don't try to hoist code in the rare case the terminator defines a + // register that is later used. + return MBB->end(); + + // If the terminator defines a register, make sure we don't hoist + // the instruction whose def might be clobbered by the terminator. + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) + Defs.insert(*AI); + } } if (Uses.empty()) @@ -1548,8 +1688,7 @@ MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB, // Also avoid moving code above predicated instruction since it's hard to // reason about register liveness with predicated instruction. bool DontMoveAcrossStore = true; - if (!PI->isSafeToMove(TII, nullptr, DontMoveAcrossStore) || - TII->isPredicated(PI)) + if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(PI)) return MBB->end(); @@ -1687,7 +1826,7 @@ bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) { break; bool DontMoveAcrossStore = true; - if (!TIB->isSafeToMove(TII, nullptr, DontMoveAcrossStore)) + if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore)) break; // Remove kills from LocalDefsSet, these registers had short live ranges.