[TailDuplicator] allow for callbr

[nickdesaulniers]

Summary

Follow up to https://reviews.llvm.org/D88823; fixes a TODO from the
clang-11 release by leveraging findPHICopyInsertPoint(), which has been
moved to be more accessible outside of llvm/lib/CodeGen/.

[nickdesaulniers]

llvm/test/CodeGen/X86/tail-dup-asm-goto.ll

21

hmmm...this doesn't look quite right to me, shouldn't the copy have occurred BEFORE the INLINEASM_BR...?

[nickdesaulniers]

I suspect that duplicateInstruction is not updating isInlineAsmBrIndirectTarget correctly when moving the INLINEASM_BR, but will have to verify.

llvm/include/llvm/CodeGen/PHIEliminationUtils.h

 //=- PHIEliminationUtils.h - Helper functions for PHI elimination -*- C++ -*-=//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_CODEGEN_PHIELIMINATIONUTILS_H
 #define LLVM_LIB_CODEGEN_PHIELIMINATIONUTILS_H
 
 #include "llvm/CodeGen/MachineBasicBlock.h"
 
 namespace llvm {
-    /// findPHICopyInsertPoint - Find a safe place in MBB to insert a copy from
-    /// SrcReg when following the CFG edge to SuccMBB. This needs to be after
-    /// any def of SrcReg, but before any subsequent point where control flow
-    /// might jump out of the basic block.
-    MachineBasicBlock::iterator
-    findPHICopyInsertPoint(MachineBasicBlock* MBB, MachineBasicBlock* SuccMBB,
+MachineBasicBlock::iterator findPHICopyInsertPoint(MachineBasicBlock *MBB,
+                                                   MachineBasicBlock *SuccMBB,
                                                    unsigned SrcReg);
-}
+} // namespace llvm
 
 #endif

llvm/include/llvm/CodeGen/TailDuplicator.h

bool duplicateSimpleBB(MachineBasicBlock *TailBB,
                          const DenseSet<Register> &RegsUsedByPhi,
                          SmallVectorImpl<MachineInstr *> &Copies);
   bool tailDuplicate(bool IsSimple,
                      MachineBasicBlock *TailBB,
                      MachineBasicBlock *ForcedLayoutPred,
                      SmallVectorImpl<MachineBasicBlock *> &TDBBs,
                      SmallVectorImpl<MachineInstr *> &Copies,
                      SmallVectorImpl<MachineBasicBlock *> *CandidatePtr);
-  void appendCopies(MachineBasicBlock *MBB,
-                 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
-                 SmallVectorImpl<MachineInstr *> &Copies);
+  void
+  appendCopies(MachineBasicBlock *MBB, MachineBasicBlock *Succ,
 
   void removeDeadBlock(
       MachineBasicBlock *MBB,
       function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_TAILDUPLICATOR_H

llvm/lib/CodeGen/PHIElimination.cpp

 //===- PhiElimination.cpp - Eliminate PHI nodes by inserting copies -------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass eliminates machine instruction PHI nodes by inserting copy
 // instructions.  This destroys SSA information, but is the desired input for
 // some register allocators.
 //
 //===----------------------------------------------------------------------===//
 
-#include "PHIEliminationUtils.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/PHIEliminationUtils.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Pass.h"

llvm/lib/CodeGen/PHIEliminationUtils.cpp

 //===-- PHIEliminationUtils.cpp - Helper functions for PHI elimination ----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
-#include "PHIEliminationUtils.h"
+#include "llvm/CodeGen/PHIEliminationUtils.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 
 using namespace llvm;
 
 // findCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg
 // when following the CFG edge to SuccMBB. This needs to be after any def of

llvm/lib/CodeGen/RenameIndependentSubregs.cpp

 ///   use %1:sub1
 ///   %2:sub1<read-undef> = ...
 ///   use %2:sub1
 ///   use %0:sub0
 //
 //===----------------------------------------------------------------------===//
 
 #include "LiveRangeUtils.h"
-#include "PHIEliminationUtils.h"
 #include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/PHIEliminationUtils.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/InitializePasses.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "rename-independent-subregs"
 

llvm/lib/CodeGen/TailDuplicator.cpp

 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
-#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
+#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/MachineSizeOpts.h"
 #include "llvm/CodeGen/MachineSSAUpdater.h"
+#include "llvm/CodeGen/MachineSizeOpts.h"
+#include "llvm/CodeGen/PHIEliminationUtils.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
if (PreRegAlloc && MI.isReturn())
       return false;
 
     // Avoid duplicating calls before register allocation. Calls presents a
     // barrier to register allocation so duplicating them may end up increasing
     // spills.
     if (PreRegAlloc && MI.isCall())
       return false;
 
-    // TailDuplicator::appendCopies will erroneously place COPYs after
-    // INLINEASM_BR instructions after 4b0aa5724fea, which demonstrates the same
-    // bug that was fixed in f7a53d82c090.
-    // FIXME: Use findPHICopyInsertPoint() to find the correct insertion point
-    //        for the COPY when replacing PHIs.
-    if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)
-      return false;
-
     if (MI.isBundle())
       InstrCount += MI.getBundleSize();
     else if (!MI.isPHI() && !MI.isMetaInstruction())
       InstrCount += 1;
 
     if (InstrCount > MaxDuplicateCount)
       return false;
   }
