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<unsigned, 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<unsigned, RegisterReference>& GetRegRefs() { return RegRefs; }
90
91 // Get the group for a register. The returned value is
92 // the index of the GroupNode representing the group.
93 unsigned GetGroup(unsigned Reg);
94
95 // Return a vector of the registers belonging to a group.
96 // If RegRefs is non-NULL then only included referenced registers.
97 void GetGroupRegs(
98 unsigned Group,
99 std::vector<unsigned> &Regs,
100 std::multimap<unsigned,
101 AggressiveAntiDepState::RegisterReference> *RegRefs);
102
103 // Union Reg1's and Reg2's groups to form a new group.
104 // Return the index of the GroupNode representing the group.
105 unsigned UnionGroups(unsigned Reg1, unsigned Reg2);
106
107 // Remove a register from its current group and place
108 // it alone in its own group. Return the index of the GroupNode
109 // representing the registers new group.
110 unsigned LeaveGroup(unsigned Reg);
111
112 /// Return true if Reg is live.
113 bool IsLive(unsigned Reg);
114 };
115
116 class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepBreaker
117 : public AntiDepBreaker {
118 MachineFunction &MF;
119 MachineRegisterInfo &MRI;
120 const TargetInstrInfo *TII;
121 const TargetRegisterInfo *TRI;
122 const RegisterClassInfo &RegClassInfo;
123
124 /// The set of registers that should only be
125 /// renamed if they are on the critical path.
126 BitVector CriticalPathSet;
127
128 /// The state used to identify and rename anti-dependence registers.
129 AggressiveAntiDepState *State = nullptr;
130
131 public:
132 AggressiveAntiDepBreaker(MachineFunction &MFi,
133 const RegisterClassInfo &RCI,
134 TargetSubtargetInfo::RegClassVector& CriticalPathRCs);
135 AggressiveAntiDepBreaker &
136 operator=(const AggressiveAntiDepBreaker &other) = delete;
137 AggressiveAntiDepBreaker(const AggressiveAntiDepBreaker &other) = delete;
138 ~AggressiveAntiDepBreaker() override;
139
140 /// Initialize anti-dep breaking for a new basic block.
141 void StartBlock(MachineBasicBlock *BB) override;
142
143 /// Identifiy anti-dependencies along the critical path
144 /// of the ScheduleDAG and break them by renaming registers.
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 /// Update liveness information to account for the current
152 /// instruction, which will not be scheduled.
153 void Observe(MachineInstr &MI, unsigned Count,
154 unsigned InsertPosIndex) override;
155
156 /// Finish anti-dep breaking for a basic block.
157 void FinishBlock() override;
158
159 private:
160 /// Keep track of a position in the allocation order for each regclass.
161 using RenameOrderType = std::map<const TargetRegisterClass *, unsigned>;
162
163 /// Return true if MO represents a register
164 /// that is both implicitly used and defined in MI
165 bool IsImplicitDefUse(MachineInstr &MI, MachineOperand &MO);
166
167 /// If MI implicitly def/uses a register, then
168 /// return that register and all subregisters.
169 void GetPassthruRegs(MachineInstr &MI, std::set<unsigned> &PassthruRegs);
170
171 void HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag,
172 const char *header = nullptr,
173 const char *footer = nullptr);
174
175 void PrescanInstruction(MachineInstr &MI, unsigned Count,
176 std::set<unsigned> &PassthruRegs);
177 void ScanInstruction(MachineInstr &MI, unsigned Count);
178 BitVector GetRenameRegisters(unsigned Reg);
179 bool FindSuitableFreeRegisters(unsigned SuperReg,
180 unsigned AntiDepGroupIndex,
181 RenameOrderType &RenameOrder,
182 std::map<unsigned, unsigned> &RenameMap);
183 };
184
185} // end namespace llvm
186
187#endif // LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H
188