Coverage Report

Created: 2019-02-23 12:57

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/GlobalISel/RegBankSelect.h
Line
Count
Source (jump to first uncovered line)
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
14.3k
    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.
148
13.9k
    MachineBasicBlock::iterator getPoint() {
149
13.9k
      if (!WasMaterialized) {
150
0
        WasMaterialized = true;
151
0
        assert(canMaterialize() && "Impossible to materialize this point");
152
0
        materialize();
153
0
      }
154
13.9k
      // When we materialized the point we should have done the splitting.
155
13.9k
      assert(!isSplit() && "Wrong pre-condition");
156
13.9k
      return getPointImpl();
157
13.9k
    }
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.
167
13.9k
    MachineBasicBlock &getInsertMBB() {
168
13.9k
      if (!WasMaterialized) {
169
13.9k
        WasMaterialized = true;
170
13.9k
        assert(canMaterialize() && "Impossible to materialize this point");
171
13.9k
        materialize();
172
13.9k
      }
173
13.9k
      // When we materialized the point we should have done the splitting.
174
13.9k
      assert(!isSplit() && "Wrong pre-condition");
175
13.9k
      return getInsertMBBImpl();
176
13.9k
    }
177
178
    /// Insert \p MI in the just before ::getPoint()
179
13.9k
    MachineBasicBlock::iterator insert(MachineInstr &MI) {
180
13.9k
      return getInsertMBB().insert(getPoint(), &MI);
181
13.9k
    }
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.
187
0
    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.
194
0
    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.
199
0
    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
213
13.9k
    MachineBasicBlock::iterator getPointImpl() override {
214
13.9k
      if (Before)
215
13.9k
        return Instr;
216
67
      return Instr.getNextNode() ? 
*Instr.getNextNode()30
217
67
                                 : 
Instr.getParent()->end()37
;
218
67
    }
219
220
13.9k
    MachineBasicBlock &getInsertMBBImpl() override {
221
13.9k
      return *Instr.getParent();
222
13.9k
    }
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.
232
14.3k
    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
244
0
    void materialize() override { /*Nothing to do to materialize*/
245
0
    }
246
247
0
    MachineBasicBlock::iterator getPointImpl() override {
248
0
      return Beginning ? MBB.begin() : MBB.end();
249
0
    }
250
251
0
    MachineBasicBlock &getInsertMBBImpl() override { return MBB; }
252
253
  public:
254
    MBBInsertPoint(MachineBasicBlock &MBB, bool Beginning = true)
255
0
        : InsertPoint(), MBB(MBB), Beginning(Beginning) {
256
0
      // If we try to insert before phis, we should use the insertion
257
0
      // points on the incoming edges.
258
0
      assert((!Beginning || MBB.getFirstNonPHI() == MBB.begin()) &&
259
0
             "Invalid beginning point");
260
0
      // If we try to insert after the terminators, we should use the
261
0
      // points on the outcoming edges.
262
0
      assert((Beginning || MBB.getFirstTerminator() == MBB.end()) &&
263
0
             "Invalid end point");
264
0
    }
265
266
0
    bool isSplit() const override { return false; }
267
    uint64_t frequency(const Pass &P) const override;
268
0
    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
287
0
    MachineBasicBlock::iterator getPointImpl() override {
288
0
      // DstOrSplit should be the Split block at this point.
289
0
      // I.e., it should have one predecessor, Src, and one successor,
290
0
      // the original Dst.
291
0
      assert(DstOrSplit && DstOrSplit->isPredecessor(&Src) &&
292
0
             DstOrSplit->pred_size() == 1 && DstOrSplit->succ_size() == 1 &&
293
0
             "Did not split?!");
294
0
      return DstOrSplit->begin();
295
0
    }
296
297
0
    MachineBasicBlock &getInsertMBBImpl() override { return *DstOrSplit; }
298
299
  public:
300
    EdgeInsertPoint(MachineBasicBlock &Src, MachineBasicBlock &Dst, Pass &P)
301
0
        : InsertPoint(), Src(Src), DstOrSplit(&Dst), P(P) {}
