| //===- MachinePipeliner.cpp - Machine Software Pipeliner Pass -------------===// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // An implementation of the Swing Modulo Scheduling (SMS) software pipeliner. |
| // |
| // This SMS implementation is a target-independent back-end pass. When enabled, |
| // the pass runs just prior to the register allocation pass, while the machine |
| // IR is in SSA form. If software pipelining is successful, then the original |
| // loop is replaced by the optimized loop. The optimized loop contains one or |
| // more prolog blocks, the pipelined kernel, and one or more epilog blocks. If |
| // the instructions cannot be scheduled in a given MII, we increase the MII by |
| // one and try again. |
| // |
| // The SMS implementation is an extension of the ScheduleDAGInstrs class. We |
| // represent loop carried dependences in the DAG as order edges to the Phi |
| // nodes. We also perform several passes over the DAG to eliminate unnecessary |
| // edges that inhibit the ability to pipeline. The implementation uses the |
| // DFAPacketizer class to compute the minimum initiation interval and the check |
| // where an instruction may be inserted in the pipelined schedule. |
| // |
| // In order for the SMS pass to work, several target specific hooks need to be |
| // implemented to get information about the loop structure and to rewrite |
| // instructions. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/CodeGen/MachinePipeliner.h" |
| #include "llvm/ADT/ArrayRef.h" |
| #include "llvm/ADT/BitVector.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/MapVector.h" |
| #include "llvm/ADT/PriorityQueue.h" |
| #include "llvm/ADT/SetOperations.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/ADT/iterator_range.h" |
| #include "llvm/Analysis/AliasAnalysis.h" |
| #include "llvm/Analysis/CycleAnalysis.h" |
| #include "llvm/Analysis/MemoryLocation.h" |
| #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
| #include "llvm/Analysis/ValueTracking.h" |
| #include "llvm/CodeGen/DFAPacketizer.h" |
| #include "llvm/CodeGen/LiveIntervals.h" |
| #include "llvm/CodeGen/MachineBasicBlock.h" |
| #include "llvm/CodeGen/MachineDominators.h" |
| #include "llvm/CodeGen/MachineFunction.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/CodeGen/MachineInstr.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/CodeGen/MachineLoopInfo.h" |
| #include "llvm/CodeGen/MachineMemOperand.h" |
| #include "llvm/CodeGen/MachineOperand.h" |
| #include "llvm/CodeGen/MachineRegisterInfo.h" |
| #include "llvm/CodeGen/ModuloSchedule.h" |
| #include "llvm/CodeGen/RegisterPressure.h" |
| #include "llvm/CodeGen/ScheduleDAG.h" |
| #include "llvm/CodeGen/ScheduleDAGMutation.h" |
| #include "llvm/CodeGen/TargetOpcodes.h" |
| #include "llvm/CodeGen/TargetRegisterInfo.h" |
| #include "llvm/CodeGen/TargetSubtargetInfo.h" |
| #include "llvm/Config/llvm-config.h" |
| #include "llvm/IR/Attributes.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/MC/LaneBitmask.h" |
| #include "llvm/MC/MCInstrDesc.h" |
| #include "llvm/MC/MCInstrItineraries.h" |
| #include "llvm/MC/MCRegisterInfo.h" |
| #include "llvm/Pass.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Compiler.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/MathExtras.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <algorithm> |
| #include <cassert> |
| #include <climits> |
| #include <cstdint> |
| #include <deque> |
| #include <functional> |
| #include <iomanip> |
| #include <iterator> |
| #include <map> |
| #include <memory> |
| #include <sstream> |
| #include <tuple> |
| #include <utility> |
| #include <vector> |
| |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "pipeliner" |
| |
| STATISTIC(NumTrytoPipeline, "Number of loops that we attempt to pipeline"); |
| STATISTIC(NumPipelined, "Number of loops software pipelined"); |
| STATISTIC(NumNodeOrderIssues, "Number of node order issues found"); |
| STATISTIC(NumFailBranch, "Pipeliner abort due to unknown branch"); |
| STATISTIC(NumFailLoop, "Pipeliner abort due to unsupported loop"); |
| STATISTIC(NumFailPreheader, "Pipeliner abort due to missing preheader"); |
| STATISTIC(NumFailLargeMaxMII, "Pipeliner abort due to MaxMII too large"); |
| STATISTIC(NumFailZeroMII, "Pipeliner abort due to zero MII"); |
| STATISTIC(NumFailNoSchedule, "Pipeliner abort due to no schedule found"); |
| STATISTIC(NumFailZeroStage, "Pipeliner abort due to zero stage"); |
| STATISTIC(NumFailLargeMaxStage, "Pipeliner abort due to too many stages"); |
| |
| /// A command line option to turn software pipelining on or off. |
| static cl::opt<bool> EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true), |
| cl::desc("Enable Software Pipelining")); |
| |
| /// A command line option to enable SWP at -Os. |
| static cl::opt<bool> EnableSWPOptSize("enable-pipeliner-opt-size", |
| cl::desc("Enable SWP at Os."), cl::Hidden, |
| cl::init(false)); |
| |
| /// A command line argument to limit minimum initial interval for pipelining. |
| static cl::opt<int> SwpMaxMii("pipeliner-max-mii", |
| cl::desc("Size limit for the MII."), |
| cl::Hidden, cl::init(27)); |
| |
| /// A command line argument to force pipeliner to use specified initial |
| /// interval. |
| static cl::opt<int> SwpForceII("pipeliner-force-ii", |
| cl::desc("Force pipeliner to use specified II."), |
| cl::Hidden, cl::init(-1)); |
| |
| /// A command line argument to limit the number of stages in the pipeline. |
| static cl::opt<int> |
| SwpMaxStages("pipeliner-max-stages", |
| cl::desc("Maximum stages allowed in the generated scheduled."), |
| cl::Hidden, cl::init(3)); |
| |
| /// A command line option to disable the pruning of chain dependences due to |
| /// an unrelated Phi. |
| static cl::opt<bool> |
| SwpPruneDeps("pipeliner-prune-deps", |
| cl::desc("Prune dependences between unrelated Phi nodes."), |
| cl::Hidden, cl::init(true)); |
| |
| /// A command line option to disable the pruning of loop carried order |
| /// dependences. |
| static cl::opt<bool> |
| SwpPruneLoopCarried("pipeliner-prune-loop-carried", |
| cl::desc("Prune loop carried order dependences."), |
| cl::Hidden, cl::init(true)); |
| |
| #ifndef NDEBUG |
| static cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1)); |
| #endif |
| |
| static cl::opt<bool> SwpIgnoreRecMII("pipeliner-ignore-recmii", |
| cl::ReallyHidden, |
| cl::desc("Ignore RecMII")); |
| |
| static cl::opt<bool> SwpShowResMask("pipeliner-show-mask", cl::Hidden, |
| cl::init(false)); |
| static cl::opt<bool> SwpDebugResource("pipeliner-dbg-res", cl::Hidden, |
| cl::init(false)); |
| |
| static cl::opt<bool> EmitTestAnnotations( |
| "pipeliner-annotate-for-testing", cl::Hidden, cl::init(false), |
| cl::desc("Instead of emitting the pipelined code, annotate instructions " |
| "with the generated schedule for feeding into the " |
| "-modulo-schedule-test pass")); |
| |
| static cl::opt<bool> ExperimentalCodeGen( |
| "pipeliner-experimental-cg", cl::Hidden, cl::init(false), |
| cl::desc( |
| "Use the experimental peeling code generator for software pipelining")); |
| |
| namespace llvm { |
| |
| // A command line option to enable the CopyToPhi DAG mutation. |
| cl::opt<bool> SwpEnableCopyToPhi("pipeliner-enable-copytophi", cl::ReallyHidden, |
| cl::init(true), |
| cl::desc("Enable CopyToPhi DAG Mutation")); |
| |
| /// A command line argument to force pipeliner to use specified issue |
| /// width. |
| cl::opt<int> SwpForceIssueWidth( |
| "pipeliner-force-issue-width", |
| cl::desc("Force pipeliner to use specified issue width."), cl::Hidden, |
| cl::init(-1)); |
| |
| } // end namespace llvm |
| |
| unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5; |
| char MachinePipeliner::ID = 0; |
| #ifndef NDEBUG |
| int MachinePipeliner::NumTries = 0; |
| #endif |
| char &llvm::MachinePipelinerID = MachinePipeliner::ID; |
| |
| INITIALIZE_PASS_BEGIN(MachinePipeliner, DEBUG_TYPE, |
| "Modulo Software Pipelining", false, false) |
| INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) |
| INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) |
| INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
| INITIALIZE_PASS_DEPENDENCY(LiveIntervals) |
| INITIALIZE_PASS_END(MachinePipeliner, DEBUG_TYPE, |
| "Modulo Software Pipelining", false, false) |
| |
| /// The "main" function for implementing Swing Modulo Scheduling. |
| bool MachinePipeliner::runOnMachineFunction(MachineFunction &mf) { |
| if (skipFunction(mf.getFunction())) |
| return false; |
| |
| if (!EnableSWP) |
| return false; |
| |
| if (mf.getFunction().getAttributes().hasFnAttr(Attribute::OptimizeForSize) && |
| !EnableSWPOptSize.getPosition()) |
| return false; |
| |
| if (!mf.getSubtarget().enableMachinePipeliner()) |
| return false; |
| |
| // Cannot pipeline loops without instruction itineraries if we are using |
| // DFA for the pipeliner. |
| if (mf.getSubtarget().useDFAforSMS() && |
| (!mf.getSubtarget().getInstrItineraryData() || |
| mf.getSubtarget().getInstrItineraryData()->isEmpty())) |
| return false; |
| |
| MF = &mf; |
| MLI = &getAnalysis<MachineLoopInfo>(); |
| MDT = &getAnalysis<MachineDominatorTree>(); |
| ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE(); |
| TII = MF->getSubtarget().getInstrInfo(); |
| RegClassInfo.runOnMachineFunction(*MF); |
| |
| for (const auto &L : *MLI) |
| scheduleLoop(*L); |
| |
| return false; |
| } |
| |
| /// Attempt to perform the SMS algorithm on the specified loop. This function is |
| /// the main entry point for the algorithm. The function identifies candidate |
| /// loops, calculates the minimum initiation interval, and attempts to schedule |
| /// the loop. |
| bool MachinePipeliner::scheduleLoop(MachineLoop &L) { |
| bool Changed = false; |
| for (const auto &InnerLoop : L) |
| Changed |= scheduleLoop(*InnerLoop); |
| |
| #ifndef NDEBUG |
| // Stop trying after reaching the limit (if any). |
| int Limit = SwpLoopLimit; |
| if (Limit >= 0) { |
| if (NumTries >= SwpLoopLimit) |
| return Changed; |
| NumTries++; |
| } |
| #endif |
| |
| setPragmaPipelineOptions(L); |
| if (!canPipelineLoop(L)) { |
| LLVM_DEBUG(dbgs() << "\n!!! Can not pipeline loop.\n"); |
| ORE->emit([&]() { |
| return MachineOptimizationRemarkMissed(DEBUG_TYPE, "canPipelineLoop", |
| L.getStartLoc(), L.getHeader()) |
| << "Failed to pipeline loop"; |
| }); |
| |
| LI.LoopPipelinerInfo.reset(); |
| return Changed; |
| } |
| |
| ++NumTrytoPipeline; |
| |
| Changed = swingModuloScheduler(L); |
| |
| LI.LoopPipelinerInfo.reset(); |
| return Changed; |
| } |
| |
| void MachinePipeliner::setPragmaPipelineOptions(MachineLoop &L) { |
| // Reset the pragma for the next loop in iteration. |
| disabledByPragma = false; |
| II_setByPragma = 0; |
| |
| MachineBasicBlock *LBLK = L.getTopBlock(); |
| |
| if (LBLK == nullptr) |
| return; |
| |
| const BasicBlock *BBLK = LBLK->getBasicBlock(); |
| if (BBLK == nullptr) |
| return; |
| |
| const Instruction *TI = BBLK->getTerminator(); |
| if (TI == nullptr) |
| return; |
| |
| MDNode *LoopID = TI->getMetadata(LLVMContext::MD_loop); |
| if (LoopID == nullptr) |
| return; |
| |
| assert(LoopID->getNumOperands() > 0 && "requires atleast one operand"); |
| assert(LoopID->getOperand(0) == LoopID && "invalid loop"); |
| |
| for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) { |
| MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i)); |
| |
| if (MD == nullptr) |
| continue; |
| |
| MDString *S = dyn_cast<MDString>(MD->getOperand(0)); |
| |
| if (S == nullptr) |
| continue; |
| |
| if (S->getString() == "llvm.loop.pipeline.initiationinterval") { |
| assert(MD->getNumOperands() == 2 && |
| "Pipeline initiation interval hint metadata should have two operands."); |
| II_setByPragma = |
| mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue(); |
| assert(II_setByPragma >= 1 && "Pipeline initiation interval must be positive."); |
| } else if (S->getString() == "llvm.loop.pipeline.disable") { |
| disabledByPragma = true; |
| } |
| } |
| } |
| |
| /// Return true if the loop can be software pipelined. The algorithm is |
| /// restricted to loops with a single basic block. Make sure that the |
| /// branch in the loop can be analyzed. |
| bool MachinePipeliner::canPipelineLoop(MachineLoop &L) { |
| if (L.getNumBlocks() != 1) { |
| ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop", |
| L.getStartLoc(), L.getHeader()) |
| << "Not a single basic block: " |
| << ore::NV("NumBlocks", L.getNumBlocks()); |
| }); |
| return false; |
| } |
| |
| if (disabledByPragma) { |
| ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop", |
| L.getStartLoc(), L.getHeader()) |
| << "Disabled by Pragma."; |
| }); |
| return false; |
| } |
| |
| // Check if the branch can't be understood because we can't do pipelining |
| // if that's the case. |
| LI.TBB = nullptr; |
| LI.FBB = nullptr; |
| LI.BrCond.clear(); |
| if (TII->analyzeBranch(*L.getHeader(), LI.TBB, LI.FBB, LI.BrCond)) { |
| LLVM_DEBUG(dbgs() << "Unable to analyzeBranch, can NOT pipeline Loop\n"); |
| NumFailBranch++; |
| ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop", |
| L.getStartLoc(), L.getHeader()) |
| << "The branch can't be understood"; |
| }); |
| return false; |
| } |
| |
| LI.LoopInductionVar = nullptr; |
| LI.LoopCompare = nullptr; |
| LI.LoopPipelinerInfo = TII->analyzeLoopForPipelining(L.getTopBlock()); |
| if (!LI.LoopPipelinerInfo) { |
| LLVM_DEBUG(dbgs() << "Unable to analyzeLoop, can NOT pipeline Loop\n"); |
| NumFailLoop++; |
| ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop", |
| L.getStartLoc(), L.getHeader()) |
| << "The loop structure is not supported"; |
| }); |
| return false; |
| } |
| |
| if (!L.getLoopPreheader()) { |
| LLVM_DEBUG(dbgs() << "Preheader not found, can NOT pipeline Loop\n"); |
| NumFailPreheader++; |
| ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop", |
| L.getStartLoc(), L.getHeader()) |
| << "No loop preheader found"; |
| }); |
| return false; |
| } |
| |
| // Remove any subregisters from inputs to phi nodes. |
| preprocessPhiNodes(*L.getHeader()); |
| return true; |
| } |
| |
| void MachinePipeliner::preprocessPhiNodes(MachineBasicBlock &B) { |
| MachineRegisterInfo &MRI = MF->getRegInfo(); |
| SlotIndexes &Slots = *getAnalysis<LiveIntervals>().getSlotIndexes(); |
| |
| for (MachineInstr &PI : B.phis()) { |
| MachineOperand &DefOp = PI.getOperand(0); |
| assert(DefOp.getSubReg() == 0); |
| auto *RC = MRI.getRegClass(DefOp.getReg()); |
| |
| for (unsigned i = 1, n = PI.getNumOperands(); i != n; i += 2) { |
| MachineOperand &RegOp = PI.getOperand(i); |
| if (RegOp.getSubReg() == 0) |
| continue; |
| |
| // If the operand uses a subregister, replace it with a new register |
| // without subregisters, and generate a copy to the new register. |
| Register NewReg = MRI.createVirtualRegister(RC); |
| MachineBasicBlock &PredB = *PI.getOperand(i+1).getMBB(); |
| MachineBasicBlock::iterator At = PredB.getFirstTerminator(); |
| const DebugLoc &DL = PredB.findDebugLoc(At); |
| auto Copy = BuildMI(PredB, At, DL, TII->get(TargetOpcode::COPY), NewReg) |
| .addReg(RegOp.getReg(), getRegState(RegOp), |
| RegOp.getSubReg()); |
| Slots.insertMachineInstrInMaps(*Copy); |
| RegOp.setReg(NewReg); |
| RegOp.setSubReg(0); |
| } |
| } |
| } |
| |
| /// The SMS algorithm consists of the following main steps: |
| /// 1. Computation and analysis of the dependence graph. |
| /// 2. Ordering of the nodes (instructions). |
| /// 3. Attempt to Schedule the loop. |
| bool MachinePipeliner::swingModuloScheduler(MachineLoop &L) { |
| assert(L.getBlocks().size() == 1 && "SMS works on single blocks only."); |
| |
| SwingSchedulerDAG SMS(*this, L, getAnalysis<LiveIntervals>(), RegClassInfo, |
| II_setByPragma, LI.LoopPipelinerInfo.get()); |
| |
| MachineBasicBlock *MBB = L.getHeader(); |
| // The kernel should not include any terminator instructions. These |
| // will be added back later. |
| SMS.startBlock(MBB); |
| |
| // Compute the number of 'real' instructions in the basic block by |
| // ignoring terminators. |
| unsigned size = MBB->size(); |
| for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(), |
| E = MBB->instr_end(); |
| I != E; ++I, --size) |
| ; |
| |
| SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size); |
| SMS.schedule(); |
| SMS.exitRegion(); |
| |
| SMS.finishBlock(); |
| return SMS.hasNewSchedule(); |
| } |
| |
| void MachinePipeliner::getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.addRequired<AAResultsWrapperPass>(); |
| AU.addPreserved<AAResultsWrapperPass>(); |
| AU.addRequired<MachineLoopInfo>(); |
| AU.addRequired<MachineDominatorTree>(); |
| AU.addRequired<LiveIntervals>(); |
| AU.addRequired<MachineOptimizationRemarkEmitterPass>(); |
| MachineFunctionPass::getAnalysisUsage(AU); |
| } |
| |
| void SwingSchedulerDAG::setMII(unsigned ResMII, unsigned RecMII) { |
| if (SwpForceII > 0) |
| MII = SwpForceII; |
| else if (II_setByPragma > 0) |
| MII = II_setByPragma; |
| else |
| MII = std::max(ResMII, RecMII); |
| } |
| |
| void SwingSchedulerDAG::setMAX_II() { |
| if (SwpForceII > 0) |
| MAX_II = SwpForceII; |
| else if (II_setByPragma > 0) |
| MAX_II = II_setByPragma; |
| else |
| MAX_II = MII + 10; |
| } |
| |
| /// We override the schedule function in ScheduleDAGInstrs to implement the |
| /// scheduling part of the Swing Modulo Scheduling algorithm. |
| void SwingSchedulerDAG::schedule() { |
| AliasAnalysis *AA = &Pass.getAnalysis<AAResultsWrapperPass>().getAAResults(); |
| buildSchedGraph(AA); |
| addLoopCarriedDependences(AA); |
| updatePhiDependences(); |
| Topo.InitDAGTopologicalSorting(); |
| changeDependences(); |
| postProcessDAG(); |
| LLVM_DEBUG(dump()); |
| |
| NodeSetType NodeSets; |
| findCircuits(NodeSets); |
| NodeSetType Circuits = NodeSets; |
| |
| // Calculate the MII. |
| unsigned ResMII = calculateResMII(); |
| unsigned RecMII = calculateRecMII(NodeSets); |
| |
| fuseRecs(NodeSets); |
| |
| // This flag is used for testing and can cause correctness problems. |
| if (SwpIgnoreRecMII) |
| RecMII = 0; |
| |
| setMII(ResMII, RecMII); |
| setMAX_II(); |
| |
| LLVM_DEBUG(dbgs() << "MII = " << MII << " MAX_II = " << MAX_II |
| << " (rec=" << RecMII << ", res=" << ResMII << ")\n"); |
| |
| // Can't schedule a loop without a valid MII. |
| if (MII == 0) { |
| LLVM_DEBUG(dbgs() << "Invalid Minimal Initiation Interval: 0\n"); |
| NumFailZeroMII++; |
| Pass.ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis( |
| DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader()) |
| << "Invalid Minimal Initiation Interval: 0"; |
| }); |
| return; |
| } |
| |
| // Don't pipeline large loops. |
| if (SwpMaxMii != -1 && (int)MII > SwpMaxMii) { |
| LLVM_DEBUG(dbgs() << "MII > " << SwpMaxMii |
| << ", we don't pipeline large loops\n"); |
| NumFailLargeMaxMII++; |
| Pass.ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis( |
| DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader()) |
| << "Minimal Initiation Interval too large: " |
| << ore::NV("MII", (int)MII) << " > " |
| << ore::NV("SwpMaxMii", SwpMaxMii) << "." |
| << "Refer to -pipeliner-max-mii."; |
| }); |
| return; |
| } |
| |
| computeNodeFunctions(NodeSets); |
| |
| registerPressureFilter(NodeSets); |
| |
| colocateNodeSets(NodeSets); |
| |
| checkNodeSets(NodeSets); |
| |
| LLVM_DEBUG({ |
| for (auto &I : NodeSets) { |
| dbgs() << " Rec NodeSet "; |
| I.dump(); |
| } |
| }); |
| |
| llvm::stable_sort(NodeSets, std::greater<NodeSet>()); |
| |
| groupRemainingNodes(NodeSets); |
| |
| removeDuplicateNodes(NodeSets); |
| |
| LLVM_DEBUG({ |
| for (auto &I : NodeSets) { |
| dbgs() << " NodeSet "; |
| I.dump(); |
| } |
| }); |
| |
| computeNodeOrder(NodeSets); |
| |
| // check for node order issues |
| checkValidNodeOrder(Circuits); |
| |
| SMSchedule Schedule(Pass.MF, this); |
| Scheduled = schedulePipeline(Schedule); |
| |
| if (!Scheduled){ |
| LLVM_DEBUG(dbgs() << "No schedule found, return\n"); |
| NumFailNoSchedule++; |
| Pass.ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis( |
| DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader()) |
| << "Unable to find schedule"; |
| }); |
| return; |
| } |
| |
| unsigned numStages = Schedule.getMaxStageCount(); |
| // No need to generate pipeline if there are no overlapped iterations. |
| if (numStages == 0) { |
| LLVM_DEBUG(dbgs() << "No overlapped iterations, skip.\n"); |
| NumFailZeroStage++; |
| Pass.ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis( |
| DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader()) |
| << "No need to pipeline - no overlapped iterations in schedule."; |
| }); |
| return; |
| } |
| // Check that the maximum stage count is less than user-defined limit. |
| if (SwpMaxStages > -1 && (int)numStages > SwpMaxStages) { |
| LLVM_DEBUG(dbgs() << "numStages:" << numStages << ">" << SwpMaxStages |
| << " : too many stages, abort\n"); |
| NumFailLargeMaxStage++; |
| Pass.ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis( |
| DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader()) |
| << "Too many stages in schedule: " |
| << ore::NV("numStages", (int)numStages) << " > " |
| << ore::NV("SwpMaxStages", SwpMaxStages) |
| << ". Refer to -pipeliner-max-stages."; |
| }); |
| return; |
| } |
| |
| Pass.ORE->emit([&]() { |
| return MachineOptimizationRemark(DEBUG_TYPE, "schedule", Loop.getStartLoc(), |
| Loop.getHeader()) |
| << "Pipelined succesfully!"; |
| }); |
| |
| // Generate the schedule as a ModuloSchedule. |
| DenseMap<MachineInstr *, int> Cycles, Stages; |
| std::vector<MachineInstr *> OrderedInsts; |
| for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle(); |
| ++Cycle) { |
| for (SUnit *SU : Schedule.getInstructions(Cycle)) { |
| OrderedInsts.push_back(SU->getInstr()); |
| Cycles[SU->getInstr()] = Cycle; |
| Stages[SU->getInstr()] = Schedule.stageScheduled(SU); |
| } |
| } |
| DenseMap<MachineInstr *, std::pair<unsigned, int64_t>> NewInstrChanges; |
| for (auto &KV : NewMIs) { |
| Cycles[KV.first] = Cycles[KV.second]; |
| Stages[KV.first] = Stages[KV.second]; |
| NewInstrChanges[KV.first] = InstrChanges[getSUnit(KV.first)]; |
| } |
| |
| ModuloSchedule MS(MF, &Loop, std::move(OrderedInsts), std::move(Cycles), |
| std::move(Stages)); |
| if (EmitTestAnnotations) { |
| assert(NewInstrChanges.empty() && |
| "Cannot serialize a schedule with InstrChanges!"); |
| ModuloScheduleTestAnnotater MSTI(MF, MS); |
| MSTI.annotate(); |
| return; |
| } |
| // The experimental code generator can't work if there are InstChanges. |
| if (ExperimentalCodeGen && NewInstrChanges.empty()) { |
| PeelingModuloScheduleExpander MSE(MF, MS, &LIS); |
| MSE.expand(); |
| } else { |
| ModuloScheduleExpander MSE(MF, MS, LIS, std::move(NewInstrChanges)); |
| MSE.expand(); |
| MSE.cleanup(); |
| } |
| ++NumPipelined; |
| } |
| |
| /// Clean up after the software pipeliner runs. |
| void SwingSchedulerDAG::finishBlock() { |
| for (auto &KV : NewMIs) |
| MF.deleteMachineInstr(KV.second); |
| NewMIs.clear(); |
| |
| // Call the superclass. |
| ScheduleDAGInstrs::finishBlock(); |
| } |
| |
| /// Return the register values for the operands of a Phi instruction. |
| /// This function assume the instruction is a Phi. |
| static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop, |
| unsigned &InitVal, unsigned &LoopVal) { |
| assert(Phi.isPHI() && "Expecting a Phi."); |
| |
| InitVal = 0; |
| LoopVal = 0; |
| for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2) |
| if (Phi.getOperand(i + 1).getMBB() != Loop) |
| InitVal = Phi.getOperand(i).getReg(); |
| else |
| LoopVal = Phi.getOperand(i).getReg(); |
| |
| assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure."); |
| } |
| |
| /// Return the Phi register value that comes the loop block. |
| static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) { |
| for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2) |
| if (Phi.getOperand(i + 1).getMBB() == LoopBB) |
| return Phi.getOperand(i).getReg(); |
| return 0; |
| } |
| |
| /// Return true if SUb can be reached from SUa following the chain edges. |
| static bool isSuccOrder(SUnit *SUa, SUnit *SUb) { |
| SmallPtrSet<SUnit *, 8> Visited; |
| SmallVector<SUnit *, 8> Worklist; |
| Worklist.push_back(SUa); |
| while (!Worklist.empty()) { |
| const SUnit *SU = Worklist.pop_back_val(); |
| for (const auto &SI : SU->Succs) { |
| SUnit *SuccSU = SI.getSUnit(); |
| if (SI.getKind() == SDep::Order) { |
| if (Visited.count(SuccSU)) |
| continue; |
| if (SuccSU == SUb) |
| return true; |
| Worklist.push_back(SuccSU); |
| Visited.insert(SuccSU); |
| } |
| } |
| } |
| return false; |
| } |
| |
| /// Return true if the instruction causes a chain between memory |
| /// references before and after it. |
| static bool isDependenceBarrier(MachineInstr &MI) { |
| return MI.isCall() || MI.mayRaiseFPException() || |
| MI.hasUnmodeledSideEffects() || |
| (MI.hasOrderedMemoryRef() && |
| (!MI.mayLoad() || !MI.isDereferenceableInvariantLoad())); |
| } |
| |
| /// Return the underlying objects for the memory references of an instruction. |
| /// This function calls the code in ValueTracking, but first checks that the |
| /// instruction has a memory operand. |
| static void getUnderlyingObjects(const MachineInstr *MI, |
| SmallVectorImpl<const Value *> &Objs) { |
| if (!MI->hasOneMemOperand()) |
| return; |
| MachineMemOperand *MM = *MI->memoperands_begin(); |
| if (!MM->getValue()) |
| return; |
| getUnderlyingObjects(MM->getValue(), Objs); |
| for (const Value *V : Objs) { |
| if (!isIdentifiedObject(V)) { |
| Objs.clear(); |
| return; |
| } |
| Objs.push_back(V); |
| } |
| } |
| |
| /// Add a chain edge between a load and store if the store can be an |
| /// alias of the load on a subsequent iteration, i.e., a loop carried |
| /// dependence. This code is very similar to the code in ScheduleDAGInstrs |
| /// but that code doesn't create loop carried dependences. |
| void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) { |
| MapVector<const Value *, SmallVector<SUnit *, 4>> PendingLoads; |
| Value *UnknownValue = |
| UndefValue::get(Type::getVoidTy(MF.getFunction().getContext())); |
| for (auto &SU : SUnits) { |
| MachineInstr &MI = *SU.getInstr(); |
| if (isDependenceBarrier(MI)) |
| PendingLoads.clear(); |
| else if (MI.mayLoad()) { |
| SmallVector<const Value *, 4> Objs; |
| ::getUnderlyingObjects(&MI, Objs); |
| if (Objs.empty()) |
| Objs.push_back(UnknownValue); |
| for (const auto *V : Objs) { |
| SmallVector<SUnit *, 4> &SUs = PendingLoads[V]; |
| SUs.push_back(&SU); |
| } |
| } else if (MI.mayStore()) { |
| SmallVector<const Value *, 4> Objs; |
| ::getUnderlyingObjects(&MI, Objs); |
| if (Objs.empty()) |
| Objs.push_back(UnknownValue); |
| for (const auto *V : Objs) { |
| MapVector<const Value *, SmallVector<SUnit *, 4>>::iterator I = |
| PendingLoads.find(V); |
| if (I == PendingLoads.end()) |
| continue; |
| for (auto *Load : I->second) { |
| if (isSuccOrder(Load, &SU)) |
| continue; |
| MachineInstr &LdMI = *Load->getInstr(); |
| // First, perform the cheaper check that compares the base register. |
| // If they are the same and the load offset is less than the store |
| // offset, then mark the dependence as loop carried potentially. |
| const MachineOperand *BaseOp1, *BaseOp2; |
| int64_t Offset1, Offset2; |
| bool Offset1IsScalable, Offset2IsScalable; |
| if (TII->getMemOperandWithOffset(LdMI, BaseOp1, Offset1, |
| Offset1IsScalable, TRI) && |
| TII->getMemOperandWithOffset(MI, BaseOp2, Offset2, |
| Offset2IsScalable, TRI)) { |
| if (BaseOp1->isIdenticalTo(*BaseOp2) && |
| Offset1IsScalable == Offset2IsScalable && |
| (int)Offset1 < (int)Offset2) { |
| assert(TII->areMemAccessesTriviallyDisjoint(LdMI, MI) && |
| "What happened to the chain edge?"); |
| SDep Dep(Load, SDep::Barrier); |
| Dep.setLatency(1); |
| SU.addPred(Dep); |
| continue; |
| } |
| } |
| // Second, the more expensive check that uses alias analysis on the |
| // base registers. If they alias, and the load offset is less than |
| // the store offset, the mark the dependence as loop carried. |
| if (!AA) { |
| SDep Dep(Load, SDep::Barrier); |
| Dep.setLatency(1); |
| SU.addPred(Dep); |
| continue; |
| } |
| MachineMemOperand *MMO1 = *LdMI.memoperands_begin(); |
| MachineMemOperand *MMO2 = *MI.memoperands_begin(); |
| if (!MMO1->getValue() || !MMO2->getValue()) { |
| SDep Dep(Load, SDep::Barrier); |
| Dep.setLatency(1); |
| SU.addPred(Dep); |
| continue; |
| } |
| if (MMO1->getValue() == MMO2->getValue() && |
| MMO1->getOffset() <= MMO2->getOffset()) { |
| SDep Dep(Load, SDep::Barrier); |
| Dep.setLatency(1); |
| SU.addPred(Dep); |
| continue; |
| } |
| if (!AA->isNoAlias( |
| MemoryLocation::getAfter(MMO1->getValue(), MMO1->getAAInfo()), |
| MemoryLocation::getAfter(MMO2->getValue(), |
| MMO2->getAAInfo()))) { |
| SDep Dep(Load, SDep::Barrier); |
| Dep.setLatency(1); |
| SU.addPred(Dep); |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| /// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer |
| /// processes dependences for PHIs. This function adds true dependences |
| /// from a PHI to a use, and a loop carried dependence from the use to the |
| /// PHI. The loop carried dependence is represented as an anti dependence |
| /// edge. This function also removes chain dependences between unrelated |
| /// PHIs. |
| void SwingSchedulerDAG::updatePhiDependences() { |
| SmallVector<SDep, 4> RemoveDeps; |
| const TargetSubtargetInfo &ST = MF.getSubtarget<TargetSubtargetInfo>(); |
| |
| // Iterate over each DAG node. |
| for (SUnit &I : SUnits) { |
| RemoveDeps.clear(); |
| // Set to true if the instruction has an operand defined by a Phi. |
| unsigned HasPhiUse = 0; |
| unsigned HasPhiDef = 0; |
| MachineInstr *MI = I.getInstr(); |
| // Iterate over each operand, and we process the definitions. |
| for (const MachineOperand &MO : MI->operands()) { |
| if (!MO.isReg()) |
| continue; |
| Register Reg = MO.getReg(); |
| if (MO.isDef()) { |
| // If the register is used by a Phi, then create an anti dependence. |
| for (MachineRegisterInfo::use_instr_iterator |
| UI = MRI.use_instr_begin(Reg), |
| UE = MRI.use_instr_end(); |
| UI != UE; ++UI) { |
| MachineInstr *UseMI = &*UI; |
| SUnit *SU = getSUnit(UseMI); |
| if (SU != nullptr && UseMI->isPHI()) { |
| if (!MI->isPHI()) { |
| SDep Dep(SU, SDep::Anti, Reg); |
| Dep.setLatency(1); |
| I.addPred(Dep); |
| } else { |
| HasPhiDef = Reg; |
| // Add a chain edge to a dependent Phi that isn't an existing |
| // predecessor. |
| if (SU->NodeNum < I.NodeNum && !I.isPred(SU)) |
| I.addPred(SDep(SU, SDep::Barrier)); |
| } |
| } |
| } |
| } else if (MO.isUse()) { |
| // If the register is defined by a Phi, then create a true dependence. |
| MachineInstr *DefMI = MRI.getUniqueVRegDef(Reg); |
| if (DefMI == nullptr) |
| continue; |
| SUnit *SU = getSUnit(DefMI); |
| if (SU != nullptr && DefMI->isPHI()) { |
| if (!MI->isPHI()) { |
| SDep Dep(SU, SDep::Data, Reg); |
| Dep.setLatency(0); |
| ST.adjustSchedDependency(SU, 0, &I, MO.getOperandNo(), Dep); |
| I.addPred(Dep); |
| } else { |
| HasPhiUse = Reg; |
| // Add a chain edge to a dependent Phi that isn't an existing |
| // predecessor. |
| if (SU->NodeNum < I.NodeNum && !I.isPred(SU)) |
| I.addPred(SDep(SU, SDep::Barrier)); |
| } |
| } |
| } |
| } |
| // Remove order dependences from an unrelated Phi. |
| if (!SwpPruneDeps) |
| continue; |
| for (auto &PI : I.Preds) { |
| MachineInstr *PMI = PI.getSUnit()->getInstr(); |
| if (PMI->isPHI() && PI.getKind() == SDep::Order) { |
| if (I.getInstr()->isPHI()) { |
| if (PMI->getOperand(0).getReg() == HasPhiUse) |
| continue; |
| if (getLoopPhiReg(*PMI, PMI->getParent()) == HasPhiDef) |
| continue; |
| } |
| RemoveDeps.push_back(PI); |
| } |
| } |
| for (int i = 0, e = RemoveDeps.size(); i != e; ++i) |
| I.removePred(RemoveDeps[i]); |
| } |
| } |
| |
| /// Iterate over each DAG node and see if we can change any dependences |
| /// in order to reduce the recurrence MII. |
| void SwingSchedulerDAG::changeDependences() { |
| // See if an instruction can use a value from the previous iteration. |
| // If so, we update the base and offset of the instruction and change |
| // the dependences. |
| for (SUnit &I : SUnits) { |
| unsigned BasePos = 0, OffsetPos = 0, NewBase = 0; |
| int64_t NewOffset = 0; |
| if (!canUseLastOffsetValue(I.getInstr(), BasePos, OffsetPos, NewBase, |
| NewOffset)) |
| continue; |
| |
| // Get the MI and SUnit for the instruction that defines the original base. |
| Register OrigBase = I.getInstr()->getOperand(BasePos).getReg(); |
| MachineInstr *DefMI = MRI.getUniqueVRegDef(OrigBase); |
| if (!DefMI) |
| continue; |
| SUnit *DefSU = getSUnit(DefMI); |
| if (!DefSU) |
| continue; |
| // Get the MI and SUnit for the instruction that defins the new base. |
| MachineInstr *LastMI = MRI.getUniqueVRegDef(NewBase); |
| if (!LastMI) |
| continue; |
| SUnit *LastSU = getSUnit(LastMI); |
| if (!LastSU) |
| continue; |
| |
| if (Topo.IsReachable(&I, LastSU)) |
| continue; |
| |
| // Remove the dependence. The value now depends on a prior iteration. |
| SmallVector<SDep, 4> Deps; |
| for (const SDep &P : I.Preds) |
| if (P.getSUnit() == DefSU) |
| Deps.push_back(P); |
| for (int i = 0, e = Deps.size(); i != e; i++) { |
| Topo.RemovePred(&I, Deps[i].getSUnit()); |
| I.removePred(Deps[i]); |
| } |
| // Remove the chain dependence between the instructions. |
| Deps.clear(); |
| for (auto &P : LastSU->Preds) |
| if (P.getSUnit() == &I && P.getKind() == SDep::Order) |
| Deps.push_back(P); |
| for (int i = 0, e = Deps.size(); i != e; i++) { |
| Topo.RemovePred(LastSU, Deps[i].getSUnit()); |
| LastSU->removePred(Deps[i]); |
| } |
| |
| // Add a dependence between the new instruction and the instruction |
| // that defines the new base. |
| SDep Dep(&I, SDep::Anti, NewBase); |
| Topo.AddPred(LastSU, &I); |
| LastSU->addPred(Dep); |
| |
| // Remember the base and offset information so that we can update the |
| // instruction during code generation. |
| InstrChanges[&I] = std::make_pair(NewBase, NewOffset); |
| } |
| } |
| |
| namespace { |
| |
| // FuncUnitSorter - Comparison operator used to sort instructions by |
| // the number of functional unit choices. |
| struct FuncUnitSorter { |
| const InstrItineraryData *InstrItins; |
| const MCSubtargetInfo *STI; |
| DenseMap<InstrStage::FuncUnits, unsigned> Resources; |
| |
| FuncUnitSorter(const TargetSubtargetInfo &TSI) |
| : InstrItins(TSI.getInstrItineraryData()), STI(&TSI) {} |
| |
| // Compute the number of functional unit alternatives needed |
| // at each stage, and take the minimum value. We prioritize the |
| // instructions by the least number of choices first. |
| unsigned minFuncUnits(const MachineInstr *Inst, |
| InstrStage::FuncUnits &F) const { |
| unsigned SchedClass = Inst->getDesc().getSchedClass(); |
| unsigned min = UINT_MAX; |
| if (InstrItins && !InstrItins->isEmpty()) { |
| for (const InstrStage &IS : |
| make_range(InstrItins->beginStage(SchedClass), |
| InstrItins->endStage(SchedClass))) { |
| InstrStage::FuncUnits funcUnits = IS.getUnits(); |
| unsigned numAlternatives = llvm::popcount(funcUnits); |
| if (numAlternatives < min) { |
| min = numAlternatives; |
| F = funcUnits; |
| } |
| } |
| return min; |
| } |
| if (STI && STI->getSchedModel().hasInstrSchedModel()) { |
| const MCSchedClassDesc *SCDesc = |
| STI->getSchedModel().getSchedClassDesc(SchedClass); |
| if (!SCDesc->isValid()) |
| // No valid Schedule Class Desc for schedClass, should be |
| // Pseudo/PostRAPseudo |
| return min; |
| |
| for (const MCWriteProcResEntry &PRE : |
| make_range(STI->getWriteProcResBegin(SCDesc), |
| STI->getWriteProcResEnd(SCDesc))) { |
| if (!PRE.Cycles) |
| continue; |
| const MCProcResourceDesc *ProcResource = |
| STI->getSchedModel().getProcResource(PRE.ProcResourceIdx); |
| unsigned NumUnits = ProcResource->NumUnits; |
| if (NumUnits < min) { |
| min = NumUnits; |
| F = PRE.ProcResourceIdx; |
| } |
| } |
| return min; |
| } |
| llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!"); |
| } |
| |
| // Compute the critical resources needed by the instruction. This |
| // function records the functional units needed by instructions that |
| // must use only one functional unit. We use this as a tie breaker |
| // for computing the resource MII. The instrutions that require |
| // the same, highly used, functional unit have high priority. |
| void calcCriticalResources(MachineInstr &MI) { |
| unsigned SchedClass = MI.getDesc().getSchedClass(); |
| if (InstrItins && !InstrItins->isEmpty()) { |
| for (const InstrStage &IS : |
| make_range(InstrItins->beginStage(SchedClass), |
| InstrItins->endStage(SchedClass))) { |
| InstrStage::FuncUnits FuncUnits = IS.getUnits(); |
| if (llvm::popcount(FuncUnits) == 1) |
| Resources[FuncUnits]++; |
| } |
| return; |
| } |
| if (STI && STI->getSchedModel().hasInstrSchedModel()) { |
| const MCSchedClassDesc *SCDesc = |
| STI->getSchedModel().getSchedClassDesc(SchedClass); |
| if (!SCDesc->isValid()) |
| // No valid Schedule Class Desc for schedClass, should be |
| // Pseudo/PostRAPseudo |
| return; |
| |
| for (const MCWriteProcResEntry &PRE : |
| make_range(STI->getWriteProcResBegin(SCDesc), |
| STI->getWriteProcResEnd(SCDesc))) { |
| if (!PRE.Cycles) |
| continue; |
| Resources[PRE.ProcResourceIdx]++; |
| } |
| return; |
| } |
| llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!"); |
| } |
| |
| /// Return true if IS1 has less priority than IS2. |
| bool operator()(const MachineInstr *IS1, const MachineInstr *IS2) const { |
| InstrStage::FuncUnits F1 = 0, F2 = 0; |
| unsigned MFUs1 = minFuncUnits(IS1, F1); |
| unsigned MFUs2 = minFuncUnits(IS2, F2); |
| if (MFUs1 == MFUs2) |
| return Resources.lookup(F1) < Resources.lookup(F2); |
| return MFUs1 > MFUs2; |
| } |
| }; |
| |
| } // end anonymous namespace |
| |
| /// Calculate the resource constrained minimum initiation interval for the |
| /// specified loop. We use the DFA to model the resources needed for |
| /// each instruction, and we ignore dependences. A different DFA is created |
| /// for each cycle that is required. When adding a new instruction, we attempt |
| /// to add it to each existing DFA, until a legal space is found. If the |
| /// instruction cannot be reserved in an existing DFA, we create a new one. |
| unsigned SwingSchedulerDAG::calculateResMII() { |
| LLVM_DEBUG(dbgs() << "calculateResMII:\n"); |
| ResourceManager RM(&MF.getSubtarget(), this); |
| return RM.calculateResMII(); |
| } |
| |
| /// Calculate the recurrence-constrainted minimum initiation interval. |
| /// Iterate over each circuit. Compute the delay(c) and distance(c) |
| /// for each circuit. The II needs to satisfy the inequality |
| /// delay(c) - II*distance(c) <= 0. For each circuit, choose the smallest |
| /// II that satisfies the inequality, and the RecMII is the maximum |
| /// of those values. |
| unsigned SwingSchedulerDAG::calculateRecMII(NodeSetType &NodeSets) { |
| unsigned RecMII = 0; |
| |
| for (NodeSet &Nodes : NodeSets) { |
| if (Nodes.empty()) |
| continue; |
| |
| unsigned Delay = Nodes.getLatency(); |
| unsigned Distance = 1; |
| |
| // ii = ceil(delay / distance) |
| unsigned CurMII = (Delay + Distance - 1) / Distance; |
| Nodes.setRecMII(CurMII); |
| if (CurMII > RecMII) |
| RecMII = CurMII; |
| } |
| |
| return RecMII; |
| } |
| |
| /// Swap all the anti dependences in the DAG. That means it is no longer a DAG, |
| /// but we do this to find the circuits, and then change them back. |
| static void swapAntiDependences(std::vector<SUnit> &SUnits) { |
| SmallVector<std::pair<SUnit *, SDep>, 8> DepsAdded; |
| for (SUnit &SU : SUnits) { |
| for (SDep &Pred : SU.Preds) |
| if (Pred.getKind() == SDep::Anti) |
| DepsAdded.push_back(std::make_pair(&SU, Pred)); |
| } |
| for (std::pair<SUnit *, SDep> &P : DepsAdded) { |
| // Remove this anti dependency and add one in the reverse direction. |
| SUnit *SU = P.first; |
| SDep &D = P.second; |
| SUnit *TargetSU = D.getSUnit(); |
| unsigned Reg = D.getReg(); |
| unsigned Lat = D.getLatency(); |
| SU->removePred(D); |
| SDep Dep(SU, SDep::Anti, Reg); |
| Dep.setLatency(Lat); |
| TargetSU->addPred(Dep); |
| } |
| } |
| |
| /// Create the adjacency structure of the nodes in the graph. |
| void SwingSchedulerDAG::Circuits::createAdjacencyStructure( |
| SwingSchedulerDAG *DAG) { |
| BitVector Added(SUnits.size()); |
| DenseMap<int, int> OutputDeps; |
| for (int i = 0, e = SUnits.size(); i != e; ++i) { |
| Added.reset(); |
| // Add any successor to the adjacency matrix and exclude duplicates. |
| for (auto &SI : SUnits[i].Succs) { |
| // Only create a back-edge on the first and last nodes of a dependence |
| // chain. This records any chains and adds them later. |
| if (SI.getKind() == SDep::Output) { |
| int N = SI.getSUnit()->NodeNum; |
| int BackEdge = i; |
| auto Dep = OutputDeps.find(BackEdge); |
| if (Dep != OutputDeps.end()) { |
| BackEdge = Dep->second; |
| OutputDeps.erase(Dep); |
| } |
| OutputDeps[N] = BackEdge; |
| } |
| // Do not process a boundary node, an artificial node. |
| // A back-edge is processed only if it goes to a Phi. |
| if (SI.getSUnit()->isBoundaryNode() || SI.isArtificial() || |
| (SI.getKind() == SDep::Anti && !SI.getSUnit()->getInstr()->isPHI())) |
| continue; |
| int N = SI.getSUnit()->NodeNum; |
| if (!Added.test(N)) { |
| AdjK[i].push_back(N); |
| Added.set(N); |
| } |
| } |
| // A chain edge between a store and a load is treated as a back-edge in the |
| // adjacency matrix. |
| for (auto &PI : SUnits[i].Preds) { |
| if (!SUnits[i].getInstr()->mayStore() || |
| !DAG->isLoopCarriedDep(&SUnits[i], PI, false)) |
| continue; |
| if (PI.getKind() == SDep::Order && PI.getSUnit()->getInstr()->mayLoad()) { |
| int N = PI.getSUnit()->NodeNum; |
| if (!Added.test(N)) { |
| AdjK[i].push_back(N); |
| Added.set(N); |
| } |
| } |
| } |
| } |
| // Add back-edges in the adjacency matrix for the output dependences. |
| for (auto &OD : OutputDeps) |
| if (!Added.test(OD.second)) { |
| AdjK[OD.first].push_back(OD.second); |
| Added.set(OD.second); |
| } |
| } |
| |
| /// Identify an elementary circuit in the dependence graph starting at the |
| /// specified node. |
| bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets, |
| bool HasBackedge) { |
| SUnit *SV = &SUnits[V]; |
| bool F = false; |
| Stack.insert(SV); |
| Blocked.set(V); |
| |
| for (auto W : AdjK[V]) { |
| if (NumPaths > MaxPaths) |
| break; |
| if (W < S) |
| continue; |
| if (W == S) { |
| if (!HasBackedge) |
| NodeSets.push_back(NodeSet(Stack.begin(), Stack.end())); |
| F = true; |
| ++NumPaths; |
| break; |
| } else if (!Blocked.test(W)) { |
| if (circuit(W, S, NodeSets, |
| Node2Idx->at(W) < Node2Idx->at(V) ? true : HasBackedge)) |
| F = true; |
| } |
| } |
| |
| if (F) |
| unblock(V); |
| else { |
| for (auto W : AdjK[V]) { |
| if (W < S) |
| continue; |
| B[W].insert(SV); |
| } |
| } |
| Stack.pop_back(); |
| return F; |
| } |
| |
| /// Unblock a node in the circuit finding algorithm. |
| void SwingSchedulerDAG::Circuits::unblock(int U) { |
| Blocked.reset(U); |
| SmallPtrSet<SUnit *, 4> &BU = B[U]; |
| while (!BU.empty()) { |
| SmallPtrSet<SUnit *, 4>::iterator SI = BU.begin(); |
| assert(SI != BU.end() && "Invalid B set."); |
| SUnit *W = *SI; |
| BU.erase(W); |
| if (Blocked.test(W->NodeNum)) |
| unblock(W->NodeNum); |
| } |
| } |
| |
| /// Identify all the elementary circuits in the dependence graph using |
| /// Johnson's circuit algorithm. |
| void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) { |
| // Swap all the anti dependences in the DAG. That means it is no longer a DAG, |
| // but we do this to find the circuits, and then change them back. |
| swapAntiDependences(SUnits); |
| |
| Circuits Cir(SUnits, Topo); |
| // Create the adjacency structure. |
| Cir.createAdjacencyStructure(this); |
| for (int i = 0, e = SUnits.size(); i != e; ++i) { |
| Cir.reset(); |
| Cir.circuit(i, i, NodeSets); |
| } |
| |
| // Change the dependences back so that we've created a DAG again. |
| swapAntiDependences(SUnits); |
| } |
| |
| // Create artificial dependencies between the source of COPY/REG_SEQUENCE that |
| // is loop-carried to the USE in next iteration. This will help pipeliner avoid |
| // additional copies that are needed across iterations. An artificial dependence |
| // edge is added from USE to SOURCE of COPY/REG_SEQUENCE. |
| |
| // PHI-------Anti-Dep-----> COPY/REG_SEQUENCE (loop-carried) |
| // SRCOfCopY------True-Dep---> COPY/REG_SEQUENCE |
| // PHI-------True-Dep------> USEOfPhi |
| |
| // The mutation creates |
| // USEOfPHI -------Artificial-Dep---> SRCOfCopy |
| |
| // This overall will ensure, the USEOfPHI is scheduled before SRCOfCopy |
| // (since USE is a predecessor), implies, the COPY/ REG_SEQUENCE is scheduled |
| // late to avoid additional copies across iterations. The possible scheduling |
| // order would be |
| // USEOfPHI --- SRCOfCopy--- COPY/REG_SEQUENCE. |
| |
| void SwingSchedulerDAG::CopyToPhiMutation::apply(ScheduleDAGInstrs *DAG) { |
| for (SUnit &SU : DAG->SUnits) { |
| // Find the COPY/REG_SEQUENCE instruction. |
| if (!SU.getInstr()->isCopy() && !SU.getInstr()->isRegSequence()) |
| continue; |
| |
| // Record the loop carried PHIs. |
| SmallVector<SUnit *, 4> PHISUs; |
| // Record the SrcSUs that feed the COPY/REG_SEQUENCE instructions. |
| SmallVector<SUnit *, 4> SrcSUs; |
| |
| for (auto &Dep : SU.Preds) { |
| SUnit *TmpSU = Dep.getSUnit(); |
| MachineInstr *TmpMI = TmpSU->getInstr(); |
| SDep::Kind DepKind = Dep.getKind(); |
| // Save the loop carried PHI. |
| if (DepKind == SDep::Anti && TmpMI->isPHI()) |
| PHISUs.push_back(TmpSU); |
| // Save the source of COPY/REG_SEQUENCE. |
| // If the source has no pre-decessors, we will end up creating cycles. |
| else if (DepKind == SDep::Data && !TmpMI->isPHI() && TmpSU->NumPreds > 0) |
| SrcSUs.push_back(TmpSU); |
| } |
| |
| if (PHISUs.size() == 0 || SrcSUs.size() == 0) |
| continue; |
| |
| // Find the USEs of PHI. If the use is a PHI or REG_SEQUENCE, push back this |
| // SUnit to the container. |
| SmallVector<SUnit *, 8> UseSUs; |
| // Do not use iterator based loop here as we are updating the container. |
| for (size_t Index = 0; Index < PHISUs.size(); ++Index) { |
| for (auto &Dep : PHISUs[Index]->Succs) { |
| if (Dep.getKind() != SDep::Data) |
| continue; |
| |
| SUnit *TmpSU = Dep.getSUnit(); |
| MachineInstr *TmpMI = TmpSU->getInstr(); |
| if (TmpMI->isPHI() || TmpMI->isRegSequence()) { |
| PHISUs.push_back(TmpSU); |
| continue; |
| } |
| UseSUs.push_back(TmpSU); |
| } |
| } |
| |
| if (UseSUs.size() == 0) |
| continue; |
| |
| SwingSchedulerDAG *SDAG = cast<SwingSchedulerDAG>(DAG); |
| // Add the artificial dependencies if it does not form a cycle. |
| for (auto *I : UseSUs) { |
| for (auto *Src : SrcSUs) { |
| if (!SDAG->Topo.IsReachable(I, Src) && Src != I) { |
| Src->addPred(SDep(I, SDep::Artificial)); |
| SDAG->Topo.AddPred(Src, I); |
| } |
| } |
| } |
| } |
| } |
| |
| /// Return true for DAG nodes that we ignore when computing the cost functions. |
| /// We ignore the back-edge recurrence in order to avoid unbounded recursion |
| /// in the calculation of the ASAP, ALAP, etc functions. |
| static bool ignoreDependence(const SDep &D, bool isPred) { |
| if (D.isArtificial() || D.getSUnit()->isBoundaryNode()) |
| return true; |
| return D.getKind() == SDep::Anti && isPred; |
| } |
| |
| /// Compute several functions need to order the nodes for scheduling. |
| /// ASAP - Earliest time to schedule a node. |
| /// ALAP - Latest time to schedule a node. |
| /// MOV - Mobility function, difference between ALAP and ASAP. |
| /// D - Depth of each node. |
| /// H - Height of each node. |
| void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) { |
| ScheduleInfo.resize(SUnits.size()); |
| |
| LLVM_DEBUG({ |
| for (int I : Topo) { |
| const SUnit &SU = SUnits[I]; |
| dumpNode(SU); |
| } |
| }); |
| |
| int maxASAP = 0; |
| // Compute ASAP and ZeroLatencyDepth. |
| for (int I : Topo) { |
| int asap = 0; |
| int zeroLatencyDepth = 0; |
| SUnit *SU = &SUnits[I]; |
| for (const SDep &P : SU->Preds) { |
| SUnit *pred = P.getSUnit(); |
| if (P.getLatency() == 0) |
| zeroLatencyDepth = |
| std::max(zeroLatencyDepth, getZeroLatencyDepth(pred) + 1); |
| if (ignoreDependence(P, true)) |
| continue; |
| asap = std::max(asap, (int)(getASAP(pred) + P.getLatency() - |
| getDistance(pred, SU, P) * MII)); |
| } |
| maxASAP = std::max(maxASAP, asap); |
| ScheduleInfo[I].ASAP = asap; |
| ScheduleInfo[I].ZeroLatencyDepth = zeroLatencyDepth; |
| } |
| |
| // Compute ALAP, ZeroLatencyHeight, and MOV. |
| for (int I : llvm::reverse(Topo)) { |
| int alap = maxASAP; |
| int zeroLatencyHeight = 0; |
| SUnit *SU = &SUnits[I]; |
| for (const SDep &S : SU->Succs) { |
| SUnit *succ = S.getSUnit(); |
| if (succ->isBoundaryNode()) |
| continue; |
| if (S.getLatency() == 0) |
| zeroLatencyHeight = |
| std::max(zeroLatencyHeight, getZeroLatencyHeight(succ) + 1); |
| if (ignoreDependence(S, true)) |
| continue; |
| alap = std::min(alap, (int)(getALAP(succ) - S.getLatency() + |
| getDistance(SU, succ, S) * MII)); |
| } |
| |
| ScheduleInfo[I].ALAP = alap; |
| ScheduleInfo[I].ZeroLatencyHeight = zeroLatencyHeight; |
| } |
| |
| // After computing the node functions, compute the summary for each node set. |
| for (NodeSet &I : NodeSets) |
| I.computeNodeSetInfo(this); |
| |
| LLVM_DEBUG({ |
| for (unsigned i = 0; i < SUnits.size(); i++) { |
| dbgs() << "\tNode " << i << ":\n"; |
| dbgs() << "\t ASAP = " << getASAP(&SUnits[i]) << "\n"; |
| dbgs() << "\t ALAP = " << getALAP(&SUnits[i]) << "\n"; |
| dbgs() << "\t MOV = " << getMOV(&SUnits[i]) << "\n"; |
| dbgs() << "\t D = " << getDepth(&SUnits[i]) << "\n"; |
| dbgs() << "\t H = " << getHeight(&SUnits[i]) << "\n"; |
| dbgs() << "\t ZLD = " << getZeroLatencyDepth(&SUnits[i]) << "\n"; |
| dbgs() << "\t ZLH = " << getZeroLatencyHeight(&SUnits[i]) << "\n"; |
| } |
| }); |
| } |
| |
| /// Compute the Pred_L(O) set, as defined in the paper. The set is defined |
| /// as the predecessors of the elements of NodeOrder that are not also in |
| /// NodeOrder. |
| static bool pred_L(SetVector<SUnit *> &NodeOrder, |
| SmallSetVector<SUnit *, 8> &Preds, |
| const NodeSet *S = nullptr) { |
| Preds.clear(); |
| for (const SUnit *SU : NodeOrder) { |
| for (const SDep &Pred : SU->Preds) { |
| if (S && S->count(Pred.getSUnit()) == 0) |
| continue; |
| if (ignoreDependence(Pred, true)) |
| continue; |
| if (NodeOrder.count(Pred.getSUnit()) == 0) |
| Preds.insert(Pred.getSUnit()); |
| } |
| // Back-edges are predecessors with an anti-dependence. |
| for (const SDep &Succ : SU->Succs) { |
| if (Succ.getKind() != SDep::Anti) |
| continue; |
| if (S && S->count(Succ.getSUnit()) == 0) |
| continue; |
| if (NodeOrder.count(Succ.getSUnit()) == 0) |
| Preds.insert(Succ.getSUnit()); |
| } |
| } |
| return !Preds.empty(); |
| } |
| |
| /// Compute the Succ_L(O) set, as defined in the paper. The set is defined |
| /// as the successors of the elements of NodeOrder that are not also in |
| /// NodeOrder. |
| static bool succ_L(SetVector<SUnit *> &NodeOrder, |
| SmallSetVector<SUnit *, 8> &Succs, |
| const NodeSet *S = nullptr) { |
| Succs.clear(); |
| for (const SUnit *SU : NodeOrder) { |
| for (const SDep &Succ : SU->Succs) { |
| if (S && S->count(Succ.getSUnit()) == 0) |
| continue; |
| if (ignoreDependence(Succ, false)) |
| continue; |
| if (NodeOrder.count(Succ.getSUnit()) == 0) |
| Succs.insert(Succ.getSUnit()); |
| } |
| for (const SDep &Pred : SU->Preds) { |
| if (Pred.getKind() != SDep::Anti) |
| continue; |
| if (S && S->count(Pred.getSUnit()) == 0) |
| continue; |
| if (NodeOrder.count(Pred.getSUnit()) == 0) |
| Succs.insert(Pred.getSUnit()); |
| } |
| } |
| return !Succs.empty(); |
| } |
| |
| /// Return true if there is a path from the specified node to any of the nodes |
| /// in DestNodes. Keep track and return the nodes in any path. |
| static bool computePath(SUnit *Cur, SetVector<SUnit *> &Path, |
| SetVector<SUnit *> &DestNodes, |
| SetVector<SUnit *> &Exclude, |
| SmallPtrSet<SUnit *, 8> &Visited) { |
| if (Cur->isBoundaryNode()) |
| return false; |
| if (Exclude.contains(Cur)) |
| return false; |
| if (DestNodes.contains(Cur)) |
| return true; |
| if (!Visited.insert(Cur).second) |
| return Path.contains(Cur); |
| bool FoundPath = false; |
| for (auto &SI : Cur->Succs) |
| if (!ignoreDependence(SI, false)) |
| FoundPath |= |
| computePath(SI.getSUnit(), Path, DestNodes, Exclude, Visited); |
| for (auto &PI : Cur->Preds) |
| if (PI.getKind() == SDep::Anti) |
| FoundPath |= |
| computePath(PI.getSUnit(), Path, DestNodes, Exclude, Visited); |
| if (FoundPath) |
| Path.insert(Cur); |
| return FoundPath; |
| } |
| |
| /// Compute the live-out registers for the instructions in a node-set. |
| /// The live-out registers are those that are defined in the node-set, |
| /// but not used. Except for use operands of Phis. |
| static void computeLiveOuts(MachineFunction &MF, RegPressureTracker &RPTracker, |
| NodeSet &NS) { |
| const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); |
| MachineRegisterInfo &MRI = MF.getRegInfo(); |
| SmallVector<RegisterMaskPair, 8> LiveOutRegs; |
| SmallSet<unsigned, 4> Uses; |
| for (SUnit *SU : NS) { |
| const MachineInstr *MI = SU->getInstr(); |
| if (MI->isPHI()) |
| continue; |
| for (const MachineOperand &MO : MI->all_uses()) { |
| Register Reg = MO.getReg(); |
| if (Reg.isVirtual()) |
| Uses.insert(Reg); |
| else if (MRI.isAllocatable(Reg)) |
| for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid(); |
| ++Units) |
| Uses.insert(*Units); |
| } |
| } |
| for (SUnit *SU : NS) |
| for (const MachineOperand &MO : SU->getInstr()->all_defs()) |
| if (!MO.isDead()) { |
| Register Reg = MO.getReg(); |
| if (Reg.isVirtual()) { |
| if (!Uses.count(Reg)) |
| LiveOutRegs.push_back(RegisterMaskPair(Reg, |
| LaneBitmask::getNone())); |
| } else if (MRI.isAllocatable(Reg)) { |
| for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid(); |
| ++Units) |
| if (!Uses.count(*Units)) |
| LiveOutRegs.push_back(RegisterMaskPair(*Units, |
| LaneBitmask::getNone())); |
| } |
| } |
| RPTracker.addLiveRegs(LiveOutRegs); |
| } |
| |
| /// A heuristic to filter nodes in recurrent node-sets if the register |
| /// pressure of a set is too high. |
| void SwingSchedulerDAG::registerPressureFilter(NodeSetType &NodeSets) { |
| for (auto &NS : NodeSets) { |
| // Skip small node-sets since they won't cause register pressure problems. |
| if (NS.size() <= 2) |
| continue; |
| IntervalPressure RecRegPressure; |
| RegPressureTracker RecRPTracker(RecRegPressure); |
| RecRPTracker.init(&MF, &RegClassInfo, &LIS, BB, BB->end(), false, true); |
| computeLiveOuts(MF, RecRPTracker, NS); |
| RecRPTracker.closeBottom(); |
| |
| std::vector<SUnit *> SUnits(NS.begin(), NS.end()); |
| llvm::sort(SUnits, [](const SUnit *A, const SUnit *B) { |
| return A->NodeNum > B->NodeNum; |
| }); |
| |
| for (auto &SU : SUnits) { |
| // Since we're computing the register pressure for a subset of the |
| // instructions in a block, we need to set the tracker for each |
| // instruction in the node-set. The tracker is set to the instruction |
| // just after the one we're interested in. |
| MachineBasicBlock::const_iterator CurInstI = SU->getInstr(); |
| RecRPTracker.setPos(std::next(CurInstI)); |
| |
| RegPressureDelta RPDelta; |
| ArrayRef<PressureChange> CriticalPSets; |
| RecRPTracker.getMaxUpwardPressureDelta(SU->getInstr(), nullptr, RPDelta, |
| CriticalPSets, |
| RecRegPressure.MaxSetPressure); |
| if (RPDelta.Excess.isValid()) { |
| LLVM_DEBUG( |
| dbgs() << "Excess register pressure: SU(" << SU->NodeNum << ") " |
| << TRI->getRegPressureSetName(RPDelta.Excess.getPSet()) |
| << ":" << RPDelta.Excess.getUnitInc() << "\n"); |
| NS.setExceedPressure(SU); |
| break; |
| } |
| RecRPTracker.recede(); |
| } |
| } |
| } |
| |
| /// A heuristic to colocate node sets that have the same set of |
| /// successors. |
| void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) { |
| unsigned Colocate = 0; |
| for (int i = 0, e = NodeSets.size(); i < e; ++i) { |
| NodeSet &N1 = NodeSets[i]; |
| SmallSetVector<SUnit *, 8> S1; |
| if (N1.empty() || !succ_L(N1, S1)) |
| continue; |
| for (int j = i + 1; j < e; ++j) { |
| NodeSet &N2 = NodeSets[j]; |
| if (N1.compareRecMII(N2) != 0) |
| continue; |
| SmallSetVector<SUnit *, 8> S2; |
| if (N2.empty() || !succ_L(N2, S2)) |
| continue; |
| if (llvm::set_is_subset(S1, S2) && S1.size() == S2.size()) { |
| N1.setColocate(++Colocate); |
| N2.setColocate(Colocate); |
| break; |
| } |
| } |
| } |
| } |
| |
| /// Check if the existing node-sets are profitable. If not, then ignore the |
| /// recurrent node-sets, and attempt to schedule all nodes together. This is |
| /// a heuristic. If the MII is large and all the recurrent node-sets are small, |
| /// then it's best to try to schedule all instructions together instead of |
| /// starting with the recurrent node-sets. |
| void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) { |
| // Look for loops with a large MII. |
| if (MII < 17) |
| return; |
| // Check if the node-set contains only a simple add recurrence. |
| for (auto &NS : NodeSets) { |
| if (NS.getRecMII() > 2) |
| return; |
| if (NS.getMaxDepth() > MII) |
| return; |
| } |
| NodeSets.clear(); |
| LLVM_DEBUG(dbgs() << "Clear recurrence node-sets\n"); |
| } |
| |
| /// Add the nodes that do not belong to a recurrence set into groups |
| /// based upon connected components. |
| void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) { |
| SetVector<SUnit *> NodesAdded; |
| SmallPtrSet<SUnit *, 8> Visited; |
| // Add the nodes that are on a path between the previous node sets and |
| // the current node set. |
| for (NodeSet &I : NodeSets) { |
| SmallSetVector<SUnit *, 8> N; |
| // Add the nodes from the current node set to the previous node set. |
| if (succ_L(I, N)) { |
| SetVector<SUnit *> Path; |
| for (SUnit *NI : N) { |
| Visited.clear(); |
| computePath(NI, Path, NodesAdded, I, Visited); |
| } |
| if (!Path.empty()) |
| I.insert(Path.begin(), Path.end()); |
| } |
| // Add the nodes from the previous node set to the current node set. |
| N.clear(); |
| if (succ_L(NodesAdded, N)) { |
| SetVector<SUnit *> Path; |
| for (SUnit *NI : N) { |
| Visited.clear(); |
| computePath(NI, Path, I, NodesAdded, Visited); |
| } |
| if (!Path.empty()) |
| I.insert(Path.begin(), Path.end()); |
| } |
| NodesAdded.insert(I.begin(), I.end()); |
| } |
| |
| // Create a new node set with the connected nodes of any successor of a node |
| // in a recurrent set. |
| NodeSet NewSet; |
| SmallSetVector<SUnit *, 8> N; |
| if (succ_L(NodesAdded, N)) |
| for (SUnit *I : N) |
| addConnectedNodes(I, NewSet, NodesAdded); |
| if (!NewSet.empty()) |
| NodeSets.push_back(NewSet); |
| |
| // Create a new node set with the connected nodes of any predecessor of a node |
| // in a recurrent set. |
| NewSet.clear(); |
| if (pred_L(NodesAdded, N)) |
| for (SUnit *I : N) |
| addConnectedNodes(I, NewSet, NodesAdded); |
| if (!NewSet.empty()) |
| NodeSets.push_back(NewSet); |
| |
| // Create new nodes sets with the connected nodes any remaining node that |
| // has no predecessor. |
| for (SUnit &SU : SUnits) { |
| if (NodesAdded.count(&SU) == 0) { |
| NewSet.clear(); |
| addConnectedNodes(&SU, NewSet, NodesAdded); |
| if (!NewSet.empty()) |
| NodeSets.push_back(NewSet); |
| } |
| } |
| } |
| |
| /// Add the node to the set, and add all of its connected nodes to the set. |
| void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet, |
| SetVector<SUnit *> &NodesAdded) { |
| NewSet.insert(SU); |
| NodesAdded.insert(SU); |
| for (auto &SI : SU->Succs) { |
| SUnit *Successor = SI.getSUnit(); |
| if (!SI.isArtificial() && !Successor->isBoundaryNode() && |
| NodesAdded.count(Successor) == 0) |
| addConnectedNodes(Successor, NewSet, NodesAdded); |
| } |
| for (auto &PI : SU->Preds) { |
| SUnit *Predecessor = PI.getSUnit(); |
| if (!PI.isArtificial() && NodesAdded.count(Predecessor) == 0) |
| addConnectedNodes(Predecessor, NewSet, NodesAdded); |
| } |
| } |
| |
| /// Return true if Set1 contains elements in Set2. The elements in common |
| /// are returned in a different container. |
| static bool isIntersect(SmallSetVector<SUnit *, 8> &Set1, const NodeSet &Set2, |
| SmallSetVector<SUnit *, 8> &Result) { |
| Result.clear(); |
| for (SUnit *SU : Set1) { |
| if (Set2.count(SU) != 0) |
| Result.insert(SU); |
| } |
| return !Result.empty(); |
| } |
| |
| /// Merge the recurrence node sets that have the same initial node. |
| void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) { |
| for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E; |
| ++I) { |
| NodeSet &NI = *I; |
| for (NodeSetType::iterator J = I + 1; J != E;) { |
| NodeSet &NJ = *J; |
| if (NI.getNode(0)->NodeNum == NJ.getNode(0)->NodeNum) { |
| if (NJ.compareRecMII(NI) > 0) |
| NI.setRecMII(NJ.getRecMII()); |
| for (SUnit *SU : *J) |
| I->insert(SU); |
| NodeSets.erase(J); |
| E = NodeSets.end(); |
| } else { |
| ++J; |
| } |
| } |
| } |
| } |
| |
| /// Remove nodes that have been scheduled in previous NodeSets. |
| void SwingSchedulerDAG::removeDuplicateNodes(NodeSetType &NodeSets) { |
| for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E; |
| ++I) |
| for (NodeSetType::iterator J = I + 1; J != E;) { |
| J->remove_if([&](SUnit *SUJ) { return I->count(SUJ); }); |
| |
| if (J->empty()) { |
| NodeSets.erase(J); |
| E = NodeSets.end(); |
| } else { |
| ++J; |
| } |
| } |
| } |
| |
| /// Compute an ordered list of the dependence graph nodes, which |
| /// indicates the order that the nodes will be scheduled. This is a |
| /// two-level algorithm. First, a partial order is created, which |
| /// consists of a list of sets ordered from highest to lowest priority. |
| void SwingSchedulerDAG::computeNodeOrder(NodeSetType &NodeSets) { |
| SmallSetVector<SUnit *, 8> R; |
| NodeOrder.clear(); |
| |
| for (auto &Nodes : NodeSets) { |
| LLVM_DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n"); |
| OrderKind Order; |
| SmallSetVector<SUnit *, 8> N; |
| if (pred_L(NodeOrder, N) && llvm::set_is_subset(N, Nodes)) { |
| R.insert(N.begin(), N.end()); |
| Order = BottomUp; |
| LLVM_DEBUG(dbgs() << " Bottom up (preds) "); |
| } else if (succ_L(NodeOrder, N) && llvm::set_is_subset(N, Nodes)) { |
| R.insert(N.begin(), N.end()); |
| Order = TopDown; |
| LLVM_DEBUG(dbgs() << " Top down (succs) "); |
| } else if (isIntersect(N, Nodes, R)) { |
| // If some of the successors are in the existing node-set, then use the |
| // top-down ordering. |
| Order = TopDown; |
| LLVM_DEBUG(dbgs() << " Top down (intersect) "); |
| } else if (NodeSets.size() == 1) { |
| for (const auto &N : Nodes) |
| if (N->Succs.size() == 0) |
| R.insert(N); |
| Order = BottomUp; |
| LLVM_DEBUG(dbgs() << " Bottom up (all) "); |
| } else { |
| // Find the node with the highest ASAP. |
| SUnit *maxASAP = nullptr; |
| for (SUnit *SU : Nodes) { |
| if (maxASAP == nullptr || getASAP(SU) > getASAP(maxASAP) || |
| (getASAP(SU) == getASAP(maxASAP) && SU->NodeNum > maxASAP->NodeNum)) |
| maxASAP = SU; |
| } |
| R.insert(maxASAP); |
| Order = BottomUp; |
| LLVM_DEBUG(dbgs() << " Bottom up (default) "); |
| } |
| |
| while (!R.empty()) { |
| if (Order == TopDown) { |
| // Choose the node with the maximum height. If more than one, choose |
| // the node wiTH the maximum ZeroLatencyHeight. If still more than one, |
| // choose the node with the lowest MOV. |
| while (!R.empty()) { |
| SUnit *maxHeight = nullptr; |
| for (SUnit *I : R) { |
| if (maxHeight == nullptr || getHeight(I) > getHeight(maxHeight)) |
| maxHeight = I; |
| else if (getHeight(I) == getHeight(maxHeight) && |
| getZeroLatencyHeight(I) > getZeroLatencyHeight(maxHeight)) |
| maxHeight = I; |
| else if (getHeight(I) == getHeight(maxHeight) && |
| getZeroLatencyHeight(I) == |
| getZeroLatencyHeight(maxHeight) && |
| getMOV(I) < getMOV(maxHeight)) |
| maxHeight = I; |
| } |
| NodeOrder.insert(maxHeight); |
| LLVM_DEBUG(dbgs() << maxHeight->NodeNum << " "); |
| R.remove(maxHeight); |
| for (const auto &I : maxHeight->Succs) { |
| if (Nodes.count(I.getSUnit()) == 0) |
| continue; |
| if (NodeOrder.contains(I.getSUnit())) |
| continue; |
| if (ignoreDependence(I, false)) |
| continue; |
| R.insert(I.getSUnit()); |
| } |
| // Back-edges are predecessors with an anti-dependence. |
| for (const auto &I : maxHeight->Preds) { |
| if (I.getKind() != SDep::Anti) |
| continue; |
| if (Nodes.count(I.getSUnit()) == 0) |
| continue; |
| if (NodeOrder.contains(I.getSUnit())) |
| continue; |
| R.insert(I.getSUnit()); |
| } |
| } |
| Order = BottomUp; |
| LLVM_DEBUG(dbgs() << "\n Switching order to bottom up "); |
| SmallSetVector<SUnit *, 8> N; |
| if (pred_L(NodeOrder, N, &Nodes)) |
| R.insert(N.begin(), N.end()); |
| } else { |
| // Choose the node with the maximum depth. If more than one, choose |
| // the node with the maximum ZeroLatencyDepth. If still more than one, |
| // choose the node with the lowest MOV. |
| while (!R.empty()) { |
| SUnit *maxDepth = nullptr; |
| for (SUnit *I : R) { |
| if (maxDepth == nullptr || getDepth(I) > getDepth(maxDepth)) |
| maxDepth = I; |
| else if (getDepth(I) == getDepth(maxDepth) && |
| getZeroLatencyDepth(I) > getZeroLatencyDepth(maxDepth)) |
| maxDepth = I; |
| else if (getDepth(I) == getDepth(maxDepth) && |
| getZeroLatencyDepth(I) == getZeroLatencyDepth(maxDepth) && |
| getMOV(I) < getMOV(maxDepth)) |
| maxDepth = I; |
| } |
| NodeOrder.insert(maxDepth); |
| LLVM_DEBUG(dbgs() << maxDepth->NodeNum << " "); |
| R.remove(maxDepth); |
| if (Nodes.isExceedSU(maxDepth)) { |
| Order = TopDown; |
| R.clear(); |
| R.insert(Nodes.getNode(0)); |
| break; |
| } |
| for (const auto &I : maxDepth->Preds) { |
| if (Nodes.count(I.getSUnit()) == 0) |
| continue; |
| if (NodeOrder.contains(I.getSUnit())) |
| continue; |
| R.insert(I.getSUnit()); |
| } |
| // Back-edges are predecessors with an anti-dependence. |
| for (const auto &I : maxDepth->Succs) { |
| if (I.getKind() != SDep::Anti) |
| continue; |
| if (Nodes.count(I.getSUnit()) == 0) |
| continue; |
| if (NodeOrder.contains(I.getSUnit())) |
| continue; |
| R.insert(I.getSUnit()); |
| } |
| } |
| Order = TopDown; |
| LLVM_DEBUG(dbgs() << "\n Switching order to top down "); |
| SmallSetVector<SUnit *, 8> N; |
| if (succ_L(NodeOrder, N, &Nodes)) |
| R.insert(N.begin(), N.end()); |
| } |
| } |
| LLVM_DEBUG(dbgs() << "\nDone with Nodeset\n"); |
| } |
| |
| LLVM_DEBUG({ |
| dbgs() << "Node order: "; |
| for (SUnit *I : NodeOrder) |
| dbgs() << " " << I->NodeNum << " "; |
| dbgs() << "\n"; |
| }); |
| } |
| |
| /// Process the nodes in the computed order and create the pipelined schedule |
| /// of the instructions, if possible. Return true if a schedule is found. |
| bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) { |
| |
| if (NodeOrder.empty()){ |
| LLVM_DEBUG(dbgs() << "NodeOrder is empty! abort scheduling\n" ); |
| return false; |
| } |
| |
| bool scheduleFound = false; |
| // Keep increasing II until a valid schedule is found. |
| for (unsigned II = MII; II <= MAX_II && !scheduleFound; ++II) { |
| Schedule.reset(); |
| Schedule.setInitiationInterval(II); |
| LLVM_DEBUG(dbgs() << "Try to schedule with " << II << "\n"); |
| |
| SetVector<SUnit *>::iterator NI = NodeOrder.begin(); |
| SetVector<SUnit *>::iterator NE = NodeOrder.end(); |
| do { |
| SUnit *SU = *NI; |
| |
| // Compute the schedule time for the instruction, which is based |
| // upon the scheduled time for any predecessors/successors. |
| int EarlyStart = INT_MIN; |
| int LateStart = INT_MAX; |
| // These values are set when the size of the schedule window is limited |
| // due to chain dependences. |
| int SchedEnd = INT_MAX; |
| int SchedStart = INT_MIN; |
| Schedule.computeStart(SU, &EarlyStart, &LateStart, &SchedEnd, &SchedStart, |
| II, this); |
| LLVM_DEBUG({ |
| dbgs() << "\n"; |
| dbgs() << "Inst (" << SU->NodeNum << ") "; |
| SU->getInstr()->dump(); |
| dbgs() << "\n"; |
| }); |
| LLVM_DEBUG({ |
| dbgs() << format("\tes: %8x ls: %8x me: %8x ms: %8x\n", EarlyStart, |
| LateStart, SchedEnd, SchedStart); |
| }); |
| |
| if (EarlyStart > LateStart || SchedEnd < EarlyStart || |
| SchedStart > LateStart) |
| scheduleFound = false; |
| else if (EarlyStart != INT_MIN && LateStart == INT_MAX) { |
| SchedEnd = std::min(SchedEnd, EarlyStart + (int)II - 1); |
| scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II); |
| } else if (EarlyStart == INT_MIN && LateStart != INT_MAX) { |
| SchedStart = std::max(SchedStart, LateStart - (int)II + 1); |
| scheduleFound = Schedule.insert(SU, LateStart, SchedStart, II); |
| } else if (EarlyStart != INT_MIN && LateStart != INT_MAX) { |
| SchedEnd = |
| std::min(SchedEnd, std::min(LateStart, EarlyStart + (int)II - 1)); |
| // When scheduling a Phi it is better to start at the late cycle and go |
| // backwards. The default order may insert the Phi too far away from |
| // its first dependence. |
| if (SU->getInstr()->isPHI()) |
| scheduleFound = Schedule.insert(SU, SchedEnd, EarlyStart, II); |
| else |
| scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II); |
| } else { |
| int FirstCycle = Schedule.getFirstCycle(); |
| scheduleFound = Schedule.insert(SU, FirstCycle + getASAP(SU), |
| FirstCycle + getASAP(SU) + II - 1, II); |
| } |
| // Even if we find a schedule, make sure the schedule doesn't exceed the |
| // allowable number of stages. We keep trying if this happens. |
| if (scheduleFound) |
| if (SwpMaxStages > -1 && |
| Schedule.getMaxStageCount() > (unsigned)SwpMaxStages) |
| scheduleFound = false; |
| |
| LLVM_DEBUG({ |
| if (!scheduleFound) |
| dbgs() << "\tCan't schedule\n"; |
| }); |
| } while (++NI != NE && scheduleFound); |
| |
| // If a schedule is found, ensure non-pipelined instructions are in stage 0 |
| if (scheduleFound) |
| scheduleFound = |
| Schedule.normalizeNonPipelinedInstructions(this, LoopPipelinerInfo); |
| |
| // If a schedule is found, check if it is a valid schedule too. |
| if (scheduleFound) |
| scheduleFound = Schedule.isValidSchedule(this); |
| } |
| |
| LLVM_DEBUG(dbgs() << "Schedule Found? " << scheduleFound |
| << " (II=" << Schedule.getInitiationInterval() |
| << ")\n"); |
| |
| if (scheduleFound) { |
| scheduleFound = LoopPipelinerInfo->shouldUseSchedule(*this, Schedule); |
| if (!scheduleFound) |
| LLVM_DEBUG(dbgs() << "Target rejected schedule\n"); |
| } |
| |
| if (scheduleFound) { |
| Schedule.finalizeSchedule(this); |
| Pass.ORE->emit([&]() { |
| return MachineOptimizationRemarkAnalysis( |
| DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader()) |
| << "Schedule found with Initiation Interval: " |
| << ore::NV("II", Schedule.getInitiationInterval()) |
| << ", MaxStageCount: " |
| << ore::NV("MaxStageCount", Schedule.getMaxStageCount()); |
| }); |
| } else |
| Schedule.reset(); |
| |
| return scheduleFound && Schedule.getMaxStageCount() > 0; |
| } |
| |
| /// Return true if we can compute the amount the instruction changes |
| /// during each iteration. Set Delta to the amount of the change. |
| bool SwingSchedulerDAG::computeDelta(MachineInstr &MI, unsigned &Delta) { |
| const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); |
| const MachineOperand *BaseOp; |
| int64_t Offset; |
| bool OffsetIsScalable; |
| if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI)) |
| return false; |
| |
| // FIXME: This algorithm assumes instructions have fixed-size offsets. |
| if (OffsetIsScalable) |
| return false; |
| |
| if (!BaseOp->isReg()) |
| return false; |
| |
| Register BaseReg = BaseOp->getReg(); |
| |
| MachineRegisterInfo &MRI = MF.getRegInfo(); |
| // Check if there is a Phi. If so, get the definition in the loop. |
| MachineInstr *BaseDef = MRI.getVRegDef(BaseReg); |
| if (BaseDef && BaseDef->isPHI()) { |
| BaseReg = getLoopPhiReg(*BaseDef, MI.getParent()); |
| BaseDef = MRI.getVRegDef(BaseReg); |
| } |
| if (!BaseDef) |
| return false; |
| |
| int D = 0; |
| if (!TII->getIncrementValue(*BaseDef, D) && D >= 0) |
| return false; |
| |
| Delta = D; |
| return true; |
| } |
| |
| /// Check if we can change the instruction to use an offset value from the |
| /// previous iteration. If so, return true and set the base and offset values |
| /// so that we can rewrite the load, if necessary. |
| /// v1 = Phi(v0, v3) |
| /// v2 = load v1, 0 |
| /// v3 = post_store v1, 4, x |
| /// This function enables the load to be rewritten as v2 = load v3, 4. |
| bool SwingSchedulerDAG::canUseLastOffsetValue(MachineInstr *MI, |
| unsigned &BasePos, |
| unsigned &OffsetPos, |
| unsigned &NewBase, |
| int64_t &Offset) { |
| // Get the load instruction. |
| if (TII->isPostIncrement(*MI)) |
| return false; |
| unsigned BasePosLd, OffsetPosLd; |
| if (!TII->getBaseAndOffsetPosition(*MI, BasePosLd, OffsetPosLd)) |
| return false; |
| Register BaseReg = MI->getOperand(BasePosLd).getReg(); |
| |
| // Look for the Phi instruction. |
| MachineRegisterInfo &MRI = MI->getMF()->getRegInfo(); |
| MachineInstr *Phi = MRI.getVRegDef(BaseReg); |
| if (!Phi || !Phi->isPHI()) |
| return false; |
| // Get the register defined in the loop block. |
| unsigned PrevReg = getLoopPhiReg(*Phi, MI->getParent()); |
| if (!PrevReg) |
| return false; |
| |
| // Check for the post-increment load/store instruction. |
| MachineInstr *PrevDef = MRI.getVRegDef(PrevReg); |
| if (!PrevDef || PrevDef == MI) |
| return false; |
| |
| if (!TII->isPostIncrement(*PrevDef)) |
| return false; |
| |
| unsigned BasePos1 = 0, OffsetPos1 = 0; |
| if (!TII->getBaseAndOffsetPosition(*PrevDef, BasePos1, OffsetPos1)) |
| return false; |
| |
| // Make sure that the instructions do not access the same memory location in |
| // the next iteration. |
| int64_t LoadOffset = MI->getOperand(OffsetPosLd).getImm(); |
| int64_t StoreOffset = PrevDef->getOperand(OffsetPos1).getImm(); |
| MachineInstr *NewMI = MF.CloneMachineInstr(MI); |
| NewMI->getOperand(OffsetPosLd).setImm(LoadOffset + StoreOffset); |
| bool Disjoint = TII->areMemAccessesTriviallyDisjoint(*NewMI, *PrevDef); |
| MF.deleteMachineInstr(NewMI); |
| if (!Disjoint) |
| return false; |
| |
| // Set the return value once we determine that we return true. |
| BasePos = BasePosLd; |
| OffsetPos = OffsetPosLd; |
| NewBase = PrevReg; |
| Offset = StoreOffset; |
| return true; |
| } |
| |
| /// Apply changes to the instruction if needed. The changes are need |
| /// to improve the scheduling and depend up on the final schedule. |
| void SwingSchedulerDAG::applyInstrChange(MachineInstr *MI, |
| SMSchedule &Schedule) { |
| SUnit *SU = getSUnit(MI); |
| DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It = |
| InstrChanges.find(SU); |
| if (It != InstrChanges.end()) { |
| std::pair<unsigned, int64_t> RegAndOffset = It->second; |
| unsigned BasePos, OffsetPos; |
| if (!TII->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos)) |
| return; |
| Register BaseReg = MI->getOperand(BasePos).getReg(); |
| MachineInstr *LoopDef = findDefInLoop(BaseReg); |
| int DefStageNum = Schedule.stageScheduled(getSUnit(LoopDef)); |
| int DefCycleNum = Schedule.cycleScheduled(getSUnit(LoopDef)); |
| int BaseStageNum = Schedule.stageScheduled(SU); |
| int BaseCycleNum = Schedule.cycleScheduled(SU); |
| if (BaseStageNum < DefStageNum) { |
| MachineInstr *NewMI = MF.CloneMachineInstr(MI); |
| int OffsetDiff = DefStageNum - BaseStageNum; |
| if (DefCycleNum < BaseCycleNum) { |
| NewMI->getOperand(BasePos).setReg(RegAndOffset.first); |
| if (OffsetDiff > 0) |
| --OffsetDiff; |
| } |
| int64_t NewOffset = |
| MI->getOperand(OffsetPos).getImm() + RegAndOffset.second * OffsetDiff; |
| NewMI->getOperand(OffsetPos).setImm(NewOffset); |
| SU->setInstr(NewMI); |
| MISUnitMap[NewMI] = SU; |
| NewMIs[MI] = NewMI; |
| } |
| } |
| } |
| |
| /// Return the instruction in the loop that defines the register. |
| /// If the definition is a Phi, then follow the Phi operand to |
| /// the instruction in the loop. |
| MachineInstr *SwingSchedulerDAG::findDefInLoop(Register Reg) { |
| SmallPtrSet<MachineInstr *, 8> Visited; |
| MachineInstr *Def = MRI.getVRegDef(Reg); |
| while (Def->isPHI()) { |
| if (!Visited.insert(Def).second) |
| break; |
| for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) |
| if (Def->getOperand(i + 1).getMBB() == BB) { |
| Def = MRI.getVRegDef(Def->getOperand(i).getReg()); |
| break; |
| } |
| } |
| return Def; |
| } |
| |
| /// Return true for an order or output dependence that is loop carried |
| /// potentially. A dependence is loop carried if the destination defines a valu |
| /// that may be used or defined by the source in a subsequent iteration. |
| bool SwingSchedulerDAG::isLoopCarriedDep(SUnit *Source, const SDep &Dep, |
| bool isSucc) { |
| if ((Dep.getKind() != SDep::Order && Dep.getKind() != SDep::Output) || |
| Dep.isArtificial() || Dep.getSUnit()->isBoundaryNode()) |
| return false; |
| |
| if (!SwpPruneLoopCarried) |
| return true; |
| |
| if (Dep.getKind() == SDep::Output) |
| return true; |
| |
| MachineInstr *SI = Source->getInstr(); |
| MachineInstr *DI = Dep.getSUnit()->getInstr(); |
| if (!isSucc) |
| std::swap(SI, DI); |
| assert(SI != nullptr && DI != nullptr && "Expecting SUnit with an MI."); |
| |
| // Assume ordered loads and stores may have a loop carried dependence. |
| if (SI->hasUnmodeledSideEffects() || DI->hasUnmodeledSideEffects() || |
| SI->mayRaiseFPException() || DI->mayRaiseFPException() || |
| SI->hasOrderedMemoryRef() || DI->hasOrderedMemoryRef()) |
| return true; |
| |
| // Only chain dependences between a load and store can be loop carried. |
| if (!DI->mayStore() || !SI->mayLoad()) |
| return false; |
| |
| unsigned DeltaS, DeltaD; |
| if (!computeDelta(*SI, DeltaS) || !computeDelta(*DI, DeltaD)) |
| return true; |
| |
| const MachineOperand *BaseOpS, *BaseOpD; |
| int64_t OffsetS, OffsetD; |
| bool OffsetSIsScalable, OffsetDIsScalable; |
| const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); |
| if (!TII->getMemOperandWithOffset(*SI, BaseOpS, OffsetS, OffsetSIsScalable, |
| TRI) || |
| !TII->getMemOperandWithOffset(*DI, BaseOpD, OffsetD, OffsetDIsScalable, |
| TRI)) |
| return true; |
| |
| assert(!OffsetSIsScalable && !OffsetDIsScalable && |
| "Expected offsets to be byte offsets"); |
| |
| MachineInstr *DefS = MRI.getVRegDef(BaseOpS->getReg()); |
| MachineInstr *DefD = MRI.getVRegDef(BaseOpD->getReg()); |
| if (!DefS || !DefD || !DefS->isPHI() || !DefD->isPHI()) |
| return true; |
| |
| unsigned InitValS = 0; |
| unsigned LoopValS = 0; |
| unsigned InitValD = 0; |
| unsigned LoopValD = 0; |
| getPhiRegs(*DefS, BB, InitValS, LoopValS); |
| getPhiRegs(*DefD, BB, InitValD, LoopValD); |
| MachineInstr *InitDefS = MRI.getVRegDef(InitValS); |
| MachineInstr *InitDefD = MRI.getVRegDef(InitValD); |
| |
| if (!InitDefS->isIdenticalTo(*InitDefD)) |
| return true; |
| |
| // Check that the base register is incremented by a constant value for each |
| // iteration. |
| MachineInstr *LoopDefS = MRI.getVRegDef(LoopValS); |
| int D = 0; |
| if (!LoopDefS || !TII->getIncrementValue(*LoopDefS, D)) |
| return true; |
| |
| uint64_t AccessSizeS = (*SI->memoperands_begin())->getSize(); |
| uint64_t AccessSizeD = (*DI->memoperands_begin())->getSize(); |
| |
| // This is the main test, which checks the offset values and the loop |
| // increment value to determine if the accesses may be loop carried. |
| if (AccessSizeS == MemoryLocation::UnknownSize || |
| AccessSizeD == MemoryLocation::UnknownSize) |
| return true; |
| |
| if (DeltaS != DeltaD || DeltaS < AccessSizeS || DeltaD < AccessSizeD) |
| return true; |
| |
| return (OffsetS + (int64_t)AccessSizeS < OffsetD + (int64_t)AccessSizeD); |
| } |
| |
| void SwingSchedulerDAG::postProcessDAG() { |
| for (auto &M : Mutations) |
| M->apply(this); |
| } |
| |
| /// Try to schedule the node at the specified StartCycle and continue |
| /// until the node is schedule or the EndCycle is reached. This function |
| /// returns true if the node is scheduled. This routine may search either |
| /// forward or backward for a place to insert the instruction based upon |
| /// the relative values of StartCycle and EndCycle. |
| bool SMSchedule::insert(SUnit *SU, int StartCycle, int EndCycle, int II) { |
| bool forward = true; |
| LLVM_DEBUG({ |
| dbgs() << "Trying to insert node between " << StartCycle << " and " |
| << EndCycle << " II: " << II << "\n"; |
| }); |
| if (StartCycle > EndCycle) |
| forward = false; |
| |
| // The terminating condition depends on the direction. |
| int termCycle = forward ? EndCycle + 1 : EndCycle - 1; |
| for (int curCycle = StartCycle; curCycle != termCycle; |
| forward ? ++curCycle : --curCycle) { |
| |
| if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()) || |
| ProcItinResources.canReserveResources(*SU, curCycle)) { |
| LLVM_DEBUG({ |
| dbgs() << "\tinsert at cycle " << curCycle << " "; |
| SU->getInstr()->dump(); |
| }); |
| |
| if (!ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode())) |
| ProcItinResources.reserveResources(*SU, curCycle); |
| ScheduledInstrs[curCycle].push_back(SU); |
| InstrToCycle.insert(std::make_pair(SU, curCycle)); |
| if (curCycle > LastCycle) |
| LastCycle = curCycle; |
| if (curCycle < FirstCycle) |
| FirstCycle = curCycle; |
| return true; |
| } |
| LLVM_DEBUG({ |
| dbgs() << "\tfailed to insert at cycle " << curCycle << " "; |
| SU->getInstr()->dump(); |
| }); |
| } |
| return false; |
| } |
| |
| // Return the cycle of the earliest scheduled instruction in the chain. |
| int SMSchedule::earliestCycleInChain(const SDep &Dep) { |
| SmallPtrSet<SUnit *, 8> Visited; |
| SmallVector<SDep, 8> Worklist; |
| Worklist.push_back(Dep); |
| int EarlyCycle = INT_MAX; |
| while (!Worklist.empty()) { |
| const SDep &Cur = Worklist.pop_back_val(); |
| SUnit *PrevSU = Cur.getSUnit(); |
| if (Visited.count(PrevSU)) |
| continue; |
| std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(PrevSU); |
| if (it == InstrToCycle.end()) |
| continue; |
| EarlyCycle = std::min(EarlyCycle, it->second); |
| for (const auto &PI : PrevSU->Preds) |
| if (PI.getKind() == SDep::Order || PI.getKind() == SDep::Output) |
| Worklist.push_back(PI); |
| Visited.insert(PrevSU); |
| } |
| return EarlyCycle; |
| } |
| |
| // Return the cycle of the latest scheduled instruction in the chain. |
| int SMSchedule::latestCycleInChain(const SDep &Dep) { |
| SmallPtrSet<SUnit *, 8> Visited; |
| SmallVector<SDep, 8> Worklist; |
| Worklist.push_back(Dep); |
| int LateCycle = INT_MIN; |
| while (!Worklist.empty()) { |
| const SDep &Cur = Worklist.pop_back_val(); |
| SUnit *SuccSU = Cur.getSUnit(); |
| if (Visited.count(SuccSU) || SuccSU->isBoundaryNode()) |
| continue; |
| std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SuccSU); |
| if (it == InstrToCycle.end()) |
| continue; |
| LateCycle = std::max(LateCycle, it->second); |
| for (const auto &SI : SuccSU->Succs) |
| if (SI.getKind() == SDep::Order || SI.getKind() == SDep::Output) |
| Worklist.push_back(SI); |
| Visited.insert(SuccSU); |
| } |
| return LateCycle; |
| } |
| |
| /// If an instruction has a use that spans multiple iterations, then |
| /// return true. These instructions are characterized by having a back-ege |
| /// to a Phi, which contains a reference to another Phi. |
| static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) { |
| for (auto &P : SU->Preds) |
| if (DAG->isBackedge(SU, P) && P.getSUnit()->getInstr()->isPHI()) |
| for (auto &S : P.getSUnit()->Succs) |
| if (S.getKind() == SDep::Data && S.getSUnit()->getInstr()->isPHI()) |
| return P.getSUnit(); |
| return nullptr; |
| } |
| |
| /// Compute the scheduling start slot for the instruction. The start slot |
| /// depends on any predecessor or successor nodes scheduled already. |
| void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, |
| int *MinEnd, int *MaxStart, int II, |
| SwingSchedulerDAG *DAG) { |
| // Iterate over each instruction that has been scheduled already. The start |
| // slot computation depends on whether the previously scheduled instruction |
| // is a predecessor or successor of the specified instruction. |
| for (int cycle = getFirstCycle(); cycle <= LastCycle; ++cycle) { |
| |
| // Iterate over each instruction in the current cycle. |
| for (SUnit *I : getInstructions(cycle)) { |
| // Because we're processing a DAG for the dependences, we recognize |
| // the back-edge in recurrences by anti dependences. |
| for (unsigned i = 0, e = (unsigned)SU->Preds.size(); i != e; ++i) { |
| const SDep &Dep = SU->Preds[i]; |
| if (Dep.getSUnit() == I) { |
| if (!DAG->isBackedge(SU, Dep)) { |
| int EarlyStart = cycle + Dep.getLatency() - |
| DAG->getDistance(Dep.getSUnit(), SU, Dep) * II; |
| *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart); |
| if (DAG->isLoopCarriedDep(SU, Dep, false)) { |
| int End = earliestCycleInChain(Dep) + (II - 1); |
| *MinEnd = std::min(*MinEnd, End); |
| } |
| } else { |
| int LateStart = cycle - Dep.getLatency() + |
| DAG->getDistance(SU, Dep.getSUnit(), Dep) * II; |
| *MinLateStart = std::min(*MinLateStart, LateStart); |
| } |
| } |
| // For instruction that requires multiple iterations, make sure that |
| // the dependent instruction is not scheduled past the definition. |
| SUnit *BE = multipleIterations(I, DAG); |
| if (BE && Dep.getSUnit() == BE && !SU->getInstr()->isPHI() && |
| !SU->isPred(I)) |
| *MinLateStart = std::min(*MinLateStart, cycle); |
| } |
| for (unsigned i = 0, e = (unsigned)SU->Succs.size(); i != e; ++i) { |
| if (SU->Succs[i].getSUnit() == I) { |
| const SDep &Dep = SU->Succs[i]; |
| if (!DAG->isBackedge(SU, Dep)) { |
| int LateStart = cycle - Dep.getLatency() + |
| DAG->getDistance(SU, Dep.getSUnit(), Dep) * II; |
| *MinLateStart = std::min(*MinLateStart, LateStart); |
| if (DAG->isLoopCarriedDep(SU, Dep)) { |
| int Start = latestCycleInChain(Dep) + 1 - II; |
| *MaxStart = std::max(*MaxStart, Start); |
| } |
| } else { |
| int EarlyStart = cycle + Dep.getLatency() - |
| DAG->getDistance(Dep.getSUnit(), SU, Dep) * II; |
| *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart); |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| /// Order the instructions within a cycle so that the definitions occur |
| /// before the uses. Returns true if the instruction is added to the start |
| /// of the list, or false if added to the end. |
| void SMSchedule::orderDependence(SwingSchedulerDAG *SSD, SUnit *SU, |
| std::deque<SUnit *> &Insts) { |
| MachineInstr *MI = SU->getInstr(); |
| bool OrderBeforeUse = false; |
| bool OrderAfterDef = false; |
| bool OrderBeforeDef = false; |
| unsigned MoveDef = 0; |
| unsigned MoveUse = 0; |
| int StageInst1 = stageScheduled(SU); |
| |
| unsigned Pos = 0; |
| for (std::deque<SUnit *>::iterator I = Insts.begin(), E = Insts.end(); I != E; |
| ++I, ++Pos) { |
| for (MachineOperand &MO : MI->operands()) { |
| if (!MO.isReg() || !MO.getReg().isVirtual()) |
| continue; |
| |
| Register Reg = MO.getReg(); |
| unsigned BasePos, OffsetPos; |
| if (ST.getInstrInfo()->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos)) |
| if (MI->getOperand(BasePos).getReg() == Reg) |
| if (unsigned NewReg = SSD->getInstrBaseReg(SU)) |
| Reg = NewReg; |
| bool Reads, Writes; |
| std::tie(Reads, Writes) = |
| (*I)->getInstr()->readsWritesVirtualRegister(Reg); |
| if (MO.isDef() && Reads && stageScheduled(*I) <= StageInst1) { |
| OrderBeforeUse = true; |
| if (MoveUse == 0) |
| MoveUse = Pos; |
| } else if (MO.isDef() && Reads && stageScheduled(*I) > StageInst1) { |
| // Add the instruction after the scheduled instruction. |
| OrderAfterDef = true; |
| MoveDef = Pos; |
| } else if (MO.isUse() && Writes && stageScheduled(*I) == StageInst1) { |
| if (cycleScheduled(*I) == cycleScheduled(SU) && !(*I)->isSucc(SU)) { |
| OrderBeforeUse = true; |
| if (MoveUse == 0) |
| MoveUse = Pos; |
| } else { |
| OrderAfterDef = true; |
| MoveDef = Pos; |
| } |
| } else if (MO.isUse() && Writes && stageScheduled(*I) > StageInst1) { |
| OrderBeforeUse = true; |
| if (MoveUse == 0) |
| MoveUse = Pos; |
| if (MoveUse != 0) { |
| OrderAfterDef = true; |
| MoveDef = Pos - 1; |
| } |
| } else if (MO.isUse() && Writes && stageScheduled(*I) < StageInst1) { |
| // Add the instruction before the scheduled instruction. |
| OrderBeforeUse = true; |
| if (MoveUse == 0) |
| MoveUse = Pos; |
| } else if (MO.isUse() && stageScheduled(*I) == StageInst1 && |
| isLoopCarriedDefOfUse(SSD, (*I)->getInstr(), MO)) { |
| if (MoveUse == 0) { |
| OrderBeforeDef = true; |
| MoveUse = Pos; |
| } |
| } |
| } |
| // Check for order dependences between instructions. Make sure the source |
| // is ordered before the destination. |
| for (auto &S : SU->Succs) { |
| if (S.getSUnit() != *I) |
| continue; |
| if (S.getKind() == SDep::Order && stageScheduled(*I) == StageInst1) { |
| OrderBeforeUse = true; |
| if (Pos < MoveUse) |
| MoveUse = Pos; |
| } |
| // We did not handle HW dependences in previous for loop, |
| // and we normally set Latency = 0 for Anti deps, |
| // so may have nodes in same cycle with Anti denpendent on HW regs. |
| else if (S.getKind() == SDep::Anti && stageScheduled(*I) == StageInst1) { |
| OrderBeforeUse = true; |
| if ((MoveUse == 0) || (Pos < MoveUse)) |
| MoveUse = Pos; |
| } |
| } |
| for (auto &P : SU->Preds) { |
| if (P.getSUnit() != *I) |
| continue; |
| if (P.getKind() == SDep::Order && stageScheduled(*I) == StageInst1) { |
| OrderAfterDef = true; |
| MoveDef = Pos; |
| } |
| } |
| } |
| |
| // A circular dependence. |
| if (OrderAfterDef && OrderBeforeUse && MoveUse == MoveDef) |
| OrderBeforeUse = false; |
| |
| // OrderAfterDef takes precedences over OrderBeforeDef. The latter is due |
| // to a loop-carried dependence. |
| if (OrderBeforeDef) |
| OrderBeforeUse = !OrderAfterDef || (MoveUse > MoveDef); |
| |
| // The uncommon case when the instruction order needs to be updated because |
| // there is both a use and def. |
| if (OrderBeforeUse && |