[GlobalISel] Introduce global variant of regbankselect

[ehjogab]

Summary

This patch introduces a new option '--regbankselect-global' to the
register bank selector. The algorithm is based on dynamic programming
and works as follows:

1. For each instruction, working top-down, compute cost of applying each InstructionMapping. If the result needs to be converted into some other register bank not supported by any of the InstructionMappings, compute the cost of introducing a copy.
2. For each instruction, working bottom-up, select the InstructionMapping with the highest utilization score. The utilization score is the sum of the cost of all mappings that make use of this mapping.
3. For each instruction, working top-down, apply the selected mapping.

Compared to the greedy version, which looks at and make decision for one
instruction at a time, this version operates at a global scope.

[arsenm]

llvm/include/llvm/CodeGen/GlobalISel/RegBankSelect.h

103–105

I think calling this "optimal" is a bit overly optimistic. Maybe Global?

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

1603

!isPreIselOpcode should cover asm already?

1608

This name is a bit obnoxious. If it's really necessary, I would rather just add this helper directly to MachineOperand

1608–1610

Can do just .getReg().isVirtual()

1703–1704

This explicit empty check is redundant

1732

Should not construct a fresh MachineIRBuilder every time

1735–1736

Is this intended to allow applyMappingImpl to insert new instructions which will iteratively have banks assigned? If so I think having a feature disparity with the single pass path is a problem

2005

Comment is unnecessary

2007

Don't like this getGSIOfMI name

2102

This checks for multiple explicit defs, but then seems to assume only a single def

[arsenm]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

1863

I think checking if this is virtual is redundant; any instruction subject to rgebank select should not have physical register operands

[ehjogab]

Thank you very much for your feedback, arsenm! Really appreciate it!

I noticed a crapload of lint warnings so I will fix them first, then fix your comments that I agree with, and then we can discuss further on those that I don't. =)

llvm/include/llvm/CodeGen/GlobalISel/RegBankSelect.h

103–105

With respect to the cost function, it should be optimal. I don't have a detailed proof yet, but the intuition is that it computes the cost of putting a certain register in a certain register bank, and by selecting the choice with lowest cost and working its way backwards to achieve that, it really should give the optimal solution. However, there is a stage in the algorithm where it may need to rematerialize the instruction (a certain situation when there exist multiple usages), and there I'm not sure whether optimality is kept...

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

1603

Don't know; I just copied what was already done in greedy, so you may be right...

1608

I agree, it's not a good name. I'll see if I can either get rid of this function, or else put it directly in MachineOperand.

1608–1610

You mean this works even if MO is not actually a register? I just assumed that you're not allowed to invoke getReg() unless you are certain that MO is really a register.

1703–1704

Yes, that's correct.

1732

I need to have a new position of insertion for each instruction, hence the creation of a new MachineIRBuilder each time. Is it possible to keep the same MachineIRBuilder and simply change the insertion point, without affecting already inserted instructions?

1735–1736

Are you saying that I should rewrite the code to make use of applyMappingImpl, such that both single- and multi-pass make use of it? Because currently the multi-pass doesn't use it at all.

1863

For uniformity, I decided to treat all instructions (except debug, which are skipped) equally in order to preserve the cost chain and register bank preferences. Hence this step will look at instructions which by themselves are not subject to regbankselect, but they may produce results which are used by instructions that are.

2007

What name would you have liked instead? =)

2102

Hm, true. The code below assumes that there's exactly one such def, and if there are multiple explicit defs it should crash as it cannot handle such cases at the moment.

[ehjogab]

Fix lint warnings

[ehjogab]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

1608–1610

Just checked MachineOperand.h, and there's an assert that will fail if getReg() is invoked and isReg() does not hold.

[ehjogab]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

1608–1610

Argh, my mistake; I saw what you meant now...

[ehjogab]

Fixes based on arsenm's comments

[ehjogab]

Fixed arsenm's comment on MachineIRBuilder

[gargaroff]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

1885

This line is causing an assertion with some of our tests .ll tests as it tries to access the regbank of a physical register.

You can provoke the assertion in existing AArch64 tests by adding RegBankSelect::Optimal to the RegBankSelect constructor call in AArch64TargetMachine.cpp.

One of the tests triggering this for example is llvm/test/CodeGen/AArch64/GlobalISel/regbank-ceil.ll.

[ehjogab]

• fix bug when register is a physical register
• fix lint warnings

[ehjogab]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

1885

Ah, apparently getRegBankOrNull() fails when the register is not a virtual register. This has been fixed in the update. Thanks for spotting this!

[ehjogab]

replace 'optimal' with 'global'

[ehjogab]

So what happens now? Should it be merge as is, or does it need to be tested more stringently before that happens? Or are there any further changes that need to be made?

[gargaroff]

I haven't had the time to test this in the new state yet, but I would love to see this integrated. However I'm not in a position to review and approve this. Someone of the GlobalISel folks should do that. As for testing, ideally you could simply leverage the existing tests of the existing GlobalISel backends by enabling this algorithm conditionally. This also requires the approval of those backend maintainers however.

Maybe it would make sense to ping the mailing list again, explaining the current state, giving some numbers how this algorithm impacts compile time and code gen, and try to discuss some integration strategy.

[ehjogab]

In D90304#2385167, @gargaroff wrote:

I haven't had the time to test this in the new state yet, but I would love to see this integrated. However I'm not in a position to review and approve this. Someone of the GlobalISel folks should do that. As for testing, ideally you could simply leverage the existing tests of the existing GlobalISel backends by enabling this algorithm conditionally. This also requires the approval of those backend maintainers however.

Maybe it would make sense to ping the mailing list again, explaining the current state, giving some numbers how this algorithm impacts compile time and code gen, and try to discuss some integration strategy.

Thanks for your suggestions! I'll attend to them when my work pipeline has cleared up a bit.

[tschuett]

How about a test-case with fast, greedy, and global to show the differences?

[ehjogab]

In D90304#2390935, @tschuett wrote:

How about a test-case with fast, greedy, and global to show the differences?

That's a good idea! Unfortunately, I don't know of any such test case. I will consult the mailing list for this; I know there has been some discussion where users were not happy with what the greedy algorithm produced.

[tschuett]

Sorry for being terse. What I meant to say, you could take an existing test case and show the effects of the different algorithms. There is probably an existing test case for the existing algorithms.

[ehjogab]

In D90304#2391033, @tschuett wrote:

Sorry for being terse. What I meant to say, you could take an existing test case and show the effects of the different algorithms. There is probably an existing test case for the existing algorithms.

