Initial commit. Code by Nick Kledzik. Cleanups and build system by me.
authorMichael J. Spencer <bigcheesegs@gmail.com>
Sun, 18 Dec 2011 08:27:59 +0000 (08:27 +0000)
committerMichael J. Spencer <bigcheesegs@gmail.com>
Sun, 18 Dec 2011 08:27:59 +0000 (08:27 +0000)
llvm-svn: 146844

32 files changed:
lld/.gitignore [new file with mode: 0644]
lld/CMakeLists.txt [new file with mode: 0644]
lld/include/lld/Core/AliasAtom.h [new file with mode: 0644]
lld/include/lld/Core/Atom.h [new file with mode: 0644]
lld/include/lld/Core/File.h [new file with mode: 0644]
lld/include/lld/Core/InputFiles.h [new file with mode: 0644]
lld/include/lld/Core/Reference.h [new file with mode: 0644]
lld/include/lld/Core/Resolver.h [new file with mode: 0644]
lld/include/lld/Core/SymbolTable.h [new file with mode: 0644]
lld/include/lld/Core/UndefinedAtom.h [new file with mode: 0644]
lld/include/lld/Core/YamlReader.h [new file with mode: 0644]
lld/include/lld/Core/YamlWriter.h [new file with mode: 0644]
lld/include/lld/Platform/Platform.h [new file with mode: 0644]
lld/include/lld/Platform/PlatformDarwin.h [new file with mode: 0644]
lld/lib/CMakeLists.txt [new file with mode: 0644]
lld/lib/Core/Atom.cpp [new file with mode: 0644]
lld/lib/Core/CMakeLists.txt [new file with mode: 0644]
lld/lib/Core/File.cpp [new file with mode: 0644]
lld/lib/Core/Resolver.cpp [new file with mode: 0644]
lld/lib/Core/SymbolTable.cpp [new file with mode: 0644]
lld/lib/Core/YamlReader.cpp [new file with mode: 0644]
lld/lib/Core/YamlWriter.cpp [new file with mode: 0644]
lld/test/CMakeLists.txt [new file with mode: 0644]
lld/test/lit.cfg [new file with mode: 0644]
lld/test/lit.site.cfg.in [new file with mode: 0644]
lld/test/tent-merge.objtxt [new file with mode: 0644]
lld/tools/CMakeLists.txt [new file with mode: 0644]
lld/tools/lld-core/CMakeLists.txt [new file with mode: 0644]
lld/tools/lld-core/lld-core.cpp [new file with mode: 0644]
lld/tools/lld/CMakeLists.txt [new file with mode: 0644]
lld/tools/lld/lld.cpp [new file with mode: 0644]
lld/utils/astyle-options [new file with mode: 0644]

