/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h

Bug Summary

File:	include/llvm/ADT/SmallBitVector.h
Warning:	line 121, column 3 Potential memory leak

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name CoverageMapping.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -analyzer-config-compatibility-mode=true -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-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/lib/ProfileData/Coverage -I /build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn350071/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.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-8~svn350071/build-llvm/lib/ProfileData/Coverage -fdebug-prefix-map=/build/llvm-toolchain-snapshot-8~svn350071=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-12-27-042839-1215-1 -x c++ /build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp

→

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//===----------------------------------------------------------------------===//

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>

43using namespace llvm;
44using namespace coverage;

46#define DEBUG_TYPE"coverage-mapping" "coverage-mapping"

48Counter CounterExpressionBuilder::get(const CounterExpression &E) {
auto It = ExpressionIndices.find(E);
if (It != ExpressionIndices.end())
  return Counter::getExpression(It->second);
unsigned I = Expressions.size();
Expressions.push_back(E);
ExpressionIndices[E] = I;
return Counter::getExpression(I);
56}

58void CounterExpressionBuilder::extractTerms(Counter C, int Factor,
                                          SmallVectorImpl<Term> &Terms) {
switch (C.getKind()) {
case Counter::Zero:
  break;
case Counter::CounterValueReference:
  Terms.emplace_back(C.getCounterID(), Factor);
  break;
case Counter::Expression:
  const auto &E = Expressions[C.getExpressionID()];
  extractTerms(E.LHS, Factor, Terms);
  extractTerms(
      E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms);
  break;
}
73}

75Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
// Gather constant terms.
SmallVector<Term, 32> Terms;
extractTerms(ExpressionTree, +1, Terms);

// If there are no terms, this is just a zero. The algorithm below assumes at
// least one term.
if (Terms.size() == 0)
  return Counter::getZero();

// Group the terms by counter ID.
llvm::sort(Terms, [](const Term &LHS, const Term &RHS) {
  return LHS.CounterID < RHS.CounterID;
});

// Combine terms by counter ID to eliminate counters that sum to zero.
auto Prev = Terms.begin();
for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
  if (I->CounterID == Prev->CounterID) {
    Prev->Factor += I->Factor;
    continue;
  }
  ++Prev;
  *Prev = *I;
}
Terms.erase(++Prev, Terms.end());

Counter C;
// Create additions. We do this before subtractions to avoid constructs like
// ((0 - X) + Y), as opposed to (Y - X).
for (auto T : Terms) {
  if (T.Factor <= 0)
    continue;
  for (int I = 0; I < T.Factor; ++I)
    if (C.isZero())
      C = Counter::getCounter(T.CounterID);
    else
      C = get(CounterExpression(CounterExpression::Add, C,
                                Counter::getCounter(T.CounterID)));
}

// Create subtractions.
for (auto T : Terms) {
  if (T.Factor >= 0)
    continue;
  for (int I = 0; I < -T.Factor; ++I)
    C = get(CounterExpression(CounterExpression::Subtract, C,
                              Counter::getCounter(T.CounterID)));
}
return C;
125}

127Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) {
return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS)));
129}

131Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) {
return simplify(
    get(CounterExpression(CounterExpression::Subtract, LHS, RHS)));
134}

136void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const {
switch (C.getKind()) {
case Counter::Zero:
  OS << '0';
  return;
case Counter::CounterValueReference:
  OS << '#' << C.getCounterID();
  break;
case Counter::Expression: {
  if (C.getExpressionID() >= Expressions.size())
    return;
  const auto &E = Expressions[C.getExpressionID()];
  OS << '(';
  dump(E.LHS, OS);
  OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
  dump(E.RHS, OS);
  OS << ')';
  break;
}
}
if (CounterValues.empty())
  return;
Expected<int64_t> Value = evaluate(C);
if (auto E = Value.takeError()) {
  consumeError(std::move(E));
  return;
}
OS << '[' << *Value << ']';
164}

166Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
switch (C.getKind()) {
case Counter::Zero:
  return 0;
case Counter::CounterValueReference:
  if (C.getCounterID() >= CounterValues.size())
    return errorCodeToError(errc::argument_out_of_domain);
  return CounterValues[C.getCounterID()];
case Counter::Expression: {
  if (C.getExpressionID() >= Expressions.size())
    return errorCodeToError(errc::argument_out_of_domain);
  const auto &E = Expressions[C.getExpressionID()];
  Expected<int64_t> LHS = evaluate(E.LHS);
  if (!LHS)
    return LHS;
  Expected<int64_t> RHS = evaluate(E.RHS);
  if (!RHS)
    return RHS;
  return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
}
}
llvm_unreachable("Unhandled CounterKind")::llvm::llvm_unreachable_internal("Unhandled CounterKind", "/build/llvm-toolchain-snapshot-8~svn350071/lib/ProfileData/Coverage/CoverageMapping.cpp"
, 187);
188}

190void FunctionRecordIterator::skipOtherFiles() {
while (Current != Records.end() && !Filename.empty() &&
       Filename != Current->Filenames[0])
  ++Current;
if (Current == Records.end())
  *this = FunctionRecordIterator();
196}

198Error CoverageMapping::loadFunctionRecord(
  const CoverageMappingRecord &Record,
  IndexedInstrProfReader &ProfileReader) {
StringRef OrigFuncName = Record.FunctionName;
if (OrigFuncName.empty())
  return make_error<CoverageMapError>(coveragemap_error::malformed);

if (Record.Filenames.empty())
  OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);
