LLVM  13.0.0git
Namespaces | Macros | Functions | Variables
MachinePipeliner.cpp File Reference
#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/MemoryLocation.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/MachinePipeliner.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/DebugLoc.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 <iterator>
#include <map>
#include <memory>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Namespaces

 llvm
 

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::ZeroOrMore, cl::desc("Enable CopyToPhi DAG Mutation"))
 
 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. More...
 
static unsigned getLoopPhiReg (MachineInstr &Phi, MachineBasicBlock *LoopBB)
 Return the Phi register value that comes the loop block. More...
 
static bool isSuccOrder (SUnit *SUa, SUnit *SUb)
 Return true if SUb can be reached from SUa following the chain edges. More...
 
static bool isDependenceBarrier (MachineInstr &MI, AliasAnalysis *AA)
 Return true if the instruction causes a chain between memory references before and after it. More...
 
static void getUnderlyingObjects (const MachineInstr *MI, SmallVectorImpl< const Value * > &Objs)
 Return the underlying objects for the memory references of an instruction. More...
 
static void swapAntiDependences (std::vector< SUnit > &SUnits)
 Swap all the anti dependences in the DAG. More...
 
static bool ignoreDependence (const SDep &D, bool isPred)
 Return true for DAG nodes that we ignore when computing the cost functions. More...
 
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. More...
 
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. More...
 
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. More...
 
static void computeLiveOuts (MachineFunction &MF, RegPressureTracker &RPTracker, NodeSet &NS)
 Compute the live-out registers for the instructions in a node-set. More...
 
static bool isIntersect (SmallSetVector< SUnit *, 8 > &Set1, const NodeSet &Set2, SmallSetVector< SUnit *, 8 > &Result)
 Return true if Set1 contains elements in Set2. More...
 
static SUnitmultipleIterations (SUnit *SU, SwingSchedulerDAG *DAG)
 If an instruction has a use that spans multiple iterations, then return true. More...
 

Variables

static cl::opt< bool > EnableSWP ("enable-pipeliner", cl::Hidden, cl::init(true), cl::ZeroOrMore, cl::desc("Enable Software Pipelining"))
 A command line option to turn software pipelining on or off. More...
 
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. More...
 
