Bug Summary

File:include/llvm/CodeGen/ExecutionDomainFix.h
Warning:line 85, column 60
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'unsigned int'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ExecutionDomainFix.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/lib/gcc/x86_64-linux-gnu/8/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/CodeGen -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp -faddrsig

/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp

1//===- ExecutionDomainFix.cpp - Fix execution domain 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/ExecutionDomainFix.h"
11#include "llvm/CodeGen/MachineRegisterInfo.h"
12#include "llvm/CodeGen/TargetInstrInfo.h"
13
14using namespace llvm;
15
16#define DEBUG_TYPE"execution-deps-fix" "execution-deps-fix"
17
18iterator_range<SmallVectorImpl<int>::const_iterator>
19ExecutionDomainFix::regIndices(unsigned Reg) const {
20 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 20, __extension__ __PRETTY_FUNCTION__))
;
21 const auto &Entry = AliasMap[Reg];
22 return make_range(Entry.begin(), Entry.end());
23}
24
25DomainValue *ExecutionDomainFix::alloc(int domain) {
26 DomainValue *dv = Avail.empty() ? new (Allocator.Allocate()) DomainValue
27 : Avail.pop_back_val();
28 if (domain >= 0)
29 dv->addDomain(domain);
30 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 30, __extension__ __PRETTY_FUNCTION__))
;
31 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 31, __extension__ __PRETTY_FUNCTION__))
;
32 return dv;
33}
34
35void ExecutionDomainFix::release(DomainValue *DV) {
36 while (DV) {
37 assert(DV->Refs && "Bad DomainValue")(static_cast <bool> (DV->Refs && "Bad DomainValue"
) ? void (0) : __assert_fail ("DV->Refs && \"Bad DomainValue\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 37, __extension__ __PRETTY_FUNCTION__))
;
38 if (--DV->Refs)
39 return;
40
41 // There are no more DV references. Collapse any contained instructions.
42 if (DV->AvailableDomains && !DV->isCollapsed())
43 collapse(DV, DV->getFirstDomain());
44
45 DomainValue *Next = DV->Next;
46 DV->clear();
47 Avail.push_back(DV);
48 // Also release the next DomainValue in the chain.
49 DV = Next;
50 }
51}
52
53DomainValue *ExecutionDomainFix::resolve(DomainValue *&DVRef) {
54 DomainValue *DV = DVRef;
55 if (!DV || !DV->Next)
56 return DV;
57
58 // DV has a chain. Find the end.
59 do
60 DV = DV->Next;
61 while (DV->Next);
62
63 // Update DVRef to point to DV.
64 retain(DV);
65 release(DVRef);
66 DVRef = DV;
67 return DV;
68}
69
70void ExecutionDomainFix::setLiveReg(int rx, DomainValue *dv) {
71 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 71, __extension__ __PRETTY_FUNCTION__))
;
72 assert(!LiveRegs.empty() && "Must enter basic block first.")(static_cast <bool> (!LiveRegs.empty() && "Must enter basic block first."
) ? void (0) : __assert_fail ("!LiveRegs.empty() && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 72, __extension__ __PRETTY_FUNCTION__))
;
73
74 if (LiveRegs[rx] == dv)
75 return;
76 if (LiveRegs[rx])
77 release(LiveRegs[rx]);
78 LiveRegs[rx] = retain(dv);
79}
80
81void ExecutionDomainFix::kill(int rx) {
82 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 82, __extension__ __PRETTY_FUNCTION__))
;
83 assert(!LiveRegs.empty() && "Must enter basic block first.")(static_cast <bool> (!LiveRegs.empty() && "Must enter basic block first."
) ? void (0) : __assert_fail ("!LiveRegs.empty() && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 83, __extension__ __PRETTY_FUNCTION__))
;
84 if (!LiveRegs[rx])
85 return;
86
87 release(LiveRegs[rx]);
88 LiveRegs[rx] = nullptr;
89}
90
91void ExecutionDomainFix::force(int rx, unsigned domain) {
92 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 92, __extension__ __PRETTY_FUNCTION__))
;
93 assert(!LiveRegs.empty() && "Must enter basic block first.")(static_cast <bool> (!LiveRegs.empty() && "Must enter basic block first."
) ? void (0) : __assert_fail ("!LiveRegs.empty() && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 93, __extension__ __PRETTY_FUNCTION__))
;
94 if (DomainValue *dv = LiveRegs[rx]) {
28
Assuming 'dv' is non-null
29
Taking true branch
95 if (dv->isCollapsed())
30
Taking true branch
96 dv->addDomain(domain);
31
Calling 'DomainValue::addDomain'
97 else if (dv->hasDomain(domain))
98 collapse(dv, domain);
99 else {
100 // This is an incompatible open DomainValue. Collapse it to whatever and
101 // force the new value into domain. This costs a domain crossing.
102 collapse(dv, dv->getFirstDomain());
103 assert(LiveRegs[rx] && "Not live after collapse?")(static_cast <bool> (LiveRegs[rx] && "Not live after collapse?"
) ? void (0) : __assert_fail ("LiveRegs[rx] && \"Not live after collapse?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 103, __extension__ __PRETTY_FUNCTION__))
;
104 LiveRegs[rx]->addDomain(domain);
105 }
106 } else {
107 // Set up basic collapsed DomainValue.
108 setLiveReg(rx, alloc(domain));
109 }
110}
111
112void ExecutionDomainFix::collapse(DomainValue *dv, unsigned domain) {
113 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 113, __extension__ __PRETTY_FUNCTION__))
;
114
115 // Collapse all the instructions.
116 while (!dv->Instrs.empty())
117 TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
118 dv->setSingleDomain(domain);
119
120 // If there are multiple users, give them new, unique DomainValues.
121 if (!LiveRegs.empty() && dv->Refs > 1)
122 for (unsigned rx = 0; rx != NumRegs; ++rx)
123 if (LiveRegs[rx] == dv)
124 setLiveReg(rx, alloc(domain));
125}
126
127bool ExecutionDomainFix::merge(DomainValue *A, DomainValue *B) {
128 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 128, __extension__ __PRETTY_FUNCTION__))
;
129 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 129, __extension__ __PRETTY_FUNCTION__))
;
130 if (A == B)
131 return true;
132 // Restrict to the domains that A and B have in common.
133 unsigned common = A->getCommonDomains(B->AvailableDomains);
134 if (!common)
135 return false;
136 A->AvailableDomains = common;
137 A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
138
139 // Clear the old DomainValue so we won't try to swizzle instructions twice.
140 B->clear();
141 // All uses of B are referred to A.
142 B->Next = retain(A);
143
144 for (unsigned rx = 0; rx != NumRegs; ++rx) {
145 assert(!LiveRegs.empty() && "no space allocated for live registers")(static_cast <bool> (!LiveRegs.empty() && "no space allocated for live registers"
) ? void (0) : __assert_fail ("!LiveRegs.empty() && \"no space allocated for live registers\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 145, __extension__ __PRETTY_FUNCTION__))
;
146 if (LiveRegs[rx] == B)
147 setLiveReg(rx, A);
148 }
149 return true;
150}
151
152void ExecutionDomainFix::enterBasicBlock(
153 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
154
155 MachineBasicBlock *MBB = TraversedMBB.MBB;
156
157 // Set up LiveRegs to represent registers entering MBB.
158 // Set default domain values to 'no domain' (nullptr)
159 if (LiveRegs.empty())
13
Assuming the condition is false
14
Taking false branch
160 LiveRegs.assign(NumRegs, nullptr);
161
162 // This is the entry block.
163 if (MBB->pred_empty()) {
15
Assuming the condition is false
16
Taking false branch
164 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << printMBBReference(*
MBB) << ": entry\n"; } } while (false)
;
165 return;
166 }
167
168 // Try to coalesce live-out registers from predecessors.
169 for (MachineBasicBlock *pred : MBB->predecessors()) {
170 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&(static_cast <bool> (unsigned(pred->getNumber()) <
MBBOutRegsInfos.size() && "Should have pre-allocated MBBInfos for all MBBs"
) ? void (0) : __assert_fail ("unsigned(pred->getNumber()) < MBBOutRegsInfos.size() && \"Should have pre-allocated MBBInfos for all MBBs\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 171, __extension__ __PRETTY_FUNCTION__))
171 "Should have pre-allocated MBBInfos for all MBBs")(static_cast <bool> (unsigned(pred->getNumber()) <
MBBOutRegsInfos.size() && "Should have pre-allocated MBBInfos for all MBBs"
) ? void (0) : __assert_fail ("unsigned(pred->getNumber()) < MBBOutRegsInfos.size() && \"Should have pre-allocated MBBInfos for all MBBs\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 171, __extension__ __PRETTY_FUNCTION__))
;
172 LiveRegsDVInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
173 // Incoming is null if this is a backedge from a BB
174 // we haven't processed yet
175 if (Incoming.empty())
17
Assuming the condition is false
18
Taking false branch
176 continue;
177
178 for (unsigned rx = 0; rx != NumRegs; ++rx) {
19
Assuming the condition is true
20
Loop condition is true. Entering loop body
179 DomainValue *pdv = resolve(Incoming[rx]);
180 if (!pdv)
21
Assuming 'pdv' is non-null
22
Taking false branch
181 continue;
182 if (!LiveRegs[rx]) {
23
Assuming the condition is false
24
Taking false branch
183 setLiveReg(rx, pdv);
184 continue;
185 }
186
187 // We have a live DomainValue from more than one predecessor.
188 if (LiveRegs[rx]->isCollapsed()) {
25
Taking false branch
189 // We are already collapsed, but predecessor is not. Force it.
190 unsigned Domain = LiveRegs[rx]->getFirstDomain();
191 if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
192 collapse(pdv, Domain);
193 continue;
194 }
195
196 // Currently open, merge in predecessor.
197 if (!pdv->isCollapsed())
26
Taking false branch
198 merge(LiveRegs[rx], pdv);
199 else
200 force(rx, pdv->getFirstDomain());
27
Calling 'ExecutionDomainFix::force'
201 }
202 }
203 LLVM_DEBUG(dbgs() << printMBBReference(*MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << printMBBReference(*
MBB) << (!TraversedMBB.IsDone ? ": incomplete\n" : ": all preds known\n"
); } } while (false)
204 << (!TraversedMBB.IsDone ? ": incomplete\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << printMBBReference(*
MBB) << (!TraversedMBB.IsDone ? ": incomplete\n" : ": all preds known\n"
); } } while (false)
205 : ": all preds known\n"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << printMBBReference(*
MBB) << (!TraversedMBB.IsDone ? ": incomplete\n" : ": all preds known\n"
); } } while (false)
;
206}
207
208void ExecutionDomainFix::leaveBasicBlock(
209 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
210 assert(!LiveRegs.empty() && "Must enter basic block first.")(static_cast <bool> (!LiveRegs.empty() && "Must enter basic block first."
) ? void (0) : __assert_fail ("!LiveRegs.empty() && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 210, __extension__ __PRETTY_FUNCTION__))
;
211 unsigned MBBNumber = TraversedMBB.MBB->getNumber();
212 assert(MBBNumber < MBBOutRegsInfos.size() &&(static_cast <bool> (MBBNumber < MBBOutRegsInfos.size
() && "Unexpected basic block number.") ? void (0) : __assert_fail
("MBBNumber < MBBOutRegsInfos.size() && \"Unexpected basic block number.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 213, __extension__ __PRETTY_FUNCTION__))
213 "Unexpected basic block number.")(static_cast <bool> (MBBNumber < MBBOutRegsInfos.size
() && "Unexpected basic block number.") ? void (0) : __assert_fail
("MBBNumber < MBBOutRegsInfos.size() && \"Unexpected basic block number.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 213, __extension__ __PRETTY_FUNCTION__))
;
214 // Save register clearances at end of MBB - used by enterBasicBlock().
215 for (DomainValue *OldLiveReg : MBBOutRegsInfos[MBBNumber]) {
216 release(OldLiveReg);
217 }
218 MBBOutRegsInfos[MBBNumber] = LiveRegs;
219 LiveRegs.clear();
220}
221
222bool ExecutionDomainFix::visitInstr(MachineInstr *MI) {
223 // Update instructions with explicit execution domains.
224 std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
225 if (DomP.first) {
226 if (DomP.second)
227 visitSoftInstr(MI, DomP.second);
228 else
229 visitHardInstr(MI, DomP.first);
230 }
231
232 return !DomP.first;
233}
234
235void ExecutionDomainFix::processDefs(MachineInstr *MI, bool Kill) {
236 assert(!MI->isDebugInstr() && "Won't process debug values")(static_cast <bool> (!MI->isDebugInstr() && "Won't process debug values"
) ? void (0) : __assert_fail ("!MI->isDebugInstr() && \"Won't process debug values\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 236, __extension__ __PRETTY_FUNCTION__))
;
237 const MCInstrDesc &MCID = MI->getDesc();
238 for (unsigned i = 0,
239 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
240 i != e; ++i) {
241 MachineOperand &MO = MI->getOperand(i);
242 if (!MO.isReg())
243 continue;
244 if (MO.isUse())
245 continue;
246 for (int rx : regIndices(MO.getReg())) {
247 // This instruction explicitly defines rx.
248 LLVM_DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << printReg(RC->getRegister
(rx), TRI) << ":\t" << *MI; } } while (false)
;
249
250 // Kill off domains redefined by generic instructions.
251 if (Kill)
252 kill(rx);
253 }
254 }
255}
256
257void ExecutionDomainFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
258 // Collapse all uses.
259 for (unsigned i = mi->getDesc().getNumDefs(),
260 e = mi->getDesc().getNumOperands();
261 i != e; ++i) {
262 MachineOperand &mo = mi->getOperand(i);
263 if (!mo.isReg())
264 continue;
265 for (int rx : regIndices(mo.getReg())) {
266 force(rx, domain);
267 }
268 }
269
270 // Kill all defs and force them.
271 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
272 MachineOperand &mo = mi->getOperand(i);
273 if (!mo.isReg())
274 continue;
275 for (int rx : regIndices(mo.getReg())) {
276 kill(rx);
277 force(rx, domain);
278 }
279 }
280}
281
282void ExecutionDomainFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
283 // Bitmask of available domains for this instruction after taking collapsed
284 // operands into account.
285 unsigned available = mask;
286
287 // Scan the explicit use operands for incoming domains.
288 SmallVector<int, 4> used;
289 if (!LiveRegs.empty())
290 for (unsigned i = mi->getDesc().getNumDefs(),
291 e = mi->getDesc().getNumOperands();
292 i != e; ++i) {
293 MachineOperand &mo = mi->getOperand(i);
294 if (!mo.isReg())
295 continue;
296 for (int rx : regIndices(mo.getReg())) {
297 DomainValue *dv = LiveRegs[rx];
298 if (dv == nullptr)
299 continue;
300 // Bitmask of domains that dv and available have in common.
301 unsigned common = dv->getCommonDomains(available);
302 // Is it possible to use this collapsed register for free?
303 if (dv->isCollapsed()) {
304 // Restrict available domains to the ones in common with the operand.
305 // If there are no common domains, we must pay the cross-domain
306 // penalty for this operand.
307 if (common)
308 available = common;
309 } else if (common)
310 // Open DomainValue is compatible, save it for merging.
311 used.push_back(rx);
312 else
313 // Open DomainValue is not compatible with instruction. It is useless
314 // now.
315 kill(rx);
316 }
317 }
318
319 // If the collapsed operands force a single domain, propagate the collapse.
320 if (isPowerOf2_32(available)) {
321 unsigned domain = countTrailingZeros(available);
322 TII->setExecutionDomain(*mi, domain);
323 visitHardInstr(mi, domain);
324 return;
325 }
326
327 // Kill off any remaining uses that don't match available, and build a list of
328 // incoming DomainValues that we want to merge.
329 SmallVector<int, 4> Regs;
330 for (int rx : used) {
331 assert(!LiveRegs.empty() && "no space allocated for live registers")(static_cast <bool> (!LiveRegs.empty() && "no space allocated for live registers"
) ? void (0) : __assert_fail ("!LiveRegs.empty() && \"no space allocated for live registers\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 331, __extension__ __PRETTY_FUNCTION__))
;
332 DomainValue *&LR = LiveRegs[rx];
333 // This useless DomainValue could have been missed above.
334 if (!LR->getCommonDomains(available)) {
335 kill(rx);
336 continue;
337 }
338 // Sorted insertion.
339 // Enables giving priority to the latest domains during merging.
340 auto I = std::upper_bound(
341 Regs.begin(), Regs.end(), rx, [&](int LHS, const int RHS) {
342 return RDA->getReachingDef(mi, RC->getRegister(LHS)) <
343 RDA->getReachingDef(mi, RC->getRegister(RHS));
344 });
345 Regs.insert(I, rx);
346 }
347
348 // doms are now sorted in order of appearance. Try to merge them all, giving
349 // priority to the latest ones.
350 DomainValue *dv = nullptr;
351 while (!Regs.empty()) {
352 if (!dv) {
353 dv = LiveRegs[Regs.pop_back_val()];
354 // Force the first dv to match the current instruction.
355 dv->AvailableDomains = dv->getCommonDomains(available);
356 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 356, __extension__ __PRETTY_FUNCTION__))
;
357 continue;
358 }
359
360 DomainValue *Latest = LiveRegs[Regs.pop_back_val()];
361 // Skip already merged values.
362 if (Latest == dv || Latest->Next)
363 continue;
364 if (merge(dv, Latest))
365 continue;
366
367 // If latest didn't merge, it is useless now. Kill all registers using it.
368 for (int i : used) {
369 assert(!LiveRegs.empty() && "no space allocated for live registers")(static_cast <bool> (!LiveRegs.empty() && "no space allocated for live registers"
) ? void (0) : __assert_fail ("!LiveRegs.empty() && \"no space allocated for live registers\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 369, __extension__ __PRETTY_FUNCTION__))
;
370 if (LiveRegs[i] == Latest)
371 kill(i);
372 }
373 }
374
375 // dv is the DomainValue we are going to use for this instruction.
376 if (!dv) {
377 dv = alloc();
378 dv->AvailableDomains = available;
379 }
380 dv->Instrs.push_back(mi);
381
382 // Finally set all defs and non-collapsed uses to dv. We must iterate through
383 // all the operators, including imp-def ones.
384 for (MachineOperand &mo : mi->operands()) {
385 if (!mo.isReg())
386 continue;
387 for (int rx : regIndices(mo.getReg())) {
388 if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx] != dv)) {
389 kill(rx);
390 setLiveReg(rx, dv);
391 }
392 }
393 }
394}
395
396void ExecutionDomainFix::processBasicBlock(
397 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
398 enterBasicBlock(TraversedMBB);
12
Calling 'ExecutionDomainFix::enterBasicBlock'
399 // If this block is not done, it makes little sense to make any decisions
400 // based on clearance information. We need to make a second pass anyway,
401 // and by then we'll have better information, so we can avoid doing the work
402 // to try and break dependencies now.
403 for (MachineInstr &MI : *TraversedMBB.MBB) {
404 if (!MI.isDebugInstr()) {
405 bool Kill = false;
406 if (TraversedMBB.PrimaryPass)
407 Kill = visitInstr(&MI);
408 processDefs(&MI, Kill);
409 }
410 }
411 leaveBasicBlock(TraversedMBB);
412}
413
414bool ExecutionDomainFix::runOnMachineFunction(MachineFunction &mf) {
415 if (skipFunction(mf.getFunction()))
1
Assuming the condition is false
2
Taking false branch
416 return false;
417 MF = &mf;
418 TII = MF->getSubtarget().getInstrInfo();
419 TRI = MF->getSubtarget().getRegisterInfo();
420 LiveRegs.clear();
421 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-7~svn338205/lib/CodeGen/ExecutionDomainFix.cpp"
, 421, __extension__ __PRETTY_FUNCTION__))
;
422
423 LLVM_DEBUG(dbgs() << "********** FIX EXECUTION DOMAIN: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "********** FIX EXECUTION DOMAIN: "
<< TRI->getRegClassName(RC) << " **********\n"
; } } while (false)
424 << TRI->getRegClassName(RC) << " **********\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("execution-deps-fix")) { dbgs() << "********** FIX EXECUTION DOMAIN: "
<< TRI->getRegClassName(RC) << " **********\n"
; } } while (false)
;
425
426 // If no relevant registers are used in the function, we can skip it
427 // completely.
428 bool anyregs = false;
429 const MachineRegisterInfo &MRI = mf.getRegInfo();
430 for (unsigned Reg : *RC) {
3
Assuming '__begin1' is not equal to '__end1'
431 if (MRI.isPhysRegUsed(Reg)) {
4
Assuming the condition is true
5
Taking true branch
432 anyregs = true;
433 break;
6
Execution continues on line 436
434 }
435 }
436 if (!anyregs)
7
Taking false branch
437 return false;
438
439 RDA = &getAnalysis<ReachingDefAnalysis>();
440
441 // Initialize the AliasMap on the first use.
442 if (AliasMap.empty()) {
8
Assuming the condition is false
9
Taking false branch
443 // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
444 // therefore the LiveRegs array.
445 AliasMap.resize(TRI->getNumRegs());
446 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
447 for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); AI.isValid();
448 ++AI)
449 AliasMap[*AI].push_back(i);
450 }
451
452 // Initialize the MBBOutRegsInfos
453 MBBOutRegsInfos.resize(mf.getNumBlockIDs());
454
455 // Traverse the basic blocks.
456 LoopTraversal Traversal;
457 LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
458 for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
10
Assuming '__begin1' is not equal to '__end1'
459 processBasicBlock(TraversedMBB);
11
Calling 'ExecutionDomainFix::processBasicBlock'
460 }
461
462 for (LiveRegsDVInfo OutLiveRegs : MBBOutRegsInfos) {
463 for (DomainValue *OutLiveReg : OutLiveRegs) {
464 if (OutLiveReg)
465 release(OutLiveReg);
466 }
467 }
468 MBBOutRegsInfos.clear();
469 Avail.clear();
470 Allocator.DestroyAll();
471
472 return false;
473}

