1//==- llvm/CodeGen/GlobalISel/RegBankSelect.cpp - RegBankSelect --*- 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/// \file
9/// This file implements the RegBankSelect class.
10//===----------------------------------------------------------------------===//
11
12#include "llvm/CodeGen/GlobalISel/RegBankSelect.h"
13#include "llvm/ADT/PostOrderIterator.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/SmallVector.h"
16#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
17#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
18#include "llvm/CodeGen/GlobalISel/Utils.h"
19#include "llvm/CodeGen/MachineBasicBlock.h"
20#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
21#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
22#include "llvm/CodeGen/MachineFunction.h"
23#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
24#include "llvm/CodeGen/MachineInstr.h"
25#include "llvm/CodeGen/MachineOperand.h"
26#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
27#include "llvm/CodeGen/MachinePassManager.h"
28#include "llvm/CodeGen/MachineRegisterInfo.h"
29#include "llvm/CodeGen/RegisterBank.h"
30#include "llvm/CodeGen/RegisterBankInfo.h"
31#include "llvm/CodeGen/TargetOpcodes.h"
32#include "llvm/CodeGen/TargetPassConfig.h"
33#include "llvm/CodeGen/TargetRegisterInfo.h"
34#include "llvm/CodeGen/TargetSubtargetInfo.h"
35#include "llvm/Config/llvm-config.h"
36#include "llvm/IR/Analysis.h"
37#include "llvm/IR/Function.h"
38#include "llvm/InitializePasses.h"
39#include "llvm/Pass.h"
40#include "llvm/Support/BlockFrequency.h"
41#include "llvm/Support/CommandLine.h"
42#include "llvm/Support/Compiler.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/ErrorHandling.h"
45#include "llvm/Support/raw_ostream.h"
46#include "llvm/Target/TargetMachine.h"
47#include <algorithm>
48#include <cassert>
49#include <cstdint>
50#include <limits>
51#include <memory>
52#include <optional>
53#include <utility>
54
55#define DEBUG_TYPE "reg-bank-select"
56
57using namespace llvm;
58
59/// Cost value representing an impossible or invalid repairing.
60/// This matches the value returned by RegisterBankInfo::copyCost() and
61/// RegisterBankInfo::getBreakDownCost() when the cost cannot be computed.
62static constexpr unsigned ImpossibleRepairCost =
63 std::numeric_limits<unsigned>::max();
64
65static cl::opt<RegBankSelectMode> RegBankSelectModeOption(
66 cl::desc("Mode of the RegBankSelect pass"), cl::Hidden,
67 cl::values(clEnumValN(RegBankSelectMode::Fast, "regbankselect-fast",
68 "Run the Fast mode (default mapping)"),
69 clEnumValN(RegBankSelectMode::Greedy, "regbankselect-greedy",
70 "Use the Greedy mode (best local mapping)")));
71
72char RegBankSelectLegacy::ID = 0;
73
74INITIALIZE_PASS_BEGIN(RegBankSelectLegacy, DEBUG_TYPE,
75 "Assign register bank of generic virtual registers",
76 false, false);
77INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
78INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
79INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
80INITIALIZE_PASS_END(RegBankSelectLegacy, DEBUG_TYPE,
81 "Assign register bank of generic virtual registers", false,
82 false)
83
84static RegBankSelectMode computeOptMode(RegBankSelectMode RequestedMode) {
85 if (RegBankSelectModeOption.getNumOccurrences() != 0) {
86 if (RegBankSelectModeOption != RequestedMode)
87 LLVM_DEBUG(dbgs() << "RegBankSelect mode overrided by command line\n");
88 return RegBankSelectModeOption;
89 }
90 return RequestedMode;
91}
92
93namespace {
94
95class RegBankSelectImpl {
96 /// Abstract class used to represent an insertion point in a CFG.
97 /// This class records an insertion point and materializes it on
98 /// demand.
99 /// It allows to reason about the frequency of this insertion point,
100 /// without having to logically materialize it (e.g., on an edge),
101 /// before we actually need to insert something.
102 class InsertPoint {
103 protected:
104 /// Tell if the insert point has already been materialized.
105 bool WasMaterialized = false;
106
107 /// Materialize the insertion point.
108 ///
109 /// If isSplit() is true, this involves actually splitting
110 /// the block or edge.
111 ///
112 /// \post getPointImpl() returns a valid iterator.
113 /// \post getInsertMBBImpl() returns a valid basic block.
114 /// \post isSplit() == false ; no more splitting should be required.
115 virtual void materialize() = 0;
116
117 /// Return the materialized insertion basic block.
118 /// Code will be inserted into that basic block.
119 ///
120 /// \pre ::materialize has been called.
121 virtual MachineBasicBlock &getInsertMBBImpl() = 0;
122
123 /// Return the materialized insertion point.
124 /// Code will be inserted before that point.
125 ///
126 /// \pre ::materialize has been called.
127 virtual MachineBasicBlock::iterator getPointImpl() = 0;
128
129 public:
130 virtual ~InsertPoint() = default;
131
132 /// The first call to this method will cause the splitting to
133 /// happen if need be, then sub sequent calls just return
134 /// the iterator to that point. I.e., no more splitting will
135 /// occur.
136 ///
137 /// \return The iterator that should be used with
138 /// MachineBasicBlock::insert. I.e., additional code happens
139 /// before that point.
140 MachineBasicBlock::iterator getPoint() {
141 if (!WasMaterialized) {
142 WasMaterialized = true;
143 assert(canMaterialize() && "Impossible to materialize this point");
144 materialize();
145 }
146 // When we materialized the point we should have done the splitting.
147 assert(!isSplit() && "Wrong pre-condition");
148 return getPointImpl();
149 }
150
151 /// The first call to this method will cause the splitting to
152 /// happen if need be, then sub sequent calls just return
153 /// the basic block that contains the insertion point.
154 /// I.e., no more splitting will occur.
155 ///
156 /// \return The basic block should be used with
157 /// MachineBasicBlock::insert and ::getPoint. The new code should
158 /// happen before that point.
159 MachineBasicBlock &getInsertMBB() {
160 if (!WasMaterialized) {
161 WasMaterialized = true;
162 assert(canMaterialize() && "Impossible to materialize this point");
163 materialize();
164 }
165 // When we materialized the point we should have done the splitting.
166 assert(!isSplit() && "Wrong pre-condition");
167 return getInsertMBBImpl();
168 }
169
170 /// Insert \p MI in the just before ::getPoint()
171 MachineBasicBlock::iterator insert(MachineInstr &MI) {
172 return getInsertMBB().insert(I: getPoint(), MI: &MI);
173 }
174
175 /// Does this point involve splitting an edge or block?
176 /// As soon as ::getPoint is called and thus, the point
177 /// materialized, the point will not require splitting anymore,
178 /// i.e., this will return false.
179 virtual bool isSplit() const { return false; }
180
181 /// Frequency of the insertion point.
182 /// \p P is used to access the various analysis that will help to
183 /// get that information, like MachineBlockFrequencyInfo. If \p P
184 /// does not contain enough to return the actual frequency,
185 /// this returns 1.
186 virtual uint64_t frequency(
187 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
188 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI) const {
189 return 1;
190 }
191
192 /// Check whether this insertion point can be materialized.
193 /// As soon as ::getPoint is called and thus, the point materialized
194 /// calling this method does not make sense.
195 virtual bool canMaterialize() const { return false; }
196 };
197
198 /// Insertion point before or after an instruction.
199 class InstrInsertPoint : public InsertPoint {
200 private:
201 /// Insertion point.
202 MachineInstr &Instr;
203
204 /// Does the insertion point is before or after Instr.
205 bool Before;
206
207 void materialize() override;
208
209 MachineBasicBlock::iterator getPointImpl() override {
210 if (Before)
211 return Instr;
212 return Instr.getNextNode() ? *Instr.getNextNode()
213 : Instr.getParent()->end();
214 }
215
216 MachineBasicBlock &getInsertMBBImpl() override {
217 return *Instr.getParent();
218 }
219
220 public:
221 /// Create an insertion point before (\p Before=true) or after \p Instr.
222 InstrInsertPoint(MachineInstr &Instr, bool Before = true);
223
224 bool isSplit() const override;
225 uint64_t
226 frequency(function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
227 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI)
228 const override;
229
230 // Worst case, we need to slice the basic block, but that is still doable.
231 bool canMaterialize() const override { return true; }
232 };
233
234 /// Insertion point at the beginning or end of a basic block.
235 class MBBInsertPoint : public InsertPoint {
236 private:
237 /// Insertion point.
238 MachineBasicBlock &MBB;
239
240 /// Does the insertion point is at the beginning or end of MBB.
241 bool Beginning;
242
243 void materialize() override { /*Nothing to do to materialize*/ }
244
245 MachineBasicBlock::iterator getPointImpl() override {
246 return Beginning ? MBB.begin() : MBB.end();
247 }
248
249 MachineBasicBlock &getInsertMBBImpl() override { return MBB; }
250
251 public:
252 MBBInsertPoint(MachineBasicBlock &MBB, bool Beginning = true)
253 : MBB(MBB), Beginning(Beginning) {
254 // If we try to insert before phis, we should use the insertion
255 // points on the incoming edges.
256 assert((!Beginning || MBB.getFirstNonPHI() == MBB.begin()) &&
257 "Invalid beginning point");
258 // If we try to insert after the terminators, we should use the
259 // points on the outcoming edges.
260 assert((Beginning || MBB.getFirstTerminator() == MBB.end()) &&
261 "Invalid end point");
262 }
263
264 bool isSplit() const override { return false; }
265 uint64_t
266 frequency(function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
267 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI)
268 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/MFAM is used to update the analysis passes as applicable when
284 /// splitting critical edges.
285 Pass *P;
286 MachineFunctionAnalysisManager *MFAM;
287
288 void materialize() override;
289
290 MachineBasicBlock::iterator getPointImpl() override {
291 // DstOrSplit should be the Split block at this point.
292 // I.e., it should have one predecessor, Src, and one successor,
293 // the original Dst.
294 assert(DstOrSplit && DstOrSplit->isPredecessor(&Src) &&
295 DstOrSplit->pred_size() == 1 && DstOrSplit->succ_size() == 1 &&
296 "Did not split?!");
297 return DstOrSplit->begin();
298 }
299
300 MachineBasicBlock &getInsertMBBImpl() override { return *DstOrSplit; }
301
302 public:
303 EdgeInsertPoint(MachineBasicBlock &Src, MachineBasicBlock &Dst, Pass *P,
304 MachineFunctionAnalysisManager *MFAM)
305 : Src(Src), DstOrSplit(&Dst), P(P), MFAM(MFAM) {}
306
307 bool isSplit() const override {
308 return Src.succ_size() > 1 && DstOrSplit->pred_size() > 1;
309 }
310
311 uint64_t
312 frequency(function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
313 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI)
314 const override;
315 bool canMaterialize() const override;
316 };
317
318 /// Struct used to represent the placement of a repairing point for
319 /// a given operand.
320 class RepairingPlacement {
321 public:
322 /// Define the kind of action this repairing needs.
323 enum RepairingKind {
324 /// Nothing to repair, just drop this action.
325 None,
326 /// Reparing code needs to happen before InsertPoints.
327 Insert,
328 /// (Re)assign the register bank of the operand.
329 Reassign,
330 /// Mark this repairing placement as impossible.
331 Impossible
332 };
333
334 /// \name Convenient types for a list of insertion points.
335 /// @{
336 using InsertionPoints = SmallVector<std::unique_ptr<InsertPoint>, 2>;
337 using insertpt_iterator = InsertionPoints::iterator;
338 using const_insertpt_iterator = InsertionPoints::const_iterator;
339 /// @}
340
341 private:
342 /// Kind of repairing.
343 RepairingKind Kind;
344 /// Index of the operand that will be repaired.
345 unsigned OpIdx;
346 /// Are all the insert points materializeable?
347 bool CanMaterialize;
348 /// Is there any of the insert points needing splitting?
349 bool HasSplit = false;
350 /// Insertion point for the repair code.
351 /// The repairing code needs to happen just before these points.
352 InsertionPoints InsertPoints;
353 /// Some insertion points may need to update the liveness and such.
354 Pass *P;
355 MachineFunctionAnalysisManager *MFAM;
356
357 public:
358 /// Create a repairing placement for the \p OpIdx-th operand of
359 /// \p MI. \p TRI is used to make some checks on the register aliases
360 /// if the machine operand is a physical register. \p P is used to
361 /// to update liveness information and such when materializing the
362 /// points.
363 RepairingPlacement(MachineInstr &MI, unsigned OpIdx,
364 const TargetRegisterInfo &TRI, Pass *P,
365 MachineFunctionAnalysisManager *MFAM,
366 RepairingKind Kind = RepairingKind::Insert);
367
368 /// \name Getters.
369 /// @{
370 RepairingKind getKind() const { return Kind; }
371 unsigned getOpIdx() const { return OpIdx; }
372 bool canMaterialize() const { return CanMaterialize; }
373 bool hasSplit() { return HasSplit; }
374 /// @}
375
376 /// \name Overloaded methods to add an insertion point.
377 /// @{
378 /// Add a MBBInsertionPoint to the list of InsertPoints.
379 void addInsertPoint(MachineBasicBlock &MBB, bool Beginning);
380 /// Add a InstrInsertionPoint to the list of InsertPoints.
381 void addInsertPoint(MachineInstr &MI, bool Before);
382 /// Add an EdgeInsertionPoint (\p Src, \p Dst) to the list of InsertPoints.
383 void addInsertPoint(MachineBasicBlock &Src, MachineBasicBlock &Dst);
384 /// Add an InsertPoint to the list of insert points.
385 /// This method takes the ownership of &\p Point.
386 void addInsertPoint(InsertPoint &Point);
387 /// @}
388
389 /// \name Accessors related to the insertion points.
390 /// @{
391 insertpt_iterator begin() { return InsertPoints.begin(); }
392 insertpt_iterator end() { return InsertPoints.end(); }
393
394 const_insertpt_iterator begin() const { return InsertPoints.begin(); }
395 const_insertpt_iterator end() const { return InsertPoints.end(); }
396
397 unsigned getNumInsertPoints() const { return InsertPoints.size(); }
398 /// @}
399
400 /// Change the type of this repairing placement to \p NewKind.
401 /// It is not possible to switch a repairing placement to the
402 /// RepairingKind::Insert. There is no fundamental problem with
403 /// that, but no uses as well, so do not support it for now.
404 ///
405 /// \pre NewKind != RepairingKind::Insert
406 /// \post getKind() == NewKind
407 void switchTo(RepairingKind NewKind) {
408 assert(NewKind != Kind && "Already of the right Kind");
409 Kind = NewKind;
410 InsertPoints.clear();
411 CanMaterialize = NewKind != RepairingKind::Impossible;
412 HasSplit = false;
413 assert(NewKind != RepairingKind::Insert &&
414 "We would need more MI to switch to Insert");
415 }
416 };
417
418protected:
419 /// Helper class used to represent the cost for mapping an instruction.
420 /// When mapping an instruction, we may introduce some repairing code.
421 /// In most cases, the repairing code is local to the instruction,
422 /// thus, we can omit the basic block frequency from the cost.
423 /// However, some alternatives may produce non-local cost, e.g., when
424 /// repairing a phi, and thus we then need to scale the local cost
425 /// to the non-local cost. This class does this for us.
426 /// \note: We could simply always scale the cost. The problem is that
427 /// there are higher chances that we saturate the cost easier and end
428 /// up having the same cost for actually different alternatives.
429 /// Another option would be to use APInt everywhere.
430 class MappingCost {
431 private:
432 /// Cost of the local instructions.
433 /// This cost is free of basic block frequency.
434 uint64_t LocalCost = 0;
435 /// Cost of the non-local instructions.
436 /// This cost should include the frequency of the related blocks.
437 uint64_t NonLocalCost = 0;
438 /// Frequency of the block where the local instructions live.
439 uint64_t LocalFreq;
440
441 MappingCost(uint64_t LocalCost, uint64_t NonLocalCost, uint64_t LocalFreq)
442 : LocalCost(LocalCost), NonLocalCost(NonLocalCost),
443 LocalFreq(LocalFreq) {}
444
445 /// Check if this cost is saturated.
446 bool isSaturated() const;
447
448 public:
449 /// Create a MappingCost assuming that most of the instructions
450 /// will occur in a basic block with \p LocalFreq frequency.
451 MappingCost(BlockFrequency LocalFreq);
452
453 /// Add \p Cost to the local cost.
454 /// \return true if this cost is saturated, false otherwise.
455 bool addLocalCost(uint64_t Cost);
456
457 /// Add \p Cost to the non-local cost.
458 /// Non-local cost should reflect the frequency of their placement.
459 /// \return true if this cost is saturated, false otherwise.
460 bool addNonLocalCost(uint64_t Cost);
461
462 /// Saturate the cost to the maximal representable value.
463 void saturate();
464
465 /// Return an instance of MappingCost that represents an
466 /// impossible mapping.
467 static MappingCost ImpossibleCost();
468
469 /// Check if this is less than \p Cost.
470 bool operator<(const MappingCost &Cost) const;
471 /// Check if this is equal to \p Cost.
472 bool operator==(const MappingCost &Cost) const;
473 /// Check if this is not equal to \p Cost.
474 bool operator!=(const MappingCost &Cost) const { return !(*this == Cost); }
475 /// Check if this is greater than \p Cost.
476 bool operator>(const MappingCost &Cost) const {
477 return *this != Cost && Cost < *this;
478 }
479
480 /// Print this on dbgs() stream.
481 void dump() const;
482
483 /// Print this on \p OS;
484 void print(raw_ostream &OS) const;
485
486 /// Overload the stream operator for easy debug printing.
487 [[maybe_unused]] friend raw_ostream &operator<<(raw_ostream &OS,
488 const MappingCost &Cost) {
489 Cost.print(OS);
490 return OS;
491 }
492 };
493
494 /// Interface to the target lowering info related
495 /// to register banks.
496 const RegisterBankInfo *RBI = nullptr;
497
498 /// MRI contains all the register class/bank information that this
499 /// pass uses and updates.
500 MachineRegisterInfo *MRI = nullptr;
501
502 /// Information on the register classes for the current function.
503 const TargetRegisterInfo *TRI = nullptr;
504
505 /// Get the frequency of blocks.
506 /// This is required for non-fast mode.
507 MachineBlockFrequencyInfo *MBFI = nullptr;
508
509 /// Get the frequency of the edges.
510 /// This is required for non-fast mode.
511 MachineBranchProbabilityInfo *MBPI = nullptr;
512
513 /// Current optimization remark emitter. Used to report failures.
514 std::unique_ptr<MachineOptimizationRemarkEmitter> MORE;
515
516 /// Helper class used for every code morphing.
517 MachineIRBuilder MIRBuilder;
518
519 /// Optimization mode of the pass.
520 RegBankSelectMode OptMode;
521
522 /// The current Pass/MFAM reference to enable updating analyses.
523 Pass *P = nullptr;
524 MachineFunctionAnalysisManager *MFAM = nullptr;
525
526 /// Assign the register bank of each operand of \p MI.
527 /// \return True on success, false otherwise.
528 bool
529 assignInstr(MachineInstr &MI,
530 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
531 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI);
532
533 /// Initialize the field members using \p MF.
534 void init(MachineFunction &MF,
535 function_ref<MachineBlockFrequencyInfo *()> GetMBFI,
536 function_ref<MachineBranchProbabilityInfo *()> GetMBPI);
537
538 /// Check if \p Reg is already assigned what is described by \p ValMapping.
539 /// \p OnlyAssign == true means that \p Reg just needs to be assigned a
540 /// register bank. I.e., no repairing is necessary to have the
541 /// assignment match.
542 bool assignmentMatch(Register Reg,
543 const RegisterBankInfo::ValueMapping &ValMapping,
544 bool &OnlyAssign) const;
545
546 /// Insert repairing code for \p Reg as specified by \p ValMapping.
547 /// The repairing placement is specified by \p RepairPt.
548 /// \p NewVRegs contains all the registers required to remap \p Reg.
549 /// In other words, the number of registers in NewVRegs must be equal
550 /// to ValMapping.BreakDown.size().
551 ///
552 /// The transformation could be sketched as:
553 /// \code
554 /// ... = op Reg
555 /// \endcode
556 /// Becomes
557 /// \code
558 /// <NewRegs> = COPY or extract Reg
559 /// ... = op Reg
560 /// \endcode
561 ///
562 /// and
563 /// \code
564 /// Reg = op ...
565 /// \endcode
566 /// Becomes
567 /// \code
568 /// Reg = op ...
569 /// Reg = COPY or build_sequence <NewRegs>
570 /// \endcode
571 ///
572 /// \pre NewVRegs.size() == ValMapping.BreakDown.size()
573 ///
574 /// \note The caller is supposed to do the rewriting of op if need be.
575 /// I.e., Reg = op ... => <NewRegs> = NewOp ...
576 ///
577 /// \return True if the repairing worked, false otherwise.
578 bool repairReg(MachineOperand &MO,
579 const RegisterBankInfo::ValueMapping &ValMapping,
580 RegBankSelectImpl::RepairingPlacement &RepairPt,
581 const iterator_range<SmallVectorImpl<Register>::const_iterator>
582 &NewVRegs);
583
584 /// Return the cost of the instruction needed to map \p MO to \p ValMapping.
585 /// The cost is free of basic block frequencies.
586 /// \pre MO.isReg()
587 /// \pre MO is assigned to a register bank.
588 /// \pre ValMapping is a valid mapping for MO.
589 uint64_t
590 getRepairCost(const MachineOperand &MO,
591 const RegisterBankInfo::ValueMapping &ValMapping) const;
592
593 /// Find the best mapping for \p MI from \p PossibleMappings.
594 /// \return a reference on the best mapping in \p PossibleMappings.
595 const RegisterBankInfo::InstructionMapping &
596 findBestMapping(MachineInstr &MI,
597 RegisterBankInfo::InstructionMappings &PossibleMappings,
598 SmallVectorImpl<RepairingPlacement> &RepairPts,
599 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
600 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI);
601
602 /// Compute the cost of mapping \p MI with \p InstrMapping and
603 /// compute the repairing placement for such mapping in \p
604 /// RepairPts.
605 /// \p BestCost is used to specify when the cost becomes too high
606 /// and thus it is not worth computing the RepairPts. Moreover if
607 /// \p BestCost == nullptr, the mapping cost is actually not
608 /// computed.
609 MappingCost
610 computeMapping(MachineInstr &MI,
611 const RegisterBankInfo::InstructionMapping &InstrMapping,
612 SmallVectorImpl<RepairingPlacement> &RepairPts,
613 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
614 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI,
615 const MappingCost *BestCost = nullptr);
616
617 /// When \p RepairPt involves splitting to repair the operand of \p MI it
618 /// refers to for the given \p ValMapping, try to change the way we repair
619 /// such that the splitting is not required anymore.
620 ///
621 /// \pre \p RepairPt.hasSplit()
622 /// \pre \p ValMapping is the mapping of \p MI.getOperand(RepairPt.getOpIdx())
623 /// that implied \p RepairPt.
624 void tryAvoidingSplit(RegBankSelectImpl::RepairingPlacement &RepairPt,
625 const MachineInstr &MI,
626 const RegisterBankInfo::ValueMapping &ValMapping) const;
627
628 /// Apply \p Mapping to \p MI. \p RepairPts represents the different
629 /// mapping action that need to happen for the mapping to be
630 /// applied.
631 /// \return True if the mapping was applied sucessfully, false otherwise.
632 bool applyMapping(MachineInstr &MI,
633 const RegisterBankInfo::InstructionMapping &InstrMapping,
634 SmallVectorImpl<RepairingPlacement> &RepairPts);
635
636public:
637 /// Create a RegBankSelect pass with the specified \p RunningMode.
638 RegBankSelectImpl(RegBankSelectMode RunningMode);
639
640 /// Check that our input is fully legal: we require the function to have the
641 /// Legalized property, so it should be.
642 ///
643 /// FIXME: This should be in the MachineVerifier.
644 bool checkFunctionIsLegal(MachineFunction &MF) const;
645
646 /// Walk through \p MF and assign a register bank to every virtual register
647 /// that are still mapped to nothing.
648 /// The target needs to provide a RegisterBankInfo and in particular
649 /// override RegisterBankInfo::getInstrMapping.
650 ///
651 /// Simplified algo:
652 /// \code
653 /// RBI = MF.subtarget.getRegBankInfo()
654 /// MIRBuilder.setMF(MF)
655 /// for each bb in MF
656 /// for each inst in bb
657 /// MIRBuilder.setInstr(inst)
658 /// MappingCosts = RBI.getMapping(inst);
659 /// Idx = findIdxOfMinCost(MappingCosts)
660 /// CurRegBank = MappingCosts[Idx].RegBank
661 /// MRI.setRegBank(inst.getOperand(0).getReg(), CurRegBank)
662 /// for each argument in inst
663 /// if (CurRegBank != argument.RegBank)
664 /// ArgReg = argument.getReg()
665 /// Tmp = MRI.createNewVirtual(MRI.getSize(ArgReg), CurRegBank)
666 /// MIRBuilder.buildInstr(COPY, Tmp, ArgReg)
667 /// inst.getOperand(argument.getOperandNo()).setReg(Tmp)
668 /// \endcode
669 bool assignRegisterBanks(
670 MachineFunction &MF,
671 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
672 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI);
673
674 bool runOnMachineFunction(
675 MachineFunction &MF, Pass *PassRef,
676 MachineFunctionAnalysisManager *MFAMRef,
677 function_ref<MachineBlockFrequencyInfo *()> GetMBFI,
678 function_ref<MachineBranchProbabilityInfo *()> GetMBPI,
679 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
680 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI);
681};
682
683} // namespace
684
685RegBankSelectImpl::RegBankSelectImpl(RegBankSelectMode RunningMode)
686 : OptMode(RunningMode) {}
687
688RegBankSelectLegacy::RegBankSelectLegacy(RegBankSelectMode RunningMode)
689 : MachineFunctionPass(ID), OptMode(computeOptMode(RequestedMode: RunningMode)) {}
690
691void RegBankSelectImpl::init(
692 MachineFunction &MF, function_ref<MachineBlockFrequencyInfo *()> GetMBFI,
693 function_ref<MachineBranchProbabilityInfo *()> GetMBPI) {
694 RBI = MF.getSubtarget().getRegBankInfo();
695 assert(RBI && "Cannot work without RegisterBankInfo");
696 MRI = &MF.getRegInfo();
697 TRI = MF.getSubtarget().getRegisterInfo();
698 if (OptMode != RegBankSelectMode::Fast) {
699 MBFI = GetMBFI();
700 MBPI = GetMBPI();
701 } else {
702 MBFI = nullptr;
703 MBPI = nullptr;
704 }
705 MIRBuilder.setMF(MF);
706 MORE = std::make_unique<MachineOptimizationRemarkEmitter>(args&: MF, args&: MBFI);
707}
708
709void RegBankSelectLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
710 if (OptMode != RegBankSelectMode::Fast) {
711 // We could preserve the information from these two analysis but
712 // the APIs do not allow to do so yet.
713 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
714 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
715 }
716 AU.addRequired<TargetPassConfig>();
717 getSelectionDAGFallbackAnalysisUsage(AU);
718 MachineFunctionPass::getAnalysisUsage(AU);
719}
720
721bool RegBankSelectImpl::assignmentMatch(
722 Register Reg, const RegisterBankInfo::ValueMapping &ValMapping,
723 bool &OnlyAssign) const {
724 // By default we assume we will have to repair something.
725 OnlyAssign = false;
726 // Each part of a break down needs to end up in a different register.
727 // In other word, Reg assignment does not match.
728 if (ValMapping.NumBreakDowns != 1)
729 return false;
730
731 const RegisterBank *CurRegBank = RBI->getRegBank(Reg, MRI: *MRI, TRI: *TRI);
732 const RegisterBank *DesiredRegBank = ValMapping.BreakDown[0].RegBank;
733 // Reg is free of assignment, a simple assignment will make the
734 // register bank to match.
735 OnlyAssign = CurRegBank == nullptr;
736 LLVM_DEBUG(dbgs() << "Does assignment already match: ";
737 if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none";
738 dbgs() << " against ";
739 assert(DesiredRegBank && "The mapping must be valid");
740 dbgs() << *DesiredRegBank << '\n';);
741 return CurRegBank == DesiredRegBank;
742}
743
744bool RegBankSelectImpl::repairReg(
745 MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping,
746 RegBankSelectImpl::RepairingPlacement &RepairPt,
747 const iterator_range<SmallVectorImpl<Register>::const_iterator> &NewVRegs) {
748
749 assert(ValMapping.NumBreakDowns == (unsigned)size(NewVRegs) &&
750 "need new vreg for each breakdown");
751
752 // An empty range of new register means no repairing.
753 assert(!NewVRegs.empty() && "We should not have to repair");
754
755 MachineInstr *MI;
756 if (ValMapping.NumBreakDowns == 1) {
757 // Assume we are repairing a use and thus, the original reg will be
758 // the source of the repairing.
759 Register Src = MO.getReg();
760 Register Dst = *NewVRegs.begin();
761
762 // If we repair a definition, swap the source and destination for
763 // the repairing.
764 if (MO.isDef())
765 std::swap(a&: Src, b&: Dst);
766
767 assert((RepairPt.getNumInsertPoints() == 1 || Dst.isPhysical()) &&
768 "We are about to create several defs for Dst");
769
770 // Build the instruction used to repair, then clone it at the right
771 // places. Avoiding buildCopy bypasses the check that Src and Dst have the
772 // same types because the type is a placeholder when this function is called.
773 MI = MIRBuilder.buildInstrNoInsert(Opcode: TargetOpcode::COPY)
774 .addDef(RegNo: Dst)
775 .addUse(RegNo: Src);
776 LLVM_DEBUG(dbgs() << "Copy: " << printReg(Src) << ':'
777 << printRegClassOrBank(Src, *MRI, TRI)
778 << " to: " << printReg(Dst) << ':'
779 << printRegClassOrBank(Dst, *MRI, TRI) << '\n');
780 } else {
781 // TODO: Support with G_IMPLICIT_DEF + G_INSERT sequence or G_EXTRACT
782 // sequence.
783 assert(ValMapping.partsAllUniform() && "irregular breakdowns not supported");
784
785 LLT RegTy = MRI->getType(Reg: MO.getReg());
786 if (MO.isDef()) {
787 unsigned MergeOp;
788 if (RegTy.isVector()) {
789 if (ValMapping.NumBreakDowns == RegTy.getNumElements())
790 MergeOp = TargetOpcode::G_BUILD_VECTOR;
791 else {
792 assert(
793 (ValMapping.BreakDown[0].Length * ValMapping.NumBreakDowns ==
794 RegTy.getSizeInBits()) &&
795 (ValMapping.BreakDown[0].Length % RegTy.getScalarSizeInBits() ==
796 0) &&
797 "don't understand this value breakdown");
798
799 MergeOp = TargetOpcode::G_CONCAT_VECTORS;
800 }
801 } else
802 MergeOp = TargetOpcode::G_MERGE_VALUES;
803
804 auto MergeBuilder =
805 MIRBuilder.buildInstrNoInsert(Opcode: MergeOp)
806 .addDef(RegNo: MO.getReg());
807
808 for (Register SrcReg : NewVRegs)
809 MergeBuilder.addUse(RegNo: SrcReg);
810
811 MI = MergeBuilder;
812 } else {
813 MachineInstrBuilder UnMergeBuilder =
814 MIRBuilder.buildInstrNoInsert(Opcode: TargetOpcode::G_UNMERGE_VALUES);
815 for (Register DefReg : NewVRegs)
816 UnMergeBuilder.addDef(RegNo: DefReg);
817
818 UnMergeBuilder.addUse(RegNo: MO.getReg());
819 MI = UnMergeBuilder;
820 }
821 }
822
823 if (RepairPt.getNumInsertPoints() != 1)
824 report_fatal_error(reason: "need testcase to support multiple insertion points");
825
826 // TODO:
827 // Check if MI is legal. if not, we need to legalize all the
828 // instructions we are going to insert.
829 std::unique_ptr<MachineInstr *[]> NewInstrs(
830 new MachineInstr *[RepairPt.getNumInsertPoints()]);
831 bool IsFirst = true;
832 unsigned Idx = 0;
833 for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
834 MachineInstr *CurMI;
835 if (IsFirst)
836 CurMI = MI;
837 else
838 CurMI = MIRBuilder.getMF().CloneMachineInstr(Orig: MI);
839 InsertPt->insert(MI&: *CurMI);
840 NewInstrs[Idx++] = CurMI;
841 IsFirst = false;
842 }
843 // TODO:
844 // Legalize NewInstrs if need be.
845 return true;
846}
847
848uint64_t RegBankSelectImpl::getRepairCost(
849 const MachineOperand &MO,
850 const RegisterBankInfo::ValueMapping &ValMapping) const {
851 assert(MO.isReg() && "We should only repair register operand");
852 assert(ValMapping.NumBreakDowns && "Nothing to map??");
853
854 bool IsSameNumOfValues = ValMapping.NumBreakDowns == 1;
855 const RegisterBank *CurRegBank = RBI->getRegBank(Reg: MO.getReg(), MRI: *MRI, TRI: *TRI);
856 // If MO does not have a register bank, we should have just been
857 // able to set one unless we have to break the value down.
858 assert(CurRegBank || MO.isDef());
859
860 // Def: Val <- NewDefs
861 // Same number of values: copy
862 // Different number: Val = build_sequence Defs1, Defs2, ...
863 // Use: NewSources <- Val.
864 // Same number of values: copy.
865 // Different number: Src1, Src2, ... =
866 // extract_value Val, Src1Begin, Src1Len, Src2Begin, Src2Len, ...
867 // We should remember that this value is available somewhere else to
868 // coalesce the value.
869
870 if (ValMapping.NumBreakDowns != 1)
871 return RBI->getBreakDownCost(ValMapping, CurBank: CurRegBank);
872
873 if (IsSameNumOfValues) {
874 const RegisterBank *DesiredRegBank = ValMapping.BreakDown[0].RegBank;
875 // If we repair a definition, swap the source and destination for
876 // the repairing.
877 if (MO.isDef())
878 std::swap(a&: CurRegBank, b&: DesiredRegBank);
879 // TODO: It may be possible to actually avoid the copy.
880 // If we repair something where the source is defined by a copy
881 // and the source of that copy is on the right bank, we can reuse
882 // it for free.
883 // E.g.,
884 // RegToRepair<BankA> = copy AlternativeSrc<BankB>
885 // = op RegToRepair<BankA>
886 // We can simply propagate AlternativeSrc instead of copying RegToRepair
887 // into a new virtual register.
888 // We would also need to propagate this information in the
889 // repairing placement.
890 unsigned Cost = RBI->copyCost(A: *DesiredRegBank, B: *CurRegBank,
891 Size: RBI->getSizeInBits(Reg: MO.getReg(), MRI: *MRI, TRI: *TRI));
892 if (Cost != ImpossibleRepairCost)
893 return Cost;
894 // Return the legalization cost of that repairing.
895 }
896 return ImpossibleRepairCost;
897}
898
899const RegisterBankInfo::InstructionMapping &RegBankSelectImpl::findBestMapping(
900 MachineInstr &MI, RegisterBankInfo::InstructionMappings &PossibleMappings,
901 SmallVectorImpl<RepairingPlacement> &RepairPts,
902 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
903 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI) {
904 assert(!PossibleMappings.empty() &&
905 "Do not know how to map this instruction");
906
907 const RegisterBankInfo::InstructionMapping *BestMapping = nullptr;
908 MappingCost Cost = MappingCost::ImpossibleCost();
909 SmallVector<RepairingPlacement, 4> LocalRepairPts;
910 for (const RegisterBankInfo::InstructionMapping *CurMapping :
911 PossibleMappings) {
912 MappingCost CurCost = computeMapping(MI, InstrMapping: *CurMapping, RepairPts&: LocalRepairPts,
913 GetCachedMBFI, GetCachedMBPI, BestCost: &Cost);
914 if (CurCost < Cost) {
915 LLVM_DEBUG(dbgs() << "New best: " << CurCost << '\n');
916 Cost = CurCost;
917 BestMapping = CurMapping;
918 RepairPts.clear();
919 for (RepairingPlacement &RepairPt : LocalRepairPts)
920 RepairPts.emplace_back(Args: std::move(RepairPt));
921 }
922 }
923 if (!BestMapping && MI.getMF()->getTarget().Options.GlobalISelAbort !=
924 GlobalISelAbortMode::Enable) {
925 // If none of the mapping worked that means they are all impossible.
926 // Thus, pick the first one and set an impossible repairing point.
927 // It will trigger the failed isel mode.
928 BestMapping = *PossibleMappings.begin();
929 RepairPts.emplace_back(Args: RepairingPlacement(MI, 0, *TRI, P, MFAM,
930 RepairingPlacement::Impossible));
931 } else
932 assert(BestMapping && "No suitable mapping for instruction");
933 return *BestMapping;
934}
935
936void RegBankSelectImpl::tryAvoidingSplit(
937 RegBankSelectImpl::RepairingPlacement &RepairPt, const MachineInstr &MI,
938 const RegisterBankInfo::ValueMapping &ValMapping) const {
939 const MachineOperand &MO = MI.getOperand(i: RepairPt.getOpIdx());
940 assert(RepairPt.hasSplit() && "We should not have to adjust for split");
941 // Splitting should only occur for PHIs or between terminators,
942 // because we only do local repairing.
943 assert((MI.isPHI() || MI.isTerminator()) && "Why do we split?");
944
945 // If we need splitting for phis, that means it is because we
946 // could not find an insertion point before the terminators of
947 // the predecessor block for this argument. In other words,
948 // the input value is defined by one of the terminators.
949 assert((!MI.isPHI() || !MO.isDef()) && "Need split for phi def?");
950
951 // We split to repair the use of a phi or a terminator.
952 if (!MO.isDef()) {
953 if (MI.isTerminator()) {
954 assert(&MI != &(*MI.getParent()->getFirstTerminator()) &&
955 "Need to split for the first terminator?!");
956 } else {
957 // For the PHI case, the split may not be actually required.
958 // In the copy case, a phi is already a copy on the incoming edge,
959 // therefore there is no need to split.
960 if (ValMapping.NumBreakDowns == 1)
961 // This is a already a copy, there is nothing to do.
962 RepairPt.switchTo(NewKind: RepairingPlacement::RepairingKind::Reassign);
963 }
964 return;
965 }
966
967 // At this point, we need to repair a defintion of a terminator.
968
969 // Technically we need to fix the def of MI on all outgoing
970 // edges of MI to keep the repairing local. In other words, we
971 // will create several definitions of the same register. This
972 // does not work for SSA unless that definition is a physical
973 // register.
974 // However, there are other cases where we can get away with
975 // that while still keeping the repairing local.
976 assert(MI.isTerminator() && MO.isDef() &&
977 "This code is for the def of a terminator");
978
979 // Since we use RPO traversal, if we need to repair a definition
980 // this means this definition could be:
981 // 1. Used by PHIs (i.e., this VReg has been visited as part of the
982 // uses of a phi.), or
983 // 2. Part of a target specific instruction (i.e., the target applied
984 // some register class constraints when creating the instruction.)
985 // If the constraints come for #2, the target said that another mapping
986 // is supported so we may just drop them. Indeed, if we do not change
987 // the number of registers holding that value, the uses will get fixed
988 // when we get to them.
989 // Uses in PHIs may have already been proceeded though.
990 // If the constraints come for #1, then, those are weak constraints and
991 // no actual uses may rely on them. However, the problem remains mainly
992 // the same as for #2. If the value stays in one register, we could
993 // just switch the register bank of the definition, but we would need to
994 // account for a repairing cost for each phi we silently change.
995 //
996 // In any case, if the value needs to be broken down into several
997 // registers, the repairing is not local anymore as we need to patch
998 // every uses to rebuild the value in just one register.
999 //
1000 // To summarize:
1001 // - If the value is in a physical register, we can do the split and
1002 // fix locally.
1003 // Otherwise if the value is in a virtual register:
1004 // - If the value remains in one register, we do not have to split
1005 // just switching the register bank would do, but we need to account
1006 // in the repairing cost all the phi we changed.
1007 // - If the value spans several registers, then we cannot do a local
1008 // repairing.
1009
1010 // Check if this is a physical or virtual register.
1011 Register Reg = MO.getReg();
1012 if (Reg.isPhysical()) {
1013 // We are going to split every outgoing edges.
1014 // Check that this is possible.
1015 // FIXME: The machine representation is currently broken
1016 // since it also several terminators in one basic block.
1017 // Because of that we would technically need a way to get
1018 // the targets of just one terminator to know which edges
1019 // we have to split.
1020 // Assert that we do not hit the ill-formed representation.
1021
1022 // If there are other terminators before that one, some of
1023 // the outgoing edges may not be dominated by this definition.
1024 assert(&MI == &(*MI.getParent()->getFirstTerminator()) &&
1025 "Do not know which outgoing edges are relevant");
1026 const MachineInstr *Next = MI.getNextNode();
1027 assert((!Next || Next->isUnconditionalBranch()) &&
1028 "Do not know where each terminator ends up");
1029 if (Next)
1030 // If the next terminator uses Reg, this means we have
1031 // to split right after MI and thus we need a way to ask
1032 // which outgoing edges are affected.
1033 assert(!Next->readsRegister(Reg, /*TRI=*/nullptr) &&
1034 "Need to split between terminators");
1035 // We will split all the edges and repair there.
1036 } else {
1037 // This is a virtual register defined by a terminator.
1038 if (ValMapping.NumBreakDowns == 1) {
1039 // There is nothing to repair, but we may actually lie on
1040 // the repairing cost because of the PHIs already proceeded
1041 // as already stated.
1042 // Though the code will be correct.
1043 assert(false && "Repairing cost may not be accurate");
1044 } else {
1045 // We need to do non-local repairing. Basically, patch all
1046 // the uses (i.e., phis) that we already proceeded.
1047 // For now, just say this mapping is not possible.
1048 RepairPt.switchTo(NewKind: RepairingPlacement::RepairingKind::Impossible);
1049 }
1050 }
1051}
1052
1053RegBankSelectImpl::MappingCost RegBankSelectImpl::computeMapping(
1054 MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
1055 SmallVectorImpl<RepairingPlacement> &RepairPts,
1056 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
1057 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI,
1058 const RegBankSelectImpl::MappingCost *BestCost) {
1059 assert((MBFI || !BestCost) && "Costs comparison require MBFI");
1060
1061 if (!InstrMapping.isValid())
1062 return MappingCost::ImpossibleCost();
1063
1064 // If mapped with InstrMapping, MI will have the recorded cost.
1065 MappingCost Cost(MBFI ? MBFI->getBlockFreq(MBB: MI.getParent())
1066 : BlockFrequency(1));
1067 bool Saturated = Cost.addLocalCost(Cost: InstrMapping.getCost());
1068 assert(!Saturated && "Possible mapping saturated the cost");
1069 LLVM_DEBUG(dbgs() << "Evaluating mapping cost for: " << MI);
1070 LLVM_DEBUG(dbgs() << "With: " << InstrMapping << '\n');
1071 RepairPts.clear();
1072 if (BestCost && Cost > *BestCost) {
1073 LLVM_DEBUG(dbgs() << "Mapping is too expensive from the start\n");
1074 return Cost;
1075 }
1076 const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
1077
1078 // Moreover, to realize this mapping, the register bank of each operand must
1079 // match this mapping. In other words, we may need to locally reassign the
1080 // register banks. Account for that repairing cost as well.
1081 // In this context, local means in the surrounding of MI.
1082 for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands();
1083 OpIdx != EndOpIdx; ++OpIdx) {
1084 const MachineOperand &MO = MI.getOperand(i: OpIdx);
1085 if (!MO.isReg())
1086 continue;
1087 Register Reg = MO.getReg();
1088 if (!Reg)
1089 continue;
1090 LLT Ty = MRI.getType(Reg);
1091 if (!Ty.isValid())
1092 continue;
1093
1094 LLVM_DEBUG(dbgs() << "Opd" << OpIdx << '\n');
1095 const RegisterBankInfo::ValueMapping &ValMapping =
1096 InstrMapping.getOperandMapping(i: OpIdx);
1097 // If Reg is already properly mapped, this is free.
1098 bool Assign;
1099 if (assignmentMatch(Reg, ValMapping, OnlyAssign&: Assign)) {
1100 LLVM_DEBUG(dbgs() << "=> is free (match).\n");
1101 continue;
1102 }
1103 if (Assign) {
1104 LLVM_DEBUG(dbgs() << "=> is free (simple assignment).\n");
1105 RepairPts.emplace_back(Args: RepairingPlacement(MI, OpIdx, *TRI, P, MFAM,
1106 RepairingPlacement::Reassign));
1107 continue;
1108 }
1109
1110 // Find the insertion point for the repairing code.
1111 RepairPts.emplace_back(Args: RepairingPlacement(MI, OpIdx, *TRI, P, MFAM,
1112 RepairingPlacement::Insert));
1113 RepairingPlacement &RepairPt = RepairPts.back();
1114
1115 // If we need to split a basic block to materialize this insertion point,
1116 // we may give a higher cost to this mapping.
1117 // Nevertheless, we may get away with the split, so try that first.
1118 if (RepairPt.hasSplit())
1119 tryAvoidingSplit(RepairPt, MI, ValMapping);
1120
1121 // Check that the materialization of the repairing is possible.
1122 if (!RepairPt.canMaterialize()) {
1123 LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n");
1124 return MappingCost::ImpossibleCost();
1125 }
1126
1127 // Account for the split cost and repair cost.
1128 // Unless the cost is already saturated or we do not care about the cost.
1129 if (!BestCost || Saturated)
1130 continue;
1131
1132 // To get accurate information we need MBFI and MBPI.
1133 // Thus, if we end up here this information should be here.
1134 assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI");
1135
1136 // FIXME: We will have to rework the repairing cost model.
1137 // The repairing cost depends on the register bank that MO has.
1138 // However, when we break down the value into different values,
1139 // MO may not have a register bank while still needing repairing.
1140 // For the fast mode, we don't compute the cost so that is fine,
1141 // but still for the repairing code, we will have to make a choice.
1142 // For the greedy mode, we should choose greedily what is the best
1143 // choice based on the next use of MO.
1144
1145 // Sums up the repairing cost of MO at each insertion point.
1146 uint64_t RepairCost = getRepairCost(MO, ValMapping);
1147
1148 // This is an impossible to repair cost.
1149 if (RepairCost == ImpossibleRepairCost)
1150 return MappingCost::ImpossibleCost();
1151
1152 // Bias used for splitting: 5%.
1153 const uint64_t PercentageForBias = 5;
1154 uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100;
1155 // We should not need more than a couple of instructions to repair
1156 // an assignment. In other words, the computation should not
1157 // overflow because the repairing cost is free of basic block
1158 // frequency.
1159 assert(((RepairCost < RepairCost * PercentageForBias) &&
1160 (RepairCost * PercentageForBias <
1161 RepairCost * PercentageForBias + 99)) &&
1162 "Repairing involves more than a billion of instructions?!");
1163 for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
1164 assert(InsertPt->canMaterialize() && "We should not have made it here");
1165 // We will applied some basic block frequency and those uses uint64_t.
1166 if (!InsertPt->isSplit())
1167 Saturated = Cost.addLocalCost(Cost: RepairCost);
1168 else {
1169 uint64_t CostForInsertPt = RepairCost;
1170 // Again we shouldn't overflow here givent that
1171 // CostForInsertPt is frequency free at this point.
1172 assert(CostForInsertPt + Bias > CostForInsertPt &&
1173 "Repairing + split bias overflows");
1174 CostForInsertPt += Bias;
1175 uint64_t PtCost =
1176 InsertPt->frequency(GetCachedMBFI, GetCachedMBPI) * CostForInsertPt;
1177 // Check if we just overflowed.
1178 if ((Saturated = PtCost < CostForInsertPt))
1179 Cost.saturate();
1180 else
1181 Saturated = Cost.addNonLocalCost(Cost: PtCost);
1182 }
1183
1184 // Stop looking into what it takes to repair, this is already
1185 // too expensive.
1186 if (BestCost && Cost > *BestCost) {
1187 LLVM_DEBUG(dbgs() << "Mapping is too expensive, stop processing\n");
1188 return Cost;
1189 }
1190
1191 // No need to accumulate more cost information.
1192 // We need to still gather the repairing information though.
1193 if (Saturated)
1194 break;
1195 }
1196 }
1197 LLVM_DEBUG(dbgs() << "Total cost is: " << Cost << "\n");
1198 return Cost;
1199}
1200
1201bool RegBankSelectImpl::applyMapping(
1202 MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping,
1203 SmallVectorImpl<RegBankSelectImpl::RepairingPlacement> &RepairPts) {
1204 // OpdMapper will hold all the information needed for the rewriting.
1205 std::optional<RegisterBankInfo::OperandsMapper> OpdMapper;
1206
1207 // First, place the repairing code.
1208 for (RepairingPlacement &RepairPt : RepairPts) {
1209 if (!RepairPt.canMaterialize() ||
1210 RepairPt.getKind() == RepairingPlacement::Impossible)
1211 return false;
1212 assert(RepairPt.getKind() != RepairingPlacement::None &&
1213 "This should not make its way in the list");
1214 unsigned OpIdx = RepairPt.getOpIdx();
1215 MachineOperand &MO = MI.getOperand(i: OpIdx);
1216 const RegisterBankInfo::ValueMapping &ValMapping =
1217 InstrMapping.getOperandMapping(i: OpIdx);
1218 Register Reg = MO.getReg();
1219
1220 switch (RepairPt.getKind()) {
1221 case RepairingPlacement::Reassign:
1222 assert(ValMapping.NumBreakDowns == 1 &&
1223 "Reassignment should only be for simple mapping");
1224 MRI->setRegBank(Reg, RegBank: *ValMapping.BreakDown[0].RegBank);
1225 break;
1226 case RepairingPlacement::Insert:
1227 // Don't insert additional instruction for debug instruction.
1228 if (MI.isDebugInstr())
1229 break;
1230 if (!OpdMapper)
1231 OpdMapper.emplace(args&: MI, args: InstrMapping, args&: *MRI);
1232 OpdMapper->createVRegs(OpIdx);
1233 if (!repairReg(MO, ValMapping, RepairPt, NewVRegs: OpdMapper->getVRegs(OpIdx)))
1234 return false;
1235 break;
1236 default:
1237 llvm_unreachable("Other kind should not happen");
1238 }
1239 }
1240
1241 // Default mappings only need rewriting when repairs create new operands.
1242 if (!OpdMapper && InstrMapping.getID() == RegisterBankInfo::DefaultMappingID)
1243 return true;
1244
1245 if (!OpdMapper)
1246 OpdMapper.emplace(args&: MI, args: InstrMapping, args&: *MRI);
1247 // Second, rewrite the instruction.
1248 LLVM_DEBUG(dbgs() << "Actual mapping of the operands: " << *OpdMapper
1249 << '\n');
1250 RBI->applyMapping(Builder&: MIRBuilder, OpdMapper: *OpdMapper);
1251
1252 return true;
1253}
1254
1255bool RegBankSelectImpl::assignInstr(
1256 MachineInstr &MI, function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
1257 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI) {
1258 LLVM_DEBUG(dbgs() << "Assign: " << MI);
1259
1260 unsigned Opc = MI.getOpcode();
1261 if (isPreISelGenericOptimizationHint(Opcode: Opc)) {
1262 assert((Opc == TargetOpcode::G_ASSERT_ZEXT ||
1263 Opc == TargetOpcode::G_ASSERT_SEXT ||
1264 Opc == TargetOpcode::G_ASSERT_ALIGN) &&
1265 "Unexpected hint opcode!");
1266 // The only correct mapping for these is to always use the source register
1267 // bank.
1268 const RegisterBank *RB =
1269 RBI->getRegBank(Reg: MI.getOperand(i: 1).getReg(), MRI: *MRI, TRI: *TRI);
1270 // We can assume every instruction above this one has a selected register
1271 // bank.
1272 assert(RB && "Expected source register to have a register bank?");
1273 LLVM_DEBUG(dbgs() << "... Hint always uses source's register bank.\n");
1274 MRI->setRegBank(Reg: MI.getOperand(i: 0).getReg(), RegBank: *RB);
1275 return true;
1276 }
1277
1278 // Remember the repairing placement for all the operands.
1279 SmallVector<RepairingPlacement, 4> RepairPts;
1280
1281 const RegisterBankInfo::InstructionMapping *BestMapping;
1282 if (OptMode == RegBankSelectMode::Fast) {
1283 BestMapping = &RBI->getInstrMapping(MI);
1284 MappingCost DefaultCost = computeMapping(MI, InstrMapping: *BestMapping, RepairPts,
1285 GetCachedMBFI, GetCachedMBPI);
1286 (void)DefaultCost;
1287 if (DefaultCost == MappingCost::ImpossibleCost())
1288 return false;
1289 } else {
1290 RegisterBankInfo::InstructionMappings PossibleMappings =
1291 RBI->getInstrPossibleMappings(MI);
1292 if (PossibleMappings.empty())
1293 return false;
1294 BestMapping = &findBestMapping(MI, PossibleMappings, RepairPts,
1295 GetCachedMBFI, GetCachedMBPI);
1296 }
1297 // Make sure the mapping is valid for MI.
1298 assert(BestMapping->verify(MI) && "Invalid instruction mapping");
1299
1300 LLVM_DEBUG(dbgs() << "Best Mapping: " << *BestMapping << '\n');
1301
1302 // After this call, MI may not be valid anymore.
1303 // Do not use it.
1304 return applyMapping(MI, InstrMapping: *BestMapping, RepairPts);
1305}
1306
1307bool RegBankSelectImpl::assignRegisterBanks(
1308 MachineFunction &MF,
1309 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
1310 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI) {
1311 // Walk the function and assign register banks to all operands.
1312 // Use a RPOT to make sure all registers are assigned before we choose
1313 // the best mapping of the current instruction.
1314 ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);
1315 for (MachineBasicBlock *MBB : RPOT) {
1316 // Set a sensible insertion point so that subsequent calls to
1317 // MIRBuilder.
1318 MIRBuilder.setMBB(*MBB);
1319 SmallVector<MachineInstr *> WorkList(
1320 make_pointer_range(Range: reverse(C: MBB->instrs())));
1321
1322 while (!WorkList.empty()) {
1323 MachineInstr &MI = *WorkList.pop_back_val();
1324
1325 // Ignore target-specific post-isel instructions: they should use proper
1326 // regclasses.
1327 if (isTargetSpecificOpcode(Opcode: MI.getOpcode()) && !MI.isPreISelOpcode())
1328 continue;
1329
1330 // Ignore inline asm instructions: they should use physical
1331 // registers/regclasses
1332 if (MI.isInlineAsm())
1333 continue;
1334
1335 // Ignore IMPLICIT_DEF which must have a regclass.
1336 if (MI.isImplicitDef())
1337 continue;
1338
1339 if (!assignInstr(MI, GetCachedMBFI, GetCachedMBPI)) {
1340 reportGISelFailure(MF, MORE&: *MORE, PassName: "gisel-regbankselect",
1341 Msg: "unable to map instruction", MI);
1342 return false;
1343 }
1344 }
1345 }
1346
1347 return true;
1348}
1349
1350bool RegBankSelectImpl::checkFunctionIsLegal(MachineFunction &MF) const {
1351#ifndef NDEBUG
1352 if (!DisableGISelLegalityCheck) {
1353 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
1354 reportGISelFailure(MF, *MORE, "gisel-regbankselect",
1355 "instruction is not legal", *MI);
1356 return false;
1357 }
1358 }
1359#endif
1360 return true;
1361}
1362
1363bool RegBankSelectImpl::runOnMachineFunction(
1364 MachineFunction &MF, Pass *PassRef, MachineFunctionAnalysisManager *MFAMRef,
1365 function_ref<MachineBlockFrequencyInfo *()> GetMBFI,
1366 function_ref<MachineBranchProbabilityInfo *()> GetMBPI,
1367 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
1368 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI) {
1369 // If the ISel pipeline failed, do not bother running that pass.
1370 if (MF.getProperties().hasFailedISel())
1371 return false;
1372
1373 P = PassRef;
1374 MFAM = MFAMRef;
1375
1376 LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
1377 const Function &F = MF.getFunction();
1378 RegBankSelectMode SaveOptMode = OptMode;
1379 if (F.hasOptNone())
1380 OptMode = RegBankSelectMode::Fast;
1381 init(MF, GetMBFI, GetMBPI);
1382
1383#ifndef NDEBUG
1384 if (!checkFunctionIsLegal(MF))
1385 return false;
1386#endif
1387
1388 assignRegisterBanks(MF, GetCachedMBFI, GetCachedMBPI);
1389
1390 OptMode = SaveOptMode;
1391 return false;
1392}
1393
1394//------------------------------------------------------------------------------
1395// Helper Classes Implementation
1396//------------------------------------------------------------------------------
1397RegBankSelectImpl::RepairingPlacement::RepairingPlacement(
1398 MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass *P,
1399 MachineFunctionAnalysisManager *MFAM,
1400 RepairingPlacement::RepairingKind Kind)
1401 // Default is, we are going to insert code to repair OpIdx.
1402 : Kind(Kind), OpIdx(OpIdx),
1403 CanMaterialize(Kind != RepairingKind::Impossible), P(P) {
1404 const MachineOperand &MO = MI.getOperand(i: OpIdx);
1405 assert(MO.isReg() && "Trying to repair a non-reg operand");
1406
1407 if (Kind != RepairingKind::Insert)
1408 return;
1409
1410 // Repairings for definitions happen after MI, uses happen before.
1411 bool Before = !MO.isDef();
1412
1413 // Check if we are done with MI.
1414 if (!MI.isPHI() && !MI.isTerminator()) {
1415 addInsertPoint(MI, Before);
1416 // We are done with the initialization.
1417 return;
1418 }
1419
1420 // Now, look for the special cases.
1421 if (MI.isPHI()) {
1422 // - PHI must be the first instructions:
1423 // * Before, we have to split the related incoming edge.
1424 // * After, move the insertion point past the last phi.
1425 if (!Before) {
1426 MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI();
1427 if (It != MI.getParent()->end())
1428 addInsertPoint(MI&: *It, /*Before*/ true);
1429 else
1430 addInsertPoint(MI&: *(--It), /*Before*/ false);
1431 return;
1432 }
1433 // We repair a use of a phi, we may need to split the related edge.
1434 MachineBasicBlock &Pred = *MI.getOperand(i: OpIdx + 1).getMBB();
1435 // Check if we can move the insertion point prior to the
1436 // terminators of the predecessor.
1437 Register Reg = MO.getReg();
1438 MachineBasicBlock::iterator It = Pred.getLastNonDebugInstr();
1439 for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It)
1440 if (It->modifiesRegister(Reg, TRI: &TRI)) {
1441 // We cannot hoist the repairing code in the predecessor.
1442 // Split the edge.
1443 addInsertPoint(Src&: Pred, Dst&: *MI.getParent());
1444 return;
1445 }
1446 // At this point, we can insert in Pred.
1447
1448 // - If It is invalid, Pred is empty and we can insert in Pred
1449 // wherever we want.
1450 // - If It is valid, It is the first non-terminator, insert after It.
1451 if (It == Pred.end())
1452 addInsertPoint(MBB&: Pred, /*Beginning*/ false);
1453 else
1454 addInsertPoint(MI&: *It, /*Before*/ false);
1455 } else {
1456 // - Terminators must be the last instructions:
1457 // * Before, move the insert point before the first terminator.
1458 // * After, we have to split the outcoming edges.
1459 if (Before) {
1460 // Check whether Reg is defined by any terminator.
1461 MachineBasicBlock::reverse_iterator It = MI;
1462 auto REnd = MI.getParent()->rend();
1463
1464 for (; It != REnd && It->isTerminator(); ++It) {
1465 assert(!It->modifiesRegister(MO.getReg(), &TRI) &&
1466 "copy insertion in middle of terminators not handled");
1467 }
1468
1469 if (It == REnd) {
1470 addInsertPoint(MI&: *MI.getParent()->begin(), Before: true);
1471 return;
1472 }
1473
1474 // We are sure to be right before the first terminator.
1475 addInsertPoint(MI&: *It, /*Before*/ false);
1476 return;
1477 }
1478 // Make sure Reg is not redefined by other terminators, otherwise
1479 // we do not know how to split.
1480 for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end();
1481 ++It != End;)
1482 // The machine verifier should reject this kind of code.
1483 assert(It->modifiesRegister(MO.getReg(), &TRI) &&
1484 "Do not know where to split");
1485 // Split each outcoming edges.
1486 MachineBasicBlock &Src = *MI.getParent();
1487 for (auto &Succ : Src.successors())
1488 addInsertPoint(MBB&: Src, Beginning: Succ);
1489 }
1490}
1491
1492void RegBankSelectImpl::RepairingPlacement::addInsertPoint(MachineInstr &MI,
1493 bool Before) {
1494 addInsertPoint(Point&: *new InstrInsertPoint(MI, Before));
1495}
1496
1497void RegBankSelectImpl::RepairingPlacement::addInsertPoint(
1498 MachineBasicBlock &MBB, bool Beginning) {
1499 addInsertPoint(Point&: *new MBBInsertPoint(MBB, Beginning));
1500}
1501
1502void RegBankSelectImpl::RepairingPlacement::addInsertPoint(
1503 MachineBasicBlock &Src, MachineBasicBlock &Dst) {
1504 addInsertPoint(Point&: *new EdgeInsertPoint(Src, Dst, P, MFAM));
1505}
1506
1507void RegBankSelectImpl::RepairingPlacement::addInsertPoint(
1508 RegBankSelectImpl::InsertPoint &Point) {
1509 CanMaterialize &= Point.canMaterialize();
1510 HasSplit |= Point.isSplit();
1511 InsertPoints.emplace_back(Args: &Point);
1512}
1513
1514RegBankSelectImpl::InstrInsertPoint::InstrInsertPoint(MachineInstr &Instr,
1515 bool Before)
1516 : Instr(Instr), Before(Before) {
1517 // Since we do not support splitting, we do not need to update
1518 // liveness and such, so do not do anything with P.
1519 assert((!Before || !Instr.isPHI()) &&
1520 "Splitting before phis requires more points");
1521 assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) &&
1522 "Splitting between phis does not make sense");
1523}
1524
1525void RegBankSelectImpl::InstrInsertPoint::materialize() {
1526 if (isSplit()) {
1527 // Slice and return the beginning of the new block.
1528 // If we need to split between the terminators, we theoritically
1529 // need to know where the first and second set of terminators end
1530 // to update the successors properly.
1531 // Now, in pratice, we should have a maximum of 2 branch
1532 // instructions; one conditional and one unconditional. Therefore
1533 // we know how to update the successor by looking at the target of
1534 // the unconditional branch.
1535 // If we end up splitting at some point, then, we should update
1536 // the liveness information and such. I.e., we would need to
1537 // access P here.
1538 // The machine verifier should actually make sure such cases
1539 // cannot happen.
1540 llvm_unreachable("Not yet implemented");
1541 }
1542 // Otherwise the insertion point is just the current or next
1543 // instruction depending on Before. I.e., there is nothing to do
1544 // here.
1545}
1546
1547bool RegBankSelectImpl::InstrInsertPoint::isSplit() const {
1548 // If the insertion point is after a terminator, we need to split.
1549 if (!Before)
1550 return Instr.isTerminator();
1551 // If we insert before an instruction that is after a terminator,
1552 // we are still after a terminator.
1553 return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator();
1554}
1555
1556uint64_t RegBankSelectImpl::InstrInsertPoint::frequency(
1557 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
1558 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI) const {
1559 // Even if we need to split, because we insert between terminators,
1560 // this split has actually the same frequency as the instruction.
1561 const MachineBlockFrequencyInfo *MBFI = GetCachedMBFI();
1562 if (!MBFI)
1563 return 1;
1564 return MBFI->getBlockFreq(MBB: Instr.getParent()).getFrequency();
1565}
1566
1567uint64_t RegBankSelectImpl::MBBInsertPoint::frequency(
1568 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
1569 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI) const {
1570 const MachineBlockFrequencyInfo *MBFI = GetCachedMBFI();
1571 if (!MBFI)
1572 return 1;
1573 return MBFI->getBlockFreq(MBB: &MBB).getFrequency();
1574}
1575
1576void RegBankSelectImpl::EdgeInsertPoint::materialize() {
1577 // If we end up repairing twice at the same place before materializing the
1578 // insertion point, we may think we have to split an edge twice.
1579 // We should have a factory for the insert point such that identical points
1580 // are the same instance.
1581 assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) &&
1582 "This point has already been split");
1583 MachineBasicBlock *NewBB = Src.SplitCriticalEdge(Succ: DstOrSplit, P, MFAM);
1584 assert(NewBB && "Invalid call to materialize");
1585 // We reuse the destination block to hold the information of the new block.
1586 DstOrSplit = NewBB;
1587}
1588
1589uint64_t RegBankSelectImpl::EdgeInsertPoint::frequency(
1590 function_ref<MachineBlockFrequencyInfo *()> GetCachedMBFI,
1591 function_ref<MachineBranchProbabilityInfo *()> GetCachedMBPI) const {
1592 const MachineBlockFrequencyInfo *MBFI = GetCachedMBFI();
1593 if (!MBFI)
1594 return 1;
1595 if (WasMaterialized)
1596 return MBFI->getBlockFreq(MBB: DstOrSplit).getFrequency();
1597
1598 const MachineBranchProbabilityInfo *MBPI = GetCachedMBPI();
1599 if (!MBPI)
1600 return 1;
1601 // The basic block will be on the edge.
1602 return (MBFI->getBlockFreq(MBB: &Src) * MBPI->getEdgeProbability(Src: &Src, Dst: DstOrSplit))
1603 .getFrequency();
1604}
1605
1606bool RegBankSelectImpl::EdgeInsertPoint::canMaterialize() const {
1607 // If this is not a critical edge, we should not have used this insert
1608 // point. Indeed, either the successor or the predecessor should
1609 // have do.
1610 assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 &&
1611 "Edge is not critical");
1612 return Src.canSplitCriticalEdge(Succ: DstOrSplit);
1613}
1614
1615RegBankSelectImpl::MappingCost::MappingCost(BlockFrequency LocalFreq)
1616 : LocalFreq(LocalFreq.getFrequency()) {}
1617
1618bool RegBankSelectImpl::MappingCost::addLocalCost(uint64_t Cost) {
1619 // Check if this overflows.
1620 if (LocalCost + Cost < LocalCost) {
1621 saturate();
1622 return true;
1623 }
1624 LocalCost += Cost;
1625 return isSaturated();
1626}
1627
1628bool RegBankSelectImpl::MappingCost::addNonLocalCost(uint64_t Cost) {
1629 // Check if this overflows.
1630 if (NonLocalCost + Cost < NonLocalCost) {
1631 saturate();
1632 return true;
1633 }
1634 NonLocalCost += Cost;
1635 return isSaturated();
1636}
1637
1638bool RegBankSelectImpl::MappingCost::isSaturated() const {
1639 return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX &&
1640 LocalFreq == UINT64_MAX;
1641}
1642
1643void RegBankSelectImpl::MappingCost::saturate() {
1644 *this = ImpossibleCost();
1645 --LocalCost;
1646}
1647
1648RegBankSelectImpl::MappingCost
1649RegBankSelectImpl::MappingCost::ImpossibleCost() {
1650 return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX);
1651}
1652
1653bool RegBankSelectImpl::MappingCost::operator<(const MappingCost &Cost) const {
1654 // Sort out the easy cases.
1655 if (*this == Cost)
1656 return false;
1657 // If one is impossible to realize the other is cheaper unless it is
1658 // impossible as well.
1659 if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost()))
1660 return (*this == ImpossibleCost()) < (Cost == ImpossibleCost());
1661 // If one is saturated the other is cheaper, unless it is saturated
1662 // as well.
1663 if (isSaturated() || Cost.isSaturated())
1664 return isSaturated() < Cost.isSaturated();
1665 // At this point we know both costs hold sensible values.
1666
1667 // If both values have a different base frequency, there is no much
1668 // we can do but to scale everything.
1669 // However, if they have the same base frequency we can avoid making
1670 // complicated computation.
1671 uint64_t ThisLocalAdjust;
1672 uint64_t OtherLocalAdjust;
1673 if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) {
1674
1675 // At this point, we know the local costs are comparable.
1676 // Do the case that do not involve potential overflow first.
1677 if (NonLocalCost == Cost.NonLocalCost)
1678 // Since the non-local costs do not discriminate on the result,
1679 // just compare the local costs.
1680 return LocalCost < Cost.LocalCost;
1681
1682 // The base costs are comparable so we may only keep the relative
1683 // value to increase our chances of avoiding overflows.
1684 ThisLocalAdjust = 0;
1685 OtherLocalAdjust = 0;
1686 if (LocalCost < Cost.LocalCost)
1687 OtherLocalAdjust = Cost.LocalCost - LocalCost;
1688 else
1689 ThisLocalAdjust = LocalCost - Cost.LocalCost;
1690 } else {
1691 ThisLocalAdjust = LocalCost;
1692 OtherLocalAdjust = Cost.LocalCost;
1693 }
1694
1695 // The non-local costs are comparable, just keep the relative value.
1696 uint64_t ThisNonLocalAdjust = 0;
1697 uint64_t OtherNonLocalAdjust = 0;
1698 if (NonLocalCost < Cost.NonLocalCost)
1699 OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost;
1700 else
1701 ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost;
1702 // Scale everything to make them comparable.
1703 uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq;
1704 // Check for overflow on that operation.
1705 bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust ||
1706 ThisScaledCost < LocalFreq);
1707 uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq;
1708 // Check for overflow on the last operation.
1709 bool OtherOverflows =
1710 OtherLocalAdjust &&
1711 (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq);
1712 // Add the non-local costs.
1713 ThisOverflows |= ThisNonLocalAdjust &&
1714 ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust;
1715 ThisScaledCost += ThisNonLocalAdjust;
1716 OtherOverflows |= OtherNonLocalAdjust &&
1717 OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust;
1718 OtherScaledCost += OtherNonLocalAdjust;
1719 // If both overflows, we cannot compare without additional
1720 // precision, e.g., APInt. Just give up on that case.
1721 if (ThisOverflows && OtherOverflows)
1722 return false;
1723 // If one overflows but not the other, we can still compare.
1724 if (ThisOverflows || OtherOverflows)
1725 return ThisOverflows < OtherOverflows;
1726 // Otherwise, just compare the values.
1727 return ThisScaledCost < OtherScaledCost;
1728}
1729
1730bool RegBankSelectImpl::MappingCost::operator==(const MappingCost &Cost) const {
1731 return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost &&
1732 LocalFreq == Cost.LocalFreq;
1733}
1734
1735#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1736LLVM_DUMP_METHOD void RegBankSelectImpl::MappingCost::dump() const {
1737 print(dbgs());
1738 dbgs() << '\n';
1739}
1740#endif
1741
1742void RegBankSelectImpl::MappingCost::print(raw_ostream &OS) const {
1743 if (*this == ImpossibleCost()) {
1744 OS << "impossible";
1745 return;
1746 }
1747 if (isSaturated()) {
1748 OS << "saturated";
1749 return;
1750 }
1751 OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost;
1752}
1753
1754bool RegBankSelectLegacy::runOnMachineFunction(MachineFunction &MF) {
1755 RegBankSelectImpl Impl(OptMode);
1756 return Impl.runOnMachineFunction(
1757 MF, PassRef: this, MFAMRef: nullptr,
1758 GetMBFI: [&]() {
1759 return &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
1760 },
1761 GetMBPI: [&]() {
1762 return &getAnalysis<MachineBranchProbabilityInfoWrapperPass>()
1763 .getMBPI();
1764 },
1765 GetCachedMBFI: [&]() {
1766 return &getAnalysisIfAvailable<MachineBlockFrequencyInfoWrapperPass>()
1767 ->getMBFI();
1768 },
1769 GetCachedMBPI: [&]() {
1770 return &getAnalysisIfAvailable<
1771 MachineBranchProbabilityInfoWrapperPass>()
1772 ->getMBPI();
1773 });
1774}
1775
1776RegBankSelectPass::RegBankSelectPass(RegBankSelectMode RunningMode)
1777 : OptMode(computeOptMode(RequestedMode: RunningMode)) {}
1778
1779PreservedAnalyses RegBankSelectPass::run(MachineFunction &MF,
1780 MachineFunctionAnalysisManager &MFAM) {
1781 MFPropsModifier _(*this, MF);
1782 RegBankSelectImpl Impl(OptMode);
1783 bool Changed = Impl.runOnMachineFunction(
1784 MF, PassRef: nullptr, MFAMRef: &MFAM,
1785 GetMBFI: [&]() { return &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF); },
1786 GetMBPI: [&]() { return &MFAM.getResult<MachineBranchProbabilityAnalysis>(IR&: MF); },
1787 GetCachedMBFI: [&]() { return MFAM.getCachedResult<MachineBlockFrequencyAnalysis>(IR&: MF); },
1788 GetCachedMBPI: [&]() {
1789 return MFAM.getCachedResult<MachineBranchProbabilityAnalysis>(IR&: MF);
1790 });
1791 return Changed ? getMachineFunctionPassPreservedAnalyses()
1792 .preserveSet<CFGAnalyses>()
1793 : PreservedAnalyses::all();
1794}
1795