[IfConversion] Bugfix: don't add Undef flag on use if reg is live.

[jonpa]

Summary

IfConversion will call UpdatePredRedefs() after an MI has been predicated by target, to update the liveness tracking, and also to add implicit use operands on MI (for the register that has become conditionally def:ed). IfConversion was always adding these use operands with the Undef flag, which caused later passes to get into trouble, since that register will incorrectly be considered dead before MI.

This was discovered with SystemZ, where the following transformation would take place where it shouldn't:

%R4L<def> = L %R15D, 440, %noreg; mem:LD4[FixedStack5]
%R4H<def> = IIHF 1000
%R4L<def> = LOCR %R10L<kill>, 14, 10, %CC<imp-use>, %R4L<imp-use,undef>

>

%R4L<def> = L %R15D, 440, %noreg; mem:LD4[FixedStack5]
%R4D<def> = LLIHL 1000
%R4L<def> = LOCR %R10L<kill>, 14, 10, %CC<imp-use>, %R4L<imp-use,undef>

LivePhysRegs thinks during the SystemZShortenInst pass that %R4L is dead at IIHF and replaces it with an LLIHL wich overwrites %R4L. The LOCR (Load On Condition Register) produced by IfConversion, has the bad undef flag.

This patch makes sure IfConversion does not add the Undef flag if the register is live.

Perhaps it would be possible to extend stepForward() to return a set of registers "live-before" instead of constructing a new LiveBeforeMI set as with this patch? Or, since stepForward() is only used by IfConversion, perhaps it could even be merged with UpdatePredRedefs somehow..?

[jonpa]

A follow-up question here is if it is really such a good idea to just throw on extra implicit use-ops on the predicated MI? Wouldn't it generally make more sense in the case where a register is conditionally defined to model this as a tied use-operand?

[kparzysz]

In D20907#451165, @jonpa wrote:

A follow-up question here is if it is really such a good idea to just throw on extra implicit use-ops on the predicated MI? Wouldn't it generally make more sense in the case where a register is conditionally defined to model this as a tied use-operand?

The register does not actually have to be defined prior to the predicated definition. If you have the tied use, you will need to mark it as <undef> in such cases.

[jonpa]

ping.

Is this patch ok to commit? My question was regarding design issues, but this is still a needed bugfix.

[qcolombet]

Hi Jonas,

Undef does not mean dead, just that this specific use does not care what is in the register. So it can be anything.

/// IsUndef - True if this register operand reads an "undef" value, i.e. the
/// read value doesn't matter.

Some passes may make this assumption and we should fix them. Which pass does the invalid transformation?

Cheers,
-Quentin

[qcolombet]

Unless I wasn't clear, a register may be live across an instruction even if it is undef for that instruction.

Note: That probably mean that the definition of that register could be move further done to make the register dead for that use, but that is a different story.

[kparzysz]

In D20907#461968, @jonpa wrote:

My question was regarding design issues, but this is still a needed bugfix.

In terms of complexity there is no benefit of adding tied uses, since you'd need to keep track of their liveness the same way as with implicit uses. If you have a predicated instruction that defines a register that has already been defined prior to that point, the implicit use/tied use would have to be "not undef", otherwise it could get reordered with the prior definition.

[jonpa]

Quentin:
LivePhysRegs was not assuming that an undef use means the register is dead, it rather misses the fact that the register was indeed live due to the (erroneous) undef flag.

Looking at the example code: in order for LivePhysRegs to discover that %R4L is live, there must be a use of %R4L on the third instruction (using stepBackward()). That can't be an undef use, since that does not signal liveness. Therfore, it must be a use op without the undef flag, which is exactly what the patch achieves.

I am a bit confused about the meaning/purpose of such implicit undef-use operands? Why add the implicit operand in UpdatePredRedefs() if it is undef? Instruction order would be maintained without it due to the register definitions, right? And it does not help liveness tracking.

Krzysztof:
My concern for using tied operands was merely about having a better model of the instruction which could be verified. I am thinking that for a predicated instruction, the input operand *must* be present and *must not* be undef if reg is live, as it is the value of the instruction if it becomes a noop. Othwerwise, the liveness is not properly modelled. Therefore, it would be preferred to model this operand explicitly, as a tied op. Just a thought...

