/build/llvm-toolchain-snapshot-7~svn326551/tools/gold/gold-plugin.cpp

Bug Summary

File:	tools/gold/gold-plugin.cpp
Warning:	line 934, column 29 Potential leak of memory pointed to by field '_M_head_impl'

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

/build/llvm-toolchain-snapshot-7~svn326551/tools/gold/gold-plugin.cpp

→

1//===-- gold-plugin.cpp - Plugin to gold for Link Time Optimization  ------===//
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 is a gold plugin for LLVM. It provides an LLVM implementation of the
11// interface described in http://gcc.gnu.org/wiki/whopr/driver .
12//
13//===----------------------------------------------------------------------===//

15#include "llvm/ADT/Statistic.h"
16#include "llvm/Bitcode/BitcodeReader.h"
17#include "llvm/Bitcode/BitcodeWriter.h"
18#include "llvm/CodeGen/CommandFlags.def"
19#include "llvm/Config/config.h" // plugin-api.h requires HAVE_STDINT_H
20#include "llvm/IR/Constants.h"
21#include "llvm/IR/DiagnosticPrinter.h"
22#include "llvm/LTO/Caching.h"
23#include "llvm/LTO/LTO.h"
24#include "llvm/Object/Error.h"
25#include "llvm/Support/CachePruning.h"
26#include "llvm/Support/CommandLine.h"
27#include "llvm/Support/FileSystem.h"
28#include "llvm/Support/ManagedStatic.h"
29#include "llvm/Support/MemoryBuffer.h"
30#include "llvm/Support/Path.h"
31#include "llvm/Support/TargetSelect.h"
32#include "llvm/Support/raw_ostream.h"
33#include <list>
34#include <map>
35#include <plugin-api.h>
36#include <string>
37#include <system_error>
38#include <utility>
39#include <vector>

41// FIXME: remove this declaration when we stop maintaining Ubuntu Quantal and
42// Precise and Debian Wheezy (binutils 2.23 is required)
43#define LDPO_PIE3 3

45#define LDPT_GET_SYMBOLS_V328 28

47using namespace llvm;
48using namespace lto;

50static ld_plugin_status discard_message(int level, const char *format, ...) {
// Die loudly. Recent versions of Gold pass ld_plugin_message as the first
// callback in the transfer vector. This should never be called.
abort();
54}

56static ld_plugin_release_input_file release_input_file = nullptr;
57static ld_plugin_get_input_file get_input_file = nullptr;
58static ld_plugin_message message = discard_message;

60namespace {
61struct claimed_file {
void *handle;
void *leader_handle;
std::vector<ld_plugin_symbol> syms;
off_t filesize;
std::string name;
67};

69/// RAII wrapper to manage opening and releasing of a ld_plugin_input_file.
70struct PluginInputFile {
void *Handle;
std::unique_ptr<ld_plugin_input_file> File;

PluginInputFile(void *Handle) : Handle(Handle) {
  File = llvm::make_unique<ld_plugin_input_file>();
  if (get_input_file(Handle, File.get()) != LDPS_OK)
    message(LDPL_FATAL, "Failed to get file information");
}
~PluginInputFile() {
  // File would have been reset to nullptr if we moved this object
  // to a new owner.
  if (File)
    if (release_input_file(Handle) != LDPS_OK)
      message(LDPL_FATAL, "Failed to release file information");
}

ld_plugin_input_file &file() { return *File; }

PluginInputFile(PluginInputFile &&RHS) = default;
PluginInputFile &operator=(PluginInputFile &&RHS) = default;
91};

93struct ResolutionInfo {
bool CanOmitFromDynSym = true;
bool DefaultVisibility = true;
96};

98}

100static ld_plugin_add_symbols add_symbols = nullptr;
101static ld_plugin_get_symbols get_symbols = nullptr;
102static ld_plugin_add_input_file add_input_file = nullptr;
103static ld_plugin_set_extra_library_path set_extra_library_path = nullptr;
104static ld_plugin_get_view get_view = nullptr;
105static bool IsExecutable = false;
106static Optional<Reloc::Model> RelocationModel = None;
107static std::string output_name = "";
108static std::list<claimed_file> Modules;
109static DenseMap<int, void *> FDToLeaderHandle;
110static StringMap<ResolutionInfo> ResInfo;
111static std::vector<std::string> Cleanup;

113namespace options {
enum OutputType {
  OT_NORMAL,
  OT_DISABLE,
  OT_BC_ONLY,
  OT_SAVE_TEMPS
};
static OutputType TheOutputType = OT_NORMAL;
static unsigned OptLevel = 2;
// Default parallelism of 0 used to indicate that user did not specify.
// Actual parallelism default value depends on implementation.
// Currently only affects ThinLTO, where the default is
// llvm::heavyweight_hardware_concurrency.
static unsigned Parallelism = 0;
// Default regular LTO codegen parallelism (number of partitions).
static unsigned ParallelCodeGenParallelismLevel = 1;
129#ifdef NDEBUG
static bool DisableVerify = true;
131#else
static bool DisableVerify = false;
133#endif
static std::string obj_path;
static std::string extra_library_path;
static std::string triple;
static std::string mcpu;
// When the thinlto plugin option is specified, only read the function
// the information from intermediate files and write a combined
// global index for the ThinLTO backends.
static bool thinlto = false;
// If false, all ThinLTO backend compilations through code gen are performed
// using multiple threads in the gold-plugin, before handing control back to
// gold. If true, write individual backend index files which reflect
// the import decisions, and exit afterwards. The assumption is
// that the build system will launch the backend processes.
static bool thinlto_index_only = false;
// If non-empty, holds the name of a file in which to write the list of
// oject files gold selected for inclusion in the link after symbol
// resolution (i.e. they had selected symbols). This will only be non-empty
// in the thinlto_index_only case. It is used to identify files, which may
// have originally been within archive libraries specified via
// --start-lib/--end-lib pairs, that should be included in the final
// native link process (since intervening function importing and inlining
// may change the symbol resolution detected in the final link and which
// files to include out of --start-lib/--end-lib libraries as a result).
static std::string thinlto_linked_objects_file;
// If true, when generating individual index files for distributed backends,
// also generate a "${bitcodefile}.imports" file at the same location for each
// bitcode file, listing the files it imports from in plain text. This is to
// support distributed build file staging.
static bool thinlto_emit_imports_files = false;
// Option to control where files for a distributed backend (the individual
// index files and optional imports files) are created.
// If specified, expects a string of the form "oldprefix:newprefix", and
// instead of generating these files in the same directory path as the
// corresponding bitcode file, will use a path formed by replacing the
// bitcode file's path prefix matching oldprefix with newprefix.
static std::string thinlto_prefix_replace;
// Option to control the name of modules encoded in the individual index
// files for a distributed backend. This enables the use of minimized
// bitcode files for the thin link, assuming the name of the full bitcode
// file used in the backend differs just in some part of the file suffix.
// If specified, expects a string of the form "oldsuffix:newsuffix".
static std::string thinlto_object_suffix_replace;
// Optional path to a directory for caching ThinLTO objects.
static std::string cache_dir;
// Optional pruning policy for ThinLTO caches.
static std::string cache_policy;
// Additional options to pass into the code generator.
// Note: This array will contain all plugin options which are not claimed
// as plugin exclusive to pass to the code generator.
static std::vector<const char *> extra;
// Sample profile file path
static std::string sample_profile;
// New pass manager
static bool new_pass_manager = false;

static void process_plugin_option(const char *opt_)
{
  if (opt_ == nullptr)
    return;
  llvm::StringRef opt = opt_;

  if (opt.startswith("mcpu=")) {
    mcpu = opt.substr(strlen("mcpu="));
  } else if (opt.startswith("extra-library-path=")) {
    extra_library_path = opt.substr(strlen("extra_library_path="));
  } else if (opt.startswith("mtriple=")) {
    triple = opt.substr(strlen("mtriple="));
  } else if (opt.startswith("obj-path=")) {
    obj_path = opt.substr(strlen("obj-path="));
  } else if (opt == "emit-llvm") {
    TheOutputType = OT_BC_ONLY;
  } else if (opt == "save-temps") {
    TheOutputType = OT_SAVE_TEMPS;
  } else if (opt == "disable-output") {
    TheOutputType = OT_DISABLE;
  } else if (opt == "thinlto") {
    thinlto = true;
  } else if (opt == "thinlto-index-only") {
    thinlto_index_only = true;
  } else if (opt.startswith("thinlto-index-only=")) {
    thinlto_index_only = true;
    thinlto_linked_objects_file = opt.substr(strlen("thinlto-index-only="));
  } else if (opt == "thinlto-emit-imports-files") {
    thinlto_emit_imports_files = true;
  } else if (opt.startswith("thinlto-prefix-replace=")) {
    thinlto_prefix_replace = opt.substr(strlen("thinlto-prefix-replace="));
    if (thinlto_prefix_replace.find(';') == std::string::npos)
      message(LDPL_FATAL, "thinlto-prefix-replace expects 'old;new' format");
  } else if (opt.startswith("thinlto-object-suffix-replace=")) {
    thinlto_object_suffix_replace =
        opt.substr(strlen("thinlto-object-suffix-replace="));
    if (thinlto_object_suffix_replace.find(';') == std::string::npos)
      message(LDPL_FATAL,
              "thinlto-object-suffix-replace expects 'old;new' format");
  } else if (opt.startswith("cache-dir=")) {
    cache_dir = opt.substr(strlen("cache-dir="));
  } else if (opt.startswith("cache-policy=")) {
    cache_policy = opt.substr(strlen("cache-policy="));
  } else if (opt.size() == 2 && opt[0] == 'O') {
    if (opt[1] < '0' || opt[1] > '3')
      message(LDPL_FATAL, "Optimization level must be between 0 and 3");
    OptLevel = opt[1] - '0';
  } else if (opt.startswith("jobs=")) {
    if (StringRef(opt_ + 5).getAsInteger(10, Parallelism))
      message(LDPL_FATAL, "Invalid parallelism level: %s", opt_ + 5);
  } else if (opt.startswith("lto-partitions=")) {
    if (opt.substr(strlen("lto-partitions="))
            .getAsInteger(10, ParallelCodeGenParallelismLevel))
      message(LDPL_FATAL, "Invalid codegen partition level: %s", opt_ + 5);
  } else if (opt == "disable-verify") {
    DisableVerify = true;
  } else if (opt.startswith("sample-profile=")) {
    sample_profile= opt.substr(strlen("sample-profile="));
  } else if (opt == "new-pass-manager") {
    new_pass_manager = true;
  } else {
    // Save this option to pass to the code generator.
    // ParseCommandLineOptions() expects argv[0] to be program name. Lazily
    // add that.
    if (extra.empty())
      extra.push_back("LLVMgold");

    extra.push_back(opt_);
  }
}
259}

