/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/ELF/InputFiles.cpp

Bug Summary

File:	tools/lld/ELF/InputFiles.cpp
Warning:	line 966, column 16 The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'unsigned long long'

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 InputFiles.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 -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~svn345461/build-llvm/tools/lld/ELF -I /build/llvm-toolchain-snapshot-8~svn345461/tools/lld/ELF -I /build/llvm-toolchain-snapshot-8~svn345461/tools/lld/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/lld/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/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~svn345461/build-llvm/tools/lld/ELF -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-10-27-211344-32123-1 -x c++ /build/llvm-toolchain-snapshot-8~svn345461/tools/lld/ELF/InputFiles.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/ELF/InputFiles.cpp

→

1//===- InputFiles.cpp -----------------------------------------------------===//
2//
3//                             The LLVM Linker
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

10#include "InputFiles.h"
11#include "InputSection.h"
12#include "LinkerScript.h"
13#include "SymbolTable.h"
14#include "Symbols.h"
15#include "SyntheticSections.h"
16#include "lld/Common/ErrorHandler.h"
17#include "lld/Common/Memory.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/CodeGen/Analysis.h"
20#include "llvm/DebugInfo/DWARF/DWARFContext.h"
21#include "llvm/IR/LLVMContext.h"
22#include "llvm/IR/Module.h"
23#include "llvm/LTO/LTO.h"
24#include "llvm/MC/StringTableBuilder.h"
25#include "llvm/Object/ELFObjectFile.h"
26#include "llvm/Support/ARMAttributeParser.h"
27#include "llvm/Support/ARMBuildAttributes.h"
28#include "llvm/Support/Path.h"
29#include "llvm/Support/TarWriter.h"
30#include "llvm/Support/raw_ostream.h"

32using namespace llvm;
33using namespace llvm::ELF;
34using namespace llvm::object;
35using namespace llvm::sys;
36using namespace llvm::sys::fs;

38using namespace lld;
39using namespace lld::elf;

41bool InputFile::IsInGroup;
42uint32_t InputFile::NextGroupId;
43std::vector<BinaryFile *> elf::BinaryFiles;
44std::vector<BitcodeFile *> elf::BitcodeFiles;
45std::vector<LazyObjFile *> elf::LazyObjFiles;
46std::vector<InputFile *> elf::ObjectFiles;
47std::vector<InputFile *> elf::SharedFiles;

49TarWriter *elf::Tar;

51InputFile::InputFile(Kind K, MemoryBufferRef M)
  : MB(M), GroupId(NextGroupId), FileKind(K) {
// All files within the same --{start,end}-group get the same group ID.
// Otherwise, a new file will get a new group ID.
if (!IsInGroup)
  ++NextGroupId;
57}

59Optional<MemoryBufferRef> elf::readFile(StringRef Path) {
// The --chroot option changes our virtual root directory.
// This is useful when you are dealing with files created by --reproduce.
if (!Config->Chroot.empty() && Path.startswith("/"))
  Path = Saver.save(Config->Chroot + Path);

log(Path);

auto MBOrErr = MemoryBuffer::getFile(Path, -1, false);
if (auto EC = MBOrErr.getError()) {
  error("cannot open " + Path + ": " + EC.message());
  return None;
}

std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
MemoryBufferRef MBRef = MB->getMemBufferRef();
make<std::unique_ptr<MemoryBuffer>>(std::move(MB)); // take MB ownership

if (Tar)
  Tar->append(relativeToRoot(Path), MBRef.getBuffer());
return MBRef;
80}

82// Concatenates arguments to construct a string representing an error location.
83static std::string createFileLineMsg(StringRef Path, unsigned Line) {
std::string Filename = path::filename(Path);
std::string Lineno = ":" + std::to_string(Line);
if (Filename == Path)
  return Filename + Lineno;
return Filename + Lineno + " (" + Path.str() + Lineno + ")";
89}

91template <class ELFT>
92static std::string getSrcMsgAux(ObjFile<ELFT> &File, const Symbol &Sym,
                              InputSectionBase &Sec, uint64_t Offset) {
// In DWARF, functions and variables are stored to different places.
// First, lookup a function for a given offset.
if (Optional<DILineInfo> Info = File.getDILineInfo(&Sec, Offset))
  return createFileLineMsg(Info->FileName, Info->Line);

// If it failed, lookup again as a variable.
if (Optional<std::pair<std::string, unsigned>> FileLine =
        File.getVariableLoc(Sym.getName()))
  return createFileLineMsg(FileLine->first, FileLine->second);

// File.SourceFile contains STT_FILE symbol, and that is a last resort.
return File.SourceFile;
106}

108std::string InputFile::getSrcMsg(const Symbol &Sym, InputSectionBase &Sec,
                               uint64_t Offset) {
if (kind() != ObjKind)
  return "";
switch (Config->EKind) {
default:
  llvm_unreachable("Invalid kind")::llvm::llvm_unreachable_internal("Invalid kind", "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/ELF/InputFiles.cpp"
, 114);
case ELF32LEKind:
  return getSrcMsgAux(cast<ObjFile<ELF32LE>>(*this), Sym, Sec, Offset);
case ELF32BEKind:
  return getSrcMsgAux(cast<ObjFile<ELF32BE>>(*this), Sym, Sec, Offset);
case ELF64LEKind:
  return getSrcMsgAux(cast<ObjFile<ELF64LE>>(*this), Sym, Sec, Offset);
case ELF64BEKind:
  return getSrcMsgAux(cast<ObjFile<ELF64BE>>(*this), Sym, Sec, Offset);
}
124}

126template <class ELFT> void ObjFile<ELFT>::initializeDwarf() {
Dwarf = llvm::make_unique<DWARFContext>(make_unique<LLDDwarfObj<ELFT>>(this));
for (std::unique_ptr<DWARFUnit> &CU : Dwarf->compile_units()) {
  auto Report = [](Error Err) {
    handleAllErrors(std::move(Err),
                    [](ErrorInfoBase &Info) { warn(Info.message()); });
  };
  Expected<const DWARFDebugLine::LineTable *> ExpectedLT =
      Dwarf->getLineTableForUnit(CU.get(), Report);
  const DWARFDebugLine::LineTable *LT = nullptr;
  if (ExpectedLT)
    LT = *ExpectedLT;
  else
    Report(ExpectedLT.takeError());
  if (!LT)
    continue;
  LineTables.push_back(LT);

  // Loop over variable records and insert them to VariableLoc.
  for (const auto &Entry : CU->dies()) {
    DWARFDie Die(CU.get(), &Entry);
    // Skip all tags that are not variables.
    if (Die.getTag() != dwarf::DW_TAG_variable)
      continue;

    // Skip if a local variable because we don't need them for generating
    // error messages. In general, only non-local symbols can fail to be
    // linked.
    if (!dwarf::toUnsigned(Die.find(dwarf::DW_AT_external), 0))
      continue;

    // Get the source filename index for the variable.
    unsigned File = dwarf::toUnsigned(Die.find(dwarf::DW_AT_decl_file), 0);
    if (!LT->hasFileAtIndex(File))
      continue;

    // Get the line number on which the variable is declared.
    unsigned Line = dwarf::toUnsigned(Die.find(dwarf::DW_AT_decl_line), 0);

    // Here we want to take the variable name to add it into VariableLoc.
    // Variable can have regular and linkage name associated. At first, we try
    // to get linkage name as it can be different, for example when we have
    // two variables in different namespaces of the same object. Use common
    // name otherwise, but handle the case when it also absent in case if the
    // input object file lacks some debug info.
    StringRef Name =
        dwarf::toString(Die.find(dwarf::DW_AT_linkage_name),
                        dwarf::toString(Die.find(dwarf::DW_AT_name), ""));
    if (!Name.empty())
      VariableLoc.insert({Name, {LT, File, Line}});
  }
}
178}

180// Returns the pair of file name and line number describing location of data
181// object (variable, array, etc) definition.
182template <class ELFT>
183Optional<std::pair<std::string, unsigned>>
184ObjFile<ELFT>::getVariableLoc(StringRef Name) {
llvm::call_once(InitDwarfLine, [this]() { initializeDwarf(); });

// Return if we have no debug information about data object.
auto It = VariableLoc.find(Name);
if (It == VariableLoc.end())
  return None;

// Take file name string from line table.
std::string FileName;
if (!It->second.LT->getFileNameByIndex(
        It->second.File, nullptr,
        DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, FileName))
  return None;

return std::make_pair(FileName, It->second.Line);
200}

202// Returns source line information for a given offset
203// using DWARF debug info.
204template <class ELFT>
205Optional<DILineInfo> ObjFile<ELFT>::getDILineInfo(InputSectionBase *S,
                                                uint64_t Offset) {
llvm::call_once(InitDwarfLine, [this]() { initializeDwarf(); });

// Use fake address calcuated by adding section file offset and offset in
// section. See comments for ObjectInfo class.
DILineInfo Info;
for (const llvm::DWARFDebugLine::LineTable *LT : LineTables)
  if (LT->getFileLineInfoForAddress(
          S->getOffsetInFile() + Offset, nullptr,
          DILineInfoSpecifier::FileLineInfoKind::AbsoluteFilePath, Info))
    return Info;
return None;
218}

220// Returns "<internal>", "foo.a(bar.o)" or "baz.o".
221std::string lld::toString(const InputFile *F) {
if (!F)
  return "<internal>";

if (F->ToStringCache.empty()) {
  if (F->ArchiveName.empty())
    F->ToStringCache = F->getName();
  else
    F->ToStringCache = (F->ArchiveName + "(" + F->getName() + ")").str();
}
return F->ToStringCache;
232}

234template <class ELFT>
235ELFFileBase<ELFT>::ELFFileBase(Kind K, MemoryBufferRef MB) : InputFile(K, MB) {
if (ELFT::TargetEndianness == support::little)
  EKind = ELFT::Is64Bits ? ELF64LEKind : ELF32LEKind;
else
  EKind = ELFT::Is64Bits ? ELF64BEKind : ELF32BEKind;

EMachine = getObj().getHeader()->e_machine;
OSABI = getObj().getHeader()->e_ident[llvm::ELF::EI_OSABI];
243}

245template <class ELFT>
246typename ELFT::SymRange ELFFileBase<ELFT>::getGlobalELFSyms() {
return makeArrayRef(ELFSyms.begin() + FirstGlobal, ELFSyms.end());
248}

250template <class ELFT>
251uint32_t ELFFileBase<ELFT>::getSectionIndex(const Elf_Sym &Sym) const {
return CHECK(getObj().getSectionIndex(&Sym, ELFSyms, SymtabSHNDX), this)check2((getObj().getSectionIndex(&Sym, ELFSyms, SymtabSHNDX
)), [&] { return toString(this); });
253}

255template <class ELFT>
256void ELFFileBase<ELFT>::initSymtab(ArrayRef<Elf_Shdr> Sections,
                                 const Elf_Shdr *Symtab) {
FirstGlobal = Symtab->sh_info;
ELFSyms = CHECK(getObj().symbols(Symtab), this)check2((getObj().symbols(Symtab)), [&] { return toString(
this); });
if (FirstGlobal == 0 || FirstGlobal > ELFSyms.size())
  fatal(toString(this) + ": invalid sh_info in symbol table");

StringTable =
    CHECK(getObj().getStringTableForSymtab(*Symtab, Sections), this)check2((getObj().getStringTableForSymtab(*Symtab, Sections)),
 [&] { return toString(this); });
265}