[qcolombet]

Hi Jonas,

Let us step back a little bit. I actually did not read any code when commenting the first time, I was clarifying the intended behavior of the undef flag wrt liveness :).
Now, I have read the relevant part of IfConversion and I can give more appropriate guidance.

[jonpa]

Given that we want the liveness to remain out of the business of the predication, I believe the proper fix is to set implicit use for all live variables. I.e., move your test on the setting of the implicit use, not in the undef flag.

I updated the patch according to your suggestion, so that the behaviour is simply to add an implicit-use operand of the reg (only) if it is live.

[qcolombet]

LGTM

[jonpa]

Commited as r273545.

[jonpa]

Revert r273545, "[IfConversion] Bugfix: Don't use undef flag while adding use operands."
as it caused PR28295.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@273707 91177308-0d34-0410-b5e6-96231b3b80d8

[jonpa]

Patch reverted by Peter Collingbourne, due to https://llvm.org/bugs/show_bug.cgi?id=28295.

I tried Peters test case, and this is what happened:

BB#9: derived from LLVM BB %if.end5
    Live Ins: %R4 %R5 %R8 %R10 %R11
    Predecessors according to CFG: BB#7
...
	%R0<def> = tMOVr %R9, pred:14, pred:%noreg
	tBL pred:14, pred:%noreg, <ga:@_ZN1CC1Ev>, <regmask %LR %D8 %D9 %D10 %D11 %D12 %D13 %D14 %D15 %Q4 %Q5 %Q6 %Q7 %R0 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R11 %S16 %S17 %S18 %S19 %S20 %S21 %S22 %S23 %S24 %S25 %S26 %S27 %S28 %S29 %S30 %S31 %D8_D10 %D9_D11 %D10_D12 %D11_D13 %D12_D14 %D13_D15 %Q4_Q5 %Q5_Q6 %Q6_Q7 %Q4_Q5_Q6_Q7 %R4_R5 %R6_R7 %R8_R9 %R10_R11 %D8_D9_D10 %D9_D10_D11 %D10_D11_D12 %D11_D12_D13 %D12_D13_D14 %D13_D14_D15 %D8_D10_D12 %D9_D11_D13 %D10_D12_D14 %D11_D13_D15 %D8_D10_D12_D14 %D9_D11_D13_D15 %D9_D10 %D11_D12 %D13_D14 %D9_D10_D11_D12 %D11_D12_D13_D14>, %LR<imp-def,dead>, %SP<imp-use>, %R0<imp-use>, %SP<imp-def>
	tBL pred:14, pred:%noreg, <ga:@_ZN1CanE1A>, <regmask %LR %D8 %D9 %D10 %D11 %D12 %D13 %D14 %D15 %Q4 %Q5 %Q6 %Q7 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R11 %S16 %S17 %S18 %S19 %S20 %S21 %S22 %S23 %S24 %S25 %S26 %S27 %S28 %S29 %S30 %S31 %D8_D10 %D9_D11 %D10_D12 %D11_D13 %D12_D14 %D13_D15 %Q4_Q5 %Q5_Q6 %Q6_Q7 %Q4_Q5_Q6_Q7 %R4_R5 %R6_R7 %R8_R9 %R10_R11 %D8_D9_D10 %D9_D10_D11 %D10_D11_D12 %D11_D12_D13 %D12_D13_D14 %D13_D14_D15 %D8_D10_D12 %D9_D11_D13 %D10_D12_D14 %D11_D13_D15 %D8_D10_D12_D14 %D9_D11_D13_D15 %D9_D10 %D11_D12 %D13_D14 %D9_D10_D11_D12 %D11_D12_D13_D14>, %LR<imp-def,dead>, %SP<imp-use>, %R0<imp-use>, %SP<imp-def>
	t2CMPri %R8<kill>, 0, pred:14, pred:%noreg, %CPSR<imp-def>

>>>	%R0<def> = tMOVr %R11<kill>, pred:1, pred:%CPSR, %R0<imp-use>

