Differential D41585 Diff 132149 llvm/trunk/lib/CodeGen/RegAllocGreedy.cpp

Changeset View

Standalone View

llvm/trunk/lib/CodeGen/RegAllocGreedy.cpp

Show First 20 Lines • Show All 442 Lines • ▼ Show 20 Lines	private:

BlockFrequency calcSpillCost();		BlockFrequency calcSpillCost();
bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&);		bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&);
void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);		void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
void growRegion(GlobalSplitCandidate &Cand);		void growRegion(GlobalSplitCandidate &Cand);
bool splitCanCauseEvictionChain(unsigned Evictee, GlobalSplitCandidate &Cand,		bool splitCanCauseEvictionChain(unsigned Evictee, GlobalSplitCandidate &Cand,
unsigned BBNumber,		unsigned BBNumber,
const AllocationOrder &Order);		const AllocationOrder &Order);
		bool splitCanCauseLocalSpill(unsigned VirtRegToSplit,
		GlobalSplitCandidate &Cand, unsigned BBNumber,
		const AllocationOrder &Order);
BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,		BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,
const AllocationOrder &Order,		const AllocationOrder &Order,
bool *CanCauseEvictionChain);		bool *CanCauseEvictionChain);
bool calcCompactRegion(GlobalSplitCandidate&);		bool calcCompactRegion(GlobalSplitCandidate&);
void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>);		void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>);
void calcGapWeights(unsigned, SmallVectorImpl<float>&);		void calcGapWeights(unsigned, SmallVectorImpl<float>&);
unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg);		unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg);
bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);		bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
▲ Show 20 Lines • Show All 963 Lines • ▼ Show 20 Lines
/// physreg1.		/// physreg1.
/// One of the split intervals ends up evicting %3 from physreg2, etc.		/// One of the split intervals ends up evicting %3 from physreg2, etc.
///		///
/// \param Evictee The register considered to be split.		/// \param Evictee The register considered to be split.
/// \param Cand The split candidate that determines the physical register		/// \param Cand The split candidate that determines the physical register
/// we are splitting for and the interferences.		/// we are splitting for and the interferences.
/// \param BBNumber The number of a BB for which the region split process will		/// \param BBNumber The number of a BB for which the region split process will
/// create a local split interval.		/// create a local split interval.
/// \param Order The phisical registers that may get evicted by a split		/// \param Order The physical registers that may get evicted by a split
/// artifact of Evictee.		/// artifact of Evictee.
/// \return True if splitting Evictee may cause a bad eviction chain, false		/// \return True if splitting Evictee may cause a bad eviction chain, false
/// otherwise.		/// otherwise.
bool RAGreedy::splitCanCauseEvictionChain(unsigned Evictee,		bool RAGreedy::splitCanCauseEvictionChain(unsigned Evictee,
GlobalSplitCandidate &Cand,		GlobalSplitCandidate &Cand,
unsigned BBNumber,		unsigned BBNumber,
const AllocationOrder &Order) {		const AllocationOrder &Order) {
EvictionTrack::EvictorInfo VregEvictorInfo = LastEvicted.getEvictor(Evictee);		EvictionTrack::EvictorInfo VregEvictorInfo = LastEvicted.getEvictor(Evictee);
unsigned Evictor = VregEvictorInfo.first;		unsigned Evictor = VregEvictorInfo.first;
unsigned PhysReg = VregEvictorInfo.second;		unsigned PhysReg = VregEvictorInfo.second;

// No actual evictor.		// No actual evictor.
if (!Evictor \|\| !PhysReg)		if (!Evictor \|\| !PhysReg)
return false;		return false;

float MaxWeight = 0;		float MaxWeight = 0;
unsigned FutureEvictedPhysReg =		unsigned FutureEvictedPhysReg =
getCheapestEvicteeWeight(Order, LIS->getInterval(Evictee),		getCheapestEvicteeWeight(Order, LIS->getInterval(Evictee),
Cand.Intf.first(), Cand.Intf.last(), &MaxWeight);		Cand.Intf.first(), Cand.Intf.last(), &MaxWeight);

// The bad eviction chain occurs when either the split candidate the		// The bad eviction chain occurs when either the split candidate is the
// evited reg or one of the split artifact will evict the evicting reg.		// evicting reg or one of the split artifact will evict the evicting reg.
if ((PhysReg != Cand.PhysReg) && (PhysReg != FutureEvictedPhysReg))		if ((PhysReg != Cand.PhysReg) && (PhysReg != FutureEvictedPhysReg))
return false;		return false;

Cand.Intf.moveToBlock(BBNumber);		Cand.Intf.moveToBlock(BBNumber);

// Check to see if the Evictor contains interference (with Evictee) in the		// Check to see if the Evictor contains interference (with Evictee) in the
// given BB. If so, this interference caused the eviction of Evictee from		// given BB. If so, this interference caused the eviction of Evictee from
// PhysReg. This suggest that we will create a local interval during the		// PhysReg. This suggest that we will create a local interval during the
Show All 13 Lines	float splitArtifactWeight =
VRAI.futureWeight(LIS->getInterval(Evictee),		VRAI.futureWeight(LIS->getInterval(Evictee),
Cand.Intf.first().getPrevIndex(), Cand.Intf.last());		Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
if (splitArtifactWeight >= 0 && splitArtifactWeight < MaxWeight)		if (splitArtifactWeight >= 0 && splitArtifactWeight < MaxWeight)
return false;		return false;

return true;		return true;
}		}

		/// \brief Check if splitting VirtRegToSplit will create a local split interval
		/// in basic block number BBNumber that may cause a spill.
		///
		/// \param VirtRegToSplit The register considered to be split.
		/// \param Cand The split candidate that determines the physical
		/// register we are splitting for and the interferences.
		/// \param BBNumber The number of a BB for which the region split process
		/// will create a local split interval.
		/// \param Order The physical registers that may get evicted by a
		/// split artifact of VirtRegToSplit.
		/// \return True if splitting VirtRegToSplit may cause a spill, false
		/// otherwise.
		bool RAGreedy::splitCanCauseLocalSpill(unsigned VirtRegToSplit,
		GlobalSplitCandidate &Cand,
		unsigned BBNumber,
		const AllocationOrder &Order) {
		Cand.Intf.moveToBlock(BBNumber);

		// Check if the local interval will find a non interfereing assignment.
		for (auto PhysReg : Order.getOrder()) {
		if (!Matrix->checkInterference(Cand.Intf.first().getPrevIndex(),
		Cand.Intf.last(), PhysReg))
		return false;
		}

		// Check if the local interval will evict a cheaper interval.
		float CheapestEvictWeight = 0;
		unsigned FutureEvictedPhysReg = getCheapestEvicteeWeight(
		Order, LIS->getInterval(VirtRegToSplit), Cand.Intf.first(),
		Cand.Intf.last(), &CheapestEvictWeight);

		// Have we found an interval that can be evicted?
		if (FutureEvictedPhysReg) {
		VirtRegAuxInfo VRAI(MF, LIS, VRM, getAnalysis<MachineLoopInfo>(), *MBFI);
		float splitArtifactWeight =
		VRAI.futureWeight(LIS->getInterval(VirtRegToSplit),
		Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
		// Will the weight of the local interval be higher than the cheapest evictee
		// weight? If so it will evict it and will not cause a spill.
		if (splitArtifactWeight >= 0 && splitArtifactWeight > CheapestEvictWeight)
		return false;
		}

		// The local interval is not able to find non interferening assignment and not
		// able to evict a less worthy interval, therfore, it can cause a spill.
		return true;
		}

/// calcGlobalSplitCost - Return the global split cost of following the split		/// calcGlobalSplitCost - Return the global split cost of following the split
/// pattern in LiveBundles. This cost should be added to the local cost of the		/// pattern in LiveBundles. This cost should be added to the local cost of the
/// interference pattern in SplitConstraints.		/// interference pattern in SplitConstraints.
///		///
BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,		BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
const AllocationOrder &Order,		const AllocationOrder &Order,
bool *CanCauseEvictionChain) {		bool *CanCauseEvictionChain) {
BlockFrequency GlobalCost = 0;		BlockFrequency GlobalCost = 0;
const BitVector &LiveBundles = Cand.LiveBundles;		const BitVector &LiveBundles = Cand.LiveBundles;
unsigned VirtRegToSplit = SA->getParent().reg;		unsigned VirtRegToSplit = SA->getParent().reg;
ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();		ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
for (unsigned i = 0; i != UseBlocks.size(); ++i) {		for (unsigned i = 0; i != UseBlocks.size(); ++i) {
const SplitAnalysis::BlockInfo &BI = UseBlocks[i];		const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
SpillPlacement::BlockConstraint &BC = SplitConstraints[i];		SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, false)];		bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, false)];
bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)];		bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)];
unsigned Ins = 0;		unsigned Ins = 0;