261static ld_plugin_status claim_file_hook(const ld_plugin_input_file *file,
                                      int *claimed);
263static ld_plugin_status all_symbols_read_hook(void);
264static ld_plugin_status cleanup_hook(void);

266extern "C" ld_plugin_status onload(ld_plugin_tv *tv);
267ld_plugin_status onload(ld_plugin_tv *tv) {
InitializeAllTargetInfos();
InitializeAllTargets();
InitializeAllTargetMCs();
InitializeAllAsmParsers();
InitializeAllAsmPrinters();

// We're given a pointer to the first transfer vector. We read through them
// until we find one where tv_tag == LDPT_NULL. The REGISTER_* tagged values
// contain pointers to functions that we need to call to register our own
// hooks. The others are addresses of functions we can use to call into gold
// for services.

bool registeredClaimFile = false;
bool RegisteredAllSymbolsRead = false;

for (; tv->tv_tag != LDPT_NULL; ++tv) {
  // Cast tv_tag to int to allow values not in "enum ld_plugin_tag", like, for
  // example, LDPT_GET_SYMBOLS_V3 when building against an older plugin-api.h
  // header.
  switch (static_cast<int>(tv->tv_tag)) {
  case LDPT_OUTPUT_NAME:
    output_name = tv->tv_u.tv_string;
    break;
  case LDPT_LINKER_OUTPUT:
    switch (tv->tv_u.tv_val) {
    case LDPO_REL: // .o
      IsExecutable = false;
      break;
    case LDPO_DYN: // .so
      IsExecutable = false;
      RelocationModel = Reloc::PIC_;
      break;
    case LDPO_PIE3: // position independent executable
      IsExecutable = true;
      RelocationModel = Reloc::PIC_;
      break;
    case LDPO_EXEC: // .exe
      IsExecutable = true;
      RelocationModel = Reloc::Static;
      break;
    default:
      message(LDPL_ERROR, "Unknown output file type %d", tv->tv_u.tv_val);
      return LDPS_ERR;
    }
    break;
  case LDPT_OPTION:
    options::process_plugin_option(tv->tv_u.tv_string);
    break;
  case LDPT_REGISTER_CLAIM_FILE_HOOK: {
    ld_plugin_register_claim_file callback;
    callback = tv->tv_u.tv_register_claim_file;

    if (callback(claim_file_hook) != LDPS_OK)
      return LDPS_ERR;

    registeredClaimFile = true;
  } break;
  case LDPT_REGISTER_ALL_SYMBOLS_READ_HOOK: {
    ld_plugin_register_all_symbols_read callback;
    callback = tv->tv_u.tv_register_all_symbols_read;

    if (callback(all_symbols_read_hook) != LDPS_OK)
      return LDPS_ERR;

    RegisteredAllSymbolsRead = true;
  } break;
  case LDPT_REGISTER_CLEANUP_HOOK: {
    ld_plugin_register_cleanup callback;
    callback = tv->tv_u.tv_register_cleanup;

    if (callback(cleanup_hook) != LDPS_OK)
      return LDPS_ERR;
  } break;
  case LDPT_GET_INPUT_FILE:
    get_input_file = tv->tv_u.tv_get_input_file;
    break;
  case LDPT_RELEASE_INPUT_FILE:
    release_input_file = tv->tv_u.tv_release_input_file;
    break;
  case LDPT_ADD_SYMBOLS:
    add_symbols = tv->tv_u.tv_add_symbols;
    break;
  case LDPT_GET_SYMBOLS_V2:
    // Do not override get_symbols_v3 with get_symbols_v2.
    if (!get_symbols)
      get_symbols = tv->tv_u.tv_get_symbols;
    break;
  case LDPT_GET_SYMBOLS_V328:
    get_symbols = tv->tv_u.tv_get_symbols;
    break;
  case LDPT_ADD_INPUT_FILE:
    add_input_file = tv->tv_u.tv_add_input_file;
    break;
  case LDPT_SET_EXTRA_LIBRARY_PATH:
    set_extra_library_path = tv->tv_u.tv_set_extra_library_path;
    break;
  case LDPT_GET_VIEW:
    get_view = tv->tv_u.tv_get_view;
    break;
  case LDPT_MESSAGE:
    message = tv->tv_u.tv_message;
    break;
  default:
    break;
  }
}

if (!registeredClaimFile) {
  message(LDPL_ERROR, "register_claim_file not passed to LLVMgold.");
  return LDPS_ERR;
}
if (!add_symbols) {
  message(LDPL_ERROR, "add_symbols not passed to LLVMgold.");
  return LDPS_ERR;
}

if (!RegisteredAllSymbolsRead)
  return LDPS_OK;

if (!get_input_file) {
  message(LDPL_ERROR, "get_input_file not passed to LLVMgold.");
  return LDPS_ERR;
}
if (!release_input_file) {
  message(LDPL_ERROR, "release_input_file not passed to LLVMgold.");
  return LDPS_ERR;
}

return LDPS_OK;
397}

399static void diagnosticHandler(const DiagnosticInfo &DI) {
std::string ErrStorage;
{
  raw_string_ostream OS(ErrStorage);
  DiagnosticPrinterRawOStream DP(OS);
  DI.print(DP);
}
ld_plugin_level Level;
switch (DI.getSeverity()) {
case DS_Error:
  message(LDPL_FATAL, "LLVM gold plugin has failed to create LTO module: %s",
          ErrStorage.c_str());
case DS_Warning:
  Level = LDPL_WARNING;
  break;
case DS_Note:
case DS_Remark:
  Level = LDPL_INFO;
  break;
}
message(Level, "LLVM gold plugin: %s",  ErrStorage.c_str());
420}

422static void check(Error E, std::string Msg = "LLVM gold plugin") {
handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) -> Error {
  message(LDPL_FATAL, "%s: %s", Msg.c_str(), EIB.message().c_str());
  return Error::success();
});
427}

429template <typename T> static T check(Expected<T> E) {
if (E)
  return std::move(*E);
check(E.takeError());
return T();
434}

436/// Called by gold to see whether this file is one that our plugin can handle.
437/// We'll try to open it and register all the symbols with add_symbol if
438/// possible.
439static ld_plugin_status claim_file_hook(const ld_plugin_input_file *file,
                                      int *claimed) {
MemoryBufferRef BufferRef;
std::unique_ptr<MemoryBuffer> Buffer;
if (get_view) {
  const void *view;
  if (get_view(file->handle, &view) != LDPS_OK) {
    message(LDPL_ERROR, "Failed to get a view of %s", file->name);
    return LDPS_ERR;
  }
  BufferRef =
      MemoryBufferRef(StringRef((const char *)view, file->filesize), "");
} else {
  int64_t offset = 0;
  // Gold has found what might be IR part-way inside of a file, such as
  // an .a archive.
  if (file->offset) {
    offset = file->offset;
  }
  ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr =
      MemoryBuffer::getOpenFileSlice(file->fd, file->name, file->filesize,
                                     offset);
  if (std::error_code EC = BufferOrErr.getError()) {
    message(LDPL_ERROR, EC.message().c_str());
    return LDPS_ERR;
  }
  Buffer = std::move(BufferOrErr.get());
  BufferRef = Buffer->getMemBufferRef();
}

*claimed = 1;

Expected<std::unique_ptr<InputFile>> ObjOrErr = InputFile::create(BufferRef);
if (!ObjOrErr) {
  handleAllErrors(ObjOrErr.takeError(), [&](const ErrorInfoBase &EI) {
    std::error_code EC = EI.convertToErrorCode();
    if (EC == object::object_error::invalid_file_type ||
        EC == object::object_error::bitcode_section_not_found)
      *claimed = 0;
    else
      message(LDPL_FATAL,
              "LLVM gold plugin has failed to create LTO module: %s",
              EI.message().c_str());
  });

  return *claimed ? LDPS_ERR : LDPS_OK;
}

std::unique_ptr<InputFile> Obj = std::move(*ObjOrErr);

Modules.emplace_back();
claimed_file &cf = Modules.back();

cf.handle = file->handle;
// Keep track of the first handle for each file descriptor, since there are
// multiple in the case of an archive. This is used later in the case of
// ThinLTO parallel backends to ensure that each file is only opened and
// released once.
auto LeaderHandle =
    FDToLeaderHandle.insert(std::make_pair(file->fd, file->handle)).first;
cf.leader_handle = LeaderHandle->second;
// Save the filesize since for parallel ThinLTO backends we can only
// invoke get_input_file once per archive (only for the leader handle).
cf.filesize = file->filesize;
// In the case of an archive library, all but the first member must have a
// non-zero offset, which we can append to the file name to obtain a
// unique name.
cf.name = file->name;
if (file->offset)
  cf.name += ".llvm." + std::to_string(file->offset) + "." +
             sys::path::filename(Obj->getSourceFileName()).str();

for (auto &Sym : Obj->symbols()) {
  cf.syms.push_back(ld_plugin_symbol());
  ld_plugin_symbol &sym = cf.syms.back();
  sym.version = nullptr;
  StringRef Name = Sym.getName();
  sym.name = strdup(Name.str().c_str());

  ResolutionInfo &Res = ResInfo[Name];

  Res.CanOmitFromDynSym &= Sym.canBeOmittedFromSymbolTable();

  sym.visibility = LDPV_DEFAULT;
  GlobalValue::VisibilityTypes Vis = Sym.getVisibility();
  if (Vis != GlobalValue::DefaultVisibility)
    Res.DefaultVisibility = false;
  switch (Vis) {
  case GlobalValue::DefaultVisibility:
    break;
  case GlobalValue::HiddenVisibility:
    sym.visibility = LDPV_HIDDEN;
    break;
  case GlobalValue::ProtectedVisibility:
    sym.visibility = LDPV_PROTECTED;
    break;
  }

  if (Sym.isUndefined()) {
    sym.def = LDPK_UNDEF;
    if (Sym.isWeak())
      sym.def = LDPK_WEAKUNDEF;
  } else if (Sym.isCommon())
    sym.def = LDPK_COMMON;
  else if (Sym.isWeak())
    sym.def = LDPK_WEAKDEF;
  else
    sym.def = LDPK_DEF;

  sym.size = 0;
  sym.comdat_key = nullptr;
  int CI = Sym.getComdatIndex();
  if (CI != -1) {
    StringRef C = Obj->getComdatTable()[CI];
    sym.comdat_key = strdup(C.str().c_str());
  }

  sym.resolution = LDPR_UNKNOWN;
}

if (!cf.syms.empty()) {
  if (add_symbols(cf.handle, cf.syms.size(), cf.syms.data()) != LDPS_OK) {
    message(LDPL_ERROR, "Unable to add symbols!");
    return LDPS_ERR;
  }
}

return LDPS_OK;
567}

