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