else
  OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);

CounterMappingContext Ctx(Record.Expressions);

std::vector<uint64_t> Counts;
if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName,
                                              Record.FunctionHash, Counts)) {
  instrprof_error IPE = InstrProfError::take(std::move(E));
  if (IPE == instrprof_error::hash_mismatch) {
    FuncHashMismatches.emplace_back(Record.FunctionName, Record.FunctionHash);
    return Error::success();
  } else if (IPE != instrprof_error::unknown_function)
    return make_error<InstrProfError>(IPE);
  Counts.assign(Record.MappingRegions.size(), 0);
}
Ctx.setCounts(Counts);

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__));

// This coverage record is a zero region for a function that's unused in
// some TU, but used in a different TU. Ignore it. The coverage maps from the
// the other TU will either be loaded (providing full region counts) or they
// won't (in which case we don't unintuitively report functions as uncovered
// when they have non-zero counts in the profile).
if (Record.MappingRegions.size() == 1 &&
    Record.MappingRegions[0].Count.isZero() && Counts[0] > 0)
  return Error::success();

FunctionRecord Function(OrigFuncName, Record.Filenames);
for (const auto &Region : Record.MappingRegions) {
  Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
  if (auto E = ExecutionCount.takeError()) {
    consumeError(std::move(E));
    return Error::success();
  }
  Function.pushRegion(Region, *ExecutionCount);
}

// Don't create records for (filenames, function) pairs we've already seen.
auto FilenamesHash = hash_combine_range(Record.Filenames.begin(),
                                        Record.Filenames.end());
if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second)
  return Error::success();

Functions.push_back(std::move(Function));
return Error::success();
254}

256Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(
  ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
  IndexedInstrProfReader &ProfileReader) {
auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());

for (const auto &CoverageReader : CoverageReaders) {
  for (auto RecordOrErr : *CoverageReader) {
    if (Error E = RecordOrErr.takeError())
      return std::move(E);
    const auto &Record = *RecordOrErr;
    if (Error E = Coverage->loadFunctionRecord(Record, ProfileReader))
      return std::move(E);
  }
}

return std::move(Coverage);
272}

274Expected<std::unique_ptr<CoverageMapping>>
275CoverageMapping::load(ArrayRef<StringRef> ObjectFilenames,
                    StringRef ProfileFilename, ArrayRef<StringRef> Arches) {
auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename);
if (Error E = ProfileReaderOrErr.takeError())
  return std::move(E);
auto ProfileReader = std::move(ProfileReaderOrErr.get());

SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers;
SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers;
for (const auto &File : llvm::enumerate(ObjectFilenames)) {
  auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(File.value());
  if (std::error_code EC = CovMappingBufOrErr.getError())
    return errorCodeToError(EC);
  StringRef Arch = Arches.empty() ? StringRef() : Arches[File.index()];
  auto CoverageReaderOrErr =
      BinaryCoverageReader::create(CovMappingBufOrErr.get(), Arch);
  if (Error E = CoverageReaderOrErr.takeError())
    return std::move(E);
  Readers.push_back(std::move(CoverageReaderOrErr.get()));
  Buffers.push_back(std::move(CovMappingBufOrErr.get()));
}
return load(Readers, *ProfileReader);
297}

299namespace {

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.
305class FunctionInstantiationSetCollector {
using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>;
MapT InstantiatedFunctions;

309public:
void insert(const FunctionRecord &Function, unsigned FileID) {
  auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
  while (I != E && I->FileID != FileID)
    ++I;
  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__));
  auto &Functions = InstantiatedFunctions[I->startLoc()];
  Functions.push_back(&Function);
}

MapT::iterator begin() { return InstantiatedFunctions.begin(); }
MapT::iterator end() { return InstantiatedFunctions.end(); }
321};

323class SegmentBuilder {
std::vector<CoverageSegment> &Segments;
SmallVector<const CountedRegion *, 8> ActiveRegions;

SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}

/// Emit a segment with the count from \p Region starting at \p StartLoc.
//
/// \p IsRegionEntry: The segment is at the start of a new non-gap region.
/// \p EmitSkippedRegion: The segment must be emitted as a skipped region.
void startSegment(const CountedRegion &Region, LineColPair StartLoc,
                  bool IsRegionEntry, bool EmitSkippedRegion = false) {
  bool HasCount = !EmitSkippedRegion &&
                  (Region.Kind != CounterMappingRegion::SkippedRegion);

  // If the new segment wouldn't affect coverage rendering, skip it.
  if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) {
    const auto &Last = Segments.back();
    if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount &&
        !Last.IsRegionEntry)
      return;
  }

  if (HasCount)
    Segments.emplace_back(StartLoc.first, StartLoc.second,
                          Region.ExecutionCount, IsRegionEntry,
                          Region.Kind == CounterMappingRegion::GapRegion);
  else
    Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry);

  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
)
    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
)
    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
)
           << " (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
)
           << (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
)
           << (!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
)
           << (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
)
  })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
);
}

