[BOLT][Golang support] Core changes

[yota9]

Summary

This is part of BOLT core changes for golang support patch: https://reviews.llvm.org/D124347

[yota9]

Small changes

[yota9]

I'm not sure what causes clang-format to complain about BF.h , locally I'm unable to repeat this.
Anyway I've commented about 3 main problems in this patch. I would be happy to discuss them and submit the golang support patches one-by-one, it would be the most right and simple away I think.
@maksfb @rafauler @Amir

bolt/lib/Core/BinaryBasicBlock.cpp

638

We need this, since some of the instructions annotations might be "locked". E.g. when dealing with golang inlined functions, we might inline only one instruction (e.g NOP) which will be removed by bolt. But this instruction has inline metadata that we need to have in order to restore inlining golang tables. So before removing such instruction we need to create NOP instruction on it's place that will store this metadata.

bolt/lib/Core/BinaryContext.cpp

2001

Golang pass needs to create 2 extra read sections. We need to create PHDR for them and emit them properly to the binary. I'm not sure how to refactor the code connected to extra section handling, would be thankful for ideas.

bolt/lib/Core/BinarySection.cpp

169

This is currently used for the created by golang pass sections. They don't have input data, so it is used as a crutch where we mark the section as changed and use its output contents for emission. With the new sections creating/emission that is probable the second problem we need to discuss.
P.S. The golang pass mmaps the memory with overhead since during section creation we're unable to table the final size. It is not a problem to use malloc/new, I've done it so the memory would be allocated lazily on the page access, but actually the sizes there are not so big..

[tschuett]

https://llvm.org/docs/ProgrammersManual.html#picking-the-right-data-structure-for-a-task

bolt/include/bolt/Core/BinaryContext.h

237

Do you care about the order? Or is a SmallStringSet sufficient?

[yota9]

bolt/include/bolt/Core/BinaryContext.h

237

Basically you are right here, but this is temp code and one of the problem that was marked by me above - we need to think about refactoring the code that emits extra sections, so probably it would be removed.

[yota9]

New writable segment creation was re-developed and separate review was created, let's start from there https://reviews.llvm.org/D143390 @maksfb @rafaelauler @Amir

[yota9]

Change patch according to https://reviews.llvm.org/D143390
@maksfb @rafauler please review D143390 :)

[yota9]

rebase

bolt/include/bolt/Core/BinaryBasicBlock.h

public:
 
   /// Erase pseudo instruction at a given iterator.
   /// Return iterator following the removed instruction.
   iterator erasePseudoInstruction(iterator II) {
     --NumPseudos;
     return Instructions.erase(II);
   }
 
+  /// Store meta-data of instruction to NOP instruction
+  /// and insert it in place of erased one
+  bool storeInstructionMetadata(iterator II);
+
   /// Erase non-pseudo instruction at a given iterator \p II.
   /// Return iterator following the removed instruction.
   iterator eraseInstruction(iterator II) {
+    if (storeInstructionMetadata(II))
+      return std::next(II);
+
     adjustNumPseudos(*II, -1);
     return Instructions.erase(II);
   }
 
   /// Erase non-pseudo instruction at a given \p Index
   void eraseInstructionAtIndex(unsigned Index) {
     eraseInstruction(Instructions.begin() + Index);
   }
public:
   }
 
   /// Replace instruction referenced by iterator \II with a sequence of
   /// instructions defined by [\p Begin, \p End] range.
   ///
   /// Return iterator pointing to the first inserted instruction.
   template <typename Itr>
   iterator replaceInstruction(iterator II, Itr Begin, Itr End) {
-    adjustNumPseudos(*II, -1);
+    II = eraseInstruction(II);
     adjustNumPseudos(Begin, End, 1);
-
-    auto I = II - Instructions.begin();
-    Instructions.insert(Instructions.erase(II), Begin, End);
-    return I + Instructions.begin();
+    return Instructions.insert(II, Begin, End);
   }
 
   iterator replaceInstruction(iterator II,
                               const InstructionListType &Replacement) {
     return replaceInstruction(II, Replacement.begin(), Replacement.end());
   }
 
   /// Insert \p NewInst before \p At, which must be an existing instruction in
   /// this BB. Return iterator pointing to the newly inserted instruction.
   iterator insertInstruction(iterator At, MCInst &&NewInst) {
     adjustNumPseudos(NewInst, 1);
     return Instructions.emplace(At, std::move(NewInst));
   }
 
   iterator insertInstruction(iterator At, MCInst &NewInst) {
     adjustNumPseudos(NewInst, 1);
     return Instructions.insert(At, NewInst);
   }
 
+  iterator insertInstructions(iterator At, InstructionListType &Instrs) {
+    for (MCInst &NewInst : Instrs) {
+      At = insertInstruction(At, NewInst);
+      ++At;
+    }
+    return At;
+  }
+
   /// Helper to retrieve any terminators in \p BB before \p Pos. This is used
   /// to skip CFI instructions and to retrieve the first terminator instruction
   /// in basic blocks with two terminators (conditional jump and unconditional
   /// jump).
   MCInst *getTerminatorBefore(MCInst *Pos);
 
   /// Used to identify whether an instruction is before a terminator and whether
   /// moving it to the end of the BB would render it dead code.

bolt/include/bolt/Core/BinaryContext.h

 #define BOLT_CORE_BINARY_CONTEXT_H
 
 #include "bolt/Core/BinaryData.h"
 #include "bolt/Core/BinarySection.h"
 #include "bolt/Core/DebugData.h"
 #include "bolt/Core/JumpTable.h"
 #include "bolt/Core/MCPlusBuilder.h"
 #include "bolt/RuntimeLibs/RuntimeLibrary.h"
+#include "bolt/Utils/NameResolver.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCCodeEmitter.h"
 #include "llvm/MC/MCContext.h"
class BinaryContext {
 
   /// DWARF line info for CUs.
   std::map<unsigned, DwarfLineTable> DwarfLineTablesCUMap;
 
