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~svn372306/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen -I /build/llvm-toolchain-snapshot-10~svn372306/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn372306/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~svn372306/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn372306=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-09-19-172240-30738-1 -x c++ /build/llvm-toolchain-snapshot-10~svn372306/lib/CodeGen/ExecutionDomainFix.cpp

/build/llvm-toolchain-snapshot-10~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/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~svn372306/include/llvm/Support/MathExtras.h

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