/// Emit segments for active regions which end before \p Loc.
///
/// \p Loc: The start location of the next region. If None, all active
/// regions are completed.
/// \p FirstCompletedRegion: Index of the first completed region.
void completeRegionsUntil(Optional<LineColPair> Loc,
                          unsigned FirstCompletedRegion) {
  // Sort the completed regions by end location. This makes it simple to
  // emit closing segments in sorted order.
  auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;
  std::stable_sort(CompletedRegionsIt, ActiveRegions.end(),
                    [](const CountedRegion *L, const CountedRegion *R) {
                      return L->endLoc() < R->endLoc();
                    });

  // Emit segments for all completed regions.
  for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;
       ++I) {
    const auto *CompletedRegion = ActiveRegions[I];
    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__))
           "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__));

    const auto *PrevCompletedRegion = ActiveRegions[I - 1];
    auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();

    // Don't emit any more segments if they start where the new region begins.
    if (Loc && CompletedSegmentLoc == *Loc)
      break;

    // Don't emit a segment if the next completed region ends at the same
    // location as this one.
    if (CompletedSegmentLoc == CompletedRegion->endLoc())
      continue;

    // Use the count from the last completed region which ends at this loc.
    for (unsigned J = I + 1; J < E; ++J)
      if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc())
        CompletedRegion = ActiveRegions[J];

    startSegment(*CompletedRegion, CompletedSegmentLoc, false);
  }

  auto Last = ActiveRegions.back();
  if (FirstCompletedRegion && Last->endLoc() != *Loc) {
    // If there's a gap after the end of the last completed region and the
    // start of the new region, use the last active region to fill the gap.
    startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(),
                 false);
  } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) {
    // Emit a skipped segment if there are no more active regions. This
    // ensures that gaps between functions are marked correctly.
    startSegment(*Last, Last->endLoc(), false, true);
  }

  // Pop the completed regions.
  ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end());
}

void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
  for (const auto &CR : enumerate(Regions)) {
    auto CurStartLoc = CR.value().startLoc();

    // Active regions which end before the current region need to be popped.
    auto CompletedRegions =
        std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(),
                              [&](const CountedRegion *Region) {
                                return !(Region->endLoc() <= CurStartLoc);
                              });
    if (CompletedRegions != ActiveRegions.end()) {
      unsigned FirstCompletedRegion =
          std::distance(ActiveRegions.begin(), CompletedRegions);
      completeRegionsUntil(CurStartLoc, FirstCompletedRegion);
    }

    bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion;

    // Try to emit a segment for the current region.
    if (CurStartLoc == CR.value().endLoc()) {
      // Avoid making zero-length regions active. If it's the last region,
      // emit a skipped segment. Otherwise use its predecessor's count.
      const bool Skipped = (CR.index() + 1) == Regions.size();
      startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(),
                   CurStartLoc, !GapRegion, Skipped);
      continue;
    }
    if (CR.index() + 1 == Regions.size() ||
        CurStartLoc != Regions[CR.index() + 1].startLoc()) {
      // Emit a segment if the next region doesn't start at the same location
      // as this one.
      startSegment(CR.value(), CurStartLoc, !GapRegion);
    }

    // This region is active (i.e not completed).
    ActiveRegions.push_back(&CR.value());
  }

  // Complete any remaining active regions.
  if (!ActiveRegions.empty())
    completeRegionsUntil(None, 0);
}

/// Sort a nested sequence of regions from a single file.
static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
  llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) {
    if (LHS.startLoc() != RHS.startLoc())
      return LHS.startLoc() < RHS.startLoc();
    if (LHS.endLoc() != RHS.endLoc())
      // When LHS completely contains RHS, we sort LHS first.
      return RHS.endLoc() < LHS.endLoc();
    // If LHS and RHS cover the same area, we need to sort them according
    // to their kinds so that the most suitable region will become "active"
    // in combineRegions(). Because we accumulate counter values only from
    // regions of the same kind as the first region of the area, prefer
    // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.
    static_assert(CounterMappingRegion::CodeRegion <
                          CounterMappingRegion::ExpansionRegion &&
                      CounterMappingRegion::ExpansionRegion <
                          CounterMappingRegion::SkippedRegion,
                  "Unexpected order of region kind values");
    return LHS.Kind < RHS.Kind;
  });
}

/// Combine counts of regions which cover the same area.
static ArrayRef<CountedRegion>
combineRegions(MutableArrayRef<CountedRegion> Regions) {
  if (Regions.empty())
    return Regions;
  auto Active = Regions.begin();
  auto End = Regions.end();
  for (auto I = Regions.begin() + 1; I != End; ++I) {
    if (Active->startLoc() != I->startLoc() ||
        Active->endLoc() != I->endLoc()) {
      // Shift to the next region.
      ++Active;
      if (Active != I)
        *Active = *I;
      continue;
    }
    // Merge duplicate region.
    // If CodeRegions and ExpansionRegions cover the same area, it's probably
    // a macro which is fully expanded to another macro. In that case, we need
    // to accumulate counts only from CodeRegions, or else the area will be
    // counted twice.
    // On the other hand, a macro may have a nested macro in its body. If the
    // outer macro is used several times, the ExpansionRegion for the nested
    // macro will also be added several times. These ExpansionRegions cover
    // the same source locations and have to be combined to reach the correct
    // value for that area.
    // We add counts of the regions of the same kind as the active region
    // to handle the both situations.
    if (I->Kind == Active->Kind)
      Active->ExecutionCount += I->ExecutionCount;
  }
  return Regions.drop_back(std::distance(++Active, End));
}

