//===- MachineSink.cpp - Sinking for machine instructions -----------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This pass moves instructions into successor blocks when possible, so that // they aren't executed on paths where their results aren't needed. // // This pass is not intended to be a replacement or a complete alternative // for an LLVM-IR-level sinking pass. It is only designed to sink simple // constructs that are not exposed before lowering and instruction selection. // //===----------------------------------------------------------------------===// #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CFG.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineCycleAnalysis.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachinePostDominators.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/RegisterClassInfo.h" #include "llvm/CodeGen/RegisterPressure.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetPassConfig.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/LLVMContext.h" #include "llvm/InitializePasses.h" #include "llvm/MC/MCRegisterInfo.h" #include "llvm/Pass.h" #include "llvm/Support/BranchProbability.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> #include <cassert> #include <cstdint> #include <utility> #include <vector> usingnamespacellvm; #define DEBUG_TYPE … static cl::opt<bool> SplitEdges("machine-sink-split", cl::desc("Split critical edges during machine sinking"), cl::init(true), cl::Hidden); static cl::opt<bool> UseBlockFreqInfo("machine-sink-bfi", cl::desc("Use block frequency info to find successors to sink"), cl::init(true), cl::Hidden); static cl::opt<unsigned> SplitEdgeProbabilityThreshold( "machine-sink-split-probability-threshold", cl::desc( "Percentage threshold for splitting single-instruction critical edge. " "If the branch threshold is higher than this threshold, we allow " "speculative execution of up to 1 instruction to avoid branching to " "splitted critical edge"), cl::init(40), cl::Hidden); static cl::opt<unsigned> SinkLoadInstsPerBlockThreshold( "machine-sink-load-instrs-threshold", cl::desc("Do not try to find alias store for a load if there is a in-path " "block whose instruction number is higher than this threshold."), cl::init(2000), cl::Hidden); static cl::opt<unsigned> SinkLoadBlocksThreshold( "machine-sink-load-blocks-threshold", cl::desc("Do not try to find alias store for a load if the block number in " "the straight line is higher than this threshold."), cl::init(20), cl::Hidden); static cl::opt<bool> SinkInstsIntoCycle("sink-insts-to-avoid-spills", cl::desc("Sink instructions into cycles to avoid " "register spills"), cl::init(false), cl::Hidden); static cl::opt<unsigned> SinkIntoCycleLimit( "machine-sink-cycle-limit", cl::desc("The maximum number of instructions considered for cycle sinking."), cl::init(50), cl::Hidden); STATISTIC(NumSunk, "Number of machine instructions sunk"); STATISTIC(NumCycleSunk, "Number of machine instructions sunk into a cycle"); STATISTIC(NumSplit, "Number of critical edges split"); STATISTIC(NumCoalesces, "Number of copies coalesced"); STATISTIC(NumPostRACopySink, "Number of copies sunk after RA"); namespace { class MachineSinking : public MachineFunctionPass { … }; } // end anonymous namespace char MachineSinking::ID = …; char &llvm::MachineSinkingID = …; INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE, "Machine code sinking", false, false) INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(MachineCycleInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE, "Machine code sinking", false, false) /// Return true if a target defined block prologue instruction interferes /// with a sink candidate. static bool blockPrologueInterferes(const MachineBasicBlock *BB, MachineBasicBlock::const_iterator End, const MachineInstr &MI, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, const MachineRegisterInfo *MRI) { … } bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI, MachineBasicBlock *MBB) { … } bool MachineSinking::PerformSinkAndFold(MachineInstr &MI, MachineBasicBlock *MBB) { … } /// AllUsesDominatedByBlock - Return true if all uses of the specified register /// occur in blocks dominated by the specified block. If any use is in the /// definition block, then return false since it is never legal to move def /// after uses. bool MachineSinking::AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, bool &BreakPHIEdge, bool &LocalUse) const { … } /// Return true if this machine instruction loads from global offset table or /// constant pool. static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) { … } void MachineSinking::FindCycleSinkCandidates( MachineCycle *Cycle, MachineBasicBlock *BB, SmallVectorImpl<MachineInstr *> &Candidates) { … } bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { … } bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { … } void MachineSinking::ProcessDbgInst(MachineInstr &MI) { … } bool MachineSinking::isWorthBreakingCriticalEdge( MachineInstr &MI, MachineBasicBlock *From, MachineBasicBlock *To, MachineBasicBlock *&DeferredFromBlock) { … } bool MachineSinking::isLegalToBreakCriticalEdge(MachineInstr &MI, MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, bool BreakPHIEdge) { … } bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI, MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, bool BreakPHIEdge) { … } std::vector<unsigned> & MachineSinking::getBBRegisterPressure(const MachineBasicBlock &MBB) { … } bool MachineSinking::registerPressureSetExceedsLimit( unsigned NRegs, const TargetRegisterClass *RC, const MachineBasicBlock &MBB) { … } /// isProfitableToSinkTo - Return true if it is profitable to sink MI. bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI, MachineBasicBlock *MBB, MachineBasicBlock *SuccToSinkTo, AllSuccsCache &AllSuccessors) { … } /// 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, AllSuccsCache &AllSuccessors) const { … } /// FindSuccToSinkTo - Find a successor to sink this instruction to. MachineBasicBlock * MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB, bool &BreakPHIEdge, AllSuccsCache &AllSuccessors) { … } /// 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) { … } /// If the sunk instruction is a copy, try to forward the copy instead of /// leaving an 'undef' DBG_VALUE in the original location. Don't do this if /// there's any subregister weirdness involved. Returns true if copy /// propagation occurred. static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI, Register Reg) { … } MIRegs; /// Sink an instruction and its associated debug instructions. static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo, MachineBasicBlock::iterator InsertPos, ArrayRef<MIRegs> DbgValuesToSink) { … } /// hasStoreBetween - check if there is store betweeen straight line blocks From /// and To. bool MachineSinking::hasStoreBetween(MachineBasicBlock *From, MachineBasicBlock *To, MachineInstr &MI) { … } /// Sink instructions into cycles if profitable. This especially tries to /// prevent register spills caused by register pressure if there is little to no /// overhead moving instructions into cycles. bool MachineSinking::SinkIntoCycle(MachineCycle *Cycle, MachineInstr &I) { … } /// 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, AllSuccsCache &AllSuccessors) { … } void MachineSinking::SalvageUnsunkDebugUsersOfCopy( MachineInstr &MI, MachineBasicBlock *TargetBlock) { … } //===----------------------------------------------------------------------===// // This pass is not intended to be a replacement or a complete alternative // for the pre-ra machine sink pass. It is only designed to sink COPY // instructions which should be handled after RA. // // This pass sinks COPY instructions into a successor block, if the COPY is not // used in the current block and the COPY is live-in to a single successor // (i.e., doesn't require the COPY to be duplicated). This avoids executing the // copy on paths where their results aren't needed. This also exposes // additional opportunites for dead copy elimination and shrink wrapping. // // These copies were either not handled by or are inserted after the MachineSink // pass. As an example of the former case, the MachineSink pass cannot sink // COPY instructions with allocatable source registers; for AArch64 these type // of copy instructions are frequently used to move function parameters (PhyReg) // into virtual registers in the entry block. // // For the machine IR below, this pass will sink %w19 in the entry into its // successor (%bb.1) because %w19 is only live-in in %bb.1. // %bb.0: // %wzr = SUBSWri %w1, 1 // %w19 = COPY %w0 // Bcc 11, %bb.2 // %bb.1: // Live Ins: %w19 // BL @fun // %w0 = ADDWrr %w0, %w19 // RET %w0 // %bb.2: // %w0 = COPY %wzr // RET %w0 // As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be // able to see %bb.0 as a candidate. //===----------------------------------------------------------------------===// namespace { class PostRAMachineSinking : public MachineFunctionPass { … }; } // namespace char PostRAMachineSinking::ID = …; char &llvm::PostRAMachineSinkingID = …; INITIALIZE_PASS(…) static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg, const TargetRegisterInfo *TRI) { … } static MachineBasicBlock * getSingleLiveInSuccBB(MachineBasicBlock &CurBB, const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs, unsigned Reg, const TargetRegisterInfo *TRI) { … } static MachineBasicBlock * getSingleLiveInSuccBB(MachineBasicBlock &CurBB, const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs, ArrayRef<unsigned> DefedRegsInCopy, const TargetRegisterInfo *TRI) { … } static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB, SmallVectorImpl<unsigned> &UsedOpsInCopy, LiveRegUnits &UsedRegUnits, const TargetRegisterInfo *TRI) { … } static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB, SmallVectorImpl<unsigned> &UsedOpsInCopy, SmallVectorImpl<unsigned> &DefedRegsInCopy) { … } static bool hasRegisterDependency(MachineInstr *MI, SmallVectorImpl<unsigned> &UsedOpsInCopy, SmallVectorImpl<unsigned> &DefedRegsInCopy, LiveRegUnits &ModifiedRegUnits, LiveRegUnits &UsedRegUnits) { … } bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB, MachineFunction &MF, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII) { … } bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) { … }
Codebase Browser
llvm