File: | include/llvm/ADT/SmallBitVector.h |
Warning: | line 120, column 3 Potential memory leak |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- llvm/CodeGen/DwarfExpression.cpp - Dwarf Debug Framework -----------===// | |||
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 support for writing dwarf debug info into asm files. | |||
10 | // | |||
11 | //===----------------------------------------------------------------------===// | |||
12 | ||||
13 | #include "DwarfExpression.h" | |||
14 | #include "DwarfCompileUnit.h" | |||
15 | #include "llvm/ADT/APInt.h" | |||
16 | #include "llvm/ADT/SmallBitVector.h" | |||
17 | #include "llvm/BinaryFormat/Dwarf.h" | |||
18 | #include "llvm/CodeGen/TargetRegisterInfo.h" | |||
19 | #include "llvm/IR/DebugInfoMetadata.h" | |||
20 | #include "llvm/Support/ErrorHandling.h" | |||
21 | #include <algorithm> | |||
22 | #include <cassert> | |||
23 | #include <cstdint> | |||
24 | ||||
25 | using namespace llvm; | |||
26 | ||||
27 | void DwarfExpression::emitConstu(uint64_t Value) { | |||
28 | if (Value < 32) | |||
29 | emitOp(dwarf::DW_OP_lit0 + Value); | |||
30 | else if (Value == std::numeric_limits<uint64_t>::max()) { | |||
31 | // Only do this for 64-bit values as the DWARF expression stack uses | |||
32 | // target-address-size values. | |||
33 | emitOp(dwarf::DW_OP_lit0); | |||
34 | emitOp(dwarf::DW_OP_not); | |||
35 | } else { | |||
36 | emitOp(dwarf::DW_OP_constu); | |||
37 | emitUnsigned(Value); | |||
38 | } | |||
39 | } | |||
40 | ||||
41 | void DwarfExpression::addReg(int DwarfReg, const char *Comment) { | |||
42 | assert(DwarfReg >= 0 && "invalid negative dwarf register number")((DwarfReg >= 0 && "invalid negative dwarf register number" ) ? static_cast<void> (0) : __assert_fail ("DwarfReg >= 0 && \"invalid negative dwarf register number\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 42, __PRETTY_FUNCTION__)); | |||
43 | assert((isUnknownLocation() || isRegisterLocation()) &&(((isUnknownLocation() || isRegisterLocation()) && "location description already locked down" ) ? static_cast<void> (0) : __assert_fail ("(isUnknownLocation() || isRegisterLocation()) && \"location description already locked down\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 44, __PRETTY_FUNCTION__)) | |||
44 | "location description already locked down")(((isUnknownLocation() || isRegisterLocation()) && "location description already locked down" ) ? static_cast<void> (0) : __assert_fail ("(isUnknownLocation() || isRegisterLocation()) && \"location description already locked down\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 44, __PRETTY_FUNCTION__)); | |||
45 | LocationKind = Register; | |||
46 | if (DwarfReg < 32) { | |||
47 | emitOp(dwarf::DW_OP_reg0 + DwarfReg, Comment); | |||
48 | } else { | |||
49 | emitOp(dwarf::DW_OP_regx, Comment); | |||
50 | emitUnsigned(DwarfReg); | |||
51 | } | |||
52 | } | |||
53 | ||||
54 | void DwarfExpression::addBReg(int DwarfReg, int Offset) { | |||
55 | assert(DwarfReg >= 0 && "invalid negative dwarf register number")((DwarfReg >= 0 && "invalid negative dwarf register number" ) ? static_cast<void> (0) : __assert_fail ("DwarfReg >= 0 && \"invalid negative dwarf register number\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 55, __PRETTY_FUNCTION__)); | |||
56 | assert(!isRegisterLocation() && "location description already locked down")((!isRegisterLocation() && "location description already locked down" ) ? static_cast<void> (0) : __assert_fail ("!isRegisterLocation() && \"location description already locked down\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 56, __PRETTY_FUNCTION__)); | |||
57 | if (DwarfReg < 32) { | |||
58 | emitOp(dwarf::DW_OP_breg0 + DwarfReg); | |||
59 | } else { | |||
60 | emitOp(dwarf::DW_OP_bregx); | |||
61 | emitUnsigned(DwarfReg); | |||
62 | } | |||
63 | emitSigned(Offset); | |||
64 | } | |||
65 | ||||
66 | void DwarfExpression::addFBReg(int Offset) { | |||
67 | emitOp(dwarf::DW_OP_fbreg); | |||
68 | emitSigned(Offset); | |||
69 | } | |||
70 | ||||
71 | void DwarfExpression::addOpPiece(unsigned SizeInBits, unsigned OffsetInBits) { | |||
72 | if (!SizeInBits) | |||
73 | return; | |||
74 | ||||
75 | const unsigned SizeOfByte = 8; | |||
76 | if (OffsetInBits > 0 || SizeInBits % SizeOfByte) { | |||
77 | emitOp(dwarf::DW_OP_bit_piece); | |||
78 | emitUnsigned(SizeInBits); | |||
79 | emitUnsigned(OffsetInBits); | |||
80 | } else { | |||
81 | emitOp(dwarf::DW_OP_piece); | |||
82 | unsigned ByteSize = SizeInBits / SizeOfByte; | |||
83 | emitUnsigned(ByteSize); | |||
84 | } | |||
85 | this->OffsetInBits += SizeInBits; | |||
86 | } | |||
87 | ||||
88 | void DwarfExpression::addShr(unsigned ShiftBy) { | |||
89 | emitConstu(ShiftBy); | |||
90 | emitOp(dwarf::DW_OP_shr); | |||
91 | } | |||
92 | ||||
93 | void DwarfExpression::addAnd(unsigned Mask) { | |||
94 | emitConstu(Mask); | |||
95 | emitOp(dwarf::DW_OP_and); | |||
96 | } | |||
97 | ||||
98 | bool DwarfExpression::addMachineReg(const TargetRegisterInfo &TRI, | |||
99 | unsigned MachineReg, unsigned MaxSize) { | |||
100 | if (!TRI.isPhysicalRegister(MachineReg)) { | |||
101 | if (isFrameRegister(TRI, MachineReg)) { | |||
102 | DwarfRegs.push_back({-1, 0, nullptr}); | |||
103 | return true; | |||
104 | } | |||
105 | return false; | |||
106 | } | |||
107 | ||||
108 | int Reg = TRI.getDwarfRegNum(MachineReg, false); | |||
109 | ||||
110 | // If this is a valid register number, emit it. | |||
111 | if (Reg >= 0) { | |||
112 | DwarfRegs.push_back({Reg, 0, nullptr}); | |||
113 | return true; | |||
114 | } | |||
115 | ||||
116 | // Walk up the super-register chain until we find a valid number. | |||
117 | // For example, EAX on x86_64 is a 32-bit fragment of RAX with offset 0. | |||
118 | for (MCSuperRegIterator SR(MachineReg, &TRI); SR.isValid(); ++SR) { | |||
119 | Reg = TRI.getDwarfRegNum(*SR, false); | |||
120 | if (Reg >= 0) { | |||
121 | unsigned Idx = TRI.getSubRegIndex(*SR, MachineReg); | |||
122 | unsigned Size = TRI.getSubRegIdxSize(Idx); | |||
123 | unsigned RegOffset = TRI.getSubRegIdxOffset(Idx); | |||
124 | DwarfRegs.push_back({Reg, 0, "super-register"}); | |||
125 | // Use a DW_OP_bit_piece to describe the sub-register. | |||
126 | setSubRegisterPiece(Size, RegOffset); | |||
127 | return true; | |||
128 | } | |||
129 | } | |||
130 | ||||
131 | // Otherwise, attempt to find a covering set of sub-register numbers. | |||
132 | // For example, Q0 on ARM is a composition of D0+D1. | |||
133 | unsigned CurPos = 0; | |||
134 | // The size of the register in bits. | |||
135 | const TargetRegisterClass *RC = TRI.getMinimalPhysRegClass(MachineReg); | |||
136 | unsigned RegSize = TRI.getRegSizeInBits(*RC); | |||
137 | // Keep track of the bits in the register we already emitted, so we | |||
138 | // can avoid emitting redundant aliasing subregs. Because this is | |||
139 | // just doing a greedy scan of all subregisters, it is possible that | |||
140 | // this doesn't find a combination of subregisters that fully cover | |||
141 | // the register (even though one may exist). | |||
142 | SmallBitVector Coverage(RegSize, false); | |||
143 | for (MCSubRegIterator SR(MachineReg, &TRI); SR.isValid(); ++SR) { | |||
144 | unsigned Idx = TRI.getSubRegIndex(MachineReg, *SR); | |||
145 | unsigned Size = TRI.getSubRegIdxSize(Idx); | |||
146 | unsigned Offset = TRI.getSubRegIdxOffset(Idx); | |||
147 | Reg = TRI.getDwarfRegNum(*SR, false); | |||
148 | if (Reg < 0) | |||
149 | continue; | |||
150 | ||||
151 | // Intersection between the bits we already emitted and the bits | |||
152 | // covered by this subregister. | |||
153 | SmallBitVector CurSubReg(RegSize, false); | |||
154 | CurSubReg.set(Offset, Offset + Size); | |||
155 | ||||
156 | // If this sub-register has a DWARF number and we haven't covered | |||
157 | // its range, emit a DWARF piece for it. | |||
158 | if (CurSubReg.test(Coverage)) { | |||
159 | // Emit a piece for any gap in the coverage. | |||
160 | if (Offset > CurPos) | |||
161 | DwarfRegs.push_back({-1, Offset - CurPos, "no DWARF register encoding"}); | |||
162 | DwarfRegs.push_back( | |||
163 | {Reg, std::min<unsigned>(Size, MaxSize - Offset), "sub-register"}); | |||
164 | if (Offset >= MaxSize) | |||
165 | break; | |||
166 | ||||
167 | // Mark it as emitted. | |||
168 | Coverage.set(Offset, Offset + Size); | |||
169 | CurPos = Offset + Size; | |||
170 | } | |||
171 | } | |||
172 | // Failed to find any DWARF encoding. | |||
173 | if (CurPos == 0) | |||
174 | return false; | |||
175 | // Found a partial or complete DWARF encoding. | |||
176 | if (CurPos < RegSize) | |||
177 | DwarfRegs.push_back({-1, RegSize - CurPos, "no DWARF register encoding"}); | |||
178 | return true; | |||
179 | } | |||
180 | ||||
181 | void DwarfExpression::addStackValue() { | |||
182 | if (DwarfVersion >= 4) | |||
183 | emitOp(dwarf::DW_OP_stack_value); | |||
184 | } | |||
185 | ||||
186 | void DwarfExpression::addSignedConstant(int64_t Value) { | |||
187 | assert(isImplicitLocation() || isUnknownLocation())((isImplicitLocation() || isUnknownLocation()) ? static_cast< void> (0) : __assert_fail ("isImplicitLocation() || isUnknownLocation()" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 187, __PRETTY_FUNCTION__)); | |||
188 | LocationKind = Implicit; | |||
189 | emitOp(dwarf::DW_OP_consts); | |||
190 | emitSigned(Value); | |||
191 | } | |||
192 | ||||
193 | void DwarfExpression::addUnsignedConstant(uint64_t Value) { | |||
194 | assert(isImplicitLocation() || isUnknownLocation())((isImplicitLocation() || isUnknownLocation()) ? static_cast< void> (0) : __assert_fail ("isImplicitLocation() || isUnknownLocation()" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 194, __PRETTY_FUNCTION__)); | |||
195 | LocationKind = Implicit; | |||
196 | emitConstu(Value); | |||
197 | } | |||
198 | ||||
199 | void DwarfExpression::addUnsignedConstant(const APInt &Value) { | |||
200 | assert(isImplicitLocation() || isUnknownLocation())((isImplicitLocation() || isUnknownLocation()) ? static_cast< void> (0) : __assert_fail ("isImplicitLocation() || isUnknownLocation()" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 200, __PRETTY_FUNCTION__)); | |||
201 | LocationKind = Implicit; | |||
202 | ||||
203 | unsigned Size = Value.getBitWidth(); | |||
204 | const uint64_t *Data = Value.getRawData(); | |||
205 | ||||
206 | // Chop it up into 64-bit pieces, because that's the maximum that | |||
207 | // addUnsignedConstant takes. | |||
208 | unsigned Offset = 0; | |||
209 | while (Offset < Size) { | |||
210 | addUnsignedConstant(*Data++); | |||
211 | if (Offset == 0 && Size <= 64) | |||
212 | break; | |||
213 | addStackValue(); | |||
214 | addOpPiece(std::min(Size - Offset, 64u), Offset); | |||
215 | Offset += 64; | |||
216 | } | |||
217 | } | |||
218 | ||||
219 | bool DwarfExpression::addMachineRegExpression(const TargetRegisterInfo &TRI, | |||
220 | DIExpressionCursor &ExprCursor, | |||
221 | unsigned MachineReg, | |||
222 | unsigned FragmentOffsetInBits) { | |||
223 | auto Fragment = ExprCursor.getFragmentInfo(); | |||
224 | if (!addMachineReg(TRI, MachineReg, Fragment ? Fragment->SizeInBits : ~1U)) { | |||
| ||||
225 | LocationKind = Unknown; | |||
226 | return false; | |||
227 | } | |||
228 | ||||
229 | bool HasComplexExpression = false; | |||
230 | auto Op = ExprCursor.peek(); | |||
231 | if (Op && Op->getOp() != dwarf::DW_OP_LLVM_fragment) | |||
232 | HasComplexExpression = true; | |||
233 | ||||
234 | // If the register can only be described by a complex expression (i.e., | |||
235 | // multiple subregisters) it doesn't safely compose with another complex | |||
236 | // expression. For example, it is not possible to apply a DW_OP_deref | |||
237 | // operation to multiple DW_OP_pieces. | |||
238 | if (HasComplexExpression && DwarfRegs.size() > 1) { | |||
239 | DwarfRegs.clear(); | |||
240 | LocationKind = Unknown; | |||
241 | return false; | |||
242 | } | |||
243 | ||||
244 | // Handle simple register locations. | |||
245 | if (!isMemoryLocation() && !HasComplexExpression) { | |||
246 | for (auto &Reg : DwarfRegs) { | |||
247 | if (Reg.DwarfRegNo >= 0) | |||
248 | addReg(Reg.DwarfRegNo, Reg.Comment); | |||
249 | addOpPiece(Reg.Size); | |||
250 | } | |||
251 | DwarfRegs.clear(); | |||
252 | return true; | |||
253 | } | |||
254 | ||||
255 | // Don't emit locations that cannot be expressed without DW_OP_stack_value. | |||
256 | if (DwarfVersion < 4) | |||
257 | if (any_of(ExprCursor, [](DIExpression::ExprOperand Op) -> bool { | |||
258 | return Op.getOp() == dwarf::DW_OP_stack_value; | |||
259 | })) { | |||
260 | DwarfRegs.clear(); | |||
261 | LocationKind = Unknown; | |||
262 | return false; | |||
263 | } | |||
264 | ||||
265 | assert(DwarfRegs.size() == 1)((DwarfRegs.size() == 1) ? static_cast<void> (0) : __assert_fail ("DwarfRegs.size() == 1", "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 265, __PRETTY_FUNCTION__)); | |||
266 | auto Reg = DwarfRegs[0]; | |||
267 | bool FBReg = isFrameRegister(TRI, MachineReg); | |||
268 | int SignedOffset = 0; | |||
269 | assert(Reg.Size == 0 && "subregister has same size as superregister")((Reg.Size == 0 && "subregister has same size as superregister" ) ? static_cast<void> (0) : __assert_fail ("Reg.Size == 0 && \"subregister has same size as superregister\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 269, __PRETTY_FUNCTION__)); | |||
270 | ||||
271 | // Pattern-match combinations for which more efficient representations exist. | |||
272 | // [Reg, DW_OP_plus_uconst, Offset] --> [DW_OP_breg, Offset]. | |||
273 | if (Op && (Op->getOp() == dwarf::DW_OP_plus_uconst)) { | |||
274 | SignedOffset = Op->getArg(0); | |||
275 | ExprCursor.take(); | |||
276 | } | |||
277 | ||||
278 | // [Reg, DW_OP_constu, Offset, DW_OP_plus] --> [DW_OP_breg, Offset] | |||
279 | // [Reg, DW_OP_constu, Offset, DW_OP_minus] --> [DW_OP_breg,-Offset] | |||
280 | // If Reg is a subregister we need to mask it out before subtracting. | |||
281 | if (Op && Op->getOp() == dwarf::DW_OP_constu) { | |||
282 | auto N = ExprCursor.peekNext(); | |||
283 | if (N && (N->getOp() == dwarf::DW_OP_plus || | |||
284 | (N->getOp() == dwarf::DW_OP_minus && !SubRegisterSizeInBits))) { | |||
285 | int Offset = Op->getArg(0); | |||
286 | SignedOffset = (N->getOp() == dwarf::DW_OP_minus) ? -Offset : Offset; | |||
287 | ExprCursor.consume(2); | |||
288 | } | |||
289 | } | |||
290 | ||||
291 | if (FBReg) | |||
292 | addFBReg(SignedOffset); | |||
293 | else | |||
294 | addBReg(Reg.DwarfRegNo, SignedOffset); | |||
295 | DwarfRegs.clear(); | |||
296 | return true; | |||
297 | } | |||
298 | ||||
299 | /// Assuming a well-formed expression, match "DW_OP_deref* DW_OP_LLVM_fragment?". | |||
300 | static bool isMemoryLocation(DIExpressionCursor ExprCursor) { | |||
301 | while (ExprCursor) { | |||
302 | auto Op = ExprCursor.take(); | |||
303 | switch (Op->getOp()) { | |||
304 | case dwarf::DW_OP_deref: | |||
305 | case dwarf::DW_OP_LLVM_fragment: | |||
306 | break; | |||
307 | default: | |||
308 | return false; | |||
309 | } | |||
310 | } | |||
311 | return true; | |||
312 | } | |||
313 | ||||
314 | void DwarfExpression::addExpression(DIExpressionCursor &&ExprCursor, | |||
315 | unsigned FragmentOffsetInBits) { | |||
316 | // If we need to mask out a subregister, do it now, unless the next | |||
317 | // operation would emit an OpPiece anyway. | |||
318 | auto N = ExprCursor.peek(); | |||
319 | if (SubRegisterSizeInBits && N && (N->getOp() != dwarf::DW_OP_LLVM_fragment)) | |||
320 | maskSubRegister(); | |||
321 | ||||
322 | Optional<DIExpression::ExprOperand> PrevConvertOp = None; | |||
323 | ||||
324 | while (ExprCursor) { | |||
325 | auto Op = ExprCursor.take(); | |||
326 | switch (Op->getOp()) { | |||
327 | case dwarf::DW_OP_LLVM_fragment: { | |||
328 | unsigned SizeInBits = Op->getArg(1); | |||
329 | unsigned FragmentOffset = Op->getArg(0); | |||
330 | // The fragment offset must have already been adjusted by emitting an | |||
331 | // empty DW_OP_piece / DW_OP_bit_piece before we emitted the base | |||
332 | // location. | |||
333 | assert(OffsetInBits >= FragmentOffset && "fragment offset not added?")((OffsetInBits >= FragmentOffset && "fragment offset not added?" ) ? static_cast<void> (0) : __assert_fail ("OffsetInBits >= FragmentOffset && \"fragment offset not added?\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 333, __PRETTY_FUNCTION__)); | |||
334 | ||||
335 | // If addMachineReg already emitted DW_OP_piece operations to represent | |||
336 | // a super-register by splicing together sub-registers, subtract the size | |||
337 | // of the pieces that was already emitted. | |||
338 | SizeInBits -= OffsetInBits - FragmentOffset; | |||
339 | ||||
340 | // If addMachineReg requested a DW_OP_bit_piece to stencil out a | |||
341 | // sub-register that is smaller than the current fragment's size, use it. | |||
342 | if (SubRegisterSizeInBits) | |||
343 | SizeInBits = std::min<unsigned>(SizeInBits, SubRegisterSizeInBits); | |||
344 | ||||
345 | // Emit a DW_OP_stack_value for implicit location descriptions. | |||
346 | if (isImplicitLocation()) | |||
347 | addStackValue(); | |||
348 | ||||
349 | // Emit the DW_OP_piece. | |||
350 | addOpPiece(SizeInBits, SubRegisterOffsetInBits); | |||
351 | setSubRegisterPiece(0, 0); | |||
352 | // Reset the location description kind. | |||
353 | LocationKind = Unknown; | |||
354 | return; | |||
355 | } | |||
356 | case dwarf::DW_OP_plus_uconst: | |||
357 | assert(!isRegisterLocation())((!isRegisterLocation()) ? static_cast<void> (0) : __assert_fail ("!isRegisterLocation()", "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 357, __PRETTY_FUNCTION__)); | |||
358 | emitOp(dwarf::DW_OP_plus_uconst); | |||
359 | emitUnsigned(Op->getArg(0)); | |||
360 | break; | |||
361 | case dwarf::DW_OP_plus: | |||
362 | case dwarf::DW_OP_minus: | |||
363 | case dwarf::DW_OP_mul: | |||
364 | case dwarf::DW_OP_div: | |||
365 | case dwarf::DW_OP_mod: | |||
366 | case dwarf::DW_OP_or: | |||
367 | case dwarf::DW_OP_and: | |||
368 | case dwarf::DW_OP_xor: | |||
369 | case dwarf::DW_OP_shl: | |||
370 | case dwarf::DW_OP_shr: | |||
371 | case dwarf::DW_OP_shra: | |||
372 | case dwarf::DW_OP_lit0: | |||
373 | case dwarf::DW_OP_not: | |||
374 | case dwarf::DW_OP_dup: | |||
375 | emitOp(Op->getOp()); | |||
376 | break; | |||
377 | case dwarf::DW_OP_deref: | |||
378 | assert(!isRegisterLocation())((!isRegisterLocation()) ? static_cast<void> (0) : __assert_fail ("!isRegisterLocation()", "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 378, __PRETTY_FUNCTION__)); | |||
379 | if (!isMemoryLocation() && ::isMemoryLocation(ExprCursor)) | |||
380 | // Turning this into a memory location description makes the deref | |||
381 | // implicit. | |||
382 | LocationKind = Memory; | |||
383 | else | |||
384 | emitOp(dwarf::DW_OP_deref); | |||
385 | break; | |||
386 | case dwarf::DW_OP_constu: | |||
387 | assert(!isRegisterLocation())((!isRegisterLocation()) ? static_cast<void> (0) : __assert_fail ("!isRegisterLocation()", "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 387, __PRETTY_FUNCTION__)); | |||
388 | emitConstu(Op->getArg(0)); | |||
389 | break; | |||
390 | case dwarf::DW_OP_LLVM_convert: { | |||
391 | unsigned BitSize = Op->getArg(0); | |||
392 | dwarf::TypeKind Encoding = static_cast<dwarf::TypeKind>(Op->getArg(1)); | |||
393 | if (DwarfVersion >= 5) { | |||
394 | emitOp(dwarf::DW_OP_convert); | |||
395 | // Reuse the base_type if we already have one in this CU otherwise we | |||
396 | // create a new one. | |||
397 | unsigned I = 0, E = CU.ExprRefedBaseTypes.size(); | |||
398 | for (; I != E; ++I) | |||
399 | if (CU.ExprRefedBaseTypes[I].BitSize == BitSize && | |||
400 | CU.ExprRefedBaseTypes[I].Encoding == Encoding) | |||
401 | break; | |||
402 | ||||
403 | if (I == E) | |||
404 | CU.ExprRefedBaseTypes.emplace_back(BitSize, Encoding); | |||
405 | ||||
406 | // If targeting a location-list; simply emit the index into the raw | |||
407 | // byte stream as ULEB128, DwarfDebug::emitDebugLocEntry has been | |||
408 | // fitted with means to extract it later. | |||
409 | // If targeting a inlined DW_AT_location; insert a DIEBaseTypeRef | |||
410 | // (containing the index and a resolve mechanism during emit) into the | |||
411 | // DIE value list. | |||
412 | emitBaseTypeRef(I); | |||
413 | } else { | |||
414 | if (PrevConvertOp && PrevConvertOp->getArg(0) < BitSize) { | |||
415 | if (Encoding == dwarf::DW_ATE_signed) | |||
416 | emitLegacySExt(PrevConvertOp->getArg(0)); | |||
417 | else if (Encoding == dwarf::DW_ATE_unsigned) | |||
418 | emitLegacyZExt(PrevConvertOp->getArg(0)); | |||
419 | PrevConvertOp = None; | |||
420 | } else { | |||
421 | PrevConvertOp = Op; | |||
422 | } | |||
423 | } | |||
424 | break; | |||
425 | } | |||
426 | case dwarf::DW_OP_stack_value: | |||
427 | LocationKind = Implicit; | |||
428 | break; | |||
429 | case dwarf::DW_OP_swap: | |||
430 | assert(!isRegisterLocation())((!isRegisterLocation()) ? static_cast<void> (0) : __assert_fail ("!isRegisterLocation()", "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 430, __PRETTY_FUNCTION__)); | |||
431 | emitOp(dwarf::DW_OP_swap); | |||
432 | break; | |||
433 | case dwarf::DW_OP_xderef: | |||
434 | assert(!isRegisterLocation())((!isRegisterLocation()) ? static_cast<void> (0) : __assert_fail ("!isRegisterLocation()", "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 434, __PRETTY_FUNCTION__)); | |||
435 | emitOp(dwarf::DW_OP_xderef); | |||
436 | break; | |||
437 | case dwarf::DW_OP_deref_size: | |||
438 | emitOp(dwarf::DW_OP_deref_size); | |||
439 | emitData1(Op->getArg(0)); | |||
440 | break; | |||
441 | default: | |||
442 | llvm_unreachable("unhandled opcode found in expression")::llvm::llvm_unreachable_internal("unhandled opcode found in expression" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 442); | |||
443 | } | |||
444 | } | |||
445 | ||||
446 | if (isImplicitLocation()) | |||
447 | // Turn this into an implicit location description. | |||
448 | addStackValue(); | |||
449 | } | |||
450 | ||||
451 | /// add masking operations to stencil out a subregister. | |||
452 | void DwarfExpression::maskSubRegister() { | |||
453 | assert(SubRegisterSizeInBits && "no subregister was registered")((SubRegisterSizeInBits && "no subregister was registered" ) ? static_cast<void> (0) : __assert_fail ("SubRegisterSizeInBits && \"no subregister was registered\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 453, __PRETTY_FUNCTION__)); | |||
454 | if (SubRegisterOffsetInBits > 0) | |||
455 | addShr(SubRegisterOffsetInBits); | |||
456 | uint64_t Mask = (1ULL << (uint64_t)SubRegisterSizeInBits) - 1ULL; | |||
457 | addAnd(Mask); | |||
458 | } | |||
459 | ||||
460 | void DwarfExpression::finalize() { | |||
461 | assert(DwarfRegs.size() == 0 && "dwarf registers not emitted")((DwarfRegs.size() == 0 && "dwarf registers not emitted" ) ? static_cast<void> (0) : __assert_fail ("DwarfRegs.size() == 0 && \"dwarf registers not emitted\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 461, __PRETTY_FUNCTION__)); | |||
462 | // Emit any outstanding DW_OP_piece operations to mask out subregisters. | |||
463 | if (SubRegisterSizeInBits == 0) | |||
464 | return; | |||
465 | // Don't emit a DW_OP_piece for a subregister at offset 0. | |||
466 | if (SubRegisterOffsetInBits == 0) | |||
467 | return; | |||
468 | addOpPiece(SubRegisterSizeInBits, SubRegisterOffsetInBits); | |||
469 | } | |||
470 | ||||
471 | void DwarfExpression::addFragmentOffset(const DIExpression *Expr) { | |||
472 | if (!Expr || !Expr->isFragment()) | |||
473 | return; | |||
474 | ||||
475 | uint64_t FragmentOffset = Expr->getFragmentInfo()->OffsetInBits; | |||
476 | assert(FragmentOffset >= OffsetInBits &&((FragmentOffset >= OffsetInBits && "overlapping or duplicate fragments" ) ? static_cast<void> (0) : __assert_fail ("FragmentOffset >= OffsetInBits && \"overlapping or duplicate fragments\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 477, __PRETTY_FUNCTION__)) | |||
477 | "overlapping or duplicate fragments")((FragmentOffset >= OffsetInBits && "overlapping or duplicate fragments" ) ? static_cast<void> (0) : __assert_fail ("FragmentOffset >= OffsetInBits && \"overlapping or duplicate fragments\"" , "/build/llvm-toolchain-snapshot-9~svn362543/lib/CodeGen/AsmPrinter/DwarfExpression.cpp" , 477, __PRETTY_FUNCTION__)); | |||
478 | if (FragmentOffset > OffsetInBits) | |||
479 | addOpPiece(FragmentOffset - OffsetInBits); | |||
480 | OffsetInBits = FragmentOffset; | |||
481 | } | |||
482 | ||||
483 | void DwarfExpression::emitLegacySExt(unsigned FromBits) { | |||
484 | // (((X >> (FromBits - 1)) * (~0)) << FromBits) | X | |||
485 | emitOp(dwarf::DW_OP_dup); | |||
486 | emitOp(dwarf::DW_OP_constu); | |||
487 | emitUnsigned(FromBits - 1); | |||
488 | emitOp(dwarf::DW_OP_shr); | |||
489 | emitOp(dwarf::DW_OP_lit0); | |||
490 | emitOp(dwarf::DW_OP_not); | |||
491 | emitOp(dwarf::DW_OP_mul); | |||
492 | emitOp(dwarf::DW_OP_constu); | |||
493 | emitUnsigned(FromBits); | |||
494 | emitOp(dwarf::DW_OP_shl); | |||
495 | emitOp(dwarf::DW_OP_or); | |||
496 | } | |||
497 | ||||
498 | void DwarfExpression::emitLegacyZExt(unsigned FromBits) { | |||
499 | // (X & (1 << FromBits - 1)) | |||
500 | emitOp(dwarf::DW_OP_constu); | |||
501 | emitUnsigned((1ULL << FromBits) - 1); | |||
502 | emitOp(dwarf::DW_OP_and); | |||
503 | } |
1 | //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // This file implements the SmallBitVector class. | |||
10 | // | |||
11 | //===----------------------------------------------------------------------===// | |||
12 | ||||
13 | #ifndef LLVM_ADT_SMALLBITVECTOR_H | |||
14 | #define LLVM_ADT_SMALLBITVECTOR_H | |||
15 | ||||
16 | #include "llvm/ADT/BitVector.h" | |||
17 | #include "llvm/ADT/iterator_range.h" | |||
18 | #include "llvm/Support/MathExtras.h" | |||
19 | #include <algorithm> | |||
20 | #include <cassert> | |||
21 | #include <climits> | |||
22 | #include <cstddef> | |||
23 | #include <cstdint> | |||
24 | #include <limits> | |||
25 | #include <utility> | |||
26 | ||||
27 | namespace llvm { | |||
28 | ||||
29 | /// This is a 'bitvector' (really, a variable-sized bit array), optimized for | |||
30 | /// the case when the array is small. It contains one pointer-sized field, which | |||
31 | /// is directly used as a plain collection of bits when possible, or as a | |||
32 | /// pointer to a larger heap-allocated array when necessary. This allows normal | |||
33 | /// "small" cases to be fast without losing generality for large inputs. | |||
34 | class SmallBitVector { | |||
35 | // TODO: In "large" mode, a pointer to a BitVector is used, leading to an | |||
36 | // unnecessary level of indirection. It would be more efficient to use a | |||
37 | // pointer to memory containing size, allocation size, and the array of bits. | |||
38 | uintptr_t X = 1; | |||
39 | ||||
40 | enum { | |||
41 | // The number of bits in this class. | |||
42 | NumBaseBits = sizeof(uintptr_t) * CHAR_BIT8, | |||
43 | ||||
44 | // One bit is used to discriminate between small and large mode. The | |||
45 | // remaining bits are used for the small-mode representation. | |||
46 | SmallNumRawBits = NumBaseBits - 1, | |||
47 | ||||
48 | // A few more bits are used to store the size of the bit set in small mode. | |||
49 | // Theoretically this is a ceil-log2. These bits are encoded in the most | |||
50 | // significant bits of the raw bits. | |||
51 | SmallNumSizeBits = (NumBaseBits == 32 ? 5 : | |||
52 | NumBaseBits == 64 ? 6 : | |||
53 | SmallNumRawBits), | |||
54 | ||||
55 | // The remaining bits are used to store the actual set in small mode. | |||
56 | SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits | |||
57 | }; | |||
58 | ||||
59 | static_assert(NumBaseBits == 64 || NumBaseBits == 32, | |||
60 | "Unsupported word size"); | |||
61 | ||||
62 | public: | |||
63 | using size_type = unsigned; | |||
64 | ||||
65 | // Encapsulation of a single bit. | |||
66 | class reference { | |||
67 | SmallBitVector &TheVector; | |||
68 | unsigned BitPos; | |||
69 | ||||
70 | public: | |||
71 | reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} | |||
72 | ||||
73 | reference(const reference&) = default; | |||
74 | ||||
75 | reference& operator=(reference t) { | |||
76 | *this = bool(t); | |||
77 | return *this; | |||
78 | } | |||
79 | ||||
80 | reference& operator=(bool t) { | |||
81 | if (t) | |||
82 | TheVector.set(BitPos); | |||
83 | else | |||
84 | TheVector.reset(BitPos); | |||
85 | return *this; | |||
86 | } | |||
87 | ||||
88 | operator bool() const { | |||
89 | return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); | |||
90 | } | |||
91 | }; | |||
92 | ||||
93 | private: | |||
94 | BitVector *getPointer() const { | |||
95 | assert(!isSmall())((!isSmall()) ? static_cast<void> (0) : __assert_fail ( "!isSmall()", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 95, __PRETTY_FUNCTION__)); | |||
96 | return reinterpret_cast<BitVector *>(X); | |||
97 | } | |||
98 | ||||
99 | void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { | |||
100 | X = 1; | |||
101 | setSmallSize(NewSize); | |||
102 | setSmallBits(NewSmallBits); | |||
103 | } | |||
104 | ||||
105 | void switchToLarge(BitVector *BV) { | |||
106 | X = reinterpret_cast<uintptr_t>(BV); | |||
107 | assert(!isSmall() && "Tried to use an unaligned pointer")((!isSmall() && "Tried to use an unaligned pointer") ? static_cast<void> (0) : __assert_fail ("!isSmall() && \"Tried to use an unaligned pointer\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 107, __PRETTY_FUNCTION__)); | |||
108 | } | |||
109 | ||||
110 | // Return all the bits used for the "small" representation; this includes | |||
111 | // bits for the size as well as the element bits. | |||
112 | uintptr_t getSmallRawBits() const { | |||
113 | assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 113, __PRETTY_FUNCTION__)); | |||
114 | return X >> 1; | |||
115 | } | |||
116 | ||||
117 | void setSmallRawBits(uintptr_t NewRawBits) { | |||
118 | assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 118, __PRETTY_FUNCTION__)); | |||
119 | X = (NewRawBits << 1) | uintptr_t(1); | |||
120 | } | |||
| ||||
121 | ||||
122 | // Return the size. | |||
123 | size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; } | |||
124 | ||||
125 | void setSmallSize(size_t Size) { | |||
126 | setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); | |||
127 | } | |||
128 | ||||
129 | // Return the element bits. | |||
130 | uintptr_t getSmallBits() const { | |||
131 | return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); | |||
132 | } | |||
133 | ||||
134 | void setSmallBits(uintptr_t NewBits) { | |||
135 | setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | | |||
136 | (getSmallSize() << SmallNumDataBits)); | |||
137 | } | |||
138 | ||||
139 | public: | |||
140 | /// Creates an empty bitvector. | |||
141 | SmallBitVector() = default; | |||
142 | ||||
143 | /// Creates a bitvector of specified number of bits. All bits are initialized | |||
144 | /// to the specified value. | |||
145 | explicit SmallBitVector(unsigned s, bool t = false) { | |||
146 | if (s <= SmallNumDataBits) | |||
147 | switchToSmall(t ? ~uintptr_t(0) : 0, s); | |||
148 | else | |||
149 | switchToLarge(new BitVector(s, t)); | |||
150 | } | |||
151 | ||||
152 | /// SmallBitVector copy ctor. | |||
153 | SmallBitVector(const SmallBitVector &RHS) { | |||
154 | if (RHS.isSmall()) | |||
155 | X = RHS.X; | |||
156 | else | |||
157 | switchToLarge(new BitVector(*RHS.getPointer())); | |||
158 | } | |||
159 | ||||
160 | SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { | |||
161 | RHS.X = 1; | |||
162 | } | |||
163 | ||||
164 | ~SmallBitVector() { | |||
165 | if (!isSmall()) | |||
166 | delete getPointer(); | |||
167 | } | |||
168 | ||||
169 | using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>; | |||
170 | using set_iterator = const_set_bits_iterator; | |||
171 | ||||
172 | const_set_bits_iterator set_bits_begin() const { | |||
173 | return const_set_bits_iterator(*this); | |||
174 | } | |||
175 | ||||
176 | const_set_bits_iterator set_bits_end() const { | |||
177 | return const_set_bits_iterator(*this, -1); | |||
178 | } | |||
179 | ||||
180 | iterator_range<const_set_bits_iterator> set_bits() const { | |||
181 | return make_range(set_bits_begin(), set_bits_end()); | |||
182 | } | |||
183 | ||||
184 | bool isSmall() const { return X & uintptr_t(1); } | |||
185 | ||||
186 | /// Tests whether there are no bits in this bitvector. | |||
187 | bool empty() const { | |||
188 | return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); | |||
189 | } | |||
190 | ||||
191 | /// Returns the number of bits in this bitvector. | |||
192 | size_t size() const { | |||
193 | return isSmall() ? getSmallSize() : getPointer()->size(); | |||
194 | } | |||
195 | ||||
196 | /// Returns the number of bits which are set. | |||
197 | size_type count() const { | |||
198 | if (isSmall()) { | |||
199 | uintptr_t Bits = getSmallBits(); | |||
200 | return countPopulation(Bits); | |||
201 | } | |||
202 | return getPointer()->count(); | |||
203 | } | |||
204 | ||||
205 | /// Returns true if any bit is set. | |||
206 | bool any() const { | |||
207 | if (isSmall()) | |||
208 | return getSmallBits() != 0; | |||
209 | return getPointer()->any(); | |||
210 | } | |||
211 | ||||
212 | /// Returns true if all bits are set. | |||
213 | bool all() const { | |||
214 | if (isSmall()) | |||
215 | return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; | |||
216 | return getPointer()->all(); | |||
217 | } | |||
218 | ||||
219 | /// Returns true if none of the bits are set. | |||
220 | bool none() const { | |||
221 | if (isSmall()) | |||
222 | return getSmallBits() == 0; | |||
223 | return getPointer()->none(); | |||
224 | } | |||
225 | ||||
226 | /// Returns the index of the first set bit, -1 if none of the bits are set. | |||
227 | int find_first() const { | |||
228 | if (isSmall()) { | |||
229 | uintptr_t Bits = getSmallBits(); | |||
230 | if (Bits == 0) | |||
231 | return -1; | |||
232 | return countTrailingZeros(Bits); | |||
233 | } | |||
234 | return getPointer()->find_first(); | |||
235 | } | |||
236 | ||||
237 | int find_last() const { | |||
238 | if (isSmall()) { | |||
239 | uintptr_t Bits = getSmallBits(); | |||
240 | if (Bits == 0) | |||
241 | return -1; | |||
242 | return NumBaseBits - countLeadingZeros(Bits) - 1; | |||
243 | } | |||
244 | return getPointer()->find_last(); | |||
245 | } | |||
246 | ||||
247 | /// Returns the index of the first unset bit, -1 if all of the bits are set. | |||
248 | int find_first_unset() const { | |||
249 | if (isSmall()) { | |||
250 | if (count() == getSmallSize()) | |||
251 | return -1; | |||
252 | ||||
253 | uintptr_t Bits = getSmallBits(); | |||
254 | return countTrailingOnes(Bits); | |||
255 | } | |||
256 | return getPointer()->find_first_unset(); | |||
257 | } | |||
258 | ||||
259 | int find_last_unset() const { | |||
260 | if (isSmall()) { | |||
261 | if (count() == getSmallSize()) | |||
262 | return -1; | |||
263 | ||||
264 | uintptr_t Bits = getSmallBits(); | |||
265 | // Set unused bits. | |||
266 | Bits |= ~uintptr_t(0) << getSmallSize(); | |||
267 | return NumBaseBits - countLeadingOnes(Bits) - 1; | |||
268 | } | |||
269 | return getPointer()->find_last_unset(); | |||
270 | } | |||
271 | ||||
272 | /// Returns the index of the next set bit following the "Prev" bit. | |||
273 | /// Returns -1 if the next set bit is not found. | |||
274 | int find_next(unsigned Prev) const { | |||
275 | if (isSmall()) { | |||
276 | uintptr_t Bits = getSmallBits(); | |||
277 | // Mask off previous bits. | |||
278 | Bits &= ~uintptr_t(0) << (Prev + 1); | |||
279 | if (Bits == 0 || Prev + 1 >= getSmallSize()) | |||
280 | return -1; | |||
281 | return countTrailingZeros(Bits); | |||
282 | } | |||
283 | return getPointer()->find_next(Prev); | |||
284 | } | |||
285 | ||||
286 | /// Returns the index of the next unset bit following the "Prev" bit. | |||
287 | /// Returns -1 if the next unset bit is not found. | |||
288 | int find_next_unset(unsigned Prev) const { | |||
289 | if (isSmall()) { | |||
290 | ++Prev; | |||
291 | uintptr_t Bits = getSmallBits(); | |||
292 | // Mask in previous bits. | |||
293 | uintptr_t Mask = (1 << Prev) - 1; | |||
294 | Bits |= Mask; | |||
295 | ||||
296 | if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize()) | |||
297 | return -1; | |||
298 | return countTrailingOnes(Bits); | |||
299 | } | |||
300 | return getPointer()->find_next_unset(Prev); | |||
301 | } | |||
302 | ||||
303 | /// find_prev - Returns the index of the first set bit that precedes the | |||
304 | /// the bit at \p PriorTo. Returns -1 if all previous bits are unset. | |||
305 | int find_prev(unsigned PriorTo) const { | |||
306 | if (isSmall()) { | |||
307 | if (PriorTo == 0) | |||
308 | return -1; | |||
309 | ||||
310 | --PriorTo; | |||
311 | uintptr_t Bits = getSmallBits(); | |||
312 | Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1); | |||
313 | if (Bits == 0) | |||
314 | return -1; | |||
315 | ||||
316 | return NumBaseBits - countLeadingZeros(Bits) - 1; | |||
317 | } | |||
318 | return getPointer()->find_prev(PriorTo); | |||
319 | } | |||
320 | ||||
321 | /// Clear all bits. | |||
322 | void clear() { | |||
323 | if (!isSmall()) | |||
324 | delete getPointer(); | |||
325 | switchToSmall(0, 0); | |||
326 | } | |||
327 | ||||
328 | /// Grow or shrink the bitvector. | |||
329 | void resize(unsigned N, bool t = false) { | |||
330 | if (!isSmall()) { | |||
331 | getPointer()->resize(N, t); | |||
332 | } else if (SmallNumDataBits >= N) { | |||
333 | uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; | |||
334 | setSmallSize(N); | |||
335 | setSmallBits(NewBits | getSmallBits()); | |||
336 | } else { | |||
337 | BitVector *BV = new BitVector(N, t); | |||
338 | uintptr_t OldBits = getSmallBits(); | |||
339 | for (size_t i = 0, e = getSmallSize(); i != e; ++i) | |||
340 | (*BV)[i] = (OldBits >> i) & 1; | |||
341 | switchToLarge(BV); | |||
342 | } | |||
343 | } | |||
344 | ||||
345 | void reserve(unsigned N) { | |||
346 | if (isSmall()) { | |||
347 | if (N > SmallNumDataBits) { | |||
348 | uintptr_t OldBits = getSmallRawBits(); | |||
349 | size_t SmallSize = getSmallSize(); | |||
350 | BitVector *BV = new BitVector(SmallSize); | |||
351 | for (size_t i = 0; i < SmallSize; ++i) | |||
352 | if ((OldBits >> i) & 1) | |||
353 | BV->set(i); | |||
354 | BV->reserve(N); | |||
355 | switchToLarge(BV); | |||
356 | } | |||
357 | } else { | |||
358 | getPointer()->reserve(N); | |||
359 | } | |||
360 | } | |||
361 | ||||
362 | // Set, reset, flip | |||
363 | SmallBitVector &set() { | |||
364 | if (isSmall()) | |||
365 | setSmallBits(~uintptr_t(0)); | |||
366 | else | |||
367 | getPointer()->set(); | |||
368 | return *this; | |||
369 | } | |||
370 | ||||
371 | SmallBitVector &set(unsigned Idx) { | |||
372 | if (isSmall()) { | |||
373 | assert(Idx <= static_cast<unsigned>(((Idx <= static_cast<unsigned>( std::numeric_limits< uintptr_t>::digits) && "undefined behavior") ? static_cast <void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 375, __PRETTY_FUNCTION__)) | |||
374 | std::numeric_limits<uintptr_t>::digits) &&((Idx <= static_cast<unsigned>( std::numeric_limits< uintptr_t>::digits) && "undefined behavior") ? static_cast <void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 375, __PRETTY_FUNCTION__)) | |||
375 | "undefined behavior")((Idx <= static_cast<unsigned>( std::numeric_limits< uintptr_t>::digits) && "undefined behavior") ? static_cast <void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 375, __PRETTY_FUNCTION__)); | |||
376 | setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); | |||
377 | } | |||
378 | else | |||
379 | getPointer()->set(Idx); | |||
380 | return *this; | |||
381 | } | |||
382 | ||||
383 | /// Efficiently set a range of bits in [I, E) | |||
384 | SmallBitVector &set(unsigned I, unsigned E) { | |||
385 | assert(I <= E && "Attempted to set backwards range!")((I <= E && "Attempted to set backwards range!") ? static_cast<void> (0) : __assert_fail ("I <= E && \"Attempted to set backwards range!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 385, __PRETTY_FUNCTION__)); | |||
386 | assert(E <= size() && "Attempted to set out-of-bounds range!")((E <= size() && "Attempted to set out-of-bounds range!" ) ? static_cast<void> (0) : __assert_fail ("E <= size() && \"Attempted to set out-of-bounds range!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 386, __PRETTY_FUNCTION__)); | |||
387 | if (I == E) return *this; | |||
388 | if (isSmall()) { | |||
389 | uintptr_t EMask = ((uintptr_t)1) << E; | |||
390 | uintptr_t IMask = ((uintptr_t)1) << I; | |||
391 | uintptr_t Mask = EMask - IMask; | |||
392 | setSmallBits(getSmallBits() | Mask); | |||
393 | } else | |||
394 | getPointer()->set(I, E); | |||
395 | return *this; | |||
396 | } | |||
397 | ||||
398 | SmallBitVector &reset() { | |||
399 | if (isSmall()) | |||
400 | setSmallBits(0); | |||
401 | else | |||
402 | getPointer()->reset(); | |||
403 | return *this; | |||
404 | } | |||
405 | ||||
406 | SmallBitVector &reset(unsigned Idx) { | |||
407 | if (isSmall()) | |||
408 | setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); | |||
409 | else | |||
410 | getPointer()->reset(Idx); | |||
411 | return *this; | |||
412 | } | |||
413 | ||||
414 | /// Efficiently reset a range of bits in [I, E) | |||
415 | SmallBitVector &reset(unsigned I, unsigned E) { | |||
416 | assert(I <= E && "Attempted to reset backwards range!")((I <= E && "Attempted to reset backwards range!") ? static_cast<void> (0) : __assert_fail ("I <= E && \"Attempted to reset backwards range!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 416, __PRETTY_FUNCTION__)); | |||
417 | assert(E <= size() && "Attempted to reset out-of-bounds range!")((E <= size() && "Attempted to reset out-of-bounds range!" ) ? static_cast<void> (0) : __assert_fail ("E <= size() && \"Attempted to reset out-of-bounds range!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 417, __PRETTY_FUNCTION__)); | |||
418 | if (I == E) return *this; | |||
419 | if (isSmall()) { | |||
420 | uintptr_t EMask = ((uintptr_t)1) << E; | |||
421 | uintptr_t IMask = ((uintptr_t)1) << I; | |||
422 | uintptr_t Mask = EMask - IMask; | |||
423 | setSmallBits(getSmallBits() & ~Mask); | |||
424 | } else | |||
425 | getPointer()->reset(I, E); | |||
426 | return *this; | |||
427 | } | |||
428 | ||||
429 | SmallBitVector &flip() { | |||
430 | if (isSmall()) | |||
431 | setSmallBits(~getSmallBits()); | |||
432 | else | |||
433 | getPointer()->flip(); | |||
434 | return *this; | |||
435 | } | |||
436 | ||||
437 | SmallBitVector &flip(unsigned Idx) { | |||
438 | if (isSmall()) | |||
439 | setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); | |||
440 | else | |||
441 | getPointer()->flip(Idx); | |||
442 | return *this; | |||
443 | } | |||
444 | ||||
445 | // No argument flip. | |||
446 | SmallBitVector operator~() const { | |||
447 | return SmallBitVector(*this).flip(); | |||
448 | } | |||
449 | ||||
450 | // Indexing. | |||
451 | reference operator[](unsigned Idx) { | |||
452 | assert(Idx < size() && "Out-of-bounds Bit access.")((Idx < size() && "Out-of-bounds Bit access.") ? static_cast <void> (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 452, __PRETTY_FUNCTION__)); | |||
453 | return reference(*this, Idx); | |||
454 | } | |||
455 | ||||
456 | bool operator[](unsigned Idx) const { | |||
457 | assert(Idx < size() && "Out-of-bounds Bit access.")((Idx < size() && "Out-of-bounds Bit access.") ? static_cast <void> (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 457, __PRETTY_FUNCTION__)); | |||
458 | if (isSmall()) | |||
459 | return ((getSmallBits() >> Idx) & 1) != 0; | |||
460 | return getPointer()->operator[](Idx); | |||
461 | } | |||
462 | ||||
463 | bool test(unsigned Idx) const { | |||
464 | return (*this)[Idx]; | |||
465 | } | |||
466 | ||||
467 | // Push single bit to end of vector. | |||
468 | void push_back(bool Val) { | |||
469 | resize(size() + 1, Val); | |||
470 | } | |||
471 | ||||
472 | /// Test if any common bits are set. | |||
473 | bool anyCommon(const SmallBitVector &RHS) const { | |||
474 | if (isSmall() && RHS.isSmall()) | |||
475 | return (getSmallBits() & RHS.getSmallBits()) != 0; | |||
476 | if (!isSmall() && !RHS.isSmall()) | |||
477 | return getPointer()->anyCommon(*RHS.getPointer()); | |||
478 | ||||
479 | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) | |||
480 | if (test(i) && RHS.test(i)) | |||
481 | return true; | |||
482 | return false; | |||
483 | } | |||
484 | ||||
485 | // Comparison operators. | |||
486 | bool operator==(const SmallBitVector &RHS) const { | |||
487 | if (size() != RHS.size()) | |||
488 | return false; | |||
489 | if (isSmall() && RHS.isSmall()) | |||
490 | return getSmallBits() == RHS.getSmallBits(); | |||
491 | else if (!isSmall() && !RHS.isSmall()) | |||
492 | return *getPointer() == *RHS.getPointer(); | |||
493 | else { | |||
494 | for (size_t i = 0, e = size(); i != e; ++i) { | |||
495 | if ((*this)[i] != RHS[i]) | |||
496 | return false; | |||
497 | } | |||
498 | return true; | |||
499 | } | |||
500 | } | |||
501 | ||||
502 | bool operator!=(const SmallBitVector &RHS) const { | |||
503 | return !(*this == RHS); | |||
504 | } | |||
505 | ||||
506 | // Intersection, union, disjoint union. | |||
507 | // FIXME BitVector::operator&= does not resize the LHS but this does | |||
508 | SmallBitVector &operator&=(const SmallBitVector &RHS) { | |||
509 | resize(std::max(size(), RHS.size())); | |||
510 | if (isSmall() && RHS.isSmall()) | |||
511 | setSmallBits(getSmallBits() & RHS.getSmallBits()); | |||
512 | else if (!isSmall() && !RHS.isSmall()) | |||
513 | getPointer()->operator&=(*RHS.getPointer()); | |||
514 | else { | |||
515 | size_t i, e; | |||
516 | for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) | |||
517 | (*this)[i] = test(i) && RHS.test(i); | |||
518 | for (e = size(); i != e; ++i) | |||
519 | reset(i); | |||
520 | } | |||
521 | return *this; | |||
522 | } | |||
523 | ||||
524 | /// Reset bits that are set in RHS. Same as *this &= ~RHS. | |||
525 | SmallBitVector &reset(const SmallBitVector &RHS) { | |||
526 | if (isSmall() && RHS.isSmall()) | |||
527 | setSmallBits(getSmallBits() & ~RHS.getSmallBits()); | |||
528 | else if (!isSmall() && !RHS.isSmall()) | |||
529 | getPointer()->reset(*RHS.getPointer()); | |||
530 | else | |||
531 | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) | |||
532 | if (RHS.test(i)) | |||
533 | reset(i); | |||
534 | ||||
535 | return *this; | |||
536 | } | |||
537 | ||||
538 | /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any(). | |||
539 | bool test(const SmallBitVector &RHS) const { | |||
540 | if (isSmall() && RHS.isSmall()) | |||
541 | return (getSmallBits() & ~RHS.getSmallBits()) != 0; | |||
542 | if (!isSmall() && !RHS.isSmall()) | |||
543 | return getPointer()->test(*RHS.getPointer()); | |||
544 | ||||
545 | unsigned i, e; | |||
546 | for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) | |||
547 | if (test(i) && !RHS.test(i)) | |||
548 | return true; | |||
549 | ||||
550 | for (e = size(); i != e; ++i) | |||
551 | if (test(i)) | |||
552 | return true; | |||
553 | ||||
554 | return false; | |||
555 | } | |||
556 | ||||
557 | SmallBitVector &operator|=(const SmallBitVector &RHS) { | |||
558 | resize(std::max(size(), RHS.size())); | |||
559 | if (isSmall() && RHS.isSmall()) | |||
560 | setSmallBits(getSmallBits() | RHS.getSmallBits()); | |||
561 | else if (!isSmall() && !RHS.isSmall()) | |||
562 | getPointer()->operator|=(*RHS.getPointer()); | |||
563 | else { | |||
564 | for (size_t i = 0, e = RHS.size(); i != e; ++i) | |||
565 | (*this)[i] = test(i) || RHS.test(i); | |||
566 | } | |||
567 | return *this; | |||
568 | } | |||
569 | ||||
570 | SmallBitVector &operator^=(const SmallBitVector &RHS) { | |||
571 | resize(std::max(size(), RHS.size())); | |||
572 | if (isSmall() && RHS.isSmall()) | |||
573 | setSmallBits(getSmallBits() ^ RHS.getSmallBits()); | |||
574 | else if (!isSmall() && !RHS.isSmall()) | |||
575 | getPointer()->operator^=(*RHS.getPointer()); | |||
576 | else { | |||
577 | for (size_t i = 0, e = RHS.size(); i != e; ++i) | |||
578 | (*this)[i] = test(i) != RHS.test(i); | |||
579 | } | |||
580 | return *this; | |||
581 | } | |||
582 | ||||
583 | SmallBitVector &operator<<=(unsigned N) { | |||
584 | if (isSmall()) | |||
585 | setSmallBits(getSmallBits() << N); | |||
586 | else | |||
587 | getPointer()->operator<<=(N); | |||
588 | return *this; | |||
589 | } | |||
590 | ||||
591 | SmallBitVector &operator>>=(unsigned N) { | |||
592 | if (isSmall()) | |||
593 | setSmallBits(getSmallBits() >> N); | |||
594 | else | |||
595 | getPointer()->operator>>=(N); | |||
596 | return *this; | |||
597 | } | |||
598 | ||||
599 | // Assignment operator. | |||
600 | const SmallBitVector &operator=(const SmallBitVector &RHS) { | |||
601 | if (isSmall()) { | |||
602 | if (RHS.isSmall()) | |||
603 | X = RHS.X; | |||
604 | else | |||
605 | switchToLarge(new BitVector(*RHS.getPointer())); | |||
606 | } else { | |||
607 | if (!RHS.isSmall()) | |||
608 | *getPointer() = *RHS.getPointer(); | |||
609 | else { | |||
610 | delete getPointer(); | |||
611 | X = RHS.X; | |||
612 | } | |||
613 | } | |||
614 | return *this; | |||
615 | } | |||
616 | ||||
617 | const SmallBitVector &operator=(SmallBitVector &&RHS) { | |||
618 | if (this != &RHS) { | |||
619 | clear(); | |||
620 | swap(RHS); | |||
621 | } | |||
622 | return *this; | |||
623 | } | |||
624 | ||||
625 | void swap(SmallBitVector &RHS) { | |||
626 | std::swap(X, RHS.X); | |||
627 | } | |||
628 | ||||
629 | /// Add '1' bits from Mask to this vector. Don't resize. | |||
630 | /// This computes "*this |= Mask". | |||
631 | void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { | |||
632 | if (isSmall()) | |||
633 | applyMask<true, false>(Mask, MaskWords); | |||
634 | else | |||
635 | getPointer()->setBitsInMask(Mask, MaskWords); | |||
636 | } | |||
637 | ||||
638 | /// Clear any bits in this vector that are set in Mask. Don't resize. | |||
639 | /// This computes "*this &= ~Mask". | |||
640 | void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { | |||
641 | if (isSmall()) | |||
642 | applyMask<false, false>(Mask, MaskWords); | |||
643 | else | |||
644 | getPointer()->clearBitsInMask(Mask, MaskWords); | |||
645 | } | |||
646 | ||||
647 | /// Add a bit to this vector for every '0' bit in Mask. Don't resize. | |||
648 | /// This computes "*this |= ~Mask". | |||
649 | void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { | |||
650 | if (isSmall()) | |||
651 | applyMask<true, true>(Mask, MaskWords); | |||
652 | else | |||
653 | getPointer()->setBitsNotInMask(Mask, MaskWords); | |||
654 | } | |||
655 | ||||
656 | /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. | |||
657 | /// This computes "*this &= Mask". | |||
658 | void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { | |||
659 | if (isSmall()) | |||
660 | applyMask<false, true>(Mask, MaskWords); | |||
661 | else | |||
662 | getPointer()->clearBitsNotInMask(Mask, MaskWords); | |||
663 | } | |||
664 | ||||
665 | private: | |||
666 | template <bool AddBits, bool InvertMask> | |||
667 | void applyMask(const uint32_t *Mask, unsigned MaskWords) { | |||
668 | assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!")((MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!" ) ? static_cast<void> (0) : __assert_fail ("MaskWords <= sizeof(uintptr_t) && \"Mask is larger than base!\"" , "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/SmallBitVector.h" , 668, __PRETTY_FUNCTION__)); | |||
669 | uintptr_t M = Mask[0]; | |||
670 | if (NumBaseBits == 64) | |||
671 | M |= uint64_t(Mask[1]) << 32; | |||
672 | if (InvertMask) | |||
673 | M = ~M; | |||
674 | if (AddBits) | |||
675 | setSmallBits(getSmallBits() | M); | |||
676 | else | |||
677 | setSmallBits(getSmallBits() & ~M); | |||
678 | } | |||
679 | }; | |||
680 | ||||
681 | inline SmallBitVector | |||
682 | operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { | |||
683 | SmallBitVector Result(LHS); | |||
684 | Result &= RHS; | |||
685 | return Result; | |||
686 | } | |||
687 | ||||
688 | inline SmallBitVector | |||
689 | operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { | |||
690 | SmallBitVector Result(LHS); | |||
691 | Result |= RHS; | |||
692 | return Result; | |||
693 | } | |||
694 | ||||
695 | inline SmallBitVector | |||
696 | operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { | |||
697 | SmallBitVector Result(LHS); | |||
698 | Result ^= RHS; | |||
699 | return Result; | |||
700 | } | |||
701 | ||||
702 | } // end namespace llvm | |||
703 | ||||
704 | namespace std { | |||
705 | ||||
706 | /// Implement std::swap in terms of BitVector swap. | |||
707 | inline void | |||
708 | swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { | |||
709 | LHS.swap(RHS); | |||
710 | } | |||
711 | ||||
712 | } // end namespace std | |||
713 | ||||
714 | #endif // LLVM_ADT_SMALLBITVECTOR_H |