...

    Successors according to CFG: BB#10(?%)

*** Bad machine code: Using an undefined physical register ***
- function:    _ZN1F5m_fn2EP1DPNS_18ClientCallBehaviorE
- basic block: BB#9 if.end5 (0x9443838)
- instruction: %R0<def> = tMOVr
- operand 4:   %R0<imp-use>

IfConversion::UpdatePredRedefs() has added the %R0<imp-use> operand to the tMOVr (without patch there would also have been an undef flag).
The second tBL does not include %R0 in the regmask, which should mean a value is returned in %R0, right?
This should then mean that %R0 *is* actually live, and that either the MachineVerifier should have noticed this due to the regmask (like LivePhysReg does),
or perhaps the tBL should have had an extra %R0<def>, in case that would generally be expected.

Any thoughts on this, anyone?

[jonpa]

Returned, not necessary, but clobbered, yes.

OK, if the second tBL just clobbers it, I guess at that point %R0 is actually dead.

To me the bug seems to come from the fact we thought it is live whereas it is not. Could you check why we think it is live before tMOVr?

IfConverter::IfConvertTriangle() gets to work on:

BB#11: derived from LLVM BB %if.end5
    Live Ins: %R4 %R5 %R8 %R10 %R11
    Predecessors according to CFG: BB#9
	%R9<def> = t2ADDri %R4, 32, pred:14, pred:%noreg, opt:%noreg
	%R0<def> = t2ADDri %R4, 16, pred:14, pred:%noreg, opt:%noreg
	tBL pred:14, pred:%noreg, <ga:@_ZN1B5m_fn1Ev>, <regmask %LR %D8 %D9 %D10 %D11 %D12 %D13 %D14 %D15 %Q4 %Q5 %Q6 %Q7 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R11 %S16 %S17 %S18 %S19 %S20 %S21 %S22 %S23 %S24 %S25 %S26 %S27 %S28 %S29 %S30 %S31 %D8_D10 %D9_D11 %D10_D12 %D11_D13 %D12_D14 %D13_D15 %Q4_Q5 %Q5_Q6 %Q6_Q7 %Q4_Q5_Q6_Q7 %R4_R5 %R6_R7 %R8_R9 %R10_R11 %D8_D9_D10 %D9_D10_D11 %D10_D11_D12 %D11_D12_D13 %D12_D13_D14 %D13_D14_D15 %D8_D10_D12 %D9_D11_D13 %D10_D12_D14 %D11_D13_D15 %D8_D10_D12_D14 %D9_D11_D13_D15 %D9_D10 %D11_D12 %D13_D14 %D9_D10_D11_D12 %D11_D12_D13_D14>, %LR<imp-def,dead>, %SP<imp-use>, %R0<imp-use>, %SP<imp-def>
	%R0<def> = tMOVr %R9, pred:14, pred:%noreg
	tBL pred:14, pred:%noreg, <ga:@_ZN1CC1Ev>, <regmask %LR %D8 %D9 %D10 %D11 %D12 %D13 %D14 %D15 %Q4 %Q5 %Q6 %Q7 %R0 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R11 %S16 %S17 %S18 %S19 %S20 %S21 %S22 %S23 %S24 %S25 %S26 %S27 %S28 %S29 %S30 %S31 %D8_D10 %D9_D11 %D10_D12 %D11_D13 %D12_D14 %D13_D15 %Q4_Q5 %Q5_Q6 %Q6_Q7 %Q4_Q5_Q6_Q7 %R4_R5 %R6_R7 %R8_R9 %R10_R11 %D8_D9_D10 %D9_D10_D11 %D10_D11_D12 %D11_D12_D13 %D12_D13_D14 %D13_D14_D15 %D8_D10_D12 %D9_D11_D13 %D10_D12_D14 %D11_D13_D15 %D8_D10_D12_D14 %D9_D11_D13_D15 %D9_D10 %D11_D12 %D13_D14 %D9_D10_D11_D12 %D11_D12_D13_D14>, %LR<imp-def,dead>, %SP<imp-use>, %R0<imp-use>, %SP<imp-def>
	tBL pred:14, pred:%noreg, <ga:@_ZN1CanE1A>, <regmask %LR %D8 %D9 %D10 %D11 %D12 %D13 %D14 %D15 %Q4 %Q5 %Q6 %Q7 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R11 %S16 %S17 %S18 %S19 %S20 %S21 %S22 %S23 %S24 %S25 %S26 %S27 %S28 %S29 %S30 %S31 %D8_D10 %D9_D11 %D10_D12 %D11_D13 %D12_D14 %D13_D15 %Q4_Q5 %Q5_Q6 %Q6_Q7 %Q4_Q5_Q6_Q7 %R4_R5 %R6_R7 %R8_R9 %R10_R11 %D8_D9_D10 %D9_D10_D11 %D10_D11_D12 %D11_D12_D13 %D12_D13_D14 %D13_D14_D15 %D8_D10_D12 %D9_D11_D13 %D10_D12_D14 %D11_D13_D15 %D8_D10_D12_D14 %D9_D11_D13_D15 %D9_D10 %D11_D12 %D13_D14 %D9_D10_D11_D12 %D11_D12_D13_D14>, %LR<imp-def,dead>, %SP<imp-use>, %R0<imp-use>, %SP<imp-def>
	t2CMPri %R8<kill>, 0, pred:14, pred:%noreg, %CPSR<imp-def>
	t2Bcc <BB#13>, pred:0, pred:%CPSR<kill>
    Successors according to CFG: BB#13(0x30000000 / 0x80000000 = 37.50%) BB#12(0x50000000 / 0x80000000 = 62.50%)