Indeed, there exists ample test cases for regbank-select (at least in some targets). However, so far the ones I have seen have been quite small and therefore would probably not benefit from running the global variant. It would be good to have a test case where it is known that the greedy algorithm chooses poorly and hence the global variant should show improvement, and I recall that there was mentioning of such a case in the mailing list. In lack of such input, I will look into the existing test cases and see what I can come up with.

This does of course not exclude the need for tests showing that the global variant produces the same results as the other algorithms when there's no better solution to be had.

[ehjogab]

Rewrote code to make use of applyMapping(). Now fast, greedy, and global version
all use the same code for enforcing the selection of instruction mappings.

[ehjogab]

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

1735–1736

Feature disparity addressed.

[ehjogab]

Rearranged function declarations in RegBankSelect.cpp (NFC)

[ehjogab]

• Improved selection: Now choosing the mapping with the highest utility instead of lowest cost, which should direct optimization towards blocks with high frequency.
• Reduce vector copying.

[ehjogab]

Bug fix

[ehjogab]

Use MappingCost instead of int for representing costs.

[ehjogab]

Bug fixes

[ehjogab]

More bugfixes

[ehjogab]

• Directly apply mapping of there is only one. This leads to improved performance as well as improved code quality for targets that only output a single mapping that is context-dependent (now only failing 32 testcases when forcing greedy to use global instead).
• Bug fix

llvm/include/llvm/CodeGen/GlobalISel/RegBankSelect.h

 //=- llvm/CodeGen/GlobalISel/RegBankSelect.h - Reg Bank Selector --*- 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
 //
 //===----------------------------------------------------------------------===//
 //

 /// tmp1(B_REGBANK) = COPY v1
 /// v2(B_REGBANK) = G_ADD i32 tmp0, tmp1
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H
 #define LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include <cassert>
 #include <cstdint>
public:
 
   /// List of the modes supported by the RegBankSelect pass.
   enum Mode {
     /// Assign the register banks as fast as possible (default).
     Fast,
     /// Greedily minimize the cost of assigning register banks.
     /// This should produce code of greater quality, but will
     /// require more compile time.
-    Greedy
+    Greedy,
+    /// Globally minimize the cost of assigning register banks.
+    /// This should increase code quality, but at the cost of
+    /// longer compile time.
+    Global
   };
 
   /// Abstract class used to represent an insertion point in a CFG.
   /// This class records an insertion point and materializes it on
   /// demand.
   /// It allows to reason about the frequency of this insertion point,
   /// without having to logically materialize it (e.g., on an edge),
   /// before we actually need to insert something.
public:
 
     /// Saturate the cost to the maximal representable value.
     void saturate();
 
     /// Return an instance of MappingCost that represents an
     /// impossible mapping.
     static MappingCost ImpossibleCost();
 
+    /// Return this cost a single value. This value saturates in case of
+    /// overflow.
+    uint64_t getFlattenedValue() const {
+      uint64_t FlattenedValue = LocalFreq * LocalCost;
+      if (LocalFreq > 0 && FlattenedValue < LocalCost) {
+        return UINT64_MAX;
+      }
+      FlattenedValue += NonLocalCost;
+      if (FlattenedValue < NonLocalCost) {
+        return UINT64_MAX;
+      }
+      return FlattenedValue;
+    }
+
+    /// Return this cost a single value without taking the frequency into
+    /// account. This value saturates in case of overflow.
+    uint64_t getFlattenedValueWithoutFreq() const {
+      uint64_t FlattenedValue = LocalCost + NonLocalCost;
+      if (FlattenedValue < LocalCost) {
+        return UINT64_MAX;
+      }
+      return FlattenedValue;
+    }
+
     /// Check if this is less than \p Cost.
     bool operator<(const MappingCost &Cost) const;
     /// Check if this is equal to \p Cost.
     bool operator==(const MappingCost &Cost) const;
     /// Check if this is not equal to \p Cost.
     bool operator!=(const MappingCost &Cost) const { return !(*this == Cost); }
     /// Check if this is greater than \p Cost.
     bool operator>(const MappingCost &Cost) const {
       return *this != Cost && Cost < *this;
     }
+    /// Check if this is greater than or equal to \p Cost.
+    bool operator>=(const MappingCost &Cost) const {
+      return !(*this < Cost);
+    }
 
     /// Print this on dbgs() stream.
     void dump() const;
 
     /// Print this on \p OS;
     void print(raw_ostream &OS) const;
 
     /// Overload the stream operator for easy debug printing.
     friend raw_ostream &operator<<(raw_ostream &OS, const MappingCost &Cost) {
       Cost.print(OS);
       return OS;
     }
   };
 
+  /// Determines the state of an InstructionMapping.
+  enum InstrMapStatus {
+    /// This mapping should not be considered.
+    NOTHING,
+    /// This mapping has been selected.
+    SELECTED,
+    /// This mapping is needed and therefore will be selected at a later point.
+    USED
+  };
+
+  /// Convenient types to represent vectors with different content but equal
+  /// lengths.
+  /// TODO: use MappingCost for costs
+  using InstrMapCosts = SmallVector<MappingCost, 4>;
+  using InstrMapScores = SmallVector<uint64_t, 4>;
+  using InstrMapDestRegBanks = SmallVector<const RegisterBank *, 4>;
+  using InstrMapDestRegisters = SmallVector<Register, 4>;
+  using InstrMapStatuses = SmallVector<InstrMapStatus, 4>;
+
+  /// Contains the global regbank-select state for an instruction.
+  struct GlobalStateOfInstr {
+    /// The instruction of this state.
+    MachineInstr &MI;
+
+    /// The InstructionMappings available for this instruction.
+    RegisterBankInfo::InstructionMappings Mappings;
+
+    /// The register bank of each InstructionMapping.
+    InstrMapDestRegBanks DestRBs;
+
+    /// The cost of applying each InstructionMapping.
+    InstrMapCosts Costs;
+
+    /// The total utility score of each InstructionMapping. The utility score
+    /// is the sum of the costs of all instructions that make use of a given
+    /// InstructionMapping.
+    InstrMapScores UtilScores;
+
+    /// The current status of each InstructionMapping.
+    InstrMapStatuses Statuses;
+
+    GlobalStateOfInstr(MachineInstr &MI) : MI(MI) {}
+  };
+
   /// Interface to the target lowering info related
   /// to register banks.
   const RegisterBankInfo *RBI = nullptr;
 
   /// MRI contains all the register class/bank information that this
   /// pass uses and updates.
   MachineRegisterInfo *MRI = nullptr;
 
   /// Information on the register classes for the current function.
   const TargetRegisterInfo *TRI = nullptr;
 
   /// Get the frequency of blocks.
   /// This is required for non-fast mode.
   MachineBlockFrequencyInfo *MBFI = nullptr;
 
   /// Get the frequency of the edges.
   /// This is required for non-fast mode.
   MachineBranchProbabilityInfo *MBPI = nullptr;
 
   /// Current optimization remark emitter. Used to report failures.
   std::unique_ptr<MachineOptimizationRemarkEmitter> MORE;
 
