1//==- llvm/CodeGen/AggressiveAntiDepBreaker.h - Anti-Dep Support -*- C++ -*-==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the AggressiveAntiDepBreaker class, which
10// implements register anti-dependence breaking during post-RA
11// scheduling. It attempts to break all anti-dependencies within a
12// block.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H
17#define LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H
18
19#include "llvm/ADT/BitVector.h"
20#include "llvm/CodeGen/AntiDepBreaker.h"
21#include "llvm/CodeGen/TargetSubtargetInfo.h"
22#include "llvm/Support/Compiler.h"
23#include <map>
24#include <set>
25#include <vector>
26
27namespace llvm {
28
29class MachineBasicBlock;
30class MachineFunction;
31class MachineInstr;
32class MachineOperand;
33class MachineRegisterInfo;
34class RegisterClassInfo;
35class TargetInstrInfo;
36class TargetRegisterClass;
37class TargetRegisterInfo;
38
39 /// Contains all the state necessary for anti-dep breaking.
40class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepState {
41 public:
42 /// Information about a register reference within a liverange
43 struct RegisterReference {
44 /// The registers operand
45 MachineOperand *Operand;
46
47 /// The register class
48 const TargetRegisterClass *RC;
49 };
50
51 private:
52 /// Number of non-virtual target registers (i.e. TRI->getNumRegs()).
53 const unsigned NumTargetRegs;
54
55 /// Implements a disjoint-union data structure to
56 /// form register groups. A node is represented by an index into
57 /// the vector. A node can "point to" itself to indicate that it
58 /// is the parent of a group, or point to another node to indicate
59 /// that it is a member of the same group as that node.
60 std::vector<unsigned> GroupNodes;
61
62 /// For each register, the index of the GroupNode
63 /// currently representing the group that the register belongs to.
64 /// Register 0 is always represented by the 0 group, a group
65 /// composed of registers that are not eligible for anti-aliasing.
66 std::vector<unsigned> GroupNodeIndices;
67
68 /// Map registers to all their references within a live range.
69 std::multimap<MCRegister, RegisterReference> RegRefs;
70
71 /// The index of the most recent kill (proceeding bottom-up),
72 /// or ~0u if the register is not live.
73 std::vector<unsigned> KillIndices;
74
75 /// The index of the most recent complete def (proceeding bottom
76 /// up), or ~0u if the register is live.
77 std::vector<unsigned> DefIndices;
78
79 public:
80 AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB);
81
82 /// Return the kill indices.
83 std::vector<unsigned> &GetKillIndices() { return KillIndices; }
84
85 /// Return the define indices.
86 std::vector<unsigned> &GetDefIndices() { return DefIndices; }
87
88 /// Return the RegRefs map.
89 std::multimap<MCRegister, RegisterReference> &GetRegRefs() {
90 return RegRefs;
91 }
92
93 // Get the group for a register. The returned value is
94 // the index of the GroupNode representing the group.
95 unsigned GetGroup(MCRegister Reg);
96
97 // Return a vector of the registers belonging to a group.
98 // If RegRefs is non-NULL then only included referenced registers.
99 void GetGroupRegs(
100 unsigned Group, std::vector<MCRegister> &Regs,
101 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>
102 *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(MCRegister Reg1, MCRegister 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(MCRegister Reg);
112
113 /// Return true if Reg is live.
114 bool IsLive(MCRegister 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 &
137 operator=(const AggressiveAntiDepBreaker &other) = delete;
138 AggressiveAntiDepBreaker(const AggressiveAntiDepBreaker &other) = delete;
139 ~AggressiveAntiDepBreaker() override;
140
141 /// Initialize anti-dep breaking for a new basic block.
142 void StartBlock(MachineBasicBlock *BB) override;
143
144 /// Identifiy anti-dependencies along the critical path
145 /// of the ScheduleDAG and break them by renaming registers.
146 unsigned BreakAntiDependencies(const std::vector<SUnit> &SUnits,
147 MachineBasicBlock::iterator Begin,
148 MachineBasicBlock::iterator End,
149 unsigned InsertPosIndex,
150 DbgValueVector &DbgValues) override;
151
152 /// Update liveness information to account for the current
153 /// instruction, which will not be scheduled.
154 void Observe(MachineInstr &MI, unsigned Count,
155 unsigned InsertPosIndex) override;
156
157 /// 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 using RenameOrderType = std::map<const TargetRegisterClass *, unsigned>;
163
164 /// 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 /// If MI implicitly def/uses a register, then
169 /// return that register and all subregisters.
170 void GetPassthruRegs(MachineInstr &MI, std::set<MCRegister> &PassthruRegs);
171
172 void HandleLastUse(MCRegister 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 const std::set<MCRegister> &PassthruRegs);
178 void ScanInstruction(MachineInstr &MI, unsigned Count);
179 BitVector GetRenameRegisters(MCRegister Reg);
180 bool FindSuitableFreeRegisters(MCRegister SuperReg,
181 unsigned AntiDepGroupIndex,
182 RenameOrderType &RenameOrder,
183 std::map<MCRegister, MCRegister> &RenameMap);
184 };
185
186} // end namespace llvm
187
188#endif // LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H
189