BB#12: derived from LLVM BB %if.then9
    Live Ins: %R4 %R5 %R10 %R11
    Predecessors according to CFG: BB#11
	%R0<def> = tMOVr %R11<kill>, pred:1, pred:%CPSR
	tBL pred:14, pred:%noreg, <ga:@_ZN1F5m_fn3Ev>, <regmask %LR %D8 %D9 %D10 %D11 %D12 %D13 %D14 %D15 %Q4 %Q5 %Q6 %Q7 %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R11 %S16 %S17 %S18 %S19 %S20 %S21 %S22 %S23 %S24 %S25 %S26 %S27 %S28 %S29 %S30 %S31 %D8_D10 %D9_D11 %D10_D12 %D11_D13 %D12_D14 %D13_D15 %Q4_Q5 %Q5_Q6 %Q6_Q7 %Q4_Q5_Q6_Q7 %R4_R5 %R6_R7 %R8_R9 %R10_R11 %D8_D9_D10 %D9_D10_D11 %D10_D11_D12 %D11_D12_D13 %D12_D13_D14 %D13_D14_D15 %D8_D10_D12 %D9_D11_D13 %D10_D12_D14 %D11_D13_D15 %D8_D10_D12_D14 %D9_D11_D13_D15 %D9_D10 %D11_D12 %D13_D14 %D9_D10_D11_D12 %D11_D12_D13_D14>, %LR<imp-def,dead>, %SP<imp-use>, %R0<imp-use>, %SP<imp-def>
    Successors according to CFG: BB#13(?%)

