Fix PR26655: Bail out if all regs of an inst BUNDLE have the correct kill flag

[mgrang]

Summary

While setting kill flags on instructions inside a BUNDLE, we bail out as soon
as we set kill flag on a register. But we are missing a check when all the
registers already have the correct kill flag set. We need to bail out in that
case as well.

This patch refactors the old code and simply makes use of the addRegisterKilled
function in MachineInstr.cpp in order to determine whether to set/remove kill
on an instruction.

[mgrang]

A gentle reminder for reviews please.

[mgrang]

Reviews please.

[davide]

Sorry if I point this out, but it already happened several times in the past (on patches where I was listed as reviewer). It's a bit unpleasant pinging each day for a patch. I'm not sure if the developer's policy document what's the timeout for a ping, but I expect 1 week to be a reasonable timeframe.
Also, keep adding (somewhat unrelated) reviewers, I don't think that helps.
As an added bonus, 3.8 is coming out anytime soon, and most of us are very busy trying to fix/review critical regressions, so a little bit of delay is somehow expected =)

[mgrang]

Thanks for the suggestions Davide and apologies for being too impatient :)
As for the reviewers, I see that the ones I have added have contributed to the source file I am making changes to. So not sure what you meant by "unrelated".

[mgrang]

Ping3 for reviews please.

[mgrang]

Ping 4 for reviews please.

[t.p.northover]

Hi,

Sorry it's taken so long to review this, but it doesn't look right to me. The IT placement pass is producing what looks like correct code:

BUNDLE %ITSTATE<imp-def,dead>, %R0<imp-def>, %D16<imp-def>, %R2<imp-use>, %CPSR<imp-use,kill>, %D17<imp-use,kill>
  * t2IT 12, 4, %ITSTATE<imp-def>
  * %R0<def> = t2MOVr %R2, pred:12, pred:%CPSR, opt:%noreg, %ITSTATE<imp-use,internal>
  * %D16<def> = VMOVD %D17<kill>, pred:12, pred:%CPSR<kill>, %ITSTATE<imp-use,kill,internal>

And then the Machine Scheduler adds what looks like a spurious <kill> flag to the CPSR usage:

BUNDLE %ITSTATE<imp-def,dead>, %R0<imp-def>, %D16<imp-def>, %R2<imp-use>, %CPSR<imp-use,kill>, %D17<imp-use,kill>
  * t2IT 12, 4, %ITSTATE<imp-def>
  * %R0<def> = t2MOVr %R2, pred:12, pred:%CPSR<kill>, opt:%noreg, %ITSTATE<imp-use,internal>
  * %D16<def> = VMOVD %D17<kill>, pred:12, pred:%CPSR<kill>, %ITSTATE<imp-use,kill,internal>

I think there's some kind of bug in the scheduler, or how ARM interacts with it. Or possibly ARM's entire usage of bundles (if the rest of LLVM strongly thinks the contents occur simultaneously or something), but that would be a shame.

Cheers.

Tim.

[mgrang]

Thanks a lot for the review and comments Tim. I will take another look at this.

[t.p.northover]

lib/CodeGen/ScheduleDAGInstrs.cpp

1211

I think this goes wrong if the last instruction in the bundle doesn't kill Reg: the MachineOperand loop never clears KillStateAlready set and so we bail.

Perhaps a more suggestive name for this variable would be SeenKill.

[MatzeB]

lib/CodeGen/ScheduleDAGInstrs.cpp

1212–1215

Indentation is wrong.
I wonder if "NewKillState = false" wouldn't be more consistent than "return", otherwise we will update all operands in the NewKillState==false case, but stop after we encountered an instruction using the register in the NewKillState==true case.

[t.p.northover]

Sorry for messing you around here, but we've just noticed there are functions in MachineInstr that should be able to handle this for you. Specifically addRegisterKilled (make sure AddIfNotFound is false) and clearRegisterKills can replace the inner loop entirely (we think). They should also handle register aliases, which is probably a good thing.

Cheers.

Tim (after a chat with Matthias).

[mgrang]

Thanks Tim and Matthias for the suggestions.

I have updated my patch to make use of the addRegisterKilled and clearRegisterKills functions.
However, I notice that the addRegisterKilled function does not check if the operand is a debug value or if it is setting an internal flag not visible outside the bundle. I have now added these checks to addRegisterKilled function.

[mgrang]

Tim/Matthias,
Could you please review this patch?

Thanks,
Mandeep

[t.p.northover]

Yep, sorry about the delay. That addition to addRegisterKilled needs some careful thought, since this isn't the only user.

The debug operand is probably fine, but it seems completely unobvious to me that all other users will want to skip internal reads, so we've got to think about all other call-sites. Not helped by the fact that I can't even see why it's necessary in this case yet.

I haven't forgotten though!

Tim.

[mgrang]

Sorry Tim for the delay in addressing your comments - was busy with an upcoming release.

