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