+  /// Global regbank-select state for a particular instruction.
+  DenseMap<MachineInstr *, GlobalStateOfInstr> GSIMIMap;
+
   /// Helper class used for every code morphing.
   MachineIRBuilder MIRBuilder;
 
   /// Optimization mode of the pass.
   Mode OptMode;
 
   /// Current target configuration. Controls how the pass handles errors.
   const TargetPassConfig *TPC;
 
-  /// Assign the register bank of each operand of \p MI.
+  /// Assign the register bank of each operand of \p MI. This is used in fast
+  /// or greedy mode.
   /// \return True on success, false otherwise.
-  bool assignInstr(MachineInstr &MI);
+  bool assignInstrLocal(MachineInstr &MI);
 
   /// Initialize the field members using \p MF.
   void init(MachineFunction &MF);
 
   /// Check if \p Reg is already assigned what is described by \p ValMapping.
   /// \p OnlyAssign == true means that \p Reg just needs to be assigned a
   /// register bank.  I.e., no repairing is necessary to have the
   /// assignment match.
private:
   /// \p BestCost == nullptr, the mapping cost is actually not
   /// computed.
   MappingCost
   computeMapping(MachineInstr &MI,
                  const RegisterBankInfo::InstructionMapping &InstrMapping,
                  SmallVectorImpl<RepairingPlacement> &RepairPts,
                  const MappingCost *BestCost = nullptr);
 
+  /// Compute the repairing placement for applying \p InstrMapping to \p MI.
+  /// This clears \p RepairPts before adding new placements.
+  /// \return True if repairs were successfully computed.
+  bool computeRepair(MachineInstr &MI,
+                     const RegisterBankInfo::InstructionMapping &InstrMapping,
+                     SmallVectorImpl<RepairingPlacement> &RepairPts);
+
+  /// Compute the repairing placement for applying \p ValMapping to operand at
+  /// \p OpIdx in \p MI.
+  /// \return True if repairs were successfully computed.
+  bool computeRepair(MachineInstr &MI,
+                     const RegisterBankInfo::ValueMapping &ValMapping,
+                     unsigned OpIdx,
+                     SmallVectorImpl<RepairingPlacement> &RepairPts);
+
   /// When \p RepairPt involves splitting to repair \p MO for the
   /// given \p ValMapping, try to change the way we repair such that
   /// the splitting is not required anymore.
   ///
   /// \pre \p RepairPt.hasSplit()
   /// \pre \p MO == MO.getParent()->getOperand(\p RepairPt.getOpIdx())
   /// \pre \p ValMapping is the mapping of \p MO for MO.getParent()
   ///      that implied \p RepairPt.
   void tryAvoidingSplit(RegBankSelect::RepairingPlacement &RepairPt,
                         const MachineOperand &MO,
                         const RegisterBankInfo::ValueMapping &ValMapping) const;
 
   /// Apply \p Mapping to \p MI. \p RepairPts represents the different
   /// mapping action that need to happen for the mapping to be
   /// applied.
   /// \return True if the mapping was applied sucessfully, false otherwise.
   bool applyMapping(MachineInstr &MI,
                     const RegisterBankInfo::InstructionMapping &InstrMapping,
                     SmallVectorImpl<RepairingPlacement> &RepairPts);
 