diff --git a/lld/.gitignore b/lld/.gitignore
new file mode 100644 (file)
index 0000000..1682afa
--- /dev/null
@@ -0,0 +1,16 @@
+#==============================================================================#
+# This file specifies intentionally untracked files that git should ignore.
+# See: http://www.kernel.org/pub/software/scm/git/docs/gitignore.html
+#==============================================================================#
+
+#==============================================================================#
+# File extensions to be ignored anywhere in the tree.
+#==============================================================================#
+# Temp files created by most text editors.
+*~
+# Merge files created by git.
+*.orig
+# Byte compiled python modules.
+*.pyc
+# vim swap files
+.*.swp
diff --git a/lld/CMakeLists.txt b/lld/CMakeLists.txt
new file mode 100644 (file)
index 0000000..4fe1e01
--- /dev/null
@@ -0,0 +1,121 @@
+# If we are not building as a part of LLVM, build lld as a standalone project,
+# using LLVM as an external library.
+
+if (CMAKE_SOURCE_DIR STREQUAL CMAKE_CURRENT_SOURCE_DIR)
+  project(lld)
+  cmake_minimum_required(VERSION 2.8)
+
+  set(LLD_PATH_TO_LLVM_SOURCE "" CACHE PATH
+    "Path to LLVM source code. Not necessary if using an installed LLVM.")
+  set(LLD_PATH_TO_LLVM_BUILD "" CACHE PATH
+    "Path to the directory where LLVM was built or installed.")
+
+  if (LLD_PATH_TO_LLVM_SOURCE)
+    if (NOT EXISTS "${LLD_PATH_TO_LLVM_SOURCE}/cmake/config-ix.cmake")
+      message(FATAL_ERROR "Please set LLD_PATH_TO_LLVM_SOURCE to the root "
+              "directory of LLVM source code.")
+    else()
+      get_filename_component(LLVM_MAIN_SRC_DIR ${LLD_PATH_TO_LLVM_SOURCE}
+                             ABSOLUTE)
+      list(APPEND CMAKE_MODULE_PATH "${LLVM_MAIN_SRC_DIR}/cmake/modules")
+    endif()
+  endif()
+
+  list(APPEND CMAKE_MODULE_PATH "${LLD_PATH_TO_LLVM_BUILD}/share/llvm/cmake")
+
+  get_filename_component(PATH_TO_LLVM_BUILD ${LLD_PATH_TO_LLVM_BUILD}
+                         ABSOLUTE)
+
+  include(AddLLVM)
+  include("${LLD_PATH_TO_LLVM_BUILD}/share/llvm/cmake/LLVMConfig.cmake")
+  include(HandleLLVMOptions)
+
+  set(PACKAGE_VERSION "${LLVM_PACKAGE_VERSION}")
+
+  set(LLVM_MAIN_INCLUDE_DIR "${LLVM_MAIN_SRC_DIR}/include")
+  set(LLVM_BINARY_DIR ${CMAKE_BINARY_DIR})
+
+  set(CMAKE_INCLUDE_CURRENT_DIR ON)
+  include_directories("${PATH_TO_LLVM_BUILD}/include"
+                      "${LLVM_MAIN_INCLUDE_DIR}")
+  link_directories("${PATH_TO_LLVM_BUILD}/lib")
+
+  set(CMAKE_RUNTIME_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/bin)
+  set(CMAKE_LIBRARY_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/lib)
+  set(CMAKE_ARCHIVE_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/lib)
+
+  set(LLD_BUILT_STANDALONE 1)
+endif()
+
+set(LLD_SOURCE_DIR ${CMAKE_CURRENT_SOURCE_DIR})
+set(LLD_BINARY_DIR ${CMAKE_CURRENT_BINARY_DIR})
+
+if (CMAKE_SOURCE_DIR STREQUAL CMAKE_BINARY_DIR)
+  message(FATAL_ERROR "In-source builds are not allowed. CMake would overwrite "
+"the makefiles distributed with LLVM. Please create a directory and run cmake "
+"from there, passing the path to this source directory as the last argument. "
+"This process created the file `CMakeCache.txt' and the directory "
+"`CMakeFiles'. Please delete them.")
+endif()
+
+macro(add_lld_library name)
+  llvm_process_sources(srcs ${ARGN})
+  if (MSVC_IDE OR XCODE)
+    string(REGEX MATCHALL "/[^/]+" split_path ${CMAKE_CURRENT_SOURCE_DIR})
+    list(GET split_path -1 dir)
+    file(GLOB_RECURSE headers
+      ../../include/lld${dir}/*.h)
+    set(srcs ${srcs} ${headers})
+  endif()
+  if (MODULE)
+    set(libkind MODULE)
+  elseif (SHARED_LIBRARY)
+    set(libkind SHARED)
+  else()
+    set(libkind)
+  endif()
+  add_library(${name} ${libkind} ${srcs})
+  if (LLVM_COMMON_DEPENDS)
+    add_dependencies(${name} ${LLVM_COMMON_DEPENDS})
+  endif()
+
+  target_link_libraries(${name} ${LLVM_USED_LIBS})
+  llvm_config(${name} ${LLVM_LINK_COMPONENTS})
+  target_link_libraries(${name} ${LLVM_COMMON_LIBS})
+  link_system_libs(${name})
+
+  if(MSVC)
+    get_target_property(cflag ${name} COMPILE_FLAGS)
+    if(NOT cflag)
+      set(cflag "")
+    endif(NOT cflag)
+    set(cflag "${cflag} /Za")
+    set_target_properties(${name} PROPERTIES COMPILE_FLAGS ${cflag})
+  endif(MSVC)
+  install(TARGETS ${name}
+    LIBRARY DESTINATION lib${LLVM_LIBDIR_SUFFIX}
+    ARCHIVE DESTINATION lib${LLVM_LIBDIR_SUFFIX})
+  set_target_properties(${name} PROPERTIES FOLDER "lld libraries")
+endmacro(add_lld_library)
+
+macro(add_lld_executable name)
+  add_llvm_executable(${name} ${ARGN})
+  set_target_properties(${name} PROPERTIES FOLDER "lld executables")
+endmacro(add_lld_executable)
+
+include_directories(BEFORE
+  ${CMAKE_CURRENT_BINARY_DIR}/include
+  ${CMAKE_CURRENT_SOURCE_DIR}/include
+  )
+
+install(DIRECTORY include/
+  DESTINATION include
+  FILES_MATCHING
+  PATTERN "*.h"
+  PATTERN ".svn" EXCLUDE
+  )
+
+add_subdirectory(lib)
+add_subdirectory(tools)
+
+add_subdirectory(test)
diff --git a/lld/include/lld/Core/AliasAtom.h b/lld/include/lld/Core/AliasAtom.h
new file mode 100644 (file)
index 0000000..8fc780a
--- /dev/null
@@ -0,0 +1,56 @@
+//===- Core/AliasAtom.h - Alias to another Atom ---------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_ALIAS_ATOM_H_
+#define LLD_CORE_ALIAS_ATOM_H_
+
+#include "lld/Core/Atom.h"
+
+#include "llvm/ADT/StringRef.h"
+
+namespace lld {
+
+class AliasAtom : public Atom {
+public:
+  AliasAtom(llvm::StringRef nm, const Atom &target,  Atom::Scope scope)
+    : Atom( target.definition()
+          , Atom::combineNever
+          , scope
+          , target.contentType()
+          , target.sectionChoice()
+          , target.userVisibleName()
+          , target.deadStrip()
+          , target.isThumb()
+          , true
+          , target.alignment()
+          )
+    , _name(nm)
+    , _aliasOf(target) {}
+
+  // overrides of Atom
+  virtual const File *file() const {
+    return _aliasOf.file();
+  }
+
+  virtual bool translationUnitSource(llvm::StringRef &path) const {
+    return _aliasOf.translationUnitSource(path);
+  }
+
+  virtual llvm::StringRef name() const {
+    return _name;
+  }
+
+private:
+  const llvm::StringRef _name;
+  const Atom &_aliasOf;
+};
+
+} // namespace lld
+
+#endif // LLD_CORE_ALIAS_ATOM_H_
diff --git a/lld/include/lld/Core/Atom.h b/lld/include/lld/Core/Atom.h
new file mode 100644 (file)
index 0000000..b8008e4
--- /dev/null
@@ -0,0 +1,197 @@
+//===- Core/Atom.h - The Fundimental Unit of Linking ----------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_ATOM_H_
+#define LLD_CORE_ATOM_H_
+
+#include "lld/Core/Reference.h"
+
+namespace llvm {
+  template <typename T>
+  class ArrayRef;
+
+  class StringRef;
+}
+
+namespace lld {
+
+class File;
+
+/// An atom is the fundamental unit of linking.  A C function or global variable
+/// is an atom.  An atom has content and attributes. The content of a function
+/// atom is the instructions that implement the function.  The content of a
+/// global variable atom is its initial bytes.
+class Atom {
+public:
+  enum Scope {
+    scopeTranslationUnit,   // static, private to translation unit
+    scopeLinkageUnit,       // hidden, accessible to just atoms being linked
+    scopeGlobal             // default
+  };
+
+  enum Definition {
+    definitionRegular,      // usual C/C++ function or global variable
+    definitionTentative,    // C-only pre-ANSI support aka common
+    definitionAbsolute,     // asm-only (foo = 10) not tied to any content
+    definitionUndefined,    // Only in .o files to model reference to undef
+    definitionSharedLibrary // Only in shared libraries to model export
+  };
+
+  enum Combine {
+    combineNever,            // most symbols
+    combineByName,           // weak-definition symbol
+    combineByTypeContent,    // simple constant that can be coalesced
+    combineByTypeContentDeep // complex coalescable constants
+  };
+
+  enum ContentType {
+    typeUnknown,            // for use with definitionUndefined
+    typeCode,               // executable code
+    typeResolver,           // function which returns address of target
+    typeBranchIsland,       // linker created for large binaries
+    typeBranchShim,         // linker created to switch thumb mode
+    typeStub,               // linker created for calling external function
+    typeStubHelper,         // linker created for initial stub binding
+    typeConstant,           // a read-only constant
+    typeCString,            // a zero terminated UTF8 C string
+    typeUTF16String,        // a zero terminated UTF16 string
+    typeCFI,                // a FDE or CIE from dwarf unwind info
+    typeLSDA,               // extra unwinding info
+    typeLiteral4,           // a four-btye read-only constant
+    typeLiteral8,           // an eight-btye read-only constant
+    typeLiteral16,          // a sixteen-btye read-only constant
+    typeData,               // read-write data
+    typeZeroFill,           // zero-fill data
+    typeObjC1Class,         // ObjC1 class [Darwin]
+    typeLazyPointer,        // pointer through which a stub jumps
+    typeLazyDylibPointer,   // pointer through which a stub jumps [Darwin]
+    typeCFString,           // NS/CFString object [Darwin]
+    typeGOT,                // pointer to external symbol
+    typeInitializerPtr,     // pointer to initializer function
+    typeTerminatorPtr,      // pointer to terminator function
+    typeCStringPtr,         // pointer to UTF8 C string [Darwin]
+    typeObjCClassPtr,       // pointer to ObjC class [Darwin]
+    typeObjC2CategoryList,  // pointers to ObjC category [Darwin]
+    typeDTraceDOF,          // runtime data for Dtrace [Darwin]
+    typeTempLTO,            // temporary atom for bitcode reader
+    typeCompactUnwindInfo,  // runtime data for unwinder [Darwin]
+    typeThunkTLV,           // thunk used to access a TLV [Darwin]
+    typeTLVInitialData,     // initial data for a TLV [Darwin]
+    typeTLVInitialZeroFill, // TLV initial zero fill data [Darwin]
+    typeTLVInitializerPtr,  // pointer to thread local initializer [Darwin]
+    typeFirstInSection,     // label for boundary of section [Darwin]
+    typeLastInSection,      // label for boundary of section [Darwin]
+  };
+
+  enum ContentPermissions {
+    perm___  = 0,           // mapped as unacessible
+    permR__  = 8,           // mapped read-only
+    permR_X  = 8 + 2,       // mapped readable and executable
+    permRW_  = 8 + 4,       // mapped readable and writable
+    permRW_L = 8 + 4 + 1,   // initially mapped r/w, then made read-only
+                            // loader writable
+  };
+
+  enum SectionChoice {
+    sectionBasedOnContent,  // linker infers final section based on content
+    sectionCustomPreferred, // linker may place in specific section
+    sectionCustomRequired   // linker must place in specific section
+  };
+
+  struct Alignment {
+    Alignment(int p2, int m = 0)
+      : powerOf2(p2)
+      , modulus(m) {}
+
+    uint16_t powerOf2;
+    uint16_t modulus;
+  };
+
+  // MacOSX specific compact unwind info
+  struct UnwindInfo {
+    uint32_t startOffset;
+    uint32_t unwindInfo;
+
+    typedef UnwindInfo *iterator;
+  };
+
+  // link-once (throw away if not used)??
+  // dll import/export
+
+  Scope scope() const { return _scope; }
+  Definition definition() const { return _definition; }
+  Combine combine() const { return _combine; }
+  ContentType contentType() const { return _contentType; }
+  Alignment alignment() const;
+  SectionChoice sectionChoice() const { return _sectionChoice; }
+  bool deadStrip() const { return _DeadStrip; }
+  bool isThumb() const { return _thumb; }
+  bool isAlias() const { return _alias; }
+  bool userVisibleName() const { return _userVisibleName; }
+  bool autoHide() const;
+  void setLive(bool l) { _live = l; }
+  bool live() const { return _live; }
+  void setOverridesDylibsWeakDef();
+
+  virtual const class File *file() const = 0;
+  virtual bool translationUnitSource(llvm::StringRef &path) const;
+  virtual llvm::StringRef name() const;
+  virtual uint64_t objectAddress() const = 0;
+  virtual llvm::StringRef customSectionName() const;
+  virtual uint64_t size() const = 0;
+  virtual ContentPermissions permissions() const { return perm___; }
+  virtual void copyRawContent(uint8_t buffer[]) const = 0;
+  virtual llvm::ArrayRef<uint8_t> rawContent() const;
+  virtual Reference::iterator referencesBegin() const;
+  virtual Reference::iterator referencesEnd() const;
+  virtual UnwindInfo::iterator beginUnwind() const;
+  virtual UnwindInfo::iterator endUnwind() const;
+
+  Atom( Definition d
+      , Combine c
+      , Scope s
+      , ContentType ct
+      , SectionChoice sc
+      , bool UserVisibleName
+      , bool DeadStrip
+      , bool IsThumb
+      , bool IsAlias
+      , Alignment a)
+    : _alignmentModulus(a.modulus)
+    , _alignmentPowerOf2(a.powerOf2)
+    , _definition(d)
+    , _combine(c)
+    , _userVisibleName(UserVisibleName)
+    , _DeadStrip(DeadStrip)
+    , _thumb(IsThumb)
+    , _alias(IsAlias)
+    , _contentType(ct)
+    , _scope(s)
+    , _sectionChoice(sc) {}
+
+  virtual ~Atom();
+
+protected:
+  uint16_t _alignmentModulus;
+  uint8_t _alignmentPowerOf2;
+  Definition _definition : 3;
+  Combine _combine : 2;
+  bool _userVisibleName : 1;
+  bool _DeadStrip : 1;
+  bool _thumb : 1;
+  bool _alias : 1;
+  bool _live : 1;
+  ContentType _contentType : 8;
+  Scope _scope : 2;
+  SectionChoice _sectionChoice: 2;
+};
+
+} // namespace lld
+
+#endif // LLD_CORE_ATOM_H_
diff --git a/lld/include/lld/Core/File.h b/lld/include/lld/Core/File.h
new file mode 100644 (file)
index 0000000..03d7887
--- /dev/null
@@ -0,0 +1,43 @@
+//===- Core/File.h - A Contaier of Atoms ----------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_FILE_H_
+#define LLD_CORE_FILE_H_
+
+#include "llvm/ADT/StringRef.h"
+
+namespace lld {
+
+class File {
+public:
+  File(llvm::StringRef p) : _path(p) {}
+  ~File();
+
+  class AtomHandler {
+  public:
+    virtual ~AtomHandler() {}
+    virtual void doAtom(const class Atom &) = 0;
+    virtual void doFile(const class File &) = 0;
+  };
+
+  llvm::StringRef path() const  {
+    return _path;
+  }
+
+  virtual bool forEachAtom(AtomHandler &) const = 0;
+  virtual bool justInTimeforEachAtom( llvm::StringRef name
+                                    , AtomHandler &) const = 0;
+
+private:
+  llvm::StringRef _path;
+};
+
+} // namespace lld
+
+#endif // LLD_CORE_FILE_H_
diff --git a/lld/include/lld/Core/InputFiles.h b/lld/include/lld/Core/InputFiles.h
new file mode 100644 (file)
index 0000000..533d07e
--- /dev/null
@@ -0,0 +1,40 @@
+//===- Core/InputFiles.h - The set of Input Files to the Linker -----------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_INPUT_FILES_H_
+#define LLD_CORE_INPUT_FILES_H_
+
+#include "lld/Core/File.h"
+
+#include <vector>
+
+namespace lld {
+
+/// This InputFiles class manages access to all input files to the linker.
+///
+/// The forEachInitialAtom() method iterates object files to add at
+/// the start of the link.
+///
+/// The searchLibraries() method is used to lazily search libraries.
+class InputFiles {
+public:
+  /// @brief iterates all atoms in initial files
+  virtual void forEachInitialAtom(File::AtomHandler &) const = 0;
+
+  /// @brief searches libraries for name
+  virtual bool searchLibraries(  llvm::StringRef name
+                               , bool searchDylibs
+                               , bool searchArchives
+                               , bool dataSymbolOnly
+                               , File::AtomHandler &) const = 0;
+};
+
+} // namespace lld
+
+#endif // LLD_CORE_INPUT_FILES_H_
diff --git a/lld/include/lld/Core/Reference.h b/lld/include/lld/Core/Reference.h
new file mode 100644 (file)
index 0000000..23bf233
--- /dev/null
@@ -0,0 +1,32 @@
+//===- Core/References.h - A Reference to Another Atom --------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_REFERENCES_H_
+#define LLD_CORE_REFERENCES_H_
+
+#include "llvm/Support/DataTypes.h"
+
+namespace lld {
+
+class Atom;
+
+class Reference {
+public:
+  typedef Reference *iterator;
+
+  const Atom *target;
+  uint64_t    addend;
+  uint32_t    offsetInAtom;
+  uint16_t    kind;
+  uint16_t    flags;
+};
+
+} // namespace lld
+
+#endif // LLD_CORE_REFERENCES_H_
diff --git a/lld/include/lld/Core/Resolver.h b/lld/include/lld/Core/Resolver.h
new file mode 100644 (file)
index 0000000..e739679
--- /dev/null
@@ -0,0 +1,82 @@
+//===- Core/Resolver.h - Resolves Atom References -------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_RESOLVER_H_
+#define LLD_CORE_RESOLVER_H_
+
+#include "lld/Core/File.h"
+#include "lld/Core/SymbolTable.h"
+
+#include <vector>
+#include <set>
+
+namespace lld {
+
+class Atom;
+class InputFiles;
+class Platform;
+class SymbolTable;
+
+/// The Resolver is responsible for merging all input object files
+/// and producing a merged graph.
+///
+/// All platform specific resolving is done by delegating to the
+/// Platform object specified.
+class Resolver : public File::AtomHandler {
+public:
+  Resolver(Platform &plat, const InputFiles &inputs)
+    : _platform(plat)
+    , _inputFiles(inputs)
+    , _haveLLVMObjs(false)
+    , _addToFinalSection(false)
+    , _completedInitialObjectFiles(false) {}
+
+  // AtomHandler methods
+  virtual void doAtom(const Atom &);
+  virtual void doFile(const File &);
+
+  /// @brief do work of merging and resolving and return list
+  std::vector<const Atom *> &resolve();
+
+private:
+  struct WhyLiveBackChain {
+    WhyLiveBackChain *previous;
+    const Atom *referer;
+  };
+
+  void initializeState();
+  void addInitialUndefines();
+  void buildInitialAtomList();
+  void resolveUndefines();
+  void updateReferences();
+  void deadStripOptimize();
+  void checkUndefines(bool final);
+  void removeCoalescedAwayAtoms();
+  void checkDylibSymbolCollisions();
+  void linkTimeOptimize();
+  void tweakAtoms();
+
+  const Atom *entryPoint();
+  void markLive(const Atom &atom, WhyLiveBackChain *previous);
+  void addAtoms(const std::vector<const Atom *>&);
+
+  Platform &_platform;
+  const InputFiles &_inputFiles;
+  SymbolTable _symbolTable;
+  std::vector<const Atom *> _atoms;
+  std::set<const Atom *> _deadStripRoots;
+  std::vector<const Atom *> _atomsWithUnresolvedReferences;
+  bool _haveLLVMObjs;
+  bool _addToFinalSection;
+  bool _completedInitialObjectFiles;
+};
+
+} // namespace lld
+
+#endif // LLD_CORE_RESOLVER_H_
diff --git a/lld/include/lld/Core/SymbolTable.h b/lld/include/lld/Core/SymbolTable.h
new file mode 100644 (file)
index 0000000..70aea36
--- /dev/null
@@ -0,0 +1,61 @@
+//===- Core/SymbolTable.h - Main Symbol Table -----------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_SYMBOL_TABLE_H_
+#define LLD_CORE_SYMBOL_TABLE_H_
+
+#include <cstring>
+#include <map>
+#include <vector>
+
+namespace llvm { class StringRef; }
+
+namespace lld {
+
+class Atom;
+
+/// The SymbolTable class is responsible for coalescing atoms.
+///
+/// All atoms coalescable by-name or by-content should be added.
+/// The method replacement() can be used to find the replacement atom
+/// if an atom has been coalesced away.
+class SymbolTable {
+public:
+  /// @brief add atom to symbol table
+  void add(const Atom &);
+
+  /// @brief checks if name is in symbol table and if so atom is not
+  ///        UndefinedAtom
+  bool isDefined(llvm::StringRef sym);
+
+  /// @brief returns atom in symbol table for specified name (or NULL)
+  const Atom *findByName(llvm::StringRef sym);
+
+  /// @brief returns vector of remaining UndefinedAtoms
+  void undefines(std::vector<const Atom *>&);
+
+  /// @brief count of by-name entries in symbol table
+  unsigned int size();
+
+  /// @brief if atom has been coalesced away, return replacement, else return atom
+  const Atom *replacement(const Atom *);
+
+private:
+  typedef std::map<llvm::StringRef, const Atom *> NameToAtom;
+  typedef std::map<const Atom *, const Atom *> AtomToAtom;
+
+  void addByName(const Atom &);
+
+  AtomToAtom _replacedAtoms;
+  NameToAtom _nameTable;
+};
+
+} // namespace lld
+
+#endif // LLD_CORE_SYMBOL_TABLE_H_
diff --git a/lld/include/lld/Core/UndefinedAtom.h b/lld/include/lld/Core/UndefinedAtom.h
new file mode 100644 (file)
index 0000000..815ea8d
--- /dev/null
@@ -0,0 +1,66 @@
+//===- Core/UndefinedAtom.h - An Undefined Atom ---------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_UNDEFINED_ATOM_H_
+#define LLD_CORE_UNDEFINED_ATOM_H_
+
+#include "lld/Core/Atom.h"
+
+#include "llvm/ADT/StringRef.h"
+
+namespace lld {
+
+/// An UndefinedAtom has no content.
+/// It exists as a place holder for a future atom.
+class UndefinedAtom : public Atom {
+public:
+  UndefinedAtom(llvm::StringRef nm)
+    : Atom( Atom::definitionUndefined
+          , Atom::combineNever
+          , Atom::scopeLinkageUnit
+          , Atom::typeUnknown
+          , Atom::sectionBasedOnContent
+          , true
+          , false
+          , false
+          , false
+          , Atom::Alignment(0))
+    , _name(nm) {}
+
+  // overrides of Atom
+  virtual const File *file() const {
+    return 0;
+  }
+
+  virtual bool translationUnitSource(llvm::StringRef path) const {
+    return false;
+  }
+
+  virtual llvm::StringRef name() const {
+    return _name;
+  }
+  virtual uint64_t size() const {
+    return 0;
+  }
+  virtual uint64_t objectAddress() const {
+    return 0;
+  }
+  virtual void copyRawContent(uint8_t buffer[]) const { }
+  virtual void setScope(Scope) { }
+  bool weakImport();
+
+protected:
+  virtual ~UndefinedAtom() {}
+
+  llvm::StringRef _name;
+};
+
+} // namespace lld
+
+#endif // LLD_CORE_UNDEFINED_ATOM_H_
diff --git a/lld/include/lld/Core/YamlReader.h b/lld/include/lld/Core/YamlReader.h
new file mode 100644 (file)
index 0000000..b2caf6a
--- /dev/null
@@ -0,0 +1,30 @@
+//===- Core/YamlReader.h - Reads YAML -------------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_YAML_READER_H_
+#define LLD_CORE_YAML_READER_H_
+
+#include "lld/Core/File.h"
+
+#include "llvm/Support/system_error.h"
+
+#include <vector>
+
+namespace llvm { class MemoryBuffer; }
+
+namespace lld {
+namespace yaml {
+
+llvm::error_code parseObjectText(  llvm::MemoryBuffer *mb
+                                 , std::vector<File *>&);
+
+} // namespace yaml
+} // namespace lld
+
+#endif // LLD_CORE_YAML_READER_H_
diff --git a/lld/include/lld/Core/YamlWriter.h b/lld/include/lld/Core/YamlWriter.h
new file mode 100644 (file)
index 0000000..6a07e82
--- /dev/null
@@ -0,0 +1,25 @@
+//===- Core/YamlWriter.h - Writes YAML ------------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_CORE_YAML_WRITER_H_
+#define LLD_CORE_YAML_WRITER_H_
+
+#include "lld/Core/File.h"
+
+#include "llvm/Support/raw_ostream.h"
+
+namespace lld {
+namespace yaml {
+
+void writeObjectText(File *, llvm::raw_ostream &);
+
+} // namespace yaml
+} // namespace lld
+
+#endif // LLD_CORE_YAML_WRITER_H_
diff --git a/lld/include/lld/Platform/Platform.h b/lld/include/lld/Platform/Platform.h
new file mode 100644 (file)
index 0000000..162fd40
--- /dev/null
@@ -0,0 +1,80 @@
+//===- Platform/Platform.h - Platform Interface ---------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_PLATFORM_PLATFORM_H_
+#define LLD_PLATFORM_PLATFORM_H_
+
+#include <vector>
+
+namespace lld {
+class Atom;
+
+/// The Platform class encapsulated plaform specific linking knowledge.
+///
+/// Much of what it does is driving by platform specific linker options.
+class Platform {
+public:
+  virtual void initialize() = 0;
+
+  /// @brief tell platform object another file has been added
+  virtual void fileAdded(const File &file) = 0;
+
+  /// @brief tell platform object another atom has been added
+  virtual void atomAdded(const Atom &file) = 0;
+
+  /// @brief give platform a chance to change each atom's scope
+  virtual void adjustScope(const Atom &atom) = 0;
+
+  /// @brief if specified atom needs alternate names, return AliasAtom(s)
+  virtual bool getAliasAtoms(const Atom &atom,
+                             std::vector<const Atom *>&) = 0;
+
+  /// @brief give platform a chance to resolve platform-specific undefs
+  virtual bool getPlatformAtoms(llvm::StringRef undefined,
+                                std::vector<const Atom *>&) = 0;
+
+  /// @brief resolver should remove unreferenced atoms
+  virtual bool deadCodeStripping() = 0;
+
+  /// @brief atom must be kept so should be root of dead-strip graph
+  virtual bool isDeadStripRoot(const Atom &atom) = 0;
+
+  /// @brief if target must have some atoms, denote here
+  virtual bool getImplicitDeadStripRoots(std::vector<const Atom *>&) = 0;
+
+  /// @brief return entry point for output file (e.g. "main") or NULL
+  virtual llvm::StringRef entryPointName() = 0;
+
+  /// @brief for iterating must-be-defined symbols ("main" or -u command line
+  ///        option)
+  typedef llvm::StringRef const *UndefinesIterator;
+  virtual UndefinesIterator  initialUndefinesBegin() const = 0;
+  virtual UndefinesIterator  initialUndefinesEnd() const = 0;
+
+  /// @brief if platform wants resolvers to search libraries for overrides
+  virtual bool searchArchivesToOverrideTentativeDefinitions() = 0;
+  virtual bool searchSharedLibrariesToOverrideTentativeDefinitions() = 0;
+
+  /// @brief if platform allows symbol to remain undefined (e.g. -r)
+  virtual bool allowUndefinedSymbol(llvm::StringRef name) = 0;
+
+  /// @brief for debugging dead code stripping, -why_live
+  virtual bool printWhyLive(llvm::StringRef name) = 0;
+
+  /// @brief print out undefined symbol error messages in platform specific way
+  virtual void errorWithUndefines(const std::vector<const Atom *>& undefs,
+                                  const std::vector<const Atom *>& all) = 0;
+
+  /// @brief last chance for platform to tweak atoms
+  virtual void postResolveTweaks(std::vector<const Atom *>& all) = 0;
+};
+
+} // namespace lld
+
+#endif // LLD_PLATFORM_PLATFORM_H_
diff --git a/lld/include/lld/Platform/PlatformDarwin.h b/lld/include/lld/Platform/PlatformDarwin.h
new file mode 100644 (file)
index 0000000..d2cf42c
--- /dev/null
@@ -0,0 +1,29 @@
+//===- Platform/PlatformDarwin.h - Darwin Platform Implementation ---------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_PLATFORM_PLATFORM_H_
+#define LLD_PLATFORM_PLATFORM_H_
+
+#include "lld/Platform/Platform.h"
+
+namespace lld {
+
+class PlatformDarwin : public Platform {
+  virtual void initialize();
+
+  // keep track of: ObjC GC-ness, if any .o file cannot be scattered,
+  // cpu-sub-type
+  virtual void fileAdded(const File &file);
+
+  virtual bool deadCodeStripping();
+};
+
+} // namespace lld
+
+#endif // LLD_PLATFORM_PLATFORM_H_
diff --git a/lld/lib/CMakeLists.txt b/lld/lib/CMakeLists.txt
new file mode 100644 (file)
index 0000000..194a13a
--- /dev/null
@@ -0,0 +1 @@
+add_subdirectory(Core)
diff --git a/lld/lib/Core/Atom.cpp b/lld/lib/Core/Atom.cpp
new file mode 100644 (file)
index 0000000..482a21f
--- /dev/null
@@ -0,0 +1,51 @@
+//===- Core/Atom.cpp - The Fundimental Unit of Linking --------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lld/Core/Atom.h"
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace lld {
+
+  Atom::~Atom() {}
+
+  bool Atom::translationUnitSource(llvm::StringRef &path) const {
+    return false;
+  }
+
+  llvm::StringRef Atom::name() const {
+    return llvm::StringRef();
+  }
+
+  llvm::StringRef Atom::customSectionName() const {
+    return llvm::StringRef();
+  }
+
+  llvm::ArrayRef<uint8_t> Atom::rawContent() const {
+    return llvm::ArrayRef<uint8_t>();
+  }
+
+  Reference::iterator Atom::referencesBegin() const {
+    return 0;
+  }
+
+  Reference::iterator Atom::referencesEnd() const{
+    return 0;
+  }
+
+  Atom::UnwindInfo::iterator Atom::beginUnwind() const{
+    return 0;
+  }
+
+  Atom::UnwindInfo::iterator Atom::endUnwind() const{
+    return 0;
+  }
+
+} // namespace lld
diff --git a/lld/lib/Core/CMakeLists.txt b/lld/lib/Core/CMakeLists.txt
new file mode 100644 (file)
index 0000000..66de63d
--- /dev/null
@@ -0,0 +1,8 @@
+add_lld_library(lldCore
+  Atom.cpp
+  File.cpp
+  Resolver.cpp
+  SymbolTable.cpp
+  YamlReader.cpp
+  YamlWriter.cpp
+  )
diff --git a/lld/lib/Core/File.cpp b/lld/lib/Core/File.cpp
new file mode 100644 (file)
index 0000000..e123d5e
--- /dev/null
@@ -0,0 +1,16 @@
+//===- Core/File.cpp - A Contaier of Atoms --------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lld/Core/File.h"
+
+namespace lld {
+
+File::~File() {}
+
+}
diff --git a/lld/lib/Core/Resolver.cpp b/lld/lib/Core/Resolver.cpp
new file mode 100644 (file)
index 0000000..b3be26b
--- /dev/null
@@ -0,0 +1,337 @@
+//===- Core/Resolver.cpp - Resolves Atom References -----------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lld/Core/Resolver.h"
+#include "lld/Core/Atom.h"
+#include "lld/Core/File.h"
+#include "lld/Core/InputFiles.h"
+#include "lld/Core/SymbolTable.h"
+#include "lld/Core/UndefinedAtom.h"
+#include "lld/Platform/Platform.h"
+
+#include "llvm/Support/raw_ostream.h"
+
+#include <algorithm>
+#include <cassert>
+#include <vector>
+
+namespace lld {
+
+class NotLive {
+public:
+  bool operator()(const Atom *atom) const {
+    return !(atom->live() || !atom->deadStrip());
+  }
+};
+
+class AtomCoalescedAway {
+public:
+  AtomCoalescedAway(SymbolTable &sym) : _symbolTable(sym) {}
+
+  bool operator()(const Atom *atom) const {
+    const Atom *rep = _symbolTable.replacement(atom);
+    return rep != atom;
+  }
+
+private:
+  SymbolTable &_symbolTable;
+};
+
+void Resolver::initializeState() {
+  _platform.initialize();
+}
+
+// add initial undefines from -u option
+void Resolver::addInitialUndefines() {
+
+}
+
+// add all atoms from all initial .o files
+void Resolver::buildInitialAtomList() {
+  // each input files contributes initial atoms
+  _atoms.reserve(1024);
+  _inputFiles.forEachInitialAtom(*this);
+
+  _completedInitialObjectFiles = true;
+}
+
+
+// called before the first atom in any file is added with doAtom()
+void Resolver::doFile(const File &file) {
+  // notify platform
+  _platform.fileAdded(file);
+}
+
+// called on each atom when a file is added
+void Resolver::doAtom(const Atom &atom) {
+  // notify platform
+  _platform.atomAdded(atom);
+
+  // add to list of known atoms
+  _atoms.push_back(&atom);
+
+  // adjust scope (e.g. force some globals to be hidden)
+  _platform.adjustScope(atom);
+
+  // non-static atoms need extra handling
+  if (atom.scope() != Atom::scopeTranslationUnit) {
+    // tell symbol table about non-static atoms
+    _symbolTable.add(atom);
+
+    // platform can add aliases for any symbol
+    std::vector<const Atom *> aliases;
+    if (_platform.getAliasAtoms(atom, aliases))
+      this->addAtoms(aliases);
+  }
+
+  if (_platform.deadCodeStripping()) {
+    // add to set of dead-strip-roots, all symbols that
+    // the compiler marks as don't strip
+    if (!atom.deadStrip())
+      _deadStripRoots.insert(&atom);
+
+    // add to set of dead-strip-roots, all symbols that
+    // the platform decided must remain
+    if (_platform.isDeadStripRoot(atom))
+      _deadStripRoots.insert(&atom);
+  }
+}
+
+// utility to add a vector of atoms
+void Resolver::addAtoms(const std::vector<const Atom *> &newAtoms) {
+  for (std::vector<const Atom *>::const_iterator it = newAtoms.begin();
+       it != newAtoms.end(); ++it) {
+    this->doAtom(**it);
+  }
+}
+
+// ask symbol table if any definitionUndefined atoms still exist
+// if so, keep searching libraries until no more atoms being added
+void Resolver::resolveUndefines() {
+  const bool searchArchives =
+    _platform.searchArchivesToOverrideTentativeDefinitions();
+  const bool searchDylibs =
+    _platform.searchSharedLibrariesToOverrideTentativeDefinitions();
+
+  // keep looping until no more undefines were added in last loop
+  unsigned int undefineGenCount = 0xFFFFFFFF;
+  while (undefineGenCount != _symbolTable.size()) {
+    undefineGenCount = _symbolTable.size();
+    std::vector<const Atom *> undefines;
+    _symbolTable.undefines(undefines);
+    for (std::vector<const Atom *>::iterator it = undefines.begin();
+         it != undefines.end(); ++it) {
+      llvm::StringRef undefName = (*it)->name();
+      // load for previous undefine may also have loaded this undefine
+      if (!_symbolTable.isDefined(undefName)) {
+        _inputFiles.searchLibraries(undefName, true, true, false, *this);
+
+        // give platform a chance to instantiate platform
+        // specific atoms (e.g. section boundary)
+        if (!_symbolTable.isDefined(undefName)) {
+          std::vector<const Atom *> platAtoms;
+          if (_platform.getPlatformAtoms(undefName, platAtoms))
+            this->addAtoms(platAtoms);
+        }
+      }
+    }
+    // search libraries for overrides of common symbols
+    if (searchArchives || searchDylibs) {
+      std::vector<const Atom *> tents;
+      for (std::vector<const Atom *>::iterator ait = _atoms.begin();
+           ait != _atoms.end(); ++ait) {
+        const Atom *atom = *ait;
+        if (atom->definition() == Atom::definitionTentative)
+          tents.push_back(atom);
+      }
+      for (std::vector<const Atom *>::iterator dit = tents.begin();
+           dit != tents.end(); ++dit) {
+        // load for previous tentative may also have loaded
+        // this tentative, so check again
+        llvm::StringRef tentName = (*dit)->name();
+        const Atom *curAtom = _symbolTable.findByName(tentName);
+        assert(curAtom != NULL);
+        if (curAtom->definition() == Atom::definitionTentative) {
+          _inputFiles.searchLibraries(tentName, searchDylibs, true, true,
+                                      *this);
+        }
+      }
+    }
+  }
+}
+
+// switch all references to undefined or coalesced away atoms
+// to the new defined atom
+void Resolver::updateReferences() {
+  for (std::vector<const Atom *>::iterator it = _atoms.begin();
+       it != _atoms.end(); ++it) {
+    const Atom *atom = *it;
+    for (Reference::iterator rit = atom->referencesBegin(),
+         end = atom->referencesEnd(); rit != end; ++rit) {
+      rit->target = _symbolTable.replacement(rit->target);
+    }
+  }
+}
+
+// for dead code stripping, recursively mark atom "live"
+void Resolver::markLive(const Atom &atom, WhyLiveBackChain *previous) {
+  // if -why_live cares about this symbol, then dump chain
+  if ((previous->referer != NULL) && _platform.printWhyLive(atom.name())) {
+    llvm::errs() << atom.name() << " from " << atom.file()->path() << "\n";
+    int depth = 1;
+    for (WhyLiveBackChain *p = previous; p != NULL;
+         p = p->previous, ++depth) {
+      for (int i = depth; i > 0; --i)
+        llvm::errs() << "  ";
+      llvm::errs() << p->referer->name() << " from "
+                   << p->referer->file()->path() << "\n";
+    }
+  }
+
+  // if already marked live, then done (stop recursion)
+  if (atom.live())
+    return;
+
+  // mark this atom is live
+  const_cast<Atom *>(&atom)->setLive(true);
+
+  // mark all atoms it references as live
+  WhyLiveBackChain thisChain;
+  thisChain.previous = previous;
+  thisChain.referer = &atom;
+  for (Reference::iterator rit = atom.referencesBegin(),
+       end = atom.referencesEnd(); rit != end; ++rit) {
+    this->markLive(*(rit->target), &thisChain);
+  }
+}
+
+// remove all atoms not actually used
+void Resolver::deadStripOptimize() {
+  // only do this optimization with -dead_strip
+  if (!_platform.deadCodeStripping())
+    return;
+
+  // clear liveness on all atoms
+  for (std::vector<const Atom *>::iterator it = _atoms.begin();
+       it != _atoms.end(); ++it) {
+    const Atom *atom = *it;
+    const_cast<Atom *>(atom)->setLive(0);
+  }
+
+  // add entry point (main) to live roots
+  const Atom *entry = this->entryPoint();
+  if (entry != NULL)
+    _deadStripRoots.insert(entry);
+
+  // add -exported_symbols_list, -init, and -u entries to live roots
+  for (Platform::UndefinesIterator uit = _platform.initialUndefinesBegin();
+       uit != _platform.initialUndefinesEnd(); ++uit) {
+    llvm::StringRef sym = *uit;
+    const Atom *symAtom = _symbolTable.findByName(sym);
+    assert(symAtom->definition() != Atom::definitionUndefined);
+    _deadStripRoots.insert(symAtom);
+  }
+
+  // add platform specific helper atoms
+  std::vector<const Atom *> platRootAtoms;
+  if (_platform.getImplicitDeadStripRoots(platRootAtoms))
+    this->addAtoms(platRootAtoms);
+
+  // mark all roots as live, and recursively all atoms they reference
+  for (std::set<const Atom *>::iterator it = _deadStripRoots.begin();
+       it != _deadStripRoots.end(); ++it) {
+    WhyLiveBackChain rootChain;
+    rootChain.previous = NULL;
+    rootChain.referer = *it;
+    this->markLive(**it, &rootChain);
+  }
+
+  // now remove all non-live atoms from _atoms
+  _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
+                              NotLive()), _atoms.end());
+}
+
+// error out if some undefines remain
+void Resolver::checkUndefines(bool final) {
+  // when using LTO, undefines are checked after bitcode is optimized
+  if (_haveLLVMObjs && !final)
+    return;
+
+  // build vector of remaining undefined symbols
+  std::vector<const Atom *> undefinedAtoms;
+  _symbolTable.undefines(undefinedAtoms);
+  if (_platform.deadCodeStripping()) {
+    // when dead code stripping we don't care if dead atoms are undefined
+    undefinedAtoms.erase(std::remove_if(
+                           undefinedAtoms.begin(), undefinedAtoms.end(),
+                           NotLive()), undefinedAtoms.end());
+  }
+
+  // let platform make error message about missing symbols
+  if (undefinedAtoms.size() != 0)
+    _platform.errorWithUndefines(undefinedAtoms, _atoms);
+}
+
+// remove from _atoms all coaleseced away atoms
+void Resolver::removeCoalescedAwayAtoms() {
+  _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
+                              AtomCoalescedAway(_symbolTable)), _atoms.end());
+}
+
+// check for interactions between symbols defined in this linkage unit
+// and same symbol name in linked dynamic shared libraries
+void Resolver::checkDylibSymbolCollisions() {
+  for (std::vector<const Atom *>::const_iterator it = _atoms.begin();
+       it != _atoms.end(); ++it) {
+    const Atom *atom = *it;
+    if (atom->scope() == Atom::scopeGlobal) {
+      if (atom->definition() == Atom::definitionTentative) {
+        // See if any shared library also has symbol which
+        // collides with the tentative definition.
+        // SymbolTable will warn if needed.
+        _inputFiles.searchLibraries(atom->name(), true, false, false, *this);
+      }
+    }
+  }
+}
+
+// get "main" atom for linkage unit
+const Atom *Resolver::entryPoint() {
+  llvm::StringRef symbolName = _platform.entryPointName();
+  if (symbolName != NULL)
+    return _symbolTable.findByName(symbolName);
+
+  return NULL;
+}
+
+// give platform a chance to tweak the set of atoms
+void Resolver::tweakAtoms() {
+  _platform.postResolveTweaks(_atoms);
+}
+
+void Resolver::linkTimeOptimize() {
+  // FIX ME
+}
+
+std::vector<const Atom *> &Resolver::resolve() {
+  this->initializeState();
+  this->addInitialUndefines();
+  this->buildInitialAtomList();
+  this->resolveUndefines();
+  this->updateReferences();
+  this->deadStripOptimize();
+  this->checkUndefines(false);
+  this->removeCoalescedAwayAtoms();
+  this->checkDylibSymbolCollisions();
+  this->linkTimeOptimize();
+  this->tweakAtoms();
+  return _atoms;
+}
+
+} // namespace lld
diff --git a/lld/lib/Core/SymbolTable.cpp b/lld/lib/Core/SymbolTable.cpp
new file mode 100644 (file)
index 0000000..3b77062
--- /dev/null
@@ -0,0 +1,140 @@
+//===- Core/SymbolTable.cpp - Main Symbol Table ---------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lld/Core/SymbolTable.h"
+#include "lld/Core/Atom.h"
+#include "lld/Core/File.h"
+#include "lld/Core/InputFiles.h"
+#include "lld/Core/Resolver.h"
+#include "lld/Core/UndefinedAtom.h"
+#include "lld/Platform/Platform.h"
+
+#include "llvm/Support/ErrorHandling.h"
+
+#include <algorithm>
+#include <cassert>
+#include <stdlib.h>
+#include <vector>
+
+namespace lld {
+
+void SymbolTable::add(const Atom &atom) {
+  assert(atom.scope() != Atom::scopeTranslationUnit);
+  switch (atom.combine()) {
+  case Atom::combineNever:
+  case Atom::combineByName:
+    this->addByName(atom);
+    break;
+  case Atom::combineByTypeContent:
+  case Atom::combineByTypeContentDeep:
+    // TO DO: support constants merging
+    break;
+  }
+}
+
+enum NameCollisionResolution {
+  NCR_First,
+  NCR_Second,
+  NCR_Weak,
+  NCR_Larger,
+  NCR_Error
+};
+
+static NameCollisionResolution cases[5][5] = {
+  //regular     tentative   absolute    undef      sharedLib
+  {
+    // first is regular
+    NCR_Error,  NCR_First,  NCR_Error,  NCR_First, NCR_First
+  },
+  {
+    // first is tentative
+    NCR_Second, NCR_Larger, NCR_Error,  NCR_First, NCR_First
+  },
+  {
+    // first is absolute
+    NCR_Error,  NCR_Error,  NCR_Error,  NCR_First, NCR_First
+  },
+  {
+    // first is undef
+    NCR_Second, NCR_Second, NCR_Second, NCR_First, NCR_Second
+  },
+  {
+    // first is sharedLib
+    NCR_Second, NCR_Second, NCR_Second, NCR_First, NCR_First
+  }
+};
+
+static NameCollisionResolution collide(Atom::Definition first,
+                                       Atom::Definition second) {
+  return cases[first][second];
+}
+
+void SymbolTable::addByName(const Atom &atom) {
+  llvm::StringRef name = atom.name();
+  const Atom *existing = this->findByName(name);
+  if (existing == NULL) {
+    // name is not in symbol table yet, add it associate with this atom
+    _nameTable[name] = &atom;
+  } else {
+    // name is already in symbol table and associated with another atom
+    switch (collide(existing->definition(), atom.definition())) {
+    case NCR_First:
+      // using first, just add new to _replacedAtoms
+      _replacedAtoms[&atom] = existing;
+      break;
+    case NCR_Second:
+      // using second, update tables
+      _nameTable[name] = &atom;
+      _replacedAtoms[existing] = &atom;
+      break;
+    default:
+      llvm::report_fatal_error("unhandled switch clause");
+    }
+  }
+}
+
+const Atom *SymbolTable::findByName(llvm::StringRef sym) {
+  NameToAtom::iterator pos = _nameTable.find(sym);
+  if (pos == _nameTable.end())
+    return NULL;
+  return pos->second;
+}
+
+bool SymbolTable::isDefined(llvm::StringRef sym) {
+  const Atom *atom = this->findByName(sym);
+  if (atom == NULL)
+    return false;
+  if (atom->definition() == Atom::definitionUndefined)
+    return false;
+  return true;
+}
+
+const Atom *SymbolTable::replacement(const Atom *atom) {
+  AtomToAtom::iterator pos = _replacedAtoms.find(atom);
+  if (pos == _replacedAtoms.end())
+    return atom;
+  // might be chain, recurse to end
+  return this->replacement(pos->second);
+}
+
+unsigned int SymbolTable::size() {
+  return _nameTable.size();
+}
+
+void SymbolTable::undefines(std::vector<const Atom *> &undefs) {
+  for (NameToAtom::iterator it = _nameTable.begin(),
+       end = _nameTable.end(); it != end; ++it) {
+    const Atom *atom = it->second;
+    assert(atom != NULL);
+    if (atom->definition() == Atom::definitionUndefined)
+      undefs.push_back(atom);
+  }
+}
+
+} // namespace lld
diff --git a/lld/lib/Core/YamlReader.cpp b/lld/lib/Core/YamlReader.cpp
new file mode 100644 (file)
index 0000000..86dea54
--- /dev/null
@@ -0,0 +1,559 @@
+//===- Core/YamlReader.cpp - Reads YAML -----------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lld/Core/YamlReader.h"
+#include "lld/Core/Atom.h"
+#include "lld/Core/File.h"
+#include "lld/Core/Reference.h"
+
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/system_error.h"
+
+#include <vector>
+
+namespace { const llvm::error_code success; }
+
+namespace lld {
+namespace yaml {
+class YAML {
+public:
+  struct Entry {
+    Entry(const char *k, const char *v, int d, bool bd, bool bs)
+      : key(strdup(k))
+      , value(strdup(v))
+      , depth(d)
+      , beginSequence(bs)
+      , beginDocument(bd) {}
+
+    const char *key;
+    const char *value;
+    int         depth;
+    bool        beginSequence;
+    bool        beginDocument;
+  };
+
+  static void parse(llvm::MemoryBuffer *mb, std::vector<const Entry *>&);
+
+private:
+  enum State {
+    start,
+    inHeaderComment,
+    inTripleDash,
+    inTriplePeriod,
+    inDocument,
+    inKey,
+    inSpaceBeforeValue,
+    inValue,
+    inValueSequence,
+    inValueSequenceEnd
+  };
+};
+
+
+void YAML::parse(llvm::MemoryBuffer *mb, std::vector<const Entry *> &entries) {
+  State state = start;
+  char key[64];
+  char value[64];
+  char *p = NULL;
+  unsigned int lineNumber = 1;
+  int depth = 0;
+  bool nextKeyIsStartOfDocument = false;
+  bool nextKeyIsStartOfSequence = false;
+  for (const char *s = mb->getBufferStart(); s < mb->getBufferEnd(); ++s) {
+    char c = *s;
+    if (c == '\n')
+      ++lineNumber;
+    switch (state) {
+    case start:
+      if (c == '#')
+        state = inHeaderComment;
+      else if (c == '-') {
+        p = &key[0];
+        *p++ = c;
+        state = inTripleDash;
+      }
+      break;
+    case inHeaderComment:
+      if (c == '\n') {
+        state = start;
+      }
+      break;
+    case inTripleDash:
+      if (c == '-') {
+        *p++ = c;
+      } else if (c == '\n') {
+        *p = '\0';
+        if (strcmp(key, "---") != 0)
+          return;
+        depth = 0;
+        state = inDocument;
+        nextKeyIsStartOfDocument = true;
+      } else {
+        return;
+      }
+      break;
+    case inTriplePeriod:
+      if (c == '.') {
+        *p++ = c;
+      } else if (c == '\n') {
+        *p = '\0';
+        if (strcmp(key, "...") != 0)
+          return;
+        depth = 0;
+        state = inHeaderComment;
+      } else {
+        return;
+      }
+      break;
+    case inDocument:
+      if (isalnum(c)) {
+        state = inKey;
+        p = &key[0];
+        *p++ = c;
+      } else if (c == '-') {
+        if (depth == 0) {
+          p = &key[0];
+          *p++ = c;
+          state = inTripleDash;
+        } else {
+          nextKeyIsStartOfSequence = true;
+          ++depth;
+        }
+      } else if (c == ' ') {
+        ++depth;
+      } else if (c == '.') {
+        p = &key[0];
+        *p++ = c;
+        state = inTriplePeriod;
+      } else if (c == '\n') {
+        // ignore empty lines
+      } else {
+        return;
+      }
+      break;
+    case inKey:
+      if (isalnum(c) || (c == '-')) {
+        *p++ = c;
+      } else if (c == ':') {
+        *p = '\0';
+        state = inSpaceBeforeValue;
+      } else if (c == '\n') {
+        *p = '\0';
+        if (strcmp(key, "---") == 0)
+          state = inDocument;
+        else
+          return;
+      } else {
+        return;
+      }
+      break;
+    case inSpaceBeforeValue:
+      if (isalnum(c) || (c == '-') || (c == '_')) {
+        p = &value[0];
+        *p++ = c;
+        state = inValue;
+      } else if (c == '\n') {
+        entries.push_back(new Entry(key, "", depth,
+                                    nextKeyIsStartOfDocument,
+                                    nextKeyIsStartOfSequence));
+        nextKeyIsStartOfSequence = false;
+        nextKeyIsStartOfDocument = false;
+        state = inDocument;
+        depth = 0;
+      } else if (c == '[') {
+        state = inValueSequence;
+      } else if (c == ' ') {
+        // eat space
+      } else {
+        return;
+      }
+      break;
+    case inValue:
+      if (isalnum(c) || (c == '-') || (c == '_')) {
+        *p++ = c;
+      } else if (c == '\n') {
+        *p = '\0';
+        entries.push_back(new Entry(key, value, depth,
+                                    nextKeyIsStartOfDocument,
+                                    nextKeyIsStartOfSequence));
+        nextKeyIsStartOfSequence = false;
+        nextKeyIsStartOfDocument = false;
+        state = inDocument;
+        depth = 0;
+      }
+      break;
+    case inValueSequence:
+      if (c == ']')
+        state = inValueSequenceEnd;
+      break;
+    case inValueSequenceEnd:
+      if (c == '\n') {
+        state = inDocument;
+        depth = 0;
+      }
+      break;
+    }
+  }
+}
+
+class YAMLFile : public File {
+public:
+  YAMLFile()
+    : File("path")
+    , _lastRefIndex(0) {}
+
+  virtual bool forEachAtom(File::AtomHandler &) const;
+  virtual bool justInTimeforEachAtom(llvm::StringRef name,
+                                     File::AtomHandler &) const;
+
+  std::vector<Atom *> _atoms;
+  std::vector<Reference> _references;
+  unsigned int _lastRefIndex;
+};
+
+bool YAMLFile::forEachAtom(File::AtomHandler &handler) const {
+  handler.doFile(*this);
+  for (std::vector<Atom *>::const_iterator it = _atoms.begin();
+       it != _atoms.end(); ++it) {
+    handler.doAtom(**it);
+  }
+  return true;
+}
+
+bool YAMLFile::justInTimeforEachAtom(llvm::StringRef name,
+                                     File::AtomHandler &handler) const {
+  return false;
+}
+
+
+class YAMLAtom : public Atom {
+public:
+  YAMLAtom( Definition d
+          , Combine c
+          , Scope s
+          , ContentType ct
+          , SectionChoice sc
+          , bool uvn
+          , bool dds
+          , bool tb
+          , bool al
+          , Alignment a
+          , YAMLFile *f
+          , const char *n)
+    : Atom(d, c, s, ct, sc, uvn, dds, tb, al, a)
+    , _file(f)
+    , _name(n)
+    , _size(0)
+    , _refStartIndex(f->_lastRefIndex)
+    , _refEndIndex(f->_references.size()) {
+    f->_lastRefIndex = _refEndIndex;
+  }
+
+  virtual const class File *file() const {
+    return _file;
+  }
+
+  virtual bool translationUnitSource(const char* *dir, const char* *name) const{
+    return false;
+  }
+
+  virtual llvm::StringRef name() const {
+    return _name;
+  }
+
+  virtual uint64_t objectAddress() const {
+    return 0;
+  }
+
+  virtual uint64_t size() const {
+    return _size;
+  }
+
+  virtual void copyRawContent(uint8_t buffer[]) const { }
+  virtual Reference::iterator referencesBegin() const;
+  virtual Reference::iterator referencesEnd() const;
+private:
+  YAMLFile *_file;
+  const char *_name;
+  unsigned long _size;
+  unsigned int _refStartIndex;
+  unsigned int _refEndIndex;
+};
+
+Reference::iterator YAMLAtom::referencesBegin() const {
+  if (_file->_references.size() < _refStartIndex)
+    return (Reference::iterator)&_file->_references[_refStartIndex];
+  return 0;
+}
+
+Reference::iterator YAMLAtom::referencesEnd() const {
+  if (_file->_references.size() < _refEndIndex)
+    return (Reference::iterator)&_file->_references[_refEndIndex];
+  return 0;
+}
+
+class YAMLAtomState {
+public:
+  YAMLAtomState();
+
+  void setName(const char *n);
+  void setScope(const char *n);
+  void setType(const char *n);
+  void setAlign2(const char *n);
+  void setDefinition(const char *n);
+
+  void setFixupKind(const char *n);
+  void setFixupOffset(const char *n);
+  void setFixupTarget(const char *n);
+  void addFixup(YAMLFile *f);
+
+  void makeAtom(YAMLFile *);
+
+private:
+  const char *_name;
+  Atom::Alignment _align;
+  Atom::Combine _combine;
+  Atom::ContentType _type;
+  Atom::Scope _scope;
+  Atom::Definition _def;
+  Atom::SectionChoice _sectionChoice;
+  bool _userVisibleName;
+  bool _dontDeadStrip;
+  bool _thumb;
+  bool _alias;
+  Reference _ref;
+};
+
+YAMLAtomState::YAMLAtomState()
+  : _name(NULL)
+  , _align(0, 0)
+  , _combine(Atom::combineNever)
+  , _type(Atom::typeData)
+  , _scope(Atom::scopeGlobal)
+  , _userVisibleName(true)
+  , _dontDeadStrip(false)
+  , _thumb(false)
+  , _alias(false) {
+  _ref.target       = NULL;
+  _ref.addend       = 0;
+  _ref.offsetInAtom = 0;
+  _ref.kind         = 0;
+  _ref.flags        = 0;
+}
+
+void YAMLAtomState::makeAtom(YAMLFile *f) {
+  Atom *a = new YAMLAtom(_def, _combine, _scope, _type, _sectionChoice,
+                         _userVisibleName, _dontDeadStrip, _thumb, _alias,
+                         _align, f, _name);
+
+  f->_atoms.push_back(a);
+
+  // reset state for next atom
+  _name             = NULL;
+  _align.powerOf2   = 0;
+  _align.modulus    = 0;
+  _combine          = Atom::combineNever;
+  _type             = Atom::typeData;
+  _scope            = Atom::scopeGlobal;
+  _def              = Atom::definitionRegular;
+  _sectionChoice    = Atom::sectionBasedOnContent;
+  _userVisibleName  = true;
+  _dontDeadStrip    = false;
+  _thumb            = false;
+  _alias            = false;
+  _ref.target       = NULL;
+  _ref.addend       = 0;
+  _ref.offsetInAtom = 0;
+  _ref.kind         = 0;
+  _ref.flags        = 0;
+}
+
+void YAMLAtomState::setName(const char *n) {
+  _name = n;
+}
+
+void YAMLAtomState::setScope(const char *s) {
+  if (strcmp(s, "global") == 0)
+    _scope = Atom::scopeGlobal;
+  else if (strcmp(s, "hidden") == 0)
+    _scope = Atom::scopeLinkageUnit;
+  else if (strcmp(s, "static") == 0)
+    _scope = Atom::scopeTranslationUnit;
+  else
+    llvm::report_fatal_error("bad scope value");
+}
+
+void YAMLAtomState::setType(const char *s) {
+  if (strcmp(s, "code") == 0)
+    _type = Atom::typeCode;
+  else if (strcmp(s, "c-string") == 0)
+    _type = Atom::typeCString;
+  else if (strcmp(s, "zero-fill") == 0)
+    _type = Atom::typeZeroFill;
+  else if (strcmp(s, "data") == 0)
+    _type = Atom::typeData;
+  else
+    llvm::report_fatal_error("bad type value");
+}
+
+void YAMLAtomState::setAlign2(const char *s) {
+  llvm::StringRef str(s);
+  uint32_t res;
+  str.getAsInteger(10, res);
+  _align.powerOf2 = static_cast<uint16_t>(res);
+}
+
+void YAMLAtomState::setDefinition(const char *s) {
+  if (strcmp(s, "regular") == 0)
+    _def = Atom::definitionRegular;
+  else if (strcmp(s, "tentative") == 0)
+    _def = Atom::definitionTentative;
+  else if (strcmp(s, "absolute") == 0)
+    _def = Atom::definitionAbsolute;
+  else
+    llvm::report_fatal_error("bad definition value");
+}
+
+void YAMLAtomState::setFixupKind(const char *s) {
+  if (strcmp(s, "pcrel32") == 0)
+    _ref.kind = 1;
+  else if (strcmp(s, "call32") == 0)
+    _ref.kind = 2;
+  else
+    llvm::report_fatal_error("bad fixup kind value");
+}
+
+void YAMLAtomState::setFixupOffset(const char *s) {
+  if ((s[0] == '0') && (s[1] == 'x'))
+    llvm::StringRef(s).getAsInteger(16, _ref.offsetInAtom);
+  else
+    llvm::StringRef(s).getAsInteger(10, _ref.offsetInAtom);
+}
+
+void YAMLAtomState::setFixupTarget(const char *s) {
+}
+
+void YAMLAtomState::addFixup(YAMLFile *f) {
+  f->_references.push_back(_ref);
+  // clear for next ref
+  _ref.target       = NULL;
+  _ref.addend       = 0;
+  _ref.offsetInAtom = 0;
+  _ref.kind         = 0;
+  _ref.flags        = 0;
+}
+
+llvm::error_code parseObjectText( llvm::MemoryBuffer *mb
+                                , std::vector<File *> &result) {
+  std::vector<const YAML::Entry *> entries;
+  YAML::parse(mb, entries);
+
+  YAMLFile *file = NULL;
+  YAMLAtomState atomState;
+  bool inAtoms       = false;
+  bool inFixups      = false;
+  int depthForAtoms  = -1;
+  int depthForFixups = -1;
+  int lastDepth      = -1;
+  bool haveAtom      = false;
+  bool haveFixup     = false;
+
+  for (std::vector<const YAML::Entry *>::iterator it = entries.begin();
+       it != entries.end(); ++it) {
+    const YAML::Entry *entry = *it;
+
+    if (entry->beginDocument) {
+      if (file != NULL) {
+        if (haveAtom) {
+          atomState.makeAtom(file);
+          haveAtom = false;
+        }
+        result.push_back(file);
+      }
+      file = new YAMLFile();
+      inAtoms = false;
+      depthForAtoms = -1;
+    }
+    if (lastDepth > entry->depth) {
+      // end of fixup sequence
+      if (haveFixup) {
+        atomState.addFixup(file);
+        haveFixup = false;
+      }
+    }
+
+    if (inAtoms && (depthForAtoms == -1)) {
+      depthForAtoms = entry->depth;
+    }
+    if (inFixups && (depthForFixups == -1)) {
+      depthForFixups = entry->depth;
+    }
+    if (strcmp(entry->key, "atoms") == 0) {
+      inAtoms = true;
+    }
+    if (inAtoms) {
+      if (depthForAtoms == entry->depth) {
+        if (entry->beginSequence) {
+          if (haveAtom) {
+            atomState.makeAtom(file);
+            haveAtom = false;
+          }
+        }
+        if (strcmp(entry->key, "name") == 0) {
+          atomState.setName(entry->value);
+          haveAtom = true;
+        } else if (strcmp(entry->key, "scope") == 0) {
+          atomState.setScope(entry->value);
+          haveAtom = true;
+        } else if (strcmp(entry->key, "type") == 0) {
+          atomState.setType(entry->value);
+          haveAtom = true;
+        } else if (strcmp(entry->key, "align2") == 0) {
+          atomState.setAlign2(entry->value);
+          haveAtom = true;
+        } else if (strcmp(entry->key, "definition") == 0) {
+          atomState.setDefinition(entry->value);
+          haveAtom = true;
+        } else if (strcmp(entry->key, "fixups") == 0) {
+          inFixups = true;
+        }
+      } else if (depthForFixups == entry->depth) {
+        if (entry->beginSequence) {
+          if (haveFixup) {
+            atomState.addFixup(file);
+            haveFixup = false;
+          }
+        }
+        if (strcmp(entry->key, "kind") == 0) {
+          atomState.setFixupKind(entry->value);
+          haveFixup = true;
+        } else if (strcmp(entry->key, "offset") == 0) {
+          atomState.setFixupOffset(entry->value);
+          haveFixup = true;
+        } else if (strcmp(entry->key, "target") == 0) {
+          atomState.setFixupTarget(entry->value);
+          haveFixup = true;
+        }
+      }
+    }
+    lastDepth = entry->depth;
+  }
+  if (haveAtom) {
+    atomState.makeAtom(file);
+  }
+
+  result.push_back(file);
+  return success;
+}
+} // namespace yaml
+} // namespace lld
diff --git a/lld/lib/Core/YamlWriter.cpp b/lld/lib/Core/YamlWriter.cpp
new file mode 100644 (file)
index 0000000..ae27c7e
--- /dev/null
@@ -0,0 +1,100 @@
+//===- Core/YamlWriter.cpp - Writes YAML ----------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lld/Core/YamlWriter.h"
+#include "lld/Core/Atom.h"
+#include "lld/Core/File.h"
+#include "lld/Core/Reference.h"
+
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/system_error.h"
+
+#include <vector>
+
+namespace lld {
+namespace yaml {
+
+class Handler : public File::AtomHandler {
+public:
+  Handler(llvm::raw_ostream &out) : _out(out) { }
+
+  virtual void doFile(const class File &) { }
+  virtual void doAtom(const class Atom &atom) {
+    _out << "    - name:        " << atom.name() << "\n";
+    _out << "      definition:  " << definitionString(atom.definition()) <<"\n";
+    _out << "      user-visible:" << atom.userVisibleName() << "\n";
+    _out << "      scope:       " << scopeString(atom.scope()) << "\n";
+    _out << "      type:        " << typeString(atom.contentType()) << "\n";
+    if (atom.referencesBegin() != atom.referencesEnd()) {
+      _out << "      fixups:\n";
+      for (Reference::iterator it = atom.referencesBegin(),
+           end = atom.referencesEnd(); it != end; ++it) {
+        _out << "      - kind:      " << it->kind << "\n";
+        _out << "        offset:    " << it->offsetInAtom << "\n";
+      }
+    }
+
+  }
+
+private:
+  const char *scopeString(Atom::Scope scope) {
+    switch (scope) {
+    case Atom::scopeTranslationUnit:
+      return "static";
+    case Atom::scopeLinkageUnit:
+      return "hidden";
+    case Atom::scopeGlobal:
+      return "global";
+    }
+    return "???";
+  }
+
+  const char *typeString(Atom::ContentType type) {
+    switch (type) {
+    case Atom::typeCode:
+      return "code";
+    case Atom::typeCString:
+      return "c-string";
+    case Atom::typeZeroFill:
+      return "zero-fill";
+    case Atom::typeData:
+      return "data";
+    default:
+      return "???";
+    }
+  }
+
+  const char *definitionString(Atom::Definition def) {
+    switch (def) {
+    case Atom::definitionRegular:
+      return "regular";
+    case Atom::definitionTentative:
+      return "tentative";
+    case Atom::definitionAbsolute:
+      return "absolute";
+    default:
+      return "???";
+    }
+  }
+
+  llvm::raw_ostream &_out;
+};
+
+void writeObjectText(File *file, llvm::raw_ostream &out) {
+  Handler h(out);
+  out << "---\n";
+  out << "atoms:\n";
+  file->forEachAtom(h);
+  out << "...\n";
+}
+
+} // namespace yaml
+} // namespace lld
diff --git a/lld/test/CMakeLists.txt b/lld/test/CMakeLists.txt
new file mode 100644 (file)
index 0000000..32e86b7
--- /dev/null
@@ -0,0 +1,55 @@
+set(LLVM_SOURCE_DIR "${LLVM_MAIN_SRC_DIR}")
+set(LLVM_BINARY_DIR "${LLVM_BINARY_DIR}")
+set(LLVM_BUILD_MODE "%(build_mode)s")
+set(LLVM_TOOLS_DIR "${LLVM_TOOLS_BINARY_DIR}/%(build_config)s")
+set(LLVM_LIBS_DIR "${LLVM_BINARY_DIR}/lib/%(build_config)s")
+set(CLANG_SOURCE_DIR "${CMAKE_CURRENT_SOURCE_DIR}/..")
+set(CLANG_BINARY_DIR "${CMAKE_CURRENT_BINARY_DIR}/..")
+if(BUILD_SHARED_LIBS)
+  set(ENABLE_SHARED 1)
+else()
+  set(ENABLE_SHARED 0)
+endif(BUILD_SHARED_LIBS)
+
+configure_file(
+  ${CMAKE_CURRENT_SOURCE_DIR}/lit.site.cfg.in
+  ${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg)
+
+include(FindPythonInterp)
+if (PYTHONINTERP_FOUND)
+  if (LLVM_MAIN_SRC_DIR)
+    set(LIT "${LLVM_SOURCE_DIR}/utils/lit/lit.py")
+  else()
+    set(LIT "${PATH_TO_LLVM_BUILD}/bin/${CMAKE_CFG_INTDIR}/llvm-lit")
+    # Installed LLVM does not contain ${CMAKE_CFG_INTDIR} in paths.
+    if (NOT EXISTS ${LIT})
+      set(LIT "${PATH_TO_LLVM_BUILD}/bin/llvm-lit")
+    endif()
+  endif()
+
+  if (PATH_TO_LLVM_BUILD)
+    set(LLD_TEST_EXTRA_ARGS "--path=${LLD_BINARY_DIR}/bin/${CMAKE_CFG_INTDIR}")
+  endif()
+
+  set(LIT_ARGS "${LLD_TEST_EXTRA_ARGS} ${LLVM_LIT_ARGS}")
+  separate_arguments(LIT_ARGS)
+
+  add_custom_target(lld-test.deps)
+  set_target_properties(lld-test.deps PROPERTIES FOLDER "lld tests")
+
+  add_custom_target(lld-test
+    COMMAND ${PYTHON_EXECUTABLE}
+                ${LIT}
+                --param lld_site_config=${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg
+                --param build_config=${CMAKE_CFG_INTDIR}
+                --param build_mode=${RUNTIME_BUILD_MODE}
+                ${LIT_ARGS}
+                ${CMAKE_CURRENT_BINARY_DIR}
+                COMMENT "Running lld regression tests")
+  set_target_properties(lld-test PROPERTIES FOLDER "lld tests")
+
+  add_dependencies(lld-test lld-test.deps)
+  add_dependencies(lld-test.deps
+    lld-core
+    )
+endif()
diff --git a/lld/test/lit.cfg b/lld/test/lit.cfg
new file mode 100644 (file)
index 0000000..8870d71
--- /dev/null
@@ -0,0 +1,110 @@
+# -*- Python -*-
+
+import os
+import platform
+import re
+import subprocess
+
+
+# Configuration file for the 'lit' test runner.
+
+# name: The name of this test suite.
+config.name = 'lld'
+
+# testFormat: The test format to use to interpret tests.
+#
+# For now we require '&&' between commands, until they get globally killed and
+# the test runner updated.
+execute_external = (platform.system() != 'Windows'
+                    or lit.getBashPath() not in [None, ""])
+config.test_format = lit.formats.ShTest(execute_external)
+
+# suffixes: A list of file extensions to treat as test files.
+config.suffixes = ['.objtxt']
+
+# test_source_root: The root path where tests are located.
+config.test_source_root = os.path.dirname(__file__)
+
+# test_exec_root: The root path where tests should be run.
+lld_obj_root = getattr(config, 'lld_obj_root', None)
+if lld_obj_root is not None:
+    config.test_exec_root = os.path.join(lld_obj_root, 'test')
+
+# Set llvm_{src,obj}_root for use by others.
+config.llvm_src_root = getattr(config, 'llvm_src_root', None)
+config.llvm_obj_root = getattr(config, 'llvm_obj_root', None)
+
+# Tweak the PATH to include the tools dir and the scripts dir.
+if lld_obj_root is not None:
+    llvm_tools_dir = getattr(config, 'llvm_tools_dir', None)
+    if not llvm_tools_dir:
+        lit.fatal('No LLVM tools dir set!')
+    path = os.path.pathsep.join((llvm_tools_dir, config.environment['PATH']))
+    config.environment['PATH'] = path
+
+    llvm_libs_dir = getattr(config, 'llvm_libs_dir', None)
+    if not llvm_libs_dir:
+        lit.fatal('No LLVM libs dir set!')
+    path = os.path.pathsep.join((llvm_libs_dir,
+                                 config.environment.get('LD_LIBRARY_PATH','')))
+    config.environment['LD_LIBRARY_PATH'] = path
+
+###
+
+# Check that the object root is known.
+if config.test_exec_root is None:
+    # Otherwise, we haven't loaded the site specific configuration (the user is
+    # probably trying to run on a test file directly, and either the site
+    # configuration hasn't been created by the build system, or we are in an
+    # out-of-tree build situation).
+
+    # Check for 'lld_site_config' user parameter, and use that if available.
+    site_cfg = lit.params.get('lld_site_config', None)
+    if site_cfg and os.path.exists(site_cfg):
+        lit.load_config(config, site_cfg)
+        raise SystemExit
+
+    # Try to detect the situation where we are using an out-of-tree build by
+    # looking for 'llvm-config'.
+    #
+    # FIXME: I debated (i.e., wrote and threw away) adding logic to
+    # automagically generate the lit.site.cfg if we are in some kind of fresh
+    # build situation. This means knowing how to invoke the build system though,
+    # and I decided it was too much magic. We should solve this by just having
+    # the .cfg files generated during the configuration step.
+
+    llvm_config = lit.util.which('llvm-config', config.environment['PATH'])
+    if not llvm_config:
+        lit.fatal('No site specific configuration available!')
+
+    # Get the source and object roots.
+    llvm_src_root = lit.util.capture(['llvm-config', '--src-root']).strip()
+    llvm_obj_root = lit.util.capture(['llvm-config', '--obj-root']).strip()
+    lld_src_root = os.path.join(llvm_src_root, "tools", "lld")
+    lld_obj_root = os.path.join(llvm_obj_root, "tools", "lld")
+
+    # Validate that we got a tree which points to here, using the standard
+    # tools/lld layout.
+    this_src_root = os.path.dirname(config.test_source_root)
+    if os.path.realpath(lld_src_root) != os.path.realpath(this_src_root):
+        lit.fatal('No site specific configuration available!')
+
+    # Check that the site specific configuration exists.
+    site_cfg = os.path.join(lld_obj_root, 'test', 'lit.site.cfg')
+    if not os.path.exists(site_cfg):
+        lit.fatal('No site specific configuration available! You may need to '
+                  'run "make test" in your lld build directory.')
+
+    # Okay, that worked. Notify the user of the automagic, and reconfigure.
+    lit.note('using out-of-tree build at %r' % lld_obj_root)
+    lit.load_config(config, site_cfg)
+    raise SystemExit
+
+# When running under valgrind, we mangle '-vg' onto the end of the triple so we
+# can check it with XFAIL and XTARGET.
+if lit.useValgrind:
+    config.target_triple += '-vg'
+
+# Shell execution
+if platform.system() not in ['Windows'] or lit.getBashPath() != '':
+    config.available_features.add('shell')
diff --git a/lld/test/lit.site.cfg.in b/lld/test/lit.site.cfg.in
new file mode 100644 (file)
index 0000000..43ee120
--- /dev/null
@@ -0,0 +1,21 @@
+## Autogenerated by LLVM/lld configuration.
+# Do not edit!
+config.llvm_src_root = "@LLVM_SOURCE_DIR@"
+config.llvm_obj_root = "@LLVM_BINARY_DIR@"
+config.llvm_tools_dir = "@LLVM_TOOLS_DIR@"
+config.llvm_libs_dir = "@LLVM_LIBS_DIR@"
+config.lit_tools_dir = "@LLVM_LIT_TOOLS_DIR@"
+config.lld_obj_root = "@LLD_BINARY_DIR@"
+config.target_triple = "@TARGET_TRIPLE@"
+
+# Support substitution of the tools and libs dirs with user parameters. This is
+# used when we can't determine the tool dir at configuration time.
+try:
+    config.llvm_tools_dir = config.llvm_tools_dir % lit.params
+    config.llvm_libs_dir = config.llvm_libs_dir % lit.params
+except KeyError,e:
+    key, = e.args
+    lit.fatal("unable to find %r parameter, use '--param=%s=VALUE'" % (key,key))
+
+# Let the main config do the real work.
+lit.load_config(config, "@LLD_SOURCE_DIR@/test/lit.cfg")
diff --git a/lld/test/tent-merge.objtxt b/lld/test/tent-merge.objtxt
new file mode 100644 (file)
index 0000000..d2a698f
--- /dev/null
@@ -0,0 +1,24 @@
+# RUN: lld-core %s | FileCheck %s
+
+#
+# Test that a tentative definition and a regular global are merged into
+# one regular global
+#
+
+---
+atoms:
+    - name:         _foo
+      definition:   tentative
+      type:         zero-fill
+      size:         4
+---
+atoms:
+    - name:         _foo
+      definition:   regular
+      type:         data
+      content:      [ 00, 00, 00, 00 ]
+...
+
+
+# CHECK:        name: _foo
+# CHECK-NEXT:   definition: regular
diff --git a/lld/tools/CMakeLists.txt b/lld/tools/CMakeLists.txt
new file mode 100644 (file)
index 0000000..4880ad1
--- /dev/null
@@ -0,0 +1,2 @@
+add_subdirectory(lld)
+add_subdirectory(lld-core)
diff --git a/lld/tools/lld-core/CMakeLists.txt b/lld/tools/lld-core/CMakeLists.txt
new file mode 100644 (file)
index 0000000..0f326dc
--- /dev/null
@@ -0,0 +1,14 @@
+set(LLVM_USED_LIBS
+  lldCore
+  )
+
+set(LLVM_LINK_COMPONENTS
+  support
+  )
+
+add_lld_executable(lld-core
+  lld-core.cpp
+  )
+
+install(TARGETS lld-core
+  RUNTIME DESTINATION bin)
diff --git a/lld/tools/lld-core/lld-core.cpp b/lld/tools/lld-core/lld-core.cpp
new file mode 100644 (file)
index 0000000..f7425e3
--- /dev/null
@@ -0,0 +1,191 @@
+//===- tools/lld/lld-core.cpp - Linker Core Test Driver -----------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lld/Core/InputFiles.h"
+#include "lld/Core/Resolver.h"
+#include "lld/Core/YamlReader.h"
+#include "lld/Core/YamlWriter.h"
+#include "lld/Platform/Platform.h"
+
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/system_error.h"
+
+#include <vector>
+
+using namespace lld;
+
+static void error(llvm::Twine message) {
+  llvm::errs() << "lld-core: " << message << ".\n";
+}
+
+static bool error(llvm::error_code ec) {
+  if (ec) {
+    error(ec.message());
+    return true;
+  }
+  return false;
+}
+
+namespace {
+class LdCore : public InputFiles, public Platform {
+public:
+  LdCore(std::vector<File *> &f) : _files(f) { }
+
+  // InputFiles interface
+  virtual void forEachInitialAtom(File::AtomHandler &) const;
+  virtual bool searchLibraries(llvm::StringRef name, bool searchDylibs,
+                               bool searchArchives, bool dataSymbolOnly,
+                               File::AtomHandler &) const;
+
+  virtual void initialize() { }
+
+  // tell platform object another file has been added
+  virtual void fileAdded(const File &file) { }
+
+  // tell platform object another atom has been added
+  virtual void atomAdded(const Atom &file) { }
+
+  // give platform a chance to change each atom's scope
+  virtual void adjustScope(const Atom &atom) { }
+
+  // if specified atom needs alternate names, return AliasAtom(s)
+  virtual bool getAliasAtoms(const Atom &atom,
+                             std::vector<const Atom *>&) {
+    return false;
+  }
+
+  // give platform a chance to resolve platform-specific undefs
+  virtual bool getPlatformAtoms(llvm::StringRef undefined,
+                                std::vector<const Atom *>&) {
+    return false;
+  }
+
+  // resolver should remove unreferenced atoms
+  virtual bool deadCodeStripping() {
+    return false;
+  }
+
+  // atom must be kept so should be root of dead-strip graph
+  virtual bool isDeadStripRoot(const Atom &atom) {
+    return false;
+  }
+
+  // if target must have some atoms, denote here
+  virtual bool getImplicitDeadStripRoots(std::vector<const Atom *>&) {
+    return false;
+  }
+
+  // return entry point for output file (e.g. "main") or NULL
+  virtual llvm::StringRef entryPointName() {
+    return NULL;
+  }
+
+  // for iterating must-be-defined symbols ("main" or -u command line option)
+  typedef llvm::StringRef const *UndefinesIterator;
+  virtual UndefinesIterator initialUndefinesBegin() const {
+    return NULL;
+  }
+  virtual UndefinesIterator initialUndefinesEnd() const {
+    return NULL;
+  }
+
+  // if platform wants resolvers to search libraries for overrides
+  virtual bool searchArchivesToOverrideTentativeDefinitions() {
+    return false;
+  }
+
+  virtual bool searchSharedLibrariesToOverrideTentativeDefinitions() {
+    return false;
+  }
+
+  // if platform allows symbol to remain undefined (e.g. -r)
+  virtual bool allowUndefinedSymbol(llvm::StringRef name) {
+    return true;
+  }
+
+  // for debugging dead code stripping, -why_live
+  virtual bool printWhyLive(llvm::StringRef name) {
+    return false;
+  }
+
+  // print out undefined symbol error messages in platform specific way
+  virtual void errorWithUndefines(const std::vector<const Atom *> &undefs,
+                                  const std::vector<const Atom *> &all) {}
+
+  // last chance for platform to tweak atoms
+  virtual void postResolveTweaks(std::vector<const Atom *> &all) {}
+
+private:
+  std::vector<File *> &_files;
+};
+}
+
+void LdCore::forEachInitialAtom(File::AtomHandler &handler) const {
+  for (std::vector<File *>::iterator it = _files.begin();
+       it != _files.end(); ++it) {
+    const File *file = *it;
+    handler.doFile(*file);
+    file->forEachAtom(handler);
+  }
+}
+
+bool LdCore::searchLibraries(llvm::StringRef name, bool searchDylibs,
+                             bool searchArchives, bool dataSymbolOnly,
+                             File::AtomHandler &) const {
+  return false;
+}
+
+namespace {
+class MergedFile : public File {
+public:
+  MergedFile(std::vector<const Atom *> &a)
+    : File("path"), _atoms(a) { }
+
+  virtual bool forEachAtom(File::AtomHandler &handler) const {
+    handler.doFile(*this);
+    for (std::vector<const Atom *>::iterator it = _atoms.begin();
+         it != _atoms.end(); ++it) {
+      handler.doAtom(**it);
+    }
+    return true;
+  }
+
+  virtual bool justInTimeforEachAtom(llvm::StringRef name,
+                                     File::AtomHandler &) const {
+    return false;
+  }
+
+private:
+  std::vector<const Atom *> &_atoms;
+};
+}
+
+int main(int argc, const char *argv[]) {
+  llvm::OwningPtr<llvm::MemoryBuffer> mb;
+  if (error(llvm::MemoryBuffer::getFileOrSTDIN(llvm::StringRef(argv[1]), mb)))
+    return 1;
+
+  std::vector<File *> files;
+  if (error(yaml::parseObjectText(mb.get(), files)))
+    return 1;
+
+  LdCore core(files);
+  Resolver resolver(core, core);
+  std::vector<const Atom *> &mergedAtoms = resolver.resolve();
+  MergedFile outFile(mergedAtoms);
+
+  std::string errorInfo;
+  llvm::raw_fd_ostream out("-", errorInfo);
+  yaml::writeObjectText(&outFile, out);
+  return 0;
+}
diff --git a/lld/tools/lld/CMakeLists.txt b/lld/tools/lld/CMakeLists.txt
new file mode 100644 (file)
index 0000000..ee0b47e
--- /dev/null
@@ -0,0 +1,6 @@
+add_lld_executable(lld
+  lld.cpp
+  )
+
+install(TARGETS lld
+  RUNTIME DESTINATION bin)
diff --git a/lld/tools/lld/lld.cpp b/lld/tools/lld/lld.cpp
new file mode 100644 (file)
index 0000000..74329b6
--- /dev/null
@@ -0,0 +1,17 @@
+//===- tools/lld/lld.cpp - Linker Driver Dispatcher ---------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This is the entry point to the lld driver. This is a thin wrapper which
+// dispatches to the given platform specific driver.
+//
+//===----------------------------------------------------------------------===//
+
+int main(int argc, char **argv) {
+  return 0;
+}
diff --git a/lld/utils/astyle-options b/lld/utils/astyle-options
new file mode 100644 (file)
index 0000000..53c496b
--- /dev/null
@@ -0,0 +1,7 @@
+style=java
+indent=spaces=2
+pad-oper
+pad-header
+unpad-paren
+convert-tabs
+align-pointer=name