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_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 18 #define LLVM_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 /// Class AggressiveAntiDepState 36 /// Contains all the state necessary for anti-dep breaking. 37 class AggressiveAntiDepState { 38 public: 39 /// RegisterReference - Information about a register reference 40 /// within a liverange 41 typedef struct { 42 /// Operand - The registers operand 43 MachineOperand *Operand; 44 /// RC - The register class 45 const TargetRegisterClass *RC; 46 } RegisterReference; 47 48 private: 49 /// NumTargetRegs - Number of non-virtual target registers 50 /// (i.e. TRI->getNumRegs()). 51 const unsigned NumTargetRegs; 52 53 /// GroupNodes - Implements a disjoint-union data structure to 54 /// form register groups. A node is represented by an index into 55 /// the vector. A node can "point to" itself to indicate that it 56 /// is the parent of a group, or point to another node to indicate 57 /// that it is a member of the same group as that node. 58 std::vector<unsigned> GroupNodes; 59 60 /// GroupNodeIndices - For each register, the index of the GroupNode 61 /// currently representing the group that the register belongs to. 62 /// Register 0 is always represented by the 0 group, a group 63 /// composed of registers that are not eligible for anti-aliasing. 64 std::vector<unsigned> GroupNodeIndices; 65 66 /// RegRefs - Map registers to all their references within a live range. 67 std::multimap<unsigned, RegisterReference> RegRefs; 68 69 /// KillIndices - The index of the most recent kill (proceding bottom-up), 70 /// or ~0u if the register is not live. 71 std::vector<unsigned> KillIndices; 72 73 /// DefIndices - The index of the most recent complete def (proceding bottom 74 /// up), or ~0u if the register is live. 75 std::vector<unsigned> DefIndices; 76 77 public: 78 AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB); 79 80 /// GetKillIndices - Return the kill indices. GetKillIndices()81 std::vector<unsigned> &GetKillIndices() { return KillIndices; } 82 83 /// GetDefIndices - Return the define indices. GetDefIndices()84 std::vector<unsigned> &GetDefIndices() { return DefIndices; } 85 86 /// GetRegRefs - Return the RegRefs map. GetRegRefs()87 std::multimap<unsigned, RegisterReference>& GetRegRefs() { return RegRefs; } 88 89 // GetGroup - Get the group for a register. The returned value is 90 // the index of the GroupNode representing the group. 91 unsigned GetGroup(unsigned Reg); 92 93 // GetGroupRegs - Return a vector of the registers belonging to a 94 // group. If RegRefs is non-NULL then only included referenced registers. 95 void GetGroupRegs( 96 unsigned Group, 97 std::vector<unsigned> &Regs, 98 std::multimap<unsigned, 99 AggressiveAntiDepState::RegisterReference> *RegRefs); 100 101 // UnionGroups - Union Reg1's and Reg2's groups to form a new 102 // group. Return the index of the GroupNode representing the 103 // group. 104 unsigned UnionGroups(unsigned Reg1, unsigned Reg2); 105 106 // LeaveGroup - Remove a register from its current group and place 107 // it alone in its own group. Return the index of the GroupNode 108 // representing the registers new group. 109 unsigned LeaveGroup(unsigned Reg); 110 111 /// IsLive - Return true if Reg is live 112 bool IsLive(unsigned Reg); 113 }; 114 115 116 /// Class AggressiveAntiDepBreaker 117 class AggressiveAntiDepBreaker : public AntiDepBreaker { 118 MachineFunction& MF; 119 MachineRegisterInfo &MRI; 120 const TargetInstrInfo *TII; 121 const TargetRegisterInfo *TRI; 122 const RegisterClassInfo &RegClassInfo; 123 124 /// CriticalPathSet - The set of registers that should only be 125 /// renamed if they are on the critical path. 126 BitVector CriticalPathSet; 127 128 /// State - The state used to identify and rename anti-dependence 129 /// registers. 130 AggressiveAntiDepState *State; 131 132 public: 133 AggressiveAntiDepBreaker(MachineFunction& MFi, 134 const RegisterClassInfo &RCI, 135 TargetSubtargetInfo::RegClassVector& CriticalPathRCs); 136 ~AggressiveAntiDepBreaker(); 137 138 /// Start - Initialize anti-dep breaking for a new basic block. 139 void StartBlock(MachineBasicBlock *BB) override; 140 141 /// BreakAntiDependencies - Identifiy anti-dependencies along the critical 142 /// path 143 /// of the ScheduleDAG and break them by renaming registers. 144 /// 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 /// Observe - Update liveness information to account for the current 152 /// instruction, which will not be scheduled. 153 /// 154 void Observe(MachineInstr *MI, unsigned Count, 155 unsigned InsertPosIndex) override; 156 157 /// Finish - 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 typedef std::map<const TargetRegisterClass *, unsigned> RenameOrderType; 163 164 /// IsImplicitDefUse - 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 /// GetPassthruRegs - If MI implicitly def/uses a register, then 169 /// return that register and all subregisters. 170 void GetPassthruRegs(MachineInstr *MI, std::set<unsigned>& PassthruRegs); 171 172 void HandleLastUse(unsigned 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 std::set<unsigned>& PassthruRegs); 178 void ScanInstruction(MachineInstr *MI, unsigned Count); 179 BitVector GetRenameRegisters(unsigned Reg); 180 bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex, 181 RenameOrderType& RenameOrder, 182 std::map<unsigned, unsigned> &RenameMap); 183 }; 184 } 185 186 #endif 187