Empty basic blocks with unconditional branches aren't eliminated

[ashivaram23]

The following function calculates a && b:

define i1 @a_and_b(i1 %a) {
start:
  br i1 %a, label %a_is_true, label %a_or_b_is_false

a_is_true:
  %b = call i1 @get_b()
  br i1 %b, label %end, label %a_or_b_is_false

a_or_b_is_false:
  br label %end

end:
  %retval = phi i1 [ true, %a_is_true ], [ false, %a_or_b_is_false ]
  ret i1 %retval
}

declare i1 @get_b()

No -O3 pass is able to remove the a_or_b_is_false block, resulting in more assembly instructions than needed:

_a_and_b:
  push rbx
  test dil, 1
  je LBB0_2
  mov bl, 1
  call _get_b
  test al, 1
  jne LBB0_3
LBB0_2:
  xor ebx, ebx
LBB0_3:
  mov eax, ebx
  pop rbx
  ret

Instead, the function should become something like

define i1 @a_and_b(i1 %a) {
start:
  br i1 %a, label %a_is_true, label %end

a_is_true:
  %b = tail call i1 @get_b()
  br label %end

end:
  %retval = phi i1 [ false, %start ], [ %b, %a_is_true ]
  ret i1 %retval
}

and generate x86 instructions like this:

_a_and_b:
  test dil, 1
  jne _get_b
  xor eax, eax
  ret

That should mostly happen in SimplifyCFGPass. I think the fix could be as simple as removing the check for BB->phis().empty() in CanRedirectPredsOfEmptyBBToSucc in Transforms/Utils/Local.cpp. A comment there says "There must be phis in BB, otherwise BB will be merged into Succ directly," but that's not always true.

[sharkautarch]

@ashivaram23

That should mostly happen in SimplifyCFGPass. I think the fix could be as simple as removing the check for BB->phis().empty() in CanRedirectPredsOfEmptyBBToSucc in Transforms/Utils/Local.cpp. A comment there says "There must be phis in BB, otherwise BB will be merged into Succ directly," but that's not always true.

I think that the issue wrt the check in CanRedirectPredsOfEmptyBBToSucc() is that:

if (BB->phis().empty() || Succ->phis().empty())
    return false;

should actually be:

if (BB->phis().empty() && Succ->phis().empty())
    return false;