X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineSink.cpp;h=1b9be50068a94c32d00dbee4cefcec125652d890;hb=4f7a4bc79f67ae7255be56f78317368b9333ef0e;hp=77820010cef0276ee98772024031e69c08091739;hpb=cd72c216cd1444252b45b9c7af305e7c7157a5fa;p=oota-llvm.git diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 77820010cef..1b9be50068a 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -19,8 +19,10 @@ #include "llvm/CodeGen/Passes.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SparseBitVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachinePostDominators.h" @@ -29,7 +31,6 @@ #include "llvm/Support/Debug.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" using namespace llvm; @@ -41,6 +42,12 @@ SplitEdges("machine-sink-split", cl::desc("Split critical edges during machine sinking"), cl::init(true), cl::Hidden); +static cl::opt +UseBlockFreqInfo("machine-sink-bfi", + cl::desc("Use block frequency info to find successors to sink"), + cl::init(true), cl::Hidden); + + STATISTIC(NumSunk, "Number of machine instructions sunk"); STATISTIC(NumSplit, "Number of critical edges split"); STATISTIC(NumCoalesces, "Number of copies coalesced"); @@ -53,6 +60,7 @@ namespace { MachineDominatorTree *DT; // Machine dominator tree MachinePostDominatorTree *PDT; // Machine post dominator tree MachineLoopInfo *LI; + const MachineBlockFrequencyInfo *MBFI; AliasAnalysis *AA; // Remember which edges have been considered for breaking. @@ -63,6 +71,11 @@ namespace { // will be split. SetVector > ToSplit; + SparseBitVector<> RegsToClearKillFlags; + + typedef std::map> + AllSuccsCache; + public: static char ID; // Pass identification MachineSinking() : MachineFunctionPass(ID) { @@ -81,6 +94,8 @@ namespace { AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); + if (UseBlockFreqInfo) + AU.addRequired(); } void releaseMemory() override { @@ -103,23 +118,29 @@ namespace { /// for the lifetime of an iteration. /// /// \return True if the edge is marked as toSplit, false otherwise. - /// False can be retruned if, for instance, this is not profitable. + /// False can be returned if, for instance, this is not profitable. bool PostponeSplitCriticalEdge(MachineInstr *MI, MachineBasicBlock *From, MachineBasicBlock *To, bool BreakPHIEdge); - bool SinkInstruction(MachineInstr *MI, bool &SawStore); + bool SinkInstruction(MachineInstr *MI, bool &SawStore, + AllSuccsCache &AllSuccessors); bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, bool &BreakPHIEdge, bool &LocalUse) const; MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB, - bool &BreakPHIEdge); + bool &BreakPHIEdge, AllSuccsCache &AllSuccessors); bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, MachineBasicBlock *MBB, - MachineBasicBlock *SuccToSinkTo); + MachineBasicBlock *SuccToSinkTo, + AllSuccsCache &AllSuccessors); bool PerformTrivialForwardCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); + + SmallVector & + GetAllSortedSuccessors(MachineInstr *MI, MachineBasicBlock *MBB, + AllSuccsCache &AllSuccessors) const; }; } // end anonymous namespace @@ -157,6 +178,11 @@ bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, DEBUG(dbgs() << "*** to: " << *MI); MRI->replaceRegWith(DstReg, SrcReg); MI->eraseFromParent(); + + // Conservatively, clear any kill flags, since it's possible that they are no + // longer correct. + MRI->clearKillFlags(SrcReg); + ++NumCoalesces; return true; } @@ -235,13 +261,13 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { DEBUG(dbgs() << "******** Machine Sinking ********\n"); - const TargetMachine &TM = MF.getTarget(); - TII = TM.getSubtargetImpl()->getInstrInfo(); - TRI = TM.getSubtargetImpl()->getRegisterInfo(); + TII = MF.getSubtarget().getInstrInfo(); + TRI = MF.getSubtarget().getRegisterInfo(); MRI = &MF.getRegInfo(); DT = &getAnalysis(); PDT = &getAnalysis(); LI = &getAnalysis(); + MBFI = UseBlockFreqInfo ? &getAnalysis() : nullptr; AA = &getAnalysis(); bool EverMadeChange = false; @@ -252,9 +278,8 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { // Process all basic blocks. CEBCandidates.clear(); ToSplit.clear(); - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); - I != E; ++I) - MadeChange |= ProcessBlock(*I); + for (auto &MBB: MF) + MadeChange |= ProcessBlock(MBB); // If we have anything we marked as toSplit, split it now. for (auto &Pair : ToSplit) { @@ -273,6 +298,12 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { if (!MadeChange) break; EverMadeChange = true; } + + // Now clear any kill flags for recorded registers. + for (auto I : RegsToClearKillFlags) + MRI->clearKillFlags(I); + RegsToClearKillFlags.clear(); + return EverMadeChange; } @@ -287,6 +318,9 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { bool MadeChange = false; + // Cache all successors, sorted by frequency info and loop depth. + AllSuccsCache AllSuccessors; + // Walk the basic block bottom-up. Remember if we saw a store. MachineBasicBlock::iterator I = MBB.end(); --I; @@ -309,7 +343,7 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { continue; } - if (SinkInstruction(MI, SawStore)) + if (SinkInstruction(MI, SawStore, AllSuccessors)) ++NumSunk, MadeChange = true; // If we just processed the first instruction in the block, we're done. @@ -326,7 +360,7 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, // If the pass has already considered breaking this edge (during this pass // through the function), then let's go ahead and break it. This means // sinking multiple "cheap" instructions into the same block. - if (!CEBCandidates.insert(std::make_pair(From, To))) + if (!CEBCandidates.insert(std::make_pair(From, To)).second) return true; if (!MI->isCopy() && !TII->isAsCheapAsAMove(MI)) @@ -461,7 +495,8 @@ static void collectDebugValues(MachineInstr *MI, /// isProfitableToSinkTo - Return true if it is profitable to sink MI. bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, MachineBasicBlock *MBB, - MachineBasicBlock *SuccToSinkTo) { + MachineBasicBlock *SuccToSinkTo, + AllSuccsCache &AllSuccessors) { assert (MI && "Invalid MachineInstr!"); assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); @@ -472,6 +507,11 @@ bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, if (!PDT->dominates(SuccToSinkTo, MBB)) return true; + // It is profitable to sink an instruction from a deeper loop to a shallower + // loop, even if the latter post-dominates the former (PR21115). + if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo)) + return true; + // Check if only use in post dominated block is PHI instruction. bool NonPHIUse = false; for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) { @@ -485,19 +525,67 @@ bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, // If SuccToSinkTo post dominates then also it may be profitable if MI // can further profitably sinked into another block in next round. bool BreakPHIEdge = false; - // FIXME - If finding successor is compile time expensive then catch results. - if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge)) - return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2); + // FIXME - If finding successor is compile time expensive then cache results. + if (MachineBasicBlock *MBB2 = + FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors)) + return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors); // If SuccToSinkTo is final destination and it is a post dominator of current // block then it is not profitable to sink MI into SuccToSinkTo block. return false; } +/// Get the sorted sequence of successors for this MachineBasicBlock, possibly +/// computing it if it was not already cached. +SmallVector & +MachineSinking::GetAllSortedSuccessors(MachineInstr *MI, MachineBasicBlock *MBB, + AllSuccsCache &AllSuccessors) const { + + // Do we have the sorted successors in cache ? + auto Succs = AllSuccessors.find(MBB); + if (Succs != AllSuccessors.end()) + return Succs->second; + + SmallVector AllSuccs(MBB->succ_begin(), + MBB->succ_end()); + + // Handle cases where sinking can happen but where the sink point isn't a + // successor. For example: + // + // x = computation + // if () {} else {} + // use x + // + const std::vector &Children = + DT->getNode(MBB)->getChildren(); + for (const auto &DTChild : Children) + // DomTree children of MBB that have MBB as immediate dominator are added. + if (DTChild->getIDom()->getBlock() == MI->getParent() && + // Skip MBBs already added to the AllSuccs vector above. + !MBB->isSuccessor(DTChild->getBlock())) + AllSuccs.push_back(DTChild->getBlock()); + + // Sort Successors according to their loop depth or block frequency info. + std::stable_sort( + AllSuccs.begin(), AllSuccs.end(), + [this](const MachineBasicBlock *L, const MachineBasicBlock *R) { + uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0; + uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0; + bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0; + return HasBlockFreq ? LHSFreq < RHSFreq + : LI->getLoopDepth(L) < LI->getLoopDepth(R); + }); + + auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs)); + + return it.first->second; +} + /// FindSuccToSinkTo - Find a successor to sink this instruction to. MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB, - bool &BreakPHIEdge) { + bool &BreakPHIEdge, + AllSuccsCache &AllSuccessors) { assert (MI && "Invalid MachineInstr!"); assert (MBB && "Invalid MachineBasicBlock!"); @@ -534,19 +622,6 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) return nullptr; - // FIXME: This picks a successor to sink into based on having one - // successor that dominates all the uses. However, there are cases where - // sinking can happen but where the sink point isn't a successor. For - // example: - // - // x = computation - // if () {} else {} - // use x - // - // the instruction could be sunk over the whole diamond for the - // if/then/else (or loop, etc), allowing it to be sunk into other blocks - // after that. - // Virtual register defs can only be sunk if all their uses are in blocks // dominated by one of the successors. if (SuccToSinkTo) { @@ -561,18 +636,11 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, } // Otherwise, we should look at all the successors and decide which one - // we should sink to. - // We give successors with smaller loop depth higher priority. - SmallVector Succs(MBB->succ_begin(), MBB->succ_end()); - // Sort Successors according to their loop depth. - std::stable_sort( - Succs.begin(), Succs.end(), - [this](const MachineBasicBlock *LHS, const MachineBasicBlock *RHS) { - return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS); - }); - for (SmallVectorImpl::iterator SI = Succs.begin(), - E = Succs.end(); SI != E; ++SI) { - MachineBasicBlock *SuccBlock = *SI; + // we should sink to. If we have reliable block frequency information + // (frequency != 0) available, give successors with smaller frequencies + // higher priority, otherwise prioritize smaller loop depths. + for (MachineBasicBlock *SuccBlock : + GetAllSortedSuccessors(MI, MBB, AllSuccessors)) { bool LocalUse = false; if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, BreakPHIEdge, LocalUse)) { @@ -587,7 +655,7 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, // If we couldn't find a block to sink to, ignore this instruction. if (!SuccToSinkTo) return nullptr; - if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) + if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors)) return nullptr; } } @@ -607,14 +675,19 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, /// SinkInstruction - Determine whether it is safe to sink the specified machine /// instruction out of its current block into a successor. -bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { +bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore, + AllSuccsCache &AllSuccessors) { // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to // be close to the source to make it easier to coalesce. if (AvoidsSinking(MI, MRI)) return false; // Check if it's safe to move the instruction. - if (!MI->isSafeToMove(TII, AA, SawStore)) + if (!MI->isSafeToMove(AA, SawStore)) + return false; + + // Convergent operations may only be moved to control equivalent locations. + if (MI->isConvergent()) return false; // FIXME: This should include support for sinking instructions within the @@ -627,7 +700,8 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { bool BreakPHIEdge = false; MachineBasicBlock *ParentBlock = MI->getParent(); - MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge); + MachineBasicBlock *SuccToSinkTo = + FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors); // If there are no outputs, it must have side-effects. if (!SuccToSinkTo) @@ -655,7 +729,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // other code paths. bool TryBreak = false; bool store = true; - if (!MI->isSafeToMove(TII, AA, store)) { + if (!MI->isSafeToMove(AA, store)) { DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); TryBreak = true; } @@ -726,7 +800,13 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // Conservatively, clear any kill flags, since it's possible that they are no // longer correct. - MI->clearKillInfo(); + // Note that we have to clear the kill flags for any register this instruction + // uses as we may sink over another instruction which currently kills the + // used registers. + for (MachineOperand &MO : MI->operands()) { + if (MO.isReg() && MO.isUse()) + RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags. + } return true; }