267template <class ELFT>
268ObjFile<ELFT>::ObjFile(MemoryBufferRef M, StringRef ArchiveName)
  : ELFFileBase<ELFT>(Base::ObjKind, M) {
this->ArchiveName = ArchiveName;
271}

273template <class ELFT> ArrayRef<Symbol *> ObjFile<ELFT>::getLocalSymbols() {
if (this->Symbols.empty())
  return {};
return makeArrayRef(this->Symbols).slice(1, this->FirstGlobal - 1);
277}

279template <class ELFT> ArrayRef<Symbol *> ObjFile<ELFT>::getGlobalSymbols() {
return makeArrayRef(this->Symbols).slice(this->FirstGlobal);
281}

283template <class ELFT>
284void ObjFile<ELFT>::parse(DenseSet<CachedHashStringRef> &ComdatGroups) {
// Read a section table. JustSymbols is usually false.
if (this->JustSymbols)
  initializeJustSymbols();
else
  initializeSections(ComdatGroups);

// Read a symbol table.
initializeSymbols();
293}

295// Sections with SHT_GROUP and comdat bits define comdat section groups.
296// They are identified and deduplicated by group name. This function
297// returns a group name.
298template <class ELFT>
299StringRef ObjFile<ELFT>::getShtGroupSignature(ArrayRef<Elf_Shdr> Sections,
                                            const Elf_Shdr &Sec) {
// Group signatures are stored as symbol names in object files.
// sh_info contains a symbol index, so we fetch a symbol and read its name.
if (this->ELFSyms.empty())
  this->initSymtab(
      Sections, CHECK(object::getSection<ELFT>(Sections, Sec.sh_link), this)check2((object::getSection<ELFT>(Sections, Sec.sh_link)
), [&] { return toString(this); }));

const Elf_Sym *Sym =
    CHECK(object::getSymbol<ELFT>(this->ELFSyms, Sec.sh_info), this)check2((object::getSymbol<ELFT>(this->ELFSyms, Sec.sh_info
)), [&] { return toString(this); });
StringRef Signature = CHECK(Sym->getName(this->StringTable), this)check2((Sym->getName(this->StringTable)), [&] { return
 toString(this); });

// As a special case, if a symbol is a section symbol and has no name,
// we use a section name as a signature.
//
// Such SHT_GROUP sections are invalid from the perspective of the ELF
// standard, but GNU gold 1.14 (the newest version as of July 2017) or
// older produce such sections as outputs for the -r option, so we need
// a bug-compatibility.
if (Signature.empty() && Sym->getType() == STT_SECTION)
  return getSectionName(Sec);
return Signature;
321}

323template <class ELFT>
324ArrayRef<typename ObjFile<ELFT>::Elf_Word>
325ObjFile<ELFT>::getShtGroupEntries(const Elf_Shdr &Sec) {
const ELFFile<ELFT> &Obj = this->getObj();
ArrayRef<Elf_Word> Entries =
    CHECK(Obj.template getSectionContentsAsArray<Elf_Word>(&Sec), this)check2((Obj.template getSectionContentsAsArray<Elf_Word>
(&Sec)), [&] { return toString(this); });
if (Entries.empty() || Entries[0] != GRP_COMDAT)
  fatal(toString(this) + ": unsupported SHT_GROUP format");
return Entries.slice(1);
332}

334template <class ELFT> bool ObjFile<ELFT>::shouldMerge(const Elf_Shdr &Sec) {
// On a regular link we don't merge sections if -O0 (default is -O1). This
// sometimes makes the linker significantly faster, although the output will
// be bigger.
//
// Doing the same for -r would create a problem as it would combine sections
// with different sh_entsize. One option would be to just copy every SHF_MERGE
// section as is to the output. While this would produce a valid ELF file with
// usable SHF_MERGE sections, tools like (llvm-)?dwarfdump get confused when
// they see two .debug_str. We could have separate logic for combining
// SHF_MERGE sections based both on their name and sh_entsize, but that seems
// to be more trouble than it is worth. Instead, we just use the regular (-O1)
// logic for -r.
if (Config->Optimize == 0 && !Config->Relocatable)
  return false;

// A mergeable section with size 0 is useless because they don't have
// any data to merge. A mergeable string section with size 0 can be
// argued as invalid because it doesn't end with a null character.
// We'll avoid a mess by handling them as if they were non-mergeable.
if (Sec.sh_size == 0)
  return false;

// Check for sh_entsize. The ELF spec is not clear about the zero
// sh_entsize. It says that "the member [sh_entsize] contains 0 if
// the section does not hold a table of fixed-size entries". We know
// that Rust 1.13 produces a string mergeable section with a zero
// sh_entsize. Here we just accept it rather than being picky about it.
uint64_t EntSize = Sec.sh_entsize;
if (EntSize == 0)
  return false;
if (Sec.sh_size % EntSize)
  fatal(toString(this) +
        ": SHF_MERGE section size must be a multiple of sh_entsize");

uint64_t Flags = Sec.sh_flags;
if (!(Flags & SHF_MERGE))
  return false;
if (Flags & SHF_WRITE)
  fatal(toString(this) + ": writable SHF_MERGE section is not supported");

return true;
376}

378// This is for --just-symbols.
379//
380// --just-symbols is a very minor feature that allows you to link your
381// output against other existing program, so that if you load both your
382// program and the other program into memory, your output can refer the
383// other program's symbols.
384//
385// When the option is given, we link "just symbols". The section table is
386// initialized with null pointers.
387template <class ELFT> void ObjFile<ELFT>::initializeJustSymbols() {
ArrayRef<Elf_Shdr> ObjSections = CHECK(this->getObj().sections(), this)check2((this->getObj().sections()), [&] { return toString
(this); });
this->Sections.resize(ObjSections.size());

for (const Elf_Shdr &Sec : ObjSections) {
  if (Sec.sh_type != SHT_SYMTAB)
    continue;
  this->initSymtab(ObjSections, &Sec);
  return;
}
397}

399template <class ELFT>
400void ObjFile<ELFT>::initializeSections(
  DenseSet<CachedHashStringRef> &ComdatGroups) {
const ELFFile<ELFT> &Obj = this->getObj();

ArrayRef<Elf_Shdr> ObjSections = CHECK(Obj.sections(), this)check2((Obj.sections()), [&] { return toString(this); });
uint64_t Size = ObjSections.size();
this->Sections.resize(Size);
this->SectionStringTable =
    CHECK(Obj.getSectionStringTable(ObjSections), this)check2((Obj.getSectionStringTable(ObjSections)), [&] { return
 toString(this); });

for (size_t I = 0, E = ObjSections.size(); I < E; I++) {
  if (this->Sections[I] == &InputSection::Discarded)
    continue;
  const Elf_Shdr &Sec = ObjSections[I];

  if (Sec.sh_type == ELF::SHT_LLVM_CALL_GRAPH_PROFILE)
    CGProfile = check(
        this->getObj().template getSectionContentsAsArray<Elf_CGProfile>(
            &Sec));

  // SHF_EXCLUDE'ed sections are discarded by the linker. However,
  // if -r is given, we'll let the final link discard such sections.
  // This is compatible with GNU.
  if ((Sec.sh_flags & SHF_EXCLUDE) && !Config->Relocatable) {
    if (Sec.sh_type == SHT_LLVM_ADDRSIG) {
      // We ignore the address-significance table if we know that the object
      // file was created by objcopy or ld -r. This is because these tools
      // will reorder the symbols in the symbol table, invalidating the data
      // in the address-significance table, which refers to symbols by index.
      if (Sec.sh_link != 0)
        this->AddrsigSec = &Sec;
      else if (Config->ICF == ICFLevel::Safe)
        warn(toString(this) + ": --icf=safe is incompatible with object "
                              "files created using objcopy or ld -r");
    }
    this->Sections[I] = &InputSection::Discarded;
    continue;
  }

  switch (Sec.sh_type) {
  case SHT_GROUP: {
    // De-duplicate section groups by their signatures.
    StringRef Signature = getShtGroupSignature(ObjSections, Sec);
    bool IsNew = ComdatGroups.insert(CachedHashStringRef(Signature)).second;
    this->Sections[I] = &InputSection::Discarded;

    // We only support GRP_COMDAT type of group. Get the all entries of the
    // section here to let getShtGroupEntries to check the type early for us.
    ArrayRef<Elf_Word> Entries = getShtGroupEntries(Sec);

    // If it is a new section group, we want to keep group members.
    // Group leader sections, which contain indices of group members, are
    // discarded because they are useless beyond this point. The only
    // exception is the -r option because in order to produce re-linkable
    // object files, we want to pass through basically everything.
    if (IsNew) {
      if (Config->Relocatable)
        this->Sections[I] = createInputSection(Sec);
      continue;
    }

    // Otherwise, discard group members.
    for (uint32_t SecIndex : Entries) {
      if (SecIndex >= Size)
        fatal(toString(this) +
              ": invalid section index in group: " + Twine(SecIndex));
      this->Sections[SecIndex] = &InputSection::Discarded;
    }
    break;
  }
  case SHT_SYMTAB:
    this->initSymtab(ObjSections, &Sec);
    break;
  case SHT_SYMTAB_SHNDX:
    this->SymtabSHNDX = CHECK(Obj.getSHNDXTable(Sec, ObjSections), this)check2((Obj.getSHNDXTable(Sec, ObjSections)), [&] { return
 toString(this); });
    break;
  case SHT_STRTAB:
  case SHT_NULL:
    break;
  default:
    this->Sections[I] = createInputSection(Sec);
  }

  // .ARM.exidx sections have a reverse dependency on the InputSection they
  // have a SHF_LINK_ORDER dependency, this is identified by the sh_link.
  if (Sec.sh_flags & SHF_LINK_ORDER) {
    InputSectionBase *LinkSec = nullptr;
    if (Sec.sh_link < this->Sections.size())
      LinkSec = this->Sections[Sec.sh_link];
    if (!LinkSec)
      fatal(toString(this) +
            ": invalid sh_link index: " + Twine(Sec.sh_link));

    InputSection *IS = cast<InputSection>(this->Sections[I]);
    LinkSec->DependentSections.push_back(IS);
    if (!isa<InputSection>(LinkSec))
      error("a section " + IS->Name +
            " with SHF_LINK_ORDER should not refer a non-regular "
            "section: " +
            toString(LinkSec));
  }
}
502}