static cl::opt< intSwpMaxMii ("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. More...
 
static cl::opt< intSwpMaxStages ("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. More...
 
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. More...
 
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. More...
 
static cl::opt< intSwpLoopLimit ("pipeliner-max", cl::Hidden, cl::init(-1))
 
static cl::opt< bool > SwpIgnoreRecMII ("pipeliner-ignore-recmii", cl::ReallyHidden, cl::init(false), cl::ZeroOrMore, 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
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "pipeliner"

Definition at line 96 of file MachinePipeliner.cpp.

Function Documentation

◆ computeLiveOuts()

static void computeLiveOuts ( MachineFunction MF,
RegPressureTracker RPTracker,
NodeSet NS 
)
static

◆ computePath()

static bool computePath ( SUnit Cur,
SetVector< SUnit * > &  Path,
SetVector< SUnit * > &  DestNodes,
SetVector< SUnit * > &  Exclude,
SmallPtrSet< SUnit *, 8 > &  Visited 
)
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 1579 of file MachinePipeliner.cpp.

References llvm::SDep::Anti, llvm::SetVector< T, Vector, Set >::contains(), llvm::SetVector< T, Vector, Set >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SUnit::isBoundaryNode(), llvm::SUnit::Preds, SI, and llvm::SUnit::Succs.

◆ getLoopPhiReg()

static unsigned getLoopPhiReg ( MachineInstr Phi,
MachineBasicBlock LoopBB 
)
static

◆ getPhiRegs()

static void getPhiRegs ( MachineInstr Phi,
MachineBasicBlock Loop,
unsigned &  InitVal,
unsigned &  LoopVal 
)
static

Return the register values for the operands of a Phi instruction.

This function assume the instruction is a Phi.

Definition at line 662 of file MachinePipeliner.cpp.

References assert(), llvm::numbers::e, llvm::MachineOperand::getMBB(), llvm::MachineInstr::getNumOperands(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getReg(), i, and llvm::MachineInstr::isPHI().

Referenced by llvm::SMSchedule::isLoopCarried(), and llvm::SwingSchedulerDAG::isLoopCarriedDep().

◆ getUnderlyingObjects()

static void getUnderlyingObjects ( const MachineInstr MI,
SmallVectorImpl< const Value * > &  Objs 
)
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 719 of file MachinePipeliner.cpp.

References llvm::getUnderlyingObjects(), llvm::MachineMemOperand::getValue(), llvm::isIdentifiedObject(), and MI.

◆ ignoreDependence()

static bool ignoreDependence ( const SDep D,
bool  isPred 
)
static

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 1431 of file MachinePipeliner.cpp.

References llvm::SDep::Anti, and D.

Referenced by pred_L(), and succ_L().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( MachinePipeliner  ,
DEBUG_TYPE  ,
"Modulo Software Pipelining ,
false  ,
false   
)

◆ isDependenceBarrier()

static bool isDependenceBarrier ( MachineInstr MI,
AliasAnalysis AA 
)
static

Return true if the instruction causes a chain between memory references before and after it.

Definition at line 709 of file MachinePipeliner.cpp.

References MI.

◆ isIntersect()

static bool isIntersect ( SmallSetVector< SUnit *, 8 > &  Set1,
const NodeSet Set2,
SmallSetVector< SUnit *, 8 > &  Result 
)
static

Return true if Set1 contains elements in Set2.

The elements in common are returned in a different container.

Definition at line 1818 of file MachinePipeliner.cpp.

References llvm::NodeSet::count(), llvm::numbers::e, i, and llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size().

◆ isSuccOrder()

static bool isSuccOrder ( SUnit SUa,
SUnit SUb 
)
static

Return true if SUb can be reached from SUa following the chain edges.

Definition at line 686 of file MachinePipeliner.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SDep::Order, llvm::SmallVectorImpl< T >::pop_back_val(), SI, and llvm::SUnit::Succs.

◆ multipleIterations()

static SUnit* multipleIterations ( SUnit SU,
SwingSchedulerDAG DAG 
)
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 2465 of file MachinePipeliner.cpp.

References llvm::SDep::Data, llvm::SwingSchedulerDAG::isBackedge(), P, llvm::SUnit::Preds, and S.

◆ pred_L()

static bool pred_L ( SetVector< SUnit * > &  NodeOrder,
SmallSetVector< SUnit *, 8 > &  Preds,
const NodeSet S = nullptr 
)
static

◆ STATISTIC() [1/11]

STATISTIC ( NumFailBranch  ,
"Pipeliner abort due to unknown branch"   
)

◆ STATISTIC() [2/11]

STATISTIC ( NumFailLargeMaxMII  ,
"Pipeliner abort due to MaxMII too large"   
)

◆ STATISTIC() [3/11]

STATISTIC ( NumFailLargeMaxStage  ,
"Pipeliner abort due to too many stages"   
)

◆ STATISTIC() [4/11]

STATISTIC ( NumFailLoop  ,
"Pipeliner abort due to unsupported loop  
)

◆ STATISTIC() [5/11]

STATISTIC ( NumFailNoSchedule  ,
"Pipeliner abort due to no schedule found"   
)

◆ STATISTIC() [6/11]

STATISTIC ( NumFailPreheader  ,
"Pipeliner abort due to missing preheader  
)

◆ STATISTIC() [7/11]

STATISTIC ( NumFailZeroMII  ,
"Pipeliner abort due to zero MII"   
)

◆ STATISTIC() [8/11]

STATISTIC ( NumFailZeroStage  ,
"Pipeliner abort due to zero stage"   
)

◆ STATISTIC() [9/11]

STATISTIC ( NumNodeOrderIssues  ,
"Number of node order issues found"   
)

◆ STATISTIC() [10/11]

STATISTIC ( NumPipelined  ,
"Number of loops software pipelined"   
)

◆ STATISTIC() [11/11]

STATISTIC ( NumTrytoPipeline  ,
"Number of loops that we attempt to pipeline"   
)

◆ succ_L()

static bool succ_L ( SetVector< SUnit * > &  NodeOrder,
SmallSetVector< SUnit *, 8 > &  Succs,
const NodeSet S = nullptr 
)
static

◆ swapAntiDependences()

static void swapAntiDependences ( std::vector< SUnit > &  SUnits)
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 1194 of file MachinePipeliner.cpp.

References llvm::SUnit::addPred(), llvm::SDep::Anti, D, llvm::numbers::e, i, P, llvm::SUnit::Preds, Reg, llvm::SUnit::removePred(), and llvm::SDep::setLatency().

Variable Documentation

◆ DEBUG_TYPE

DEBUG_TYPE

Definition at line 192 of file MachinePipeliner.cpp.

◆ EmitTestAnnotations

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

◆ EnableSWP

cl::opt<bool> EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true), cl::ZeroOrMore, cl::desc("Enable Software Pipelining"))
static

A command line option to turn software pipelining on or off.

Referenced by llvm::MachinePipeliner::runOnMachineFunction().

◆ EnableSWPOptSize

cl::opt<bool> EnableSWPOptSize("enable-pipeliner-opt-size", cl::desc("Enable SWP at Os."), cl::Hidden, cl::init(false))
static

A command line option to enable SWP at -Os.

Referenced by llvm::MachinePipeliner::runOnMachineFunction().

◆ ExperimentalCodeGen

cl::opt<bool> ExperimentalCodeGen("pipeliner-experimental-cg", cl::Hidden, cl::init(false), cl::desc( "Use the experimental peeling code generator for software pipelining"))
static

◆ false

Modulo Software false

Definition at line 193 of file MachinePipeliner.cpp.

◆ Pipelining

Modulo Software Pipelining

Definition at line 193 of file MachinePipeliner.cpp.

◆ SwpDebugResource

cl::opt<bool> SwpDebugResource("pipeliner-dbg-res", cl::Hidden, cl::init(false))
static

◆ SwpIgnoreRecMII

cl::opt<bool> SwpIgnoreRecMII("pipeliner-ignore-recmii", cl::ReallyHidden, cl::init(false), cl::ZeroOrMore, cl::desc("Ignore RecMII"))
static

◆ SwpLoopLimit

cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1))
static