So I ran the entire set of correctness tests in our validation framework without the check for isInternalRead() and I did not see any extra regressions. Also there are no extra unit test failures without this check. So I guess the check for isInternalRead() is really not needed and can be safely removed.

On the other hand the check for isDebug() is needed otherwise the following unit test fails:

******************** TEST 'LLVM :: CodeGen/MIR/ARM/sched-it-debug-nodes.mir' FAILED ********************
Script:
--
build/llvm/./bin/llc -mtriple thumbv7 -start-after if-converter -print-before=post-RA-sched -print-after=post-RA-sched src/llvm/test/CodeGen/MIR/ARM/sched-it-debug-nodes.mir -o /dev/null 2>&1 | build/llvm/./bin/FileCheck src/llvm/test/CodeGen/MIR/ARM/sched-it-debug-nodes.mir
--
Exit Code: 134

Command Output (stderr):
--
build/llvm/test/CodeGen/MIR/ARM/Output/sched-it-debug-nodes.mir.script: line 1: 41373 Aborted                 build/llvm/./bin/llc -mtriple thumbv7 -start-after if-converter -print-before=post-RA-sched -print-after=post-RA-sched src/llvm/test/CodeGen/MIR/ARM/sched-it-debug-nodes.mir -o /dev/null 2>&1
     41374 Done                    | build/llvm/./bin/FileCheck src/llvm/test/CodeGen/MIR/ARM/sched-it-debug-nodes.mir

[mgrang]

Gentle reminder for reviews please.

[mgrang]

Tim/Matthias,
Could you please review this patch?

Thanks,
Mandeep

[MatzeB]

In D17356#405435, @mgrang wrote:

So I ran the entire set of correctness tests in our validation framework without the check for isInternalRead() and I did not see any extra regressions. Also there are no extra unit test failures without this check. So I guess the check for isInternalRead() is really not needed and can be safely removed.

You have to be carefull here, I think there are just no in-tree targets at the moment that use bundles before register allocation. Having said that I looked at the code and I believe it was checking the first instruction of a bundle only, the first instruction is the BUNDLE summary instruction and should not have any internal reads anyway so with this reasoning it should be fine to ignore it.

I believe the check for DebugValue nodes can be done outside (see below). With the issues below addressed this looks good to me.

lib/CodeGen/MachineInstr.cpp

1944–1950

Why not check MI.isDebugValue() at the caller?

lib/CodeGen/ScheduleDAGInstrs.cpp

1200

Use a reference to pass TRI as it must not be nullptr.

test/CodeGen/Thumb2/thumb2-cpsr-liveness.ll

1

It would be nice to add a comment on what the test is testing.

lib/CodeGen/MachineInstr.cpp