504// For ARM only, to set the EF_ARM_ABI_FLOAT_SOFT or EF_ARM_ABI_FLOAT_HARD
505// flag in the ELF Header we need to look at Tag_ABI_VFP_args to find out how
506// the input objects have been compiled.
507static void updateARMVFPArgs(const ARMAttributeParser &Attributes,
                           const InputFile *F) {
if (!Attributes.hasAttribute(ARMBuildAttrs::ABI_VFP_args))
  // If an ABI tag isn't present then it is implicitly given the value of 0
  // which maps to ARMBuildAttrs::BaseAAPCS. However many assembler files,
  // including some in glibc that don't use FP args (and should have value 3)
  // don't have the attribute so we do not consider an implicit value of 0
  // as a clash.
  return;

unsigned VFPArgs = Attributes.getAttributeValue(ARMBuildAttrs::ABI_VFP_args);
ARMVFPArgKind Arg;
switch (VFPArgs) {
case ARMBuildAttrs::BaseAAPCS:
  Arg = ARMVFPArgKind::Base;
  break;
case ARMBuildAttrs::HardFPAAPCS:
  Arg = ARMVFPArgKind::VFP;
  break;
case ARMBuildAttrs::ToolChainFPPCS:
  // Tool chain specific convention that conforms to neither AAPCS variant.
  Arg = ARMVFPArgKind::ToolChain;
  break;
case ARMBuildAttrs::CompatibleFPAAPCS:
  // Object compatible with all conventions.
  return;
default:
  error(toString(F) + ": unknown Tag_ABI_VFP_args value: " + Twine(VFPArgs));
  return;
}
// Follow ld.bfd and error if there is a mix of calling conventions.
if (Config->ARMVFPArgs != Arg && Config->ARMVFPArgs != ARMVFPArgKind::Default)
  error(toString(F) + ": incompatible Tag_ABI_VFP_args");
else
  Config->ARMVFPArgs = Arg;
542}

544// The ARM support in lld makes some use of instructions that are not available
545// on all ARM architectures. Namely:
546// - Use of BLX instruction for interworking between ARM and Thumb state.
547// - Use of the extended Thumb branch encoding in relocation.
548// - Use of the MOVT/MOVW instructions in Thumb Thunks.
549// The ARM Attributes section contains information about the architecture chosen
550// at compile time. We follow the convention that if at least one input object
551// is compiled with an architecture that supports these features then lld is
552// permitted to use them.
553static void updateSupportedARMFeatures(const ARMAttributeParser &Attributes) {
if (!Attributes.hasAttribute(ARMBuildAttrs::CPU_arch))
  return;
auto Arch = Attributes.getAttributeValue(ARMBuildAttrs::CPU_arch);
switch (Arch) {
case ARMBuildAttrs::Pre_v4:
case ARMBuildAttrs::v4:
case ARMBuildAttrs::v4T:
  // Architectures prior to v5 do not support BLX instruction
  break;
case ARMBuildAttrs::v5T:
case ARMBuildAttrs::v5TE:
case ARMBuildAttrs::v5TEJ:
case ARMBuildAttrs::v6:
case ARMBuildAttrs::v6KZ:
case ARMBuildAttrs::v6K:
  Config->ARMHasBlx = true;
  // Architectures used in pre-Cortex processors do not support
  // The J1 = 1 J2 = 1 Thumb branch range extension, with the exception
  // of Architecture v6T2 (arm1156t2-s and arm1156t2f-s) that do.
  break;
default:
  // All other Architectures have BLX and extended branch encoding
  Config->ARMHasBlx = true;
  Config->ARMJ1J2BranchEncoding = true;
  if (Arch != ARMBuildAttrs::v6_M && Arch != ARMBuildAttrs::v6S_M)
    // All Architectures used in Cortex processors with the exception
    // of v6-M and v6S-M have the MOVT and MOVW instructions.
    Config->ARMHasMovtMovw = true;
  break;
}
584}

586template <class ELFT>
587InputSectionBase *ObjFile<ELFT>::getRelocTarget(const Elf_Shdr &Sec) {
uint32_t Idx = Sec.sh_info;
if (Idx >= this->Sections.size())
  fatal(toString(this) + ": invalid relocated section index: " + Twine(Idx));
InputSectionBase *Target = this->Sections[Idx];

// Strictly speaking, a relocation section must be included in the
// group of the section it relocates. However, LLVM 3.3 and earlier
// would fail to do so, so we gracefully handle that case.
if (Target == &InputSection::Discarded)
  return nullptr;

if (!Target)
  fatal(toString(this) + ": unsupported relocation reference");
return Target;
602}

604// Create a regular InputSection class that has the same contents
605// as a given section.
606static InputSection *toRegularSection(MergeInputSection *Sec) {
return make<InputSection>(Sec->File, Sec->Flags, Sec->Type, Sec->Alignment,
                          Sec->data(), Sec->Name);
609}

611template <class ELFT>
612InputSectionBase *ObjFile<ELFT>::createInputSection(const Elf_Shdr &Sec) {
StringRef Name = getSectionName(Sec);

switch (Sec.sh_type) {
case SHT_ARM_ATTRIBUTES: {
  if (Config->EMachine != EM_ARM)
    break;
  ARMAttributeParser Attributes;
  ArrayRef<uint8_t> Contents = check(this->getObj().getSectionContents(&Sec));
  Attributes.Parse(Contents, /*isLittle*/ Config->EKind == ELF32LEKind);
  updateSupportedARMFeatures(Attributes);
  updateARMVFPArgs(Attributes, this);

  // FIXME: Retain the first attribute section we see. The eglibc ARM
  // dynamic loaders require the presence of an attribute section for dlopen
  // to work. In a full implementation we would merge all attribute sections.
  if (In.ARMAttributes == nullptr) {
    In.ARMAttributes = make<InputSection>(*this, Sec, Name);
    return In.ARMAttributes;
  }
  return &InputSection::Discarded;
}
case SHT_RELA:
case SHT_REL: {
  // Find a relocation target section and associate this section with that.
  // Target may have been discarded if it is in a different section group
  // and the group is discarded, even though it's a violation of the
  // spec. We handle that situation gracefully by discarding dangling
  // relocation sections.
  InputSectionBase *Target = getRelocTarget(Sec);
  if (!Target)
    return nullptr;

  // This section contains relocation information.
  // If -r is given, we do not interpret or apply relocation
  // but just copy relocation sections to output.
  if (Config->Relocatable)
    return make<InputSection>(*this, Sec, Name);

  if (Target->FirstRelocation)
    fatal(toString(this) +
          ": multiple relocation sections to one section are not supported");

  // ELF spec allows mergeable sections with relocations, but they are
  // rare, and it is in practice hard to merge such sections by contents,
  // because applying relocations at end of linking changes section
  // contents. So, we simply handle such sections as non-mergeable ones.
  // Degrading like this is acceptable because section merging is optional.
  if (auto *MS = dyn_cast<MergeInputSection>(Target)) {
    Target = toRegularSection(MS);
    this->Sections[Sec.sh_info] = Target;
  }

  if (Sec.sh_type == SHT_RELA) {
    ArrayRef<Elf_Rela> Rels = CHECK(this->getObj().relas(&Sec), this)check2((this->getObj().relas(&Sec)), [&] { return toString
(this); });
    Target->FirstRelocation = Rels.begin();
    Target->NumRelocations = Rels.size();
    Target->AreRelocsRela = true;
  } else {
    ArrayRef<Elf_Rel> Rels = CHECK(this->getObj().rels(&Sec), this)check2((this->getObj().rels(&Sec)), [&] { return toString
(this); });
    Target->FirstRelocation = Rels.begin();
    Target->NumRelocations = Rels.size();
    Target->AreRelocsRela = false;
  }
  assert(isUInt<31>(Target->NumRelocations))((isUInt<31>(Target->NumRelocations)) ? static_cast<
void> (0) : __assert_fail ("isUInt<31>(Target->NumRelocations)"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/ELF/InputFiles.cpp"
, 676, __PRETTY_FUNCTION__));

  // Relocation sections processed by the linker are usually removed
  // from the output, so returning `nullptr` for the normal case.
  // However, if -emit-relocs is given, we need to leave them in the output.
  // (Some post link analysis tools need this information.)
  if (Config->EmitRelocs) {
    InputSection *RelocSec = make<InputSection>(*this, Sec, Name);
    // We will not emit relocation section if target was discarded.
    Target->DependentSections.push_back(RelocSec);
    return RelocSec;
  }
  return nullptr;
}
}

// The GNU linker uses .note.GNU-stack section as a marker indicating
// that the code in the object file does not expect that the stack is
// executable (in terms of NX bit). If all input files have the marker,
// the GNU linker adds a PT_GNU_STACK segment to tells the loader to
// make the stack non-executable. Most object files have this section as
// of 2017.
//
// But making the stack non-executable is a norm today for security
// reasons. Failure to do so may result in a serious security issue.
// Therefore, we make LLD always add PT_GNU_STACK unless it is
// explicitly told to do otherwise (by -z execstack). Because the stack
// executable-ness is controlled solely by command line options,
// .note.GNU-stack sections are simply ignored.
if (Name == ".note.GNU-stack")
  return &InputSection::Discarded;

// Split stacks is a feature to support a discontiguous stack,
// commonly used in the programming language Go. For the details,
// see https://gcc.gnu.org/wiki/SplitStacks. An object file compiled
// for split stack will include a .note.GNU-split-stack section.
if (Name == ".note.GNU-split-stack") {
  if (Config->Relocatable) {
    error("cannot mix split-stack and non-split-stack in a relocatable link");
    return &InputSection::Discarded;
  }
  this->SplitStack = true;
  return &InputSection::Discarded;
}

// An object file cmpiled for split stack, but where some of the
// functions were compiled with the no_split_stack_attribute will
// include a .note.GNU-no-split-stack section.
if (Name == ".note.GNU-no-split-stack") {
  this->SomeNoSplitStack = true;
  return &InputSection::Discarded;
}

// The linkonce feature is a sort of proto-comdat. Some glibc i386 object
// files contain definitions of symbol "__x86.get_pc_thunk.bx" in linkonce
// sections. Drop those sections to avoid duplicate symbol errors.
// FIXME: This is glibc PR20543, we should remove this hack once that has been
// fixed for a while.
if (Name.startswith(".gnu.linkonce."))
  return &InputSection::Discarded;

// If we are creating a new .build-id section, strip existing .build-id
// sections so that the output won't have more than one .build-id.
// This is not usually a problem because input object files normally don't
// have .build-id sections, but you can create such files by
// "ld.{bfd,gold,lld} -r --build-id", and we want to guard against it.
if (Name == ".note.gnu.build-id" && Config->BuildId != BuildIdKind::None)
  return &InputSection::Discarded;

// The linker merges EH (exception handling) frames and creates a
// .eh_frame_hdr section for runtime. So we handle them with a special
// class. For relocatable outputs, they are just passed through.
if (Name == ".eh_frame" && !Config->Relocatable)
  return make<EhInputSection>(*this, Sec, Name);

if (shouldMerge(Sec))
  return make<MergeInputSection>(*this, Sec, Name);
return make<InputSection>(*this, Sec, Name);
754}

756template <class ELFT>
757StringRef ObjFile<ELFT>::getSectionName(const Elf_Shdr &Sec) {
return CHECK(this->getObj().getSectionName(&Sec, SectionStringTable), this)check2((this->getObj().getSectionName(&Sec, SectionStringTable
)), [&] { return toString(this); });
759}

761template <class ELFT> void ObjFile<ELFT>::initializeSymbols() {
this->Symbols.reserve(this->ELFSyms.size());
for (const Elf_Sym &Sym : this->ELFSyms)
  this->Symbols.push_back(createSymbol(&Sym));
765}

