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