   /// Internal helper for removing section name from a lookup table.
   void deregisterSectionName(const BinarySection &Section);
 
 public:
+
   static Expected<std::unique_ptr<BinaryContext>>
   createBinaryContext(const ObjectFile *File, bool IsPIC,
                       std::unique_ptr<DWARFContext> DwCtx);
 
   /// Superset of compiler units that will contain overwritten code that needs
   /// new debug info. In a few cases, functions may end up not being
   /// overwritten, but it is okay to re-generate debug info for them.
   std::set<const DWARFUnit *> ProcessedCUs;
std::map<uint64_t, BinaryFunction> &getBinaryFunctions() {
     return BinaryFunctions;
   }
 
   /// Return all functions for this rewrite instance.
   const std::map<uint64_t, BinaryFunction> &getBinaryFunctions() const {
     return BinaryFunctions;
   }
 
+  /// Return BF by name. If the global function was not found return the first
+  /// found local
+  BinaryFunction *getBinaryFunctionByName(StringRef Name) {
+    BinaryData *Data = getFirstBinaryDataByName(Name);
+    if (!Data)
+      return nullptr;
+
+    return getBinaryFunctionAtAddress(Data->getAddress());
+  }
+
+  const BinaryFunction *getBinaryFunctionByName(StringRef Name) const {
+    return const_cast<BinaryContext *>(this)->getBinaryFunctionByName(Name);
+  }
+
   /// Create BOLT-injected function
   BinaryFunction *createInjectedBinaryFunction(const std::string &Name,
                                                bool IsSimple = true);
 
   std::vector<BinaryFunction *> &getInjectedBinaryFunctions() {
     return InjectedBinaryFunctions;
   }
 
const BinaryData *getPLTBinaryDataByName(StringRef Name) const {
     // without it.
     size_t At = Name.find("@");
     if (At != std::string::npos)
       return getBinaryDataByName(Name.str().substr(0, At) + "@PLT");
 
     return nullptr;
   }
 
+  /// Return BinaryData for the given \p Name
+  /// If the data was not found return first local BinaryData or nullptr
+  BinaryData *getFirstBinaryDataByName(StringRef Name) {
+    BinaryData *Data = getBinaryDataByName(Name);
+    if (!Data)
+      return getBinaryDataByName(NameResolver::uniquifyID(Name, 1));
+    return Data;
+  }
+
+  const BinaryData *getFirstBinaryDataByName(StringRef Name) const {
+    return const_cast<BinaryContext *>(this)->getFirstBinaryDataByName(Name);
+  }
+
   /// Return true if \p SymbolName was generated internally and was not present
   /// in the input binary.
   bool isInternalSymbolName(const StringRef Name) {
     return Name.startswith("SYMBOLat") || Name.startswith("DATAat") ||
            Name.startswith("HOLEat");
   }
 
   MCSymbol *getHotTextStartSymbol() const {
std::pair<size_t, size_t> calculateEmittedSize(BinaryFunction &BF,
                                                  bool FixBranches = true);
 
   /// Calculate the size of the instruction \p Inst optionally using a
   /// user-supplied emitter for lock-free multi-thread work. MCCodeEmitter is
   /// not thread safe and each thread should operate with its own copy of it.
   uint64_t
   computeInstructionSize(const MCInst &Inst,
                          const MCCodeEmitter *Emitter = nullptr) const {
+    if (isAArch64())
+      return 4;
+
     if (auto Size = MIB->getAnnotationWithDefault<uint32_t>(Inst, "Size"))
       return Size;
 
     if (!Emitter)
       Emitter = this->MCE.get();
     SmallString<256> Code;
     SmallVector<MCFixup, 4> Fixups;
     raw_svector_ostream VecOS(Code);
createStreamer(llvm::raw_pwrite_stream &OS) const {
     std::unique_ptr<MCStreamer> Streamer(TheTarget->createMCObjectStreamer(
         *TheTriple, *Ctx, std::unique_ptr<MCAsmBackend>(MAB), std::move(OW),
         std::unique_ptr<MCCodeEmitter>(MCE), *STI,
         /* RelaxAll */ false,
         /* IncrementalLinkerCompatible */ false,
         /* DWARFMustBeAtTheEnd */ false));
     return Streamer;
   }
+
+  /// Returns std pair of binary functons desired and maximum alignment bytes
+  std::pair<unsigned, unsigned> getBFAlignment(BinaryFunction &Function,
+                                               bool EmitColdPart) const;
 };
 
 template <typename T, typename = std::enable_if_t<sizeof(T) == 1>>
 inline raw_ostream &operator<<(raw_ostream &OS, const ArrayRef<T> &ByteArray) {
   const char *Sep = "";
   for (const auto Byte : ByteArray) {
     OS << Sep << format("%.2x", Byte);
     Sep = " ";
   }
   return OS;
 }
 
 } // namespace bolt
 } // namespace llvm
 
 #endif

bolt/include/bolt/Core/BinaryData.h

protected:
 
   /// Section this data belongs to.
   BinarySection *Section{nullptr};
 
   /// Start address of this symbol.
   uint64_t Address{0};
   /// Size of this data (can be 0).
   uint64_t Size{0};
+  /// Output size of this data (if changed).
+  uint64_t OutputSize{0};
   /// Alignment of this data.
   uint16_t Alignment{1};
 
   bool IsMoveable{true};
 
   /// Symbol flags (same as llvm::SymbolRef::Flags)
   unsigned Flags{0};
 
public:
   const BinarySection &getSection() const { return *Section; }
   StringRef getSectionName() const;
 
   BinarySection &getOutputSection() { return *OutputSection; }
   const BinarySection &getOutputSection() const { return *OutputSection; }
   StringRef getOutputSectionName() const;
   uint64_t getOutputAddress() const;
   uint64_t getOutputOffset() const { return OutputOffset; }