767template <class ELFT> Symbol *ObjFile<ELFT>::createSymbol(const Elf_Sym *Sym) {
int Binding = Sym->getBinding();

uint32_t SecIdx = this->getSectionIndex(*Sym);
if (SecIdx >= this->Sections.size())
  fatal(toString(this) + ": invalid section index: " + Twine(SecIdx));

InputSectionBase *Sec = this->Sections[SecIdx];
uint8_t StOther = Sym->st_other;
uint8_t Type = Sym->getType();
uint64_t Value = Sym->st_value;
uint64_t Size = Sym->st_size;

if (Binding == STB_LOCAL) {
  if (Sym->getType() == STT_FILE)
    SourceFile = CHECK(Sym->getName(this->StringTable), this)check2((Sym->getName(this->StringTable)), [&] { return
 toString(this); });

  if (this->StringTable.size() <= Sym->st_name)
    fatal(toString(this) + ": invalid symbol name offset");

  StringRefZ Name = this->StringTable.data() + Sym->st_name;
  if (Sym->st_shndx == SHN_UNDEF)
    return make<Undefined>(this, Name, Binding, StOther, Type);

  return make<Defined>(this, Name, Binding, StOther, Type, Value, Size, Sec);
}

StringRef Name = CHECK(Sym->getName(this->StringTable), this)check2((Sym->getName(this->StringTable)), [&] { return
 toString(this); });

switch (Sym->st_shndx) {
case SHN_UNDEF:
  return Symtab->addUndefined<ELFT>(Name, Binding, StOther, Type,
                                    /*CanOmitFromDynSym=*/false, this);
case SHN_COMMON:
  if (Value == 0 || Value >= UINT32_MAX(4294967295U))
    fatal(toString(this) + ": common symbol '" + Name +
          "' has invalid alignment: " + Twine(Value));
  return Symtab->addCommon(Name, Size, Value, Binding, StOther, Type, *this);
}

switch (Binding) {
default:
  fatal(toString(this) + ": unexpected binding: " + Twine(Binding));
case STB_GLOBAL:
case STB_WEAK:
case STB_GNU_UNIQUE:
  if (Sec == &InputSection::Discarded)
    return Symtab->addUndefined<ELFT>(Name, Binding, StOther, Type,
                                      /*CanOmitFromDynSym=*/false, this);
  return Symtab->addDefined(Name, StOther, Type, Value, Size, Binding, Sec,
                            this);
}
819}

821ArchiveFile::ArchiveFile(std::unique_ptr<Archive> &&File)
  : InputFile(ArchiveKind, File->getMemoryBufferRef()),
    File(std::move(File)) {}

825template <class ELFT> void ArchiveFile::parse() {
for (const Archive::Symbol &Sym : File->symbols())
  Symtab->addLazyArchive<ELFT>(Sym.getName(), *this, Sym);
828}

830// Returns a buffer pointing to a member file containing a given symbol.
831InputFile *ArchiveFile::fetch(const Archive::Symbol &Sym) {
Archive::Child C =
    CHECK(Sym.getMember(), toString(this) +check2((Sym.getMember()), [&] { return toString(toString(
this) + ": could not get the member for symbol " + Sym.getName
()); })
                               ": could not get the member for symbol " +check2((Sym.getMember()), [&] { return toString(toString(
this) + ": could not get the member for symbol " + Sym.getName
()); })
                               Sym.getName())check2((Sym.getMember()), [&] { return toString(toString(
this) + ": could not get the member for symbol " + Sym.getName
()); });

if (!Seen.insert(C.getChildOffset()).second)
  return nullptr;

MemoryBufferRef MB =
    CHECK(C.getMemoryBufferRef(),check2((C.getMemoryBufferRef()), [&] { return toString(toString
(this) + ": could not get the buffer for the member defining symbol "
 + Sym.getName()); })
          toString(this) +check2((C.getMemoryBufferRef()), [&] { return toString(toString
(this) + ": could not get the buffer for the member defining symbol "
 + Sym.getName()); })
              ": could not get the buffer for the member defining symbol " +check2((C.getMemoryBufferRef()), [&] { return toString(toString
(this) + ": could not get the buffer for the member defining symbol "
 + Sym.getName()); })
              Sym.getName())check2((C.getMemoryBufferRef()), [&] { return toString(toString
(this) + ": could not get the buffer for the member defining symbol "
 + Sym.getName()); });

if (Tar && C.getParent()->isThin())
  Tar->append(relativeToRoot(CHECK(C.getFullName(), this)check2((C.getFullName()), [&] { return toString(this); })), MB.getBuffer());

InputFile *File = createObjectFile(
    MB, getName(), C.getParent()->isThin() ? 0 : C.getChildOffset());
File->GroupId = GroupId;
return File;
853}

855template <class ELFT>
856SharedFile<ELFT>::SharedFile(MemoryBufferRef M, StringRef DefaultSoName)
  : ELFFileBase<ELFT>(Base::SharedKind, M), SoName(DefaultSoName),
    IsNeeded(!Config->AsNeeded) {}

860// Partially parse the shared object file so that we can call
861// getSoName on this object.
862template <class ELFT> void SharedFile<ELFT>::parseSoName() {
const Elf_Shdr *DynamicSec = nullptr;
const ELFFile<ELFT> Obj = this->getObj();
ArrayRef<Elf_Shdr> Sections = CHECK(Obj.sections(), this)check2((Obj.sections()), [&] { return toString(this); });

// Search for .dynsym, .dynamic, .symtab, .gnu.version and .gnu.version_d.
for (const Elf_Shdr &Sec : Sections) {
  switch (Sec.sh_type) {
  default:
    continue;
  case SHT_DYNSYM:
    this->initSymtab(Sections, &Sec);
    break;
  case SHT_DYNAMIC:
    DynamicSec = &Sec;
    break;
  case SHT_SYMTAB_SHNDX:
    this->SymtabSHNDX = CHECK(Obj.getSHNDXTable(Sec, Sections), this)check2((Obj.getSHNDXTable(Sec, Sections)), [&] { return toString
(this); });
    break;
  case SHT_GNU_versym:
    this->VersymSec = &Sec;
    break;
  case SHT_GNU_verdef:
    this->VerdefSec = &Sec;
    break;
  }
}

if (this->VersymSec && this->ELFSyms.empty())
  error("SHT_GNU_versym should be associated with symbol table");

// Search for a DT_SONAME tag to initialize this->SoName.
if (!DynamicSec)
  return;
ArrayRef<Elf_Dyn> Arr =
    CHECK(Obj.template getSectionContentsAsArray<Elf_Dyn>(DynamicSec), this)check2((Obj.template getSectionContentsAsArray<Elf_Dyn>
(DynamicSec)), [&] { return toString(this); });
for (const Elf_Dyn &Dyn : Arr) {
  if (Dyn.d_tag == DT_SONAME) {
    uint64_t Val = Dyn.getVal();
    if (Val >= this->StringTable.size())
      fatal(toString(this) + ": invalid DT_SONAME entry");
    SoName = this->StringTable.data() + Val;
    return;
  }
}
907}

909// Parses ".gnu.version" section which is a parallel array for the symbol table.
910// If a given file doesn't have ".gnu.version" section, returns VER_NDX_GLOBAL.
911template <class ELFT> std::vector<uint32_t> SharedFile<ELFT>::parseVersyms() {
size_t Size = this->ELFSyms.size() - this->FirstGlobal;
if (!VersymSec)
  return std::vector<uint32_t>(Size, VER_NDX_GLOBAL);

const char *Base = this->MB.getBuffer().data();
const Elf_Versym *Versym =
    reinterpret_cast<const Elf_Versym *>(Base + VersymSec->sh_offset) +
    this->FirstGlobal;

std::vector<uint32_t> Ret(Size);
for (size_t I = 0; I < Size; ++I)
  Ret[I] = Versym[I].vs_index;
return Ret;
925}

927// Parse the version definitions in the object file if present. Returns a vector
928// whose nth element contains a pointer to the Elf_Verdef for version identifier
929// n. Version identifiers that are not definitions map to nullptr.
930template <class ELFT>
931std::vector<const typename ELFT::Verdef *> SharedFile<ELFT>::parseVerdefs() {
if (!VerdefSec)
  return {};

// We cannot determine the largest verdef identifier without inspecting
// every Elf_Verdef, but both bfd and gold assign verdef identifiers
// sequentially starting from 1, so we predict that the largest identifier
// will be VerdefCount.
unsigned VerdefCount = VerdefSec->sh_info;
std::vector<const Elf_Verdef *> Verdefs(VerdefCount + 1);

// Build the Verdefs array by following the chain of Elf_Verdef objects
// from the start of the .gnu.version_d section.
const char *Base = this->MB.getBuffer().data();
const char *Verdef = Base + VerdefSec->sh_offset;
for (unsigned I = 0; I != VerdefCount; ++I) {
  auto *CurVerdef = reinterpret_cast<const Elf_Verdef *>(Verdef);
  Verdef += CurVerdef->vd_next;
  unsigned VerdefIndex = CurVerdef->vd_ndx;
  Verdefs.resize(VerdefIndex + 1);
  Verdefs[VerdefIndex] = CurVerdef;
}

return Verdefs;
955}

957// We do not usually care about alignments of data in shared object
958// files because the loader takes care of it. However, if we promote a
959// DSO symbol to point to .bss due to copy relocation, we need to keep
960// the original alignment requirements. We infer it in this function.
961template <class ELFT>
962uint32_t SharedFile<ELFT>::getAlignment(ArrayRef<Elf_Shdr> Sections,
                                      const Elf_Sym &Sym) {
uint64_t Ret = UINT64_MAX(18446744073709551615UL);
if (Sym.st_value)
1
Assuming the condition is true→
2
←
Taking true branch→
  Ret = 1ULL << countTrailingZeros((uint64_t)Sym.st_value);
3
←
Calling 'countTrailingZeros<unsigned long>'→
10
←
Returning from 'countTrailingZeros<unsigned long>'→
11
←
The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'unsigned long long'
if (0 < Sym.st_shndx && Sym.st_shndx < Sections.size())
  Ret = std::min<uint64_t>(Ret, Sections[Sym.st_shndx].sh_addralign);
return (Ret > UINT32_MAX(4294967295U)) ? 0 : Ret;
970}

