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 -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-10~svn374877/lib/CodeGen -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn374877/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/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.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++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn374877=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-10-15-233810-7101-1 -x c++ /build/llvm-toolchain-snapshot-10~svn374877/lib/CodeGen/ExecutionDomainFix.cpp

/build/llvm-toolchain-snapshot-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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)
28
Assuming 'DV' is non-null
29
Assuming field 'Next' is null
30
Taking true branch
55 return DV;
31
Returning without writing to 'DVRef->Instrs.Size', which participates in a condition later
32
Returning pointer (loaded from 'DV'), which participates in a condition later
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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/lib/CodeGen/ExecutionDomainFix.cpp"
, 91, __PRETTY_FUNCTION__))
;
67
Assuming 'rx' is < field 'NumRegs'
68
'?' 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-10~svn374877/lib/CodeGen/ExecutionDomainFix.cpp"
, 92, __PRETTY_FUNCTION__))
;
69
Assuming the condition is true
70
'?' condition is true
93 if (DomainValue *dv = LiveRegs[rx]) {
71
Assuming 'dv' is non-null
72
Taking true branch
94 if (dv->isCollapsed())
73
Calling 'DomainValue::isCollapsed'
79
Returning from 'DomainValue::isCollapsed'
80
Taking true branch
95 dv->addDomain(domain);
81
Passing the value 32 via 1st parameter 'domain'
82
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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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 'rx' is not equal to field 'NumRegs'
26
Loop condition is true. Entering loop body
178 DomainValue *pdv = resolve(Incoming[rx]);
27
Calling 'ExecutionDomainFix::resolve'
33
Returning from 'ExecutionDomainFix::resolve'
179 if (!pdv
33.1
'pdv' is non-null
33.1
'pdv' is non-null
33.1
'pdv' is non-null
33.1
'pdv' is non-null
)
34
Taking false branch
180 continue;
181 if (!LiveRegs[rx]) {
35
Assuming pointer value is null
36
Assuming the condition is false
37
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()) {
38
Calling 'DomainValue::isCollapsed'
44
Returning from 'DomainValue::isCollapsed'
45
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())
46
Calling 'DomainValue::isCollapsed'
52
Returning from 'DomainValue::isCollapsed'
53
Taking false branch
197 merge(LiveRegs[rx], pdv);
198 else
199 force(rx, pdv->getFirstDomain());
54
Calling 'DomainValue::getFirstDomain'
64
Returning from 'DomainValue::getFirstDomain'
65
Passing the value 32 via 2nd parameter 'domain'
66
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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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-10~svn374877/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 const int Def = RDA->getReachingDef(mi, RC->getRegister(rx));
340 auto I = partition_point(Regs, [&](int I) {
341 return RDA->getReachingDef(mi, RC->getRegister(I)) <= Def;
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-10~svn374877/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-10~svn374877/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-10~svn374877/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 false
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
10.1
'anyregs' is true
10.1
'anyregs' is true
10.1
'anyregs' is true
10.1
'anyregs' is true
)
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-10~svn374877/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(); }
39
Calling 'SmallVectorBase::empty'
42
Returning from 'SmallVectorBase::empty'
43
Returning zero, which participates in a condition later
47
Calling 'SmallVectorBase::empty'
50
Returning from 'SmallVectorBase::empty'
51
Returning the value 1, which participates in a condition later
74
Calling 'SmallVectorBase::empty'
77
Returning from 'SmallVectorBase::empty'
78
Returning the value 1, which participates in a condition later
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-10~svn374877/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-10~svn374877/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-10~svn374877/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; }
83
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);
55
Calling 'countTrailingZeros<unsigned int>'
62
Returning from 'countTrailingZeros<unsigned int>'
63
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-10~svn374877/include/llvm/ADT/SmallVector.h

