Bug Summary

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

Annotated Source Code

[?] Use j/k keys for keyboard navigation

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/CodeGen/TargetInstrInfo.h"
19#include "llvm/CodeGen/TargetSubtargetInfo.h"
20#include "llvm/Support/Allocator.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/raw_ostream.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")(static_cast <bool> (Reg < AliasMap.size() &&
"Invalid register") ? void (0) : __assert_fail ("Reg < AliasMap.size() && \"Invalid register\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 32, __extension__ __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")(static_cast <bool> (dv->Refs == 0 && "Reference count wasn't cleared"
) ? void (0) : __assert_fail ("dv->Refs == 0 && \"Reference count wasn't cleared\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 43, __extension__ __PRETTY_FUNCTION__))
;
44 assert(!dv->Next && "Chained DomainValue shouldn't have been recycled")(static_cast <bool> (!dv->Next && "Chained DomainValue shouldn't have been recycled"
) ? void (0) : __assert_fail ("!dv->Next && \"Chained DomainValue shouldn't have been recycled\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 44, __extension__ __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")(static_cast <bool> (DV->Refs && "Bad DomainValue"
) ? void (0) : __assert_fail ("DV->Refs && \"Bad DomainValue\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 52, __extension__ __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")(static_cast <bool> (unsigned(rx) < NumRegs &&
"Invalid index") ? void (0) : __assert_fail ("unsigned(rx) < NumRegs && \"Invalid index\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 88, __extension__ __PRETTY_FUNCTION__))
;
89 assert(LiveRegs && "Must enter basic block first.")(static_cast <bool> (LiveRegs && "Must enter basic block first."
) ? void (0) : __assert_fail ("LiveRegs && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 89, __extension__ __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")(static_cast <bool> (unsigned(rx) < NumRegs &&
"Invalid index") ? void (0) : __assert_fail ("unsigned(rx) < NumRegs && \"Invalid index\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 100, __extension__ __PRETTY_FUNCTION__))
;
101 assert(LiveRegs && "Must enter basic block first.")(static_cast <bool> (LiveRegs && "Must enter basic block first."
) ? void (0) : __assert_fail ("LiveRegs && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 101, __extension__ __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")(static_cast <bool> (unsigned(rx) < NumRegs &&
"Invalid index") ? void (0) : __assert_fail ("unsigned(rx) < NumRegs && \"Invalid index\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 111, __extension__ __PRETTY_FUNCTION__))
;
112 assert(LiveRegs && "Must enter basic block first.")(static_cast <bool> (LiveRegs && "Must enter basic block first."
) ? void (0) : __assert_fail ("LiveRegs && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 112, __extension__ __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?")(static_cast <bool> (LiveRegs[rx].Value && "Not live after collapse?"
) ? void (0) : __assert_fail ("LiveRegs[rx].Value && \"Not live after collapse?\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 122, __extension__ __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")(static_cast <bool> (dv->hasDomain(domain) &&
"Cannot collapse") ? void (0) : __assert_fail ("dv->hasDomain(domain) && \"Cannot collapse\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 134, __extension__ __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")(static_cast <bool> (!A->isCollapsed() && "Cannot merge into collapsed"
) ? void (0) : __assert_fail ("!A->isCollapsed() && \"Cannot merge into collapsed\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 150, __extension__ __PRETTY_FUNCTION__))
;
151 assert(!B->isCollapsed() && "Cannot merge from collapsed")(static_cast <bool> (!B->isCollapsed() && "Cannot merge from collapsed"
) ? void (0) : __assert_fail ("!B->isCollapsed() && \"Cannot merge from collapsed\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 151, __extension__ __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")(static_cast <bool> (LiveRegs && "no space allocated for live registers"
) ? void (0) : __assert_fail ("LiveRegs && \"no space allocated for live registers\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 167, __extension__ __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() << printMBBReference(*MBB) << ": entry\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << printMBBReference(*
MBB) << ": 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() &&(static_cast <bool> (fi != MBBInfos.end() && "Should have pre-allocated MBBInfos for all MBBs"
) ? void (0) : __assert_fail ("fi != MBBInfos.end() && \"Should have pre-allocated MBBInfos for all MBBs\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 212, __extension__ __PRETTY_FUNCTION__))
212 "Should have pre-allocated MBBInfos for all MBBs")(static_cast <bool> (fi != MBBInfos.end() && "Should have pre-allocated MBBInfos for all MBBs"
) ? void (0) : __assert_fail ("fi != MBBInfos.end() && \"Should have pre-allocated MBBInfos for all MBBs\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 212, __extension__ __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() << printMBBReference(*
MBB) << (!isBlockDone(MBB) ? ": incomplete\n" : ": all preds known\n"
); } } while (false)
249 dbgs() << printMBBReference(*MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << printMBBReference(*
MBB) << (!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() << printMBBReference(*
MBB) << (!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.")(static_cast <bool> (LiveRegs && "Must enter basic block first."
) ? void (0) : __assert_fail ("LiveRegs && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 254, __extension__ __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")(static_cast <bool> (MO.isUndef() && "Expected undef machine operand"
) ? void (0) : __assert_fail ("MO.isUndef() && \"Expected undef machine operand\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 296, __extension__ __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 &&(static_cast <bool> (AliasMap[Reg].size() == 1 &&
"Reg is expected to be mapped to a single index") ? void (0)
: __assert_fail ("AliasMap[Reg].size() == 1 && \"Reg is expected to be mapped to a single index\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 327, __extension__ __PRETTY_FUNCTION__))
327 "Reg is expected to be mapped to a single index")(static_cast <bool> (AliasMap[Reg].size() == 1 &&
"Reg is expected to be mapped to a single index") ? void (0)
: __assert_fail ("AliasMap[Reg].size() == 1 && \"Reg is expected to be mapped to a single index\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 327, __extension__ __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")(static_cast <bool> (!MI->isDebugValue() && "Won't process debug values"
) ? void (0) : __assert_fail ("!MI->isDebugValue() && \"Won't process debug values\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 371, __extension__ __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() << printReg(RC->getRegister(rx), TRI) << ":\t" << CurInstrdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << printReg(RC->getRegister
(rx), TRI) << ":\t" << CurInstr << '\t' <<
*MI; } } while (false)
398 << '\t' << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << printReg(RC->getRegister
(rx), TRI) << ":\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")(static_cast <bool> (LiveRegs && "no space allocated for live registers"
) ? void (0) : __assert_fail ("LiveRegs && \"no space allocated for live registers\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 527, __extension__ __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 false. Execution continues on line 570
546 if (!dv) {
6
Taking true 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")(static_cast <bool> (dv->AvailableDomains &&
"Domain should have been filtered") ? void (0) : __assert_fail
("dv->AvailableDomains && \"Domain should have been filtered\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 550, __extension__ __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)
557 continue;
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")(static_cast <bool> (LiveRegs && "no space allocated for live registers"
) ? void (0) : __assert_fail ("LiveRegs && \"no space allocated for live registers\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 563, __extension__ __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) {
9
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(),
10
Loop condition is true. Entering loop body
579 ee = mi->operands_end();
580 ii != ee; ++ii) {
581 MachineOperand &mo = *ii;
582 if (!mo.isReg()) continue;
11
Taking false branch
583 for (int rx : regIndices(mo.getReg())) {
12
Assuming '__begin' is not equal to '__end'
584 if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) {
13
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")(static_cast <bool> (NumRegs == RC->getNumRegs() &&
"Bad regclass") ? void (0) : __assert_fail ("NumRegs == RC->getNumRegs() && \"Bad regclass\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/ExecutionDepsFix.cpp"
, 627, __extension__ __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}