+  /// Make a single pass over the instructions and select register banks. This
+  /// is run when in Fast or Greedy mode.
+  void selectRegBanksSinglePass(MachineFunction &MF);
+
+  /// Make multiple passes over the instructions:
+  ///   1. Compute the costs of selecting a particular register bank (top down).
+  ///   2. Find the selection of register banks (bottom up).
+  ///   3. Assign register banks (top down).
+  /// This is run when in Global mode.
+  void selectRegBanksMultiPass(MachineFunction &MF);
+
+  /// Clears all variables used for containing the global regbank-select state.
+  void clearGlobalState();
+
+  /// Check if \p MI has a global regbank-select state associated with it.
+  bool hasGSIOfMI(MachineInstr &MI);
+
+  /// Get the global regbank-select state associated with \p MI.
+  GlobalStateOfInstr &getGSIOfMI(MachineInstr &MI);
+
+  /// Get the global regbank-select state associated with the instruction that
+  /// defines \p Reg.
+  GlobalStateOfInstr &getGSIOfDefOfReg(Register Reg);
+
+  unsigned getIdxOfMatchingDestRegBank(GlobalStateOfInstr &GSI,
+                                       const RegisterBank *DesiredRegBank);
+
+  /// Compute cost for the given instruction and mappings. If \p Mappings
+  /// contains a \p NULL entry, then the instruction will be treated as an
+  /// instruction whose operands use registers that have been pre-assigned
+  /// either a register bank or register class.
+  /// \return True if successful, false otherwise.
+  bool computeGlobalCost(MachineInstr &MI,
+                         RegisterBankInfo::InstructionMappings &Mappings);
+
+  /// Mark the corresponding InstructionMapping of each operand in the given
+  /// InstructionMapping as used.
+  void markOperandsAsUsed(MachineInstr &MI, unsigned Score,
+                          const RegisterBankInfo::InstructionMapping *IMap);
+
+  /// Selects the \p InstructionMapping with lowest cost for the given \p MI.
+  bool selectGlobalInstrMapping(MachineInstr &MI);
+
+  /// Compute lowest cost for getting the value associated with the given \p GSI
+  /// into the desired register bank. The cost is cached in \p GSI for
+  /// subsequent lookups.
+  /// \return Lowest cost.
+  MappingCost
+  computeLowestCostOfDstInRegBank(GlobalStateOfInstr &GSI,
+                                  const RegisterBank *DesiredRegBank);
+
+  /// Assign the register bank of each operand of \p MI. This is used in global
+  /// mode.
+  /// \return True on success, false otherwise.
+  bool assignInstrGlobal(MachineInstr &MI);
+
 public:
   /// Create a RegBankSelect pass with the specified \p RunningMode.
   RegBankSelect(Mode RunningMode = Fast);
 
   StringRef getPassName() const override { return "RegBankSelect"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 

llvm/include/llvm/CodeGen/GlobalISel/RegisterBankInfo.h

 //===- llvm/CodeGen/GlobalISel/RegisterBankInfo.h ---------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
getInstructionMapping(unsigned ID, unsigned Cost,
     return getInstructionMappingImpl(/*IsInvalid*/ false, ID, Cost,
                                      OperandsMapping, NumOperands);
   }
 
   /// Method to get a uniquely generated invalid InstructionMapping.
   const InstructionMapping &getInvalidInstructionMapping() const {
     return getInstructionMappingImpl(/*IsInvalid*/ true);
   }
+
+  /// Method to get a InstructionMapping that corresponds to a given
+  /// MachineInstruction.
+  const InstructionMapping &
+  getInstructionMapping(unsigned ID, unsigned Cost, const MachineInstr &MI,
+                        const MachineRegisterInfo &MRI,
+                        const TargetRegisterInfo &TRI) const;
   /// @}
 
   /// Get the register bank for the \p OpIdx-th operand of \p MI form
   /// the encoding constraints, if any.
   ///
   /// \return A register bank that covers the register class of the
   /// related encoding constraints or nullptr if \p MI did not provide
   /// enough information to deduce it.

llvm/include/llvm/CodeGen/MachineOperand.h

 //===-- llvm/CodeGen/MachineOperand.h - MachineOperand class ----*- 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
 //
 //===----------------------------------------------------------------------===//
 //
public:
   void dump() const;
 
   //===--------------------------------------------------------------------===//
   // Accessors that tell you what kind of MachineOperand you're looking at.
   //===--------------------------------------------------------------------===//
 
   /// isReg - Tests if this is a MO_Register operand.
   bool isReg() const { return OpKind == MO_Register; }
+  /// isVirtualReg - Tests if this is a MO_Register operand and that its
+  /// register is virtual.
+  bool isVirtualReg() const { return isReg() && getReg().isVirtual(); }
   /// isImm - Tests if this is a MO_Immediate operand.
   bool isImm() const { return OpKind == MO_Immediate; }
   /// isCImm - Test if this is a MO_CImmediate operand.
   bool isCImm() const { return OpKind == MO_CImmediate; }
   /// isFPImm - Tests if this is a MO_FPImmediate operand.
   bool isFPImm() const { return OpKind == MO_FPImmediate; }
   /// isMBB - Tests if this is a MO_MachineBasicBlock operand.
   bool isMBB() const { return OpKind == MO_MachineBasicBlock; }

llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp

 //==- llvm/CodeGen/GlobalISel/RegBankSelect.cpp - RegBankSelect --*- 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
 //
 //===----------------------------------------------------------------------===//
 /// \file

 
 using namespace llvm;
 
 static cl::opt<RegBankSelect::Mode> RegBankSelectMode(
     cl::desc("Mode of the RegBankSelect pass"), cl::Hidden, cl::Optional,
     cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast",
                           "Run the Fast mode (default mapping)"),
                clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy",
-                          "Use the Greedy mode (best local mapping)")));
+                          "Use the Greedy mode (better local mapping)"),
+               clEnumValN(RegBankSelect::Mode::Global, "regbankselect-global",
+                          "Use the Global mode (better global mapping)")));
 
 char RegBankSelect::ID = 0;
 
 INITIALIZE_PASS_BEGIN(RegBankSelect, DEBUG_TYPE,
                       "Assign register bank of generic virtual registers",
                       false, false);
 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
RegBankSelect::MappingCost RegBankSelect::computeMapping(
   for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands();
        OpIdx != EndOpIdx; ++OpIdx) {
     const MachineOperand &MO = MI.getOperand(OpIdx);
     if (!MO.isReg())
       continue;
     Register Reg = MO.getReg();
     if (!Reg)
       continue;
-    LLVM_DEBUG(dbgs() << "Opd" << OpIdx << '\n');
+    LLVM_DEBUG(dbgs() << "Opd " << OpIdx << '\n');
+
+    // Compute repairing placement, if needed.
     const RegisterBankInfo::ValueMapping &ValMapping =
         InstrMapping.getOperandMapping(OpIdx);
-    // If Reg is already properly mapped, this is free.
-    bool Assign;
-    if (assignmentMatch(Reg, ValMapping, Assign)) {
-      LLVM_DEBUG(dbgs() << "=> is free (match).\n");
-      continue;
+    unsigned NumPrevRepairs = RepairPts.size();
+    if (!computeRepair(MI, ValMapping, OpIdx, RepairPts)) {
+      return MappingCost::ImpossibleCost();
     }
-    if (Assign) {
-      LLVM_DEBUG(dbgs() << "=> is free (simple assignment).\n");
-      RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this,
-                                                RepairingPlacement::Reassign));
+    unsigned NumAddedRepairs = RepairPts.size() - NumPrevRepairs;
+    if (NumAddedRepairs == 0) {
       continue;
     }
-
-    // Find the insertion point for the repairing code.
-    RepairPts.emplace_back(
-        RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert));
+    assert(NumAddedRepairs == 1 &&
+           "Cannot handle situation when multiple repairing placements has " \
+           "been added!");
     RepairingPlacement &RepairPt = RepairPts.back();
-
-    // If we need to split a basic block to materialize this insertion point,
-    // we may give a higher cost to this mapping.
-    // Nevertheless, we may get away with the split, so try that first.
-    if (RepairPt.hasSplit())
-      tryAvoidingSplit(RepairPt, MO, ValMapping);
-
-    // Check that the materialization of the repairing is possible.
-    if (!RepairPt.canMaterialize()) {
-      LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n");
-      return MappingCost::ImpossibleCost();
+    if (RepairPt.getKind() != RepairingPlacement::Insert) {
+      continue;
     }
 
     // Account for the split cost and repair cost.
     // Unless the cost is already saturated or we do not care about the cost.
     if (!BestCost || Saturated)
       continue;
 
     // To get accurate information we need MBFI and MBPI.
for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
       if (Saturated)
         break;
     }
   }
   LLVM_DEBUG(dbgs() << "Total cost is: " << Cost << "\n");
   return Cost;
 }
 
