LLVM  14.0.0git
AggressiveAntiDepBreaker.h
Go to the documentation of this file.
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"
22 #include "llvm/Support/Compiler.h"
23 #include <map>
24 #include <set>
25 #include <vector>
26 
27 namespace llvm {
28 
29 class MachineBasicBlock;
30 class MachineFunction;
31 class MachineInstr;
32 class MachineOperand;
33 class MachineRegisterInfo;
34 class RegisterClassInfo;
35 class TargetInstrInfo;
36 class TargetRegisterClass;
37 class TargetRegisterInfo;
38 
39  /// Contains all the state necessary for anti-dep breaking.
41  public:
42  /// Information about a register reference within a liverange
44  /// The registers operand
46 
47  /// The register class
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,
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 
117  : public AntiDepBreaker {
118  MachineFunction &MF;
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:
133  const RegisterClassInfo &RCI,
134  TargetSubtargetInfo::RegClassVector& CriticalPathRCs);
135  ~AggressiveAntiDepBreaker() override;
136 
137  /// Initialize anti-dep breaking for a new basic block.
138  void StartBlock(MachineBasicBlock *BB) override;
139 
140  /// Identifiy anti-dependencies along the critical path
141  /// of the ScheduleDAG and break them by renaming registers.
142  unsigned BreakAntiDependencies(const std::vector<SUnit> &SUnits,
145  unsigned InsertPosIndex,
146  DbgValueVector &DbgValues) override;
147 
148  /// Update liveness information to account for the current
149  /// instruction, which will not be scheduled.
150  void Observe(MachineInstr &MI, unsigned Count,
151  unsigned InsertPosIndex) override;
152 
153  /// Finish anti-dep breaking for a basic block.
154  void FinishBlock() override;
155 
156  private:
157  /// Keep track of a position in the allocation order for each regclass.
158  using RenameOrderType = std::map<const TargetRegisterClass *, unsigned>;
159 
160  /// Return true if MO represents a register
161  /// that is both implicitly used and defined in MI
162  bool IsImplicitDefUse(MachineInstr &MI, MachineOperand &MO);
163 
164  /// If MI implicitly def/uses a register, then
165  /// return that register and all subregisters.
166  void GetPassthruRegs(MachineInstr &MI, std::set<unsigned> &PassthruRegs);
167 
168  void HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag,
169  const char *header = nullptr,
170  const char *footer = nullptr);
171 
172  void PrescanInstruction(MachineInstr &MI, unsigned Count,
173  std::set<unsigned> &PassthruRegs);
174  void ScanInstruction(MachineInstr &MI, unsigned Count);
175  BitVector GetRenameRegisters(unsigned Reg);
176  bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex,
177  RenameOrderType& RenameOrder,
178  std::map<unsigned, unsigned> &RenameMap);
179  };
180 
181 } // end namespace llvm
182 
183 #endif // LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1558
llvm::AggressiveAntiDepState::GetRegRefs
std::multimap< unsigned, RegisterReference > & GetRegRefs()
Return the RegRefs map.
Definition: AggressiveAntiDepBreaker.h:89
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
llvm::AggressiveAntiDepState::RegisterReference::Operand
MachineOperand * Operand
The registers operand.
Definition: AggressiveAntiDepBreaker.h:45
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1559
llvm::AggressiveAntiDepState
Contains all the state necessary for anti-dep breaking.
Definition: AggressiveAntiDepBreaker.h:40
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
BitVector.h
AntiDepBreaker.h
llvm::BitVector
Definition: BitVector.h:74
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::AggressiveAntiDepState::GetKillIndices
std::vector< unsigned > & GetKillIndices()
Return the kill indices.
Definition: AggressiveAntiDepBreaker.h:83
llvm::RegisterClassInfo
Definition: RegisterClassInfo.h:30
llvm::AggressiveAntiDepState::GetDefIndices
std::vector< unsigned > & GetDefIndices()
Return the define indices.
Definition: AggressiveAntiDepBreaker.h:86
llvm::AggressiveAntiDepBreaker
Definition: AggressiveAntiDepBreaker.h:116
llvm::MachineFunction
Definition: MachineFunction.h:234
Compiler.h
TargetSubtargetInfo.h
LLVM_LIBRARY_VISIBILITY
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:131
llvm::AggressiveAntiDepState::RegisterReference::RC
const TargetRegisterClass * RC
The register class.
Definition: AggressiveAntiDepBreaker.h:48
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::AggressiveAntiDepState::RegisterReference
Information about a register reference within a liverange.
Definition: AggressiveAntiDepBreaker.h:43
llvm::AntiDepBreaker
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
Definition: AntiDepBreaker.h:32
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::AntiDepBreaker::DbgValueVector
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
Definition: AntiDepBreaker.h:35