Extended Description

This bug happens in Cortex-M0 after https://reviews.llvm.org/D21885 and none of the follow-ups seem to have fixed it.

The failing test case comes from the libcxx testsuite. Apologies for the big testcase but I didn't manage to
reduce it further using bugpoint without introducing unpleasant "undefs" everywhere.

clang -S -o test.s -mcpu=cortex-m0 --target=arm-arm-none-eabi iterator.pass.bad.ll

The issue is that, at the point the RegisterScavenger is run, we have a very big basic block, number 47.

In which the phyisical register %R2 has a very long live range as it is defined
very early in the function.

%R2<def> = tLDRpci <cp#0>, pred:14, pred:%noreg

Right before the Register scavenging there is this sequence if instructions in that same basic block #​47

%vreg42<def> = tLDRpci <cp#143>, pred:14, pred:%noreg; tGPR:%vreg42
%vreg42<def,tied1> = tADDhirr %vreg42<tied0>, %SP<kill>, pred:14, pred:%noreg; tGPR:%vreg42
tSTRi %R0, %vreg42<kill>, 0, pred:14, pred:%noreg; mem:ST4[%760] tGPR:%vreg42
%vreg43<def> = tLDRpci <cp#144>, pred:14, pred:%noreg; tGPR:%vreg43
%vreg43<def,tied1> = tADDhirr %vreg43<tied0>, %SP<kill>, pred:14, pred:%noreg; tGPR:%vreg43
tSTRi %R1, %vreg43<kill>, 0, pred:14, pred:%noreg; mem:ST4[%761](align=8) tGPR:%vreg43
%vreg44<def> = tLDRpci <cp#145>, pred:14, pred:%noreg; tGPR:%vreg44
%vreg44<def,tied1> = tADDhirr %vreg44<tied0>, %SP<kill>, pred:14, pred:%noreg; tGPR:%vreg44  <-- (B)
tSTRi %R2, %vreg44<kill>, 0, pred:14, pred:%noreg; mem:ST4[%761+4] tGPR:%vreg44   <-- (A)

After the register scavenger, though, R2 is spilled (R12 is a scratch register in ARM).

%R12<def> = tMOVr %R2<kill>, pred:14, pred:%noreg
%R2<def> = tLDRpci <cp#143>, pred:14, pred:%noreg
%R2<def,tied1> = tADDhirr %R2<tied0>, %SP<kill>, pred:14, pred:%noreg
tSTRi %R0, %R2<kill>, 0, pred:14, pred:%noreg; mem:ST4[%760]
%R2<def> = tLDRpci <cp#144>, pred:14, pred:%noreg
%R2<def,tied1> = tADDhirr %R2<tied0>, %SP<kill>, pred:14, pred:%noreg
tSTRi %R1, %R2<kill>, 0, pred:14, pred:%noreg; mem:ST4[%761](align=8)
%R2<def> = tLDRpci <cp#145>, pred:14, pred:%noreg
%R2<def,tied1> = tADDhirr %R2<tied0>, %SP<kill>, pred:14, pred:%noreg
tSTRi %R2<kill>, %R2<kill>, 0, pred:14, pred:%noreg; mem:ST4[%761+4]    <-- problem
%R2<def> = tMOVr %R12<kill>, pred:14, pred:%noreg

The value of R2 is still used however has been clobbered durng the spill.

What I see is that the current algorithm in scavengeFrameVirtualRegsInBlock
loops from the last to the first instruction, but if an instruction only reads
a virtual register and does not write it, then this instruction is handled in
the next iteration (so the iteration of the previous instruction).

static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI,
RegScavenger &RS,
MachineBasicBlock &MBB) {
const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
RS.enterBasicBlockEnd(MBB);

unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();
bool NextInstructionReadsVReg = false;
for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
--I;
// Move RegScavenger to the position between *I and *std::next(I).
RS.backward(I);

// Look for unassigned vregs in the uses of *std::next(I).
if (NextInstructionReadsVReg) {
  MachineBasicBlock::iterator N = std::next(I);
  const MachineInstr &NMI = *N;
  for (const MachineOperand &MO : NMI.operands()) {
    if (!MO.isReg())
      continue;
    unsigned Reg = MO.getReg();
    // We only care about virtual registers and ignore virtual registers
    // created by the target callbacks in the process (those will be handled
    // in a scavenging round).
    if (!TargetRegisterInfo::isVirtualRegister(Reg) ||
        TargetRegisterInfo::virtReg2Index(Reg) >= InitialNumVirtRegs)
      continue;
    if (!MO.readsReg())
      continue;

    unsigned SReg = scavengeVReg(MRI, RS, Reg, true); // <-- (C)
    N->addRegisterKilled(SReg, &TRI, false);
    RS.setRegUsed(SReg);
  }
}
... rest of the loop ...

}

So in my testcase when I == (A), given that it only reads a vreg but does not
write it, it is handled in the next iteration. This is, when I == (B) in which
case N == (A). Then because of RS.backward(I) at the beginning of the loop,
RS.MBBI points at (B) so scavengeVReg will start from (B) without
checking anything of (A).

I made a quick experiment replacing (C) with

RS.skipTo(N);
unsigned SReg = scavengeVReg(MRI, RS, Reg, true);

but I'm pretty sure this is wrong (and also makes other tests fail). So I'm a
bit puzzled at this point what is the reason why the RegScavenger thinks that
R2 is an eligible register at this point. It looks to me that not considering
(A) might be the cause but then this problem could have happened in other parts
of that basic block that expose similar patterns.

Kind regards.