Bug Summary

File:include/llvm/CodeGen/ExecutionDomainFix.h
Warning:line 84, 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-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 -analyzer-config-compatibility-mode=true -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-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn358520/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-9~svn358520/lib/CodeGen -I /build/llvm-toolchain-snapshot-9~svn358520/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn358520/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/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.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-9~svn358520/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn358520=. -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-2019-04-17-050842-1547-1 -x c++ /build/llvm-toolchain-snapshot-9~svn358520/lib/CodeGen/ExecutionDomainFix.cpp -faddrsig

/build/llvm-toolchain-snapshot-9~svn358520/lib/CodeGen/ExecutionDomainFix.cpp

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

/build/llvm-toolchain-snapshot-9~svn358520/include/llvm/CodeGen/ExecutionDomainFix.h

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

/build/llvm-toolchain-snapshot-9~svn358520/include/llvm/Support/MathExtras.h

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