IfConversion: Add implicit uses for redefined regs with live subregisters

[kparzysz]

Summary

Normally, if conversion would add implicit uses for redefined registers, e.g. R0<def> = add_if ..., R0<imp-use>. However, if only subregisters of R0 are known to be live but not R0 itself, such implicit uses will not be added, causing prior definitions of such subregisters and R0 itself to become dead.

[kparzysz]

Removed debug statement.

[jonpa]

It seems LivePhysRegs::addReg() adds the register and its sub regs, so I am thinking it should be enough here to iterate over super regs (including self) instead of all aliases?

[kparzysz]

Replaced the reg-alias iterator with super-reg iterator.

[kparzysz]

Ping.

[jonpa]

From what I can understand, the MachineFunction has first the %R16 and %R17 defined in BB#0, to be later used in BB#2. This is why these registers are the ones present in
the live-in lists to begin with, and not %D8. Then, the Hexagon Copy-To-Combine pass rewrites BB#0, to copy %D8 with one instruction. The live-in lists remain the same, and the use operands also:

(abbreviated)

BB#0: derived from LLVM BB %entry
    Live Ins: %R0 %R1 %D8 %D8
	%R16<def> = A2_tfr %R1<kill>
	%R17<def> = A2_tfr %R0<kill>
    Successors according to CFG: BB#3(0x30000000 / 0x80000000 = 37.50%) BB#1(0x50000000 / 0x80000000 = 62.50%)

BB#1: derived from LLVM BB %for.body.preheader
    Live Ins: %R16 %R17
    Predecessors according to CFG: BB#0
    Successors according to CFG: BB#2(?%)

BB#2: derived from LLVM BB %for.body
    Live Ins: %D2 %R16 %R17 %R29 %R30 %R31
    Predecessors according to CFG: BB#1 BB#2
	%R17<def> = A2_addi %R17<kill>, -1
	%R16<def> = A2_addi %R16<kill>, 8

-> # After Hexagon Copy-To-Combine Pass:

BB#0: derived from LLVM BB %entry
    Live Ins: %R0 %R1 %D8 %D8
	%D8<def> = A2_combinew %R0<kill>, %R1<kill>

BB#1: derived from LLVM BB %for.body.preheader
    Live Ins: %R16 %R17
    Predecessors according to CFG: BB#0
    Successors according to CFG: BB#2(?%)

BB#2: derived from LLVM BB %for.body
    Live Ins: %D2 %R16 %R17 %R29 %R30 %R31
	%R17<def> = A2_addi %R17<kill>, -1
	%R16<def> = A2_addi %R16<kill>, 8

The first question for me is if this transformation is entirely correct. Should also implicit-defs of %R16 or %R17 be added to the new instruction? Or should it add %D8 to live-in lists and as implicit-use operands? (The latter alternative seems discouraging due to its complexity).

This patch seems conservatively right though in this context to assume that %D8 is live when any one of its subregs is live (it will make LivePhysRegs in later passes think that all of the subregs are live.)

Quentin, what do you think?

[kparzysz]

More ping.

[kparzysz]

Ping.

[qcolombet]

Hi Krzysztof,

Thanks for your patience, I missed the patch earlier.

I don't like the idea of the if-converter growing the live-in set for no apparent reason. In my opinion, we end up in this situation because other passes did something wrong, like in that case the Copy-To-Combine pass if I understand correctly.

To give a bit more concret on why I don't like it, Matthias recently removed a similar fix in BranchFolding IIRC, that in the end was kidding bugs somewhere else.

Cheers,
-Quentin

[kparzysz]

Changed the approach from making super-register live, to adding implicit uses of sub-registers.

[kparzysz]

Ping.

[kparzysz]

Ping. This is a different solution---it does not change the live-in set.

[qcolombet]

Hi Krzysztof,