BB#13: derived from LLVM BB %cleanup
    Live Ins: %D8 %D9 %D10 %D11 %D12 %D13 %D14 %D15 %Q4 %Q5 %Q6 %Q7 %R0 %R4 %R5 %R10 %S16 %S17 %S18 %S19 %S20 %S21 %S22 %S23 %S24 %S25 %S26 %S27 %S28 %S29 %S30 %S31 %D6_D8 %D7_D9 %D8_D10 %D9_D11 %D10_D12 %D11_D13 %D12_D14 %D13_D15 %D14_D16 %D15_D17 %Q3_Q4 %Q4_Q5 %Q5_Q6 %Q6_Q7 %Q7_Q8 %Q1_Q2_Q3_Q4 %Q2_Q3_Q4_Q5 %Q3_Q4_Q5_Q6 %Q4_Q5_Q6_Q7 %Q5_Q6_Q7_Q8 %Q6_Q7_Q8_Q9 %Q7_Q8_Q9_Q10 %R0_R1 %R4_R5 %R10_R11 %D6_D7_D8 %D7_D8_D9 %D8_D9_D10 %D9_D10_D11 %D10_D11_D12 %D11_D12_D13 %D12_D13_D14 %D13_D14_D15 %D14_D15_D16 %D15_D16_D17 %D4_D6_D8 %D5_D7_D9 %D6_D8_D10 %D7_D9_D11 %D8_D10_D12 %D9_D11_D13 %D10_D12_D14 %D11_D13_D15 %D12_D14_D16 %D13_D15_D17 %D14_D16_D18 %D15_D17_D19 %D2_D4_D6_D8 %D3_D5_D7_D9 %D4_D6_D8_D10 %D5_D7_D9_D11 %D6_D8_D10_D12 %D7_D9_D11_D13 %D8_D10_D12_D14 %D9_D11_D13_D15 %D10_D12_D14_D16 %D11_D13_D15_D17 %D12_D14_D16_D18 %D13_D15_D17_D19 %D14_D16_D18_D20 %D15_D17_D19_D21 %D7_D8 %D9_D10 %D11_D12 %D13_D14 %D15_D16 %D5_D6_D7_D8 %D7_D8_D9_D10 %D9_D10_D11_D12 %D11_D12_D13_D14 %D13_D14_D15_D16 %D15_D16_D17_D18 %D8 %D9 %D10 %D11 %D12 %D13 %D14 %D15 %Q4 %Q5 %Q6 %Q7 %R4 %R5 %R10 %S16 %S17 %S18 %S19 %S20 %S21 %S22 %S23 %S24 %S25 %S26 %S27 %S28 %S29 %S30 %S31 %D6_D8 %D7_D9 %D8_D10 %D9_D11 %D10_D12 %D11_D13 %D12_D14 %D13_D15 %D14_D16 %D15_D17 %Q3_Q4 %Q4_Q5 %Q5_Q6 %Q6_Q7 %Q7_Q8 %Q1_Q2_Q3_Q4 %Q2_Q3_Q4_Q5 %Q3_Q4_Q5_Q6 %Q4_Q5_Q6_Q7 %Q5_Q6_Q7_Q8 %Q6_Q7_Q8_Q9 %Q7_Q8_Q9_Q10 %R4_R5 %R10_R11 %D6_D7_D8 %D7_D8_D9 %D8_D9_D10 %D9_D10_D11 %D10_D11_D12 %D11_D12_D13 %D12_D13_D14 %D13_D14_D15 %D14_D15_D16 %D15_D16_D17 %D4_D6_D8 %D5_D7_D9 %D6_D8_D10 %D7_D9_D11 %D8_D10_D12 %D9_D11_D13 %D10_D12_D14 %D11_D13_D15 %D12_D14_D16 %D13_D15_D17 %D14_D16_D18 %D15_D17_D19 %D2_D4_D6_D8 %D3_D5_D7_D9 %D4_D6_D8_D10 %D5_D7_D9_D11 %D6_D8_D10_D12 %D7_D9_D11_D13 %D8_D10_D12_D14 %D9_D11_D13_D15 %D10_D12_D14_D16 %D11_D13_D15_D17 %D12_D14_D16_D18 %D13_D15_D17_D19 %D14_D16_D18_D20 %D15_D17_D19_D21 %D7_D8 %D9_D10 %D11_D12 %D13_D14 %D15_D16 %D5_D6_D7_D8 %D7_D8_D9_D10 %D9_D10_D11_D12 %D11_D12_D13_D14 %D13_D14_D15_D16 %D15_D16_D17_D18
    Predecessors according to CFG: BB#12 BB#11
	%R0<def> = t2MOVi 1, pred:14, pred:%noreg, opt:%noreg
	%R9<def> = t2ADDri %R6, 28, pred:14, pred:%noreg, opt:%noreg
Successors according to CFG: BB#14(?%)

Before predicating BB#12, it does

// Initialize liveins to the first BB. These are potentially redefined by
// predicated instructions.
Redefs.init(TRI);
Redefs.addLiveIns(*CvtBBI->BB);
Redefs.addLiveIns(*NextBBI->BB);

