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(const bool Init) {
 193   if (Init)
 194     BuilderState.reset(new State());
 195
 196   unsigned int CUNum = getCUNum(DwarfContext, IsDWO);
 197   getState().CloneUnitCtxMap.resize(CUNum);
 198   DWARFContext::unit_iterator_range CU4TURanges =
 199       IsDWO ? DwarfContext->dwo_types_section_units()
 200             : DwarfContext->types_section_units();
 201
 202   const DWARFUnitIndex &TUIndex = DwarfContext->getTUIndex();
 203   if (!TUIndex.getRows().empty()) {
 204     for (auto &Row : TUIndex.getRows()) {
 205       uint64_t Signature = Row.getSignature();
 206       // manually populate TypeUnit to UnitVector
 207       DwarfContext->getTypeUnitForHash(DwarfContext->getMaxVersion(), Signature,
 208                                        true);
 209     }
 210   }
 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 }
 236
 237 void DIEBuilder::buildCompileUnits(const bool Init) {
 238   if (Init)
 239     BuilderState.reset(new State());
 240
 241   unsigned int CUNum = getCUNum(DwarfContext, IsDWO);
 242   getState().CloneUnitCtxMap.resize(CUNum);
 243   DWARFContext::unit_iterator_range CURanges =
 244       IsDWO ? DwarfContext->dwo_info_section_units()
 245             : DwarfContext->info_section_units();
 246
 247   // This handles DWARF4 CUs and DWARF5 CU/TUs.
 248   // Creating a vector so that for reference handling only DWARF5 CU/TUs are
 249   // used, and not DWARF4 TUs.getState().DUList
 250   getState().Type = ProcessingType::CUs;
 251   for (std::unique_ptr<DWARFUnit> &DU : CURanges) {
 252     if (DU->isTypeUnit())
 253       continue;
 254     registerUnit(*DU.get(), false);
 255   }
 256
 257   // Using DULIst since it can be modified by cross CU refrence resolution.
 258   for (DWARFUnit *DU : getState().DUList) {
 259     if (DU->isTypeUnit())
 260       continue;
 261     constructFromUnit(*DU);
 262   }
 263 }
 264 void DIEBuilder::buildCompileUnits(const std::vector<DWARFUnit *> &CUs) {
 265   BuilderState.reset(new State());
 266   // Initializing to full size because there could be cross CU references with
 267   // different abbrev offsets. LLVM happens to output CUs that have cross CU
 268   // references with the same abbrev table. So destinations end up in the first
 269   // set, even if they themselves don't have src cross cu ref. We could have
 270   // cases where this is not the case. In which case this container needs to be
 271   // big enough for all.
 272   getState().CloneUnitCtxMap.resize(DwarfContext->getNumCompileUnits());
 273   getState().Type = ProcessingType::CUs;
 274   for (DWARFUnit *CU : CUs)
 275     registerUnit(*CU, false);
 276
 277   for (DWARFUnit *DU : getState().DUList)
 278     constructFromUnit(*DU);
 279 }
 280
 281 void DIEBuilder::buildBoth() {
 282   BuilderState.release();
 283   BuilderState = std::make_unique<State>();
 284   buildTypeUnits(false);
 285   buildCompileUnits(false);
 286 }
 287
 288 DIE *DIEBuilder::constructDIEFast(DWARFDie &DDie, DWARFUnit &U,
 289                                   uint32_t UnitId) {
 290
 291   std::optional<uint32_t> Idx = getAllocDIEId(U, DDie);
 292   if (Idx) {
 293     DWARFUnitInfo &DWARFUnitInfo = getUnitInfo(UnitId);
 294     DIEInfo &DieInfo = getDIEInfo(UnitId, *Idx);
 295     if (DWARFUnitInfo.IsConstructed && DieInfo.Die)
 296       return DieInfo.Die;
 297   } else {
 298     Idx = allocDIE(U, DDie, getState().DIEAlloc, UnitId);
 299   }
 300
 301   DIEInfo &DieInfo = getDIEInfo(UnitId, *Idx);
 302
 303   uint64_t Offset = DDie.getOffset();
 304   uint64_t NextOffset = Offset;
 305   DWARFDataExtractor Data = U.getDebugInfoExtractor();
 306   DWARFDebugInfoEntry DDIEntry;
 307
 308   if (DDIEntry.extractFast(U, &NextOffset, Data, U.getNextUnitOffset(), 0))
 309     assert(NextOffset - U.getOffset() <= Data.getData().size() &&
 310            "NextOffset OOB");
 311
 312   SmallString<40> DIECopy(Data.getData().substr(Offset, NextOffset - Offset));
 313   Data =
 314       DWARFDataExtractor(DIECopy, Data.isLittleEndian(), Data.getAddressSize());
 315
 316   const DWARFAbbreviationDeclaration *Abbrev =
 317       DDie.getAbbreviationDeclarationPtr();
 318   uint64_t AttrOffset = getULEB128Size(Abbrev->getCode());
 319
 320   using AttrSpec = DWARFAbbreviationDeclaration::AttributeSpec;
 321   for (const AttrSpec &AttrSpec : Abbrev->attributes()) {
 322     DWARFFormValue Val(AttrSpec.Form);
 323     Val.extractValue(Data, &AttrOffset, U.getFormParams(), &U);
 324     cloneAttribute(*DieInfo.Die, DDie, U, Val, AttrSpec);
 325   }
 326   return DieInfo.Die;
 327 }
 328
 329 static DWARFUnit *
 330 getUnitForOffset(DIEBuilder &Builder, DWARFContext &DWCtx,
 331                  const uint64_t Offset,
 332                  const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
 333   auto findUnit = [&](std::vector<DWARFUnit *> &Units) -> DWARFUnit * {
 334     auto CUIter = llvm::upper_bound(Units, Offset,
 335                                     [](uint64_t LHS, const DWARFUnit *RHS) {
 336                                       return LHS < RHS->getNextUnitOffset();
 337                                     });
 338     static std::vector<DWARFUnit *> CUOffsets;
 339     static std::once_flag InitVectorFlag;
 340     auto initCUVector = [&]() {
 341       CUOffsets.reserve(DWCtx.getNumCompileUnits());
 342       for (const std::unique_ptr<DWARFUnit> &CU : DWCtx.compile_units())
 343         CUOffsets.emplace_back(CU.get());
 344     };
 345     DWARFUnit *CU = CUIter != Units.end() ? *CUIter : nullptr;
 346     // Above algorithm breaks when there is only one CU, and reference is
 347     // outside of it. Fall through slower path, that searches all the CUs.
 348     // For example when src and destination of cross CU references have
 349     // different abbrev section.
 350     if (!CU ||
 351         (CU && AttrSpec.Form == dwarf::DW_FORM_ref_addr &&
 352          !(CU->getOffset() < Offset && CU->getNextUnitOffset() > Offset))) {
 353       // This is a work around for XCode clang. There is a build error when we
 354       // pass DWCtx.compile_units() to llvm::upper_bound
 355       std::call_once(InitVectorFlag, initCUVector);
 356       auto CUIter = std::upper_bound(CUOffsets.begin(), CUOffsets.end(), Offset,
 357                                      [](uint64_t LHS, const DWARFUnit *RHS) {
 358                                        return LHS < RHS->getNextUnitOffset();
 359                                      });
 360       CU = CUIter != CUOffsets.end() ? (*CUIter) : nullptr;
 361     }
 362     return CU;
 363   };
 364
 365   switch (Builder.getCurrentProcessingState()) {
 366   case DIEBuilder::ProcessingType::DWARF4TUs:
 367     return findUnit(Builder.getDWARF4TUVector());
 368   case DIEBuilder::ProcessingType::DWARF5TUs:
 369     return findUnit(Builder.getDWARF5TUVector());
 370   case DIEBuilder::ProcessingType::CUs:
 371     return findUnit(Builder.getDWARFCUVector());
 372   };
 373
 374   return nullptr;
 375 }
 376
 377 uint32_t DIEBuilder::computeDIEOffset(const DWARFUnit &CU, DIE &Die,
 378                                       uint32_t &CurOffset) {
 379   getState().DWARFDieAddressesParsed.erase(Die.getOffset());
 380   uint32_t CurSize = 0;
 381   Die.setOffset(CurOffset);
 382   for (DIEValue &Val : Die.values())
 383     CurSize += Val.sizeOf(CU.getFormParams());
 384   CurSize += getULEB128Size(Die.getAbbrevNumber());
 385   CurOffset += CurSize;
 386
 387   for (DIE &Child : Die.children()) {
 388     uint32_t ChildSize = computeDIEOffset(CU, Child, CurOffset);
 389     CurSize += ChildSize;
 390   }
 391   // for children end mark.
 392   if (Die.hasChildren()) {
 393     CurSize += sizeof(uint8_t);
 394     CurOffset += sizeof(uint8_t);
 395   }
 396
 397   Die.setSize(CurSize);
 398
 399   return CurSize;
 400 }
 401
 402 void DIEBuilder::finish() {
 403   auto computeOffset = [&](const DWARFUnit &CU,
 404                            uint64_t &UnitStartOffset) -> void {
 405     DIE *UnitDIE = getUnitDIEbyUnit(CU);
 406     uint32_t HeaderSize = CU.getHeaderSize();
 407     uint32_t CurOffset = HeaderSize;
 408     computeDIEOffset(CU, *UnitDIE, CurOffset);
 409
 410     DWARFUnitInfo &CurUnitInfo = getUnitInfoByDwarfUnit(CU);
 411     CurUnitInfo.UnitOffset = UnitStartOffset;
 412     CurUnitInfo.UnitLength = HeaderSize + UnitDIE->getSize();
 413     UnitStartOffset += CurUnitInfo.UnitLength;
 414   };
 415   // Computing offsets for .debug_types section.
 416   // It's processed first when CU is registered so will be at the begginnig of
 417   // the vector.
 418   uint64_t TypeUnitStartOffset = 0;
 419   for (const DWARFUnit *CU : getState().DUList) {
 420     // We process DWARF$ types first.
 421     if (!(CU->getVersion() < 5 && CU->isTypeUnit()))
 422       break;
 423     computeOffset(*CU, TypeUnitStartOffset);
 424   }
 425
 426   for (const DWARFUnit *CU : getState().DUList) {
 427     // Skipping DWARF4 types.
 428     if (CU->getVersion() < 5 && CU->isTypeUnit())
 429       continue;
 430     computeOffset(*CU, UnitSize);
 431   }
 432   if (opts::Verbosity >= 1) {
 433     if (!getState().DWARFDieAddressesParsed.empty())
 434       dbgs() << "Referenced DIE offsets not in .debug_info\n";
 435     for (const uint64_t Address : getState().DWARFDieAddressesParsed) {
 436       dbgs() << Twine::utohexstr(Address) << "\n";
 437     }
 438   }
 439   updateReferences();
 440 }
 441
 442 DWARFDie DIEBuilder::resolveDIEReference(
 443     const DWARFFormValue &RefValue,
 444     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 445     DWARFUnit *&RefCU, DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
 446   assert(RefValue.isFormClass(DWARFFormValue::FC_Reference));
 447   uint64_t RefOffset = *RefValue.getAsReference();
 448   return resolveDIEReference(AttrSpec, RefOffset, RefCU, DwarfDebugInfoEntry);
 449 }
 450
 451 DWARFDie DIEBuilder::resolveDIEReference(
 452     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 453     const uint64_t RefOffset, DWARFUnit *&RefCU,
 454     DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
 455   uint64_t TmpRefOffset = RefOffset;
 456   if ((RefCU =
 457            getUnitForOffset(*this, *DwarfContext, TmpRefOffset, AttrSpec))) {
 458     /// Trying to add to current working set in case it's cross CU reference.
 459     registerUnit(*RefCU, true);
 460     DWARFDataExtractor DebugInfoData = RefCU->getDebugInfoExtractor();
 461     if (DwarfDebugInfoEntry.extractFast(*RefCU, &TmpRefOffset, DebugInfoData,
 462                                         RefCU->getNextUnitOffset(), 0)) {
 463       // In a file with broken references, an attribute might point to a NULL
 464       // DIE.
 465       DWARFDie RefDie = DWARFDie(RefCU, &DwarfDebugInfoEntry);
 466       if (!RefDie.isNULL()) {
 467         std::optional<uint32_t> UnitId = getUnitId(*RefCU);
 468
 469         // forward reference
 470         if (UnitId && !getState().CloneUnitCtxMap[*UnitId].IsConstructed &&
 471             !getAllocDIEId(*RefCU, RefDie))
 472           allocDIE(*RefCU, RefDie, getState().DIEAlloc, *UnitId);
 473         return RefDie;
 474       }
 475       errs() << "BOLT-WARNING: [internal-dwarf-error]: invalid referenced DIE "
 476                 "at offset: "
 477              << Twine::utohexstr(RefOffset) << ".\n";
 478
 479     } else {
 480       errs() << "BOLT-WARNING: [internal-dwarf-error]: could not parse "
 481                 "referenced DIE at offset: "
 482              << Twine::utohexstr(RefOffset) << ".\n";
 483     }
 484   } else {
 485     errs() << "BOLT-WARNING: [internal-dwarf-error]: could not find referenced "
 486               "CU. Referenced DIE offset: "
 487            << Twine::utohexstr(RefOffset) << ".\n";
 488   }
 489   return DWARFDie();
 490 }
 491
 492 void DIEBuilder::cloneDieReferenceAttribute(
 493     DIE &Die, const DWARFUnit &U, const DWARFDie &InputDIE,
 494     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 495     const DWARFFormValue &Val) {
 496   const uint64_t Ref = *Val.getAsReference();
 497
 498   DIE *NewRefDie = nullptr;
 499   DWARFUnit *RefUnit = nullptr;
 500
 501   DWARFDebugInfoEntry DDIEntry;
 502   const DWARFDie RefDie = resolveDIEReference(Val, AttrSpec, RefUnit, DDIEntry);
 503
 504   if (!RefDie)
 505     return;
 506
 507   const std::optional<uint32_t> UnitId = getUnitId(*RefUnit);
 508   const std::optional<uint32_t> IsAllocId = getAllocDIEId(*RefUnit, RefDie);
 509   assert(IsAllocId.has_value() && "Encountered unexpected unallocated DIE.");
 510   const uint32_t DIEId = *IsAllocId;
 511   DIEInfo &DieInfo = getDIEInfo(*UnitId, DIEId);
 512
 513   if (!DieInfo.Die) {
 514     assert(Ref > InputDIE.getOffset());
 515     (void)Ref;
 516     errs() << "BOLT-WARNING: [internal-dwarf-error]: encounter unexpected "
 517               "unallocated DIE. Should be alloc!\n";
 518     // We haven't cloned this DIE yet. Just create an empty one and
 519     // store it. It'll get really cloned when we process it.
 520     DieInfo.Die = DIE::get(getState().DIEAlloc, dwarf::Tag(RefDie.getTag()));
 521   }
 522   NewRefDie = DieInfo.Die;
 523
 524   if (AttrSpec.Form == dwarf::DW_FORM_ref_addr) {
 525     // no matter forward reference or backward reference, we are supposed
 526     // to calculate them in `finish` due to the possible modification of
 527     // the DIE.
 528     DWARFDie CurDie = const_cast<DWARFDie &>(InputDIE);
 529     DIEInfo *CurDieInfo = &getDIEInfoByDwarfDie(CurDie);
 530     getState().AddrReferences.push_back(
 531         std::make_pair(CurDieInfo, AddrReferenceInfo(&DieInfo, AttrSpec)));
 532
 533     Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_addr,
 534                  DIEInteger(0xDEADBEEF));
 535     return;
 536   }
 537
 538   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 539                DIEEntry(*NewRefDie));
 540 }
 541
 542 void DIEBuilder::cloneStringAttribute(
 543     DIE &Die, const DWARFUnit &U,
 544     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 545     const DWARFFormValue &Val) {
 546   if (AttrSpec.Form == dwarf::DW_FORM_string) {
 547     Expected<const char *> StrAddr = Val.getAsCString();
 548     if (!StrAddr) {
 549       consumeError(StrAddr.takeError());
 550       return;
 551     }
 552     Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_string,
 553                  new (getState().DIEAlloc)
 554                      DIEInlineString(StrAddr.get(), getState().DIEAlloc));
 555   } else {
 556     std::optional<uint64_t> OffsetIndex = Val.getRawUValue();
 557     Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 558                  DIEInteger(*OffsetIndex));
 559   }
 560 }
 561
 562 bool DIEBuilder::cloneExpression(const DataExtractor &Data,
 563                                  const DWARFExpression &Expression,
 564                                  DWARFUnit &U,
 565                                  SmallVectorImpl<uint8_t> &OutputBuffer,
 566                                  const CloneExpressionStage &Stage) {
 567   using Encoding = DWARFExpression::Operation::Encoding;
 568   using Descr = DWARFExpression::Operation::Description;
 569   uint64_t OpOffset = 0;
 570   bool DoesContainReference = false;
 571   for (const DWARFExpression::Operation &Op : Expression) {
 572     const Descr &Description = Op.getDescription();
 573     // DW_OP_const_type is variable-length and has 3
 574     // operands. Thus far we only support 2.
 575     if ((Description.Op.size() == 2 &&
 576          Description.Op[0] == Encoding::BaseTypeRef) ||
 577         (Description.Op.size() == 2 &&
 578          Description.Op[1] == Encoding::BaseTypeRef &&
 579          Description.Op[0] != Encoding::Size1))
 580       outs() << "BOLT-WARNING: [internal-dwarf-error]: unsupported DW_OP "
 581                 "encoding.\n";
 582
 583     if ((Description.Op.size() == 1 &&
 584          Description.Op[0] == Encoding::BaseTypeRef) ||
 585         (Description.Op.size() == 2 &&
 586          Description.Op[1] == Encoding::BaseTypeRef &&
 587          Description.Op[0] == Encoding::Size1)) {
 588       // This code assumes that the other non-typeref operand fits into 1
 589       // byte.
 590       assert(OpOffset < Op.getEndOffset());
 591       const uint32_t ULEBsize = Op.getEndOffset() - OpOffset - 1;
 592       (void)ULEBsize;
 593       assert(ULEBsize <= 16);
 594
 595       // Copy over the operation.
 596       OutputBuffer.push_back(Op.getCode());
 597       uint64_t RefOffset;
 598       if (Description.Op.size() == 1) {
 599         RefOffset = Op.getRawOperand(0);
 600       } else {
 601         OutputBuffer.push_back(Op.getRawOperand(0));
 602         RefOffset = Op.getRawOperand(1);
 603       }
 604       uint32_t Offset = 0;
 605       if (RefOffset > 0 || Op.getCode() != dwarf::DW_OP_convert) {
 606         DoesContainReference = true;
 607         std::optional<uint32_t> RefDieID =
 608             getAllocDIEId(U, U.getOffset() + RefOffset);
 609         std::optional<uint32_t> RefUnitID = getUnitId(U);
 610         if (RefDieID.has_value() && RefUnitID.has_value()) {
 611           DIEInfo &RefDieInfo = getDIEInfo(*RefUnitID, *RefDieID);
 612           if (DIE *Clone = RefDieInfo.Die)
 613             Offset = Stage == CloneExpressionStage::INIT ? RefOffset
 614                                                          : Clone->getOffset();
 615           else
 616             errs() << "BOLT-WARNING: [internal-dwarf-error]: base type ref "
 617                       "doesn't point to "
 618                       "DW_TAG_base_type.\n";
 619         }
 620       }
 621       uint8_t ULEB[16];
 622       // Hard coding to max size so size doesn't change when we update the
 623       // offset.
 624       encodeULEB128(Offset, ULEB, 4);
 625       ArrayRef<uint8_t> ULEBbytes(ULEB, 4);
 626       OutputBuffer.append(ULEBbytes.begin(), ULEBbytes.end());
 627     } else {
 628       // Copy over everything else unmodified.
 629       const StringRef Bytes = Data.getData().slice(OpOffset, Op.getEndOffset());
 630       OutputBuffer.append(Bytes.begin(), Bytes.end());
 631     }
 632     OpOffset = Op.getEndOffset();
 633   }
 634   return DoesContainReference;
 635 }
 636
 637 void DIEBuilder::cloneBlockAttribute(
 638     DIE &Die, DWARFUnit &U,
 639     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 640     const DWARFFormValue &Val) {
 641   DIEValueList *Attr;
 642   DIEValue Value;
 643   DIELoc *Loc = nullptr;
 644   DIEBlock *Block = nullptr;
 645
 646   if (AttrSpec.Form == dwarf::DW_FORM_exprloc) {
 647     Loc = new (getState().DIEAlloc) DIELoc;
 648   } else if (doesFormBelongToClass(AttrSpec.Form, DWARFFormValue::FC_Block,
 649                                    U.getVersion())) {
 650     Block = new (getState().DIEAlloc) DIEBlock;
 651   } else {
 652     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unexpected Form value in "
 653               "cloneBlockAttribute\n";
 654     return;
 655   }
 656   Attr = Loc ? static_cast<DIEValueList *>(Loc)
 657              : static_cast<DIEValueList *>(Block);
 658
 659   SmallVector<uint8_t, 32> Buffer;
 660   ArrayRef<uint8_t> Bytes = *Val.getAsBlock();
 661   if (DWARFAttribute::mayHaveLocationExpr(AttrSpec.Attr) &&
 662       (Val.isFormClass(DWARFFormValue::FC_Block) ||
 663        Val.isFormClass(DWARFFormValue::FC_Exprloc))) {
 664     DataExtractor Data(StringRef((const char *)Bytes.data(), Bytes.size()),
 665                        U.isLittleEndian(), U.getAddressByteSize());
 666     DWARFExpression Expr(Data, U.getAddressByteSize(),
 667                          U.getFormParams().Format);
 668     if (cloneExpression(Data, Expr, U, Buffer, CloneExpressionStage::INIT))
 669       getState().LocWithReferencesToProcess.emplace_back(
 670           Bytes.vec(), U, Die, AttrSpec.Form, AttrSpec.Attr);
 671     Bytes = Buffer;
 672   }
 673   for (auto Byte : Bytes)
 674     Attr->addValue(getState().DIEAlloc, static_cast<dwarf::Attribute>(0),
 675                    dwarf::DW_FORM_data1, DIEInteger(Byte));
 676
 677   if (Loc)
 678     Loc->setSize(Bytes.size());
 679   else
 680     Block->setSize(Bytes.size());
 681
 682   if (Loc)
 683     Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
 684                      dwarf::Form(AttrSpec.Form), Loc);
 685   else
 686     Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
 687                      dwarf::Form(AttrSpec.Form), Block);
 688   Die.addValue(getState().DIEAlloc, Value);
 689 }
 690
 691 void DIEBuilder::cloneAddressAttribute(
 692     DIE &Die, const DWARFUnit &U,
 693     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 694     const DWARFFormValue &Val) {
 695   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 696                DIEInteger(Val.getRawUValue()));
 697 }
 698
 699 void DIEBuilder::cloneRefsigAttribute(
 700     DIE &Die, DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 701     const DWARFFormValue &Val) {
 702   const std::optional<uint64_t> SigVal = Val.getRawUValue();
 703   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_sig8,
 704                DIEInteger(*SigVal));
 705 }
 706
 707 void DIEBuilder::cloneScalarAttribute(
 708     DIE &Die, const DWARFDie &InputDIE,
 709     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 710     const DWARFFormValue &Val) {
 711   uint64_t Value;
 712
 713   if (auto OptionalValue = Val.getAsUnsignedConstant())
 714     Value = *OptionalValue;
 715   else if (auto OptionalValue = Val.getAsSignedConstant())
 716     Value = *OptionalValue;
 717   else if (auto OptionalValue = Val.getAsSectionOffset())
 718     Value = *OptionalValue;
 719   else {
 720     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
 721               "attribute form. Dropping "
 722               "attribute.\n";
 723     return;
 724   }
 725
 726   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 727                DIEInteger(Value));
 728 }
 729
 730 void DIEBuilder::cloneLoclistAttrubute(
 731     DIE &Die, const DWARFDie &InputDIE,
 732     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 733     const DWARFFormValue &Val) {
 734   std::optional<uint64_t> Value = std::nullopt;
 735
 736   if (auto OptionalValue = Val.getAsUnsignedConstant())
 737     Value = OptionalValue;
 738   else if (auto OptionalValue = Val.getAsSignedConstant())
 739     Value = OptionalValue;
 740   else if (auto OptionalValue = Val.getAsSectionOffset())
 741     Value = OptionalValue;
 742   else
 743     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
 744               "attribute form. Dropping "
 745               "attribute.\n";
 746
 747   if (!Value.has_value())
 748     return;
 749
 750   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 751                DIELocList(*Value));
 752 }
 753
 754 void DIEBuilder::cloneAttribute(
 755     DIE &Die, const DWARFDie &InputDIE, DWARFUnit &U, const DWARFFormValue &Val,
 756     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
 757   switch (AttrSpec.Form) {
 758   case dwarf::DW_FORM_strp:
 759   case dwarf::DW_FORM_string:
 760   case dwarf::DW_FORM_strx:
 761   case dwarf::DW_FORM_strx1:
 762   case dwarf::DW_FORM_strx2:
 763   case dwarf::DW_FORM_strx3:
 764   case dwarf::DW_FORM_strx4:
 765   case dwarf::DW_FORM_GNU_str_index:
 766   case dwarf::DW_FORM_line_strp:
 767     cloneStringAttribute(Die, U, AttrSpec, Val);
 768     break;
 769   case dwarf::DW_FORM_ref_addr:
 770   case dwarf::DW_FORM_ref1:
 771   case dwarf::DW_FORM_ref2:
 772   case dwarf::DW_FORM_ref4:
 773   case dwarf::DW_FORM_ref8:
 774     cloneDieReferenceAttribute(Die, U, InputDIE, AttrSpec, Val);
 775     break;
 776   case dwarf::DW_FORM_block:
 777   case dwarf::DW_FORM_block1:
 778   case dwarf::DW_FORM_block2:
 779   case dwarf::DW_FORM_block4:
 780   case dwarf::DW_FORM_exprloc:
 781     cloneBlockAttribute(Die, U, AttrSpec, Val);
 782     break;
 783   case dwarf::DW_FORM_addr:
 784   case dwarf::DW_FORM_addrx:
 785   case dwarf::DW_FORM_GNU_addr_index:
 786     cloneAddressAttribute(Die, U, AttrSpec, Val);
 787     break;
 788   case dwarf::DW_FORM_data1:
 789   case dwarf::DW_FORM_data2:
 790   case dwarf::DW_FORM_data4:
 791   case dwarf::DW_FORM_data8:
 792   case dwarf::DW_FORM_udata:
 793   case dwarf::DW_FORM_sdata:
 794   case dwarf::DW_FORM_sec_offset:
 795   case dwarf::DW_FORM_rnglistx:
 796   case dwarf::DW_FORM_flag:
 797   case dwarf::DW_FORM_flag_present:
 798   case dwarf::DW_FORM_implicit_const:
 799     cloneScalarAttribute(Die, InputDIE, AttrSpec, Val);
 800     break;
 801   case dwarf::DW_FORM_loclistx:
 802     cloneLoclistAttrubute(Die, InputDIE, AttrSpec, Val);
 803     break;
 804   case dwarf::DW_FORM_ref_sig8:
 805     cloneRefsigAttribute(Die, AttrSpec, Val);
 806     break;
 807   default:
 808     errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported attribute "
 809               "form " +
 810                   dwarf::FormEncodingString(AttrSpec.Form).str() +
 811                   " in cloneAttribute. Dropping.";
 812   }
 813 }
 814 void DIEBuilder::assignAbbrev(DIEAbbrev &Abbrev) {
 815   // Check the set for priors.
 816   FoldingSetNodeID ID;
 817   Abbrev.Profile(ID);
 818   void *InsertToken;
 819   DIEAbbrev *InSet = AbbreviationsSet.FindNodeOrInsertPos(ID, InsertToken);
 820
 821   // If it's newly added.
 822   if (InSet) {
 823     // Assign existing abbreviation number.
 824     Abbrev.setNumber(InSet->getNumber());
 825   } else {
 826     // Add to abbreviation list.
 827     Abbreviations.push_back(
 828         std::make_unique<DIEAbbrev>(Abbrev.getTag(), Abbrev.hasChildren()));
 829     for (const auto &Attr : Abbrev.getData())
 830       Abbreviations.back()->AddAttribute(Attr.getAttribute(), Attr.getForm());
 831     AbbreviationsSet.InsertNode(Abbreviations.back().get(), InsertToken);
 832     // Assign the unique abbreviation number.
 833     Abbrev.setNumber(Abbreviations.size());
 834     Abbreviations.back()->setNumber(Abbreviations.size());
 835   }
 836 }
 837
 838 void DIEBuilder::generateAbbrevs() {
 839   if (isEmpty())
 840     return;
 841
 842   for (DWARFUnit *DU : getState().DUList) {
 843     DIE *UnitDIE = getUnitDIEbyUnit(*DU);
 844     generateUnitAbbrevs(UnitDIE);
 845   }
 846 }
 847
 848 void DIEBuilder::generateUnitAbbrevs(DIE *Die) {
 849   DIEAbbrev NewAbbrev = Die->generateAbbrev();
 850
 851   if (Die->hasChildren())
 852     NewAbbrev.setChildrenFlag(dwarf::DW_CHILDREN_yes);
 853   assignAbbrev(NewAbbrev);
 854   Die->setAbbrevNumber(NewAbbrev.getNumber());
 855
 856   for (auto &Child : Die->children()) {
 857     generateUnitAbbrevs(&Child);
 858   }
 859 }
 860
 861 static uint64_t getHash(const DWARFUnit &DU) {
 862   // Before DWARF5 TU units are in their own section, so at least one offset,
 863   // first one, will be the same as CUs in .debug_info.dwo section
 864   if (DU.getVersion() < 5 && DU.isTypeUnit()) {
 865     const uint64_t TypeUnitHash =
 866         cast_or_null<DWARFTypeUnit>(&DU)->getTypeHash();
 867     const uint64_t Offset = DU.getOffset();
 868     return llvm::hash_combine(llvm::hash_value(TypeUnitHash),
 869                               llvm::hash_value(Offset));
 870   }
 871   return DU.getOffset();
 872 }
 873
 874 void DIEBuilder::registerUnit(DWARFUnit &DU, bool NeedSort) {
 875   auto IterGlobal = AllProcessed.insert(getHash(DU));
 876   // If DU is already in a current working set or was already processed we can
 877   // skip it.
 878   if (!IterGlobal.second)
 879     return;
 880   if (getState().Type == ProcessingType::DWARF4TUs) {
 881     getState().DWARF4TUVector.push_back(&DU);
 882   } else if (getState().Type == ProcessingType::DWARF5TUs) {
 883     getState().DWARF5TUVector.push_back(&DU);
 884   } else {
 885     getState().DWARFCUVector.push_back(&DU);
 886     /// Sorting for cross CU reference resolution.
 887     if (NeedSort)
 888       std::sort(getState().DWARFCUVector.begin(),
 889                 getState().DWARFCUVector.end(),
 890                 [](const DWARFUnit *A, const DWARFUnit *B) {
 891                   return A->getOffset() < B->getOffset();
 892                 });
 893   }
 894   getState().UnitIDMap[getHash(DU)] = getState().DUList.size();
 895   getState().DUList.push_back(&DU);
 896 }
 897
 898 std::optional<uint32_t> DIEBuilder::getUnitId(const DWARFUnit &DU) {
 899   auto Iter = getState().UnitIDMap.find(getHash(DU));
 900   if (Iter != getState().UnitIDMap.end())
 901     return Iter->second;
 902   return std::nullopt;
 903 }
 904
 905 } // namespace bolt
 906 } // namespace llvm