Bug Summary

File:lib/CodeGen/ExecutionDepsFix.cpp
Warning:line 577, column 12
Dereference of null pointer

Annotated Source Code

1//===- ExecutionDepsFix.cpp - Fix execution dependecy issues ----*- C++ -*-===//
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#include "llvm/CodeGen/ExecutionDepsFix.h"
11
12#include "llvm/ADT/PostOrderIterator.h"
13#include "llvm/ADT/iterator_range.h"
14#include "llvm/CodeGen/LivePhysRegs.h"
15#include "llvm/CodeGen/MachineFunctionPass.h"
16#include "llvm/CodeGen/MachineRegisterInfo.h"
17#include "llvm/CodeGen/RegisterClassInfo.h"
18#include "llvm/Support/Allocator.h"
19#include "llvm/Support/Debug.h"
20#include "llvm/Support/raw_ostream.h"
21#include "llvm/Target/TargetInstrInfo.h"
22#include "llvm/Target/TargetSubtargetInfo.h"
23
24using namespace llvm;
25
26#define DEBUG_TYPE"execution-deps-fix" "execution-deps-fix"
27
28/// Translate TRI register number to a list of indices into our smaller tables
29/// of interesting registers.
30iterator_range<SmallVectorImpl<int>::const_iterator>
31ExecutionDepsFix::regIndices(unsigned Reg) const {
32 assert(Reg < AliasMap.size() && "Invalid register")((Reg < AliasMap.size() && "Invalid register") ? static_cast
<void> (0) : __assert_fail ("Reg < AliasMap.size() && \"Invalid register\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 32, __PRETTY_FUNCTION__))
;
33 const auto &Entry = AliasMap[Reg];
34 return make_range(Entry.begin(), Entry.end());
35}
36
37DomainValue *ExecutionDepsFix::alloc(int domain) {
38 DomainValue *dv = Avail.empty() ?
39 new(Allocator.Allocate()) DomainValue :
40 Avail.pop_back_val();
41 if (domain >= 0)
42 dv->addDomain(domain);
43 assert(dv->Refs == 0 && "Reference count wasn't cleared")((dv->Refs == 0 && "Reference count wasn't cleared"
) ? static_cast<void> (0) : __assert_fail ("dv->Refs == 0 && \"Reference count wasn't cleared\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 43, __PRETTY_FUNCTION__))
;
44 assert(!dv->Next && "Chained DomainValue shouldn't have been recycled")((!dv->Next && "Chained DomainValue shouldn't have been recycled"
) ? static_cast<void> (0) : __assert_fail ("!dv->Next && \"Chained DomainValue shouldn't have been recycled\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 44, __PRETTY_FUNCTION__))
;
45 return dv;
46}
47
48/// Release a reference to DV. When the last reference is released,
49/// collapse if needed.
50void ExecutionDepsFix::release(DomainValue *DV) {
51 while (DV) {
52 assert(DV->Refs && "Bad DomainValue")((DV->Refs && "Bad DomainValue") ? static_cast<
void> (0) : __assert_fail ("DV->Refs && \"Bad DomainValue\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 52, __PRETTY_FUNCTION__))
;
53 if (--DV->Refs)
54 return;
55
56 // There are no more DV references. Collapse any contained instructions.
57 if (DV->AvailableDomains && !DV->isCollapsed())
58 collapse(DV, DV->getFirstDomain());
59
60 DomainValue *Next = DV->Next;
61 DV->clear();
62 Avail.push_back(DV);
63 // Also release the next DomainValue in the chain.
64 DV = Next;
65 }
66}
67
68/// Follow the chain of dead DomainValues until a live DomainValue is reached.
69/// Update the referenced pointer when necessary.
70DomainValue *ExecutionDepsFix::resolve(DomainValue *&DVRef) {
71 DomainValue *DV = DVRef;
72 if (!DV || !DV->Next)
73 return DV;
74
75 // DV has a chain. Find the end.
76 do DV = DV->Next;
77 while (DV->Next);
78
79 // Update DVRef to point to DV.
80 retain(DV);
81 release(DVRef);
82 DVRef = DV;
83 return DV;
84}
85
86/// Set LiveRegs[rx] = dv, updating reference counts.
87void ExecutionDepsFix::setLiveReg(int rx, DomainValue *dv) {
88 assert(unsigned(rx) < NumRegs && "Invalid index")((unsigned(rx) < NumRegs && "Invalid index") ? static_cast
<void> (0) : __assert_fail ("unsigned(rx) < NumRegs && \"Invalid index\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 88, __PRETTY_FUNCTION__))
;
89 assert(LiveRegs && "Must enter basic block first.")((LiveRegs && "Must enter basic block first.") ? static_cast
<void> (0) : __assert_fail ("LiveRegs && \"Must enter basic block first.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 89, __PRETTY_FUNCTION__))
;
90
91 if (LiveRegs[rx].Value == dv)
92 return;
93 if (LiveRegs[rx].Value)
94 release(LiveRegs[rx].Value);
95 LiveRegs[rx].Value = retain(dv);
96}
97
98// Kill register rx, recycle or collapse any DomainValue.
99void ExecutionDepsFix::kill(int rx) {
100 assert(unsigned(rx) < NumRegs && "Invalid index")((unsigned(rx) < NumRegs && "Invalid index") ? static_cast
<void> (0) : __assert_fail ("unsigned(rx) < NumRegs && \"Invalid index\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 100, __PRETTY_FUNCTION__))
;
101 assert(LiveRegs && "Must enter basic block first.")((LiveRegs && "Must enter basic block first.") ? static_cast
<void> (0) : __assert_fail ("LiveRegs && \"Must enter basic block first.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 101, __PRETTY_FUNCTION__))
;
102 if (!LiveRegs[rx].Value)
103 return;
104
105 release(LiveRegs[rx].Value);
106 LiveRegs[rx].Value = nullptr;
107}
108
109/// Force register rx into domain.
110void ExecutionDepsFix::force(int rx, unsigned domain) {
111 assert(unsigned(rx) < NumRegs && "Invalid index")((unsigned(rx) < NumRegs && "Invalid index") ? static_cast
<void> (0) : __assert_fail ("unsigned(rx) < NumRegs && \"Invalid index\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 111, __PRETTY_FUNCTION__))
;
112 assert(LiveRegs && "Must enter basic block first.")((LiveRegs && "Must enter basic block first.") ? static_cast
<void> (0) : __assert_fail ("LiveRegs && \"Must enter basic block first.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 112, __PRETTY_FUNCTION__))
;
113 if (DomainValue *dv = LiveRegs[rx].Value) {
114 if (dv->isCollapsed())
115 dv->addDomain(domain);
116 else if (dv->hasDomain(domain))
117 collapse(dv, domain);
118 else {
119 // This is an incompatible open DomainValue. Collapse it to whatever and
120 // force the new value into domain. This costs a domain crossing.
121 collapse(dv, dv->getFirstDomain());
122 assert(LiveRegs[rx].Value && "Not live after collapse?")((LiveRegs[rx].Value && "Not live after collapse?") ?
static_cast<void> (0) : __assert_fail ("LiveRegs[rx].Value && \"Not live after collapse?\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 122, __PRETTY_FUNCTION__))
;
123 LiveRegs[rx].Value->addDomain(domain);
124 }
125 } else {
126 // Set up basic collapsed DomainValue.
127 setLiveReg(rx, alloc(domain));
128 }
129}
130
131/// Collapse open DomainValue into given domain. If there are multiple
132/// registers using dv, they each get a unique collapsed DomainValue.
133void ExecutionDepsFix::collapse(DomainValue *dv, unsigned domain) {
134 assert(dv->hasDomain(domain) && "Cannot collapse")((dv->hasDomain(domain) && "Cannot collapse") ? static_cast
<void> (0) : __assert_fail ("dv->hasDomain(domain) && \"Cannot collapse\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 134, __PRETTY_FUNCTION__))
;
135
136 // Collapse all the instructions.
137 while (!dv->Instrs.empty())
138 TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
139 dv->setSingleDomain(domain);
140
141 // If there are multiple users, give them new, unique DomainValues.
142 if (LiveRegs && dv->Refs > 1)
143 for (unsigned rx = 0; rx != NumRegs; ++rx)
144 if (LiveRegs[rx].Value == dv)
145 setLiveReg(rx, alloc(domain));
146}
147
148/// All instructions and registers in B are moved to A, and B is released.
149bool ExecutionDepsFix::merge(DomainValue *A, DomainValue *B) {
150 assert(!A->isCollapsed() && "Cannot merge into collapsed")((!A->isCollapsed() && "Cannot merge into collapsed"
) ? static_cast<void> (0) : __assert_fail ("!A->isCollapsed() && \"Cannot merge into collapsed\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 150, __PRETTY_FUNCTION__))
;
151 assert(!B->isCollapsed() && "Cannot merge from collapsed")((!B->isCollapsed() && "Cannot merge from collapsed"
) ? static_cast<void> (0) : __assert_fail ("!B->isCollapsed() && \"Cannot merge from collapsed\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 151, __PRETTY_FUNCTION__))
;
152 if (A == B)
153 return true;
154 // Restrict to the domains that A and B have in common.
155 unsigned common = A->getCommonDomains(B->AvailableDomains);
156 if (!common)
157 return false;
158 A->AvailableDomains = common;
159 A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
160
161 // Clear the old DomainValue so we won't try to swizzle instructions twice.
162 B->clear();
163 // All uses of B are referred to A.
164 B->Next = retain(A);
165
166 for (unsigned rx = 0; rx != NumRegs; ++rx) {
167 assert(LiveRegs && "no space allocated for live registers")((LiveRegs && "no space allocated for live registers"
) ? static_cast<void> (0) : __assert_fail ("LiveRegs && \"no space allocated for live registers\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 167, __PRETTY_FUNCTION__))
;
168 if (LiveRegs[rx].Value == B)
169 setLiveReg(rx, A);
170 }
171 return true;
172}
173
174/// Set up LiveRegs by merging predecessor live-out values.
175void ExecutionDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
176 // Reset instruction counter in each basic block.
177 CurInstr = 0;
178
179 // Set up UndefReads to track undefined register reads.
180 UndefReads.clear();
181 LiveRegSet.clear();
182
183 // Set up LiveRegs to represent registers entering MBB.
184 if (!LiveRegs)
185 LiveRegs = new LiveReg[NumRegs];
186
187 // Default values are 'nothing happened a long time ago'.
188 for (unsigned rx = 0; rx != NumRegs; ++rx) {
189 LiveRegs[rx].Value = nullptr;
190 LiveRegs[rx].Def = -(1 << 20);
191 }
192
193 // This is the entry block.
194 if (MBB->pred_empty()) {
195 for (const auto &LI : MBB->liveins()) {
196 for (int rx : regIndices(LI.PhysReg)) {
197 // Treat function live-ins as if they were defined just before the first
198 // instruction. Usually, function arguments are set up immediately
199 // before the call.
200 LiveRegs[rx].Def = -1;
201 }
202 }
203 DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": entry\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "BB#" << MBB->
getNumber() << ": entry\n"; } } while (false)
;
204 return;
205 }
206
207 // Try to coalesce live-out registers from predecessors.
208 for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(),
209 pe = MBB->pred_end(); pi != pe; ++pi) {
210 auto fi = MBBInfos.find(*pi);
211 assert(fi != MBBInfos.end() &&((fi != MBBInfos.end() && "Should have pre-allocated MBBInfos for all MBBs"
) ? static_cast<void> (0) : __assert_fail ("fi != MBBInfos.end() && \"Should have pre-allocated MBBInfos for all MBBs\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 212, __PRETTY_FUNCTION__))
212 "Should have pre-allocated MBBInfos for all MBBs")((fi != MBBInfos.end() && "Should have pre-allocated MBBInfos for all MBBs"
) ? static_cast<void> (0) : __assert_fail ("fi != MBBInfos.end() && \"Should have pre-allocated MBBInfos for all MBBs\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 212, __PRETTY_FUNCTION__))
;
213 LiveReg *Incoming = fi->second.OutRegs;
214 // Incoming is null if this is a backedge from a BB
215 // we haven't processed yet
216 if (Incoming == nullptr) {
217 continue;
218 }
219
220 for (unsigned rx = 0; rx != NumRegs; ++rx) {
221 // Use the most recent predecessor def for each register.
222 LiveRegs[rx].Def = std::max(LiveRegs[rx].Def, Incoming[rx].Def);
223
224 DomainValue *pdv = resolve(Incoming[rx].Value);
225 if (!pdv)
226 continue;
227 if (!LiveRegs[rx].Value) {
228 setLiveReg(rx, pdv);
229 continue;
230 }
231
232 // We have a live DomainValue from more than one predecessor.
233 if (LiveRegs[rx].Value->isCollapsed()) {
234 // We are already collapsed, but predecessor is not. Force it.
235 unsigned Domain = LiveRegs[rx].Value->getFirstDomain();
236 if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
237 collapse(pdv, Domain);
238 continue;
239 }
240
241 // Currently open, merge in predecessor.
242 if (!pdv->isCollapsed())
243 merge(LiveRegs[rx].Value, pdv);
244 else
245 force(rx, pdv->getFirstDomain());
246 }
247 }
248 DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "BB#" << MBB->
getNumber() << (!isBlockDone(MBB) ? ": incomplete\n" : ": all preds known\n"
); } } while (false)
249 dbgs() << "BB#" << MBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "BB#" << MBB->
getNumber() << (!isBlockDone(MBB) ? ": incomplete\n" : ": all preds known\n"
); } } while (false)
250 << (!isBlockDone(MBB) ? ": incomplete\n" : ": all preds known\n"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "BB#" << MBB->
getNumber() << (!isBlockDone(MBB) ? ": incomplete\n" : ": all preds known\n"
); } } while (false)
;
251}
252
253void ExecutionDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) {
254 assert(LiveRegs && "Must enter basic block first.")((LiveRegs && "Must enter basic block first.") ? static_cast
<void> (0) : __assert_fail ("LiveRegs && \"Must enter basic block first.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 254, __PRETTY_FUNCTION__))
;
255 LiveReg *OldOutRegs = MBBInfos[MBB].OutRegs;
256 // Save register clearances at end of MBB - used by enterBasicBlock().
257 MBBInfos[MBB].OutRegs = LiveRegs;
258
259 // While processing the basic block, we kept `Def` relative to the start
260 // of the basic block for convenience. However, future use of this information
261 // only cares about the clearance from the end of the block, so adjust
262 // everything to be relative to the end of the basic block.
263 for (unsigned i = 0, e = NumRegs; i != e; ++i)
264 LiveRegs[i].Def -= CurInstr;
265 if (OldOutRegs) {
266 // This must be the second pass.
267 // Release all the DomainValues instead of keeping them.
268 for (unsigned i = 0, e = NumRegs; i != e; ++i)
269 release(OldOutRegs[i].Value);
270 delete[] OldOutRegs;
271 }
272 LiveRegs = nullptr;
273}
274
275bool ExecutionDepsFix::visitInstr(MachineInstr *MI) {
276 // Update instructions with explicit execution domains.
277 std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
278 if (DomP.first) {
279 if (DomP.second)
280 visitSoftInstr(MI, DomP.second);
281 else
282 visitHardInstr(MI, DomP.first);
283 }
284
285 return !DomP.first;
286}
287
288/// \brief Helps avoid false dependencies on undef registers by updating the
289/// machine instructions' undef operand to use a register that the instruction
290/// is truly dependent on, or use a register with clearance higher than Pref.
291void ExecutionDepsFix::pickBestRegisterForUndef(MachineInstr *MI,
292 unsigned OpIdx, unsigned Pref) {
293 MachineOperand &MO = MI->getOperand(OpIdx);
294 assert(MO.isUndef() && "Expected undef machine operand")((MO.isUndef() && "Expected undef machine operand") ?
static_cast<void> (0) : __assert_fail ("MO.isUndef() && \"Expected undef machine operand\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 294, __PRETTY_FUNCTION__))
;
295
296 unsigned OriginalReg = MO.getReg();
297
298 // Update only undef operands that are mapped to one register.
299 if (AliasMap[OriginalReg].size() != 1)
300 return;
301
302 // Get the undef operand's register class
303 const TargetRegisterClass *OpRC =
304 TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
305
306 // If the instruction has a true dependency, we can hide the false depdency
307 // behind it.
308 for (MachineOperand &CurrMO : MI->operands()) {
309 if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
310 !OpRC->contains(CurrMO.getReg()))
311 continue;
312 // We found a true dependency - replace the undef register with the true
313 // dependency.
314 MO.setReg(CurrMO.getReg());
315 return;
316 }
317
318 // Go over all registers in the register class and find the register with
319 // max clearance or clearance higher than Pref.
320 unsigned MaxClearance = 0;
321 unsigned MaxClearanceReg = OriginalReg;
322 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
323 for (auto Reg : Order) {
324 assert(AliasMap[Reg].size() == 1 &&((AliasMap[Reg].size() == 1 && "Reg is expected to be mapped to a single index"
) ? static_cast<void> (0) : __assert_fail ("AliasMap[Reg].size() == 1 && \"Reg is expected to be mapped to a single index\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 325, __PRETTY_FUNCTION__))
325 "Reg is expected to be mapped to a single index")((AliasMap[Reg].size() == 1 && "Reg is expected to be mapped to a single index"
) ? static_cast<void> (0) : __assert_fail ("AliasMap[Reg].size() == 1 && \"Reg is expected to be mapped to a single index\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 325, __PRETTY_FUNCTION__))
;
326 int RCrx = *regIndices(Reg).begin();
327 unsigned Clearance = CurInstr - LiveRegs[RCrx].Def;
328 if (Clearance <= MaxClearance)
329 continue;
330 MaxClearance = Clearance;
331 MaxClearanceReg = Reg;
332
333 if (MaxClearance > Pref)
334 break;
335 }
336
337 // Update the operand if we found a register with better clearance.
338 if (MaxClearanceReg != OriginalReg)
339 MO.setReg(MaxClearanceReg);
340}
341
342/// \brief Return true to if it makes sense to break dependence on a partial def
343/// or undef use.
344bool ExecutionDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
345 unsigned Pref) {
346 unsigned reg = MI->getOperand(OpIdx).getReg();
347 for (int rx : regIndices(reg)) {
348 unsigned Clearance = CurInstr - LiveRegs[rx].Def;
349 DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "Clearance: " <<
Clearance << ", want " << Pref; } } while (false
)
;
350
351 if (Pref > Clearance) {
352 DEBUG(dbgs() << ": Break dependency.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << ": Break dependency.\n"
; } } while (false)
;
353 continue;
354 }
355 DEBUG(dbgs() << ": OK .\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << ": OK .\n"; } } while
(false)
;
356 return false;
357 }
358 return true;
359}
360
361// Update def-ages for registers defined by MI.
362// If Kill is set, also kill off DomainValues clobbered by the defs.
363//
364// Also break dependencies on partial defs and undef uses.
365void ExecutionDepsFix::processDefs(MachineInstr *MI, bool breakDependency,
366 bool Kill) {
367 assert(!MI->isDebugValue() && "Won't process debug values")((!MI->isDebugValue() && "Won't process debug values"
) ? static_cast<void> (0) : __assert_fail ("!MI->isDebugValue() && \"Won't process debug values\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 367, __PRETTY_FUNCTION__))
;
368
369 // Break dependence on undef uses. Do this before updating LiveRegs below.
370 unsigned OpNum;
371 if (breakDependency) {
372 unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
373 if (Pref) {
374 pickBestRegisterForUndef(MI, OpNum, Pref);
375 if (shouldBreakDependence(MI, OpNum, Pref))
376 UndefReads.push_back(std::make_pair(MI, OpNum));
377 }
378 }
379 const MCInstrDesc &MCID = MI->getDesc();
380 for (unsigned i = 0,
381 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
382 i != e; ++i) {
383 MachineOperand &MO = MI->getOperand(i);
384 if (!MO.isReg())
385 continue;
386 if (MO.isUse())
387 continue;
388 for (int rx : regIndices(MO.getReg())) {
389 // This instruction explicitly defines rx.
390 DEBUG(dbgs() << TRI->getName(RC->getRegister(rx)) << ":\t" << CurInstrdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << TRI->getName(RC->
getRegister(rx)) << ":\t" << CurInstr << '\t'
<< *MI; } } while (false)
391 << '\t' << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << TRI->getName(RC->
getRegister(rx)) << ":\t" << CurInstr << '\t'
<< *MI; } } while (false)
;
392
393 if (breakDependency) {
394 // Check clearance before partial register updates.
395 // Call breakDependence before setting LiveRegs[rx].Def.
396 unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
397 if (Pref && shouldBreakDependence(MI, i, Pref))
398 TII->breakPartialRegDependency(*MI, i, TRI);
399 }
400
401 // How many instructions since rx was last written?
402 LiveRegs[rx].Def = CurInstr;
403
404 // Kill off domains redefined by generic instructions.
405 if (Kill)
406 kill(rx);
407 }
408 }
409 ++CurInstr;
410}
411
412/// \break Break false dependencies on undefined register reads.
413///
414/// Walk the block backward computing precise liveness. This is expensive, so we
415/// only do it on demand. Note that the occurrence of undefined register reads
416/// that should be broken is very rare, but when they occur we may have many in
417/// a single block.
418void ExecutionDepsFix::processUndefReads(MachineBasicBlock *MBB) {
419 if (UndefReads.empty())
420 return;
421
422 // Collect this block's live out register units.
423 LiveRegSet.init(*TRI);
424 // We do not need to care about pristine registers as they are just preserved
425 // but not actually used in the function.
426 LiveRegSet.addLiveOutsNoPristines(*MBB);
427
428 MachineInstr *UndefMI = UndefReads.back().first;
429 unsigned OpIdx = UndefReads.back().second;
430
431 for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
432 // Update liveness, including the current instruction's defs.
433 LiveRegSet.stepBackward(I);
434
435 if (UndefMI == &I) {
436 if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
437 TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
438
439 UndefReads.pop_back();
440 if (UndefReads.empty())
441 return;
442
443 UndefMI = UndefReads.back().first;
444 OpIdx = UndefReads.back().second;
445 }
446 }
447}
448
449// A hard instruction only works in one domain. All input registers will be
450// forced into that domain.
451void ExecutionDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
452 // Collapse all uses.
453 for (unsigned i = mi->getDesc().getNumDefs(),
454 e = mi->getDesc().getNumOperands(); i != e; ++i) {
455 MachineOperand &mo = mi->getOperand(i);
456 if (!mo.isReg()) continue;
457 for (int rx : regIndices(mo.getReg())) {
458 force(rx, domain);
459 }
460 }
461
462 // Kill all defs and force them.
463 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
464 MachineOperand &mo = mi->getOperand(i);
465 if (!mo.isReg()) continue;
466 for (int rx : regIndices(mo.getReg())) {
467 kill(rx);
468 force(rx, domain);
469 }
470 }
471}
472
473// A soft instruction can be changed to work in other domains given by mask.
474void ExecutionDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
475 // Bitmask of available domains for this instruction after taking collapsed
476 // operands into account.
477 unsigned available = mask;
478
479 // Scan the explicit use operands for incoming domains.
480 SmallVector<int, 4> used;
481 if (LiveRegs)
1
Assuming pointer value is null
2
Taking false branch
482 for (unsigned i = mi->getDesc().getNumDefs(),
483 e = mi->getDesc().getNumOperands(); i != e; ++i) {
484 MachineOperand &mo = mi->getOperand(i);
485 if (!mo.isReg()) continue;
486 for (int rx : regIndices(mo.getReg())) {
487 DomainValue *dv = LiveRegs[rx].Value;
488 if (dv == nullptr)
489 continue;
490 // Bitmask of domains that dv and available have in common.
491 unsigned common = dv->getCommonDomains(available);
492 // Is it possible to use this collapsed register for free?
493 if (dv->isCollapsed()) {
494 // Restrict available domains to the ones in common with the operand.
495 // If there are no common domains, we must pay the cross-domain
496 // penalty for this operand.
497 if (common) available = common;
498 } else if (common)
499 // Open DomainValue is compatible, save it for merging.
500 used.push_back(rx);
501 else
502 // Open DomainValue is not compatible with instruction. It is useless
503 // now.
504 kill(rx);
505 }
506 }
507
508 // If the collapsed operands force a single domain, propagate the collapse.
509 if (isPowerOf2_32(available)) {
3
Taking false branch
510 unsigned domain = countTrailingZeros(available);
511 TII->setExecutionDomain(*mi, domain);
512 visitHardInstr(mi, domain);
513 return;
514 }
515
516 // Kill off any remaining uses that don't match available, and build a list of
517 // incoming DomainValues that we want to merge.
518 SmallVector<const LiveReg *, 4> Regs;
519 for (int rx : used) {
4
Assuming '__begin' is equal to '__end'
520 assert(LiveRegs && "no space allocated for live registers")((LiveRegs && "no space allocated for live registers"
) ? static_cast<void> (0) : __assert_fail ("LiveRegs && \"no space allocated for live registers\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 520, __PRETTY_FUNCTION__))
;
521 const LiveReg &LR = LiveRegs[rx];
522 // This useless DomainValue could have been missed above.
523 if (!LR.Value->getCommonDomains(available)) {
524 kill(rx);
525 continue;
526 }
527 // Sorted insertion.
528 auto I = std::upper_bound(Regs.begin(), Regs.end(), &LR,
529 [](const LiveReg *LHS, const LiveReg *RHS) {
530 return LHS->Def < RHS->Def;
531 });
532 Regs.insert(I, &LR);
533 }
534
535 // doms are now sorted in order of appearance. Try to merge them all, giving
536 // priority to the latest ones.
537 DomainValue *dv = nullptr;
538 while (!Regs.empty()) {
5
Loop condition is true. Entering loop body
8
Loop condition is true. Entering loop body
14
Loop condition is true. Entering loop body
20
Loop condition is false. Execution continues on line 563
539 if (!dv) {
6
Taking true branch
9
Taking false branch
15
Taking false branch
540 dv = Regs.pop_back_val()->Value;
541 // Force the first dv to match the current instruction.
542 dv->AvailableDomains = dv->getCommonDomains(available);
543 assert(dv->AvailableDomains && "Domain should have been filtered")((dv->AvailableDomains && "Domain should have been filtered"
) ? static_cast<void> (0) : __assert_fail ("dv->AvailableDomains && \"Domain should have been filtered\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 543, __PRETTY_FUNCTION__))
;
544 continue;
7
Execution continues on line 538
545 }
546
547 DomainValue *Latest = Regs.pop_back_val()->Value;
548 // Skip already merged values.
549 if (Latest == dv || Latest->Next)
10
Assuming 'Latest' is not equal to 'dv'
11
Assuming the condition is true
12
Taking true branch
16
Assuming 'Latest' is not equal to 'dv'
17
Assuming the condition is true
18
Taking true branch
550 continue;
13
Execution continues on line 538
19
Execution continues on line 538
551 if (merge(dv, Latest))
552 continue;
553
554 // If latest didn't merge, it is useless now. Kill all registers using it.
555 for (int i : used) {
556 assert(LiveRegs && "no space allocated for live registers")((LiveRegs && "no space allocated for live registers"
) ? static_cast<void> (0) : __assert_fail ("LiveRegs && \"no space allocated for live registers\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 556, __PRETTY_FUNCTION__))
;
557 if (LiveRegs[i].Value == Latest)
558 kill(i);
559 }
560 }
561
562 // dv is the DomainValue we are going to use for this instruction.
563 if (!dv) {
21
Taking false branch
564 dv = alloc();
565 dv->AvailableDomains = available;
566 }
567 dv->Instrs.push_back(mi);
568
569 // Finally set all defs and non-collapsed uses to dv. We must iterate through
570 // all the operators, including imp-def ones.
571 for (MachineInstr::mop_iterator ii = mi->operands_begin(),
22
Loop condition is true. Entering loop body
26
Loop condition is true. Entering loop body
572 ee = mi->operands_end();
573 ii != ee; ++ii) {
25
Assuming 'ii' is not equal to 'ee'
574 MachineOperand &mo = *ii;
575 if (!mo.isReg()) continue;
23
Taking true branch
24
Execution continues on line 573
27
Taking false branch
576 for (int rx : regIndices(mo.getReg())) {
28
Assuming '__begin' is not equal to '__end'
577 if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) {
29
Dereference of null pointer
578 kill(rx);
579 setLiveReg(rx, dv);
580 }
581 }
582 }
583}
584
585void ExecutionDepsFix::processBasicBlock(MachineBasicBlock *MBB,
586 bool PrimaryPass) {
587 enterBasicBlock(MBB);
588 // If this block is not done, it makes little sense to make any decisions
589 // based on clearance information. We need to make a second pass anyway,
590 // and by then we'll have better information, so we can avoid doing the work
591 // to try and break dependencies now.
592 bool breakDependency = isBlockDone(MBB);
593 for (MachineInstr &MI : *MBB) {
594 if (!MI.isDebugValue()) {
595 bool Kill = false;
596 if (PrimaryPass)
597 Kill = visitInstr(&MI);
598 processDefs(&MI, breakDependency, Kill);
599 }
600 }
601 if (breakDependency)
602 processUndefReads(MBB);
603 leaveBasicBlock(MBB);
604}
605
606bool ExecutionDepsFix::isBlockDone(MachineBasicBlock *MBB) {
607 return MBBInfos[MBB].PrimaryCompleted &&
608 MBBInfos[MBB].IncomingCompleted == MBBInfos[MBB].PrimaryIncoming &&
609 MBBInfos[MBB].IncomingProcessed == MBB->pred_size();
610}
611
612void ExecutionDepsFix::updateSuccessors(MachineBasicBlock *MBB, bool Primary) {
613 bool Done = isBlockDone(MBB);
614 for (auto *Succ : MBB->successors()) {
615 if (!isBlockDone(Succ)) {
616 if (Primary) {
617 MBBInfos[Succ].IncomingProcessed++;
618 }
619 if (Done) {
620 MBBInfos[Succ].IncomingCompleted++;
621 }
622 if (isBlockDone(Succ)) {
623 // Perform secondary processing for this successor. See the big comment
624 // in runOnMachineFunction, for an explanation of the iteration order.
625 processBasicBlock(Succ, false);
626 updateSuccessors(Succ, false);
627 }
628 }
629 }
630}
631
632bool ExecutionDepsFix::runOnMachineFunction(MachineFunction &mf) {
633 if (skipFunction(*mf.getFunction()))
634 return false;
635 MF = &mf;
636 TII = MF->getSubtarget().getInstrInfo();
637 TRI = MF->getSubtarget().getRegisterInfo();
638 RegClassInfo.runOnMachineFunction(mf);
639 LiveRegs = nullptr;
640 assert(NumRegs == RC->getNumRegs() && "Bad regclass")((NumRegs == RC->getNumRegs() && "Bad regclass") ?
static_cast<void> (0) : __assert_fail ("NumRegs == RC->getNumRegs() && \"Bad regclass\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/lib/CodeGen/ExecutionDepsFix.cpp"
, 640, __PRETTY_FUNCTION__))
;
641
642 DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
<< TRI->getRegClassName(RC) << " **********\n"
; } } while (false)
643 << TRI->getRegClassName(RC) << " **********\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
<< TRI->getRegClassName(RC) << " **********\n"
; } } while (false)
;
644
645 // If no relevant registers are used in the function, we can skip it
646 // completely.
647 bool anyregs = false;
648 const MachineRegisterInfo &MRI = mf.getRegInfo();
649 for (unsigned Reg : *RC) {
650 if (MRI.isPhysRegUsed(Reg)) {
651 anyregs = true;
652 break;
653 }
654 }
655 if (!anyregs) return false;
656
657 // Initialize the AliasMap on the first use.
658 if (AliasMap.empty()) {
659 // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
660 // therefore the LiveRegs array.
661 AliasMap.resize(TRI->getNumRegs());
662 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
663 for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true);
664 AI.isValid(); ++AI)
665 AliasMap[*AI].push_back(i);
666 }
667
668 // Initialize the MMBInfos
669 for (auto &MBB : mf) {
670 MBBInfo InitialInfo;
671 MBBInfos.insert(std::make_pair(&MBB, InitialInfo));
672 }
673
674 /*
675 * We want to visit every instruction in every basic block in order to update
676 * it's execution domain or break any false dependencies. However, for the
677 * dependency breaking, we need to know clearances from all predecessors
678 * (including any backedges). One way to do so would be to do two complete
679 * passes over all basic blocks/instructions, the first for recording
680 * clearances, the second to break the dependencies. However, for functions
681 * without backedges, or functions with a lot of straight-line code, and
682 * a small loop, that would be a lot of unnecessary work (since only the
683 * BBs that are part of the loop require two passes). As an example,
684 * consider the following loop.
685 *
686 *
687 * PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT
688 * ^ |
689 * +----------------------------------+
690 *
691 * The iteration order is as follows:
692 * Naive: PH A B C D A' B' C' D'
693 * Optimized: PH A B C A' B' C' D
694 *
695 * Note that we avoid processing D twice, because we can entirely process
696 * the predecessors before getting to D. We call a block that is ready
697 * for its second round of processing `done` (isBlockDone). Once we finish
698 * processing some block, we update the counters in MBBInfos and re-process
699 * any successors that are now done.
700 */
701
702 MachineBasicBlock *Entry = &*MF->begin();
703 ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
704 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
705 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
706 MachineBasicBlock *MBB = *MBBI;
707 // N.B: IncomingProcessed and IncomingCompleted were already updated while
708 // processing this block's predecessors.
709 MBBInfos[MBB].PrimaryCompleted = true;
710 MBBInfos[MBB].PrimaryIncoming = MBBInfos[MBB].IncomingProcessed;
711 processBasicBlock(MBB, true);
712 updateSuccessors(MBB, true);
713 }
714
715 // We need to go through again and finalize any blocks that are not done yet.
716 // This is possible if blocks have dead predecessors, so we didn't visit them
717 // above.
718 for (ReversePostOrderTraversal<MachineBasicBlock *>::rpo_iterator
719 MBBI = RPOT.begin(),
720 MBBE = RPOT.end();
721 MBBI != MBBE; ++MBBI) {
722 MachineBasicBlock *MBB = *MBBI;
723 if (!isBlockDone(MBB)) {
724 processBasicBlock(MBB, false);
725 // Don't update successors here. We'll get to them anyway through this
726 // loop.
727 }
728 }
729
730 // Clear the LiveOuts vectors and collapse any remaining DomainValues.
731 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
732 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
733 auto FI = MBBInfos.find(*MBBI);
734 if (FI == MBBInfos.end() || !FI->second.OutRegs)
735 continue;
736 for (unsigned i = 0, e = NumRegs; i != e; ++i)
737 if (FI->second.OutRegs[i].Value)
738 release(FI->second.OutRegs[i].Value);
739 delete[] FI->second.OutRegs;
740 }
741 MBBInfos.clear();
742 UndefReads.clear();
743 Avail.clear();
744 Allocator.DestroyAll();
745
746 return false;
747}