1 //==- llvm/CodeGen/AggressiveAntiDepBreaker.h - Anti-Dep Support -*- 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 // This file implements the AggressiveAntiDepBreaker class, which 10 // implements register anti-dependence breaking during post-RA 11 // scheduling. It attempts to break all anti-dependencies within a 12 // block. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 17 #define LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 18 19 #include "llvm/ADT/BitVector.h" 20 #include "llvm/CodeGen/AntiDepBreaker.h" 21 #include "llvm/CodeGen/TargetSubtargetInfo.h" 22 #include "llvm/Support/Compiler.h" 23 #include <map> 24 #include <set> 25 #include <vector> 26 27 namespace llvm { 28 29 class MachineBasicBlock; 30 class MachineFunction; 31 class MachineInstr; 32 class MachineOperand; 33 class MachineRegisterInfo; 34 class RegisterClassInfo; 35 class TargetInstrInfo; 36 class TargetRegisterClass; 37 class TargetRegisterInfo; 38 39 /// Contains all the state necessary for anti-dep breaking. 40 class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepState { 41 public: 42 /// Information about a register reference within a liverange 43 struct RegisterReference { 44 /// The registers operand 45 MachineOperand *Operand; 46 47 /// The register class 48 const TargetRegisterClass *RC; 49 }; 50 51 private: 52 /// Number of non-virtual target registers (i.e. TRI->getNumRegs()). 53 const unsigned NumTargetRegs; 54 55 /// Implements a disjoint-union data structure to 56 /// form register groups. A node is represented by an index into 57 /// the vector. A node can "point to" itself to indicate that it 58 /// is the parent of a group, or point to another node to indicate 59 /// that it is a member of the same group as that node. 60 std::vector<unsigned> GroupNodes; 61 62 /// For each register, the index of the GroupNode 63 /// currently representing the group that the register belongs to. 64 /// Register 0 is always represented by the 0 group, a group 65 /// composed of registers that are not eligible for anti-aliasing. 66 std::vector<unsigned> GroupNodeIndices; 67 68 /// Map registers to all their references within a live range. 69 std::multimap<MCRegister, RegisterReference> RegRefs; 70 71 /// The index of the most recent kill (proceeding bottom-up), 72 /// or ~0u if the register is not live. 73 std::vector<unsigned> KillIndices; 74 75 /// The index of the most recent complete def (proceeding bottom 76 /// up), or ~0u if the register is live. 77 std::vector<unsigned> DefIndices; 78 79 public: 80 AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB); 81 82 /// Return the kill indices. GetKillIndices()83 std::vector<unsigned> &GetKillIndices() { return KillIndices; } 84 85 /// Return the define indices. GetDefIndices()86 std::vector<unsigned> &GetDefIndices() { return DefIndices; } 87 88 /// Return the RegRefs map. GetRegRefs()89 std::multimap<MCRegister, RegisterReference> &GetRegRefs() { 90 return RegRefs; 91 } 92 93 // Get the group for a register. The returned value is 94 // the index of the GroupNode representing the group. 95 unsigned GetGroup(MCRegister Reg); 96 97 // Return a vector of the registers belonging to a group. 98 // If RegRefs is non-NULL then only included referenced registers. 99 void GetGroupRegs( 100 unsigned Group, std::vector<MCRegister> &Regs, 101 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference> 102 *RegRefs); 103 104 // Union Reg1's and Reg2's groups to form a new group. 105 // Return the index of the GroupNode representing the group. 106 unsigned UnionGroups(MCRegister Reg1, MCRegister Reg2); 107 108 // Remove a register from its current group and place 109 // it alone in its own group. Return the index of the GroupNode 110 // representing the registers new group. 111 unsigned LeaveGroup(MCRegister Reg); 112 113 /// Return true if Reg is live. 114 bool IsLive(MCRegister Reg); 115 }; 116 117 class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepBreaker 118 : public AntiDepBreaker { 119 MachineFunction &MF; 120 MachineRegisterInfo &MRI; 121 const TargetInstrInfo *TII; 122 const TargetRegisterInfo *TRI; 123 const RegisterClassInfo &RegClassInfo; 124 125 /// The set of registers that should only be 126 /// renamed if they are on the critical path. 127 BitVector CriticalPathSet; 128 129 /// The state used to identify and rename anti-dependence registers. 130 AggressiveAntiDepState *State = nullptr; 131 132 public: 133 AggressiveAntiDepBreaker(MachineFunction &MFi, 134 const RegisterClassInfo &RCI, 135 TargetSubtargetInfo::RegClassVector& CriticalPathRCs); 136 AggressiveAntiDepBreaker & 137 operator=(const AggressiveAntiDepBreaker &other) = delete; 138 AggressiveAntiDepBreaker(const AggressiveAntiDepBreaker &other) = delete; 139 ~AggressiveAntiDepBreaker() override; 140 141 /// Initialize anti-dep breaking for a new basic block. 142 void StartBlock(MachineBasicBlock *BB) override; 143 144 /// Identifiy anti-dependencies along the critical path 145 /// of the ScheduleDAG and break them by renaming registers. 146 unsigned BreakAntiDependencies(const std::vector<SUnit> &SUnits, 147 MachineBasicBlock::iterator Begin, 148 MachineBasicBlock::iterator End, 149 unsigned InsertPosIndex, 150 DbgValueVector &DbgValues) override; 151 152 /// Update liveness information to account for the current 153 /// instruction, which will not be scheduled. 154 void Observe(MachineInstr &MI, unsigned Count, 155 unsigned InsertPosIndex) override; 156 157 /// Finish anti-dep breaking for a basic block. 158 void FinishBlock() override; 159 160 private: 161 /// Keep track of a position in the allocation order for each regclass. 162 using RenameOrderType = std::map<const TargetRegisterClass *, unsigned>; 163 164 /// Return true if MO represents a register 165 /// that is both implicitly used and defined in MI 166 bool IsImplicitDefUse(MachineInstr &MI, MachineOperand &MO); 167 168 /// If MI implicitly def/uses a register, then 169 /// return that register and all subregisters. 170 void GetPassthruRegs(MachineInstr &MI, std::set<MCRegister> &PassthruRegs); 171 172 void HandleLastUse(MCRegister Reg, unsigned KillIdx, const char *tag, 173 const char *header = nullptr, 174 const char *footer = nullptr); 175 176 void PrescanInstruction(MachineInstr &MI, unsigned Count, 177 const std::set<MCRegister> &PassthruRegs); 178 void ScanInstruction(MachineInstr &MI, unsigned Count); 179 BitVector GetRenameRegisters(MCRegister Reg); 180 bool FindSuitableFreeRegisters(MCRegister SuperReg, 181 unsigned AntiDepGroupIndex, 182 RenameOrderType &RenameOrder, 183 std::map<MCRegister, MCRegister> &RenameMap); 184 }; 185 186 } // end namespace llvm 187 188 #endif // LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 189