Subzero: Add basic ELFObjectWriter (text section, symtab, strtab, headers)

src/IceELFSection.h

Index: src/IceELFSection.h
diff --git a/src/IceELFSection.h b/src/IceELFSection.h
new file mode 100644
index 0000000000000000000000000000000000000000..94af0dc15841fb23b0ea2597f23d2ba7a0e555c5
--- /dev/null
+++ b/src/IceELFSection.h
@@ -0,0 +1,317 @@
+//===- subzero/src/IceELFSection.h - Model of ELF sections ------*- C++ -*-===//
+//
+//                        The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Representation of ELF sections.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SUBZERO_SRC_ICEELFSECTION_H
+#define SUBZERO_SRC_ICEELFSECTION_H
+
+#include "IceDefs.h"
+#include "IceELFStreamer.h"
+
+using namespace llvm::ELF;
+
+namespace Ice {
+
+class ELFStreamer;
+class ELFStringTableSection;
+
+// Base representation of an ELF section.
+class ELFSection {
+  ELFSection(const ELFSection &) = delete;
+  ELFSection &operator=(const ELFSection &) = delete;
+
+public:
+  // Constructs an ELF section, filling in fields that will be known
+  // once the *type* of section is decided.  Other fields may be updated
+  // incrementally or only after the program is completely defined.
+  ELFSection(const IceString &Name, Elf64_Word sh_type, Elf64_Xword sh_flags,
+             Elf64_Xword sh_addralign, Elf64_Xword sh_entsize)
+      : Name(Name), Header(), Number(NoSectionNumber) {
+    Header.sh_type = sh_type;
+    Header.sh_flags = sh_flags;
+    Header.sh_addralign = sh_addralign;
+    Header.sh_entsize = sh_entsize;
+  }
+
+  // Sentinel value for a section number/index for before the final
+  // section index is actually known.
+  static const SizeT NoSectionNumber;

[Jim Stichnoth, 2014/11/21 21:32:22]

I think you could do this instead, for slightly better clarity and efficiency:

enum { NoSectionNumber = std::numeric_limits<SizeT>::max() };

I guess one problem is that you lose the SizeT typing of the constant, though it
may not matter here since it looks like only equality comparisons are done.

Same for the other static const members below.

[jvoung (off chromium), 2014/11/24 21:35:46]

Done.

+
+  // Set the section number/index after it is finally known.
+  void setNumber(SizeT N) {
+    // Should only set the number once: from NoSectionNumber -> N.
+    assert(Number == NoSectionNumber);
+    Number = N;
+  }
+  SizeT getNumber() const {
+    assert(Number != NoSectionNumber);
+    return Number;
+  }
+
+  void setSize(Elf64_Xword sh_size) { Header.sh_size = sh_size; }
+  SizeT getCurrentSize() const { return Header.sh_size; }
+
+  void setNameStrIndex(Elf64_Word sh_name) { Header.sh_name = sh_name; }
+
+  IceString getName() const { return Name; }
+
+  void setLinkNum(Elf64_Word sh_link) { Header.sh_link = sh_link; }
+
+  void setInfoNum(Elf64_Word sh_info) { Header.sh_info = sh_info; }
+
+  void setFileOffset(Elf64_Off sh_offset) { Header.sh_offset = sh_offset; }
+
+  Elf64_Xword getSectionAlign() const { return Header.sh_addralign; }
+
+  // Write the section header out with the given streamer.
+  template <bool IsELF64> void writeHeader(ELFStreamer &Str);
+
+protected:
+  ~ELFSection() {}
+
+  // Name of the section in convenient string form (instead of a index
+  // into the Section Header String Table, which is not known till later).
+  IceString Name;
+
+  // The fields of the header. May only be partially initialized, but should
+  // be fully initialized before writing.
+  Elf64_Shdr Header;
+
+  // The number of the section after laying out sections.
+  SizeT Number;
+};
+
+// Models text/code sections. Code is written out incrementally and the
+// size of the section is then updated incrementally.
+class ELFTextSection : public ELFSection {
+  ELFTextSection(const ELFTextSection &) = delete;
+  ELFTextSection &operator=(const ELFTextSection &) = delete;
+
+public:
+  using ELFSection::ELFSection;
+
+  void appendData(ELFStreamer &Str, const llvm::StringRef MoreData);
+};
+
+// Models data/rodata sections. Data is written out incrementally and the
+// size of the section is then updated incrementally.
+// Some rodata sections may have fixed entsize and duplicates may be mergeable.
+class ELFDataSection : public ELFSection {
+  ELFDataSection(const ELFDataSection &) = delete;
+  ELFDataSection &operator=(const ELFDataSection &) = delete;
+
+public:
+  using ELFSection::ELFSection;
+
+  void appendData(ELFStreamer &Str, const llvm::StringRef MoreData);
+};
+
+// Model of ELF symbol table entries. Besides keeping track of the fields
+// required for an elf symbol table entry it also tracks the number that
+// represents the symbol's final index in the symbol table.
+struct ELFSym {
+  Elf64_Sym Sym;
+  SizeT Number;
+
+  static const SizeT UnknownNumber;
+
+  void setNumber(SizeT N) {
+    assert(Number == UnknownNumber);
+    Number = N;
+  }
+
+  SizeT getNumber() const {
+    assert(Number != UnknownNumber);
+    return Number;
+  }
+};
+
+// Models a symbol table. Symbols may be added up until updateIndices is
+// called. At that point the indices of each symbol will be finalized.
+class ELFSymbolTableSection : public ELFSection {
+public:
+  using ELFSection::ELFSection;
+
+  // Create initial entry for a symbol when it is defined.
+  // Each entry should only be defined once.
+  // We might want to allow Name to be a dummy name initially, then
+  // get updated to the real thing, since Data initializers are read
+  // before the bitcode's symbol table is read.
+  void createDefinedSym(const IceString &Name, uint8_t Type, uint8_t Binding,
+                        ELFSection *Section, RelocOffsetT Offset, SizeT Size);
+
+  // Note that a symbol table entry needs to be created for the given
+  // symbol because it is undefined.
+  void noteUndefinedSym(const IceString &Name, ELFSection *NullSection);
+
+  size_t getSectionDataSize() const {
+    return (LocalSymbols.size() + GlobalSymbols.size()) * Header.sh_entsize;
+  }
+
+  size_t getNumLocals() const { return LocalSymbols.size(); }
+
+  void updateIndices(const ELFStringTableSection *StrTab);
+
+  void writeData(ELFStreamer &Str, bool IsELF64);
+
+private:
+  // Map from symbol name + section to its symbol information.
+  typedef std::pair<IceString, ELFSection *> SymtabKey;
+  typedef std::map<SymtabKey, ELFSym> SymMap;
+
+  template <bool IsELF64>
+  void writeSymbolMap(ELFStreamer &Str, const SymMap &Map);
+
+  // Keep Local and Global symbols separate, since the sh_info needs to
+  // know the index of the last LOCAL.
+  SymMap LocalSymbols;
+  SymMap GlobalSymbols;
+};
+
+// Base model of a relocation section.
+class ELFRelocationSectionBase : public ELFSection {
+  ELFRelocationSectionBase(const ELFRelocationSectionBase &) = delete;
+  ELFRelocationSectionBase &
+  operator=(const ELFRelocationSectionBase &) = delete;
+
+public:
+  ELFRelocationSectionBase(const IceString &Name, Elf64_Word sh_type,
+                           Elf64_Xword sh_flags, Elf64_Xword sh_addralign,
+                           Elf64_Xword sh_entsize, ELFSection *RelatedSection)
+      : ELFSection(Name, sh_type, sh_flags, sh_addralign, sh_entsize),
+        RelatedSection(RelatedSection) {}
+
+  ELFSection *getRelatedSection() const { return RelatedSection; }
+
+private:
+  ELFSection *RelatedSection;
+};
+
+// ELFRelocationSection which depends on the actual relocation type.
+// Specializations are needed depending on the ELFCLASS and whether
+// or not addends are explicit or implicitly embedded in the related
+// section (ELFCLASS64 pack their r_info field differently from ELFCLASS32).
+template <typename RelType>
+class ELFRelocationSection : ELFRelocationSectionBase {
+  ELFRelocationSection(const ELFRelocationSectionBase &) = delete;
+  ELFRelocationSection &operator=(const ELFRelocationSectionBase &) = delete;
+
+public:
+  using ELFRelocationSectionBase::ELFRelocationSectionBase;
+
+  void addRelocations() {
+    // TODO: fill me in
+  }
+
+private:
+  typedef std::pair<RelType, ELFSym *> ELFRelSym;
+  typedef std::vector<ELFRelSym> RelocationList;
+  RelocationList Relocations;
+};
+
+// Models a string table.  The user will build the string table by
+// adding strings incrementally.  At some point, all strings should be
+// known and layOutStrings() should be called. After that, no other
+// strings may be added.  However, the final offsets of the strings
+// can be discovered and used to fill out section headers and symbol
+// table entries.
+class ELFStringTableSection : public ELFSection {
+  ELFStringTableSection(const ELFStringTableSection &) = delete;
+  ELFStringTableSection &operator=(const ELFStringTableSection &) = delete;
+
+public:
+  using ELFSection::ELFSection;
+
+  // Add a string to the table, in preparation for final layout.
+  void add(const IceString &Str);
+
+  // Finalizes the layout of the string table and fills in the section Data.
+  void doLayout();
+
+  // Grabs the final index of a string after layout.
+  size_t getIndex(const IceString &Str) const;
+
+  llvm::StringRef getSectionData() const {
+    assert(isLaidOut());
+    return llvm::StringRef(reinterpret_cast<const char *>(StringData.data()),
+                           StringData.size());
+  }
+
+  size_t getSectionDataSize() const { return getSectionData().size(); }
+
+private:
+  bool isLaidOut() const { return !StringData.empty(); }
+
+  // Strings can share a string table entry if they share the same suffix.
+  // E.g., "pop\\0" and "lollipop\0" can both use the characters in

[Jim Stichnoth, 2014/11/21 21:32:22]

Did you mean for the backslashes to be doubled?  (and lollipop here has just one
backslash)

[jvoung (off chromium), 2014/11/24 21:35:46]

Hmm, I guess \0 should be fine -- making consistent. Or just omit them =)

+  // "lolipop\\0", but "pops\\0" cannot, and "unpop\\0" cannot either.
+  // Though, "pop\\0", "lollipop\\0", and "unpop\\0" share "pop\\0" as
+  // the suffix, "pop\\0" can only share the characters with one of them.
+  struct SuffixComparator {
+    bool operator()(const IceString &StrA, const IceString &StrB) const;
+  };
+
+  typedef std::map<IceString, size_t, SuffixComparator> StringToIndexType;
+
+  static const size_t UnknownIndex;
+
+  // Track strings to their index.  Index will be UnknownIndex if not
+  // yet laid out.
+  StringToIndexType StringToIndexMap;
+
+  typedef std::vector<uint8_t> RawDataType;
+  RawDataType StringData;
+};
+
+template <bool IsELF64> void ELFSection::writeHeader(ELFStreamer &Str) {
+  Str.writeELFWord<IsELF64>(Header.sh_name);
+  Str.writeELFWord<IsELF64>(Header.sh_type);
+  Str.writeELFXword<IsELF64>(Header.sh_flags);
+  Str.writeAddrOrOffset<IsELF64>(Header.sh_addr);
+  Str.writeAddrOrOffset<IsELF64>(Header.sh_offset);
+  Str.writeELFXword<IsELF64>(Header.sh_size);
+  Str.writeELFWord<IsELF64>(Header.sh_link);
+  Str.writeELFWord<IsELF64>(Header.sh_info);
+  Str.writeELFXword<IsELF64>(Header.sh_addralign);
+  Str.writeELFXword<IsELF64>(Header.sh_entsize);
+}
+
+template <bool IsELF64>
+void ELFSymbolTableSection::writeSymbolMap(ELFStreamer &Str,
+                                           const SymMap &Map) {
+  // The order of the fields is different, so branch on IsELF64.
+  if (IsELF64) {
+    for (auto &KeyValue : Map) {
+      const Elf64_Sym &SymInfo = KeyValue.second.Sym;
+      Str.writeELFWord<IsELF64>(SymInfo.st_name);
+      Str.write8(SymInfo.st_info);
+      Str.write8(SymInfo.st_other);
+      Str.writeLE16(SymInfo.st_shndx);
+      Str.writeAddrOrOffset<IsELF64>(SymInfo.st_value);
+      Str.writeELFXword<IsELF64>(SymInfo.st_size);
+    }
+  } else {
+    for (auto &KeyValue : Map) {
+      const Elf64_Sym &SymInfo = KeyValue.second.Sym;
+      Str.writeELFWord<IsELF64>(SymInfo.st_name);
+      Str.writeAddrOrOffset<IsELF64>(SymInfo.st_value);
+      Str.writeELFWord<IsELF64>(SymInfo.st_size);
+      Str.write8(SymInfo.st_info);
+      Str.write8(SymInfo.st_other);
+      Str.writeLE16(SymInfo.st_shndx);
+    }
+  }
+}
+
+} // end of namespace Ice
+
+#endif // SUBZERO_SRC_ICEELFSECTION_H