972// Fully parse the shared object file. This must be called after parseSoName().
973//
974// This function parses symbol versions. If a DSO has version information,
975// the file has a ".gnu.version_d" section which contains symbol version
976// definitions. Each symbol is associated to one version through a table in
977// ".gnu.version" section. That table is a parallel array for the symbol
978// table, and each table entry contains an index in ".gnu.version_d".
979//
980// The special index 0 is reserved for VERF_NDX_LOCAL and 1 is for
981// VER_NDX_GLOBAL. There's no table entry for these special versions in
982// ".gnu.version_d".
983//
984// The file format for symbol versioning is perhaps a bit more complicated
985// than necessary, but you can easily understand the code if you wrap your
986// head around the data structure described above.
987template <class ELFT> void SharedFile<ELFT>::parseRest() {
Verdefs = parseVerdefs();                       // parse .gnu.version_d
std::vector<uint32_t> Versyms = parseVersyms(); // parse .gnu.version
ArrayRef<Elf_Shdr> Sections = CHECK(this->getObj().sections(), this)check2((this->getObj().sections()), [&] { return toString
(this); });

// System libraries can have a lot of symbols with versions. Using a
// fixed buffer for computing the versions name (foo@ver) can save a
// lot of allocations.
SmallString<0> VersionedNameBuffer;

// Add symbols to the symbol table.
ArrayRef<Elf_Sym> Syms = this->getGlobalELFSyms();
for (size_t I = 0; I < Syms.size(); ++I) {
  const Elf_Sym &Sym = Syms[I];

  // ELF spec requires that all local symbols precede weak or global
  // symbols in each symbol table, and the index of first non-local symbol
  // is stored to sh_info. If a local symbol appears after some non-local
  // symbol, that's a violation of the spec.
  StringRef Name = CHECK(Sym.getName(this->StringTable), this)check2((Sym.getName(this->StringTable)), [&] { return toString
(this); });
  if (Sym.getBinding() == STB_LOCAL) {
    warn("found local symbol '" + Name +
         "' in global part of symbol table in file " + toString(this));
    continue;
  }

  if (Sym.isUndefined()) {
    Symbol *S = Symtab->addUndefined<ELFT>(Name, Sym.getBinding(),
                                           Sym.st_other, Sym.getType(),
                                           /*CanOmitFromDynSym=*/false, this);
    S->ExportDynamic = true;
    continue;
  }

  // MIPS BFD linker puts _gp_disp symbol into DSO files and incorrectly
  // assigns VER_NDX_LOCAL to this section global symbol. Here is a
  // workaround for this bug.
  uint32_t Idx = Versyms[I] & ~VERSYM_HIDDEN;
  if (Config->EMachine == EM_MIPS && Idx == VER_NDX_LOCAL &&
      Name == "_gp_disp")
    continue;

  uint64_t Alignment = getAlignment(Sections, Sym);
  if (!(Versyms[I] & VERSYM_HIDDEN))
    Symtab->addShared(Name, *this, Sym, Alignment, Idx);

  // Also add the symbol with the versioned name to handle undefined symbols
  // with explicit versions.
  if (Idx == VER_NDX_GLOBAL)
    continue;

  if (Idx >= Verdefs.size() || Idx == VER_NDX_LOCAL) {
    error("corrupt input file: version definition index " + Twine(Idx) +
          " for symbol " + Name + " is out of bounds\n>>> defined in " +
          toString(this));
    continue;
  }

  StringRef VerName =
      this->StringTable.data() + Verdefs[Idx]->getAux()->vda_name;
  VersionedNameBuffer.clear();
  Name = (Name + "@" + VerName).toStringRef(VersionedNameBuffer);
  Symtab->addShared(Saver.save(Name), *this, Sym, Alignment, Idx);
}
1051}

1053static ELFKind getBitcodeELFKind(const Triple &T) {
if (T.isLittleEndian())
  return T.isArch64Bit() ? ELF64LEKind : ELF32LEKind;
return T.isArch64Bit() ? ELF64BEKind : ELF32BEKind;
1057}

1059static uint8_t getBitcodeMachineKind(StringRef Path, const Triple &T) {
switch (T.getArch()) {
case Triple::aarch64:
  return EM_AARCH64;
case Triple::amdgcn:
case Triple::r600:
  return EM_AMDGPU;
case Triple::arm:
case Triple::thumb:
  return EM_ARM;
case Triple::avr:
  return EM_AVR;
case Triple::mips:
case Triple::mipsel:
case Triple::mips64:
case Triple::mips64el:
  return EM_MIPS;
case Triple::ppc:
  return EM_PPC;
case Triple::ppc64:
case Triple::ppc64le:
  return EM_PPC64;
case Triple::x86:
  return T.isOSIAMCU() ? EM_IAMCU : EM_386;
case Triple::x86_64:
  return EM_X86_64;
default:
  error(Path + ": could not infer e_machine from bitcode target triple " +
        T.str());
  return EM_NONE;
}
1090}

1092BitcodeFile::BitcodeFile(MemoryBufferRef MB, StringRef ArchiveName,
                       uint64_t OffsetInArchive)
  : InputFile(BitcodeKind, MB) {
this->ArchiveName = ArchiveName;

std::string Path = MB.getBufferIdentifier().str();
if (Config->ThinLTOIndexOnly)
  Path = replaceThinLTOSuffix(MB.getBufferIdentifier());

// ThinLTO assumes that all MemoryBufferRefs given to it have a unique
// name. If two archives define two members with the same name, this
// causes a collision which result in only one of the objects being taken
// into consideration at LTO time (which very likely causes undefined
// symbols later in the link stage). So we append file offset to make
// filename unique.
MemoryBufferRef MBRef(
    MB.getBuffer(),
    Saver.save(ArchiveName + Path +
               (ArchiveName.empty() ? "" : utostr(OffsetInArchive))));

Obj = CHECK(lto::InputFile::create(MBRef), this)check2((lto::InputFile::create(MBRef)), [&] { return toString
(this); });

Triple T(Obj->getTargetTriple());
EKind = getBitcodeELFKind(T);
EMachine = getBitcodeMachineKind(MB.getBufferIdentifier(), T);
1117}

1119static uint8_t mapVisibility(GlobalValue::VisibilityTypes GvVisibility) {
switch (GvVisibility) {
case GlobalValue::DefaultVisibility:
  return STV_DEFAULT;
case GlobalValue::HiddenVisibility:
  return STV_HIDDEN;
case GlobalValue::ProtectedVisibility:
  return STV_PROTECTED;
}
llvm_unreachable("unknown visibility")::llvm::llvm_unreachable_internal("unknown visibility", "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/ELF/InputFiles.cpp"
, 1128);
1129}

1131template <class ELFT>
1132static Symbol *createBitcodeSymbol(const std::vector<bool> &KeptComdats,
                                 const lto::InputFile::Symbol &ObjSym,
                                 BitcodeFile &F) {
StringRef Name = Saver.save(ObjSym.getName());
uint32_t Binding = ObjSym.isWeak() ? STB_WEAK : STB_GLOBAL;

uint8_t Type = ObjSym.isTLS() ? STT_TLS : STT_NOTYPE;
uint8_t Visibility = mapVisibility(ObjSym.getVisibility());
bool CanOmitFromDynSym = ObjSym.canBeOmittedFromSymbolTable();

int C = ObjSym.getComdatIndex();
if (C != -1 && !KeptComdats[C])
  return Symtab->addUndefined<ELFT>(Name, Binding, Visibility, Type,
                                    CanOmitFromDynSym, &F);

if (ObjSym.isUndefined())
  return Symtab->addUndefined<ELFT>(Name, Binding, Visibility, Type,
                                    CanOmitFromDynSym, &F);

if (ObjSym.isCommon())
  return Symtab->addCommon(Name, ObjSym.getCommonSize(),
                           ObjSym.getCommonAlignment(), Binding, Visibility,
                           STT_OBJECT, F);

return Symtab->addBitcode(Name, Binding, Visibility, Type, CanOmitFromDynSym,
                          F);
1158}

1160template <class ELFT>
1161void BitcodeFile::parse(DenseSet<CachedHashStringRef> &ComdatGroups) {
std::vector<bool> KeptComdats;
for (StringRef S : Obj->getComdatTable())
  KeptComdats.push_back(ComdatGroups.insert(CachedHashStringRef(S)).second);

for (const lto::InputFile::Symbol &ObjSym : Obj->symbols())
  Symbols.push_back(createBitcodeSymbol<ELFT>(KeptComdats, ObjSym, *this));
1168}

1170static ELFKind getELFKind(MemoryBufferRef MB) {
unsigned char Size;
unsigned char Endian;
std::tie(Size, Endian) = getElfArchType(MB.getBuffer());

if (Endian != ELFDATA2LSB && Endian != ELFDATA2MSB)
  fatal(MB.getBufferIdentifier() + ": invalid data encoding");
if (Size != ELFCLASS32 && Size != ELFCLASS64)
  fatal(MB.getBufferIdentifier() + ": invalid file class");

size_t BufSize = MB.getBuffer().size();
if ((Size == ELFCLASS32 && BufSize < sizeof(Elf32_Ehdr)) ||
    (Size == ELFCLASS64 && BufSize < sizeof(Elf64_Ehdr)))
  fatal(MB.getBufferIdentifier() + ": file is too short");

if (Size == ELFCLASS32)
  return (Endian == ELFDATA2LSB) ? ELF32LEKind : ELF32BEKind;
return (Endian == ELFDATA2LSB) ? ELF64LEKind : ELF64BEKind;
1188}

1190void BinaryFile::parse() {
ArrayRef<uint8_t> Data = arrayRefFromStringRef(MB.getBuffer());
auto *Section = make<InputSection>(this, SHF_ALLOC | SHF_WRITE, SHT_PROGBITS,
                                   8, Data, ".data");
Sections.push_back(Section);

// For each input file foo that is embedded to a result as a binary
// blob, we define _binary_foo_{start,end,size} symbols, so that
// user programs can access blobs by name. Non-alphanumeric
// characters in a filename are replaced with underscore.
std::string S = "_binary_" + MB.getBufferIdentifier().str();
for (size_t I = 0; I < S.size(); ++I)
  if (!isAlnum(S[I]))
    S[I] = '_';

Symtab->addDefined(Saver.save(S + "_start"), STV_DEFAULT, STT_OBJECT, 0, 0,
                   STB_GLOBAL, Section, nullptr);
Symtab->addDefined(Saver.save(S + "_end"), STV_DEFAULT, STT_OBJECT,
                   Data.size(), 0, STB_GLOBAL, Section, nullptr);
Symtab->addDefined(Saver.save(S + "_size"), STV_DEFAULT, STT_OBJECT,
                   Data.size(), 0, STB_GLOBAL, nullptr, nullptr);
1211}

1213InputFile *elf::createObjectFile(MemoryBufferRef MB, StringRef ArchiveName,
                               uint64_t OffsetInArchive) {
if (isBitcode(MB))
  return make<BitcodeFile>(MB, ArchiveName, OffsetInArchive);

switch (getELFKind(MB)) {
case ELF32LEKind:
  return make<ObjFile<ELF32LE>>(MB, ArchiveName);
case ELF32BEKind:
  return make<ObjFile<ELF32BE>>(MB, ArchiveName);
case ELF64LEKind:
  return make<ObjFile<ELF64LE>>(MB, ArchiveName);
case ELF64BEKind:
  return make<ObjFile<ELF64BE>>(MB, ArchiveName);
default:
  llvm_unreachable("getELFKind")::llvm::llvm_unreachable_internal("getELFKind", "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/ELF/InputFiles.cpp"
, 1228);
}
1230}

1232InputFile *elf::createSharedFile(MemoryBufferRef MB, StringRef DefaultSoName) {
switch (getELFKind(MB)) {
case ELF32LEKind:
  return make<SharedFile<ELF32LE>>(MB, DefaultSoName);
case ELF32BEKind:
  return make<SharedFile<ELF32BE>>(MB, DefaultSoName);
case ELF64LEKind:
  return make<SharedFile<ELF64LE>>(MB, DefaultSoName);
case ELF64BEKind:
  return make<SharedFile<ELF64BE>>(MB, DefaultSoName);
default:
  llvm_unreachable("getELFKind")::llvm::llvm_unreachable_internal("getELFKind", "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/ELF/InputFiles.cpp"
, 1243);
}
1245}

1247MemoryBufferRef LazyObjFile::getBuffer() {
if (AddedToLink)
  return MemoryBufferRef();
AddedToLink = true;
return MB;
1252}