-  uint64_t getOutputSize() const { return Size; }
+  uint64_t getOutputSize() const { return OutputSize ? OutputSize : Size; }
+  void setOutputSize(uint64_t NewSize) { OutputSize = NewSize; }
 
   bool isMoved() const;
   bool containsAddress(uint64_t Address) const {
     return ((getAddress() <= Address && Address < getEndAddress()) ||
             (getAddress() == Address && !getSize()));
   }
   bool containsRange(uint64_t Address, uint64_t Size) const {
     return containsAddress(Address) && Address + Size <= getEndAddress();

bolt/include/bolt/Core/BinaryFunction.h

 
 enum IndirectCallPromotionType : char {
   ICP_NONE,        /// Don't perform ICP.
   ICP_CALLS,       /// Perform ICP on indirect calls.
   ICP_JUMP_TABLES, /// Perform ICP on jump tables.
   ICP_ALL          /// Perform ICP on calls and jump tables.
 };
 
+enum IndexOrder {
+  GO_FIRST_BF_INDEX = 0,
+  FIRST_BF_INDEX = 1,
+  GO_UNUSED_BF_INDEX = -3U,
+  GO_LAST_BF_INDEX = -2U,
+  INVALID_BF_INDEX = -1U,
+};
+
 /// Information on a single indirect call to a particular callee.
 struct IndirectCallProfile {
   MCSymbol *Symbol;
   uint32_t Offset;
   uint64_t Count;
   uint64_t Mispreds;
 
   IndirectCallProfile(MCSymbol *Symbol, uint64_t Count, uint64_t Mispreds,
private:
 
   /// Size of the function in the output file.
   uint64_t OutputSize{0};
 
   /// Maximum size this function is allowed to have.
   uint64_t MaxSize{std::numeric_limits<uint64_t>::max()};
 
   /// Alignment requirements for the function.
-  uint16_t Alignment{2};
+  uint16_t Alignment{MinAlign};
 
   /// Maximum number of bytes used for alignment of hot part of the function.
   uint16_t MaxAlignmentBytes{0};
 
   /// Maximum number of bytes used for alignment of cold part of the function.
   uint16_t MaxColdAlignmentBytes{0};
 
+  // If function is golang stores the offset to functab entry
+  uint32_t GolangFunctabOffset{0};
+
   const MCSymbol *PersonalityFunction{nullptr};
   uint8_t PersonalityEncoding{dwarf::DW_EH_PE_sdata4 | dwarf::DW_EH_PE_pcrel};
 
   BinaryContext &BC;
 
   std::unique_ptr<BinaryLoopInfo> BLI;
 
   /// All labels in the function that are referenced via relocations from
private:
   /// Set to false by SCTC. Dynostats can't be reliably computed for
   /// functions with non-canonical CFG.
   /// This attribute is only valid when hasCFG() == true.
   bool HasCanonicalCFG{true};
 
   /// True if another function body was merged into this one.
   bool HasFunctionsFoldedInto{false};
 
+  /// True if we have a suspicion that the function was written in ASM
+  bool IsAsm{false};
+
   /// Name for the section this function code should reside in.
   std::string CodeSectionName;
 
   /// Name for the corresponding cold code section.
   std::string ColdCodeSectionName;
 
   /// Parent function fragment for split function fragments.
   SmallPtrSet<BinaryFunction *, 1> ParentFragments;
private:
   /// different parameters by every pass.
   mutable uint64_t Hash{0};
 
   /// For PLT functions it contains a symbol associated with a function
   /// reference. It is nullptr for non-PLT functions.
   const MCSymbol *PLTSymbol{nullptr};
 
   /// Function order for streaming into the destination binary.
-  uint32_t Index{-1U};
+  uint32_t Index{INVALID_BF_INDEX};
 
   /// Get basic block index assuming it belongs to this function.
   unsigned getIndex(const BinaryBasicBlock *BB) const {
     assert(BB->getIndex() < BasicBlocks.size());
     return BB->getIndex();
   }
 
   /// Return basic block that originally contained offset \p Offset
public:
 
   /// Return original address of the function (or offset from base for PIC).
   uint64_t getAddress() const { return Address; }
 
   uint64_t getOutputAddress() const { return OutputAddress; }
 
   uint64_t getOutputSize() const { return OutputSize; }
 
-  /// Does this function have a valid streaming order index?
-  bool hasValidIndex() const { return Index != -1U; }
+  /// Returns true if this function has a valid streaming order index
+  bool hasValidIndex() const { return Index != INVALID_BF_INDEX; }
 
   /// Get the streaming order index for this function.
   uint32_t getIndex() const { return Index; }
 
   /// Set the streaming order index for this function.
   void setIndex(uint32_t Idx) {
-    assert(!hasValidIndex());
     Index = Idx;
   }
 
   /// Return offset of the function body in the binary file.
   uint64_t getFileOffset() const {
     return getLayout().getMainFragment().getFileOffset();
   }
 
public:
   /// fragment.
   bool hasIndirectTargetToSplitFragment() const {
     return HasIndirectTargetToSplitFragment;
   }
 
   /// Return true if all CFG edges have local successors.
   bool hasCanonicalCFG() const { return HasCanonicalCFG; }
 
+  /// Return true if we have a suspicion that the function was written in ASM
+  bool isAsm() const { return IsAsm; }
+
   /// Return true if the original function code has all necessary relocations
   /// to track addresses of functions emitted to new locations.
   bool hasExternalRefRelocations() const { return HasExternalRefRelocations; }
 
   /// Return true if the function has instruction(s) with unknown control flow.
   bool hasUnknownControlFlow() const { return HasUnknownControlFlow; }
 
   /// Return true if the function body is non-contiguous.
public:
   bool hasMemoryProfile() const { return HasMemoryProfile; }
 
   /// Return true if the body of the function was merged into another function.
   bool isFolded() const { return FoldedIntoFunction != nullptr; }
 
   /// Return true if other functions were folded into this one.
   bool hasFunctionsFoldedInto() const { return HasFunctionsFoldedInto; }
 
+  /// Sets golang funtab offset for this function
+  void setGolangFunctabOffset(uint32_t Offset) { GolangFunctabOffset = Offset; }
+
+  /// Return true if the function is presented in original go functab
+  bool isGolang() const { return GolangFunctabOffset != 0; }
+
+  /// Get golang funtab offset for this function
+  uint32_t getGolangFunctabOffset() const { return GolangFunctabOffset; }
+
   /// If this function was folded, return the function it was folded into.
   BinaryFunction *getFoldedIntoFunction() const { return FoldedIntoFunction; }
 
   /// Return true if the function uses jump tables.
   bool hasJumpTables() const { return !JumpTables.empty(); }
 
   /// Return true if the function has SDT marker
   bool hasSDTMarker() const { return HasSDTMarker; }
public:
   void setIsPatched(bool V) { IsPatched = V; }
 
   void setHasIndirectTargetToSplitFragment(bool V) {
     HasIndirectTargetToSplitFragment = V;
   }
 
   void setHasCanonicalCFG(bool V) { HasCanonicalCFG = V; }
 
+  void setIsAsm(bool V) { IsAsm = V; }
+
   void setFolded(BinaryFunction *BF) { FoldedIntoFunction = BF; }
 
   /// Indicate that another function body was merged with this function.
   void setHasFunctionsFoldedInto() { HasFunctionsFoldedInto = true; }
 
   BinaryFunction &setPersonalityFunction(uint64_t Addr) {
     assert(!PersonalityFunction && "can't set personality function twice");
     PersonalityFunction = BC.getOrCreateGlobalSymbol(Addr, "FUNCat");

   }
 
   size_t estimateColdSize() const {
     if (!isSplit())
       return estimateSize();
     size_t Estimate = 0;
     for (const BinaryBasicBlock &BB : blocks())
       if (BB.isCold())
-        Estimate += BC.computeCodeSize(BB.begin(), BB.end());
+        Estimate += BB.estimateSize();
     return Estimate;
   }
 
   size_t estimateSize() const {
     size_t Estimate = 0;
     for (const BinaryBasicBlock &BB : blocks())
-      Estimate += BC.computeCodeSize(BB.begin(), BB.end());
+      Estimate += BB.estimateSize();
     return Estimate;
   }
 
   /// Return output address ranges for a function.
   DebugAddressRangesVector getOutputAddressRanges() const;
 
   /// Given an address corresponding to an instruction in the input binary,
   /// return an address of this instruction in output binary.

bolt/include/bolt/Core/BinarySection.h

class BinarySection {
   uint64_t OutputSize{0};          // Section size in the rewritten binary.
   uint64_t OutputFileOffset{0};    // File offset in the rewritten binary file.
   StringRef OutputContents;        // Rewritten section contents.
   const uint64_t SectionNumber;    // Order in which the section was created.
   unsigned SectionID{-1u};         // Unique ID used for address mapping.
                                    // Set by ExecutableFileMemoryManager.
   uint32_t Index{0};               // Section index in the output file.
   mutable bool IsReordered{false}; // Have the contents been reordered?
+  mutable bool IsChanged{false};   // The section is changed and OutputContents
+                                   // should be used for emission.
   bool IsAnonymous{false};         // True if the name should not be included
                                    // in the output file.
 
   uint64_t hash(const BinaryData &BD,
                 std::map<const BinaryData *, uint64_t> &Cache) const;
 
   // non-copyable
   BinarySection(const BinarySection &) = delete;
bool isAllocatable() const {
     if (isELF()) {
       return (ELFFlags & ELF::SHF_ALLOC) && !isTBSS();
     } else {
       // On non-ELF assume all sections are allocatable.
       return true;
     }
   }
   bool isReordered() const { return IsReordered; }
+  bool isChanged() const { return IsChanged; }
   bool isAnonymous() const { return IsAnonymous; }
   unsigned getELFType() const { return ELFType; }
   unsigned getELFFlags() const { return ELFFlags; }
 
   uint8_t *getData() {
     return reinterpret_cast<uint8_t *>(
         const_cast<char *>(getContents().data()));
   }
public:
   }
 
   /// Does this section have any non-pending relocations?
   bool hasRelocations() const { return !Relocations.empty(); }
 
   /// Does this section have any pending relocations?
   bool hasPendingRelocations() const { return !PendingRelocations.empty(); }
 
+  /// Does this section have any dynamic relocations?
+  bool hasDynamicRelocations() const { return !DynamicRelocations.empty(); }
+
   /// Remove non-pending relocation with the given /p Offset.
   bool removeRelocationAt(uint64_t Offset) {
     auto Itr = Relocations.find(Offset);
     if (Itr != Relocations.end()) {
       Relocations.erase(Itr);
       return true;
     }
+
+    return false;
+  }
+
+  /// Remove the dynamic relocation (if any) at the given /p Offset.
+  bool removeDynamicRelocationAt(uint64_t Offset) {
+    Relocation Key{Offset, 0, 0, 0, 0};
+    auto Itr = DynamicRelocations.find(Key);
+    if (Itr != DynamicRelocations.end()) {
+      DynamicRelocations.erase(Itr);
+      return true;
+    }
+
     return false;
   }
 
   void clearRelocations();
 
   /// Add a new relocation at the given /p Offset.
   void addRelocation(uint64_t Offset, MCSymbol *Symbol, uint64_t Type,
-                     uint64_t Addend, uint64_t Value = 0,
+                     uint64_t Addend = 0, uint64_t Value = 0,
                      bool Pending = false) {
     assert(Offset < getSize() && "offset not within section bounds");
     if (!Pending) {
       Relocations.emplace(Relocation{Offset, Symbol, Type, Addend, Value});
     } else {
       PendingRelocations.emplace_back(
           Relocation{Offset, Symbol, Type, Addend, Value});
     }
   }
 
   /// Add a dynamic relocation at the given /p Offset.
   void addDynamicRelocation(uint64_t Offset, MCSymbol *Symbol, uint64_t Type,
-                            uint64_t Addend, uint64_t Value = 0) {
+                            uint64_t Addend = 0, uint64_t Value = 0) {
     assert(Offset < getSize() && "offset not within section bounds");
     DynamicRelocations.emplace(Relocation{Offset, Symbol, Type, Addend, Value});
   }
 
   /// Add relocation against the original contents of this section.
   void addPendingRelocation(const Relocation &Rel) {
     PendingRelocations.push_back(Rel);
   }
public:
   BinaryPatcher *getPatcher() { return Patcher.get(); }
 
   /// Lookup the relocation (if any) at the given /p Offset.
   const Relocation *getRelocationAt(uint64_t Offset) const {
     auto Itr = Relocations.find(Offset);
     return Itr != Relocations.end() ? &*Itr : nullptr;
   }
 
-  /// Lookup the relocation (if any) at the given /p Offset.
+  /// Lookup the dynamic relocation (if any) at the given /p Offset.
   const Relocation *getDynamicRelocationAt(uint64_t Offset) const {
     Relocation Key{Offset, 0, 0, 0, 0};
     auto Itr = DynamicRelocations.find(Key);
     return Itr != DynamicRelocations.end() ? &*Itr : nullptr;
   }
 
   uint64_t hash(const BinaryData &BD) const {
     std::map<const BinaryData *, uint64_t> Cache;
public:
   uint64_t getOutputSize() const { return OutputSize; }
   uint8_t *getOutputData() {
     return reinterpret_cast<uint8_t *>(
         const_cast<char *>(getOutputContents().data()));
   }
   const uint8_t *getOutputData() const {
     return reinterpret_cast<const uint8_t *>(getOutputContents().data());
   }
+  void setOutputContents(uint8_t *Data, uint64_t Size) {
+    IsChanged = true;
+    OutputSize = Size;
+    OutputContents = StringRef(reinterpret_cast<const char *>(Data), Size);
+  }
   StringRef getOutputContents() const { return OutputContents; }
   uint64_t getAllocAddress() const {
     return reinterpret_cast<uint64_t>(getOutputData());
   }
   uint64_t getOutputAddress() const { return OutputAddress; }
   uint64_t getOutputFileOffset() const { return OutputFileOffset; }
   unsigned getSectionID() const {
     assert(hasValidSectionID() && "trying to use uninitialized section id");

bolt/include/bolt/Core/MCPlusBuilder.h

unsigned getOrCreateAnnotationIndex(StringRef Name) {
 
     const unsigned Index =
         AnnotationNameIndexMap.size() + MCPlus::MCAnnotation::kGeneric;
     AnnotationNameIndexMap.insert(std::make_pair(Name, Index));
     AnnotationNames.emplace_back(std::string(Name));
     return Index;
   }
 
+  /// Copy annotations from one instruction to other
+  void copyAnnotationInst(const MCInst &From, MCInst &To,
+                          AllocatorIdTy AllocatorId = 0) {
+    const MCInst *AnnotationInst = getAnnotationInst(From);
+    if (!AnnotationInst)
+      return;
+
+    for (unsigned I = 0; I < AnnotationInst->getNumOperands(); ++I) {
+      const int64_t Imm = AnnotationInst->getOperand(I).getImm();
+      const unsigned Index = extractAnnotationIndex(Imm);
+      const int64_t Value = extractAnnotationValue(Imm);
+      setAnnotationOpValue(To, Index, Value, AllocatorId);
+    }
+  }
+
   /// Store an annotation value on an MCInst.  This assumes the annotation
   /// is not already present.
   template <typename ValueType>
   const ValueType &addAnnotation(MCInst &Inst, unsigned Index,
                                  const ValueType &Val,
                                  AllocatorIdTy AllocatorId = 0) {
     assert(!hasAnnotation(Inst, Index));
     AnnotationAllocator &Allocator = getAnnotationAllocator(AllocatorId);

bolt/include/bolt/Core/Relocation.h

struct Relocation {
   static uint64_t getNone();
 
   /// Return code for a PC-relative 4-byte relocation
   static uint64_t getPC32();
 
   /// Return code for a PC-relative 8-byte relocation
   static uint64_t getPC64();
 
+  /// Return code for a ABS 4-byte relocation
+  static uint64_t getAbs32();
+
   /// Return code for a ABS 8-byte relocation
   static uint64_t getAbs64();
 
   /// Return code for a RELATIVE relocation
   static uint64_t getRelative();
 
+  /// Return code for ABS relocation based on size
+  static uint64_t getAbs(uint8_t Size);
+
   /// Return true if this relocation is PC-relative. Return false otherwise.
   bool isPCRelative() const { return isPCRelative(Type); }
 
   /// Return true if this relocation is R_*_RELATIVE type. Return false
   /// otherwise.
   bool isRelative() const { return isRelative(Type); }
 
+  /// Return true if this relocation is IRELATIVE type. Return false otherwise.
+  bool isIRelative() const { return isIRelative(Type); }
+
   /// Emit relocation at a current \p Streamer' position. The caller is
   /// responsible for setting the position correctly.
   size_t emit(MCStreamer *Streamer) const;
 
   /// Print a relocation to \p OS.
   void print(raw_ostream &OS) const;
 };
 

bolt/include/bolt/Utils/NameResolver.h

class NameResolver {
   StringMap<uint64_t> Counters;
 
   /// Character guaranteed not to be used by any "native" name passed to
   /// uniquify() function.
   static constexpr char Sep = '/';
 
 public:
   /// Return unique version of the \p Name in the form "Name<Sep><Number>".
+  static std::string uniquifyID(StringRef Name, uint64_t ID) {
+    return (Name + Twine(Sep) + Twine(ID)).str();
+  }
+
   std::string uniquify(StringRef Name) {
     const uint64_t ID = ++Counters[Name];
-    return (Name + Twine(Sep) + Twine(ID)).str();
+    return uniquifyID(Name, ID);
   }
 
   /// For uniquified \p Name, return the original form (that may no longer be
   /// unique).
   static StringRef restore(StringRef Name) {
     return Name.substr(0, Name.find_first_of(Sep));
   }
 

bolt/lib/Core/BinaryBasicBlock.cpp

for (const auto &LocSymKV : *LocSyms) {
     if (getFunction()->requiresAddressTranslation()) {
       getFunction()->getInputOffsetToAddressMap().emplace(
           std::make_pair(InputFunctionOffset, OutputOffset + BBAddress));
     }
   }
   LocSyms.reset(nullptr);
 }
 
+bool BinaryBasicBlock::storeInstructionMetadata(BinaryBasicBlock::iterator II) {
+  // In case the instruction has locked annotation we will save all
+  // its annotations to noop instruction and store it in place of
+  // erased instruction
+  BinaryContext &BC = Function->getBinaryContext();
+  if (!BC.MIB->hasAnnotation(*II, "Locked"))
+    return false;
+
+  MCInst Noop;
+  BC.MIB->createNoop(Noop);
+  std::unique_lock<llvm::sys::RWMutex> Lock(BC.CtxMutex);
+  BC.MIB->copyAnnotationInst(*II, Noop);
+  Instructions[std::distance(Instructions.begin(), II)] = Noop;
+  return true;
+}
+
 } // namespace bolt
 } // namespace llvm

bolt/lib/Core/BinaryContext.cpp

for (auto SI = Sections.begin(); SI != Sections.end();) {
     LLVM_DEBUG(dbgs() << "LLVM-DEBUG: deregistering " << Section->getName()
                       << '\n';);
     deregisterSectionName(*Section);
     SI = Sections.erase(SI);
     delete Section;
   }
 }
 
 bool BinaryContext::deregisterSection(BinarySection &Section) {
   BinarySection *SectionPtr = &Section;
   auto Itr = Sections.find(SectionPtr);
   if (Itr != Sections.end()) {
     auto Range = AddressToSection.equal_range(SectionPtr->getAddress());
     while (Range.first != Range.second) {
       if (Range.first->second == SectionPtr) {
         AddressToSection.erase(Range.first);
         break;
while (BFI != BinaryFunctions.end()) {
       llvm::move(FunctionRanges, std::back_inserter(OutputRanges));
       std::advance(BFI, 1);
     }
   }
 
   return OutputRanges;
 }
 
+std::pair<unsigned, unsigned>
+BinaryContext::getBFAlignment(BinaryFunction &Function,
+                              bool EmitColdPart) const {
+  unsigned Alignment = Function.getAlignment();
+  if (HasRelocations) {
+    unsigned MaxAlignBytes = EmitColdPart ? Function.getMaxColdAlignmentBytes()
+                                          : Function.getMaxAlignmentBytes();
+    return std::make_pair(Alignment, MaxAlignBytes);
+  }
+
+  return std::make_pair(Alignment, Alignment);
+}
+
 } // namespace bolt
 } // namespace llvm

bolt/lib/Core/BinaryEmitter.cpp

for (BinaryBasicBlock *const BB : FF) {
     Streamer.emitLabel(BB->getLabel());
     if (!EmitCodeOnly) {
       if (MCSymbol *EntrySymbol = BF.getSecondaryEntryPointSymbol(*BB))
         Streamer.emitLabel(EntrySymbol);
     }
 
     // Check if special alignment for macro-fusion is needed.
     bool MayNeedMacroFusionAlignment =
-        (opts::AlignMacroOpFusion == MFT_ALL) ||
-        (opts::AlignMacroOpFusion == MFT_HOT && BB->getKnownExecutionCount());
+        ((opts::AlignMacroOpFusion == MFT_ALL) ||
+         (opts::AlignMacroOpFusion == MFT_HOT && BB->getKnownExecutionCount()));
     BinaryBasicBlock::const_iterator MacroFusionPair;
     if (MayNeedMacroFusionAlignment) {
       MacroFusionPair = BB->getMacroOpFusionPair();
       if (MacroFusionPair == BB->end())
         MayNeedMacroFusionAlignment = false;
     }
 
     SMLoc LastLocSeen;

bolt/lib/Core/BinarySection.cpp

 //===----------------------------------------------------------------------===//
 
 #include "bolt/Core/BinarySection.h"
 #include "bolt/Core/BinaryContext.h"
 #include "bolt/Utils/Utils.h"
 #include "llvm/MC/MCStreamer.h"
 #include "llvm/Support/CommandLine.h"
 
+#include <sys/mman.h>
+
 #define DEBUG_TYPE "bolt"
 
 using namespace llvm;
 using namespace bolt;
 
 namespace opts {
 extern cl::opt<bool> PrintRelocations;
 extern cl::opt<bool> HotData;
BinarySection::hash(const BinaryData &BD,
 
   Cache[&BD] = Hash;
 
   return Hash;
 }
 
 void BinarySection::emitAsData(MCStreamer &Streamer,
                                const Twine &SectionName) const {
-  StringRef SectionContents = getContents();
+  StringRef SectionContents = isChanged() ? getOutputContents() : getContents();
   MCSectionELF *ELFSection =
       BC.Ctx->getELFSection(SectionName, getELFType(), getELFFlags());
 
   Streamer.switchSection(ELFSection);
   Streamer.emitValueToAlignment(getAlign());
 
   if (BC.HasRelocations && opts::HotData && isReordered())
     Streamer.emitLabel(BC.Ctx->getOrCreateSymbol("__hot_data_start"));
LLVM_DEBUG(
                << " file offset 0x"
                << Twine::utohexstr(SectionFileOffset + Reloc.Offset) << '\n';);
   }
 
   clearList(PendingRelocations);
 }
 
 BinarySection::~BinarySection() {
+  if (isChanged()) {
+    munmap(getOutputData(), getOutputSize());
+    return;
+  }
+
   if (isReordered()) {
     delete[] getData();
     return;
   }
 
   if (!isAllocatable() && !hasValidSectionID() &&
       (!hasSectionRef() ||
        OutputContents.data() != getContents(Section).data())) {

bolt/lib/Core/Relocation.cpp

 }
 
 bool Relocation::isPCRelative(uint64_t Type) {
   if (Arch == Triple::aarch64)
     return isPCRelativeAArch64(Type);
   return isPCRelativeX86(Type);
 }
 
+uint64_t Relocation::getAbs32() {
+  if (Arch == Triple::aarch64)
+    return ELF::R_AARCH64_ABS32;
+  return ELF::R_X86_64_32;
+}
+
 uint64_t Relocation::getAbs64() {
   if (Arch == Triple::aarch64)
     return ELF::R_AARCH64_ABS64;
   return ELF::R_X86_64_64;
 }
 
 uint64_t Relocation::getRelative() {
   if (Arch == Triple::aarch64)
     return ELF::R_AARCH64_RELATIVE;
   return ELF::R_X86_64_RELATIVE;
 }
 
+uint64_t Relocation::getAbs(uint8_t Size) {
+  if (Size == sizeof(uint64_t))
+    return Relocation::getAbs64();
+  else if (Size == sizeof(uint32_t))
+    return Relocation::getAbs32();
+
+  llvm_unreachable("Wrong relocation size");
+  return 0;
+
+}
+
 size_t Relocation::emit(MCStreamer *Streamer) const {
   const size_t Size = getSizeForType(Type);
   MCContext &Ctx = Streamer->getContext();
   if (isPCRelative(Type)) {
     MCSymbol *TempLabel = Ctx.createNamedTempSymbol();
     Streamer->emitLabel(TempLabel);
     const MCExpr *Value = nullptr;
     if (Symbol) {

bolt/lib/Rewrite/RewriteInstance.cpp

 #include "bolt/Core/BinaryEmitter.h"
 #include "bolt/Core/BinaryFunction.h"
 #include "bolt/Core/DebugData.h"
 #include "bolt/Core/Exceptions.h"
 #include "bolt/Core/FunctionLayout.h"
 #include "bolt/Core/MCPlusBuilder.h"
 #include "bolt/Core/ParallelUtilities.h"
 #include "bolt/Core/Relocation.h"
+#include "bolt/Passes/BinaryPasses.h"
 #include "bolt/Passes/CacheMetrics.h"
 #include "bolt/Passes/ReorderFunctions.h"
+#include "bolt/Passes/SplitFunctions.h"
 #include "bolt/Profile/BoltAddressTranslation.h"
 #include "bolt/Profile/DataAggregator.h"
 #include "bolt/Profile/DataReader.h"
 #include "bolt/Profile/YAMLProfileReader.h"
 #include "bolt/Profile/YAMLProfileWriter.h"
 #include "bolt/Rewrite/BinaryPassManager.h"
 #include "bolt/Rewrite/DWARFRewriter.h"
 #include "bolt/Rewrite/ExecutableFileMemoryManager.h"

 extern cl::opt<MacroFusionType> AlignMacroOpFusion;
 extern cl::list<std::string> HotTextMoveSections;
 extern cl::opt<bool> Hugify;
 extern cl::opt<bool> Instrument;
 extern cl::opt<JumpTableSupportLevel> JumpTables;
 extern cl::list<std::string> ReorderData;
 extern cl::opt<bolt::ReorderFunctions::ReorderType> ReorderFunctions;
 extern cl::opt<bool> TimeBuild;
+extern cl::opt<bool> PreserveBlocksAlignment;
+extern cl::opt<bool> AlignBlocks;
+extern cl::opt<bool> NoInline;
+extern cl::opt<bool> StringOps;
+extern cl::opt<FrameOptimizationType> FrameOptimization;
+extern cl::opt<bool> SplitFunctions;
+extern llvm::cl::opt<bool> InsertRetpolines;
+extern cl::opt<bool> InstructionsLowering;
+extern cl::list<Peepholes::PeepholeOpts> Peepholes;
 
 cl::opt<bool> AllowStripped("allow-stripped",
                             cl::desc("allow processing of stripped binaries"),
                             cl::Hidden, cl::cat(BoltCategory));
 
 static cl::opt<bool> ForceToDataRelocations(
     "force-data-relocations",
     cl::desc("force relocations to data sections to always be processed"),
void RewriteInstance::adjustCommandLineOptions() {
   }
 
   if (opts::HotText && opts::HotTextMoveSections.getNumOccurrences() == 0) {
     opts::HotTextMoveSections.addValue(".stub");
     opts::HotTextMoveSections.addValue(".mover");
     opts::HotTextMoveSections.addValue(".never_hugify");
   }
 
+  if ((BC->isAArch64()) &&
+      (opts::AlignBlocks || opts::PreserveBlocksAlignment)) {
+    errs() << "BOLT-WARNING: Disabling block alignment\n";
+    opts::AlignBlocks = false;
+    opts::PreserveBlocksAlignment = false;
+  }
+
   if (opts::UseOldText && !BC->OldTextSectionAddress) {
     errs() << "BOLT-WARNING: cannot use old .text as the section was not found"
               "\n";
     opts::UseOldText = false;
   }
   if (opts::UseOldText && !BC->HasRelocations) {
     errs() << "BOLT-WARNING: cannot use old .text in non-relocation mode\n";
     opts::UseOldText = false;
void RewriteInstance::processProfileData() {
 
   if (opts::AggregateOnly)
     exit(0);
 }
 
 void RewriteInstance::disassembleFunctions() {
   NamedRegionTimer T("disassembleFunctions", "disassemble functions",
                      TimerGroupName, TimerGroupDesc, opts::TimeRewrite);
+  // Create annotation indices to allow lock-free execution
+  BC->MIB->getOrCreateAnnotationIndex("Size");
+  BC->MIB->getOrCreateAnnotationIndex("Locked");
+
   for (auto &BFI : BC->getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
 
     ErrorOr<ArrayRef<uint8_t>> FunctionData = Function.getData();
     if (!FunctionData) {
       errs() << "BOLT-ERROR: corresponding section is non-executable or "
              << "empty for function " << Function << '\n';
       exit(1);
if (!ELF64LEFile) {
     errs() << "BOLT-ERROR: only 64-bit LE ELF binaries are supported\n";
     exit(1);
   }
   const ELFFile<ELF64LE> &Obj = ELF64LEFile->getELFFile();
   raw_fd_ostream &OS = Out->os();
 
   // Write/re-write program headers.
   Phnum = Obj.getHeader().e_phnum;
+
   if (PHDRTableOffset) {
     // Writing new pheader table and adding one new entry for R+X segment.
     Phnum += 1;
     if (NewWritableSegmentSize) {
       // Adding one more entry for R+W segment.
       Phnum += 1;
     }
   } else {
if (PHDRTableAddress && Phdr.p_type == ELF::PT_PHDR) {
                sizeof(NewTextPhdr));
       if (NewWritableSegmentSize) {
         ELF64LEPhdrTy NewWritablePhdr = createNewWritableSectionsPhdr();
         OS.write(reinterpret_cast<const char *>(&NewWritablePhdr),
                  sizeof(NewWritablePhdr));
       }
       AddedSegment = true;
     }
+
     OS.write(reinterpret_cast<const char *>(&NewPhdr), sizeof(NewPhdr));
   }
 
   if (!opts::UseGnuStack && !AddedSegment) {
     // Append the new header to the end of the table.
     ELF64LE::Phdr NewTextPhdr = createNewTextPhdr();
     OS.write(reinterpret_cast<const char *>(&NewTextPhdr), sizeof(NewTextPhdr));
     if (NewWritableSegmentSize) {
if (Function) {
               "Cannot locate fragment containg secondary entrypoint");
           FF = Function->getLayout().fragment_begin();
         }
 
         NewSymbol.st_shndx =
             Function->getCodeSection(FF->getFragmentNum())->getIndex();
       } else {
         // Check if the symbol belongs to moved data object and update it.
-        BinaryData *BD = opts::ReorderData.empty()
-                             ? nullptr
-                             : BC->getBinaryDataAtAddress(Symbol.st_value);
+        BinaryData *BD =
+            opts::ForceToDataRelocations || !opts::ReorderData.empty()
+                ? BC->getBinaryDataAtAddress(Symbol.st_value)
+                : nullptr;
         if (BD && BD->isMoved() && !BD->isJumpTable()) {
           assert((!BD->getSize() || !Symbol.st_size ||
                   Symbol.st_size == BD->getSize()) &&
                  "sizes must match");
 
           BinarySection &OutputSection = BD->getOutputSection();
           assert(OutputSection.getIndex());
           LLVM_DEBUG(dbgs()
                      << "BOLT-DEBUG: moving " << BD->getName() << " from "
                      << *BC->getSectionNameForAddress(Symbol.st_value) << " ("
                      << Symbol.st_shndx << ") to " << OutputSection.getName()
                      << " (" << OutputSection.getIndex() << ")\n");
           NewSymbol.st_shndx = OutputSection.getIndex();
           NewSymbol.st_value = BD->getOutputAddress();
+          NewSymbol.st_size = BD->getOutputSize();
         } else {
           // Otherwise just update the section for the symbol.
           if (Symbol.st_shndx < ELF::SHN_LORESERVE)
             NewSymbol.st_shndx = getNewSectionIndex(Symbol.st_shndx);
         }
 
         // Detect local syms in the text section that we didn't update
         // and that were preserved by the linker to support relocations against
if (opts::HotText && !NumHotTextSymsUpdated) {
     addSymbol("__hot_end");
   }
 
   if (opts::HotData && !NumHotDataSymsUpdated) {
     addSymbol("__hot_data_start");
     addSymbol("__hot_data_end");
   }
 
+  auto addSectionSymbol = [&](uint64_t Address, unsigned Index) {
+    ELFSymTy Symbol;
+    Symbol.st_value = Address;
+    Symbol.st_shndx = Index;
+    Symbol.st_name = AddToStrTab("");
+    Symbol.st_size = 0;
+    Symbol.st_other = 0;
+    Symbol.setBindingAndType(ELF::STB_LOCAL, ELF::STT_SECTION);
+    Symbols.emplace_back(Symbol);
+  };
+
+  for (BinarySection &Section : BC->allocatableSections()) {
+    if (Section.hasSectionRef())
+      continue;
+
+    addSectionSymbol(Section.getOutputAddress(), Section.getIndex());
+  }
+
   // Put local symbols at the beginning.
   llvm::stable_sort(Symbols, [](const ELFSymTy &A, const ELFSymTy &B) {
     if (A.getBinding() == ELF::STB_LOCAL && B.getBinding() != ELF::STB_LOCAL)
       return true;
     return false;
   });
 
   for (const ELFSymTy &Symbol : Symbols)
for (BinarySection &Section : BC->allocatableSections()) {
         Elf_Rela NewRelA;
         MCSymbol *Symbol = Rel.Symbol;
         uint32_t SymbolIdx = 0;
         uint64_t Addend = Rel.Addend;
         uint64_t RelOffset =
             getNewFunctionOrDataAddress(SectionInputAddress + Rel.Offset);
 
         RelOffset = RelOffset == 0 ? SectionAddress + Rel.Offset : RelOffset;
-        if (Rel.Symbol) {
+        if (Symbol) {
+          if (!IsRelative && !Rel.isIRelative()) {
             SymbolIdx = getOutputDynamicSymbolIndex(Symbol);
           } else {
+            // The R_*_(I)RELATIVE relocation inserted by BOLT
+            ErrorOr<uint64_t> Address = BC->getSymbolValue(*Symbol);
+            if (Address)
+              Addend += getNewFunctionOrDataAddress(*Address);
+          }
+        } else {
           // Usually this case is used for R_*_(I)RELATIVE relocations
           const uint64_t Address = getNewFunctionOrDataAddress(Addend);
           if (Address)
             Addend = Address;
         }
 
         NewRelA.setSymbolAndType(SymbolIdx, Rel.Type, EF.isMips64EL());
         NewRelA.r_offset = RelOffset;