1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- 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 defines the SmallVector class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_SMALLVECTOR_H
14#define LLVM_ADT_SMALLVECTOR_H
15
16#include "llvm/ADT/iterator_range.h"
17#include "llvm/Support/AlignOf.h"
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/MathExtras.h"
20#include "llvm/Support/MemAlloc.h"
21#include "llvm/Support/type_traits.h"
22#include "llvm/Support/ErrorHandling.h"
23#include <algorithm>
24#include <cassert>
25#include <cstddef>
26#include <cstdlib>
27#include <cstring>
28#include <initializer_list>
29#include <iterator>
30#include <memory>
31#include <new>
32#include <type_traits>
33#include <utility>
34
35namespace llvm {
36
37/// This is all the non-templated stuff common to all SmallVectors.
38class SmallVectorBase {
39protected:
40 void *BeginX;
41 unsigned Size = 0, Capacity;
42
43 SmallVectorBase() = delete;
44 SmallVectorBase(void *FirstEl, size_t TotalCapacity)
45 : BeginX(FirstEl), Capacity(TotalCapacity) {}
46
47 /// This is an implementation of the grow() method which only works
48 /// on POD-like data types and is out of line to reduce code duplication.
49 void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize);
50
51public:
52 size_t size() const { return Size; }
53 size_t capacity() const { return Capacity; }
54
55 LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; }
40
Assuming field 'Size' is not equal to 0
41
Returning zero, which participates in a condition later
48
Assuming field 'Size' is 0
49
Returning the value 1, which participates in a condition later
75
Assuming field 'Size' is 0
76
Returning the value 1, which participates in a condition later
56
57 /// Set the array size to \p N, which the current array must have enough
58 /// capacity for.
59 ///
60 /// This does not construct or destroy any elements in the vector.
61 ///
62 /// Clients can use this in conjunction with capacity() to write past the end
63 /// of the buffer when they know that more elements are available, and only
64 /// update the size later. This avoids the cost of value initializing elements
65 /// which will only be overwritten.
66 void set_size(size_t N) {
67 assert(N <= capacity())((N <= capacity()) ? static_cast<void> (0) : __assert_fail
("N <= capacity()", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 67, __PRETTY_FUNCTION__))
;
68 Size = N;
69 }
70};
71
72/// Figure out the offset of the first element.
73template <class T, typename = void> struct SmallVectorAlignmentAndSize {
74 AlignedCharArrayUnion<SmallVectorBase> Base;
75 AlignedCharArrayUnion<T> FirstEl;
76};
77
78/// This is the part of SmallVectorTemplateBase which does not depend on whether
79/// the type T is a POD. The extra dummy template argument is used by ArrayRef
80/// to avoid unnecessarily requiring T to be complete.
81template <typename T, typename = void>
82class SmallVectorTemplateCommon : public SmallVectorBase {
83 /// Find the address of the first element. For this pointer math to be valid
84 /// with small-size of 0 for T with lots of alignment, it's important that
85 /// SmallVectorStorage is properly-aligned even for small-size of 0.
86 void *getFirstEl() const {
87 return const_cast<void *>(reinterpret_cast<const void *>(
88 reinterpret_cast<const char *>(this) +
89 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl
)
));
90 }
91 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
92
93protected:
94 SmallVectorTemplateCommon(size_t Size)
95 : SmallVectorBase(getFirstEl(), Size) {}
96
97 void grow_pod(size_t MinCapacity, size_t TSize) {
98 SmallVectorBase::grow_pod(getFirstEl(), MinCapacity, TSize);
99 }
100
101 /// Return true if this is a smallvector which has not had dynamic
102 /// memory allocated for it.
103 bool isSmall() const { return BeginX == getFirstEl(); }
104
105 /// Put this vector in a state of being small.
106 void resetToSmall() {
107 BeginX = getFirstEl();
108 Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
109 }
110
111public:
112 using size_type = size_t;
113 using difference_type = ptrdiff_t;
114 using value_type = T;
115 using iterator = T *;
116 using const_iterator = const T *;
117
118 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
119 using reverse_iterator = std::reverse_iterator<iterator>;
120
121 using reference = T &;
122 using const_reference = const T &;
123 using pointer = T *;
124 using const_pointer = const T *;
125
126 // forward iterator creation methods.
127 iterator begin() { return (iterator)this->BeginX; }
128 const_iterator begin() const { return (const_iterator)this->BeginX; }
129 iterator end() { return begin() + size(); }
130 const_iterator end() const { return begin() + size(); }
131
132 // reverse iterator creation methods.
133 reverse_iterator rbegin() { return reverse_iterator(end()); }
134 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
135 reverse_iterator rend() { return reverse_iterator(begin()); }
136 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
137
138 size_type size_in_bytes() const { return size() * sizeof(T); }
139 size_type max_size() const { return size_type(-1) / sizeof(T); }
140
141 size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
142
143 /// Return a pointer to the vector's buffer, even if empty().
144 pointer data() { return pointer(begin()); }
145 /// Return a pointer to the vector's buffer, even if empty().
146 const_pointer data() const { return const_pointer(begin()); }
147
148 reference operator[](size_type idx) {
149 assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 149, __PRETTY_FUNCTION__))
;
150 return begin()[idx];
151 }
152 const_reference operator[](size_type idx) const {
153 assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 153, __PRETTY_FUNCTION__))
;
154 return begin()[idx];
155 }
156
157 reference front() {
158 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 158, __PRETTY_FUNCTION__))
;
159 return begin()[0];
160 }
161 const_reference front() const {
162 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 162, __PRETTY_FUNCTION__))
;
163 return begin()[0];
164 }
165
166 reference back() {
167 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 167, __PRETTY_FUNCTION__))
;
168 return end()[-1];
169 }
170 const_reference back() const {
171 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 171, __PRETTY_FUNCTION__))
;
172 return end()[-1];
173 }
174};
175
176/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put method
177/// implementations that are designed to work with non-POD-like T's.
178template <typename T, bool = is_trivially_copyable<T>::value>
179class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
180protected:
181 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
182
183 static void destroy_range(T *S, T *E) {
184 while (S != E) {
185 --E;
186 E->~T();
187 }
188 }
189
190 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
191 /// constructing elements as needed.
192 template<typename It1, typename It2>
193 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
194 std::uninitialized_copy(std::make_move_iterator(I),
195 std::make_move_iterator(E), Dest);
196 }
197
198 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
199 /// constructing elements as needed.
200 template<typename It1, typename It2>
201 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
202 std::uninitialized_copy(I, E, Dest);
203 }
204
205 /// Grow the allocated memory (without initializing new elements), doubling
206 /// the size of the allocated memory. Guarantees space for at least one more
207 /// element, or MinSize more elements if specified.
208 void grow(size_t MinSize = 0);
209
210public:
211 void push_back(const T &Elt) {
212 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
213 this->grow();
214 ::new ((void*) this->end()) T(Elt);
215 this->set_size(this->size() + 1);
216 }
217
218 void push_back(T &&Elt) {
219 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
220 this->grow();
221 ::new ((void*) this->end()) T(::std::move(Elt));
222 this->set_size(this->size() + 1);
223 }
224
225 void pop_back() {
226 this->set_size(this->size() - 1);
227 this->end()->~T();
228 }
229};
230
231// Define this out-of-line to dissuade the C++ compiler from inlining it.
232template <typename T, bool TriviallyCopyable>
233void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
234 if (MinSize > UINT32_MAX(4294967295U))
235 report_bad_alloc_error("SmallVector capacity overflow during allocation");
236
237 // Always grow, even from zero.
238 size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
239 NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX(4294967295U)));
240 T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
241
242 // Move the elements over.
243 this->uninitialized_move(this->begin(), this->end(), NewElts);
244
245 // Destroy the original elements.
246 destroy_range(this->begin(), this->end());
247
248 // If this wasn't grown from the inline copy, deallocate the old space.
249 if (!this->isSmall())
250 free(this->begin());
251
252 this->BeginX = NewElts;
253 this->Capacity = NewCapacity;
254}
255
256/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
257/// method implementations that are designed to work with POD-like T's.
258template <typename T>
259class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
260protected:
261 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
262
263 // No need to do a destroy loop for POD's.
264 static void destroy_range(T *, T *) {}
265
266 /// Move the range [I, E) onto the uninitialized memory
267 /// starting with "Dest", constructing elements into it as needed.
268 template<typename It1, typename It2>
269 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
270 // Just do a copy.
271 uninitialized_copy(I, E, Dest);
272 }
273
274 /// Copy the range [I, E) onto the uninitialized memory
275 /// starting with "Dest", constructing elements into it as needed.
276 template<typename It1, typename It2>
277 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
278 // Arbitrary iterator types; just use the basic implementation.
279 std::uninitialized_copy(I, E, Dest);
280 }
281
282 /// Copy the range [I, E) onto the uninitialized memory
283 /// starting with "Dest", constructing elements into it as needed.
284 template <typename T1, typename T2>
285 static void uninitialized_copy(
286 T1 *I, T1 *E, T2 *Dest,
287 typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,
288 T2>::value>::type * = nullptr) {
289 // Use memcpy for PODs iterated by pointers (which includes SmallVector
290 // iterators): std::uninitialized_copy optimizes to memmove, but we can
291 // use memcpy here. Note that I and E are iterators and thus might be
292 // invalid for memcpy if they are equal.
293 if (I != E)
294 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
295 }
296
297 /// Double the size of the allocated memory, guaranteeing space for at
298 /// least one more element or MinSize if specified.
299 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
300
301public:
302 void push_back(const T &Elt) {
303 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
304 this->grow();
305 memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
306 this->set_size(this->size() + 1);
307 }
308
309 void pop_back() { this->set_size(this->size() - 1); }
310};
311
312/// This class consists of common code factored out of the SmallVector class to
313/// reduce code duplication based on the SmallVector 'N' template parameter.
314template <typename T>
315class SmallVectorImpl : public SmallVectorTemplateBase<T> {
316 using SuperClass = SmallVectorTemplateBase<T>;
317
318public:
319 using iterator = typename SuperClass::iterator;
320 using const_iterator = typename SuperClass::const_iterator;
321 using reference = typename SuperClass::reference;
322 using size_type = typename SuperClass::size_type;
323
324protected:
325 // Default ctor - Initialize to empty.
326 explicit SmallVectorImpl(unsigned N)
327 : SmallVectorTemplateBase<T>(N) {}
328
329public:
330 SmallVectorImpl(const SmallVectorImpl &) = delete;
331
332 ~SmallVectorImpl() {
333 // Subclass has already destructed this vector's elements.
334 // If this wasn't grown from the inline copy, deallocate the old space.
335 if (!this->isSmall())
336 free(this->begin());
337 }
338
339 void clear() {
340 this->destroy_range(this->begin(), this->end());
341 this->Size = 0;
342 }
343
344 void resize(size_type N) {
345 if (N < this->size()) {
346 this->destroy_range(this->begin()+N, this->end());
347 this->set_size(N);
348 } else if (N > this->size()) {
349 if (this->capacity() < N)
350 this->grow(N);
351 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
352 new (&*I) T();
353 this->set_size(N);
354 }
355 }
356
357 void resize(size_type N, const T &NV) {
358 if (N < this->size()) {
359 this->destroy_range(this->begin()+N, this->end());
360 this->set_size(N);
361 } else if (N > this->size()) {
362 if (this->capacity() < N)
363 this->grow(N);
364 std::uninitialized_fill(this->end(), this->begin()+N, NV);
365 this->set_size(N);
366 }
367 }
368
369 void reserve(size_type N) {
370 if (this->capacity() < N)
371 this->grow(N);
372 }
373
374 LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
375 T Result = ::std::move(this->back());
376 this->pop_back();
377 return Result;
378 }
379
380 void swap(SmallVectorImpl &RHS);
381
382 /// Add the specified range to the end of the SmallVector.
383 template <typename in_iter,
384 typename = typename std::enable_if<std::is_convertible<
385 typename std::iterator_traits<in_iter>::iterator_category,
386 std::input_iterator_tag>::value>::type>
387 void append(in_iter in_start, in_iter in_end) {
388 size_type NumInputs = std::distance(in_start, in_end);
389 if (NumInputs > this->capacity() - this->size())
390 this->grow(this->size()+NumInputs);
391
392 this->uninitialized_copy(in_start, in_end, this->end());
393 this->set_size(this->size() + NumInputs);
394 }
395
396 /// Append \p NumInputs copies of \p Elt to the end.
397 void append(size_type NumInputs, const T &Elt) {
398 if (NumInputs > this->capacity() - this->size())
399 this->grow(this->size()+NumInputs);
400
401 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
402 this->set_size(this->size() + NumInputs);
403 }
404
405 void append(std::initializer_list<T> IL) {
406 append(IL.begin(), IL.end());
407 }
408
409 // FIXME: Consider assigning over existing elements, rather than clearing &
410 // re-initializing them - for all assign(...) variants.
411
412 void assign(size_type NumElts, const T &Elt) {
413 clear();
414 if (this->capacity() < NumElts)
415 this->grow(NumElts);
416 this->set_size(NumElts);
417 std::uninitialized_fill(this->begin(), this->end(), Elt);
418 }
419
420 template <typename in_iter,
421 typename = typename std::enable_if<std::is_convertible<
422 typename std::iterator_traits<in_iter>::iterator_category,
423 std::input_iterator_tag>::value>::type>
424 void assign(in_iter in_start, in_iter in_end) {
425 clear();
426 append(in_start, in_end);
427 }
428
429 void assign(std::initializer_list<T> IL) {
430 clear();
431 append(IL);
432 }
433
434 iterator erase(const_iterator CI) {
435 // Just cast away constness because this is a non-const member function.
436 iterator I = const_cast<iterator>(CI);
437
438 assert(I >= this->begin() && "Iterator to erase is out of bounds.")((I >= this->begin() && "Iterator to erase is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Iterator to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 438, __PRETTY_FUNCTION__))
;
439 assert(I < this->end() && "Erasing at past-the-end iterator.")((I < this->end() && "Erasing at past-the-end iterator."
) ? static_cast<void> (0) : __assert_fail ("I < this->end() && \"Erasing at past-the-end iterator.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 439, __PRETTY_FUNCTION__))
;
440
441 iterator N = I;
442 // Shift all elts down one.
443 std::move(I+1, this->end(), I);
444 // Drop the last elt.
445 this->pop_back();
446 return(N);
447 }
448
449 iterator erase(const_iterator CS, const_iterator CE) {
450 // Just cast away constness because this is a non-const member function.
451 iterator S = const_cast<iterator>(CS);
452 iterator E = const_cast<iterator>(CE);
453
454 assert(S >= this->begin() && "Range to erase is out of bounds.")((S >= this->begin() && "Range to erase is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("S >= this->begin() && \"Range to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 454, __PRETTY_FUNCTION__))
;
455 assert(S <= E && "Trying to erase invalid range.")((S <= E && "Trying to erase invalid range.") ? static_cast
<void> (0) : __assert_fail ("S <= E && \"Trying to erase invalid range.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 455, __PRETTY_FUNCTION__))
;
456 assert(E <= this->end() && "Trying to erase past the end.")((E <= this->end() && "Trying to erase past the end."
) ? static_cast<void> (0) : __assert_fail ("E <= this->end() && \"Trying to erase past the end.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 456, __PRETTY_FUNCTION__))
;
457
458 iterator N = S;
459 // Shift all elts down.
460 iterator I = std::move(E, this->end(), S);
461 // Drop the last elts.
462 this->destroy_range(I, this->end());
463 this->set_size(I - this->begin());
464 return(N);
465 }
466
467 iterator insert(iterator I, T &&Elt) {
468 if (I == this->end()) { // Important special case for empty vector.
469 this->push_back(::std::move(Elt));
470 return this->end()-1;
471 }
472
473 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 473, __PRETTY_FUNCTION__))
;
474 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 474, __PRETTY_FUNCTION__))
;
475
476 if (this->size() >= this->capacity()) {
477 size_t EltNo = I-this->begin();
478 this->grow();
479 I = this->begin()+EltNo;
480 }
481
482 ::new ((void*) this->end()) T(::std::move(this->back()));
483 // Push everything else over.
484 std::move_backward(I, this->end()-1, this->end());
485 this->set_size(this->size() + 1);
486
487 // If we just moved the element we're inserting, be sure to update
488 // the reference.
489 T *EltPtr = &Elt;
490 if (I <= EltPtr && EltPtr < this->end())
491 ++EltPtr;
492
493 *I = ::std::move(*EltPtr);
494 return I;
495 }
496
497 iterator insert(iterator I, const T &Elt) {
498 if (I == this->end()) { // Important special case for empty vector.
499 this->push_back(Elt);
500 return this->end()-1;
501 }
502
503 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 503, __PRETTY_FUNCTION__))
;
504 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 504, __PRETTY_FUNCTION__))
;
505
506 if (this->size() >= this->capacity()) {
507 size_t EltNo = I-this->begin();
508 this->grow();
509 I = this->begin()+EltNo;
510 }
511 ::new ((void*) this->end()) T(std::move(this->back()));
512 // Push everything else over.
513 std::move_backward(I, this->end()-1, this->end());
514 this->set_size(this->size() + 1);
515
516 // If we just moved the element we're inserting, be sure to update
517 // the reference.
518 const T *EltPtr = &Elt;
519 if (I <= EltPtr && EltPtr < this->end())
520 ++EltPtr;
521
522 *I = *EltPtr;
523 return I;
524 }
525
526 iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
527 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
528 size_t InsertElt = I - this->begin();
529
530 if (I == this->end()) { // Important special case for empty vector.
531 append(NumToInsert, Elt);
532 return this->begin()+InsertElt;
533 }
534
535 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 535, __PRETTY_FUNCTION__))
;
536 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 536, __PRETTY_FUNCTION__))
;
537
538 // Ensure there is enough space.
539 reserve(this->size() + NumToInsert);
540
541 // Uninvalidate the iterator.
542 I = this->begin()+InsertElt;
543
544 // If there are more elements between the insertion point and the end of the
545 // range than there are being inserted, we can use a simple approach to
546 // insertion. Since we already reserved space, we know that this won't
547 // reallocate the vector.
548 if (size_t(this->end()-I) >= NumToInsert) {
549 T *OldEnd = this->end();
550 append(std::move_iterator<iterator>(this->end() - NumToInsert),
551 std::move_iterator<iterator>(this->end()));
552
553 // Copy the existing elements that get replaced.
554 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
555
556 std::fill_n(I, NumToInsert, Elt);
557 return I;
558 }
559
560 // Otherwise, we're inserting more elements than exist already, and we're
561 // not inserting at the end.
562
563 // Move over the elements that we're about to overwrite.
564 T *OldEnd = this->end();
565 this->set_size(this->size() + NumToInsert);
566 size_t NumOverwritten = OldEnd-I;
567 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
568
569 // Replace the overwritten part.
570 std::fill_n(I, NumOverwritten, Elt);
571
572 // Insert the non-overwritten middle part.
573 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
574 return I;
575 }
576
577 template <typename ItTy,
578 typename = typename std::enable_if<std::is_convertible<
579 typename std::iterator_traits<ItTy>::iterator_category,
580 std::input_iterator_tag>::value>::type>
581 iterator insert(iterator I, ItTy From, ItTy To) {
582 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
583 size_t InsertElt = I - this->begin();
584
585 if (I == this->end()) { // Important special case for empty vector.
586 append(From, To);
587 return this->begin()+InsertElt;
588 }
589
590 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 590, __PRETTY_FUNCTION__))
;
591 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/SmallVector.h"
, 591, __PRETTY_FUNCTION__))
;
592
593 size_t NumToInsert = std::distance(From, To);
594
595 // Ensure there is enough space.
596 reserve(this->size() + NumToInsert);
597
598 // Uninvalidate the iterator.
599 I = this->begin()+InsertElt;
600
601 // If there are more elements between the insertion point and the end of the
602 // range than there are being inserted, we can use a simple approach to
603 // insertion. Since we already reserved space, we know that this won't
604 // reallocate the vector.
605 if (size_t(this->end()-I) >= NumToInsert) {
606 T *OldEnd = this->end();
607 append(std::move_iterator<iterator>(this->end() - NumToInsert),
608 std::move_iterator<iterator>(this->end()));
609
610 // Copy the existing elements that get replaced.
611 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
612
613 std::copy(From, To, I);
614 return I;
615 }
616
617 // Otherwise, we're inserting more elements than exist already, and we're
618 // not inserting at the end.
619
620 // Move over the elements that we're about to overwrite.
621 T *OldEnd = this->end();
622 this->set_size(this->size() + NumToInsert);
623 size_t NumOverwritten = OldEnd-I;
624 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
625
626 // Replace the overwritten part.
627 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
628 *J = *From;
629 ++J; ++From;
630 }
631
632 // Insert the non-overwritten middle part.
633 this->uninitialized_copy(From, To, OldEnd);
634 return I;
635 }
636
637 void insert(iterator I, std::initializer_list<T> IL) {
638 insert(I, IL.begin(), IL.end());
639 }
640
641 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
642 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
643 this->grow();
644 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
645 this->set_size(this->size() + 1);
646 return this->back();
647 }
648
649 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
650
651 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
652
653 bool operator==(const SmallVectorImpl &RHS) const {
654 if (this->size() != RHS.size()) return false;
655 return std::equal(this->begin(), this->end(), RHS.begin());
656 }
657 bool operator!=(const SmallVectorImpl &RHS) const {
658 return !(*this == RHS);
659 }
660
661 bool operator<(const SmallVectorImpl &RHS) const {
662 return std::lexicographical_compare(this->begin(), this->end(),
663 RHS.begin(), RHS.end());
664 }
665};
666
667template <typename T>
668void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
669 if (this == &RHS) return;
670
671 // We can only avoid copying elements if neither vector is small.
672 if (!this->isSmall() && !RHS.isSmall()) {
673 std::swap(this->BeginX, RHS.BeginX);
674 std::swap(this->Size, RHS.Size);
675 std::swap(this->Capacity, RHS.Capacity);
676 return;
677 }
678 if (RHS.size() > this->capacity())
679 this->grow(RHS.size());
680 if (this->size() > RHS.capacity())
681 RHS.grow(this->size());
682
683 // Swap the shared elements.
684 size_t NumShared = this->size();
685 if (NumShared > RHS.size()) NumShared = RHS.size();
686 for (size_type i = 0; i != NumShared; ++i)
687 std::swap((*this)[i], RHS[i]);
688
689 // Copy over the extra elts.
690 if (this->size() > RHS.size()) {
691 size_t EltDiff = this->size() - RHS.size();
692 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
693 RHS.set_size(RHS.size() + EltDiff);
694 this->destroy_range(this->begin()+NumShared, this->end());
695 this->set_size(NumShared);
696 } else if (RHS.size() > this->size()) {
697 size_t EltDiff = RHS.size() - this->size();
698 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
699 this->set_size(this->size() + EltDiff);
700 this->destroy_range(RHS.begin()+NumShared, RHS.end());
701 RHS.set_size(NumShared);
702 }
703}
704
705template <typename T>
706SmallVectorImpl<T> &SmallVectorImpl<T>::
707 operator=(const SmallVectorImpl<T> &RHS) {
708 // Avoid self-assignment.
709 if (this == &RHS) return *this;
710
711 // If we already have sufficient space, assign the common elements, then
712 // destroy any excess.
713 size_t RHSSize = RHS.size();
714 size_t CurSize = this->size();
715 if (CurSize >= RHSSize) {
716 // Assign common elements.
717 iterator NewEnd;
718 if (RHSSize)
719 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
720 else
721 NewEnd = this->begin();
722
723 // Destroy excess elements.
724 this->destroy_range(NewEnd, this->end());
725
726 // Trim.
727 this->set_size(RHSSize);
728 return *this;
729 }
730
731 // If we have to grow to have enough elements, destroy the current elements.
732 // This allows us to avoid copying them during the grow.
733 // FIXME: don't do this if they're efficiently moveable.
734 if (this->capacity() < RHSSize) {
735 // Destroy current elements.
736 this->destroy_range(this->begin(), this->end());
737 this->set_size(0);
738 CurSize = 0;
739 this->grow(RHSSize);
740 } else if (CurSize) {
741 // Otherwise, use assignment for the already-constructed elements.
742 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
743 }
744
745 // Copy construct the new elements in place.
746 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
747 this->begin()+CurSize);
748
749 // Set end.
750 this->set_size(RHSSize);
751 return *this;
752}
753
754template <typename T>
755SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
756 // Avoid self-assignment.
757 if (this == &RHS) return *this;
758
759 // If the RHS isn't small, clear this vector and then steal its buffer.
760 if (!RHS.isSmall()) {
761 this->destroy_range(this->begin(), this->end());
762 if (!this->isSmall()) free(this->begin());
763 this->BeginX = RHS.BeginX;
764 this->Size = RHS.Size;
765 this->Capacity = RHS.Capacity;
766 RHS.resetToSmall();
767 return *this;
768 }
769
770 // If we already have sufficient space, assign the common elements, then
771 // destroy any excess.
772 size_t RHSSize = RHS.size();
773 size_t CurSize = this->size();
774 if (CurSize >= RHSSize) {
775 // Assign common elements.
776 iterator NewEnd = this->begin();
777 if (RHSSize)
778 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
779
780 // Destroy excess elements and trim the bounds.
781 this->destroy_range(NewEnd, this->end());
782 this->set_size(RHSSize);
783
784 // Clear the RHS.
785 RHS.clear();
786
787 return *this;
788 }
789
790 // If we have to grow to have enough elements, destroy the current elements.
791 // This allows us to avoid copying them during the grow.
792 // FIXME: this may not actually make any sense if we can efficiently move
793 // elements.
794 if (this->capacity() < RHSSize) {
795 // Destroy current elements.
796 this->destroy_range(this->begin(), this->end());
797 this->set_size(0);
798 CurSize = 0;
799 this->grow(RHSSize);
800 } else if (CurSize) {
801 // Otherwise, use assignment for the already-constructed elements.
802 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
803 }
804
805 // Move-construct the new elements in place.
806 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
807 this->begin()+CurSize);
808
809 // Set end.
810 this->set_size(RHSSize);
811
812 RHS.clear();
813 return *this;
814}
815
816/// Storage for the SmallVector elements. This is specialized for the N=0 case
817/// to avoid allocating unnecessary storage.
818template <typename T, unsigned N>
819struct SmallVectorStorage {
820 AlignedCharArrayUnion<T> InlineElts[N];
821};
822
823/// We need the storage to be properly aligned even for small-size of 0 so that
824/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
825/// well-defined.
826template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
827
828/// This is a 'vector' (really, a variable-sized array), optimized
829/// for the case when the array is small. It contains some number of elements
830/// in-place, which allows it to avoid heap allocation when the actual number of
831/// elements is below that threshold. This allows normal "small" cases to be
832/// fast without losing generality for large inputs.
833///
834/// Note that this does not attempt to be exception safe.
835///
836template <typename T, unsigned N>
837class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {
838public:
839 SmallVector() : SmallVectorImpl<T>(N) {}
840
841 ~SmallVector() {
842 // Destroy the constructed elements in the vector.
843 this->destroy_range(this->begin(), this->end());
844 }
845
846 explicit SmallVector(size_t Size, const T &Value = T())
847 : SmallVectorImpl<T>(N) {
848 this->assign(Size, Value);
849 }
850
851 template <typename ItTy,
852 typename = typename std::enable_if<std::is_convertible<
853 typename std::iterator_traits<ItTy>::iterator_category,
854 std::input_iterator_tag>::value>::type>
855 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
856 this->append(S, E);
857 }
858
859 template <typename RangeTy>
860 explicit SmallVector(const iterator_range<RangeTy> &R)
861 : SmallVectorImpl<T>(N) {
862 this->append(R.begin(), R.end());
863 }
864
865 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
866 this->assign(IL);
867 }
868
869 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
870 if (!RHS.empty())
871 SmallVectorImpl<T>::operator=(RHS);
872 }
873
874 const SmallVector &operator=(const SmallVector &RHS) {
875 SmallVectorImpl<T>::operator=(RHS);
876 return *this;
877 }
878
879 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
880 if (!RHS.empty())
881 SmallVectorImpl<T>::operator=(::std::move(RHS));
882 }
883
884 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
885 if (!RHS.empty())
886 SmallVectorImpl<T>::operator=(::std::move(RHS));
887 }
888
889 const SmallVector &operator=(SmallVector &&RHS) {
890 SmallVectorImpl<T>::operator=(::std::move(RHS));
891 return *this;
892 }
893
894 const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
895 SmallVectorImpl<T>::operator=(::std::move(RHS));
896 return *this;
897 }
898
899 const SmallVector &operator=(std::initializer_list<T> IL) {
900 this->assign(IL);
901 return *this;
902 }
903};
904
905template <typename T, unsigned N>
906inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
907 return X.capacity_in_bytes();
908}
909
910} // end namespace llvm
911
912namespace std {
913
914 /// Implement std::swap in terms of SmallVector swap.
915 template<typename T>
916 inline void
917 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
918 LHS.swap(RHS);
919 }
920
921 /// Implement std::swap in terms of SmallVector swap.
922 template<typename T, unsigned N>
923 inline void
924 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
925 LHS.swap(RHS);
926 }
927
928} // end namespace std
929
930#endif // LLVM_ADT_SMALLVECTOR_H