569static void freeSymName(ld_plugin_symbol &Sym) {
free(Sym.name);
free(Sym.comdat_key);
Sym.name = nullptr;
Sym.comdat_key = nullptr;
574}

576/// Helper to get a file's symbols and a view into it via gold callbacks.
577static const void *getSymbolsAndView(claimed_file &F) {
ld_plugin_status status = get_symbols(F.handle, F.syms.size(), F.syms.data());
if (status == LDPS_NO_SYMS)
  return nullptr;

if (status != LDPS_OK)
  message(LDPL_FATAL, "Failed to get symbol information");

const void *View;
if (get_view(F.handle, &View) != LDPS_OK)
  message(LDPL_FATAL, "Failed to get a view of file");

return View;
590}

592/// Parse the thinlto-object-suffix-replace option into the \p OldSuffix and
593/// \p NewSuffix strings, if it was specified.
594static void getThinLTOOldAndNewSuffix(std::string &OldSuffix,
                                    std::string &NewSuffix) {
assert(options::thinlto_object_suffix_replace.empty() ||(static_cast <bool> (options::thinlto_object_suffix_replace
.empty() || options::thinlto_object_suffix_replace.find(";") !=
 StringRef::npos) ? void (0) : __assert_fail ("options::thinlto_object_suffix_replace.empty() || options::thinlto_object_suffix_replace.find(\";\") != StringRef::npos"
, "/build/llvm-toolchain-snapshot-7~svn326551/tools/gold/gold-plugin.cpp"
, 597, __extension__ __PRETTY_FUNCTION__))
       options::thinlto_object_suffix_replace.find(";") != StringRef::npos)(static_cast <bool> (options::thinlto_object_suffix_replace
.empty() || options::thinlto_object_suffix_replace.find(";") !=
 StringRef::npos) ? void (0) : __assert_fail ("options::thinlto_object_suffix_replace.empty() || options::thinlto_object_suffix_replace.find(\";\") != StringRef::npos"
, "/build/llvm-toolchain-snapshot-7~svn326551/tools/gold/gold-plugin.cpp"
, 597, __extension__ __PRETTY_FUNCTION__));
StringRef SuffixReplace = options::thinlto_object_suffix_replace;
std::tie(OldSuffix, NewSuffix) = SuffixReplace.split(';');
600}

602/// Given the original \p Path to an output file, replace any filename
603/// suffix matching \p OldSuffix with \p NewSuffix.
604static std::string getThinLTOObjectFileName(StringRef Path, StringRef OldSuffix,
                                          StringRef NewSuffix) {
if (OldSuffix.empty() && NewSuffix.empty())
  return Path;
StringRef NewPath = Path;
NewPath.consume_back(OldSuffix);
std::string NewNewPath = NewPath;
NewNewPath += NewSuffix;
return NewNewPath;
613}

615// Returns true if S is valid as a C language identifier.
616static bool isValidCIdentifier(StringRef S) {
return !S.empty() && (isAlpha(S[0]) || S[0] == '_') &&
       std::all_of(S.begin() + 1, S.end(),
                   [](char C) { return C == '_' || isAlnum(C); });
620}

622static bool isUndefined(ld_plugin_symbol &Sym) {
return Sym.def == LDPK_UNDEF || Sym.def == LDPK_WEAKUNDEF;
624}

626static void addModule(LTO &Lto, claimed_file &F, const void *View,
                    StringRef Filename) {
MemoryBufferRef BufferRef(StringRef((const char *)View, F.filesize),
                          Filename);
Expected<std::unique_ptr<InputFile>> ObjOrErr = InputFile::create(BufferRef);

if (!ObjOrErr)
  message(LDPL_FATAL, "Could not read bitcode from file : %s",
          toString(ObjOrErr.takeError()).c_str());

unsigned SymNum = 0;
std::unique_ptr<InputFile> Input = std::move(ObjOrErr.get());
auto InputFileSyms = Input->symbols();
assert(InputFileSyms.size() == F.syms.size())(static_cast <bool> (InputFileSyms.size() == F.syms.size
()) ? void (0) : __assert_fail ("InputFileSyms.size() == F.syms.size()"
, "/build/llvm-toolchain-snapshot-7~svn326551/tools/gold/gold-plugin.cpp"
, 639, __extension__ __PRETTY_FUNCTION__));
std::vector<SymbolResolution> Resols(F.syms.size());
for (ld_plugin_symbol &Sym : F.syms) {
  const InputFile::Symbol &InpSym = InputFileSyms[SymNum];
  SymbolResolution &R = Resols[SymNum++];

  ld_plugin_symbol_resolution Resolution =
      (ld_plugin_symbol_resolution)Sym.resolution;

  ResolutionInfo &Res = ResInfo[Sym.name];

  switch (Resolution) {
  case LDPR_UNKNOWN:
    llvm_unreachable("Unexpected resolution")::llvm::llvm_unreachable_internal("Unexpected resolution", "/build/llvm-toolchain-snapshot-7~svn326551/tools/gold/gold-plugin.cpp"
, 652);

  case LDPR_RESOLVED_IR:
  case LDPR_RESOLVED_EXEC:
  case LDPR_RESOLVED_DYN:
  case LDPR_PREEMPTED_IR:
  case LDPR_PREEMPTED_REG:
  case LDPR_UNDEF:
    break;

  case LDPR_PREVAILING_DEF_IRONLY:
    R.Prevailing = !isUndefined(Sym);
    break;

  case LDPR_PREVAILING_DEF:
    R.Prevailing = !isUndefined(Sym);
    R.VisibleToRegularObj = true;
    break;

  case LDPR_PREVAILING_DEF_IRONLY_EXP:
    R.Prevailing = !isUndefined(Sym);
    if (!Res.CanOmitFromDynSym)
      R.VisibleToRegularObj = true;
    break;
  }

  // If the symbol has a C identifier section name, we need to mark
  // it as visible to a regular object so that LTO will keep it around
  // to ensure the linker generates special __start_<secname> and
  // __stop_<secname> symbols which may be used elsewhere.
  if (isValidCIdentifier(InpSym.getSectionName()))
    R.VisibleToRegularObj = true;

  if (Resolution != LDPR_RESOLVED_DYN && Resolution != LDPR_UNDEF &&
      (IsExecutable || !Res.DefaultVisibility))
    R.FinalDefinitionInLinkageUnit = true;

  freeSymName(Sym);
}

check(Lto.add(std::move(Input), Resols),
      std::string("Failed to link module ") + F.name);
694}

696static void recordFile(const std::string &Filename, bool TempOutFile) {
if (add_input_file(Filename.c_str()) != LDPS_OK)
  message(LDPL_FATAL,
          "Unable to add .o file to the link. File left behind in: %s",
          Filename.c_str());
if (TempOutFile)
  Cleanup.push_back(Filename);
703}

705/// Return the desired output filename given a base input name, a flag
706/// indicating whether a temp file should be generated, and an optional task id.
707/// The new filename generated is returned in \p NewFilename.
708static int getOutputFileName(StringRef InFilename, bool TempOutFile,
                           SmallString<128> &NewFilename, int TaskID) {
int FD = -1;
if (TempOutFile) {
  std::error_code EC =
      sys::fs::createTemporaryFile("lto-llvm", "o", FD, NewFilename);
  if (EC)
    message(LDPL_FATAL, "Could not create temporary file: %s",
            EC.message().c_str());
} else {
  NewFilename = InFilename;
  if (TaskID > 0)
    NewFilename += utostr(TaskID);
  std::error_code EC =
      sys::fs::openFileForWrite(NewFilename, FD, sys::fs::F_None);
  if (EC)
    message(LDPL_FATAL, "Could not open file %s: %s", NewFilename.c_str(),
            EC.message().c_str());
}
return FD;
728}

