Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp
Warning:line 786, column 22
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name AggressiveAntiDepBreaker.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -D PIC -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -D_RET_PROTECTOR -ret-protector -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp
1//===- AggressiveAntiDepBreaker.cpp - Anti-dep breaker --------------------===//
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#include "AggressiveAntiDepBreaker.h"
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/SmallSet.h"
19#include "llvm/ADT/iterator_range.h"
20#include "llvm/CodeGen/MachineBasicBlock.h"
21#include "llvm/CodeGen/MachineFrameInfo.h"
22#include "llvm/CodeGen/MachineFunction.h"
23#include "llvm/CodeGen/MachineInstr.h"
24#include "llvm/CodeGen/MachineOperand.h"
25#include "llvm/CodeGen/MachineRegisterInfo.h"
26#include "llvm/CodeGen/RegisterClassInfo.h"
27#include "llvm/CodeGen/ScheduleDAG.h"
28#include "llvm/CodeGen/TargetInstrInfo.h"
29#include "llvm/CodeGen/TargetRegisterInfo.h"
30#include "llvm/MC/MCInstrDesc.h"
31#include "llvm/MC/MCRegisterInfo.h"
32#include "llvm/Support/CommandLine.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Support/MachineValueType.h"
35#include "llvm/Support/raw_ostream.h"
36#include <cassert>
37#include <utility>
38
39using namespace llvm;
40
41#define DEBUG_TYPE"post-RA-sched" "post-RA-sched"
42
43// If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod
44static cl::opt<int>
45DebugDiv("agg-antidep-debugdiv",
46 cl::desc("Debug control for aggressive anti-dep breaker"),
47 cl::init(0), cl::Hidden);
48
49static cl::opt<int>
50DebugMod("agg-antidep-debugmod",
51 cl::desc("Debug control for aggressive anti-dep breaker"),
52 cl::init(0), cl::Hidden);
53
54AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs,
55 MachineBasicBlock *BB)
56 : NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0),
57 GroupNodeIndices(TargetRegs, 0), KillIndices(TargetRegs, 0),
58 DefIndices(TargetRegs, 0) {
59 const unsigned BBSize = BB->size();
60 for (unsigned i = 0; i < NumTargetRegs; ++i) {
61 // Initialize all registers to be in their own group. Initially we
62 // assign the register to the same-indexed GroupNode.
63 GroupNodeIndices[i] = i;
64 // Initialize the indices to indicate that no registers are live.
65 KillIndices[i] = ~0u;
66 DefIndices[i] = BBSize;
67 }
68}
69
70unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) {
71 unsigned Node = GroupNodeIndices[Reg];
72 while (GroupNodes[Node] != Node)
73 Node = GroupNodes[Node];
74
75 return Node;
76}
77
78void AggressiveAntiDepState::GetGroupRegs(
79 unsigned Group,
80 std::vector<unsigned> &Regs,
81 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs)
82{
83 for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {
84 if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0))
85 Regs.push_back(Reg);
86 }
87}
88
89unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2) {
90 assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!")((void)0);
91 assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!")((void)0);
92
93 // find group for each register
94 unsigned Group1 = GetGroup(Reg1);
95 unsigned Group2 = GetGroup(Reg2);
96
97 // if either group is 0, then that must become the parent
98 unsigned Parent = (Group1 == 0) ? Group1 : Group2;
99 unsigned Other = (Parent == Group1) ? Group2 : Group1;
100 GroupNodes.at(Other) = Parent;
101 return Parent;
102}
103
104unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg) {
105 // Create a new GroupNode for Reg. Reg's existing GroupNode must
106 // stay as is because there could be other GroupNodes referring to
107 // it.
108 unsigned idx = GroupNodes.size();
109 GroupNodes.push_back(idx);
110 GroupNodeIndices[Reg] = idx;
111 return idx;
112}
113
114bool AggressiveAntiDepState::IsLive(unsigned Reg) {
115 // KillIndex must be defined and DefIndex not defined for a register
116 // to be live.
117 return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
118}
119
120AggressiveAntiDepBreaker::AggressiveAntiDepBreaker(
121 MachineFunction &MFi, const RegisterClassInfo &RCI,
122 TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
123 : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()),
124 TII(MF.getSubtarget().getInstrInfo()),
125 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) {
126 /* Collect a bitset of all registers that are only broken if they
127 are on the critical path. */
128 for (unsigned i = 0, e = CriticalPathRCs.size(); i < e; ++i) {
129 BitVector CPSet = TRI->getAllocatableSet(MF, CriticalPathRCs[i]);
130 if (CriticalPathSet.none())
131 CriticalPathSet = CPSet;
132 else
133 CriticalPathSet |= CPSet;
134 }
135
136 LLVM_DEBUG(dbgs() << "AntiDep Critical-Path Registers:")do { } while (false);
137 LLVM_DEBUG(for (unsigned rdo { } while (false)
138 : CriticalPathSet.set_bits()) dbgs()do { } while (false)
139 << " " << printReg(r, TRI))do { } while (false);
140 LLVM_DEBUG(dbgs() << '\n')do { } while (false);
141}
142
143AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() {
144 delete State;
145}
146
147void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) {
148 assert(!State)((void)0);
149 State = new AggressiveAntiDepState(TRI->getNumRegs(), BB);
150
151 bool IsReturnBlock = BB->isReturnBlock();
152 std::vector<unsigned> &KillIndices = State->GetKillIndices();
153 std::vector<unsigned> &DefIndices = State->GetDefIndices();
154
155 // Examine the live-in regs of all successors.
156 for (MachineBasicBlock *Succ : BB->successors())
157 for (const auto &LI : Succ->liveins()) {
158 for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) {
159 unsigned Reg = *AI;
160 State->UnionGroups(Reg, 0);
161 KillIndices[Reg] = BB->size();
162 DefIndices[Reg] = ~0u;
163 }
164 }
165
166 // Mark live-out callee-saved registers. In a return block this is
167 // all callee-saved registers. In non-return this is any
168 // callee-saved register that is not saved in the prolog.
169 const MachineFrameInfo &MFI = MF.getFrameInfo();
170 BitVector Pristine = MFI.getPristineRegs(MF);
171 for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I;
172 ++I) {
173 unsigned Reg = *I;
174 if (!IsReturnBlock && !Pristine.test(Reg))
175 continue;
176 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
177 unsigned AliasReg = *AI;
178 State->UnionGroups(AliasReg, 0);
179 KillIndices[AliasReg] = BB->size();
180 DefIndices[AliasReg] = ~0u;
181 }
182 }
183}
184
185void AggressiveAntiDepBreaker::FinishBlock() {
186 delete State;
187 State = nullptr;
188}
189
190void AggressiveAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count,
191 unsigned InsertPosIndex) {
192 assert(Count < InsertPosIndex && "Instruction index out of expected range!")((void)0);
193
194 std::set<unsigned> PassthruRegs;
195 GetPassthruRegs(MI, PassthruRegs);
196 PrescanInstruction(MI, Count, PassthruRegs);
197 ScanInstruction(MI, Count);
198
199 LLVM_DEBUG(dbgs() << "Observe: ")do { } while (false);
200 LLVM_DEBUG(MI.dump())do { } while (false);
201 LLVM_DEBUG(dbgs() << "\tRegs:")do { } while (false);
202
203 std::vector<unsigned> &DefIndices = State->GetDefIndices();
204 for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) {
205 // If Reg is current live, then mark that it can't be renamed as
206 // we don't know the extent of its live-range anymore (now that it
207 // has been scheduled). If it is not live but was defined in the
208 // previous schedule region, then set its def index to the most
209 // conservative location (i.e. the beginning of the previous
210 // schedule region).
211 if (State->IsLive(Reg)) {
212 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs()do { } while (false)
213 << " " << printReg(Reg, TRI) << "=g" << State->GetGroup(Reg)do { } while (false)
214 << "->g0(region live-out)")do { } while (false);
215 State->UnionGroups(Reg, 0);
216 } else if ((DefIndices[Reg] < InsertPosIndex)
217 && (DefIndices[Reg] >= Count)) {
218 DefIndices[Reg] = Count;
219 }
220 }
221 LLVM_DEBUG(dbgs() << '\n')do { } while (false);
222}
223
224bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr &MI,
225 MachineOperand &MO) {
226 if (!MO.isReg() || !MO.isImplicit())
227 return false;
228
229 Register Reg = MO.getReg();
230 if (Reg == 0)
231 return false;
232
233 MachineOperand *Op = nullptr;
234 if (MO.isDef())
235 Op = MI.findRegisterUseOperand(Reg, true);
236 else
237 Op = MI.findRegisterDefOperand(Reg);
238
239 return(Op && Op->isImplicit());
240}
241
242void AggressiveAntiDepBreaker::GetPassthruRegs(
243 MachineInstr &MI, std::set<unsigned> &PassthruRegs) {
244 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
245 MachineOperand &MO = MI.getOperand(i);
246 if (!MO.isReg()) continue;
247 if ((MO.isDef() && MI.isRegTiedToUseOperand(i)) ||
248 IsImplicitDefUse(MI, MO)) {
249 const Register Reg = MO.getReg();
250 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
251 SubRegs.isValid(); ++SubRegs)
252 PassthruRegs.insert(*SubRegs);
253 }
254 }
255}
256
257/// AntiDepEdges - Return in Edges the anti- and output- dependencies
258/// in SU that we want to consider for breaking.
259static void AntiDepEdges(const SUnit *SU, std::vector<const SDep *> &Edges) {
260 SmallSet<unsigned, 4> RegSet;
261 for (const SDep &Pred : SU->Preds) {
262 if ((Pred.getKind() == SDep::Anti) || (Pred.getKind() == SDep::Output)) {
263 if (RegSet.insert(Pred.getReg()).second)
264 Edges.push_back(&Pred);
265 }
266 }
267}
268
269/// CriticalPathStep - Return the next SUnit after SU on the bottom-up
270/// critical path.
271static const SUnit *CriticalPathStep(const SUnit *SU) {
272 const SDep *Next = nullptr;
273 unsigned NextDepth = 0;
274 // Find the predecessor edge with the greatest depth.
275 if (SU) {
276 for (const SDep &Pred : SU->Preds) {
277 const SUnit *PredSU = Pred.getSUnit();
278 unsigned PredLatency = Pred.getLatency();
279 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;
280 // In the case of a latency tie, prefer an anti-dependency edge over
281 // other types of edges.
282 if (NextDepth < PredTotalLatency ||
283 (NextDepth == PredTotalLatency && Pred.getKind() == SDep::Anti)) {
284 NextDepth = PredTotalLatency;
285 Next = &Pred;
286 }
287 }
288 }
289
290 return (Next) ? Next->getSUnit() : nullptr;
291}
292
293void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx,
294 const char *tag,
295 const char *header,
296 const char *footer) {
297 std::vector<unsigned> &KillIndices = State->GetKillIndices();
298 std::vector<unsigned> &DefIndices = State->GetDefIndices();
299 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
300 RegRefs = State->GetRegRefs();
301
302 // FIXME: We must leave subregisters of live super registers as live, so that
303 // we don't clear out the register tracking information for subregisters of
304 // super registers we're still tracking (and with which we're unioning
305 // subregister definitions).
306 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
307 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) {
308 LLVM_DEBUG(if (!header && footer) dbgs() << footer)do { } while (false);
309 return;
310 }
311
312 if (!State->IsLive(Reg)) {
313 KillIndices[Reg] = KillIdx;
314 DefIndices[Reg] = ~0u;
315 RegRefs.erase(Reg);
316 State->LeaveGroup(Reg);
317 LLVM_DEBUG(if (header) {do { } while (false)
318 dbgs() << header << printReg(Reg, TRI);do { } while (false)
319 header = nullptr;do { } while (false)
320 })do { } while (false);
321 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag)do { } while (false);
322 // Repeat for subregisters. Note that we only do this if the superregister
323 // was not live because otherwise, regardless whether we have an explicit
324 // use of the subregister, the subregister's contents are needed for the
325 // uses of the superregister.
326 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
327 unsigned SubregReg = *SubRegs;
328 if (!State->IsLive(SubregReg)) {
329 KillIndices[SubregReg] = KillIdx;
330 DefIndices[SubregReg] = ~0u;
331 RegRefs.erase(SubregReg);
332 State->LeaveGroup(SubregReg);
333 LLVM_DEBUG(if (header) {do { } while (false)
334 dbgs() << header << printReg(Reg, TRI);do { } while (false)
335 header = nullptr;do { } while (false)
336 })do { } while (false);
337 LLVM_DEBUG(dbgs() << " " << printReg(SubregReg, TRI) << "->g"do { } while (false)
338 << State->GetGroup(SubregReg) << tag)do { } while (false);
339 }
340 }
341 }
342
343 LLVM_DEBUG(if (!header && footer) dbgs() << footer)do { } while (false);
344}
345
346void AggressiveAntiDepBreaker::PrescanInstruction(
347 MachineInstr &MI, unsigned Count, std::set<unsigned> &PassthruRegs) {
348 std::vector<unsigned> &DefIndices = State->GetDefIndices();
349 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
350 RegRefs = State->GetRegRefs();
351
352 // Handle dead defs by simulating a last-use of the register just
353 // after the def. A dead def can occur because the def is truly
354 // dead, or because only a subregister is live at the def. If we
355 // don't do this the dead def will be incorrectly merged into the
356 // previous def.
357 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
358 MachineOperand &MO = MI.getOperand(i);
359 if (!MO.isReg() || !MO.isDef()) continue;
360 Register Reg = MO.getReg();
361 if (Reg == 0) continue;
362
363 HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n");
364 }
365
366 LLVM_DEBUG(dbgs() << "\tDef Groups:")do { } while (false);
367 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
368 MachineOperand &MO = MI.getOperand(i);
369 if (!MO.isReg() || !MO.isDef()) continue;
370 Register Reg = MO.getReg();
371 if (Reg == 0) continue;
372
373 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g"do { } while (false)
374 << State->GetGroup(Reg))do { } while (false);
375
376 // If MI's defs have a special allocation requirement, don't allow
377 // any def registers to be changed. Also assume all registers
378 // defined in a call must not be changed (ABI). Inline assembly may
379 // reference either system calls or the register directly. Skip it until we
380 // can tell user specified registers from compiler-specified.
381 if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI) ||
382 MI.isInlineAsm()) {
383 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)")do { } while (false);
384 State->UnionGroups(Reg, 0);
385 }
386
387 // Any aliased that are live at this point are completely or
388 // partially defined here, so group those aliases with Reg.
389 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) {
390 unsigned AliasReg = *AI;
391 if (State->IsLive(AliasReg)) {
392 State->UnionGroups(Reg, AliasReg);
393 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via "do { } while (false)
394 << printReg(AliasReg, TRI) << ")")do { } while (false);
395 }
396 }
397
398 // Note register reference...
399 const TargetRegisterClass *RC = nullptr;
400 if (i < MI.getDesc().getNumOperands())
401 RC = TII->getRegClass(MI.getDesc(), i, TRI, MF);
402 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
403 RegRefs.insert(std::make_pair(Reg, RR));
404 }
405
406 LLVM_DEBUG(dbgs() << '\n')do { } while (false);
407
408 // Scan the register defs for this instruction and update
409 // live-ranges.
410 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
411 MachineOperand &MO = MI.getOperand(i);
412 if (!MO.isReg() || !MO.isDef()) continue;
413 Register Reg = MO.getReg();
414 if (Reg == 0) continue;
415 // Ignore KILLs and passthru registers for liveness...
416 if (MI.isKill() || (PassthruRegs.count(Reg) != 0))
417 continue;
418
419 // Update def for Reg and aliases.
420 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
421 // We need to be careful here not to define already-live super registers.
422 // If the super register is already live, then this definition is not
423 // a definition of the whole super register (just a partial insertion
424 // into it). Earlier subregister definitions (which we've not yet visited
425 // because we're iterating bottom-up) need to be linked to the same group
426 // as this definition.
427 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI))
428 continue;
429
430 DefIndices[*AI] = Count;
431 }
432 }
433}
434
435void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr &MI,
436 unsigned Count) {
437 LLVM_DEBUG(dbgs() << "\tUse Groups:")do { } while (false);
438 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
439 RegRefs = State->GetRegRefs();
440
441 // If MI's uses have special allocation requirement, don't allow
442 // any use registers to be changed. Also assume all registers
443 // used in a call must not be changed (ABI).
444 // Inline Assembly register uses also cannot be safely changed.
445 // FIXME: The issue with predicated instruction is more complex. We are being
446 // conservatively here because the kill markers cannot be trusted after
447 // if-conversion:
448 // %r6 = LDR %sp, %reg0, 92, 14, %reg0; mem:LD4[FixedStack14]
449 // ...
450 // STR %r0, killed %r6, %reg0, 0, 0, %cpsr; mem:ST4[%395]
451 // %r6 = LDR %sp, %reg0, 100, 0, %cpsr; mem:LD4[FixedStack12]
452 // STR %r0, killed %r6, %reg0, 0, 14, %reg0; mem:ST4[%396](align=8)
453 //
454 // The first R6 kill is not really a kill since it's killed by a predicated
455 // instruction which may not be executed. The second R6 def may or may not
456 // re-define R6 so it's not safe to change it since the last R6 use cannot be
457 // changed.
458 bool Special = MI.isCall() || MI.hasExtraSrcRegAllocReq() ||
459 TII->isPredicated(MI) || MI.isInlineAsm();
460
461 // Scan the register uses for this instruction and update
462 // live-ranges, groups and RegRefs.
463 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
464 MachineOperand &MO = MI.getOperand(i);
465 if (!MO.isReg() || !MO.isUse()) continue;
466 Register Reg = MO.getReg();
467 if (Reg == 0) continue;
468
469 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g"do { } while (false)
470 << State->GetGroup(Reg))do { } while (false);
471
472 // It wasn't previously live but now it is, this is a kill. Forget
473 // the previous live-range information and start a new live-range
474 // for the register.
475 HandleLastUse(Reg, Count, "(last-use)");
476
477 if (Special) {
478 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)")do { } while (false);
479 State->UnionGroups(Reg, 0);
480 }
481
482 // Note register reference...
483 const TargetRegisterClass *RC = nullptr;
484 if (i < MI.getDesc().getNumOperands())
485 RC = TII->getRegClass(MI.getDesc(), i, TRI, MF);
486 AggressiveAntiDepState::RegisterReference RR = { &MO, RC };
487 RegRefs.insert(std::make_pair(Reg, RR));
488 }
489
490 LLVM_DEBUG(dbgs() << '\n')do { } while (false);
491
492 // Form a group of all defs and uses of a KILL instruction to ensure
493 // that all registers are renamed as a group.
494 if (MI.isKill()) {
495 LLVM_DEBUG(dbgs() << "\tKill Group:")do { } while (false);
496
497 unsigned FirstReg = 0;
498 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
499 MachineOperand &MO = MI.getOperand(i);
500 if (!MO.isReg()) continue;
501 Register Reg = MO.getReg();
502 if (Reg == 0) continue;
503
504 if (FirstReg != 0) {
505 LLVM_DEBUG(dbgs() << "=" << printReg(Reg, TRI))do { } while (false);
506 State->UnionGroups(FirstReg, Reg);
507 } else {
508 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI))do { } while (false);
509 FirstReg = Reg;
510 }
511 }
512
513 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n')do { } while (false);
514 }
515}
516
517BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) {
518 BitVector BV(TRI->getNumRegs(), false);
519 bool first = true;
520
521 // Check all references that need rewriting for Reg. For each, use
522 // the corresponding register class to narrow the set of registers
523 // that are appropriate for renaming.
524 for (const auto &Q : make_range(State->GetRegRefs().equal_range(Reg))) {
525 const TargetRegisterClass *RC = Q.second.RC;
526 if (!RC) continue;
527
528 BitVector RCBV = TRI->getAllocatableSet(MF, RC);
529 if (first) {
530 BV |= RCBV;
531 first = false;
532 } else {
533 BV &= RCBV;
534 }
535
536 LLVM_DEBUG(dbgs() << " " << TRI->getRegClassName(RC))do { } while (false);
537 }
538
539 return BV;
540}
541
542bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
543 unsigned AntiDepGroupIndex,
544 RenameOrderType& RenameOrder,
545 std::map<unsigned, unsigned> &RenameMap) {
546 std::vector<unsigned> &KillIndices = State->GetKillIndices();
547 std::vector<unsigned> &DefIndices = State->GetDefIndices();
548 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
549 RegRefs = State->GetRegRefs();
550
551 // Collect all referenced registers in the same group as
552 // AntiDepReg. These all need to be renamed together if we are to
553 // break the anti-dependence.
554 std::vector<unsigned> Regs;
555 State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs);
556 assert(!Regs.empty() && "Empty register group!")((void)0);
557 if (Regs.empty())
558 return false;
559
560 // Find the "superest" register in the group. At the same time,
561 // collect the BitVector of registers that can be used to rename
562 // each register.
563 LLVM_DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndexdo { } while (false)
564 << ":\n")do { } while (false);
565 std::map<unsigned, BitVector> RenameRegisterMap;
566 unsigned SuperReg = 0;
567 for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
568 unsigned Reg = Regs[i];
569 if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg))
570 SuperReg = Reg;
571
572 // If Reg has any references, then collect possible rename regs
573 if (RegRefs.count(Reg) > 0) {
574 LLVM_DEBUG(dbgs() << "\t\t" << printReg(Reg, TRI) << ":")do { } while (false);
575
576 BitVector &BV = RenameRegisterMap[Reg];
577 assert(BV.empty())((void)0);
578 BV = GetRenameRegisters(Reg);
579
580 LLVM_DEBUG({do { } while (false)
581 dbgs() << " ::";do { } while (false)
582 for (unsigned r : BV.set_bits())do { } while (false)
583 dbgs() << " " << printReg(r, TRI);do { } while (false)
584 dbgs() << "\n";do { } while (false)
585 })do { } while (false);
586 }
587 }
588
589 // All group registers should be a subreg of SuperReg.
590 for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
591 unsigned Reg = Regs[i];
592 if (Reg == SuperReg) continue;
593 bool IsSub = TRI->isSubRegister(SuperReg, Reg);
594 // FIXME: remove this once PR18663 has been properly fixed. For now,
595 // return a conservative answer:
596 // assert(IsSub && "Expecting group subregister");
597 if (!IsSub)
598 return false;
599 }
600
601#ifndef NDEBUG1
602 // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod
603 if (DebugDiv > 0) {
604 static int renamecnt = 0;
605 if (renamecnt++ % DebugDiv != DebugMod)
606 return false;
607
608 dbgs() << "*** Performing rename " << printReg(SuperReg, TRI)
609 << " for debug ***\n";
610 }
611#endif
612
613 // Check each possible rename register for SuperReg in round-robin
614 // order. If that register is available, and the corresponding
615 // registers are available for the other group subregisters, then we
616 // can use those registers to rename.
617
618 // FIXME: Using getMinimalPhysRegClass is very conservative. We should
619 // check every use of the register and find the largest register class
620 // that can be used in all of them.
621 const TargetRegisterClass *SuperRC =
622 TRI->getMinimalPhysRegClass(SuperReg, MVT::Other);
623
624 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC);
625 if (Order.empty()) {
626 LLVM_DEBUG(dbgs() << "\tEmpty Super Regclass!!\n")do { } while (false);
627 return false;
628 }
629
630 LLVM_DEBUG(dbgs() << "\tFind Registers:")do { } while (false);
631
632 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size()));
633
634 unsigned OrigR = RenameOrder[SuperRC];
635 unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR);
636 unsigned R = OrigR;
637 do {
638 if (R == 0) R = Order.size();
639 --R;
640 const unsigned NewSuperReg = Order[R];
641 // Don't consider non-allocatable registers
642 if (!MRI.isAllocatable(NewSuperReg)) continue;
643 // Don't replace a register with itself.
644 if (NewSuperReg == SuperReg) continue;
645
646 LLVM_DEBUG(dbgs() << " [" << printReg(NewSuperReg, TRI) << ':')do { } while (false);
647 RenameMap.clear();
648
649 // For each referenced group register (which must be a SuperReg or
650 // a subregister of SuperReg), find the corresponding subregister
651 // of NewSuperReg and make sure it is free to be renamed.
652 for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
653 unsigned Reg = Regs[i];
654 unsigned NewReg = 0;
655 if (Reg == SuperReg) {
656 NewReg = NewSuperReg;
657 } else {
658 unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg);
659 if (NewSubRegIdx != 0)
660 NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx);
661 }
662
663 LLVM_DEBUG(dbgs() << " " << printReg(NewReg, TRI))do { } while (false);
664
665 // Check if Reg can be renamed to NewReg.
666 if (!RenameRegisterMap[Reg].test(NewReg)) {
667 LLVM_DEBUG(dbgs() << "(no rename)")do { } while (false);
668 goto next_super_reg;
669 }
670
671 // If NewReg is dead and NewReg's most recent def is not before
672 // Regs's kill, it's safe to replace Reg with NewReg. We
673 // must also check all aliases of NewReg, because we can't define a
674 // register when any sub or super is already live.
675 if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) {
676 LLVM_DEBUG(dbgs() << "(live)")do { } while (false);
677 goto next_super_reg;
678 } else {
679 bool found = false;
680 for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) {
681 unsigned AliasReg = *AI;
682 if (State->IsLive(AliasReg) ||
683 (KillIndices[Reg] > DefIndices[AliasReg])) {
684 LLVM_DEBUG(dbgs()do { } while (false)
685 << "(alias " << printReg(AliasReg, TRI) << " live)")do { } while (false);
686 found = true;
687 break;
688 }
689 }
690 if (found)
691 goto next_super_reg;
692 }
693
694 // We cannot rename 'Reg' to 'NewReg' if one of the uses of 'Reg' also
695 // defines 'NewReg' via an early-clobber operand.
696 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) {
697 MachineInstr *UseMI = Q.second.Operand->getParent();
698 int Idx = UseMI->findRegisterDefOperandIdx(NewReg, false, true, TRI);
699 if (Idx == -1)
700 continue;
701
702 if (UseMI->getOperand(Idx).isEarlyClobber()) {
703 LLVM_DEBUG(dbgs() << "(ec)")do { } while (false);
704 goto next_super_reg;
705 }
706 }
707
708 // Also, we cannot rename 'Reg' to 'NewReg' if the instruction defining
709 // 'Reg' is an early-clobber define and that instruction also uses
710 // 'NewReg'.
711 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) {
712 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber())
713 continue;
714
715 MachineInstr *DefMI = Q.second.Operand->getParent();
716 if (DefMI->readsRegister(NewReg, TRI)) {
717 LLVM_DEBUG(dbgs() << "(ec)")do { } while (false);
718 goto next_super_reg;
719 }
720 }
721
722 // Record that 'Reg' can be renamed to 'NewReg'.
723 RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg));
724 }
725
726 // If we fall-out here, then every register in the group can be
727 // renamed, as recorded in RenameMap.
728 RenameOrder.erase(SuperRC);
729 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R));
730 LLVM_DEBUG(dbgs() << "]\n")do { } while (false);
731 return true;
732
733 next_super_reg:
734 LLVM_DEBUG(dbgs() << ']')do { } while (false);
735 } while (R != EndR);
736
737 LLVM_DEBUG(dbgs() << '\n')do { } while (false);
738
739 // No registers are free and available!
740 return false;
741}
742
743/// BreakAntiDependencies - Identifiy anti-dependencies within the
744/// ScheduleDAG and break them by renaming registers.
745unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(
746 const std::vector<SUnit> &SUnits,
747 MachineBasicBlock::iterator Begin,
748 MachineBasicBlock::iterator End,
749 unsigned InsertPosIndex,
750 DbgValueVector &DbgValues) {
751 std::vector<unsigned> &KillIndices = State->GetKillIndices();
752 std::vector<unsigned> &DefIndices = State->GetDefIndices();
753 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
754 RegRefs = State->GetRegRefs();
755
756 // The code below assumes that there is at least one instruction,
757 // so just duck out immediately if the block is empty.
758 if (SUnits.empty()) return 0;
1
Assuming the condition is false
→
2
←
Taking false branch
→
759
760 // For each regclass the next register to use for renaming.
761 RenameOrderType RenameOrder;
762
763 // ...need a map from MI to SUnit.
764 std::map<MachineInstr *, const SUnit *> MISUnitMap;
765 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
3
←
Assuming 'i' is equal to 'e'
→
4
←
Loop condition is false. Execution continues on line 774
→
766 const SUnit *SU = &SUnits[i];
767 MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->getInstr(),
768 SU));
769 }
770
771 // Track progress along the critical path through the SUnit graph as
772 // we walk the instructions. This is needed for regclasses that only
773 // break critical-path anti-dependencies.
774 const SUnit *CriticalPathSU = nullptr;
5
←
'CriticalPathSU' initialized to a null pointer value
→
775 MachineInstr *CriticalPathMI = nullptr;
776 if (CriticalPathSet.any()) {
6
←
Assuming the condition is true
→
7
←
Taking true branch
→
777 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
8
←
Assuming 'i' is equal to 'e'
→
9
←
Loop condition is false. Execution continues on line 785
→
778 const SUnit *SU = &SUnits[i];
779 if (!CriticalPathSU ||
780 ((SU->getDepth() + SU->Latency) >
781 (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) {
782 CriticalPathSU = SU;
783 }
784 }
785 assert(CriticalPathSU && "Failed to find SUnit critical path")((void)0);
786 CriticalPathMI = CriticalPathSU->getInstr();
10
←
Called C++ object pointer is null
787 }
788
789#ifndef NDEBUG1
790 LLVM_DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n")do { } while (false);
791 LLVM_DEBUG(dbgs() << "Available regs:")do { } while (false);
792 for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
793 if (!State->IsLive(Reg))
794 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI))do { } while (false);
795 }
796 LLVM_DEBUG(dbgs() << '\n')do { } while (false);
797#endif
798
799 BitVector RegAliases(TRI->getNumRegs());
800
801 // Attempt to break anti-dependence edges. Walk the instructions
802 // from the bottom up, tracking information about liveness as we go
803 // to help determine which registers are available.
804 unsigned Broken = 0;
805 unsigned Count = InsertPosIndex - 1;
806 for (MachineBasicBlock::iterator I = End, E = Begin;
807 I != E; --Count) {
808 MachineInstr &MI = *--I;
809
810 if (MI.isDebugInstr())
811 continue;
812
813 LLVM_DEBUG(dbgs() << "Anti: ")do { } while (false);
814 LLVM_DEBUG(MI.dump())do { } while (false);
815
816 std::set<unsigned> PassthruRegs;
817 GetPassthruRegs(MI, PassthruRegs);
818
819 // Process the defs in MI...
820 PrescanInstruction(MI, Count, PassthruRegs);
821
822 // The dependence edges that represent anti- and output-
823 // dependencies that are candidates for breaking.
824 std::vector<const SDep *> Edges;
825 const SUnit *PathSU = MISUnitMap[&MI];
826 AntiDepEdges(PathSU, Edges);
827
828 // If MI is not on the critical path, then we don't rename
829 // registers in the CriticalPathSet.
830 BitVector *ExcludeRegs = nullptr;
831 if (&MI == CriticalPathMI) {
832 CriticalPathSU = CriticalPathStep(CriticalPathSU);
833 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr;
834 } else if (CriticalPathSet.any()) {
835 ExcludeRegs = &CriticalPathSet;
836 }
837
838 // Ignore KILL instructions (they form a group in ScanInstruction
839 // but don't cause any anti-dependence breaking themselves)
840 if (!MI.isKill()) {
841 // Attempt to break each anti-dependency...
842 for (unsigned i = 0, e = Edges.size(); i != e; ++i) {
843 const SDep *Edge = Edges[i];
844 SUnit *NextSU = Edge->getSUnit();
845
846 if ((Edge->getKind() != SDep::Anti) &&
847 (Edge->getKind() != SDep::Output)) continue;
848
849 unsigned AntiDepReg = Edge->getReg();
850 LLVM_DEBUG(dbgs() << "\tAntidep reg: " << printReg(AntiDepReg, TRI))do { } while (false);
851 assert(AntiDepReg != 0 && "Anti-dependence on reg0?")((void)0);
852
853 if (!MRI.isAllocatable(AntiDepReg)) {
854 // Don't break anti-dependencies on non-allocatable registers.
855 LLVM_DEBUG(dbgs() << " (non-allocatable)\n")do { } while (false);
856 continue;
857 } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg)) {
858 // Don't break anti-dependencies for critical path registers
859 // if not on the critical path
860 LLVM_DEBUG(dbgs() << " (not critical-path)\n")do { } while (false);
861 continue;
862 } else if (PassthruRegs.count(AntiDepReg) != 0) {
863 // If the anti-dep register liveness "passes-thru", then
864 // don't try to change it. It will be changed along with
865 // the use if required to break an earlier antidep.
866 LLVM_DEBUG(dbgs() << " (passthru)\n")do { } while (false);
867 continue;
868 } else {
869 // No anti-dep breaking for implicit deps
870 MachineOperand *AntiDepOp = MI.findRegisterDefOperand(AntiDepReg);
871 assert(AntiDepOp && "Can't find index for defined register operand")((void)0);
872 if (!AntiDepOp || AntiDepOp->isImplicit()) {
873 LLVM_DEBUG(dbgs() << " (implicit)\n")do { } while (false);
874 continue;
875 }
876
877 // If the SUnit has other dependencies on the SUnit that
878 // it anti-depends on, don't bother breaking the
879 // anti-dependency since those edges would prevent such
880 // units from being scheduled past each other
881 // regardless.
882 //
883 // Also, if there are dependencies on other SUnits with the
884 // same register as the anti-dependency, don't attempt to
885 // break it.
886 for (const SDep &Pred : PathSU->Preds) {
887 if (Pred.getSUnit() == NextSU ? (Pred.getKind() != SDep::Anti ||
888 Pred.getReg() != AntiDepReg)
889 : (Pred.getKind() == SDep::Data &&
890 Pred.getReg() == AntiDepReg)) {
891 AntiDepReg = 0;
892 break;
893 }
894 }
895 for (const SDep &Pred : PathSU->Preds) {
896 if ((Pred.getSUnit() == NextSU) && (Pred.getKind() != SDep::Anti) &&
897 (Pred.getKind() != SDep::Output)) {
898 LLVM_DEBUG(dbgs() << " (real dependency)\n")do { } while (false);
899 AntiDepReg = 0;
900 break;
901 } else if ((Pred.getSUnit() != NextSU) &&
902 (Pred.getKind() == SDep::Data) &&
903 (Pred.getReg() == AntiDepReg)) {
904 LLVM_DEBUG(dbgs() << " (other dependency)\n")do { } while (false);
905 AntiDepReg = 0;
906 break;
907 }
908 }
909
910 if (AntiDepReg == 0) continue;
911
912 // If the definition of the anti-dependency register does not start
913 // a new live range, bail out. This can happen if the anti-dep
914 // register is a sub-register of another register whose live range
915 // spans over PathSU. In such case, PathSU defines only a part of
916 // the larger register.
917 RegAliases.reset();
918 for (MCRegAliasIterator AI(AntiDepReg, TRI, true); AI.isValid(); ++AI)
919 RegAliases.set(*AI);
920 for (SDep S : PathSU->Succs) {
921 SDep::Kind K = S.getKind();
922 if (K != SDep::Data && K != SDep::Output && K != SDep::Anti)
923 continue;
924 unsigned R = S.getReg();
925 if (!RegAliases[R])
926 continue;
927 if (R == AntiDepReg || TRI->isSubRegister(AntiDepReg, R))
928 continue;
929 AntiDepReg = 0;
930 break;
931 }
932
933 if (AntiDepReg == 0) continue;
934 }
935
936 assert(AntiDepReg != 0)((void)0);
937 if (AntiDepReg == 0) continue;
938
939 // Determine AntiDepReg's register group.
940 const unsigned GroupIndex = State->GetGroup(AntiDepReg);
941 if (GroupIndex == 0) {
942 LLVM_DEBUG(dbgs() << " (zero group)\n")do { } while (false);
943 continue;
944 }
945
946 LLVM_DEBUG(dbgs() << '\n')do { } while (false);
947
948 // Look for a suitable register to use to break the anti-dependence.
949 std::map<unsigned, unsigned> RenameMap;
950 if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
951 LLVM_DEBUG(dbgs() << "\tBreaking anti-dependence edge on "do { } while (false)
952 << printReg(AntiDepReg, TRI) << ":")do { } while (false);
953
954 // Handle each group register...
955 for (const auto &P : RenameMap) {
956 unsigned CurrReg = P.first;
957 unsigned NewReg = P.second;
958
959 LLVM_DEBUG(dbgs() << " " << printReg(CurrReg, TRI) << "->"do { } while (false)
960 << printReg(NewReg, TRI) << "("do { } while (false)
961 << RegRefs.count(CurrReg) << " refs)")do { } while (false);
962
963 // Update the references to the old register CurrReg to
964 // refer to the new register NewReg.
965 for (const auto &Q : make_range(RegRefs.equal_range(CurrReg))) {
966 Q.second.Operand->setReg(NewReg);
967 // If the SU for the instruction being updated has debug
968 // information related to the anti-dependency register, make
969 // sure to update that as well.
970 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()];
971 if (!SU) continue;
972 UpdateDbgValues(DbgValues, Q.second.Operand->getParent(),
973 AntiDepReg, NewReg);
974 }
975
976 // We just went back in time and modified history; the
977 // liveness information for CurrReg is now inconsistent. Set
978 // the state as if it were dead.
979 State->UnionGroups(NewReg, 0);
980 RegRefs.erase(NewReg);
981 DefIndices[NewReg] = DefIndices[CurrReg];
982 KillIndices[NewReg] = KillIndices[CurrReg];
983
984 State->UnionGroups(CurrReg, 0);
985 RegRefs.erase(CurrReg);
986 DefIndices[CurrReg] = KillIndices[CurrReg];
987 KillIndices[CurrReg] = ~0u;
988 assert(((KillIndices[CurrReg] == ~0u) !=((void)0)
989 (DefIndices[CurrReg] == ~0u)) &&((void)0)
990 "Kill and Def maps aren't consistent for AntiDepReg!")((void)0);
991 }
992
993 ++Broken;
994 LLVM_DEBUG(dbgs() << '\n')do { } while (false);
995 }
996 }
997 }
998
999 ScanInstruction(MI, Count);
1000 }
1001
1002 return Broken;
1003}
1004
1005AntiDepBreaker *llvm::createAggressiveAntiDepBreaker(
1006 MachineFunction &MFi, const RegisterClassInfo &RCI,
1007 TargetSubtargetInfo::RegClassVector &CriticalPathRCs) {
1008 return new AggressiveAntiDepBreaker(MFi, RCI, CriticalPathRCs);
1009}