+bool RegBankSelect::computeRepair(
+    MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
+    SmallVectorImpl<RepairingPlacement> &RepairPts) {
+  RepairPts.clear();
+
+  LLVM_DEBUG(dbgs() << "  - Compute repairs for " << MI);
+
+  for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands();
+       OpIdx != EndOpIdx; ++OpIdx) {
+    LLVM_DEBUG(dbgs() << "    - Operand " << OpIdx << '\n');
+
+    // Compute repairing placement, if needed.
+    const RegisterBankInfo::ValueMapping &ValMapping =
+        InstrMapping.getOperandMapping(OpIdx);
+    if (!computeRepair(MI, ValMapping, OpIdx, RepairPts)) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+bool RegBankSelect::computeRepair(
+    MachineInstr &MI, const RegisterBankInfo::ValueMapping &ValMapping,
+    unsigned OpIdx, SmallVectorImpl<RepairingPlacement> &RepairPts) {
+  const MachineOperand &MO = MI.getOperand(OpIdx);
+  if (!MO.isReg()) {
+    return true;
+  }
+  Register Reg = MO.getReg();
+  if (!Reg) {
+    return true;
+  }
+
+  // If Reg is already properly mapped, this is free.
+  bool Assign;
+  if (assignmentMatch(Reg, ValMapping, Assign)) {
+    LLVM_DEBUG(dbgs() << "=> matching assignment (free).\n");
+    return true;
+  }
+  if (Assign) {
+    LLVM_DEBUG(dbgs() << "=> simple assignment (free).\n");
+    RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this,
+                                              RepairingPlacement::Reassign));
+    return true;
+  }
+
+  // Find the insertion point for the repairing code.
+  LLVM_DEBUG(dbgs() << "=> repair code (not free).\n");
+  RepairPts.emplace_back(
+      RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert));
+  RepairingPlacement &RepairPt = RepairPts.back();
+
+  // If we need to split a basic block to materialize this insertion point, we
+  // may give a higher cost to this mapping. Nevertheless, we may get away with
+  // the split, so try that first.
+  if (RepairPt.hasSplit())
+    tryAvoidingSplit(RepairPt, MO, ValMapping);
+
+  // Check that the materialization of the repairing is possible.
+  if (!RepairPt.canMaterialize()) {
+    LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n");
+    return false;
+  }
+
+  return true;
+}
+
 bool RegBankSelect::applyMapping(
     MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
     SmallVectorImpl<RegBankSelect::RepairingPlacement> &RepairPts) {
   // OpdMapper will hold all the information needed for the rewriting.
   RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI);
 
   // First, place the repairing code.
   for (RepairingPlacement &RepairPt : RepairPts) {
bool RegBankSelect::applyMapping(
 
   // Second, rewrite the instruction.
   LLVM_DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n');
   RBI->applyMapping(OpdMapper);
 
   return true;
 }
 
-bool RegBankSelect::assignInstr(MachineInstr &MI) {
+bool RegBankSelect::assignInstrLocal(MachineInstr &MI) {
   LLVM_DEBUG(dbgs() << "Assign: " << MI);
   // Remember the repairing placement for all the operands.
   SmallVector<RepairingPlacement, 4> RepairPts;
 
   const RegisterBankInfo::InstructionMapping *BestMapping;
   if (OptMode == RegBankSelect::Mode::Fast) {
     BestMapping = &RBI->getInstrMapping(MI);
     MappingCost DefaultCost = computeMapping(MI, *BestMapping, RepairPts);
bool RegBankSelect::assignInstrLocal(MachineInstr &MI) {
 
   LLVM_DEBUG(dbgs() << "Best Mapping: " << *BestMapping << '\n');
 
   // After this call, MI may not be valid anymore.
   // Do not use it.
   return applyMapping(MI, *BestMapping, RepairPts);
 }
 
-bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) {
-  // If the ISel pipeline failed, do not bother running that pass.
-  if (MF.getProperties().hasProperty(
-          MachineFunctionProperties::Property::FailedISel))
-    return false;
-
-  LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
-  const Function &F = MF.getFunction();
-  Mode SaveOptMode = OptMode;
-  if (F.hasOptNone())
-    OptMode = Mode::Fast;
-  init(MF);
-
-#ifndef NDEBUG
-  // Check that our input is fully legal: we require the function to have the
-  // Legalized property, so it should be.
-  // FIXME: This should be in the MachineVerifier.
-  if (!DisableGISelLegalityCheck)
-    if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
-      reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
-                         "instruction is not legal", *MI);
-      return false;
-    }
-#endif
+static inline bool isUnassignableMachineInstr(const MachineInstr &MI) {
+  return
+    // Ignore target-specific post-isel instructions: they should use proper
+    // regclasses.
+    (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode()) ||
+    // Ignore inline asm instructions: they should use physical
+    // registers/regclasses.
+    MI.isInlineAsm() ||
+    // Ignore debug info.
+    MI.isDebugInstr();
 
+void RegBankSelect::selectRegBanksSinglePass(MachineFunction &MF) {
   // 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);
+  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   for (MachineBasicBlock *MBB : RPOT) {
-    // Set a sensible insertion point so that subsequent calls to
-    // MIRBuilder.
+    // Set a sensible insertion point for 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.
+      // iterator beforehand.
       MachineInstr &MI = *MII++;
 
-      // Ignore target-specific post-isel instructions: they should use proper
-      // regclasses.
-      if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode())
+      if (isUnassignableMachineInstr(MI)) {
         continue;
+      }
 
-      // Ignore inline asm instructions: they should use physical
-      // registers/regclasses
-      if (MI.isInlineAsm())
+      if (!assignInstrLocal(MI)) {
+        reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
+                           "unable to map instruction", MI);
+        return;
+      }
+
+      // 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();
+        }
+      }
+    }
+  }
+}
+
+void RegBankSelect::selectRegBanksMultiPass(MachineFunction &MF) {
+  // Compute the costs of selecting a particular register bank. Walk the
+  // instructions top-down to make sure all registers have been assigned costs
+  // before computing cost of current instruction.
+  LLVM_DEBUG(dbgs() << "Computing costs...\n");
+  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
+  for (MachineBasicBlock *MBB : RPOT) {
+    // Set a sensible insertion point for 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
+      // beforehand.
+      MachineInstr &MI = *MII++;
+
+      if (isUnassignableMachineInstr(MI)) {
         continue;
+      }
 
-      // Ignore debug info.
-      if (MI.isDebugInstr())
+      RegisterBankInfo::InstructionMappings PossibleMappings;
+      PossibleMappings = RBI->getInstrPossibleMappings(MI);
+      if (PossibleMappings.empty()) {
+        reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
+                           "unable to find mappings for instruction", MI);
+        return;
+      }
+
+      LLVM_DEBUG(dbgs() << "- Processing " << MI);
+
+      if (!computeGlobalCost(MI, PossibleMappings)) {
+        reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
+                           "unable to compute cost for instruction", MI);
+        return;
+      }
+
+      // If there is only one mapping, select it directly. This is primarily to
+      // get expected result for targets that only return one mapping instead of
+      // all possible mappings, and the single mapping returned assumes that all
+      // input operands have already been assigned.
+      if (PossibleMappings.size() == 1) {
+        LLVM_DEBUG(dbgs() << "  Has only one mapping, select it now\n");
+        auto &GSI = getGSIOfMI(MI);
+        GSI.Statuses[0] = SELECTED;
+        const auto &SelectedMapping = GSI.Mappings[0];
+        assert(SelectedMapping->verify(MI) && "Invalid instruction mapping");
+        SmallVector<RepairingPlacement, 4> RepairPts;
+        if (!computeRepair(MI, *SelectedMapping, RepairPts)) {
+          reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
+                             "unable to compute repairs for instruction", MI);
+        }
+        if (!applyMapping(MI, *SelectedMapping, RepairPts)) {
+          reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
+                             "unable to apply mapping for instruction", MI);
+        }
+      }
+
+      // 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();
+        }
+      }
+    }
+  }
+
+  // Find selection of register banks. Walk the instructions bottom-up to make
+  // sure that that all uses of a register have been selected before selecting
+  // the register bank of the current instruction.
+  LLVM_DEBUG(dbgs() << "Selecting register bank selection...\n");
+  for (MachineBasicBlock *MBB : post_order(&MF)) {
+    if (MBB->empty()) {
+      continue;
+    }
+
+    bool ReachedBegin = false;
+    for (auto MII = std::prev(MBB->end()), Begin = MBB->begin(); !ReachedBegin;
+         MII--) {
+      if (MII == Begin) {
+        ReachedBegin = true;
+      }
+
+      auto &MI = *MII;
+      if (isUnassignableMachineInstr(MI)) {
+        continue;
+      }
+
+      LLVM_DEBUG(dbgs() << "- Processing " << MI);
+      if (!hasGSIOfMI(MI)) {
+        LLVM_DEBUG(dbgs() << "  Part of repair, do not process\n");
         continue;
+      }
+      if (getGSIOfMI(MI).Mappings.size() == 1) {
+        LLVM_DEBUG(dbgs() << "  Only one mapping, already selected\n");
+        continue;
+      }
 
-      if (!assignInstr(MI)) {
+      if (!selectGlobalInstrMapping(MI)) {
         reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
-                           "unable to map instruction", MI);
-        return false;
+                           "unable to select register banks", MI);
+      }
+    }
+  }
+
+  // Assign instructions. Walk the instructions top down.
+  LLVM_DEBUG(dbgs() << "Assigning instructions...\n");
+  for (MachineBasicBlock *MBB : RPOT) {
+    // Set a sensible insertion point for 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
+      // beforehand.
+      MachineInstr &MI = *MII++;
+
+      if (isUnassignableMachineInstr(MI)) {
+        continue;
+      }
+
+      LLVM_DEBUG(dbgs() << "- Processing " << MI);
+      if (!hasGSIOfMI(MI)) {
+        LLVM_DEBUG(dbgs() << "  Part of repair, do not process\n");
+        continue;
+      }
+      if (getGSIOfMI(MI).Mappings.size() == 1) {
+        LLVM_DEBUG(dbgs() << "  Only one mapping, already selected\n");
+        continue;
+      }
+
+      if (!assignInstrGlobal(MI)) {
+        reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
+                           "unable to assign instruction", MI);
       }
 
       // 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();
         }
       }
     }
   }
 
