/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/AggressiveAntiDepBreaker.h
Line | Count | Source |
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 | 215k | std::vector<unsigned> &GetKillIndices() { return KillIndices; } |
79 | | |
80 | | /// Return the define indices. |
81 | 299k | std::vector<unsigned> &GetDefIndices() { return DefIndices; } |
82 | | |
83 | | /// Return the RegRefs map. |
84 | 342k | 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 |