]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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 | ||
1a4d82fc JJ |
17 | #ifndef LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H |
18 | #define LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H | |
223e47cc LB |
19 | |
20 | #include "AntiDepBreaker.h" | |
970d7e83 LB |
21 | #include "llvm/ADT/BitVector.h" |
22 | #include "llvm/ADT/SmallSet.h" | |
223e47cc LB |
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" | |
223e47cc | 28 | #include "llvm/Target/TargetRegisterInfo.h" |
970d7e83 | 29 | #include "llvm/Target/TargetSubtargetInfo.h" |
223e47cc LB |
30 | #include <map> |
31 | ||
32 | namespace llvm { | |
33 | class RegisterClassInfo; | |
34 | ||
223e47cc LB |
35 | /// Contains all the state necessary for anti-dep breaking. |
36 | class AggressiveAntiDepState { | |
37 | public: | |
1a4d82fc | 38 | /// Information about a register reference within a liverange |
223e47cc | 39 | typedef struct { |
1a4d82fc | 40 | /// The registers operand |
223e47cc | 41 | MachineOperand *Operand; |
1a4d82fc | 42 | /// The register class |
223e47cc LB |
43 | const TargetRegisterClass *RC; |
44 | } RegisterReference; | |
45 | ||
46 | private: | |
1a4d82fc | 47 | /// Number of non-virtual target registers (i.e. TRI->getNumRegs()). |
223e47cc LB |
48 | const unsigned NumTargetRegs; |
49 | ||
1a4d82fc | 50 | /// Implements a disjoint-union data structure to |
223e47cc LB |
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 | ||
1a4d82fc | 57 | /// For each register, the index of the GroupNode |
223e47cc LB |
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 | ||
1a4d82fc | 63 | /// Map registers to all their references within a live range. |
223e47cc LB |
64 | std::multimap<unsigned, RegisterReference> RegRefs; |
65 | ||
1a4d82fc | 66 | /// The index of the most recent kill (proceding bottom-up), |
223e47cc LB |
67 | /// or ~0u if the register is not live. |
68 | std::vector<unsigned> KillIndices; | |
69 | ||
1a4d82fc | 70 | /// The index of the most recent complete def (proceding bottom |
223e47cc LB |
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 | ||
1a4d82fc | 77 | /// Return the kill indices. |
223e47cc LB |
78 | std::vector<unsigned> &GetKillIndices() { return KillIndices; } |
79 | ||
1a4d82fc | 80 | /// Return the define indices. |
223e47cc LB |
81 | std::vector<unsigned> &GetDefIndices() { return DefIndices; } |
82 | ||
1a4d82fc | 83 | /// Return the RegRefs map. |
223e47cc LB |
84 | std::multimap<unsigned, RegisterReference>& GetRegRefs() { return RegRefs; } |
85 | ||
1a4d82fc | 86 | // Get the group for a register. The returned value is |
223e47cc LB |
87 | // the index of the GroupNode representing the group. |
88 | unsigned GetGroup(unsigned Reg); | |
89 | ||
1a4d82fc JJ |
90 | // Return a vector of the registers belonging to a group. |
91 | // If RegRefs is non-NULL then only included referenced registers. | |
223e47cc LB |
92 | void GetGroupRegs( |
93 | unsigned Group, | |
94 | std::vector<unsigned> &Regs, | |
95 | std::multimap<unsigned, | |
96 | AggressiveAntiDepState::RegisterReference> *RegRefs); | |
97 | ||
1a4d82fc JJ |
98 | // Union Reg1's and Reg2's groups to form a new group. |
99 | // Return the index of the GroupNode representing the group. | |
223e47cc LB |
100 | unsigned UnionGroups(unsigned Reg1, unsigned Reg2); |
101 | ||
1a4d82fc | 102 | // Remove a register from its current group and place |
223e47cc LB |
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 | ||
1a4d82fc | 107 | /// Return true if Reg is live. |
223e47cc LB |
108 | bool IsLive(unsigned Reg); |
109 | }; | |
110 | ||
111 | ||
223e47cc LB |
112 | class AggressiveAntiDepBreaker : public AntiDepBreaker { |
113 | MachineFunction& MF; | |
114 | MachineRegisterInfo &MRI; | |
115 | const TargetInstrInfo *TII; | |
116 | const TargetRegisterInfo *TRI; | |
117 | const RegisterClassInfo &RegClassInfo; | |
118 | ||
1a4d82fc | 119 | /// The set of registers that should only be |
223e47cc LB |
120 | /// renamed if they are on the critical path. |
121 | BitVector CriticalPathSet; | |
122 | ||
1a4d82fc | 123 | /// The state used to identify and rename anti-dependence registers. |
223e47cc LB |
124 | AggressiveAntiDepState *State; |
125 | ||
126 | public: | |
127 | AggressiveAntiDepBreaker(MachineFunction& MFi, | |
128 | const RegisterClassInfo &RCI, | |
129 | TargetSubtargetInfo::RegClassVector& CriticalPathRCs); | |
130 | ~AggressiveAntiDepBreaker(); | |
131 | ||
1a4d82fc JJ |
132 | /// Initialize anti-dep breaking for a new basic block. |
133 | void StartBlock(MachineBasicBlock *BB) override; | |
223e47cc | 134 | |
1a4d82fc | 135 | /// Identifiy anti-dependencies along the critical path |
223e47cc LB |
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, | |
1a4d82fc | 142 | DbgValueVector &DbgValues) override; |
223e47cc | 143 | |
1a4d82fc | 144 | /// Update liveness information to account for the current |
223e47cc LB |
145 | /// instruction, which will not be scheduled. |
146 | /// | |
1a4d82fc JJ |
147 | void Observe(MachineInstr *MI, unsigned Count, |
148 | unsigned InsertPosIndex) override; | |
223e47cc | 149 | |
1a4d82fc JJ |
150 | /// Finish anti-dep breaking for a basic block. |
151 | void FinishBlock() override; | |
223e47cc LB |
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 | ||
1a4d82fc | 157 | /// Return true if MO represents a register |
223e47cc LB |
158 | /// that is both implicitly used and defined in MI |
159 | bool IsImplicitDefUse(MachineInstr *MI, MachineOperand& MO); | |
160 | ||
1a4d82fc | 161 | /// If MI implicitly def/uses a register, then |
223e47cc LB |
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, | |
1a4d82fc JJ |
166 | const char *header = nullptr, |
167 | const char *footer = nullptr); | |
223e47cc LB |
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 |