730/// Parse the thinlto_prefix_replace option into the \p OldPrefix and
731/// \p NewPrefix strings, if it was specified.
732static void getThinLTOOldAndNewPrefix(std::string &OldPrefix,
                                    std::string &NewPrefix) {
StringRef PrefixReplace = options::thinlto_prefix_replace;
assert(PrefixReplace.empty() || PrefixReplace.find(";") != StringRef::npos)(static_cast <bool> (PrefixReplace.empty() || PrefixReplace
.find(";") != StringRef::npos) ? void (0) : __assert_fail ("PrefixReplace.empty() || PrefixReplace.find(\";\") != StringRef::npos"
, "/build/llvm-toolchain-snapshot-7~svn326551/tools/gold/gold-plugin.cpp"
, 735, __extension__ __PRETTY_FUNCTION__));
std::tie(OldPrefix, NewPrefix) = PrefixReplace.split(';');
737}

739/// Creates instance of LTO.
740/// OnIndexWrite is callback to let caller know when LTO writes index files.
741/// LinkedObjectsFile is an output stream to write the list of object files for
742/// the final ThinLTO linking. Can be nullptr.
743static std::unique_ptr<LTO> createLTO(IndexWriteCallback OnIndexWrite,
                                    raw_fd_ostream *LinkedObjectsFile) {
Config Conf;
ThinBackend Backend;

Conf.CPU = options::mcpu;
Conf.Options = InitTargetOptionsFromCodeGenFlags();

// Disable the new X86 relax relocations since gold might not support them.
// FIXME: Check the gold version or add a new option to enable them.
Conf.Options.RelaxELFRelocations = false;

// Enable function/data sections by default.
Conf.Options.FunctionSections = true;
Conf.Options.DataSections = true;

Conf.MAttrs = MAttrs;
Conf.RelocModel = RelocationModel;
Conf.DisableVerify = options::DisableVerify;
Conf.OptLevel = options::OptLevel;
if (options::Parallelism)
  Backend = createInProcessThinBackend(options::Parallelism);
if (options::thinlto_index_only) {
  std::string OldPrefix, NewPrefix;
  getThinLTOOldAndNewPrefix(OldPrefix, NewPrefix);
  Backend = createWriteIndexesThinBackend(OldPrefix, NewPrefix,
                                          options::thinlto_emit_imports_files,
                                          LinkedObjectsFile, OnIndexWrite);
}

Conf.OverrideTriple = options::triple;
Conf.DefaultTriple = sys::getDefaultTargetTriple();

Conf.DiagHandler = diagnosticHandler;

switch (options::TheOutputType) {
case options::OT_NORMAL:
  break;

case options::OT_DISABLE:
  Conf.PreOptModuleHook = [](size_t Task, const Module &M) { return false; };
  break;

case options::OT_BC_ONLY:
  Conf.PostInternalizeModuleHook = [](size_t Task, const Module &M) {
    std::error_code EC;
    raw_fd_ostream OS(output_name, EC, sys::fs::OpenFlags::F_None);
    if (EC)
      message(LDPL_FATAL, "Failed to write the output file.");
    WriteBitcodeToFile(M, OS, /* ShouldPreserveUseListOrder */ false);
    return false;
  };
  break;

case options::OT_SAVE_TEMPS:
  check(Conf.addSaveTemps(output_name + ".",
                          /* UseInputModulePath */ true));
  break;
}

if (!options::sample_profile.empty())
  Conf.SampleProfile = options::sample_profile;

// Use new pass manager if set in driver
Conf.UseNewPM = options::new_pass_manager;

return llvm::make_unique<LTO>(std::move(Conf), Backend,
                              options::ParallelCodeGenParallelismLevel);
811}

813// Write empty files that may be expected by a distributed build
814// system when invoked with thinlto_index_only. This is invoked when
815// the linker has decided not to include the given module in the
816// final link. Frequently the distributed build system will want to
817// confirm that all expected outputs are created based on all of the
818// modules provided to the linker.
819// If SkipModule is true then .thinlto.bc should contain just
820// SkipModuleByDistributedBackend flag which requests distributed backend
821// to skip the compilation of the corresponding module and produce an empty
822// object file.
823static void writeEmptyDistributedBuildOutputs(const std::string &ModulePath,
                                            const std::string &OldPrefix,
                                            const std::string &NewPrefix,
                                            bool SkipModule) {
std::string NewModulePath =
    getThinLTOOutputFile(ModulePath, OldPrefix, NewPrefix);
std::error_code EC;
{
  raw_fd_ostream OS(NewModulePath + ".thinlto.bc", EC,
                    sys::fs::OpenFlags::F_None);
  if (EC)
    message(LDPL_FATAL, "Failed to write '%s': %s",
            (NewModulePath + ".thinlto.bc").c_str(), EC.message().c_str());

  if (SkipModule) {
    ModuleSummaryIndex Index(false);
    Index.setSkipModuleByDistributedBackend();
    WriteIndexToFile(Index, OS, nullptr);
  }
}
if (options::thinlto_emit_imports_files) {
  raw_fd_ostream OS(NewModulePath + ".imports", EC,
                    sys::fs::OpenFlags::F_None);
  if (EC)
    message(LDPL_FATAL, "Failed to write '%s': %s",
            (NewModulePath + ".imports").c_str(), EC.message().c_str());
}
850}

852// Creates and returns output stream with a list of object files for final
853// linking of distributed ThinLTO.
854static std::unique_ptr<raw_fd_ostream> CreateLinkedObjectsFile() {
if (options::thinlto_linked_objects_file.empty())
  return nullptr;
assert(options::thinlto_index_only)(static_cast <bool> (options::thinlto_index_only) ? void
 (0) : __assert_fail ("options::thinlto_index_only", "/build/llvm-toolchain-snapshot-7~svn326551/tools/gold/gold-plugin.cpp"
, 857, __extension__ __PRETTY_FUNCTION__));
std::error_code EC;
auto LinkedObjectsFile = llvm::make_unique<raw_fd_ostream>(
    options::thinlto_linked_objects_file, EC, sys::fs::OpenFlags::F_None);
if (EC)
  message(LDPL_FATAL, "Failed to create '%s': %s",
          options::thinlto_linked_objects_file.c_str(), EC.message().c_str());
return LinkedObjectsFile;
865}

867/// Runs LTO and return a list of pairs <FileName, IsTemporary>.
868static std::vector<std::pair<SmallString<128>, bool>> runLTO() {
// Map to own RAII objects that manage the file opening and releasing
// interfaces with gold. This is needed only for ThinLTO mode, since
// unlike regular LTO, where addModule will result in the opened file
// being merged into a new combined module, we need to keep these files open
// through Lto->run().
DenseMap<void *, std::unique_ptr<PluginInputFile>> HandleToInputFile;

// Owns string objects and tells if index file was already created.
StringMap<bool> ObjectToIndexFileState;

std::unique_ptr<raw_fd_ostream> LinkedObjects = CreateLinkedObjectsFile();
std::unique_ptr<LTO> Lto = createLTO(
    [&ObjectToIndexFileState](const std::string &Identifier) {
      ObjectToIndexFileState[Identifier] = true;
    },
    LinkedObjects.get());

std::string OldPrefix, NewPrefix;
if (options::thinlto_index_only)
  getThinLTOOldAndNewPrefix(OldPrefix, NewPrefix);

std::string OldSuffix, NewSuffix;
getThinLTOOldAndNewSuffix(OldSuffix, NewSuffix);

for (claimed_file &F : Modules) {
  if (options::thinlto && !HandleToInputFile.count(F.leader_handle))
    HandleToInputFile.insert(std::make_pair(
        F.leader_handle, llvm::make_unique<PluginInputFile>(F.handle)));
  // In case we are thin linking with a minimized bitcode file, ensure
  // the module paths encoded in the index reflect where the backends
  // will locate the full bitcode files for compiling/importing.
  std::string Identifier =
      getThinLTOObjectFileName(F.name, OldSuffix, NewSuffix);
  auto ObjFilename = ObjectToIndexFileState.insert({Identifier, false});
  assert(ObjFilename.second)(static_cast <bool> (ObjFilename.second) ? void (0) : __assert_fail
 ("ObjFilename.second", "/build/llvm-toolchain-snapshot-7~svn326551/tools/gold/gold-plugin.cpp"
, 903, __extension__ __PRETTY_FUNCTION__));
  if (const void *View = getSymbolsAndView(F))
    addModule(*Lto, F, View, ObjFilename.first->first());
  else if (options::thinlto_index_only) {
    ObjFilename.first->second = true;
    writeEmptyDistributedBuildOutputs(Identifier, OldPrefix, NewPrefix,
                                      /* SkipModule */ true);
  }
}

SmallString<128> Filename;
// Note that getOutputFileName will append a unique ID for each task
if (!options::obj_path.empty())
  Filename = options::obj_path;
else if (options::TheOutputType == options::OT_SAVE_TEMPS)
  Filename = output_name + ".o";
bool SaveTemps = !Filename.empty();

size_t MaxTasks = Lto->getMaxTasks();
std::vector<std::pair<SmallString<128>, bool>> Files(MaxTasks);

auto AddStream =
    [&](size_t Task) -> std::unique_ptr<lto::NativeObjectStream> {
  Files[Task].second = !SaveTemps;
2
←
Assuming 'SaveTemps' is not equal to 0→
  int FD = getOutputFileName(Filename, /* TempOutFile */ !SaveTemps,
                             Files[Task].first, Task);
  return llvm::make_unique<lto::NativeObjectStream>(
3
←
Calling 'make_unique'→
5
←
Returned allocated memory→
      llvm::make_unique<llvm::raw_fd_ostream>(FD, true));
};

auto AddBuffer = [&](size_t Task, std::unique_ptr<MemoryBuffer> MB) {
  *AddStream(Task)->OS << MB->getBuffer();
1
Calling 'operator()'→
6
←
Returned allocated memory→
7
←
Potential leak of memory pointed to by field '_M_head_impl'
};

NativeObjectCache Cache;
if (!options::cache_dir.empty())
  Cache = check(localCache(options::cache_dir, AddBuffer));

check(Lto->run(AddStream, Cache));

// Write empty output files that may be expected by the distributed build
// system.
if (options::thinlto_index_only)
  for (auto &Identifier : ObjectToIndexFileState)
    if (!Identifier.getValue())
      writeEmptyDistributedBuildOutputs(Identifier.getKey(), OldPrefix,
                                        NewPrefix, /* SkipModule */ false);

return Files;
952}

