summaryrefslogtreecommitdiffstats
path: root/lld/COFF/ICF.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lld/COFF/ICF.cpp')
-rw-r--r--lld/COFF/ICF.cpp270
1 files changed, 135 insertions, 135 deletions
diff --git a/lld/COFF/ICF.cpp b/lld/COFF/ICF.cpp
index 7e105ddad75..2b2818de388 100644
--- a/lld/COFF/ICF.cpp
+++ b/lld/COFF/ICF.cpp
@@ -37,32 +37,32 @@ using namespace llvm;
namespace lld {
namespace coff {
-static Timer ICFTimer("ICF", Timer::root());
+static Timer icfTimer("ICF", Timer::root());
class ICF {
public:
- void run(ArrayRef<Chunk *> V);
+ void run(ArrayRef<Chunk *> v);
private:
- void segregate(size_t Begin, size_t End, bool Constant);
+ void segregate(size_t begin, size_t end, bool constant);
- bool assocEquals(const SectionChunk *A, const SectionChunk *B);
+ bool assocEquals(const SectionChunk *a, const SectionChunk *b);
- bool equalsConstant(const SectionChunk *A, const SectionChunk *B);
- bool equalsVariable(const SectionChunk *A, const SectionChunk *B);
+ bool equalsConstant(const SectionChunk *a, const SectionChunk *b);
+ bool equalsVariable(const SectionChunk *a, const SectionChunk *b);
- bool isEligible(SectionChunk *C);
+ bool isEligible(SectionChunk *c);
- size_t findBoundary(size_t Begin, size_t End);
+ size_t findBoundary(size_t begin, size_t end);
- void forEachClassRange(size_t Begin, size_t End,
- std::function<void(size_t, size_t)> Fn);
+ void forEachClassRange(size_t begin, size_t end,
+ std::function<void(size_t, size_t)> fn);
- void forEachClass(std::function<void(size_t, size_t)> Fn);
+ void forEachClass(std::function<void(size_t, size_t)> fn);
- std::vector<SectionChunk *> Chunks;
- int Cnt = 0;
- std::atomic<bool> Repeat = {false};
+ std::vector<SectionChunk *> chunks;
+ int cnt = 0;
+ std::atomic<bool> repeat = {false};
};
// Returns true if section S is subject of ICF.
@@ -76,144 +76,144 @@ private:
// merge read-only sections in a couple of cases where the address of the
// section is insignificant to the user program and the behaviour matches that
// of the Visual C++ linker.
-bool ICF::isEligible(SectionChunk *C) {
+bool ICF::isEligible(SectionChunk *c) {
// Non-comdat chunks, dead chunks, and writable chunks are not elegible.
- bool Writable = C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
- if (!C->isCOMDAT() || !C->Live || Writable)
+ bool writable = c->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
+ if (!c->isCOMDAT() || !c->live || writable)
return false;
// Code sections are eligible.
- if (C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE)
+ if (c->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE)
return true;
// .pdata and .xdata unwind info sections are eligible.
- StringRef OutSecName = C->getSectionName().split('$').first;
- if (OutSecName == ".pdata" || OutSecName == ".xdata")
+ StringRef outSecName = c->getSectionName().split('$').first;
+ if (outSecName == ".pdata" || outSecName == ".xdata")
return true;
// So are vtables.
- if (C->Sym && C->Sym->getName().startswith("??_7"))
+ if (c->sym && c->sym->getName().startswith("??_7"))
return true;
// Anything else not in an address-significance table is eligible.
- return !C->KeepUnique;
+ return !c->keepUnique;
}
// Split an equivalence class into smaller classes.
-void ICF::segregate(size_t Begin, size_t End, bool Constant) {
- while (Begin < End) {
+void ICF::segregate(size_t begin, size_t end, bool constant) {
+ while (begin < end) {
// Divide [Begin, End) into two. Let Mid be the start index of the
// second group.
- auto Bound = std::stable_partition(
- Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
- if (Constant)
- return equalsConstant(Chunks[Begin], S);
- return equalsVariable(Chunks[Begin], S);
+ auto bound = std::stable_partition(
+ chunks.begin() + begin + 1, chunks.begin() + end, [&](SectionChunk *s) {
+ if (constant)
+ return equalsConstant(chunks[begin], s);
+ return equalsVariable(chunks[begin], s);
});
- size_t Mid = Bound - Chunks.begin();
+ size_t mid = bound - chunks.begin();
// Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
// equivalence class ID because every group ends with a unique index.
- for (size_t I = Begin; I < Mid; ++I)
- Chunks[I]->Class[(Cnt + 1) % 2] = Mid;
+ for (size_t i = begin; i < mid; ++i)
+ chunks[i]->eqClass[(cnt + 1) % 2] = mid;
// If we created a group, we need to iterate the main loop again.
- if (Mid != End)
- Repeat = true;
+ if (mid != end)
+ repeat = true;
- Begin = Mid;
+ begin = mid;
}
}
// Returns true if two sections' associative children are equal.
-bool ICF::assocEquals(const SectionChunk *A, const SectionChunk *B) {
- auto ChildClasses = [&](const SectionChunk *SC) {
- std::vector<uint32_t> Classes;
- for (const SectionChunk &C : SC->children())
- if (!C.getSectionName().startswith(".debug") &&
- C.getSectionName() != ".gfids$y" && C.getSectionName() != ".gljmp$y")
- Classes.push_back(C.Class[Cnt % 2]);
- return Classes;
+bool ICF::assocEquals(const SectionChunk *a, const SectionChunk *b) {
+ auto childClasses = [&](const SectionChunk *sc) {
+ std::vector<uint32_t> classes;
+ for (const SectionChunk &c : sc->children())
+ if (!c.getSectionName().startswith(".debug") &&
+ c.getSectionName() != ".gfids$y" && c.getSectionName() != ".gljmp$y")
+ classes.push_back(c.eqClass[cnt % 2]);
+ return classes;
};
- return ChildClasses(A) == ChildClasses(B);
+ return childClasses(a) == childClasses(b);
}
// Compare "non-moving" part of two sections, namely everything
// except relocation targets.
-bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
- if (A->RelocsSize != B->RelocsSize)
+bool ICF::equalsConstant(const SectionChunk *a, const SectionChunk *b) {
+ if (a->relocsSize != b->relocsSize)
return false;
// Compare relocations.
- auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
- if (R1.Type != R2.Type ||
- R1.VirtualAddress != R2.VirtualAddress) {
+ auto eq = [&](const coff_relocation &r1, const coff_relocation &r2) {
+ if (r1.Type != r2.Type ||
+ r1.VirtualAddress != r2.VirtualAddress) {
return false;
}
- Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
- Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
- if (B1 == B2)
+ Symbol *b1 = a->file->getSymbol(r1.SymbolTableIndex);
+ Symbol *b2 = b->file->getSymbol(r2.SymbolTableIndex);
+ if (b1 == b2)
return true;
- if (auto *D1 = dyn_cast<DefinedRegular>(B1))
- if (auto *D2 = dyn_cast<DefinedRegular>(B2))
- return D1->getValue() == D2->getValue() &&
- D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
+ if (auto *d1 = dyn_cast<DefinedRegular>(b1))
+ if (auto *d2 = dyn_cast<DefinedRegular>(b2))
+ return d1->getValue() == d2->getValue() &&
+ d1->getChunk()->eqClass[cnt % 2] == d2->getChunk()->eqClass[cnt % 2];
return false;
};
- if (!std::equal(A->getRelocs().begin(), A->getRelocs().end(),
- B->getRelocs().begin(), Eq))
+ if (!std::equal(a->getRelocs().begin(), a->getRelocs().end(),
+ b->getRelocs().begin(), eq))
return false;
// Compare section attributes and contents.
- return A->getOutputCharacteristics() == B->getOutputCharacteristics() &&
- A->getSectionName() == B->getSectionName() &&
- A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
- A->Checksum == B->Checksum && A->getContents() == B->getContents() &&
- assocEquals(A, B);
+ return a->getOutputCharacteristics() == b->getOutputCharacteristics() &&
+ a->getSectionName() == b->getSectionName() &&
+ a->header->SizeOfRawData == b->header->SizeOfRawData &&
+ a->checksum == b->checksum && a->getContents() == b->getContents() &&
+ assocEquals(a, b);
}
// Compare "moving" part of two sections, namely relocation targets.
-bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
+bool ICF::equalsVariable(const SectionChunk *a, const SectionChunk *b) {
// Compare relocations.
- auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
- Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
- Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
- if (B1 == B2)
+ auto eq = [&](const coff_relocation &r1, const coff_relocation &r2) {
+ Symbol *b1 = a->file->getSymbol(r1.SymbolTableIndex);
+ Symbol *b2 = b->file->getSymbol(r2.SymbolTableIndex);
+ if (b1 == b2)
return true;
- if (auto *D1 = dyn_cast<DefinedRegular>(B1))
- if (auto *D2 = dyn_cast<DefinedRegular>(B2))
- return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
+ if (auto *d1 = dyn_cast<DefinedRegular>(b1))
+ if (auto *d2 = dyn_cast<DefinedRegular>(b2))
+ return d1->getChunk()->eqClass[cnt % 2] == d2->getChunk()->eqClass[cnt % 2];
return false;
};
- return std::equal(A->getRelocs().begin(), A->getRelocs().end(),
- B->getRelocs().begin(), Eq) &&
- assocEquals(A, B);
+ return std::equal(a->getRelocs().begin(), a->getRelocs().end(),
+ b->getRelocs().begin(), eq) &&
+ assocEquals(a, b);
}
// Find the first Chunk after Begin that has a different class from Begin.
-size_t ICF::findBoundary(size_t Begin, size_t End) {
- for (size_t I = Begin + 1; I < End; ++I)
- if (Chunks[Begin]->Class[Cnt % 2] != Chunks[I]->Class[Cnt % 2])
- return I;
- return End;
+size_t ICF::findBoundary(size_t begin, size_t end) {
+ for (size_t i = begin + 1; i < end; ++i)
+ if (chunks[begin]->eqClass[cnt % 2] != chunks[i]->eqClass[cnt % 2])
+ return i;
+ return end;
}
-void ICF::forEachClassRange(size_t Begin, size_t End,
- std::function<void(size_t, size_t)> Fn) {
- while (Begin < End) {
- size_t Mid = findBoundary(Begin, End);
- Fn(Begin, Mid);
- Begin = Mid;
+void ICF::forEachClassRange(size_t begin, size_t end,
+ std::function<void(size_t, size_t)> fn) {
+ while (begin < end) {
+ size_t mid = findBoundary(begin, end);
+ fn(begin, mid);
+ begin = mid;
}
}
// Call Fn on each class group.
-void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
+void ICF::forEachClass(std::function<void(size_t, size_t)> fn) {
// If the number of sections are too small to use threading,
// call Fn sequentially.
- if (Chunks.size() < 1024) {
- forEachClassRange(0, Chunks.size(), Fn);
- ++Cnt;
+ if (chunks.size() < 1024) {
+ forEachClassRange(0, chunks.size(), fn);
+ ++cnt;
return;
}
@@ -221,97 +221,97 @@ void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
// The sharding must be completed before any calls to Fn are made
// so that Fn can modify the Chunks in its shard without causing data
// races.
- const size_t NumShards = 256;
- size_t Step = Chunks.size() / NumShards;
- size_t Boundaries[NumShards + 1];
- Boundaries[0] = 0;
- Boundaries[NumShards] = Chunks.size();
- parallelForEachN(1, NumShards, [&](size_t I) {
- Boundaries[I] = findBoundary((I - 1) * Step, Chunks.size());
+ const size_t numShards = 256;
+ size_t step = chunks.size() / numShards;
+ size_t boundaries[numShards + 1];
+ boundaries[0] = 0;
+ boundaries[numShards] = chunks.size();
+ parallelForEachN(1, numShards, [&](size_t i) {
+ boundaries[i] = findBoundary((i - 1) * step, chunks.size());
});
- parallelForEachN(1, NumShards + 1, [&](size_t I) {
- if (Boundaries[I - 1] < Boundaries[I]) {
- forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
+ parallelForEachN(1, numShards + 1, [&](size_t i) {
+ if (boundaries[i - 1] < boundaries[i]) {
+ forEachClassRange(boundaries[i - 1], boundaries[i], fn);
}
});
- ++Cnt;
+ ++cnt;
}
// Merge identical COMDAT sections.
// Two sections are considered the same if their section headers,
// contents and relocations are all the same.
-void ICF::run(ArrayRef<Chunk *> Vec) {
- ScopedTimer T(ICFTimer);
+void ICF::run(ArrayRef<Chunk *> vec) {
+ ScopedTimer t(icfTimer);
// Collect only mergeable sections and group by hash value.
- uint32_t NextId = 1;
- for (Chunk *C : Vec) {
- if (auto *SC = dyn_cast<SectionChunk>(C)) {
- if (isEligible(SC))
- Chunks.push_back(SC);
+ uint32_t nextId = 1;
+ for (Chunk *c : vec) {
+ if (auto *sc = dyn_cast<SectionChunk>(c)) {
+ if (isEligible(sc))
+ chunks.push_back(sc);
else
- SC->Class[0] = NextId++;
+ sc->eqClass[0] = nextId++;
}
}
// Make sure that ICF doesn't merge sections that are being handled by string
// tail merging.
- for (MergeChunk *MC : MergeChunk::Instances)
- if (MC)
- for (SectionChunk *SC : MC->Sections)
- SC->Class[0] = NextId++;
+ for (MergeChunk *mc : MergeChunk::instances)
+ if (mc)
+ for (SectionChunk *sc : mc->sections)
+ sc->eqClass[0] = nextId++;
// Initially, we use hash values to partition sections.
- parallelForEach(Chunks, [&](SectionChunk *SC) {
- SC->Class[0] = xxHash64(SC->getContents());
+ parallelForEach(chunks, [&](SectionChunk *sc) {
+ sc->eqClass[0] = xxHash64(sc->getContents());
});
// Combine the hashes of the sections referenced by each section into its
// hash.
- for (unsigned Cnt = 0; Cnt != 2; ++Cnt) {
- parallelForEach(Chunks, [&](SectionChunk *SC) {
- uint32_t Hash = SC->Class[Cnt % 2];
- for (Symbol *B : SC->symbols())
- if (auto *Sym = dyn_cast_or_null<DefinedRegular>(B))
- Hash += Sym->getChunk()->Class[Cnt % 2];
+ for (unsigned cnt = 0; cnt != 2; ++cnt) {
+ parallelForEach(chunks, [&](SectionChunk *sc) {
+ uint32_t hash = sc->eqClass[cnt % 2];
+ for (Symbol *b : sc->symbols())
+ if (auto *sym = dyn_cast_or_null<DefinedRegular>(b))
+ hash += sym->getChunk()->eqClass[cnt % 2];
// Set MSB to 1 to avoid collisions with non-hash classs.
- SC->Class[(Cnt + 1) % 2] = Hash | (1U << 31);
+ sc->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
});
}
// From now on, sections in Chunks are ordered so that sections in
// the same group are consecutive in the vector.
- llvm::stable_sort(Chunks, [](const SectionChunk *A, const SectionChunk *B) {
- return A->Class[0] < B->Class[0];
+ llvm::stable_sort(chunks, [](const SectionChunk *a, const SectionChunk *b) {
+ return a->eqClass[0] < b->eqClass[0];
});
// Compare static contents and assign unique IDs for each static content.
- forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
+ forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
// Split groups by comparing relocations until convergence is obtained.
do {
- Repeat = false;
+ repeat = false;
forEachClass(
- [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
- } while (Repeat);
+ [&](size_t begin, size_t end) { segregate(begin, end, false); });
+ } while (repeat);
- log("ICF needed " + Twine(Cnt) + " iterations");
+ log("ICF needed " + Twine(cnt) + " iterations");
// Merge sections in the same classs.
- forEachClass([&](size_t Begin, size_t End) {
- if (End - Begin == 1)
+ forEachClass([&](size_t begin, size_t end) {
+ if (end - begin == 1)
return;
- log("Selected " + Chunks[Begin]->getDebugName());
- for (size_t I = Begin + 1; I < End; ++I) {
- log(" Removed " + Chunks[I]->getDebugName());
- Chunks[Begin]->replace(Chunks[I]);
+ log("Selected " + chunks[begin]->getDebugName());
+ for (size_t i = begin + 1; i < end; ++i) {
+ log(" Removed " + chunks[i]->getDebugName());
+ chunks[begin]->replace(chunks[i]);
}
});
}
// Entry point to ICF.
-void doICF(ArrayRef<Chunk *> Chunks) { ICF().run(Chunks); }
+void doICF(ArrayRef<Chunk *> chunks) { ICF().run(chunks); }
} // namespace coff
} // namespace lld
OpenPOWER on IntegriCloud