Bug Summary

File:lib/CodeGen/AsmPrinter/DwarfExpression.cpp
Warning:line 390, column 40
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'uintptr_t'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DwarfExpression.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn325118/build-llvm/lib/CodeGen/AsmPrinter -I /build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter -I /build/llvm-toolchain-snapshot-7~svn325118/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn325118/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn325118/build-llvm/lib/CodeGen/AsmPrinter -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-02-14-150435-17243-1 -x c++ /build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp

/build/llvm-toolchain-snapshot-7~svn325118/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-7~svn325118/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-7~svn325118/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-7~svn325118/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-7~svn325118/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-7~svn325118/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)) {
4
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) {
5
Assuming 'Reg' is < 0
6
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) {
7
Loop condition is true. Entering loop body
10
Loop condition is true. Entering loop body
13
Loop condition is true. Entering loop body
16
Loop condition is false. Execution continues on line 121
107 Reg = TRI.getDwarfRegNum(*SR, false);
108 if (Reg >= 0) {
8
Assuming 'Reg' is < 0
9
Taking false branch
11
Assuming 'Reg' is < 0
12
Taking false branch
14
Assuming 'Reg' is < 0
15
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. Because this is
127 // just doing a greedy scan of all subregisters, it is possible that
128 // this doesn't find a combination of subregisters that fully cover
129 // the register (even though one may exist).
130 SmallBitVector Coverage(RegSize, false);
131 for (MCSubRegIterator SR(MachineReg, &TRI); SR.isValid(); ++SR) {
17
Loop condition is true. Entering loop body
22
Loop condition is true. Entering loop body
27
Loop condition is true. Entering loop body
32
Loop condition is true. Entering loop body
132 unsigned Idx = TRI.getSubRegIndex(MachineReg, *SR);
133 unsigned Size = TRI.getSubRegIdxSize(Idx);
134 unsigned Offset = TRI.getSubRegIdxOffset(Idx);
135 Reg = TRI.getDwarfRegNum(*SR, false);
136 if (Reg < 0)
18
Assuming 'Reg' is >= 0
19
Taking false branch
23
Assuming 'Reg' is >= 0
24
Taking false branch
28
Assuming 'Reg' is >= 0
29
Taking false branch
33
Assuming 'Reg' is >= 0
34
Taking false branch
137 continue;
138
139 // Intersection between the bits we already emitted and the bits
140 // covered by this subregister.
141 SmallBitVector CurSubReg(RegSize, false);
142 CurSubReg.set(Offset, Offset + Size);
143
144 // If this sub-register has a DWARF number and we haven't covered
145 // its range, emit a DWARF piece for it.
146 if (CurSubReg.test(Coverage)) {
20
Assuming the condition is false
21
Taking false branch
25
Assuming the condition is false
26
Taking false branch
30
Assuming the condition is false
31
Taking false branch
35
Assuming the condition is true
36
Taking true branch
147 // Emit a piece for any gap in the coverage.
148 if (Offset > CurPos)
37
Assuming 'Offset' is <= 'CurPos'
38
Taking false branch
149 DwarfRegs.push_back({-1, Offset - CurPos, "no DWARF register encoding"});
150 DwarfRegs.push_back(
151 {Reg, std::min<unsigned>(Size, MaxSize - Offset), "sub-register"});
152 if (Offset >= MaxSize)
39
Taking false branch
153 break;
154
155 // Mark it as emitted.
156 Coverage.set(Offset, Offset + Size);
40
Calling 'SmallBitVector::set'
157 CurPos = Offset + Size;
158 }
159 }
160 // Failed to find any DWARF encoding.
161 if (CurPos == 0)
162 return false;
163 // Found a partial or complete DWARF encoding.
164 if (CurPos < RegSize)
165 DwarfRegs.push_back({-1, RegSize - CurPos, "no DWARF register encoding"});
166 return true;
167}
168
169void DwarfExpression::addStackValue() {
170 if (DwarfVersion >= 4)
171 emitOp(dwarf::DW_OP_stack_value);
172}
173
174void DwarfExpression::addSignedConstant(int64_t Value) {
175 assert(LocationKind == Implicit || LocationKind == Unknown)(static_cast <bool> (LocationKind == Implicit || LocationKind
== Unknown) ? void (0) : __assert_fail ("LocationKind == Implicit || LocationKind == Unknown"
, "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 175, __extension__ __PRETTY_FUNCTION__))
;
176 LocationKind = Implicit;
177 emitOp(dwarf::DW_OP_consts);
178 emitSigned(Value);
179}
180
181void DwarfExpression::addUnsignedConstant(uint64_t Value) {
182 assert(LocationKind == Implicit || LocationKind == Unknown)(static_cast <bool> (LocationKind == Implicit || LocationKind
== Unknown) ? void (0) : __assert_fail ("LocationKind == Implicit || LocationKind == Unknown"
, "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 182, __extension__ __PRETTY_FUNCTION__))
;
183 LocationKind = Implicit;
184 emitOp(dwarf::DW_OP_constu);
185 emitUnsigned(Value);
186}
187
188void DwarfExpression::addUnsignedConstant(const APInt &Value) {
189 assert(LocationKind == Implicit || LocationKind == Unknown)(static_cast <bool> (LocationKind == Implicit || LocationKind
== Unknown) ? void (0) : __assert_fail ("LocationKind == Implicit || LocationKind == Unknown"
, "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 189, __extension__ __PRETTY_FUNCTION__))
;
190 LocationKind = Implicit;
191
192 unsigned Size = Value.getBitWidth();
193 const uint64_t *Data = Value.getRawData();
194
195 // Chop it up into 64-bit pieces, because that's the maximum that
196 // addUnsignedConstant takes.
197 unsigned Offset = 0;
198 while (Offset < Size) {
199 addUnsignedConstant(*Data++);
200 if (Offset == 0 && Size <= 64)
201 break;
202 addStackValue();
203 addOpPiece(std::min(Size - Offset, 64u), Offset);
204 Offset += 64;
205 }
206}
207
208bool DwarfExpression::addMachineRegExpression(const TargetRegisterInfo &TRI,
209 DIExpressionCursor &ExprCursor,
210 unsigned MachineReg,
211 unsigned FragmentOffsetInBits) {
212 auto Fragment = ExprCursor.getFragmentInfo();
213 if (!addMachineReg(TRI, MachineReg, Fragment ? Fragment->SizeInBits : ~1U)) {
1
Assuming the condition is false
2
'?' condition is false
3
Calling 'DwarfExpression::addMachineReg'
214 LocationKind = Unknown;
215 return false;
216 }
217
218 bool HasComplexExpression = false;
219 auto Op = ExprCursor.peek();
220 if (Op && Op->getOp() != dwarf::DW_OP_LLVM_fragment)
221 HasComplexExpression = true;
222
223 // If the register can only be described by a complex expression (i.e.,
224 // multiple subregisters) it doesn't safely compose with another complex
225 // expression. For example, it is not possible to apply a DW_OP_deref
226 // operation to multiple DW_OP_pieces.
227 if (HasComplexExpression && DwarfRegs.size() > 1) {
228 DwarfRegs.clear();
229 LocationKind = Unknown;
230 return false;
231 }
232
233 // Handle simple register locations.
234 if (LocationKind != Memory && !HasComplexExpression) {
235 for (auto &Reg : DwarfRegs) {
236 if (Reg.DwarfRegNo >= 0)
237 addReg(Reg.DwarfRegNo, Reg.Comment);
238 addOpPiece(Reg.Size);
239 }
240 DwarfRegs.clear();
241 return true;
242 }
243
244 // Don't emit locations that cannot be expressed without DW_OP_stack_value.
245 if (DwarfVersion < 4)
246 if (std::any_of(ExprCursor.begin(), ExprCursor.end(),
247 [](DIExpression::ExprOperand Op) -> bool {
248 return Op.getOp() == dwarf::DW_OP_stack_value;
249 })) {
250 DwarfRegs.clear();
251 LocationKind = Unknown;
252 return false;
253 }
254
255 assert(DwarfRegs.size() == 1)(static_cast <bool> (DwarfRegs.size() == 1) ? void (0) :
__assert_fail ("DwarfRegs.size() == 1", "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 255, __extension__ __PRETTY_FUNCTION__))
;
256 auto Reg = DwarfRegs[0];
257 bool FBReg = isFrameRegister(TRI, MachineReg);
258 int SignedOffset = 0;
259 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-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 259, __extension__ __PRETTY_FUNCTION__))
;
260
261 // Pattern-match combinations for which more efficient representations exist.
262 // [Reg, DW_OP_plus_uconst, Offset] --> [DW_OP_breg, Offset].
263 if (Op && (Op->getOp() == dwarf::DW_OP_plus_uconst)) {
264 SignedOffset = Op->getArg(0);
265 ExprCursor.take();
266 }
267
268 // [Reg, DW_OP_constu, Offset, DW_OP_plus] --> [DW_OP_breg, Offset]
269 // [Reg, DW_OP_constu, Offset, DW_OP_minus] --> [DW_OP_breg,-Offset]
270 // If Reg is a subregister we need to mask it out before subtracting.
271 if (Op && Op->getOp() == dwarf::DW_OP_constu) {
272 auto N = ExprCursor.peekNext();
273 if (N && (N->getOp() == dwarf::DW_OP_plus ||
274 (N->getOp() == dwarf::DW_OP_minus && !SubRegisterSizeInBits))) {
275 int Offset = Op->getArg(0);
276 SignedOffset = (N->getOp() == dwarf::DW_OP_minus) ? -Offset : Offset;
277 ExprCursor.consume(2);
278 }
279 }
280
281 if (FBReg)
282 addFBReg(SignedOffset);
283 else
284 addBReg(Reg.DwarfRegNo, SignedOffset);
285 DwarfRegs.clear();
286 return true;
287}
288
289/// Assuming a well-formed expression, match "DW_OP_deref* DW_OP_LLVM_fragment?".
290static bool isMemoryLocation(DIExpressionCursor ExprCursor) {
291 while (ExprCursor) {
292 auto Op = ExprCursor.take();
293 switch (Op->getOp()) {
294 case dwarf::DW_OP_deref:
295 case dwarf::DW_OP_LLVM_fragment:
296 break;
297 default:
298 return false;
299 }
300 }
301 return true;
302}
303
304void DwarfExpression::addExpression(DIExpressionCursor &&ExprCursor,
305 unsigned FragmentOffsetInBits) {
306 // If we need to mask out a subregister, do it now, unless the next
307 // operation would emit an OpPiece anyway.
308 auto N = ExprCursor.peek();
309 if (SubRegisterSizeInBits && N && (N->getOp() != dwarf::DW_OP_LLVM_fragment))
310 maskSubRegister();
311
312 while (ExprCursor) {
313 auto Op = ExprCursor.take();
314 switch (Op->getOp()) {
315 case dwarf::DW_OP_LLVM_fragment: {
316 unsigned SizeInBits = Op->getArg(1);
317 unsigned FragmentOffset = Op->getArg(0);
318 // The fragment offset must have already been adjusted by emitting an
319 // empty DW_OP_piece / DW_OP_bit_piece before we emitted the base
320 // location.
321 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-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 321, __extension__ __PRETTY_FUNCTION__))
;
322
323 // If addMachineReg already emitted DW_OP_piece operations to represent
324 // a super-register by splicing together sub-registers, subtract the size
325 // of the pieces that was already emitted.
326 SizeInBits -= OffsetInBits - FragmentOffset;
327
328 // If addMachineReg requested a DW_OP_bit_piece to stencil out a
329 // sub-register that is smaller than the current fragment's size, use it.
330 if (SubRegisterSizeInBits)
331 SizeInBits = std::min<unsigned>(SizeInBits, SubRegisterSizeInBits);
332
333 // Emit a DW_OP_stack_value for implicit location descriptions.
334 if (LocationKind == Implicit)
335 addStackValue();
336
337 // Emit the DW_OP_piece.
338 addOpPiece(SizeInBits, SubRegisterOffsetInBits);
339 setSubRegisterPiece(0, 0);
340 // Reset the location description kind.
341 LocationKind = Unknown;
342 return;
343 }
344 case dwarf::DW_OP_plus_uconst:
345 assert(LocationKind != Register)(static_cast <bool> (LocationKind != Register) ? void (
0) : __assert_fail ("LocationKind != Register", "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 345, __extension__ __PRETTY_FUNCTION__))
;
346 emitOp(dwarf::DW_OP_plus_uconst);
347 emitUnsigned(Op->getArg(0));
348 break;
349 case dwarf::DW_OP_plus:
350 case dwarf::DW_OP_minus:
351 case dwarf::DW_OP_mul:
352 case dwarf::DW_OP_div:
353 case dwarf::DW_OP_mod:
354 case dwarf::DW_OP_or:
355 case dwarf::DW_OP_xor:
356 case dwarf::DW_OP_shl:
357 case dwarf::DW_OP_shr:
358 case dwarf::DW_OP_shra:
359 emitOp(Op->getOp());
360 break;
361 case dwarf::DW_OP_deref:
362 assert(LocationKind != Register)(static_cast <bool> (LocationKind != Register) ? void (
0) : __assert_fail ("LocationKind != Register", "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 362, __extension__ __PRETTY_FUNCTION__))
;
363 if (LocationKind != Memory && isMemoryLocation(ExprCursor))
364 // Turning this into a memory location description makes the deref
365 // implicit.
366 LocationKind = Memory;
367 else
368 emitOp(dwarf::DW_OP_deref);
369 break;
370 case dwarf::DW_OP_constu:
371 assert(LocationKind != Register)(static_cast <bool> (LocationKind != Register) ? void (
0) : __assert_fail ("LocationKind != Register", "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 371, __extension__ __PRETTY_FUNCTION__))
;
372 emitOp(dwarf::DW_OP_constu);
373 emitUnsigned(Op->getArg(0));
374 break;
375 case dwarf::DW_OP_stack_value:
376 LocationKind = Implicit;
377 break;
378 case dwarf::DW_OP_swap:
379 assert(LocationKind != Register)(static_cast <bool> (LocationKind != Register) ? void (
0) : __assert_fail ("LocationKind != Register", "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 379, __extension__ __PRETTY_FUNCTION__))
;
380 emitOp(dwarf::DW_OP_swap);
381 break;
382 case dwarf::DW_OP_xderef:
383 assert(LocationKind != Register)(static_cast <bool> (LocationKind != Register) ? void (
0) : __assert_fail ("LocationKind != Register", "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 383, __extension__ __PRETTY_FUNCTION__))
;
384 emitOp(dwarf::DW_OP_xderef);
385 break;
386 default:
387 llvm_unreachable("unhandled opcode found in expression")::llvm::llvm_unreachable_internal("unhandled opcode found in expression"
, "/build/llvm-toolchain-snapshot-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 387)
;
388 }
389 }
390
391 if (LocationKind == Implicit)
392 // Turn this into an implicit location description.
393 addStackValue();
394}
395
396/// add masking operations to stencil out a subregister.
397void DwarfExpression::maskSubRegister() {
398 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-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 398, __extension__ __PRETTY_FUNCTION__))
;
399 if (SubRegisterOffsetInBits > 0)
400 addShr(SubRegisterOffsetInBits);
401 uint64_t Mask = (1ULL << (uint64_t)SubRegisterSizeInBits) - 1ULL;
402 addAnd(Mask);
403}
404
405void DwarfExpression::finalize() {
406 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-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 406, __extension__ __PRETTY_FUNCTION__))
;
407 // Emit any outstanding DW_OP_piece operations to mask out subregisters.
408 if (SubRegisterSizeInBits == 0)
409 return;
410 // Don't emit a DW_OP_piece for a subregister at offset 0.
411 if (SubRegisterOffsetInBits == 0)
412 return;
413 addOpPiece(SubRegisterSizeInBits, SubRegisterOffsetInBits);
414}
415
416void DwarfExpression::addFragmentOffset(const DIExpression *Expr) {
417 if (!Expr || !Expr->isFragment())
418 return;
419
420 uint64_t FragmentOffset = Expr->getFragmentInfo()->OffsetInBits;
421 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-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 422, __extension__ __PRETTY_FUNCTION__))
422 "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-7~svn325118/lib/CodeGen/AsmPrinter/DwarfExpression.cpp"
, 422, __extension__ __PRETTY_FUNCTION__))
;
423 if (FragmentOffset > OffsetInBits)
424 addOpPiece(FragmentOffset - OffsetInBits);
425 OffsetInBits = FragmentOffset;
426}

/build/llvm-toolchain-snapshot-7~svn325118/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-7~svn325118/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-7~svn325118/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-7~svn325118/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-7~svn325118/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)
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-7~svn325118/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-7~svn325118/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-7~svn325118/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-7~svn325118/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-7~svn325118/include/llvm/ADT/SmallBitVector.h"
, 387, __extension__ __PRETTY_FUNCTION__))
;
388 if (I == E) return *this;
41
Taking false branch
389 if (isSmall()) {
42
Taking true branch
390 uintptr_t EMask = ((uintptr_t)1) << E;
43
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'uintptr_t'
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-7~svn325118/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-7~svn325118/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-7~svn325118/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-7~svn325118/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-7~svn325118/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