Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
Warning:line 45, column 25
The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'unsigned long long'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DWARFDie.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 -setup-static-analyzer -mrelocation-model pic -pic-level 1 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -D PIC -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -D_RET_PROTECTOR -ret-protector -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp

→
1//===- DWARFDie.cpp -------------------------------------------------------===//
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/DebugInfo/DWARF/DWARFDie.h"
10#include "llvm/ADT/None.h"
11#include "llvm/ADT/Optional.h"
12#include "llvm/ADT/SmallSet.h"
13#include "llvm/ADT/StringRef.h"
14#include "llvm/BinaryFormat/Dwarf.h"
15#include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
16#include "llvm/DebugInfo/DWARF/DWARFContext.h"
17#include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
18#include "llvm/DebugInfo/DWARF/DWARFExpression.h"
19#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
20#include "llvm/DebugInfo/DWARF/DWARFUnit.h"
21#include "llvm/Object/ObjectFile.h"
22#include "llvm/Support/DataExtractor.h"
23#include "llvm/Support/Format.h"
24#include "llvm/Support/FormatAdapters.h"
25#include "llvm/Support/FormatVariadic.h"
26#include "llvm/Support/MathExtras.h"
27#include "llvm/Support/WithColor.h"
28#include "llvm/Support/raw_ostream.h"
29#include <algorithm>
30#include <cassert>
31#include <cinttypes>
32#include <cstdint>
33#include <string>
34#include <utility>
35
36using namespace llvm;
37using namespace dwarf;
38using namespace object;
39
40static void dumpApplePropertyAttribute(raw_ostream &OS, uint64_t Val) {
41 OS << " (";
42 do {
43 uint64_t Shift = countTrailingZeros(Val);
46
←
Calling 'countTrailingZeros<unsigned long long>'
→
53
←
Returning from 'countTrailingZeros<unsigned long long>'
→
54
←
'Shift' initialized to 64
→
44 assert(Shift < 64 && "undefined behavior")((void)0);
45 uint64_t Bit = 1ULL << Shift;
55
←
The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'unsigned long long'
46 auto PropName = ApplePropertyString(Bit);
47 if (!PropName.empty())
48 OS << PropName;
49 else
50 OS << format("DW_APPLE_PROPERTY_0x%" PRIx64"llx", Bit);
51 if (!(Val ^= Bit))
52 break;
53 OS << ", ";
54 } while (true);
55 OS << ")";
56}
57
58static void dumpRanges(const DWARFObject &Obj, raw_ostream &OS,
59 const DWARFAddressRangesVector &Ranges,
60 unsigned AddressSize, unsigned Indent,
61 const DIDumpOptions &DumpOpts) {
62 if (!DumpOpts.ShowAddresses)
63 return;
64
65 for (const DWARFAddressRange &R : Ranges) {
66 OS << '\n';
67 OS.indent(Indent);
68 R.dump(OS, AddressSize, DumpOpts, &Obj);
69 }
70}
71
72static void dumpLocationList(raw_ostream &OS, const DWARFFormValue &FormValue,
73 DWARFUnit *U, unsigned Indent,
74 DIDumpOptions DumpOpts) {
75 assert(FormValue.isFormClass(DWARFFormValue::FC_SectionOffset) &&((void)0)
76 "bad FORM for location list")((void)0);
77 DWARFContext &Ctx = U->getContext();
78 const MCRegisterInfo *MRI = Ctx.getRegisterInfo();
79 uint64_t Offset = *FormValue.getAsSectionOffset();
80
81 if (FormValue.getForm() == DW_FORM_loclistx) {
82 FormValue.dump(OS, DumpOpts);
83
84 if (auto LoclistOffset = U->getLoclistOffset(Offset))
85 Offset = *LoclistOffset;
86 else
87 return;
88 }
89 U->getLocationTable().dumpLocationList(&Offset, OS, U->getBaseAddress(), MRI,
90 Ctx.getDWARFObj(), U, DumpOpts,
91 Indent);
92 return;
93}
94
95static void dumpLocationExpr(raw_ostream &OS, const DWARFFormValue &FormValue,
96 DWARFUnit *U, unsigned Indent,
97 DIDumpOptions DumpOpts) {
98 assert((FormValue.isFormClass(DWARFFormValue::FC_Block) ||((void)0)
99 FormValue.isFormClass(DWARFFormValue::FC_Exprloc)) &&((void)0)
100 "bad FORM for location expression")((void)0);
101 DWARFContext &Ctx = U->getContext();
102 const MCRegisterInfo *MRI = Ctx.getRegisterInfo();
103 ArrayRef<uint8_t> Expr = *FormValue.getAsBlock();
104 DataExtractor Data(StringRef((const char *)Expr.data(), Expr.size()),
105 Ctx.isLittleEndian(), 0);
106 DWARFExpression(Data, U->getAddressByteSize(), U->getFormParams().Format)
107 .print(OS, DumpOpts, MRI, U);
108 return;
109}
110
111/// Dump the name encoded in the type tag.
112static void dumpTypeTagName(raw_ostream &OS, dwarf::Tag T) {
113 StringRef TagStr = TagString(T);
114 if (!TagStr.startswith("DW_TAG_") || !TagStr.endswith("_type"))
115 return;
116 OS << TagStr.substr(7, TagStr.size() - 12) << " ";
117}
118
119static void dumpArrayType(raw_ostream &OS, const DWARFDie &D) {
120 for (const DWARFDie &C : D.children())
121 if (C.getTag() == DW_TAG_subrange_type) {
122 Optional<uint64_t> LB;
123 Optional<uint64_t> Count;
124 Optional<uint64_t> UB;
125 Optional<unsigned> DefaultLB;
126 if (Optional<DWARFFormValue> L = C.find(DW_AT_lower_bound))
127 LB = L->getAsUnsignedConstant();
128 if (Optional<DWARFFormValue> CountV = C.find(DW_AT_count))
129 Count = CountV->getAsUnsignedConstant();
130 if (Optional<DWARFFormValue> UpperV = C.find(DW_AT_upper_bound))
131 UB = UpperV->getAsUnsignedConstant();
132 if (Optional<DWARFFormValue> LV =
133 D.getDwarfUnit()->getUnitDIE().find(DW_AT_language))
134 if (Optional<uint64_t> LC = LV->getAsUnsignedConstant())
135 if ((DefaultLB =
136 LanguageLowerBound(static_cast<dwarf::SourceLanguage>(*LC))))
137 if (LB && *LB == *DefaultLB)
138 LB = None;
139 if (!LB && !Count && !UB)
140 OS << "[]";
141 else if (!LB && (Count || UB) && DefaultLB)
142 OS << '[' << (Count ? *Count : *UB - *DefaultLB + 1) << ']';
143 else {
144 OS << "[[";
145 if (LB)
146 OS << *LB;
147 else
148 OS << '?';
149 OS << ", ";
150 if (Count)
151 if (LB)
152 OS << *LB + *Count;
153 else
154 OS << "? + " << *Count;
155 else if (UB)
156 OS << *UB + 1;
157 else
158 OS << '?';
159 OS << ")]";
160 }
161 }
162}
163
164/// Recursively dump the DIE type name when applicable.
165static void dumpTypeName(raw_ostream &OS, const DWARFDie &D) {
166 if (!D.isValid())
167 return;
168
169 if (const char *Name = D.getName(DINameKind::LinkageName)) {
170 OS << Name;
171 return;
172 }
173
174 // FIXME: We should have pretty printers per language. Currently we print
175 // everything as if it was C++ and fall back to the TAG type name.
176 const dwarf::Tag T = D.getTag();
177 switch (T) {
178 case DW_TAG_array_type:
179 case DW_TAG_pointer_type:
180 case DW_TAG_ptr_to_member_type:
181 case DW_TAG_reference_type:
182 case DW_TAG_rvalue_reference_type:
183 case DW_TAG_subroutine_type:
184 break;
185 default:
186 dumpTypeTagName(OS, T);
187 }
188
189 // Follow the DW_AT_type if possible.
190 DWARFDie TypeDie = D.getAttributeValueAsReferencedDie(DW_AT_type);
191 dumpTypeName(OS, TypeDie);
192
193 switch (T) {
194 case DW_TAG_subroutine_type: {
195 if (!TypeDie)
196 OS << "void";
197 OS << '(';
198 bool First = true;
199 for (const DWARFDie &C : D.children()) {
200 if (C.getTag() == DW_TAG_formal_parameter) {
201 if (!First)
202 OS << ", ";
203 First = false;
204 dumpTypeName(OS, C.getAttributeValueAsReferencedDie(DW_AT_type));
205 }
206 }
207 OS << ')';
208 break;
209 }
210 case DW_TAG_array_type: {
211 dumpArrayType(OS, D);
212 break;
213 }
214 case DW_TAG_pointer_type:
215 OS << '*';
216 break;
217 case DW_TAG_ptr_to_member_type:
218 if (DWARFDie Cont =
219 D.getAttributeValueAsReferencedDie(DW_AT_containing_type)) {
220 dumpTypeName(OS << ' ', Cont);
221 OS << "::";
222 }
223 OS << '*';
224 break;
225 case DW_TAG_reference_type:
226 OS << '&';
227 break;
228 case DW_TAG_rvalue_reference_type:
229 OS << "&&";
230 break;
231 default:
232 break;
233 }
234}
235
236static void dumpAttribute(raw_ostream &OS, const DWARFDie &Die,
237 const DWARFAttribute &AttrValue, unsigned Indent,
238 DIDumpOptions DumpOpts) {
239 if (!Die.isValid())
16
←
Assuming the condition is false
→
17
←
Taking false branch
→
240 return;
241 const char BaseIndent[] = " ";
242 OS << BaseIndent;
243 OS.indent(Indent + 2);
244 dwarf::Attribute Attr = AttrValue.Attr;
245 WithColor(OS, HighlightColor::Attribute) << formatv("{0}", Attr);
246
247 dwarf::Form Form = AttrValue.Value.getForm();
248 if (DumpOpts.Verbose
17.1
Field 'Verbose' is false
17.1
Field 'Verbose' is false
 || DumpOpts.ShowForm)
18
←
Assuming field 'ShowForm' is false
→
19
←
Taking false branch
→
249 OS << formatv(" [{0}]", Form);
250
251 DWARFUnit *U = Die.getDwarfUnit();
252 const DWARFFormValue &FormValue = AttrValue.Value;
253
254 OS << "\t(";
255
256 StringRef Name;
257 std::string File;
258 auto Color = HighlightColor::Enumerator;
259 if (Attr == DW_AT_decl_file || Attr == DW_AT_call_file) {
20
←
Assuming 'Attr' is not equal to DW_AT_decl_file
→
21
←
Assuming 'Attr' is not equal to DW_AT_call_file
→
22
←
Taking false branch
→
260 Color = HighlightColor::String;
261 if (const auto *LT = U->getContext().getLineTableForUnit(U))
262 if (LT->getFileNameByIndex(
263 FormValue.getAsUnsignedConstant().getValue(),
264 U->getCompilationDir(),
265 DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, File)) {
266 File = '"' + File + '"';
267 Name = File;
268 }
269 } else if (Optional<uint64_t> Val = FormValue.getAsUnsignedConstant())
23
←
Assuming the condition is false
→
24
←
Taking false branch
→
270 Name = AttributeValueString(Attr, *Val);
271
272 if (!Name.empty())
25
←
Assuming the condition is false
→
26
←
Taking false branch
→
273 WithColor(OS, Color) << Name;
274 else if (Attr == DW_AT_decl_line || Attr == DW_AT_call_line)
27
←
Assuming 'Attr' is not equal to DW_AT_decl_line
→
28
←
Assuming 'Attr' is not equal to DW_AT_call_line
→
29
←
Taking false branch
→
275 OS << *FormValue.getAsUnsignedConstant();
276 else if (Attr == DW_AT_low_pc &&
30
←
Assuming 'Attr' is not equal to DW_AT_low_pc
→
31
←
Taking false branch
→
277 (FormValue.getAsAddress() ==
278 dwarf::computeTombstoneAddress(U->getAddressByteSize()))) {
279 if (DumpOpts.Verbose) {
280 FormValue.dump(OS, DumpOpts);
281 OS << " (";
282 }
283 OS << "dead code";
284 if (DumpOpts.Verbose)
285 OS << ')';
286 } else if (Attr == DW_AT_high_pc && !DumpOpts.ShowForm && !DumpOpts.Verbose &&
32
←
Assuming 'Attr' is not equal to DW_AT_high_pc
→
33
←
Taking false branch
→
287 FormValue.getAsUnsignedConstant()) {
288 if (DumpOpts.ShowAddresses) {
289 // Print the actual address rather than the offset.
290 uint64_t LowPC, HighPC, Index;
291 if (Die.getLowAndHighPC(LowPC, HighPC, Index))
292 DWARFFormValue::dumpAddress(OS, U->getAddressByteSize(), HighPC);
293 else
294 FormValue.dump(OS, DumpOpts);
295 }
296 } else if (DWARFAttribute::mayHaveLocationList(Attr) &&
297 FormValue.isFormClass(DWARFFormValue::FC_SectionOffset))
298 dumpLocationList(OS, FormValue, U, sizeof(BaseIndent) + Indent + 4,
299 DumpOpts);
300 else if (FormValue.isFormClass(DWARFFormValue::FC_Exprloc) ||
34
←
Assuming the condition is false
→
301 (DWARFAttribute::mayHaveLocationExpr(Attr) &&
302 FormValue.isFormClass(DWARFFormValue::FC_Block)))
303 dumpLocationExpr(OS, FormValue, U, sizeof(BaseIndent) + Indent + 4,
304 DumpOpts);
305 else
306 FormValue.dump(OS, DumpOpts);
307
308 std::string Space = DumpOpts.ShowAddresses
34.1
Field 'ShowAddresses' is false
34.1
Field 'ShowAddresses' is false
 ? " " : "";
35
←
'?' condition is false
→
309
310 // We have dumped the attribute raw value. For some attributes
311 // having both the raw value and the pretty-printed value is
312 // interesting. These attributes are handled below.
313 if (Attr == DW_AT_specification || Attr == DW_AT_abstract_origin) {
36
←
Assuming 'Attr' is not equal to DW_AT_specification
→
37
←
Assuming 'Attr' is not equal to DW_AT_abstract_origin
→
38
←
Taking false branch
→
314 if (const char *Name =
315 Die.getAttributeValueAsReferencedDie(FormValue).getName(
316 DINameKind::LinkageName))
317 OS << Space << "\"" << Name << '\"';
318 } else if (Attr == DW_AT_type) {
39
←
Assuming 'Attr' is not equal to DW_AT_type
→
40
←
Taking false branch
→
319 OS << Space << "\"";
320 dumpTypeName(OS, Die.getAttributeValueAsReferencedDie(FormValue));
321 OS << '"';
322 } else if (Attr == DW_AT_APPLE_property_attribute) {
41
←
Assuming 'Attr' is equal to DW_AT_APPLE_property_attribute
→
42
←
Taking true branch
→
323 if (Optional<uint64_t> OptVal = FormValue.getAsUnsignedConstant())
43
←
Assuming the condition is true
→
44
←
Taking true branch
→
324 dumpApplePropertyAttribute(OS, *OptVal);
45
←
Calling 'dumpApplePropertyAttribute'
→
325 } else if (Attr == DW_AT_ranges) {
326 const DWARFObject &Obj = Die.getDwarfUnit()->getContext().getDWARFObj();
327 // For DW_FORM_rnglistx we need to dump the offset separately, since
328 // we have only dumped the index so far.
329 if (FormValue.getForm() == DW_FORM_rnglistx)
330 if (auto RangeListOffset =
331 U->getRnglistOffset(*FormValue.getAsSectionOffset())) {
332 DWARFFormValue FV = DWARFFormValue::createFromUValue(
333 dwarf::DW_FORM_sec_offset, *RangeListOffset);
334 FV.dump(OS, DumpOpts);
335 }
336 if (auto RangesOrError = Die.getAddressRanges())
337 dumpRanges(Obj, OS, RangesOrError.get(), U->getAddressByteSize(),
338 sizeof(BaseIndent) + Indent + 4, DumpOpts);
339 else
340 DumpOpts.RecoverableErrorHandler(createStringError(
341 errc::invalid_argument, "decoding address ranges: %s",
342 toString(RangesOrError.takeError()).c_str()));
343 }
344
345 OS << ")\n";
346}
347
348bool DWARFDie::isSubprogramDIE() const { return getTag() == DW_TAG_subprogram; }
349
350bool DWARFDie::isSubroutineDIE() const {
351 auto Tag = getTag();
352 return Tag == DW_TAG_subprogram || Tag == DW_TAG_inlined_subroutine;
353}
354
355Optional<DWARFFormValue> DWARFDie::find(dwarf::Attribute Attr) const {
356 if (!isValid())
357 return None;
358 auto AbbrevDecl = getAbbreviationDeclarationPtr();
359 if (AbbrevDecl)
360 return AbbrevDecl->getAttributeValue(getOffset(), Attr, *U);
361 return None;
362}
363
364Optional<DWARFFormValue>
365DWARFDie::find(ArrayRef<dwarf::Attribute> Attrs) const {
366 if (!isValid())
367 return None;
368 auto AbbrevDecl = getAbbreviationDeclarationPtr();
369 if (AbbrevDecl) {
370 for (auto Attr : Attrs) {
371 if (auto Value = AbbrevDecl->getAttributeValue(getOffset(), Attr, *U))
372 return Value;
373 }
374 }
375 return None;
376}
377
378Optional<DWARFFormValue>
379DWARFDie::findRecursively(ArrayRef<dwarf::Attribute> Attrs) const {
380 SmallVector<DWARFDie, 3> Worklist;
381 Worklist.push_back(*this);
382
383 // Keep track if DIEs already seen to prevent infinite recursion.
384 // Empirically we rarely see a depth of more than 3 when dealing with valid
385 // DWARF. This corresponds to following the DW_AT_abstract_origin and
386 // DW_AT_specification just once.
387 SmallSet<DWARFDie, 3> Seen;
388 Seen.insert(*this);
389
390 while (!Worklist.empty()) {
391 DWARFDie Die = Worklist.pop_back_val();
392
393 if (!Die.isValid())
394 continue;
395
396 if (auto Value = Die.find(Attrs))
397 return Value;
398
399 if (auto D = Die.getAttributeValueAsReferencedDie(DW_AT_abstract_origin))
400 if (Seen.insert(D).second)
401 Worklist.push_back(D);
402
403 if (auto D = Die.getAttributeValueAsReferencedDie(DW_AT_specification))
404 if (Seen.insert(D).second)
405 Worklist.push_back(D);
406 }
407
408 return None;
409}
410
411DWARFDie
412DWARFDie::getAttributeValueAsReferencedDie(dwarf::Attribute Attr) const {
413 if (Optional<DWARFFormValue> F = find(Attr))
414 return getAttributeValueAsReferencedDie(*F);
415 return DWARFDie();
416}
417
418DWARFDie
419DWARFDie::getAttributeValueAsReferencedDie(const DWARFFormValue &V) const {
420 if (auto SpecRef = V.getAsRelativeReference()) {
421 if (SpecRef->Unit)
422 return SpecRef->Unit->getDIEForOffset(SpecRef->Unit->getOffset() + SpecRef->Offset);
423 if (auto SpecUnit = U->getUnitVector().getUnitForOffset(SpecRef->Offset))
424 return SpecUnit->getDIEForOffset(SpecRef->Offset);
425 }
426 return DWARFDie();
427}
428
429Optional<uint64_t> DWARFDie::getRangesBaseAttribute() const {
430 return toSectionOffset(find({DW_AT_rnglists_base, DW_AT_GNU_ranges_base}));
431}
432
433Optional<uint64_t> DWARFDie::getLocBaseAttribute() const {
434 return toSectionOffset(find(DW_AT_loclists_base));
435}
436
437Optional<uint64_t> DWARFDie::getHighPC(uint64_t LowPC) const {
438 uint64_t Tombstone = dwarf::computeTombstoneAddress(U->getAddressByteSize());
439 if (LowPC == Tombstone)
440 return None;
441 if (auto FormValue = find(DW_AT_high_pc)) {
442 if (auto Address = FormValue->getAsAddress()) {
443 // High PC is an address.
444 return Address;
445 }
446 if (auto Offset = FormValue->getAsUnsignedConstant()) {
447 // High PC is an offset from LowPC.
448 return LowPC + *Offset;
449 }
450 }
451 return None;
452}
453
454bool DWARFDie::getLowAndHighPC(uint64_t &LowPC, uint64_t &HighPC,
455 uint64_t &SectionIndex) const {
456 auto F = find(DW_AT_low_pc);
457 auto LowPcAddr = toSectionedAddress(F);
458 if (!LowPcAddr)
459 return false;
460 if (auto HighPcAddr = getHighPC(LowPcAddr->Address)) {
461 LowPC = LowPcAddr->Address;
462 HighPC = *HighPcAddr;
463 SectionIndex = LowPcAddr->SectionIndex;
464 return true;
465 }
466 return false;
467}
468
469Expected<DWARFAddressRangesVector> DWARFDie::getAddressRanges() const {
470 if (isNULL())
471 return DWARFAddressRangesVector();
472 // Single range specified by low/high PC.
473 uint64_t LowPC, HighPC, Index;
474 if (getLowAndHighPC(LowPC, HighPC, Index))
475 return DWARFAddressRangesVector{{LowPC, HighPC, Index}};
476
477 Optional<DWARFFormValue> Value = find(DW_AT_ranges);
478 if (Value) {
479 if (Value->getForm() == DW_FORM_rnglistx)
480 return U->findRnglistFromIndex(*Value->getAsSectionOffset());
481 return U->findRnglistFromOffset(*Value->getAsSectionOffset());
482 }
483 return DWARFAddressRangesVector();
484}
485
486void DWARFDie::collectChildrenAddressRanges(
487 DWARFAddressRangesVector &Ranges) const {
488 if (isNULL())
489 return;
490 if (isSubprogramDIE()) {
491 if (auto DIERangesOrError = getAddressRanges())
492 llvm::append_range(Ranges, DIERangesOrError.get());
493 else
494 llvm::consumeError(DIERangesOrError.takeError());
495 }
496
497 for (auto Child : children())
498 Child.collectChildrenAddressRanges(Ranges);
499}
500
501bool DWARFDie::addressRangeContainsAddress(const uint64_t Address) const {
502 auto RangesOrError = getAddressRanges();
503 if (!RangesOrError) {
504 llvm::consumeError(RangesOrError.takeError());
505 return false;
506 }
507
508 for (const auto &R : RangesOrError.get())
509 if (R.LowPC <= Address && Address < R.HighPC)
510 return true;
511 return false;
512}
513
514Expected<DWARFLocationExpressionsVector>
515DWARFDie::getLocations(dwarf::Attribute Attr) const {
516 Optional<DWARFFormValue> Location = find(Attr);
517 if (!Location)
518 return createStringError(inconvertibleErrorCode(), "No %s",
519 dwarf::AttributeString(Attr).data());
520
521 if (Optional<uint64_t> Off = Location->getAsSectionOffset()) {
522 uint64_t Offset = *Off;
523
524 if (Location->getForm() == DW_FORM_loclistx) {
525 if (auto LoclistOffset = U->getLoclistOffset(Offset))
526 Offset = *LoclistOffset;
527 else
528 return createStringError(inconvertibleErrorCode(),
529 "Loclist table not found");
530 }
531 return U->findLoclistFromOffset(Offset);
532 }
533
534 if (Optional<ArrayRef<uint8_t>> Expr = Location->getAsBlock()) {
535 return DWARFLocationExpressionsVector{
536 DWARFLocationExpression{None, to_vector<4>(*Expr)}};
537 }
538
539 return createStringError(
540 inconvertibleErrorCode(), "Unsupported %s encoding: %s",
541 dwarf::AttributeString(Attr).data(),
542 dwarf::FormEncodingString(Location->getForm()).data());
543}
544
545const char *DWARFDie::getSubroutineName(DINameKind Kind) const {
546 if (!isSubroutineDIE())
547 return nullptr;
548 return getName(Kind);
549}
550
551const char *DWARFDie::getName(DINameKind Kind) const {
552 if (!isValid() || Kind == DINameKind::None)
553 return nullptr;
554 // Try to get mangled name only if it was asked for.
555 if (Kind == DINameKind::LinkageName) {
556 if (auto Name = getLinkageName())
557 return Name;
558 }
559 return getShortName();
560}
561
562const char *DWARFDie::getShortName() const {
563 if (!isValid())
564 return nullptr;
565
566 return dwarf::toString(findRecursively(dwarf::DW_AT_name), nullptr);
567}
568
569const char *DWARFDie::getLinkageName() const {
570 if (!isValid())
571 return nullptr;
572
573 return dwarf::toString(findRecursively({dwarf::DW_AT_MIPS_linkage_name,
574 dwarf::DW_AT_linkage_name}),
575 nullptr);
576}
577
578uint64_t DWARFDie::getDeclLine() const {
579 return toUnsigned(findRecursively(DW_AT_decl_line), 0);
580}
581
582std::string
583DWARFDie::getDeclFile(DILineInfoSpecifier::FileLineInfoKind Kind) const {
584 auto D = getAttributeValueAsReferencedDie(DW_AT_abstract_origin);
585 if (!D)
586 D = *this;
587 std::string FileName;
588 if (auto DeclFile = toUnsigned(D.find(DW_AT_decl_file))) {
589 if (const auto *LineTable =
590 getDwarfUnit()->getContext().getLineTableForUnit(
591 D.getDwarfUnit()->getLinkedUnit()))
592 LineTable->getFileNameByIndex(
593 *DeclFile, D.getDwarfUnit()->getCompilationDir(), Kind, FileName);
594 }
595 return FileName;
596}
597
598void DWARFDie::getCallerFrame(uint32_t &CallFile, uint32_t &CallLine,
599 uint32_t &CallColumn,
600 uint32_t &CallDiscriminator) const {
601 CallFile = toUnsigned(find(DW_AT_call_file), 0);
602 CallLine = toUnsigned(find(DW_AT_call_line), 0);
603 CallColumn = toUnsigned(find(DW_AT_call_column), 0);
604 CallDiscriminator = toUnsigned(find(DW_AT_GNU_discriminator), 0);
605}
606
607/// Helper to dump a DIE with all of its parents, but no siblings.
608static unsigned dumpParentChain(DWARFDie Die, raw_ostream &OS, unsigned Indent,
609 DIDumpOptions DumpOpts, unsigned Depth = 0) {
610 if (!Die)
611 return Indent;
612 if (DumpOpts.ParentRecurseDepth > 0 && Depth >= DumpOpts.ParentRecurseDepth)
613 return Indent;
614 Indent = dumpParentChain(Die.getParent(), OS, Indent, DumpOpts, Depth + 1);
615 Die.dump(OS, Indent, DumpOpts);
616 return Indent + 2;
617}
618
619void DWARFDie::dump(raw_ostream &OS, unsigned Indent,
620 DIDumpOptions DumpOpts) const {
621 if (!isValid())
2
←
Assuming the condition is false
→
3
←
Taking false branch
→
622 return;
623 DWARFDataExtractor debug_info_data = U->getDebugInfoExtractor();
624 const uint64_t Offset = getOffset();
625 uint64_t offset = Offset;
626 if (DumpOpts.ShowParents) {
4
←
Assuming field 'ShowParents' is false
→
5
←
Taking false branch
→
627 DIDumpOptions ParentDumpOpts = DumpOpts;
628 ParentDumpOpts.ShowParents = false;
629 ParentDumpOpts.ShowChildren = false;
630 Indent = dumpParentChain(getParent(), OS, Indent, ParentDumpOpts);
631 }
632
633 if (debug_info_data.isValidOffset(offset)) {
6
←
Taking true branch
→
634 uint32_t abbrCode = debug_info_data.getULEB128(&offset);
635 if (DumpOpts.ShowAddresses)
7
←
Assuming field 'ShowAddresses' is false
→
8
←
Taking false branch
→
636 WithColor(OS, HighlightColor::Address).get()
637 << format("\n0x%8.8" PRIx64"llx" ": ", Offset);
638
639 if (abbrCode) {
9
←
Assuming 'abbrCode' is not equal to 0
→
10
←
Taking true branch
→
640 auto AbbrevDecl = getAbbreviationDeclarationPtr();
641 if (AbbrevDecl) {
11
←
Assuming 'AbbrevDecl' is non-null
→
12
←
Taking true branch
→
642 WithColor(OS, HighlightColor::Tag).get().indent(Indent)
643 << formatv("{0}", getTag());
644 if (DumpOpts.Verbose)
13
←
Assuming field 'Verbose' is false
→
14
←
Taking false branch
→
645 OS << format(" [%u] %c", abbrCode,
646 AbbrevDecl->hasChildren() ? '*' : ' ');
647 OS << '\n';
648
649 // Dump all data in the DIE for the attributes.
650 for (const DWARFAttribute &AttrValue : attributes())
651 dumpAttribute(OS, *this, AttrValue, Indent, DumpOpts);
15
←
Calling 'dumpAttribute'
→
652
653 if (DumpOpts.ShowChildren && DumpOpts.ChildRecurseDepth > 0) {
654 DWARFDie Child = getFirstChild();
655 DumpOpts.ChildRecurseDepth--;
656 DIDumpOptions ChildDumpOpts = DumpOpts;
657 ChildDumpOpts.ShowParents = false;
658 while (Child) {
659 Child.dump(OS, Indent + 2, ChildDumpOpts);
660 Child = Child.getSibling();
661 }
662 }
663 } else {
664 OS << "Abbreviation code not found in 'debug_abbrev' class for code: "
665 << abbrCode << '\n';
666 }
667 } else {
668 OS.indent(Indent) << "NULL\n";
669 }
670 }
671}
672
673LLVM_DUMP_METHOD__attribute__((noinline)) void DWARFDie::dump() const { dump(llvm::errs(), 0); }
1
Calling 'DWARFDie::dump'
→
674
675DWARFDie DWARFDie::getParent() const {
676 if (isValid())
677 return U->getParent(Die);
678 return DWARFDie();
679}
680
681DWARFDie DWARFDie::getSibling() const {
682 if (isValid())
683 return U->getSibling(Die);
684 return DWARFDie();
685}
686
687DWARFDie DWARFDie::getPreviousSibling() const {
688 if (isValid())
689 return U->getPreviousSibling(Die);
690 return DWARFDie();
691}
692
693DWARFDie DWARFDie::getFirstChild() const {
694 if (isValid())
695 return U->getFirstChild(Die);
696 return DWARFDie();
697}
698
699DWARFDie DWARFDie::getLastChild() const {
700 if (isValid())
701 return U->getLastChild(Die);
702 return DWARFDie();
703}
704
705iterator_range<DWARFDie::attribute_iterator> DWARFDie::attributes() const {
706 return make_range(attribute_iterator(*this, false),
707 attribute_iterator(*this, true));
708}
709
710DWARFDie::attribute_iterator::attribute_iterator(DWARFDie D, bool End)
711 : Die(D), Index(0) {
712 auto AbbrDecl = Die.getAbbreviationDeclarationPtr();
713 assert(AbbrDecl && "Must have abbreviation declaration")((void)0);
714 if (End) {
715 // This is the end iterator so we set the index to the attribute count.
716 Index = AbbrDecl->getNumAttributes();
717 } else {
718 // This is the begin iterator so we extract the value for this->Index.
719 AttrValue.Offset = D.getOffset() + AbbrDecl->getCodeByteSize();
720 updateForIndex(*AbbrDecl, 0);
721 }
722}
723
724void DWARFDie::attribute_iterator::updateForIndex(
725 const DWARFAbbreviationDeclaration &AbbrDecl, uint32_t I) {
726 Index = I;
727 // AbbrDecl must be valid before calling this function.
728 auto NumAttrs = AbbrDecl.getNumAttributes();
729 if (Index < NumAttrs) {
730 AttrValue.Attr = AbbrDecl.getAttrByIndex(Index);
731 // Add the previous byte size of any previous attribute value.
732 AttrValue.Offset += AttrValue.ByteSize;
733 uint64_t ParseOffset = AttrValue.Offset;
734 if (AbbrDecl.getAttrIsImplicitConstByIndex(Index))
735 AttrValue.Value = DWARFFormValue::createFromSValue(
736 AbbrDecl.getFormByIndex(Index),
737 AbbrDecl.getAttrImplicitConstValueByIndex(Index));
738 else {
739 auto U = Die.getDwarfUnit();
740 assert(U && "Die must have valid DWARF unit")((void)0);
741 AttrValue.Value = DWARFFormValue::createFromUnit(
742 AbbrDecl.getFormByIndex(Index), U, &ParseOffset);
743 }
744 AttrValue.ByteSize = ParseOffset - AttrValue.Offset;
745 } else {
746 assert(Index == NumAttrs && "Indexes should be [0, NumAttrs) only")((void)0);
747 AttrValue = {};
748 }
749}
750
751DWARFDie::attribute_iterator &DWARFDie::attribute_iterator::operator++() {
752 if (auto AbbrDecl = Die.getAbbreviationDeclarationPtr())
753 updateForIndex(*AbbrDecl, Index + 1);
754 return *this;
755}
756
757bool DWARFAttribute::mayHaveLocationList(dwarf::Attribute Attr) {
758 switch(Attr) {
759 case DW_AT_location:
760 case DW_AT_string_length:
761 case DW_AT_return_addr:
762 case DW_AT_data_member_location:
763 case DW_AT_frame_base:
764 case DW_AT_static_link:
765 case DW_AT_segment:
766 case DW_AT_use_location:
767 case DW_AT_vtable_elem_location:
768 return true;
769 default:
770 return false;
771 }
772}
773
774bool DWARFAttribute::mayHaveLocationExpr(dwarf::Attribute Attr) {
775 switch (Attr) {
776 // From the DWARF v5 specification.
777 case DW_AT_location:
778 case DW_AT_byte_size:
779 case DW_AT_bit_offset:
780 case DW_AT_bit_size:
781 case DW_AT_string_length:
782 case DW_AT_lower_bound:
783 case DW_AT_return_addr:
784 case DW_AT_bit_stride:
785 case DW_AT_upper_bound:
786 case DW_AT_count:
787 case DW_AT_data_member_location:
788 case DW_AT_frame_base:
789 case DW_AT_segment:
790 case DW_AT_static_link:
791 case DW_AT_use_location:
792 case DW_AT_vtable_elem_location:
793 case DW_AT_allocated:
794 case DW_AT_associated:
795 case DW_AT_data_location:
796 case DW_AT_byte_stride:
797 case DW_AT_rank:
798 case DW_AT_call_value:
799 case DW_AT_call_origin:
800 case DW_AT_call_target:
801 case DW_AT_call_target_clobbered:
802 case DW_AT_call_data_location:
803 case DW_AT_call_data_value:
804 // Extensions.
805 case DW_AT_GNU_call_site_value:
806 case DW_AT_GNU_call_site_target:
807 return true;
808 default:
809 return false;
810 }
811}
←

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