[GlobalISel] Simplify RegBankSelect

[sebastian-ne]

Summary

Save the instruction list of a block before selecting banks.
This allows to cope with moved instructions, even if they are reordered
or splitted into multiple basic blocks.

[foad]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

46

Don't need this since it's already done in the header.

732–733

Can you initialise the worklist from RPOT and then just have a single worklist loop, instead of two nested loops?

llvm/lib/Target/AMDGPU/AMDGPURegisterBankInfo.cpp

774–776 ↗

(On Diff #377514)

Before this patch, how did these new BBs get regbankselected?

[sebastian-ne]

Fix review comments, use just the worklist instead of a nested loop.

llvm/lib/Target/AMDGPU/AMDGPURegisterBankInfo.cpp

774–776 ↗

(On Diff #377514)

RegBankSelect had logic to detect if applyMapping moved an instruction to a new basic block and then continued from there.

The banks for instructions in RemainderBB and RestoreExecBB are set here, so they don’t need to be selected.

[foad]

OK, so if applyMapping creates new instructions it either has to

1. set banks for the new instructions' operands as they are created, or
2. do something to make sure RegBankSelect visits the new instructions.

[sebastian-ne]

Exactly

[foad]

The low level implementation details look OK to me.

I guess we need to get some agreement about the high level design: is this a good way of handling newly created instructions and BBs? In particular I wonder if there is some way of handling newly created instructions automatically, without having to call setNextInstruction, but I can't quite see how it would work.

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

698

Could just Worklist.insert(Worklist.end(), ...)?

[sebastian-ne]

Thanks, the Worklist.insert does read better than std::copy.

I guess we need to get some agreement about the high level design: is this a good way of handling newly created instructions and BBs? In particular I wonder if there is some way of handling newly created instructions automatically, without having to call setNextInstruction, but I can't quite see how it would work.

Yes, it gets quite complicated when introducing loops for call instructions because it moves multiple instructions and now also unbundles them (so the I++ used in RegBankSelect points to the wrong instruction – after the bundle).

[aemerson]

In D111223#3045476, @foad wrote:

The low level implementation details look OK to me.

I guess we need to get some agreement about the high level design: is this a good way of handling newly created instructions and BBs? In particular I wonder if there is some way of handling newly created instructions automatically, without having to call setNextInstruction, but I can't quite see how it would work.

Could an observer be installed to watch for newly created instructions?

[sebastian-ne]

I implemented it using an observer and it worked. Then I realized that I never registered the observer anywhere…
So, here’s a simpler implementation that seems to be enough to find all instructions.

The new patch for creating loops around call instructions does not use bundles anymore because they create more problems than they solve (e.g. the legalizer tries and fails to legalize instructions in a bundle). This simplifies the cases that need to be handled.

[foad]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

702

Pass (MBB->instr_rbegin(), MBB->instr_rend()) into the constructor here?

708

I think there's a pop_back_value you can use.

[sebastian-ne]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

702

I just tried and couldn’t get it working. I guess the iterator returns a MachineInstr& and no pointer, but SmallVector<MachineInstr&> doesn’t work.

[sebastian-ne]

Use pop_back_val

[foad]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

702

Ugh. This might work:

SmallVector<MachineInstr *> WorkList(make_pointer_range(reverse(MBB->instrs())));

[sebastian-ne]

The make_pointer_range worked, thanks

[arsenm]

Is the latest diff incomplete or is this really this simple now?

[sebastian-ne]

It’s complete. It worked in all cases I tested, so I hope it really can be that simple :)

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <limits>
 #include <memory>
 #include <utility>
 
 #define DEBUG_TYPE "regbankselect"
 
 using namespace llvm;
 
 static cl::opt<RegBankSelect::Mode> RegBankSelectMode(
if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
       return false;
     }
 #endif
 
   // Walk the function and assign register banks to all operands.
   // Use a RPOT to make sure all registers are assigned before we choose
   // the best mapping of the current instruction.
   ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);
   for (MachineBasicBlock *MBB : RPOT) {
     // Set a sensible insertion point so that subsequent calls to
     // MIRBuilder.
     MIRBuilder.setMBB(*MBB);
-    for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end();
-         MII != End;) {
-      // MI might be invalidated by the assignment, so move the
-      // iterator before hand.
-      MachineInstr &MI = *MII++;
+    SmallVector<MachineInstr *> WorkList;
+    for (MachineInstr &MI : reverse(MBB->instrs()))
+      WorkList.push_back(&MI);
+
+    while (!WorkList.empty()) {
+      MachineInstr &MI = *WorkList.back();
+      WorkList.pop_back();
 
       // Ignore target-specific post-isel instructions: they should use proper
       // regclasses.
       if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode())
         continue;
 
       // Ignore inline asm instructions: they should use physical
       // registers/regclasses
       if (MI.isInlineAsm())
         continue;
 
       // Ignore debug info.
       if (MI.isDebugInstr())
         continue;
 
       // Ignore IMPLICIT_DEF which must have a regclass.
       if (MI.isImplicitDef())
         continue;
 
       if (!assignInstr(MI)) {
         reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
                            "unable to map instruction", MI);
         return false;
       }
-
-      // It's possible the mapping changed control flow, and moved the following
-      // instruction to a new block, so figure out the new parent.
-      if (MII != End) {
-        MachineBasicBlock *NextInstBB = MII->getParent();
-        if (NextInstBB != MBB) {
-          LLVM_DEBUG(dbgs() << "Instruction mapping changed control flow\n");
-          MBB = NextInstBB;
-          MIRBuilder.setMBB(*MBB);
-          End = MBB->end();
-        }
-      }
     }
   }
 
   OptMode = SaveOptMode;
   return false;
 }
 
 //------------------------------------------------------------------------------
 //                  Helper Classes Implementation