diff options
| author | Andrew Kelley <andrew@ziglang.org> | 2020-01-16 13:09:45 -0500 |
|---|---|---|
| committer | Andrew Kelley <andrew@ziglang.org> | 2020-01-16 13:09:45 -0500 |
| commit | ba4cc03b4f0d71ac3e0147aa3dde449299ce8cd5 (patch) | |
| tree | 88e0c274db5c1c943944c565833bea103692a556 /deps/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp | |
| parent | fbe6af81fdb1b964bb0c28f51de2458800b8274c (diff) | |
| download | zig-ba4cc03b4f0d71ac3e0147aa3dde449299ce8cd5.tar.gz zig-ba4cc03b4f0d71ac3e0147aa3dde449299ce8cd5.zip | |
remove embedded LLD
we no longer have any patches against upstream LLD
Diffstat (limited to 'deps/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp')
| -rw-r--r-- | deps/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp | 580 |
1 files changed, 0 insertions, 580 deletions
diff --git a/deps/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp b/deps/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp deleted file mode 100644 index de5adb0887..0000000000 --- a/deps/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp +++ /dev/null @@ -1,580 +0,0 @@ -//===- lib/ReaderWriter/MachO/CompactUnwindPass.cpp -------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -/// -/// \file A pass to convert MachO's __compact_unwind sections into the final -/// __unwind_info format used during runtime. See -/// mach-o/compact_unwind_encoding.h for more details on the formats involved. -/// -//===----------------------------------------------------------------------===// - -#include "ArchHandler.h" -#include "File.h" -#include "MachONormalizedFileBinaryUtils.h" -#include "MachOPasses.h" -#include "lld/Common/LLVM.h" -#include "lld/Core/DefinedAtom.h" -#include "lld/Core/File.h" -#include "lld/Core/Reference.h" -#include "lld/Core/Simple.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Format.h" - -#define DEBUG_TYPE "macho-compact-unwind" - -namespace lld { -namespace mach_o { - -namespace { -struct CompactUnwindEntry { - const Atom *rangeStart; - const Atom *personalityFunction; - const Atom *lsdaLocation; - const Atom *ehFrame; - - uint32_t rangeLength; - - // There are 3 types of compact unwind entry, distinguished by the encoding - // value: 0 indicates a function with no unwind info; - // _archHandler.dwarfCompactUnwindType() indicates that the entry defers to - // __eh_frame, and that the ehFrame entry will be valid; any other value is a - // real compact unwind entry -- personalityFunction will be set and - // lsdaLocation may be. - uint32_t encoding; - - CompactUnwindEntry(const DefinedAtom *function) - : rangeStart(function), personalityFunction(nullptr), - lsdaLocation(nullptr), ehFrame(nullptr), rangeLength(function->size()), - encoding(0) {} - - CompactUnwindEntry() - : rangeStart(nullptr), personalityFunction(nullptr), - lsdaLocation(nullptr), ehFrame(nullptr), rangeLength(0), encoding(0) {} -}; - -struct UnwindInfoPage { - ArrayRef<CompactUnwindEntry> entries; -}; -} - -class UnwindInfoAtom : public SimpleDefinedAtom { -public: - UnwindInfoAtom(ArchHandler &archHandler, const File &file, bool isBig, - std::vector<const Atom *> &personalities, - std::vector<uint32_t> &commonEncodings, - std::vector<UnwindInfoPage> &pages, uint32_t numLSDAs) - : SimpleDefinedAtom(file), _archHandler(archHandler), - _commonEncodingsOffset(7 * sizeof(uint32_t)), - _personalityArrayOffset(_commonEncodingsOffset + - commonEncodings.size() * sizeof(uint32_t)), - _topLevelIndexOffset(_personalityArrayOffset + - personalities.size() * sizeof(uint32_t)), - _lsdaIndexOffset(_topLevelIndexOffset + - 3 * (pages.size() + 1) * sizeof(uint32_t)), - _firstPageOffset(_lsdaIndexOffset + 2 * numLSDAs * sizeof(uint32_t)), - _isBig(isBig) { - - addHeader(commonEncodings.size(), personalities.size(), pages.size()); - addCommonEncodings(commonEncodings); - addPersonalityFunctions(personalities); - addTopLevelIndexes(pages); - addLSDAIndexes(pages, numLSDAs); - addSecondLevelPages(pages); - } - - ~UnwindInfoAtom() override = default; - - ContentType contentType() const override { - return DefinedAtom::typeProcessedUnwindInfo; - } - - Alignment alignment() const override { return 4; } - - uint64_t size() const override { return _contents.size(); } - - ContentPermissions permissions() const override { - return DefinedAtom::permR__; - } - - ArrayRef<uint8_t> rawContent() const override { return _contents; } - - void addHeader(uint32_t numCommon, uint32_t numPersonalities, - uint32_t numPages) { - using normalized::write32; - - uint32_t headerSize = 7 * sizeof(uint32_t); - _contents.resize(headerSize); - - uint8_t *headerEntries = _contents.data(); - // version - write32(headerEntries, 1, _isBig); - // commonEncodingsArraySectionOffset - write32(headerEntries + sizeof(uint32_t), _commonEncodingsOffset, _isBig); - // commonEncodingsArrayCount - write32(headerEntries + 2 * sizeof(uint32_t), numCommon, _isBig); - // personalityArraySectionOffset - write32(headerEntries + 3 * sizeof(uint32_t), _personalityArrayOffset, - _isBig); - // personalityArrayCount - write32(headerEntries + 4 * sizeof(uint32_t), numPersonalities, _isBig); - // indexSectionOffset - write32(headerEntries + 5 * sizeof(uint32_t), _topLevelIndexOffset, _isBig); - // indexCount - write32(headerEntries + 6 * sizeof(uint32_t), numPages + 1, _isBig); - } - - /// Add the list of common encodings to the section; this is simply an array - /// of uint32_t compact values. Size has already been specified in the header. - void addCommonEncodings(std::vector<uint32_t> &commonEncodings) { - using normalized::write32; - - _contents.resize(_commonEncodingsOffset + - commonEncodings.size() * sizeof(uint32_t)); - uint8_t *commonEncodingsArea = - reinterpret_cast<uint8_t *>(_contents.data() + _commonEncodingsOffset); - - for (uint32_t encoding : commonEncodings) { - write32(commonEncodingsArea, encoding, _isBig); - commonEncodingsArea += sizeof(uint32_t); - } - } - - void addPersonalityFunctions(std::vector<const Atom *> personalities) { - _contents.resize(_personalityArrayOffset + - personalities.size() * sizeof(uint32_t)); - - for (unsigned i = 0; i < personalities.size(); ++i) - addImageReferenceIndirect(_personalityArrayOffset + i * sizeof(uint32_t), - personalities[i]); - } - - void addTopLevelIndexes(std::vector<UnwindInfoPage> &pages) { - using normalized::write32; - - uint32_t numIndexes = pages.size() + 1; - _contents.resize(_topLevelIndexOffset + numIndexes * 3 * sizeof(uint32_t)); - - uint32_t pageLoc = _firstPageOffset; - - // The most difficult job here is calculating the LSDAs; everything else - // follows fairly naturally, but we can't state where the first - uint8_t *indexData = &_contents[_topLevelIndexOffset]; - uint32_t numLSDAs = 0; - for (unsigned i = 0; i < pages.size(); ++i) { - // functionOffset - addImageReference(_topLevelIndexOffset + 3 * i * sizeof(uint32_t), - pages[i].entries[0].rangeStart); - // secondLevelPagesSectionOffset - write32(indexData + (3 * i + 1) * sizeof(uint32_t), pageLoc, _isBig); - write32(indexData + (3 * i + 2) * sizeof(uint32_t), - _lsdaIndexOffset + numLSDAs * 2 * sizeof(uint32_t), _isBig); - - for (auto &entry : pages[i].entries) - if (entry.lsdaLocation) - ++numLSDAs; - } - - // Finally, write out the final sentinel index - auto &finalEntry = pages[pages.size() - 1].entries.back(); - addImageReference(_topLevelIndexOffset + - 3 * pages.size() * sizeof(uint32_t), - finalEntry.rangeStart, finalEntry.rangeLength); - // secondLevelPagesSectionOffset => 0 - write32(indexData + (3 * pages.size() + 2) * sizeof(uint32_t), - _lsdaIndexOffset + numLSDAs * 2 * sizeof(uint32_t), _isBig); - } - - void addLSDAIndexes(std::vector<UnwindInfoPage> &pages, uint32_t numLSDAs) { - _contents.resize(_lsdaIndexOffset + numLSDAs * 2 * sizeof(uint32_t)); - - uint32_t curOffset = _lsdaIndexOffset; - for (auto &page : pages) { - for (auto &entry : page.entries) { - if (!entry.lsdaLocation) - continue; - - addImageReference(curOffset, entry.rangeStart); - addImageReference(curOffset + sizeof(uint32_t), entry.lsdaLocation); - curOffset += 2 * sizeof(uint32_t); - } - } - } - - void addSecondLevelPages(std::vector<UnwindInfoPage> &pages) { - for (auto &page : pages) { - addRegularSecondLevelPage(page); - } - } - - void addRegularSecondLevelPage(const UnwindInfoPage &page) { - uint32_t curPageOffset = _contents.size(); - const int16_t headerSize = sizeof(uint32_t) + 2 * sizeof(uint16_t); - uint32_t curPageSize = - headerSize + 2 * page.entries.size() * sizeof(uint32_t); - _contents.resize(curPageOffset + curPageSize); - - using normalized::write32; - using normalized::write16; - // 2 => regular page - write32(&_contents[curPageOffset], 2, _isBig); - // offset of 1st entry - write16(&_contents[curPageOffset + 4], headerSize, _isBig); - write16(&_contents[curPageOffset + 6], page.entries.size(), _isBig); - - uint32_t pagePos = curPageOffset + headerSize; - for (auto &entry : page.entries) { - addImageReference(pagePos, entry.rangeStart); - - write32(_contents.data() + pagePos + sizeof(uint32_t), entry.encoding, - _isBig); - if ((entry.encoding & 0x0f000000U) == - _archHandler.dwarfCompactUnwindType()) - addEhFrameReference(pagePos + sizeof(uint32_t), entry.ehFrame); - - pagePos += 2 * sizeof(uint32_t); - } - } - - void addEhFrameReference(uint32_t offset, const Atom *dest, - Reference::Addend addend = 0) { - addReference(Reference::KindNamespace::mach_o, _archHandler.kindArch(), - _archHandler.unwindRefToEhFrameKind(), offset, dest, addend); - } - - void addImageReference(uint32_t offset, const Atom *dest, - Reference::Addend addend = 0) { - addReference(Reference::KindNamespace::mach_o, _archHandler.kindArch(), - _archHandler.imageOffsetKind(), offset, dest, addend); - } - - void addImageReferenceIndirect(uint32_t offset, const Atom *dest) { - addReference(Reference::KindNamespace::mach_o, _archHandler.kindArch(), - _archHandler.imageOffsetKindIndirect(), offset, dest, 0); - } - -private: - mach_o::ArchHandler &_archHandler; - std::vector<uint8_t> _contents; - uint32_t _commonEncodingsOffset; - uint32_t _personalityArrayOffset; - uint32_t _topLevelIndexOffset; - uint32_t _lsdaIndexOffset; - uint32_t _firstPageOffset; - bool _isBig; -}; - -/// Pass for instantiating and optimizing GOT slots. -/// -class CompactUnwindPass : public Pass { -public: - CompactUnwindPass(const MachOLinkingContext &context) - : _ctx(context), _archHandler(_ctx.archHandler()), - _file(*_ctx.make_file<MachOFile>("<mach-o Compact Unwind Pass>")), - _isBig(MachOLinkingContext::isBigEndian(_ctx.arch())) { - _file.setOrdinal(_ctx.getNextOrdinalAndIncrement()); - } - -private: - llvm::Error perform(SimpleFile &mergedFile) override { - LLVM_DEBUG(llvm::dbgs() << "MachO Compact Unwind pass\n"); - - std::map<const Atom *, CompactUnwindEntry> unwindLocs; - std::map<const Atom *, const Atom *> dwarfFrames; - std::vector<const Atom *> personalities; - uint32_t numLSDAs = 0; - - // First collect all __compact_unwind and __eh_frame entries, addressable by - // the function referred to. - collectCompactUnwindEntries(mergedFile, unwindLocs, personalities, - numLSDAs); - - collectDwarfFrameEntries(mergedFile, dwarfFrames); - - // Skip rest of pass if no unwind info. - if (unwindLocs.empty() && dwarfFrames.empty()) - return llvm::Error::success(); - - // FIXME: if there are more than 4 personality functions then we need to - // defer to DWARF info for the ones we don't put in the list. They should - // also probably be sorted by frequency. - assert(personalities.size() <= 4); - - // TODO: Find commmon encodings for use by compressed pages. - std::vector<uint32_t> commonEncodings; - - // Now sort the entries by final address and fixup the compact encoding to - // its final form (i.e. set personality function bits & create DWARF - // references where needed). - std::vector<CompactUnwindEntry> unwindInfos = createUnwindInfoEntries( - mergedFile, unwindLocs, personalities, dwarfFrames); - - // Remove any unused eh-frame atoms. - pruneUnusedEHFrames(mergedFile, unwindInfos, unwindLocs, dwarfFrames); - - // Finally, we can start creating pages based on these entries. - - LLVM_DEBUG(llvm::dbgs() << " Splitting entries into pages\n"); - // FIXME: we split the entries into pages naively: lots of 4k pages followed - // by a small one. ld64 tried to minimize space and align them to real 4k - // boundaries. That might be worth doing, or perhaps we could perform some - // minor balancing for expected number of lookups. - std::vector<UnwindInfoPage> pages; - auto remainingInfos = llvm::makeArrayRef(unwindInfos); - do { - pages.push_back(UnwindInfoPage()); - - // FIXME: we only create regular pages at the moment. These can hold up to - // 1021 entries according to the documentation. - unsigned entriesInPage = std::min(1021U, (unsigned)remainingInfos.size()); - - pages.back().entries = remainingInfos.slice(0, entriesInPage); - remainingInfos = remainingInfos.slice(entriesInPage); - - LLVM_DEBUG(llvm::dbgs() - << " Page from " - << pages.back().entries[0].rangeStart->name() << " to " - << pages.back().entries.back().rangeStart->name() << " + " - << llvm::format("0x%x", - pages.back().entries.back().rangeLength) - << " has " << entriesInPage << " entries\n"); - } while (!remainingInfos.empty()); - - auto *unwind = new (_file.allocator()) - UnwindInfoAtom(_archHandler, _file, _isBig, personalities, - commonEncodings, pages, numLSDAs); - mergedFile.addAtom(*unwind); - - // Finally, remove all __compact_unwind atoms now that we've processed them. - mergedFile.removeDefinedAtomsIf([](const DefinedAtom *atom) { - return atom->contentType() == DefinedAtom::typeCompactUnwindInfo; - }); - - return llvm::Error::success(); - } - - void collectCompactUnwindEntries( - const SimpleFile &mergedFile, - std::map<const Atom *, CompactUnwindEntry> &unwindLocs, - std::vector<const Atom *> &personalities, uint32_t &numLSDAs) { - LLVM_DEBUG(llvm::dbgs() << " Collecting __compact_unwind entries\n"); - - for (const DefinedAtom *atom : mergedFile.defined()) { - if (atom->contentType() != DefinedAtom::typeCompactUnwindInfo) - continue; - - auto unwindEntry = extractCompactUnwindEntry(atom); - unwindLocs.insert(std::make_pair(unwindEntry.rangeStart, unwindEntry)); - - LLVM_DEBUG(llvm::dbgs() << " Entry for " - << unwindEntry.rangeStart->name() << ", encoding=" - << llvm::format("0x%08x", unwindEntry.encoding)); - if (unwindEntry.personalityFunction) - LLVM_DEBUG(llvm::dbgs() - << ", personality=" - << unwindEntry.personalityFunction->name() - << ", lsdaLoc=" << unwindEntry.lsdaLocation->name()); - LLVM_DEBUG(llvm::dbgs() << '\n'); - - // Count number of LSDAs we see, since we need to know how big the index - // will be while laying out the section. - if (unwindEntry.lsdaLocation) - ++numLSDAs; - - // Gather the personality functions now, so that they're in deterministic - // order (derived from the DefinedAtom order). - if (unwindEntry.personalityFunction && - !llvm::count(personalities, unwindEntry.personalityFunction)) - personalities.push_back(unwindEntry.personalityFunction); - } - } - - CompactUnwindEntry extractCompactUnwindEntry(const DefinedAtom *atom) { - CompactUnwindEntry entry; - - for (const Reference *ref : *atom) { - switch (ref->offsetInAtom()) { - case 0: - // FIXME: there could legitimately be functions with multiple encoding - // entries. However, nothing produces them at the moment. - assert(ref->addend() == 0 && "unexpected offset into function"); - entry.rangeStart = ref->target(); - break; - case 0x10: - assert(ref->addend() == 0 && "unexpected offset into personality fn"); - entry.personalityFunction = ref->target(); - break; - case 0x18: - assert(ref->addend() == 0 && "unexpected offset into LSDA atom"); - entry.lsdaLocation = ref->target(); - break; - } - } - - if (atom->rawContent().size() < 4 * sizeof(uint32_t)) - return entry; - - using normalized::read32; - entry.rangeLength = - read32(atom->rawContent().data() + 2 * sizeof(uint32_t), _isBig); - entry.encoding = - read32(atom->rawContent().data() + 3 * sizeof(uint32_t), _isBig); - return entry; - } - - void - collectDwarfFrameEntries(const SimpleFile &mergedFile, - std::map<const Atom *, const Atom *> &dwarfFrames) { - for (const DefinedAtom *ehFrameAtom : mergedFile.defined()) { - if (ehFrameAtom->contentType() != DefinedAtom::typeCFI) - continue; - if (ArchHandler::isDwarfCIE(_isBig, ehFrameAtom)) - continue; - - if (const Atom *function = _archHandler.fdeTargetFunction(ehFrameAtom)) - dwarfFrames[function] = ehFrameAtom; - } - } - - /// Every atom defined in __TEXT,__text needs an entry in the final - /// __unwind_info section (in order). These comes from two sources: - /// + Input __compact_unwind sections where possible (after adding the - /// personality function offset which is only known now). - /// + A synthesised reference to __eh_frame if there's no __compact_unwind - /// or too many personality functions to be accommodated. - std::vector<CompactUnwindEntry> createUnwindInfoEntries( - const SimpleFile &mergedFile, - const std::map<const Atom *, CompactUnwindEntry> &unwindLocs, - const std::vector<const Atom *> &personalities, - const std::map<const Atom *, const Atom *> &dwarfFrames) { - std::vector<CompactUnwindEntry> unwindInfos; - - LLVM_DEBUG(llvm::dbgs() << " Creating __unwind_info entries\n"); - // The final order in the __unwind_info section must be derived from the - // order of typeCode atoms, since that's how they'll be put into the object - // file eventually (yuck!). - for (const DefinedAtom *atom : mergedFile.defined()) { - if (atom->contentType() != DefinedAtom::typeCode) - continue; - - unwindInfos.push_back(finalizeUnwindInfoEntryForAtom( - atom, unwindLocs, personalities, dwarfFrames)); - - LLVM_DEBUG(llvm::dbgs() - << " Entry for " << atom->name() << ", final encoding=" - << llvm::format("0x%08x", unwindInfos.back().encoding) - << '\n'); - } - - return unwindInfos; - } - - /// Remove unused EH frames. - /// - /// An EH frame is considered unused if there is a corresponding compact - /// unwind atom that doesn't require the EH frame. - void pruneUnusedEHFrames( - SimpleFile &mergedFile, - const std::vector<CompactUnwindEntry> &unwindInfos, - const std::map<const Atom *, CompactUnwindEntry> &unwindLocs, - const std::map<const Atom *, const Atom *> &dwarfFrames) { - - // Worklist of all 'used' FDEs. - std::vector<const DefinedAtom *> usedDwarfWorklist; - - // We have to check two conditions when building the worklist: - // (1) EH frames used by compact unwind entries. - for (auto &entry : unwindInfos) - if (entry.ehFrame) - usedDwarfWorklist.push_back(cast<DefinedAtom>(entry.ehFrame)); - - // (2) EH frames that reference functions with no corresponding compact - // unwind info. - for (auto &entry : dwarfFrames) - if (!unwindLocs.count(entry.first)) - usedDwarfWorklist.push_back(cast<DefinedAtom>(entry.second)); - - // Add all transitively referenced CFI atoms by processing the worklist. - std::set<const Atom *> usedDwarfFrames; - while (!usedDwarfWorklist.empty()) { - const DefinedAtom *cfiAtom = usedDwarfWorklist.back(); - usedDwarfWorklist.pop_back(); - usedDwarfFrames.insert(cfiAtom); - for (const auto *ref : *cfiAtom) { - const DefinedAtom *cfiTarget = dyn_cast<DefinedAtom>(ref->target()); - if (cfiTarget->contentType() == DefinedAtom::typeCFI) - usedDwarfWorklist.push_back(cfiTarget); - } - } - - // Finally, delete all unreferenced CFI atoms. - mergedFile.removeDefinedAtomsIf([&](const DefinedAtom *atom) { - if ((atom->contentType() == DefinedAtom::typeCFI) && - !usedDwarfFrames.count(atom)) - return true; - return false; - }); - } - - CompactUnwindEntry finalizeUnwindInfoEntryForAtom( - const DefinedAtom *function, - const std::map<const Atom *, CompactUnwindEntry> &unwindLocs, - const std::vector<const Atom *> &personalities, - const std::map<const Atom *, const Atom *> &dwarfFrames) { - auto unwindLoc = unwindLocs.find(function); - - CompactUnwindEntry entry; - if (unwindLoc == unwindLocs.end()) { - // Default entry has correct encoding (0 => no unwind), but we need to - // synthesise the function. - entry.rangeStart = function; - entry.rangeLength = function->size(); - } else - entry = unwindLoc->second; - - - // If there's no __compact_unwind entry, or it explicitly says to use - // __eh_frame, we need to try and fill in the correct DWARF atom. - if (entry.encoding == _archHandler.dwarfCompactUnwindType() || - entry.encoding == 0) { - auto dwarfFrame = dwarfFrames.find(function); - if (dwarfFrame != dwarfFrames.end()) { - entry.encoding = _archHandler.dwarfCompactUnwindType(); - entry.ehFrame = dwarfFrame->second; - } - } - - auto personality = llvm::find(personalities, entry.personalityFunction); - uint32_t personalityIdx = personality == personalities.end() - ? 0 - : personality - personalities.begin() + 1; - - // FIXME: We should also use DWARF when there isn't enough room for the - // personality function in the compact encoding. - assert(personalityIdx < 4 && "too many personality functions"); - - entry.encoding |= personalityIdx << 28; - - if (entry.lsdaLocation) - entry.encoding |= 1U << 30; - - return entry; - } - - const MachOLinkingContext &_ctx; - mach_o::ArchHandler &_archHandler; - MachOFile &_file; - bool _isBig; -}; - -void addCompactUnwindPass(PassManager &pm, const MachOLinkingContext &ctx) { - assert(ctx.needsCompactUnwindPass()); - pm.add(llvm::make_unique<CompactUnwindPass>(ctx)); -} - -} // end namesapce mach_o -} // end namesapce lld |