1254InputFile *LazyObjFile::fetch() {
MemoryBufferRef MBRef = getBuffer();
if (MBRef.getBuffer().empty())
  return nullptr;

InputFile *File = createObjectFile(MBRef, ArchiveName, OffsetInArchive);
File->GroupId = GroupId;
return File;
1262}

1264template <class ELFT> void LazyObjFile::parse() {
// A lazy object file wraps either a bitcode file or an ELF file.
if (isBitcode(this->MB)) {
  std::unique_ptr<lto::InputFile> Obj =
      CHECK(lto::InputFile::create(this->MB), this)check2((lto::InputFile::create(this->MB)), [&] { return
 toString(this); });
  for (const lto::InputFile::Symbol &Sym : Obj->symbols())
    if (!Sym.isUndefined())
      Symtab->addLazyObject<ELFT>(Saver.save(Sym.getName()), *this);
  return;
}

if (getELFKind(this->MB) != Config->EKind) {
  error("incompatible file: " + this->MB.getBufferIdentifier());
  return;
}

ELFFile<ELFT> Obj = check(ELFFile<ELFT>::create(MB.getBuffer()));
ArrayRef<typename ELFT::Shdr> Sections = CHECK(Obj.sections(), this)check2((Obj.sections()), [&] { return toString(this); });

for (const typename ELFT::Shdr &Sec : Sections) {
  if (Sec.sh_type != SHT_SYMTAB)
    continue;

  typename ELFT::SymRange Syms = CHECK(Obj.symbols(&Sec), this)check2((Obj.symbols(&Sec)), [&] { return toString(this
); });
  uint32_t FirstGlobal = Sec.sh_info;
  StringRef StringTable =
      CHECK(Obj.getStringTableForSymtab(Sec, Sections), this)check2((Obj.getStringTableForSymtab(Sec, Sections)), [&] {
 return toString(this); });

  for (const typename ELFT::Sym &Sym : Syms.slice(FirstGlobal))
    if (Sym.st_shndx != SHN_UNDEF)
      Symtab->addLazyObject<ELFT>(CHECK(Sym.getName(StringTable), this)check2((Sym.getName(StringTable)), [&] { return toString(
this); }),
                                  *this);
  return;
}
1298}

1300std::string elf::replaceThinLTOSuffix(StringRef Path) {
StringRef Suffix = Config->ThinLTOObjectSuffixReplace.first;
StringRef Repl = Config->ThinLTOObjectSuffixReplace.second;

if (Path.consume_back(Suffix))
  return (Path + Repl).str();
return Path;
1307}

1309template void ArchiveFile::parse<ELF32LE>();
1310template void ArchiveFile::parse<ELF32BE>();
1311template void ArchiveFile::parse<ELF64LE>();
1312template void ArchiveFile::parse<ELF64BE>();

1314template void BitcodeFile::parse<ELF32LE>(DenseSet<CachedHashStringRef> &);
1315template void BitcodeFile::parse<ELF32BE>(DenseSet<CachedHashStringRef> &);
1316template void BitcodeFile::parse<ELF64LE>(DenseSet<CachedHashStringRef> &);
1317template void BitcodeFile::parse<ELF64BE>(DenseSet<CachedHashStringRef> &);

1319template void LazyObjFile::parse<ELF32LE>();
1320template void LazyObjFile::parse<ELF32BE>();
1321template void LazyObjFile::parse<ELF64LE>();
1322template void LazyObjFile::parse<ELF64BE>();

1324template class elf::ELFFileBase<ELF32LE>;
1325template class elf::ELFFileBase<ELF32BE>;
1326template class elf::ELFFileBase<ELF64LE>;
1327template class elf::ELFFileBase<ELF64BE>;

1329template class elf::ObjFile<ELF32LE>;
1330template class elf::ObjFile<ELF32BE>;
1331template class elf::ObjFile<ELF64LE>;
1332template class elf::ObjFile<ELF64BE>;

1334template class elf::SharedFile<ELF32LE>;
1335template class elf::SharedFile<ELF32BE>;
1336template class elf::SharedFile<ELF64LE>;
1337template class elf::SharedFile<ELF64BE>;

←

/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h

