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