520public:
/// Build a sorted list of CoverageSegments from a list of Regions.
static std::vector<CoverageSegment>
buildSegments(MutableArrayRef<CountedRegion> Regions) {
  std::vector<CoverageSegment> Segments;
  SegmentBuilder Builder(Segments);

  sortNestedRegions(Regions);
  ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);

  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)
    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)
    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)
      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)
             << 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)
             << " (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)
  })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);

  Builder.buildSegmentsImpl(CombinedRegions);

540#ifndef NDEBUG
  for (unsigned I = 1, E = Segments.size(); I < E; ++I) {
    const auto &L = Segments[I - 1];
    const auto &R = Segments[I];
    if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {
      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)
                        << " 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);
      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__));
    }
  }
550#endif

  return Segments;
}
554};

556} // end anonymous namespace

558std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
std::vector<StringRef> Filenames;
for (const auto &Function : getCoveredFunctions())
  Filenames.insert(Filenames.end(), Function.Filenames.begin(),
                   Function.Filenames.end());
llvm::sort(Filenames);
auto Last = std::unique(Filenames.begin(), Filenames.end());
Filenames.erase(Last, Filenames.end());
return Filenames;
567}

569static SmallBitVector gatherFileIDs(StringRef SourceFile,
                                  const FunctionRecord &Function) {
SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
2
←
Calling constructor for 'SmallBitVector'→
6
←
Returning from constructor for 'SmallBitVector'→
for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
7
←
Assuming 'I' is < 'E'→
8
←
Loop condition is true.  Entering loop body→
  if (SourceFile == Function.Filenames[I])
9
←
Assuming the condition is true→
10
←
Taking true branch→
    FilenameEquivalence[I] = true;
11
←
Calling 'reference::operator='→
return FilenameEquivalence;
576}

578/// Return the ID of the file where the definition of the function is located.
579static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) {
SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
for (const auto &CR : Function.CountedRegions)
  if (CR.Kind == CounterMappingRegion::ExpansionRegion)
    IsNotExpandedFile[CR.ExpandedFileID] = false;
int I = IsNotExpandedFile.find_first();
if (I == -1)
  return None;
return I;
588}

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.
592static Optional<unsigned> findMainViewFileID(StringRef SourceFile,
                                           const FunctionRecord &Function) {
Optional<unsigned> I = findMainViewFileID(Function);
if (I && SourceFile == Function.Filenames[*I])
  return I;
return None;
598}

600static bool isExpansion(const CountedRegion &R, unsigned FileID) {
return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
602}

604CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const {
CoverageData FileCoverage(Filename);
std::vector<CountedRegion> Regions;

for (const auto &Function : Functions) {
  auto MainFileID = findMainViewFileID(Filename, Function);
  auto FileIDs = gatherFileIDs(Filename, Function);
1
Calling 'gatherFileIDs'→
  for (const auto &CR : Function.CountedRegions)
    if (FileIDs.test(CR.FileID)) {
      Regions.push_back(CR);
      if (MainFileID && isExpansion(CR, *MainFileID))
        FileCoverage.Expansions.emplace_back(CR, Function);
    }
}

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);
FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);

return FileCoverage;
623}

625std::vector<InstantiationGroup>
626CoverageMapping::getInstantiationGroups(StringRef Filename) const {
FunctionInstantiationSetCollector InstantiationSetCollector;
for (const auto &Function : Functions) {
  auto MainFileID = findMainViewFileID(Filename, Function);
  if (!MainFileID)
    continue;
  InstantiationSetCollector.insert(Function, *MainFileID);
}

std::vector<InstantiationGroup> Result;
for (auto &InstantiationSet : InstantiationSetCollector) {
  InstantiationGroup IG{InstantiationSet.first.first,
                        InstantiationSet.first.second,
                        std::move(InstantiationSet.second)};
  Result.emplace_back(std::move(IG));
}
return Result;
643}

645CoverageData
646CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const {
auto MainFileID = findMainViewFileID(Function);
if (!MainFileID)
  return CoverageData();

CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
std::vector<CountedRegion> Regions;
for (const auto &CR : Function.CountedRegions)
  if (CR.FileID == *MainFileID) {
    Regions.push_back(CR);
    if (isExpansion(CR, *MainFileID))
      FunctionCoverage.Expansions.emplace_back(CR, Function);
  }

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)
                  << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { dbgs() << "Emitting segments for function: "
 << Function.Name << "\n"; } } while (false);
FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);

return FunctionCoverage;
665}

667CoverageData CoverageMapping::getCoverageForExpansion(
  const ExpansionRecord &Expansion) const {
CoverageData ExpansionCoverage(
    Expansion.Function.Filenames[Expansion.FileID]);
std::vector<CountedRegion> Regions;
for (const auto &CR : Expansion.Function.CountedRegions)
  if (CR.FileID == Expansion.FileID) {
    Regions.push_back(CR);
    if (isExpansion(CR, Expansion.FileID))
      ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
  }

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)
                  << Expansion.FileID << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coverage-mapping")) { dbgs() << "Emitting segments for expansion of file "
 << Expansion.FileID << "\n"; } } while (false);
ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);

return ExpansionCoverage;
684}