1//===-- llvm/Support/MathExtras.h - Useful math 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 functions that are useful for math stuff.
11//
12//===----------------------------------------------------------------------===//
13 
14#ifndef LLVM_SUPPORT_MATHEXTRAS_H
15#define LLVM_SUPPORT_MATHEXTRAS_H
16 
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/SwapByteOrder.h"
19#include <algorithm>
20#include <cassert>
21#include <climits>
22#include <cstring>
23#include <limits>
24#include <type_traits>
25 
26#ifdef __ANDROID_NDK__
27#include <android/api-level.h>
28#endif
29 
30#ifdef _MSC_VER
31// Declare these intrinsics manually rather including intrin.h. It's very
32// expensive, and MathExtras.h is popular.
33// #include <intrin.h>
34extern "C" {
35unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
36unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
37unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
38unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
39}
40#endif
41 
42namespace llvm {
43/// The behavior an operation has on an input of 0.
44enum ZeroBehavior {
45  /// The returned value is undefined.
46  ZB_Undefined,
47  /// The returned value is numeric_limits<T>::max()
48  ZB_Max,
49  /// The returned value is numeric_limits<T>::digits
50  ZB_Width
51};
52 
53namespace detail {
54template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
55  static std::size_t count(T Val, ZeroBehavior) {
56    if (!Val)
57      return std::numeric_limits<T>::digits;
58    if (Val & 0x1)
59      return 0;
60 
61    // Bisection method.
62    std::size_t ZeroBits = 0;
63    T Shift = std::numeric_limits<T>::digits >> 1;
64    T Mask = std::numeric_limits<T>::max() >> Shift;
65    while (Shift) {
66      if ((Val & Mask) == 0) {
67        Val >>= Shift;
68        ZeroBits |= Shift;
69      }
70      Shift >>= 1;
71      Mask >>= Shift;
72    }
73    return ZeroBits;
74  }
75};
76 
77#if __GNUC__4 >= 4 || defined(_MSC_VER)
78template <typename T> struct TrailingZerosCounter<T, 4> {
79  static std::size_t count(T Val, ZeroBehavior ZB) {
80    if (ZB != ZB_Undefined && Val == 0)
81      return 32;
82 
83#if __has_builtin(__builtin_ctz)1 || LLVM_GNUC_PREREQ(4, 0, 0)((4 << 20) + (2 << 10) + 1 >= ((4) << 20
) + ((0) << 10) + (0))
84    return __builtin_ctz(Val);
85#elif defined(_MSC_VER)
86    unsigned long Index;
87    _BitScanForward(&Index, Val);
88    return Index;
89#endif
90  }
91};
92 
93#if !defined(_MSC_VER) || defined(_M_X64)
94template <typename T> struct TrailingZerosCounter<T, 8> {
95  static std::size_t count(T Val, ZeroBehavior ZB) {
96    if (ZB != ZB_Undefined && Val == 0)
5
←
Assuming 'Val' is equal to 0→
6
←
Taking true branch→
97      return 64;
7
←
Returning the value 64→
98 
99#if __has_builtin(__builtin_ctzll)1 || LLVM_GNUC_PREREQ(4, 0, 0)((4 << 20) + (2 << 10) + 1 >= ((4) << 20
) + ((0) << 10) + (0))
100    return __builtin_ctzll(Val);
101#elif defined(_MSC_VER)
102    unsigned long Index;
103    _BitScanForward64(&Index, Val);
104    return Index;
105#endif
106  }
107};
108#endif
109#endif
110} // namespace detail
111 
112/// Count number of 0's from the least significant bit to the most
113///   stopping at the first 1.
114///
115/// Only unsigned integral types are allowed.
116///
117/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
118///   valid arguments.
119template <typename T>
120std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
121  static_assert(std::numeric_limits<T>::is_integer &&
122                    !std::numeric_limits<T>::is_signed,
123                "Only unsigned integral types are allowed.");
124  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
4
←
Calling 'TrailingZerosCounter::count'→
8
←
Returning from 'TrailingZerosCounter::count'→
9
←
Returning the value 64→
125}
126 
127namespace detail {
128template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
129  static std::size_t count(T Val, ZeroBehavior) {
130    if (!Val)
131      return std::numeric_limits<T>::digits;
132 
133    // Bisection method.
134    std::size_t ZeroBits = 0;
135    for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
136      T Tmp = Val >> Shift;
137      if (Tmp)
138        Val = Tmp;
139      else
140        ZeroBits |= Shift;
141    }
142    return ZeroBits;
143  }
144};
145 
146#if __GNUC__4 >= 4 || defined(_MSC_VER)
147template <typename T> struct LeadingZerosCounter<T, 4> {
148  static std::size_t count(T Val, ZeroBehavior ZB) {
149    if (ZB != ZB_Undefined && Val == 0)
150      return 32;
151 
152#if __has_builtin(__builtin_clz)1 || LLVM_GNUC_PREREQ(4, 0, 0)((4 << 20) + (2 << 10) + 1 >= ((4) << 20
) + ((0) << 10) + (0))
153    return __builtin_clz(Val);
154#elif defined(_MSC_VER)
155    unsigned long Index;
156    _BitScanReverse(&Index, Val);
157    return Index ^ 31;
158#endif
159  }
160};
161 
162#if !defined(_MSC_VER) || defined(_M_X64)
163template <typename T> struct LeadingZerosCounter<T, 8> {
164  static std::size_t count(T Val, ZeroBehavior ZB) {
165    if (ZB != ZB_Undefined && Val == 0)
166      return 64;
167 
168#if __has_builtin(__builtin_clzll)1 || LLVM_GNUC_PREREQ(4, 0, 0)((4 << 20) + (2 << 10) + 1 >= ((4) << 20
) + ((0) << 10) + (0))
169    return __builtin_clzll(Val);
170#elif defined(_MSC_VER)
171    unsigned long Index;
172    _BitScanReverse64(&Index, Val);
173    return Index ^ 63;
174#endif
175  }
176};
177#endif
178#endif
179} // namespace detail
180 
181/// Count number of 0's from the most significant bit to the least
182///   stopping at the first 1.
183///
184/// Only unsigned integral types are allowed.
185///
186/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
187///   valid arguments.
188template <typename T>
189std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
190  static_assert(std::numeric_limits<T>::is_integer &&
191                    !std::numeric_limits<T>::is_signed,
192                "Only unsigned integral types are allowed.");
193  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
194}
195 
196/// Get the index of the first set bit starting from the least
197///   significant bit.
198///
199/// Only unsigned integral types are allowed.
200///
201/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
202///   valid arguments.
203template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
204  if (ZB == ZB_Max && Val == 0)
205    return std::numeric_limits<T>::max();
206 
207  return countTrailingZeros(Val, ZB_Undefined);
208}
209 
210/// Create a bitmask with the N right-most bits set to 1, and all other
211/// bits set to 0.  Only unsigned types are allowed.
212template <typename T> T maskTrailingOnes(unsigned N) {
213  static_assert(std::is_unsigned<T>::value, "Invalid type!");
214  const unsigned Bits = CHAR_BIT8 * sizeof(T);
215  assert(N <= Bits && "Invalid bit index")((N <= Bits && "Invalid bit index") ? static_cast<
void> (0) : __assert_fail ("N <= Bits && \"Invalid bit index\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 215, __PRETTY_FUNCTION__));
216  return N == 0 ? 0 : (T(-1) >> (Bits - N));
217}
218 
219/// Create a bitmask with the N left-most bits set to 1, and all other
220/// bits set to 0.  Only unsigned types are allowed.
221template <typename T> T maskLeadingOnes(unsigned N) {
222  return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
223}
224 
225/// Create a bitmask with the N right-most bits set to 0, and all other
226/// bits set to 1.  Only unsigned types are allowed.
227template <typename T> T maskTrailingZeros(unsigned N) {
228  return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
229}
230 
231/// Create a bitmask with the N left-most bits set to 0, and all other
232/// bits set to 1.  Only unsigned types are allowed.
233template <typename T> T maskLeadingZeros(unsigned N) {
234  return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
235}
236 
237/// Get the index of the last set bit starting from the least
238///   significant bit.
239///
240/// Only unsigned integral types are allowed.
241///
242/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
243///   valid arguments.
244template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
245  if (ZB == ZB_Max && Val == 0)
246    return std::numeric_limits<T>::max();
247 
248  // Use ^ instead of - because both gcc and llvm can remove the associated ^
249  // in the __builtin_clz intrinsic on x86.
250  return countLeadingZeros(Val, ZB_Undefined) ^
251         (std::numeric_limits<T>::digits - 1);
252}
253 
254/// Macro compressed bit reversal table for 256 bits.
255///
256/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
257static const unsigned char BitReverseTable256[256] = {
258#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
259#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
260#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
261  R6(0), R6(2), R6(1), R6(3)
262#undef R2
263#undef R4
264#undef R6
265};
266 
267/// Reverse the bits in \p Val.
268template <typename T>
269T reverseBits(T Val) {
270  unsigned char in[sizeof(Val)];
271  unsigned char out[sizeof(Val)];
272  std::memcpy(in, &Val, sizeof(Val));
273  for (unsigned i = 0; i < sizeof(Val); ++i)
274    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
275  std::memcpy(&Val, out, sizeof(Val));
276  return Val;
277}
278 
279// NOTE: The following support functions use the _32/_64 extensions instead of
280// type overloading so that signed and unsigned integers can be used without
281// ambiguity.
282 
283/// Return the high 32 bits of a 64 bit value.
284constexpr inline uint32_t Hi_32(uint64_t Value) {
285  return static_cast<uint32_t>(Value >> 32);
286}
287 
288/// Return the low 32 bits of a 64 bit value.
289constexpr inline uint32_t Lo_32(uint64_t Value) {
290  return static_cast<uint32_t>(Value);
291}
292 
293/// Make a 64-bit integer from a high / low pair of 32-bit integers.
294constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
295  return ((uint64_t)High << 32) | (uint64_t)Low;
296}
297 
298/// Checks if an integer fits into the given bit width.
299template <unsigned N> constexpr inline bool isInt(int64_t x) {
300  return N >= 64 || (-(INT64_C(1)1L<<(N-1)) <= x && x < (INT64_C(1)1L<<(N-1)));
301}
302// Template specializations to get better code for common cases.
303template <> constexpr inline bool isInt<8>(int64_t x) {
304  return static_cast<int8_t>(x) == x;
305}
306template <> constexpr inline bool isInt<16>(int64_t x) {
307  return static_cast<int16_t>(x) == x;
308}
309template <> constexpr inline bool isInt<32>(int64_t x) {
310  return static_cast<int32_t>(x) == x;
311}
312 
313/// Checks if a signed integer is an N bit number shifted left by S.
314template <unsigned N, unsigned S>
315constexpr inline bool isShiftedInt(int64_t x) {
316  static_assert(
317      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
318  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
319  return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
320}
321 
322/// Checks if an unsigned integer fits into the given bit width.
323///
324/// This is written as two functions rather than as simply
325///
326///   return N >= 64 || X < (UINT64_C(1) << N);
327///
328/// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
329/// left too many places.
330template <unsigned N>
331constexpr inline typename std::enable_if<(N < 64), bool>::type
332isUInt(uint64_t X) {
333  static_assert(N > 0, "isUInt<0> doesn't make sense");
334  return X < (UINT64_C(1)1UL << (N));
335}
336template <unsigned N>
337constexpr inline typename std::enable_if<N >= 64, bool>::type
338isUInt(uint64_t X) {
339  return true;
340}
341 
342// Template specializations to get better code for common cases.
343template <> constexpr inline bool isUInt<8>(uint64_t x) {
344  return static_cast<uint8_t>(x) == x;
345}
346template <> constexpr inline bool isUInt<16>(uint64_t x) {
347  return static_cast<uint16_t>(x) == x;
348}
349template <> constexpr inline bool isUInt<32>(uint64_t x) {
350  return static_cast<uint32_t>(x) == x;
351}
352 
353/// Checks if a unsigned integer is an N bit number shifted left by S.
354template <unsigned N, unsigned S>
355constexpr inline bool isShiftedUInt(uint64_t x) {
356  static_assert(
357      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358  static_assert(N + S <= 64,
359                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360  // Per the two static_asserts above, S must be strictly less than 64.  So
361  // 1 << S is not undefined behavior.
362  return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
363}
364 
365/// Gets the maximum value for a N-bit unsigned integer.
366inline uint64_t maxUIntN(uint64_t N) {
367  assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 367, __PRETTY_FUNCTION__));
368 
369  // uint64_t(1) << 64 is undefined behavior, so we can't do
370  //   (uint64_t(1) << N) - 1
371  // without checking first that N != 64.  But this works and doesn't have a
372  // branch.
373  return UINT64_MAX(18446744073709551615UL) >> (64 - N);
374}
375 
376/// Gets the minimum value for a N-bit signed integer.
377inline int64_t minIntN(int64_t N) {
378  assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 378, __PRETTY_FUNCTION__));
379 
380  return -(UINT64_C(1)1UL<<(N-1));
381}
382 
383/// Gets the maximum value for a N-bit signed integer.
384inline int64_t maxIntN(int64_t N) {
385  assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 385, __PRETTY_FUNCTION__));
386 
387  // This relies on two's complement wraparound when N == 64, so we convert to
388  // int64_t only at the very end to avoid UB.
389  return (UINT64_C(1)1UL << (N - 1)) - 1;
390}
391 
392/// Checks if an unsigned integer fits into the given (dynamic) bit width.
393inline bool isUIntN(unsigned N, uint64_t x) {
394  return N >= 64 || x <= maxUIntN(N);
395}
396 
397/// Checks if an signed integer fits into the given (dynamic) bit width.
398inline bool isIntN(unsigned N, int64_t x) {
399  return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
400}
401 
402/// Return true if the argument is a non-empty sequence of ones starting at the
403/// least significant bit with the remainder zero (32 bit version).
404/// Ex. isMask_32(0x0000FFFFU) == true.
405constexpr inline bool isMask_32(uint32_t Value) {
406  return Value && ((Value + 1) & Value) == 0;
407}
408 
409/// Return true if the argument is a non-empty sequence of ones starting at the
410/// least significant bit with the remainder zero (64 bit version).
411constexpr inline bool isMask_64(uint64_t Value) {
412  return Value && ((Value + 1) & Value) == 0;
413}
414 
415/// Return true if the argument contains a non-empty sequence of ones with the
416/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
417constexpr inline bool isShiftedMask_32(uint32_t Value) {
418  return Value && isMask_32((Value - 1) | Value);
419}
420 
421/// Return true if the argument contains a non-empty sequence of ones with the
422/// remainder zero (64 bit version.)
423constexpr inline bool isShiftedMask_64(uint64_t Value) {
424  return Value && isMask_64((Value - 1) | Value);
425}
426 
427/// Return true if the argument is a power of two > 0.
428/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
429constexpr inline bool isPowerOf2_32(uint32_t Value) {
430  return Value && !(Value & (Value - 1));
431}
432 
433/// Return true if the argument is a power of two > 0 (64 bit edition.)
434constexpr inline bool isPowerOf2_64(uint64_t Value) {
435  return Value && !(Value & (Value - 1));
436}
437 
438/// Return a byte-swapped representation of the 16-bit argument.
439inline uint16_t ByteSwap_16(uint16_t Value) {
440  return sys::SwapByteOrder_16(Value);
441}
442 
443/// Return a byte-swapped representation of the 32-bit argument.
444inline uint32_t ByteSwap_32(uint32_t Value) {
445  return sys::SwapByteOrder_32(Value);
446}
447 
448/// Return a byte-swapped representation of the 64-bit argument.
449inline uint64_t ByteSwap_64(uint64_t Value) {
450  return sys::SwapByteOrder_64(Value);
451}
452 
453/// Count the number of ones from the most significant bit to the first
454/// zero bit.
455///
456/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
457/// Only unsigned integral types are allowed.
458///
459/// \param ZB the behavior on an input of all ones. Only ZB_Width and
460/// ZB_Undefined are valid arguments.
461template <typename T>
462std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
463  static_assert(std::numeric_limits<T>::is_integer &&
464                    !std::numeric_limits<T>::is_signed,
465                "Only unsigned integral types are allowed.");
466  return countLeadingZeros<T>(~Value, ZB);
467}
468 
469/// Count the number of ones from the least significant bit to the first
470/// zero bit.
471///
472/// Ex. countTrailingOnes(0x00FF00FF) == 8.
473/// Only unsigned integral types are allowed.
474///
475/// \param ZB the behavior on an input of all ones. Only ZB_Width and
476/// ZB_Undefined are valid arguments.
477template <typename T>
478std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
479  static_assert(std::numeric_limits<T>::is_integer &&
480                    !std::numeric_limits<T>::is_signed,
481                "Only unsigned integral types are allowed.");
482  return countTrailingZeros<T>(~Value, ZB);
483}
484 
485namespace detail {
486template <typename T, std::size_t SizeOfT> struct PopulationCounter {
487  static unsigned count(T Value) {
488    // Generic version, forward to 32 bits.
489    static_assert(SizeOfT <= 4, "Not implemented!");
490#if __GNUC__4 >= 4
491    return __builtin_popcount(Value);
492#else
493    uint32_t v = Value;
494    v = v - ((v >> 1) & 0x55555555);
495    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
496    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
497#endif
498  }
499};
500 
501template <typename T> struct PopulationCounter<T, 8> {
502  static unsigned count(T Value) {
503#if __GNUC__4 >= 4
504    return __builtin_popcountll(Value);
505#else
506    uint64_t v = Value;
507    v = v - ((v >> 1) & 0x5555555555555555ULL);
508    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
509    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
510    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
511#endif
512  }
513};
514} // namespace detail
515 
516/// Count the number of set bits in a value.
517/// Ex. countPopulation(0xF000F000) = 8
518/// Returns 0 if the word is zero.
519template <typename T>
520inline unsigned countPopulation(T Value) {
521  static_assert(std::numeric_limits<T>::is_integer &&
522                    !std::numeric_limits<T>::is_signed,
523                "Only unsigned integral types are allowed.");
524  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
525}
526 
527/// Return the log base 2 of the specified value.
528inline double Log2(double Value) {
529#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
530  return __builtin_log(Value) / __builtin_log(2.0);
531#else
532  return log2(Value);
533#endif
534}
535 
536/// Return the floor log base 2 of the specified value, -1 if the value is zero.
537/// (32 bit edition.)
538/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
539inline unsigned Log2_32(uint32_t Value) {
540  return 31 - countLeadingZeros(Value);
541}
542 
543/// Return the floor log base 2 of the specified value, -1 if the value is zero.
544/// (64 bit edition.)
545inline unsigned Log2_64(uint64_t Value) {
546  return 63 - countLeadingZeros(Value);
547}
548 
549/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
550/// (32 bit edition).
551/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
552inline unsigned Log2_32_Ceil(uint32_t Value) {
553  return 32 - countLeadingZeros(Value - 1);
554}
555 
556/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
557/// (64 bit edition.)
558inline unsigned Log2_64_Ceil(uint64_t Value) {
559  return 64 - countLeadingZeros(Value - 1);
560}
561 
562/// Return the greatest common divisor of the values using Euclid's algorithm.
563inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
564  while (B) {
565    uint64_t T = B;
566    B = A % B;
567    A = T;
568  }
569  return A;
570}
571 
572/// This function takes a 64-bit integer and returns the bit equivalent double.
573inline double BitsToDouble(uint64_t Bits) {
574  double D;
575  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
576  memcpy(&D, &Bits, sizeof(Bits));
577  return D;
578}
579 
580/// This function takes a 32-bit integer and returns the bit equivalent float.
581inline float BitsToFloat(uint32_t Bits) {
582  float F;
583  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
584  memcpy(&F, &Bits, sizeof(Bits));
585  return F;
586}
587 
588/// This function takes a double and returns the bit equivalent 64-bit integer.
589/// Note that copying doubles around changes the bits of NaNs on some hosts,
590/// notably x86, so this routine cannot be used if these bits are needed.
591inline uint64_t DoubleToBits(double Double) {
592  uint64_t Bits;
593  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
594  memcpy(&Bits, &Double, sizeof(Double));
595  return Bits;
596}
597 
598/// This function takes a float and returns the bit equivalent 32-bit integer.
599/// Note that copying floats around changes the bits of NaNs on some hosts,
600/// notably x86, so this routine cannot be used if these bits are needed.
601inline uint32_t FloatToBits(float Float) {
602  uint32_t Bits;
603  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
604  memcpy(&Bits, &Float, sizeof(Float));
605  return Bits;
606}
607 
608/// A and B are either alignments or offsets. Return the minimum alignment that
609/// may be assumed after adding the two together.
610constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
611  // The largest power of 2 that divides both A and B.
612  //
613  // Replace "-Value" by "1+~Value" in the following commented code to avoid
614  // MSVC warning C4146
615  //    return (A | B) & -(A | B);
616  return (A | B) & (1 + ~(A | B));
617}
618 
619/// Aligns \c Addr to \c Alignment bytes, rounding up.
620///
621/// Alignment should be a power of two.  This method rounds up, so
622/// alignAddr(7, 4) == 8 and alignAddr(8, 4) == 8.
623inline uintptr_t alignAddr(const void *Addr, size_t Alignment) {
624  assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&((Alignment && isPowerOf2_64((uint64_t)Alignment) &&
 "Alignment is not a power of two!") ? static_cast<void>
 (0) : __assert_fail ("Alignment && isPowerOf2_64((uint64_t)Alignment) && \"Alignment is not a power of two!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 625, __PRETTY_FUNCTION__))
625         "Alignment is not a power of two!")((Alignment && isPowerOf2_64((uint64_t)Alignment) &&
 "Alignment is not a power of two!") ? static_cast<void>
 (0) : __assert_fail ("Alignment && isPowerOf2_64((uint64_t)Alignment) && \"Alignment is not a power of two!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 625, __PRETTY_FUNCTION__));
626 
627  assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr)(((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr) ? static_cast
<void> (0) : __assert_fail ("(uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr"
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 627, __PRETTY_FUNCTION__));
628 
629  return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
630}
631 
632/// Returns the necessary adjustment for aligning \c Ptr to \c Alignment
633/// bytes, rounding up.
634inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) {
635  return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
636}
637 
638/// Returns the next power of two (in 64-bits) that is strictly greater than A.
639/// Returns zero on overflow.
640inline uint64_t NextPowerOf2(uint64_t A) {
641  A |= (A >> 1);
642  A |= (A >> 2);
643  A |= (A >> 4);
644  A |= (A >> 8);
645  A |= (A >> 16);
646  A |= (A >> 32);
647  return A + 1;
648}
649 
650/// Returns the power of two which is less than or equal to the given value.
651/// Essentially, it is a floor operation across the domain of powers of two.
652inline uint64_t PowerOf2Floor(uint64_t A) {
653  if (!A) return 0;
654  return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
655}
656 
657/// Returns the power of two which is greater than or equal to the given value.
658/// Essentially, it is a ceil operation across the domain of powers of two.
659inline uint64_t PowerOf2Ceil(uint64_t A) {
660  if (!A)
661    return 0;
662  return NextPowerOf2(A - 1);
663}
664 
665/// Returns the next integer (mod 2**64) that is greater than or equal to
666/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
667///
668/// If non-zero \p Skew is specified, the return value will be a minimal
669/// integer that is greater than or equal to \p Value and equal to
670/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
671/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
672///
673/// Examples:
674/// \code
675///   alignTo(5, 8) = 8
676///   alignTo(17, 8) = 24
677///   alignTo(~0LL, 8) = 0
678///   alignTo(321, 255) = 510
679///
680///   alignTo(5, 8, 7) = 7
681///   alignTo(17, 8, 1) = 17
682///   alignTo(~0LL, 8, 3) = 3
683///   alignTo(321, 255, 42) = 552
684/// \endcode
685inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
686  assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 686, __PRETTY_FUNCTION__));
687  Skew %= Align;
688  return (Value + Align - 1 - Skew) / Align * Align + Skew;
689}
690 
691/// Returns the next integer (mod 2**64) that is greater than or equal to
692/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
693template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
694  static_assert(Align != 0u, "Align must be non-zero");
695  return (Value + Align - 1) / Align * Align;
696}
697 
698/// Returns the integer ceil(Numerator / Denominator).
699inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
700  return alignTo(Numerator, Denominator) / Denominator;
701}
702 
703/// \c alignTo for contexts where a constant expression is required.
704/// \sa alignTo
705///
706/// \todo FIXME: remove when \c constexpr becomes really \c constexpr
707template <uint64_t Align>
708struct AlignTo {
709  static_assert(Align != 0u, "Align must be non-zero");
710  template <uint64_t Value>
711  struct from_value {
712    static const uint64_t value = (Value + Align - 1) / Align * Align;
713  };
714};
715 
716/// Returns the largest uint64_t less than or equal to \p Value and is
717/// \p Skew mod \p Align. \p Align must be non-zero
718inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
719  assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 719, __PRETTY_FUNCTION__));
720  Skew %= Align;
721  return (Value - Skew) / Align * Align + Skew;
722}
723 
724/// Returns the offset to the next integer (mod 2**64) that is greater than
725/// or equal to \p Value and is a multiple of \p Align. \p Align must be
726/// non-zero.
727inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
728  return alignTo(Value, Align) - Value;
729}
730 
731/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
732/// Requires 0 < B <= 32.
733template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
734  static_assert(B > 0, "Bit width can't be 0.");
735  static_assert(B <= 32, "Bit width out of range.");
736  return int32_t(X << (32 - B)) >> (32 - B);
737}
738 
739/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
740/// Requires 0 < B < 32.
741inline int32_t SignExtend32(uint32_t X, unsigned B) {
742  assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 742, __PRETTY_FUNCTION__));
743  assert(B <= 32 && "Bit width out of range.")((B <= 32 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 32 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 743, __PRETTY_FUNCTION__));
744  return int32_t(X << (32 - B)) >> (32 - B);
745}
746 
747/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
748/// Requires 0 < B < 64.
749template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
750  static_assert(B > 0, "Bit width can't be 0.");
751  static_assert(B <= 64, "Bit width out of range.");
752  return int64_t(x << (64 - B)) >> (64 - B);
753}
754 
755/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
756/// Requires 0 < B < 64.
757inline int64_t SignExtend64(uint64_t X, unsigned B) {
758  assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 758, __PRETTY_FUNCTION__));
759  assert(B <= 64 && "Bit width out of range.")((B <= 64 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 64 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h"
, 759, __PRETTY_FUNCTION__));
760  return int64_t(X << (64 - B)) >> (64 - B);
761}
762 
763/// Subtract two unsigned integers, X and Y, of type T and return the absolute
764/// value of the result.
765template <typename T>
766typename std::enable_if<std::is_unsigned<T>::value, T>::type
767AbsoluteDifference(T X, T Y) {
768  return std::max(X, Y) - std::min(X, Y);
769}
770 
771/// Add two unsigned integers, X and Y, of type T.  Clamp the result to the
772/// maximum representable value of T on overflow.  ResultOverflowed indicates if
773/// the result is larger than the maximum representable value of type T.
774template <typename T>
775typename std::enable_if<std::is_unsigned<T>::value, T>::type
776SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
777  bool Dummy;
778  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
779  // Hacker's Delight, p. 29
780  T Z = X + Y;
781  Overflowed = (Z < X || Z < Y);
782  if (Overflowed)
783    return std::numeric_limits<T>::max();
784  else
785    return Z;
786}
787 
788/// Multiply two unsigned integers, X and Y, of type T.  Clamp the result to the
789/// maximum representable value of T on overflow.  ResultOverflowed indicates if
790/// the result is larger than the maximum representable value of type T.
791template <typename T>
792typename std::enable_if<std::is_unsigned<T>::value, T>::type
793SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
794  bool Dummy;
795  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
796 
797  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
798  // because it fails for uint16_t (where multiplication can have undefined
799  // behavior due to promotion to int), and requires a division in addition
800  // to the multiplication.
801 
802  Overflowed = false;
803 
804  // Log2(Z) would be either Log2Z or Log2Z + 1.
805  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
806  // will necessarily be less than Log2Max as desired.
807  int Log2Z = Log2_64(X) + Log2_64(Y);
808  const T Max = std::numeric_limits<T>::max();
809  int Log2Max = Log2_64(Max);
810  if (Log2Z < Log2Max) {
811    return X * Y;
812  }
813  if (Log2Z > Log2Max) {
814    Overflowed = true;
815    return Max;
816  }
817 
818  // We're going to use the top bit, and maybe overflow one
819  // bit past it. Multiply all but the bottom bit then add
820  // that on at the end.
821  T Z = (X >> 1) * Y;
822  if (Z & ~(Max >> 1)) {
823    Overflowed = true;
824    return Max;
825  }
826  Z <<= 1;
827  if (X & 1)
828    return SaturatingAdd(Z, Y, ResultOverflowed);
829 
830  return Z;
831}
832 
833/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
834/// the product. Clamp the result to the maximum representable value of T on
835/// overflow. ResultOverflowed indicates if the result is larger than the
836/// maximum representable value of type T.
837template <typename T>
838typename std::enable_if<std::is_unsigned<T>::value, T>::type
839SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
840  bool Dummy;
841  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
842 
843  T Product = SaturatingMultiply(X, Y, &Overflowed);
844  if (Overflowed)
845    return Product;
846 
847  return SaturatingAdd(A, Product, &Overflowed);
848}
849 
850/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
851extern const float huge_valf;
852} // End llvm namespace
853 
854#endif