302
303
0
    bool isSplit() const override {
304
0
      return Src.succ_size() > 1 && DstOrSplit->pred_size() > 1;
305
0
    }
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
    /// @{
361
21.5M
    RepairingKind getKind() const { return Kind; }
362
10.7M
    unsigned getOpIdx() const { return OpIdx; }
363
10.7M
    bool canMaterialize() const { return CanMaterialize; }
364
14.3k
    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
    /// @{
382
14.4k
    insertpt_iterator begin() { return InsertPoints.begin(); }
383
14.4k
    insertpt_iterator end() { return InsertPoints.end(); }
384
385
0
    const_insertpt_iterator begin() const { return InsertPoints.begin(); }
386
0
    const_insertpt_iterator end() const { return InsertPoints.end(); }
387
388
27.9k
    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
398
0
    void switchTo(RepairingKind NewKind) {
399
0
      assert(NewKind != Kind && "Already of the right Kind");
400
0
      Kind = NewKind;
401
0
      InsertPoints.clear();
402
0
      CanMaterialize = NewKind != RepairingKind::Impossible;
403
0
      HasSplit = false;
404
0
      assert(NewKind != RepairingKind::Insert &&
405
0
             "We would need more MI to switch to Insert");
406
0
    }
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
432
    MappingCost(uint64_t LocalCost, uint64_t NonLocalCost, uint64_t LocalFreq)
433
        : LocalCost(LocalCost), NonLocalCost(NonLocalCost),
434
15.7M
          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
2.51k
    bool operator!=(const MappingCost &Cost) const { return !(*this == Cost); }
466
    /// Check if this is greater than \p Cost.
467
2.51k
    bool operator>(const MappingCost &Cost) const {
468
2.51k
      return *this != Cost && 
Cost < *this2.21k
;
469
2.51k
    }
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
0
    friend raw_ostream &operator<<(raw_ostream &OS, const MappingCost &Cost) {
479
0
      Cost.print(OS);
480
0
      return OS;
481
0
    }
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(unsigned 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<unsigned>::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
621
7.02k
  StringRef getPassName() const override { return "RegBankSelect"; }
622
623
  void getAnalysisUsage(AnalysisUsage &AU) const override;
624
625
7.02k
  MachineFunctionProperties getRequiredProperties() const override {
626
7.02k
    return MachineFunctionProperties()
627
7.02k
        .set(MachineFunctionProperties::Property::IsSSA)
628
7.02k
        .set(MachineFunctionProperties::Property::Legalized);
629
7.02k
  }
630
631
7.02k
  MachineFunctionProperties getSetProperties() const override {
632
7.02k
    return MachineFunctionProperties().set(
633
7.02k
        MachineFunctionProperties::Property::RegBankSelected);
634
7.02k
  }
635
636
  /// Walk through \p MF and assign a register bank to every virtual register
637
  /// that are still mapped to nothing.
638
  /// The target needs to provide a RegisterBankInfo and in particular
639
  /// override RegisterBankInfo::getInstrMapping.
640
  ///
641
  /// Simplified algo:
642
  /// \code
643
  ///   RBI = MF.subtarget.getRegBankInfo()
644
  ///   MIRBuilder.setMF(MF)
645
  ///   for each bb in MF
646
  ///     for each inst in bb
647
  ///       MIRBuilder.setInstr(inst)
648
  ///       MappingCosts = RBI.getMapping(inst);
649
  ///       Idx = findIdxOfMinCost(MappingCosts)
650
  ///       CurRegBank = MappingCosts[Idx].RegBank
651
  ///       MRI.setRegBank(inst.getOperand(0).getReg(), CurRegBank)
652
  ///       for each argument in inst
653
  ///         if (CurRegBank != argument.RegBank)
654
  ///           ArgReg = argument.getReg()
655
  ///           Tmp = MRI.createNewVirtual(MRI.getSize(ArgReg), CurRegBank)
656
  ///           MIRBuilder.buildInstr(COPY, Tmp, ArgReg)
657
  ///           inst.getOperand(argument.getOperandNo()).setReg(Tmp)
658
  /// \endcode
659
  bool runOnMachineFunction(MachineFunction &MF) override;
660
};
661
662
} // end namespace llvm
663
664
#endif // LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H