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