686LineCoverageStats::LineCoverageStats(
  ArrayRef<const CoverageSegment *> LineSegments,
  const CoverageSegment *WrappedSegment, unsigned Line)
  : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line),
    LineSegments(LineSegments), WrappedSegment(WrappedSegment) {
// Find the minimum number of regions which start in this line.
unsigned MinRegionCount = 0;
auto isStartOfRegion = [](const CoverageSegment *S) {
  return !S->IsGapRegion && S->HasCount && S->IsRegionEntry;
};
for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I)
  if (isStartOfRegion(LineSegments[I]))
    ++MinRegionCount;

bool StartOfSkippedRegion = !LineSegments.empty() &&
                            !LineSegments.front()->HasCount &&
                            LineSegments.front()->IsRegionEntry;

HasMultipleRegions = MinRegionCount > 1;
Mapped =
    !StartOfSkippedRegion &&
    ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0));

if (!Mapped)
  return;

// Pick the max count from the non-gap, region entry segments and the
// wrapped count.
if (WrappedSegment)
  ExecutionCount = WrappedSegment->Count;
if (!MinRegionCount)
  return;
for (const auto *LS : LineSegments)
  if (isStartOfRegion(LS))
    ExecutionCount = std::max(ExecutionCount, LS->Count);
721}

723LineCoverageIterator &LineCoverageIterator::operator++() {
if (Next == CD.end()) {
  Stats = LineCoverageStats();
  Ended = true;
  return *this;
}
if (Segments.size())
  WrappedSegment = Segments.back();
Segments.clear();
while (Next != CD.end() && Next->Line == Line)
  Segments.push_back(&*Next++);
Stats = LineCoverageStats(Segments, WrappedSegment, Line);
++Line;
return *this;
737}

739static std::string getCoverageMapErrString(coveragemap_error Err) {
switch (Err) {
case coveragemap_error::success:
  return "Success";
case coveragemap_error::eof:
  return "End of File";
case coveragemap_error::no_data_found:
  return "No coverage data found";
case coveragemap_error::unsupported_version:
  return "Unsupported coverage format version";
case coveragemap_error::truncated:
  return "Truncated coverage data";
case coveragemap_error::malformed:
  return "Malformed coverage data";
}
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}

757namespace {

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.
762class CoverageMappingErrorCategoryType : public std::error_category {
const char *name() const noexcept override { return "llvm.coveragemap"; }
std::string message(int IE) const override {
  return getCoverageMapErrString(static_cast<coveragemap_error>(IE));
}
767};

769} // end anonymous namespace

771std::string CoverageMapError::message() const {
return getCoverageMapErrString(Err);
773}

775static ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory;

777const std::error_category &llvm::coverage::coveragemap_category() {
return *ErrorCategory;
779}

781char CoverageMapError::ID = 0;

←

/build/llvm-toolchain-snapshot-8~svn350071/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//===----------------------------------------------------------------------===//

14#ifndef LLVM_ADT_SMALLBITVECTOR_H
15#define LLVM_ADT_SMALLBITVECTOR_H

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>

28namespace llvm {

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 {
// TODO: In "large" mode, a pointer to a BitVector is used, leading to an
// unnecessary level of indirection. It would be more efficient to use a
// pointer to memory containing size, allocation size, and the array of bits.
uintptr_t X = 1;

enum {
  // The number of bits in this class.
  NumBaseBits = sizeof(uintptr_t) * CHAR_BIT8,

  // One bit is used to discriminate between small and large mode. The
  // remaining bits are used for the small-mode representation.
  SmallNumRawBits = NumBaseBits - 1,

  // A few more bits are used to store the size of the bit set in small mode.
  // Theoretically this is a ceil-log2. These bits are encoded in the most
  // significant bits of the raw bits.
  SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
                      NumBaseBits == 64 ? 6 :
                      SmallNumRawBits),

  // The remaining bits are used to store the actual set in small mode.
  SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
};

static_assert(NumBaseBits == 64 || NumBaseBits == 32,
              "Unsupported word size");

63public:
using size_type = unsigned;

// Encapsulation of a single bit.
class reference {
  SmallBitVector &TheVector;
  unsigned BitPos;

public:
  reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}

  reference(const reference&) = default;

  reference& operator=(reference t) {
    *this = bool(t);
    return *this;
  }

  reference& operator=(bool t) {
    if (t)
12
←
Taking true branch→
      TheVector.set(BitPos);
13
←
Calling 'SmallBitVector::set'→
    else
      TheVector.reset(BitPos);
    return *this;
  }

  operator bool() const {
    return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
  }
};

94private:
BitVector *getPointer() const {
  assert(!isSmall())((!isSmall()) ? static_cast<void> (0) : __assert_fail (
"!isSmall()", "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h"
, 96, __PRETTY_FUNCTION__));
  return reinterpret_cast<BitVector *>(X);
}

void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
  X = 1;
  setSmallSize(NewSize);
  setSmallBits(NewSmallBits);
}

void switchToLarge(BitVector *BV) {
  X = reinterpret_cast<uintptr_t>(BV);
  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__));
}

// Return all the bits used for the "small" representation; this includes
// bits for the size as well as the element bits.
uintptr_t getSmallRawBits() const {
  assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()"
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h"
, 114, __PRETTY_FUNCTION__));
  return X >> 1;
}

void setSmallRawBits(uintptr_t NewRawBits) {
  assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()"
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h"
, 119, __PRETTY_FUNCTION__));
18
←
'?' condition is true→
  X = (NewRawBits << 1) | uintptr_t(1);
}
19
←
Potential memory leak

