From cd49eb3fa17f9f19cfffa9437eb4db10dc11d43c Mon Sep 17 00:00:00 2001
From: David Blaikie <dblaikie@gmail.com>
Date: Mon, 14 Dec 2015 07:42:00 +0000
Subject: [PATCH] [llvm-dwp] Deduplicate type units

It's O(N^2) because it does a simple walk through the existing types to
find duplicates, but that will be fixed in a follow-up commit to use a
mapping data structure of some kind.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@255482 91177308-0d34-0410-b5e6-96231b3b80d8
---
 test/tools/llvm-dwp/Inputs/type_dedup/a.dwo | Bin 0 -> 1449 bytes
 test/tools/llvm-dwp/Inputs/type_dedup/b.dwo | Bin 0 -> 1449 bytes
 test/tools/llvm-dwp/X86/type_dedup.test     |  35 ++++++++++++++++++++
 tools/llvm-dwp/llvm-dwp.cpp                 |  18 ++++++----
 4 files changed, 47 insertions(+), 6 deletions(-)
 create mode 100644 test/tools/llvm-dwp/Inputs/type_dedup/a.dwo
 create mode 100644 test/tools/llvm-dwp/Inputs/type_dedup/b.dwo
 create mode 100644 test/tools/llvm-dwp/X86/type_dedup.test

