[GlobalISel] Clear unreachable blocks' contents after selection.

[aemerson]

Summary

If these blocks are unreachable, then we can discard all of the instructions. However, keep the block around because it may have an address taken or the block may have a stale reference from a PHI somewhere. Instead of finding those PHIs and fixing them up, just leave the block empty.

This was motivated by https://reviews.llvm.org/D110603 which ran into this problem.

[paquette]

This seems reasonable to me.

[uabelho]

llvm/lib/CodeGen/GlobalISel/InstructionSelect.cpp

217

What happens if the unreachable block defines a value %val that is used in the phi? Will it be handled some way or lead to a verifier error? (I don't know this code at all so perhaps it's totally obvious it will just work out nicely.)

llvm/lib/CodeGen/GlobalISel/InstructionSelect.cpp

if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
       reportGISelFailure(MF, TPC, MORE, "gisel-select",
                          "instruction is not legal", *MI);
       return false;
     }
   // FIXME: We could introduce new blocks and will need to fix the outer loop.
   // Until then, keep track of the number of blocks to assert that we don't.
   const size_t NumBlocks = MF.size();
 #endif
+  // Keep track of selected blocks, so we can delete unreachable ones later.
+  DenseSet<MachineBasicBlock *> SelectedBlocks;
 
   for (MachineBasicBlock *MBB : post_order(&MF)) {
     ISel->CurMBB = MBB;
+    SelectedBlocks.insert(MBB);
     if (MBB->empty())
       continue;
 
     // Select instructions in reverse block order. We permit erasing so have
     // to resort to manually iterating and recognizing the begin (rend) case.
     bool ReachedBegin = false;
     for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
          !ReachedBegin;) {
#endif
       });
     }
   }
 
   for (MachineBasicBlock &MBB : MF) {
     if (MBB.empty())
       continue;
 
+    if (!SelectedBlocks.contains(&MBB)) {
+      // This is an unreachable block and therefore hasn't been selected, since
+      // the main selection loop above uses a postorder block traversal.
+      // We delete all the instructions in this block since it's unreachable.
+      MBB.clear();
+      // Don't delete the block in case the block has it's address taken or is
+      // still being referenced by a phi somewhere.
+      continue;
+    }
     // Try to find redundant copies b/w vregs of the same register class.
     bool ReachedBegin = false;
     for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
       // Select this instruction.
       MachineInstr &MI = *MII;
 
       // And have our iterator point to the next instruction, if there is one.
       if (MII == Begin)

llvm/test/CodeGen/AArch64/GlobalISel/select-blockaddress.mir

body:             |
   ; CHECK-LABEL: name: test_blockaddress
   ; CHECK: bb.0 (%ir-block.0):
   ; CHECK:   [[MOVaddrBA:%[0-9]+]]:gpr64common = MOVaddrBA target-flags(aarch64-page) blockaddress(@test_blockaddress, %ir-block.block), target-flags(aarch64-pageoff, aarch64-nc) blockaddress(@test_blockaddress, %ir-block.block)
   ; CHECK:   [[MOVaddr:%[0-9]+]]:gpr64common = MOVaddr target-flags(aarch64-page) @addr, target-flags(aarch64-pageoff, aarch64-nc) @addr
   ; CHECK:   [[COPY:%[0-9]+]]:gpr64 = COPY [[MOVaddrBA]]
   ; CHECK:   STRXui [[COPY]], [[MOVaddr]], 0 :: (store (p0) into @addr)
   ; CHECK:   BR [[MOVaddrBA]]
   ; CHECK: bb.1.block (address-taken):
-  ; CHECK:   RET_ReallyLR
   ; LARGE-LABEL: name: test_blockaddress
   ; LARGE: bb.0 (%ir-block.0):
   ; LARGE:   [[MOVZXi:%[0-9]+]]:gpr64 = MOVZXi target-flags(aarch64-g0, aarch64-nc) blockaddress(@test_blockaddress, %ir-block.block), 0
   ; LARGE:   [[MOVKXi:%[0-9]+]]:gpr64 = MOVKXi [[MOVZXi]], target-flags(aarch64-g1, aarch64-nc) blockaddress(@test_blockaddress, %ir-block.block), 16
   ; LARGE:   [[MOVKXi1:%[0-9]+]]:gpr64 = MOVKXi [[MOVKXi]], target-flags(aarch64-g2, aarch64-nc) blockaddress(@test_blockaddress, %ir-block.block), 32
   ; LARGE:   [[MOVKXi2:%[0-9]+]]:gpr64 = MOVKXi [[MOVKXi1]], target-flags(aarch64-g3) blockaddress(@test_blockaddress, %ir-block.block), 48
   ; LARGE:   [[MOVZXi1:%[0-9]+]]:gpr64 = MOVZXi target-flags(aarch64-g0, aarch64-nc) @addr, 0
   ; LARGE:   [[MOVKXi3:%[0-9]+]]:gpr64 = MOVKXi [[MOVZXi1]], target-flags(aarch64-g1, aarch64-nc) @addr, 16
   ; LARGE:   [[MOVKXi4:%[0-9]+]]:gpr64 = MOVKXi [[MOVKXi3]], target-flags(aarch64-g2, aarch64-nc) @addr, 32
   ; LARGE:   [[MOVKXi5:%[0-9]+]]:gpr64common = MOVKXi [[MOVKXi4]], target-flags(aarch64-g3) @addr, 48
   ; LARGE:   STRXui [[MOVKXi2]], [[MOVKXi5]], 0 :: (store (p0) into @addr)
   ; LARGE:   BR [[MOVKXi2]]
   ; LARGE: bb.1.block (address-taken):
-  ; LARGE:   RET_ReallyLR
   bb.1 (%ir-block.0):
     %0:gpr(p0) = G_BLOCK_ADDR blockaddress(@test_blockaddress, %ir-block.block)
     %1:gpr(p0) = G_GLOBAL_VALUE @addr
     G_STORE %0(p0), %1(p0) :: (store (p0) into @addr)
     G_BRINDIRECT %0(p0)
 
   bb.2.block (address-taken):
     RET_ReallyLR
 
 ...

llvm/test/CodeGen/AArch64/GlobalISel/select-unreachable-blocks.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=aarch64-unknown-unknown -o - -verify-machineinstrs -run-pass=instruction-select %s | FileCheck %s
+---
+name:            test_unreachable_delete
+alignment:       4
+exposesReturnsTwice: false
+legalized:       true
+regBankSelected: true
+selected:        false
+tracksRegLiveness: true
+liveins:
+body:             |
+  ; CHECK-LABEL: name: test_unreachable_delete
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT:   liveins: $w0
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gpr32sp = COPY $w0
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gpr32 = COPY $wzr
+  ; CHECK-NEXT:   [[MOVi32imm:%[0-9]+]]:gpr32 = MOVi32imm 1
+  ; CHECK-NEXT:   B %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.3(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[ADDWri:%[0-9]+]]:gpr32sp = ADDWri [[COPY]], 2, 0
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gpr32 = PHI [[ADDWri]], %bb.2
+  ; CHECK-NEXT:   $w0 = COPY [[PHI]]
+  ; CHECK-NEXT:   RET_ReallyLR implicit $w0
+  bb.1:
+    successors: %bb.3
+    liveins: $w0
+
+    %0:gpr(s32) = COPY $w0
+    %1:gpr(s32) = G_CONSTANT i32 0
+    %3:gpr(s32) = G_CONSTANT i32 1
+    %5:gpr(s32) = G_CONSTANT i32 2
+    G_BR %bb.3
+
+  bb.5:
+    ; This block is unreachable.
+    %unreachable_inst:gpr(s32) = G_XOR %1, %3
+    $w0 = COPY %unreachable_inst(s32)
+
+  bb.3:
+    successors: %bb.4(0x80000000)
+
+    %6:gpr(s32) = G_ADD %0, %5
+
+  bb.4:
+    %7:gpr(s32) = G_PHI %6(s32), %bb.3
+    $w0 = COPY %7(s32)
+    RET_ReallyLR implicit $w0
+
+...