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