/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/CodeGen/ExecutionDomainFix.h

1//==-- llvm/CodeGen/ExecutionDomainFix.h - Execution Domain Fix -*- 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/// \file Execution Domain Fix pass.
11///
12/// Some X86 SSE instructions like mov, and, or, xor are available in different
13/// variants for different operand types. These variant instructions are
14/// equivalent, but on Nehalem and newer cpus there is extra latency
15/// transferring data between integer and floating point domains. ARM cores
16/// have similar issues when they are configured with both VFP and NEON
17/// pipelines.
18///
19/// This pass changes the variant instructions to minimize domain crossings.
20//
21//===----------------------------------------------------------------------===//
22
23#ifndef LLVM_CODEGEN_EXECUTIONDOMAINFIX_H
24#define LLVM_CODEGEN_EXECUTIONDOMAINFIX_H
25
26#include "llvm/ADT/SmallVector.h"
27#include "llvm/CodeGen/LoopTraversal.h"
28#include "llvm/CodeGen/MachineFunctionPass.h"
29#include "llvm/CodeGen/ReachingDefAnalysis.h"
30#include "llvm/CodeGen/TargetRegisterInfo.h"
31
32namespace llvm {
33
34class MachineBasicBlock;
35class MachineInstr;
36class TargetInstrInfo;
37
38/// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track
39/// of execution domains.
40///
41/// An open DomainValue represents a set of instructions that can still switch
42/// execution domain. Multiple registers may refer to the same open
43/// DomainValue - they will eventually be collapsed to the same execution
44/// domain.
45///
46/// A collapsed DomainValue represents a single register that has been forced
47/// into one of more execution domains. There is a separate collapsed
48/// DomainValue for each register, but it may contain multiple execution
49/// domains. A register value is initially created in a single execution
50/// domain, but if we were forced to pay the penalty of a domain crossing, we
51/// keep track of the fact that the register is now available in multiple
52/// domains.
53struct DomainValue {
54 /// Basic reference counting.
55 unsigned Refs = 0;
56
57 /// Bitmask of available domains. For an open DomainValue, it is the still
58 /// possible domains for collapsing. For a collapsed DomainValue it is the
59 /// domains where the register is available for free.
60 unsigned AvailableDomains;
61
62 /// Pointer to the next DomainValue in a chain. When two DomainValues are
63 /// merged, Victim.Next is set to point to Victor, so old DomainValue
64 /// references can be updated by following the chain.
65 DomainValue *Next;
66
67 /// Twiddleable instructions using or defining these registers.
68 SmallVector<MachineInstr *, 8> Instrs;
69
70 DomainValue() { clear(); }
71
72 /// A collapsed DomainValue has no instructions to twiddle - it simply keeps
73 /// track of the domains where the registers are already available.
74 bool isCollapsed() const { return Instrs.empty(); }
75
76 /// Is domain available?
77 bool hasDomain(unsigned domain) const {
78 assert(domain <(static_cast <bool> (domain < static_cast<unsigned
>(std::numeric_limits<unsigned>::digits) && "undefined behavior"
) ? void (0) : __assert_fail ("domain < static_cast<unsigned>(std::numeric_limits<unsigned>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/CodeGen/ExecutionDomainFix.h"
, 80, __extension__ __PRETTY_FUNCTION__))
79 static_cast<unsigned>(std::numeric_limits<unsigned>::digits) &&(static_cast <bool> (domain < static_cast<unsigned
>(std::numeric_limits<unsigned>::digits) && "undefined behavior"
) ? void (0) : __assert_fail ("domain < static_cast<unsigned>(std::numeric_limits<unsigned>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/CodeGen/ExecutionDomainFix.h"
, 80, __extension__ __PRETTY_FUNCTION__))
80 "undefined behavior")(static_cast <bool> (domain < static_cast<unsigned
>(std::numeric_limits<unsigned>::digits) && "undefined behavior"
) ? void (0) : __assert_fail ("domain < static_cast<unsigned>(std::numeric_limits<unsigned>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/CodeGen/ExecutionDomainFix.h"
, 80, __extension__ __PRETTY_FUNCTION__))
;
81 return AvailableDomains & (1u << domain);
82 }
83
84 /// Mark domain as available.
85 void addDomain(unsigned domain) { AvailableDomains |= 1u << domain; }
32
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'unsigned int'
86
87 // Restrict to a single domain available.
88 void setSingleDomain(unsigned domain) { AvailableDomains = 1u << domain; }
89
90 /// Return bitmask of domains that are available and in mask.
91 unsigned getCommonDomains(unsigned mask) const {
92 return AvailableDomains & mask;
93 }
94
95 /// First domain available.
96 unsigned getFirstDomain() const {
97 return countTrailingZeros(AvailableDomains);
98 }
99
100 /// Clear this DomainValue and point to next which has all its data.
101 void clear() {
102 AvailableDomains = 0;
103 Next = nullptr;
104 Instrs.clear();
105 }
106};
107
108class ExecutionDomainFix : public MachineFunctionPass {
109 SpecificBumpPtrAllocator<DomainValue> Allocator;
110 SmallVector<DomainValue *, 16> Avail;
111
112 const TargetRegisterClass *const RC;
113 MachineFunction *MF;
114 const TargetInstrInfo *TII;
115 const TargetRegisterInfo *TRI;
116 std::vector<SmallVector<int, 1>> AliasMap;
117 const unsigned NumRegs;
118 /// Value currently in each register, or NULL when no value is being tracked.
119 /// This counts as a DomainValue reference.
120 using LiveRegsDVInfo = std::vector<DomainValue *>;
121 LiveRegsDVInfo LiveRegs;
122 /// Keeps domain information for all registers. Note that this
123 /// is different from the usual definition notion of liveness. The CPU
124 /// doesn't care whether or not we consider a register killed.
125 using OutRegsInfoMap = SmallVector<LiveRegsDVInfo, 4>;
126 OutRegsInfoMap MBBOutRegsInfos;
127
128 ReachingDefAnalysis *RDA;
129
130public:
131 ExecutionDomainFix(char &PassID, const TargetRegisterClass &RC)
132 : MachineFunctionPass(PassID), RC(&RC), NumRegs(RC.getNumRegs()) {}
133
134 void getAnalysisUsage(AnalysisUsage &AU) const override {
135 AU.setPreservesAll();
136 AU.addRequired<ReachingDefAnalysis>();
137 MachineFunctionPass::getAnalysisUsage(AU);
138 }
139
140 bool runOnMachineFunction(MachineFunction &MF) override;
141
142 MachineFunctionProperties getRequiredProperties() const override {
143 return MachineFunctionProperties().set(
144 MachineFunctionProperties::Property::NoVRegs);
145 }
146
147private:
148 /// Translate TRI register number to a list of indices into our smaller tables
149 /// of interesting registers.
150 iterator_range<SmallVectorImpl<int>::const_iterator>
151 regIndices(unsigned Reg) const;
152
153 /// DomainValue allocation.
154 DomainValue *alloc(int domain = -1);
155
156 /// Add reference to DV.
157 DomainValue *retain(DomainValue *DV) {
158 if (DV)
159 ++DV->Refs;
160 return DV;
161 }
162
163 /// Release a reference to DV. When the last reference is released,
164 /// collapse if needed.
165 void release(DomainValue *);
166
167 /// Follow the chain of dead DomainValues until a live DomainValue is reached.
168 /// Update the referenced pointer when necessary.
169 DomainValue *resolve(DomainValue *&);
170
171 /// Set LiveRegs[rx] = dv, updating reference counts.
172 void setLiveReg(int rx, DomainValue *DV);
173
174 /// Kill register rx, recycle or collapse any DomainValue.
175 void kill(int rx);
176
177 /// Force register rx into domain.
178 void force(int rx, unsigned domain);
179
180 /// Collapse open DomainValue into given domain. If there are multiple
181 /// registers using dv, they each get a unique collapsed DomainValue.
182 void collapse(DomainValue *dv, unsigned domain);
183
184 /// All instructions and registers in B are moved to A, and B is released.
185 bool merge(DomainValue *A, DomainValue *B);
186
187 /// Set up LiveRegs by merging predecessor live-out values.
188 void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
189
190 /// Update live-out values.
191 void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
192
193 /// Process he given basic block.
194 void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
195
196 /// Visit given insturcion.
197 bool visitInstr(MachineInstr *);
198
199 /// Update def-ages for registers defined by MI.
200 /// If Kill is set, also kill off DomainValues clobbered by the defs.
201 void processDefs(MachineInstr *, bool Kill);
202
203 /// A soft instruction can be changed to work in other domains given by mask.
204 void visitSoftInstr(MachineInstr *, unsigned mask);
205
206 /// A hard instruction only works in one domain. All input registers will be
207 /// forced into that domain.
208 void visitHardInstr(MachineInstr *, unsigned domain);
209};
210
211} // namespace llvm
212
213#endif // LLVM_CODEGEN_EXECUTIONDOMAINFIX_H