File: | include/llvm/ADT/SmallBitVector.h |
Warning: | line 121, column 3 Potential memory leak |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- CoverageMapping.cpp - Code coverage mapping support ----------------===// | |||
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 clang's and llvm's instrumentation based | |||
11 | // code coverage. | |||
12 | // | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #include "llvm/ProfileData/Coverage/CoverageMapping.h" | |||
16 | #include "llvm/ADT/ArrayRef.h" | |||
17 | #include "llvm/ADT/DenseMap.h" | |||
18 | #include "llvm/ADT/None.h" | |||
19 | #include "llvm/ADT/Optional.h" | |||
20 | #include "llvm/ADT/SmallBitVector.h" | |||
21 | #include "llvm/ADT/SmallVector.h" | |||
22 | #include "llvm/ADT/StringRef.h" | |||
23 | #include "llvm/ProfileData/Coverage/CoverageMappingReader.h" | |||
24 | #include "llvm/ProfileData/InstrProfReader.h" | |||
25 | #include "llvm/Support/Debug.h" | |||
26 | #include "llvm/Support/Errc.h" | |||
27 | #include "llvm/Support/Error.h" | |||
28 | #include "llvm/Support/ErrorHandling.h" | |||
29 | #include "llvm/Support/ManagedStatic.h" | |||
30 | #include "llvm/Support/MemoryBuffer.h" | |||
31 | #include "llvm/Support/raw_ostream.h" | |||
32 | #include <algorithm> | |||
33 | #include <cassert> | |||
34 | #include <cstdint> | |||
35 | #include <iterator> | |||
36 | #include <map> | |||
37 | #include <memory> | |||
38 | #include <string> | |||
39 | #include <system_error> | |||
40 | #include <utility> | |||
41 | #include <vector> | |||
42 | ||||
43 | using namespace llvm; | |||
44 | using namespace coverage; | |||
45 | ||||
46 | #define DEBUG_TYPE"coverage-mapping" "coverage-mapping" | |||
47 | ||||
48 | Counter CounterExpressionBuilder::get(const CounterExpression &E) { | |||
49 | auto It = ExpressionIndices.find(E); | |||
50 | if (It != ExpressionIndices.end()) | |||
51 | return Counter::getExpression(It->second); | |||
52 | unsigned I = Expressions.size(); | |||
53 | Expressions.push_back(E); | |||
54 | ExpressionIndices[E] = I; | |||
55 | return Counter::getExpression(I); | |||
56 | } | |||
57 | ||||
58 | void CounterExpressionBuilder::extractTerms(Counter C, int Factor, | |||
59 | SmallVectorImpl<Term> &Terms) { | |||
60 | switch (C.getKind()) { | |||
61 | case Counter::Zero: | |||
62 | break; | |||
63 | case Counter::CounterValueReference: | |||
64 | Terms.emplace_back(C.getCounterID(), Factor); | |||
65 | break; | |||
66 | case Counter::Expression: | |||
67 | const auto &E = Expressions[C.getExpressionID()]; | |||
68 | extractTerms(E.LHS, Factor, Terms); | |||
69 | extractTerms( | |||
70 | E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms); | |||
71 | break; | |||
72 | } | |||
73 | } | |||
74 | ||||
75 | Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) { | |||
76 | // Gather constant terms. | |||
77 | SmallVector<Term, 32> Terms; | |||
78 | extractTerms(ExpressionTree, +1, Terms); | |||
79 | ||||
80 | // If there are no terms, this is just a zero. The algorithm below assumes at | |||
81 | // least one term. | |||
82 | if (Terms.size() == 0) | |||
83 | return Counter::getZero(); | |||
84 | ||||
85 | // Group the terms by counter ID. | |||
86 | llvm::sort(Terms, [](const Term &LHS, const Term &RHS) { | |||
87 | return LHS.CounterID < RHS.CounterID; | |||
88 | }); | |||
89 | ||||
90 | // Combine terms by counter ID to eliminate counters that sum to zero. | |||
91 | auto Prev = Terms.begin(); | |||
92 | for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) { | |||
93 | if (I->CounterID == Prev->CounterID) { | |||
94 | Prev->Factor += I->Factor; | |||
95 | continue; | |||
96 | } | |||
97 | ++Prev; | |||
98 | *Prev = *I; | |||
99 | } | |||
100 | Terms.erase(++Prev, Terms.end()); | |||
101 | ||||
102 | Counter C; | |||
103 | // Create additions. We do this before subtractions to avoid constructs like | |||
104 | // ((0 - X) + Y), as opposed to (Y - X). | |||
105 | for (auto T : Terms) { | |||
106 | if (T.Factor <= 0) | |||
107 | continue; | |||
108 | for (int I = 0; I < T.Factor; ++I) | |||
109 | if (C.isZero()) | |||
110 | C = Counter::getCounter(T.CounterID); | |||
111 | else | |||
112 | C = get(CounterExpression(CounterExpression::Add, C, | |||
113 | Counter::getCounter(T.CounterID))); | |||
114 | } | |||
115 | ||||
116 | // Create subtractions. | |||
117 | for (auto T : Terms) { | |||
118 | if (T.Factor >= 0) | |||
119 | continue; | |||
120 | for (int I = 0; I < -T.Factor; ++I) | |||
121 | C = get(CounterExpression(CounterExpression::Subtract, C, | |||
122 | Counter::getCounter(T.CounterID))); | |||
123 | } | |||
124 | return C; | |||
125 | } | |||
126 | ||||
127 | Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) { | |||
128 | return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS))); | |||
129 | } | |||
130 | ||||
131 | Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) { | |||
132 | return simplify( | |||
133 | get(CounterExpression(CounterExpression::Subtract, LHS, RHS))); | |||
134 | } | |||
135 | ||||
136 | void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const { | |||
137 | switch (C.getKind()) { | |||
138 | case Counter::Zero: | |||
139 | OS << '0'; | |||
140 | return; | |||
141 | case Counter::CounterValueReference: | |||
142 | OS << '#' << C.getCounterID(); | |||
143 | break; | |||
144 | case Counter::Expression: { | |||
145 | if (C.getExpressionID() >= Expressions.size()) | |||
146 | return; | |||
147 | const auto &E = Expressions[C.getExpressionID()]; | |||
148 | OS << '('; | |||
149 | dump(E.LHS, OS); | |||
150 | OS << (E.Kind == CounterExpression::Subtract ? " - " : " + "); | |||
151 | dump(E.RHS, OS); | |||
152 | OS << ')'; | |||
153 | break; | |||
154 | } | |||
155 | } | |||
156 | if (CounterValues.empty()) | |||
157 | return; | |||
158 | Expected<int64_t> Value = evaluate(C); | |||
159 | if (auto E = Value.takeError()) { | |||
160 | consumeError(std::move(E)); | |||
161 | return; | |||
162 | } | |||
163 | OS << '[' << *Value << ']'; | |||
164 | } | |||
165 | ||||
166 | Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { | |||
167 | switch (C.getKind()) { | |||
168 | case Counter::Zero: | |||
169 | return 0; | |||
170 | case Counter::CounterValueReference: | |||
171 | if (C.getCounterID() >= CounterValues.size()) | |||
172 | return errorCodeToError(errc::argument_out_of_domain); | |||
173 | return CounterValues[C.getCounterID()]; | |||
174 | case Counter::Expression: { | |||
175 | if (C.getExpressionID() >= Expressions.size()) | |||
176 | return errorCodeToError(errc::argument_out_of_domain); | |||
177 | const auto &E = Expressions[C.getExpressionID()]; | |||
178 | Expected<int64_t> LHS = evaluate(E.LHS); | |||
179 | if (!LHS) | |||
180 | return LHS; | |||
181 | Expected<int64_t> RHS = evaluate(E.RHS); | |||
182 | if (!RHS) | |||
183 | return RHS; | |||
184 | return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS; | |||
185 | } | |||
186 | } | |||
187 | llvm_unreachable("Unhandled CounterKind")::llvm::llvm_unreachable_internal("Unhandled CounterKind", "/build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp" , 187); | |||
188 | } | |||
189 | ||||
190 | void FunctionRecordIterator::skipOtherFiles() { | |||
191 | while (Current != Records.end() && !Filename.empty() && | |||
192 | Filename != Current->Filenames[0]) | |||
193 | ++Current; | |||
194 | if (Current == Records.end()) | |||
195 | *this = FunctionRecordIterator(); | |||
196 | } | |||
197 | ||||
198 | Error CoverageMapping::loadFunctionRecord( | |||
199 | const CoverageMappingRecord &Record, | |||
200 | IndexedInstrProfReader &ProfileReader) { | |||
201 | StringRef OrigFuncName = Record.FunctionName; | |||
202 | if (OrigFuncName.empty()) | |||
203 | return make_error<CoverageMapError>(coveragemap_error::malformed); | |||
204 | ||||
205 | if (Record.Filenames.empty()) | |||
206 | OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName); | |||
207 | else | |||
208 | OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]); | |||
209 | ||||
210 | CounterMappingContext Ctx(Record.Expressions); | |||
211 | ||||
212 | std::vector<uint64_t> Counts; | |||
213 | if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName, | |||
214 | Record.FunctionHash, Counts)) { | |||
215 | instrprof_error IPE = InstrProfError::take(std::move(E)); | |||
216 | if (IPE == instrprof_error::hash_mismatch) { | |||
217 | FuncHashMismatches.emplace_back(Record.FunctionName, Record.FunctionHash); | |||
218 | return Error::success(); | |||
219 | } else if (IPE != instrprof_error::unknown_function) | |||
220 | return make_error<InstrProfError>(IPE); | |||
221 | Counts.assign(Record.MappingRegions.size(), 0); | |||
222 | } | |||
223 | Ctx.setCounts(Counts); | |||
224 | ||||
225 | assert(!Record.MappingRegions.empty() && "Function has no regions")((!Record.MappingRegions.empty() && "Function has no regions" ) ? static_cast<void> (0) : __assert_fail ("!Record.MappingRegions.empty() && \"Function has no regions\"" , "/build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp" , 225, __PRETTY_FUNCTION__)); | |||
226 | ||||
227 | // This coverage record is a zero region for a function that's unused in | |||
228 | // some TU, but used in a different TU. Ignore it. The coverage maps from the | |||
229 | // the other TU will either be loaded (providing full region counts) or they | |||
230 | // won't (in which case we don't unintuitively report functions as uncovered | |||
231 | // when they have non-zero counts in the profile). | |||
232 | if (Record.MappingRegions.size() == 1 && | |||
233 | Record.MappingRegions[0].Count.isZero() && Counts[0] > 0) | |||
234 | return Error::success(); | |||
235 | ||||
236 | FunctionRecord Function(OrigFuncName, Record.Filenames); | |||
237 | for (const auto &Region : Record.MappingRegions) { | |||
238 | Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count); | |||
239 | if (auto E = ExecutionCount.takeError()) { | |||
240 | consumeError(std::move(E)); | |||
241 | return Error::success(); | |||
242 | } | |||
243 | Function.pushRegion(Region, *ExecutionCount); | |||
244 | } | |||
245 | ||||
246 | // Don't create records for (filenames, function) pairs we've already seen. | |||
247 | auto FilenamesHash = hash_combine_range(Record.Filenames.begin(), | |||
248 | Record.Filenames.end()); | |||
249 | if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second) | |||
250 | return Error::success(); | |||
251 | ||||
252 | Functions.push_back(std::move(Function)); | |||
253 | return Error::success(); | |||
254 | } | |||
255 | ||||
256 | Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( | |||
257 | ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, | |||
258 | IndexedInstrProfReader &ProfileReader) { | |||
259 | auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); | |||
260 | ||||
261 | for (const auto &CoverageReader : CoverageReaders) { | |||
262 | for (auto RecordOrErr : *CoverageReader) { | |||
263 | if (Error E = RecordOrErr.takeError()) | |||
264 | return std::move(E); | |||
265 | const auto &Record = *RecordOrErr; | |||
266 | if (Error E = Coverage->loadFunctionRecord(Record, ProfileReader)) | |||
267 | return std::move(E); | |||
268 | } | |||
269 | } | |||
270 | ||||
271 | return std::move(Coverage); | |||
272 | } | |||
273 | ||||
274 | Expected<std::unique_ptr<CoverageMapping>> | |||
275 | CoverageMapping::load(ArrayRef<StringRef> ObjectFilenames, | |||
276 | StringRef ProfileFilename, ArrayRef<StringRef> Arches) { | |||
277 | auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename); | |||
278 | if (Error E = ProfileReaderOrErr.takeError()) | |||
279 | return std::move(E); | |||
280 | auto ProfileReader = std::move(ProfileReaderOrErr.get()); | |||
281 | ||||
282 | SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers; | |||
283 | SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers; | |||
284 | for (const auto &File : llvm::enumerate(ObjectFilenames)) { | |||
285 | auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(File.value()); | |||
286 | if (std::error_code EC = CovMappingBufOrErr.getError()) | |||
287 | return errorCodeToError(EC); | |||
288 | StringRef Arch = Arches.empty() ? StringRef() : Arches[File.index()]; | |||
289 | auto CoverageReaderOrErr = | |||
290 | BinaryCoverageReader::create(CovMappingBufOrErr.get(), Arch); | |||
291 | if (Error E = CoverageReaderOrErr.takeError()) | |||
292 | return std::move(E); | |||
293 | Readers.push_back(std::move(CoverageReaderOrErr.get())); | |||
294 | Buffers.push_back(std::move(CovMappingBufOrErr.get())); | |||
295 | } | |||
296 | return load(Readers, *ProfileReader); | |||
297 | } | |||
298 | ||||
299 | namespace { | |||
300 | ||||
301 | /// Distributes functions into instantiation sets. | |||
302 | /// | |||
303 | /// An instantiation set is a collection of functions that have the same source | |||
304 | /// code, ie, template functions specializations. | |||
305 | class FunctionInstantiationSetCollector { | |||
306 | using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; | |||
307 | MapT InstantiatedFunctions; | |||
308 | ||||
309 | public: | |||
310 | void insert(const FunctionRecord &Function, unsigned FileID) { | |||
311 | auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end(); | |||
312 | while (I != E && I->FileID != FileID) | |||
313 | ++I; | |||
314 | assert(I != E && "function does not cover the given file")((I != E && "function does not cover the given file") ? static_cast<void> (0) : __assert_fail ("I != E && \"function does not cover the given file\"" , "/build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp" , 314, __PRETTY_FUNCTION__)); | |||
315 | auto &Functions = InstantiatedFunctions[I->startLoc()]; | |||
316 | Functions.push_back(&Function); | |||
317 | } | |||
318 | ||||
319 | MapT::iterator begin() { return InstantiatedFunctions.begin(); } | |||
320 | MapT::iterator end() { return InstantiatedFunctions.end(); } | |||
321 | }; | |||
322 | ||||
323 | class SegmentBuilder { | |||
324 | std::vector<CoverageSegment> &Segments; | |||
325 | SmallVector<const CountedRegion *, 8> ActiveRegions; | |||
326 | ||||
327 | SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {} | |||
328 | ||||
329 | /// Emit a segment with the count from \p Region starting at \p StartLoc. | |||
330 | // | |||
331 | /// \p IsRegionEntry: The segment is at the start of a new non-gap region. | |||
332 | /// \p EmitSkippedRegion: The segment must be emitted as a skipped region. | |||
333 | void startSegment(const CountedRegion &Region, LineColPair StartLoc, | |||
334 | bool IsRegionEntry, bool EmitSkippedRegion = false) { | |||
335 | bool HasCount = !EmitSkippedRegion && | |||
336 | (Region.Kind != CounterMappingRegion::SkippedRegion); | |||
337 | ||||
338 | // If the new segment wouldn't affect coverage rendering, skip it. | |||
339 | if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) { | |||
340 | const auto &Last = Segments.back(); | |||
341 | if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount && | |||
342 | !Last.IsRegionEntry) | |||
343 | return; | |||
344 | } | |||
345 | ||||
346 | if (HasCount) | |||
347 | Segments.emplace_back(StartLoc.first, StartLoc.second, | |||
348 | Region.ExecutionCount, IsRegionEntry, | |||
349 | Region.Kind == CounterMappingRegion::GapRegion); | |||
350 | else | |||
351 | Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry); | |||
352 | ||||
353 | LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { const auto &Last = Segments.back (); dbgs() << "Segment at " << Last.Line << ":" << Last.Col << " (count = " << Last.Count << ")" << (Last.IsRegionEntry ? ", RegionEntry" : "") << (!Last.HasCount ? ", Skipped" : "") << (Last .IsGapRegion ? ", Gap" : "") << "\n"; }; } } while (false ) | |||
354 | const auto &Last = Segments.back();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { const auto &Last = Segments.back (); dbgs() << "Segment at " << Last.Line << ":" << Last.Col << " (count = " << Last.Count << ")" << (Last.IsRegionEntry ? ", RegionEntry" : "") << (!Last.HasCount ? ", Skipped" : "") << (Last .IsGapRegion ? ", Gap" : "") << "\n"; }; } } while (false ) | |||
355 | dbgs() << "Segment at " << Last.Line << ":" << Last.Coldo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { const auto &Last = Segments.back (); dbgs() << "Segment at " << Last.Line << ":" << Last.Col << " (count = " << Last.Count << ")" << (Last.IsRegionEntry ? ", RegionEntry" : "") << (!Last.HasCount ? ", Skipped" : "") << (Last .IsGapRegion ? ", Gap" : "") << "\n"; }; } } while (false ) | |||
356 | << " (count = " << Last.Count << ")"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { const auto &Last = Segments.back (); dbgs() << "Segment at " << Last.Line << ":" << Last.Col << " (count = " << Last.Count << ")" << (Last.IsRegionEntry ? ", RegionEntry" : "") << (!Last.HasCount ? ", Skipped" : "") << (Last .IsGapRegion ? ", Gap" : "") << "\n"; }; } } while (false ) | |||
357 | << (Last.IsRegionEntry ? ", RegionEntry" : "")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { const auto &Last = Segments.back (); dbgs() << "Segment at " << Last.Line << ":" << Last.Col << " (count = " << Last.Count << ")" << (Last.IsRegionEntry ? ", RegionEntry" : "") << (!Last.HasCount ? ", Skipped" : "") << (Last .IsGapRegion ? ", Gap" : "") << "\n"; }; } } while (false ) | |||
358 | << (!Last.HasCount ? ", Skipped" : "")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { const auto &Last = Segments.back (); dbgs() << "Segment at " << Last.Line << ":" << Last.Col << " (count = " << Last.Count << ")" << (Last.IsRegionEntry ? ", RegionEntry" : "") << (!Last.HasCount ? ", Skipped" : "") << (Last .IsGapRegion ? ", Gap" : "") << "\n"; }; } } while (false ) | |||
359 | << (Last.IsGapRegion ? ", Gap" : "") << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { const auto &Last = Segments.back (); dbgs() << "Segment at " << Last.Line << ":" << Last.Col << " (count = " << Last.Count << ")" << (Last.IsRegionEntry ? ", RegionEntry" : "") << (!Last.HasCount ? ", Skipped" : "") << (Last .IsGapRegion ? ", Gap" : "") << "\n"; }; } } while (false ) | |||
360 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { const auto &Last = Segments.back (); dbgs() << "Segment at " << Last.Line << ":" << Last.Col << " (count = " << Last.Count << ")" << (Last.IsRegionEntry ? ", RegionEntry" : "") << (!Last.HasCount ? ", Skipped" : "") << (Last .IsGapRegion ? ", Gap" : "") << "\n"; }; } } while (false ); | |||
361 | } | |||
362 | ||||
363 | /// Emit segments for active regions which end before \p Loc. | |||
364 | /// | |||
365 | /// \p Loc: The start location of the next region. If None, all active | |||
366 | /// regions are completed. | |||
367 | /// \p FirstCompletedRegion: Index of the first completed region. | |||
368 | void completeRegionsUntil(Optional<LineColPair> Loc, | |||
369 | unsigned FirstCompletedRegion) { | |||
370 | // Sort the completed regions by end location. This makes it simple to | |||
371 | // emit closing segments in sorted order. | |||
372 | auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion; | |||
373 | std::stable_sort(CompletedRegionsIt, ActiveRegions.end(), | |||
374 | [](const CountedRegion *L, const CountedRegion *R) { | |||
375 | return L->endLoc() < R->endLoc(); | |||
376 | }); | |||
377 | ||||
378 | // Emit segments for all completed regions. | |||
379 | for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E; | |||
380 | ++I) { | |||
381 | const auto *CompletedRegion = ActiveRegions[I]; | |||
382 | assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&(((!Loc || CompletedRegion->endLoc() <= *Loc) && "Completed region ends after start of new region") ? static_cast <void> (0) : __assert_fail ("(!Loc || CompletedRegion->endLoc() <= *Loc) && \"Completed region ends after start of new region\"" , "/build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp" , 383, __PRETTY_FUNCTION__)) | |||
383 | "Completed region ends after start of new region")(((!Loc || CompletedRegion->endLoc() <= *Loc) && "Completed region ends after start of new region") ? static_cast <void> (0) : __assert_fail ("(!Loc || CompletedRegion->endLoc() <= *Loc) && \"Completed region ends after start of new region\"" , "/build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp" , 383, __PRETTY_FUNCTION__)); | |||
384 | ||||
385 | const auto *PrevCompletedRegion = ActiveRegions[I - 1]; | |||
386 | auto CompletedSegmentLoc = PrevCompletedRegion->endLoc(); | |||
387 | ||||
388 | // Don't emit any more segments if they start where the new region begins. | |||
389 | if (Loc && CompletedSegmentLoc == *Loc) | |||
390 | break; | |||
391 | ||||
392 | // Don't emit a segment if the next completed region ends at the same | |||
393 | // location as this one. | |||
394 | if (CompletedSegmentLoc == CompletedRegion->endLoc()) | |||
395 | continue; | |||
396 | ||||
397 | // Use the count from the last completed region which ends at this loc. | |||
398 | for (unsigned J = I + 1; J < E; ++J) | |||
399 | if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc()) | |||
400 | CompletedRegion = ActiveRegions[J]; | |||
401 | ||||
402 | startSegment(*CompletedRegion, CompletedSegmentLoc, false); | |||
403 | } | |||
404 | ||||
405 | auto Last = ActiveRegions.back(); | |||
406 | if (FirstCompletedRegion && Last->endLoc() != *Loc) { | |||
407 | // If there's a gap after the end of the last completed region and the | |||
408 | // start of the new region, use the last active region to fill the gap. | |||
409 | startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(), | |||
410 | false); | |||
411 | } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) { | |||
412 | // Emit a skipped segment if there are no more active regions. This | |||
413 | // ensures that gaps between functions are marked correctly. | |||
414 | startSegment(*Last, Last->endLoc(), false, true); | |||
415 | } | |||
416 | ||||
417 | // Pop the completed regions. | |||
418 | ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end()); | |||
419 | } | |||
420 | ||||
421 | void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) { | |||
422 | for (const auto &CR : enumerate(Regions)) { | |||
423 | auto CurStartLoc = CR.value().startLoc(); | |||
424 | ||||
425 | // Active regions which end before the current region need to be popped. | |||
426 | auto CompletedRegions = | |||
427 | std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(), | |||
428 | [&](const CountedRegion *Region) { | |||
429 | return !(Region->endLoc() <= CurStartLoc); | |||
430 | }); | |||
431 | if (CompletedRegions != ActiveRegions.end()) { | |||
432 | unsigned FirstCompletedRegion = | |||
433 | std::distance(ActiveRegions.begin(), CompletedRegions); | |||
434 | completeRegionsUntil(CurStartLoc, FirstCompletedRegion); | |||
435 | } | |||
436 | ||||
437 | bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion; | |||
438 | ||||
439 | // Try to emit a segment for the current region. | |||
440 | if (CurStartLoc == CR.value().endLoc()) { | |||
441 | // Avoid making zero-length regions active. If it's the last region, | |||
442 | // emit a skipped segment. Otherwise use its predecessor's count. | |||
443 | const bool Skipped = (CR.index() + 1) == Regions.size(); | |||
444 | startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(), | |||
445 | CurStartLoc, !GapRegion, Skipped); | |||
446 | continue; | |||
447 | } | |||
448 | if (CR.index() + 1 == Regions.size() || | |||
449 | CurStartLoc != Regions[CR.index() + 1].startLoc()) { | |||
450 | // Emit a segment if the next region doesn't start at the same location | |||
451 | // as this one. | |||
452 | startSegment(CR.value(), CurStartLoc, !GapRegion); | |||
453 | } | |||
454 | ||||
455 | // This region is active (i.e not completed). | |||
456 | ActiveRegions.push_back(&CR.value()); | |||
457 | } | |||
458 | ||||
459 | // Complete any remaining active regions. | |||
460 | if (!ActiveRegions.empty()) | |||
461 | completeRegionsUntil(None, 0); | |||
462 | } | |||
463 | ||||
464 | /// Sort a nested sequence of regions from a single file. | |||
465 | static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) { | |||
466 | llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) { | |||
467 | if (LHS.startLoc() != RHS.startLoc()) | |||
468 | return LHS.startLoc() < RHS.startLoc(); | |||
469 | if (LHS.endLoc() != RHS.endLoc()) | |||
470 | // When LHS completely contains RHS, we sort LHS first. | |||
471 | return RHS.endLoc() < LHS.endLoc(); | |||
472 | // If LHS and RHS cover the same area, we need to sort them according | |||
473 | // to their kinds so that the most suitable region will become "active" | |||
474 | // in combineRegions(). Because we accumulate counter values only from | |||
475 | // regions of the same kind as the first region of the area, prefer | |||
476 | // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion. | |||
477 | static_assert(CounterMappingRegion::CodeRegion < | |||
478 | CounterMappingRegion::ExpansionRegion && | |||
479 | CounterMappingRegion::ExpansionRegion < | |||
480 | CounterMappingRegion::SkippedRegion, | |||
481 | "Unexpected order of region kind values"); | |||
482 | return LHS.Kind < RHS.Kind; | |||
483 | }); | |||
484 | } | |||
485 | ||||
486 | /// Combine counts of regions which cover the same area. | |||
487 | static ArrayRef<CountedRegion> | |||
488 | combineRegions(MutableArrayRef<CountedRegion> Regions) { | |||
489 | if (Regions.empty()) | |||
490 | return Regions; | |||
491 | auto Active = Regions.begin(); | |||
492 | auto End = Regions.end(); | |||
493 | for (auto I = Regions.begin() + 1; I != End; ++I) { | |||
494 | if (Active->startLoc() != I->startLoc() || | |||
495 | Active->endLoc() != I->endLoc()) { | |||
496 | // Shift to the next region. | |||
497 | ++Active; | |||
498 | if (Active != I) | |||
499 | *Active = *I; | |||
500 | continue; | |||
501 | } | |||
502 | // Merge duplicate region. | |||
503 | // If CodeRegions and ExpansionRegions cover the same area, it's probably | |||
504 | // a macro which is fully expanded to another macro. In that case, we need | |||
505 | // to accumulate counts only from CodeRegions, or else the area will be | |||
506 | // counted twice. | |||
507 | // On the other hand, a macro may have a nested macro in its body. If the | |||
508 | // outer macro is used several times, the ExpansionRegion for the nested | |||
509 | // macro will also be added several times. These ExpansionRegions cover | |||
510 | // the same source locations and have to be combined to reach the correct | |||
511 | // value for that area. | |||
512 | // We add counts of the regions of the same kind as the active region | |||
513 | // to handle the both situations. | |||
514 | if (I->Kind == Active->Kind) | |||
515 | Active->ExecutionCount += I->ExecutionCount; | |||
516 | } | |||
517 | return Regions.drop_back(std::distance(++Active, End)); | |||
518 | } | |||
519 | ||||
520 | public: | |||
521 | /// Build a sorted list of CoverageSegments from a list of Regions. | |||
522 | static std::vector<CoverageSegment> | |||
523 | buildSegments(MutableArrayRef<CountedRegion> Regions) { | |||
524 | std::vector<CoverageSegment> Segments; | |||
525 | SegmentBuilder Builder(Segments); | |||
526 | ||||
527 | sortNestedRegions(Regions); | |||
528 | ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions); | |||
529 | ||||
530 | LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { dbgs() << "Combined regions:\n" ; for (const auto &CR : CombinedRegions) dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " << CR.LineEnd << ":" << CR.ColumnEnd << " (count=" << CR.ExecutionCount << ")\n" ; }; } } while (false) | |||
531 | dbgs() << "Combined regions:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { dbgs() << "Combined regions:\n" ; for (const auto &CR : CombinedRegions) dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " << CR.LineEnd << ":" << CR.ColumnEnd << " (count=" << CR.ExecutionCount << ")\n" ; }; } } while (false) | |||
532 | for (const auto &CR : CombinedRegions)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { dbgs() << "Combined regions:\n" ; for (const auto &CR : CombinedRegions) dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " << CR.LineEnd << ":" << CR.ColumnEnd << " (count=" << CR.ExecutionCount << ")\n" ; }; } } while (false) | |||
533 | dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { dbgs() << "Combined regions:\n" ; for (const auto &CR : CombinedRegions) dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " << CR.LineEnd << ":" << CR.ColumnEnd << " (count=" << CR.ExecutionCount << ")\n" ; }; } } while (false) | |||
534 | << CR.LineEnd << ":" << CR.ColumnEnddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { dbgs() << "Combined regions:\n" ; for (const auto &CR : CombinedRegions) dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " << CR.LineEnd << ":" << CR.ColumnEnd << " (count=" << CR.ExecutionCount << ")\n" ; }; } } while (false) | |||
535 | << " (count=" << CR.ExecutionCount << ")\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { dbgs() << "Combined regions:\n" ; for (const auto &CR : CombinedRegions) dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " << CR.LineEnd << ":" << CR.ColumnEnd << " (count=" << CR.ExecutionCount << ")\n" ; }; } } while (false) | |||
536 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { { dbgs() << "Combined regions:\n" ; for (const auto &CR : CombinedRegions) dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " << CR.LineEnd << ":" << CR.ColumnEnd << " (count=" << CR.ExecutionCount << ")\n" ; }; } } while (false); | |||
537 | ||||
538 | Builder.buildSegmentsImpl(CombinedRegions); | |||
539 | ||||
540 | #ifndef NDEBUG | |||
541 | for (unsigned I = 1, E = Segments.size(); I < E; ++I) { | |||
542 | const auto &L = Segments[I - 1]; | |||
543 | const auto &R = Segments[I]; | |||
544 | if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) { | |||
545 | LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Coldo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { dbgs() << " ! Segment " << L.Line << ":" << L.Col << " followed by " << R.Line << ":" << R.Col << "\n"; } } while ( false) | |||
546 | << " followed by " << R.Line << ":" << R.Col << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { dbgs() << " ! Segment " << L.Line << ":" << L.Col << " followed by " << R.Line << ":" << R.Col << "\n"; } } while ( false); | |||
547 | assert(false && "Coverage segments not unique or sorted")((false && "Coverage segments not unique or sorted") ? static_cast<void> (0) : __assert_fail ("false && \"Coverage segments not unique or sorted\"" , "/build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp" , 547, __PRETTY_FUNCTION__)); | |||
548 | } | |||
549 | } | |||
550 | #endif | |||
551 | ||||
552 | return Segments; | |||
553 | } | |||
554 | }; | |||
555 | ||||
556 | } // end anonymous namespace | |||
557 | ||||
558 | std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const { | |||
559 | std::vector<StringRef> Filenames; | |||
560 | for (const auto &Function : getCoveredFunctions()) | |||
561 | Filenames.insert(Filenames.end(), Function.Filenames.begin(), | |||
562 | Function.Filenames.end()); | |||
563 | llvm::sort(Filenames); | |||
564 | auto Last = std::unique(Filenames.begin(), Filenames.end()); | |||
565 | Filenames.erase(Last, Filenames.end()); | |||
566 | return Filenames; | |||
567 | } | |||
568 | ||||
569 | static SmallBitVector gatherFileIDs(StringRef SourceFile, | |||
570 | const FunctionRecord &Function) { | |||
571 | SmallBitVector FilenameEquivalence(Function.Filenames.size(), false); | |||
572 | for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I) | |||
573 | if (SourceFile == Function.Filenames[I]) | |||
574 | FilenameEquivalence[I] = true; | |||
575 | return FilenameEquivalence; | |||
576 | } | |||
577 | ||||
578 | /// Return the ID of the file where the definition of the function is located. | |||
579 | static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) { | |||
580 | SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); | |||
581 | for (const auto &CR : Function.CountedRegions) | |||
582 | if (CR.Kind == CounterMappingRegion::ExpansionRegion) | |||
583 | IsNotExpandedFile[CR.ExpandedFileID] = false; | |||
584 | int I = IsNotExpandedFile.find_first(); | |||
585 | if (I == -1) | |||
586 | return None; | |||
587 | return I; | |||
588 | } | |||
589 | ||||
590 | /// Check if SourceFile is the file that contains the definition of | |||
591 | /// the Function. Return the ID of the file in that case or None otherwise. | |||
592 | static Optional<unsigned> findMainViewFileID(StringRef SourceFile, | |||
593 | const FunctionRecord &Function) { | |||
594 | Optional<unsigned> I = findMainViewFileID(Function); | |||
595 | if (I && SourceFile == Function.Filenames[*I]) | |||
596 | return I; | |||
597 | return None; | |||
598 | } | |||
599 | ||||
600 | static bool isExpansion(const CountedRegion &R, unsigned FileID) { | |||
601 | return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID; | |||
602 | } | |||
603 | ||||
604 | CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const { | |||
605 | CoverageData FileCoverage(Filename); | |||
606 | std::vector<CountedRegion> Regions; | |||
607 | ||||
608 | for (const auto &Function : Functions) { | |||
609 | auto MainFileID = findMainViewFileID(Filename, Function); | |||
610 | auto FileIDs = gatherFileIDs(Filename, Function); | |||
| ||||
611 | for (const auto &CR : Function.CountedRegions) | |||
612 | if (FileIDs.test(CR.FileID)) { | |||
613 | Regions.push_back(CR); | |||
614 | if (MainFileID && isExpansion(CR, *MainFileID)) | |||
615 | FileCoverage.Expansions.emplace_back(CR, Function); | |||
616 | } | |||
617 | } | |||
618 | ||||
619 | LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { dbgs() << "Emitting segments for file: " << Filename << "\n"; } } while (false); | |||
620 | FileCoverage.Segments = SegmentBuilder::buildSegments(Regions); | |||
621 | ||||
622 | return FileCoverage; | |||
623 | } | |||
624 | ||||
625 | std::vector<InstantiationGroup> | |||
626 | CoverageMapping::getInstantiationGroups(StringRef Filename) const { | |||
627 | FunctionInstantiationSetCollector InstantiationSetCollector; | |||
628 | for (const auto &Function : Functions) { | |||
629 | auto MainFileID = findMainViewFileID(Filename, Function); | |||
630 | if (!MainFileID) | |||
631 | continue; | |||
632 | InstantiationSetCollector.insert(Function, *MainFileID); | |||
633 | } | |||
634 | ||||
635 | std::vector<InstantiationGroup> Result; | |||
636 | for (auto &InstantiationSet : InstantiationSetCollector) { | |||
637 | InstantiationGroup IG{InstantiationSet.first.first, | |||
638 | InstantiationSet.first.second, | |||
639 | std::move(InstantiationSet.second)}; | |||
640 | Result.emplace_back(std::move(IG)); | |||
641 | } | |||
642 | return Result; | |||
643 | } | |||
644 | ||||
645 | CoverageData | |||
646 | CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { | |||
647 | auto MainFileID = findMainViewFileID(Function); | |||
648 | if (!MainFileID) | |||
649 | return CoverageData(); | |||
650 | ||||
651 | CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); | |||
652 | std::vector<CountedRegion> Regions; | |||
653 | for (const auto &CR : Function.CountedRegions) | |||
654 | if (CR.FileID == *MainFileID) { | |||
655 | Regions.push_back(CR); | |||
656 | if (isExpansion(CR, *MainFileID)) | |||
657 | FunctionCoverage.Expansions.emplace_back(CR, Function); | |||
658 | } | |||
659 | ||||
660 | LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Namedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { dbgs() << "Emitting segments for function: " << Function.Name << "\n"; } } while (false) | |||
661 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { dbgs() << "Emitting segments for function: " << Function.Name << "\n"; } } while (false); | |||
662 | FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions); | |||
663 | ||||
664 | return FunctionCoverage; | |||
665 | } | |||
666 | ||||
667 | CoverageData CoverageMapping::getCoverageForExpansion( | |||
668 | const ExpansionRecord &Expansion) const { | |||
669 | CoverageData ExpansionCoverage( | |||
670 | Expansion.Function.Filenames[Expansion.FileID]); | |||
671 | std::vector<CountedRegion> Regions; | |||
672 | for (const auto &CR : Expansion.Function.CountedRegions) | |||
673 | if (CR.FileID == Expansion.FileID) { | |||
674 | Regions.push_back(CR); | |||
675 | if (isExpansion(CR, Expansion.FileID)) | |||
676 | ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function); | |||
677 | } | |||
678 | ||||
679 | LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { dbgs() << "Emitting segments for expansion of file " << Expansion.FileID << "\n"; } } while (false) | |||
680 | << Expansion.FileID << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("coverage-mapping")) { dbgs() << "Emitting segments for expansion of file " << Expansion.FileID << "\n"; } } while (false); | |||
681 | ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); | |||
682 | ||||
683 | return ExpansionCoverage; | |||
684 | } | |||
685 | ||||
686 | LineCoverageStats::LineCoverageStats( | |||
687 | ArrayRef<const CoverageSegment *> LineSegments, | |||
688 | const CoverageSegment *WrappedSegment, unsigned Line) | |||
689 | : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line), | |||
690 | LineSegments(LineSegments), WrappedSegment(WrappedSegment) { | |||
691 | // Find the minimum number of regions which start in this line. | |||
692 | unsigned MinRegionCount = 0; | |||
693 | auto isStartOfRegion = [](const CoverageSegment *S) { | |||
694 | return !S->IsGapRegion && S->HasCount && S->IsRegionEntry; | |||
695 | }; | |||
696 | for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I) | |||
697 | if (isStartOfRegion(LineSegments[I])) | |||
698 | ++MinRegionCount; | |||
699 | ||||
700 | bool StartOfSkippedRegion = !LineSegments.empty() && | |||
701 | !LineSegments.front()->HasCount && | |||
702 | LineSegments.front()->IsRegionEntry; | |||
703 | ||||
704 | HasMultipleRegions = MinRegionCount > 1; | |||
705 | Mapped = | |||
706 | !StartOfSkippedRegion && | |||
707 | ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0)); | |||
708 | ||||
709 | if (!Mapped) | |||
710 | return; | |||
711 | ||||
712 | // Pick the max count from the non-gap, region entry segments and the | |||
713 | // wrapped count. | |||
714 | if (WrappedSegment) | |||
715 | ExecutionCount = WrappedSegment->Count; | |||
716 | if (!MinRegionCount) | |||
717 | return; | |||
718 | for (const auto *LS : LineSegments) | |||
719 | if (isStartOfRegion(LS)) | |||
720 | ExecutionCount = std::max(ExecutionCount, LS->Count); | |||
721 | } | |||
722 | ||||
723 | LineCoverageIterator &LineCoverageIterator::operator++() { | |||
724 | if (Next == CD.end()) { | |||
725 | Stats = LineCoverageStats(); | |||
726 | Ended = true; | |||
727 | return *this; | |||
728 | } | |||
729 | if (Segments.size()) | |||
730 | WrappedSegment = Segments.back(); | |||
731 | Segments.clear(); | |||
732 | while (Next != CD.end() && Next->Line == Line) | |||
733 | Segments.push_back(&*Next++); | |||
734 | Stats = LineCoverageStats(Segments, WrappedSegment, Line); | |||
735 | ++Line; | |||
736 | return *this; | |||
737 | } | |||
738 | ||||
739 | static std::string getCoverageMapErrString(coveragemap_error Err) { | |||
740 | switch (Err) { | |||
741 | case coveragemap_error::success: | |||
742 | return "Success"; | |||
743 | case coveragemap_error::eof: | |||
744 | return "End of File"; | |||
745 | case coveragemap_error::no_data_found: | |||
746 | return "No coverage data found"; | |||
747 | case coveragemap_error::unsupported_version: | |||
748 | return "Unsupported coverage format version"; | |||
749 | case coveragemap_error::truncated: | |||
750 | return "Truncated coverage data"; | |||
751 | case coveragemap_error::malformed: | |||
752 | return "Malformed coverage data"; | |||
753 | } | |||
754 | llvm_unreachable("A value of coveragemap_error has no message.")::llvm::llvm_unreachable_internal("A value of coveragemap_error has no message." , "/build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp" , 754); | |||
755 | } | |||
756 | ||||
757 | namespace { | |||
758 | ||||
759 | // FIXME: This class is only here to support the transition to llvm::Error. It | |||
760 | // will be removed once this transition is complete. Clients should prefer to | |||
761 | // deal with the Error value directly, rather than converting to error_code. | |||
762 | class CoverageMappingErrorCategoryType : public std::error_category { | |||
763 | const char *name() const noexcept override { return "llvm.coveragemap"; } | |||
764 | std::string message(int IE) const override { | |||
765 | return getCoverageMapErrString(static_cast<coveragemap_error>(IE)); | |||
766 | } | |||
767 | }; | |||
768 | ||||
769 | } // end anonymous namespace | |||
770 | ||||
771 | std::string CoverageMapError::message() const { | |||
772 | return getCoverageMapErrString(Err); | |||
773 | } | |||
774 | ||||
775 | static ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory; | |||
776 | ||||
777 | const std::error_category &llvm::coverage::coveragemap_category() { | |||
778 | return *ErrorCategory; | |||
779 | } | |||
780 | ||||
781 | char CoverageMapError::ID = 0; |
1 | //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===// | |||
2 | // | |||
3 | // The LLVM Compiler Infrastructure | |||
4 | // | |||
5 | // This file is distributed under the University of Illinois Open Source | |||
6 | // License. See LICENSE.TXT for details. | |||
7 | // | |||
8 | //===----------------------------------------------------------------------===// | |||
9 | // | |||
10 | // This file implements the SmallBitVector class. | |||
11 | // | |||
12 | //===----------------------------------------------------------------------===// | |||
13 | ||||
14 | #ifndef LLVM_ADT_SMALLBITVECTOR_H | |||
15 | #define LLVM_ADT_SMALLBITVECTOR_H | |||
16 | ||||
17 | #include "llvm/ADT/BitVector.h" | |||
18 | #include "llvm/ADT/iterator_range.h" | |||
19 | #include "llvm/Support/MathExtras.h" | |||
20 | #include <algorithm> | |||
21 | #include <cassert> | |||
22 | #include <climits> | |||
23 | #include <cstddef> | |||
24 | #include <cstdint> | |||
25 | #include <limits> | |||
26 | #include <utility> | |||
27 | ||||
28 | namespace llvm { | |||
29 | ||||
30 | /// This is a 'bitvector' (really, a variable-sized bit array), optimized for | |||
31 | /// the case when the array is small. It contains one pointer-sized field, which | |||
32 | /// is directly used as a plain collection of bits when possible, or as a | |||
33 | /// pointer to a larger heap-allocated array when necessary. This allows normal | |||
34 | /// "small" cases to be fast without losing generality for large inputs. | |||
35 | class SmallBitVector { | |||
36 | // TODO: In "large" mode, a pointer to a BitVector is used, leading to an | |||
37 | // unnecessary level of indirection. It would be more efficient to use a | |||
38 | // pointer to memory containing size, allocation size, and the array of bits. | |||
39 | uintptr_t X = 1; | |||
40 | ||||
41 | enum { | |||
42 | // The number of bits in this class. | |||
43 | NumBaseBits = sizeof(uintptr_t) * CHAR_BIT8, | |||
44 | ||||
45 | // One bit is used to discriminate between small and large mode. The | |||
46 | // remaining bits are used for the small-mode representation. | |||
47 | SmallNumRawBits = NumBaseBits - 1, | |||
48 | ||||
49 | // A few more bits are used to store the size of the bit set in small mode. | |||
50 | // Theoretically this is a ceil-log2. These bits are encoded in the most | |||
51 | // significant bits of the raw bits. | |||
52 | SmallNumSizeBits = (NumBaseBits == 32 ? 5 : | |||
53 | NumBaseBits == 64 ? 6 : | |||
54 | SmallNumRawBits), | |||
55 | ||||
56 | // The remaining bits are used to store the actual set in small mode. | |||
57 | SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits | |||
58 | }; | |||
59 | ||||
60 | static_assert(NumBaseBits == 64 || NumBaseBits == 32, | |||
61 | "Unsupported word size"); | |||
62 | ||||
63 | public: | |||
64 | using size_type = unsigned; | |||
65 | ||||
66 | // Encapsulation of a single bit. | |||
67 | class reference { | |||
68 | SmallBitVector &TheVector; | |||
69 | unsigned BitPos; | |||
70 | ||||
71 | public: | |||
72 | reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} | |||
73 | ||||
74 | reference(const reference&) = default; | |||
75 | ||||
76 | reference& operator=(reference t) { | |||
77 | *this = bool(t); | |||
78 | return *this; | |||
79 | } | |||
80 | ||||
81 | reference& operator=(bool t) { | |||
82 | if (t) | |||
83 | TheVector.set(BitPos); | |||
84 | else | |||
85 | TheVector.reset(BitPos); | |||
86 | return *this; | |||
87 | } | |||
88 | ||||
89 | operator bool() const { | |||
90 | return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); | |||
91 | } | |||
92 | }; | |||
93 | ||||
94 | private: | |||
95 | BitVector *getPointer() const { | |||
96 | assert(!isSmall())((!isSmall()) ? static_cast<void> (0) : __assert_fail ( "!isSmall()", "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 96, __PRETTY_FUNCTION__)); | |||
97 | return reinterpret_cast<BitVector *>(X); | |||
98 | } | |||
99 | ||||
100 | void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { | |||
101 | X = 1; | |||
102 | setSmallSize(NewSize); | |||
103 | setSmallBits(NewSmallBits); | |||
104 | } | |||
105 | ||||
106 | void switchToLarge(BitVector *BV) { | |||
107 | X = reinterpret_cast<uintptr_t>(BV); | |||
108 | assert(!isSmall() && "Tried to use an unaligned pointer")((!isSmall() && "Tried to use an unaligned pointer") ? static_cast<void> (0) : __assert_fail ("!isSmall() && \"Tried to use an unaligned pointer\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 108, __PRETTY_FUNCTION__)); | |||
109 | } | |||
110 | ||||
111 | // Return all the bits used for the "small" representation; this includes | |||
112 | // bits for the size as well as the element bits. | |||
113 | uintptr_t getSmallRawBits() const { | |||
114 | assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 114, __PRETTY_FUNCTION__)); | |||
115 | return X >> 1; | |||
116 | } | |||
117 | ||||
118 | void setSmallRawBits(uintptr_t NewRawBits) { | |||
119 | assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 119, __PRETTY_FUNCTION__)); | |||
120 | X = (NewRawBits << 1) | uintptr_t(1); | |||
121 | } | |||
| ||||
122 | ||||
123 | // Return the size. | |||
124 | size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; } | |||
125 | ||||
126 | void setSmallSize(size_t Size) { | |||
127 | setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); | |||
128 | } | |||
129 | ||||
130 | // Return the element bits. | |||
131 | uintptr_t getSmallBits() const { | |||
132 | return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); | |||
133 | } | |||
134 | ||||
135 | void setSmallBits(uintptr_t NewBits) { | |||
136 | setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | | |||
137 | (getSmallSize() << SmallNumDataBits)); | |||
138 | } | |||
139 | ||||
140 | public: | |||
141 | /// Creates an empty bitvector. | |||
142 | SmallBitVector() = default; | |||
143 | ||||
144 | /// Creates a bitvector of specified number of bits. All bits are initialized | |||
145 | /// to the specified value. | |||
146 | explicit SmallBitVector(unsigned s, bool t = false) { | |||
147 | if (s <= SmallNumDataBits) | |||
148 | switchToSmall(t ? ~uintptr_t(0) : 0, s); | |||
149 | else | |||
150 | switchToLarge(new BitVector(s, t)); | |||
151 | } | |||
152 | ||||
153 | /// SmallBitVector copy ctor. | |||
154 | SmallBitVector(const SmallBitVector &RHS) { | |||
155 | if (RHS.isSmall()) | |||
156 | X = RHS.X; | |||
157 | else | |||
158 | switchToLarge(new BitVector(*RHS.getPointer())); | |||
159 | } | |||
160 | ||||
161 | SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { | |||
162 | RHS.X = 1; | |||
163 | } | |||
164 | ||||
165 | ~SmallBitVector() { | |||
166 | if (!isSmall()) | |||
167 | delete getPointer(); | |||
168 | } | |||
169 | ||||
170 | using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>; | |||
171 | using set_iterator = const_set_bits_iterator; | |||
172 | ||||
173 | const_set_bits_iterator set_bits_begin() const { | |||
174 | return const_set_bits_iterator(*this); | |||
175 | } | |||
176 | ||||
177 | const_set_bits_iterator set_bits_end() const { | |||
178 | return const_set_bits_iterator(*this, -1); | |||
179 | } | |||
180 | ||||
181 | iterator_range<const_set_bits_iterator> set_bits() const { | |||
182 | return make_range(set_bits_begin(), set_bits_end()); | |||
183 | } | |||
184 | ||||
185 | bool isSmall() const { return X & uintptr_t(1); } | |||
186 | ||||
187 | /// Tests whether there are no bits in this bitvector. | |||
188 | bool empty() const { | |||
189 | return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); | |||
190 | } | |||
191 | ||||
192 | /// Returns the number of bits in this bitvector. | |||
193 | size_t size() const { | |||
194 | return isSmall() ? getSmallSize() : getPointer()->size(); | |||
195 | } | |||
196 | ||||
197 | /// Returns the number of bits which are set. | |||
198 | size_type count() const { | |||
199 | if (isSmall()) { | |||
200 | uintptr_t Bits = getSmallBits(); | |||
201 | return countPopulation(Bits); | |||
202 | } | |||
203 | return getPointer()->count(); | |||
204 | } | |||
205 | ||||
206 | /// Returns true if any bit is set. | |||
207 | bool any() const { | |||
208 | if (isSmall()) | |||
209 | return getSmallBits() != 0; | |||
210 | return getPointer()->any(); | |||
211 | } | |||
212 | ||||
213 | /// Returns true if all bits are set. | |||
214 | bool all() const { | |||
215 | if (isSmall()) | |||
216 | return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; | |||
217 | return getPointer()->all(); | |||
218 | } | |||
219 | ||||
220 | /// Returns true if none of the bits are set. | |||
221 | bool none() const { | |||
222 | if (isSmall()) | |||
223 | return getSmallBits() == 0; | |||
224 | return getPointer()->none(); | |||
225 | } | |||
226 | ||||
227 | /// Returns the index of the first set bit, -1 if none of the bits are set. | |||
228 | int find_first() const { | |||
229 | if (isSmall()) { | |||
230 | uintptr_t Bits = getSmallBits(); | |||
231 | if (Bits == 0) | |||
232 | return -1; | |||
233 | return countTrailingZeros(Bits); | |||
234 | } | |||
235 | return getPointer()->find_first(); | |||
236 | } | |||
237 | ||||
238 | int find_last() const { | |||
239 | if (isSmall()) { | |||
240 | uintptr_t Bits = getSmallBits(); | |||
241 | if (Bits == 0) | |||
242 | return -1; | |||
243 | return NumBaseBits - countLeadingZeros(Bits) - 1; | |||
244 | } | |||
245 | return getPointer()->find_last(); | |||
246 | } | |||
247 | ||||
248 | /// Returns the index of the first unset bit, -1 if all of the bits are set. | |||
249 | int find_first_unset() const { | |||
250 | if (isSmall()) { | |||
251 | if (count() == getSmallSize()) | |||
252 | return -1; | |||
253 | ||||
254 | uintptr_t Bits = getSmallBits(); | |||
255 | return countTrailingOnes(Bits); | |||
256 | } | |||
257 | return getPointer()->find_first_unset(); | |||
258 | } | |||
259 | ||||
260 | int find_last_unset() const { | |||
261 | if (isSmall()) { | |||
262 | if (count() == getSmallSize()) | |||
263 | return -1; | |||
264 | ||||
265 | uintptr_t Bits = getSmallBits(); | |||
266 | // Set unused bits. | |||
267 | Bits |= ~uintptr_t(0) << getSmallSize(); | |||
268 | return NumBaseBits - countLeadingOnes(Bits) - 1; | |||
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>(((Idx <= static_cast<unsigned>( std::numeric_limits< uintptr_t>::digits) && "undefined behavior") ? static_cast <void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 376, __PRETTY_FUNCTION__)) | |||
375 | std::numeric_limits<uintptr_t>::digits) &&((Idx <= static_cast<unsigned>( std::numeric_limits< uintptr_t>::digits) && "undefined behavior") ? static_cast <void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 376, __PRETTY_FUNCTION__)) | |||
376 | "undefined behavior")((Idx <= static_cast<unsigned>( std::numeric_limits< uintptr_t>::digits) && "undefined behavior") ? static_cast <void> (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 376, __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!")((I <= E && "Attempted to set backwards range!") ? static_cast<void> (0) : __assert_fail ("I <= E && \"Attempted to set backwards range!\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 386, __PRETTY_FUNCTION__)); | |||
387 | assert(E <= size() && "Attempted to set out-of-bounds range!")((E <= size() && "Attempted to set out-of-bounds range!" ) ? static_cast<void> (0) : __assert_fail ("E <= size() && \"Attempted to set out-of-bounds range!\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 387, __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!")((I <= E && "Attempted to reset backwards range!") ? static_cast<void> (0) : __assert_fail ("I <= E && \"Attempted to reset backwards range!\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 417, __PRETTY_FUNCTION__)); | |||
418 | assert(E <= size() && "Attempted to reset out-of-bounds range!")((E <= size() && "Attempted to reset out-of-bounds range!" ) ? static_cast<void> (0) : __assert_fail ("E <= size() && \"Attempted to reset out-of-bounds range!\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 418, __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.")((Idx < size() && "Out-of-bounds Bit access.") ? static_cast <void> (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 453, __PRETTY_FUNCTION__)); | |||
454 | return reference(*this, Idx); | |||
455 | } | |||
456 | ||||
457 | bool operator[](unsigned Idx) const { | |||
458 | assert(Idx < size() && "Out-of-bounds Bit access.")((Idx < size() && "Out-of-bounds Bit access.") ? static_cast <void> (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 458, __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 | // Push single bit to end of vector. | |||
469 | void push_back(bool Val) { | |||
470 | resize(size() + 1, Val); | |||
471 | } | |||
472 | ||||
473 | /// Test if any common bits are set. | |||
474 | bool anyCommon(const SmallBitVector &RHS) const { | |||
475 | if (isSmall() && RHS.isSmall()) | |||
476 | return (getSmallBits() & RHS.getSmallBits()) != 0; | |||
477 | if (!isSmall() && !RHS.isSmall()) | |||
478 | return getPointer()->anyCommon(*RHS.getPointer()); | |||
479 | ||||
480 | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) | |||
481 | if (test(i) && RHS.test(i)) | |||
482 | return true; | |||
483 | return false; | |||
484 | } | |||
485 | ||||
486 | // Comparison operators. | |||
487 | bool operator==(const SmallBitVector &RHS) const { | |||
488 | if (size() != RHS.size()) | |||
489 | return false; | |||
490 | if (isSmall() && RHS.isSmall()) | |||
491 | return getSmallBits() == RHS.getSmallBits(); | |||
492 | else if (!isSmall() && !RHS.isSmall()) | |||
493 | return *getPointer() == *RHS.getPointer(); | |||
494 | else { | |||
495 | for (size_t i = 0, e = size(); i != e; ++i) { | |||
496 | if ((*this)[i] != RHS[i]) | |||
497 | return false; | |||
498 | } | |||
499 | return true; | |||
500 | } | |||
501 | } | |||
502 | ||||
503 | bool operator!=(const SmallBitVector &RHS) const { | |||
504 | return !(*this == RHS); | |||
505 | } | |||
506 | ||||
507 | // Intersection, union, disjoint union. | |||
508 | // FIXME BitVector::operator&= does not resize the LHS but this does | |||
509 | SmallBitVector &operator&=(const SmallBitVector &RHS) { | |||
510 | resize(std::max(size(), RHS.size())); | |||
511 | if (isSmall() && RHS.isSmall()) | |||
512 | setSmallBits(getSmallBits() & RHS.getSmallBits()); | |||
513 | else if (!isSmall() && !RHS.isSmall()) | |||
514 | getPointer()->operator&=(*RHS.getPointer()); | |||
515 | else { | |||
516 | size_t i, e; | |||
517 | for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) | |||
518 | (*this)[i] = test(i) && RHS.test(i); | |||
519 | for (e = size(); i != e; ++i) | |||
520 | reset(i); | |||
521 | } | |||
522 | return *this; | |||
523 | } | |||
524 | ||||
525 | /// Reset bits that are set in RHS. Same as *this &= ~RHS. | |||
526 | SmallBitVector &reset(const SmallBitVector &RHS) { | |||
527 | if (isSmall() && RHS.isSmall()) | |||
528 | setSmallBits(getSmallBits() & ~RHS.getSmallBits()); | |||
529 | else if (!isSmall() && !RHS.isSmall()) | |||
530 | getPointer()->reset(*RHS.getPointer()); | |||
531 | else | |||
532 | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) | |||
533 | if (RHS.test(i)) | |||
534 | reset(i); | |||
535 | ||||
536 | return *this; | |||
537 | } | |||
538 | ||||
539 | /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any(). | |||
540 | bool test(const SmallBitVector &RHS) const { | |||
541 | if (isSmall() && RHS.isSmall()) | |||
542 | return (getSmallBits() & ~RHS.getSmallBits()) != 0; | |||
543 | if (!isSmall() && !RHS.isSmall()) | |||
544 | return getPointer()->test(*RHS.getPointer()); | |||
545 | ||||
546 | unsigned i, e; | |||
547 | for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) | |||
548 | if (test(i) && !RHS.test(i)) | |||
549 | return true; | |||
550 | ||||
551 | for (e = size(); i != e; ++i) | |||
552 | if (test(i)) | |||
553 | return true; | |||
554 | ||||
555 | return false; | |||
556 | } | |||
557 | ||||
558 | SmallBitVector &operator|=(const SmallBitVector &RHS) { | |||
559 | resize(std::max(size(), RHS.size())); | |||
560 | if (isSmall() && RHS.isSmall()) | |||
561 | setSmallBits(getSmallBits() | RHS.getSmallBits()); | |||
562 | else if (!isSmall() && !RHS.isSmall()) | |||
563 | getPointer()->operator|=(*RHS.getPointer()); | |||
564 | else { | |||
565 | for (size_t i = 0, e = RHS.size(); i != e; ++i) | |||
566 | (*this)[i] = test(i) || RHS.test(i); | |||
567 | } | |||
568 | return *this; | |||
569 | } | |||
570 | ||||
571 | SmallBitVector &operator^=(const SmallBitVector &RHS) { | |||
572 | resize(std::max(size(), RHS.size())); | |||
573 | if (isSmall() && RHS.isSmall()) | |||
574 | setSmallBits(getSmallBits() ^ RHS.getSmallBits()); | |||
575 | else if (!isSmall() && !RHS.isSmall()) | |||
576 | getPointer()->operator^=(*RHS.getPointer()); | |||
577 | else { | |||
578 | for (size_t i = 0, e = RHS.size(); i != e; ++i) | |||
579 | (*this)[i] = test(i) != RHS.test(i); | |||
580 | } | |||
581 | return *this; | |||
582 | } | |||
583 | ||||
584 | SmallBitVector &operator<<=(unsigned N) { | |||
585 | if (isSmall()) | |||
586 | setSmallBits(getSmallBits() << N); | |||
587 | else | |||
588 | getPointer()->operator<<=(N); | |||
589 | return *this; | |||
590 | } | |||
591 | ||||
592 | SmallBitVector &operator>>=(unsigned N) { | |||
593 | if (isSmall()) | |||
594 | setSmallBits(getSmallBits() >> N); | |||
595 | else | |||
596 | getPointer()->operator>>=(N); | |||
597 | return *this; | |||
598 | } | |||
599 | ||||
600 | // Assignment operator. | |||
601 | const SmallBitVector &operator=(const SmallBitVector &RHS) { | |||
602 | if (isSmall()) { | |||
603 | if (RHS.isSmall()) | |||
604 | X = RHS.X; | |||
605 | else | |||
606 | switchToLarge(new BitVector(*RHS.getPointer())); | |||
607 | } else { | |||
608 | if (!RHS.isSmall()) | |||
609 | *getPointer() = *RHS.getPointer(); | |||
610 | else { | |||
611 | delete getPointer(); | |||
612 | X = RHS.X; | |||
613 | } | |||
614 | } | |||
615 | return *this; | |||
616 | } | |||
617 | ||||
618 | const SmallBitVector &operator=(SmallBitVector &&RHS) { | |||
619 | if (this != &RHS) { | |||
620 | clear(); | |||
621 | swap(RHS); | |||
622 | } | |||
623 | return *this; | |||
624 | } | |||
625 | ||||
626 | void swap(SmallBitVector &RHS) { | |||
627 | std::swap(X, RHS.X); | |||
628 | } | |||
629 | ||||
630 | /// Add '1' bits from Mask to this vector. Don't resize. | |||
631 | /// This computes "*this |= Mask". | |||
632 | void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { | |||
633 | if (isSmall()) | |||
634 | applyMask<true, false>(Mask, MaskWords); | |||
635 | else | |||
636 | getPointer()->setBitsInMask(Mask, MaskWords); | |||
637 | } | |||
638 | ||||
639 | /// Clear any bits in this vector that are set in Mask. Don't resize. | |||
640 | /// This computes "*this &= ~Mask". | |||
641 | void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { | |||
642 | if (isSmall()) | |||
643 | applyMask<false, false>(Mask, MaskWords); | |||
644 | else | |||
645 | getPointer()->clearBitsInMask(Mask, MaskWords); | |||
646 | } | |||
647 | ||||
648 | /// Add a bit to this vector for every '0' bit in Mask. Don't resize. | |||
649 | /// This computes "*this |= ~Mask". | |||
650 | void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { | |||
651 | if (isSmall()) | |||
652 | applyMask<true, true>(Mask, MaskWords); | |||
653 | else | |||
654 | getPointer()->setBitsNotInMask(Mask, MaskWords); | |||
655 | } | |||
656 | ||||
657 | /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. | |||
658 | /// This computes "*this &= Mask". | |||
659 | void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { | |||
660 | if (isSmall()) | |||
661 | applyMask<false, true>(Mask, MaskWords); | |||
662 | else | |||
663 | getPointer()->clearBitsNotInMask(Mask, MaskWords); | |||
664 | } | |||
665 | ||||
666 | private: | |||
667 | template <bool AddBits, bool InvertMask> | |||
668 | void applyMask(const uint32_t *Mask, unsigned MaskWords) { | |||
669 | assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!")((MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!" ) ? static_cast<void> (0) : __assert_fail ("MaskWords <= sizeof(uintptr_t) && \"Mask is larger than base!\"" , "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h" , 669, __PRETTY_FUNCTION__)); | |||
670 | uintptr_t M = Mask[0]; | |||
671 | if (NumBaseBits == 64) | |||
672 | M |= uint64_t(Mask[1]) << 32; | |||
673 | if (InvertMask) | |||
674 | M = ~M; | |||
675 | if (AddBits) | |||
676 | setSmallBits(getSmallBits() | M); | |||
677 | else | |||
678 | setSmallBits(getSmallBits() & ~M); | |||
679 | } | |||
680 | }; | |||
681 | ||||
682 | inline SmallBitVector | |||
683 | operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { | |||
684 | SmallBitVector Result(LHS); | |||
685 | Result &= RHS; | |||
686 | return Result; | |||
687 | } | |||
688 | ||||
689 | inline SmallBitVector | |||
690 | operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { | |||
691 | SmallBitVector Result(LHS); | |||
692 | Result |= RHS; | |||
693 | return Result; | |||
694 | } | |||
695 | ||||
696 | inline SmallBitVector | |||
697 | operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { | |||
698 | SmallBitVector Result(LHS); | |||
699 | Result ^= RHS; | |||
700 | return Result; | |||
701 | } | |||
702 | ||||
703 | } // end namespace llvm | |||
704 | ||||
705 | namespace std { | |||
706 | ||||
707 | /// Implement std::swap in terms of BitVector swap. | |||
708 | inline void | |||
709 | swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { | |||
710 | LHS.swap(RHS); | |||
711 | } | |||
712 | ||||
713 | } // end namespace std | |||
714 | ||||
715 | #endif // LLVM_ADT_SMALLBITVECTOR_H |