Here %R0 gets inserted into Redefs, since it is live into BB#13!

First of all, if you ask me, I'd say that the Live Ins list is suspiciously long for BB#13. I have seen and reported bad live-in lists before: https://llvm.org/bugs/show_bug.cgi?id=25263. Another point is that %R0 is actually not really live-in to BB#13, since it is overwritten unconditionally by the t2MOVi.

Regardless of live-in lists correctness, I am thinking that IfConversion should learn to not think that a live-out reg is live into both successors here. After all, it should not be impossible to have e.g. unoptimized cases where you define a reg, and conditionally redefine it in another block, or?

BTW Quentin: I do not see your post here on Phabricator for some reason. Did you perhaps just reply to the e-mail (which perhaps should have worked...)?

[llvm-commits]

Hi Jonas,

[jonpa]

Matthias, from what I can see you have some experience with this part of IfConversion.cpp. Perhaps you could give some advice on or even fix this problem? In short, a bug in IfConversion was found and fixed, but when patch was applied, we ran into a problem relating to Redefs - see above.

I am now on vacation, and cannot not fix IfConversion right now, so if anybody could take the time that would be great, as this is a bug that should be fixed ASAP.

[MatzeB]

In D20907#473455, @jonpa wrote:

Matthias, from what I can see you have some experience with this part of IfConversion.cpp. Perhaps you could give some advice on or even fix this problem? In short, a bug in IfConversion was found and fixed, but when patch was applied, we ran into a problem relating to Redefs - see above.

I am now on vacation, and cannot not fix IfConversion right now, so if anybody could take the time that would be great, as this is a bug that should be fixed ASAP.

It has been a while since I worked on the IfConversion pass.

Just to document the problem for myself and the record: The current way of modeling predicated instructions as a sequence of instructions is a bad fit to our expectations of how read/write operands work. We expect a read/write operand to always read/write the register which may not be true for a predicated instruction that isn't executed. We get by by cheating and adding enough def/use operands until liveness seemingly makes sense even if you are not aware of the predication effects. To give a typical example (I am prefixing the instructions with P0 and P1 to indicate two disjunct predicates):

0      %R1 = ...
10 P0: %R0 = ...
20 P0: %R1 = ...
30 P1: %R0 = %R1
40         = use %R0
50.        = use %R1

The real situation here is:

a) R1 is defined at instruction 0 and this definition is live at the beginning of instruction 30. R1 however is not live at instruction 20, R1 is live after instruction 20 however the value is different from the value live at instruction 0 and 30.
b) R0 is live from instruction 10-40.

We cannot represent most of these subtleties and therefore "fixup" the representation with implicit operands in a way that we can ignore the predication:

a) Value R1 cannot simply become dead without a killing use at instruction 10, we conservatively assume it is still alive instead. We can achieve this here by adding an implicit use operand on instruction 20 which would otherwise kill R1.
b) The R0 definition at instruction 30 would make it look like R0 is undefined so we add another undef use.

The IfConverter currently does those fixups which should be good enough to model the liveness correctly (in a conservative manner). I still consider this somewhat a hack as the relations between defs and uses are bogus after this conversion, we are merely saved by the fact that the IfConversion pass runs really late and we do not have any later passes looking into def/use relationships.

[MatzeB]

In D20907#473455, @jonpa wrote:

Matthias, from what I can see you have some experience with this part of IfConversion.cpp. Perhaps you could give some advice on or even fix this problem? In short, a bug in IfConversion was found and fixed, but when patch was applied, we ran into a problem relating to Redefs - see above.

To come back to this discussion: I added the UpdatePredRedefs() code to achieve the liveness effects stated in my previous post. I have no idea why I used the undef flag, it was one of my first commits to llvm so I assume I misunderstood the semantics back then. So removing this flag is the right call.

To fix calls clobbering a live register; "pseudo" live in the sense that it is only live in our "ignore the predicates" worldview. I believe we have to add a implicit def and(!) and implicit use in the presence of clobbers or dead definitions.