+  clearGlobalState();
+}
+
+static inline const RegisterBank *
+getRegBankOfOpInInstrMap(const RegisterBankInfo::InstructionMapping *InstrMap,
+                         unsigned Opx) {
+  assert(InstrMap->getNumOperands() >= Opx &&
+         "InstructionMapping has too few operands!");
+  const auto &ValMap = InstrMap->getOperandMapping(Opx);
+  assert(ValMap.NumBreakDowns > 0 && "No breakdowns in ValueMapping!");
+  return ValMap.BreakDown[0].RegBank;
+}
+
+static inline bool
+isAssignableReg(Register Reg, const MachineRegisterInfo &MRI) {
+  return MRI.getRegClassOrNull(Reg) || MRI.getRegBankOrNull(Reg);
+}
+
+unsigned
+RegBankSelect::getIdxOfMatchingDestRegBank(GlobalStateOfInstr &GSI,
+                                           const RegisterBank *DesiredRegBank) {
+  unsigned Idx = 0;
+  const unsigned NumIMaps = GSI.DestRBs.size();
+  assert(NumIMaps > 0 && "Instruction has no destination register banks!");
+  for (; Idx < NumIMaps; ++Idx) {
+    if (GSI.DestRBs[Idx] == DesiredRegBank) {
+      return Idx;
+    }
+  }
+  llvm_unreachable("Found no InstructionMapping with matching register bank!");
+}
+
+RegBankSelect::MappingCost RegBankSelect::computeLowestCostOfDstInRegBank(
+    GlobalStateOfInstr &GSI,
+    const RegisterBank *DesiredRegBank) {
+  auto &MI = GSI.MI;
+  LLVM_DEBUG(dbgs() << "      DefMI: " << MI);
+
+  auto &Mappings = GSI.Mappings;
+  assert(Mappings.size() > 0 && "No InstructionMappings found!");
+  assert(Mappings.size() == GSI.DestRBs.size() && "Mismatching sizes!");
+  assert(Mappings.size() == GSI.Costs.size() && "Mismatching sizes!");
+
+  // Find dst with matching register bank
+  for (unsigned Idx = 0; Idx < Mappings.size(); ++Idx) {
+    if (GSI.DestRBs[Idx] == DesiredRegBank) {
+      auto &Cost = GSI.Costs[Idx];
+      LLVM_DEBUG(dbgs() << "      Found register bank match at cost " << Cost
+                        << "\n");
+      return Cost;
+    }
+  }
+
+  // No match found. Find lowest cost of converting dest to register bank.
+  LLVM_DEBUG(dbgs() << "      No matching register bank found\n");
+  assert(MI.getNumExplicitDefs() > 0 && "Instruction has no defs!");
+  Register DestReg = MI.getOperand(0).getReg();
+  int BestIdx = -1;
+  const MappingCost ImpossibleCost = MappingCost::ImpossibleCost();
+  MappingCost BestCost = ImpossibleCost;
+  for (unsigned Idx = 0; Idx < Mappings.size(); ++Idx) {
+    MappingCost Cost = GSI.Costs[Idx];
+
+    LLVM_DEBUG(dbgs() << "        - InstructionMapping: " << *Mappings[Idx] <<
+               "\n");
+    LLVM_DEBUG(dbgs() << "          Cost: " << Cost << "\n");
+
+    // Skip mappings that already has too high cost.
+    if (Cost >= BestCost) {
+      LLVM_DEBUG(dbgs() << "          Too expensive mapping\n");
+      continue;
+    }
+
+    assert(MI.getNumExplicitDefs() > 0 && "Instruction has no defs!");
+    const RegisterBank *CurRegBank =
+        getRegBankOfOpInInstrMap(GSI.Mappings[Idx], 0);
+    unsigned CopyCost = RBI->copyCost(*DesiredRegBank, *CurRegBank,
+                                      RBI->getSizeInBits(DestReg, *MRI, *TRI));
+    // TODO: use a dedicated constant for impossible copy cost.
+    if (CopyCost == std::numeric_limits<unsigned>::max()) {
+      LLVM_DEBUG(dbgs() << "          No such copy\n");
+      continue;
+    }
+    LLVM_DEBUG(dbgs() << "          Cost of copying: " << CopyCost << "\n");
+    Cost.addLocalCost(CopyCost);
+    if (Cost < BestCost) {
+      BestIdx = Idx;
+      BestCost = Cost;
+      LLVM_DEBUG(dbgs() << "        * New best cost: " << BestCost << "\n");
+    }
+  }
+  assert(BestIdx >= 0 && "No register bank conversion found!");
+  LLVM_DEBUG(dbgs() << "        Best InstructionMapping: " << *Mappings[BestIdx]
+                    << "\n");
+
+  // Make new entry for converting register bank for dest.
+  Mappings.emplace_back(Mappings[BestIdx]);
+  GSI.DestRBs.emplace_back(DesiredRegBank);
+  GSI.Costs.emplace_back(BestCost);
+  GSI.UtilScores.emplace_back(0);
+  GSI.Statuses.emplace_back(NOTHING);
+
+  return BestCost;
+}
+
+bool RegBankSelect::computeGlobalCost(
+    MachineInstr &MI, RegisterBankInfo::InstructionMappings &Mappings) {
+  auto Res = GSIMIMap.try_emplace(&MI, MI);
+  auto &GSI = (*Res.first).second;
+
+  // Compute costs for each InstructionMapping
+  for (const auto *IMap : Mappings) {
+    LLVM_DEBUG(dbgs() << "  - Processing mapping "; IMap->print(dbgs());
+               dbgs() << "\n");
+
+    // Start with cost of instruction itself.
+    MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent()) : 1);
+    Cost.addLocalCost(IMap->getCost());
+
+    // Add cost for getting each operand into the right register bank. For each
+    // operand, this cost is the cost of producing the operand plus the cost of
+    // putting it in the right register bank.
+    //
+    // NOTE: We could get a more accurate cost by simulating a repair, but that
+    // would be more expensive (and the question is whether that's worth it).
+    const unsigned NumOps = IMap->getNumOperands();
+    for (unsigned Opx = MI.getNumExplicitDefs(); Opx < NumOps; ++Opx) {
+      auto MO = MI.getOperand(Opx);
+      if (!MO.isVirtualReg() || !isAssignableReg(MO.getReg(), *MRI)) {
+        continue;
+      }
+
+      LLVM_DEBUG(dbgs() << "    - Operand: " << Opx << "\n");
+
+      const RegisterBank *RB = getRegBankOfOpInInstrMap(IMap, Opx);
+      auto &GSI = getGSIOfDefOfReg(MO.getReg());
+      MappingCost DefMICost = computeLowestCostOfDstInRegBank(GSI, RB);
+      LLVM_DEBUG(dbgs() << "      Cost of operand: " << DefMICost << "\n");
+      uint64_t FlattenedDefMICost = DefMICost.getFlattenedValueWithoutFreq();
+      LLVM_DEBUG(dbgs() << "      Amount to count towards mapping cost: " <<
+                 FlattenedDefMICost << "\n");
+      Cost.addLocalCost(FlattenedDefMICost);
+    }
+    LLVM_DEBUG(dbgs() << "    Cost of mapping: " << Cost << "\n");
+
+    bool HasDest = MI.getNumExplicitDefs() > 0;
+    const RegisterBank *DestRB =
+        HasDest ? getRegBankOfOpInInstrMap(IMap, 0) : nullptr;
+    GSI.Mappings.emplace_back(IMap);
+    GSI.Costs.emplace_back(Cost);
+    GSI.UtilScores.emplace_back(0);
+    GSI.DestRBs.emplace_back(DestRB);
+    GSI.Statuses.emplace_back(NOTHING);
+  }
+
+  return true;
+}
+
+void RegBankSelect::markOperandsAsUsed(
+    MachineInstr &MI, unsigned Score,
+    const RegisterBankInfo::InstructionMapping *IMap) {
+  const unsigned NumOps = IMap->getNumOperands();
+  for (unsigned Opx = MI.getNumExplicitDefs(); Opx < NumOps; ++Opx) {
+    MachineOperand &MO = MI.getOperand(Opx);
+    if (!MO.isVirtualReg() || !isAssignableReg(MO.getReg(), *MRI)) {
+      continue;
+    }
+
+    const RegisterBank *RB = getRegBankOfOpInInstrMap(IMap, Opx);
+    LLVM_DEBUG(dbgs() << "    - Operand: " << Opx << ", reg bank: " << *RB
+                      << "\n");
+
+    auto &GSI = getGSIOfDefOfReg(MO.getReg());
+    unsigned MapIdx = getIdxOfMatchingDestRegBank(GSI, RB);
+    uint64_t UtilScore = GSI.UtilScores[MapIdx] + Score;
+    if (UtilScore < Score) {
+      // Sum has overflown; saturate value.
+      UtilScore = UINT64_MAX;
+    }
+    GSI.UtilScores[MapIdx] = UtilScore;
+    if (GSI.Statuses[MapIdx] == NOTHING) {
+      GSI.Statuses[MapIdx] = USED;
+    }
+  }
+}
+
+bool RegBankSelect::hasGSIOfMI(MachineInstr &MI) {
+  auto DI = GSIMIMap.find(&MI);
+  return DI != GSIMIMap.end();
+}
+
+RegBankSelect::GlobalStateOfInstr &RegBankSelect::getGSIOfMI(MachineInstr &MI) {
+  auto DI = GSIMIMap.find(&MI);
+  assert(DI != GSIMIMap.end() && "No such instruction in GSIMIMap!");
+  return DI->second;
+}
+
+RegBankSelect::GlobalStateOfInstr &
+RegBankSelect::getGSIOfDefOfReg(Register Reg) {
+  MachineInstr *DefMI = MRI->getVRegDef(Reg);
+  assert(DefMI && "No defining instruction");
+  return getGSIOfMI(*DefMI);
+}
+
+bool RegBankSelect::selectGlobalInstrMapping(MachineInstr &MI) {
+  auto &GSI = getGSIOfMI(MI);
+
+  // Determine whether this instruction is a leaf in the data-flow graph.
+  const unsigned NumIMaps = GSI.Mappings.size();
+  assert(NumIMaps > 0 && "Instruction has no InstructionMappings!");
+  bool HasUses = false;
+  for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) {
+    int Status = GSI.Statuses[Idx];
+    if (Status == USED) {
+      HasUses = true;
+      break;
+    }
+  }
+
+  int BestIdx = -1;
+  if (HasUses) {
+    LLVM_DEBUG(dbgs() << "  Looking for mapping with highest utility score\n");
+    uint64_t BestScore = 0;
+    for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) {
+      if (GSI.Statuses[Idx] != USED) {
+        continue;
+      }
+      const uint64_t Score = GSI.UtilScores[Idx];
+      if (BestIdx < 0 || Score > BestScore) {
+        BestScore = Score;
+        BestIdx = Idx;
+      }
+    }
+  }
+  else {
+    LLVM_DEBUG(dbgs() << "  Looking for mapping with lowest cost\n");
+    MappingCost BestCost = MappingCost::ImpossibleCost();
+    for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) {
+      const MappingCost &Cost = GSI.Costs[Idx];
+      if (Cost < BestCost) {
+        BestCost = Cost;
+        BestIdx = Idx;
+      }
+    }
+  }
+  assert(BestIdx >= 0 && "No mapping found!");
+
+  GSI.Statuses[BestIdx] = SELECTED;
+  const auto *Mapping = GSI.Mappings[BestIdx];
+  MappingCost Cost = GSI.Costs[BestIdx];
+  LLVM_DEBUG(dbgs() << "  * Selecting "; Mapping->print(dbgs()));
+  if (HasUses) {
+    uint64_t Score = GSI.UtilScores[BestIdx];
+    LLVM_DEBUG(dbgs() << ", score: " << Score << "\n");
+  } else {
+    LLVM_DEBUG(dbgs() << ", cost: " << Cost << "\n");
+
+  }
+  markOperandsAsUsed(MI, Cost.getFlattenedValue(), Mapping);
+
+  return true;
+}
+
+bool RegBankSelect::assignInstrGlobal(MachineInstr &MI) {
+  auto &GSI = getGSIOfMI(MI);
+
+  // Find selected instruction mapping.
+  int SelectedIdx = -1;
+  for (unsigned Idx = 0, NumIMaps = GSI.Mappings.size(); Idx < NumIMaps;
+       ++Idx) {
+    if (GSI.Statuses[Idx] == SELECTED) {
+      SelectedIdx = Idx;
+      break;
+    }
+  }
+  assert(SelectedIdx >= 0 && "No instruction mapping selected!");
+  const auto *SelectedMapping = GSI.Mappings[SelectedIdx];
+  LLVM_DEBUG(dbgs() << "  - Best mapping: "; SelectedMapping->print(dbgs());
+             dbgs() << "\n");
+
+  // Apply the mapping.
+  assert(SelectedMapping->verify(MI) && "Invalid instruction mapping");
+  SmallVector<RepairingPlacement, 4> RepairPts;
+  if (!computeRepair(MI, *SelectedMapping, RepairPts)) {
+    return false;
+  }
+  if (!applyMapping(MI, *SelectedMapping, RepairPts)) {
+    return false;
+  }
+
+  return true;
+}
+
+void RegBankSelect::clearGlobalState() {
+  GSIMIMap.clear();
+}
+
+bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) {
+  // If the ISel pipeline failed, do not bother running that pass.
+  if (MF.getProperties().hasProperty(
+          MachineFunctionProperties::Property::FailedISel))
+    return false;
+
+  LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
+  const Function &F = MF.getFunction();
+  Mode SaveOptMode = OptMode;
+  if (F.hasOptNone())
+    OptMode = Mode::Fast;
+  init(MF);
+
+#ifndef NDEBUG
+  // Check that our input is fully legal: we require the function to have the
+  // Legalized property, so it should be.
+  // FIXME: This should be in the MachineVerifier.
+  if (!DisableGISelLegalityCheck)
+    if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
+      reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
+                         "instruction is not legal", *MI);
+      return false;
+    }
+#endif
+
+  if (OptMode == Mode::Global) {
+    selectRegBanksMultiPass(MF);
+  } else {
+    selectRegBanksSinglePass(MF);
+  }
+
   OptMode = SaveOptMode;
   return false;
 }
 
 //------------------------------------------------------------------------------
 //                  Helper Classes Implementation
 //------------------------------------------------------------------------------
 RegBankSelect::RepairingPlacement::RepairingPlacement(
if (*this == ImpossibleCost()) {
     OS << "impossible";
     return;
   }
   if (isSaturated()) {
     OS << "saturated";
     return;
   }
   OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost;
 }