954/// gold informs us that all symbols have been read. At this point, we use
955/// get_symbols to see if any of our definitions have been overridden by a
956/// native object file. Then, perform optimization and codegen.
957static ld_plugin_status allSymbolsReadHook() {
if (Modules.empty())
  return LDPS_OK;

if (unsigned NumOpts = options::extra.size())
  cl::ParseCommandLineOptions(NumOpts, &options::extra[0]);

std::vector<std::pair<SmallString<128>, bool>> Files = runLTO();

if (options::TheOutputType == options::OT_DISABLE ||
    options::TheOutputType == options::OT_BC_ONLY)
  return LDPS_OK;

if (options::thinlto_index_only) {
  if (llvm::AreStatisticsEnabled())
    llvm::PrintStatistics();
  cleanup_hook();
  exit(0);
}

for (const auto &F : Files)
  if (!F.first.empty())
    recordFile(F.first.str(), F.second);

if (!options::extra_library_path.empty() &&
    set_extra_library_path(options::extra_library_path.c_str()) != LDPS_OK)
  message(LDPL_FATAL, "Unable to set the extra library path.");

return LDPS_OK;
986}

988static ld_plugin_status all_symbols_read_hook(void) {
ld_plugin_status Ret = allSymbolsReadHook();
llvm_shutdown();

if (options::TheOutputType == options::OT_BC_ONLY ||
    options::TheOutputType == options::OT_DISABLE) {
  if (options::TheOutputType == options::OT_DISABLE) {
    // Remove the output file here since ld.bfd creates the output file
    // early.
    std::error_code EC = sys::fs::remove(output_name);
    if (EC)
      message(LDPL_ERROR, "Failed to delete '%s': %s", output_name.c_str(),
              EC.message().c_str());
  }
  exit(0);
}

return Ret;
1006}

1008static ld_plugin_status cleanup_hook(void) {
for (std::string &Name : Cleanup) {
  std::error_code EC = sys::fs::remove(Name);
  if (EC)
    message(LDPL_ERROR, "Failed to delete '%s': %s", Name.c_str(),
            EC.message().c_str());
}

// Prune cache
if (!options::cache_dir.empty()) {
  CachePruningPolicy policy = check(parseCachePruningPolicy(options::cache_policy));
  pruneCache(options::cache_dir, policy);
}

return LDPS_OK;
1023}

←

/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h

