Bug Summary

File:lib/CodeGen/AggressiveAntiDepBreaker.cpp
Warning:line 794, column 22
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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