// Return the size.
size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }

void setSmallSize(size_t Size) {
  setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
}

// Return the element bits.
uintptr_t getSmallBits() const {
  return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
}

void setSmallBits(uintptr_t NewBits) {
  setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
17
←
Calling 'SmallBitVector::setSmallRawBits'→
                  (getSmallSize() << SmallNumDataBits));
}

140public:
/// Creates an empty bitvector.
SmallBitVector() = default;

/// Creates a bitvector of specified number of bits. All bits are initialized
/// to the specified value.
explicit SmallBitVector(unsigned s, bool t = false) {
  if (s <= SmallNumDataBits)
3
←
Assuming 's' is > SmallNumDataBits→
4
←
Taking false branch→
    switchToSmall(t ? ~uintptr_t(0) : 0, s);
  else
    switchToLarge(new BitVector(s, t));
5
←
Memory is allocated→
}

/// SmallBitVector copy ctor.
SmallBitVector(const SmallBitVector &RHS) {
  if (RHS.isSmall())
    X = RHS.X;
  else
    switchToLarge(new BitVector(*RHS.getPointer()));
}

SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
  RHS.X = 1;
}

~SmallBitVector() {
  if (!isSmall())
    delete getPointer();
}

using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
using set_iterator = const_set_bits_iterator;

const_set_bits_iterator set_bits_begin() const {
  return const_set_bits_iterator(*this);
}

const_set_bits_iterator set_bits_end() const {
  return const_set_bits_iterator(*this, -1);
}

iterator_range<const_set_bits_iterator> set_bits() const {
  return make_range(set_bits_begin(), set_bits_end());
}

bool isSmall() const { return X & uintptr_t(1); }

/// Tests whether there are no bits in this bitvector.
bool empty() const {
  return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
}

/// Returns the number of bits in this bitvector.
size_t size() const {
  return isSmall() ? getSmallSize() : getPointer()->size();
}

/// Returns the number of bits which are set.
size_type count() const {
  if (isSmall()) {
    uintptr_t Bits = getSmallBits();
    return countPopulation(Bits);
  }
  return getPointer()->count();
}

/// Returns true if any bit is set.
bool any() const {
  if (isSmall())
    return getSmallBits() != 0;
  return getPointer()->any();
}

/// Returns true if all bits are set.
bool all() const {
  if (isSmall())
    return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
  return getPointer()->all();
}

/// Returns true if none of the bits are set.
bool none() const {
  if (isSmall())
    return getSmallBits() == 0;
  return getPointer()->none();
}

/// Returns the index of the first set bit, -1 if none of the bits are set.
int find_first() const {
  if (isSmall()) {
    uintptr_t Bits = getSmallBits();
    if (Bits == 0)
      return -1;
    return countTrailingZeros(Bits);
  }
  return getPointer()->find_first();
}

int find_last() const {
  if (isSmall()) {
    uintptr_t Bits = getSmallBits();
    if (Bits == 0)
      return -1;
    return NumBaseBits - countLeadingZeros(Bits) - 1;
  }
  return getPointer()->find_last();
}

/// Returns the index of the first unset bit, -1 if all of the bits are set.
int find_first_unset() const {
  if (isSmall()) {
    if (count() == getSmallSize())
      return -1;

    uintptr_t Bits = getSmallBits();
    return countTrailingOnes(Bits);
  }
  return getPointer()->find_first_unset();
}

int find_last_unset() const {
  if (isSmall()) {
    if (count() == getSmallSize())
      return -1;

    uintptr_t Bits = getSmallBits();
    // Set unused bits.
    Bits |= ~uintptr_t(0) << getSmallSize();
    return NumBaseBits - countLeadingOnes(Bits) - 1;
  }
  return getPointer()->find_last_unset();
}

/// Returns the index of the next set bit following the "Prev" bit.
/// Returns -1 if the next set bit is not found.
int find_next(unsigned Prev) const {
  if (isSmall()) {
    uintptr_t Bits = getSmallBits();
    // Mask off previous bits.
    Bits &= ~uintptr_t(0) << (Prev + 1);
    if (Bits == 0 || Prev + 1 >= getSmallSize())
      return -1;
    return countTrailingZeros(Bits);
  }
  return getPointer()->find_next(Prev);
}

/// Returns the index of the next unset bit following the "Prev" bit.
/// Returns -1 if the next unset bit is not found.
int find_next_unset(unsigned Prev) const {
  if (isSmall()) {
    ++Prev;
    uintptr_t Bits = getSmallBits();
    // Mask in previous bits.
    uintptr_t Mask = (1 << Prev) - 1;
    Bits |= Mask;

    if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
      return -1;
    return countTrailingOnes(Bits);
  }
  return getPointer()->find_next_unset(Prev);
}

/// find_prev - Returns the index of the first set bit that precedes the
/// the bit at \p PriorTo.  Returns -1 if all previous bits are unset.
int find_prev(unsigned PriorTo) const {
  if (isSmall()) {
    if (PriorTo == 0)
      return -1;

    --PriorTo;
    uintptr_t Bits = getSmallBits();
    Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
    if (Bits == 0)
      return -1;

    return NumBaseBits - countLeadingZeros(Bits) - 1;
  }
  return getPointer()->find_prev(PriorTo);
}

