1 //===- Analyze.cpp - PDB analysis functions ---------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "Analyze.h"
11
12 #include "llvm/ADT/DenseSet.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
15 #include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
16 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
17 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
18 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
19 #include "llvm/DebugInfo/PDB/Native/RawError.h"
20 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
21
22 #include "llvm/Support/FormatVariadic.h"
23 #include "llvm/Support/raw_ostream.h"
24
25 #include <list>
26
27 using namespace llvm;
28 using namespace llvm::codeview;
29 using namespace llvm::pdb;
30
getLeafTypeName(TypeLeafKind LT)31 static StringRef getLeafTypeName(TypeLeafKind LT) {
32 switch (LT) {
33 #define TYPE_RECORD(ename, value, name) \
34 case ename: \
35 return #name;
36 #include "llvm/DebugInfo/CodeView/CodeViewTypes.def"
37 default:
38 break;
39 }
40 return "UnknownLeaf";
41 }
42
43 namespace {
44 struct HashLookupVisitor : public TypeVisitorCallbacks {
45 struct Entry {
46 TypeIndex TI;
47 CVType Record;
48 };
49
HashLookupVisitor__anond1c4c7cc0111::HashLookupVisitor50 explicit HashLookupVisitor(TpiStream &Tpi) : Tpi(Tpi) {}
51
visitTypeBegin__anond1c4c7cc0111::HashLookupVisitor52 Error visitTypeBegin(CVType &Record) override {
53 uint32_t H = Tpi.getHashValues()[I];
54 Record.Hash = H;
55 TypeIndex TI(I + TypeIndex::FirstNonSimpleIndex);
56 Lookup[H].push_back(Entry{TI, Record});
57 ++I;
58 return Error::success();
59 }
60
61 uint32_t I = 0;
62 DenseMap<uint32_t, std::list<Entry>> Lookup;
63 TpiStream &Tpi;
64 };
65 }
66
AnalysisStyle(PDBFile & File)67 AnalysisStyle::AnalysisStyle(PDBFile &File) : File(File) {}
68
dump()69 Error AnalysisStyle::dump() {
70 auto Tpi = File.getPDBTpiStream();
71 if (!Tpi)
72 return Tpi.takeError();
73
74 HashLookupVisitor Hasher(*Tpi);
75
76 uint32_t RecordCount = Tpi->getNumTypeRecords();
77 auto Offsets = Tpi->getTypeIndexOffsets();
78 auto Types = llvm::make_unique<LazyRandomTypeCollection>(
79 Tpi->typeArray(), RecordCount, Offsets);
80
81 if (auto EC = codeview::visitTypeStream(*Types, Hasher))
82 return EC;
83
84 auto &Adjusters = Tpi->getHashAdjusters();
85 DenseSet<uint32_t> AdjusterSet;
86 for (const auto &Adj : Adjusters) {
87 assert(AdjusterSet.find(Adj.second) == AdjusterSet.end());
88 AdjusterSet.insert(Adj.second);
89 }
90
91 uint32_t Count = 0;
92 outs() << "Searching for hash collisions\n";
93 for (const auto &H : Hasher.Lookup) {
94 if (H.second.size() <= 1)
95 continue;
96 ++Count;
97 outs() << formatv("Hash: {0}, Count: {1} records\n", H.first,
98 H.second.size());
99 for (const auto &R : H.second) {
100 auto Iter = AdjusterSet.find(R.TI.getIndex());
101 StringRef Prefix;
102 if (Iter != AdjusterSet.end()) {
103 Prefix = "[HEAD]";
104 AdjusterSet.erase(Iter);
105 }
106 StringRef LeafName = getLeafTypeName(R.Record.Type);
107 uint32_t TI = R.TI.getIndex();
108 StringRef TypeName = Types->getTypeName(R.TI);
109 outs() << formatv("{0,-6} {1} ({2:x}) {3}\n", Prefix, LeafName, TI,
110 TypeName);
111 }
112 }
113
114 outs() << "\n";
115 outs() << "Dumping hash adjustment chains\n";
116 for (const auto &A : Tpi->getHashAdjusters()) {
117 TypeIndex TI(A.second);
118 StringRef TypeName = Types->getTypeName(TI);
119 const CVType &HeadRecord = Types->getType(TI);
120 assert(HeadRecord.Hash.hasValue());
121
122 auto CollisionsIter = Hasher.Lookup.find(*HeadRecord.Hash);
123 if (CollisionsIter == Hasher.Lookup.end())
124 continue;
125
126 const auto &Collisions = CollisionsIter->second;
127 outs() << TypeName << "\n";
128 outs() << formatv(" [HEAD] {0:x} {1} {2}\n", uint32_t(A.second),
129 getLeafTypeName(HeadRecord.Type), TypeName);
130 for (const auto &Chain : Collisions) {
131 if (Chain.TI == TI)
132 continue;
133 const CVType &TailRecord = Types->getType(Chain.TI);
134 outs() << formatv(" {0:x} {1} {2}\n", Chain.TI.getIndex(),
135 getLeafTypeName(TailRecord.Type),
136 Types->getTypeName(Chain.TI));
137 }
138 }
139 outs() << formatv("There are {0} orphaned hash adjusters\n",
140 AdjusterSet.size());
141 for (const auto &Adj : AdjusterSet) {
142 outs() << formatv(" {0}\n", Adj);
143 }
144
145 uint32_t DistinctHashValues = Hasher.Lookup.size();
146 outs() << formatv("{0}/{1} hash collisions", Count, DistinctHashValues);
147 return Error::success();
148 }
149