10b57cec5SDimitry Andric //=- llvm/CodeGen/GlobalISel/RegBankSelect.h - Reg Bank Selector --*- C++ -*-=// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 9fe6060f1SDimitry Andric /// \file 10fe6060f1SDimitry Andric /// This file describes the interface of the MachineFunctionPass 110b57cec5SDimitry Andric /// responsible for assigning the generic virtual registers to register bank. 12fe6060f1SDimitry Andric /// 130b57cec5SDimitry Andric /// By default, the reg bank selector relies on local decisions to 140b57cec5SDimitry Andric /// assign the register bank. In other words, it looks at one instruction 150b57cec5SDimitry Andric /// at a time to decide where the operand of that instruction should live. 160b57cec5SDimitry Andric /// 170b57cec5SDimitry Andric /// At higher optimization level, we could imagine that the reg bank selector 180b57cec5SDimitry Andric /// would use more global analysis and do crazier thing like duplicating 190b57cec5SDimitry Andric /// instructions and so on. This is future work. 200b57cec5SDimitry Andric /// 210b57cec5SDimitry Andric /// For now, the pass uses a greedy algorithm to decide where the operand 220b57cec5SDimitry Andric /// of an instruction should live. It asks the target which banks may be 230b57cec5SDimitry Andric /// used for each operand of the instruction and what is the cost. Then, 240b57cec5SDimitry Andric /// it chooses the solution which minimize the cost of the instruction plus 250b57cec5SDimitry Andric /// the cost of any move that may be needed to the values into the right 260b57cec5SDimitry Andric /// register bank. 270b57cec5SDimitry Andric /// In other words, the cost for an instruction on a register bank RegBank 280b57cec5SDimitry Andric /// is: Cost of I on RegBank plus the sum of the cost for bringing the 290b57cec5SDimitry Andric /// input operands from their current register bank to RegBank. 300b57cec5SDimitry Andric /// Thus, the following formula: 310b57cec5SDimitry Andric /// cost(I, RegBank) = cost(I.Opcode, RegBank) + 320b57cec5SDimitry Andric /// sum(for each arg in I.arguments: costCrossCopy(arg.RegBank, RegBank)) 330b57cec5SDimitry Andric /// 340b57cec5SDimitry Andric /// E.g., Let say we are assigning the register bank for the instruction 350b57cec5SDimitry Andric /// defining v2. 360b57cec5SDimitry Andric /// v0(A_REGBANK) = ... 370b57cec5SDimitry Andric /// v1(A_REGBANK) = ... 380b57cec5SDimitry Andric /// v2 = G_ADD i32 v0, v1 <-- MI 390b57cec5SDimitry Andric /// 400b57cec5SDimitry Andric /// The target may say it can generate G_ADD i32 on register bank A and B 410b57cec5SDimitry Andric /// with a cost of respectively 5 and 1. 420b57cec5SDimitry Andric /// Then, let say the cost of a cross register bank copies from A to B is 1. 430b57cec5SDimitry Andric /// The reg bank selector would compare the following two costs: 440b57cec5SDimitry Andric /// cost(MI, A_REGBANK) = cost(G_ADD, A_REGBANK) + cost(v0.RegBank, A_REGBANK) + 450b57cec5SDimitry Andric /// cost(v1.RegBank, A_REGBANK) 460b57cec5SDimitry Andric /// = 5 + cost(A_REGBANK, A_REGBANK) + cost(A_REGBANK, 470b57cec5SDimitry Andric /// A_REGBANK) 480b57cec5SDimitry Andric /// = 5 + 0 + 0 = 5 490b57cec5SDimitry Andric /// cost(MI, B_REGBANK) = cost(G_ADD, B_REGBANK) + cost(v0.RegBank, B_REGBANK) + 500b57cec5SDimitry Andric /// cost(v1.RegBank, B_REGBANK) 510b57cec5SDimitry Andric /// = 1 + cost(A_REGBANK, B_REGBANK) + cost(A_REGBANK, 520b57cec5SDimitry Andric /// B_REGBANK) 530b57cec5SDimitry Andric /// = 1 + 1 + 1 = 3 540b57cec5SDimitry Andric /// Therefore, in this specific example, the reg bank selector would choose 550b57cec5SDimitry Andric /// bank B for MI. 560b57cec5SDimitry Andric /// v0(A_REGBANK) = ... 570b57cec5SDimitry Andric /// v1(A_REGBANK) = ... 580b57cec5SDimitry Andric /// tmp0(B_REGBANK) = COPY v0 590b57cec5SDimitry Andric /// tmp1(B_REGBANK) = COPY v1 600b57cec5SDimitry Andric /// v2(B_REGBANK) = G_ADD i32 tmp0, tmp1 610b57cec5SDimitry Andric // 620b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 630b57cec5SDimitry Andric 640b57cec5SDimitry Andric #ifndef LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H 650b57cec5SDimitry Andric #define LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H 660b57cec5SDimitry Andric 670b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h" 680b57cec5SDimitry Andric #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" 690b57cec5SDimitry Andric #include "llvm/CodeGen/MachineBasicBlock.h" 700b57cec5SDimitry Andric #include "llvm/CodeGen/MachineFunctionPass.h" 710b57cec5SDimitry Andric #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 7281ad6265SDimitry Andric #include "llvm/CodeGen/RegisterBankInfo.h" 730b57cec5SDimitry Andric #include <cassert> 740b57cec5SDimitry Andric #include <cstdint> 750b57cec5SDimitry Andric #include <memory> 760b57cec5SDimitry Andric 770b57cec5SDimitry Andric namespace llvm { 780b57cec5SDimitry Andric 790b57cec5SDimitry Andric class BlockFrequency; 800b57cec5SDimitry Andric class MachineBlockFrequencyInfo; 810b57cec5SDimitry Andric class MachineBranchProbabilityInfo; 820b57cec5SDimitry Andric class MachineOperand; 830b57cec5SDimitry Andric class MachineRegisterInfo; 840b57cec5SDimitry Andric class Pass; 850b57cec5SDimitry Andric class raw_ostream; 860b57cec5SDimitry Andric class TargetPassConfig; 870b57cec5SDimitry Andric class TargetRegisterInfo; 880b57cec5SDimitry Andric 890b57cec5SDimitry Andric /// This pass implements the reg bank selector pass used in the GlobalISel 900b57cec5SDimitry Andric /// pipeline. At the end of this pass, all register operands have been assigned 910b57cec5SDimitry Andric class RegBankSelect : public MachineFunctionPass { 920b57cec5SDimitry Andric public: 930b57cec5SDimitry Andric static char ID; 940b57cec5SDimitry Andric 950b57cec5SDimitry Andric /// List of the modes supported by the RegBankSelect pass. 960b57cec5SDimitry Andric enum Mode { 970b57cec5SDimitry Andric /// Assign the register banks as fast as possible (default). 980b57cec5SDimitry Andric Fast, 990b57cec5SDimitry Andric /// Greedily minimize the cost of assigning register banks. 1000b57cec5SDimitry Andric /// This should produce code of greater quality, but will 1010b57cec5SDimitry Andric /// require more compile time. 1020b57cec5SDimitry Andric Greedy 1030b57cec5SDimitry Andric }; 1040b57cec5SDimitry Andric 1050b57cec5SDimitry Andric /// Abstract class used to represent an insertion point in a CFG. 1060b57cec5SDimitry Andric /// This class records an insertion point and materializes it on 1070b57cec5SDimitry Andric /// demand. 1080b57cec5SDimitry Andric /// It allows to reason about the frequency of this insertion point, 1090b57cec5SDimitry Andric /// without having to logically materialize it (e.g., on an edge), 1100b57cec5SDimitry Andric /// before we actually need to insert something. 1110b57cec5SDimitry Andric class InsertPoint { 1120b57cec5SDimitry Andric protected: 1130b57cec5SDimitry Andric /// Tell if the insert point has already been materialized. 1140b57cec5SDimitry Andric bool WasMaterialized = false; 1150b57cec5SDimitry Andric 1160b57cec5SDimitry Andric /// Materialize the insertion point. 1170b57cec5SDimitry Andric /// 1180b57cec5SDimitry Andric /// If isSplit() is true, this involves actually splitting 1190b57cec5SDimitry Andric /// the block or edge. 1200b57cec5SDimitry Andric /// 1210b57cec5SDimitry Andric /// \post getPointImpl() returns a valid iterator. 1220b57cec5SDimitry Andric /// \post getInsertMBBImpl() returns a valid basic block. 1230b57cec5SDimitry Andric /// \post isSplit() == false ; no more splitting should be required. 1240b57cec5SDimitry Andric virtual void materialize() = 0; 1250b57cec5SDimitry Andric 1260b57cec5SDimitry Andric /// Return the materialized insertion basic block. 1270b57cec5SDimitry Andric /// Code will be inserted into that basic block. 1280b57cec5SDimitry Andric /// 1290b57cec5SDimitry Andric /// \pre ::materialize has been called. 1300b57cec5SDimitry Andric virtual MachineBasicBlock &getInsertMBBImpl() = 0; 1310b57cec5SDimitry Andric 1320b57cec5SDimitry Andric /// Return the materialized insertion point. 1330b57cec5SDimitry Andric /// Code will be inserted before that point. 1340b57cec5SDimitry Andric /// 1350b57cec5SDimitry Andric /// \pre ::materialize has been called. 1360b57cec5SDimitry Andric virtual MachineBasicBlock::iterator getPointImpl() = 0; 1370b57cec5SDimitry Andric 1380b57cec5SDimitry Andric public: 1390b57cec5SDimitry Andric virtual ~InsertPoint() = default; 1400b57cec5SDimitry Andric 1410b57cec5SDimitry Andric /// The first call to this method will cause the splitting to 1420b57cec5SDimitry Andric /// happen if need be, then sub sequent calls just return 1430b57cec5SDimitry Andric /// the iterator to that point. I.e., no more splitting will 1440b57cec5SDimitry Andric /// occur. 1450b57cec5SDimitry Andric /// 1460b57cec5SDimitry Andric /// \return The iterator that should be used with 1470b57cec5SDimitry Andric /// MachineBasicBlock::insert. I.e., additional code happens 1480b57cec5SDimitry Andric /// before that point. getPoint()1490b57cec5SDimitry Andric MachineBasicBlock::iterator getPoint() { 1500b57cec5SDimitry Andric if (!WasMaterialized) { 1510b57cec5SDimitry Andric WasMaterialized = true; 1520b57cec5SDimitry Andric assert(canMaterialize() && "Impossible to materialize this point"); 1530b57cec5SDimitry Andric materialize(); 1540b57cec5SDimitry Andric } 1550b57cec5SDimitry Andric // When we materialized the point we should have done the splitting. 1560b57cec5SDimitry Andric assert(!isSplit() && "Wrong pre-condition"); 1570b57cec5SDimitry Andric return getPointImpl(); 1580b57cec5SDimitry Andric } 1590b57cec5SDimitry Andric 1600b57cec5SDimitry Andric /// The first call to this method will cause the splitting to 1610b57cec5SDimitry Andric /// happen if need be, then sub sequent calls just return 1620b57cec5SDimitry Andric /// the basic block that contains the insertion point. 1630b57cec5SDimitry Andric /// I.e., no more splitting will occur. 1640b57cec5SDimitry Andric /// 1650b57cec5SDimitry Andric /// \return The basic block should be used with 1660b57cec5SDimitry Andric /// MachineBasicBlock::insert and ::getPoint. The new code should 1670b57cec5SDimitry Andric /// happen before that point. getInsertMBB()1680b57cec5SDimitry Andric MachineBasicBlock &getInsertMBB() { 1690b57cec5SDimitry Andric if (!WasMaterialized) { 1700b57cec5SDimitry Andric WasMaterialized = true; 1710b57cec5SDimitry Andric assert(canMaterialize() && "Impossible to materialize this point"); 1720b57cec5SDimitry Andric materialize(); 1730b57cec5SDimitry Andric } 1740b57cec5SDimitry Andric // When we materialized the point we should have done the splitting. 1750b57cec5SDimitry Andric assert(!isSplit() && "Wrong pre-condition"); 1760b57cec5SDimitry Andric return getInsertMBBImpl(); 1770b57cec5SDimitry Andric } 1780b57cec5SDimitry Andric 1790b57cec5SDimitry Andric /// Insert \p MI in the just before ::getPoint() insert(MachineInstr & MI)1800b57cec5SDimitry Andric MachineBasicBlock::iterator insert(MachineInstr &MI) { 1810b57cec5SDimitry Andric return getInsertMBB().insert(getPoint(), &MI); 1820b57cec5SDimitry Andric } 1830b57cec5SDimitry Andric 1840b57cec5SDimitry Andric /// Does this point involve splitting an edge or block? 1850b57cec5SDimitry Andric /// As soon as ::getPoint is called and thus, the point 1860b57cec5SDimitry Andric /// materialized, the point will not require splitting anymore, 1870b57cec5SDimitry Andric /// i.e., this will return false. isSplit()1880b57cec5SDimitry Andric virtual bool isSplit() const { return false; } 1890b57cec5SDimitry Andric 1900b57cec5SDimitry Andric /// Frequency of the insertion point. 1910b57cec5SDimitry Andric /// \p P is used to access the various analysis that will help to 1920b57cec5SDimitry Andric /// get that information, like MachineBlockFrequencyInfo. If \p P 1935f757f3fSDimitry Andric /// does not contain enough to return the actual frequency, 1940b57cec5SDimitry Andric /// this returns 1. frequency(const Pass & P)1950b57cec5SDimitry Andric virtual uint64_t frequency(const Pass &P) const { return 1; } 1960b57cec5SDimitry Andric 1970b57cec5SDimitry Andric /// Check whether this insertion point can be materialized. 1980b57cec5SDimitry Andric /// As soon as ::getPoint is called and thus, the point materialized 1990b57cec5SDimitry Andric /// calling this method does not make sense. canMaterialize()2000b57cec5SDimitry Andric virtual bool canMaterialize() const { return false; } 2010b57cec5SDimitry Andric }; 2020b57cec5SDimitry Andric 2030b57cec5SDimitry Andric /// Insertion point before or after an instruction. 2040b57cec5SDimitry Andric class InstrInsertPoint : public InsertPoint { 2050b57cec5SDimitry Andric private: 2060b57cec5SDimitry Andric /// Insertion point. 2070b57cec5SDimitry Andric MachineInstr &Instr; 2080b57cec5SDimitry Andric 2090b57cec5SDimitry Andric /// Does the insertion point is before or after Instr. 2100b57cec5SDimitry Andric bool Before; 2110b57cec5SDimitry Andric 2120b57cec5SDimitry Andric void materialize() override; 2130b57cec5SDimitry Andric getPointImpl()2140b57cec5SDimitry Andric MachineBasicBlock::iterator getPointImpl() override { 2150b57cec5SDimitry Andric if (Before) 2160b57cec5SDimitry Andric return Instr; 2170b57cec5SDimitry Andric return Instr.getNextNode() ? *Instr.getNextNode() 2180b57cec5SDimitry Andric : Instr.getParent()->end(); 2190b57cec5SDimitry Andric } 2200b57cec5SDimitry Andric getInsertMBBImpl()2210b57cec5SDimitry Andric MachineBasicBlock &getInsertMBBImpl() override { 2220b57cec5SDimitry Andric return *Instr.getParent(); 2230b57cec5SDimitry Andric } 2240b57cec5SDimitry Andric 2250b57cec5SDimitry Andric public: 2260b57cec5SDimitry Andric /// Create an insertion point before (\p Before=true) or after \p Instr. 2270b57cec5SDimitry Andric InstrInsertPoint(MachineInstr &Instr, bool Before = true); 2280b57cec5SDimitry Andric 2290b57cec5SDimitry Andric bool isSplit() const override; 2300b57cec5SDimitry Andric uint64_t frequency(const Pass &P) const override; 2310b57cec5SDimitry Andric 2320b57cec5SDimitry Andric // Worst case, we need to slice the basic block, but that is still doable. canMaterialize()2330b57cec5SDimitry Andric bool canMaterialize() const override { return true; } 2340b57cec5SDimitry Andric }; 2350b57cec5SDimitry Andric 2360b57cec5SDimitry Andric /// Insertion point at the beginning or end of a basic block. 2370b57cec5SDimitry Andric class MBBInsertPoint : public InsertPoint { 2380b57cec5SDimitry Andric private: 2390b57cec5SDimitry Andric /// Insertion point. 2400b57cec5SDimitry Andric MachineBasicBlock &MBB; 2410b57cec5SDimitry Andric 2420b57cec5SDimitry Andric /// Does the insertion point is at the beginning or end of MBB. 2430b57cec5SDimitry Andric bool Beginning; 2440b57cec5SDimitry Andric materialize()2450b57cec5SDimitry Andric void materialize() override { /*Nothing to do to materialize*/ 2460b57cec5SDimitry Andric } 2470b57cec5SDimitry Andric getPointImpl()2480b57cec5SDimitry Andric MachineBasicBlock::iterator getPointImpl() override { 2490b57cec5SDimitry Andric return Beginning ? MBB.begin() : MBB.end(); 2500b57cec5SDimitry Andric } 2510b57cec5SDimitry Andric getInsertMBBImpl()2520b57cec5SDimitry Andric MachineBasicBlock &getInsertMBBImpl() override { return MBB; } 2530b57cec5SDimitry Andric 2540b57cec5SDimitry Andric public: 2550b57cec5SDimitry Andric MBBInsertPoint(MachineBasicBlock &MBB, bool Beginning = true) MBB(MBB)25604eeddc0SDimitry Andric : MBB(MBB), Beginning(Beginning) { 2570b57cec5SDimitry Andric // If we try to insert before phis, we should use the insertion 2580b57cec5SDimitry Andric // points on the incoming edges. 2590b57cec5SDimitry Andric assert((!Beginning || MBB.getFirstNonPHI() == MBB.begin()) && 2600b57cec5SDimitry Andric "Invalid beginning point"); 2610b57cec5SDimitry Andric // If we try to insert after the terminators, we should use the 2620b57cec5SDimitry Andric // points on the outcoming edges. 2630b57cec5SDimitry Andric assert((Beginning || MBB.getFirstTerminator() == MBB.end()) && 2640b57cec5SDimitry Andric "Invalid end point"); 2650b57cec5SDimitry Andric } 2660b57cec5SDimitry Andric isSplit()2670b57cec5SDimitry Andric bool isSplit() const override { return false; } 2680b57cec5SDimitry Andric uint64_t frequency(const Pass &P) const override; canMaterialize()2690b57cec5SDimitry Andric bool canMaterialize() const override { return true; }; 2700b57cec5SDimitry Andric }; 2710b57cec5SDimitry Andric 2720b57cec5SDimitry Andric /// Insertion point on an edge. 2730b57cec5SDimitry Andric class EdgeInsertPoint : public InsertPoint { 2740b57cec5SDimitry Andric private: 2750b57cec5SDimitry Andric /// Source of the edge. 2760b57cec5SDimitry Andric MachineBasicBlock &Src; 2770b57cec5SDimitry Andric 2780b57cec5SDimitry Andric /// Destination of the edge. 2790b57cec5SDimitry Andric /// After the materialization is done, this hold the basic block 2800b57cec5SDimitry Andric /// that resulted from the splitting. 2810b57cec5SDimitry Andric MachineBasicBlock *DstOrSplit; 2820b57cec5SDimitry Andric 2830b57cec5SDimitry Andric /// P is used to update the analysis passes as applicable. 2840b57cec5SDimitry Andric Pass &P; 2850b57cec5SDimitry Andric 2860b57cec5SDimitry Andric void materialize() override; 2870b57cec5SDimitry Andric getPointImpl()2880b57cec5SDimitry Andric MachineBasicBlock::iterator getPointImpl() override { 2890b57cec5SDimitry Andric // DstOrSplit should be the Split block at this point. 2900b57cec5SDimitry Andric // I.e., it should have one predecessor, Src, and one successor, 2910b57cec5SDimitry Andric // the original Dst. 2920b57cec5SDimitry Andric assert(DstOrSplit && DstOrSplit->isPredecessor(&Src) && 2930b57cec5SDimitry Andric DstOrSplit->pred_size() == 1 && DstOrSplit->succ_size() == 1 && 2940b57cec5SDimitry Andric "Did not split?!"); 2950b57cec5SDimitry Andric return DstOrSplit->begin(); 2960b57cec5SDimitry Andric } 2970b57cec5SDimitry Andric getInsertMBBImpl()2980b57cec5SDimitry Andric MachineBasicBlock &getInsertMBBImpl() override { return *DstOrSplit; } 2990b57cec5SDimitry Andric 3000b57cec5SDimitry Andric public: EdgeInsertPoint(MachineBasicBlock & Src,MachineBasicBlock & Dst,Pass & P)3010b57cec5SDimitry Andric EdgeInsertPoint(MachineBasicBlock &Src, MachineBasicBlock &Dst, Pass &P) 30204eeddc0SDimitry Andric : Src(Src), DstOrSplit(&Dst), P(P) {} 3030b57cec5SDimitry Andric isSplit()3040b57cec5SDimitry Andric bool isSplit() const override { 3050b57cec5SDimitry Andric return Src.succ_size() > 1 && DstOrSplit->pred_size() > 1; 3060b57cec5SDimitry Andric } 3070b57cec5SDimitry Andric 3080b57cec5SDimitry Andric uint64_t frequency(const Pass &P) const override; 3090b57cec5SDimitry Andric bool canMaterialize() const override; 3100b57cec5SDimitry Andric }; 3110b57cec5SDimitry Andric 3120b57cec5SDimitry Andric /// Struct used to represent the placement of a repairing point for 3130b57cec5SDimitry Andric /// a given operand. 3140b57cec5SDimitry Andric class RepairingPlacement { 3150b57cec5SDimitry Andric public: 3160b57cec5SDimitry Andric /// Define the kind of action this repairing needs. 3170b57cec5SDimitry Andric enum RepairingKind { 3180b57cec5SDimitry Andric /// Nothing to repair, just drop this action. 3190b57cec5SDimitry Andric None, 3200b57cec5SDimitry Andric /// Reparing code needs to happen before InsertPoints. 3210b57cec5SDimitry Andric Insert, 3220b57cec5SDimitry Andric /// (Re)assign the register bank of the operand. 3230b57cec5SDimitry Andric Reassign, 3240b57cec5SDimitry Andric /// Mark this repairing placement as impossible. 3250b57cec5SDimitry Andric Impossible 3260b57cec5SDimitry Andric }; 3270b57cec5SDimitry Andric 3280b57cec5SDimitry Andric /// \name Convenient types for a list of insertion points. 3290b57cec5SDimitry Andric /// @{ 3300b57cec5SDimitry Andric using InsertionPoints = SmallVector<std::unique_ptr<InsertPoint>, 2>; 3310b57cec5SDimitry Andric using insertpt_iterator = InsertionPoints::iterator; 3320b57cec5SDimitry Andric using const_insertpt_iterator = InsertionPoints::const_iterator; 3330b57cec5SDimitry Andric /// @} 3340b57cec5SDimitry Andric 3350b57cec5SDimitry Andric private: 3360b57cec5SDimitry Andric /// Kind of repairing. 3370b57cec5SDimitry Andric RepairingKind Kind; 3380b57cec5SDimitry Andric /// Index of the operand that will be repaired. 3390b57cec5SDimitry Andric unsigned OpIdx; 3400b57cec5SDimitry Andric /// Are all the insert points materializeable? 3410b57cec5SDimitry Andric bool CanMaterialize; 3420b57cec5SDimitry Andric /// Is there any of the insert points needing splitting? 3430b57cec5SDimitry Andric bool HasSplit = false; 3440b57cec5SDimitry Andric /// Insertion point for the repair code. 3450b57cec5SDimitry Andric /// The repairing code needs to happen just before these points. 3460b57cec5SDimitry Andric InsertionPoints InsertPoints; 3470b57cec5SDimitry Andric /// Some insertion points may need to update the liveness and such. 3480b57cec5SDimitry Andric Pass &P; 3490b57cec5SDimitry Andric 3500b57cec5SDimitry Andric public: 3510b57cec5SDimitry Andric /// Create a repairing placement for the \p OpIdx-th operand of 3520b57cec5SDimitry Andric /// \p MI. \p TRI is used to make some checks on the register aliases 3530b57cec5SDimitry Andric /// if the machine operand is a physical register. \p P is used to 3540b57cec5SDimitry Andric /// to update liveness information and such when materializing the 3550b57cec5SDimitry Andric /// points. 3560b57cec5SDimitry Andric RepairingPlacement(MachineInstr &MI, unsigned OpIdx, 3570b57cec5SDimitry Andric const TargetRegisterInfo &TRI, Pass &P, 3580b57cec5SDimitry Andric RepairingKind Kind = RepairingKind::Insert); 3590b57cec5SDimitry Andric 3600b57cec5SDimitry Andric /// \name Getters. 3610b57cec5SDimitry Andric /// @{ getKind()3620b57cec5SDimitry Andric RepairingKind getKind() const { return Kind; } getOpIdx()3630b57cec5SDimitry Andric unsigned getOpIdx() const { return OpIdx; } canMaterialize()3640b57cec5SDimitry Andric bool canMaterialize() const { return CanMaterialize; } hasSplit()3650b57cec5SDimitry Andric bool hasSplit() { return HasSplit; } 3660b57cec5SDimitry Andric /// @} 3670b57cec5SDimitry Andric 3680b57cec5SDimitry Andric /// \name Overloaded methods to add an insertion point. 3690b57cec5SDimitry Andric /// @{ 3700b57cec5SDimitry Andric /// Add a MBBInsertionPoint to the list of InsertPoints. 3710b57cec5SDimitry Andric void addInsertPoint(MachineBasicBlock &MBB, bool Beginning); 3720b57cec5SDimitry Andric /// Add a InstrInsertionPoint to the list of InsertPoints. 3730b57cec5SDimitry Andric void addInsertPoint(MachineInstr &MI, bool Before); 3740b57cec5SDimitry Andric /// Add an EdgeInsertionPoint (\p Src, \p Dst) to the list of InsertPoints. 3750b57cec5SDimitry Andric void addInsertPoint(MachineBasicBlock &Src, MachineBasicBlock &Dst); 3760b57cec5SDimitry Andric /// Add an InsertPoint to the list of insert points. 3770b57cec5SDimitry Andric /// This method takes the ownership of &\p Point. 3780b57cec5SDimitry Andric void addInsertPoint(InsertPoint &Point); 3790b57cec5SDimitry Andric /// @} 3800b57cec5SDimitry Andric 3810b57cec5SDimitry Andric /// \name Accessors related to the insertion points. 3820b57cec5SDimitry Andric /// @{ begin()3830b57cec5SDimitry Andric insertpt_iterator begin() { return InsertPoints.begin(); } end()3840b57cec5SDimitry Andric insertpt_iterator end() { return InsertPoints.end(); } 3850b57cec5SDimitry Andric begin()3860b57cec5SDimitry Andric const_insertpt_iterator begin() const { return InsertPoints.begin(); } end()3870b57cec5SDimitry Andric const_insertpt_iterator end() const { return InsertPoints.end(); } 3880b57cec5SDimitry Andric getNumInsertPoints()3890b57cec5SDimitry Andric unsigned getNumInsertPoints() const { return InsertPoints.size(); } 3900b57cec5SDimitry Andric /// @} 3910b57cec5SDimitry Andric 3920b57cec5SDimitry Andric /// Change the type of this repairing placement to \p NewKind. 3930b57cec5SDimitry Andric /// It is not possible to switch a repairing placement to the 3940b57cec5SDimitry Andric /// RepairingKind::Insert. There is no fundamental problem with 3950b57cec5SDimitry Andric /// that, but no uses as well, so do not support it for now. 3960b57cec5SDimitry Andric /// 3970b57cec5SDimitry Andric /// \pre NewKind != RepairingKind::Insert 3980b57cec5SDimitry Andric /// \post getKind() == NewKind switchTo(RepairingKind NewKind)3990b57cec5SDimitry Andric void switchTo(RepairingKind NewKind) { 4000b57cec5SDimitry Andric assert(NewKind != Kind && "Already of the right Kind"); 4010b57cec5SDimitry Andric Kind = NewKind; 4020b57cec5SDimitry Andric InsertPoints.clear(); 4030b57cec5SDimitry Andric CanMaterialize = NewKind != RepairingKind::Impossible; 4040b57cec5SDimitry Andric HasSplit = false; 4050b57cec5SDimitry Andric assert(NewKind != RepairingKind::Insert && 4060b57cec5SDimitry Andric "We would need more MI to switch to Insert"); 4070b57cec5SDimitry Andric } 4080b57cec5SDimitry Andric }; 4090b57cec5SDimitry Andric 410bdd1243dSDimitry Andric protected: 4110b57cec5SDimitry Andric /// Helper class used to represent the cost for mapping an instruction. 4120b57cec5SDimitry Andric /// When mapping an instruction, we may introduce some repairing code. 4130b57cec5SDimitry Andric /// In most cases, the repairing code is local to the instruction, 4140b57cec5SDimitry Andric /// thus, we can omit the basic block frequency from the cost. 4150b57cec5SDimitry Andric /// However, some alternatives may produce non-local cost, e.g., when 4160b57cec5SDimitry Andric /// repairing a phi, and thus we then need to scale the local cost 4170b57cec5SDimitry Andric /// to the non-local cost. This class does this for us. 4180b57cec5SDimitry Andric /// \note: We could simply always scale the cost. The problem is that 4190b57cec5SDimitry Andric /// there are higher chances that we saturate the cost easier and end 4200b57cec5SDimitry Andric /// up having the same cost for actually different alternatives. 4210b57cec5SDimitry Andric /// Another option would be to use APInt everywhere. 4220b57cec5SDimitry Andric class MappingCost { 4230b57cec5SDimitry Andric private: 4240b57cec5SDimitry Andric /// Cost of the local instructions. 4250b57cec5SDimitry Andric /// This cost is free of basic block frequency. 4260b57cec5SDimitry Andric uint64_t LocalCost = 0; 4270b57cec5SDimitry Andric /// Cost of the non-local instructions. 4280b57cec5SDimitry Andric /// This cost should include the frequency of the related blocks. 4290b57cec5SDimitry Andric uint64_t NonLocalCost = 0; 4300b57cec5SDimitry Andric /// Frequency of the block where the local instructions live. 4310b57cec5SDimitry Andric uint64_t LocalFreq; 4320b57cec5SDimitry Andric MappingCost(uint64_t LocalCost,uint64_t NonLocalCost,uint64_t LocalFreq)4330b57cec5SDimitry Andric MappingCost(uint64_t LocalCost, uint64_t NonLocalCost, uint64_t LocalFreq) 4340b57cec5SDimitry Andric : LocalCost(LocalCost), NonLocalCost(NonLocalCost), 4350b57cec5SDimitry Andric LocalFreq(LocalFreq) {} 4360b57cec5SDimitry Andric 4370b57cec5SDimitry Andric /// Check if this cost is saturated. 4380b57cec5SDimitry Andric bool isSaturated() const; 4390b57cec5SDimitry Andric 4400b57cec5SDimitry Andric public: 4410b57cec5SDimitry Andric /// Create a MappingCost assuming that most of the instructions 4420b57cec5SDimitry Andric /// will occur in a basic block with \p LocalFreq frequency. 4435f757f3fSDimitry Andric MappingCost(BlockFrequency LocalFreq); 4440b57cec5SDimitry Andric 4450b57cec5SDimitry Andric /// Add \p Cost to the local cost. 4460b57cec5SDimitry Andric /// \return true if this cost is saturated, false otherwise. 4470b57cec5SDimitry Andric bool addLocalCost(uint64_t Cost); 4480b57cec5SDimitry Andric 4490b57cec5SDimitry Andric /// Add \p Cost to the non-local cost. 4500b57cec5SDimitry Andric /// Non-local cost should reflect the frequency of their placement. 4510b57cec5SDimitry Andric /// \return true if this cost is saturated, false otherwise. 4520b57cec5SDimitry Andric bool addNonLocalCost(uint64_t Cost); 4530b57cec5SDimitry Andric 4540b57cec5SDimitry Andric /// Saturate the cost to the maximal representable value. 4550b57cec5SDimitry Andric void saturate(); 4560b57cec5SDimitry Andric 4570b57cec5SDimitry Andric /// Return an instance of MappingCost that represents an 4580b57cec5SDimitry Andric /// impossible mapping. 4590b57cec5SDimitry Andric static MappingCost ImpossibleCost(); 4600b57cec5SDimitry Andric 4610b57cec5SDimitry Andric /// Check if this is less than \p Cost. 4620b57cec5SDimitry Andric bool operator<(const MappingCost &Cost) const; 4630b57cec5SDimitry Andric /// Check if this is equal to \p Cost. 4640b57cec5SDimitry Andric bool operator==(const MappingCost &Cost) const; 4650b57cec5SDimitry Andric /// Check if this is not equal to \p Cost. 4660b57cec5SDimitry Andric bool operator!=(const MappingCost &Cost) const { return !(*this == Cost); } 4670b57cec5SDimitry Andric /// Check if this is greater than \p Cost. 4680b57cec5SDimitry Andric bool operator>(const MappingCost &Cost) const { 4690b57cec5SDimitry Andric return *this != Cost && Cost < *this; 4700b57cec5SDimitry Andric } 4710b57cec5SDimitry Andric 4720b57cec5SDimitry Andric /// Print this on dbgs() stream. 4730b57cec5SDimitry Andric void dump() const; 4740b57cec5SDimitry Andric 4750b57cec5SDimitry Andric /// Print this on \p OS; 4760b57cec5SDimitry Andric void print(raw_ostream &OS) const; 4770b57cec5SDimitry Andric 4780b57cec5SDimitry Andric /// Overload the stream operator for easy debug printing. 4790b57cec5SDimitry Andric friend raw_ostream &operator<<(raw_ostream &OS, const MappingCost &Cost) { 4800b57cec5SDimitry Andric Cost.print(OS); 4810b57cec5SDimitry Andric return OS; 4820b57cec5SDimitry Andric } 4830b57cec5SDimitry Andric }; 4840b57cec5SDimitry Andric 4850b57cec5SDimitry Andric /// Interface to the target lowering info related 4860b57cec5SDimitry Andric /// to register banks. 4870b57cec5SDimitry Andric const RegisterBankInfo *RBI = nullptr; 4880b57cec5SDimitry Andric 4890b57cec5SDimitry Andric /// MRI contains all the register class/bank information that this 4900b57cec5SDimitry Andric /// pass uses and updates. 4910b57cec5SDimitry Andric MachineRegisterInfo *MRI = nullptr; 4920b57cec5SDimitry Andric 4930b57cec5SDimitry Andric /// Information on the register classes for the current function. 4940b57cec5SDimitry Andric const TargetRegisterInfo *TRI = nullptr; 4950b57cec5SDimitry Andric 4960b57cec5SDimitry Andric /// Get the frequency of blocks. 4970b57cec5SDimitry Andric /// This is required for non-fast mode. 4980b57cec5SDimitry Andric MachineBlockFrequencyInfo *MBFI = nullptr; 4990b57cec5SDimitry Andric 5000b57cec5SDimitry Andric /// Get the frequency of the edges. 5010b57cec5SDimitry Andric /// This is required for non-fast mode. 5020b57cec5SDimitry Andric MachineBranchProbabilityInfo *MBPI = nullptr; 5030b57cec5SDimitry Andric 5040b57cec5SDimitry Andric /// Current optimization remark emitter. Used to report failures. 5050b57cec5SDimitry Andric std::unique_ptr<MachineOptimizationRemarkEmitter> MORE; 5060b57cec5SDimitry Andric 5070b57cec5SDimitry Andric /// Helper class used for every code morphing. 5080b57cec5SDimitry Andric MachineIRBuilder MIRBuilder; 5090b57cec5SDimitry Andric 5100b57cec5SDimitry Andric /// Optimization mode of the pass. 5110b57cec5SDimitry Andric Mode OptMode; 5120b57cec5SDimitry Andric 5130b57cec5SDimitry Andric /// Current target configuration. Controls how the pass handles errors. 5140b57cec5SDimitry Andric const TargetPassConfig *TPC; 5150b57cec5SDimitry Andric 5160b57cec5SDimitry Andric /// Assign the register bank of each operand of \p MI. 5170b57cec5SDimitry Andric /// \return True on success, false otherwise. 5180b57cec5SDimitry Andric bool assignInstr(MachineInstr &MI); 5190b57cec5SDimitry Andric 5200b57cec5SDimitry Andric /// Initialize the field members using \p MF. 5210b57cec5SDimitry Andric void init(MachineFunction &MF); 5220b57cec5SDimitry Andric 5230b57cec5SDimitry Andric /// Check if \p Reg is already assigned what is described by \p ValMapping. 5240b57cec5SDimitry Andric /// \p OnlyAssign == true means that \p Reg just needs to be assigned a 5250b57cec5SDimitry Andric /// register bank. I.e., no repairing is necessary to have the 5260b57cec5SDimitry Andric /// assignment match. 5270b57cec5SDimitry Andric bool assignmentMatch(Register Reg, 5280b57cec5SDimitry Andric const RegisterBankInfo::ValueMapping &ValMapping, 5290b57cec5SDimitry Andric bool &OnlyAssign) const; 5300b57cec5SDimitry Andric 5310b57cec5SDimitry Andric /// Insert repairing code for \p Reg as specified by \p ValMapping. 5320b57cec5SDimitry Andric /// The repairing placement is specified by \p RepairPt. 5330b57cec5SDimitry Andric /// \p NewVRegs contains all the registers required to remap \p Reg. 5340b57cec5SDimitry Andric /// In other words, the number of registers in NewVRegs must be equal 5350b57cec5SDimitry Andric /// to ValMapping.BreakDown.size(). 5360b57cec5SDimitry Andric /// 5370b57cec5SDimitry Andric /// The transformation could be sketched as: 5380b57cec5SDimitry Andric /// \code 5390b57cec5SDimitry Andric /// ... = op Reg 5400b57cec5SDimitry Andric /// \endcode 5410b57cec5SDimitry Andric /// Becomes 5420b57cec5SDimitry Andric /// \code 5430b57cec5SDimitry Andric /// <NewRegs> = COPY or extract Reg 5440b57cec5SDimitry Andric /// ... = op Reg 5450b57cec5SDimitry Andric /// \endcode 5460b57cec5SDimitry Andric /// 5470b57cec5SDimitry Andric /// and 5480b57cec5SDimitry Andric /// \code 5490b57cec5SDimitry Andric /// Reg = op ... 5500b57cec5SDimitry Andric /// \endcode 5510b57cec5SDimitry Andric /// Becomes 5520b57cec5SDimitry Andric /// \code 5530b57cec5SDimitry Andric /// Reg = op ... 5540b57cec5SDimitry Andric /// Reg = COPY or build_sequence <NewRegs> 5550b57cec5SDimitry Andric /// \endcode 5560b57cec5SDimitry Andric /// 5570b57cec5SDimitry Andric /// \pre NewVRegs.size() == ValMapping.BreakDown.size() 5580b57cec5SDimitry Andric /// 5590b57cec5SDimitry Andric /// \note The caller is supposed to do the rewriting of op if need be. 5600b57cec5SDimitry Andric /// I.e., Reg = op ... => <NewRegs> = NewOp ... 5610b57cec5SDimitry Andric /// 5620b57cec5SDimitry Andric /// \return True if the repairing worked, false otherwise. 5630b57cec5SDimitry Andric bool repairReg(MachineOperand &MO, 5640b57cec5SDimitry Andric const RegisterBankInfo::ValueMapping &ValMapping, 5650b57cec5SDimitry Andric RegBankSelect::RepairingPlacement &RepairPt, 5660b57cec5SDimitry Andric const iterator_range<SmallVectorImpl<Register>::const_iterator> 5670b57cec5SDimitry Andric &NewVRegs); 5680b57cec5SDimitry Andric 5690b57cec5SDimitry Andric /// Return the cost of the instruction needed to map \p MO to \p ValMapping. 5700b57cec5SDimitry Andric /// The cost is free of basic block frequencies. 5710b57cec5SDimitry Andric /// \pre MO.isReg() 5720b57cec5SDimitry Andric /// \pre MO is assigned to a register bank. 5730b57cec5SDimitry Andric /// \pre ValMapping is a valid mapping for MO. 5740b57cec5SDimitry Andric uint64_t 5750b57cec5SDimitry Andric getRepairCost(const MachineOperand &MO, 5760b57cec5SDimitry Andric const RegisterBankInfo::ValueMapping &ValMapping) const; 5770b57cec5SDimitry Andric 5780b57cec5SDimitry Andric /// Find the best mapping for \p MI from \p PossibleMappings. 5790b57cec5SDimitry Andric /// \return a reference on the best mapping in \p PossibleMappings. 5800b57cec5SDimitry Andric const RegisterBankInfo::InstructionMapping & 5810b57cec5SDimitry Andric findBestMapping(MachineInstr &MI, 5820b57cec5SDimitry Andric RegisterBankInfo::InstructionMappings &PossibleMappings, 5830b57cec5SDimitry Andric SmallVectorImpl<RepairingPlacement> &RepairPts); 5840b57cec5SDimitry Andric 5850b57cec5SDimitry Andric /// Compute the cost of mapping \p MI with \p InstrMapping and 5860b57cec5SDimitry Andric /// compute the repairing placement for such mapping in \p 5870b57cec5SDimitry Andric /// RepairPts. 5880b57cec5SDimitry Andric /// \p BestCost is used to specify when the cost becomes too high 5890b57cec5SDimitry Andric /// and thus it is not worth computing the RepairPts. Moreover if 5900b57cec5SDimitry Andric /// \p BestCost == nullptr, the mapping cost is actually not 5910b57cec5SDimitry Andric /// computed. 5920b57cec5SDimitry Andric MappingCost 5930b57cec5SDimitry Andric computeMapping(MachineInstr &MI, 5940b57cec5SDimitry Andric const RegisterBankInfo::InstructionMapping &InstrMapping, 5950b57cec5SDimitry Andric SmallVectorImpl<RepairingPlacement> &RepairPts, 5960b57cec5SDimitry Andric const MappingCost *BestCost = nullptr); 5970b57cec5SDimitry Andric 5980b57cec5SDimitry Andric /// When \p RepairPt involves splitting to repair \p MO for the 5990b57cec5SDimitry Andric /// given \p ValMapping, try to change the way we repair such that 6000b57cec5SDimitry Andric /// the splitting is not required anymore. 6010b57cec5SDimitry Andric /// 6020b57cec5SDimitry Andric /// \pre \p RepairPt.hasSplit() 6030b57cec5SDimitry Andric /// \pre \p MO == MO.getParent()->getOperand(\p RepairPt.getOpIdx()) 6040b57cec5SDimitry Andric /// \pre \p ValMapping is the mapping of \p MO for MO.getParent() 6050b57cec5SDimitry Andric /// that implied \p RepairPt. 6060b57cec5SDimitry Andric void tryAvoidingSplit(RegBankSelect::RepairingPlacement &RepairPt, 6070b57cec5SDimitry Andric const MachineOperand &MO, 6080b57cec5SDimitry Andric const RegisterBankInfo::ValueMapping &ValMapping) const; 6090b57cec5SDimitry Andric 6100b57cec5SDimitry Andric /// Apply \p Mapping to \p MI. \p RepairPts represents the different 6110b57cec5SDimitry Andric /// mapping action that need to happen for the mapping to be 6120b57cec5SDimitry Andric /// applied. 6130b57cec5SDimitry Andric /// \return True if the mapping was applied sucessfully, false otherwise. 6140b57cec5SDimitry Andric bool applyMapping(MachineInstr &MI, 6150b57cec5SDimitry Andric const RegisterBankInfo::InstructionMapping &InstrMapping, 6160b57cec5SDimitry Andric SmallVectorImpl<RepairingPlacement> &RepairPts); 6170b57cec5SDimitry Andric 6180b57cec5SDimitry Andric public: 6190b57cec5SDimitry Andric /// Create a RegBankSelect pass with the specified \p RunningMode. 62006c3fb27SDimitry Andric RegBankSelect(char &PassID = ID, Mode RunningMode = Fast); 6210b57cec5SDimitry Andric getPassName()6220b57cec5SDimitry Andric StringRef getPassName() const override { return "RegBankSelect"; } 6230b57cec5SDimitry Andric 6240b57cec5SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override; 6250b57cec5SDimitry Andric getRequiredProperties()6260b57cec5SDimitry Andric MachineFunctionProperties getRequiredProperties() const override { 6270b57cec5SDimitry Andric return MachineFunctionProperties() 6280b57cec5SDimitry Andric .set(MachineFunctionProperties::Property::IsSSA) 6290b57cec5SDimitry Andric .set(MachineFunctionProperties::Property::Legalized); 6300b57cec5SDimitry Andric } 6310b57cec5SDimitry Andric getSetProperties()6320b57cec5SDimitry Andric MachineFunctionProperties getSetProperties() const override { 6330b57cec5SDimitry Andric return MachineFunctionProperties().set( 6340b57cec5SDimitry Andric MachineFunctionProperties::Property::RegBankSelected); 6350b57cec5SDimitry Andric } 6360b57cec5SDimitry Andric getClearedProperties()6370b57cec5SDimitry Andric MachineFunctionProperties getClearedProperties() const override { 6380b57cec5SDimitry Andric return MachineFunctionProperties() 6390b57cec5SDimitry Andric .set(MachineFunctionProperties::Property::NoPHIs); 6400b57cec5SDimitry Andric } 6410b57cec5SDimitry Andric 642bdd1243dSDimitry Andric /// Check that our input is fully legal: we require the function to have the 643bdd1243dSDimitry Andric /// Legalized property, so it should be. 644bdd1243dSDimitry Andric /// 645bdd1243dSDimitry Andric /// FIXME: This should be in the MachineVerifier. 646bdd1243dSDimitry Andric bool checkFunctionIsLegal(MachineFunction &MF) const; 647bdd1243dSDimitry Andric 6480b57cec5SDimitry Andric /// Walk through \p MF and assign a register bank to every virtual register 6490b57cec5SDimitry Andric /// that are still mapped to nothing. 6500b57cec5SDimitry Andric /// The target needs to provide a RegisterBankInfo and in particular 6510b57cec5SDimitry Andric /// override RegisterBankInfo::getInstrMapping. 6520b57cec5SDimitry Andric /// 6530b57cec5SDimitry Andric /// Simplified algo: 6540b57cec5SDimitry Andric /// \code 6550b57cec5SDimitry Andric /// RBI = MF.subtarget.getRegBankInfo() 6560b57cec5SDimitry Andric /// MIRBuilder.setMF(MF) 6570b57cec5SDimitry Andric /// for each bb in MF 6580b57cec5SDimitry Andric /// for each inst in bb 6590b57cec5SDimitry Andric /// MIRBuilder.setInstr(inst) 6600b57cec5SDimitry Andric /// MappingCosts = RBI.getMapping(inst); 6610b57cec5SDimitry Andric /// Idx = findIdxOfMinCost(MappingCosts) 6620b57cec5SDimitry Andric /// CurRegBank = MappingCosts[Idx].RegBank 6630b57cec5SDimitry Andric /// MRI.setRegBank(inst.getOperand(0).getReg(), CurRegBank) 6640b57cec5SDimitry Andric /// for each argument in inst 6650b57cec5SDimitry Andric /// if (CurRegBank != argument.RegBank) 6660b57cec5SDimitry Andric /// ArgReg = argument.getReg() 6670b57cec5SDimitry Andric /// Tmp = MRI.createNewVirtual(MRI.getSize(ArgReg), CurRegBank) 6680b57cec5SDimitry Andric /// MIRBuilder.buildInstr(COPY, Tmp, ArgReg) 6690b57cec5SDimitry Andric /// inst.getOperand(argument.getOperandNo()).setReg(Tmp) 6700b57cec5SDimitry Andric /// \endcode 671bdd1243dSDimitry Andric bool assignRegisterBanks(MachineFunction &MF); 672bdd1243dSDimitry Andric 6730b57cec5SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override; 6740b57cec5SDimitry Andric }; 6750b57cec5SDimitry Andric 6760b57cec5SDimitry Andric } // end namespace llvm 6770b57cec5SDimitry Andric 6780b57cec5SDimitry Andric #endif // LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H 679