diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/MachineSink.cpp')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/MachineSink.cpp | 160 |
1 files changed, 102 insertions, 58 deletions
diff --git a/contrib/llvm/lib/CodeGen/MachineSink.cpp b/contrib/llvm/lib/CodeGen/MachineSink.cpp index 5e6d619..571a5c1 100644 --- a/contrib/llvm/lib/CodeGen/MachineSink.cpp +++ b/contrib/llvm/lib/CodeGen/MachineSink.cpp @@ -27,6 +27,7 @@ #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachinePostDominators.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/IR/LLVMContext.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -104,7 +105,7 @@ namespace { private: bool ProcessBlock(MachineBasicBlock &MBB); - bool isWorthBreakingCriticalEdge(MachineInstr *MI, + bool isWorthBreakingCriticalEdge(MachineInstr &MI, MachineBasicBlock *From, MachineBasicBlock *To); /// \brief Postpone the splitting of the given critical @@ -119,27 +120,27 @@ namespace { /// /// \return True if the edge is marked as toSplit, false otherwise. /// False can be returned if, for instance, this is not profitable. - bool PostponeSplitCriticalEdge(MachineInstr *MI, + 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, + MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB, bool &BreakPHIEdge, AllSuccsCache &AllSuccessors); - bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, + bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI, MachineBasicBlock *MBB, MachineBasicBlock *SuccToSinkTo, AllSuccsCache &AllSuccessors); - bool PerformTrivialForwardCoalescing(MachineInstr *MI, + bool PerformTrivialForwardCoalescing(MachineInstr &MI, MachineBasicBlock *MBB); SmallVector<MachineBasicBlock *, 4> & - GetAllSortedSuccessors(MachineInstr *MI, MachineBasicBlock *MBB, + GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB, AllSuccsCache &AllSuccessors) const; }; } // end anonymous namespace @@ -154,13 +155,13 @@ INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(MachineSinking, "machine-sink", "Machine code sinking", false, false) -bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, +bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI, MachineBasicBlock *MBB) { - if (!MI->isCopy()) + if (!MI.isCopy()) return false; - unsigned SrcReg = MI->getOperand(1).getReg(); - unsigned DstReg = MI->getOperand(0).getReg(); + unsigned SrcReg = MI.getOperand(1).getReg(); + unsigned DstReg = MI.getOperand(0).getReg(); if (!TargetRegisterInfo::isVirtualRegister(SrcReg) || !TargetRegisterInfo::isVirtualRegister(DstReg) || !MRI->hasOneNonDBGUse(SrcReg)) @@ -175,9 +176,9 @@ bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, if (DefMI->isCopyLike()) return false; DEBUG(dbgs() << "Coalescing: " << *DefMI); - DEBUG(dbgs() << "*** to: " << *MI); + DEBUG(dbgs() << "*** to: " << MI); MRI->replaceRegWith(DstReg, SrcReg); - MI->eraseFromParent(); + MI.eraseFromParent(); // Conservatively, clear any kill flags, since it's possible that they are no // longer correct. @@ -256,7 +257,7 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, } bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { - if (skipOptnoneFunction(*MF.getFunction())) + if (skipFunction(*MF.getFunction())) return false; DEBUG(dbgs() << "******** Machine Sinking ********\n"); @@ -283,7 +284,7 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { // If we have anything we marked as toSplit, split it now. for (auto &Pair : ToSplit) { - auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, this); + auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this); if (NewSucc != nullptr) { DEBUG(dbgs() << " *** Splitting critical edge:" " BB#" << Pair.first->getNumber() @@ -326,7 +327,7 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { --I; bool ProcessedBegin, SawStore = false; do { - MachineInstr *MI = I; // The instruction to sink. + MachineInstr &MI = *I; // The instruction to sink. // Predecrement I (if it's not begin) so that it isn't invalidated by // sinking. @@ -334,7 +335,7 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { if (!ProcessedBegin) --I; - if (MI->isDebugValue()) + if (MI.isDebugValue()) continue; bool Joined = PerformTrivialForwardCoalescing(MI, &MBB); @@ -343,8 +344,10 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { continue; } - if (SinkInstruction(MI, SawStore, AllSuccessors)) - ++NumSunk, MadeChange = true; + if (SinkInstruction(MI, SawStore, AllSuccessors)) { + ++NumSunk; + MadeChange = true; + } // If we just processed the first instruction in the block, we're done. } while (!ProcessedBegin); @@ -352,7 +355,7 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { return MadeChange; } -bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, +bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI, MachineBasicBlock *From, MachineBasicBlock *To) { // FIXME: Need much better heuristics. @@ -363,14 +366,14 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, if (!CEBCandidates.insert(std::make_pair(From, To)).second) return true; - if (!MI->isCopy() && !TII->isAsCheapAsAMove(MI)) + if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI)) return true; // MI is cheap, we probably don't want to break the critical edge for it. // However, if this would allow some definitions of its source operands // to be sunk then it's probably worth it. - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI.getOperand(i); if (!MO.isReg() || !MO.isUse()) continue; unsigned Reg = MO.getReg(); @@ -391,7 +394,7 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, // If definition resides elsewhere, we aren't // blocking it from being sunk so don't break the edge. MachineInstr *DefMI = MRI->getVRegDef(Reg); - if (DefMI->getParent() == MI->getParent()) + if (DefMI->getParent() == MI.getParent()) return true; } } @@ -399,7 +402,7 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, return false; } -bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr *MI, +bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI, MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, bool BreakPHIEdge) { @@ -469,35 +472,30 @@ bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr *MI, return true; } -static bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) { - return MI->isInsertSubreg() || MI->isSubregToReg() || MI->isRegSequence(); -} - /// collectDebgValues - Scan instructions following MI and collect any /// matching DBG_VALUEs. -static void collectDebugValues(MachineInstr *MI, +static void collectDebugValues(MachineInstr &MI, SmallVectorImpl<MachineInstr *> &DbgValues) { DbgValues.clear(); - if (!MI->getOperand(0).isReg()) + if (!MI.getOperand(0).isReg()) return; MachineBasicBlock::iterator DI = MI; ++DI; - for (MachineBasicBlock::iterator DE = MI->getParent()->end(); + for (MachineBasicBlock::iterator DE = MI.getParent()->end(); DI != DE; ++DI) { if (!DI->isDebugValue()) return; if (DI->getOperand(0).isReg() && - DI->getOperand(0).getReg() == MI->getOperand(0).getReg()) - DbgValues.push_back(DI); + DI->getOperand(0).getReg() == MI.getOperand(0).getReg()) + DbgValues.push_back(&*DI); } } /// isProfitableToSinkTo - Return true if it is profitable to sink MI. -bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, +bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI, MachineBasicBlock *MBB, MachineBasicBlock *SuccToSinkTo, AllSuccsCache &AllSuccessors) { - assert (MI && "Invalid MachineInstr!"); assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); if (MBB == SuccToSinkTo) @@ -538,7 +536,7 @@ bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, /// Get the sorted sequence of successors for this MachineBasicBlock, possibly /// computing it if it was not already cached. SmallVector<MachineBasicBlock *, 4> & -MachineSinking::GetAllSortedSuccessors(MachineInstr *MI, MachineBasicBlock *MBB, +MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB, AllSuccsCache &AllSuccessors) const { // Do we have the sorted successors in cache ? @@ -560,7 +558,7 @@ MachineSinking::GetAllSortedSuccessors(MachineInstr *MI, MachineBasicBlock *MBB, 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() && + if (DTChild->getIDom()->getBlock() == MI.getParent() && // Skip MBBs already added to the AllSuccs vector above. !MBB->isSuccessor(DTChild->getBlock())) AllSuccs.push_back(DTChild->getBlock()); @@ -582,12 +580,10 @@ MachineSinking::GetAllSortedSuccessors(MachineInstr *MI, MachineBasicBlock *MBB, } /// FindSuccToSinkTo - Find a successor to sink this instruction to. -MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, - MachineBasicBlock *MBB, - bool &BreakPHIEdge, - AllSuccsCache &AllSuccessors) { - - assert (MI && "Invalid MachineInstr!"); +MachineBasicBlock * +MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB, + bool &BreakPHIEdge, + AllSuccsCache &AllSuccessors) { assert (MBB && "Invalid MachineBasicBlock!"); // Loop over all the operands of the specified instruction. If there is @@ -596,8 +592,8 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, // SuccToSinkTo - This is the successor to sink this instruction to, once we // decide. MachineBasicBlock *SuccToSinkTo = nullptr; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI.getOperand(i); if (!MO.isReg()) continue; // Ignore non-register operands. unsigned Reg = MO.getReg(); @@ -673,22 +669,70 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, return SuccToSinkTo; } +/// \brief Return true if MI is likely to be usable as a memory operation by the +/// implicit null check optimization. +/// +/// This is a "best effort" heuristic, and should not be relied upon for +/// correctness. This returning true does not guarantee that the implicit null +/// check optimization is legal over MI, and this returning false does not +/// guarantee MI cannot possibly be used to do a null check. +static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI, + const TargetInstrInfo *TII, + const TargetRegisterInfo *TRI) { + typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate; + + auto *MBB = MI.getParent(); + if (MBB->pred_size() != 1) + return false; + + auto *PredMBB = *MBB->pred_begin(); + auto *PredBB = PredMBB->getBasicBlock(); + + // Frontends that don't use implicit null checks have no reason to emit + // branches with make.implicit metadata, and this function should always + // return false for them. + if (!PredBB || + !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit)) + return false; + + unsigned BaseReg; + int64_t Offset; + if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI)) + return false; + + if (!(MI.mayLoad() && !MI.isPredicable())) + return false; + + MachineBranchPredicate MBP; + if (TII->analyzeBranchPredicate(*PredMBB, MBP, false)) + return false; + + return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 && + (MBP.Predicate == MachineBranchPredicate::PRED_NE || + MBP.Predicate == MachineBranchPredicate::PRED_EQ) && + MBP.LHS.getReg() == BaseReg; +} + /// 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)) + // Don't sink instructions that the target prefers not to sink. + if (!TII->shouldSink(MI)) return false; // Check if it's safe to move the instruction. - if (!MI->isSafeToMove(AA, SawStore)) + if (!MI.isSafeToMove(AA, SawStore)) return false; // Convergent operations may not be made control-dependent on additional // values. - if (MI->isConvergent()) + if (MI.isConvergent()) + return false; + + // Don't break implicit null checks. This is a performance heuristic, and not + // required for correctness. + if (SinkingPreventsImplicitNullCheck(MI, TII, TRI)) return false; // FIXME: This should include support for sinking instructions within the @@ -700,7 +744,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore, // and z and only shrink the live range of x. bool BreakPHIEdge = false; - MachineBasicBlock *ParentBlock = MI->getParent(); + MachineBasicBlock *ParentBlock = MI.getParent(); MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors); @@ -712,8 +756,8 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore, // If the instruction to move defines a dead physical register which is live // when leaving the basic block, don't move it because it could turn into a // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>) - for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { - const MachineOperand &MO = MI->getOperand(I); + for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) { + const MachineOperand &MO = MI.getOperand(I); if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; @@ -721,7 +765,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore, return false; } - DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); + DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo); // If the block has multiple predecessors, this is a critical edge. // Decide if we can sink along it or need to break the edge. @@ -730,7 +774,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore, // other code paths. bool TryBreak = false; bool store = true; - if (!MI->isSafeToMove(AA, store)) { + if (!MI.isSafeToMove(AA, store)) { DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); TryBreak = true; } @@ -804,7 +848,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore, // 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()) { + for (MachineOperand &MO : MI.operands()) { if (MO.isReg() && MO.isUse()) RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags. } |
