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