We were discussing similar liveness issues in https://reviews.llvm.org/D17257 with Jonas and I believe the right way to fix that would be to switch the live-in sets to RegUnit. The implicit operand would work but they look like a workaround to the actual problem to me.
Adding the RegUnit instead of the PhysReg is easy and could be hidden in the addLiveIn method, removing them is a different story.

Cheers,
-Quentin

[qcolombet]

+Matthias

[kparzysz]

In D23172#549912, @qcolombet wrote:

The implicit operand would work but they look like a workaround to the actual problem to me.

If I understand correctly---the reg unit approach will still add the implicit operands, it will just use reg units to track liveness?

[qcolombet]

If I understand correctly---the reg unit approach will still add the implicit operands, it will just use reg units to track liveness?

You shouldn't need the implicit operands anymore, because the double register would make the two reg unit of the simple register live and the uses would be from those reg unit.
In other words,
live in: D0 (sets reg unit A and B)
use S0 (uses reg unit A)
use S1 (uses reg unit B)
Would be valid without anything else. (Modulo updating the MachineVerifier to check at the RegUnit level).
But again, the problem with the RegUnit approach is that updating the live-ins may be expensive.

I admit I did not spend a lot of time thinking about it.

Cheers,
Q.

[kparzysz]

In D23172#550016, @qcolombet wrote:

You shouldn't need the implicit operands anymore, because the double register would make the two reg unit of the simple register live and the uses would be from those reg unit.

Then I don't understand.

I have an instruction:
d8 = L2_loadrd_io <base-reg>, <offset> # load register double

It then is predicated (assume that no implicit operands are added):
d8 = L2_ploadrdf_io <pred-reg>, <base-reg>, <offset> # load register double if-false

If if-conversion puts that block together with a prior definition of r17 (a subreg of d8), e.g
r17 = <something>
d8 = L2_ploadrdf_io <pred-reg>, <base-reg>, <offset> # load register double if-false
how will the compiler know that the first one is not dead?

[MatzeB]

In D23172#550016, @qcolombet wrote:

If I understand correctly---the reg unit approach will still add the implicit operands, it will just use reg units to track liveness?

You shouldn't need the implicit operands anymore, because the double register would make the two reg unit of the simple register live and the uses would be from those reg unit.
In other words,
live in: D0 (sets reg unit A and B)
use S0 (uses reg unit A)
use S1 (uses reg unit B)
Would be valid without anything else. (Modulo updating the MachineVerifier to check at the RegUnit level).
But again, the problem with the RegUnit approach is that updating the live-ins may be expensive.

I don't see how we could get away without the implicit operands in the if-conversion (without teaching many other parts of the compiler what predicated code is). I wrote a longer explanation in another review where I had to remind myself: https://reviews.llvm.org/D20907#476017

[MatzeB]

Looks fine to me in principle, however I think we can get away with 1 implicit use per clobber at most:

lib/CodeGen/IfConversion.cpp

1119–1123

Would it be more reasonable to check if any subreg is alive and then only add a single implicit use for Reg. Otherwise I'd be concerned that we end up with a large number of implicit-use operands for deep register hierarchies.

[MatzeB]

test/CodeGen/Hexagon/ifcvt-live-subreg.mir

2 ↗

