Coverage Report

Created: 2018-11-16 02:38

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