Page MenuHomePhabricator

[IfConversion] More simple, correct dead/kill liveness handling
ClosedPublic

Authored by JesperAntonsson on Sep 8 2017, 1:17 AM.

Details

Summary

The MachineVerifier reports of issues with liveness after IfConversion in randomized testing for our out-of-tree target. This patch is replacing the complex handling of dead/kill-flags with a simpler, reusable subpass that recomputes a BB's dead/kill flags at the end of each transformation.

The recomputation may be slightly different and a few Hexagon MIR test were adjusted to reflect this.

Diff Detail

Repository
rL LLVM

Event Timeline

JesperAntonsson created this revision.Sep 8 2017, 1:17 AM
kparzysz added inline comments.Sep 8 2017, 9:21 AM
lib/CodeGen/MachineBasicBlock.cpp
456 ↗(On Diff #114310)

Are you seeing any cases where a "dead" flag would be removed? This is somewhat concerning. Whether a use is a kill or not depends on the ordering relative to other uses, which can change. Whether a def is dead or not is more closely related to the program's semantics: once a def is dead, new uses should not really appear.

kparzysz edited edge metadata.Sep 8 2017, 9:29 AM

This seems like a reasonable way of handling it, but I'd like Matthias and Kyle to comment on this as well.

lib/CodeGen/MachineBasicBlock.cpp
456 ↗(On Diff #114310)

I thought about it for a bit---I guess that a dead def from a side A of a diamond can appear to "reach" a use from side B of the diamond after predication, if A precedes B in the predicated code.

iteratee edited edge metadata.Sep 8 2017, 10:53 AM

This looks fine overall to me.

lib/CodeGen/MachineBasicBlock.cpp
449 ↗(On Diff #114310)

Would it be worth it to have an early exit from the loop when IsLive is true?

MatzeB edited edge metadata.Sep 8 2017, 10:55 AM

This is a very good idea!

lib/CodeGen/MachineBasicBlock.cpp
425 ↗(On Diff #114310)
  • I'd put this function in LivePhysRegs.h maybe next to computeLiveIns() and not make it a member of MachineBasicBlock.
  • How about changing this to also add kill/dead flags (see below) and calling it recomputeLivenessFlags()?
  • It may or may not be a good idea to break this up into a more flexible function: recomputeLivenessFlagsInRange(LivePhysRegs &LiveRegs, iterator_range<MachineBasicBlock::reverse_iterator> Range); so that you can apply it to arbitrary ranges inside a basic block given a LivePhysRegs with liveness behind the range. You could still have a convenience function that processes a whole block and uses this internally.
426 ↗(On Diff #114310)

Try using references for things that cannot be nullptr.

429–434 ↗(On Diff #114310)

Better use LiveRegs.addLiveOutsNoPristines() instead of doing the loop yourself. It will get some corner cases like return blocks right.

433 ↗(On Diff #114310)

(writing MachineBasicBlock * instead of auto is friendlier to readers.)

437–438 ↗(On Diff #114310)

Are DebugValues allowed to be inside instruction bundles? I'd probably go for if (MO->isDebug()) in the following loop instead of using MI.isDebugValue() here.

446 ↗(On Diff #114310)

Maybe add an assert(TargetRegisterInfo::isPhysReg(Reg)) here to make things explicit?

447–449 ↗(On Diff #114310)

This is expensive, and not necessary I think:

454–457 ↗(On Diff #114310)

How about:

if (MO->isDef())
  MO->setIsDead(!LiveRegs.available(MRI, Reg));
if (MO->readsReg())
  MO->setIsKill(!LiveRegs.available(MRI, Reg));

Thanks for the reviews, everybody! Here I'm submitting an updated patch based on Matthias' suggestions.

Hope I covered everything, shout if not. (The range-based method extraction might be a good idea, but I'm leaving that to anyone that has use for it.)

As far as I have understood, DebugValues are not allowed in bundles, but I moved the check to the operand anyway. But the question made me think about bundling... Do I need to go inside bundles to adjust as well? I'm only doing bundle heads here.

Since I'm now adding flags as well, I had to update a few tests more.

kparzysz added inline comments.Sep 11 2017, 7:59 AM
lib/CodeGen/LivePhysRegs.cpp
294 ↗(On Diff #114596)

It doesn't look like this code going to add a kill flag to the use of r0 in the add.

r0 = add r0, r1
... = r0
lib/CodeGen/LivePhysRegs.cpp
294 ↗(On Diff #114596)

True, good catch. It would also remove pre-existing kill flags.

Seems I should first set dead flags like I do now, then do a partial stepBackward over (non-early-clobber?) defs only, before I loop over use-MOs to set kill flags, and then do the remaining stepBackward? Would that be a good approach?

MatzeB added inline comments.Sep 11 2017, 10:08 AM
lib/CodeGen/LivePhysRegs.cpp
294 ↗(On Diff #114596)

Should be easy enough to factor out the def/use loops in stepBackward() into two functions that can be used individually.

This is a new patch that will handle the issue Krzysztof pointed out. Some more Hexagon tests affected. Makes me wonder: Is it ok to say that a predicated instruction's use of a register is killed if it is defined by the same instruction?

JesperAntonsson marked 3 inline comments as done.Sep 13 2017, 2:30 AM

This new implementation doesn't run cleanly with our extended test suite. I have to look a bit more into it.

I just started a test run on a Hexagon suite, but I wonder if the anti-dependence breaker could be a problem. This is regarding the question of whether the implicit uses on predicated instructions should be killed or not. BTW, the same argument applies to tied uses. Even though the live ranges seem to end/start at that instruction, the register cannot be renamed in only one of them. This differentiates those instructions from a case of unrelated use/def coincidentally using the same register (as was in the example: r0 = add r0, r1).

To add to my previous comment---there is a plan to eliminate kill flags in the future (as I was told), so passes the rely on those will eventually need to be modified. If it's the presence of kill flags on predicated instructions (and tied uses) that is causing problems, maybe it would be a good thing to address that in the passes that are exploiting that to generate wrong code. It would imply more work, so I guess the answer depends on how much more work it would be.

Good news everyone... The Hexagon test suite passed.

I just started a test run on a Hexagon suite, but I wonder if the anti-dependence breaker could be a problem. This is regarding the question of whether the implicit uses on predicated instructions should be killed or not. BTW, the same argument applies to tied uses. Even though the live ranges seem to end/start at that instruction, the register cannot be renamed in only one of them. This differentiates those instructions from a case of unrelated use/def coincidentally using the same register (as was in the example: r0 = add r0, r1).

For instruction that def/use the same vreg (tied or not) it shouldn't matter whether we add a kill flag. That is either way it is obvious that the def will overwrite the register. But given that it doesn't matter we can just as well do it.
While it feels slightly off for tied operands I don't think it matters there either as the no-partially-renaming semantics stems from the fact that the tied bit is set not from present or missing kill flags.

To add to my previous comment---there is a plan to eliminate kill flags in the future (as I was told), so passes the rely on those will eventually need to be modified. If it's the presence of kill flags on predicated instructions (and tied uses) that is causing problems, maybe it would be a good thing to address that in the passes that are exploiting that to generate wrong code. It would imply more work, so I guess the answer depends on how much more work it would be.

Yes we are in the process of eliminating kill flags. Ideally you should be able to remove all kill flags from a machine function and still generate exactly the same code. I think we are already there for aarch64 and x86 (though I didn't do in-depth validation yet). However I think we should work towards that goal delibarately: When writing new code make sure it does not read/depend on kill flags, at the same time when changing existing code I'd avoid removing kill flags to avoid unexpected performance swings on targets that still read kill flags.

MatzeB accepted this revision.Sep 13 2017, 10:34 AM

LGTM with nitpicks.

include/llvm/CodeGen/LivePhysRegs.h
111–113 ↗(On Diff #115004)

Maybe call this removeDefs?

115–116 ↗(On Diff #115004)

Call this addUses?

This revision is now accepted and ready to land.Sep 13 2017, 10:34 AM
JesperAntonsson edited the summary of this revision. (Show Details)

I found and fixed the reason our randomized tests didn't run cleanly. It was essentially that stepBackwards removed defined regs from the set even if the instruction was predicated. That meant a dominating def could be marked dead, which is wrong. The reason I found this is that I use the new recompute function also in a later stage in our out-of-tree backend, and that went bad when I started to add faulty deads. If I understand it correctly, this is a bug in the current implementation of LivePhysRegs.

I fixed this by adding an early return to removeDefs() if the instruction is predicated. NB this does not recognize that a sequence of predicated instructions may combine to define a reg with certainty. Thus we might miss an opportunity to determine a reg isn't live just before such a sequence and even remove such information if it was there beforehand. I think this has low impact, though.

I found and fixed the reason our randomized tests didn't run cleanly. It was essentially that stepBackwards removed defined regs from the set even if the instruction was predicated.

It's supposed to do that. This is exactly the reason why we add implicit uses to predicated instructions if there is a live def reaching it.

Ah, thanks. Then the fault is in our backend, that we somehow miss to add that imp-use in some circumstances. My previous patch is probably better, then. I'll reupload that with Matthias suggested name changes. :-)

Reverted the changes in the previous patch, except for the name improvements. I guess we can land this, then. I don't have the privileges yet, so I'm grateful for help with that. :-)

This revision was automatically updated to reflect the committed changes.

I found and fixed the reason our randomized tests didn't run cleanly. It was essentially that stepBackwards removed defined regs from the set even if the instruction was predicated.

It's supposed to do that. This is exactly the reason why we add implicit uses to predicated instructions if there is a live def reaching it.

Indeed, generic codegen in llvm has no notion of predication. That's why we do the ifconversion pass really late and then "fake" liveness with those extra operands to make sure everything that needs to be appears live even when the code has no notion of predication (conservatively correct). We should not need any tweaks for predication outside the ifconversion pass.