for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end();
         // from PredBB.
         processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true);
       } else {
         // Replace def of virtual registers with new registers, and update
         // uses with PHI source register or the new registers.
         duplicateInstruction(MI, TailBB, PredBB, LocalVRMap, UsedByPhi);
       }
     }
-    appendCopies(PredBB, CopyInfos, Copies);
+    appendCopies(PredBB, TailBB, CopyInfos, Copies);
 
     NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch
 
     // Update the CFG.
     PredBB->removeSuccessor(PredBB->succ_begin());
     assert(PredBB->succ_empty() &&
            "TailDuplicate called on block with multiple successors!");
     for (MachineBasicBlock *Succ : TailBB->successors())
if (PreRegAlloc) {
       while (I != TailBB->end()) {
         // Replace def of virtual registers with new registers, and update
         // uses with PHI source register or the new registers.
         MachineInstr *MI = &*I++;
         assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
         duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
         MI->eraseFromParent();
       }
-      appendCopies(PrevBB, CopyInfos, Copies);
+      appendCopies(PrevBB, TailBB, CopyInfos, Copies);
     } else {
       TII->removeBranch(*PrevBB);
       // No PHIs to worry about, just splice the instructions over.
       PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
     }
     PrevBB->removeSuccessor(PrevBB->succ_begin());
     assert(PrevBB->succ_empty());
     PrevBB->transferSuccessors(TailBB);
for (MachineBasicBlock *PredBB : Preds) {
     MachineBasicBlock::iterator I = TailBB->begin();
     // Process PHI instructions first.
     while (I != TailBB->end() && I->isPHI()) {
       // Replace the uses of the def of the PHI with the register coming
       // from PredBB.
       MachineInstr *MI = &*I++;
       processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);
     }
-    appendCopies(PredBB, CopyInfos, Copies);
+    appendCopies(PredBB, TailBB, CopyInfos, Copies);
   }
 
   return Changed;
 }
 
 /// At the end of the block \p MBB generate COPY instructions between registers
 /// described by \p CopyInfos. Append resulting instructions to \p Copies.
-void TailDuplicator::appendCopies(MachineBasicBlock *MBB,
-      SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
-      SmallVectorImpl<MachineInstr*> &Copies) {
-  MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();
+void TailDuplicator::appendCopies(
+    MachineBasicBlock *MBB, MachineBasicBlock *Succ,
+    SmallVectorImpl<MachineInstr *> &Copies) {
   const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY);
   for (auto &CI : CopyInfos) {
+    MachineBasicBlock::iterator Loc =
+        findPHICopyInsertPoint(MBB, Succ, CI.first);
     auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)
                 .addReg(CI.second.Reg, 0, CI.second.SubReg);
     Copies.push_back(C);
   }
 }
 
 /// Remove the specified dead machine basic block from the function, updating
 /// the CFG.

llvm/test/CodeGen/X86/tail-dup-asm-goto.ll

 ; NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
 ; RUN: llc -mtriple=x86_64-linux -stop-after=early-tailduplication < %s | FileCheck %s
 
