[WIP] Use RPOT to process worklist of moveToVALU

llvm/lib/Target/AMDGPU/SIFixSGPRCopies.cpp

if (DstReg == AMDGPU::M0 &&
             DefMI->eraseFromParent();
           MI.eraseFromParent();
         }
       }
     }
     return true;
   }
   if (!SrcReg.isVirtual() || TRI->isAGPR(*MRI, SrcReg)) {
-    TII->moveToVALU(MI, MDT);
+    std::set<MachineInstr *> Worklist;
+    Worklist.insert(&MI);
+    TII->moveToVALU(Worklist, MDT);
     return true;
   }
 
   unsigned SMovOp;
   int64_t Imm;
   // If we are just copying an immediate, we can replace the copy with
   // s_mov_b32.
   if (isSafeToFoldImmIntoCopy(&MI, MRI->getVRegDef(SrcReg), TII, SMovOp, Imm)) {

 void SIFixSGPRCopies::lowerVGPR2SGPRCopies(MachineFunction &MF) {
 
   SmallVector<unsigned, 8> LoweringWorklist;
   for (auto &C : V2SCopies) {
     if (needToBeConvertedToVALU(&C.second))
       LoweringWorklist.push_back(C.second.ID);
   }
 
+  // Store all the V2S copy instructions that need to be moved to VALU
+  // in the Worklist.
+  std::set<MachineInstr *> Worklist;
+
   while (!LoweringWorklist.empty()) {
     unsigned CurID = LoweringWorklist.pop_back_val();
     auto CurInfoIt = V2SCopies.find(CurID);
     if (CurInfoIt != V2SCopies.end()) {
       V2SCopyInfo C = CurInfoIt->getSecond();
       LLVM_DEBUG(dbgs() << "Processing ...\n"; C.dump());
       for (auto S : C.Siblings) {
         auto SibInfoIt = V2SCopies.find(S);
         if (SibInfoIt != V2SCopies.end()) {
           V2SCopyInfo &SI = SibInfoIt->getSecond();
           LLVM_DEBUG(dbgs() << "Sibling:\n"; SI.dump());
           if (!SI.NeedToBeConvertedToVALU) {
             set_subtract(SI.SChain, C.SChain);
             if (needToBeConvertedToVALU(&SI))
               LoweringWorklist.push_back(SI.ID);
           }
           SI.Siblings.remove_if([&](unsigned ID) { return ID == C.ID; });
         }
       }
       LLVM_DEBUG(dbgs() << "V2S copy " << *C.Copy
                         << " is being turned to VALU\n");
       V2SCopies.erase(C.ID);
-      TII->moveToVALU(*C.Copy, MDT);
+      Worklist.insert(C.Copy);
     }
   }
 
+  TII->moveToVALU(Worklist, MDT);
+
   // Now do actual lowering
   for (auto C : V2SCopies) {
     MachineInstr *MI = C.second.Copy;
     MachineBasicBlock *MBB = MI->getParent();
     // We decide to turn V2S copy to v_readfirstlane_b32
     // remove it from the V2SCopies and remove it from all its siblings
     LLVM_DEBUG(dbgs() << "V2S copy " << *MI
                       << " is being turned to v_readfirstlane_b32"

llvm/lib/Target/AMDGPU/SIInstrInfo.h

MachineOperand buildExtractSubRegOrImm(MachineBasicBlock::iterator MI,
                                          MachineOperand &SuperReg,
                                          const TargetRegisterClass *SuperRC,
                                          unsigned SubIdx,
                                          const TargetRegisterClass *SubRC) const;
 private:
   void swapOperands(MachineInstr &Inst) const;
 
   std::pair<bool, MachineBasicBlock *>
-  moveScalarAddSub(SetVectorType &Worklist, MachineInstr &Inst,
+  moveScalarAddSub(std::set<MachineInstr *> &Worklist, MachineInstr &Inst,
                    MachineDominatorTree *MDT = nullptr) const;
 
-  void lowerSelect(SetVectorType &Worklist, MachineInstr &Inst,
+  void lowerSelect(std::set<MachineInstr *> &Worklist, MachineInstr &Inst,
                    MachineDominatorTree *MDT = nullptr) const;
 
-  void lowerScalarAbs(SetVectorType &Worklist,
+  void lowerScalarAbs(std::set<MachineInstr *> &Worklist,
                       MachineInstr &Inst) const;
 
-  void lowerScalarXnor(SetVectorType &Worklist,
+  void lowerScalarXnor(std::set<MachineInstr *> &Worklist,
                        MachineInstr &Inst) const;
 
-  void splitScalarNotBinop(SetVectorType &Worklist,
+  void splitScalarNotBinop(std::set<MachineInstr *> &Worklist,
                            MachineInstr &Inst,
                            unsigned Opcode) const;
 
-  void splitScalarBinOpN2(SetVectorType &Worklist,
+  void splitScalarBinOpN2(std::set<MachineInstr *> &Worklist,
                           MachineInstr &Inst,
                           unsigned Opcode) const;
 
-  void splitScalar64BitUnaryOp(SetVectorType &Worklist,
+  void splitScalar64BitUnaryOp(std::set<MachineInstr *> &Worklist,
                                MachineInstr &Inst, unsigned Opcode,
                                bool Swap = false) const;
 
-  void splitScalar64BitAddSub(SetVectorType &Worklist, MachineInstr &Inst,
+  void splitScalar64BitAddSub(std::set<MachineInstr *> &Worklist, MachineInstr &Inst,
                               MachineDominatorTree *MDT = nullptr) const;
 
-  void splitScalar64BitBinaryOp(SetVectorType &Worklist, MachineInstr &Inst,
+  void splitScalar64BitBinaryOp(std::set<MachineInstr *> &Worklist, MachineInstr &Inst,
                                 unsigned Opcode,
                                 MachineDominatorTree *MDT = nullptr) const;
 
-  void splitScalar64BitXnor(SetVectorType &Worklist, MachineInstr &Inst,
+  void splitScalar64BitXnor(std::set<MachineInstr *> &Worklist, MachineInstr &Inst,
                                 MachineDominatorTree *MDT = nullptr) const;
 
-  void splitScalar64BitBCNT(SetVectorType &Worklist,
+  void splitScalar64BitBCNT(std::set<MachineInstr *> &Worklist,
                             MachineInstr &Inst) const;
-  void splitScalar64BitBFE(SetVectorType &Worklist,
+  void splitScalar64BitBFE(std::set<MachineInstr *> &Worklist,
                            MachineInstr &Inst) const;
-  void movePackToVALU(SetVectorType &Worklist,
+  void movePackToVALU(std::set<MachineInstr *> &Worklist,
                       MachineRegisterInfo &MRI,
                       MachineInstr &Inst) const;
 
   void addUsersToMoveToVALUWorklist(Register Reg, MachineRegisterInfo &MRI,
-                                    SetVectorType &Worklist) const;
+                                    std::set<MachineInstr *> &Worklist) const;
 
   void addSCCDefUsersToVALUWorklist(MachineOperand &Op,
                                     MachineInstr &SCCDefInst,
-                                    SetVectorType &Worklist,
+                                    std::set<MachineInstr *> &Worklist,
                                     Register NewCond = Register()) const;
   void addSCCDefsToVALUWorklist(MachineInstr *SCCUseInst,
-                                SetVectorType &Worklist) const;
+                                std::set<MachineInstr *> &Worklist) const;
 
   const TargetRegisterClass *
   getDestEquivalentVGPRClass(const MachineInstr &Inst) const;
 
   bool checkInstOffsetsDoNotOverlap(const MachineInstr &MIa,
                                     const MachineInstr &MIb) const;
 
   Register findUsedSGPR(const MachineInstr &MI, int OpIndices[3]) const;
public:
 
   /// Change SADDR form of a FLAT \p Inst to its VADDR form if saddr operand
   /// was moved to VGPR. \returns true if succeeded.
   bool moveFlatAddrToVGPR(MachineInstr &Inst) const;
 
   /// Replace this instruction's opcode with the equivalent VALU
   /// opcode.  This function will also move the users of \p MI to the
   /// VALU if necessary. If present, \p MDT is updated.
-  MachineBasicBlock *moveToVALU(MachineInstr &MI,
+  //MachineBasicBlock *moveToVALU(MachineInstr &MI,
+  //                              MachineDominatorTree *MDT = nullptr) const;
+
+  void moveToVALU(std::set<MachineInstr *>& worklist,
                                 MachineDominatorTree *MDT = nullptr) const;
 
   void insertNoop(MachineBasicBlock &MBB,
                   MachineBasicBlock::iterator MI) const override;
 
   void insertNoops(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
                    unsigned Quantity) const override;
 

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

 #include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/CodeGen/RegisterScavenging.h"
 #include "llvm/CodeGen/ScheduleDAG.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/IntrinsicsAMDGPU.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Target/TargetMachine.h"
+#include "llvm/ADT/PostOrderIterator.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "si-instr-info"
 
 #define GET_INSTRINFO_CTOR_DTOR
 #include "AMDGPUGenInstrInfo.inc"
 
if (VAddr && AMDGPU::getIfAddr64Inst(MI.getOpcode()) != -1) {
       // to SGPRs.
       CreatedBB = loadSRsrcFromVGPR(*this, MI, *Rsrc, MDT);
       return CreatedBB;
     }
   }
   return CreatedBB;
 }
 
-MachineBasicBlock *SIInstrInfo::moveToVALU(MachineInstr &TopInst,
+void SIInstrInfo::moveToVALU(std::set<MachineInstr *>& Worklist,
                                            MachineDominatorTree *MDT) const {
-  SetVectorType Worklist;
-  Worklist.insert(&TopInst);
-  MachineBasicBlock *CreatedBB = nullptr;
-  MachineBasicBlock *CreatedBBTmp = nullptr;
+  if (Worklist.empty()) return;
+
+  MachineFunction* MF = (*Worklist.begin())->getMF();
+  if (MF->empty()) return;
+  ReversePostOrderTraversal<MachineFunction*> RPOT(MF);
+
+  for (MachineBasicBlock *MBB : RPOT) {
+    if (MBB->empty())
+      continue;
+    for (auto I = MBB->instr_begin(); I != MBB->instr_end(); ++I) {
+      if (Worklist.empty()) break;
+      MachineInstr& Inst = *I;
+
+      auto itr = std::find(Worklist.begin(), Worklist.end(), &Inst);
+      if (itr == Worklist.end()) continue;
+
+      Worklist.erase(itr);
 
-  while (!Worklist.empty()) {
-    MachineInstr &Inst = *Worklist.pop_back_val();
-    MachineBasicBlock *MBB = Inst.getParent();
       MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
 
       unsigned Opcode = Inst.getOpcode();
       unsigned NewOpcode = getVALUOp(Inst);
 
       // Handle some special cases
       switch (Opcode) {
       default:
         break;
       case AMDGPU::S_ADD_U64_PSEUDO:
       case AMDGPU::S_SUB_U64_PSEUDO:
         splitScalar64BitAddSub(Worklist, Inst, MDT);
         Inst.eraseFromParent();
         continue;
       case AMDGPU::S_ADD_I32:
       case AMDGPU::S_SUB_I32: {
         // FIXME: The u32 versions currently selected use the carry.
         bool Changed;
+        MachineBasicBlock *CreatedBBTmp = nullptr;
         std::tie(Changed, CreatedBBTmp) = moveScalarAddSub(Worklist, Inst, MDT);
-      if (CreatedBBTmp && TopInst.getParent() == CreatedBBTmp)
-        CreatedBB = CreatedBBTmp;
         if (Changed)
           continue;
 
         // Default handling
         break;
       }
       case AMDGPU::S_AND_B64:
         splitScalar64BitBinaryOp(Worklist, Inst, AMDGPU::S_AND_B32, MDT);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_OR_B64:
         splitScalar64BitBinaryOp(Worklist, Inst, AMDGPU::S_OR_B32, MDT);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_XOR_B64:
         splitScalar64BitBinaryOp(Worklist, Inst, AMDGPU::S_XOR_B32, MDT);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_NAND_B64:
         splitScalar64BitBinaryOp(Worklist, Inst, AMDGPU::S_NAND_B32, MDT);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_NOR_B64:
         splitScalar64BitBinaryOp(Worklist, Inst, AMDGPU::S_NOR_B32, MDT);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_XNOR_B64:
         if (ST.hasDLInsts())
           splitScalar64BitBinaryOp(Worklist, Inst, AMDGPU::S_XNOR_B32, MDT);
         else
           splitScalar64BitXnor(Worklist, Inst, MDT);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_ANDN2_B64:
         splitScalar64BitBinaryOp(Worklist, Inst, AMDGPU::S_ANDN2_B32, MDT);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_ORN2_B64:
         splitScalar64BitBinaryOp(Worklist, Inst, AMDGPU::S_ORN2_B32, MDT);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_BREV_B64:
         splitScalar64BitUnaryOp(Worklist, Inst, AMDGPU::S_BREV_B32, true);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_NOT_B64:
         splitScalar64BitUnaryOp(Worklist, Inst, AMDGPU::S_NOT_B32);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_BCNT1_I32_B64:
         splitScalar64BitBCNT(Worklist, Inst);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_BFE_I64:
         splitScalar64BitBFE(Worklist, Inst);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_LSHL_B32:
         if (ST.hasOnlyRevVALUShifts()) {
           NewOpcode = AMDGPU::V_LSHLREV_B32_e64;
           swapOperands(Inst);
         }
         break;
       case AMDGPU::S_ASHR_I32:
         if (ST.hasOnlyRevVALUShifts()) {
           NewOpcode = AMDGPU::V_ASHRREV_I32_e64;
           swapOperands(Inst);
         }
         break;
       case AMDGPU::S_LSHR_B32:
         if (ST.hasOnlyRevVALUShifts()) {
           NewOpcode = AMDGPU::V_LSHRREV_B32_e64;
           swapOperands(Inst);
         }
         break;
       case AMDGPU::S_LSHL_B64:
         if (ST.hasOnlyRevVALUShifts()) {
           NewOpcode = AMDGPU::V_LSHLREV_B64_e64;
           swapOperands(Inst);
         }
         break;
       case AMDGPU::S_ASHR_I64:
         if (ST.hasOnlyRevVALUShifts()) {
           NewOpcode = AMDGPU::V_ASHRREV_I64_e64;
           swapOperands(Inst);
         }
         break;
       case AMDGPU::S_LSHR_B64:
         if (ST.hasOnlyRevVALUShifts()) {
           NewOpcode = AMDGPU::V_LSHRREV_B64_e64;
           swapOperands(Inst);
         }
         break;
 
       case AMDGPU::S_ABS_I32:
         lowerScalarAbs(Worklist, Inst);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_CBRANCH_SCC0:
       case AMDGPU::S_CBRANCH_SCC1: {
           // Clear unused bits of vcc
           Register CondReg = Inst.getOperand(1).getReg();
           bool IsSCC = CondReg == AMDGPU::SCC;
           Register VCC = RI.getVCC();
           Register EXEC = ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC;
           unsigned Opc = ST.isWave32() ? AMDGPU::S_AND_B32 : AMDGPU::S_AND_B64;
           BuildMI(*MBB, Inst, Inst.getDebugLoc(), get(Opc), VCC)
               .addReg(EXEC)
               .addReg(IsSCC ? VCC : CondReg);
           Inst.removeOperand(1);
         }
         break;
 
       case AMDGPU::S_BFE_U64:
       case AMDGPU::S_BFM_B64:
         llvm_unreachable("Moving this op to VALU not implemented");
 
       case AMDGPU::S_PACK_LL_B32_B16:
       case AMDGPU::S_PACK_LH_B32_B16:
       case AMDGPU::S_PACK_HL_B32_B16:
       case AMDGPU::S_PACK_HH_B32_B16:
         movePackToVALU(Worklist, MRI, Inst);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_XNOR_B32:
         lowerScalarXnor(Worklist, Inst);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_NAND_B32:
         splitScalarNotBinop(Worklist, Inst, AMDGPU::S_AND_B32);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_NOR_B32:
         splitScalarNotBinop(Worklist, Inst, AMDGPU::S_OR_B32);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_ANDN2_B32:
         splitScalarBinOpN2(Worklist, Inst, AMDGPU::S_AND_B32);
         Inst.eraseFromParent();
         continue;
 
       case AMDGPU::S_ORN2_B32:
         splitScalarBinOpN2(Worklist, Inst, AMDGPU::S_OR_B32);
         Inst.eraseFromParent();
         continue;
 
       // TODO: remove as soon as everything is ready
       // to replace VGPR to SGPR copy with V_READFIRSTLANEs.
       // S_ADD/SUB_CO_PSEUDO as well as S_UADDO/USUBO_PSEUDO
       // can only be selected from the uniform SDNode.
       case AMDGPU::S_ADD_CO_PSEUDO:
       case AMDGPU::S_SUB_CO_PSEUDO: {
         unsigned Opc = (Inst.getOpcode() == AMDGPU::S_ADD_CO_PSEUDO)
                            ? AMDGPU::V_ADDC_U32_e64
                            : AMDGPU::V_SUBB_U32_e64;
         const auto *CarryRC = RI.getRegClass(AMDGPU::SReg_1_XEXECRegClassID);
 
         Register CarryInReg = Inst.getOperand(4).getReg();
         if (!MRI.constrainRegClass(CarryInReg, CarryRC)) {
           Register NewCarryReg = MRI.createVirtualRegister(CarryRC);
           BuildMI(*MBB, &Inst, Inst.getDebugLoc(), get(AMDGPU::COPY), NewCarryReg)
               .addReg(CarryInReg);
         }
 
         Register CarryOutReg = Inst.getOperand(1).getReg();
 
         Register DestReg = MRI.createVirtualRegister(RI.getEquivalentVGPRClass(
             MRI.getRegClass(Inst.getOperand(0).getReg())));
         MachineInstr *CarryOp =
             BuildMI(*MBB, &Inst, Inst.getDebugLoc(), get(Opc), DestReg)
                 .addReg(CarryOutReg, RegState::Define)
                 .add(Inst.getOperand(2))
                 .add(Inst.getOperand(3))
                 .addReg(CarryInReg)
                 .addImm(0);
-      CreatedBBTmp = legalizeOperands(*CarryOp);
-      if (CreatedBBTmp && TopInst.getParent() == CreatedBBTmp)
-        CreatedBB = CreatedBBTmp;
+        legalizeOperands(*CarryOp);
         MRI.replaceRegWith(Inst.getOperand(0).getReg(), DestReg);
         addUsersToMoveToVALUWorklist(DestReg, MRI, Worklist);
         Inst.eraseFromParent();
       }
         continue;
       case AMDGPU::S_UADDO_PSEUDO:
       case AMDGPU::S_USUBO_PSEUDO: {
         const DebugLoc &DL = Inst.getDebugLoc();
         MachineOperand &Dest0 = Inst.getOperand(0);
         MachineOperand &Dest1 = Inst.getOperand(1);
         MachineOperand &Src0 = Inst.getOperand(2);
         MachineOperand &Src1 = Inst.getOperand(3);
 
         unsigned Opc = (Inst.getOpcode() == AMDGPU::S_UADDO_PSEUDO)
                            ? AMDGPU::V_ADD_CO_U32_e64
                            : AMDGPU::V_SUB_CO_U32_e64;
         const TargetRegisterClass *NewRC =
             RI.getEquivalentVGPRClass(MRI.getRegClass(Dest0.getReg()));
         Register DestReg = MRI.createVirtualRegister(NewRC);
         MachineInstr *NewInstr = BuildMI(*MBB, &Inst, DL, get(Opc), DestReg)
                                      .addReg(Dest1.getReg(), RegState::Define)
                                      .add(Src0)
                                      .add(Src1)
                                      .addImm(0); // clamp bit
 
-      CreatedBBTmp = legalizeOperands(*NewInstr, MDT);
-      if (CreatedBBTmp && TopInst.getParent() == CreatedBBTmp)
-        CreatedBB = CreatedBBTmp;
+        legalizeOperands(*NewInstr, MDT);
 
         MRI.replaceRegWith(Dest0.getReg(), DestReg);
         addUsersToMoveToVALUWorklist(NewInstr->getOperand(0).getReg(), MRI,
                                      Worklist);
         Inst.eraseFromParent();
       }
         continue;
 
       case AMDGPU::S_CSELECT_B32:
       case AMDGPU::S_CSELECT_B64:
         lowerSelect(Worklist, Inst, MDT);
         Inst.eraseFromParent();
         continue;
       case AMDGPU::S_CMP_EQ_I32:
       case AMDGPU::S_CMP_LG_I32:
       case AMDGPU::S_CMP_GT_I32:
       case AMDGPU::S_CMP_GE_I32:
       case AMDGPU::S_CMP_LT_I32:
       case AMDGPU::S_CMP_LE_I32:
       case AMDGPU::S_CMP_EQ_U32:
       case AMDGPU::S_CMP_LG_U32:
       case AMDGPU::S_CMP_GT_U32:
       case AMDGPU::S_CMP_GE_U32:
       case AMDGPU::S_CMP_LT_U32:
       case AMDGPU::S_CMP_LE_U32:
       case AMDGPU::S_CMP_EQ_U64:
       case AMDGPU::S_CMP_LG_U64: {
           const MCInstrDesc &NewDesc = get(NewOpcode);
           Register CondReg = MRI.createVirtualRegister(RI.getWaveMaskRegClass());
           MachineInstr *NewInstr =
               BuildMI(*MBB, Inst, Inst.getDebugLoc(), NewDesc, CondReg)
                   .add(Inst.getOperand(0))
                   .add(Inst.getOperand(1));
           legalizeOperands(*NewInstr, MDT);
           int SCCIdx = Inst.findRegisterDefOperandIdx(AMDGPU::SCC);
           MachineOperand SCCOp = Inst.getOperand(SCCIdx);
           addSCCDefUsersToVALUWorklist(SCCOp, Inst, Worklist, CondReg);
           Inst.eraseFromParent();
         }
         continue;
       }
 
       if (NewOpcode == AMDGPU::INSTRUCTION_LIST_END) {
         // We cannot move this instruction to the VALU, so we should try to
         // legalize its operands instead.
-      CreatedBBTmp = legalizeOperands(Inst, MDT);
-      if (CreatedBBTmp && TopInst.getParent() == CreatedBBTmp)
-        CreatedBB = CreatedBBTmp;
+        legalizeOperands(Inst, MDT);
         continue;
       }
 
       // Handle converting generic instructions like COPY-to-SGPR into
       // COPY-to-VGPR.
       if (NewOpcode == Opcode) {
         Register DstReg = Inst.getOperand(0).getReg();
         const TargetRegisterClass *NewDstRC = getDestEquivalentVGPRClass(Inst);
 
         if (Inst.isCopy() && Inst.getOperand(1).getReg().isVirtual() &&
             NewDstRC == RI.getRegClassForReg(MRI, Inst.getOperand(1).getReg())) {
           // Instead of creating a copy where src and dst are the same register
           // class, we just replace all uses of dst with src.  These kinds of
           // copies interfere with the heuristics MachineSink uses to decide
           // whether or not to split a critical edge.  Since the pass assumes
           // that copies will end up as machine instructions and not be
           // eliminated.
           addUsersToMoveToVALUWorklist(DstReg, MRI, Worklist);
           MRI.replaceRegWith(DstReg, Inst.getOperand(1).getReg());
           MRI.clearKillFlags(Inst.getOperand(1).getReg());
           Inst.getOperand(0).setReg(DstReg);
 
           // Make sure we don't leave around a dead VGPR->SGPR copy. Normally
           // these are deleted later, but at -O0 it would leave a suspicious
           // looking illegal copy of an undef register.
           for (unsigned I = Inst.getNumOperands() - 1; I != 0; --I)
             Inst.removeOperand(I);
           Inst.setDesc(get(AMDGPU::IMPLICIT_DEF));
           continue;
         }
 
         Register NewDstReg = MRI.createVirtualRegister(NewDstRC);
         MRI.replaceRegWith(DstReg, NewDstReg);
         legalizeOperands(Inst, MDT);
         addUsersToMoveToVALUWorklist(NewDstReg, MRI, Worklist);
         continue;
       }
 
       // Use the new VALU Opcode.
       auto NewInstr = BuildMI(*MBB, Inst, Inst.getDebugLoc(), get(NewOpcode))
                           .setMIFlags(Inst.getFlags());
       for (const MachineOperand &Op : Inst.explicit_operands())
         NewInstr->addOperand(Op);
 
       // Remove any references to SCC. Vector instructions can't read from it, and
       // We're just about to add the implicit use / defs of VCC, and we don't want
       // both.
       for (MachineOperand &Op : Inst.implicit_operands()) {
         if (Op.getReg() == AMDGPU::SCC) {
           // Only propagate through live-def of SCC.
           if (Op.isDef() && !Op.isDead())
             addSCCDefUsersToVALUWorklist(Op, Inst, Worklist);
           if (Op.isUse())
             addSCCDefsToVALUWorklist(NewInstr, Worklist);
         }
       }
 
       Inst.eraseFromParent();
 
       Register NewDstReg;
       if (NewInstr->getOperand(0).isReg() && NewInstr->getOperand(0).isDef()) {
         Register DstReg = NewInstr->getOperand(0).getReg();
         assert(DstReg.isVirtual());
 
         // Update the destination register class.
         const TargetRegisterClass *NewDstRC =
             getDestEquivalentVGPRClass(*NewInstr);
         assert(NewDstRC);
 
         NewDstReg = MRI.createVirtualRegister(NewDstRC);
         MRI.replaceRegWith(DstReg, NewDstReg);
       }
 
       if (Opcode == AMDGPU::S_SEXT_I32_I8 || Opcode == AMDGPU::S_SEXT_I32_I16) {
         // We are converting these to a BFE, so we need to add the missing
         // operands for the size and offset.
         unsigned Size = (Opcode == AMDGPU::S_SEXT_I32_I8) ? 8 : 16;
         NewInstr.addImm(0);
         NewInstr.addImm(Size);
       } else if (Opcode == AMDGPU::S_BCNT1_I32_B32) {
         // The VALU version adds the second operand to the result, so insert an
         // extra 0 operand.
         NewInstr.addImm(0);
       }
 
       if (Opcode == AMDGPU::S_BFE_I32 || Opcode == AMDGPU::S_BFE_U32) {
         const MachineOperand &OffsetWidthOp = NewInstr->getOperand(2);
         // If we need to move this to VGPRs, we need to unpack the second operand
         // back into the 2 separate ones for bit offset and width.
         assert(OffsetWidthOp.isImm() &&
                "Scalar BFE is only implemented for constant width and offset");
         uint32_t Imm = OffsetWidthOp.getImm();
 
         uint32_t Offset = Imm & 0x3f; // Extract bits [5:0].
         uint32_t BitWidth = (Imm & 0x7f0000) >> 16; // Extract bits [22:16].
         NewInstr->removeOperand(2);
         NewInstr.addImm(Offset);
         NewInstr.addImm(BitWidth);
       }
 
       fixImplicitOperands(*NewInstr);
 
       // Legalize the operands
-    CreatedBBTmp = legalizeOperands(*NewInstr, MDT);
-    if (CreatedBBTmp && TopInst.getParent() == CreatedBBTmp)
-      CreatedBB = CreatedBBTmp;
+      legalizeOperands(*NewInstr, MDT);
 
       if (NewDstReg)
         addUsersToMoveToVALUWorklist(NewDstReg, MRI, Worklist);
     }
-  return CreatedBB;
+  }
 }
 
 // Add/sub require special handling to deal with carry outs.
 std::pair<bool, MachineBasicBlock *>
-SIInstrInfo::moveScalarAddSub(SetVectorType &Worklist, MachineInstr &Inst,
+SIInstrInfo::moveScalarAddSub(std::set<MachineInstr *> &Worklist, MachineInstr &Inst,
                               MachineDominatorTree *MDT) const {
   if (ST.hasAddNoCarry()) {
     // Assume there is no user of scc since we don't select this in that case.
     // Since scc isn't used, it doesn't really matter if the i32 or u32 variant
     // is used.
 
     MachineBasicBlock &MBB = *Inst.getParent();
     MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
if (ST.hasAddNoCarry()) {
 
     addUsersToMoveToVALUWorklist(ResultReg, MRI, Worklist);
     return std::pair(true, NewBB);
   }
 
   return std::pair(false, nullptr);
 }
 
-void SIInstrInfo::lowerSelect(SetVectorType &Worklist, MachineInstr &Inst,
+void SIInstrInfo::lowerSelect(std::set<MachineInstr *> &Worklist, MachineInstr &Inst,
                               MachineDominatorTree *MDT) const {
 
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   MachineBasicBlock::iterator MII = Inst;
   DebugLoc DL = Inst.getDebugLoc();
 
   MachineOperand &Dest = Inst.getOperand(0);
auto UpdatedInst =
           .add(Src0) // True
           .addReg(IsSCC ? CopySCC : SCCSource);
 
   MRI.replaceRegWith(Dest.getReg(), ResultReg);
   legalizeOperands(*UpdatedInst, MDT);
   addUsersToMoveToVALUWorklist(ResultReg, MRI, Worklist);
 }
 
-void SIInstrInfo::lowerScalarAbs(SetVectorType &Worklist,
+void SIInstrInfo::lowerScalarAbs(std::set<MachineInstr *> &Worklist,
                                  MachineInstr &Inst) const {
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   MachineBasicBlock::iterator MII = Inst;
   DebugLoc DL = Inst.getDebugLoc();
 
   MachineOperand &Dest = Inst.getOperand(0);
   MachineOperand &Src = Inst.getOperand(1);
void SIInstrInfo::lowerScalarAbs(std::set<MachineInstr *> &Worklist,
   BuildMI(MBB, MII, DL, get(AMDGPU::V_MAX_I32_e64), ResultReg)
     .addReg(Src.getReg())
     .addReg(TmpReg);
 
   MRI.replaceRegWith(Dest.getReg(), ResultReg);
   addUsersToMoveToVALUWorklist(ResultReg, MRI, Worklist);
 }
 
-void SIInstrInfo::lowerScalarXnor(SetVectorType &Worklist,
+void SIInstrInfo::lowerScalarXnor(std::set<MachineInstr *> &Worklist,
                                   MachineInstr &Inst) const {
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   MachineBasicBlock::iterator MII = Inst;
   const DebugLoc &DL = Inst.getDebugLoc();
 
   MachineOperand &Dest = Inst.getOperand(0);
   MachineOperand &Src0 = Inst.getOperand(1);
if (ST.hasDLInsts()) {
     MRI.replaceRegWith(Dest.getReg(), NewDest);
 
     Worklist.insert(Xor);
 
     addUsersToMoveToVALUWorklist(NewDest, MRI, Worklist);
   }
 }
 
-void SIInstrInfo::splitScalarNotBinop(SetVectorType &Worklist,
+void SIInstrInfo::splitScalarNotBinop(std::set<MachineInstr *> &Worklist,
                                       MachineInstr &Inst,
                                       unsigned Opcode) const {
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   MachineBasicBlock::iterator MII = Inst;
   const DebugLoc &DL = Inst.getDebugLoc();
 
   MachineOperand &Dest = Inst.getOperand(0);
void SIInstrInfo::splitScalarNotBinop(std::set<MachineInstr *> &Worklist,
 
   Worklist.insert(&Op);
   Worklist.insert(&Not);
 
   MRI.replaceRegWith(Dest.getReg(), NewDest);
   addUsersToMoveToVALUWorklist(NewDest, MRI, Worklist);
 }
 
-void SIInstrInfo::splitScalarBinOpN2(SetVectorType& Worklist,
+void SIInstrInfo::splitScalarBinOpN2(std::set<MachineInstr *>& Worklist,
                                      MachineInstr &Inst,
                                      unsigned Opcode) const {
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   MachineBasicBlock::iterator MII = Inst;
   const DebugLoc &DL = Inst.getDebugLoc();
 
   MachineOperand &Dest = Inst.getOperand(0);
void SIInstrInfo::splitScalarBinOpN2(std::set<MachineInstr *>& Worklist,
   Worklist.insert(&Not);
   Worklist.insert(&Op);
 
   MRI.replaceRegWith(Dest.getReg(), NewDest);
   addUsersToMoveToVALUWorklist(NewDest, MRI, Worklist);
 }
 
 void SIInstrInfo::splitScalar64BitUnaryOp(
-    SetVectorType &Worklist, MachineInstr &Inst,
+    std::set<MachineInstr *> &Worklist, MachineInstr &Inst,
     unsigned Opcode, bool Swap) const {
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
 
   MachineOperand &Dest = Inst.getOperand(0);
   MachineOperand &Src0 = Inst.getOperand(1);
   DebugLoc DL = Inst.getDebugLoc();
 
void SIInstrInfo::splitScalar64BitUnaryOp(
 
   // We don't need to legalizeOperands here because for a single operand, src0
   // will support any kind of input.
 
   // Move all users of this moved value.
   addUsersToMoveToVALUWorklist(FullDestReg, MRI, Worklist);
 }
 
-void SIInstrInfo::splitScalar64BitAddSub(SetVectorType &Worklist,
+void SIInstrInfo::splitScalar64BitAddSub(std::set<MachineInstr *> &Worklist,
                                          MachineInstr &Inst,
                                          MachineDominatorTree *MDT) const {
   bool IsAdd = (Inst.getOpcode() == AMDGPU::S_ADD_U64_PSEUDO);
 
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   const auto *CarryRC = RI.getRegClass(AMDGPU::SReg_1_XEXECRegClassID);
 
void SIInstrInfo::splitScalar64BitAddSub(std::set<MachineInstr *> &Worklist,
   // valid.
   legalizeOperands(*LoHalf, MDT);
   legalizeOperands(*HiHalf, MDT);
 
   // Move all users of this moved value.
   addUsersToMoveToVALUWorklist(FullDestReg, MRI, Worklist);
 }
 
-void SIInstrInfo::splitScalar64BitBinaryOp(SetVectorType &Worklist,
+void SIInstrInfo::splitScalar64BitBinaryOp(std::set<MachineInstr *> &Worklist,
                                            MachineInstr &Inst, unsigned Opcode,
                                            MachineDominatorTree *MDT) const {
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
 
   MachineOperand &Dest = Inst.getOperand(0);
   MachineOperand &Src0 = Inst.getOperand(1);
   MachineOperand &Src1 = Inst.getOperand(2);
void SIInstrInfo::splitScalar64BitBinaryOp(std::set<MachineInstr *> &Worklist,
 
   Worklist.insert(&LoHalf);
   Worklist.insert(&HiHalf);
 
   // Move all users of this moved value.
   addUsersToMoveToVALUWorklist(FullDestReg, MRI, Worklist);
 }
 
-void SIInstrInfo::splitScalar64BitXnor(SetVectorType &Worklist,
+void SIInstrInfo::splitScalar64BitXnor(std::set<MachineInstr *> &Worklist,
                                        MachineInstr &Inst,
                                        MachineDominatorTree *MDT) const {
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
 
   MachineOperand &Dest = Inst.getOperand(0);
   MachineOperand &Src0 = Inst.getOperand(1);
   MachineOperand &Src1 = Inst.getOperand(2);
MachineInstr &Xor = *BuildMI(MBB, MII, DL, get(AMDGPU::S_XOR_B64), NewDest)
     .add(*Op1);
 
   MRI.replaceRegWith(Dest.getReg(), NewDest);
 
   Worklist.insert(&Xor);
 }
 
 void SIInstrInfo::splitScalar64BitBCNT(
-    SetVectorType &Worklist, MachineInstr &Inst) const {
+    std::set<MachineInstr *> &Worklist, MachineInstr &Inst) const {
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
 
   MachineBasicBlock::iterator MII = Inst;
   const DebugLoc &DL = Inst.getDebugLoc();
 
   MachineOperand &Dest = Inst.getOperand(0);
   MachineOperand &Src = Inst.getOperand(1);
void SIInstrInfo::splitScalar64BitBCNT(
 
   MRI.replaceRegWith(Dest.getReg(), ResultReg);
 
   // We don't need to legalize operands here. src0 for either instruction can be
   // an SGPR, and the second input is unused or determined here.
   addUsersToMoveToVALUWorklist(ResultReg, MRI, Worklist);
 }
 
-void SIInstrInfo::splitScalar64BitBFE(SetVectorType &Worklist,
+void SIInstrInfo::splitScalar64BitBFE(std::set<MachineInstr *> &Worklist,
                                       MachineInstr &Inst) const {
   MachineBasicBlock &MBB = *Inst.getParent();
   MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   MachineBasicBlock::iterator MII = Inst;
   const DebugLoc &DL = Inst.getDebugLoc();
 
   MachineOperand &Dest = Inst.getOperand(0);
   uint32_t Imm = Inst.getOperand(2).getImm();
void SIInstrInfo::splitScalar64BitBFE(std::set<MachineInstr *> &Worklist,
 
   MRI.replaceRegWith(Dest.getReg(), ResultReg);
   addUsersToMoveToVALUWorklist(ResultReg, MRI, Worklist);
 }
 
 void SIInstrInfo::addUsersToMoveToVALUWorklist(
   Register DstReg,
   MachineRegisterInfo &MRI,
-  SetVectorType &Worklist) const {
+  std::set<MachineInstr *> &Worklist) const {
   for (MachineRegisterInfo::use_iterator I = MRI.use_begin(DstReg),
          E = MRI.use_end(); I != E;) {
     MachineInstr &UseMI = *I->getParent();
 
     unsigned OpNo = 0;
 
     switch (UseMI.getOpcode()) {
     case AMDGPU::COPY:
if (!RI.hasVectorRegisters(getOpRegClass(UseMI, OpNo))) {
         ++I;
       } while (I != E && I->getParent() == &UseMI);
     } else {
       ++I;
     }
   }
 }
 
-void SIInstrInfo::movePackToVALU(SetVectorType &Worklist,
+void SIInstrInfo::movePackToVALU(std::set<MachineInstr *> &Worklist,
                                  MachineRegisterInfo &MRI,
                                  MachineInstr &Inst) const {
   Register ResultReg = MRI.createVirtualRegister(&AMDGPU::VGPR_32RegClass);
   MachineBasicBlock *MBB = Inst.getParent();
   MachineOperand &Src0 = Inst.getOperand(1);
   MachineOperand &Src1 = Inst.getOperand(2);
   const DebugLoc &DL = Inst.getDebugLoc();
 
void SIInstrInfo::movePackToVALU(std::set<MachineInstr *> &Worklist,
 
   MachineOperand &Dest = Inst.getOperand(0);
   MRI.replaceRegWith(Dest.getReg(), ResultReg);
   addUsersToMoveToVALUWorklist(ResultReg, MRI, Worklist);
 }
 
 void SIInstrInfo::addSCCDefUsersToVALUWorklist(MachineOperand &Op,
                                                MachineInstr &SCCDefInst,
-                                               SetVectorType &Worklist,
+                                               std::set<MachineInstr *> &Worklist,
                                                Register NewCond) const {
 
   // Ensure that def inst defines SCC, which is still live.
   assert(Op.isReg() && Op.getReg() == AMDGPU::SCC && Op.isDef() &&
          !Op.isDead() && Op.getParent() == &SCCDefInst);
   SmallVector<MachineInstr *, 4> CopyToDelete;
   // This assumes that all the users of SCC are in the same block
   // as the SCC def.

 }
 
 // Instructions that use SCC may be converted to VALU instructions. When that
 // happens, the SCC register is changed to VCC_LO. The instruction that defines
 // SCC must be changed to an instruction that defines VCC. This function makes
 // sure that the instruction that defines SCC is added to the moveToVALU
 // worklist.
 void SIInstrInfo::addSCCDefsToVALUWorklist(MachineInstr *SCCUseInst,
-                                           SetVectorType &Worklist) const {
+                                           std::set<MachineInstr *> &Worklist) const {
   // Look for a preceding instruction that either defines VCC or SCC. If VCC
   // then there is nothing to do because the defining instruction has been
   // converted to a VALU already. If SCC then that instruction needs to be
   // converted to a VALU.
   for (MachineInstr &MI :
        make_range(std::next(MachineBasicBlock::reverse_iterator(SCCUseInst)),
                   SCCUseInst->getParent()->rend())) {
     if (MI.modifiesRegister(AMDGPU::VCC, &RI))