Bug Summary

File:lib/CodeGen/AsmPrinter/DwarfExpression.cpp
Warning:line 159, column 1
Potential leak of memory pointed to by 'Coverage.X'

Annotated Source Code

[?] Use j/k keys for keyboard navigation

/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/AsmPrinter/DwarfExpression.cpp

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
25using namespace llvm;
26
27void 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
40void 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
52void DwarfExpression::addFBReg(int Offset) {
53 emitOp(dwarf::DW_OP_fbreg);
54 emitSigned(Offset);
55}
56
57void 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
74void DwarfExpression::addShr(unsigned ShiftBy) {
75 emitOp(dwarf::DW_OP_constu);
76 emitUnsigned(ShiftBy);
77 emitOp(dwarf::DW_OP_shr);
78}
79
80void DwarfExpression::addAnd(unsigned Mask) {
81 emitOp(dwarf::DW_OP_constu);
82 emitUnsigned(Mask);
83 emitOp(dwarf::DW_OP_and);
84}
85
86bool DwarfExpression::addMachineReg(const TargetRegisterInfo &TRI,
87 unsigned MachineReg, unsigned MaxSize) {
88 if (!TRI.isPhysicalRegister(MachineReg)) {
3
Taking false branch
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) {
4
Assuming 'Reg' is < 0
5
Taking false branch
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) {
6
Loop condition is true. Entering loop body
9
Loop condition is true. Entering loop body
12
Loop condition is true. Entering loop body
15
Loop condition is false. Execution continues on line 121
107 Reg = TRI.getDwarfRegNum(*SR, false);
108 if (Reg >= 0) {
7
Assuming 'Reg' is < 0
8
Taking false branch
10
Assuming 'Reg' is < 0
11
Taking false branch
13
Assuming 'Reg' is < 0
14
Taking false branch
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);
16
Calling constructor for 'SmallBitVector'
20
Returning from constructor for 'SmallBitVector'
128 for (MCSubRegIterator SR(MachineReg, &TRI); SR.isValid(); ++SR) {
21
Loop condition is true. Entering loop body
25
Loop condition is true. Entering loop body
29
Loop condition is true. Entering loop body
33
Loop condition is false. Execution continues on line 158
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)
22
Assuming 'Reg' is >= 0
23
Taking false branch
26
Assuming 'Reg' is >= 0
27
Taking false branch
30
Assuming 'Reg' is >= 0
31
Taking false branch
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)) {
24
Taking false branch
28
Taking false branch
32
Taking false branch
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}
34
Potential leak of memory pointed to by 'Coverage.X'
160
161void DwarfExpression::addStackValue() {
162 if (DwarfVersion >= 4)
163 emitOp(dwarf::DW_OP_stack_value);
164}
165
166void 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
173void 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
180void 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
200bool 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)) {
1
'?' condition is false
2
Calling 'DwarfExpression::addMachineReg'
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?".
282static 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
296void 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.
382void 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
390void 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
401void 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}

/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h

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
28namespace 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.
35class 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
63public:
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
94private:
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
144public:
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)
17
Assuming 's' is > SmallNumDataBits
18
Taking false branch
152 switchToSmall(t ? ~uintptr_t(0) : 0, s);
153 else
154 switchToLarge(new BitVector(s, t));
19
Memory is allocated
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
653private:
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
669inline SmallBitVector
670operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
671 SmallBitVector Result(LHS);
672 Result &= RHS;
673 return Result;
674}
675
676inline SmallBitVector
677operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
678 SmallBitVector Result(LHS);
679 Result |= RHS;
680 return Result;
681}
682
683inline SmallBitVector
684operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
685 SmallBitVector Result(LHS);
686 Result ^= RHS;
687 return Result;
688}
689
690} // end namespace llvm
691
692namespace std {
693
694/// Implement std::swap in terms of BitVector swap.
695inline void
696swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
697 LHS.swap(RHS);
698}
699
700} // end namespace std
701
702#endif // LLVM_ADT_SMALLBITVECTOR_H