(On Diff #70850)

Always good to see a small and to the point test.

• I'd add a sentence about what is tested.
• It's good style to have at least one CHECK-LABEL: name: foo in case someone adds more functions later (also sometimes protects you from accidentally matching random output before the function starts).
• I'd also go and CHECK for all if-converted instructions to make it a bit more obvious what is happening here.

[kparzysz]

lib/CodeGen/IfConversion.cpp

1119–1123

I've been thinking about it. What about this case?

Live-in: %H
if (...) {
  // Define/use super-reg.
  %H:L = ...
  ... = %H:L
}
// %H is still live here
... = %H

After if-conversion we would end up with something like

%H:L = predicated ..., %H:L<imp-use>
... = predicated %H:L

Wouldn't the implicit use be invalid (since %L is not defined)?

[kparzysz]

lib/CodeGen/IfConversion.cpp

1119–1123

The %H:L above is meant to represent a super-register consisting of two halves: %H and %L respectively.

[MatzeB]

lib/CodeGen/IfConversion.cpp

1119–1123

Using partially defined registers is fine. (It would only be invalid if it would be completely undefined).

[kparzysz]

Applied suggested changes.

[MatzeB]

LGTM

[kparzysz]

Committed in r282626. Forgot to add link in the commit message, so closing manually.

lib/CodeGen/IfConversion.cpp

const TargetRegisterInfo *TRI = MI.getParent()->getParent()
     ->getSubtarget().getRegisterInfo();
 
   // Before stepping forward past MI, remember which regs were live
   // before MI. This is needed to set the Undef flag only when reg is
   // dead.
   SparseSet<unsigned> LiveBeforeMI;
   LiveBeforeMI.setUniverse(TRI->getNumRegs());
   for (auto &Reg : Redefs)
-    LiveBeforeMI.insert(Reg);
+    for (MCSuperRegIterator S(Reg, TRI, true); S.isValid(); ++S)
+      LiveBeforeMI.insert(*S);
 
   SmallVector<std::pair<unsigned, const MachineOperand*>, 4> Clobbers;
   Redefs.stepForward(MI, Clobbers);
 
   // Now add the implicit uses for each of the clobbered values.
   for (auto Reg : Clobbers) {
     // FIXME: Const cast here is nasty, but better than making StepForward
     // take a mutable instruction instead of const.
for (auto Reg : Clobbers) {
     assert(Op.isReg() && "Register operand required");
     if (Op.isDead()) {
       // If we found a dead def, but it needs to be live, then remove the dead
       // flag.
       if (Redefs.contains(Op.getReg()))
         Op.setIsDead(false);
     }
     if (LiveBeforeMI.count(Reg.first))
       MIB.addReg(Reg.first, RegState::Implicit);
   }
 }
 
 /**
  * Remove kill flags from operands with a registers in the @p DontKill set.
  */
 static void RemoveKills(MachineInstr &MI, const LivePhysRegs &DontKill) {
   for (MIBundleOperands O(MI); O.isValid(); ++O) {
     if (!O->isReg() || !O->isKill())
       continue;
     if (DontKill.contains(O->getReg()))
       O->setIsKill(false);

test/CodeGen/Hexagon/ifcvt-impuse.ll

+; RUN: llc -march=hexagon < %s | FileCheck %s
+; CHECK: r17:16 = combine(r0, r1)
+
+; After if-conversion, the early exit is predicated, together with the
+; restore of d8:
+;   if (!p0.new) r17:16 = memd(r29 + #0)
+;
+; If the if-converter does not add implicit uses to this predicated load,
+; the copy-in from d0 to d8 will become dead. The if-converter can miss
+; this, because the live-in information contains r16 and r17, but not d8
+; explicitly.
+
+target triple = "hexagon"
+
+define double @fred(i32 %n, double* nocapture readonly %a) local_unnamed_addr #0 {
+entry:
+  %cmp5 = icmp slt i32 %n, 1
+  br i1 %cmp5, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %sum.07 = phi double [ %add, %for.body ], [ 0.000000e+00, %for.body.preheader ]
+  %i.06 = phi i32 [ %inc, %for.body ], [ 1, %for.body.preheader ]
+  %sub = add nsw i32 %i.06, -1
+  %arrayidx = getelementptr inbounds double, double* %a, i32 %sub
+  %0 = load double, double* %arrayidx, align 8
+  %add = fadd double %sum.07, %0
+  %inc = add nuw nsw i32 %i.06, 1
+  %exitcond = icmp eq i32 %i.06, %n
+  br i1 %exitcond, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  %sum.0.lcssa = phi double [ 0.000000e+00, %entry ], [ %add, %for.end.loopexit ]
+  ret double %sum.0.lcssa
+}
+
+attributes #0 = { nounwind optsize readonly "target-cpu"="hexagonv55" }