#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/ScheduleDFS.h"
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void ReadyQueue::dump() {
- dbgs() << " " << Name << ": ";
+ dbgs() << Name << ": ";
for (unsigned i = 0, e = Queue.size(); i < e; ++i)
dbgs() << Queue[i]->NodeNum << " ";
dbgs() << "\n";
const std::vector<unsigned> &RegionPressure =
RPTracker.getPressure().MaxSetPressure;
for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
- unsigned Limit = TRI->getRegPressureSetLimit(i);
- DEBUG(dbgs() << TRI->getRegPressureSetName(i)
- << "Limit " << Limit
- << " Actual " << RegionPressure[i] << "\n");
- if (RegionPressure[i] > Limit)
+ unsigned Limit = RegClassInfo->getRegPressureSetLimit(i);
+ if (RegionPressure[i] > Limit) {
+ DEBUG(dbgs() << TRI->getRegPressureSetName(i)
+ << " Limit " << Limit
+ << " Actual " << RegionPressure[i] << "\n");
RegionCriticalPSets.push_back(PressureElement(i, 0));
+ }
}
DEBUG(dbgs() << "Excess PSets: ";
for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i)
}
DEBUG(
for (unsigned i = 0, e = NewMaxPressure.size(); i < e; ++i) {
- unsigned Limit = TRI->getRegPressureSetLimit(i);
+ unsigned Limit = RegClassInfo->getRegPressureSetLimit(i);
if (NewMaxPressure[i] > Limit ) {
dbgs() << " " << TRI->getRegPressureSetName(i) << ": "
<< NewMaxPressure[i] << " > " << Limit << "\n";
/// Represent the type of SchedCandidate found within a single queue.
/// pickNodeBidirectional depends on these listed by decreasing priority.
enum CandReason {
- NoCand, PhysRegCopy, SingleExcess, SingleCritical, Cluster, Weak,
+ NoCand, PhysRegCopy, RegExcess, RegCritical, Cluster, Weak, RegMax,
ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
- TopDepthReduce, TopPathReduce, SingleMax, MultiPressure, NextDefUse,
- NodeOrder};
+ TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder};
#ifndef NDEBUG
static const char *getReasonStr(ConvergingScheduler::CandReason Reason);
// The reason for this candidate.
CandReason Reason;
+ // Set of reasons that apply to multiple candidates.
+ uint32_t RepeatReasonSet;
+
// Register pressure values for the best candidate.
RegPressureDelta RPDelta;
SchedResourceDelta ResDelta;
SchedCandidate(const CandPolicy &policy)
- : Policy(policy), SU(NULL), Reason(NoCand) {}
+ : Policy(policy), SU(NULL), Reason(NoCand), RepeatReasonSet(0) {}
bool isValid() const { return SU; }
ResDelta = Best.ResDelta;
}
+ bool isRepeat(CandReason R) { return RepeatReasonSet & (1 << R); }
+ void setRepeat(CandReason R) { RepeatReasonSet |= (1 << R); }
+
void initResourceDelta(const ScheduleDAGMI *DAG,
const TargetSchedModel *SchedModel);
};
<< getResourceName(ZoneCritResIdx) << "\n";
}
if (OtherResLimited)
- dbgs() << " RemainingLimit: " << getResourceName(OtherCritIdx);
+ dbgs() << " RemainingLimit: " << getResourceName(OtherCritIdx) << "\n";
if (!IsResourceLimited && !OtherResLimited)
dbgs() << " Latency limited both directions.\n");
}
}
+
/// Return true if this heuristic determines order.
static bool tryLess(int TryVal, int CandVal,
ConvergingScheduler::SchedCandidate &TryCand,
Cand.Reason = Reason;
return true;
}
+ Cand.setRepeat(Reason);
return false;
}
Cand.Reason = Reason;
return true;
}
+ Cand.setRepeat(Reason);
return false;
}
// Avoid exceeding the target's limit.
if (tryLess(TryCand.RPDelta.Excess.UnitIncrease,
- Cand.RPDelta.Excess.UnitIncrease, TryCand, Cand, SingleExcess))
+ Cand.RPDelta.Excess.UnitIncrease, TryCand, Cand, RegExcess))
return;
- if (Cand.Reason == SingleExcess)
- Cand.Reason = MultiPressure;
// Avoid increasing the max critical pressure in the scheduled region.
if (tryLess(TryCand.RPDelta.CriticalMax.UnitIncrease,
Cand.RPDelta.CriticalMax.UnitIncrease,
- TryCand, Cand, SingleCritical))
+ TryCand, Cand, RegCritical))
return;
- if (Cand.Reason == SingleCritical)
- Cand.Reason = MultiPressure;
// Keep clustered nodes together to encourage downstream peephole
// optimizations which may reduce resource requirements.
return;
// Weak edges are for clustering and other constraints.
- //
- // Deferring TryCand here does not change Cand's reason. This is good in the
- // sense that a bad candidate shouldn't affect a previous candidate's
- // goodness, but bad in that it is assymetric and depends on queue order.
- CandReason OrigReason = Cand.Reason;
if (tryLess(getWeakLeft(TryCand.SU, Zone.isTop()),
getWeakLeft(Cand.SU, Zone.isTop()),
TryCand, Cand, Weak)) {
- Cand.Reason = OrigReason;
return;
}
+ // Avoid increasing the max pressure of the entire region.
+ if (tryLess(TryCand.RPDelta.CurrentMax.UnitIncrease,
+ Cand.RPDelta.CurrentMax.UnitIncrease, TryCand, Cand, RegMax))
+ return;
+
// Avoid critical resource consumption and balance the schedule.
TryCand.initResourceDelta(DAG, SchedModel);
if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
}
}
- // Avoid increasing the max pressure of the entire region.
- if (tryLess(TryCand.RPDelta.CurrentMax.UnitIncrease,
- Cand.RPDelta.CurrentMax.UnitIncrease, TryCand, Cand, SingleMax))
- return;
- if (Cand.Reason == SingleMax)
- Cand.Reason = MultiPressure;
-
// Prefer immediate defs/users of the last scheduled instruction. This is a
// local pressure avoidance strategy that also makes the machine code
// readable.
}
}
-/// pickNodeFromQueue helper that returns true if the LHS reg pressure effect is
-/// more desirable than RHS from scheduling standpoint.
-static bool compareRPDelta(const RegPressureDelta &LHS,
- const RegPressureDelta &RHS) {
- // Compare each component of pressure in decreasing order of importance
- // without checking if any are valid. Invalid PressureElements are assumed to
- // have UnitIncrease==0, so are neutral.
-
- // Avoid increasing the max critical pressure in the scheduled region.
- if (LHS.Excess.UnitIncrease != RHS.Excess.UnitIncrease) {
- DEBUG(dbgs() << " RP excess top - bot: "
- << (LHS.Excess.UnitIncrease - RHS.Excess.UnitIncrease) << '\n');
- return LHS.Excess.UnitIncrease < RHS.Excess.UnitIncrease;
- }
- // Avoid increasing the max critical pressure in the scheduled region.
- if (LHS.CriticalMax.UnitIncrease != RHS.CriticalMax.UnitIncrease) {
- DEBUG(dbgs() << " RP critical top - bot: "
- << (LHS.CriticalMax.UnitIncrease - RHS.CriticalMax.UnitIncrease)
- << '\n');
- return LHS.CriticalMax.UnitIncrease < RHS.CriticalMax.UnitIncrease;
- }
- // Avoid increasing the max pressure of the entire region.
- if (LHS.CurrentMax.UnitIncrease != RHS.CurrentMax.UnitIncrease) {
- DEBUG(dbgs() << " RP current top - bot: "
- << (LHS.CurrentMax.UnitIncrease - RHS.CurrentMax.UnitIncrease)
- << '\n');
- return LHS.CurrentMax.UnitIncrease < RHS.CurrentMax.UnitIncrease;
- }
- return false;
-}
-
#ifndef NDEBUG
const char *ConvergingScheduler::getReasonStr(
ConvergingScheduler::CandReason Reason) {
switch (Reason) {
case NoCand: return "NOCAND ";
case PhysRegCopy: return "PREG-COPY";
- case SingleExcess: return "REG-EXCESS";
- case SingleCritical: return "REG-CRIT ";
+ case RegExcess: return "REG-EXCESS";
+ case RegCritical: return "REG-CRIT ";
case Cluster: return "CLUSTER ";
case Weak: return "WEAK ";
- case SingleMax: return "REG-MAX ";
- case MultiPressure: return "REG-MULTI ";
+ case RegMax: return "REG-MAX ";
case ResourceReduce: return "RES-REDUCE";
case ResourceDemand: return "RES-DEMAND";
case TopDepthReduce: return "TOP-DEPTH ";
switch (Cand.Reason) {
default:
break;
- case SingleExcess:
+ case RegExcess:
P = Cand.RPDelta.Excess;
break;
- case SingleCritical:
+ case RegCritical:
P = Cand.RPDelta.CriticalMax;
break;
- case SingleMax:
+ case RegMax:
P = Cand.RPDelta.CurrentMax;
break;
case ResourceReduce:
// affects picking from either Q. If scheduling in one direction must
// increase pressure for one of the excess PSets, then schedule in that
// direction first to provide more freedom in the other direction.
- if (BotCand.Reason == SingleExcess || BotCand.Reason == SingleCritical) {
+ if ((BotCand.Reason == RegExcess && !BotCand.isRepeat(RegExcess))
+ || (BotCand.Reason == RegCritical
+ && !BotCand.isRepeat(RegCritical)))
+ {
IsTopNode = false;
tracePick(BotCand, IsTopNode);
return BotCand.SU;
pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
assert(TopCand.Reason != NoCand && "failed to find the first candidate");
- // If either Q has a single candidate that minimizes pressure above the
- // original region's pressure pick it.
- if (TopCand.Reason <= SingleMax || BotCand.Reason <= SingleMax) {
- if (TopCand.Reason < BotCand.Reason) {
- IsTopNode = true;
- tracePick(TopCand, IsTopNode);
- return TopCand.SU;
- }
- IsTopNode = false;
- tracePick(BotCand, IsTopNode);
- return BotCand.SU;
- }
- // Check for a salient pressure difference and pick the best from either side.
- if (compareRPDelta(TopCand.RPDelta, BotCand.RPDelta)) {
- IsTopNode = true;
- tracePick(TopCand, IsTopNode);
- return TopCand.SU;
- }
- // Otherwise prefer the bottom candidate, in node order if all else failed.
+ // Choose the queue with the most important (lowest enum) reason.
if (TopCand.Reason < BotCand.Reason) {
IsTopNode = true;
tracePick(TopCand, IsTopNode);
return TopCand.SU;
}
+ // Otherwise prefer the bottom candidate, in node order if all else failed.
IsTopNode = false;
tracePick(BotCand, IsTopNode);
return BotCand.SU;