[UnreachableBlockElim] Use COPY if PHI input is undef

[uabelho]

Summary

If we have

%vreg0<def> = PHI %vreg2<undef>, <BB#0>, %vreg3, <BB#2>; GR32:%vreg0,%vreg2,%vreg3
%vreg3<def,tied1> = ADD32ri8 %vreg0<kill,tied0>, 1, %EFLAGS<imp-def>; GR32:%vreg3,%vreg0

then we can't just change %vreg0 into %vreg3, since %vreg2 is actually
undef. We would have to also copy the undef flag to be able to change the
register.

Instead we deal with this case like other cases where we can't just
replace the register: we insert a COPY. The code creating the COPY already
copied all flags from the PHI input, so the undef flag will be transferred
as it should.

[kparzysz]

Looks good. Thanks.

Could you change the testcase to MIR and only run the unreachable block elimination?

[uabelho]

In D38235#884338, @kparzysz wrote:

Looks good. Thanks.

Could you change the testcase to MIR and only run the unreachable block elimination?

I've tried but I don't understand what happens when I try to make a MIR test.

First weirdness:

Even if I try to stop before unreachable machine block elimination with
llc -optimize-regalloc -O0 -o - -stop-before=unreachable-mbb-elimination
it doesn't stop before? WIth -debug-pass=Executions I see:

[...]
[2017-10-03 10:06:20.575253544] 0x3c95710 Executing Pass 'Process Implicit Definitions' on Function 'f'...
[2017-10-03 10:06:20.575288256] 0x3c95710 Made Modification 'Process Implicit Definitions' on Function 'f'...
[2017-10-03 10:06:20.575317590] 0x3c95710 Freeing Pass 'Process Implicit Definitions' on Function 'f'...
[2017-10-03 10:06:20.575343782] 0x3c95710 Executing Pass 'Remove unreachable machine basic blocks' on Function 'f'...
[2017-10-03 10:06:20.575384081] 0x3c95710 Made Modification 'Remove unreachable machine basic blocks' on Function 'f'...
[2017-10-03 10:06:20.575412158] 0x3c95710 Executing Pass 'Live Variable Analysis' on Function 'f'...
[2017-10-03 10:06:20.575482280] 0x3c95710 Executing Pass 'MachineDominator Tree Construction' on Function 'f'...
[2017-10-03 10:06:20.575531100] 0x3c95710 Executing Pass 'Machine Natural Loop Construction' on Function 'f'...
[2017-10-03 10:06:20.575574333] 0x3c95710 Executing Pass 'Eliminate PHI nodes for register allocation' on Function 'f'...
[2017-10-03 10:06:20.575609045] 0x3c95710 Freeing Pass 'Eliminate PHI nodes for register allocation' on Function 'f'...
[2017-10-03 10:06:20.575635795] 0x3c95710 Freeing Pass 'Remove unreachable machine basic blocks' on Function 'f'...
[...]
Shouldn't it stop before "Executing Pass 'Remove unreachable machine basic blocks' on Function 'f'" ?

Second weirdness:
If I try to work around the above by instead stopping after "Process Implicit Definitions" and then just
run run-pass=unreachable-mbb-elimination I get

Machine code for function f: IsSSA

BB#0: derived from LLVM BB %bb0

    JMP_1 <BB#1>
Successors according to CFG: BB#1(0x80000000 / 0x80000000 = 100.00%)

BB#1: derived from LLVM BB %bb1

Predecessors according to CFG: BB#0 BB#2
    %vreg0<def> = PHI %vreg2<undef>, <BB#0>, %vreg3, <BB#2>; GR32:%vreg0,%vreg2,%vreg3
    %vreg3<def,tied1> = ADD32ri8 %vreg0<kill,tied0>, 1, %EFLAGS<imp-def>; GR32:%vreg3,%vreg0
    JMP_1 <BB#3>
