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<unsigned, 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. 83 std::vector<unsigned> &GetKillIndices() { return KillIndices; } 84 85 /// Return the define indices. 86 std::vector<unsigned> &GetDefIndices() { return DefIndices; } 87 88 /// Return the RegRefs map. 89 std::multimap<unsigned, RegisterReference>& GetRegRefs() { return RegRefs; } 90 91 // Get the group for a register. The returned value is 92 // the index of the GroupNode representing the group. 93 unsigned GetGroup(unsigned Reg); 94 95 // Return a vector of the registers belonging to a group. 96 // If RegRefs is non-NULL then only included referenced registers. 97 void GetGroupRegs( 98 unsigned Group, 99 std::vector<unsigned> &Regs, 100 std::multimap<unsigned, 101 AggressiveAntiDepState::RegisterReference> *RegRefs); 102 103 // Union Reg1's and Reg2's groups to form a new group. 104 // Return the index of the GroupNode representing the group. 105 unsigned UnionGroups(unsigned Reg1, unsigned Reg2); 106 107 // Remove a register from its current group and place 108 // it alone in its own group. Return the index of the GroupNode 109 // representing the registers new group. 110 unsigned LeaveGroup(unsigned Reg); 111 112 /// Return true if Reg is live. 113 bool IsLive(unsigned Reg); 114 }; 115 116 class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepBreaker 117 : public AntiDepBreaker { 118 MachineFunction &MF; 119 MachineRegisterInfo &MRI; 120 const TargetInstrInfo *TII; 121 const TargetRegisterInfo *TRI; 122 const RegisterClassInfo &RegClassInfo; 123 124 /// The set of registers that should only be 125 /// renamed if they are on the critical path. 126 BitVector CriticalPathSet; 127 128 /// The state used to identify and rename anti-dependence registers. 129 AggressiveAntiDepState *State = nullptr; 130 131 public: 132 AggressiveAntiDepBreaker(MachineFunction &MFi, 133 const RegisterClassInfo &RCI, 134 TargetSubtargetInfo::RegClassVector& CriticalPathRCs); 135 AggressiveAntiDepBreaker & 136 operator=(const AggressiveAntiDepBreaker &other) = delete; 137 AggressiveAntiDepBreaker(const AggressiveAntiDepBreaker &other) = delete; 138 ~AggressiveAntiDepBreaker() override; 139 140 /// Initialize anti-dep breaking for a new basic block. 141 void StartBlock(MachineBasicBlock *BB) override; 142 143 /// Identifiy anti-dependencies along the critical path 144 /// of the ScheduleDAG and break them by renaming registers. 145 unsigned BreakAntiDependencies(const std::vector<SUnit> &SUnits, 146 MachineBasicBlock::iterator Begin, 147 MachineBasicBlock::iterator End, 148 unsigned InsertPosIndex, 149 DbgValueVector &DbgValues) override; 150 151 /// Update liveness information to account for the current 152 /// instruction, which will not be scheduled. 153 void Observe(MachineInstr &MI, unsigned Count, 154 unsigned InsertPosIndex) override; 155 156 /// Finish anti-dep breaking for a basic block. 157 void FinishBlock() override; 158 159 private: 160 /// Keep track of a position in the allocation order for each regclass. 161 using RenameOrderType = std::map<const TargetRegisterClass *, unsigned>; 162 163 /// Return true if MO represents a register 164 /// that is both implicitly used and defined in MI 165 bool IsImplicitDefUse(MachineInstr &MI, MachineOperand &MO); 166 167 /// If MI implicitly def/uses a register, then 168 /// return that register and all subregisters. 169 void GetPassthruRegs(MachineInstr &MI, std::set<unsigned> &PassthruRegs); 170 171 void HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag, 172 const char *header = nullptr, 173 const char *footer = nullptr); 174 175 void PrescanInstruction(MachineInstr &MI, unsigned Count, 176 std::set<unsigned> &PassthruRegs); 177 void ScanInstruction(MachineInstr &MI, unsigned Count); 178 BitVector GetRenameRegisters(unsigned Reg); 179 bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex, 180 RenameOrderType& RenameOrder, 181 std::map<unsigned, unsigned> &RenameMap); 182 }; 183 184 } // end namespace llvm 185 186 #endif // LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 187