/// Clear all bits.
void clear() {
  if (!isSmall())
    delete getPointer();
  switchToSmall(0, 0);
}

/// Grow or shrink the bitvector.
void resize(unsigned N, bool t = false) {
  if (!isSmall()) {
    getPointer()->resize(N, t);
  } else if (SmallNumDataBits >= N) {
    uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;
    setSmallSize(N);
    setSmallBits(NewBits | getSmallBits());
  } else {
    BitVector *BV = new BitVector(N, t);
    uintptr_t OldBits = getSmallBits();
    for (size_t i = 0, e = getSmallSize(); i != e; ++i)
      (*BV)[i] = (OldBits >> i) & 1;
    switchToLarge(BV);
  }
}

void reserve(unsigned N) {
  if (isSmall()) {
    if (N > SmallNumDataBits) {
      uintptr_t OldBits = getSmallRawBits();
      size_t SmallSize = getSmallSize();
      BitVector *BV = new BitVector(SmallSize);
      for (size_t i = 0; i < SmallSize; ++i)
        if ((OldBits >> i) & 1)
          BV->set(i);
      BV->reserve(N);
      switchToLarge(BV);
    }
  } else {
    getPointer()->reserve(N);
  }
}

// Set, reset, flip
SmallBitVector &set() {
  if (isSmall())
    setSmallBits(~uintptr_t(0));
  else
    getPointer()->set();
  return *this;
}

SmallBitVector &set(unsigned Idx) {
  if (isSmall()) {
14
←
Taking true branch→
    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__))
15
←
'?' condition is true→
                      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__))
           "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__));
    setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
16
←
Calling 'SmallBitVector::setSmallBits'→
  }
  else
    getPointer()->set(Idx);
  return *this;
}

/// Efficiently set a range of bits in [I, E)
SmallBitVector &set(unsigned I, unsigned E) {
  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__));
  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__));
  if (I == E) return *this;
  if (isSmall()) {
    uintptr_t EMask = ((uintptr_t)1) << E;
    uintptr_t IMask = ((uintptr_t)1) << I;
    uintptr_t Mask = EMask - IMask;
    setSmallBits(getSmallBits() | Mask);
  } else
    getPointer()->set(I, E);
  return *this;
}

SmallBitVector &reset() {
  if (isSmall())
    setSmallBits(0);
  else
    getPointer()->reset();
  return *this;
}

SmallBitVector &reset(unsigned Idx) {
  if (isSmall())
    setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
  else
    getPointer()->reset(Idx);
  return *this;
}

/// Efficiently reset a range of bits in [I, E)
SmallBitVector &reset(unsigned I, unsigned E) {
  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__));
  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__));
  if (I == E) return *this;
  if (isSmall()) {
    uintptr_t EMask = ((uintptr_t)1) << E;
    uintptr_t IMask = ((uintptr_t)1) << I;
    uintptr_t Mask = EMask - IMask;
    setSmallBits(getSmallBits() & ~Mask);
  } else
    getPointer()->reset(I, E);
  return *this;
}

SmallBitVector &flip() {
  if (isSmall())
    setSmallBits(~getSmallBits());
  else
    getPointer()->flip();
  return *this;
}

SmallBitVector &flip(unsigned Idx) {
  if (isSmall())
    setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
  else
    getPointer()->flip(Idx);
  return *this;
}

// No argument flip.
SmallBitVector operator~() const {
  return SmallBitVector(*this).flip();
}

// Indexing.
reference operator[](unsigned Idx) {
  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__));
  return reference(*this, Idx);
}

bool operator[](unsigned Idx) const {
  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__));
  if (isSmall())
    return ((getSmallBits() >> Idx) & 1) != 0;
  return getPointer()->operator[](Idx);
}

bool test(unsigned Idx) const {
  return (*this)[Idx];
}

// Push single bit to end of vector.
void push_back(bool Val) {
  resize(size() + 1, Val);
}

/// Test if any common bits are set.
bool anyCommon(const SmallBitVector &RHS) const {
  if (isSmall() && RHS.isSmall())
    return (getSmallBits() & RHS.getSmallBits()) != 0;
  if (!isSmall() && !RHS.isSmall())
    return getPointer()->anyCommon(*RHS.getPointer());

  for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
    if (test(i) && RHS.test(i))
      return true;
  return false;
}

// Comparison operators.
bool operator==(const SmallBitVector &RHS) const {
  if (size() != RHS.size())
    return false;
  if (isSmall() && RHS.isSmall())
    return getSmallBits() == RHS.getSmallBits();
  else if (!isSmall() && !RHS.isSmall())
    return *getPointer() == *RHS.getPointer();
  else {
    for (size_t i = 0, e = size(); i != e; ++i) {
      if ((*this)[i] != RHS[i])
        return false;
    }
    return true;
  }
}

bool operator!=(const SmallBitVector &RHS) const {
  return !(*this == RHS);
}

// Intersection, union, disjoint union.
// FIXME BitVector::operator&= does not resize the LHS but this does
SmallBitVector &operator&=(const SmallBitVector &RHS) {
  resize(std::max(size(), RHS.size()));
  if (isSmall() && RHS.isSmall())
    setSmallBits(getSmallBits() & RHS.getSmallBits());
  else if (!isSmall() && !RHS.isSmall())
    getPointer()->operator&=(*RHS.getPointer());
  else {
    size_t i, e;
    for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
      (*this)[i] = test(i) && RHS.test(i);
    for (e = size(); i != e; ++i)
      reset(i);
  }
  return *this;
}

