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 static -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" -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 -stack-protector 2 -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
1 | |
2 | |
3 | |
4 | |
5 | |
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 | |
36 | using namespace llvm; |
37 | using namespace dwarf; |
38 | using namespace object; |
39 | |
40 | static 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"); |
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, Bit); |
51 | if (!(Val ^= Bit)) |
52 | break; |
53 | OS << ", "; |
54 | } while (true); |
55 | OS << ")"; |
56 | } |
57 | |
58 | static 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 | |
72 | static void dumpLocationList(raw_ostream &OS, const DWARFFormValue &FormValue, |
73 | DWARFUnit *U, unsigned Indent, |
74 | DIDumpOptions DumpOpts) { |
75 | assert(FormValue.isFormClass(DWARFFormValue::FC_SectionOffset) && |
76 | "bad FORM for location list"); |
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 | |
95 | static void dumpLocationExpr(raw_ostream &OS, const DWARFFormValue &FormValue, |
96 | DWARFUnit *U, unsigned Indent, |
97 | DIDumpOptions DumpOpts) { |
98 | assert((FormValue.isFormClass(DWARFFormValue::FC_Block) || |
99 | FormValue.isFormClass(DWARFFormValue::FC_Exprloc)) && |
100 | "bad FORM for location expression"); |
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 | |
112 | static 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 | |
119 | static 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 | |
165 | static 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 | |
175 | |
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 | |
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 | |
236 | static 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 | |
|
| |
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 || DumpOpts.ShowForm) |
| 18 | | Assuming field 'ShowForm' is false | |
|
| |
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 | |
|
| |
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 | |
|
| |
270 | Name = AttributeValueString(Attr, *Val); |
271 | |
272 | if (!Name.empty()) |
| 25 | | Assuming the condition is false | |
|
| |
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 | |
|
| |
275 | OS << *FormValue.getAsUnsignedConstant(); |
276 | else if (Attr == DW_AT_low_pc && |
| 30 | | Assuming 'Attr' is not equal to DW_AT_low_pc | |
|
| |
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 | |
|
| |
287 | FormValue.getAsUnsignedConstant()) { |
288 | if (DumpOpts.ShowAddresses) { |
289 | |
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 ? " " : ""; |
| |
309 | |
310 | |
311 | |
312 | |
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 | |
|
| |
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 | |
|
| |
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 | |
|
| |
323 | if (Optional<uint64_t> OptVal = FormValue.getAsUnsignedConstant()) |
| 43 | | Assuming the condition is true | |
|
| |
324 | dumpApplePropertyAttribute(OS, *OptVal); |
| 45 | | Calling 'dumpApplePropertyAttribute' | |
|
325 | } else if (Attr == DW_AT_ranges) { |
326 | const DWARFObject &Obj = Die.getDwarfUnit()->getContext().getDWARFObj(); |
327 | |
328 | |
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 | |
348 | bool DWARFDie::isSubprogramDIE() const { return getTag() == DW_TAG_subprogram; } |
349 | |
350 | bool DWARFDie::isSubroutineDIE() const { |
351 | auto Tag = getTag(); |
352 | return Tag == DW_TAG_subprogram || Tag == DW_TAG_inlined_subroutine; |
353 | } |
354 | |
355 | Optional<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 | |
364 | Optional<DWARFFormValue> |
365 | DWARFDie::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 | |
378 | Optional<DWARFFormValue> |
379 | DWARFDie::findRecursively(ArrayRef<dwarf::Attribute> Attrs) const { |
380 | SmallVector<DWARFDie, 3> Worklist; |
381 | Worklist.push_back(*this); |
382 | |
383 | |
384 | |
385 | |
386 | |
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 | |
411 | DWARFDie |
412 | DWARFDie::getAttributeValueAsReferencedDie(dwarf::Attribute Attr) const { |
413 | if (Optional<DWARFFormValue> F = find(Attr)) |
414 | return getAttributeValueAsReferencedDie(*F); |
415 | return DWARFDie(); |
416 | } |
417 | |
418 | DWARFDie |
419 | DWARFDie::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 | |
429 | Optional<uint64_t> DWARFDie::getRangesBaseAttribute() const { |
430 | return toSectionOffset(find({DW_AT_rnglists_base, DW_AT_GNU_ranges_base})); |
431 | } |
432 | |
433 | Optional<uint64_t> DWARFDie::getLocBaseAttribute() const { |
434 | return toSectionOffset(find(DW_AT_loclists_base)); |
435 | } |
436 | |
437 | Optional<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 | |
444 | return Address; |
445 | } |
446 | if (auto Offset = FormValue->getAsUnsignedConstant()) { |
447 | |
448 | return LowPC + *Offset; |
449 | } |
450 | } |
451 | return None; |
452 | } |
453 | |
454 | bool 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 | |
469 | Expected<DWARFAddressRangesVector> DWARFDie::getAddressRanges() const { |
470 | if (isNULL()) |
471 | return DWARFAddressRangesVector(); |
472 | |
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 | |
486 | void 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 | |
501 | bool 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 | |
514 | Expected<DWARFLocationExpressionsVector> |
515 | DWARFDie::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 | |
545 | const char *DWARFDie::getSubroutineName(DINameKind Kind) const { |
546 | if (!isSubroutineDIE()) |
547 | return nullptr; |
548 | return getName(Kind); |
549 | } |
550 | |
551 | const char *DWARFDie::getName(DINameKind Kind) const { |
552 | if (!isValid() || Kind == DINameKind::None) |
553 | return nullptr; |
554 | |
555 | if (Kind == DINameKind::LinkageName) { |
556 | if (auto Name = getLinkageName()) |
557 | return Name; |
558 | } |
559 | return getShortName(); |
560 | } |
561 | |
562 | const char *DWARFDie::getShortName() const { |
563 | if (!isValid()) |
564 | return nullptr; |
565 | |
566 | return dwarf::toString(findRecursively(dwarf::DW_AT_name), nullptr); |
567 | } |
568 | |
569 | const 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 | |
578 | uint64_t DWARFDie::getDeclLine() const { |
579 | return toUnsigned(findRecursively(DW_AT_decl_line), 0); |
580 | } |
581 | |
582 | std::string |
583 | DWARFDie::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 | |
598 | void 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 | |
608 | static 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 | |
619 | void DWARFDie::dump(raw_ostream &OS, unsigned Indent, |
620 | DIDumpOptions DumpOpts) const { |
621 | if (!isValid()) |
| 2 | | Assuming the condition is false | |
|
| |
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 | |
|
| |
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)) { |
| |
634 | uint32_t abbrCode = debug_info_data.getULEB128(&offset); |
635 | if (DumpOpts.ShowAddresses) |
| 7 | | Assuming field 'ShowAddresses' is false | |
|
| |
636 | WithColor(OS, HighlightColor::Address).get() |
637 | << format("\n0x%8.8" PRIx64 ": ", Offset); |
638 | |
639 | if (abbrCode) { |
| 9 | | Assuming 'abbrCode' is not equal to 0 | |
|
| |
640 | auto AbbrevDecl = getAbbreviationDeclarationPtr(); |
641 | if (AbbrevDecl) { |
| 11 | | Assuming 'AbbrevDecl' is non-null | |
|
| |
642 | WithColor(OS, HighlightColor::Tag).get().indent(Indent) |
643 | << formatv("{0}", getTag()); |
644 | if (DumpOpts.Verbose) |
| 13 | | Assuming field 'Verbose' is false | |
|
| |
645 | OS << format(" [%u] %c", abbrCode, |
646 | AbbrevDecl->hasChildren() ? '*' : ' '); |
647 | OS << '\n'; |
648 | |
649 | |
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 | |
673 | LLVM_DUMP_METHOD void DWARFDie::dump() const { dump(llvm::errs(), 0); } |
| 1 | Calling 'DWARFDie::dump' | |
|
674 | |
675 | DWARFDie DWARFDie::getParent() const { |
676 | if (isValid()) |
677 | return U->getParent(Die); |
678 | return DWARFDie(); |
679 | } |
680 | |
681 | DWARFDie DWARFDie::getSibling() const { |
682 | if (isValid()) |
683 | return U->getSibling(Die); |
684 | return DWARFDie(); |
685 | } |
686 | |
687 | DWARFDie DWARFDie::getPreviousSibling() const { |
688 | if (isValid()) |
689 | return U->getPreviousSibling(Die); |
690 | return DWARFDie(); |
691 | } |
692 | |
693 | DWARFDie DWARFDie::getFirstChild() const { |
694 | if (isValid()) |
695 | return U->getFirstChild(Die); |
696 | return DWARFDie(); |
697 | } |
698 | |
699 | DWARFDie DWARFDie::getLastChild() const { |
700 | if (isValid()) |
701 | return U->getLastChild(Die); |
702 | return DWARFDie(); |
703 | } |
704 | |
705 | iterator_range<DWARFDie::attribute_iterator> DWARFDie::attributes() const { |
706 | return make_range(attribute_iterator(*this, false), |
707 | attribute_iterator(*this, true)); |
708 | } |
709 | |
710 | DWARFDie::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"); |
714 | if (End) { |
715 | |
716 | Index = AbbrDecl->getNumAttributes(); |
717 | } else { |
718 | |
719 | AttrValue.Offset = D.getOffset() + AbbrDecl->getCodeByteSize(); |
720 | updateForIndex(*AbbrDecl, 0); |
721 | } |
722 | } |
723 | |
724 | void DWARFDie::attribute_iterator::updateForIndex( |
725 | const DWARFAbbreviationDeclaration &AbbrDecl, uint32_t I) { |
726 | Index = I; |
727 | |
728 | auto NumAttrs = AbbrDecl.getNumAttributes(); |
729 | if (Index < NumAttrs) { |
730 | AttrValue.Attr = AbbrDecl.getAttrByIndex(Index); |
731 | |
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"); |
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"); |
747 | AttrValue = {}; |
748 | } |
749 | } |
750 | |
751 | DWARFDie::attribute_iterator &DWARFDie::attribute_iterator::operator++() { |
752 | if (auto AbbrDecl = Die.getAbbreviationDeclarationPtr()) |
753 | updateForIndex(*AbbrDecl, Index + 1); |
754 | return *this; |
755 | } |
756 | |
757 | bool 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 | |
774 | bool DWARFAttribute::mayHaveLocationExpr(dwarf::Attribute Attr) { |
775 | switch (Attr) { |
776 | |
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 | |
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 | } |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
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 | |
31 | |
32 | |
33 | extern "C" { |
34 | unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask); |
35 | unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask); |
36 | unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask); |
37 | unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask); |
38 | } |
39 | #endif |
40 | |
41 | namespace llvm { |
42 | |
43 | |
44 | enum ZeroBehavior { |
45 | |
46 | ZB_Undefined, |
47 | |
48 | ZB_Max, |
49 | |
50 | ZB_Width |
51 | }; |
52 | |
53 | |
54 | namespace numbers { |
55 | |
56 | |
57 | constexpr double e = 2.7182818284590452354, |
58 | egamma = .57721566490153286061, |
59 | ln2 = .69314718055994530942, |
60 | ln10 = 2.3025850929940456840, |
61 | log2e = 1.4426950408889634074, |
62 | log10e = .43429448190325182765, |
63 | pi = 3.1415926535897932385, |
64 | inv_pi = .31830988618379067154, |
65 | sqrtpi = 1.7724538509055160273, |
66 | inv_sqrtpi = .56418958354775628695, |
67 | sqrt2 = 1.4142135623730950488, |
68 | inv_sqrt2 = .70710678118654752440, |
69 | sqrt3 = 1.7320508075688772935, |
70 | inv_sqrt3 = .57735026918962576451, |
71 | phi = 1.6180339887498948482; |
72 | constexpr float ef = 2.71828183F, |
73 | egammaf = .577215665F, |
74 | ln2f = .693147181F, |
75 | ln10f = 2.30258509F, |
76 | log2ef = 1.44269504F, |
77 | log10ef = .434294482F, |
78 | pif = 3.14159265F, |
79 | inv_pif = .318309886F, |
80 | sqrtpif = 1.77245385F, |
81 | inv_sqrtpif = .564189584F, |
82 | sqrt2f = 1.41421356F, |
83 | inv_sqrt2f = .707106781F, |
84 | sqrt3f = 1.73205081F, |
85 | inv_sqrt3f = .577350269F, |
86 | phif = 1.61803399F; |
87 | } |
88 | |
89 | namespace detail { |
90 | template <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 | |
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__) || defined(_MSC_VER) |
114 | template <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) || defined(__GNUC__) |
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) |
130 | template <typename T> struct TrailingZerosCounter<T, 8> { |
131 | static unsigned count(T Val, ZeroBehavior ZB) { |
132 | if (ZB != ZB_Undefined && Val == 0) |
| 48 | | Assuming 'Val' is equal to 0 | |
|
| |
133 | return 64; |
| |
134 | |
135 | #if __has_builtin(__builtin_ctzll) || defined(__GNUC__) |
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 | } |
147 | |
148 | |
149 | |
150 | |
151 | |
152 | |
153 | |
154 | |
155 | template <typename T> |
156 | unsigned 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' | |
|
| |
161 | } |
162 | |
163 | namespace detail { |
164 | template <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 | |
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__) || defined(_MSC_VER) |
183 | template <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) || defined(__GNUC__) |
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) |
199 | template <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) || defined(__GNUC__) |
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 | } |
216 | |
217 | |
218 | |
219 | |
220 | |
221 | |
222 | |
223 | |
224 | template <typename T> |
225 | unsigned 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 | |
233 | |
234 | |
235 | |
236 | |
237 | |
238 | |
239 | template <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 | |
247 | |
248 | template <typename T> T maskTrailingOnes(unsigned N) { |
249 | static_assert(std::is_unsigned<T>::value, "Invalid type!"); |
250 | const unsigned Bits = CHAR_BIT * sizeof(T); |
251 | assert(N <= Bits && "Invalid bit index"); |
252 | return N == 0 ? 0 : (T(-1) >> (Bits - N)); |
253 | } |
254 | |
255 | |
256 | |
257 | template <typename T> T maskLeadingOnes(unsigned N) { |
258 | return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N); |
259 | } |
260 | |
261 | |
262 | |
263 | template <typename T> T maskTrailingZeros(unsigned N) { |
264 | return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N); |
265 | } |
266 | |
267 | |
268 | |
269 | template <typename T> T maskLeadingZeros(unsigned N) { |
270 | return maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N); |
271 | } |
272 | |
273 | |
274 | |
275 | |
276 | |
277 | |
278 | |
279 | |
280 | template <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 | |
285 | |
286 | return countLeadingZeros(Val, ZB_Undefined) ^ |
287 | (std::numeric_limits<T>::digits - 1); |
288 | } |
289 | |
290 | |
291 | |
292 | |
293 | static 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 | |
304 | template <typename T> |
305 | T 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) |
316 | template<> |
317 | inline uint8_t reverseBits<uint8_t>(uint8_t Val) { |
318 | return __builtin_bitreverse8(Val); |
319 | } |
320 | #endif |
321 | |
322 | #if __has_builtin(__builtin_bitreverse16) |
323 | template<> |
324 | inline uint16_t reverseBits<uint16_t>(uint16_t Val) { |
325 | return __builtin_bitreverse16(Val); |
326 | } |
327 | #endif |
328 | |
329 | #if __has_builtin(__builtin_bitreverse32) |
330 | template<> |
331 | inline uint32_t reverseBits<uint32_t>(uint32_t Val) { |
332 | return __builtin_bitreverse32(Val); |
333 | } |
334 | #endif |
335 | |
336 | #if __has_builtin(__builtin_bitreverse64) |
337 | template<> |
338 | inline uint64_t reverseBits<uint64_t>(uint64_t Val) { |
339 | return __builtin_bitreverse64(Val); |
340 | } |
341 | #endif |
342 | |
343 | |
344 | |
345 | |
346 | |
347 | |
348 | constexpr inline uint32_t Hi_32(uint64_t Value) { |
349 | return static_cast<uint32_t>(Value >> 32); |
350 | } |
351 | |
352 | |
353 | constexpr inline uint32_t Lo_32(uint64_t Value) { |
354 | return static_cast<uint32_t>(Value); |
355 | } |
356 | |
357 | |
358 | constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) { |
359 | return ((uint64_t)High << 32) | (uint64_t)Low; |
360 | } |
361 | |
362 | |
363 | template <unsigned N> constexpr inline bool isInt(int64_t x) { |
364 | return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1))); |
365 | } |
366 | |
367 | template <> constexpr inline bool isInt<8>(int64_t x) { |
368 | return static_cast<int8_t>(x) == x; |
369 | } |
370 | template <> constexpr inline bool isInt<16>(int64_t x) { |
371 | return static_cast<int16_t>(x) == x; |
372 | } |
373 | template <> constexpr inline bool isInt<32>(int64_t x) { |
374 | return static_cast<int32_t>(x) == x; |
375 | } |
376 | |
377 | |
378 | template <unsigned N, unsigned S> |
379 | constexpr 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) << S) == 0); |
384 | } |
385 | |
386 | |
387 | |
388 | |
389 | |
390 | |
391 | |
392 | |
393 | |
394 | template <unsigned N> |
395 | constexpr 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) << (N)); |
398 | } |
399 | template <unsigned N> |
400 | constexpr inline std::enable_if_t<N >= 64, bool> isUInt(uint64_t) { |
401 | return true; |
402 | } |
403 | |
404 | |
405 | template <> constexpr inline bool isUInt<8>(uint64_t x) { |
406 | return static_cast<uint8_t>(x) == x; |
407 | } |
408 | template <> constexpr inline bool isUInt<16>(uint64_t x) { |
409 | return static_cast<uint16_t>(x) == x; |
410 | } |
411 | template <> constexpr inline bool isUInt<32>(uint64_t x) { |
412 | return static_cast<uint32_t>(x) == x; |
413 | } |
414 | |
415 | |
416 | template <unsigned N, unsigned S> |
417 | constexpr 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 | |
423 | |
424 | return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0); |
425 | } |
426 | |
427 | |
428 | inline uint64_t maxUIntN(uint64_t N) { |
429 | assert(N > 0 && N <= 64 && "integer width out of range"); |
430 | |
431 | |
432 | |
433 | |
434 | |
435 | return UINT64_MAX >> (64 - N); |
436 | } |
437 | |
438 | |
439 | inline int64_t minIntN(int64_t N) { |
440 | assert(N > 0 && N <= 64 && "integer width out of range"); |
441 | |
442 | return UINT64_C(1) + ~(UINT64_C(1) << (N - 1)); |
443 | } |
444 | |
445 | |
446 | inline int64_t maxIntN(int64_t N) { |
447 | assert(N > 0 && N <= 64 && "integer width out of range"); |
448 | |
449 | |
450 | |
451 | return (UINT64_C(1) << (N - 1)) - 1; |
452 | } |
453 | |
454 | |
455 | inline bool isUIntN(unsigned N, uint64_t x) { |
456 | return N >= 64 || x <= maxUIntN(N); |
457 | } |
458 | |
459 | |
460 | inline bool isIntN(unsigned N, int64_t x) { |
461 | return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N)); |
462 | } |
463 | |
464 | |
465 | |
466 | |
467 | constexpr inline bool isMask_32(uint32_t Value) { |
468 | return Value && ((Value + 1) & Value) == 0; |
469 | } |
470 | |
471 | |
472 | |
473 | constexpr inline bool isMask_64(uint64_t Value) { |
474 | return Value && ((Value + 1) & Value) == 0; |
475 | } |
476 | |
477 | |
478 | |
479 | constexpr inline bool isShiftedMask_32(uint32_t Value) { |
480 | return Value && isMask_32((Value - 1) | Value); |
481 | } |
482 | |
483 | |
484 | |
485 | constexpr inline bool isShiftedMask_64(uint64_t Value) { |
486 | return Value && isMask_64((Value - 1) | Value); |
487 | } |
488 | |
489 | |
490 | |
491 | constexpr inline bool isPowerOf2_32(uint32_t Value) { |
492 | return Value && !(Value & (Value - 1)); |
493 | } |
494 | |
495 | |
496 | constexpr inline bool isPowerOf2_64(uint64_t Value) { |
497 | return Value && !(Value & (Value - 1)); |
498 | } |
499 | |
500 | |
501 | |
502 | |
503 | |
504 | |
505 | |
506 | |
507 | |
508 | template <typename T> |
509 | unsigned 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 | |
517 | |
518 | |
519 | |
520 | |
521 | |
522 | |
523 | |
524 | template <typename T> |
525 | unsigned 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 | |
532 | namespace detail { |
533 | template <typename T, std::size_t SizeOfT> struct PopulationCounter { |
534 | static unsigned count(T Value) { |
535 | |
536 | static_assert(SizeOfT <= 4, "Not implemented!"); |
537 | #if defined(__GNUC__) |
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 | |
548 | template <typename T> struct PopulationCounter<T, 8> { |
549 | static unsigned count(T Value) { |
550 | #if defined(__GNUC__) |
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 | } |
562 | |
563 | |
564 | |
565 | |
566 | template <typename T> |
567 | inline 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 | |
575 | |
576 | template <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 | |
582 | template <> constexpr inline size_t CTLog2<1>() { return 0; } |
583 | |
584 | |
585 | inline 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 | |
594 | |
595 | |
596 | inline unsigned Log2_32(uint32_t Value) { |
597 | return 31 - countLeadingZeros(Value); |
598 | } |
599 | |
600 | |
601 | |
602 | inline unsigned Log2_64(uint64_t Value) { |
603 | return 63 - countLeadingZeros(Value); |
604 | } |
605 | |
606 | |
607 | |
608 | |
609 | inline unsigned Log2_32_Ceil(uint32_t Value) { |
610 | return 32 - countLeadingZeros(Value - 1); |
611 | } |
612 | |
613 | |
614 | |
615 | inline unsigned Log2_64_Ceil(uint64_t Value) { |
616 | return 64 - countLeadingZeros(Value - 1); |
617 | } |
618 | |
619 | |
620 | template <typename T> |
621 | inline 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 | |
630 | inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) { |
631 | return greatestCommonDivisor<uint64_t>(A, B); |
632 | } |
633 | |
634 | |
635 | inline 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 | |
643 | inline 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 | |
651 | |
652 | |
653 | inline 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 | |
661 | |
662 | |
663 | inline 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 | |
671 | |
672 | constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) { |
673 | |
674 | |
675 | |
676 | |
677 | |
678 | return (A | B) & (1 + ~(A | B)); |
679 | } |
680 | |
681 | |
682 | |
683 | inline 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 | |
694 | |
695 | inline uint64_t PowerOf2Floor(uint64_t A) { |
696 | if (!A) return 0; |
697 | return 1ull << (63 - countLeadingZeros(A, ZB_Undefined)); |
698 | } |
699 | |
700 | |
701 | |
702 | inline uint64_t PowerOf2Ceil(uint64_t A) { |
703 | if (!A) |
704 | return 0; |
705 | return NextPowerOf2(A - 1); |
706 | } |
707 | |
708 | |
709 | |
710 | |
711 | |
712 | |
713 | |
714 | |
715 | |
716 | |
717 | |
718 | |
719 | |
720 | |
721 | |
722 | |
723 | |
724 | |
725 | |
726 | |
727 | |
728 | inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) { |
729 | assert(Align != 0u && "Align can't be 0."); |
730 | Skew %= Align; |
731 | return (Value + Align - 1 - Skew) / Align * Align + Skew; |
732 | } |
733 | |
734 | |
735 | |
736 | template <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 | |
742 | inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) { |
743 | return alignTo(Numerator, Denominator) / Denominator; |
744 | } |
745 | |
746 | |
747 | inline uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator) { |
748 | return (Numerator + (Denominator / 2)) / Denominator; |
749 | } |
750 | |
751 | |
752 | |
753 | inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) { |
754 | assert(Align != 0u && "Align can't be 0."); |
755 | Skew %= Align; |
756 | return (Value - Skew) / Align * Align + Skew; |
757 | } |
758 | |
759 | |
760 | |
761 | template <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 | |
768 | |
769 | inline int32_t SignExtend32(uint32_t X, unsigned B) { |
770 | assert(B > 0 && "Bit width can't be 0."); |
771 | assert(B <= 32 && "Bit width out of range."); |
772 | return int32_t(X << (32 - B)) >> (32 - B); |
773 | } |
774 | |
775 | |
776 | |
777 | template <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 | |
784 | |
785 | inline int64_t SignExtend64(uint64_t X, unsigned B) { |
786 | assert(B > 0 && "Bit width can't be 0."); |
787 | assert(B <= 64 && "Bit width out of range."); |
788 | return int64_t(X << (64 - B)) >> (64 - B); |
789 | } |
790 | |
791 | |
792 | |
793 | template <typename T> |
794 | std::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 | |
799 | |
800 | |
801 | template <typename T> |
802 | std::enable_if_t<std::is_unsigned<T>::value, T> |
803 | SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) { |
804 | bool Dummy; |
805 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
806 | |
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 | |
816 | |
817 | |
818 | template <typename T> |
819 | std::enable_if_t<std::is_unsigned<T>::value, T> |
820 | SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) { |
821 | bool Dummy; |
822 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
823 | |
824 | |
825 | |
826 | |
827 | |
828 | |
829 | Overflowed = false; |
830 | |
831 | |
832 | |
833 | |
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 | |
846 | |
847 | |
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 | |
861 | |
862 | |
863 | |
864 | template <typename T> |
865 | std::enable_if_t<std::is_unsigned<T>::value, T> |
866 | SaturatingMultiplyAdd(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 | |
878 | extern const float huge_valf; |
879 | |
880 | |
881 | |
882 | |
883 | template <typename T> |
884 | std::enable_if_t<std::is_signed<T>::value, T> AddOverflow(T X, T Y, T &Result) { |
885 | #if __has_builtin(__builtin_add_overflow) |
886 | return __builtin_add_overflow(X, Y, &Result); |
887 | #else |
888 | |
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 | |
895 | Result = static_cast<T>(UResult); |
896 | |
897 | |
898 | if (X > 0 && Y > 0) |
899 | return Result <= 0; |
900 | |
901 | if (X < 0 && Y < 0) |
902 | return Result >= 0; |
903 | return false; |
904 | #endif |
905 | } |
906 | |
907 | |
908 | |
909 | template <typename T> |
910 | std::enable_if_t<std::is_signed<T>::value, T> SubOverflow(T X, T Y, T &Result) { |
911 | #if __has_builtin(__builtin_sub_overflow) |
912 | return __builtin_sub_overflow(X, Y, &Result); |
913 | #else |
914 | |
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 | |
921 | Result = static_cast<T>(UResult); |
922 | |
923 | |
924 | if (X <= 0 && Y > 0) |
925 | return Result >= 0; |
926 | |
927 | if (X >= 0 && Y < 0) |
928 | return Result <= 0; |
929 | return false; |
930 | #endif |
931 | } |
932 | |
933 | |
934 | |
935 | template <typename T> |
936 | std::enable_if_t<std::is_signed<T>::value, T> MulOverflow(T X, T Y, T &Result) { |
937 | |
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 | |
944 | const bool IsNegative = (X < 0) ^ (Y < 0); |
945 | Result = IsNegative ? (0 - UResult) : UResult; |
946 | |
947 | |
948 | if (UX == 0 || UY == 0) |
949 | return false; |
950 | |
951 | |
952 | |
953 | |
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 | } |
961 | |
962 | #endif |