/build/llvm-toolchain-snapshot-10~svn374877/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
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
53/// Mathematical constants.
54namespace numbers {
55// TODO: Track C++20 std::numbers.
56// TODO: Favor using the hexadecimal FP constants (requires C++17).
57constexpr double e = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113
58 egamma = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620
59 ln2 = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162
60 ln10 = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392
61 log2e = 1.4426950408889634074, // (0x1.71547652b82feP+0)
62 log10e = .43429448190325182765, // (0x1.bcb7b1526e50eP-2)
63 pi = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796
64 inv_pi = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541
65 sqrtpi = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161
66 inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197
67 sqrt2 = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219
68 inv_sqrt2 = .70710678118654752440, // (0x1.6a09e667f3bcdP-1)
69 sqrt3 = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194
70 inv_sqrt3 = .57735026918962576451, // (0x1.279a74590331cP-1)
71 phi = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622
72constexpr float ef = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113
73 egammaf = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620
74 ln2f = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162
75 ln10f = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392
76 log2ef = 1.44269504F, // (0x1.715476P+0)
77 log10ef = .434294482F, // (0x1.bcb7b2P-2)
78 pif = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796
79 inv_pif = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541
80 sqrtpif = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161
81 inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197
82 sqrt2f = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193
83 inv_sqrt2f = .707106781F, // (0x1.6a09e6P-1)
84 sqrt3f = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194
85 inv_sqrt3f = .577350269F, // (0x1.279a74P-1)
86 phif = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622
87} // namespace numbers
88
89namespace detail {
90template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
91 static unsigned count(T Val, ZeroBehavior) {
92 if (!Val)
93 return std::numeric_limits<T>::digits;
94 if (Val & 0x1)
95 return 0;
96
97 // Bisection method.
98 unsigned ZeroBits = 0;
99 T Shift = std::numeric_limits<T>::digits >> 1;
100 T Mask = std::numeric_limits<T>::max() >> Shift;
101 while (Shift) {
102 if ((Val & Mask) == 0) {
103 Val >>= Shift;
104 ZeroBits |= Shift;
105 }
106 Shift >>= 1;
107 Mask >>= Shift;
108 }
109 return ZeroBits;
110 }
111};
112
113#if defined(__GNUC__4) || defined(_MSC_VER)
114template <typename T> struct TrailingZerosCounter<T, 4> {
115 static unsigned count(T Val, ZeroBehavior ZB) {
116 if (ZB
56.1
'ZB' is not equal to ZB_Undefined
56.1
'ZB' is not equal to ZB_Undefined
56.1
'ZB' is not equal to ZB_Undefined
56.1
'ZB' is not equal to ZB_Undefined
!= ZB_Undefined && Val == 0)
57
Assuming 'Val' is equal to 0
58
Taking true branch
117 return 32;
59
Returning the value 32
118
119#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
120 return __builtin_ctz(Val);
121#elif defined(_MSC_VER)
122 unsigned long Index;
123 _BitScanForward(&Index, Val);
124 return Index;
125#endif
126 }
127};
128
129#if !defined(_MSC_VER) || defined(_M_X64)
130template <typename T> struct TrailingZerosCounter<T, 8> {
131 static unsigned count(T Val, ZeroBehavior ZB) {
132 if (ZB != ZB_Undefined && Val == 0)
133 return 64;
134
135#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
136 return __builtin_ctzll(Val);
137#elif defined(_MSC_VER)
138 unsigned long Index;
139 _BitScanForward64(&Index, Val);
140 return Index;
141#endif
142 }
143};
144#endif
145#endif
146} // namespace detail
147
148/// Count number of 0's from the least significant bit to the most
149/// stopping at the first 1.
150///
151/// Only unsigned integral types are allowed.
152///
153/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
154/// valid arguments.
155template <typename T>
156unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
157 static_assert(std::numeric_limits<T>::is_integer &&
158 !std::numeric_limits<T>::is_signed,
159 "Only unsigned integral types are allowed.");
160 return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
56
Calling 'TrailingZerosCounter::count'
60
Returning from 'TrailingZerosCounter::count'
61
Returning the value 32
161}
162
163namespace detail {
164template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
165 static unsigned count(T Val, ZeroBehavior) {
166 if (!Val)
167 return std::numeric_limits<T>::digits;
168
169 // Bisection method.
170 unsigned ZeroBits = 0;
171 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
172 T Tmp = Val >> Shift;
173 if (Tmp)
174 Val = Tmp;
175 else
176 ZeroBits |= Shift;
177 }
178 return ZeroBits;
179 }
180};
181
182#if defined(__GNUC__4) || defined(_MSC_VER)
183template <typename T> struct LeadingZerosCounter<T, 4> {
184 static unsigned count(T Val, ZeroBehavior ZB) {
185 if (ZB != ZB_Undefined && Val == 0)
186 return 32;
187
188#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
189 return __builtin_clz(Val);
190#elif defined(_MSC_VER)
191 unsigned long Index;
192 _BitScanReverse(&Index, Val);
193 return Index ^ 31;
194#endif
195 }
196};
197
198#if !defined(_MSC_VER) || defined(_M_X64)
199template <typename T> struct LeadingZerosCounter<T, 8> {
200 static unsigned count(T Val, ZeroBehavior ZB) {
201 if (ZB != ZB_Undefined && Val == 0)
202 return 64;
203
204#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
205 return __builtin_clzll(Val);
206#elif defined(_MSC_VER)
207 unsigned long Index;
208 _BitScanReverse64(&Index, Val);
209 return Index ^ 63;
210#endif
211 }
212};
213#endif
214#endif
215} // namespace detail
216
217/// Count number of 0's from the most significant bit to the least
218/// stopping at the first 1.
219///
220/// Only unsigned integral types are allowed.
221///
222/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
223/// valid arguments.
224template <typename T>
225unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
226 static_assert(std::numeric_limits<T>::is_integer &&
227 !std::numeric_limits<T>::is_signed,
228 "Only unsigned integral types are allowed.");
229 return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
230}
231
232/// Get the index of the first set bit starting from the least
233/// significant bit.
234///
235/// Only unsigned integral types are allowed.
236///
237/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
238/// valid arguments.
239template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
240 if (ZB == ZB_Max && Val == 0)
241 return std::numeric_limits<T>::max();
242
243 return countTrailingZeros(Val, ZB_Undefined);
244}
245
246/// Create a bitmask with the N right-most bits set to 1, and all other
247/// bits set to 0. Only unsigned types are allowed.
248template <typename T> T maskTrailingOnes(unsigned N) {
249 static_assert(std::is_unsigned<T>::value, "Invalid type!");
250 const unsigned Bits = CHAR_BIT8 * sizeof(T);
251 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-10~svn374877/include/llvm/Support/MathExtras.h"
, 251, __PRETTY_FUNCTION__))
;
252 return N == 0 ? 0 : (T(-1) >> (Bits - N));
253}
254
255/// Create a bitmask with the N left-most bits set to 1, and all other
256/// bits set to 0. Only unsigned types are allowed.
257template <typename T> T maskLeadingOnes(unsigned N) {
258 return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
259}
260
261/// Create a bitmask with the N right-most bits set to 0, and all other
262/// bits set to 1. Only unsigned types are allowed.
263template <typename T> T maskTrailingZeros(unsigned N) {
264 return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
265}
266
267/// Create a bitmask with the N left-most bits set to 0, and all other
268/// bits set to 1. Only unsigned types are allowed.
269template <typename T> T maskLeadingZeros(unsigned N) {
270 return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
271}
272
273/// Get the index of the last set bit starting from the least
274/// significant bit.
275///
276/// Only unsigned integral types are allowed.
277///
278/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
279/// valid arguments.
280template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
281 if (ZB == ZB_Max && Val == 0)
282 return std::numeric_limits<T>::max();
283
284 // Use ^ instead of - because both gcc and llvm can remove the associated ^
285 // in the __builtin_clz intrinsic on x86.
286 return countLeadingZeros(Val, ZB_Undefined) ^
287 (std::numeric_limits<T>::digits - 1);
288}
289
290/// Macro compressed bit reversal table for 256 bits.
291///
292/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
293static const unsigned char BitReverseTable256[256] = {
294#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
295#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
296#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
297 R6(0), R6(2), R6(1), R6(3)
298#undef R2
299#undef R4
300#undef R6
301};
302
303/// Reverse the bits in \p Val.
304template <typename T>
305T reverseBits(T Val) {
306 unsigned char in[sizeof(Val)];
307 unsigned char out[sizeof(Val)];
308 std::memcpy(in, &Val, sizeof(Val));
309 for (unsigned i = 0; i < sizeof(Val); ++i)
310 out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
311 std::memcpy(&Val, out, sizeof(Val));
312 return Val;
313}
314
315// NOTE: The following support functions use the _32/_64 extensions instead of
316// type overloading so that signed and unsigned integers can be used without
317// ambiguity.
318
319/// Return the high 32 bits of a 64 bit value.
320constexpr inline uint32_t Hi_32(uint64_t Value) {
321 return static_cast<uint32_t>(Value >> 32);
322}
323
324/// Return the low 32 bits of a 64 bit value.
325constexpr inline uint32_t Lo_32(uint64_t Value) {
326 return static_cast<uint32_t>(Value);
327}
328
329/// Make a 64-bit integer from a high / low pair of 32-bit integers.
330constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
331 return ((uint64_t)High << 32) | (uint64_t)Low;
332}
333
334/// Checks if an integer fits into the given bit width.
335template <unsigned N> constexpr inline bool isInt(int64_t x) {
336 return N >= 64 || (-(INT64_C(1)1L<<(N-1)) <= x && x < (INT64_C(1)1L<<(N-1)));
337}
338// Template specializations to get better code for common cases.
339template <> constexpr inline bool isInt<8>(int64_t x) {
340 return static_cast<int8_t>(x) == x;
341}
342template <> constexpr inline bool isInt<16>(int64_t x) {
343 return static_cast<int16_t>(x) == x;
344}
345template <> constexpr inline bool isInt<32>(int64_t x) {
346 return static_cast<int32_t>(x) == x;
347}
348
349/// Checks if a signed integer is an N bit number shifted left by S.
350template <unsigned N, unsigned S>
351constexpr inline bool isShiftedInt(int64_t x) {
352 static_assert(
353 N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
354 static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
355 return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
356}
357
358/// Checks if an unsigned integer fits into the given bit width.
359///
360/// This is written as two functions rather than as simply
361///
362/// return N >= 64 || X < (UINT64_C(1) << N);
363///
364/// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
365/// left too many places.
366template <unsigned N>
367constexpr inline typename std::enable_if<(N < 64), bool>::type
368isUInt(uint64_t X) {
369 static_assert(N > 0, "isUInt<0> doesn't make sense");
370 return X < (UINT64_C(1)1UL << (N));
371}
372template <unsigned N>
373constexpr inline typename std::enable_if<N >= 64, bool>::type
374isUInt(uint64_t X) {
375 return true;
376}
377
378// Template specializations to get better code for common cases.
379template <> constexpr inline bool isUInt<8>(uint64_t x) {
380 return static_cast<uint8_t>(x) == x;
381}
382template <> constexpr inline bool isUInt<16>(uint64_t x) {
383 return static_cast<uint16_t>(x) == x;
384}
385template <> constexpr inline bool isUInt<32>(uint64_t x) {
386 return static_cast<uint32_t>(x) == x;
387}
388
389/// Checks if a unsigned integer is an N bit number shifted left by S.
390template <unsigned N, unsigned S>
391constexpr inline bool isShiftedUInt(uint64_t x) {
392 static_assert(
393 N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
394 static_assert(N + S <= 64,
395 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
396 // Per the two static_asserts above, S must be strictly less than 64. So
397 // 1 << S is not undefined behavior.
398 return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
399}
400
401/// Gets the maximum value for a N-bit unsigned integer.
402inline uint64_t maxUIntN(uint64_t N) {
403 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-10~svn374877/include/llvm/Support/MathExtras.h"
, 403, __PRETTY_FUNCTION__))
;
404
405 // uint64_t(1) << 64 is undefined behavior, so we can't do
406 // (uint64_t(1) << N) - 1
407 // without checking first that N != 64. But this works and doesn't have a
408 // branch.
409 return UINT64_MAX(18446744073709551615UL) >> (64 - N);
410}
411
412/// Gets the minimum value for a N-bit signed integer.
413inline int64_t minIntN(int64_t N) {
414 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-10~svn374877/include/llvm/Support/MathExtras.h"
, 414, __PRETTY_FUNCTION__))
;
415
416 return -(UINT64_C(1)1UL<<(N-1));
417}
418
419/// Gets the maximum value for a N-bit signed integer.
420inline int64_t maxIntN(int64_t N) {
421 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-10~svn374877/include/llvm/Support/MathExtras.h"
, 421, __PRETTY_FUNCTION__))
;
422
423 // This relies on two's complement wraparound when N == 64, so we convert to
424 // int64_t only at the very end to avoid UB.
425 return (UINT64_C(1)1UL << (N - 1)) - 1;
426}
427
428/// Checks if an unsigned integer fits into the given (dynamic) bit width.
429inline bool isUIntN(unsigned N, uint64_t x) {
430 return N >= 64 || x <= maxUIntN(N);
431}
432
433/// Checks if an signed integer fits into the given (dynamic) bit width.
434inline bool isIntN(unsigned N, int64_t x) {
435 return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
436}
437
438/// Return true if the argument is a non-empty sequence of ones starting at the
439/// least significant bit with the remainder zero (32 bit version).
440/// Ex. isMask_32(0x0000FFFFU) == true.
441constexpr inline bool isMask_32(uint32_t Value) {
442 return Value && ((Value + 1) & Value) == 0;
443}
444
445/// Return true if the argument is a non-empty sequence of ones starting at the
446/// least significant bit with the remainder zero (64 bit version).
447constexpr inline bool isMask_64(uint64_t Value) {
448 return Value && ((Value + 1) & Value) == 0;
449}
450
451/// Return true if the argument contains a non-empty sequence of ones with the
452/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
453constexpr inline bool isShiftedMask_32(uint32_t Value) {
454 return Value && isMask_32((Value - 1) | Value);
455}
456
457/// Return true if the argument contains a non-empty sequence of ones with the
458/// remainder zero (64 bit version.)
459constexpr inline bool isShiftedMask_64(uint64_t Value) {
460 return Value && isMask_64((Value - 1) | Value);
461}
462
463/// Return true if the argument is a power of two > 0.
464/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
465constexpr inline bool isPowerOf2_32(uint32_t Value) {
466 return Value && !(Value & (Value - 1));
467}
468
469/// Return true if the argument is a power of two > 0 (64 bit edition.)
470constexpr inline bool isPowerOf2_64(uint64_t Value) {
471 return Value && !(Value & (Value - 1));
472}
473
474/// Return a byte-swapped representation of the 16-bit argument.
475inline uint16_t ByteSwap_16(uint16_t Value) {
476 return sys::SwapByteOrder_16(Value);
477}
478
479/// Return a byte-swapped representation of the 32-bit argument.
480inline uint32_t ByteSwap_32(uint32_t Value) {
481 return sys::SwapByteOrder_32(Value);
482}
483
484/// Return a byte-swapped representation of the 64-bit argument.
485inline uint64_t ByteSwap_64(uint64_t Value) {
486 return sys::SwapByteOrder_64(Value);
487}
488
489/// Count the number of ones from the most significant bit to the first
490/// zero bit.
491///
492/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
493/// Only unsigned integral types are allowed.
494///
495/// \param ZB the behavior on an input of all ones. Only ZB_Width and
496/// ZB_Undefined are valid arguments.
497template <typename T>
498unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
499 static_assert(std::numeric_limits<T>::is_integer &&
500 !std::numeric_limits<T>::is_signed,
501 "Only unsigned integral types are allowed.");
502 return countLeadingZeros<T>(~Value, ZB);
503}
504
505/// Count the number of ones from the least significant bit to the first
506/// zero bit.
507///
508/// Ex. countTrailingOnes(0x00FF00FF) == 8.
509/// Only unsigned integral types are allowed.
510///
511/// \param ZB the behavior on an input of all ones. Only ZB_Width and
512/// ZB_Undefined are valid arguments.
513template <typename T>
514unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
515 static_assert(std::numeric_limits<T>::is_integer &&
516 !std::numeric_limits<T>::is_signed,
517 "Only unsigned integral types are allowed.");
518 return countTrailingZeros<T>(~Value, ZB);
519}
520
521namespace detail {
522template <typename T, std::size_t SizeOfT> struct PopulationCounter {
523 static unsigned count(T Value) {
524 // Generic version, forward to 32 bits.
525 static_assert(SizeOfT <= 4, "Not implemented!");
526#if defined(__GNUC__4)
527 return __builtin_popcount(Value);
528#else
529 uint32_t v = Value;
530 v = v - ((v >> 1) & 0x55555555);
531 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
532 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
533#endif
534 }
535};
536
537template <typename T> struct PopulationCounter<T, 8> {
538 static unsigned count(T Value) {
539#if defined(__GNUC__4)
540 return __builtin_popcountll(Value);
541#else
542 uint64_t v = Value;
543 v = v - ((v >> 1) & 0x5555555555555555ULL);
544 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
545 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
546 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
547#endif
548 }
549};
550} // namespace detail
551
552/// Count the number of set bits in a value.
553/// Ex. countPopulation(0xF000F000) = 8
554/// Returns 0 if the word is zero.
555template <typename T>
556inline unsigned countPopulation(T Value) {
557 static_assert(std::numeric_limits<T>::is_integer &&
558 !std::numeric_limits<T>::is_signed,
559 "Only unsigned integral types are allowed.");
560 return detail::PopulationCounter<T, sizeof(T)>::count(Value);
561}
562
563/// Compile time Log2.
564/// Valid only for positive powers of two.
565template <size_t kValue> constexpr inline size_t CTLog2() {
566 static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue),
567 "Value is not a valid power of 2");
568 return 1 + CTLog2<kValue / 2>();
569}
570
571template <> constexpr inline size_t CTLog2<1>() { return 0; }
572
573/// Return the log base 2 of the specified value.
574inline double Log2(double Value) {
575#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
576 return __builtin_log(Value) / __builtin_log(2.0);
577#else
578 return log2(Value);
579#endif
580}
581
582/// Return the floor log base 2 of the specified value, -1 if the value is zero.
583/// (32 bit edition.)
584/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
585inline unsigned Log2_32(uint32_t Value) {
586 return 31 - countLeadingZeros(Value);
587}
588
589/// Return the floor log base 2 of the specified value, -1 if the value is zero.
590/// (64 bit edition.)
591inline unsigned Log2_64(uint64_t Value) {
592 return 63 - countLeadingZeros(Value);
593}
594
595/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
596/// (32 bit edition).
597/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
598inline unsigned Log2_32_Ceil(uint32_t Value) {
599 return 32 - countLeadingZeros(Value - 1);
600}
601
602/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
603/// (64 bit edition.)
604inline unsigned Log2_64_Ceil(uint64_t Value) {
605 return 64 - countLeadingZeros(Value - 1);
606}
607
608/// Return the greatest common divisor of the values using Euclid's algorithm.
609template <typename T>
610inline T greatestCommonDivisor(T A, T B) {
611 while (B) {
612 T Tmp = B;
613 B = A % B;
614 A = Tmp;
615 }
616 return A;
617}
618
619inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
620 return greatestCommonDivisor<uint64_t>(A, B);
621}
622
623/// This function takes a 64-bit integer and returns the bit equivalent double.
624inline double BitsToDouble(uint64_t Bits) {
625 double D;
626 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
627 memcpy(&D, &Bits, sizeof(Bits));
628 return D;
629}
630
631/// This function takes a 32-bit integer and returns the bit equivalent float.
632inline float BitsToFloat(uint32_t Bits) {
633 float F;
634 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
635 memcpy(&F, &Bits, sizeof(Bits));
636 return F;
637}
638
639/// This function takes a double and returns the bit equivalent 64-bit integer.
640/// Note that copying doubles around changes the bits of NaNs on some hosts,
641/// notably x86, so this routine cannot be used if these bits are needed.
642inline uint64_t DoubleToBits(double Double) {
643 uint64_t Bits;
644 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
645 memcpy(&Bits, &Double, sizeof(Double));
646 return Bits;
647}
648
649/// This function takes a float and returns the bit equivalent 32-bit integer.
650/// Note that copying floats around changes the bits of NaNs on some hosts,
651/// notably x86, so this routine cannot be used if these bits are needed.
652inline uint32_t FloatToBits(float Float) {
653 uint32_t Bits;
654 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
655 memcpy(&Bits, &Float, sizeof(Float));
656 return Bits;
657}
658
659/// A and B are either alignments or offsets. Return the minimum alignment that
660/// may be assumed after adding the two together.
661constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
662 // The largest power of 2 that divides both A and B.
663 //
664 // Replace "-Value" by "1+~Value" in the following commented code to avoid
665 // MSVC warning C4146
666 // return (A | B) & -(A | B);
667 return (A | B) & (1 + ~(A | B));
668}
669
670/// Returns the next power of two (in 64-bits) that is strictly greater than A.
671/// Returns zero on overflow.
672inline uint64_t NextPowerOf2(uint64_t A) {
673 A |= (A >> 1);
674 A |= (A >> 2);
675 A |= (A >> 4);
676 A |= (A >> 8);
677 A |= (A >> 16);
678 A |= (A >> 32);
679 return A + 1;
680}
681
682/// Returns the power of two which is less than or equal to the given value.
683/// Essentially, it is a floor operation across the domain of powers of two.
684inline uint64_t PowerOf2Floor(uint64_t A) {
685 if (!A) return 0;
686 return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
687}
688
689/// Returns the power of two which is greater than or equal to the given value.
690/// Essentially, it is a ceil operation across the domain of powers of two.
691inline uint64_t PowerOf2Ceil(uint64_t A) {
692 if (!A)
693 return 0;
694 return NextPowerOf2(A - 1);
695}
696
697/// Returns the next integer (mod 2**64) that is greater than or equal to
698/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
699///
700/// If non-zero \p Skew is specified, the return value will be a minimal
701/// integer that is greater than or equal to \p Value and equal to
702/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
703/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
704///
705/// Examples:
706/// \code
707/// alignTo(5, 8) = 8
708/// alignTo(17, 8) = 24
709/// alignTo(~0LL, 8) = 0
710/// alignTo(321, 255) = 510
711///
712/// alignTo(5, 8, 7) = 7
713/// alignTo(17, 8, 1) = 17
714/// alignTo(~0LL, 8, 3) = 3
715/// alignTo(321, 255, 42) = 552
716/// \endcode
717inline uint64_t alignTo(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-10~svn374877/include/llvm/Support/MathExtras.h"
, 718, __PRETTY_FUNCTION__))
;
719 Skew %= Align;
720 return (Value + Align - 1 - Skew) / Align * Align + Skew;
721}
722
723/// Returns the next integer (mod 2**64) that is greater than or equal to
724/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
725template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
726 static_assert(Align != 0u, "Align must be non-zero");
727 return (Value + Align - 1) / Align * Align;
728}
729
730/// Returns the integer ceil(Numerator / Denominator).
731inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
732 return alignTo(Numerator, Denominator) / Denominator;
733}
734
735/// Returns the largest uint64_t less than or equal to \p Value and is
736/// \p Skew mod \p Align. \p Align must be non-zero
737inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
738 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-10~svn374877/include/llvm/Support/MathExtras.h"
, 738, __PRETTY_FUNCTION__))
;
739 Skew %= Align;
740 return (Value - Skew) / Align * Align + Skew;
741}
742
743/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
744/// Requires 0 < B <= 32.
745template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
746 static_assert(B > 0, "Bit width can't be 0.");
747 static_assert(B <= 32, "Bit width out of range.");
748 return int32_t(X << (32 - B)) >> (32 - B);
749}
750
751/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
752/// Requires 0 < B < 32.
753inline int32_t SignExtend32(uint32_t X, unsigned B) {
754 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-10~svn374877/include/llvm/Support/MathExtras.h"
, 754, __PRETTY_FUNCTION__))
;
755 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-10~svn374877/include/llvm/Support/MathExtras.h"
, 755, __PRETTY_FUNCTION__))
;
756 return int32_t(X << (32 - B)) >> (32 - B);
757}
758
759/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
760/// Requires 0 < B < 64.
761template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
762 static_assert(B > 0, "Bit width can't be 0.");
763 static_assert(B <= 64, "Bit width out of range.");
764 return int64_t(x << (64 - B)) >> (64 - B);
765}
766
767/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
768/// Requires 0 < B < 64.
769inline int64_t SignExtend64(uint64_t X, unsigned B) {
770 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-10~svn374877/include/llvm/Support/MathExtras.h"
, 770, __PRETTY_FUNCTION__))
;
771 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-10~svn374877/include/llvm/Support/MathExtras.h"
, 771, __PRETTY_FUNCTION__))
;
772 return int64_t(X << (64 - B)) >> (64 - B);
773}
774
775/// Subtract two unsigned integers, X and Y, of type T and return the absolute
776/// value of the result.
777template <typename T>
778typename std::enable_if<std::is_unsigned<T>::value, T>::type
779AbsoluteDifference(T X, T Y) {
780 return std::max(X, Y) - std::min(X, Y);
781}
782
783/// Add two unsigned integers, X and Y, of type T. Clamp the result to the
784/// maximum representable value of T on overflow. ResultOverflowed indicates if
785/// the result is larger than the maximum representable value of type T.
786template <typename T>
787typename std::enable_if<std::is_unsigned<T>::value, T>::type
788SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
789 bool Dummy;
790 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
791 // Hacker's Delight, p. 29
792 T Z = X + Y;
793 Overflowed = (Z < X || Z < Y);
794 if (Overflowed)
795 return std::numeric_limits<T>::max();
796 else
797 return Z;
798}
799
800/// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the
801/// maximum representable value of T on overflow. ResultOverflowed indicates if
802/// the result is larger than the maximum representable value of type T.
803template <typename T>
804typename std::enable_if<std::is_unsigned<T>::value, T>::type
805SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
806 bool Dummy;
807 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
808
809 // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
810 // because it fails for uint16_t (where multiplication can have undefined
811 // behavior due to promotion to int), and requires a division in addition
812 // to the multiplication.
813
814 Overflowed = false;
815
816 // Log2(Z) would be either Log2Z or Log2Z + 1.
817 // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
818 // will necessarily be less than Log2Max as desired.
819 int Log2Z = Log2_64(X) + Log2_64(Y);
820 const T Max = std::numeric_limits<T>::max();
821 int Log2Max = Log2_64(Max);
822 if (Log2Z < Log2Max) {
823 return X * Y;
824 }
825 if (Log2Z > Log2Max) {
826 Overflowed = true;
827 return Max;
828 }
829
830 // We're going to use the top bit, and maybe overflow one
831 // bit past it. Multiply all but the bottom bit then add
832 // that on at the end.
833 T Z = (X >> 1) * Y;
834 if (Z & ~(Max >> 1)) {
835 Overflowed = true;
836 return Max;
837 }
838 Z <<= 1;
839 if (X & 1)
840 return SaturatingAdd(Z, Y, ResultOverflowed);
841
842 return Z;
843}
844
845/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
846/// the product. Clamp the result to the maximum representable value of T on
847/// overflow. ResultOverflowed indicates if the result is larger than the
848/// maximum representable value of type T.
849template <typename T>
850typename std::enable_if<std::is_unsigned<T>::value, T>::type
851SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
852 bool Dummy;
853 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
854
855 T Product = SaturatingMultiply(X, Y, &Overflowed);
856 if (Overflowed)
857 return Product;
858
859 return SaturatingAdd(A, Product, &Overflowed);
860}
861
862/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
863extern const float huge_valf;
864
865
866/// Add two signed integers, computing the two's complement truncated result,
867/// returning true if overflow occured.
868template <typename T>
869typename std::enable_if<std::is_signed<T>::value, T>::type
870AddOverflow(T X, T Y, T &Result) {
871#if __has_builtin(__builtin_add_overflow)1
872 return __builtin_add_overflow(X, Y, &Result);
873#else
874 // Perform the unsigned addition.
875 using U = typename std::make_unsigned<T>::type;
876 const U UX = static_cast<U>(X);
877 const U UY = static_cast<U>(Y);
878 const U UResult = UX + UY;
879
880 // Convert to signed.
881 Result = static_cast<T>(UResult);
882
883 // Adding two positive numbers should result in a positive number.
884 if (X > 0 && Y > 0)
885 return Result <= 0;
886 // Adding two negatives should result in a negative number.
887 if (X < 0 && Y < 0)
888 return Result >= 0;
889 return false;
890#endif
891}
892
893/// Subtract two signed integers, computing the two's complement truncated
894/// result, returning true if an overflow ocurred.
895template <typename T>
896typename std::enable_if<std::is_signed<T>::value, T>::type
897SubOverflow(T X, T Y, T &Result) {
898#if __has_builtin(__builtin_sub_overflow)1
899 return __builtin_sub_overflow(X, Y, &Result);
900#else
901 // Perform the unsigned addition.
902 using U = typename std::make_unsigned<T>::type;
903 const U UX = static_cast<U>(X);
904 const U UY = static_cast<U>(Y);
905 const U UResult = UX - UY;
906
907 // Convert to signed.
908 Result = static_cast<T>(UResult);
909
910 // Subtracting a positive number from a negative results in a negative number.
911 if (X <= 0 && Y > 0)
912 return Result >= 0;
913 // Subtracting a negative number from a positive results in a positive number.
914 if (X >= 0 && Y < 0)
915 return Result <= 0;
916 return false;
917#endif
918}
919
920
921/// Multiply two signed integers, computing the two's complement truncated
922/// result, returning true if an overflow ocurred.
923template <typename T>
924typename std::enable_if<std::is_signed<T>::value, T>::type
925MulOverflow(T X, T Y, T &Result) {
926 // Perform the unsigned multiplication on absolute values.
927 using U = typename std::make_unsigned<T>::type;
928 const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
929 const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
930 const U UResult = UX * UY;
931
932 // Convert to signed.
933 const bool IsNegative = (X < 0) ^ (Y < 0);
934 Result = IsNegative ? (0 - UResult) : UResult;
935
936 // If any of the args was 0, result is 0 and no overflow occurs.
937 if (UX == 0 || UY == 0)
938 return false;
939
940 // UX and UY are in [1, 2^n], where n is the number of digits.
941 // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
942 // positive) divided by an argument compares to the other.
943 if (IsNegative)
944 return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
945 else
946 return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
947}
948
949} // End llvm namespace
950
951#endif