| File: | tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp |
| Warning: | line 374, column 7 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- lib/ReaderWriter/MachO/CompactUnwindPass.cpp -------------*- C++ -*-===// | |||||||||
| 2 | // | |||||||||
| 3 | // The LLVM Linker | |||||||||
| 4 | // | |||||||||
| 5 | // This file is distributed under the University of Illinois Open Source | |||||||||
| 6 | // License. See LICENSE.TXT for details. | |||||||||
| 7 | // | |||||||||
| 8 | //===----------------------------------------------------------------------===// | |||||||||
| 9 | /// | |||||||||
| 10 | /// \file A pass to convert MachO's __compact_unwind sections into the final | |||||||||
| 11 | /// __unwind_info format used during runtime. See | |||||||||
| 12 | /// mach-o/compact_unwind_encoding.h for more details on the formats involved. | |||||||||
| 13 | /// | |||||||||
| 14 | //===----------------------------------------------------------------------===// | |||||||||
| 15 | ||||||||||
| 16 | #include "ArchHandler.h" | |||||||||
| 17 | #include "File.h" | |||||||||
| 18 | #include "MachONormalizedFileBinaryUtils.h" | |||||||||
| 19 | #include "MachOPasses.h" | |||||||||
| 20 | #include "lld/Common/LLVM.h" | |||||||||
| 21 | #include "lld/Core/DefinedAtom.h" | |||||||||
| 22 | #include "lld/Core/File.h" | |||||||||
| 23 | #include "lld/Core/Reference.h" | |||||||||
| 24 | #include "lld/Core/Simple.h" | |||||||||
| 25 | #include "llvm/ADT/DenseMap.h" | |||||||||
| 26 | #include "llvm/Support/Debug.h" | |||||||||
| 27 | #include "llvm/Support/Format.h" | |||||||||
| 28 | ||||||||||
| 29 | #define DEBUG_TYPE"macho-compact-unwind" "macho-compact-unwind" | |||||||||
| 30 | ||||||||||
| 31 | namespace lld { | |||||||||
| 32 | namespace mach_o { | |||||||||
| 33 | ||||||||||
| 34 | namespace { | |||||||||
| 35 | struct CompactUnwindEntry { | |||||||||
| 36 | const Atom *rangeStart; | |||||||||
| 37 | const Atom *personalityFunction; | |||||||||
| 38 | const Atom *lsdaLocation; | |||||||||
| 39 | const Atom *ehFrame; | |||||||||
| 40 | ||||||||||
| 41 | uint32_t rangeLength; | |||||||||
| 42 | ||||||||||
| 43 | // There are 3 types of compact unwind entry, distinguished by the encoding | |||||||||
| 44 | // value: 0 indicates a function with no unwind info; | |||||||||
| 45 | // _archHandler.dwarfCompactUnwindType() indicates that the entry defers to | |||||||||
| 46 | // __eh_frame, and that the ehFrame entry will be valid; any other value is a | |||||||||
| 47 | // real compact unwind entry -- personalityFunction will be set and | |||||||||
| 48 | // lsdaLocation may be. | |||||||||
| 49 | uint32_t encoding; | |||||||||
| 50 | ||||||||||
| 51 | CompactUnwindEntry(const DefinedAtom *function) | |||||||||
| 52 | : rangeStart(function), personalityFunction(nullptr), | |||||||||
| 53 | lsdaLocation(nullptr), ehFrame(nullptr), rangeLength(function->size()), | |||||||||
| 54 | encoding(0) {} | |||||||||
| 55 | ||||||||||
| 56 | CompactUnwindEntry() | |||||||||
| 57 | : rangeStart(nullptr), personalityFunction(nullptr), | |||||||||
| 58 | lsdaLocation(nullptr), ehFrame(nullptr), rangeLength(0), encoding(0) {} | |||||||||
| 59 | }; | |||||||||
| 60 | ||||||||||
| 61 | struct UnwindInfoPage { | |||||||||
| 62 | ArrayRef<CompactUnwindEntry> entries; | |||||||||
| 63 | }; | |||||||||
| 64 | } | |||||||||
| 65 | ||||||||||
| 66 | class UnwindInfoAtom : public SimpleDefinedAtom { | |||||||||
| 67 | public: | |||||||||
| 68 | UnwindInfoAtom(ArchHandler &archHandler, const File &file, bool isBig, | |||||||||
| 69 | std::vector<const Atom *> &personalities, | |||||||||
| 70 | std::vector<uint32_t> &commonEncodings, | |||||||||
| 71 | std::vector<UnwindInfoPage> &pages, uint32_t numLSDAs) | |||||||||
| 72 | : SimpleDefinedAtom(file), _archHandler(archHandler), | |||||||||
| 73 | _commonEncodingsOffset(7 * sizeof(uint32_t)), | |||||||||
| 74 | _personalityArrayOffset(_commonEncodingsOffset + | |||||||||
| 75 | commonEncodings.size() * sizeof(uint32_t)), | |||||||||
| 76 | _topLevelIndexOffset(_personalityArrayOffset + | |||||||||
| 77 | personalities.size() * sizeof(uint32_t)), | |||||||||
| 78 | _lsdaIndexOffset(_topLevelIndexOffset + | |||||||||
| 79 | 3 * (pages.size() + 1) * sizeof(uint32_t)), | |||||||||
| 80 | _firstPageOffset(_lsdaIndexOffset + 2 * numLSDAs * sizeof(uint32_t)), | |||||||||
| 81 | _isBig(isBig) { | |||||||||
| 82 | ||||||||||
| 83 | addHeader(commonEncodings.size(), personalities.size(), pages.size()); | |||||||||
| 84 | addCommonEncodings(commonEncodings); | |||||||||
| 85 | addPersonalityFunctions(personalities); | |||||||||
| 86 | addTopLevelIndexes(pages); | |||||||||
| 87 | addLSDAIndexes(pages, numLSDAs); | |||||||||
| 88 | addSecondLevelPages(pages); | |||||||||
| 89 | } | |||||||||
| 90 | ||||||||||
| 91 | ~UnwindInfoAtom() override = default; | |||||||||
| 92 | ||||||||||
| 93 | ContentType contentType() const override { | |||||||||
| 94 | return DefinedAtom::typeProcessedUnwindInfo; | |||||||||
| 95 | } | |||||||||
| 96 | ||||||||||
| 97 | Alignment alignment() const override { return 4; } | |||||||||
| 98 | ||||||||||
| 99 | uint64_t size() const override { return _contents.size(); } | |||||||||
| 100 | ||||||||||
| 101 | ContentPermissions permissions() const override { | |||||||||
| 102 | return DefinedAtom::permR__; | |||||||||
| 103 | } | |||||||||
| 104 | ||||||||||
| 105 | ArrayRef<uint8_t> rawContent() const override { return _contents; } | |||||||||
| 106 | ||||||||||
| 107 | void addHeader(uint32_t numCommon, uint32_t numPersonalities, | |||||||||
| 108 | uint32_t numPages) { | |||||||||
| 109 | using normalized::write32; | |||||||||
| 110 | ||||||||||
| 111 | uint32_t headerSize = 7 * sizeof(uint32_t); | |||||||||
| 112 | _contents.resize(headerSize); | |||||||||
| 113 | ||||||||||
| 114 | uint8_t *headerEntries = _contents.data(); | |||||||||
| 115 | // version | |||||||||
| 116 | write32(headerEntries, 1, _isBig); | |||||||||
| 117 | // commonEncodingsArraySectionOffset | |||||||||
| 118 | write32(headerEntries + sizeof(uint32_t), _commonEncodingsOffset, _isBig); | |||||||||
| 119 | // commonEncodingsArrayCount | |||||||||
| 120 | write32(headerEntries + 2 * sizeof(uint32_t), numCommon, _isBig); | |||||||||
| 121 | // personalityArraySectionOffset | |||||||||
| 122 | write32(headerEntries + 3 * sizeof(uint32_t), _personalityArrayOffset, | |||||||||
| 123 | _isBig); | |||||||||
| 124 | // personalityArrayCount | |||||||||
| 125 | write32(headerEntries + 4 * sizeof(uint32_t), numPersonalities, _isBig); | |||||||||
| 126 | // indexSectionOffset | |||||||||
| 127 | write32(headerEntries + 5 * sizeof(uint32_t), _topLevelIndexOffset, _isBig); | |||||||||
| 128 | // indexCount | |||||||||
| 129 | write32(headerEntries + 6 * sizeof(uint32_t), numPages + 1, _isBig); | |||||||||
| 130 | } | |||||||||
| 131 | ||||||||||
| 132 | /// Add the list of common encodings to the section; this is simply an array | |||||||||
| 133 | /// of uint32_t compact values. Size has already been specified in the header. | |||||||||
| 134 | void addCommonEncodings(std::vector<uint32_t> &commonEncodings) { | |||||||||
| 135 | using normalized::write32; | |||||||||
| 136 | ||||||||||
| 137 | _contents.resize(_commonEncodingsOffset + | |||||||||
| 138 | commonEncodings.size() * sizeof(uint32_t)); | |||||||||
| 139 | uint8_t *commonEncodingsArea = | |||||||||
| 140 | reinterpret_cast<uint8_t *>(_contents.data() + _commonEncodingsOffset); | |||||||||
| 141 | ||||||||||
| 142 | for (uint32_t encoding : commonEncodings) { | |||||||||
| 143 | write32(commonEncodingsArea, encoding, _isBig); | |||||||||
| 144 | commonEncodingsArea += sizeof(uint32_t); | |||||||||
| 145 | } | |||||||||
| 146 | } | |||||||||
| 147 | ||||||||||
| 148 | void addPersonalityFunctions(std::vector<const Atom *> personalities) { | |||||||||
| 149 | _contents.resize(_personalityArrayOffset + | |||||||||
| 150 | personalities.size() * sizeof(uint32_t)); | |||||||||
| 151 | ||||||||||
| 152 | for (unsigned i = 0; i < personalities.size(); ++i) | |||||||||
| 153 | addImageReferenceIndirect(_personalityArrayOffset + i * sizeof(uint32_t), | |||||||||
| 154 | personalities[i]); | |||||||||
| 155 | } | |||||||||
| 156 | ||||||||||
| 157 | void addTopLevelIndexes(std::vector<UnwindInfoPage> &pages) { | |||||||||
| 158 | using normalized::write32; | |||||||||
| 159 | ||||||||||
| 160 | uint32_t numIndexes = pages.size() + 1; | |||||||||
| 161 | _contents.resize(_topLevelIndexOffset + numIndexes * 3 * sizeof(uint32_t)); | |||||||||
| 162 | ||||||||||
| 163 | uint32_t pageLoc = _firstPageOffset; | |||||||||
| 164 | ||||||||||
| 165 | // The most difficult job here is calculating the LSDAs; everything else | |||||||||
| 166 | // follows fairly naturally, but we can't state where the first | |||||||||
| 167 | uint8_t *indexData = &_contents[_topLevelIndexOffset]; | |||||||||
| 168 | uint32_t numLSDAs = 0; | |||||||||
| 169 | for (unsigned i = 0; i < pages.size(); ++i) { | |||||||||
| 170 | // functionOffset | |||||||||
| 171 | addImageReference(_topLevelIndexOffset + 3 * i * sizeof(uint32_t), | |||||||||
| 172 | pages[i].entries[0].rangeStart); | |||||||||
| 173 | // secondLevelPagesSectionOffset | |||||||||
| 174 | write32(indexData + (3 * i + 1) * sizeof(uint32_t), pageLoc, _isBig); | |||||||||
| 175 | write32(indexData + (3 * i + 2) * sizeof(uint32_t), | |||||||||
| 176 | _lsdaIndexOffset + numLSDAs * 2 * sizeof(uint32_t), _isBig); | |||||||||
| 177 | ||||||||||
| 178 | for (auto &entry : pages[i].entries) | |||||||||
| 179 | if (entry.lsdaLocation) | |||||||||
| 180 | ++numLSDAs; | |||||||||
| 181 | } | |||||||||
| 182 | ||||||||||
| 183 | // Finally, write out the final sentinel index | |||||||||
| 184 | auto &finalEntry = pages[pages.size() - 1].entries.back(); | |||||||||
| 185 | addImageReference(_topLevelIndexOffset + | |||||||||
| 186 | 3 * pages.size() * sizeof(uint32_t), | |||||||||
| 187 | finalEntry.rangeStart, finalEntry.rangeLength); | |||||||||
| 188 | // secondLevelPagesSectionOffset => 0 | |||||||||
| 189 | write32(indexData + (3 * pages.size() + 2) * sizeof(uint32_t), | |||||||||
| 190 | _lsdaIndexOffset + numLSDAs * 2 * sizeof(uint32_t), _isBig); | |||||||||
| 191 | } | |||||||||
| 192 | ||||||||||
| 193 | void addLSDAIndexes(std::vector<UnwindInfoPage> &pages, uint32_t numLSDAs) { | |||||||||
| 194 | _contents.resize(_lsdaIndexOffset + numLSDAs * 2 * sizeof(uint32_t)); | |||||||||
| 195 | ||||||||||
| 196 | uint32_t curOffset = _lsdaIndexOffset; | |||||||||
| 197 | for (auto &page : pages) { | |||||||||
| 198 | for (auto &entry : page.entries) { | |||||||||
| 199 | if (!entry.lsdaLocation) | |||||||||
| 200 | continue; | |||||||||
| 201 | ||||||||||
| 202 | addImageReference(curOffset, entry.rangeStart); | |||||||||
| 203 | addImageReference(curOffset + sizeof(uint32_t), entry.lsdaLocation); | |||||||||
| 204 | curOffset += 2 * sizeof(uint32_t); | |||||||||
| 205 | } | |||||||||
| 206 | } | |||||||||
| 207 | } | |||||||||
| 208 | ||||||||||
| 209 | void addSecondLevelPages(std::vector<UnwindInfoPage> &pages) { | |||||||||
| 210 | for (auto &page : pages) { | |||||||||
| 211 | addRegularSecondLevelPage(page); | |||||||||
| 212 | } | |||||||||
| 213 | } | |||||||||
| 214 | ||||||||||
| 215 | void addRegularSecondLevelPage(const UnwindInfoPage &page) { | |||||||||
| 216 | uint32_t curPageOffset = _contents.size(); | |||||||||
| 217 | const int16_t headerSize = sizeof(uint32_t) + 2 * sizeof(uint16_t); | |||||||||
| 218 | uint32_t curPageSize = | |||||||||
| 219 | headerSize + 2 * page.entries.size() * sizeof(uint32_t); | |||||||||
| 220 | _contents.resize(curPageOffset + curPageSize); | |||||||||
| 221 | ||||||||||
| 222 | using normalized::write32; | |||||||||
| 223 | using normalized::write16; | |||||||||
| 224 | // 2 => regular page | |||||||||
| 225 | write32(&_contents[curPageOffset], 2, _isBig); | |||||||||
| 226 | // offset of 1st entry | |||||||||
| 227 | write16(&_contents[curPageOffset + 4], headerSize, _isBig); | |||||||||
| 228 | write16(&_contents[curPageOffset + 6], page.entries.size(), _isBig); | |||||||||
| 229 | ||||||||||
| 230 | uint32_t pagePos = curPageOffset + headerSize; | |||||||||
| 231 | for (auto &entry : page.entries) { | |||||||||
| 232 | addImageReference(pagePos, entry.rangeStart); | |||||||||
| 233 | ||||||||||
| 234 | write32(_contents.data() + pagePos + sizeof(uint32_t), entry.encoding, | |||||||||
| 235 | _isBig); | |||||||||
| 236 | if ((entry.encoding & 0x0f000000U) == | |||||||||
| 237 | _archHandler.dwarfCompactUnwindType()) | |||||||||
| 238 | addEhFrameReference(pagePos + sizeof(uint32_t), entry.ehFrame); | |||||||||
| 239 | ||||||||||
| 240 | pagePos += 2 * sizeof(uint32_t); | |||||||||
| 241 | } | |||||||||
| 242 | } | |||||||||
| 243 | ||||||||||
| 244 | void addEhFrameReference(uint32_t offset, const Atom *dest, | |||||||||
| 245 | Reference::Addend addend = 0) { | |||||||||
| 246 | addReference(Reference::KindNamespace::mach_o, _archHandler.kindArch(), | |||||||||
| 247 | _archHandler.unwindRefToEhFrameKind(), offset, dest, addend); | |||||||||
| 248 | } | |||||||||
| 249 | ||||||||||
| 250 | void addImageReference(uint32_t offset, const Atom *dest, | |||||||||
| 251 | Reference::Addend addend = 0) { | |||||||||
| 252 | addReference(Reference::KindNamespace::mach_o, _archHandler.kindArch(), | |||||||||
| 253 | _archHandler.imageOffsetKind(), offset, dest, addend); | |||||||||
| 254 | } | |||||||||
| 255 | ||||||||||
| 256 | void addImageReferenceIndirect(uint32_t offset, const Atom *dest) { | |||||||||
| 257 | addReference(Reference::KindNamespace::mach_o, _archHandler.kindArch(), | |||||||||
| 258 | _archHandler.imageOffsetKindIndirect(), offset, dest, 0); | |||||||||
| 259 | } | |||||||||
| 260 | ||||||||||
| 261 | private: | |||||||||
| 262 | mach_o::ArchHandler &_archHandler; | |||||||||
| 263 | std::vector<uint8_t> _contents; | |||||||||
| 264 | uint32_t _commonEncodingsOffset; | |||||||||
| 265 | uint32_t _personalityArrayOffset; | |||||||||
| 266 | uint32_t _topLevelIndexOffset; | |||||||||
| 267 | uint32_t _lsdaIndexOffset; | |||||||||
| 268 | uint32_t _firstPageOffset; | |||||||||
| 269 | bool _isBig; | |||||||||
| 270 | }; | |||||||||
| 271 | ||||||||||
| 272 | /// Pass for instantiating and optimizing GOT slots. | |||||||||
| 273 | /// | |||||||||
| 274 | class CompactUnwindPass : public Pass { | |||||||||
| 275 | public: | |||||||||
| 276 | CompactUnwindPass(const MachOLinkingContext &context) | |||||||||
| 277 | : _ctx(context), _archHandler(_ctx.archHandler()), | |||||||||
| 278 | _file(*_ctx.make_file<MachOFile>("<mach-o Compact Unwind Pass>")), | |||||||||
| 279 | _isBig(MachOLinkingContext::isBigEndian(_ctx.arch())) { | |||||||||
| 280 | _file.setOrdinal(_ctx.getNextOrdinalAndIncrement()); | |||||||||
| 281 | } | |||||||||
| 282 | ||||||||||
| 283 | private: | |||||||||
| 284 | llvm::Error perform(SimpleFile &mergedFile) override { | |||||||||
| 285 | LLVM_DEBUG(llvm::dbgs() << "MachO Compact Unwind pass\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << "MachO Compact Unwind pass\n" ; } } while (false); | |||||||||
| 286 | ||||||||||
| 287 | std::map<const Atom *, CompactUnwindEntry> unwindLocs; | |||||||||
| 288 | std::map<const Atom *, const Atom *> dwarfFrames; | |||||||||
| 289 | std::vector<const Atom *> personalities; | |||||||||
| 290 | uint32_t numLSDAs = 0; | |||||||||
| 291 | ||||||||||
| 292 | // First collect all __compact_unwind and __eh_frame entries, addressable by | |||||||||
| 293 | // the function referred to. | |||||||||
| 294 | collectCompactUnwindEntries(mergedFile, unwindLocs, personalities, | |||||||||
| ||||||||||
| 295 | numLSDAs); | |||||||||
| 296 | ||||||||||
| 297 | collectDwarfFrameEntries(mergedFile, dwarfFrames); | |||||||||
| 298 | ||||||||||
| 299 | // Skip rest of pass if no unwind info. | |||||||||
| 300 | if (unwindLocs.empty() && dwarfFrames.empty()) | |||||||||
| 301 | return llvm::Error::success(); | |||||||||
| 302 | ||||||||||
| 303 | // FIXME: if there are more than 4 personality functions then we need to | |||||||||
| 304 | // defer to DWARF info for the ones we don't put in the list. They should | |||||||||
| 305 | // also probably be sorted by frequency. | |||||||||
| 306 | assert(personalities.size() <= 4)((personalities.size() <= 4) ? static_cast<void> (0) : __assert_fail ("personalities.size() <= 4", "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 306, __PRETTY_FUNCTION__)); | |||||||||
| 307 | ||||||||||
| 308 | // TODO: Find commmon encodings for use by compressed pages. | |||||||||
| 309 | std::vector<uint32_t> commonEncodings; | |||||||||
| 310 | ||||||||||
| 311 | // Now sort the entries by final address and fixup the compact encoding to | |||||||||
| 312 | // its final form (i.e. set personality function bits & create DWARF | |||||||||
| 313 | // references where needed). | |||||||||
| 314 | std::vector<CompactUnwindEntry> unwindInfos = createUnwindInfoEntries( | |||||||||
| 315 | mergedFile, unwindLocs, personalities, dwarfFrames); | |||||||||
| 316 | ||||||||||
| 317 | // Remove any unused eh-frame atoms. | |||||||||
| 318 | pruneUnusedEHFrames(mergedFile, unwindInfos, unwindLocs, dwarfFrames); | |||||||||
| 319 | ||||||||||
| 320 | // Finally, we can start creating pages based on these entries. | |||||||||
| 321 | ||||||||||
| 322 | LLVM_DEBUG(llvm::dbgs() << " Splitting entries into pages\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Splitting entries into pages\n" ; } } while (false); | |||||||||
| 323 | // FIXME: we split the entries into pages naively: lots of 4k pages followed | |||||||||
| 324 | // by a small one. ld64 tried to minimize space and align them to real 4k | |||||||||
| 325 | // boundaries. That might be worth doing, or perhaps we could perform some | |||||||||
| 326 | // minor balancing for expected number of lookups. | |||||||||
| 327 | std::vector<UnwindInfoPage> pages; | |||||||||
| 328 | auto remainingInfos = llvm::makeArrayRef(unwindInfos); | |||||||||
| 329 | do { | |||||||||
| 330 | pages.push_back(UnwindInfoPage()); | |||||||||
| 331 | ||||||||||
| 332 | // FIXME: we only create regular pages at the moment. These can hold up to | |||||||||
| 333 | // 1021 entries according to the documentation. | |||||||||
| 334 | unsigned entriesInPage = std::min(1021U, (unsigned)remainingInfos.size()); | |||||||||
| 335 | ||||||||||
| 336 | pages.back().entries = remainingInfos.slice(0, entriesInPage); | |||||||||
| 337 | remainingInfos = remainingInfos.slice(entriesInPage); | |||||||||
| 338 | ||||||||||
| 339 | LLVM_DEBUG(llvm::dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { 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 (false) | |||||||||
| 340 | << " Page from "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { 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 (false) | |||||||||
| 341 | << pages.back().entries[0].rangeStart->name() << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { 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 (false) | |||||||||
| 342 | << pages.back().entries.back().rangeStart->name() << " + "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { 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 (false) | |||||||||
| 343 | << llvm::format("0x%x",do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { 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 (false) | |||||||||
| 344 | pages.back().entries.back().rangeLength)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { 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 (false) | |||||||||
| 345 | << " has " << entriesInPage << " entries\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { 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 (false); | |||||||||
| 346 | } while (!remainingInfos.empty()); | |||||||||
| 347 | ||||||||||
| 348 | auto *unwind = new (_file.allocator()) | |||||||||
| 349 | UnwindInfoAtom(_archHandler, _file, _isBig, personalities, | |||||||||
| 350 | commonEncodings, pages, numLSDAs); | |||||||||
| 351 | mergedFile.addAtom(*unwind); | |||||||||
| 352 | ||||||||||
| 353 | // Finally, remove all __compact_unwind atoms now that we've processed them. | |||||||||
| 354 | mergedFile.removeDefinedAtomsIf([](const DefinedAtom *atom) { | |||||||||
| 355 | return atom->contentType() == DefinedAtom::typeCompactUnwindInfo; | |||||||||
| 356 | }); | |||||||||
| 357 | ||||||||||
| 358 | return llvm::Error::success(); | |||||||||
| 359 | } | |||||||||
| 360 | ||||||||||
| 361 | void collectCompactUnwindEntries( | |||||||||
| 362 | const SimpleFile &mergedFile, | |||||||||
| 363 | std::map<const Atom *, CompactUnwindEntry> &unwindLocs, | |||||||||
| 364 | std::vector<const Atom *> &personalities, uint32_t &numLSDAs) { | |||||||||
| 365 | LLVM_DEBUG(llvm::dbgs() << " Collecting __compact_unwind entries\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Collecting __compact_unwind entries\n" ; } } while (false); | |||||||||
| 366 | ||||||||||
| 367 | for (const DefinedAtom *atom : mergedFile.defined()) { | |||||||||
| 368 | if (atom->contentType() != DefinedAtom::typeCompactUnwindInfo) | |||||||||
| 369 | continue; | |||||||||
| 370 | ||||||||||
| 371 | auto unwindEntry = extractCompactUnwindEntry(atom); | |||||||||
| 372 | unwindLocs.insert(std::make_pair(unwindEntry.rangeStart, unwindEntry)); | |||||||||
| 373 | ||||||||||
| 374 | LLVM_DEBUG(llvm::dbgs() << " Entry for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << unwindEntry.rangeStart->name() << ", encoding=" << llvm::format("0x%08x", unwindEntry.encoding); } } while (false) | |||||||||
| ||||||||||
| 375 | << unwindEntry.rangeStart->name() << ", encoding="do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << unwindEntry.rangeStart->name() << ", encoding=" << llvm::format("0x%08x", unwindEntry.encoding); } } while (false) | |||||||||
| 376 | << llvm::format("0x%08x", unwindEntry.encoding))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << unwindEntry.rangeStart->name() << ", encoding=" << llvm::format("0x%08x", unwindEntry.encoding); } } while (false); | |||||||||
| 377 | if (unwindEntry.personalityFunction) | |||||||||
| 378 | LLVM_DEBUG(llvm::dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << ", personality=" << unwindEntry.personalityFunction->name() << ", lsdaLoc=" << unwindEntry.lsdaLocation->name(); } } while (false) | |||||||||
| 379 | << ", personality="do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << ", personality=" << unwindEntry.personalityFunction->name() << ", lsdaLoc=" << unwindEntry.lsdaLocation->name(); } } while (false) | |||||||||
| 380 | << unwindEntry.personalityFunction->name()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << ", personality=" << unwindEntry.personalityFunction->name() << ", lsdaLoc=" << unwindEntry.lsdaLocation->name(); } } while (false) | |||||||||
| 381 | << ", lsdaLoc=" << unwindEntry.lsdaLocation->name())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << ", personality=" << unwindEntry.personalityFunction->name() << ", lsdaLoc=" << unwindEntry.lsdaLocation->name(); } } while (false); | |||||||||
| 382 | LLVM_DEBUG(llvm::dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << '\n'; } } while (false); | |||||||||
| 383 | ||||||||||
| 384 | // Count number of LSDAs we see, since we need to know how big the index | |||||||||
| 385 | // will be while laying out the section. | |||||||||
| 386 | if (unwindEntry.lsdaLocation) | |||||||||
| 387 | ++numLSDAs; | |||||||||
| 388 | ||||||||||
| 389 | // Gather the personality functions now, so that they're in deterministic | |||||||||
| 390 | // order (derived from the DefinedAtom order). | |||||||||
| 391 | if (unwindEntry.personalityFunction) { | |||||||||
| 392 | auto pFunc = std::find(personalities.begin(), personalities.end(), | |||||||||
| 393 | unwindEntry.personalityFunction); | |||||||||
| 394 | if (pFunc == personalities.end()) | |||||||||
| 395 | personalities.push_back(unwindEntry.personalityFunction); | |||||||||
| 396 | } | |||||||||
| 397 | } | |||||||||
| 398 | } | |||||||||
| 399 | ||||||||||
| 400 | CompactUnwindEntry extractCompactUnwindEntry(const DefinedAtom *atom) { | |||||||||
| 401 | CompactUnwindEntry entry; | |||||||||
| 402 | ||||||||||
| 403 | for (const Reference *ref : *atom) { | |||||||||
| 404 | switch (ref->offsetInAtom()) { | |||||||||
| 405 | case 0: | |||||||||
| 406 | // FIXME: there could legitimately be functions with multiple encoding | |||||||||
| 407 | // entries. However, nothing produces them at the moment. | |||||||||
| 408 | assert(ref->addend() == 0 && "unexpected offset into function")((ref->addend() == 0 && "unexpected offset into function" ) ? static_cast<void> (0) : __assert_fail ("ref->addend() == 0 && \"unexpected offset into function\"" , "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 408, __PRETTY_FUNCTION__)); | |||||||||
| 409 | entry.rangeStart = ref->target(); | |||||||||
| 410 | break; | |||||||||
| 411 | case 0x10: | |||||||||
| 412 | assert(ref->addend() == 0 && "unexpected offset into personality fn")((ref->addend() == 0 && "unexpected offset into personality fn" ) ? static_cast<void> (0) : __assert_fail ("ref->addend() == 0 && \"unexpected offset into personality fn\"" , "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 412, __PRETTY_FUNCTION__)); | |||||||||
| 413 | entry.personalityFunction = ref->target(); | |||||||||
| 414 | break; | |||||||||
| 415 | case 0x18: | |||||||||
| 416 | assert(ref->addend() == 0 && "unexpected offset into LSDA atom")((ref->addend() == 0 && "unexpected offset into LSDA atom" ) ? static_cast<void> (0) : __assert_fail ("ref->addend() == 0 && \"unexpected offset into LSDA atom\"" , "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 416, __PRETTY_FUNCTION__)); | |||||||||
| 417 | entry.lsdaLocation = ref->target(); | |||||||||
| 418 | break; | |||||||||
| 419 | } | |||||||||
| 420 | } | |||||||||
| 421 | ||||||||||
| 422 | if (atom->rawContent().size() < 4 * sizeof(uint32_t)) | |||||||||
| 423 | return entry; | |||||||||
| 424 | ||||||||||
| 425 | using normalized::read32; | |||||||||
| 426 | entry.rangeLength = | |||||||||
| 427 | read32(atom->rawContent().data() + 2 * sizeof(uint32_t), _isBig); | |||||||||
| 428 | entry.encoding = | |||||||||
| 429 | read32(atom->rawContent().data() + 3 * sizeof(uint32_t), _isBig); | |||||||||
| 430 | return entry; | |||||||||
| 431 | } | |||||||||
| 432 | ||||||||||
| 433 | void | |||||||||
| 434 | collectDwarfFrameEntries(const SimpleFile &mergedFile, | |||||||||
| 435 | std::map<const Atom *, const Atom *> &dwarfFrames) { | |||||||||
| 436 | for (const DefinedAtom *ehFrameAtom : mergedFile.defined()) { | |||||||||
| 437 | if (ehFrameAtom->contentType() != DefinedAtom::typeCFI) | |||||||||
| 438 | continue; | |||||||||
| 439 | if (ArchHandler::isDwarfCIE(_isBig, ehFrameAtom)) | |||||||||
| 440 | continue; | |||||||||
| 441 | ||||||||||
| 442 | if (const Atom *function = _archHandler.fdeTargetFunction(ehFrameAtom)) | |||||||||
| 443 | dwarfFrames[function] = ehFrameAtom; | |||||||||
| 444 | } | |||||||||
| 445 | } | |||||||||
| 446 | ||||||||||
| 447 | /// Every atom defined in __TEXT,__text needs an entry in the final | |||||||||
| 448 | /// __unwind_info section (in order). These comes from two sources: | |||||||||
| 449 | /// + Input __compact_unwind sections where possible (after adding the | |||||||||
| 450 | /// personality function offset which is only known now). | |||||||||
| 451 | /// + A synthesised reference to __eh_frame if there's no __compact_unwind | |||||||||
| 452 | /// or too many personality functions to be accommodated. | |||||||||
| 453 | std::vector<CompactUnwindEntry> createUnwindInfoEntries( | |||||||||
| 454 | const SimpleFile &mergedFile, | |||||||||
| 455 | const std::map<const Atom *, CompactUnwindEntry> &unwindLocs, | |||||||||
| 456 | const std::vector<const Atom *> &personalities, | |||||||||
| 457 | const std::map<const Atom *, const Atom *> &dwarfFrames) { | |||||||||
| 458 | std::vector<CompactUnwindEntry> unwindInfos; | |||||||||
| 459 | ||||||||||
| 460 | LLVM_DEBUG(llvm::dbgs() << " Creating __unwind_info entries\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Creating __unwind_info entries\n" ; } } while (false); | |||||||||
| 461 | // The final order in the __unwind_info section must be derived from the | |||||||||
| 462 | // order of typeCode atoms, since that's how they'll be put into the object | |||||||||
| 463 | // file eventually (yuck!). | |||||||||
| 464 | for (const DefinedAtom *atom : mergedFile.defined()) { | |||||||||
| 465 | if (atom->contentType() != DefinedAtom::typeCode) | |||||||||
| 466 | continue; | |||||||||
| 467 | ||||||||||
| 468 | unwindInfos.push_back(finalizeUnwindInfoEntryForAtom( | |||||||||
| 469 | atom, unwindLocs, personalities, dwarfFrames)); | |||||||||
| 470 | ||||||||||
| 471 | LLVM_DEBUG(llvm::dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << atom->name() << ", final encoding=" << llvm::format("0x%08x", unwindInfos.back().encoding) << '\n'; } } while (false) | |||||||||
| 472 | << " Entry for " << atom->name() << ", final encoding="do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << atom->name() << ", final encoding=" << llvm::format("0x%08x", unwindInfos.back().encoding) << '\n'; } } while (false) | |||||||||
| 473 | << llvm::format("0x%08x", unwindInfos.back().encoding)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << atom->name() << ", final encoding=" << llvm::format("0x%08x", unwindInfos.back().encoding) << '\n'; } } while (false) | |||||||||
| 474 | << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("macho-compact-unwind")) { llvm::dbgs() << " Entry for " << atom->name() << ", final encoding=" << llvm::format("0x%08x", unwindInfos.back().encoding) << '\n'; } } while (false); | |||||||||
| 475 | } | |||||||||
| 476 | ||||||||||
| 477 | return unwindInfos; | |||||||||
| 478 | } | |||||||||
| 479 | ||||||||||
| 480 | /// Remove unused EH frames. | |||||||||
| 481 | /// | |||||||||
| 482 | /// An EH frame is considered unused if there is a corresponding compact | |||||||||
| 483 | /// unwind atom that doesn't require the EH frame. | |||||||||
| 484 | void pruneUnusedEHFrames( | |||||||||
| 485 | SimpleFile &mergedFile, | |||||||||
| 486 | const std::vector<CompactUnwindEntry> &unwindInfos, | |||||||||
| 487 | const std::map<const Atom *, CompactUnwindEntry> &unwindLocs, | |||||||||
| 488 | const std::map<const Atom *, const Atom *> &dwarfFrames) { | |||||||||
| 489 | ||||||||||
| 490 | // Worklist of all 'used' FDEs. | |||||||||
| 491 | std::vector<const DefinedAtom *> usedDwarfWorklist; | |||||||||
| 492 | ||||||||||
| 493 | // We have to check two conditions when building the worklist: | |||||||||
| 494 | // (1) EH frames used by compact unwind entries. | |||||||||
| 495 | for (auto &entry : unwindInfos) | |||||||||
| 496 | if (entry.ehFrame) | |||||||||
| 497 | usedDwarfWorklist.push_back(cast<DefinedAtom>(entry.ehFrame)); | |||||||||
| 498 | ||||||||||
| 499 | // (2) EH frames that reference functions with no corresponding compact | |||||||||
| 500 | // unwind info. | |||||||||
| 501 | for (auto &entry : dwarfFrames) | |||||||||
| 502 | if (!unwindLocs.count(entry.first)) | |||||||||
| 503 | usedDwarfWorklist.push_back(cast<DefinedAtom>(entry.second)); | |||||||||
| 504 | ||||||||||
| 505 | // Add all transitively referenced CFI atoms by processing the worklist. | |||||||||
| 506 | std::set<const Atom *> usedDwarfFrames; | |||||||||
| 507 | while (!usedDwarfWorklist.empty()) { | |||||||||
| 508 | const DefinedAtom *cfiAtom = usedDwarfWorklist.back(); | |||||||||
| 509 | usedDwarfWorklist.pop_back(); | |||||||||
| 510 | usedDwarfFrames.insert(cfiAtom); | |||||||||
| 511 | for (const auto *ref : *cfiAtom) { | |||||||||
| 512 | const DefinedAtom *cfiTarget = dyn_cast<DefinedAtom>(ref->target()); | |||||||||
| 513 | if (cfiTarget->contentType() == DefinedAtom::typeCFI) | |||||||||
| 514 | usedDwarfWorklist.push_back(cfiTarget); | |||||||||
| 515 | } | |||||||||
| 516 | } | |||||||||
| 517 | ||||||||||
| 518 | // Finally, delete all unreferenced CFI atoms. | |||||||||
| 519 | mergedFile.removeDefinedAtomsIf([&](const DefinedAtom *atom) { | |||||||||
| 520 | if ((atom->contentType() == DefinedAtom::typeCFI) && | |||||||||
| 521 | !usedDwarfFrames.count(atom)) | |||||||||
| 522 | return true; | |||||||||
| 523 | return false; | |||||||||
| 524 | }); | |||||||||
| 525 | } | |||||||||
| 526 | ||||||||||
| 527 | CompactUnwindEntry finalizeUnwindInfoEntryForAtom( | |||||||||
| 528 | const DefinedAtom *function, | |||||||||
| 529 | const std::map<const Atom *, CompactUnwindEntry> &unwindLocs, | |||||||||
| 530 | const std::vector<const Atom *> &personalities, | |||||||||
| 531 | const std::map<const Atom *, const Atom *> &dwarfFrames) { | |||||||||
| 532 | auto unwindLoc = unwindLocs.find(function); | |||||||||
| 533 | ||||||||||
| 534 | CompactUnwindEntry entry; | |||||||||
| 535 | if (unwindLoc == unwindLocs.end()) { | |||||||||
| 536 | // Default entry has correct encoding (0 => no unwind), but we need to | |||||||||
| 537 | // synthesise the function. | |||||||||
| 538 | entry.rangeStart = function; | |||||||||
| 539 | entry.rangeLength = function->size(); | |||||||||
| 540 | } else | |||||||||
| 541 | entry = unwindLoc->second; | |||||||||
| 542 | ||||||||||
| 543 | ||||||||||
| 544 | // If there's no __compact_unwind entry, or it explicitly says to use | |||||||||
| 545 | // __eh_frame, we need to try and fill in the correct DWARF atom. | |||||||||
| 546 | if (entry.encoding == _archHandler.dwarfCompactUnwindType() || | |||||||||
| 547 | entry.encoding == 0) { | |||||||||
| 548 | auto dwarfFrame = dwarfFrames.find(function); | |||||||||
| 549 | if (dwarfFrame != dwarfFrames.end()) { | |||||||||
| 550 | entry.encoding = _archHandler.dwarfCompactUnwindType(); | |||||||||
| 551 | entry.ehFrame = dwarfFrame->second; | |||||||||
| 552 | } | |||||||||
| 553 | } | |||||||||
| 554 | ||||||||||
| 555 | auto personality = std::find(personalities.begin(), personalities.end(), | |||||||||
| 556 | entry.personalityFunction); | |||||||||
| 557 | uint32_t personalityIdx = personality == personalities.end() | |||||||||
| 558 | ? 0 | |||||||||
| 559 | : personality - personalities.begin() + 1; | |||||||||
| 560 | ||||||||||
| 561 | // FIXME: We should also use DWARF when there isn't enough room for the | |||||||||
| 562 | // personality function in the compact encoding. | |||||||||
| 563 | assert(personalityIdx < 4 && "too many personality functions")((personalityIdx < 4 && "too many personality functions" ) ? static_cast<void> (0) : __assert_fail ("personalityIdx < 4 && \"too many personality functions\"" , "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 563, __PRETTY_FUNCTION__)); | |||||||||
| 564 | ||||||||||
| 565 | entry.encoding |= personalityIdx << 28; | |||||||||
| 566 | ||||||||||
| 567 | if (entry.lsdaLocation) | |||||||||
| 568 | entry.encoding |= 1U << 30; | |||||||||
| 569 | ||||||||||
| 570 | return entry; | |||||||||
| 571 | } | |||||||||
| 572 | ||||||||||
| 573 | const MachOLinkingContext &_ctx; | |||||||||
| 574 | mach_o::ArchHandler &_archHandler; | |||||||||
| 575 | MachOFile &_file; | |||||||||
| 576 | bool _isBig; | |||||||||
| 577 | }; | |||||||||
| 578 | ||||||||||
| 579 | void addCompactUnwindPass(PassManager &pm, const MachOLinkingContext &ctx) { | |||||||||
| 580 | assert(ctx.needsCompactUnwindPass())((ctx.needsCompactUnwindPass()) ? static_cast<void> (0) : __assert_fail ("ctx.needsCompactUnwindPass()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/lld/lib/ReaderWriter/MachO/CompactUnwindPass.cpp" , 580, __PRETTY_FUNCTION__)); | |||||||||
| 581 | pm.add(llvm::make_unique<CompactUnwindPass>(ctx)); | |||||||||
| 582 | } | |||||||||
| 583 | ||||||||||
| 584 | } // end namesapce mach_o | |||||||||
| 585 | } // end namesapce lld |
| 1 | // Pair implementation -*- C++ -*- |
| 2 | |
| 3 | // Copyright (C) 2001-2016 Free Software Foundation, Inc. |
| 4 | // |
| 5 | // This file is part of the GNU ISO C++ Library. This library is free |
| 6 | // software; you can redistribute it and/or modify it under the |
| 7 | // terms of the GNU General Public License as published by the |
| 8 | // Free Software Foundation; either version 3, or (at your option) |
| 9 | // any later version. |
| 10 | |
| 11 | // This library is distributed in the hope that it will be useful, |
| 12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 14 | // GNU General Public License for more details. |
| 15 | |
| 16 | // Under Section 7 of GPL version 3, you are granted additional |
| 17 | // permissions described in the GCC Runtime Library Exception, version |
| 18 | // 3.1, as published by the Free Software Foundation. |
| 19 | |
| 20 | // You should have received a copy of the GNU General Public License and |
| 21 | // a copy of the GCC Runtime Library Exception along with this program; |
| 22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
| 23 | // <http://www.gnu.org/licenses/>. |
| 24 | |
| 25 | /* |
| 26 | * |
| 27 | * Copyright (c) 1994 |
| 28 | * Hewlett-Packard Company |
| 29 | * |
| 30 | * Permission to use, copy, modify, distribute and sell this software |
| 31 | * and its documentation for any purpose is hereby granted without fee, |
| 32 | * provided that the above copyright notice appear in all copies and |
| 33 | * that both that copyright notice and this permission notice appear |
| 34 | * in supporting documentation. Hewlett-Packard Company makes no |
| 35 | * representations about the suitability of this software for any |
| 36 | * purpose. It is provided "as is" without express or implied warranty. |
| 37 | * |
| 38 | * |
| 39 | * Copyright (c) 1996,1997 |
| 40 | * Silicon Graphics Computer Systems, Inc. |
| 41 | * |
| 42 | * Permission to use, copy, modify, distribute and sell this software |
| 43 | * and its documentation for any purpose is hereby granted without fee, |
| 44 | * provided that the above copyright notice appear in all copies and |
| 45 | * that both that copyright notice and this permission notice appear |
| 46 | * in supporting documentation. Silicon Graphics makes no |
| 47 | * representations about the suitability of this software for any |
| 48 | * purpose. It is provided "as is" without express or implied warranty. |
| 49 | */ |
| 50 | |
| 51 | /** @file bits/stl_pair.h |
| 52 | * This is an internal header file, included by other library headers. |
| 53 | * Do not attempt to use it directly. @headername{utility} |
| 54 | */ |
| 55 | |
| 56 | #ifndef _STL_PAIR_H1 |
| 57 | #define _STL_PAIR_H1 1 |
| 58 | |
| 59 | #include <bits/move.h> // for std::move / std::forward, and std::swap |
| 60 | |
| 61 | #if __cplusplus201103L >= 201103L |
| 62 | #include <type_traits> // for std::__decay_and_strip too |
| 63 | #endif |
| 64 | |
| 65 | namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default"))) |
| 66 | { |
| 67 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
| 68 | |
| 69 | /** |
| 70 | * @addtogroup utilities |
| 71 | * @{ |
| 72 | */ |
| 73 | |
| 74 | #if __cplusplus201103L >= 201103L |
| 75 | /// piecewise_construct_t |
| 76 | struct piecewise_construct_t { explicit piecewise_construct_t() = default; }; |
| 77 | |
| 78 | /// piecewise_construct |
| 79 | constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t(); |
| 80 | |
| 81 | // Forward declarations. |
| 82 | template<typename...> |
| 83 | class tuple; |
| 84 | |
| 85 | template<std::size_t...> |
| 86 | struct _Index_tuple; |
| 87 | |
| 88 | // Concept utility functions, reused in conditionally-explicit |
| 89 | // constructors. |
| 90 | // See PR 70437, don't look at is_constructible or |
| 91 | // is_convertible if the types are the same to |
| 92 | // avoid querying those properties for incomplete types. |
| 93 | template <bool, typename _T1, typename _T2> |
| 94 | struct _PCC |
| 95 | { |
| 96 | template <typename _U1, typename _U2> |
| 97 | static constexpr bool _ConstructiblePair() |
| 98 | { |
| 99 | return __and_<is_constructible<_T1, const _U1&>, |
| 100 | is_constructible<_T2, const _U2&>>::value; |
| 101 | } |
| 102 | |
| 103 | template <typename _U1, typename _U2> |
| 104 | static constexpr bool _ImplicitlyConvertiblePair() |
| 105 | { |
| 106 | return __and_<is_convertible<const _U1&, _T1>, |
| 107 | is_convertible<const _U2&, _T2>>::value; |
| 108 | } |
| 109 | |
| 110 | template <typename _U1, typename _U2> |
| 111 | static constexpr bool _MoveConstructiblePair() |
| 112 | { |
| 113 | return __and_<is_constructible<_T1, _U1&&>, |
| 114 | is_constructible<_T2, _U2&&>>::value; |
| 115 | } |
| 116 | |
| 117 | template <typename _U1, typename _U2> |
| 118 | static constexpr bool _ImplicitlyMoveConvertiblePair() |
| 119 | { |
| 120 | return __and_<is_convertible<_U1&&, _T1>, |
| 121 | is_convertible<_U2&&, _T2>>::value; |
| 122 | } |
| 123 | |
| 124 | template <bool __implicit, typename _U1, typename _U2> |
| 125 | static constexpr bool _CopyMovePair() |
| 126 | { |
| 127 | using __do_converts = __and_<is_convertible<const _U1&, _T1>, |
| 128 | is_convertible<_U2&&, _T2>>; |
| 129 | using __converts = typename conditional<__implicit, |
| 130 | __do_converts, |
| 131 | __not_<__do_converts>>::type; |
| 132 | return __and_<is_constructible<_T1, const _U1&>, |
| 133 | is_constructible<_T2, _U2&&>, |
| 134 | __converts |
| 135 | >::value; |
| 136 | } |
| 137 | |
| 138 | template <bool __implicit, typename _U1, typename _U2> |
| 139 | static constexpr bool _MoveCopyPair() |
| 140 | { |
| 141 | using __do_converts = __and_<is_convertible<_U1&&, _T1>, |
| 142 | is_convertible<const _U2&, _T2>>; |
| 143 | using __converts = typename conditional<__implicit, |
| 144 | __do_converts, |
| 145 | __not_<__do_converts>>::type; |
| 146 | return __and_<is_constructible<_T1, _U1&&>, |
| 147 | is_constructible<_T2, const _U2&&>, |
| 148 | __converts |
| 149 | >::value; |
| 150 | } |
| 151 | }; |
| 152 | |
| 153 | template <typename _T1, typename _T2> |
| 154 | struct _PCC<false, _T1, _T2> |
| 155 | { |
| 156 | template <typename _U1, typename _U2> |
| 157 | static constexpr bool _ConstructiblePair() |
| 158 | { |
| 159 | return false; |
| 160 | } |
| 161 | |
| 162 | template <typename _U1, typename _U2> |
| 163 | static constexpr bool _ImplicitlyConvertiblePair() |
| 164 | { |
| 165 | return false; |
| 166 | } |
| 167 | |
| 168 | template <typename _U1, typename _U2> |
| 169 | static constexpr bool _MoveConstructiblePair() |
| 170 | { |
| 171 | return false; |
| 172 | } |
| 173 | |
| 174 | template <typename _U1, typename _U2> |
| 175 | static constexpr bool _ImplicitlyMoveConvertiblePair() |
| 176 | { |
| 177 | return false; |
| 178 | } |
| 179 | }; |
| 180 | |
| 181 | struct __wrap_nonesuch : std::__nonesuch { |
| 182 | explicit __wrap_nonesuch(const __nonesuch&) = delete; |
| 183 | }; |
| 184 | |
| 185 | #endif |
| 186 | |
| 187 | /** |
| 188 | * @brief Struct holding two objects of arbitrary type. |
| 189 | * |
| 190 | * @tparam _T1 Type of first object. |
| 191 | * @tparam _T2 Type of second object. |
| 192 | */ |
| 193 | template<typename _T1, typename _T2> |
| 194 | struct pair |
| 195 | { |
| 196 | typedef _T1 first_type; /// @c first_type is the first bound type |
| 197 | typedef _T2 second_type; /// @c second_type is the second bound type |
| 198 | |
| 199 | _T1 first; /// @c first is a copy of the first object |
| 200 | _T2 second; /// @c second is a copy of the second object |
| 201 | |
| 202 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| 203 | // 265. std::pair::pair() effects overly restrictive |
| 204 | /** The default constructor creates @c first and @c second using their |
| 205 | * respective default constructors. */ |
| 206 | #if __cplusplus201103L >= 201103L |
| 207 | template <typename _U1 = _T1, |
| 208 | typename _U2 = _T2, |
| 209 | typename enable_if<__and_< |
| 210 | __is_implicitly_default_constructible<_U1>, |
| 211 | __is_implicitly_default_constructible<_U2>> |
| 212 | ::value, bool>::type = true> |
| 213 | #endif |
| 214 | _GLIBCXX_CONSTEXPRconstexpr pair() |
| 215 | : first(), second() { } |
| 216 | |
| 217 | #if __cplusplus201103L >= 201103L |
| 218 | template <typename _U1 = _T1, |
| 219 | typename _U2 = _T2, |
| 220 | typename enable_if<__and_< |
| 221 | is_default_constructible<_U1>, |
| 222 | is_default_constructible<_U2>, |
| 223 | __not_< |
| 224 | __and_<__is_implicitly_default_constructible<_U1>, |
| 225 | __is_implicitly_default_constructible<_U2>>>> |
| 226 | ::value, bool>::type = false> |
| 227 | explicit constexpr pair() |
| 228 | : first(), second() { } |
| 229 | #endif |
| 230 | |
| 231 | /** Two objects may be passed to a @c pair constructor to be copied. */ |
| 232 | #if __cplusplus201103L < 201103L |
| 233 | pair(const _T1& __a, const _T2& __b) |
| 234 | : first(__a), second(__b) { } |
| 235 | #else |
| 236 | // Shortcut for constraining the templates that don't take pairs. |
| 237 | using _PCCP = _PCC<true, _T1, _T2>; |
| 238 | |
| 239 | template<typename _U1 = _T1, typename _U2=_T2, typename |
| 240 | enable_if<_PCCP::template |
| 241 | _ConstructiblePair<_U1, _U2>() |
| 242 | && _PCCP::template |
| 243 | _ImplicitlyConvertiblePair<_U1, _U2>(), |
| 244 | bool>::type=true> |
| 245 | constexpr pair(const _T1& __a, const _T2& __b) |
| 246 | : first(__a), second(__b) { } |
| 247 | |
| 248 | template<typename _U1 = _T1, typename _U2=_T2, typename |
| 249 | enable_if<_PCCP::template |
| 250 | _ConstructiblePair<_U1, _U2>() |
| 251 | && !_PCCP::template |
| 252 | _ImplicitlyConvertiblePair<_U1, _U2>(), |
| 253 | bool>::type=false> |
| 254 | explicit constexpr pair(const _T1& __a, const _T2& __b) |
| 255 | : first(__a), second(__b) { } |
| 256 | #endif |
| 257 | |
| 258 | /** There is also a templated copy ctor for the @c pair class itself. */ |
| 259 | #if __cplusplus201103L < 201103L |
| 260 | template<typename _U1, typename _U2> |
| 261 | pair(const pair<_U1, _U2>& __p) |
| 262 | : first(__p.first), second(__p.second) { } |
| 263 | #else |
| 264 | // Shortcut for constraining the templates that take pairs. |
| 265 | template <typename _U1, typename _U2> |
| 266 | using _PCCFP = _PCC<!is_same<_T1, _U1>::value |
| 267 | || !is_same<_T2, _U2>::value, |
| 268 | _T1, _T2>; |
| 269 | |
| 270 | template<typename _U1, typename _U2, typename |
| 271 | enable_if<_PCCFP<_U1, _U2>::template |
| 272 | _ConstructiblePair<_U1, _U2>() |
| 273 | && _PCCFP<_U1, _U2>::template |
| 274 | _ImplicitlyConvertiblePair<_U1, _U2>(), |
| 275 | bool>::type=true> |
| 276 | constexpr pair(const pair<_U1, _U2>& __p) |
| 277 | : first(__p.first), second(__p.second) { } |
| 278 | |
| 279 | template<typename _U1, typename _U2, typename |
| 280 | enable_if<_PCCFP<_U1, _U2>::template |
| 281 | _ConstructiblePair<_U1, _U2>() |
| 282 | && !_PCCFP<_U1, _U2>::template |
| 283 | _ImplicitlyConvertiblePair<_U1, _U2>(), |
| 284 | bool>::type=false> |
| 285 | explicit constexpr pair(const pair<_U1, _U2>& __p) |
| 286 | : first(__p.first), second(__p.second) { } |
| 287 | |
| 288 | constexpr pair(const pair&) = default; |
| 289 | constexpr pair(pair&&) = default; |
| 290 | |
| 291 | // DR 811. |
| 292 | template<typename _U1, typename |
| 293 | enable_if<_PCCP::template |
| 294 | _MoveCopyPair<true, _U1, _T2>(), |
| 295 | bool>::type=true> |
| 296 | constexpr pair(_U1&& __x, const _T2& __y) |
| 297 | : first(std::forward<_U1>(__x)), second(__y) { } |
| 298 | |
| 299 | template<typename _U1, typename |
| 300 | enable_if<_PCCP::template |
| 301 | _MoveCopyPair<false, _U1, _T2>(), |
| 302 | bool>::type=false> |
| 303 | explicit constexpr pair(_U1&& __x, const _T2& __y) |
| 304 | : first(std::forward<_U1>(__x)), second(__y) { } |
| 305 | |
| 306 | template<typename _U2, typename |
| 307 | enable_if<_PCCP::template |
| 308 | _CopyMovePair<true, _T1, _U2>(), |
| 309 | bool>::type=true> |
| 310 | constexpr pair(const _T1& __x, _U2&& __y) |
| 311 | : first(__x), second(std::forward<_U2>(__y)) { } |
| 312 | |
| 313 | template<typename _U2, typename |
| 314 | enable_if<_PCCP::template |
| 315 | _CopyMovePair<false, _T1, _U2>(), |
| 316 | bool>::type=false> |
| 317 | explicit pair(const _T1& __x, _U2&& __y) |
| 318 | : first(__x), second(std::forward<_U2>(__y)) { } |
| 319 | |
| 320 | template<typename _U1, typename _U2, typename |
| 321 | enable_if<_PCCP::template |
| 322 | _MoveConstructiblePair<_U1, _U2>() |
| 323 | && _PCCP::template |
| 324 | _ImplicitlyMoveConvertiblePair<_U1, _U2>(), |
| 325 | bool>::type=true> |
| 326 | constexpr pair(_U1&& __x, _U2&& __y) |
| 327 | : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { } |
| 328 | |
| 329 | template<typename _U1, typename _U2, typename |
| 330 | enable_if<_PCCP::template |
| 331 | _MoveConstructiblePair<_U1, _U2>() |
| 332 | && !_PCCP::template |
| 333 | _ImplicitlyMoveConvertiblePair<_U1, _U2>(), |
| 334 | bool>::type=false> |
| 335 | explicit constexpr pair(_U1&& __x, _U2&& __y) |
| 336 | : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { } |
| 337 | |
| 338 | |
| 339 | template<typename _U1, typename _U2, typename |
| 340 | enable_if<_PCCFP<_U1, _U2>::template |
| 341 | _MoveConstructiblePair<_U1, _U2>() |
| 342 | && _PCCFP<_U1, _U2>::template |
| 343 | _ImplicitlyMoveConvertiblePair<_U1, _U2>(), |
| 344 | bool>::type=true> |
| 345 | constexpr pair(pair<_U1, _U2>&& __p) |
| 346 | : first(std::forward<_U1>(__p.first)), |
| 347 | second(std::forward<_U2>(__p.second)) { } |
| 348 | |
| 349 | template<typename _U1, typename _U2, typename |
| 350 | enable_if<_PCCFP<_U1, _U2>::template |
| 351 | _MoveConstructiblePair<_U1, _U2>() |
| 352 | && !_PCCFP<_U1, _U2>::template |
| 353 | _ImplicitlyMoveConvertiblePair<_U1, _U2>(), |
| 354 | bool>::type=false> |
| 355 | explicit constexpr pair(pair<_U1, _U2>&& __p) |
| 356 | : first(std::forward<_U1>(__p.first)), |
| 357 | second(std::forward<_U2>(__p.second)) { } |
| 358 | |
| 359 | template<typename... _Args1, typename... _Args2> |
| 360 | pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>); |
| 361 | |
| 362 | pair& |
| 363 | operator=(typename conditional< |
| 364 | __and_<is_copy_assignable<_T1>, |
| 365 | is_copy_assignable<_T2>>::value, |
| 366 | const pair&, const __wrap_nonesuch&>::type __p) |
| 367 | { |
| 368 | first = __p.first; |
| 369 | second = __p.second; |
| 370 | return *this; |
| 371 | } |
| 372 | |
| 373 | pair& |
| 374 | operator=(typename conditional< |
| 375 | __not_<__and_<is_copy_assignable<_T1>, |
| 376 | is_copy_assignable<_T2>>>::value, |
| 377 | const pair&, const __wrap_nonesuch&>::type __p) = delete; |
| 378 | |
| 379 | pair& |
| 380 | operator=(typename conditional< |
| 381 | __and_<is_move_assignable<_T1>, |
| 382 | is_move_assignable<_T2>>::value, |
| 383 | pair&&, __wrap_nonesuch&&>::type __p) |
| 384 | noexcept(__and_<is_nothrow_move_assignable<_T1>, |
| 385 | is_nothrow_move_assignable<_T2>>::value) |
| 386 | { |
| 387 | first = std::forward<first_type>(__p.first); |
| 388 | second = std::forward<second_type>(__p.second); |
| 389 | return *this; |
| 390 | } |
| 391 | |
| 392 | template<typename _U1, typename _U2> |
| 393 | typename enable_if<__and_<is_assignable<_T1&, const _U1&>, |
| 394 | is_assignable<_T2&, const _U2&>>::value, |
| 395 | pair&>::type |
| 396 | operator=(const pair<_U1, _U2>& __p) |
| 397 | { |
| 398 | first = __p.first; |
| 399 | second = __p.second; |
| 400 | return *this; |
| 401 | } |
| 402 | |
| 403 | template<typename _U1, typename _U2> |
| 404 | typename enable_if<__and_<is_assignable<_T1&, _U1&&>, |
| 405 | is_assignable<_T2&, _U2&&>>::value, |
| 406 | pair&>::type |
| 407 | operator=(pair<_U1, _U2>&& __p) |
| 408 | { |
| 409 | first = std::forward<_U1>(__p.first); |
| 410 | second = std::forward<_U2>(__p.second); |
| 411 | return *this; |
| 412 | } |
| 413 | |
| 414 | void |
| 415 | swap(pair& __p) |
| 416 | noexcept(__is_nothrow_swappable<_T1>::value |
| 417 | && __is_nothrow_swappable<_T2>::value) |
| 418 | { |
| 419 | using std::swap; |
| 420 | swap(first, __p.first); |
| 421 | swap(second, __p.second); |
| 422 | } |
| 423 | |
| 424 | private: |
| 425 | template<typename... _Args1, std::size_t... _Indexes1, |
| 426 | typename... _Args2, std::size_t... _Indexes2> |
| 427 | pair(tuple<_Args1...>&, tuple<_Args2...>&, |
| 428 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>); |
| 429 | #endif |
| 430 | }; |
| 431 | |
| 432 | /// Two pairs of the same type are equal iff their members are equal. |
| 433 | template<typename _T1, typename _T2> |
| 434 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
| 435 | operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
| 436 | { return __x.first == __y.first && __x.second == __y.second; } |
| 437 | |
| 438 | /// <http://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html> |
| 439 | template<typename _T1, typename _T2> |
| 440 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
| 441 | operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
| 442 | { return __x.first < __y.first |
| 443 | || (!(__y.first < __x.first) && __x.second < __y.second); } |
| 444 | |
| 445 | /// Uses @c operator== to find the result. |
| 446 | template<typename _T1, typename _T2> |
| 447 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
| 448 | operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
| 449 | { return !(__x == __y); } |
| 450 | |
| 451 | /// Uses @c operator< to find the result. |
| 452 | template<typename _T1, typename _T2> |
| 453 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
| 454 | operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
| 455 | { return __y < __x; } |
| 456 | |
| 457 | /// Uses @c operator< to find the result. |
| 458 | template<typename _T1, typename _T2> |
| 459 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
| 460 | operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
| 461 | { return !(__y < __x); } |
| 462 | |
| 463 | /// Uses @c operator< to find the result. |
| 464 | template<typename _T1, typename _T2> |
| 465 | inline _GLIBCXX_CONSTEXPRconstexpr bool |
| 466 | operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) |
| 467 | { return !(__x < __y); } |
| 468 | |
| 469 | #if __cplusplus201103L >= 201103L |
| 470 | /// See std::pair::swap(). |
| 471 | // Note: no std::swap overloads in C++03 mode, this has performance |
| 472 | // implications, see, eg, libstdc++/38466. |
| 473 | template<typename _T1, typename _T2> |
| 474 | inline void |
| 475 | swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y) |
| 476 | noexcept(noexcept(__x.swap(__y))) |
| 477 | { __x.swap(__y); } |
| 478 | #endif |
| 479 | |
| 480 | /** |
| 481 | * @brief A convenience wrapper for creating a pair from two objects. |
| 482 | * @param __x The first object. |
| 483 | * @param __y The second object. |
| 484 | * @return A newly-constructed pair<> object of the appropriate type. |
| 485 | * |
| 486 | * The standard requires that the objects be passed by reference-to-const, |
| 487 | * but LWG issue #181 says they should be passed by const value. We follow |
| 488 | * the LWG by default. |
| 489 | */ |
| 490 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| 491 | // 181. make_pair() unintended behavior |
| 492 | #if __cplusplus201103L >= 201103L |
| 493 | // NB: DR 706. |
| 494 | template<typename _T1, typename _T2> |
| 495 | constexpr pair<typename __decay_and_strip<_T1>::__type, |
| 496 | typename __decay_and_strip<_T2>::__type> |
| 497 | make_pair(_T1&& __x, _T2&& __y) |
| 498 | { |
| 499 | typedef typename __decay_and_strip<_T1>::__type __ds_type1; |
| 500 | typedef typename __decay_and_strip<_T2>::__type __ds_type2; |
| 501 | typedef pair<__ds_type1, __ds_type2> __pair_type; |
| 502 | return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y)); |
| 503 | } |
| 504 | #else |
| 505 | template<typename _T1, typename _T2> |
| 506 | inline pair<_T1, _T2> |
| 507 | make_pair(_T1 __x, _T2 __y) |
| 508 | { return pair<_T1, _T2>(__x, __y); } |
| 509 | #endif |
| 510 | |
| 511 | /// @} |
| 512 | |
| 513 | _GLIBCXX_END_NAMESPACE_VERSION |
| 514 | } // namespace std |
| 515 | |
| 516 | #endif /* _STL_PAIR_H */ |