Bug Summary

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