-; Ensure that we don't duplicate a block with an "INLINEASM_BR" instruction
-; during code gen.
 declare void @foo()
 
 define i8* @test1(i8** %arg1, i8* %arg2) {
   ; CHECK-LABEL: name: test1
   ; CHECK: bb.0.bb:
   ; CHECK:   successors: %bb.1(0x50000000), %bb.2(0x30000000)
   ; CHECK:   liveins: $rdi, $rsi
   ; CHECK:   [[COPY:%[0-9]+]]:gr64 = COPY $rsi
   ; CHECK:   [[COPY1:%[0-9]+]]:gr64 = COPY $rdi
   ; CHECK:   [[MOV64rm:%[0-9]+]]:gr64 = MOV64rm [[COPY1]], 1, $noreg, 0, $noreg :: (load 8 from %ir.arg1)
   ; CHECK:   [[SUB64rr:%[0-9]+]]:gr64 = SUB64rr [[MOV64rm]], [[COPY]], implicit-def $eflags
   ; CHECK:   JCC_1 %bb.2, 4, implicit $eflags
   ; CHECK:   JMP_1 %bb.1
   ; CHECK: bb.1.bb100:
-  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   successors: %bb.5(0x80000000), %bb.4(0x00000000)
   ; CHECK:   MOV64mi32 [[COPY1]], 1, $noreg, 0, $noreg, 0 :: (store 8 into %ir.arg1)
-  ; CHECK:   JMP_1 %bb.3
+  ; CHECK:   INLINEASM_BR &"#$0 $1 $2", 9 /* sideeffect mayload attdialect */, 13 /* imm */, 42, 13 /* imm */, 0, 13 /* imm */, blockaddress(@test1, %ir-block.bb17.i.i.i), 12 /* clobber */, implicit-def early-clobber $df, 12 /* clobber */, implicit-def early-clobber $fpsw, 12 /* clobber */, implicit-def early-clobber $eflags
+  ; CHECK:   [[COPY2:%[0-9]+]]:gr64 = COPY [[MOV64rm]]
+  ; CHECK:   JMP_1 %bb.5
   ; CHECK: bb.2.bb106:
-  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   successors: %bb.5(0x80000000), %bb.4(0x00000000)
   ; CHECK:   ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
   ; CHECK:   CALL64pcrel32 @foo, csr_64, implicit $rsp, implicit $ssp, implicit-def $rsp, implicit-def $ssp
   ; CHECK:   ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
-  ; CHECK: bb.3.bb110:
-  ; CHECK:   successors: %bb.5(0x80000000), %bb.4(0x00000000)
-  ; CHECK:   [[PHI:%[0-9]+]]:gr64 = PHI [[COPY]], %bb.2, [[MOV64rm]], %bb.1
   ; CHECK:   INLINEASM_BR &"#$0 $1 $2", 9 /* sideeffect mayload attdialect */, 13 /* imm */, 42, 13 /* imm */, 0, 13 /* imm */, blockaddress(@test1, %ir-block.bb17.i.i.i), 12 /* clobber */, implicit-def early-clobber $df, 12 /* clobber */, implicit-def early-clobber $fpsw, 12 /* clobber */, implicit-def early-clobber $eflags
+  ; CHECK:   [[COPY3:%[0-9]+]]:gr64 = COPY [[COPY]]
   ; CHECK:   JMP_1 %bb.5
   ; CHECK: bb.4.bb17.i.i.i (address-taken):
   ; CHECK:   successors: %bb.5(0x80000000)
+  ; CHECK:   [[PHI:%[0-9]+]]:gr64 = PHI [[COPY2]], %bb.1, [[COPY3]], %bb.2
   ; CHECK: bb.5.kmem_cache_has_cpu_partial.exit:
-  ; CHECK:   $rax = COPY [[PHI]]
+  ; CHECK:   [[PHI1:%[0-9]+]]:gr64 = PHI [[PHI]], %bb.4, [[COPY2]], %bb.1, [[COPY3]], %bb.2
+  ; CHECK:   $rax = COPY [[PHI1]]
   ; CHECK:   RET 0, $rax
 bb:
   %i28.i = load i8*, i8** %arg1, align 8
   %if = icmp ne i8* %i28.i, %arg2
   br i1 %if, label %bb100, label %bb106
 
 bb100:                                            ; preds = %bb
   store i8* null, i8** %arg1, align 8