I am now on vacation, and cannot not fix IfConversion right now, so if anybody could take the time that would be great, as this is a bug that should be fixed ASAP.

While all of this is really nasty, it is hardly a new thing. This was broken before my commit in 2013 and as you found out it still is. I try to find time for this soon, but no promises.

[MatzeB]

Phab apparently didn't parse my mail response last time. So just for my own and others records: I believe that r275201 resolved the problems here and you should try pushing this again Jonas!

[jonpa]

The IfConverter currently does those fixups which should be good enough to model the liveness correctly (in a conservative manner). I still consider this somewhat a hack as the relations between defs and uses are bogus after this conversion, we are merely saved by the fact that the IfConversion pass runs really late and we do not have any later passes looking into def/use relationships.

With this patch, it should be conservatively correct, as you say. It would also be possible to teach buildSchedGraph() to skip adding edges where two different predicates are known to be disjoint, i.e. for two defs of the same reg.

To fix calls clobbering a live register; "pseudo" live in the sense that it is only live in our "ignore the predicates" worldview. I believe we have to add a implicit def and(!) and implicit use in the presence of clobbers or dead definitions.

I am not following why predicating a call with a regmask would require adding any extra operands at all - do you have an example?

I believe that r275201 resolved the problems here and you should try pushing this again Jonas!

Great about the live-in lists :-)

Still seem to me though, that IfConversion should be fixed to have the right liveness tracking. According to earlier discussion, it is just not true that a reg that is live into one successor is live into both successors, and therefore I still think these lines needs fixing:

// Initialize liveins to the first BB. These are potentially redefined by
// predicated instructions.
Redefs.init(TRI);
Redefs.addLiveIns(*CvtBBI->BB);
Redefs.addLiveIns(*NextBBI->BB);

(As Quentin pointed out, this is conservatively correct, but the MachineVerifier complains, because the IfConversion pass may add an implicit-use op on an instruction in one of the successors, while it was not actually live into that MBB, but the other)

[jonpa]

Pushed again as r277571, since everyone agrees this is better to have in trunk.

Do we need to do anything further with IfConversion liveness tracking at this point, or should it really work with correct live-in lists? (I am having a bit of second thoughts about this although we agreed before that this could be possible).

[MatzeB]

In D20907#504458, @jonpa wrote:

Pushed again as r277571, since everyone agrees this is better to have in trunk.

Do we need to do anything further with IfConversion liveness tracking at this point, or should it really work with correct live-in lists? (I am having a bit of second thoughts about this although we agreed before that this could be possible).

I don't know whether there is further work necessary at the moment. However I plan to revisit IfConversion soon anyway, because I am still in the process of making code depend less on kill flags (ideally to the point where we can completely remove them). That means I have to rework the liveness tracking logic in IfConversion anyway to walk backwards instead of forward.

lib/CodeGen/IfConversion.cpp

 void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
   SmallVector<MachineOperand, 4> Cond;
   if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
     BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
 }
 
 /// Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all
-/// values defined in MI which are not live/used by MI.
+/// values defined in MI which are also live/used by MI.
 static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs) {
+  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);
+
   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.
     MachineOperand &Op = const_cast<MachineOperand&>(*Reg.second);
     MachineInstr *OpMI = Op.getParent();
     MachineInstrBuilder MIB(*OpMI->getParent()->getParent(), OpMI);
     if (Op.isRegMask()) {
       // First handle regmasks.  They clobber any entries in the mask which
       // means that we need a def for those registers.
-      MIB.addReg(Reg.first, RegState::Implicit | RegState::Undef);
+      if (LiveBeforeMI.count(Reg.first))
+        MIB.addReg(Reg.first, RegState::Implicit);
 
       // We also need to add an implicit def of this register for the later
       // use to read from.
       // For the register allocator to have allocated a register clobbered
       // by the call which is used later, it must be the case that
       // the call doesn't return.
       MIB.addReg(Reg.first, RegState::Implicit | RegState::Define);
       continue;
     }
     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);
     }
-    MIB.addReg(Reg.first, RegState::Implicit | RegState::Undef);
+    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) {