109467b48Spatrick //===- CriticalAntiDepBreaker.cpp - Anti-dep breaker ----------------------===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick //
909467b48Spatrick // This file implements the CriticalAntiDepBreaker class, which
1009467b48Spatrick // implements register anti-dependence breaking along a blocks
1109467b48Spatrick // critical path during post-RA scheduler.
1209467b48Spatrick //
1309467b48Spatrick //===----------------------------------------------------------------------===//
1409467b48Spatrick
1509467b48Spatrick #include "CriticalAntiDepBreaker.h"
1609467b48Spatrick #include "llvm/ADT/ArrayRef.h"
1709467b48Spatrick #include "llvm/ADT/DenseMap.h"
1809467b48Spatrick #include "llvm/ADT/SmallVector.h"
1909467b48Spatrick #include "llvm/CodeGen/MachineBasicBlock.h"
2009467b48Spatrick #include "llvm/CodeGen/MachineFrameInfo.h"
2109467b48Spatrick #include "llvm/CodeGen/MachineFunction.h"
2209467b48Spatrick #include "llvm/CodeGen/MachineInstr.h"
2309467b48Spatrick #include "llvm/CodeGen/MachineOperand.h"
2409467b48Spatrick #include "llvm/CodeGen/MachineRegisterInfo.h"
2509467b48Spatrick #include "llvm/CodeGen/RegisterClassInfo.h"
2609467b48Spatrick #include "llvm/CodeGen/ScheduleDAG.h"
2709467b48Spatrick #include "llvm/CodeGen/TargetInstrInfo.h"
2809467b48Spatrick #include "llvm/CodeGen/TargetRegisterInfo.h"
2909467b48Spatrick #include "llvm/CodeGen/TargetSubtargetInfo.h"
3009467b48Spatrick #include "llvm/MC/MCInstrDesc.h"
3109467b48Spatrick #include "llvm/MC/MCRegisterInfo.h"
3209467b48Spatrick #include "llvm/Support/Debug.h"
3309467b48Spatrick #include "llvm/Support/raw_ostream.h"
3409467b48Spatrick #include <cassert>
3509467b48Spatrick #include <utility>
3609467b48Spatrick
3709467b48Spatrick using namespace llvm;
3809467b48Spatrick
3909467b48Spatrick #define DEBUG_TYPE "post-RA-sched"
4009467b48Spatrick
CriticalAntiDepBreaker(MachineFunction & MFi,const RegisterClassInfo & RCI)4109467b48Spatrick CriticalAntiDepBreaker::CriticalAntiDepBreaker(MachineFunction &MFi,
4209467b48Spatrick const RegisterClassInfo &RCI)
43*d415bd75Srobert : MF(MFi), MRI(MF.getRegInfo()), TII(MF.getSubtarget().getInstrInfo()),
4409467b48Spatrick TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI),
4509467b48Spatrick Classes(TRI->getNumRegs(), nullptr), KillIndices(TRI->getNumRegs(), 0),
4609467b48Spatrick DefIndices(TRI->getNumRegs(), 0), KeepRegs(TRI->getNumRegs(), false) {}
4709467b48Spatrick
4809467b48Spatrick CriticalAntiDepBreaker::~CriticalAntiDepBreaker() = default;
4909467b48Spatrick
StartBlock(MachineBasicBlock * BB)5009467b48Spatrick void CriticalAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
5109467b48Spatrick const unsigned BBSize = BB->size();
5209467b48Spatrick for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) {
5309467b48Spatrick // Clear out the register class data.
5409467b48Spatrick Classes[i] = nullptr;
5509467b48Spatrick
5609467b48Spatrick // Initialize the indices to indicate that no registers are live.
5709467b48Spatrick KillIndices[i] = ~0u;
5809467b48Spatrick DefIndices[i] = BBSize;
5909467b48Spatrick }
6009467b48Spatrick
6109467b48Spatrick // Clear "do not change" set.
6209467b48Spatrick KeepRegs.reset();
6309467b48Spatrick
6409467b48Spatrick bool IsReturnBlock = BB->isReturnBlock();
6509467b48Spatrick
6609467b48Spatrick // Examine the live-in regs of all successors.
6773471bf0Spatrick for (const MachineBasicBlock *Succ : BB->successors())
6873471bf0Spatrick for (const auto &LI : Succ->liveins()) {
6909467b48Spatrick for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) {
7009467b48Spatrick unsigned Reg = *AI;
7109467b48Spatrick Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
7209467b48Spatrick KillIndices[Reg] = BBSize;
7309467b48Spatrick DefIndices[Reg] = ~0u;
7409467b48Spatrick }
7509467b48Spatrick }
7609467b48Spatrick
7709467b48Spatrick // Mark live-out callee-saved registers. In a return block this is
7809467b48Spatrick // all callee-saved registers. In non-return this is any
7909467b48Spatrick // callee-saved register that is not saved in the prolog.
8009467b48Spatrick const MachineFrameInfo &MFI = MF.getFrameInfo();
8109467b48Spatrick BitVector Pristine = MFI.getPristineRegs(MF);
8209467b48Spatrick for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I;
8309467b48Spatrick ++I) {
8409467b48Spatrick unsigned Reg = *I;
8509467b48Spatrick if (!IsReturnBlock && !Pristine.test(Reg))
8609467b48Spatrick continue;
8709467b48Spatrick for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) {
8809467b48Spatrick unsigned Reg = *AI;
8909467b48Spatrick Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
9009467b48Spatrick KillIndices[Reg] = BBSize;
9109467b48Spatrick DefIndices[Reg] = ~0u;
9209467b48Spatrick }
9309467b48Spatrick }
9409467b48Spatrick }
9509467b48Spatrick
FinishBlock()9609467b48Spatrick void CriticalAntiDepBreaker::FinishBlock() {
9709467b48Spatrick RegRefs.clear();
9809467b48Spatrick KeepRegs.reset();
9909467b48Spatrick }
10009467b48Spatrick
Observe(MachineInstr & MI,unsigned Count,unsigned InsertPosIndex)10109467b48Spatrick void CriticalAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count,
10209467b48Spatrick unsigned InsertPosIndex) {
10309467b48Spatrick // Kill instructions can define registers but are really nops, and there might
10409467b48Spatrick // be a real definition earlier that needs to be paired with uses dominated by
10509467b48Spatrick // this kill.
10609467b48Spatrick
10709467b48Spatrick // FIXME: It may be possible to remove the isKill() restriction once PR18663
10809467b48Spatrick // has been properly fixed. There can be value in processing kills as seen in
10909467b48Spatrick // the AggressiveAntiDepBreaker class.
11009467b48Spatrick if (MI.isDebugInstr() || MI.isKill())
11109467b48Spatrick return;
11209467b48Spatrick assert(Count < InsertPosIndex && "Instruction index out of expected range!");
11309467b48Spatrick
11409467b48Spatrick for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) {
11509467b48Spatrick if (KillIndices[Reg] != ~0u) {
11609467b48Spatrick // If Reg is currently live, then mark that it can't be renamed as
11709467b48Spatrick // we don't know the extent of its live-range anymore (now that it
11809467b48Spatrick // has been scheduled).
11909467b48Spatrick Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
12009467b48Spatrick KillIndices[Reg] = Count;
12109467b48Spatrick } else if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) {
12209467b48Spatrick // Any register which was defined within the previous scheduling region
12309467b48Spatrick // may have been rescheduled and its lifetime may overlap with registers
12409467b48Spatrick // in ways not reflected in our current liveness state. For each such
12509467b48Spatrick // register, adjust the liveness state to be conservatively correct.
12609467b48Spatrick Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
12709467b48Spatrick
12809467b48Spatrick // Move the def index to the end of the previous region, to reflect
12909467b48Spatrick // that the def could theoretically have been scheduled at the end.
13009467b48Spatrick DefIndices[Reg] = InsertPosIndex;
13109467b48Spatrick }
13209467b48Spatrick }
13309467b48Spatrick
13409467b48Spatrick PrescanInstruction(MI);
13509467b48Spatrick ScanInstruction(MI, Count);
13609467b48Spatrick }
13709467b48Spatrick
13809467b48Spatrick /// CriticalPathStep - Return the next SUnit after SU on the bottom-up
13909467b48Spatrick /// critical path.
CriticalPathStep(const SUnit * SU)14009467b48Spatrick static const SDep *CriticalPathStep(const SUnit *SU) {
14109467b48Spatrick const SDep *Next = nullptr;
14209467b48Spatrick unsigned NextDepth = 0;
14309467b48Spatrick // Find the predecessor edge with the greatest depth.
14473471bf0Spatrick for (const SDep &P : SU->Preds) {
14573471bf0Spatrick const SUnit *PredSU = P.getSUnit();
14673471bf0Spatrick unsigned PredLatency = P.getLatency();
14709467b48Spatrick unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;
14809467b48Spatrick // In the case of a latency tie, prefer an anti-dependency edge over
14909467b48Spatrick // other types of edges.
15009467b48Spatrick if (NextDepth < PredTotalLatency ||
15173471bf0Spatrick (NextDepth == PredTotalLatency && P.getKind() == SDep::Anti)) {
15209467b48Spatrick NextDepth = PredTotalLatency;
15373471bf0Spatrick Next = &P;
15409467b48Spatrick }
15509467b48Spatrick }
15609467b48Spatrick return Next;
15709467b48Spatrick }
15809467b48Spatrick
PrescanInstruction(MachineInstr & MI)15909467b48Spatrick void CriticalAntiDepBreaker::PrescanInstruction(MachineInstr &MI) {
16009467b48Spatrick // It's not safe to change register allocation for source operands of
16109467b48Spatrick // instructions that have special allocation requirements. Also assume all
16209467b48Spatrick // registers used in a call must not be changed (ABI).
16309467b48Spatrick // FIXME: The issue with predicated instruction is more complex. We are being
16409467b48Spatrick // conservative here because the kill markers cannot be trusted after
16509467b48Spatrick // if-conversion:
16609467b48Spatrick // %r6 = LDR %sp, %reg0, 92, 14, %reg0; mem:LD4[FixedStack14]
16709467b48Spatrick // ...
16809467b48Spatrick // STR %r0, killed %r6, %reg0, 0, 0, %cpsr; mem:ST4[%395]
16909467b48Spatrick // %r6 = LDR %sp, %reg0, 100, 0, %cpsr; mem:LD4[FixedStack12]
17009467b48Spatrick // STR %r0, killed %r6, %reg0, 0, 14, %reg0; mem:ST4[%396](align=8)
17109467b48Spatrick //
17209467b48Spatrick // The first R6 kill is not really a kill since it's killed by a predicated
17309467b48Spatrick // instruction which may not be executed. The second R6 def may or may not
17409467b48Spatrick // re-define R6 so it's not safe to change it since the last R6 use cannot be
17509467b48Spatrick // changed.
17609467b48Spatrick bool Special =
17709467b48Spatrick MI.isCall() || MI.hasExtraSrcRegAllocReq() || TII->isPredicated(MI);
17809467b48Spatrick
17909467b48Spatrick // Scan the register operands for this instruction and update
18009467b48Spatrick // Classes and RegRefs.
18109467b48Spatrick for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
18209467b48Spatrick MachineOperand &MO = MI.getOperand(i);
18309467b48Spatrick if (!MO.isReg()) continue;
18409467b48Spatrick Register Reg = MO.getReg();
18509467b48Spatrick if (Reg == 0) continue;
18609467b48Spatrick const TargetRegisterClass *NewRC = nullptr;
18709467b48Spatrick
18809467b48Spatrick if (i < MI.getDesc().getNumOperands())
18909467b48Spatrick NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF);
19009467b48Spatrick
19109467b48Spatrick // For now, only allow the register to be changed if its register
19209467b48Spatrick // class is consistent across all uses.
19309467b48Spatrick if (!Classes[Reg] && NewRC)
19409467b48Spatrick Classes[Reg] = NewRC;
19509467b48Spatrick else if (!NewRC || Classes[Reg] != NewRC)
19609467b48Spatrick Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
19709467b48Spatrick
19809467b48Spatrick // Now check for aliases.
19909467b48Spatrick for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {
20009467b48Spatrick // If an alias of the reg is used during the live range, give up.
20109467b48Spatrick // Note that this allows us to skip checking if AntiDepReg
20209467b48Spatrick // overlaps with any of the aliases, among other things.
20309467b48Spatrick unsigned AliasReg = *AI;
20409467b48Spatrick if (Classes[AliasReg]) {
20509467b48Spatrick Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1);
20609467b48Spatrick Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
20709467b48Spatrick }
20809467b48Spatrick }
20909467b48Spatrick
21009467b48Spatrick // If we're still willing to consider this register, note the reference.
21109467b48Spatrick if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1))
21209467b48Spatrick RegRefs.insert(std::make_pair(Reg, &MO));
21309467b48Spatrick
214*d415bd75Srobert if (MO.isUse() && Special) {
215*d415bd75Srobert if (!KeepRegs.test(Reg)) {
216*d415bd75Srobert for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
217*d415bd75Srobert SubRegs.isValid(); ++SubRegs)
218*d415bd75Srobert KeepRegs.set(*SubRegs);
219*d415bd75Srobert }
220*d415bd75Srobert }
221*d415bd75Srobert }
222*d415bd75Srobert
223*d415bd75Srobert for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
224*d415bd75Srobert const MachineOperand &MO = MI.getOperand(I);
225*d415bd75Srobert if (!MO.isReg()) continue;
226*d415bd75Srobert Register Reg = MO.getReg();
227*d415bd75Srobert if (!Reg.isValid())
228*d415bd75Srobert continue;
22909467b48Spatrick // If this reg is tied and live (Classes[Reg] is set to -1), we can't change
23009467b48Spatrick // it or any of its sub or super regs. We need to use KeepRegs to mark the
23109467b48Spatrick // reg because not all uses of the same reg within an instruction are
23209467b48Spatrick // necessarily tagged as tied.
23309467b48Spatrick // Example: an x86 "xor %eax, %eax" will have one source operand tied to the
23409467b48Spatrick // def register but not the second (see PR20020 for details).
23509467b48Spatrick // FIXME: can this check be relaxed to account for undef uses
23609467b48Spatrick // of a register? In the above 'xor' example, the uses of %eax are undef, so
23709467b48Spatrick // earlier instructions could still replace %eax even though the 'xor'
23809467b48Spatrick // itself can't be changed.
239*d415bd75Srobert if (MI.isRegTiedToUseOperand(I) &&
24009467b48Spatrick Classes[Reg] == reinterpret_cast<TargetRegisterClass *>(-1)) {
24109467b48Spatrick for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
24209467b48Spatrick SubRegs.isValid(); ++SubRegs) {
24309467b48Spatrick KeepRegs.set(*SubRegs);
24409467b48Spatrick }
24509467b48Spatrick for (MCSuperRegIterator SuperRegs(Reg, TRI);
24609467b48Spatrick SuperRegs.isValid(); ++SuperRegs) {
24709467b48Spatrick KeepRegs.set(*SuperRegs);
24809467b48Spatrick }
24909467b48Spatrick }
25009467b48Spatrick }
25109467b48Spatrick }
25209467b48Spatrick
ScanInstruction(MachineInstr & MI,unsigned Count)25309467b48Spatrick void CriticalAntiDepBreaker::ScanInstruction(MachineInstr &MI, unsigned Count) {
25409467b48Spatrick // Update liveness.
25509467b48Spatrick // Proceeding upwards, registers that are defed but not used in this
25609467b48Spatrick // instruction are now dead.
25709467b48Spatrick assert(!MI.isKill() && "Attempting to scan a kill instruction");
25809467b48Spatrick
25909467b48Spatrick if (!TII->isPredicated(MI)) {
26009467b48Spatrick // Predicated defs are modeled as read + write, i.e. similar to two
26109467b48Spatrick // address updates.
26209467b48Spatrick for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
26309467b48Spatrick MachineOperand &MO = MI.getOperand(i);
26409467b48Spatrick
26509467b48Spatrick if (MO.isRegMask()) {
26609467b48Spatrick auto ClobbersPhysRegAndSubRegs = [&](unsigned PhysReg) {
26709467b48Spatrick for (MCSubRegIterator SRI(PhysReg, TRI, true); SRI.isValid(); ++SRI)
26809467b48Spatrick if (!MO.clobbersPhysReg(*SRI))
26909467b48Spatrick return false;
27009467b48Spatrick
27109467b48Spatrick return true;
27209467b48Spatrick };
27309467b48Spatrick
27409467b48Spatrick for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) {
27509467b48Spatrick if (ClobbersPhysRegAndSubRegs(i)) {
27609467b48Spatrick DefIndices[i] = Count;
27709467b48Spatrick KillIndices[i] = ~0u;
27809467b48Spatrick KeepRegs.reset(i);
27909467b48Spatrick Classes[i] = nullptr;
28009467b48Spatrick RegRefs.erase(i);
28109467b48Spatrick }
28209467b48Spatrick }
28309467b48Spatrick }
28409467b48Spatrick
28509467b48Spatrick if (!MO.isReg()) continue;
28609467b48Spatrick Register Reg = MO.getReg();
28709467b48Spatrick if (Reg == 0) continue;
28809467b48Spatrick if (!MO.isDef()) continue;
28909467b48Spatrick
29009467b48Spatrick // Ignore two-addr defs.
29109467b48Spatrick if (MI.isRegTiedToUseOperand(i))
29209467b48Spatrick continue;
29309467b48Spatrick
29409467b48Spatrick // If we've already marked this reg as unchangeable, don't remove
29509467b48Spatrick // it or any of its subregs from KeepRegs.
29609467b48Spatrick bool Keep = KeepRegs.test(Reg);
29709467b48Spatrick
29809467b48Spatrick // For the reg itself and all subregs: update the def to current;
29909467b48Spatrick // reset the kill state, any restrictions, and references.
30009467b48Spatrick for (MCSubRegIterator SRI(Reg, TRI, true); SRI.isValid(); ++SRI) {
30109467b48Spatrick unsigned SubregReg = *SRI;
30209467b48Spatrick DefIndices[SubregReg] = Count;
30309467b48Spatrick KillIndices[SubregReg] = ~0u;
30409467b48Spatrick Classes[SubregReg] = nullptr;
30509467b48Spatrick RegRefs.erase(SubregReg);
30609467b48Spatrick if (!Keep)
30709467b48Spatrick KeepRegs.reset(SubregReg);
30809467b48Spatrick }
30909467b48Spatrick // Conservatively mark super-registers as unusable.
31009467b48Spatrick for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR)
31109467b48Spatrick Classes[*SR] = reinterpret_cast<TargetRegisterClass *>(-1);
31209467b48Spatrick }
31309467b48Spatrick }
31409467b48Spatrick for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
31509467b48Spatrick MachineOperand &MO = MI.getOperand(i);
31609467b48Spatrick if (!MO.isReg()) continue;
31709467b48Spatrick Register Reg = MO.getReg();
31809467b48Spatrick if (Reg == 0) continue;
31909467b48Spatrick if (!MO.isUse()) continue;
32009467b48Spatrick
32109467b48Spatrick const TargetRegisterClass *NewRC = nullptr;
32209467b48Spatrick if (i < MI.getDesc().getNumOperands())
32309467b48Spatrick NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF);
32409467b48Spatrick
32509467b48Spatrick // For now, only allow the register to be changed if its register
32609467b48Spatrick // class is consistent across all uses.
32709467b48Spatrick if (!Classes[Reg] && NewRC)
32809467b48Spatrick Classes[Reg] = NewRC;
32909467b48Spatrick else if (!NewRC || Classes[Reg] != NewRC)
33009467b48Spatrick Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
33109467b48Spatrick
33209467b48Spatrick RegRefs.insert(std::make_pair(Reg, &MO));
33309467b48Spatrick
33409467b48Spatrick // It wasn't previously live but now it is, this is a kill.
33509467b48Spatrick // Repeat for all aliases.
33609467b48Spatrick for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
33709467b48Spatrick unsigned AliasReg = *AI;
33809467b48Spatrick if (KillIndices[AliasReg] == ~0u) {
33909467b48Spatrick KillIndices[AliasReg] = Count;
34009467b48Spatrick DefIndices[AliasReg] = ~0u;
34109467b48Spatrick }
34209467b48Spatrick }
34309467b48Spatrick }
34409467b48Spatrick }
34509467b48Spatrick
34609467b48Spatrick // Check all machine operands that reference the antidependent register and must
34709467b48Spatrick // be replaced by NewReg. Return true if any of their parent instructions may
34809467b48Spatrick // clobber the new register.
34909467b48Spatrick //
35009467b48Spatrick // Note: AntiDepReg may be referenced by a two-address instruction such that
35109467b48Spatrick // it's use operand is tied to a def operand. We guard against the case in which
35209467b48Spatrick // the two-address instruction also defines NewReg, as may happen with
35309467b48Spatrick // pre/postincrement loads. In this case, both the use and def operands are in
35409467b48Spatrick // RegRefs because the def is inserted by PrescanInstruction and not erased
35509467b48Spatrick // during ScanInstruction. So checking for an instruction with definitions of
35609467b48Spatrick // both NewReg and AntiDepReg covers it.
35709467b48Spatrick bool
isNewRegClobberedByRefs(RegRefIter RegRefBegin,RegRefIter RegRefEnd,unsigned NewReg)35809467b48Spatrick CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin,
35909467b48Spatrick RegRefIter RegRefEnd,
36009467b48Spatrick unsigned NewReg) {
36109467b48Spatrick for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) {
36209467b48Spatrick MachineOperand *RefOper = I->second;
36309467b48Spatrick
36409467b48Spatrick // Don't allow the instruction defining AntiDepReg to earlyclobber its
36509467b48Spatrick // operands, in case they may be assigned to NewReg. In this case antidep
36609467b48Spatrick // breaking must fail, but it's too rare to bother optimizing.
36709467b48Spatrick if (RefOper->isDef() && RefOper->isEarlyClobber())
36809467b48Spatrick return true;
36909467b48Spatrick
37009467b48Spatrick // Handle cases in which this instruction defines NewReg.
37109467b48Spatrick MachineInstr *MI = RefOper->getParent();
372*d415bd75Srobert for (const MachineOperand &CheckOper : MI->operands()) {
37309467b48Spatrick if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg))
37409467b48Spatrick return true;
37509467b48Spatrick
37609467b48Spatrick if (!CheckOper.isReg() || !CheckOper.isDef() ||
37709467b48Spatrick CheckOper.getReg() != NewReg)
37809467b48Spatrick continue;
37909467b48Spatrick
38009467b48Spatrick // Don't allow the instruction to define NewReg and AntiDepReg.
38109467b48Spatrick // When AntiDepReg is renamed it will be an illegal op.
38209467b48Spatrick if (RefOper->isDef())
38309467b48Spatrick return true;
38409467b48Spatrick
38509467b48Spatrick // Don't allow an instruction using AntiDepReg to be earlyclobbered by
38609467b48Spatrick // NewReg.
38709467b48Spatrick if (CheckOper.isEarlyClobber())
38809467b48Spatrick return true;
38909467b48Spatrick
39009467b48Spatrick // Don't allow inline asm to define NewReg at all. Who knows what it's
39109467b48Spatrick // doing with it.
39209467b48Spatrick if (MI->isInlineAsm())
39309467b48Spatrick return true;
39409467b48Spatrick }
39509467b48Spatrick }
39609467b48Spatrick return false;
39709467b48Spatrick }
39809467b48Spatrick
39909467b48Spatrick unsigned CriticalAntiDepBreaker::
findSuitableFreeRegister(RegRefIter RegRefBegin,RegRefIter RegRefEnd,unsigned AntiDepReg,unsigned LastNewReg,const TargetRegisterClass * RC,SmallVectorImpl<unsigned> & Forbid)40009467b48Spatrick findSuitableFreeRegister(RegRefIter RegRefBegin,
40109467b48Spatrick RegRefIter RegRefEnd,
40209467b48Spatrick unsigned AntiDepReg,
40309467b48Spatrick unsigned LastNewReg,
40409467b48Spatrick const TargetRegisterClass *RC,
40509467b48Spatrick SmallVectorImpl<unsigned> &Forbid) {
40609467b48Spatrick ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(RC);
407*d415bd75Srobert for (unsigned NewReg : Order) {
40809467b48Spatrick // Don't replace a register with itself.
40909467b48Spatrick if (NewReg == AntiDepReg) continue;
41009467b48Spatrick // Don't replace a register with one that was recently used to repair
41109467b48Spatrick // an anti-dependence with this AntiDepReg, because that would
41209467b48Spatrick // re-introduce that anti-dependence.
41309467b48Spatrick if (NewReg == LastNewReg) continue;
41409467b48Spatrick // If any instructions that define AntiDepReg also define the NewReg, it's
41509467b48Spatrick // not suitable. For example, Instruction with multiple definitions can
41609467b48Spatrick // result in this condition.
41709467b48Spatrick if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue;
41809467b48Spatrick // If NewReg is dead and NewReg's most recent def is not before
41909467b48Spatrick // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg.
42009467b48Spatrick assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u))
42109467b48Spatrick && "Kill and Def maps aren't consistent for AntiDepReg!");
42209467b48Spatrick assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u))
42309467b48Spatrick && "Kill and Def maps aren't consistent for NewReg!");
42409467b48Spatrick if (KillIndices[NewReg] != ~0u ||
42509467b48Spatrick Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) ||
42609467b48Spatrick KillIndices[AntiDepReg] > DefIndices[NewReg])
42709467b48Spatrick continue;
42809467b48Spatrick // If NewReg overlaps any of the forbidden registers, we can't use it.
42909467b48Spatrick bool Forbidden = false;
43073471bf0Spatrick for (unsigned R : Forbid)
43173471bf0Spatrick if (TRI->regsOverlap(NewReg, R)) {
43209467b48Spatrick Forbidden = true;
43309467b48Spatrick break;
43409467b48Spatrick }
43509467b48Spatrick if (Forbidden) continue;
43609467b48Spatrick return NewReg;
43709467b48Spatrick }
43809467b48Spatrick
43909467b48Spatrick // No registers are free and available!
44009467b48Spatrick return 0;
44109467b48Spatrick }
44209467b48Spatrick
44309467b48Spatrick unsigned CriticalAntiDepBreaker::
BreakAntiDependencies(const std::vector<SUnit> & SUnits,MachineBasicBlock::iterator Begin,MachineBasicBlock::iterator End,unsigned InsertPosIndex,DbgValueVector & DbgValues)44409467b48Spatrick BreakAntiDependencies(const std::vector<SUnit> &SUnits,
44509467b48Spatrick MachineBasicBlock::iterator Begin,
44609467b48Spatrick MachineBasicBlock::iterator End,
44709467b48Spatrick unsigned InsertPosIndex,
44809467b48Spatrick DbgValueVector &DbgValues) {
44909467b48Spatrick // The code below assumes that there is at least one instruction,
45009467b48Spatrick // so just duck out immediately if the block is empty.
45109467b48Spatrick if (SUnits.empty()) return 0;
45209467b48Spatrick
45309467b48Spatrick // Keep a map of the MachineInstr*'s back to the SUnit representing them.
45409467b48Spatrick // This is used for updating debug information.
45509467b48Spatrick //
45609467b48Spatrick // FIXME: Replace this with the existing map in ScheduleDAGInstrs::MISUnitMap
45709467b48Spatrick DenseMap<MachineInstr *, const SUnit *> MISUnitMap;
45809467b48Spatrick
45909467b48Spatrick // Find the node at the bottom of the critical path.
46009467b48Spatrick const SUnit *Max = nullptr;
461*d415bd75Srobert for (const SUnit &SU : SUnits) {
462*d415bd75Srobert MISUnitMap[SU.getInstr()] = &SU;
463*d415bd75Srobert if (!Max || SU.getDepth() + SU.Latency > Max->getDepth() + Max->Latency)
464*d415bd75Srobert Max = &SU;
46509467b48Spatrick }
46609467b48Spatrick assert(Max && "Failed to find bottom of the critical path");
46709467b48Spatrick
46809467b48Spatrick #ifndef NDEBUG
46909467b48Spatrick {
47009467b48Spatrick LLVM_DEBUG(dbgs() << "Critical path has total latency "
47109467b48Spatrick << (Max->getDepth() + Max->Latency) << "\n");
47209467b48Spatrick LLVM_DEBUG(dbgs() << "Available regs:");
47309467b48Spatrick for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
47409467b48Spatrick if (KillIndices[Reg] == ~0u)
47509467b48Spatrick LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI));
47609467b48Spatrick }
47709467b48Spatrick LLVM_DEBUG(dbgs() << '\n');
47809467b48Spatrick }
47909467b48Spatrick #endif
48009467b48Spatrick
48109467b48Spatrick // Track progress along the critical path through the SUnit graph as we walk
48209467b48Spatrick // the instructions.
48309467b48Spatrick const SUnit *CriticalPathSU = Max;
48409467b48Spatrick MachineInstr *CriticalPathMI = CriticalPathSU->getInstr();
48509467b48Spatrick
48609467b48Spatrick // Consider this pattern:
48709467b48Spatrick // A = ...
48809467b48Spatrick // ... = A
48909467b48Spatrick // A = ...
49009467b48Spatrick // ... = A
49109467b48Spatrick // A = ...
49209467b48Spatrick // ... = A
49309467b48Spatrick // A = ...
49409467b48Spatrick // ... = A
49509467b48Spatrick // There are three anti-dependencies here, and without special care,
49609467b48Spatrick // we'd break all of them using the same register:
49709467b48Spatrick // A = ...
49809467b48Spatrick // ... = A
49909467b48Spatrick // B = ...
50009467b48Spatrick // ... = B
50109467b48Spatrick // B = ...
50209467b48Spatrick // ... = B
50309467b48Spatrick // B = ...
50409467b48Spatrick // ... = B
50509467b48Spatrick // because at each anti-dependence, B is the first register that
50609467b48Spatrick // isn't A which is free. This re-introduces anti-dependencies
50709467b48Spatrick // at all but one of the original anti-dependencies that we were
50809467b48Spatrick // trying to break. To avoid this, keep track of the most recent
50909467b48Spatrick // register that each register was replaced with, avoid
51009467b48Spatrick // using it to repair an anti-dependence on the same register.
51109467b48Spatrick // This lets us produce this:
51209467b48Spatrick // A = ...
51309467b48Spatrick // ... = A
51409467b48Spatrick // B = ...
51509467b48Spatrick // ... = B
51609467b48Spatrick // C = ...
51709467b48Spatrick // ... = C
51809467b48Spatrick // B = ...
51909467b48Spatrick // ... = B
52009467b48Spatrick // This still has an anti-dependence on B, but at least it isn't on the
52109467b48Spatrick // original critical path.
52209467b48Spatrick //
52309467b48Spatrick // TODO: If we tracked more than one register here, we could potentially
52409467b48Spatrick // fix that remaining critical edge too. This is a little more involved,
52509467b48Spatrick // because unlike the most recent register, less recent registers should
52609467b48Spatrick // still be considered, though only if no other registers are available.
52709467b48Spatrick std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0);
52809467b48Spatrick
52909467b48Spatrick // Attempt to break anti-dependence edges on the critical path. Walk the
53009467b48Spatrick // instructions from the bottom up, tracking information about liveness
53109467b48Spatrick // as we go to help determine which registers are available.
53209467b48Spatrick unsigned Broken = 0;
53309467b48Spatrick unsigned Count = InsertPosIndex - 1;
53409467b48Spatrick for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) {
53509467b48Spatrick MachineInstr &MI = *--I;
53609467b48Spatrick // Kill instructions can define registers but are really nops, and there
53709467b48Spatrick // might be a real definition earlier that needs to be paired with uses
53809467b48Spatrick // dominated by this kill.
53909467b48Spatrick
54009467b48Spatrick // FIXME: It may be possible to remove the isKill() restriction once PR18663
54109467b48Spatrick // has been properly fixed. There can be value in processing kills as seen
54209467b48Spatrick // in the AggressiveAntiDepBreaker class.
54309467b48Spatrick if (MI.isDebugInstr() || MI.isKill())
54409467b48Spatrick continue;
54509467b48Spatrick
54609467b48Spatrick // Check if this instruction has a dependence on the critical path that
54709467b48Spatrick // is an anti-dependence that we may be able to break. If it is, set
54809467b48Spatrick // AntiDepReg to the non-zero register associated with the anti-dependence.
54909467b48Spatrick //
55009467b48Spatrick // We limit our attention to the critical path as a heuristic to avoid
55109467b48Spatrick // breaking anti-dependence edges that aren't going to significantly
55209467b48Spatrick // impact the overall schedule. There are a limited number of registers
55309467b48Spatrick // and we want to save them for the important edges.
55409467b48Spatrick //
55509467b48Spatrick // TODO: Instructions with multiple defs could have multiple
55609467b48Spatrick // anti-dependencies. The current code here only knows how to break one
55709467b48Spatrick // edge per instruction. Note that we'd have to be able to break all of
55809467b48Spatrick // the anti-dependencies in an instruction in order to be effective.
55909467b48Spatrick unsigned AntiDepReg = 0;
56009467b48Spatrick if (&MI == CriticalPathMI) {
56109467b48Spatrick if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) {
56209467b48Spatrick const SUnit *NextSU = Edge->getSUnit();
56309467b48Spatrick
56409467b48Spatrick // Only consider anti-dependence edges.
56509467b48Spatrick if (Edge->getKind() == SDep::Anti) {
56609467b48Spatrick AntiDepReg = Edge->getReg();
56709467b48Spatrick assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
56809467b48Spatrick if (!MRI.isAllocatable(AntiDepReg))
56909467b48Spatrick // Don't break anti-dependencies on non-allocatable registers.
57009467b48Spatrick AntiDepReg = 0;
57109467b48Spatrick else if (KeepRegs.test(AntiDepReg))
57209467b48Spatrick // Don't break anti-dependencies if a use down below requires
57309467b48Spatrick // this exact register.
57409467b48Spatrick AntiDepReg = 0;
57509467b48Spatrick else {
57609467b48Spatrick // If the SUnit has other dependencies on the SUnit that it
57709467b48Spatrick // anti-depends on, don't bother breaking the anti-dependency
57809467b48Spatrick // since those edges would prevent such units from being
57909467b48Spatrick // scheduled past each other regardless.
58009467b48Spatrick //
58109467b48Spatrick // Also, if there are dependencies on other SUnits with the
58209467b48Spatrick // same register as the anti-dependency, don't attempt to
58309467b48Spatrick // break it.
58473471bf0Spatrick for (const SDep &P : CriticalPathSU->Preds)
58573471bf0Spatrick if (P.getSUnit() == NextSU
58673471bf0Spatrick ? (P.getKind() != SDep::Anti || P.getReg() != AntiDepReg)
58773471bf0Spatrick : (P.getKind() == SDep::Data &&
58873471bf0Spatrick P.getReg() == AntiDepReg)) {
58909467b48Spatrick AntiDepReg = 0;
59009467b48Spatrick break;
59109467b48Spatrick }
59209467b48Spatrick }
59309467b48Spatrick }
59409467b48Spatrick CriticalPathSU = NextSU;
59509467b48Spatrick CriticalPathMI = CriticalPathSU->getInstr();
59609467b48Spatrick } else {
59709467b48Spatrick // We've reached the end of the critical path.
59809467b48Spatrick CriticalPathSU = nullptr;
59909467b48Spatrick CriticalPathMI = nullptr;
60009467b48Spatrick }
60109467b48Spatrick }
60209467b48Spatrick
60309467b48Spatrick PrescanInstruction(MI);
60409467b48Spatrick
60509467b48Spatrick SmallVector<unsigned, 2> ForbidRegs;
60609467b48Spatrick
60709467b48Spatrick // If MI's defs have a special allocation requirement, don't allow
60809467b48Spatrick // any def registers to be changed. Also assume all registers
60909467b48Spatrick // defined in a call must not be changed (ABI).
61009467b48Spatrick if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI))
61109467b48Spatrick // If this instruction's defs have special allocation requirement, don't
61209467b48Spatrick // break this anti-dependency.
61309467b48Spatrick AntiDepReg = 0;
61409467b48Spatrick else if (AntiDepReg) {
61509467b48Spatrick // If this instruction has a use of AntiDepReg, breaking it
61609467b48Spatrick // is invalid. If the instruction defines other registers,
61709467b48Spatrick // save a list of them so that we don't pick a new register
61809467b48Spatrick // that overlaps any of them.
619*d415bd75Srobert for (const MachineOperand &MO : MI.operands()) {
62009467b48Spatrick if (!MO.isReg()) continue;
62109467b48Spatrick Register Reg = MO.getReg();
62209467b48Spatrick if (Reg == 0) continue;
62309467b48Spatrick if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) {
62409467b48Spatrick AntiDepReg = 0;
62509467b48Spatrick break;
62609467b48Spatrick }
62709467b48Spatrick if (MO.isDef() && Reg != AntiDepReg)
62809467b48Spatrick ForbidRegs.push_back(Reg);
62909467b48Spatrick }
63009467b48Spatrick }
63109467b48Spatrick
63209467b48Spatrick // Determine AntiDepReg's register class, if it is live and is
63309467b48Spatrick // consistently used within a single class.
63409467b48Spatrick const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg]
63509467b48Spatrick : nullptr;
63609467b48Spatrick assert((AntiDepReg == 0 || RC != nullptr) &&
63709467b48Spatrick "Register should be live if it's causing an anti-dependence!");
63809467b48Spatrick if (RC == reinterpret_cast<TargetRegisterClass *>(-1))
63909467b48Spatrick AntiDepReg = 0;
64009467b48Spatrick
64109467b48Spatrick // Look for a suitable register to use to break the anti-dependence.
64209467b48Spatrick //
64309467b48Spatrick // TODO: Instead of picking the first free register, consider which might
64409467b48Spatrick // be the best.
64509467b48Spatrick if (AntiDepReg != 0) {
64609467b48Spatrick std::pair<std::multimap<unsigned, MachineOperand *>::iterator,
64709467b48Spatrick std::multimap<unsigned, MachineOperand *>::iterator>
64809467b48Spatrick Range = RegRefs.equal_range(AntiDepReg);
64909467b48Spatrick if (unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second,
65009467b48Spatrick AntiDepReg,
65109467b48Spatrick LastNewReg[AntiDepReg],
65209467b48Spatrick RC, ForbidRegs)) {
65309467b48Spatrick LLVM_DEBUG(dbgs() << "Breaking anti-dependence edge on "
65409467b48Spatrick << printReg(AntiDepReg, TRI) << " with "
65509467b48Spatrick << RegRefs.count(AntiDepReg) << " references"
65609467b48Spatrick << " using " << printReg(NewReg, TRI) << "!\n");
65709467b48Spatrick
65809467b48Spatrick // Update the references to the old register to refer to the new
65909467b48Spatrick // register.
66009467b48Spatrick for (std::multimap<unsigned, MachineOperand *>::iterator
66109467b48Spatrick Q = Range.first, QE = Range.second; Q != QE; ++Q) {
66209467b48Spatrick Q->second->setReg(NewReg);
66309467b48Spatrick // If the SU for the instruction being updated has debug information
66409467b48Spatrick // related to the anti-dependency register, make sure to update that
66509467b48Spatrick // as well.
66609467b48Spatrick const SUnit *SU = MISUnitMap[Q->second->getParent()];
66709467b48Spatrick if (!SU) continue;
66809467b48Spatrick UpdateDbgValues(DbgValues, Q->second->getParent(),
66909467b48Spatrick AntiDepReg, NewReg);
67009467b48Spatrick }
67109467b48Spatrick
67209467b48Spatrick // We just went back in time and modified history; the
67309467b48Spatrick // liveness information for the anti-dependence reg is now
67409467b48Spatrick // inconsistent. Set the state as if it were dead.
67509467b48Spatrick Classes[NewReg] = Classes[AntiDepReg];
67609467b48Spatrick DefIndices[NewReg] = DefIndices[AntiDepReg];
67709467b48Spatrick KillIndices[NewReg] = KillIndices[AntiDepReg];
67809467b48Spatrick assert(((KillIndices[NewReg] == ~0u) !=
67909467b48Spatrick (DefIndices[NewReg] == ~0u)) &&
68009467b48Spatrick "Kill and Def maps aren't consistent for NewReg!");
68109467b48Spatrick
68209467b48Spatrick Classes[AntiDepReg] = nullptr;
68309467b48Spatrick DefIndices[AntiDepReg] = KillIndices[AntiDepReg];
68409467b48Spatrick KillIndices[AntiDepReg] = ~0u;
68509467b48Spatrick assert(((KillIndices[AntiDepReg] == ~0u) !=
68609467b48Spatrick (DefIndices[AntiDepReg] == ~0u)) &&
68709467b48Spatrick "Kill and Def maps aren't consistent for AntiDepReg!");
68809467b48Spatrick
68909467b48Spatrick RegRefs.erase(AntiDepReg);
69009467b48Spatrick LastNewReg[AntiDepReg] = NewReg;
69109467b48Spatrick ++Broken;
69209467b48Spatrick }
69309467b48Spatrick }
69409467b48Spatrick
69509467b48Spatrick ScanInstruction(MI, Count);
69609467b48Spatrick }
69709467b48Spatrick
69809467b48Spatrick return Broken;
69909467b48Spatrick }
700097a140dSpatrick
701097a140dSpatrick AntiDepBreaker *
createCriticalAntiDepBreaker(MachineFunction & MFi,const RegisterClassInfo & RCI)702097a140dSpatrick llvm::createCriticalAntiDepBreaker(MachineFunction &MFi,
703097a140dSpatrick const RegisterClassInfo &RCI) {
704097a140dSpatrick return new CriticalAntiDepBreaker(MFi, RCI);
705097a140dSpatrick }
706