Cand.Intf.moveToBlock(BC.Number);		Cand.Intf.moveToBlock(BC.Number);
// Check wheather a local interval is going to be created during the region		// Check wheather a local interval is going to be created during the region
// split.		// split. Calculate adavanced spilt cost (cost of local intervals) if option
if (EnableAdvancedRASplitCost && CanCauseEvictionChain &&		// is enabled.
Cand.Intf.hasInterference() && BI.LiveIn && BI.LiveOut && RegIn &&		if (EnableAdvancedRASplitCost && Cand.Intf.hasInterference() && BI.LiveIn &&
RegOut) {		BI.LiveOut && RegIn && RegOut) {

if (splitCanCauseEvictionChain(VirtRegToSplit, Cand, BC.Number, Order)) {		if (CanCauseEvictionChain &&
// This interfernce cause our eviction from this assignment, we might		splitCanCauseEvictionChain(VirtRegToSplit, Cand, BC.Number, Order)) {
// evict somebody else, add that cost.		// This interference causes our eviction from this assignment, we might
		// evict somebody else and eventually someone will spill, add that cost.
// See splitCanCauseEvictionChain for detailed description of scenarios.		// See splitCanCauseEvictionChain for detailed description of scenarios.
GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);		GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);		GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);

*CanCauseEvictionChain = true;		*CanCauseEvictionChain = true;

		} else if (splitCanCauseLocalSpill(VirtRegToSplit, Cand, BC.Number,
		Order)) {
		// This interference causes local interval to spill, add that cost.
		GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
		GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
}		}
}		}