◆ SwpMaxMii

cl::opt<int> SwpMaxMii("pipeliner-max-mii", cl::desc("Size limit for the MII."), cl::Hidden, cl::init(27))
static

A command line argument to limit minimum initial interval for pipelining.

Referenced by llvm::SwingSchedulerDAG::schedule().

◆ SwpMaxStages

cl::opt<int> SwpMaxStages("pipeliner-max-stages", cl::desc("Maximum stages allowed in the generated scheduled."), cl::Hidden, cl::init(3))
static

A command line argument to limit the number of stages in the pipeline.

Referenced by llvm::SwingSchedulerDAG::schedule().

◆ SwpPruneDeps

cl::opt<bool> SwpPruneDeps("pipeliner-prune-deps", cl::desc("Prune dependences between unrelated Phi nodes."), cl::Hidden, cl::init(true))
static

A command line option to disable the pruning of chain dependences due to an unrelated Phi.

◆ SwpPruneLoopCarried

cl::opt<bool> SwpPruneLoopCarried("pipeliner-prune-loop-carried", cl::desc("Prune loop carried order dependences."), cl::Hidden, cl::init(true))
static

A command line option to disable the pruning of loop carried order dependences.

Referenced by llvm::SwingSchedulerDAG::isLoopCarriedDep().

◆ SwpShowResMask

cl::opt<bool> SwpShowResMask("pipeliner-show-mask", cl::Hidden, cl::init(false))
static