Bug Summary

File:lib/CodeGen/ExecutionDepsFix.cpp
Warning:line 584, 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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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~svn301389/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.
291/// Returns true if it was able to find a true dependency, thus not requiring
292/// a dependency breaking instruction regardless of clearance.
293bool ExecutionDepsFix::pickBestRegisterForUndef(MachineInstr *MI,
294 unsigned OpIdx, unsigned Pref) {
295 MachineOperand &MO = MI->getOperand(OpIdx);
296 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~svn301389/lib/CodeGen/ExecutionDepsFix.cpp"
, 296, __PRETTY_FUNCTION__))
;
297
298 unsigned OriginalReg = MO.getReg();
299
300 // Update only undef operands that are mapped to one register.
301 if (AliasMap[OriginalReg].size() != 1)
302 return false;
303
304 // Get the undef operand's register class
305 const TargetRegisterClass *OpRC =
306 TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
307
308 // If the instruction has a true dependency, we can hide the false depdency
309 // behind it.
310 for (MachineOperand &CurrMO : MI->operands()) {
311 if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
312 !OpRC->contains(CurrMO.getReg()))
313 continue;
314 // We found a true dependency - replace the undef register with the true
315 // dependency.
316 MO.setReg(CurrMO.getReg());
317 return true;
318 }
319
320 // Go over all registers in the register class and find the register with
321 // max clearance or clearance higher than Pref.
322 unsigned MaxClearance = 0;
323 unsigned MaxClearanceReg = OriginalReg;
324 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
325 for (auto Reg : Order) {
326 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~svn301389/lib/CodeGen/ExecutionDepsFix.cpp"
, 327, __PRETTY_FUNCTION__))
327 "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~svn301389/lib/CodeGen/ExecutionDepsFix.cpp"
, 327, __PRETTY_FUNCTION__))
;
328 int RCrx = *regIndices(Reg).begin();
329 unsigned Clearance = CurInstr - LiveRegs[RCrx].Def;
330 if (Clearance <= MaxClearance)
331 continue;
332 MaxClearance = Clearance;
333 MaxClearanceReg = Reg;
334
335 if (MaxClearance > Pref)
336 break;
337 }
338
339 // Update the operand if we found a register with better clearance.
340 if (MaxClearanceReg != OriginalReg)
341 MO.setReg(MaxClearanceReg);
342
343 return false;
344}
345
346/// \brief Return true to if it makes sense to break dependence on a partial def
347/// or undef use.
348bool ExecutionDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
349 unsigned Pref) {
350 unsigned reg = MI->getOperand(OpIdx).getReg();
351 for (int rx : regIndices(reg)) {
352 unsigned Clearance = CurInstr - LiveRegs[rx].Def;
353 DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "Clearance: " <<
Clearance << ", want " << Pref; } } while (false
)
;
354
355 if (Pref > Clearance) {
356 DEBUG(dbgs() << ": Break dependency.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << ": Break dependency.\n"
; } } while (false)
;
357 continue;
358 }
359 DEBUG(dbgs() << ": OK .\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << ": OK .\n"; } } while
(false)
;
360 return false;
361 }
362 return true;
363}
364
365// Update def-ages for registers defined by MI.
366// If Kill is set, also kill off DomainValues clobbered by the defs.
367//
368// Also break dependencies on partial defs and undef uses.
369void ExecutionDepsFix::processDefs(MachineInstr *MI, bool breakDependency,
370 bool Kill) {
371 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~svn301389/lib/CodeGen/ExecutionDepsFix.cpp"
, 371, __PRETTY_FUNCTION__))
;
372
373 // Break dependence on undef uses. Do this before updating LiveRegs below.
374 unsigned OpNum;
375 if (breakDependency) {
376 unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
377 if (Pref) {
378 bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
379 // We don't need to bother trying to break a dependency if this
380 // instruction has a true dependency on that register through another
381 // operand - we'll have to wait for it to be available regardless.
382 if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref))
383 UndefReads.push_back(std::make_pair(MI, OpNum));
384 }
385 }
386 const MCInstrDesc &MCID = MI->getDesc();
387 for (unsigned i = 0,
388 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
389 i != e; ++i) {
390 MachineOperand &MO = MI->getOperand(i);
391 if (!MO.isReg())
392 continue;
393 if (MO.isUse())
394 continue;
395 for (int rx : regIndices(MO.getReg())) {
396 // This instruction explicitly defines rx.
397 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)
398 << '\t' << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << TRI->getName(RC->
getRegister(rx)) << ":\t" << CurInstr << '\t'
<< *MI; } } while (false)
;
399
400 if (breakDependency) {
401 // Check clearance before partial register updates.
402 // Call breakDependence before setting LiveRegs[rx].Def.
403 unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
404 if (Pref && shouldBreakDependence(MI, i, Pref))
405 TII->breakPartialRegDependency(*MI, i, TRI);
406 }
407
408 // How many instructions since rx was last written?
409 LiveRegs[rx].Def = CurInstr;
410
411 // Kill off domains redefined by generic instructions.
412 if (Kill)
413 kill(rx);
414 }
415 }
416 ++CurInstr;
417}
418
419/// \break Break false dependencies on undefined register reads.
420///
421/// Walk the block backward computing precise liveness. This is expensive, so we
422/// only do it on demand. Note that the occurrence of undefined register reads
423/// that should be broken is very rare, but when they occur we may have many in
424/// a single block.
425void ExecutionDepsFix::processUndefReads(MachineBasicBlock *MBB) {
426 if (UndefReads.empty())
427 return;
428
429 // Collect this block's live out register units.
430 LiveRegSet.init(*TRI);
431 // We do not need to care about pristine registers as they are just preserved
432 // but not actually used in the function.
433 LiveRegSet.addLiveOutsNoPristines(*MBB);
434
435 MachineInstr *UndefMI = UndefReads.back().first;
436 unsigned OpIdx = UndefReads.back().second;
437
438 for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
439 // Update liveness, including the current instruction's defs.
440 LiveRegSet.stepBackward(I);
441
442 if (UndefMI == &I) {
443 if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
444 TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
445
446 UndefReads.pop_back();
447 if (UndefReads.empty())
448 return;
449
450 UndefMI = UndefReads.back().first;
451 OpIdx = UndefReads.back().second;
452 }
453 }
454}
455
456// A hard instruction only works in one domain. All input registers will be
457// forced into that domain.
458void ExecutionDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
459 // Collapse all uses.
460 for (unsigned i = mi->getDesc().getNumDefs(),
461 e = mi->getDesc().getNumOperands(); i != e; ++i) {
462 MachineOperand &mo = mi->getOperand(i);
463 if (!mo.isReg()) continue;
464 for (int rx : regIndices(mo.getReg())) {
465 force(rx, domain);
466 }
467 }
468
469 // Kill all defs and force them.
470 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
471 MachineOperand &mo = mi->getOperand(i);
472 if (!mo.isReg()) continue;
473 for (int rx : regIndices(mo.getReg())) {
474 kill(rx);
475 force(rx, domain);
476 }
477 }
478}
479
480// A soft instruction can be changed to work in other domains given by mask.
481void ExecutionDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
482 // Bitmask of available domains for this instruction after taking collapsed
483 // operands into account.
484 unsigned available = mask;
485
486 // Scan the explicit use operands for incoming domains.
487 SmallVector<int, 4> used;
488 if (LiveRegs)
1
Assuming pointer value is null
2
Taking false branch
489 for (unsigned i = mi->getDesc().getNumDefs(),
490 e = mi->getDesc().getNumOperands(); i != e; ++i) {
491 MachineOperand &mo = mi->getOperand(i);
492 if (!mo.isReg()) continue;
493 for (int rx : regIndices(mo.getReg())) {
494 DomainValue *dv = LiveRegs[rx].Value;
495 if (dv == nullptr)
496 continue;
497 // Bitmask of domains that dv and available have in common.
498 unsigned common = dv->getCommonDomains(available);
499 // Is it possible to use this collapsed register for free?
500 if (dv->isCollapsed()) {
501 // Restrict available domains to the ones in common with the operand.
502 // If there are no common domains, we must pay the cross-domain
503 // penalty for this operand.
504 if (common) available = common;
505 } else if (common)
506 // Open DomainValue is compatible, save it for merging.
507 used.push_back(rx);
508 else
509 // Open DomainValue is not compatible with instruction. It is useless
510 // now.
511 kill(rx);
512 }
513 }
514
515 // If the collapsed operands force a single domain, propagate the collapse.
516 if (isPowerOf2_32(available)) {
3
Taking false branch
517 unsigned domain = countTrailingZeros(available);
518 TII->setExecutionDomain(*mi, domain);
519 visitHardInstr(mi, domain);
520 return;
521 }
522
523 // Kill off any remaining uses that don't match available, and build a list of
524 // incoming DomainValues that we want to merge.
525 SmallVector<const LiveReg *, 4> Regs;
526 for (int rx : used) {
4
Assuming '__begin' is equal to '__end'
527 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~svn301389/lib/CodeGen/ExecutionDepsFix.cpp"
, 527, __PRETTY_FUNCTION__))
;
528 const LiveReg &LR = LiveRegs[rx];
529 // This useless DomainValue could have been missed above.
530 if (!LR.Value->getCommonDomains(available)) {
531 kill(rx);
532 continue;
533 }
534 // Sorted insertion.
535 auto I = std::upper_bound(Regs.begin(), Regs.end(), &LR,
536 [](const LiveReg *LHS, const LiveReg *RHS) {
537 return LHS->Def < RHS->Def;
538 });
539 Regs.insert(I, &LR);
540 }
541
542 // doms are now sorted in order of appearance. Try to merge them all, giving
543 // priority to the latest ones.
544 DomainValue *dv = nullptr;
545 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 570
546 if (!dv) {
6
Taking true branch
9
Taking false branch
15
Taking false branch
547 dv = Regs.pop_back_val()->Value;
548 // Force the first dv to match the current instruction.
549 dv->AvailableDomains = dv->getCommonDomains(available);
550 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~svn301389/lib/CodeGen/ExecutionDepsFix.cpp"
, 550, __PRETTY_FUNCTION__))
;
551 continue;
7
Execution continues on line 545
552 }
553
554 DomainValue *Latest = Regs.pop_back_val()->Value;
555 // Skip already merged values.
556 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
557 continue;
13
Execution continues on line 545
19
Execution continues on line 545
558 if (merge(dv, Latest))
559 continue;
560
561 // If latest didn't merge, it is useless now. Kill all registers using it.
562 for (int i : used) {
563 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~svn301389/lib/CodeGen/ExecutionDepsFix.cpp"
, 563, __PRETTY_FUNCTION__))
;
564 if (LiveRegs[i].Value == Latest)
565 kill(i);
566 }
567 }
568
569 // dv is the DomainValue we are going to use for this instruction.
570 if (!dv) {
21
Taking false branch
571 dv = alloc();
572 dv->AvailableDomains = available;
573 }
574 dv->Instrs.push_back(mi);
575
576 // Finally set all defs and non-collapsed uses to dv. We must iterate through
577 // all the operators, including imp-def ones.
578 for (MachineInstr::mop_iterator ii = mi->operands_begin(),
22
Loop condition is true. Entering loop body
26
Loop condition is true. Entering loop body
579 ee = mi->operands_end();
580 ii != ee; ++ii) {
25
Assuming 'ii' is not equal to 'ee'
581 MachineOperand &mo = *ii;
582 if (!mo.isReg()) continue;
23
Taking true branch
24
Execution continues on line 580
27
Taking false branch
583 for (int rx : regIndices(mo.getReg())) {
28
Assuming '__begin' is not equal to '__end'
584 if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) {
29
Dereference of null pointer
585 kill(rx);
586 setLiveReg(rx, dv);
587 }
588 }
589 }
590}
591
592void ExecutionDepsFix::processBasicBlock(MachineBasicBlock *MBB,
593 bool PrimaryPass) {
594 enterBasicBlock(MBB);
595 // If this block is not done, it makes little sense to make any decisions
596 // based on clearance information. We need to make a second pass anyway,
597 // and by then we'll have better information, so we can avoid doing the work
598 // to try and break dependencies now.
599 bool breakDependency = isBlockDone(MBB);
600 for (MachineInstr &MI : *MBB) {
601 if (!MI.isDebugValue()) {
602 bool Kill = false;
603 if (PrimaryPass)
604 Kill = visitInstr(&MI);
605 processDefs(&MI, breakDependency, Kill);
606 }
607 }
608 if (breakDependency)
609 processUndefReads(MBB);
610 leaveBasicBlock(MBB);
611}
612
613bool ExecutionDepsFix::isBlockDone(MachineBasicBlock *MBB) {
614 return MBBInfos[MBB].PrimaryCompleted &&
615 MBBInfos[MBB].IncomingCompleted == MBBInfos[MBB].PrimaryIncoming &&
616 MBBInfos[MBB].IncomingProcessed == MBB->pred_size();
617}
618
619bool ExecutionDepsFix::runOnMachineFunction(MachineFunction &mf) {
620 if (skipFunction(*mf.getFunction()))
621 return false;
622 MF = &mf;
623 TII = MF->getSubtarget().getInstrInfo();
624 TRI = MF->getSubtarget().getRegisterInfo();
625 RegClassInfo.runOnMachineFunction(mf);
626 LiveRegs = nullptr;
627 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~svn301389/lib/CodeGen/ExecutionDepsFix.cpp"
, 627, __PRETTY_FUNCTION__))
;
628
629 DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
<< TRI->getRegClassName(RC) << " **********\n"
; } } while (false)
630 << TRI->getRegClassName(RC) << " **********\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
<< TRI->getRegClassName(RC) << " **********\n"
; } } while (false)
;
631
632 // If no relevant registers are used in the function, we can skip it
633 // completely.
634 bool anyregs = false;
635 const MachineRegisterInfo &MRI = mf.getRegInfo();
636 for (unsigned Reg : *RC) {
637 if (MRI.isPhysRegUsed(Reg)) {
638 anyregs = true;
639 break;
640 }
641 }
642 if (!anyregs) return false;
643
644 // Initialize the AliasMap on the first use.
645 if (AliasMap.empty()) {
646 // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
647 // therefore the LiveRegs array.
648 AliasMap.resize(TRI->getNumRegs());
649 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
650 for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true);
651 AI.isValid(); ++AI)
652 AliasMap[*AI].push_back(i);
653 }
654
655 // Initialize the MMBInfos
656 for (auto &MBB : mf) {
657 MBBInfo InitialInfo;
658 MBBInfos.insert(std::make_pair(&MBB, InitialInfo));
659 }
660
661 /*
662 * We want to visit every instruction in every basic block in order to update
663 * it's execution domain or break any false dependencies. However, for the
664 * dependency breaking, we need to know clearances from all predecessors
665 * (including any backedges). One way to do so would be to do two complete
666 * passes over all basic blocks/instructions, the first for recording
667 * clearances, the second to break the dependencies. However, for functions
668 * without backedges, or functions with a lot of straight-line code, and
669 * a small loop, that would be a lot of unnecessary work (since only the
670 * BBs that are part of the loop require two passes). As an example,
671 * consider the following loop.
672 *
673 *
674 * PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT
675 * ^ |
676 * +----------------------------------+
677 *
678 * The iteration order is as follows:
679 * Naive: PH A B C D A' B' C' D'
680 * Optimized: PH A B C A' B' C' D
681 *
682 * Note that we avoid processing D twice, because we can entirely process
683 * the predecessors before getting to D. We call a block that is ready
684 * for its second round of processing `done` (isBlockDone). Once we finish
685 * processing some block, we update the counters in MBBInfos and re-process
686 * any successors that are now done.
687 */
688
689 MachineBasicBlock *Entry = &*MF->begin();
690 ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
691 SmallVector<MachineBasicBlock *, 4> Workqueue;
692 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
693 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
694 MachineBasicBlock *MBB = *MBBI;
695 // N.B: IncomingProcessed and IncomingCompleted were already updated while
696 // processing this block's predecessors.
697 MBBInfos[MBB].PrimaryCompleted = true;
698 MBBInfos[MBB].PrimaryIncoming = MBBInfos[MBB].IncomingProcessed;
699 bool Primary = true;
700 Workqueue.push_back(MBB);
701 while (!Workqueue.empty()) {
702 MachineBasicBlock *ActiveMBB = &*Workqueue.back();
703 Workqueue.pop_back();
704 processBasicBlock(ActiveMBB, Primary);
705 bool Done = isBlockDone(ActiveMBB);
706 for (auto *Succ : ActiveMBB->successors()) {
707 if (!isBlockDone(Succ)) {
708 if (Primary) {
709 MBBInfos[Succ].IncomingProcessed++;
710 }
711 if (Done) {
712 MBBInfos[Succ].IncomingCompleted++;
713 }
714 if (isBlockDone(Succ)) {
715 Workqueue.push_back(Succ);
716 }
717 }
718 }
719 Primary = false;
720 }
721 }
722
723 // We need to go through again and finalize any blocks that are not done yet.
724 // This is possible if blocks have dead predecessors, so we didn't visit them
725 // above.
726 for (ReversePostOrderTraversal<MachineBasicBlock *>::rpo_iterator
727 MBBI = RPOT.begin(),
728 MBBE = RPOT.end();
729 MBBI != MBBE; ++MBBI) {
730 MachineBasicBlock *MBB = *MBBI;
731 if (!isBlockDone(MBB)) {
732 processBasicBlock(MBB, false);
733 // Don't update successors here. We'll get to them anyway through this
734 // loop.
735 }
736 }
737
738 // Clear the LiveOuts vectors and collapse any remaining DomainValues.
739 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
740 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
741 auto FI = MBBInfos.find(*MBBI);
742 if (FI == MBBInfos.end() || !FI->second.OutRegs)
743 continue;
744 for (unsigned i = 0, e = NumRegs; i != e; ++i)
745 if (FI->second.OutRegs[i].Value)
746 release(FI->second.OutRegs[i].Value);
747 delete[] FI->second.OutRegs;
748 }
749 MBBInfos.clear();
750 UndefReads.clear();
751 Avail.clear();
752 Allocator.DestroyAll();
753
754 return false;
755}