LLVM 17.0.0git
|
#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>
Go to the source code of this file.
Namespaces | |
namespace | llvm |
This is an optimization pass for GlobalISel generic memory operations. | |
Macros | |
#define | DEBUG_TYPE "pipeliner" |
Functions | |
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") | |
cl::opt< bool > | llvm::SwpEnableCopyToPhi ("pipeliner-enable-copytophi", cl::ReallyHidden, cl::init(true), cl::desc("Enable CopyToPhi DAG Mutation")) |
cl::opt< int > | llvm::SwpForceIssueWidth ("pipeliner-force-issue-width", cl::desc("Force pipeliner to use specified issue width."), cl::Hidden, cl::init(-1)) |
A command line argument to force pipeliner to use specified issue width. | |
INITIALIZE_PASS_BEGIN (MachinePipeliner, DEBUG_TYPE, "Modulo Software Pipelining", false, false) INITIALIZE_PASS_END(MachinePipeliner | |
static void | getPhiRegs (MachineInstr &Phi, MachineBasicBlock *Loop, unsigned &InitVal, unsigned &LoopVal) |
Return the register values for the operands of a Phi instruction. | |
static unsigned | getLoopPhiReg (MachineInstr &Phi, MachineBasicBlock *LoopBB) |
Return the Phi register value that comes the loop block. | |
static bool | isSuccOrder (SUnit *SUa, SUnit *SUb) |
Return true if SUb can be reached from SUa following the chain edges. | |
static bool | isDependenceBarrier (MachineInstr &MI) |
Return true if the instruction causes a chain between memory references before and after it. | |
static void | getUnderlyingObjects (const MachineInstr *MI, SmallVectorImpl< const Value * > &Objs) |
Return the underlying objects for the memory references of an instruction. | |
static void | swapAntiDependences (std::vector< SUnit > &SUnits) |
Swap all the anti dependences in the DAG. | |
static bool | ignoreDependence (const SDep &D, bool isPred) |
Return true for DAG nodes that we ignore when computing the cost functions. | |
static bool | pred_L (SetVector< SUnit * > &NodeOrder, SmallSetVector< SUnit *, 8 > &Preds, const NodeSet *S=nullptr) |
Compute the Pred_L(O) set, as defined in the paper. | |
static bool | succ_L (SetVector< SUnit * > &NodeOrder, SmallSetVector< SUnit *, 8 > &Succs, const NodeSet *S=nullptr) |
Compute the Succ_L(O) set, as defined in the paper. | |
static bool | computePath (SUnit *Cur, SetVector< SUnit * > &Path, SetVector< SUnit * > &DestNodes, SetVector< SUnit * > &Exclude, SmallPtrSet< SUnit *, 8 > &Visited) |
Return true if there is a path from the specified node to any of the nodes in DestNodes. | |
static void | computeLiveOuts (MachineFunction &MF, RegPressureTracker &RPTracker, NodeSet &NS) |
Compute the live-out registers for the instructions in a node-set. | |
static bool | isIntersect (SmallSetVector< SUnit *, 8 > &Set1, const NodeSet &Set2, SmallSetVector< SUnit *, 8 > &Result) |
Return true if Set1 contains elements in Set2. | |
static SUnit * | multipleIterations (SUnit *SU, SwingSchedulerDAG *DAG) |
If an instruction has a use that spans multiple iterations, then return true. | |
Variables | |
static cl::opt< bool > | EnableSWP ("enable-pipeliner", cl::Hidden, cl::init(true), cl::desc("Enable Software Pipelining")) |
A command line option to turn software pipelining on or off. | |
static cl::opt< bool > | EnableSWPOptSize ("enable-pipeliner-opt-size", cl::desc("Enable SWP at Os."), cl::Hidden, cl::init(false)) |
A command line option to enable SWP at -Os. | |
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 limit minimum initial interval for pipelining. | |
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 force pipeliner to use specified initial interval. | |
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 argument to limit the number of stages in the pipeline. | |
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 chain dependences due to an unrelated Phi. | |
static cl::opt< bool > | SwpPruneLoopCarried ("pipeliner-prune-loop-carried", cl::desc("Prune loop carried order dependences."), cl::Hidden, cl::init(true)) |
A command line option to disable the pruning of loop carried order dependences. | |
static cl::opt< int > | SwpLoopLimit ("pipeliner-max", cl::Hidden, cl::init(-1)) |
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")) |
DEBUG_TYPE | |
Modulo Software | Pipelining |
Modulo Software | false |
#define DEBUG_TYPE "pipeliner" |
Definition at line 99 of file MachinePipeliner.cpp.
|
static |
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.
Definition at line 1550 of file MachinePipeliner.cpp.
References llvm::RegPressureTracker::addLiveRegs(), llvm::MachineInstr::all_defs(), llvm::SUnit::getInstr(), llvm::LaneBitmask::getNone(), llvm::MachineFunction::getRegInfo(), llvm::TargetSubtargetInfo::getRegisterInfo(), llvm::MachineFunction::getSubtarget(), llvm::MCRegisterInfo::DiffListIterator::isValid(), MI, MRI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), TRI, and Uses.
|
static |
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.
Definition at line 1521 of file MachinePipeliner.cpp.
References llvm::SDep::Anti, computePath(), llvm::SetVector< T, Vector, Set >::contains(), ignoreDependence(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SUnit::isBoundaryNode(), llvm::SUnit::Preds, SI, and llvm::SUnit::Succs.
Referenced by computePath().
|
static |
Return the Phi register value that comes the loop block.
Definition at line 698 of file MachinePipeliner.cpp.
References llvm::MachineOperand::getMBB(), llvm::MachineInstr::getNumOperands(), llvm::MachineInstr::getOperand(), and llvm::MachineOperand::getReg().
Referenced by llvm::SMSchedule::isLoopCarriedDefOfUse().
|
static |
Return the register values for the operands of a Phi instruction.
This function assume the instruction is a Phi.
Definition at line 682 of file MachinePipeliner.cpp.
References assert(), llvm::MachineOperand::getMBB(), llvm::MachineInstr::getNumOperands(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getReg(), and llvm::MachineInstr::isPHI().
Referenced by llvm::SMSchedule::isLoopCarried(), and llvm::SwingSchedulerDAG::isLoopCarriedDep().
|
static |
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.
Definition at line 739 of file MachinePipeliner.cpp.
References llvm::SmallVectorImpl< T >::clear(), llvm::getUnderlyingObjects(), llvm::MachineMemOperand::getValue(), llvm::isIdentifiedObject(), MI, and llvm::SmallVectorTemplateBase< T, bool >::push_back().
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.
Definition at line 1379 of file MachinePipeliner.cpp.
References llvm::SDep::Anti, and D.
Referenced by computePath(), pred_L(), and succ_L().
INITIALIZE_PASS_BEGIN | ( | MachinePipeliner | , |
DEBUG_TYPE | , | ||
"Modulo Software Pipelining" | , | ||
false | , | ||
false | |||
) |
|
static |
Return true if the instruction causes a chain between memory references before and after it.
Definition at line 729 of file MachinePipeliner.cpp.
References MI.
|
static |
Return true if Set1 contains elements in Set2.
The elements in common are returned in a different container.
Definition at line 1762 of file MachinePipeliner.cpp.
References llvm::NodeSet::count().
Return true if SUb can be reached from SUa following the chain edges.
Definition at line 706 of file MachinePipeliner.cpp.
References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SDep::Order, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), SI, and llvm::SUnit::Succs.
|
static |
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.
Definition at line 2414 of file MachinePipeliner.cpp.
References llvm::SDep::Data, llvm::SUnit::getInstr(), llvm::SDep::getKind(), llvm::SDep::getSUnit(), llvm::SwingSchedulerDAG::isBackedge(), llvm::MachineInstr::isPHI(), P, and llvm::SUnit::Preds.
Referenced by llvm::SMSchedule::computeStart().
|
static |
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.
Definition at line 1465 of file MachinePipeliner.cpp.
References llvm::SDep::Anti, llvm::SetVector< T, Vector, Set >::clear(), llvm::SetVector< T, Vector, Set >::empty(), llvm::SDep::getKind(), llvm::SDep::getSUnit(), ignoreDependence(), llvm::SetVector< T, Vector, Set >::insert(), llvm::NodeOrder, llvm::SUnit::Preds, and llvm::SUnit::Succs.
STATISTIC | ( | NumFailBranch | , |
"Pipeliner abort due to unknown branch" | |||
) |
STATISTIC | ( | NumFailLargeMaxMII | , |
"Pipeliner abort due to MaxMII too large" | |||
) |
STATISTIC | ( | NumFailLargeMaxStage | , |
"Pipeliner abort due to too many stages" | |||
) |
STATISTIC | ( | NumFailLoop | , |
"Pipeliner abort due to unsupported loop" | |||
) |
STATISTIC | ( | NumFailNoSchedule | , |
"Pipeliner abort due to no schedule found" | |||
) |
STATISTIC | ( | NumFailPreheader | , |
"Pipeliner abort due to missing preheader" | |||
) |
STATISTIC | ( | NumFailZeroMII | , |
"Pipeliner abort due to zero MII" | |||
) |
STATISTIC | ( | NumFailZeroStage | , |
"Pipeliner abort due to zero stage" | |||
) |
STATISTIC | ( | NumNodeOrderIssues | , |
"Number of node order issues found" | |||
) |
STATISTIC | ( | NumPipelined | , |
"Number of loops software pipelined" | |||
) |
STATISTIC | ( | NumTrytoPipeline | , |
"Number of loops that we attempt to pipeline" | |||
) |
|
static |
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.
Definition at line 1494 of file MachinePipeliner.cpp.
References llvm::SDep::Anti, llvm::SetVector< T, Vector, Set >::clear(), llvm::SetVector< T, Vector, Set >::empty(), llvm::SDep::getKind(), llvm::SDep::getSUnit(), ignoreDependence(), llvm::SetVector< T, Vector, Set >::insert(), llvm::NodeOrder, llvm::SUnit::Preds, and llvm::SUnit::Succs.
|
static |
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.
Definition at line 1147 of file MachinePipeliner.cpp.
References llvm::SUnit::addPred(), llvm::SDep::Anti, D, llvm::SDep::getKind(), P, llvm::SUnit::Preds, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SUnit::removePred(), and llvm::SDep::setLatency().
DEBUG_TYPE |
Definition at line 206 of file MachinePipeliner.cpp.
|
static |
Referenced by llvm::SwingSchedulerDAG::schedule().
|
static |
A command line option to turn software pipelining on or off.
Referenced by llvm::MachinePipeliner::runOnMachineFunction().
|
static |
A command line option to enable SWP at -Os.
Referenced by llvm::MachinePipeliner::runOnMachineFunction().
|
static |
Referenced by llvm::SwingSchedulerDAG::schedule().
Modulo Software false |
Definition at line 207 of file MachinePipeliner.cpp.
Modulo Software Pipelining |
Definition at line 207 of file MachinePipeliner.cpp.
|
static |
A command line argument to force pipeliner to use specified initial interval.
|
static |
Referenced by llvm::SwingSchedulerDAG::schedule().
|
static |
|
static |
A command line argument to limit minimum initial interval for pipelining.
Referenced by llvm::SwingSchedulerDAG::schedule().
|
static |
A command line argument to limit the number of stages in the pipeline.
Referenced by llvm::SwingSchedulerDAG::schedule().
|
static |
A command line option to disable the pruning of chain dependences due to an unrelated Phi.
|
static |
A command line option to disable the pruning of loop carried order dependences.
Referenced by llvm::SwingSchedulerDAG::isLoopCarriedDep().
|
static |
Referenced by llvm::ResourceManager::initProcResourceVectors().