- DEBUG(errs() << "Critical path has total latency "
- << (Max->getDepth() + Max->Latency) << "\n");
-
- // Track progress along the critical path through the SUnit graph as we walk
- // the instructions.
- SUnit *CriticalPathSU = Max;
- MachineInstr *CriticalPathMI = CriticalPathSU->getInstr();
-
- // Consider this pattern:
- // A = ...
- // ... = A
- // A = ...
- // ... = A
- // A = ...
- // ... = A
- // A = ...
- // ... = A
- // There are three anti-dependencies here, and without special care,
- // we'd break all of them using the same register:
- // A = ...
- // ... = A
- // B = ...
- // ... = B
- // B = ...
- // ... = B
- // B = ...
- // ... = B
- // because at each anti-dependence, B is the first register that
- // isn't A which is free. This re-introduces anti-dependencies
- // at all but one of the original anti-dependencies that we were
- // trying to break. To avoid this, keep track of the most recent
- // register that each register was replaced with, avoid
- // using it to repair an anti-dependence on the same register.
- // This lets us produce this:
- // A = ...
- // ... = A
- // B = ...
- // ... = B
- // C = ...
- // ... = C
- // B = ...
- // ... = B
- // This still has an anti-dependence on B, but at least it isn't on the
- // original critical path.
- //
- // TODO: If we tracked more than one register here, we could potentially
- // fix that remaining critical edge too. This is a little more involved,
- // because unlike the most recent register, less recent registers should
- // still be considered, though only if no other registers are available.
- unsigned LastNewReg[TargetRegisterInfo::FirstVirtualRegister] = {};
-
- // Attempt to break anti-dependence edges on the critical path. 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;
-
- // After regalloc, IMPLICIT_DEF instructions aren't safe to treat as
- // dependence-breaking. In the case of an INSERT_SUBREG, the IMPLICIT_DEF
- // is left behind appearing to clobber the super-register, while the
- // subregister needs to remain live. So we just ignore them.
- if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
- continue;
-
- // Check if this instruction has a dependence on the critical path that
- // is 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.
- //
- // We limit our attention to the critical path as 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.
- //
- // 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.
- unsigned AntiDepReg = 0;
- if (MI == CriticalPathMI) {
- if (SDep *Edge = CriticalPathStep(CriticalPathSU)) {
- SUnit *NextSU = Edge->getSUnit();
-
- // Only consider anti-dependence edges.
- if (Edge->getKind() == SDep::Anti) {
- AntiDepReg = Edge->getReg();
- assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
- // Don't break anti-dependencies on non-allocatable registers.
- if (!AllocatableSet.test(AntiDepReg))
- 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 = CriticalPathSU->Preds.begin(),
- PE = CriticalPathSU->Preds.end(); P != PE; ++P)
- if (P->getSUnit() == NextSU ?
- (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
- (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) {
- AntiDepReg = 0;
- break;
- }
- }
- }
- CriticalPathSU = NextSU;
- CriticalPathMI = CriticalPathSU->getInstr();
- } else {
- // We've reached the end of the critical path.
- CriticalPathSU = 0;
- CriticalPathMI = 0;
- }