Bug Summary

File:include/llvm/CodeGen/ExecutionDomainFix.h
Warning:line 88, column 65
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-config-compatibility-mode=true -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-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn349319/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen -I /build/llvm-toolchain-snapshot-8~svn349319/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn349319/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/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-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn349319/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-8~svn349319=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-12-17-043027-19008-1 -x c++ /build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn349319/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")((Reg < AliasMap.size() && "Invalid register") ? static_cast
<void> (0) : __assert_fail ("Reg < AliasMap.size() && \"Invalid register\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 20, __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")((dv->Refs == 0 && "Reference count wasn't cleared"
) ? static_cast<void> (0) : __assert_fail ("dv->Refs == 0 && \"Reference count wasn't cleared\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 30, __PRETTY_FUNCTION__))
;
31 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\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 31, __PRETTY_FUNCTION__))
;
32 return dv;
33}
34
35void ExecutionDomainFix::release(DomainValue *DV) {
36 while (DV) {
37 assert(DV->Refs && "Bad DomainValue")((DV->Refs && "Bad DomainValue") ? static_cast<
void> (0) : __assert_fail ("DV->Refs && \"Bad DomainValue\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 37, __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")((unsigned(rx) < NumRegs && "Invalid index") ? static_cast
<void> (0) : __assert_fail ("unsigned(rx) < NumRegs && \"Invalid index\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 71, __PRETTY_FUNCTION__))
;
72 assert(!LiveRegs.empty() && "Must enter basic block first.")((!LiveRegs.empty() && "Must enter basic block first."
) ? static_cast<void> (0) : __assert_fail ("!LiveRegs.empty() && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 72, __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")((unsigned(rx) < NumRegs && "Invalid index") ? static_cast
<void> (0) : __assert_fail ("unsigned(rx) < NumRegs && \"Invalid index\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 82, __PRETTY_FUNCTION__))
;
83 assert(!LiveRegs.empty() && "Must enter basic block first.")((!LiveRegs.empty() && "Must enter basic block first."
) ? static_cast<void> (0) : __assert_fail ("!LiveRegs.empty() && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 83, __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")((unsigned(rx) < NumRegs && "Invalid index") ? static_cast
<void> (0) : __assert_fail ("unsigned(rx) < NumRegs && \"Invalid index\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 92, __PRETTY_FUNCTION__))
;
33
Assuming the condition is true
34
'?' condition is true
93 assert(!LiveRegs.empty() && "Must enter basic block first.")((!LiveRegs.empty() && "Must enter basic block first."
) ? static_cast<void> (0) : __assert_fail ("!LiveRegs.empty() && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 93, __PRETTY_FUNCTION__))
;
35
Assuming the condition is true
36
'?' condition is true
94 if (DomainValue *dv = LiveRegs[rx]) {
37
Assuming 'dv' is non-null
38
Taking true branch
95 if (dv->isCollapsed())
39
Taking false branch
96 dv->addDomain(domain);
97 else if (dv->hasDomain(domain))
40
Assuming the condition is false
41
Taking false branch
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());
42
Calling 'DomainValue::getFirstDomain'
52
Returning from 'DomainValue::getFirstDomain'
53
Passing the value 32 via 2nd parameter 'domain'
54
Calling 'ExecutionDomainFix::collapse'
103 assert(LiveRegs[rx] && "Not live after collapse?")((LiveRegs[rx] && "Not live after collapse?") ? static_cast
<void> (0) : __assert_fail ("LiveRegs[rx] && \"Not live after collapse?\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 103, __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")((dv->hasDomain(domain) && "Cannot collapse") ? static_cast
<void> (0) : __assert_fail ("dv->hasDomain(domain) && \"Cannot collapse\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 113, __PRETTY_FUNCTION__))
;
55
Assuming the condition is true
56
'?' condition is true
114
115 // Collapse all the instructions.
116 while (!dv->Instrs.empty())
57
Loop condition is true. Entering loop body
58
Loop condition is false. Execution continues on line 118
117 TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
118 dv->setSingleDomain(domain);
59
Passing the value 32 via 1st parameter 'domain'
60
Calling 'DomainValue::setSingleDomain'
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")((!A->isCollapsed() && "Cannot merge into collapsed"
) ? static_cast<void> (0) : __assert_fail ("!A->isCollapsed() && \"Cannot merge into collapsed\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 128, __PRETTY_FUNCTION__))
;
129 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\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 129, __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")((!LiveRegs.empty() && "no space allocated for live registers"
) ? static_cast<void> (0) : __assert_fail ("!LiveRegs.empty() && \"no space allocated for live registers\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 145, __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())
17
Assuming the condition is false
18
Taking false branch
160 LiveRegs.assign(NumRegs, nullptr);
161
162 // This is the entry block.
163 if (MBB->pred_empty()) {
19
Assuming the condition is false
20
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() &&((unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
"Should have pre-allocated MBBInfos for all MBBs") ? static_cast
<void> (0) : __assert_fail ("unsigned(pred->getNumber()) < MBBOutRegsInfos.size() && \"Should have pre-allocated MBBInfos for all MBBs\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 171, __PRETTY_FUNCTION__))
21
Assuming the condition is true
22
'?' condition is true
171 "Should have pre-allocated MBBInfos for all MBBs")((unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
"Should have pre-allocated MBBInfos for all MBBs") ? static_cast
<void> (0) : __assert_fail ("unsigned(pred->getNumber()) < MBBOutRegsInfos.size() && \"Should have pre-allocated MBBInfos for all MBBs\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 171, __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())
23
Assuming the condition is false
24
Taking false branch
176 continue;
177
178 for (unsigned rx = 0; rx != NumRegs; ++rx) {
25
Assuming the condition is true
26
Loop condition is true. Entering loop body
179 DomainValue *pdv = resolve(Incoming[rx]);
180 if (!pdv)
27
Taking false branch
181 continue;
182 if (!LiveRegs[rx]) {
28
Assuming the condition is false
29
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()) {
30
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())
31
Taking false branch
198 merge(LiveRegs[rx], pdv);
199 else
200 force(rx, pdv->getFirstDomain());
32
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.")((!LiveRegs.empty() && "Must enter basic block first."
) ? static_cast<void> (0) : __assert_fail ("!LiveRegs.empty() && \"Must enter basic block first.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 210, __PRETTY_FUNCTION__))
;
211 unsigned MBBNumber = TraversedMBB.MBB->getNumber();
212 assert(MBBNumber < MBBOutRegsInfos.size() &&((MBBNumber < MBBOutRegsInfos.size() && "Unexpected basic block number."
) ? static_cast<void> (0) : __assert_fail ("MBBNumber < MBBOutRegsInfos.size() && \"Unexpected basic block number.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 213, __PRETTY_FUNCTION__))
213 "Unexpected basic block number.")((MBBNumber < MBBOutRegsInfos.size() && "Unexpected basic block number."
) ? static_cast<void> (0) : __assert_fail ("MBBNumber < MBBOutRegsInfos.size() && \"Unexpected basic block number.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 213, __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")((!MI->isDebugInstr() && "Won't process debug values"
) ? static_cast<void> (0) : __assert_fail ("!MI->isDebugInstr() && \"Won't process debug values\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 236, __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")((!LiveRegs.empty() && "no space allocated for live registers"
) ? static_cast<void> (0) : __assert_fail ("!LiveRegs.empty() && \"no space allocated for live registers\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 331, __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")((dv->AvailableDomains && "Domain should have been filtered"
) ? static_cast<void> (0) : __assert_fail ("dv->AvailableDomains && \"Domain should have been filtered\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 356, __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")((!LiveRegs.empty() && "no space allocated for live registers"
) ? static_cast<void> (0) : __assert_fail ("!LiveRegs.empty() && \"no space allocated for live registers\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 369, __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);
16
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")((NumRegs == RC->getNumRegs() && "Bad regclass") ?
static_cast<void> (0) : __assert_fail ("NumRegs == RC->getNumRegs() && \"Bad regclass\""
, "/build/llvm-toolchain-snapshot-8~svn349319/lib/CodeGen/ExecutionDomainFix.cpp"
, 421, __PRETTY_FUNCTION__))
;
3
Assuming the condition is true
4
'?' condition is true
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)
5
Assuming 'DebugFlag' is 0
6
Loop condition is false. Exiting loop
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) {
7
Assuming '__begin1' is not equal to '__end1'
431 if (MRI.isPhysRegUsed(Reg)) {
8
Assuming the condition is true
9
Taking true branch
432 anyregs = true;
433 break;
10
Execution continues on line 436
434 }
435 }
436 if (!anyregs)
11
Taking false branch
437 return false;
438
439 RDA = &getAnalysis<ReachingDefAnalysis>();
440
441 // Initialize the AliasMap on the first use.
442 if (AliasMap.empty()) {
12
Assuming the condition is false
13
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) {
14
Assuming '__begin1' is not equal to '__end1'
459 processBasicBlock(TraversedMBB);
15
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-8~svn349319/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 <((domain < static_cast<unsigned>(std::numeric_limits
<unsigned>::digits) && "undefined behavior") ? static_cast
<void> (0) : __assert_fail ("domain < static_cast<unsigned>(std::numeric_limits<unsigned>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/CodeGen/ExecutionDomainFix.h"
, 80, __PRETTY_FUNCTION__))
79 static_cast<unsigned>(std::numeric_limits<unsigned>::digits) &&((domain < static_cast<unsigned>(std::numeric_limits
<unsigned>::digits) && "undefined behavior") ? static_cast
<void> (0) : __assert_fail ("domain < static_cast<unsigned>(std::numeric_limits<unsigned>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/CodeGen/ExecutionDomainFix.h"
, 80, __PRETTY_FUNCTION__))
80 "undefined behavior")((domain < static_cast<unsigned>(std::numeric_limits
<unsigned>::digits) && "undefined behavior") ? static_cast
<void> (0) : __assert_fail ("domain < static_cast<unsigned>(std::numeric_limits<unsigned>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/CodeGen/ExecutionDomainFix.h"
, 80, __PRETTY_FUNCTION__))
;
81 return AvailableDomains & (1u << domain);
82 }
83
84 /// Mark domain as available.
85 void addDomain(unsigned domain) { AvailableDomains |= 1u << domain; }
86
87 // Restrict to a single domain available.
88 void setSingleDomain(unsigned domain) { AvailableDomains = 1u << domain; }
61
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'
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);
43
Calling 'countTrailingZeros<unsigned int>'
50
Returning from 'countTrailingZeros<unsigned int>'
51
Returning the value 32
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

/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h

1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- 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// This file contains some functions that are useful for math stuff.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_SUPPORT_MATHEXTRAS_H
15#define LLVM_SUPPORT_MATHEXTRAS_H
16
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/SwapByteOrder.h"
19#include <algorithm>
20#include <cassert>
21#include <climits>
22#include <cstring>
23#include <limits>
24#include <type_traits>
25
26#ifdef __ANDROID_NDK__
27#include <android/api-level.h>
28#endif
29
30#ifdef _MSC_VER
31// Declare these intrinsics manually rather including intrin.h. It's very
32// expensive, and MathExtras.h is popular.
33// #include <intrin.h>
34extern "C" {
35unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
36unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
37unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
38unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
39}
40#endif
41
42namespace llvm {
43/// The behavior an operation has on an input of 0.
44enum ZeroBehavior {
45 /// The returned value is undefined.
46 ZB_Undefined,
47 /// The returned value is numeric_limits<T>::max()
48 ZB_Max,
49 /// The returned value is numeric_limits<T>::digits
50 ZB_Width
51};
52
53namespace detail {
54template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
55 static std::size_t count(T Val, ZeroBehavior) {
56 if (!Val)
57 return std::numeric_limits<T>::digits;
58 if (Val & 0x1)
59 return 0;
60
61 // Bisection method.
62 std::size_t ZeroBits = 0;
63 T Shift = std::numeric_limits<T>::digits >> 1;
64 T Mask = std::numeric_limits<T>::max() >> Shift;
65 while (Shift) {
66 if ((Val & Mask) == 0) {
67 Val >>= Shift;
68 ZeroBits |= Shift;
69 }
70 Shift >>= 1;
71 Mask >>= Shift;
72 }
73 return ZeroBits;
74 }
75};
76
77#if __GNUC__4 >= 4 || defined(_MSC_VER)
78template <typename T> struct TrailingZerosCounter<T, 4> {
79 static std::size_t count(T Val, ZeroBehavior ZB) {
80 if (ZB != ZB_Undefined && Val == 0)
45
Assuming 'Val' is equal to 0
46
Taking true branch
81 return 32;
47
Returning the value 32
82
83#if __has_builtin(__builtin_ctz)1 || LLVM_GNUC_PREREQ(4, 0, 0)((4 << 20) + (2 << 10) + 1 >= ((4) << 20
) + ((0) << 10) + (0))
84 return __builtin_ctz(Val);
85#elif defined(_MSC_VER)
86 unsigned long Index;
87 _BitScanForward(&Index, Val);
88 return Index;
89#endif
90 }
91};
92
93#if !defined(_MSC_VER) || defined(_M_X64)
94template <typename T> struct TrailingZerosCounter<T, 8> {
95 static std::size_t count(T Val, ZeroBehavior ZB) {
96 if (ZB != ZB_Undefined && Val == 0)
97 return 64;
98
99#if __has_builtin(__builtin_ctzll)1 || LLVM_GNUC_PREREQ(4, 0, 0)((4 << 20) + (2 << 10) + 1 >= ((4) << 20
) + ((0) << 10) + (0))
100 return __builtin_ctzll(Val);
101#elif defined(_MSC_VER)
102 unsigned long Index;
103 _BitScanForward64(&Index, Val);
104 return Index;
105#endif
106 }
107};
108#endif
109#endif
110} // namespace detail
111
112/// Count number of 0's from the least significant bit to the most
113/// stopping at the first 1.
114///
115/// Only unsigned integral types are allowed.
116///
117/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
118/// valid arguments.
119template <typename T>
120std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
121 static_assert(std::numeric_limits<T>::is_integer &&
122 !std::numeric_limits<T>::is_signed,
123 "Only unsigned integral types are allowed.");
124 return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
44
Calling 'TrailingZerosCounter::count'
48
Returning from 'TrailingZerosCounter::count'
49
Returning the value 32
125}
126
127namespace detail {
128template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
129 static std::size_t count(T Val, ZeroBehavior) {
130 if (!Val)
131 return std::numeric_limits<T>::digits;
132
133 // Bisection method.
134 std::size_t ZeroBits = 0;
135 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
136 T Tmp = Val >> Shift;
137 if (Tmp)
138 Val = Tmp;
139 else
140 ZeroBits |= Shift;
141 }
142 return ZeroBits;
143 }
144};
145
146#if __GNUC__4 >= 4 || defined(_MSC_VER)
147template <typename T> struct LeadingZerosCounter<T, 4> {
148 static std::size_t count(T Val, ZeroBehavior ZB) {
149 if (ZB != ZB_Undefined && Val == 0)
150 return 32;
151
152#if __has_builtin(__builtin_clz)1 || LLVM_GNUC_PREREQ(4, 0, 0)((4 << 20) + (2 << 10) + 1 >= ((4) << 20
) + ((0) << 10) + (0))
153 return __builtin_clz(Val);
154#elif defined(_MSC_VER)
155 unsigned long Index;
156 _BitScanReverse(&Index, Val);
157 return Index ^ 31;
158#endif
159 }
160};
161
162#if !defined(_MSC_VER) || defined(_M_X64)
163template <typename T> struct LeadingZerosCounter<T, 8> {
164 static std::size_t count(T Val, ZeroBehavior ZB) {
165 if (ZB != ZB_Undefined && Val == 0)
166 return 64;
167
168#if __has_builtin(__builtin_clzll)1 || LLVM_GNUC_PREREQ(4, 0, 0)((4 << 20) + (2 << 10) + 1 >= ((4) << 20
) + ((0) << 10) + (0))
169 return __builtin_clzll(Val);
170#elif defined(_MSC_VER)
171 unsigned long Index;
172 _BitScanReverse64(&Index, Val);
173 return Index ^ 63;
174#endif
175 }
176};
177#endif
178#endif
179} // namespace detail
180
181/// Count number of 0's from the most significant bit to the least
182/// stopping at the first 1.
183///
184/// Only unsigned integral types are allowed.
185///
186/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
187/// valid arguments.
188template <typename T>
189std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
190 static_assert(std::numeric_limits<T>::is_integer &&
191 !std::numeric_limits<T>::is_signed,
192 "Only unsigned integral types are allowed.");
193 return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
194}
195
196/// Get the index of the first set bit starting from the least
197/// significant bit.
198///
199/// Only unsigned integral types are allowed.
200///
201/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
202/// valid arguments.
203template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
204 if (ZB == ZB_Max && Val == 0)
205 return std::numeric_limits<T>::max();
206
207 return countTrailingZeros(Val, ZB_Undefined);
208}
209
210/// Create a bitmask with the N right-most bits set to 1, and all other
211/// bits set to 0. Only unsigned types are allowed.
212template <typename T> T maskTrailingOnes(unsigned N) {
213 static_assert(std::is_unsigned<T>::value, "Invalid type!");
214 const unsigned Bits = CHAR_BIT8 * sizeof(T);
215 assert(N <= Bits && "Invalid bit index")((N <= Bits && "Invalid bit index") ? static_cast<
void> (0) : __assert_fail ("N <= Bits && \"Invalid bit index\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 215, __PRETTY_FUNCTION__))
;
216 return N == 0 ? 0 : (T(-1) >> (Bits - N));
217}
218
219/// Create a bitmask with the N left-most bits set to 1, and all other
220/// bits set to 0. Only unsigned types are allowed.
221template <typename T> T maskLeadingOnes(unsigned N) {
222 return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
223}
224
225/// Create a bitmask with the N right-most bits set to 0, and all other
226/// bits set to 1. Only unsigned types are allowed.
227template <typename T> T maskTrailingZeros(unsigned N) {
228 return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
229}
230
231/// Create a bitmask with the N left-most bits set to 0, and all other
232/// bits set to 1. Only unsigned types are allowed.
233template <typename T> T maskLeadingZeros(unsigned N) {
234 return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
235}
236
237/// Get the index of the last set bit starting from the least
238/// significant bit.
239///
240/// Only unsigned integral types are allowed.
241///
242/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
243/// valid arguments.
244template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
245 if (ZB == ZB_Max && Val == 0)
246 return std::numeric_limits<T>::max();
247
248 // Use ^ instead of - because both gcc and llvm can remove the associated ^
249 // in the __builtin_clz intrinsic on x86.
250 return countLeadingZeros(Val, ZB_Undefined) ^
251 (std::numeric_limits<T>::digits - 1);
252}
253
254/// Macro compressed bit reversal table for 256 bits.
255///
256/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
257static const unsigned char BitReverseTable256[256] = {
258#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
259#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
260#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
261 R6(0), R6(2), R6(1), R6(3)
262#undef R2
263#undef R4
264#undef R6
265};
266
267/// Reverse the bits in \p Val.
268template <typename T>
269T reverseBits(T Val) {
270 unsigned char in[sizeof(Val)];
271 unsigned char out[sizeof(Val)];
272 std::memcpy(in, &Val, sizeof(Val));
273 for (unsigned i = 0; i < sizeof(Val); ++i)
274 out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
275 std::memcpy(&Val, out, sizeof(Val));
276 return Val;
277}
278
279// NOTE: The following support functions use the _32/_64 extensions instead of
280// type overloading so that signed and unsigned integers can be used without
281// ambiguity.
282
283/// Return the high 32 bits of a 64 bit value.
284constexpr inline uint32_t Hi_32(uint64_t Value) {
285 return static_cast<uint32_t>(Value >> 32);
286}
287
288/// Return the low 32 bits of a 64 bit value.
289constexpr inline uint32_t Lo_32(uint64_t Value) {
290 return static_cast<uint32_t>(Value);
291}
292
293/// Make a 64-bit integer from a high / low pair of 32-bit integers.
294constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
295 return ((uint64_t)High << 32) | (uint64_t)Low;
296}
297
298/// Checks if an integer fits into the given bit width.
299template <unsigned N> constexpr inline bool isInt(int64_t x) {
300 return N >= 64 || (-(INT64_C(1)1L<<(N-1)) <= x && x < (INT64_C(1)1L<<(N-1)));
301}
302// Template specializations to get better code for common cases.
303template <> constexpr inline bool isInt<8>(int64_t x) {
304 return static_cast<int8_t>(x) == x;
305}
306template <> constexpr inline bool isInt<16>(int64_t x) {
307 return static_cast<int16_t>(x) == x;
308}
309template <> constexpr inline bool isInt<32>(int64_t x) {
310 return static_cast<int32_t>(x) == x;
311}
312
313/// Checks if a signed integer is an N bit number shifted left by S.
314template <unsigned N, unsigned S>
315constexpr inline bool isShiftedInt(int64_t x) {
316 static_assert(
317 N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
318 static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
319 return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
320}
321
322/// Checks if an unsigned integer fits into the given bit width.
323///
324/// This is written as two functions rather than as simply
325///
326/// return N >= 64 || X < (UINT64_C(1) << N);
327///
328/// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
329/// left too many places.
330template <unsigned N>
331constexpr inline typename std::enable_if<(N < 64), bool>::type
332isUInt(uint64_t X) {
333 static_assert(N > 0, "isUInt<0> doesn't make sense");
334 return X < (UINT64_C(1)1UL << (N));
335}
336template <unsigned N>
337constexpr inline typename std::enable_if<N >= 64, bool>::type
338isUInt(uint64_t X) {
339 return true;
340}
341
342// Template specializations to get better code for common cases.
343template <> constexpr inline bool isUInt<8>(uint64_t x) {
344 return static_cast<uint8_t>(x) == x;
345}
346template <> constexpr inline bool isUInt<16>(uint64_t x) {
347 return static_cast<uint16_t>(x) == x;
348}
349template <> constexpr inline bool isUInt<32>(uint64_t x) {
350 return static_cast<uint32_t>(x) == x;
351}
352
353/// Checks if a unsigned integer is an N bit number shifted left by S.
354template <unsigned N, unsigned S>
355constexpr inline bool isShiftedUInt(uint64_t x) {
356 static_assert(
357 N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358 static_assert(N + S <= 64,
359 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360 // Per the two static_asserts above, S must be strictly less than 64. So
361 // 1 << S is not undefined behavior.
362 return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
363}
364
365/// Gets the maximum value for a N-bit unsigned integer.
366inline uint64_t maxUIntN(uint64_t N) {
367 assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 367, __PRETTY_FUNCTION__))
;
368
369 // uint64_t(1) << 64 is undefined behavior, so we can't do
370 // (uint64_t(1) << N) - 1
371 // without checking first that N != 64. But this works and doesn't have a
372 // branch.
373 return UINT64_MAX(18446744073709551615UL) >> (64 - N);
374}
375
376/// Gets the minimum value for a N-bit signed integer.
377inline int64_t minIntN(int64_t N) {
378 assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 378, __PRETTY_FUNCTION__))
;
379
380 return -(UINT64_C(1)1UL<<(N-1));
381}
382
383/// Gets the maximum value for a N-bit signed integer.
384inline int64_t maxIntN(int64_t N) {
385 assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 385, __PRETTY_FUNCTION__))
;
386
387 // This relies on two's complement wraparound when N == 64, so we convert to
388 // int64_t only at the very end to avoid UB.
389 return (UINT64_C(1)1UL << (N - 1)) - 1;
390}
391
392/// Checks if an unsigned integer fits into the given (dynamic) bit width.
393inline bool isUIntN(unsigned N, uint64_t x) {
394 return N >= 64 || x <= maxUIntN(N);
395}
396
397/// Checks if an signed integer fits into the given (dynamic) bit width.
398inline bool isIntN(unsigned N, int64_t x) {
399 return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
400}
401
402/// Return true if the argument is a non-empty sequence of ones starting at the
403/// least significant bit with the remainder zero (32 bit version).
404/// Ex. isMask_32(0x0000FFFFU) == true.
405constexpr inline bool isMask_32(uint32_t Value) {
406 return Value && ((Value + 1) & Value) == 0;
407}
408
409/// Return true if the argument is a non-empty sequence of ones starting at the
410/// least significant bit with the remainder zero (64 bit version).
411constexpr inline bool isMask_64(uint64_t Value) {
412 return Value && ((Value + 1) & Value) == 0;
413}
414
415/// Return true if the argument contains a non-empty sequence of ones with the
416/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
417constexpr inline bool isShiftedMask_32(uint32_t Value) {
418 return Value && isMask_32((Value - 1) | Value);
419}
420
421/// Return true if the argument contains a non-empty sequence of ones with the
422/// remainder zero (64 bit version.)
423constexpr inline bool isShiftedMask_64(uint64_t Value) {
424 return Value && isMask_64((Value - 1) | Value);
425}
426
427/// Return true if the argument is a power of two > 0.
428/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
429constexpr inline bool isPowerOf2_32(uint32_t Value) {
430 return Value && !(Value & (Value - 1));
431}
432
433/// Return true if the argument is a power of two > 0 (64 bit edition.)
434constexpr inline bool isPowerOf2_64(uint64_t Value) {
435 return Value && !(Value & (Value - 1));
436}
437
438/// Return a byte-swapped representation of the 16-bit argument.
439inline uint16_t ByteSwap_16(uint16_t Value) {
440 return sys::SwapByteOrder_16(Value);
441}
442
443/// Return a byte-swapped representation of the 32-bit argument.
444inline uint32_t ByteSwap_32(uint32_t Value) {
445 return sys::SwapByteOrder_32(Value);
446}
447
448/// Return a byte-swapped representation of the 64-bit argument.
449inline uint64_t ByteSwap_64(uint64_t Value) {
450 return sys::SwapByteOrder_64(Value);
451}
452
453/// Count the number of ones from the most significant bit to the first
454/// zero bit.
455///
456/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
457/// Only unsigned integral types are allowed.
458///
459/// \param ZB the behavior on an input of all ones. Only ZB_Width and
460/// ZB_Undefined are valid arguments.
461template <typename T>
462std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
463 static_assert(std::numeric_limits<T>::is_integer &&
464 !std::numeric_limits<T>::is_signed,
465 "Only unsigned integral types are allowed.");
466 return countLeadingZeros<T>(~Value, ZB);
467}
468
469/// Count the number of ones from the least significant bit to the first
470/// zero bit.
471///
472/// Ex. countTrailingOnes(0x00FF00FF) == 8.
473/// Only unsigned integral types are allowed.
474///
475/// \param ZB the behavior on an input of all ones. Only ZB_Width and
476/// ZB_Undefined are valid arguments.
477template <typename T>
478std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
479 static_assert(std::numeric_limits<T>::is_integer &&
480 !std::numeric_limits<T>::is_signed,
481 "Only unsigned integral types are allowed.");
482 return countTrailingZeros<T>(~Value, ZB);
483}
484
485namespace detail {
486template <typename T, std::size_t SizeOfT> struct PopulationCounter {
487 static unsigned count(T Value) {
488 // Generic version, forward to 32 bits.
489 static_assert(SizeOfT <= 4, "Not implemented!");
490#if __GNUC__4 >= 4
491 return __builtin_popcount(Value);
492#else
493 uint32_t v = Value;
494 v = v - ((v >> 1) & 0x55555555);
495 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
496 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
497#endif
498 }
499};
500
501template <typename T> struct PopulationCounter<T, 8> {
502 static unsigned count(T Value) {
503#if __GNUC__4 >= 4
504 return __builtin_popcountll(Value);
505#else
506 uint64_t v = Value;
507 v = v - ((v >> 1) & 0x5555555555555555ULL);
508 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
509 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
510 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
511#endif
512 }
513};
514} // namespace detail
515
516/// Count the number of set bits in a value.
517/// Ex. countPopulation(0xF000F000) = 8
518/// Returns 0 if the word is zero.
519template <typename T>
520inline unsigned countPopulation(T Value) {
521 static_assert(std::numeric_limits<T>::is_integer &&
522 !std::numeric_limits<T>::is_signed,
523 "Only unsigned integral types are allowed.");
524 return detail::PopulationCounter<T, sizeof(T)>::count(Value);
525}
526
527/// Return the log base 2 of the specified value.
528inline double Log2(double Value) {
529#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
530 return __builtin_log(Value) / __builtin_log(2.0);
531#else
532 return log2(Value);
533#endif
534}
535
536/// Return the floor log base 2 of the specified value, -1 if the value is zero.
537/// (32 bit edition.)
538/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
539inline unsigned Log2_32(uint32_t Value) {
540 return 31 - countLeadingZeros(Value);
541}
542
543/// Return the floor log base 2 of the specified value, -1 if the value is zero.
544/// (64 bit edition.)
545inline unsigned Log2_64(uint64_t Value) {
546 return 63 - countLeadingZeros(Value);
547}
548
549/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
550/// (32 bit edition).
551/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
552inline unsigned Log2_32_Ceil(uint32_t Value) {
553 return 32 - countLeadingZeros(Value - 1);
554}
555
556/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
557/// (64 bit edition.)
558inline unsigned Log2_64_Ceil(uint64_t Value) {
559 return 64 - countLeadingZeros(Value - 1);
560}
561
562/// Return the greatest common divisor of the values using Euclid's algorithm.
563inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
564 while (B) {
565 uint64_t T = B;
566 B = A % B;
567 A = T;
568 }
569 return A;
570}
571
572/// This function takes a 64-bit integer and returns the bit equivalent double.
573inline double BitsToDouble(uint64_t Bits) {
574 double D;
575 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
576 memcpy(&D, &Bits, sizeof(Bits));
577 return D;
578}
579
580/// This function takes a 32-bit integer and returns the bit equivalent float.
581inline float BitsToFloat(uint32_t Bits) {
582 float F;
583 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
584 memcpy(&F, &Bits, sizeof(Bits));
585 return F;
586}
587
588/// This function takes a double and returns the bit equivalent 64-bit integer.
589/// Note that copying doubles around changes the bits of NaNs on some hosts,
590/// notably x86, so this routine cannot be used if these bits are needed.
591inline uint64_t DoubleToBits(double Double) {
592 uint64_t Bits;
593 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
594 memcpy(&Bits, &Double, sizeof(Double));
595 return Bits;
596}
597
598/// This function takes a float and returns the bit equivalent 32-bit integer.
599/// Note that copying floats around changes the bits of NaNs on some hosts,
600/// notably x86, so this routine cannot be used if these bits are needed.
601inline uint32_t FloatToBits(float Float) {
602 uint32_t Bits;
603 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
604 memcpy(&Bits, &Float, sizeof(Float));
605 return Bits;
606}
607
608/// A and B are either alignments or offsets. Return the minimum alignment that
609/// may be assumed after adding the two together.
610constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
611 // The largest power of 2 that divides both A and B.
612 //
613 // Replace "-Value" by "1+~Value" in the following commented code to avoid
614 // MSVC warning C4146
615 // return (A | B) & -(A | B);
616 return (A | B) & (1 + ~(A | B));
617}
618
619/// Aligns \c Addr to \c Alignment bytes, rounding up.
620///
621/// Alignment should be a power of two. This method rounds up, so
622/// alignAddr(7, 4) == 8 and alignAddr(8, 4) == 8.
623inline uintptr_t alignAddr(const void *Addr, size_t Alignment) {
624 assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&((Alignment && isPowerOf2_64((uint64_t)Alignment) &&
"Alignment is not a power of two!") ? static_cast<void>
(0) : __assert_fail ("Alignment && isPowerOf2_64((uint64_t)Alignment) && \"Alignment is not a power of two!\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 625, __PRETTY_FUNCTION__))
625 "Alignment is not a power of two!")((Alignment && isPowerOf2_64((uint64_t)Alignment) &&
"Alignment is not a power of two!") ? static_cast<void>
(0) : __assert_fail ("Alignment && isPowerOf2_64((uint64_t)Alignment) && \"Alignment is not a power of two!\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 625, __PRETTY_FUNCTION__))
;
626
627 assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr)(((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr) ? static_cast
<void> (0) : __assert_fail ("(uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr"
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 627, __PRETTY_FUNCTION__))
;
628
629 return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
630}
631
632/// Returns the necessary adjustment for aligning \c Ptr to \c Alignment
633/// bytes, rounding up.
634inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) {
635 return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
636}
637
638/// Returns the next power of two (in 64-bits) that is strictly greater than A.
639/// Returns zero on overflow.
640inline uint64_t NextPowerOf2(uint64_t A) {
641 A |= (A >> 1);
642 A |= (A >> 2);
643 A |= (A >> 4);
644 A |= (A >> 8);
645 A |= (A >> 16);
646 A |= (A >> 32);
647 return A + 1;
648}
649
650/// Returns the power of two which is less than or equal to the given value.
651/// Essentially, it is a floor operation across the domain of powers of two.
652inline uint64_t PowerOf2Floor(uint64_t A) {
653 if (!A) return 0;
654 return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
655}
656
657/// Returns the power of two which is greater than or equal to the given value.
658/// Essentially, it is a ceil operation across the domain of powers of two.
659inline uint64_t PowerOf2Ceil(uint64_t A) {
660 if (!A)
661 return 0;
662 return NextPowerOf2(A - 1);
663}
664
665/// Returns the next integer (mod 2**64) that is greater than or equal to
666/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
667///
668/// If non-zero \p Skew is specified, the return value will be a minimal
669/// integer that is greater than or equal to \p Value and equal to
670/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
671/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
672///
673/// Examples:
674/// \code
675/// alignTo(5, 8) = 8
676/// alignTo(17, 8) = 24
677/// alignTo(~0LL, 8) = 0
678/// alignTo(321, 255) = 510
679///
680/// alignTo(5, 8, 7) = 7
681/// alignTo(17, 8, 1) = 17
682/// alignTo(~0LL, 8, 3) = 3
683/// alignTo(321, 255, 42) = 552
684/// \endcode
685inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
686 assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 686, __PRETTY_FUNCTION__))
;
687 Skew %= Align;
688 return (Value + Align - 1 - Skew) / Align * Align + Skew;
689}
690
691/// Returns the next integer (mod 2**64) that is greater than or equal to
692/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
693template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
694 static_assert(Align != 0u, "Align must be non-zero");
695 return (Value + Align - 1) / Align * Align;
696}
697
698/// Returns the integer ceil(Numerator / Denominator).
699inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
700 return alignTo(Numerator, Denominator) / Denominator;
701}
702
703/// \c alignTo for contexts where a constant expression is required.
704/// \sa alignTo
705///
706/// \todo FIXME: remove when \c constexpr becomes really \c constexpr
707template <uint64_t Align>
708struct AlignTo {
709 static_assert(Align != 0u, "Align must be non-zero");
710 template <uint64_t Value>
711 struct from_value {
712 static const uint64_t value = (Value + Align - 1) / Align * Align;
713 };
714};
715
716/// Returns the largest uint64_t less than or equal to \p Value and is
717/// \p Skew mod \p Align. \p Align must be non-zero
718inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
719 assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 719, __PRETTY_FUNCTION__))
;
720 Skew %= Align;
721 return (Value - Skew) / Align * Align + Skew;
722}
723
724/// Returns the offset to the next integer (mod 2**64) that is greater than
725/// or equal to \p Value and is a multiple of \p Align. \p Align must be
726/// non-zero.
727inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
728 return alignTo(Value, Align) - Value;
729}
730
731/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
732/// Requires 0 < B <= 32.
733template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
734 static_assert(B > 0, "Bit width can't be 0.");
735 static_assert(B <= 32, "Bit width out of range.");
736 return int32_t(X << (32 - B)) >> (32 - B);
737}
738
739/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
740/// Requires 0 < B < 32.
741inline int32_t SignExtend32(uint32_t X, unsigned B) {
742 assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 742, __PRETTY_FUNCTION__))
;
743 assert(B <= 32 && "Bit width out of range.")((B <= 32 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 32 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 743, __PRETTY_FUNCTION__))
;
744 return int32_t(X << (32 - B)) >> (32 - B);
745}
746
747/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
748/// Requires 0 < B < 64.
749template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
750 static_assert(B > 0, "Bit width can't be 0.");
751 static_assert(B <= 64, "Bit width out of range.");
752 return int64_t(x << (64 - B)) >> (64 - B);
753}
754
755/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
756/// Requires 0 < B < 64.
757inline int64_t SignExtend64(uint64_t X, unsigned B) {
758 assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 758, __PRETTY_FUNCTION__))
;
759 assert(B <= 64 && "Bit width out of range.")((B <= 64 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 64 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-8~svn349319/include/llvm/Support/MathExtras.h"
, 759, __PRETTY_FUNCTION__))
;
760 return int64_t(X << (64 - B)) >> (64 - B);
761}
762
763/// Subtract two unsigned integers, X and Y, of type T and return the absolute
764/// value of the result.
765template <typename T>
766typename std::enable_if<std::is_unsigned<T>::value, T>::type
767AbsoluteDifference(T X, T Y) {
768 return std::max(X, Y) - std::min(X, Y);
769}
770
771/// Add two unsigned integers, X and Y, of type T. Clamp the result to the
772/// maximum representable value of T on overflow. ResultOverflowed indicates if
773/// the result is larger than the maximum representable value of type T.
774template <typename T>
775typename std::enable_if<std::is_unsigned<T>::value, T>::type
776SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
777 bool Dummy;
778 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
779 // Hacker's Delight, p. 29
780 T Z = X + Y;
781 Overflowed = (Z < X || Z < Y);
782 if (Overflowed)
783 return std::numeric_limits<T>::max();
784 else
785 return Z;
786}
787
788/// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the
789/// maximum representable value of T on overflow. ResultOverflowed indicates if
790/// the result is larger than the maximum representable value of type T.
791template <typename T>
792typename std::enable_if<std::is_unsigned<T>::value, T>::type
793SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
794 bool Dummy;
795 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
796
797 // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
798 // because it fails for uint16_t (where multiplication can have undefined
799 // behavior due to promotion to int), and requires a division in addition
800 // to the multiplication.
801
802 Overflowed = false;
803
804 // Log2(Z) would be either Log2Z or Log2Z + 1.
805 // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
806 // will necessarily be less than Log2Max as desired.
807 int Log2Z = Log2_64(X) + Log2_64(Y);
808 const T Max = std::numeric_limits<T>::max();
809 int Log2Max = Log2_64(Max);
810 if (Log2Z < Log2Max) {
811 return X * Y;
812 }
813 if (Log2Z > Log2Max) {
814 Overflowed = true;
815 return Max;
816 }
817
818 // We're going to use the top bit, and maybe overflow one
819 // bit past it. Multiply all but the bottom bit then add
820 // that on at the end.
821 T Z = (X >> 1) * Y;
822 if (Z & ~(Max >> 1)) {
823 Overflowed = true;
824 return Max;
825 }
826 Z <<= 1;
827 if (X & 1)
828 return SaturatingAdd(Z, Y, ResultOverflowed);
829
830 return Z;
831}
832
833/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
834/// the product. Clamp the result to the maximum representable value of T on
835/// overflow. ResultOverflowed indicates if the result is larger than the
836/// maximum representable value of type T.
837template <typename T>
838typename std::enable_if<std::is_unsigned<T>::value, T>::type
839SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
840 bool Dummy;
841 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
842
843 T Product = SaturatingMultiply(X, Y, &Overflowed);
844 if (Overflowed)
845 return Product;
846
847 return SaturatingAdd(A, Product, &Overflowed);
848}
849
850/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
851extern const float huge_valf;
852} // End llvm namespace
853
854#endif