1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- 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 contains some templates that are useful if you are working with the
11// STL at all.
12//
13// No library is required when using these functions.
14//
15//===----------------------------------------------------------------------===//
16 
17#ifndef LLVM_ADT_STLEXTRAS_H
18#define LLVM_ADT_STLEXTRAS_H
19 
20#include "llvm/ADT/Optional.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/iterator.h"
23#include "llvm/ADT/iterator_range.h"
24#include "llvm/Support/ErrorHandling.h"
25#include <algorithm>
26#include <cassert>
27#include <cstddef>
28#include <cstdint>
29#include <cstdlib>
30#include <functional>
31#include <initializer_list>
32#include <iterator>
33#include <limits>
34#include <memory>
35#include <tuple>
36#include <type_traits>
37#include <utility>
38 
39namespace llvm {
40 
41// Only used by compiler if both template types are the same.  Useful when
42// using SFINAE to test for the existence of member functions.
43template <typename T, T> struct SameType;
44 
45namespace detail {
46 
47template <typename RangeT>
48using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
49 
50template <typename RangeT>
51using ValueOfRange = typename std::remove_reference<decltype(
52    *std::begin(std::declval<RangeT &>()))>::type;
53 
54} // end namespace detail
55 
56//===----------------------------------------------------------------------===//
57//     Extra additions to <functional>
58//===----------------------------------------------------------------------===//
59 
60template <class Ty> struct identity {
61  using argument_type = Ty;
62 
63  Ty &operator()(Ty &self) const {
64    return self;
65  }
66  const Ty &operator()(const Ty &self) const {
67    return self;
68  }
69};
70 
71template <class Ty> struct less_ptr {
72  bool operator()(const Ty* left, const Ty* right) const {
73    return *left < *right;
74  }
75};
76 
77template <class Ty> struct greater_ptr {
78  bool operator()(const Ty* left, const Ty* right) const {
79    return *right < *left;
80  }
81};
82 
83/// An efficient, type-erasing, non-owning reference to a callable. This is
84/// intended for use as the type of a function parameter that is not used
85/// after the function in question returns.
86///
87/// This class does not own the callable, so it is not in general safe to store
88/// a function_ref.
89template<typename Fn> class function_ref;
90 
91template<typename Ret, typename ...Params>
92class function_ref<Ret(Params...)> {
93  Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
94  intptr_t callable;
95 
96  template<typename Callable>
97  static Ret callback_fn(intptr_t callable, Params ...params) {
98    return (*reinterpret_cast<Callable*>(callable))(
99        std::forward<Params>(params)...);
100  }
101 
102public:
103  function_ref() = default;
104  function_ref(std::nullptr_t) {}
105 
106  template <typename Callable>
107  function_ref(Callable &&callable,
108               typename std::enable_if<
109                   !std::is_same<typename std::remove_reference<Callable>::type,
110                                 function_ref>::value>::type * = nullptr)
111      : callback(callback_fn<typename std::remove_reference<Callable>::type>),
112        callable(reinterpret_cast<intptr_t>(&callable)) {}
113 
114  Ret operator()(Params ...params) const {
115    return callback(callable, std::forward<Params>(params)...);
116  }
117 
118  operator bool() const { return callback; }
119};
120 
121// deleter - Very very very simple method that is used to invoke operator
122// delete on something.  It is used like this:
123//
124//   for_each(V.begin(), B.end(), deleter<Interval>);
125template <class T>
126inline void deleter(T *Ptr) {
127  delete Ptr;
128}
129 
130//===----------------------------------------------------------------------===//
131//     Extra additions to <iterator>
132//===----------------------------------------------------------------------===//
133 
134namespace adl_detail {
135 
136using std::begin;
137 
138template <typename ContainerTy>
139auto adl_begin(ContainerTy &&container)
140    -> decltype(begin(std::forward<ContainerTy>(container))) {
141  return begin(std::forward<ContainerTy>(container));
142}
143 
144using std::end;
145 
146template <typename ContainerTy>
147auto adl_end(ContainerTy &&container)
148    -> decltype(end(std::forward<ContainerTy>(container))) {
149  return end(std::forward<ContainerTy>(container));
150}
151 
152using std::swap;
153 
154template <typename T>
155void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
156                                                       std::declval<T>()))) {
157  swap(std::forward<T>(lhs), std::forward<T>(rhs));
158}
159 
160} // end namespace adl_detail
161 
162template <typename ContainerTy>
163auto adl_begin(ContainerTy &&container)
164    -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
165  return adl_detail::adl_begin(std::forward<ContainerTy>(container));
166}
167 
168template <typename ContainerTy>
169auto adl_end(ContainerTy &&container)
170    -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
171  return adl_detail::adl_end(std::forward<ContainerTy>(container));
172}
173 
174template <typename T>
175void adl_swap(T &&lhs, T &&rhs) noexcept(
176    noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
177  adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
178}
179 
180// mapped_iterator - This is a simple iterator adapter that causes a function to
181// be applied whenever operator* is invoked on the iterator.
182 
183template <typename ItTy, typename FuncTy,
184          typename FuncReturnTy =
185            decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
186class mapped_iterator
187    : public iterator_adaptor_base<
188             mapped_iterator<ItTy, FuncTy>, ItTy,
189             typename std::iterator_traits<ItTy>::iterator_category,
190             typename std::remove_reference<FuncReturnTy>::type> {
191public:
192  mapped_iterator(ItTy U, FuncTy F)
193    : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
194 
195  ItTy getCurrent() { return this->I; }
196 
197  FuncReturnTy operator*() { return F(*this->I); }
198 
199private:
200  FuncTy F;
201};
202 
203// map_iterator - Provide a convenient way to create mapped_iterators, just like
204// make_pair is useful for creating pairs...
205template <class ItTy, class FuncTy>
206inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
207  return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
208}
209 
210/// Helper to determine if type T has a member called rbegin().
211template <typename Ty> class has_rbegin_impl {
212  using yes = char[1];
213  using no = char[2];
214 
215  template <typename Inner>
216  static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
217 
218  template <typename>
219  static no& test(...);
220 
221public:
222  static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
223};
224 
225/// Metafunction to determine if T& or T has a member called rbegin().
226template <typename Ty>
227struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
228};
229 
230// Returns an iterator_range over the given container which iterates in reverse.
231// Note that the container must have rbegin()/rend() methods for this to work.
232template <typename ContainerTy>
233auto reverse(ContainerTy &&C,
234             typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
235                 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
236  return make_range(C.rbegin(), C.rend());
237}
238 
239// Returns a std::reverse_iterator wrapped around the given iterator.
240template <typename IteratorTy>
241std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
242  return std::reverse_iterator<IteratorTy>(It);
243}
244 
245// Returns an iterator_range over the given container which iterates in reverse.
246// Note that the container must have begin()/end() methods which return
247// bidirectional iterators for this to work.
248template <typename ContainerTy>
249auto reverse(
250    ContainerTy &&C,
251    typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
252    -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
253                           llvm::make_reverse_iterator(std::begin(C)))) {
254  return make_range(llvm::make_reverse_iterator(std::end(C)),
255                    llvm::make_reverse_iterator(std::begin(C)));
256}
257 
258/// An iterator adaptor that filters the elements of given inner iterators.
259///
260/// The predicate parameter should be a callable object that accepts the wrapped
261/// iterator's reference type and returns a bool. When incrementing or
262/// decrementing the iterator, it will call the predicate on each element and
263/// skip any where it returns false.
264///
265/// \code
266///   int A[] = { 1, 2, 3, 4 };
267///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
268///   // R contains { 1, 3 }.
269/// \endcode
270template <typename WrappedIteratorT, typename PredicateT>
271class filter_iterator
272    : public iterator_adaptor_base<
273          filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
274          typename std::common_type<
275              std::forward_iterator_tag,
276              typename std::iterator_traits<
277                  WrappedIteratorT>::iterator_category>::type> {
278  using BaseT = iterator_adaptor_base<
279      filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
280      typename std::common_type<
281          std::forward_iterator_tag,
282          typename std::iterator_traits<WrappedIteratorT>::iterator_category>::
283          type>;
284 
285  struct PayloadType {
286    WrappedIteratorT End;
287    PredicateT Pred;
288  };
289 
290  Optional<PayloadType> Payload;
291 
292  void findNextValid() {
293    assert(Payload && "Payload should be engaged when findNextValid is called")(static_cast <bool> (Payload && "Payload should be engaged when findNextValid is called"
) ? void (0) : __assert_fail ("Payload && \"Payload should be engaged when findNextValid is called\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 293, __extension__ __PRETTY_FUNCTION__));
294    while (this->I != Payload->End && !Payload->Pred(*this->I))
295      BaseT::operator++();
296  }
297 
298  // Construct the begin iterator. The begin iterator requires to know where end
299  // is, so that it can properly stop when it hits end.
300  filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
301      : BaseT(std::move(Begin)),
302        Payload(PayloadType{std::move(End), std::move(Pred)}) {
303    findNextValid();
304  }
305 
306  // Construct the end iterator. It's not incrementable, so Payload doesn't
307  // have to be engaged.
308  filter_iterator(WrappedIteratorT End) : BaseT(End) {}
309 
310public:
311  using BaseT::operator++;
312 
313  filter_iterator &operator++() {
314    BaseT::operator++();
315    findNextValid();
316    return *this;
317  }
318 
319  template <typename RT, typename PT>
320  friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>>
321  make_filter_range(RT &&, PT);
322};
323 
324/// Convenience function that takes a range of elements and a predicate,
325/// and return a new filter_iterator range.
326///
327/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
328/// lifetime of that temporary is not kept by the returned range object, and the
329/// temporary is going to be dropped on the floor after the make_iterator_range
330/// full expression that contains this function call.
331template <typename RangeT, typename PredicateT>
332iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
333make_filter_range(RangeT &&Range, PredicateT Pred) {
334  using FilterIteratorT =
335      filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
336  return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
337                                    std::end(std::forward<RangeT>(Range)),
338                                    std::move(Pred)),
339                    FilterIteratorT(std::end(std::forward<RangeT>(Range))));
340}
341 
342// forward declarations required by zip_shortest/zip_first
343template <typename R, typename UnaryPredicate>
344bool all_of(R &&range, UnaryPredicate P);
345 
346template <size_t... I> struct index_sequence;
347 
348template <class... Ts> struct index_sequence_for;
349 
350namespace detail {
351 
352using std::declval;
353 
354// We have to alias this since inlining the actual type at the usage site
355// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
356template<typename... Iters> struct ZipTupleType {
357  using type = std::tuple<decltype(*declval<Iters>())...>;
358};
359 
360template <typename ZipType, typename... Iters>
361using zip_traits = iterator_facade_base<
362    ZipType, typename std::common_type<std::bidirectional_iterator_tag,
363                                       typename std::iterator_traits<
364                                           Iters>::iterator_category...>::type,
365    // ^ TODO: Implement random access methods.
366    typename ZipTupleType<Iters...>::type,
367    typename std::iterator_traits<typename std::tuple_element<
368        0, std::tuple<Iters...>>::type>::difference_type,
369    // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
370    // inner iterators have the same difference_type. It would fail if, for
371    // instance, the second field's difference_type were non-numeric while the
372    // first is.
373    typename ZipTupleType<Iters...>::type *,
374    typename ZipTupleType<Iters...>::type>;
375 
376template <typename ZipType, typename... Iters>
377struct zip_common : public zip_traits<ZipType, Iters...> {
378  using Base = zip_traits<ZipType, Iters...>;
379  using value_type = typename Base::value_type;
380 
381  std::tuple<Iters...> iterators;
382 
383protected:
384  template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
385    return value_type(*std::get<Ns>(iterators)...);
386  }
387 
388  template <size_t... Ns>
389  decltype(iterators) tup_inc(index_sequence<Ns...>) const {
390    return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
391  }
392 
393  template <size_t... Ns>
394  decltype(iterators) tup_dec(index_sequence<Ns...>) const {
395    return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
396  }
397 
398public:
399  zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
400 
401  value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
402 
403  const value_type operator*() const {
404    return deref(index_sequence_for<Iters...>{});
405  }
406 
407  ZipType &operator++() {
408    iterators = tup_inc(index_sequence_for<Iters...>{});
409    return *reinterpret_cast<ZipType *>(this);
410  }
411 
412  ZipType &operator--() {
413    static_assert(Base::IsBidirectional,
414                  "All inner iterators must be at least bidirectional.");
415    iterators = tup_dec(index_sequence_for<Iters...>{});
416    return *reinterpret_cast<ZipType *>(this);
417  }
418};
419 
420template <typename... Iters>
421struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
422  using Base = zip_common<zip_first<Iters...>, Iters...>;
423 
424  bool operator==(const zip_first<Iters...> &other) const {
425    return std::get<0>(this->iterators) == std::get<0>(other.iterators);
426  }
427 
428  zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
429};
430 
431template <typename... Iters>
432class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
433  template <size_t... Ns>
434  bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
435    return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
436                                              std::get<Ns>(other.iterators)...},
437                  identity<bool>{});
438  }
439 
440public:
441  using Base = zip_common<zip_shortest<Iters...>, Iters...>;
442 
443  zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
444 
445  bool operator==(const zip_shortest<Iters...> &other) const {
446    return !test(other, index_sequence_for<Iters...>{});
447  }
448};
449 
450template <template <typename...> class ItType, typename... Args> class zippy {
451public:
452  using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
453  using iterator_category = typename iterator::iterator_category;
454  using value_type = typename iterator::value_type;
455  using difference_type = typename iterator::difference_type;
456  using pointer = typename iterator::pointer;
457  using reference = typename iterator::reference;
458 
459private:
460  std::tuple<Args...> ts;
461 
462  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
463    return iterator(std::begin(std::get<Ns>(ts))...);
464  }
465  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
466    return iterator(std::end(std::get<Ns>(ts))...);
467  }
468 
469public:
470  zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
471 
472  iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
473  iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
474};
475 
476} // end namespace detail
477 
478/// zip iterator for two or more iteratable types.
479template <typename T, typename U, typename... Args>
480detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
481                                                       Args &&... args) {
482  return detail::zippy<detail::zip_shortest, T, U, Args...>(
483      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
484}
485 
486/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
487/// be the shortest.
488template <typename T, typename U, typename... Args>
489detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
490                                                          Args &&... args) {
491  return detail::zippy<detail::zip_first, T, U, Args...>(
492      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
493}
494 
495/// Iterator wrapper that concatenates sequences together.
496///
497/// This can concatenate different iterators, even with different types, into
498/// a single iterator provided the value types of all the concatenated
499/// iterators expose `reference` and `pointer` types that can be converted to
500/// `ValueT &` and `ValueT *` respectively. It doesn't support more
501/// interesting/customized pointer or reference types.
502///
503/// Currently this only supports forward or higher iterator categories as
504/// inputs and always exposes a forward iterator interface.
505template <typename ValueT, typename... IterTs>
506class concat_iterator
507    : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
508                                  std::forward_iterator_tag, ValueT> {
509  using BaseT = typename concat_iterator::iterator_facade_base;
510 
511  /// We store both the current and end iterators for each concatenated
512  /// sequence in a tuple of pairs.
513  ///
514  /// Note that something like iterator_range seems nice at first here, but the
515  /// range properties are of little benefit and end up getting in the way
516  /// because we need to do mutation on the current iterators.
517  std::tuple<std::pair<IterTs, IterTs>...> IterPairs;
518 
519  /// Attempts to increment a specific iterator.
520  ///
521  /// Returns true if it was able to increment the iterator. Returns false if
522  /// the iterator is already at the end iterator.
523  template <size_t Index> bool incrementHelper() {
524    auto &IterPair = std::get<Index>(IterPairs);
525    if (IterPair.first == IterPair.second)
526      return false;
527 
528    ++IterPair.first;
529    return true;
530  }
531 
532  /// Increments the first non-end iterator.
533  ///
534  /// It is an error to call this with all iterators at the end.
535  template <size_t... Ns> void increment(index_sequence<Ns...>) {
536    // Build a sequence of functions to increment each iterator if possible.
537    bool (concat_iterator::*IncrementHelperFns[])() = {
538        &concat_iterator::incrementHelper<Ns>...};
539 
540    // Loop over them, and stop as soon as we succeed at incrementing one.
541    for (auto &IncrementHelperFn : IncrementHelperFns)
542      if ((this->*IncrementHelperFn)())
543        return;
544 
545    llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 545);
546  }
547 
548  /// Returns null if the specified iterator is at the end. Otherwise,
549  /// dereferences the iterator and returns the address of the resulting
550  /// reference.
551  template <size_t Index> ValueT *getHelper() const {
552    auto &IterPair = std::get<Index>(IterPairs);
553    if (IterPair.first == IterPair.second)
554      return nullptr;
555 
556    return &*IterPair.first;
557  }
558 
559  /// Finds the first non-end iterator, dereferences, and returns the resulting
560  /// reference.
561  ///
562  /// It is an error to call this with all iterators at the end.
563  template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
564    // Build a sequence of functions to get from iterator if possible.
565    ValueT *(concat_iterator::*GetHelperFns[])() const = {
566        &concat_iterator::getHelper<Ns>...};
567 
568    // Loop over them, and return the first result we find.
569    for (auto &GetHelperFn : GetHelperFns)
570      if (ValueT *P = (this->*GetHelperFn)())
571        return *P;
572 
573    llvm_unreachable("Attempted to get a pointer from an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to get a pointer from an end concat iterator!"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 573);
574  }
575 
576public:
577  /// Constructs an iterator from a squence of ranges.
578  ///
579  /// We need the full range to know how to switch between each of the
580  /// iterators.
581  template <typename... RangeTs>
582  explicit concat_iterator(RangeTs &&... Ranges)
583      : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {}
584 
585  using BaseT::operator++;
586 
587  concat_iterator &operator++() {
588    increment(index_sequence_for<IterTs...>());
589    return *this;
590  }
591 
592  ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
593 
594  bool operator==(const concat_iterator &RHS) const {
595    return IterPairs == RHS.IterPairs;
596  }
597};
598 
599namespace detail {
600 
601/// Helper to store a sequence of ranges being concatenated and access them.
602///
603/// This is designed to facilitate providing actual storage when temporaries
604/// are passed into the constructor such that we can use it as part of range
605/// based for loops.
606template <typename ValueT, typename... RangeTs> class concat_range {
607public:
608  using iterator =
609      concat_iterator<ValueT,
610                      decltype(std::begin(std::declval<RangeTs &>()))...>;
611 
612private:
613  std::tuple<RangeTs...> Ranges;
614 
615  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
616    return iterator(std::get<Ns>(Ranges)...);
617  }
618  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
619    return iterator(make_range(std::end(std::get<Ns>(Ranges)),
620                               std::end(std::get<Ns>(Ranges)))...);
621  }
622 
623public:
624  concat_range(RangeTs &&... Ranges)
625      : Ranges(std::forward<RangeTs>(Ranges)...) {}
626 
627  iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
628  iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
629};
630 
631} // end namespace detail
632 
633/// Concatenated range across two or more ranges.
634///
635/// The desired value type must be explicitly specified.
636template <typename ValueT, typename... RangeTs>
637detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
638  static_assert(sizeof...(RangeTs) > 1,
639                "Need more than one range to concatenate!");
640  return detail::concat_range<ValueT, RangeTs...>(
641      std::forward<RangeTs>(Ranges)...);
642}
643 
644//===----------------------------------------------------------------------===//
645//     Extra additions to <utility>
646//===----------------------------------------------------------------------===//
647 
648/// \brief Function object to check whether the first component of a std::pair
649/// compares less than the first component of another std::pair.
650struct less_first {
651  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
652    return lhs.first < rhs.first;
653  }
654};
655 
656/// \brief Function object to check whether the second component of a std::pair
657/// compares less than the second component of another std::pair.
658struct less_second {
659  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
660    return lhs.second < rhs.second;
661  }
662};
663 
664// A subset of N3658. More stuff can be added as-needed.
665 
666/// \brief Represents a compile-time sequence of integers.
667template <class T, T... I> struct integer_sequence {
668  using value_type = T;
669 
670  static constexpr size_t size() { return sizeof...(I); }
671};
672 
673/// \brief Alias for the common case of a sequence of size_ts.
674template <size_t... I>
675struct index_sequence : integer_sequence<std::size_t, I...> {};
676 
677template <std::size_t N, std::size_t... I>
678struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
679template <std::size_t... I>
680struct build_index_impl<0, I...> : index_sequence<I...> {};
681 
682/// \brief Creates a compile-time integer sequence for a parameter pack.
683template <class... Ts>
684struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
685 
686/// Utility type to build an inheritance chain that makes it easy to rank
687/// overload candidates.
688template <int N> struct rank : rank<N - 1> {};
689template <> struct rank<0> {};
690 
691/// \brief traits class for checking whether type T is one of any of the given
692/// types in the variadic list.
693template <typename T, typename... Ts> struct is_one_of {
694  static const bool value = false;
695};
696 
697template <typename T, typename U, typename... Ts>
698struct is_one_of<T, U, Ts...> {
699  static const bool value =
700      std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
701};
702 
703/// \brief traits class for checking whether type T is a base class for all
704///  the given types in the variadic list.
705template <typename T, typename... Ts> struct are_base_of {
706  static const bool value = true;
707};
708 
709template <typename T, typename U, typename... Ts>
710struct are_base_of<T, U, Ts...> {
711  static const bool value =
712      std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
713};
714 
715//===----------------------------------------------------------------------===//
716//     Extra additions for arrays
717//===----------------------------------------------------------------------===//
718 
719/// Find the length of an array.
720template <class T, std::size_t N>
721constexpr inline size_t array_lengthof(T (&)[N]) {
722  return N;
723}
724 
725/// Adapt std::less<T> for array_pod_sort.
726template<typename T>
727inline int array_pod_sort_comparator(const void *P1, const void *P2) {
728  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
729                     *reinterpret_cast<const T*>(P2)))
730    return -1;
731  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
732                     *reinterpret_cast<const T*>(P1)))
733    return 1;
734  return 0;
735}
736 
737/// get_array_pod_sort_comparator - This is an internal helper function used to
738/// get type deduction of T right.
739template<typename T>
740inline int (*get_array_pod_sort_comparator(const T &))
741             (const void*, const void*) {
742  return array_pod_sort_comparator<T>;
743}
744 
745/// array_pod_sort - This sorts an array with the specified start and end
746/// extent.  This is just like std::sort, except that it calls qsort instead of
747/// using an inlined template.  qsort is slightly slower than std::sort, but
748/// most sorts are not performance critical in LLVM and std::sort has to be
749/// template instantiated for each type, leading to significant measured code
750/// bloat.  This function should generally be used instead of std::sort where
751/// possible.
752///
753/// This function assumes that you have simple POD-like types that can be
754/// compared with std::less and can be moved with memcpy.  If this isn't true,
755/// you should use std::sort.
756///
757/// NOTE: If qsort_r were portable, we could allow a custom comparator and
758/// default to std::less.
759template<class IteratorTy>
760inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
761  // Don't inefficiently call qsort with one element or trigger undefined
762  // behavior with an empty sequence.
763  auto NElts = End - Start;
764  if (NElts <= 1) return;
765  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
766}
767 
768template <class IteratorTy>
769inline void array_pod_sort(
770    IteratorTy Start, IteratorTy End,
771    int (*Compare)(
772        const typename std::iterator_traits<IteratorTy>::value_type *,
773        const typename std::iterator_traits<IteratorTy>::value_type *)) {
774  // Don't inefficiently call qsort with one element or trigger undefined
775  // behavior with an empty sequence.
776  auto NElts = End - Start;
777  if (NElts <= 1) return;
778  qsort(&*Start, NElts, sizeof(*Start),
779        reinterpret_cast<int (*)(const void *, const void *)>(Compare));
780}
781 
782//===----------------------------------------------------------------------===//
783//     Extra additions to <algorithm>
784//===----------------------------------------------------------------------===//
785 
786/// For a container of pointers, deletes the pointers and then clears the
787/// container.
788template<typename Container>
789void DeleteContainerPointers(Container &C) {
790  for (auto V : C)
791    delete V;
792  C.clear();
793}
794 
795/// In a container of pairs (usually a map) whose second element is a pointer,
796/// deletes the second elements and then clears the container.
797template<typename Container>
798void DeleteContainerSeconds(Container &C) {
799  for (auto &V : C)
800    delete V.second;
801  C.clear();
802}
803 
804/// Provide wrappers to std::for_each which take ranges instead of having to
805/// pass begin/end explicitly.
806template <typename R, typename UnaryPredicate>
807UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
808  return std::for_each(adl_begin(Range), adl_end(Range), P);
809}
810 
811/// Provide wrappers to std::all_of which take ranges instead of having to pass
812/// begin/end explicitly.
813template <typename R, typename UnaryPredicate>
814bool all_of(R &&Range, UnaryPredicate P) {
815  return std::all_of(adl_begin(Range), adl_end(Range), P);
816}
817 
818/// Provide wrappers to std::any_of which take ranges instead of having to pass
819/// begin/end explicitly.
820template <typename R, typename UnaryPredicate>
821bool any_of(R &&Range, UnaryPredicate P) {
822  return std::any_of(adl_begin(Range), adl_end(Range), P);
823}
824 
825/// Provide wrappers to std::none_of which take ranges instead of having to pass
826/// begin/end explicitly.
827template <typename R, typename UnaryPredicate>
828bool none_of(R &&Range, UnaryPredicate P) {
829  return std::none_of(adl_begin(Range), adl_end(Range), P);
830}
831 
832/// Provide wrappers to std::find which take ranges instead of having to pass
833/// begin/end explicitly.
834template <typename R, typename T>
835auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
836  return std::find(adl_begin(Range), adl_end(Range), Val);
837}
838 
839/// Provide wrappers to std::find_if which take ranges instead of having to pass
840/// begin/end explicitly.
841template <typename R, typename UnaryPredicate>
842auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
843  return std::find_if(adl_begin(Range), adl_end(Range), P);
844}
845 
846template <typename R, typename UnaryPredicate>
847auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
848  return std::find_if_not(adl_begin(Range), adl_end(Range), P);
849}
850 
851/// Provide wrappers to std::remove_if which take ranges instead of having to
852/// pass begin/end explicitly.
853template <typename R, typename UnaryPredicate>
854auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
855  return std::remove_if(adl_begin(Range), adl_end(Range), P);
856}
857 
858/// Provide wrappers to std::copy_if which take ranges instead of having to
859/// pass begin/end explicitly.
860template <typename R, typename OutputIt, typename UnaryPredicate>
861OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
862  return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
863}
864 
865template <typename R, typename OutputIt>
866OutputIt copy(R &&Range, OutputIt Out) {
867  return std::copy(adl_begin(Range), adl_end(Range), Out);
868}
869 
870/// Wrapper function around std::find to detect if an element exists
871/// in a container.
872template <typename R, typename E>
873bool is_contained(R &&Range, const E &Element) {
874  return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
875}
876 
877/// Wrapper function around std::count to count the number of times an element
878/// \p Element occurs in the given range \p Range.
879template <typename R, typename E>
880auto count(R &&Range, const E &Element) ->
881    typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
882  return std::count(adl_begin(Range), adl_end(Range), Element);
883}
884 
885/// Wrapper function around std::count_if to count the number of times an
886/// element satisfying a given predicate occurs in a range.
887template <typename R, typename UnaryPredicate>
888auto count_if(R &&Range, UnaryPredicate P) ->
889    typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
890  return std::count_if(adl_begin(Range), adl_end(Range), P);
891}
892 
893/// Wrapper function around std::transform to apply a function to a range and
894/// store the result elsewhere.
895template <typename R, typename OutputIt, typename UnaryPredicate>
896OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
897  return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
898}
899 
900/// Provide wrappers to std::partition which take ranges instead of having to
901/// pass begin/end explicitly.
902template <typename R, typename UnaryPredicate>
903auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
904  return std::partition(adl_begin(Range), adl_end(Range), P);
905}
906 
907/// Provide wrappers to std::lower_bound which take ranges instead of having to
908/// pass begin/end explicitly.
909template <typename R, typename ForwardIt>
910auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
911  return std::lower_bound(adl_begin(Range), adl_end(Range), I);
912}
913 
914/// \brief Given a range of type R, iterate the entire range and return a
915/// SmallVector with elements of the vector.  This is useful, for example,
916/// when you want to iterate a range and then sort the results.
917template <unsigned Size, typename R>
918SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
919to_vector(R &&Range) {
920  return {adl_begin(Range), adl_end(Range)};
921}
922 
923/// Provide a container algorithm similar to C++ Library Fundamentals v2's
924/// `erase_if` which is equivalent to:
925///
926///   C.erase(remove_if(C, pred), C.end());
927///
928/// This version works for any container with an erase method call accepting
929/// two iterators.
930template <typename Container, typename UnaryPredicate>
931void erase_if(Container &C, UnaryPredicate P) {
932  C.erase(remove_if(C, P), C.end());
933}
934 
935//===----------------------------------------------------------------------===//
936//     Extra additions to <memory>
937//===----------------------------------------------------------------------===//
938 
939// Implement make_unique according to N3656.
940 
941/// \brief Constructs a `new T()` with the given args and returns a
942///        `unique_ptr<T>` which owns the object.
943///
944/// Example:
945///
946///     auto p = make_unique<int>();
947///     auto p = make_unique<std::tuple<int, int>>(0, 1);
948template <class T, class... Args>
949typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
950make_unique(Args &&... args) {
951  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
4
←
Memory is allocated→
952}
953 
954/// \brief Constructs a `new T[n]` with the given args and returns a
955///        `unique_ptr<T[]>` which owns the object.
956///
957/// \param n size of the new array.
958///
959/// Example:
960///
961///     auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
962template <class T>
963typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
964                        std::unique_ptr<T>>::type
965make_unique(size_t n) {
966  return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
967}
968 
969/// This function isn't used and is only here to provide better compile errors.
970template <class T, class... Args>
971typename std::enable_if<std::extent<T>::value != 0>::type
972make_unique(Args &&...) = delete;
973 
974struct FreeDeleter {
975  void operator()(void* v) {
976    ::free(v);
977  }
978};
979 
980template<typename First, typename Second>
981struct pair_hash {
982  size_t operator()(const std::pair<First, Second> &P) const {
983    return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
984  }
985};
986 
987/// A functor like C++14's std::less<void> in its absence.
988struct less {
989  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
990    return std::forward<A>(a) < std::forward<B>(b);
991  }
992};
993 
994/// A functor like C++14's std::equal<void> in its absence.
995struct equal {
996  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
997    return std::forward<A>(a) == std::forward<B>(b);
998  }
999};
1000 
1001/// Binary functor that adapts to any other binary functor after dereferencing
1002/// operands.
1003template <typename T> struct deref {
1004  T func;
1005 
1006  // Could be further improved to cope with non-derivable functors and
1007  // non-binary functors (should be a variadic template member function
1008  // operator()).
1009  template <typename A, typename B>
1010  auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1011    assert(lhs)(static_cast <bool> (lhs) ? void (0) : __assert_fail ("lhs"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 1011, __extension__ __PRETTY_FUNCTION__));
1012    assert(rhs)(static_cast <bool> (rhs) ? void (0) : __assert_fail ("rhs"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 1012, __extension__ __PRETTY_FUNCTION__));
1013    return func(*lhs, *rhs);
1014  }
1015};
1016 
1017namespace detail {
1018 
1019template <typename R> class enumerator_iter;
1020 
1021template <typename R> struct result_pair {
1022  friend class enumerator_iter<R>;
1023 
1024  result_pair() = default;
1025  result_pair(std::size_t Index, IterOfRange<R> Iter)
1026      : Index(Index), Iter(Iter) {}
1027 
1028  result_pair<R> &operator=(const result_pair<R> &Other) {
1029    Index = Other.Index;
1030    Iter = Other.Iter;
1031    return *this;
1032  }
1033 
1034  std::size_t index() const { return Index; }
1035  const ValueOfRange<R> &value() const { return *Iter; }
1036  ValueOfRange<R> &value() { return *Iter; }
1037 
1038private:
1039  std::size_t Index = std::numeric_limits<std::size_t>::max();
1040  IterOfRange<R> Iter;
1041};
1042 
1043template <typename R>
1044class enumerator_iter
1045    : public iterator_facade_base<
1046          enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1047          typename std::iterator_traits<IterOfRange<R>>::difference_type,
1048          typename std::iterator_traits<IterOfRange<R>>::pointer,
1049          typename std::iterator_traits<IterOfRange<R>>::reference> {
1050  using result_type = result_pair<R>;
1051 
1052public:
1053  explicit enumerator_iter(IterOfRange<R> EndIter)
1054      : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1055 
1056  enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1057      : Result(Index, Iter) {}
1058 
1059  result_type &operator*() { return Result; }
1060  const result_type &operator*() const { return Result; }
1061 
1062  enumerator_iter<R> &operator++() {
1063    assert(Result.Index != std::numeric_limits<size_t>::max())(static_cast <bool> (Result.Index != std::numeric_limits
<size_t>::max()) ? void (0) : __assert_fail ("Result.Index != std::numeric_limits<size_t>::max()"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 1063, __extension__ __PRETTY_FUNCTION__));
1064    ++Result.Iter;
1065    ++Result.Index;
1066    return *this;
1067  }
1068 
1069  bool operator==(const enumerator_iter<R> &RHS) const {
1070    // Don't compare indices here, only iterators.  It's possible for an end
1071    // iterator to have different indices depending on whether it was created
1072    // by calling std::end() versus incrementing a valid iterator.
1073    return Result.Iter == RHS.Result.Iter;
1074  }
1075 
1076  enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1077    Result = Other.Result;
1078    return *this;
1079  }
1080 
1081private:
1082  result_type Result;
1083};
1084 
1085template <typename R> class enumerator {
1086public:
1087  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1088 
1089  enumerator_iter<R> begin() {
1090    return enumerator_iter<R>(0, std::begin(TheRange));
1091  }
1092 
1093  enumerator_iter<R> end() {
1094    return enumerator_iter<R>(std::end(TheRange));
1095  }
1096 
1097private:
1098  R TheRange;
1099};
1100 
1101} // end namespace detail
1102 
1103/// Given an input range, returns a new range whose values are are pair (A,B)
1104/// such that A is the 0-based index of the item in the sequence, and B is
1105/// the value from the original sequence.  Example:
1106///
1107/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1108/// for (auto X : enumerate(Items)) {
1109///   printf("Item %d - %c\n", X.index(), X.value());
1110/// }
1111///
1112/// Output:
1113///   Item 0 - A
1114///   Item 1 - B
1115///   Item 2 - C
1116///   Item 3 - D
1117///
1118template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1119  return detail::enumerator<R>(std::forward<R>(TheRange));
1120}
1121 
1122namespace detail {
1123 
1124template <typename F, typename Tuple, std::size_t... I>
1125auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1126    -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1127  return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1128}
1129 
1130} // end namespace detail
1131 
1132/// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1133/// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1134/// return the result.
1135template <typename F, typename Tuple>
1136auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1137    std::forward<F>(f), std::forward<Tuple>(t),
1138    build_index_impl<
1139        std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1140  using Indices = build_index_impl<
1141      std::tuple_size<typename std::decay<Tuple>::type>::value>;
1142 
1143  return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1144                                  Indices{});
1145}
1146 
1147} // end namespace llvm
1148 
1149#endif // LLVM_ADT_STLEXTRAS_H