llvm/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp

 //===- llvm/CodeGen/GlobalISel/RegisterBankInfo.cpp --------------*- 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
 //
 //===----------------------------------------------------------------------===//
 /// \file
for (Register VReg : getVRegs(Idx)) {
       if (!IsFirstNewVReg)
         OS << ", ";
       IsFirstNewVReg = false;
       OS << printReg(VReg, TRI);
     }
     OS << "])";
   }
 }
+
+const RegisterBankInfo::InstructionMapping &
+RegisterBankInfo::getInstructionMapping(unsigned ID, unsigned Cost,
+                                        const MachineInstr &MI,
+                                        const MachineRegisterInfo &MRI,
+                                        const TargetRegisterInfo &TRI) const {
+  SmallVector<const RegisterBankInfo::ValueMapping *, 4> OMapVec;
+  for (auto MO : MI.operands()) {
+    const RegisterBank *RegBank;
+    if (MO.isReg()) {
+      RegBank = getRegBank(MO.getReg(), MRI, TRI);
+    } else {
+      // Since this operand is not a register but we still need to provide a
+      // ValueMapping, any register bank will do as this value will never be
+      // looked at.
+      RegBank = &getRegBank(0);
+    }
+    assert(RegBank && "Could not find register bank!");
+    unsigned Len = RegBank->getSize();
+    OMapVec.emplace_back(&getValueMapping(0, Len, *RegBank));
+  }
+  return getInstructionMapping(ID, Cost, getOperandsMapping(OMapVec),
+                               OMapVec.size());
+}