LLVM  8.0.1
Macros | Functions | Variables
RegisterCoalescer.cpp File Reference
#include "RegisterCoalescer.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/MachineBasicBlock.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/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCInstrDesc.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/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>
Include dependency graph for RegisterCoalescer.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "regalloc"
 

Functions

 STATISTIC (numJoins, "Number of interval joins performed")
 
 STATISTIC (numCrossRCs, "Number of cross class joins performed")
 
 STATISTIC (numCommutes, "Number of instruction commuting performed")
 
 STATISTIC (numExtends, "Number of copies extended")
 
 STATISTIC (NumReMats, "Number of instructions re-materialized")
 
 STATISTIC (NumInflated, "Number of register classes inflated")
 
 STATISTIC (NumLaneConflicts, "Number of dead lane conflicts tested")
 
 STATISTIC (NumLaneResolves, "Number of dead lane conflicts resolved")
 
 STATISTIC (NumShrinkToUses, "Number of shrinkToUses called")
 
 INITIALIZE_PASS_BEGIN (RegisterCoalescer, "simple-register-coalescing", "Simple Register Coalescing", false, false) INITIALIZE_PASS_END(RegisterCoalescer
 
simple register Simple Register static false bool isMoveInstr (const TargetRegisterInfo &tri, const MachineInstr *MI, unsigned &Src, unsigned &Dst, unsigned &SrcSub, unsigned &DstSub)
 
static bool isSplitEdge (const MachineBasicBlock *MBB)
 Return true if this block should be vacated by the coalescer to eliminate branches. More...
 
static std::pair< bool, booladdSegmentsWithValNo (LiveRange &Dst, VNInfo *DstValNo, const LiveRange &Src, const VNInfo *SrcValNo)
 Copy segments with value number SrcValNo from liverange Src to live range and use value number DstValNo there. More...
 
static bool definesFullReg (const MachineInstr &MI, unsigned Reg)
 Returns true if MI defines the full vreg Reg, as opposed to just defining a subregister. More...
 
static bool isDefInSubRange (LiveInterval &LI, SlotIndex Def)
 Check if any of the subranges of LI contain a definition at Def. More...
 
static int compareMBBPriority (const MBBPriorityInfo *LHS, const MBBPriorityInfo *RHS)
 C-style comparator that sorts first based on the loop depth of the basic block (the unsigned), and then on the MBB number. More...
 
static bool isLocalCopy (MachineInstr *Copy, const LiveIntervals *LIS)
 
static bool isTerminalReg (unsigned DstReg, const MachineInstr &Copy, const MachineRegisterInfo *MRI)
 Check if DstReg is a terminal node. More...
 

Variables

static cl::opt< boolEnableJoining ("join-liveintervals", cl::desc("Coalesce copies (default=true)"), cl::init(true), cl::Hidden)
 
static cl::opt< boolUseTerminalRule ("terminal-rule", cl::desc("Apply the terminal rule"), cl::init(false), cl::Hidden)
 
static cl::opt< boolEnableJoinSplits ("join-splitedges", cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden)
 Temporary flag to test critical edge unsplitting. More...
 
static cl::opt< cl::boolOrDefaultEnableGlobalCopies ("join-globalcopies", cl::desc("Coalesce copies that span blocks (default=subtarget)"), cl::init(cl::BOU_UNSET), cl::Hidden)
 Temporary flag to test global copy optimization. More...
 
static cl::opt< boolVerifyCoalescing ("verify-coalescing", cl::desc("Verify machine instrs before and after register coalescing"), cl::Hidden)
 
static cl::opt< unsignedLateRematUpdateThreshold ("late-remat-update-threshold", cl::Hidden, cl::desc("During rematerialization for a copy, if the def instruction has " "many other copy uses to be rematerialized, delay the multiple " "separate live interval update work and do them all at once after " "all those rematerialization are done. It will save a lot of " "repeated work. "), cl::init(100))
 
simple register coalescing
 
simple register Simple Register Coalescing
 
simple register Simple Register false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "regalloc"

Definition at line 63 of file RegisterCoalescer.cpp.

Function Documentation

◆ addSegmentsWithValNo()

static std::pair<bool,bool> addSegmentsWithValNo ( LiveRange Dst,
VNInfo DstValNo,
const LiveRange Src,
const VNInfo SrcValNo 
)
static

Copy segments with value number SrcValNo from liverange Src to live range and use value number DstValNo there.

Definition at line 694 of file RegisterCoalescer.cpp.

References llvm::LiveRange::addSegment(), Allocator, assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::BuildMI(), llvm::SmallVectorImpl< T >::clear(), llvm::TargetInstrInfo::CommuteAnyOperandIndex, llvm::TargetInstrInfo::commuteInstruction(), llvm::MachineRegisterInfo::constrainRegClass(), llvm::LiveRange::createDeadDef(), llvm::LiveInterval::createSubRangeFrom(), llvm::dbgs(), llvm::VNInfo::def, DefMI, llvm::LiveRange::Segment::end, llvm::MachineBasicBlock::end(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::MachineBasicBlock::erase(), llvm::LiveIntervals::extendToIndices(), llvm::TargetInstrInfo::findCommutedOpIndices(), llvm::MachineInstr::findRegisterDefOperandIdx(), llvm::MCInstrInfo::get(), llvm::SlotIndex::getBaseIndex(), llvm::MachineInstr::getDebugLoc(), llvm::CoalescerPair::getDstReg(), llvm::MachineBasicBlock::getFirstTerminator(), llvm::LiveIntervals::getInstructionFromIndex(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::MachineRegisterInfo::getMaxLaneMaskForVReg(), llvm::LiveIntervals::getMBBEndIdx(), llvm::LiveIntervals::getMBBStartIdx(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getParent(), llvm::MachineInstr::getParent(), llvm::MachineOperand::getReg(), llvm::MachineRegisterInfo::getRegClass(), llvm::SlotIndex::getRegSlot(), llvm::CoalescerPair::getSrcReg(), llvm::MachineOperand::getSubReg(), llvm::LiveIntervals::getVNInfoAllocator(), llvm::LiveRange::getVNInfoAt(), llvm::LiveRange::getVNInfoBefore(), llvm::LiveInterval::hasSubRanges(), I, llvm::MachineBasicBlock::insert(), llvm::LiveIntervals::InsertMachineInstrInMaps(), llvm::MachineInstr::isCommutable(), llvm::MachineInstr::isCopy(), llvm::SlotIndex::isDead(), llvm::MachineInstr::isDebugValue(), llvm::MachineBasicBlock::isEHPad(), llvm::CoalescerPair::isFlipped(), llvm::MachineInstr::isFullCopy(), llvm::LiveQueryResult::isKill(), llvm::VNInfo::isPHIDef(), llvm::CoalescerPair::isPhys(), llvm::TargetRegisterInfo::isPhysicalRegister(), llvm::MachineInstr::isRegTiedToDefOperand(), llvm::MachineInstr::isRegTiedToUseOperand(), llvm::SlotIndex::isSameInstr(), llvm::MachineOperand::isUndef(), llvm::VNInfo::isUnused(), llvm::TargetRegisterInfo::isVirtualRegister(), LLVM_DEBUG, llvm::VNInfo::markUnused(), llvm::BitmaskEnumDetail::Mask(), llvm::LiveRange::MergeValueNumberInto(), llvm::LiveRange::overlaps(), P, llvm::SmallVectorTemplateBase< T >::pop_back(), llvm::MachineBasicBlock::pred_size(), llvm::MachineBasicBlock::predecessors(), llvm::printMBBReference(), llvm::LiveIntervals::pruneValue(), llvm::LiveRange::Query(), llvm::LiveInterval::refineSubRanges(), llvm::LiveInterval::reg, llvm::LiveIntervals::removeVRegDefAt(), llvm::LiveIntervals::ReplaceMachineInstrInMaps(), llvm::LiveRange::segments, llvm::MachineOperand::setIsKill(), llvm::MachineOperand::setReg(), llvm::SmallVectorBase::size(), llvm::LiveRange::Segment::start, llvm::LiveInterval::subranges(), llvm::MachineOperand::substPhysReg(), llvm::MachineBasicBlock::succ_size(), llvm::MachineRegisterInfo::use_begin(), llvm::MachineRegisterInfo::use_end(), llvm::MachineRegisterInfo::use_nodbg_operands(), UseMI, llvm::LiveRange::Segment::valno, llvm::LiveRange::valnos, and llvm::LiveQueryResult::valueOutOrDead().

◆ compareMBBPriority()

static int compareMBBPriority ( const MBBPriorityInfo *  LHS,
const MBBPriorityInfo *  RHS 
)
static

C-style comparator that sorts first based on the loop depth of the basic block (the unsigned), and then on the MBB number.

EnableGlobalCopies assumes that the primary sort key is loop depth.

Definition at line 3388 of file RegisterCoalescer.cpp.

Referenced by isTerminalReg().

◆ definesFullReg()

static bool definesFullReg ( const MachineInstr MI,
unsigned  Reg 
)
static

Returns true if MI defines the full vreg Reg, as opposed to just defining a subregister.

Definition at line 1160 of file RegisterCoalescer.cpp.

References assert(), llvm::TargetRegisterInfo::composeSubRegIndexLaneMask(), llvm::TargetRegisterInfo::composeSubRegIndices(), llvm::TargetRegisterClass::contains(), llvm::VNInfo::def, DefMI, E, llvm::MachineInstr::eraseFromParent(), llvm::TargetRegisterInfo::getCommonSubClass(), llvm::MachineInstr::getDebugLoc(), llvm::MachineInstr::getDesc(), llvm::CoalescerPair::getDstIdx(), llvm::CoalescerPair::getDstReg(), llvm::LiveIntervals::getInstructionFromIndex(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::TargetRegisterInfo::getMatchingSuperRegClass(), llvm::MachineRegisterInfo::getMaxLaneMaskForVReg(), llvm::CoalescerPair::getNewRC(), llvm::MCInstrDesc::getNumDefs(), llvm::MCInstrDesc::getNumOperands(), llvm::MachineInstr::getNumOperands(), llvm::MachineInstr::getOperand(), llvm::MachineInstr::getParent(), llvm::MachineOperand::getReg(), llvm::TargetInstrInfo::getRegClass(), llvm::MachineRegisterInfo::getRegClass(), llvm::SlotIndex::getRegSlot(), llvm::CoalescerPair::getSrcIdx(), llvm::CoalescerPair::getSrcReg(), llvm::MCRegisterInfo::getSubReg(), llvm::MachineOperand::getSubReg(), llvm::LiveInterval::hasSubRanges(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::TargetInstrInfo::isAsCheapAsAMove(), llvm::MachineInstr::isCopyLike(), llvm::MachineOperand::isDead(), llvm::MachineOperand::isDef(), llvm::MachineOperand::isEarlyClobber(), llvm::CoalescerPair::isFlipped(), llvm::MachineOperand::isImplicit(), llvm::MachineInstr::isImplicitDef(), llvm::VNInfo::isPHIDef(), llvm::TargetRegisterInfo::isPhysicalRegister(), llvm::MachineOperand::isReg(), llvm::MachineInstr::isSafeToMove(), llvm::TargetInstrInfo::isTriviallyReMaterializable(), llvm::MachineOperand::isUndef(), llvm::VNInfo::isUnused(), llvm::TargetRegisterInfo::isVirtualRegister(), llvm::MachineInstr::operands(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::LiveRange::Query(), Reg, llvm::TargetInstrInfo::reMaterialize(), llvm::LiveIntervals::ReplaceMachineInstrInMaps(), llvm::SmallVectorImpl< T >::reserve(), llvm::MachineInstr::setDebugLoc(), llvm::MachineOperand::setIsUndef(), llvm::MachineRegisterInfo::setRegClass(), llvm::MachineOperand::setSubReg(), llvm::LiveInterval::subranges(), and llvm::LiveQueryResult::valueIn().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( RegisterCoalescer  ,
"simple-register-coalescing ,
"Simple Register Coalescing ,
false  ,
false   
)

◆ isDefInSubRange()

static bool isDefInSubRange ( LiveInterval LI,
SlotIndex  Def 
)
static

Check if any of the subranges of LI contain a definition at Def.

Definition at line 3045 of file RegisterCoalescer.cpp.

References Allocator, llvm::LaneBitmask::any(), assert(), llvm::LiveRange::assign(), llvm::MachineRegisterInfo::clearKillFlags(), llvm::HexagonISD::CP, llvm::LiveInterval::createSubRangeFrom(), llvm::dbgs(), llvm::tgtok::Def, llvm::VNInfo::def, llvm::Depth, llvm::SmallVectorBase::empty(), llvm::LiveRange::empty(), llvm::MachineInstr::eraseFromParent(), llvm::CoalescerPair::getDstReg(), llvm::LiveIntervals::getInterval(), llvm::CoalescerPair::getNewRC(), llvm::LaneBitmask::getNone(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getReg(), llvm::CoalescerPair::getSrcIdx(), llvm::CoalescerPair::getSrcReg(), llvm::LiveIntervals::getVNInfoAllocator(), llvm::LiveInterval::hasSubRanges(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::MachineInstr::isCopy(), llvm::VNInfo::isPHIDef(), llvm::CoalescerPair::isPhys(), llvm::VNInfo::isUnused(), llvm::SlotIndex::isValid(), llvm::TargetRegisterInfo::isVirtualRegister(), llvm::LiveRange::join(), llvm::LiveInterval::SubRange::LaneMask, llvm::AArch64CC::LE, LLVM_DEBUG, LLVM_FALLTHROUGH, llvm_unreachable, llvm::VNInfo::markUnused(), llvm::BitmaskEnumDetail::Mask(), llvm::max(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::PrintLaneMask(), llvm::printReg(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::LiveInterval::refineSubRanges(), llvm::LiveInterval::reg, llvm::LiveIntervals::RemoveMachineInstrFromMaps(), llvm::MachineRegisterInfo::shouldTrackSubRegLiveness(), llvm::SmallVectorBase::size(), llvm::LiveInterval::subranges(), TRI, and llvm::LiveRange::verify().

◆ isLocalCopy()

static bool isLocalCopy ( MachineInstr Copy,
const LiveIntervals LIS 
)
static

◆ isMoveInstr()

simple register Simple Register static false bool isMoveInstr ( const TargetRegisterInfo tri,
const MachineInstr MI,
unsigned Src,
unsigned Dst,
unsigned SrcSub,
unsigned DstSub 
)
static

◆ isSplitEdge()

static bool isSplitEdge ( const MachineBasicBlock MBB)
static

Return true if this block should be vacated by the coalescer to eliminate branches.

The important cases to handle in the coalescer are critical edges split during phi elimination which contain only copies. Simple blocks that contain non-branches should also be vacated, but this can be handled by an earlier pass similar to early if-conversion.

Definition at line 364 of file RegisterCoalescer.cpp.

References llvm::MachineInstr::isCopyLike(), llvm::MachineInstr::isUnconditionalBranch(), llvm::MachineBasicBlock::pred_size(), and llvm::MachineBasicBlock::succ_size().

Referenced by isTerminalReg().

◆ isTerminalReg()

static bool isTerminalReg ( unsigned  DstReg,
const MachineInstr Copy,
const MachineRegisterInfo MRI 
)
static

Check if DstReg is a terminal node.

I.e., it does not have any affinity other than Copy.

Definition at line 3462 of file RegisterCoalescer.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::array_pod_sort(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::MachineBasicBlock::begin(), llvm::MachineFunction::begin(), llvm::cl::BOU_TRUE, llvm::cl::BOU_UNSET, llvm::SmallPtrSetImplBase::clear(), llvm::SmallVectorImpl< T >::clear(), llvm::LiveInterval::clearSubRanges(), compareMBBPriority(), llvm::dbgs(), llvm::Depth, llvm::dump(), E, llvm::SmallVectorBase::empty(), EnableGlobalCopies, llvm::TargetSubtargetInfo::enableJoinGlobalCopies(), EnableJoining, EnableJoinSplits, llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::MachineBasicBlock::end(), llvm::MachineFunction::end(), llvm::SmallVectorImpl< T >::erase(), llvm::TargetSubtargetInfo::getInstrInfo(), llvm::LiveIntervals::getInterval(), llvm::MachineLoopInfo::getLoopDepth(), llvm::MachineRegisterInfo::getMaxLaneMaskForVReg(), llvm::MachineBasicBlock::getName(), llvm::MachineFunction::getName(), llvm::MachineInstr::getParent(), llvm::MachineRegisterInfo::getRegClass(), llvm::TargetRegisterInfo::getRegClassName(), llvm::MachineFunction::getRegInfo(), llvm::TargetSubtargetInfo::getRegisterInfo(), llvm::MachineFunction::getSubtarget(), llvm::LiveInterval::hasSubRanges(), I, llvm::MachineInstr::isCopyLike(), isLocalCopy(), isMoveInstr(), llvm::TargetRegisterInfo::isPhysicalRegister(), isSplitEdge(), LLVM_DEBUG, llvm::max(), llvm::RISCVFenceField::O, llvm::LiveRange::overlaps(), print(), llvm::LiveIntervals::print(), llvm::printReg(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::MachineRegisterInfo::recomputeRegClass(), llvm::MachineRegisterInfo::reg_nodbg_empty(), llvm::MachineRegisterInfo::reg_nodbg_instructions(), llvm::sys::fs::remove(), llvm::RegisterClassInfo::runOnMachineFunction(), llvm::MachineRegisterInfo::shouldTrackSubRegLiveness(), llvm::SmallVectorBase::size(), llvm::MachineFunction::size(), llvm::LiveInterval::subranges(), UseTerminalRule, llvm::MachineFunction::verify(), and VerifyCoalescing.

◆ STATISTIC() [1/9]

STATISTIC ( numJoins  ,
"Number of interval joins performed"   
)

◆ STATISTIC() [2/9]

STATISTIC ( numCrossRCs  ,
"Number of cross class joins performed"   
)

◆ STATISTIC() [3/9]

STATISTIC ( numCommutes  ,
"Number of instruction commuting performed"   
)

◆ STATISTIC() [4/9]

STATISTIC ( numExtends  ,
"Number of copies extended"   
)

◆ STATISTIC() [5/9]

STATISTIC ( NumReMats  ,
"Number of instructions re-materialized"   
)

◆ STATISTIC() [6/9]

STATISTIC ( NumInflated  ,
"Number of register classes inflated"   
)

◆ STATISTIC() [7/9]

STATISTIC ( NumLaneConflicts  ,
"Number of dead lane conflicts tested"   
)

◆ STATISTIC() [8/9]

STATISTIC ( NumLaneResolves  ,
"Number of dead lane conflicts resolved"   
)

◆ STATISTIC() [9/9]

STATISTIC ( NumShrinkToUses  ,
"Number of shrinkToUses called"   
)

Variable Documentation

◆ coalescing

simple register coalescing

Definition at line 337 of file RegisterCoalescer.cpp.

◆ Coalescing

simple register Simple Register Coalescing

Definition at line 337 of file RegisterCoalescer.cpp.

◆ EnableGlobalCopies

cl::opt<cl::boolOrDefault> EnableGlobalCopies("join-globalcopies", cl::desc("Coalesce copies that span blocks (default=subtarget)"), cl::init(cl::BOU_UNSET), cl::Hidden)
static

Temporary flag to test global copy optimization.

Referenced by isTerminalReg().

◆ EnableJoining

cl::opt<bool> EnableJoining("join-liveintervals", cl::desc("Coalesce copies (default=true)"), cl::init(true), cl::Hidden)
static

Referenced by isTerminalReg().

◆ EnableJoinSplits

cl::opt<bool> EnableJoinSplits("join-splitedges", cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden)
static

Temporary flag to test critical edge unsplitting.

Referenced by isTerminalReg().

◆ false

simple register Simple Register false

Definition at line 337 of file RegisterCoalescer.cpp.

◆ LateRematUpdateThreshold

cl::opt<unsigned> LateRematUpdateThreshold("late-remat-update-threshold", cl::Hidden, cl::desc("During rematerialization for a copy, if the def instruction has " "many other copy uses to be rematerialized, delay the multiple " "separate live interval update work and do them all at once after " "all those rematerialization are done. It will save a lot of " "repeated work. "), cl::init(100))
static

◆ UseTerminalRule

cl::opt<bool> UseTerminalRule("terminal-rule", cl::desc("Apply the terminal rule"), cl::init(false), cl::Hidden)
static

Referenced by isTerminalReg().

◆ VerifyCoalescing

cl::opt<bool> VerifyCoalescing("verify-coalescing", cl::desc("Verify machine instrs before and after register coalescing"), cl::Hidden)
static

Referenced by isTerminalReg().