if (BI.LiveIn)		if (BI.LiveIn)
Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);		Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
if (BI.LiveOut)		if (BI.LiveOut)
Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);		Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
while (Ins--)		while (Ins--)
Show All 12 Lines	if (RegIn && RegOut) {
if (Cand.Intf.hasInterference()) {		if (Cand.Intf.hasInterference()) {
GlobalCost += SpillPlacer->getBlockFrequency(Number);		GlobalCost += SpillPlacer->getBlockFrequency(Number);
GlobalCost += SpillPlacer->getBlockFrequency(Number);		GlobalCost += SpillPlacer->getBlockFrequency(Number);

// Check wheather a local interval is going to be created during the		// Check wheather a local interval is going to be created during the
// region split.		// region split.
if (EnableAdvancedRASplitCost && CanCauseEvictionChain &&		if (EnableAdvancedRASplitCost && CanCauseEvictionChain &&
splitCanCauseEvictionChain(VirtRegToSplit, Cand, Number, Order)) {		splitCanCauseEvictionChain(VirtRegToSplit, Cand, Number, Order)) {
// This interfernce cause our eviction from this assignment, we might		// This interference cause our eviction from this assignment, we might
// evict somebody else, add that cost.		// evict somebody else, add that cost.
// See splitCanCauseEvictionChain for detailed description of		// See splitCanCauseEvictionChain for detailed description of
// scenarios.		// scenarios.
GlobalCost += SpillPlacer->getBlockFrequency(Number);		GlobalCost += SpillPlacer->getBlockFrequency(Number);
GlobalCost += SpillPlacer->getBlockFrequency(Number);		GlobalCost += SpillPlacer->getBlockFrequency(Number);

*CanCauseEvictionChain = true;		*CanCauseEvictionChain = true;
}		}
▲ Show 20 Lines • Show All 1,577 Lines • Show Last 20 Lines