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

   1 //== llvm/CodeGen/GlobalISel/RegBankSelect.h - Reg Bank Selector -*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// \file This file describes the interface of the MachineFunctionPass
  11 /// responsible for assigning the generic virtual registers to register bank.
  12
  13 /// By default, the reg bank selector relies on local decisions to
  14 /// assign the register bank. In other words, it looks at one instruction
  15 /// at a time to decide where the operand of that instruction should live.
  16 ///
  17 /// At higher optimization level, we could imagine that the reg bank selector
  18 /// would use more global analysis and do crazier thing like duplicating
  19 /// instructions and so on. This is future work.
  20 ///
  21 /// For now, the pass uses a greedy algorithm to decide where the operand
  22 /// of an instruction should live. It asks the target which banks may be
  23 /// used for each operand of the instruction and what is the cost. Then,
  24 /// it chooses the solution which minimize the cost of the instruction plus
  25 /// the cost of any move that may be needed to to the values into the right
  26 /// register bank.
  27 /// In other words, the cost for an instruction on a register bank RegBank
  28 /// is: Cost of I on RegBank plus the sum of the cost for bringing the
  29 /// input operands from their current register bank to RegBank.
  30 /// Thus, the following formula:
  31 /// cost(I, RegBank) = cost(I.Opcode, RegBank) +
  32 ///    sum(for each arg in I.arguments: costCrossCopy(arg.RegBank, RegBank))
  33 ///
  34 /// E.g., Let say we are assigning the register bank for the instruction
  35 /// defining v2.
  36 /// v0(A_REGBANK) = ...
  37 /// v1(A_REGBANK) = ...
  38 /// v2 = G_ADD i32 v0, v1 <-- MI
  39 ///
  40 /// The target may say it can generate G_ADD i32 on register bank A and B
  41 /// with a cost of respectively 5 and 1.
  42 /// Then, let say the cost of a cross register bank copies from A to B is 1.
  43 /// The reg bank selector would compare the following two costs:
  44 /// cost(MI, A_REGBANK) = cost(G_ADD, A_REGBANK) + cost(v0.RegBank, A_REGBANK) +
  45 ///    cost(v1.RegBank, A_REGBANK)
  46 ///                     = 5 + cost(A_REGBANK, A_REGBANK) + cost(A_REGBANK,
  47 ///                                                             A_REGBANK)
  48 ///                     = 5 + 0 + 0 = 5
  49 /// cost(MI, B_REGBANK) = cost(G_ADD, B_REGBANK) + cost(v0.RegBank, B_REGBANK) +
  50 ///    cost(v1.RegBank, B_REGBANK)
  51 ///                     = 1 + cost(A_REGBANK, B_REGBANK) + cost(A_REGBANK,
  52 ///                                                             B_REGBANK)
  53 ///                     = 1 + 1 + 1 = 3
  54 /// Therefore, in this specific example, the reg bank selector would choose
  55 /// bank B for MI.
  56 /// v0(A_REGBANK) = ...
  57 /// v1(A_REGBANK) = ...
  58 /// tmp0(B_REGBANK) = COPY v0
  59 /// tmp1(B_REGBANK) = COPY v1
  60 /// v2(B_REGBANK) = G_ADD i32 tmp0, tmp1
  61 //
  62 //===----------------------------------------------------------------------===//
  63
  64 #ifndef LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H
  65 #define LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H
  66
  67 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
  68 #include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
  69 #include "llvm/CodeGen/MachineFunctionPass.h"
  70 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  71
  72 namespace llvm {
  73 // Forward declarations.
  74 class BlockFrequency;
  75 class MachineBranchProbabilityInfo;
  76 class MachineBlockFrequencyInfo;
  77 class MachineRegisterInfo;
  78 class TargetPassConfig;
  79 class TargetRegisterInfo;
  80 class raw_ostream;
  81
  82 /// This pass implements the reg bank selector pass used in the GlobalISel
  83 /// pipeline. At the end of this pass, all register operands have been assigned
  84 class RegBankSelect : public MachineFunctionPass {
  85 public:
  86   static char ID;
  87
  88   /// List of the modes supported by the RegBankSelect pass.
  89   enum Mode {
  90     /// Assign the register banks as fast as possible (default).
  91     Fast,
  92     /// Greedily minimize the cost of assigning register banks.
  93     /// This should produce code of greater quality, but will
  94     /// require more compile time.
  95     Greedy
  96   };
  97
  98   /// Abstract class used to represent an insertion point in a CFG.
  99   /// This class records an insertion point and materializes it on
 100   /// demand.
 101   /// It allows to reason about the frequency of this insertion point,
 102   /// without having to logically materialize it (e.g., on an edge),
 103   /// before we actually need to insert something.
 104   class InsertPoint {
 105   protected:
 106     /// Tell if the insert point has already been materialized.
 107     bool WasMaterialized = false;
 108     /// Materialize the insertion point.
 109     ///
 110     /// If isSplit() is true, this involves actually splitting
 111     /// the block or edge.
 112     ///
 113     /// \post getPointImpl() returns a valid iterator.
 114     /// \post getInsertMBBImpl() returns a valid basic block.
 115     /// \post isSplit() == false ; no more splitting should be required.
 116     virtual void materialize() = 0;
 117
 118     /// Return the materialized insertion basic block.
 119     /// Code will be inserted into that basic block.
 120     ///
 121     /// \pre ::materialize has been called.
 122     virtual MachineBasicBlock &getInsertMBBImpl() = 0;
 123
 124     /// Return the materialized insertion point.
 125     /// Code will be inserted before that point.
 126     ///
 127     /// \pre ::materialize has been called.
 128     virtual MachineBasicBlock::iterator getPointImpl() = 0;
 129
 130   public:
 131     virtual ~InsertPoint() {}
 132
 133     /// The first call to this method will cause the splitting to
 134     /// happen if need be, then sub sequent calls just return
 135     /// the iterator to that point. I.e., no more splitting will
 136     /// occur.
 137     ///
 138     /// \return The iterator that should be used with
 139     /// MachineBasicBlock::insert. I.e., additional code happens
 140     /// before that point.
 141     MachineBasicBlock::iterator getPoint() {
 142       if (!WasMaterialized) {
 143         WasMaterialized = true;
 144         assert(canMaterialize() && "Impossible to materialize this point");
 145         materialize();
 146       }
 147       // When we materialized the point we should have done the splitting.
 148       assert(!isSplit() && "Wrong pre-condition");
 149       return getPointImpl();
 150     }
 151
 152     /// The first call to this method will cause the splitting to
 153     /// happen if need be, then sub sequent calls just return
 154     /// the basic block that contains the insertion point.
 155     /// I.e., no more splitting will occur.
 156     ///
 157     /// \return The basic block should be used with
 158     /// MachineBasicBlock::insert and ::getPoint. The new code should
 159     /// happen before that point.
 160     MachineBasicBlock &getInsertMBB() {
 161       if (!WasMaterialized) {
 162         WasMaterialized = true;
 163         assert(canMaterialize() && "Impossible to materialize this point");
 164         materialize();
 165       }
 166       // When we materialized the point we should have done the splitting.
 167       assert(!isSplit() && "Wrong pre-condition");
 168       return getInsertMBBImpl();
 169     }
 170
 171     /// Insert \p MI in the just before ::getPoint()
 172     MachineBasicBlock::iterator insert(MachineInstr &MI) {
 173       return getInsertMBB().insert(getPoint(), &MI);
 174     }
 175
 176     /// Does this point involve splitting an edge or block?
 177     /// As soon as ::getPoint is called and thus, the point
 178     /// materialized, the point will not require splitting anymore,
 179     /// i.e., this will return false.
 180     virtual bool isSplit() const { return false; }
 181
 182     /// Frequency of the insertion point.
 183     /// \p P is used to access the various analysis that will help to
 184     /// get that information, like MachineBlockFrequencyInfo.  If \p P
 185     /// does not contain enough enough to return the actual frequency,
 186     /// this returns 1.
 187     virtual uint64_t frequency(const Pass &P) const { return 1; }
 188
 189     /// Check whether this insertion point can be materialized.
 190     /// As soon as ::getPoint is called and thus, the point materialized
 191     /// calling this method does not make sense.
 192     virtual bool canMaterialize() const { return false; }
 193   };
 194
 195   /// Insertion point before or after an instruction.
 196   class InstrInsertPoint : public InsertPoint {
 197   private:
 198     /// Insertion point.
 199     MachineInstr &Instr;
 200     /// Does the insertion point is before or after Instr.
 201     bool Before;
 202
 203     void materialize() override;
 204
 205     MachineBasicBlock::iterator getPointImpl() override {
 206       if (Before)
 207         return Instr;
 208       return Instr.getNextNode() ? *Instr.getNextNode()
 209                                  : Instr.getParent()->end();
 210     }
 211
 212     MachineBasicBlock &getInsertMBBImpl() override {
 213       return *Instr.getParent();
 214     }
 215
 216   public:
 217     /// Create an insertion point before (\p Before=true) or after \p Instr.
 218     InstrInsertPoint(MachineInstr &Instr, bool Before = true);
 219     bool isSplit() const override;
 220     uint64_t frequency(const Pass &P) const override;
 221
 222     // Worst case, we need to slice the basic block, but that is still doable.
 223     bool canMaterialize() const override { return true; }
 224   };
 225
 226   /// Insertion point at the beginning or end of a basic block.
 227   class MBBInsertPoint : public InsertPoint {
 228   private:
 229     /// Insertion point.
 230     MachineBasicBlock &MBB;
 231     /// Does the insertion point is at the beginning or end of MBB.
 232     bool Beginning;
 233
 234     void materialize() override { /*Nothing to do to materialize*/
 235     }
 236
 237     MachineBasicBlock::iterator getPointImpl() override {
 238       return Beginning ? MBB.begin() : MBB.end();
 239     }
 240
 241     MachineBasicBlock &getInsertMBBImpl() override { return MBB; }
 242
 243   public:
 244     MBBInsertPoint(MachineBasicBlock &MBB, bool Beginning = true)
 245         : InsertPoint(), MBB(MBB), Beginning(Beginning) {
 246       // If we try to insert before phis, we should use the insertion
 247       // points on the incoming edges.
 248       assert((!Beginning || MBB.getFirstNonPHI() == MBB.begin()) &&
 249              "Invalid beginning point");
 250       // If we try to insert after the terminators, we should use the
 251       // points on the outcoming edges.
 252       assert((Beginning || MBB.getFirstTerminator() == MBB.end()) &&
 253              "Invalid end point");
 254     }
 255     bool isSplit() const override { return false; }
 256     uint64_t frequency(const Pass &P) const override;
 257     bool canMaterialize() const override { return true; };
 258   };
 259
 260   /// Insertion point on an edge.
 261   class EdgeInsertPoint : public InsertPoint {
 262   private:
 263     /// Source of the edge.
 264     MachineBasicBlock &Src;
 265     /// Destination of the edge.
 266     /// After the materialization is done, this hold the basic block
 267     /// that resulted from the splitting.
 268     MachineBasicBlock *DstOrSplit;
 269     /// P is used to update the analysis passes as applicable.
 270     Pass &P;
 271
 272     void materialize() override;
 273
 274     MachineBasicBlock::iterator getPointImpl() override {
 275       // DstOrSplit should be the Split block at this point.
 276       // I.e., it should have one predecessor, Src, and one successor,
 277       // the original Dst.
 278       assert(DstOrSplit && DstOrSplit->isPredecessor(&Src) &&
 279              DstOrSplit->pred_size() == 1 && DstOrSplit->succ_size() == 1 &&
 280              "Did not split?!");
 281       return DstOrSplit->begin();
 282     }
 283
 284     MachineBasicBlock &getInsertMBBImpl() override { return *DstOrSplit; }
 285
 286   public:
 287     EdgeInsertPoint(MachineBasicBlock &Src, MachineBasicBlock &Dst, Pass &P)
 288         : InsertPoint(), Src(Src), DstOrSplit(&Dst), P(P) {}
 289     bool isSplit() const override {
 290       return Src.succ_size() > 1 && DstOrSplit->pred_size() > 1;
 291     }
 292     uint64_t frequency(const Pass &P) const override;
 293     bool canMaterialize() const override;
 294   };
 295
 296   /// Struct used to represent the placement of a repairing point for
 297   /// a given operand.
 298   class RepairingPlacement {
 299   public:
 300     /// Define the kind of action this repairing needs.
 301     enum RepairingKind {
 302       /// Nothing to repair, just drop this action.
 303       None,
 304       /// Reparing code needs to happen before InsertPoints.
 305       Insert,
 306       /// (Re)assign the register bank of the operand.
 307       Reassign,
 308       /// Mark this repairing placement as impossible.
 309       Impossible
 310     };
 311
 312     /// \name Convenient types for a list of insertion points.
 313     /// @{
 314     typedef SmallVector<std::unique_ptr<InsertPoint>, 2> InsertionPoints;
 315     typedef InsertionPoints::iterator insertpt_iterator;
 316     typedef InsertionPoints::const_iterator const_insertpt_iterator;
 317     /// @}
 318
 319   private:
 320     /// Kind of repairing.
 321     RepairingKind Kind;
 322     /// Index of the operand that will be repaired.
 323     unsigned OpIdx;
 324     /// Are all the insert points materializeable?
 325     bool CanMaterialize;
 326     /// Is there any of the insert points needing splitting?
 327     bool HasSplit;
 328     /// Insertion point for the repair code.
 329     /// The repairing code needs to happen just before these points.
 330     InsertionPoints InsertPoints;
 331     /// Some insertion points may need to update the liveness and such.
 332     Pass &P;
 333
 334   public:
 335     /// Create a repairing placement for the \p OpIdx-th operand of
 336     /// \p MI. \p TRI is used to make some checks on the register aliases
 337     /// if the machine operand is a physical register. \p P is used to
 338     /// to update liveness information and such when materializing the
 339     /// points.
 340     RepairingPlacement(MachineInstr &MI, unsigned OpIdx,
 341                        const TargetRegisterInfo &TRI, Pass &P,
 342                        RepairingKind Kind = RepairingKind::Insert);
 343
 344     /// \name Getters.
 345     /// @{
 346     RepairingKind getKind() const { return Kind; }
 347     unsigned getOpIdx() const { return OpIdx; }
 348     bool canMaterialize() const { return CanMaterialize; }
 349     bool hasSplit() { return HasSplit; }
 350     /// @}
 351
 352     /// \name Overloaded methods to add an insertion point.
 353     /// @{
 354     /// Add a MBBInsertionPoint to the list of InsertPoints.
 355     void addInsertPoint(MachineBasicBlock &MBB, bool Beginning);
 356     /// Add a InstrInsertionPoint to the list of InsertPoints.
 357     void addInsertPoint(MachineInstr &MI, bool Before);
 358     /// Add an EdgeInsertionPoint (\p Src, \p Dst) to the list of InsertPoints.
 359     void addInsertPoint(MachineBasicBlock &Src, MachineBasicBlock &Dst);
 360     /// Add an InsertPoint to the list of insert points.
 361     /// This method takes the ownership of &\p Point.
 362     void addInsertPoint(InsertPoint &Point);
 363     /// @}
 364
 365     /// \name Accessors related to the insertion points.
 366     /// @{
 367     insertpt_iterator begin() { return InsertPoints.begin(); }
 368     insertpt_iterator end() { return InsertPoints.end(); }
 369
 370     const_insertpt_iterator begin() const { return InsertPoints.begin(); }
 371     const_insertpt_iterator end() const { return InsertPoints.end(); }
 372
 373     unsigned getNumInsertPoints() const { return InsertPoints.size(); }
 374     /// @}
 375
 376     /// Change the type of this repairing placement to \p NewKind.
 377     /// It is not possible to switch a repairing placement to the
 378     /// RepairingKind::Insert. There is no fundamental problem with
 379     /// that, but no uses as well, so do not support it for now.
 380     ///
 381     /// \pre NewKind != RepairingKind::Insert
 382     /// \post getKind() == NewKind
 383     void switchTo(RepairingKind NewKind) {
 384       assert(NewKind != Kind && "Already of the right Kind");
 385       Kind = NewKind;
 386       InsertPoints.clear();
 387       CanMaterialize = NewKind != RepairingKind::Impossible;
 388       HasSplit = false;
 389       assert(NewKind != RepairingKind::Insert &&
 390              "We would need more MI to switch to Insert");
 391     }
 392   };
 393
 394 private:
 395   /// Helper class used to represent the cost for mapping an instruction.
 396   /// When mapping an instruction, we may introduce some repairing code.
 397   /// In most cases, the repairing code is local to the instruction,
 398   /// thus, we can omit the basic block frequency from the cost.
 399   /// However, some alternatives may produce non-local cost, e.g., when
 400   /// repairing a phi, and thus we then need to scale the local cost
 401   /// to the non-local cost. This class does this for us.
 402   /// \note: We could simply always scale the cost. The problem is that
 403   /// there are higher chances that we saturate the cost easier and end
 404   /// up having the same cost for actually different alternatives.
 405   /// Another option would be to use APInt everywhere.
 406   class MappingCost {
 407   private:
 408     /// Cost of the local instructions.
 409     /// This cost is free of basic block frequency.
 410     uint64_t LocalCost;
 411     /// Cost of the non-local instructions.
 412     /// This cost should include the frequency of the related blocks.
 413     uint64_t NonLocalCost;
 414     /// Frequency of the block where the local instructions live.
 415     uint64_t LocalFreq;
 416
 417     MappingCost(uint64_t LocalCost, uint64_t NonLocalCost, uint64_t LocalFreq)
 418         : LocalCost(LocalCost), NonLocalCost(NonLocalCost),
 419           LocalFreq(LocalFreq) {}
 420
 421     /// Check if this cost is saturated.
 422     bool isSaturated() const;
 423
 424   public:
 425     /// Create a MappingCost assuming that most of the instructions
 426     /// will occur in a basic block with \p LocalFreq frequency.
 427     MappingCost(const BlockFrequency &LocalFreq);
 428
 429     /// Add \p Cost to the local cost.
 430     /// \return true if this cost is saturated, false otherwise.
 431     bool addLocalCost(uint64_t Cost);
 432
 433     /// Add \p Cost to the non-local cost.
 434     /// Non-local cost should reflect the frequency of their placement.
 435     /// \return true if this cost is saturated, false otherwise.
 436     bool addNonLocalCost(uint64_t Cost);
 437
 438     /// Saturate the cost to the maximal representable value.
 439     void saturate();
 440
 441     /// Return an instance of MappingCost that represents an
 442     /// impossible mapping.
 443     static MappingCost ImpossibleCost();
 444
 445     /// Check if this is less than \p Cost.
 446     bool operator<(const MappingCost &Cost) const;
 447     /// Check if this is equal to \p Cost.
 448     bool operator==(const MappingCost &Cost) const;
 449     /// Check if this is not equal to \p Cost.
 450     bool operator!=(const MappingCost &Cost) const { return !(*this == Cost); }
 451     /// Check if this is greater than \p Cost.
 452     bool operator>(const MappingCost &Cost) const {
 453       return *this != Cost && Cost < *this;
 454     }
 455
 456     /// Print this on dbgs() stream.
 457     void dump() const;
 458
 459     /// Print this on \p OS;
 460     void print(raw_ostream &OS) const;
 461
 462     /// Overload the stream operator for easy debug printing.
 463     friend raw_ostream &operator<<(raw_ostream &OS, const MappingCost &Cost) {
 464       Cost.print(OS);
 465       return OS;
 466     }
 467   };
 468
 469   /// Interface to the target lowering info related
 470   /// to register banks.
 471   const RegisterBankInfo *RBI;
 472
 473   /// MRI contains all the register class/bank information that this
 474   /// pass uses and updates.
 475   MachineRegisterInfo *MRI;
 476
 477   /// Information on the register classes for the current function.
 478   const TargetRegisterInfo *TRI;
 479
 480   /// Get the frequency of blocks.
 481   /// This is required for non-fast mode.
 482   MachineBlockFrequencyInfo *MBFI;
 483
 484   /// Get the frequency of the edges.
 485   /// This is required for non-fast mode.
 486   MachineBranchProbabilityInfo *MBPI;
 487
 488   /// Current optimization remark emitter. Used to report failures.
 489   std::unique_ptr<MachineOptimizationRemarkEmitter> MORE;
 490
 491   /// Helper class used for every code morphing.
 492   MachineIRBuilder MIRBuilder;
 493
 494   /// Optimization mode of the pass.
 495   Mode OptMode;
 496
 497   /// Current target configuration. Controls how the pass handles errors.
 498   const TargetPassConfig *TPC;
 499
 500   /// Assign the register bank of each operand of \p MI.
 501   /// \return True on success, false otherwise.
 502   bool assignInstr(MachineInstr &MI);
 503
 504   /// Initialize the field members using \p MF.
 505   void init(MachineFunction &MF);
 506
 507   /// Check if \p Reg is already assigned what is described by \p ValMapping.
 508   /// \p OnlyAssign == true means that \p Reg just needs to be assigned a
 509   /// register bank.  I.e., no repairing is necessary to have the
 510   /// assignment match.
 511   bool assignmentMatch(unsigned Reg,
 512                        const RegisterBankInfo::ValueMapping &ValMapping,
 513                        bool &OnlyAssign) const;
 514
 515   /// Insert repairing code for \p Reg as specified by \p ValMapping.
 516   /// The repairing placement is specified by \p RepairPt.
 517   /// \p NewVRegs contains all the registers required to remap \p Reg.
 518   /// In other words, the number of registers in NewVRegs must be equal
 519   /// to ValMapping.BreakDown.size().
 520   ///
 521   /// The transformation could be sketched as:
 522   /// \code
 523   /// ... = op Reg
 524   /// \endcode
 525   /// Becomes
 526   /// \code
 527   /// <NewRegs> = COPY or extract Reg
 528   /// ... = op Reg
 529   /// \endcode
 530   ///
 531   /// and
 532   /// \code
 533   /// Reg = op ...
 534   /// \endcode
 535   /// Becomes
 536   /// \code
 537   /// Reg = op ...
 538   /// Reg = COPY or build_sequence <NewRegs>
 539   /// \endcode
 540   ///
 541   /// \pre NewVRegs.size() == ValMapping.BreakDown.size()
 542   ///
 543   /// \note The caller is supposed to do the rewriting of op if need be.
 544   /// I.e., Reg = op ... => <NewRegs> = NewOp ...
 545   ///
 546   /// \return True if the repairing worked, false otherwise.
 547   bool repairReg(MachineOperand &MO,
 548                  const RegisterBankInfo::ValueMapping &ValMapping,
 549                  RegBankSelect::RepairingPlacement &RepairPt,
 550                  const iterator_range<SmallVectorImpl<unsigned>::const_iterator>
 551                      &NewVRegs);
 552
 553   /// Return the cost of the instruction needed to map \p MO to \p ValMapping.
 554   /// The cost is free of basic block frequencies.
 555   /// \pre MO.isReg()
 556   /// \pre MO is assigned to a register bank.
 557   /// \pre ValMapping is a valid mapping for MO.
 558   uint64_t
 559   getRepairCost(const MachineOperand &MO,
 560                 const RegisterBankInfo::ValueMapping &ValMapping) const;
 561
 562   /// Find the best mapping for \p MI from \p PossibleMappings.
 563   /// \return a reference on the best mapping in \p PossibleMappings.
 564   const RegisterBankInfo::InstructionMapping &
 565   findBestMapping(MachineInstr &MI,
 566                   RegisterBankInfo::InstructionMappings &PossibleMappings,
 567                   SmallVectorImpl<RepairingPlacement> &RepairPts);
 568
 569   /// Compute the cost of mapping \p MI with \p InstrMapping and
 570   /// compute the repairing placement for such mapping in \p
 571   /// RepairPts.
 572   /// \p BestCost is used to specify when the cost becomes too high
 573   /// and thus it is not worth computing the RepairPts.  Moreover if
 574   /// \p BestCost == nullptr, the mapping cost is actually not
 575   /// computed.
 576   MappingCost
 577   computeMapping(MachineInstr &MI,
 578                  const RegisterBankInfo::InstructionMapping &InstrMapping,
 579                  SmallVectorImpl<RepairingPlacement> &RepairPts,
 580                  const MappingCost *BestCost = nullptr);
 581
 582   /// When \p RepairPt involves splitting to repair \p MO for the
 583   /// given \p ValMapping, try to change the way we repair such that
 584   /// the splitting is not required anymore.
 585   ///
 586   /// \pre \p RepairPt.hasSplit()
 587   /// \pre \p MO == MO.getParent()->getOperand(\p RepairPt.getOpIdx())
 588   /// \pre \p ValMapping is the mapping of \p MO for MO.getParent()
 589   ///      that implied \p RepairPt.
 590   void tryAvoidingSplit(RegBankSelect::RepairingPlacement &RepairPt,
 591                         const MachineOperand &MO,
 592                         const RegisterBankInfo::ValueMapping &ValMapping) const;
 593
 594   /// Apply \p Mapping to \p MI. \p RepairPts represents the different
 595   /// mapping action that need to happen for the mapping to be
 596   /// applied.
 597   /// \return True if the mapping was applied sucessfully, false otherwise.
 598   bool applyMapping(MachineInstr &MI,
 599                     const RegisterBankInfo::InstructionMapping &InstrMapping,
 600                     SmallVectorImpl<RepairingPlacement> &RepairPts);
 601
 602 public:
 603   /// Create a RegBankSelect pass with the specified \p RunningMode.
 604   RegBankSelect(Mode RunningMode = Fast);
 605
 606   StringRef getPassName() const override { return "RegBankSelect"; }
 607
 608   void getAnalysisUsage(AnalysisUsage &AU) const override;
 609
 610   MachineFunctionProperties getRequiredProperties() const override {
 611     return MachineFunctionProperties()
 612         .set(MachineFunctionProperties::Property::IsSSA)
 613         .set(MachineFunctionProperties::Property::Legalized);
 614   }
 615
 616   MachineFunctionProperties getSetProperties() const override {
 617     return MachineFunctionProperties().set(
 618         MachineFunctionProperties::Property::RegBankSelected);
 619   }
 620
 621   /// Walk through \p MF and assign a register bank to every virtual register
 622   /// that are still mapped to nothing.
 623   /// The target needs to provide a RegisterBankInfo and in particular
 624   /// override RegisterBankInfo::getInstrMapping.
 625   ///
 626   /// Simplified algo:
 627   /// \code
 628   ///   RBI = MF.subtarget.getRegBankInfo()
 629   ///   MIRBuilder.setMF(MF)
 630   ///   for each bb in MF
 631   ///     for each inst in bb
 632   ///       MIRBuilder.setInstr(inst)
 633   ///       MappingCosts = RBI.getMapping(inst);
 634   ///       Idx = findIdxOfMinCost(MappingCosts)
 635   ///       CurRegBank = MappingCosts[Idx].RegBank
 636   ///       MRI.setRegBank(inst.getOperand(0).getReg(), CurRegBank)
 637   ///       for each argument in inst
 638   ///         if (CurRegBank != argument.RegBank)
 639   ///           ArgReg = argument.getReg()
 640   ///           Tmp = MRI.createNewVirtual(MRI.getSize(ArgReg), CurRegBank)
 641   ///           MIRBuilder.buildInstr(COPY, Tmp, ArgReg)
 642   ///           inst.getOperand(argument.getOperandNo()).setReg(Tmp)
 643   /// \endcode
 644   bool runOnMachineFunction(MachineFunction &MF) override;
 645 };
 646
 647 } // End namespace llvm.
 648
 649 #endif