diff --git a/test/tools/llvm-dwp/Inputs/type_dedup/a.dwo b/test/tools/llvm-dwp/Inputs/type_dedup/a.dwo
new file mode 100644
index 0000000000000000000000000000000000000000..cfd54c5fbc1a2487494f5e222067c0c17db39ff2
GIT binary patch
literal 1449
zcmbtU&1=*^6n`_5=xRV(0%|KrK!mM_xZPTG{aCk(pY-6tdrh+08q6kZlCJJas7G(=
z*_+@&1bgkpKgCPIi+{m__$HZ2(lO$}2k-0me(%lOWGAogY~H1WfD{6Ks4|HHv}qL&
z@^AnKw7?6UXxp0lNgBkFwPs(jJ61bOcA{ricYUqb>8)7pFr1DrR@iEH1svO(Ou$(M
zFCLHM2%IiB!ywIq$jkESm(kup9iZMreTd3)4Hck8Fd*@-&4c;AHly?$VuaE;u)Qq&
z{^r9MhiZHR(deA8y@O?UKTbY^g^(B^d1oc0fzAj%h&o5~)j2vL49FrmzuPx;w%h-D
z>nH%d1Q<RrZ!TRmt{L<+05jqGQh>9x4YF{`)B$vpa}0ws@XV8_6c*4DGCx7Y1Hlx)
zPG{rHanWZ<;h)NA=({`HTVd?k!xu5wMT$iw-HJz})X&m797LnIo@cX(e~93?ZsJet
zlrV_=JkQtqKXV4#oBmgWzl>G67es$Y;miKV3NHJl?}>he2JZ!c@9dDsJ_$a;K*f0N
zvmk5;FP+MLf&~@h+@IW_+%H^dRqk`Fs2C@&3-ET?Sp+KgHNq;!nJ)#nT(p%|<t}1{
zmDMVED~RtZD38>Bp4UDhCHqHlAK{xoj-zi0<&b<Y$1rX>{}Wy<E=}hZm492j(2XS4
exG~?OX%mi%AEQiTAeQ_CKcXN-$^gG9s{97%fPyUm

literal 0
HcmV?d00001

diff --git a/test/tools/llvm-dwp/Inputs/type_dedup/b.dwo b/test/tools/llvm-dwp/Inputs/type_dedup/b.dwo
new file mode 100644
index 0000000000000000000000000000000000000000..278369f80d66ad56d79c3d0de4e1a4e7f5870081
GIT binary patch
literal 1449
zcmbtU&5P4O6n`_5Xf+_a1k_cKfCya=vD@yV^`mwbKT+`Dy*6pOhE0>&WV;p*!g>;K
z>P_(MK?VH-#Djl>XOABA50GAblguR9G2+1o@9Xz|@6Bt{$>S@xu2Mok3V{w3nM48V
zw1~TD*aZV>;0FD0!<u@N*pEW1WuLJdRy~<)g_~A$t<`R{m#umbOh=~*Y^Avjj_r=e
z;H-cfjYd%jP7|DgA18k3Ch7FkXfL34QLmxiMCG}L3Q!{$kY8V4{rK`|woU1A#0aHx
zU>}p<+q2j2`&8o-h(_mxwLXPUZ+pFWU?C(1NZv6CX`nNL52D18ePxbL2m`W6PV96{
zo$Yi!T-pmjR{_Ht=EbG6#yNu?24E(fU-EI5woVofnL2=Oa*kne2A+8kmBIpALgojE
zcp#Vp*zs(X^d0ocB=h%WH1M3Qjb0GB_Fy{#J4>;sq`hc3jJ+f-!+to7%6T#yd%FmI
z$C-H3G9~asFU`}n{?8o6_NxC?_b+2r?n%+#Q24U{u7b;c>D!`Tp}|W5;5*wTvQL6{
zFi<gGdn*X*!b_)e?_oj3IQJ(vDAzNWTb26&D=NmxYXZEScV>ageS)xxappq-9?9Br
zt8y2y!t!bnJQu_l1(Zf=KhH~_kevNJyN~c$Ap6nRgmOr}mwgylo&N@}7MH5?vdX_L
jUg$~^tK69HQMC!j#g9>@F%V1sf$vd}EM<V-6jgo$BS(RX

literal 0
HcmV?d00001

diff --git a/test/tools/llvm-dwp/X86/type_dedup.test b/test/tools/llvm-dwp/X86/type_dedup.test
new file mode 100644
index 00000000000..3005705fcaa
--- /dev/null
+++ b/test/tools/llvm-dwp/X86/type_dedup.test
@@ -0,0 +1,35 @@
+RUN: llvm-dwp %p/../Inputs/type_dedup/a.dwo %p/../Inputs/type_dedup/b.dwo -o %t
+RUN: llvm-dwarfdump %t | FileCheck %s
+
+a.cpp:
+  struct common { };
+  common a1;
+  struct adistinct { };
+  adistinct a2;
+
+b.cpp:
+  struct common { };
+  common b1;
+  struct bdistinct { };
+  bdistinct b2;
+
+CHECK-LABEL: .debug_types.dwo contents:
+CHECK: [[COMMONUOFF:0x[0-9a-f]*]]:
+CHECK-LABEL: Type Unit: length = 0x00000020 version = 0x0004 abbr_offset =
+CHECK:         0x0000 addr_size = 0x08 type_signature = [[COMMONSIG:0x[0-9a-f]*]] type_offset = 0x[[COMMONOFF:.*]] (next unit at [[AUOFF:.*]])
+CHECK:                DW_TAG_type_unit
+CHECK: [[COMMONOFF]]:   DW_TAG_structure_type
+CHECK:                    DW_AT_name {{.*}} "common"
+CHECK: [[AUOFF]]:
+CHECK-LABEL: Type Unit: length = 0x00000020 version = 0x0004 abbr_offset =
+CHECK:         0x0000 addr_size = 0x08 type_signature = [[ASIG:0x[0-9a-f]*]] type_offset = 0x[[AOFF:.*]] (next unit at [[BUOFF:.*]])
+CHECK:             DW_TAG_type_unit
+CHECK: 0x00000042:   DW_TAG_structure_type
+CHECK:                 DW_AT_name {{.*}} "adistinct"
+CHECK: [[BUOFF]]:
+CHECK-LABEL: Type Unit: length = 0x00000020 version = 0x0004 abbr_offset =
+CHECK:         0x{{.*}} addr_size = 0x08 type_signature = [[BSIG:0x[0-9a-f]*]] type_offset = 0x[[BOFF:.*]] (next unit at [[XUOFF:.*]])
+CHECK:             DW_TAG_type_unit
+CHECK: 0x00000066:   DW_TAG_structure_type
+CHECK:                 DW_AT_name {{.*}} "bdistinct"
+CHECK-NOT: Type Unit
diff --git a/tools/llvm-dwp/llvm-dwp.cpp b/tools/llvm-dwp/llvm-dwp.cpp
index 5d95a751f71..5fb1c52330f 100644
--- a/tools/llvm-dwp/llvm-dwp.cpp
+++ b/tools/llvm-dwp/llvm-dwp.cpp
@@ -148,24 +148,30 @@ static void addAllTypes(MCStreamer &Out,
   uint32_t Offset = 0;
   DataExtractor Data(Types, true, 0);
   while (Data.isValidOffset(Offset)) {
-    TypeIndexEntries.push_back(CUEntry);
-    auto &Entry = TypeIndexEntries.back();
+    UnitIndexEntry Entry = CUEntry;
     // Zero out the debug_info contribution
     Entry.Contributions[0] = {};
     auto &C = Entry.Contributions[DW_SECT_TYPES - DW_SECT_INFO];
-    C.Offset = TypesOffset + Offset;
+    C.Offset = TypesOffset;
     auto PrevOffset = Offset;
     // Length of the unit, including the 4 byte length field.
     C.Length = Data.getU32(&Offset) + 4;
 
-    Out.EmitBytes(Types.substr(Offset - 4, C.Length));
-    TypesOffset += C.Length;
-
     Data.getU16(&Offset); // Version
     Data.getU32(&Offset); // Abbrev offset
     Data.getU8(&Offset);  // Address size
     Entry.Signature = Data.getU64(&Offset);
     Offset = PrevOffset + C.Length;
+
+    if (any_of(TypeIndexEntries, [&](const UnitIndexEntry &E) {
+          return E.Signature == Entry.Signature;
+        }))
+      continue;
+
+    Out.EmitBytes(Types.substr(PrevOffset, C.Length));
+    TypesOffset += C.Length;
+
+    TypeIndexEntries.push_back(Entry);
   }
 }
 
-- 
2.34.1