bolt/lib/Core/DIEBuilder.cpp

   1 //===- bolt/Core/DIEBuilder.cpp -------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "bolt/Core/DIEBuilder.h"
  10 #include "bolt/Core/BinaryContext.h"
  11 #include "bolt/Core/ParallelUtilities.h"
  12 #include "llvm/ADT/StringRef.h"
  13 #include "llvm/BinaryFormat/Dwarf.h"
  14 #include "llvm/CodeGen/DIE.h"
  15 #include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
  16 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
  17 #include "llvm/DebugInfo/DWARF/DWARFExpression.h"
  18 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
  19 #include "llvm/DebugInfo/DWARF/DWARFTypeUnit.h"
  20 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
  21 #include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"
  22 #include "llvm/ObjectYAML/DWARFYAML.h"
  23 #include "llvm/Support/Casting.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include "llvm/Support/Format.h"
  27 #include "llvm/Support/LEB128.h"
  28 #include "llvm/Support/ThreadPool.h"
  29 #include "llvm/Support/YAMLTraits.h"
  30
  31 #include <algorithm>
  32 #include <cstdint>
  33 #include <memory>
  34 #include <mutex>
  35 #include <string>
  36 #include <unordered_map>
  37 #include <utility>
  38 #include <vector>
  39
  40 #undef DEBUG_TYPE
  41 #define DEBUG_TYPE "bolt"
  42 namespace opts {
  43 extern cl::opt<unsigned> Verbosity;
  44 }
  45 namespace llvm {
  46 namespace bolt {
  47
  48 void DIEBuilder::updateReferences() {
  49   for (auto &[SrcDIEInfo, ReferenceInfo] : getState().AddrReferences) {
  50     DIEInfo *DstDIEInfo = ReferenceInfo.Dst;
  51     DWARFUnitInfo &DstUnitInfo = getUnitInfo(DstDIEInfo->UnitId);
  52     dwarf::Attribute Attr = ReferenceInfo.AttrSpec.Attr;
  53     dwarf::Form Form = ReferenceInfo.AttrSpec.Form;
  54
  55     const uint64_t NewAddr =
  56         DstDIEInfo->Die->getOffset() + DstUnitInfo.UnitOffset;
  57     SrcDIEInfo->Die->replaceValue(getState().DIEAlloc, Attr, Form,
  58                                   DIEInteger(NewAddr));
  59   }
  60
  61   // Handling referenes in location expressions.
  62   for (LocWithReference &LocExpr : getState().LocWithReferencesToProcess) {
  63     SmallVector<uint8_t, 32> Buffer;
  64     DataExtractor Data(StringRef((const char *)LocExpr.BlockData.data(),
  65                                  LocExpr.BlockData.size()),
  66                        LocExpr.U.isLittleEndian(),
  67                        LocExpr.U.getAddressByteSize());
  68     DWARFExpression Expr(Data, LocExpr.U.getAddressByteSize(),
  69                          LocExpr.U.getFormParams().Format);
  70     cloneExpression(Data, Expr, LocExpr.U, Buffer, CloneExpressionStage::PATCH);
  71
  72     DIEValueList *AttrVal;
  73     if (LocExpr.Form == dwarf::DW_FORM_exprloc) {
  74       DIELoc *DL = new (getState().DIEAlloc) DIELoc;
  75       DL->setSize(Buffer.size());
  76       AttrVal = static_cast<DIEValueList *>(DL);
  77     } else {
  78       DIEBlock *DBL = new (getState().DIEAlloc) DIEBlock;
  79       DBL->setSize(Buffer.size());
  80       AttrVal = static_cast<DIEValueList *>(DBL);
  81     }
  82     for (auto Byte : Buffer)
  83       AttrVal->addValue(getState().DIEAlloc, static_cast<dwarf::Attribute>(0),
  84                         dwarf::DW_FORM_data1, DIEInteger(Byte));
  85
  86     DIEValue Value;
  87     if (LocExpr.Form == dwarf::DW_FORM_exprloc)
  88       Value =
  89           DIEValue(dwarf::Attribute(LocExpr.Attr), dwarf::Form(LocExpr.Form),
  90                    static_cast<DIELoc *>(AttrVal));
  91     else
  92       Value =
  93           DIEValue(dwarf::Attribute(LocExpr.Attr), dwarf::Form(LocExpr.Form),
  94                    static_cast<DIEBlock *>(AttrVal));
  95
  96     LocExpr.Die.replaceValue(getState().DIEAlloc, LocExpr.Attr, LocExpr.Form,
  97                              Value);
  98   }
  99
 100   return;
 101 }
 102
 103 uint32_t DIEBuilder::allocDIE(const DWARFUnit &DU, const DWARFDie &DDie,
 104                               BumpPtrAllocator &Alloc, const uint32_t UId) {
 105   DWARFUnitInfo &DWARFUnitInfo = getUnitInfo(UId);
 106   const uint64_t DDieOffset = DDie.getOffset();
 107   if (DWARFUnitInfo.DIEIDMap.count(DDieOffset))
 108     return DWARFUnitInfo.DIEIDMap[DDieOffset];
 109
 110   DIE *Die = DIE::get(Alloc, dwarf::Tag(DDie.getTag()));
 111   // This handles the case where there is a DIE ref which points to
 112   // invalid DIE. This prevents assert when IR is written out.
 113   // Also it makes debugging easier.
 114   // DIE dump is not very useful.
 115   // It's nice to know original offset from which this DIE was constructed.
 116   Die->setOffset(DDie.getOffset());
 117   if (opts::Verbosity >= 1)
 118     getState().DWARFDieAddressesParsed.insert(DDie.getOffset());
 119   const uint32_t DId = DWARFUnitInfo.DieInfoVector.size();
 120   DWARFUnitInfo.DIEIDMap[DDieOffset] = DId;
 121   DWARFUnitInfo.DieInfoVector.emplace_back(
 122       std::make_unique<DIEInfo>(DIEInfo{Die, DId, UId}));
 123   return DId;
 124 }
 125
 126 void DIEBuilder::constructFromUnit(DWARFUnit &DU) {
 127   std::optional<uint32_t> UnitId = getUnitId(DU);
 128   if (!UnitId) {
 129     errs() << "BOLT-WARNING: [internal-dwarf-error]: "
 130            << "Skip Unit at " << Twine::utohexstr(DU.getOffset()) << "\n";
 131     return;
 132   }
 133
 134   const uint32_t UnitHeaderSize = DU.getHeaderSize();
 135   uint64_t DIEOffset = DU.getOffset() + UnitHeaderSize;
 136   uint64_t NextCUOffset = DU.getNextUnitOffset();
 137   DWARFDataExtractor DebugInfoData = DU.getDebugInfoExtractor();
 138   DWARFDebugInfoEntry DIEEntry;
 139   std::vector<DIE *> CurParentDIEStack;
 140   std::vector<uint32_t> Parents;
 141   uint32_t TUTypeOffset = 0;
 142
 143   if (DWARFTypeUnit *TU = dyn_cast_or_null<DWARFTypeUnit>(&DU))
 144     TUTypeOffset = TU->getTypeOffset();
 145
 146   assert(DebugInfoData.isValidOffset(NextCUOffset - 1));
 147   Parents.push_back(UINT32_MAX);
 148   do {
 149     const bool IsTypeDIE = (TUTypeOffset == DIEOffset - DU.getOffset());
 150     if (!DIEEntry.extractFast(DU, &DIEOffset, DebugInfoData, NextCUOffset,
 151                               Parents.back()))
 152       break;
 153
 154     if (const DWARFAbbreviationDeclaration *AbbrDecl =
 155             DIEEntry.getAbbreviationDeclarationPtr()) {
 156       DWARFDie DDie(&DU, &DIEEntry);
 157
 158       DIE *CurDIE = constructDIEFast(DDie, DU, *UnitId);
 159       DWARFUnitInfo &UI = getUnitInfo(*UnitId);
 160       // Can't rely on first element in DieVector due to cross CU forward
 161       // references.
 162       if (!UI.UnitDie)
 163         UI.UnitDie = CurDIE;
 164       if (IsTypeDIE)
 165         getState().TypeDIEMap[&DU] = CurDIE;
 166
 167       if (!CurParentDIEStack.empty())
 168         CurParentDIEStack.back()->addChild(CurDIE);
 169
 170       if (AbbrDecl->hasChildren())
 171         CurParentDIEStack.push_back(CurDIE);
 172     } else {
 173       // NULL DIE: finishes current children scope.
 174       CurParentDIEStack.pop_back();
 175     }
 176   } while (CurParentDIEStack.size() > 0);
 177
 178   getState().CloneUnitCtxMap[*UnitId].IsConstructed = true;
 179 }
 180
 181 DIEBuilder::DIEBuilder(DWARFContext *DwarfContext, bool IsDWO)
 182     : DwarfContext(DwarfContext), IsDWO(IsDWO) {}
 183
 184 static unsigned int getCUNum(DWARFContext *DwarfContext, bool IsDWO) {
 185   unsigned int CUNum = IsDWO ? DwarfContext->getNumDWOCompileUnits()
 186                              : DwarfContext->getNumCompileUnits();
 187   CUNum += IsDWO ? DwarfContext->getNumDWOTypeUnits()
 188                  : DwarfContext->getNumTypeUnits();
 189   return CUNum;
 190 }
 191
 192 void DIEBuilder::buildTypeUnits(DebugStrOffsetsWriter *StrOffsetWriter,
 193                                 const bool Init) {
 194   if (Init)
 195     BuilderState.reset(new State());
 196
 197   const DWARFUnitIndex &TUIndex = DwarfContext->getTUIndex();
 198   if (!TUIndex.getRows().empty()) {
 199     for (auto &Row : TUIndex.getRows()) {
 200       uint64_t Signature = Row.getSignature();
 201       // manually populate TypeUnit to UnitVector
 202       DwarfContext->getTypeUnitForHash(DwarfContext->getMaxVersion(), Signature,
 203                                        true);
 204     }
 205   }
 206   const unsigned int CUNum = getCUNum(DwarfContext, IsDWO);
 207   getState().CloneUnitCtxMap.resize(CUNum);
 208   DWARFContext::unit_iterator_range CU4TURanges =
 209       IsDWO ? DwarfContext->dwo_types_section_units()
 210             : DwarfContext->types_section_units();
 211
 212   getState().Type = ProcessingType::DWARF4TUs;
 213   for (std::unique_ptr<DWARFUnit> &DU : CU4TURanges)
 214     registerUnit(*DU.get(), false);
 215
 216   for (std::unique_ptr<DWARFUnit> &DU : CU4TURanges)
 217     constructFromUnit(*DU.get());
 218
 219   DWARFContext::unit_iterator_range CURanges =
 220       IsDWO ? DwarfContext->dwo_info_section_units()
 221             : DwarfContext->info_section_units();
 222
 223   // This handles DWARF4 CUs and DWARF5 CU/TUs.
 224   // Creating a vector so that for reference handling only DWARF5 CU/TUs are
 225   // used, and not DWARF4 TUs.
 226   getState().Type = ProcessingType::DWARF5TUs;
 227   for (std::unique_ptr<DWARFUnit> &DU : CURanges) {
 228     if (!DU->isTypeUnit())
 229       continue;
 230     registerUnit(*DU.get(), false);
 231   }
 232
 233   for (DWARFUnit *DU : getState().DWARF5TUVector) {
 234     constructFromUnit(*DU);
 235     if (StrOffsetWriter)
 236       StrOffsetWriter->finalizeSection(*DU, *this);
 237   }
 238 }
 239
 240 void DIEBuilder::buildCompileUnits(const bool Init) {
 241   if (Init)
 242     BuilderState.reset(new State());
 243
 244   unsigned int CUNum = getCUNum(DwarfContext, IsDWO);
 245   getState().CloneUnitCtxMap.resize(CUNum);
 246   DWARFContext::unit_iterator_range CURanges =
 247       IsDWO ? DwarfContext->dwo_info_section_units()
 248             : DwarfContext->info_section_units();
 249
 250   // This handles DWARF4 CUs and DWARF5 CU/TUs.
 251   // Creating a vector so that for reference handling only DWARF5 CU/TUs are
 252   // used, and not DWARF4 TUs.getState().DUList
 253   getState().Type = ProcessingType::CUs;
 254   for (std::unique_ptr<DWARFUnit> &DU : CURanges) {
 255     if (DU->isTypeUnit())
 256       continue;
 257     registerUnit(*DU.get(), false);
 258   }
 259
 260   // Using DULIst since it can be modified by cross CU refrence resolution.
 261   for (DWARFUnit *DU : getState().DUList) {
 262     if (DU->isTypeUnit())
 263       continue;
 264     constructFromUnit(*DU);
 265   }
 266 }
 267 void DIEBuilder::buildCompileUnits(const std::vector<DWARFUnit *> &CUs) {
 268   BuilderState.reset(new State());
 269   // Allocating enough for current batch being processed.
 270   // In real use cases we either processing a batch of CUs with no cross
 271   // references, or if they do have them it is due to LTO. With clang they will
 272   // share the same abbrev table. In either case this vector will not grow.
 273   getState().CloneUnitCtxMap.resize(CUs.size());
 274   getState().Type = ProcessingType::CUs;
 275   for (DWARFUnit *CU : CUs)
 276     registerUnit(*CU, false);
 277
 278   for (DWARFUnit *DU : getState().DUList)
 279     constructFromUnit(*DU);
 280 }
 281
 282 void DIEBuilder::buildDWOUnit(DWARFUnit &U) {
 283   BuilderState.release();
 284   BuilderState = std::make_unique<State>();
 285   buildTypeUnits(nullptr, false);
 286   getState().Type = ProcessingType::CUs;
 287   registerUnit(U, false);
 288   constructFromUnit(U);
 289 }
 290
 291 DIE *DIEBuilder::constructDIEFast(DWARFDie &DDie, DWARFUnit &U,
 292                                   uint32_t UnitId) {
 293
 294   std::optional<uint32_t> Idx = getAllocDIEId(U, DDie);
 295   if (Idx) {
 296     DWARFUnitInfo &DWARFUnitInfo = getUnitInfo(UnitId);
 297     DIEInfo &DieInfo = getDIEInfo(UnitId, *Idx);
 298     if (DWARFUnitInfo.IsConstructed && DieInfo.Die)
 299       return DieInfo.Die;
 300   } else {
 301     Idx = allocDIE(U, DDie, getState().DIEAlloc, UnitId);
 302   }
 303
 304   DIEInfo &DieInfo = getDIEInfo(UnitId, *Idx);
 305
 306   uint64_t Offset = DDie.getOffset();
 307   uint64_t NextOffset = Offset;
 308   DWARFDataExtractor Data = U.getDebugInfoExtractor();
 309   DWARFDebugInfoEntry DDIEntry;
 310
 311   if (DDIEntry.extractFast(U, &NextOffset, Data, U.getNextUnitOffset(), 0))
 312     assert(NextOffset - U.getOffset() <= Data.getData().size() &&
 313            "NextOffset OOB");
 314
 315   SmallString<40> DIECopy(Data.getData().substr(Offset, NextOffset - Offset));
 316   Data =
 317       DWARFDataExtractor(DIECopy, Data.isLittleEndian(), Data.getAddressSize());
 318
 319   const DWARFAbbreviationDeclaration *Abbrev =
 320       DDie.getAbbreviationDeclarationPtr();
 321   uint64_t AttrOffset = getULEB128Size(Abbrev->getCode());
 322
 323   using AttrSpec = DWARFAbbreviationDeclaration::AttributeSpec;
 324   for (const AttrSpec &AttrSpec : Abbrev->attributes()) {
 325     DWARFFormValue Val(AttrSpec.Form);
 326     Val.extractValue(Data, &AttrOffset, U.getFormParams(), &U);
 327     cloneAttribute(*DieInfo.Die, DDie, U, Val, AttrSpec);
 328   }
 329   return DieInfo.Die;
 330 }
 331
 332 static DWARFUnit *
 333 getUnitForOffset(DIEBuilder &Builder, DWARFContext &DWCtx,
 334                  const uint64_t Offset,
 335                  const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
 336   auto findUnit = [&](std::vector<DWARFUnit *> &Units) -> DWARFUnit * {
 337     auto CUIter = llvm::upper_bound(Units, Offset,
 338                                     [](uint64_t LHS, const DWARFUnit *RHS) {
 339                                       return LHS < RHS->getNextUnitOffset();
 340                                     });
 341     static std::vector<DWARFUnit *> CUOffsets;
 342     static std::once_flag InitVectorFlag;
 343     auto initCUVector = [&]() {
 344       CUOffsets.reserve(DWCtx.getNumCompileUnits());
 345       for (const std::unique_ptr<DWARFUnit> &CU : DWCtx.compile_units())
 346         CUOffsets.emplace_back(CU.get());
 347     };
 348     DWARFUnit *CU = CUIter != Units.end() ? *CUIter : nullptr;
 349     // Above algorithm breaks when there is only one CU, and reference is
 350     // outside of it. Fall through slower path, that searches all the CUs.
 351     // For example when src and destination of cross CU references have
 352     // different abbrev section.
 353     if (!CU ||
 354         (CU && AttrSpec.Form == dwarf::DW_FORM_ref_addr &&
 355          !(CU->getOffset() < Offset && CU->getNextUnitOffset() > Offset))) {
 356       // This is a work around for XCode clang. There is a build error when we
 357       // pass DWCtx.compile_units() to llvm::upper_bound
 358       std::call_once(InitVectorFlag, initCUVector);
 359       auto CUIter = std::upper_bound(CUOffsets.begin(), CUOffsets.end(), Offset,
 360                                      [](uint64_t LHS, const DWARFUnit *RHS) {
 361                                        return LHS < RHS->getNextUnitOffset();
 362                                      });
 363       CU = CUIter != CUOffsets.end() ? (*CUIter) : nullptr;
 364     }
 365     return CU;
 366   };
 367
 368   switch (Builder.getCurrentProcessingState()) {
 369   case DIEBuilder::ProcessingType::DWARF4TUs:
 370     return findUnit(Builder.getDWARF4TUVector());
 371   case DIEBuilder::ProcessingType::DWARF5TUs:
 372     return findUnit(Builder.getDWARF5TUVector());
 373   case DIEBuilder::ProcessingType::CUs:
 374     return findUnit(Builder.getDWARFCUVector());
 375   };
 376
 377   return nullptr;
 378 }
 379
 380 uint32_t DIEBuilder::computeDIEOffset(const DWARFUnit &CU, DIE &Die,
 381                                       uint32_t &CurOffset) {
 382   getState().DWARFDieAddressesParsed.erase(Die.getOffset());
 383   uint32_t CurSize = 0;
 384   Die.setOffset(CurOffset);
 385   for (DIEValue &Val : Die.values())
 386     CurSize += Val.sizeOf(CU.getFormParams());
 387   CurSize += getULEB128Size(Die.getAbbrevNumber());
 388   CurOffset += CurSize;
 389
 390   for (DIE &Child : Die.children()) {
 391     uint32_t ChildSize = computeDIEOffset(CU, Child, CurOffset);
 392     CurSize += ChildSize;
 393   }
 394   // for children end mark.
 395   if (Die.hasChildren()) {
 396     CurSize += sizeof(uint8_t);
 397     CurOffset += sizeof(uint8_t);
 398   }
 399
 400   Die.setSize(CurSize);
 401
 402   return CurSize;
 403 }
 404
 405 void DIEBuilder::finish() {
 406   auto computeOffset = [&](const DWARFUnit &CU,
 407                            uint64_t &UnitStartOffset) -> void {
 408     DIE *UnitDIE = getUnitDIEbyUnit(CU);
 409     uint32_t HeaderSize = CU.getHeaderSize();
 410     uint32_t CurOffset = HeaderSize;
 411     computeDIEOffset(CU, *UnitDIE, CurOffset);
 412
 413     DWARFUnitInfo &CurUnitInfo = getUnitInfoByDwarfUnit(CU);
 414     CurUnitInfo.UnitOffset = UnitStartOffset;
 415     CurUnitInfo.UnitLength = HeaderSize + UnitDIE->getSize();
 416     UnitStartOffset += CurUnitInfo.UnitLength;
 417   };
 418   // Computing offsets for .debug_types section.
 419   // It's processed first when CU is registered so will be at the begginnig of
 420   // the vector.
 421   uint64_t TypeUnitStartOffset = 0;
 422   for (const DWARFUnit *CU : getState().DUList) {
 423     // We process DWARF$ types first.
 424     if (!(CU->getVersion() < 5 && CU->isTypeUnit()))
 425       break;
 426     computeOffset(*CU, TypeUnitStartOffset);
 427   }
 428
 429   for (const DWARFUnit *CU : getState().DUList) {
 430     // Skipping DWARF4 types.
 431     if (CU->getVersion() < 5 && CU->isTypeUnit())
 432       continue;
 433     computeOffset(*CU, UnitSize);
 434   }
 435   if (opts::Verbosity >= 1) {
 436     if (!getState().DWARFDieAddressesParsed.empty())
 437       dbgs() << "Referenced DIE offsets not in .debug_info\n";
 438     for (const uint64_t Address : getState().DWARFDieAddressesParsed) {
 439       dbgs() << Twine::utohexstr(Address) << "\n";
 440     }
 441   }
 442   updateReferences();
 443 }
 444
 445 DWARFDie DIEBuilder::resolveDIEReference(
 446     const DWARFFormValue &RefValue,
 447     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 448     DWARFUnit *&RefCU, DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
 449   assert(RefValue.isFormClass(DWARFFormValue::FC_Reference));
 450   uint64_t RefOffset = *RefValue.getAsReference();
 451   return resolveDIEReference(AttrSpec, RefOffset, RefCU, DwarfDebugInfoEntry);
 452 }
 453
 454 DWARFDie DIEBuilder::resolveDIEReference(
 455     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 456     const uint64_t RefOffset, DWARFUnit *&RefCU,
 457     DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
 458   uint64_t TmpRefOffset = RefOffset;
 459   if ((RefCU =
 460            getUnitForOffset(*this, *DwarfContext, TmpRefOffset, AttrSpec))) {
 461     /// Trying to add to current working set in case it's cross CU reference.
 462     registerUnit(*RefCU, true);
 463     DWARFDataExtractor DebugInfoData = RefCU->getDebugInfoExtractor();
 464     if (DwarfDebugInfoEntry.extractFast(*RefCU, &TmpRefOffset, DebugInfoData,
 465                                         RefCU->getNextUnitOffset(), 0)) {
 466       // In a file with broken references, an attribute might point to a NULL
 467       // DIE.
 468       DWARFDie RefDie = DWARFDie(RefCU, &DwarfDebugInfoEntry);
 469       if (!RefDie.isNULL()) {
 470         std::optional<uint32_t> UnitId = getUnitId(*RefCU);
 471
 472         // forward reference
 473         if (UnitId && !getState().CloneUnitCtxMap[*UnitId].IsConstructed &&
 474             !getAllocDIEId(*RefCU, RefDie))
 475           allocDIE(*RefCU, RefDie, getState().DIEAlloc, *UnitId);
 476         return RefDie;
 477       }
 478       errs() << "BOLT-WARNING: [internal-dwarf-error]: invalid referenced DIE "
 479                 "at offset: "
 480              << Twine::utohexstr(RefOffset) << ".\n";
 481
 482     } else {
 483       errs() << "BOLT-WARNING: [internal-dwarf-error]: could not parse "
 484                 "referenced DIE at offset: "
 485              << Twine::utohexstr(RefOffset) << ".\n";
 486     }
 487   } else {
 488     errs() << "BOLT-WARNING: [internal-dwarf-error]: could not find referenced "
 489               "CU. Referenced DIE offset: "
 490            << Twine::utohexstr(RefOffset) << ".\n";
 491   }
 492   return DWARFDie();
 493 }
 494
 495 void DIEBuilder::cloneDieReferenceAttribute(
 496     DIE &Die, const DWARFUnit &U, const DWARFDie &InputDIE,
 497     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 498     const DWARFFormValue &Val) {
 499   const uint64_t Ref = *Val.getAsReference();
 500
 501   DIE *NewRefDie = nullptr;
 502   DWARFUnit *RefUnit = nullptr;
 503
 504   DWARFDebugInfoEntry DDIEntry;
 505   const DWARFDie RefDie = resolveDIEReference(Val, AttrSpec, RefUnit, DDIEntry);
 506
 507   if (!RefDie)
 508     return;
 509
 510   const std::optional<uint32_t> UnitId = getUnitId(*RefUnit);
 511   const std::optional<uint32_t> IsAllocId = getAllocDIEId(*RefUnit, RefDie);
 512   assert(IsAllocId.has_value() && "Encountered unexpected unallocated DIE.");
 513   const uint32_t DIEId = *IsAllocId;
 514   DIEInfo &DieInfo = getDIEInfo(*UnitId, DIEId);
 515
 516   if (!DieInfo.Die) {
 517     assert(Ref > InputDIE.getOffset());
 518     (void)Ref;
 519     errs() << "BOLT-WARNING: [internal-dwarf-error]: encounter unexpected "
 520               "unallocated DIE. Should be alloc!\n";
 521     // We haven't cloned this DIE yet. Just create an empty one and
 522     // store it. It'll get really cloned when we process it.
 523     DieInfo.Die = DIE::get(getState().DIEAlloc, dwarf::Tag(RefDie.getTag()));
 524   }
 525   NewRefDie = DieInfo.Die;
 526
 527   if (AttrSpec.Form == dwarf::DW_FORM_ref_addr) {
 528     // no matter forward reference or backward reference, we are supposed
 529     // to calculate them in `finish` due to the possible modification of
 530     // the DIE.
 531     DWARFDie CurDie = const_cast<DWARFDie &>(InputDIE);
 532     DIEInfo *CurDieInfo = &getDIEInfoByDwarfDie(CurDie);
 533     getState().AddrReferences.push_back(
 534         std::make_pair(CurDieInfo, AddrReferenceInfo(&DieInfo, AttrSpec)));
 535
 536     Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_addr,
 537                  DIEInteger(0xDEADBEEF));
 538     return;
 539   }
 540
 541   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 542                DIEEntry(*NewRefDie));
 543 }
 544
 545 void DIEBuilder::cloneStringAttribute(
 546     DIE &Die, const DWARFUnit &U,
 547     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 548     const DWARFFormValue &Val) {
 549   if (AttrSpec.Form == dwarf::DW_FORM_string) {
 550     Expected<const char *> StrAddr = Val.getAsCString();
 551     if (!StrAddr) {
 552       consumeError(StrAddr.takeError());
 553       return;
 554     }
 555     Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_string,
 556                  new (getState().DIEAlloc)
 557                      DIEInlineString(StrAddr.get(), getState().DIEAlloc));
 558   } else {
 559     std::optional<uint64_t> OffsetIndex = Val.getRawUValue();
 560     Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 561                  DIEInteger(*OffsetIndex));
 562   }
 563 }
 564
 565 bool DIEBuilder::cloneExpression(const DataExtractor &Data,
 566                                  const DWARFExpression &Expression,
 567                                  DWARFUnit &U,
 568                                  SmallVectorImpl<uint8_t> &OutputBuffer,
 569                                  const CloneExpressionStage &Stage) {
 570   using Encoding = DWARFExpression::Operation::Encoding;
 571   using Descr = DWARFExpression::Operation::Description;
 572   uint64_t OpOffset = 0;
 573   bool DoesContainReference = false;
 574   for (const DWARFExpression::Operation &Op : Expression) {
 575     const Descr &Description = Op.getDescription();
 576     // DW_OP_const_type is variable-length and has 3
 577     // operands. Thus far we only support 2.
 578     if ((Description.Op.size() == 2 &&
 579          Description.Op[0] == Encoding::BaseTypeRef) ||
 580         (Description.Op.size() == 2 &&
 581          Description.Op[1] == Encoding::BaseTypeRef &&
 582          Description.Op[0] != Encoding::Size1))
 583       outs() << "BOLT-WARNING: [internal-dwarf-error]: unsupported DW_OP "
 584                 "encoding.\n";
 585
 586     if ((Description.Op.size() == 1 &&
 587          Description.Op[0] == Encoding::BaseTypeRef) ||
 588         (Description.Op.size() == 2 &&
 589          Description.Op[1] == Encoding::BaseTypeRef &&
 590          Description.Op[0] == Encoding::Size1)) {
 591       // This code assumes that the other non-typeref operand fits into 1
 592       // byte.
 593       assert(OpOffset < Op.getEndOffset());
 594       const uint32_t ULEBsize = Op.getEndOffset() - OpOffset - 1;
 595       (void)ULEBsize;
 596       assert(ULEBsize <= 16);
 597
 598       // Copy over the operation.
 599       OutputBuffer.push_back(Op.getCode());
 600       uint64_t RefOffset;
 601       if (Description.Op.size() == 1) {
 602         RefOffset = Op.getRawOperand(0);
 603       } else {
 604         OutputBuffer.push_back(Op.getRawOperand(0));
 605         RefOffset = Op.getRawOperand(1);
 606       }
 607       uint32_t Offset = 0;
 608       if (RefOffset > 0 || Op.getCode() != dwarf::DW_OP_convert) {
 609         DoesContainReference = true;
 610         std::optional<uint32_t> RefDieID =
 611             getAllocDIEId(U, U.getOffset() + RefOffset);
 612         std::optional<uint32_t> RefUnitID = getUnitId(U);
 613         if (RefDieID.has_value() && RefUnitID.has_value()) {
 614           DIEInfo &RefDieInfo = getDIEInfo(*RefUnitID, *RefDieID);
 615           if (DIE *Clone = RefDieInfo.Die)
 616             Offset = Stage == CloneExpressionStage::INIT ? RefOffset
 617                                                          : Clone->getOffset();
 618           else
 619             errs() << "BOLT-WARNING: [internal-dwarf-error]: base type ref "
 620                       "doesn't point to "
 621                       "DW_TAG_base_type.\n";
 622         }
 623       }
 624       uint8_t ULEB[16];
 625       // Hard coding to max size so size doesn't change when we update the
 626       // offset.
 627       encodeULEB128(Offset, ULEB, 4);
 628       ArrayRef<uint8_t> ULEBbytes(ULEB, 4);
 629       OutputBuffer.append(ULEBbytes.begin(), ULEBbytes.end());
 630     } else {
 631       // Copy over everything else unmodified.
 632       const StringRef Bytes = Data.getData().slice(OpOffset, Op.getEndOffset());
 633       OutputBuffer.append(Bytes.begin(), Bytes.end());
 634     }
 635     OpOffset = Op.getEndOffset();
 636   }
 637   return DoesContainReference;
 638 }
 639
 640 void DIEBuilder::cloneBlockAttribute(
 641     DIE &Die, DWARFUnit &U,
 642     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 643     const DWARFFormValue &Val) {
 644   DIEValueList *Attr;
 645   DIEValue Value;
 646   DIELoc *Loc = nullptr;
 647   DIEBlock *Block = nullptr;
 648
 649   if (AttrSpec.Form == dwarf::DW_FORM_exprloc) {
 650     Loc = new (getState().DIEAlloc) DIELoc;
 651   } else if (doesFormBelongToClass(AttrSpec.Form, DWARFFormValue::FC_Block,
 652                                    U.getVersion())) {
 653     Block = new (getState().DIEAlloc) DIEBlock;
 654   } else {
 655     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unexpected Form value in "
 656               "cloneBlockAttribute\n";
 657     return;
 658   }
 659   Attr = Loc ? static_cast<DIEValueList *>(Loc)
 660              : static_cast<DIEValueList *>(Block);
 661
 662   SmallVector<uint8_t, 32> Buffer;
 663   ArrayRef<uint8_t> Bytes = *Val.getAsBlock();
 664   if (DWARFAttribute::mayHaveLocationExpr(AttrSpec.Attr) &&
 665       (Val.isFormClass(DWARFFormValue::FC_Block) ||
 666        Val.isFormClass(DWARFFormValue::FC_Exprloc))) {
 667     DataExtractor Data(StringRef((const char *)Bytes.data(), Bytes.size()),
 668                        U.isLittleEndian(), U.getAddressByteSize());
 669     DWARFExpression Expr(Data, U.getAddressByteSize(),
 670                          U.getFormParams().Format);
 671     if (cloneExpression(Data, Expr, U, Buffer, CloneExpressionStage::INIT))
 672       getState().LocWithReferencesToProcess.emplace_back(
 673           Bytes.vec(), U, Die, AttrSpec.Form, AttrSpec.Attr);
 674     Bytes = Buffer;
 675   }
 676   for (auto Byte : Bytes)
 677     Attr->addValue(getState().DIEAlloc, static_cast<dwarf::Attribute>(0),
 678                    dwarf::DW_FORM_data1, DIEInteger(Byte));
 679
 680   if (Loc)
 681     Loc->setSize(Bytes.size());
 682   else
 683     Block->setSize(Bytes.size());
 684
 685   if (Loc)
 686     Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
 687                      dwarf::Form(AttrSpec.Form), Loc);
 688   else
 689     Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
 690                      dwarf::Form(AttrSpec.Form), Block);
 691   Die.addValue(getState().DIEAlloc, Value);
 692 }
 693
 694 void DIEBuilder::cloneAddressAttribute(
 695     DIE &Die, const DWARFUnit &U,
 696     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 697     const DWARFFormValue &Val) {
 698   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 699                DIEInteger(Val.getRawUValue()));
 700 }
 701
 702 void DIEBuilder::cloneRefsigAttribute(
 703     DIE &Die, DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 704     const DWARFFormValue &Val) {
 705   const std::optional<uint64_t> SigVal = Val.getRawUValue();
 706   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_sig8,
 707                DIEInteger(*SigVal));
 708 }
 709
 710 void DIEBuilder::cloneScalarAttribute(
 711     DIE &Die, const DWARFDie &InputDIE,
 712     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 713     const DWARFFormValue &Val) {
 714   uint64_t Value;
 715
 716   if (auto OptionalValue = Val.getAsUnsignedConstant())
 717     Value = *OptionalValue;
 718   else if (auto OptionalValue = Val.getAsSignedConstant())
 719     Value = *OptionalValue;
 720   else if (auto OptionalValue = Val.getAsSectionOffset())
 721     Value = *OptionalValue;
 722   else {
 723     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
 724               "attribute form. Dropping "
 725               "attribute.\n";
 726     return;
 727   }
 728
 729   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 730                DIEInteger(Value));
 731 }
 732
 733 void DIEBuilder::cloneLoclistAttrubute(
 734     DIE &Die, const DWARFDie &InputDIE,
 735     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 736     const DWARFFormValue &Val) {
 737   std::optional<uint64_t> Value = std::nullopt;
 738
 739   if (auto OptionalValue = Val.getAsUnsignedConstant())
 740     Value = OptionalValue;
 741   else if (auto OptionalValue = Val.getAsSignedConstant())
 742     Value = OptionalValue;
 743   else if (auto OptionalValue = Val.getAsSectionOffset())
 744     Value = OptionalValue;
 745   else
 746     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
 747               "attribute form. Dropping "
 748               "attribute.\n";
 749
 750   if (!Value.has_value())
 751     return;
 752
 753   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 754                DIELocList(*Value));
 755 }
 756
 757 void DIEBuilder::cloneAttribute(
 758     DIE &Die, const DWARFDie &InputDIE, DWARFUnit &U, const DWARFFormValue &Val,
 759     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
 760   switch (AttrSpec.Form) {
 761   case dwarf::DW_FORM_strp:
 762   case dwarf::DW_FORM_string:
 763   case dwarf::DW_FORM_strx:
 764   case dwarf::DW_FORM_strx1:
 765   case dwarf::DW_FORM_strx2:
 766   case dwarf::DW_FORM_strx3:
 767   case dwarf::DW_FORM_strx4:
 768   case dwarf::DW_FORM_GNU_str_index:
 769   case dwarf::DW_FORM_line_strp:
 770     cloneStringAttribute(Die, U, AttrSpec, Val);
 771     break;
 772   case dwarf::DW_FORM_ref_addr:
 773   case dwarf::DW_FORM_ref1:
 774   case dwarf::DW_FORM_ref2:
 775   case dwarf::DW_FORM_ref4:
 776   case dwarf::DW_FORM_ref8:
 777     cloneDieReferenceAttribute(Die, U, InputDIE, AttrSpec, Val);
 778     break;
 779   case dwarf::DW_FORM_block:
 780   case dwarf::DW_FORM_block1:
 781   case dwarf::DW_FORM_block2:
 782   case dwarf::DW_FORM_block4:
 783   case dwarf::DW_FORM_exprloc:
 784     cloneBlockAttribute(Die, U, AttrSpec, Val);
 785     break;
 786   case dwarf::DW_FORM_addr:
 787   case dwarf::DW_FORM_addrx:
 788   case dwarf::DW_FORM_GNU_addr_index:
 789     cloneAddressAttribute(Die, U, AttrSpec, Val);
 790     break;
 791   case dwarf::DW_FORM_data1:
 792   case dwarf::DW_FORM_data2:
 793   case dwarf::DW_FORM_data4:
 794   case dwarf::DW_FORM_data8:
 795   case dwarf::DW_FORM_udata:
 796   case dwarf::DW_FORM_sdata:
 797   case dwarf::DW_FORM_sec_offset:
 798   case dwarf::DW_FORM_rnglistx:
 799   case dwarf::DW_FORM_flag:
 800   case dwarf::DW_FORM_flag_present:
 801   case dwarf::DW_FORM_implicit_const:
 802     cloneScalarAttribute(Die, InputDIE, AttrSpec, Val);
 803     break;
 804   case dwarf::DW_FORM_loclistx:
 805     cloneLoclistAttrubute(Die, InputDIE, AttrSpec, Val);
 806     break;
 807   case dwarf::DW_FORM_ref_sig8:
 808     cloneRefsigAttribute(Die, AttrSpec, Val);
 809     break;
 810   default:
 811     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported attribute "
 812               "form " +
 813                   dwarf::FormEncodingString(AttrSpec.Form).str() +
 814                   " in cloneAttribute. Dropping.";
 815   }
 816 }
 817 void DIEBuilder::assignAbbrev(DIEAbbrev &Abbrev) {
 818   // Check the set for priors.
 819   FoldingSetNodeID ID;
 820   Abbrev.Profile(ID);
 821   void *InsertToken;
 822   DIEAbbrev *InSet = AbbreviationsSet.FindNodeOrInsertPos(ID, InsertToken);
 823
 824   // If it's newly added.
 825   if (InSet) {
 826     // Assign existing abbreviation number.
 827     Abbrev.setNumber(InSet->getNumber());
 828   } else {
 829     // Add to abbreviation list.
 830     Abbreviations.push_back(
 831         std::make_unique<DIEAbbrev>(Abbrev.getTag(), Abbrev.hasChildren()));
 832     for (const auto &Attr : Abbrev.getData())
 833       Abbreviations.back()->AddAttribute(Attr.getAttribute(), Attr.getForm());
 834     AbbreviationsSet.InsertNode(Abbreviations.back().get(), InsertToken);
 835     // Assign the unique abbreviation number.
 836     Abbrev.setNumber(Abbreviations.size());
 837     Abbreviations.back()->setNumber(Abbreviations.size());
 838   }
 839 }
 840
 841 void DIEBuilder::generateAbbrevs() {
 842   if (isEmpty())
 843     return;
 844
 845   for (DWARFUnit *DU : getState().DUList) {
 846     DIE *UnitDIE = getUnitDIEbyUnit(*DU);
 847     generateUnitAbbrevs(UnitDIE);
 848   }
 849 }
 850
 851 void DIEBuilder::generateUnitAbbrevs(DIE *Die) {
 852   DIEAbbrev NewAbbrev = Die->generateAbbrev();
 853
 854   if (Die->hasChildren())
 855     NewAbbrev.setChildrenFlag(dwarf::DW_CHILDREN_yes);
 856   assignAbbrev(NewAbbrev);
 857   Die->setAbbrevNumber(NewAbbrev.getNumber());
 858
 859   for (auto &Child : Die->children()) {
 860     generateUnitAbbrevs(&Child);
 861   }
 862 }
 863
 864 static uint64_t getHash(const DWARFUnit &DU) {
 865   // Before DWARF5 TU units are in their own section, so at least one offset,
 866   // first one, will be the same as CUs in .debug_info.dwo section
 867   if (DU.getVersion() < 5 && DU.isTypeUnit()) {
 868     const uint64_t TypeUnitHash =
 869         cast_or_null<DWARFTypeUnit>(&DU)->getTypeHash();
 870     const uint64_t Offset = DU.getOffset();
 871     return llvm::hash_combine(llvm::hash_value(TypeUnitHash),
 872                               llvm::hash_value(Offset));
 873   }
 874   return DU.getOffset();
 875 }
 876
 877 void DIEBuilder::registerUnit(DWARFUnit &DU, bool NeedSort) {
 878   auto IterGlobal = AllProcessed.insert(getHash(DU));
 879   // If DU is already in a current working set or was already processed we can
 880   // skip it.
 881   if (!IterGlobal.second)
 882     return;
 883   if (getState().Type == ProcessingType::DWARF4TUs) {
 884     getState().DWARF4TUVector.push_back(&DU);
 885   } else if (getState().Type == ProcessingType::DWARF5TUs) {
 886     getState().DWARF5TUVector.push_back(&DU);
 887   } else {
 888     getState().DWARFCUVector.push_back(&DU);
 889     /// Sorting for cross CU reference resolution.
 890     if (NeedSort)
 891       std::sort(getState().DWARFCUVector.begin(),
 892                 getState().DWARFCUVector.end(),
 893                 [](const DWARFUnit *A, const DWARFUnit *B) {
 894                   return A->getOffset() < B->getOffset();
 895                 });
 896   }
 897   getState().UnitIDMap[getHash(DU)] = getState().DUList.size();
 898   // This handles the case where we do have cross cu references, but CUs do not
 899   // share the same abbrev table.
 900   if (getState().DUList.size() == getState().CloneUnitCtxMap.size())
 901     getState().CloneUnitCtxMap.emplace_back();
 902   getState().DUList.push_back(&DU);
 903 }
 904
 905 std::optional<uint32_t> DIEBuilder::getUnitId(const DWARFUnit &DU) {
 906   auto Iter = getState().UnitIDMap.find(getHash(DU));
 907   if (Iter != getState().UnitIDMap.end())
 908     return Iter->second;
 909   return std::nullopt;
 910 }
 911
 912 } // namespace bolt
 913 } // namespace llvm