/// Reset bits that are set in RHS. Same as *this &= ~RHS.
SmallBitVector &reset(const SmallBitVector &RHS) {
  if (isSmall() && RHS.isSmall())
    setSmallBits(getSmallBits() & ~RHS.getSmallBits());
  else if (!isSmall() && !RHS.isSmall())
    getPointer()->reset(*RHS.getPointer());
  else
    for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
      if (RHS.test(i))
        reset(i);

  return *this;
}

/// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
bool test(const SmallBitVector &RHS) const {
  if (isSmall() && RHS.isSmall())
    return (getSmallBits() & ~RHS.getSmallBits()) != 0;
  if (!isSmall() && !RHS.isSmall())
    return getPointer()->test(*RHS.getPointer());

  unsigned i, e;
  for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
    if (test(i) && !RHS.test(i))
      return true;

  for (e = size(); i != e; ++i)
    if (test(i))
      return true;

  return false;
}

SmallBitVector &operator|=(const SmallBitVector &RHS) {
  resize(std::max(size(), RHS.size()));
  if (isSmall() && RHS.isSmall())
    setSmallBits(getSmallBits() | RHS.getSmallBits());
  else if (!isSmall() && !RHS.isSmall())
    getPointer()->operator|=(*RHS.getPointer());
  else {
    for (size_t i = 0, e = RHS.size(); i != e; ++i)
      (*this)[i] = test(i) || RHS.test(i);
  }
  return *this;
}

SmallBitVector &operator^=(const SmallBitVector &RHS) {
  resize(std::max(size(), RHS.size()));
  if (isSmall() && RHS.isSmall())
    setSmallBits(getSmallBits() ^ RHS.getSmallBits());
  else if (!isSmall() && !RHS.isSmall())
    getPointer()->operator^=(*RHS.getPointer());
  else {
    for (size_t i = 0, e = RHS.size(); i != e; ++i)
      (*this)[i] = test(i) != RHS.test(i);
  }
  return *this;
}

SmallBitVector &operator<<=(unsigned N) {
  if (isSmall())
    setSmallBits(getSmallBits() << N);
  else
    getPointer()->operator<<=(N);
  return *this;
}

SmallBitVector &operator>>=(unsigned N) {
  if (isSmall())
    setSmallBits(getSmallBits() >> N);
  else
    getPointer()->operator>>=(N);
  return *this;
}

// Assignment operator.
const SmallBitVector &operator=(const SmallBitVector &RHS) {
  if (isSmall()) {
    if (RHS.isSmall())
      X = RHS.X;
    else
      switchToLarge(new BitVector(*RHS.getPointer()));
  } else {
    if (!RHS.isSmall())
      *getPointer() = *RHS.getPointer();
    else {
      delete getPointer();
      X = RHS.X;
    }
  }
  return *this;
}

const SmallBitVector &operator=(SmallBitVector &&RHS) {
  if (this != &RHS) {
    clear();
    swap(RHS);
  }
  return *this;
}

void swap(SmallBitVector &RHS) {
  std::swap(X, RHS.X);
}

/// Add '1' bits from Mask to this vector. Don't resize.
/// This computes "*this |= Mask".
void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
  if (isSmall())
    applyMask<true, false>(Mask, MaskWords);
  else
    getPointer()->setBitsInMask(Mask, MaskWords);
}

/// Clear any bits in this vector that are set in Mask. Don't resize.
/// This computes "*this &= ~Mask".
void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
  if (isSmall())
    applyMask<false, false>(Mask, MaskWords);
  else
    getPointer()->clearBitsInMask(Mask, MaskWords);
}

/// Add a bit to this vector for every '0' bit in Mask. Don't resize.
/// This computes "*this |= ~Mask".
void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
  if (isSmall())
    applyMask<true, true>(Mask, MaskWords);
  else
    getPointer()->setBitsNotInMask(Mask, MaskWords);
}

/// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
/// This computes "*this &= Mask".
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
  if (isSmall())
    applyMask<false, true>(Mask, MaskWords);
  else
    getPointer()->clearBitsNotInMask(Mask, MaskWords);
}

666private:
template <bool AddBits, bool InvertMask>
void applyMask(const uint32_t *Mask, unsigned MaskWords) {
  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__));
  uintptr_t M = Mask[0];
  if (NumBaseBits == 64)
    M |= uint64_t(Mask[1]) << 32;
  if (InvertMask)
    M = ~M;
  if (AddBits)
    setSmallBits(getSmallBits() | M);
  else
    setSmallBits(getSmallBits() & ~M);
}
680};

682inline SmallBitVector
683operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
SmallBitVector Result(LHS);
Result &= RHS;
return Result;
687}

689inline SmallBitVector
690operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
SmallBitVector Result(LHS);
Result |= RHS;
return Result;
694}

696inline SmallBitVector
697operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
SmallBitVector Result(LHS);
Result ^= RHS;
return Result;
701}

703} // end namespace llvm

705namespace std {

707/// Implement std::swap in terms of BitVector swap.
708inline void
709swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
LHS.swap(RHS);
711}

713} // end namespace std

715#endif // LLVM_ADT_SMALLBITVECTOR_H