- ScheduleDAGInstrs::FinishBlock();
-}
-
-/// CriticalPathStep - Return the next SUnit after SU on the bottom-up
-/// critical path.
-static SDep *CriticalPathStep(SUnit *SU) {
- SDep *Next = 0;
- unsigned NextDepth = 0;
- // Find the predecessor edge with the greatest depth.
- for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
- P != PE; ++P) {
- SUnit *PredSU = P->getSUnit();
- unsigned PredLatency = P->getLatency();
- unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;
- // In the case of a latency tie, prefer an anti-dependency edge over
- // other types of edges.
- if (NextDepth < PredTotalLatency ||
- (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) {
- NextDepth = PredTotalLatency;
- Next = &*P;
- }
- }
- return Next;
-}
-
-/// AntiDepPathStep - Return SUnit that SU has an anti-dependence on.
-static SDep *AntiDepPathStep(SUnit *SU) {
- for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
- P != PE; ++P) {
- if (P->getKind() == SDep::Anti) {
- return &*P;
- }
- }
- return 0;
-}
-
-void SchedulePostRATDList::PrescanInstruction(MachineInstr *MI, unsigned Count) {
- // Scan the register defs for this instruction and update
- // live-ranges, groups and RegRefs.
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg() || !MO.isDef()) continue;
- unsigned Reg = MO.getReg();
- if (Reg == 0) continue;
- // Ignore two-addr defs for liveness...
- if (MI->isRegTiedToUseOperand(i)) continue;
-
- // Update Def for Reg and subregs.
- DefIndices[Reg] = Count;
- for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
- *Subreg; ++Subreg) {
- unsigned SubregReg = *Subreg;
- DefIndices[SubregReg] = Count;
- }
- }
-
- DEBUG(errs() << "\tDef Groups:");
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg() || !MO.isDef()) continue;
- unsigned Reg = MO.getReg();
- if (Reg == 0) continue;
-
- DEBUG(errs() << " " << TRI->getName(Reg) << "=g" << GetGroup(Reg));
-
- // If MI's defs have special allocation requirement, don't allow
- // any def registers to be changed. Also assume all registers
- // defined in a call must not be changed (ABI).
- if (MI->getDesc().isCall() || MI->getDesc().hasExtraDefRegAllocReq()) {
- DEBUG(if (GetGroup(Reg) != 0) errs() << "->g0(alloc-req)");
- UnionGroups(Reg, 0);
- }
-
- // Any subregisters that are live at this point are defined here,
- // so group those subregisters with Reg.
- for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
- *Subreg; ++Subreg) {
- unsigned SubregReg = *Subreg;
- if (IsLive(SubregReg)) {
- UnionGroups(Reg, SubregReg);
- DEBUG(errs() << "->g" << GetGroup(Reg) << "(via " <<
- TRI->getName(SubregReg) << ")");
- }
- }
-
- // Note register reference...
- const TargetRegisterClass *RC = NULL;
- if (i < MI->getDesc().getNumOperands())
- RC = MI->getDesc().OpInfo[i].getRegClass(TRI);
- RegisterReference RR = { &MO, RC };
- RegRefs.insert(std::make_pair(Reg, RR));
- }
-
- DEBUG(errs() << '\n');
-}
-
-void SchedulePostRATDList::ScanInstruction(MachineInstr *MI,
- unsigned Count) {
- DEBUG(errs() << "\tUse Groups:");
-
- // Scan the register uses for this instruction and update
- // live-ranges, groups and RegRefs.
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg() || !MO.isUse()) continue;
- unsigned Reg = MO.getReg();
- if (Reg == 0) continue;
-
- DEBUG(errs() << " " << TRI->getName(Reg) << "=g" << GetGroup(Reg));
-
- // It wasn't previously live but now it is, this is a kill. Forget
- // the previous live-range information and start a new live-range
- // for the register.
- if (!IsLive(Reg)) {
- KillIndices[Reg] = Count;
- DefIndices[Reg] = ~0u;
- RegRefs.erase(Reg);
- LeaveGroup(Reg);
- DEBUG(errs() << "->g" << GetGroup(Reg) << "(last-use)");
- }
- // Repeat, for subregisters.
- for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
- *Subreg; ++Subreg) {
- unsigned SubregReg = *Subreg;
- if (!IsLive(SubregReg)) {
- KillIndices[SubregReg] = Count;
- DefIndices[SubregReg] = ~0u;
- RegRefs.erase(SubregReg);
- LeaveGroup(SubregReg);
- DEBUG(errs() << "->g" << GetGroup(SubregReg) << "(last-use)");
- }
- }
-
- // If MI's uses have special allocation requirement, don't allow
- // any use registers to be changed. Also assume all registers
- // used in a call must not be changed (ABI).
- if (MI->getDesc().isCall() || MI->getDesc().hasExtraSrcRegAllocReq()) {
- DEBUG(if (GetGroup(Reg) != 0) errs() << "->g0(alloc-req)");
- UnionGroups(Reg, 0);
- }
-
- // Note register reference...
- const TargetRegisterClass *RC = NULL;
- if (i < MI->getDesc().getNumOperands())
- RC = MI->getDesc().OpInfo[i].getRegClass(TRI);
- RegisterReference RR = { &MO, RC };
- RegRefs.insert(std::make_pair(Reg, RR));
- }
-
- DEBUG(errs() << '\n');
-
- // Form a group of all defs and uses of a KILL instruction to ensure
- // that all registers are renamed as a group.
- if (MI->getOpcode() == TargetInstrInfo::KILL) {
- unsigned FirstReg = 0;
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg()) continue;
- unsigned Reg = MO.getReg();
- if (Reg == 0) continue;
-
- if (FirstReg != 0)
- UnionGroups(FirstReg, Reg);
- FirstReg = Reg;
- }
-
- DEBUG(if (FirstReg != 0) errs() << "\tKill Group: g" <<
- GetGroup(FirstReg) << '\n');
- }
-}
-
-unsigned SchedulePostRATDList::FindSuitableFreeRegister(unsigned AntiDepReg) {
- // Collect all registers in the same group as AntiDepReg. These all
- // need to be renamed together if we are to break the
- // anti-dependence.
- std::vector<unsigned> Regs;
- GetGroupRegs(GetGroup(AntiDepReg), Regs);
-
- DEBUG(errs() << "\tRename Register Group:");
- DEBUG(for (unsigned i = 0, e = Regs.size(); i != e; ++i)
- DEBUG(errs() << " " << TRI->getName(Regs[i])));
- DEBUG(errs() << "\n");
-
- // If there is a single register that needs to be renamed then we
- // can do it ourselves.
- if (Regs.size() == 1) {
- assert(Regs[0] == AntiDepReg && "Register group does not contain register!");
-
- // Check all references that need rewriting. Gather up all the
- // register classes for the register references.
- const TargetRegisterClass *FirstRC = NULL;
- std::set<const TargetRegisterClass *> RCs;
- std::pair<std::multimap<unsigned, RegisterReference>::iterator,
- std::multimap<unsigned, RegisterReference>::iterator>
- Range = RegRefs.equal_range(AntiDepReg);
- for (std::multimap<unsigned, RegisterReference>::iterator
- Q = Range.first, QE = Range.second; Q != QE; ++Q) {
- const TargetRegisterClass *RC = Q->second.RC;
- if (RC == NULL) continue;
- if (FirstRC == NULL)
- FirstRC = RC;
- else if (FirstRC != RC)
- RCs.insert(RC);
- }
-
- if (FirstRC == NULL)
- return 0;
-
- DEBUG(errs() << "\tChecking Regclasses: " << FirstRC->getName());
- DEBUG(for (std::set<const TargetRegisterClass *>::iterator S =
- RCs.begin(), E = RCs.end(); S != E; ++S)
- errs() << " " << (*S)->getName());
- DEBUG(errs() << '\n');
-
- // Using the allocation order for one of the register classes,
- // find the first register that belongs to all the register
- // classes that is available over the liverange of the register.
- DEBUG(errs() << "\tFind Register:");
- for (TargetRegisterClass::iterator R = FirstRC->allocation_order_begin(MF),
- RE = FirstRC->allocation_order_end(MF); R != RE; ++R) {
- unsigned NewReg = *R;
-
- // Don't replace a register with itself.
- if (NewReg == AntiDepReg) continue;
-
- DEBUG(errs() << " " << TRI->getName(NewReg));
-
- // Make sure NewReg is in all required register classes.
- for (std::set<const TargetRegisterClass *>::iterator S =
- RCs.begin(), E = RCs.end(); S != E; ++S) {
- const TargetRegisterClass *RC = *S;
- if (!RC->contains(NewReg)) {
- DEBUG(errs() << "(not in " << RC->getName() << ")");
- NewReg = 0;
- break;
- }
- }
-
- // If NewReg is dead and NewReg's most recent def is not before
- // AntiDepReg's kill, it's safe to replace AntiDepReg with
- // NewReg. We must also check all subregisters of NewReg.
- if (IsLive(NewReg) || (KillIndices[AntiDepReg] > DefIndices[NewReg])) {
- DEBUG(errs() << "(live)");
- continue;
- }
- {
- bool found = false;
- for (const unsigned *Subreg = TRI->getSubRegisters(NewReg);
- *Subreg; ++Subreg) {
- unsigned SubregReg = *Subreg;
- if (IsLive(SubregReg) || (KillIndices[AntiDepReg] > DefIndices[SubregReg])) {
- DEBUG(errs() << "(subreg " << TRI->getName(SubregReg) << " live)");
- found = true;
- }
- }
- if (found)
- continue;
- }
-
- if (NewReg != 0) {
- DEBUG(errs() << '\n');
- return NewReg;
- }
- }
-
- DEBUG(errs() << '\n');
- }
-
- // No registers are free and available!
- return 0;
-}
-
-/// BreakAntiDependencies - Identifiy anti-dependencies along the critical path
-/// of the ScheduleDAG and break them by renaming registers.
-///
-bool SchedulePostRATDList::BreakAntiDependencies(bool CriticalPathOnly) {
- // The code below assumes that there is at least one instruction,
- // so just duck out immediately if the block is empty.
- if (SUnits.empty()) return false;
-
- // If breaking anti-dependencies only along the critical path, track
- // progress along the critical path through the SUnit graph as we
- // walk the instructions.
- SUnit *CriticalPathSU = 0;
- MachineInstr *CriticalPathMI = 0;
-
- // If breaking all anti-dependencies need a map from MI to SUnit.
- std::map<MachineInstr *, SUnit *> MISUnitMap;
-
- // Find the node at the bottom of the critical path.
- if (CriticalPathOnly) {
- SUnit *Max = 0;
- for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
- SUnit *SU = &SUnits[i];
- if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency)
- Max = SU;
- }
-
- DEBUG(errs() << "Critical path has total latency "
- << (Max->getDepth() + Max->Latency) << "\n");
- CriticalPathSU = Max;
- CriticalPathMI = CriticalPathSU->getInstr();
- } else {
- for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
- SUnit *SU = &SUnits[i];
- MISUnitMap.insert(std::pair<MachineInstr *, SUnit *>(SU->getInstr(), SU));
- }
- DEBUG(errs() << "Breaking all anti-dependencies\n");
- }
-
-#ifndef NDEBUG
- {
- DEBUG(errs() << "Available regs:");
- for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
- if (!IsLive(Reg))
- DEBUG(errs() << " " << TRI->getName(Reg));
- }
- DEBUG(errs() << '\n');
- }
- std::string dbgStr;
-#endif
-
- // Attempt to break anti-dependence edges. Walk the instructions
- // from the bottom up, tracking information about liveness as we go
- // to help determine which registers are available.
- bool Changed = false;
- unsigned Count = InsertPosIndex - 1;
- for (MachineBasicBlock::iterator I = InsertPos, E = Begin;
- I != E; --Count) {
- MachineInstr *MI = --I;
-
- DEBUG(errs() << "Anti: ");
- DEBUG(MI->dump());
-
- // Process the defs in MI...
- PrescanInstruction(MI, Count);
-
- // Check if this instruction has an anti-dependence that we may be
- // able to break. If it is, set AntiDepReg to the non-zero
- // register associated with the anti-dependence.
- //
- unsigned AntiDepReg = 0;
-
- // Limiting our attention to the critical path is a heuristic to avoid
- // breaking anti-dependence edges that aren't going to significantly
- // impact the overall schedule. There are a limited number of registers
- // and we want to save them for the important edges.
- //
- // We can also break all anti-dependencies because they can
- // occur along the non-critical path but are still detrimental for
- // scheduling.
- //
- // TODO: Instructions with multiple defs could have multiple
- // anti-dependencies. The current code here only knows how to break one
- // edge per instruction. Note that we'd have to be able to break all of
- // the anti-dependencies in an instruction in order to be effective.
- if (!CriticalPathOnly || (MI == CriticalPathMI)) {
- DEBUG(dbgStr.clear());
-
- SUnit *PathSU;
- SDep *Edge;
- if (CriticalPathOnly) {
- PathSU = CriticalPathSU;
- Edge = CriticalPathStep(PathSU);
- } else {
- PathSU = MISUnitMap[MI];
- Edge = (PathSU) ? AntiDepPathStep(PathSU) : 0;
- }
-
- if (Edge) {
- SUnit *NextSU = Edge->getSUnit();
-
- // Only consider anti-dependence edges, and ignore KILL
- // instructions (they form a group in ScanInstruction but
- // don't cause any anti-dependence breaking themselves)
- if ((Edge->getKind() == SDep::Anti) &&
- (MI->getOpcode() != TargetInstrInfo::KILL)) {
- AntiDepReg = Edge->getReg();
- DEBUG(dbgStr += "\tAntidep reg: ");
- DEBUG(dbgStr += TRI->getName(AntiDepReg));
- assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
- if (!AllocatableSet.test(AntiDepReg)) {
- // Don't break anti-dependencies on non-allocatable registers.
- DEBUG(dbgStr += " (non-allocatable)");
- AntiDepReg = 0;
- } else {
- int OpIdx = MI->findRegisterDefOperandIdx(AntiDepReg);
- assert(OpIdx != -1 && "Can't find index for defined register operand");
- if (MI->isRegTiedToUseOperand(OpIdx)) {
- // If the anti-dep register is tied to a use, then don't try to
- // change it. It will be changed along with the use if required
- // to break an earlier antidep.
- DEBUG(dbgStr += " (tied-to-use)");
- AntiDepReg = 0;
- } else {
- // If the SUnit has other dependencies on the SUnit that
- // it anti-depends on, don't bother breaking the
- // anti-dependency since those edges would prevent such
- // units from being scheduled past each other
- // regardless.
- //
- // Also, if there are dependencies on other SUnits with
- // the same register as the anti-dependency, don't
- // attempt to break it.
- for (SUnit::pred_iterator P = PathSU->Preds.begin(),
- PE = PathSU->Preds.end(); P != PE; ++P) {
- if (P->getSUnit() == NextSU ?
- (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
- (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) {
- DEBUG(dbgStr += " (real dependency)");
- AntiDepReg = 0;
- break;
- }
- }
- }
- }
- }
-
- if (CriticalPathOnly) {
- CriticalPathSU = NextSU;
- CriticalPathMI = CriticalPathSU->getInstr();
- }
- } else {
- // We've reached the end of the critical path.
- CriticalPathSU = 0;
- CriticalPathMI = 0;
- }
- }
-
- // Determine AntiDepReg's register group.
- const unsigned GroupIndex = AntiDepReg != 0 ? GetGroup(AntiDepReg) : 0;
- if (GroupIndex == 0) {
- DEBUG(if (AntiDepReg != 0) dbgStr += " (zero group)");
- AntiDepReg = 0;
- }
-
- DEBUG(if (!dbgStr.empty()) errs() << dbgStr << '\n');
-
- // Look for a suitable register to use to break the anti-dependence.
- if (AntiDepReg != 0) {
- if (unsigned NewReg = FindSuitableFreeRegister(AntiDepReg)) {
- DEBUG(errs() << "\tBreaking anti-dependence edge on "
- << TRI->getName(AntiDepReg)
- << " with " << RegRefs.count(AntiDepReg) << " references"
- << " using " << TRI->getName(NewReg) << "!\n");
-
- // Update the references to the old register to refer to the new
- // register.
- std::pair<std::multimap<unsigned, RegisterReference>::iterator,
- std::multimap<unsigned, RegisterReference>::iterator>
- Range = RegRefs.equal_range(AntiDepReg);
- for (std::multimap<unsigned, RegisterReference>::iterator
- Q = Range.first, QE = Range.second; Q != QE; ++Q)
- Q->second.Operand->setReg(NewReg);
-
- // We just went back in time and modified history; the
- // liveness information for the anti-dependence reg is now
- // inconsistent. Set the state as if it were dead.
- // FIXME forall in group
- UnionGroups(NewReg, 0);
- RegRefs.erase(NewReg);
- DefIndices[NewReg] = DefIndices[AntiDepReg];
- KillIndices[NewReg] = KillIndices[AntiDepReg];
-
- // FIXME forall in group
- UnionGroups(AntiDepReg, 0);
- RegRefs.erase(AntiDepReg);
- DefIndices[AntiDepReg] = KillIndices[AntiDepReg];
- KillIndices[AntiDepReg] = ~0u;
- assert(((KillIndices[AntiDepReg] == ~0u) !=
- (DefIndices[AntiDepReg] == ~0u)) &&
- "Kill and Def maps aren't consistent for AntiDepReg!");
-
- Changed = true;
- ++NumFixedAnti;
- }
- }
-
- ScanInstruction(MI, Count);
- }
-
- return Changed;
projects / oota-llvm.git / blobdiff