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