1 //===- ICF.cpp ------------------------------------------------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // ICF is short for Identical Code Folding. That is a size optimization to
11 // identify and merge two or more read-only sections (typically functions)
12 // that happened to have the same contents. It usually reduces output size
15 // On Windows, ICF is enabled by default.
17 // See ELF/ICF.cpp for the details about the algortihm.
19 //===----------------------------------------------------------------------===//
24 #include "lld/Core/Parallel.h"
25 #include "llvm/ADT/Hashing.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
39 void run(const std::vector<Chunk *> &V);
42 void segregate(size_t Begin, size_t End, bool Constant);
44 bool equalsConstant(const SectionChunk *A, const SectionChunk *B);
45 bool equalsVariable(const SectionChunk *A, const SectionChunk *B);
47 uint32_t getHash(SectionChunk *C);
48 bool isEligible(SectionChunk *C);
50 size_t findBoundary(size_t Begin, size_t End);
52 void forEachColorRange(size_t Begin, size_t End,
53 std::function<void(size_t, size_t)> Fn);
55 void forEachColor(std::function<void(size_t, size_t)> Fn);
57 std::vector<SectionChunk *> Chunks;
59 std::atomic<uint32_t> NextId = {1};
60 std::atomic<bool> Repeat = {false};
63 // Returns a hash value for S.
64 uint32_t ICF::getHash(SectionChunk *C) {
65 return hash_combine(C->getPermissions(),
66 hash_value(C->SectionName),
69 uint32_t(C->Header->SizeOfRawData),
73 // Returns true if section S is subject of ICF.
74 bool ICF::isEligible(SectionChunk *C) {
75 bool Global = C->Sym && C->Sym->isExternal();
76 bool Writable = C->getPermissions() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
77 return C->isCOMDAT() && C->isLive() && Global && !Writable;
80 // Split a range into smaller ranges by recoloring sections
81 void ICF::segregate(size_t Begin, size_t End, bool Constant) {
83 // Divide [Begin, End) into two. Let Mid be the start index of the
85 auto Bound = std::stable_partition(
86 Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
88 return equalsConstant(Chunks[Begin], S);
89 return equalsVariable(Chunks[Begin], S);
91 size_t Mid = Bound - Chunks.begin();
93 // Split [Begin, End) into [Begin, Mid) and [Mid, End).
94 uint32_t Id = NextId++;
95 for (size_t I = Begin; I < Mid; ++I)
96 Chunks[I]->Color[(Cnt + 1) % 2] = Id;
98 // If we created a group, we need to iterate the main loop again.
106 // Compare "non-moving" part of two sections, namely everything
107 // except relocation targets.
108 bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
109 if (A->NumRelocs != B->NumRelocs)
112 // Compare relocations.
113 auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
114 if (R1.Type != R2.Type ||
115 R1.VirtualAddress != R2.VirtualAddress) {
118 SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
119 SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
122 if (auto *D1 = dyn_cast<DefinedRegular>(B1))
123 if (auto *D2 = dyn_cast<DefinedRegular>(B2))
124 return D1->getValue() == D2->getValue() &&
125 D1->getChunk()->Color[Cnt % 2] == D2->getChunk()->Color[Cnt % 2];
128 if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq))
131 // Compare section attributes and contents.
132 return A->getPermissions() == B->getPermissions() &&
133 A->SectionName == B->SectionName &&
134 A->getAlign() == B->getAlign() &&
135 A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
136 A->Checksum == B->Checksum &&
137 A->getContents() == B->getContents();
140 // Compare "moving" part of two sections, namely relocation targets.
141 bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
142 // Compare relocations.
143 auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
144 SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
145 SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
148 if (auto *D1 = dyn_cast<DefinedRegular>(B1))
149 if (auto *D2 = dyn_cast<DefinedRegular>(B2))
150 return D1->getChunk()->Color[Cnt % 2] == D2->getChunk()->Color[Cnt % 2];
153 return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq);
156 size_t ICF::findBoundary(size_t Begin, size_t End) {
157 for (size_t I = Begin + 1; I < End; ++I)
158 if (Chunks[Begin]->Color[Cnt % 2] != Chunks[I]->Color[Cnt % 2])
163 void ICF::forEachColorRange(size_t Begin, size_t End,
164 std::function<void(size_t, size_t)> Fn) {
166 Begin = findBoundary(Begin - 1, End);
168 while (Begin < End) {
169 size_t Mid = findBoundary(Begin, Chunks.size());
175 // Call Fn on each color group.
176 void ICF::forEachColor(std::function<void(size_t, size_t)> Fn) {
177 // If the number of sections are too small to use threading,
178 // call Fn sequentially.
179 if (Chunks.size() < 1024) {
180 forEachColorRange(0, Chunks.size(), Fn);
184 // Split sections into 256 shards and call Fn in parallel.
185 size_t NumShards = 256;
186 size_t Step = Chunks.size() / NumShards;
187 parallel_for(size_t(0), NumShards, [&](size_t I) {
188 forEachColorRange(I * Step, (I + 1) * Step, Fn);
190 forEachColorRange(Step * NumShards, Chunks.size(), Fn);
193 // Merge identical COMDAT sections.
194 // Two sections are considered the same if their section headers,
195 // contents and relocations are all the same.
196 void ICF::run(const std::vector<Chunk *> &Vec) {
197 // Collect only mergeable sections and group by hash value.
198 for (Chunk *C : Vec) {
199 auto *SC = dyn_cast<SectionChunk>(C);
203 if (isEligible(SC)) {
204 // Set MSB to 1 to avoid collisions with non-hash colors.
205 SC->Color[0] = getHash(SC) | (1 << 31);
206 Chunks.push_back(SC);
208 SC->Color[0] = NextId++;
215 // From now on, sections in Chunks are ordered so that sections in
216 // the same group are consecutive in the vector.
217 std::stable_sort(Chunks.begin(), Chunks.end(),
218 [](SectionChunk *A, SectionChunk *B) {
219 return A->Color[0] < B->Color[0];
222 // Compare static contents and assign unique IDs for each static content.
223 forEachColor([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
226 // Split groups by comparing relocations until convergence is obtained.
230 [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
235 outs() << "\nICF needed " << Cnt << " iterations\n";
237 // Merge sections in the same colors.
238 forEachColor([&](size_t Begin, size_t End) {
239 if (End - Begin == 1)
243 outs() << "Selected " << Chunks[Begin]->getDebugName() << "\n";
244 for (size_t I = Begin + 1; I < End; ++I) {
246 outs() << " Removed " << Chunks[I]->getDebugName() << "\n";
247 Chunks[Begin]->replace(Chunks[I]);
252 // Entry point to ICF.
253 void doICF(const std::vector<Chunk *> &Chunks) { ICF().run(Chunks); }