bool MachineInstr::addRegisterKilled(unsigned IncomingReg,
   bool hasAliases = isPhysReg &&
     MCRegAliasIterator(IncomingReg, RegInfo, false).isValid();
   bool Found = false;
   SmallVector<unsigned,4> DeadOps;
   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
     MachineOperand &MO = getOperand(i);
     if (!MO.isReg() || !MO.isUse() || MO.isUndef())
       continue;
+
+    // DEBUG_VALUE nodes do not contribute to code generation and should
+    // always be ignored. Failure to do so may result in trying to modify
+    // KILL flags on DEBUG_VALUE nodes.
+    if (MO.isDebug())
+      continue;
+
     unsigned Reg = MO.getReg();
     if (!Reg)
       continue;
 
     if (Reg == IncomingReg) {
       if (!Found) {
         if (MO.isKill())
           // The register is already marked kill.

lib/CodeGen/ScheduleDAGInstrs.cpp

for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
     }
   }
 }
 
 /// \brief If we change a kill flag on the bundle instruction implicit register
 /// operands, then we also need to propagate that to any instructions inside
 /// the bundle which had the same kill state.
 static void toggleBundleKillFlag(MachineInstr *MI, unsigned Reg,
-                                 bool NewKillState) {
+                                 bool NewKillState,
+                                 const TargetRegisterInfo *TRI) {
   if (MI->getOpcode() != TargetOpcode::BUNDLE)
     return;
 
   // Walk backwards from the last instruction in the bundle to the first.
   // Once we set a kill flag on an instruction, we bail out, as otherwise we
   // might set it on too many operands.  We will clear as many flags as we
   // can though.
   MachineBasicBlock::instr_iterator Begin = MI->getIterator();
   MachineBasicBlock::instr_iterator End = getBundleEnd(*MI);
   while (Begin != End) {
-    for (MachineOperand &MO : (--End)->operands()) {
-      if (!MO.isReg() || MO.isDef() || Reg != MO.getReg())
-        continue;
-
-      // DEBUG_VALUE nodes do not contribute to code generation and should
-      // always be ignored.  Failure to do so may result in trying to modify
-      // KILL flags on DEBUG_VALUE nodes, which is distressing.
-      if (MO.isDebug())
-        continue;
-
-      // If the register has the internal flag then it could be killing an
-      // internal def of the register.  In this case, just skip.  We only want
-      // to toggle the flag on operands visible outside the bundle.
-      if (MO.isInternalRead())
-        continue;
-
-      if (MO.isKill() == NewKillState)
-        continue;
-      MO.setIsKill(NewKillState);
-      if (NewKillState)
+    if (NewKillState) {
+      if ((--End)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
          return;
-    }
+    } else
+        (--End)->clearRegisterKills(Reg, TRI);
   }
 }
 
 bool ScheduleDAGInstrs::toggleKillFlag(MachineInstr *MI, MachineOperand &MO) {
   // Setting kill flag...
   if (!MO.isKill()) {
     MO.setIsKill(true);
-    toggleBundleKillFlag(MI, MO.getReg(), true);
+    toggleBundleKillFlag(MI, MO.getReg(), true, TRI);
     return false;
   }
 
   // If MO itself is live, clear the kill flag...
   if (LiveRegs.test(MO.getReg())) {
     MO.setIsKill(false);
-    toggleBundleKillFlag(MI, MO.getReg(), false);
+    toggleBundleKillFlag(MI, MO.getReg(), false, TRI);
     return false;
   }
 
   // If any subreg of MO is live, then create an imp-def for that
   // subreg and keep MO marked as killed.
   MO.setIsKill(false);
-  toggleBundleKillFlag(MI, MO.getReg(), false);
+  toggleBundleKillFlag(MI, MO.getReg(), false, TRI);
   bool AllDead = true;
   const unsigned SuperReg = MO.getReg();
   MachineInstrBuilder MIB(MF, MI);
   for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) {
     if (LiveRegs.test(*SubRegs)) {
       MIB.addReg(*SubRegs, RegState::ImplicitDefine);
       AllDead = false;
     }
   }
 
   if(AllDead) {
     MO.setIsKill(true);
-    toggleBundleKillFlag(MI, MO.getReg(), true);
+    toggleBundleKillFlag(MI, MO.getReg(), true, TRI);
   }
   return false;
 }
 
 // FIXME: Reuse the LivePhysRegs utility for this.
 void ScheduleDAGInstrs::fixupKills(MachineBasicBlock *MBB) {
   DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n');
 

test/CodeGen/Thumb2/thumb2-cpsr-liveness.ll

+; RUN: llc < %s -mtriple=thumbv7-linux-gnueabi -misched-postra=true
+
+define i32 @test_cpsr() {
+entry:
+  %a = alloca [10 x i32], align 4
+  %0 = bitcast [10 x i32]* %a to i8*
+  %arrayidx.gep = getelementptr [10 x i32], [10 x i32]* %a, i32 0, i32 0
+  br label %for.body
+
+for.cond.cleanup:
+  %c.1.reg2mem.0.lcssa = phi i32 [ %c.1.reg2mem.0, %for.inc ]
+  ret i32 %c.1.reg2mem.0.lcssa
+
+for.body:
+  %1 = phi i32 [ 0, %entry ], [ %.pre, %for.inc.for.body_crit_edge ]
+  %c.018.reg2mem.0 = phi i32 [ 0, %entry ], [ %c.1.reg2mem.0, %for.inc.for.body_crit_edge ]
+  %b.017.reg2mem.0 = phi double [ 0.000000e+00, %entry ], [ %b.1.reg2mem.0, %for.inc.for.body_crit_edge ]
+  %arrayidx.phi = phi i32* [ %arrayidx.gep, %entry ], [ %arrayidx.inc, %for.inc.for.body_crit_edge ]
+  %i.019 = phi i32 [ 0, %entry ], [ %inc, %for.inc.for.body_crit_edge ]
+  %cmp1 = icmp slt i32 %1, 10
+  %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1
+  br i1 %cmp1, label %for.inc, label %if.end
+
+if.end:
+  %conv = sitofp i32 %i.019 to double
+  %cmp2 = fcmp nsz ogt double %conv, %b.017.reg2mem.0
+  %selv = select i1 %cmp2, double %conv, double %b.017.reg2mem.0
+  %selv7 = select i1 %cmp2, i32 %i.019, i32 %c.018.reg2mem.0
+  br label %for.inc
+
+for.inc:
+  %b.1.reg2mem.0 = phi double [ %b.017.reg2mem.0, %for.body ], [ %selv, %if.end ]
+  %c.1.reg2mem.0 = phi i32 [ %c.018.reg2mem.0, %for.body ], [ %selv7, %if.end ]
+  %exitcond = icmp eq i32 %i.019, 9
+  br i1 %exitcond, label %for.cond.cleanup, label %for.inc.for.body_crit_edge
+
+for.inc.for.body_crit_edge:
+  %inc = add nuw nsw i32 %i.019, 1
+  %.pre = load i32, i32* %arrayidx.inc, align 4
+  br label %for.body
+}