RegBankSelect.h 25 KB

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