Successors according to CFG: BB#3(0x80000000 / 0x80000000 = 100.00%)

BB#2: derived from LLVM BB %bb2

    JMP_1 <BB#1>
Successors according to CFG: BB#1(0x80000000 / 0x80000000 = 100.00%)

BB#3: derived from LLVM BB %bb3

Predecessors according to CFG: BB#1
    RETQ

End machine code for function f.

• • Bad machine code: PHI operand is not live-out from predecessor ***
• function: f
• basic block: BB#1 bb1 (0x4995cf8)
• instruction: %vreg0<def> = PHI
• operand 1: %vreg2<undef>

LLVM ERROR: Found 1 machine code errors.

So the MIR output from processimpdefs is not accepted as input.

So the smallest MIR test I've managed to do is if I stop before processimpdefs
and then run with that output as input with
-run-pass=processimpdefs -run-pass=unreachable-mbb-elimination.

I'll upload that new testcase in a minute.

[uabelho]

Changed the testcase to MIR.

[uabelho]

In D38235#884338, @kparzysz wrote:

Looks good. Thanks.

Could you change the testcase to MIR and only run the unreachable block elimination?

Do you prefer the new version?

[kparzysz]

Yes. This is great! Thanks.

[uabelho]

Several build bots broke due to my new test case. I think it's because it assumed the default target would be x86.
I reverted in r314880 and then recommited with a (hopefully) fixed testcase in r314882.

lib/CodeGen/UnreachableBlockElim.cpp

while (phi != BB->end() && phi->isPHI()) {
         unsigned OutputReg = Output.getReg();
         assert(Output.getSubReg() == 0 && "Cannot have output subregister");
         ModifiedPHI = true;
 
         if (InputReg != OutputReg) {
           MachineRegisterInfo &MRI = F.getRegInfo();
           unsigned InputSub = Input.getSubReg();
           if (InputSub == 0 &&
-              MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg))) {
+              MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) &&
+              !Input.isUndef()) {
             MRI.replaceRegWith(OutputReg, InputReg);
           } else {
             // The input register to the PHI has a subregister or it can't be
-            // constrained to the proper register class:
+            // constrained to the proper register class or it is undef:
             // insert a COPY instead of simply replacing the output
             // with the input.
             const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
             BuildMI(*BB, BB->getFirstNonPHI(), phi->getDebugLoc(),
                     TII->get(TargetOpcode::COPY), OutputReg)
                 .addReg(InputReg, getRegState(Input), InputSub);
           }
           phi++->eraseFromParent();

test/CodeGen/X86/unreachable-mbb-undef-phi.ll

+; RUN: llc -optimize-regalloc -O0 %s -o - -stop-after=unreachable-mbb-elimination | FileCheck %s
+
+define void @f() {
+bb0:
+  br label %bb1
+
+bb1:                                           ; preds = %bb2, %bb0
+  %inc1 = phi i32 [ %inc, %bb2 ], [ undef, %bb0 ]
+  %inc = add nsw i32 %inc1, 1
+  %tobool = icmp eq i32 0, 0
+  br i1 %tobool, label %bb3, label %bb2
+
+bb2:                                           ; preds = %bb1
+  br label %bb1
+
+bb3:                                           ; preds = %bb1
+  ret void
+}
+
+; bb2 is dead and should be removed and the add input should be marked with
+; undef since the bb0 value in the PHI is undef. Shouldn't crash.
+
+; CHECK: bb.0.bb0:
+; CHECK:   successors: %bb.1.bb1
+; CHECK:   JMP_1 %bb.1.bb1
+
+; CHECK: bb.1.bb1:
+; CHECK:   successors: %bb.2.bb3
+; CHECK:   dead %eax = ADD32ri8 undef %eax, 1, implicit-def dead %eflags
+; CHECK:   JMP_1 %bb.2.bb3
+
+; CHECK: bb.2.bb3:
+; CHECK:   RETQ