1 //===- SectionPriorities.cpp ----------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
48 struct Cluster {  struct
49   Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {}  in Cluster()  function
62   Edge bestPred = {-1, 0};
72   std::vector<Cluster> clusters;
75 // Maximum amount the combined cluster density can be worse than the original
76 // cluster to consider merging.
85   auto getOrCreateCluster = [&](const InputSection *isec) -> int {  in CallGraphSort()
89       clusters.emplace_back(clusters.size(), isec->getSize());  in CallGraphSort()
91     return res.first->second;  in CallGraphSort()
96     const auto fromSec = c.first.first->canonical();  in CallGraphSort()
97     const auto toSec = c.first.second->canonical();  in CallGraphSort()
102     // output.  This messes with the cluster size and density calculations.  We  in CallGraphSort()
105     if (fromSec->parent != toSec->parent)  in CallGraphSort()
117     Cluster &toC = clusters[to];  in CallGraphSort()
118     if (toC.bestPred.from == -1 || toC.bestPred.weight < weight) {  in CallGraphSort()
123   for (Cluster &c : clusters)  in CallGraphSort()
128 static bool isNewDensityBad(Cluster &a, Cluster &b) {  in isNewDensityBad()
133 // Find the leader of V's belonged cluster (represented as an equivalence
134 // class). We apply union-find path-halving technique (simple to implement) in
144 static void mergeClusters(std::vector<Cluster> &cs, Cluster &into, int intoIdx,  in mergeClusters()
145                           Cluster &from, int fromIdx) {  in mergeClusters()
157 // Group InputSections into clusters using the Call-Chain Clustering heuristic
160   const uint64_t maxClusterSize = target->getPageSize();  in run()
162   // Cluster indices sorted by density.  in run()
164   // For union-find.  in run()
175     // The cluster index is the same as the index of its leader here because  in run()
176     // clusters[L] has not been merged into another cluster yet.  in run()
177     Cluster &c = clusters[l];  in run()
180     if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)  in run()
184     // Already in the same cluster.  in run()
188     Cluster *predC = &clusters[predL];  in run()
189     if (c.size + predC->size > maxClusterSize)  in run()
198   // Sort remaining non-empty clusters by density.  in run()
212   // order-file code.  in run()
216       orderMap[sections[i]] = curOrder--;  in run()
222   if (!config->printSymbolOrder.empty()) {  in run()
224     raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::OF_None);  in run()
226       error("cannot open " + config->printSymbolOrder + ": " + ec.message());  in run()
237         for (Symbol *sym : isec->getFile()->symbols) {  in run()
239             if (d->isec() == isec)  in run()
240               os << sym->getName() << "\n";  in run()
254   if (sym->isAbsolute())  in getSymbolPriority()
257   auto it = priorities.find(sym->getName());  in getSymbolPriority()
260   const SymbolPriorityEntry &entry = it->second;  in getSymbolPriority()
261   const InputFile *f = sym->isec()->getFile();  in getSymbolPriority()
267   if (f->archiveName.empty())  in getSymbolPriority()
268     filename = path::filename(f->getName());  in getSymbolPriority()
270     filename = saver().save(path::filename(f->archiveName) + "(" +  in getSymbolPriority()
271                             path::filename(f->getName()) + ")");  in getSymbolPriority()
282     for (const CallGraphEntry &entry : obj->callGraph) {  in extractCallGraphProfile()
283       assert(entry.fromIndex < obj->symbols.size() &&  in extractCallGraphProfile()
284              entry.toIndex < obj->symbols.size());  in extractCallGraphProfile()
285       auto *fromSym = dyn_cast_or_null<Defined>(obj->symbols[entry.fromIndex]);  in extractCallGraphProfile()
286       auto *toSym = dyn_cast_or_null<Defined>(obj->symbols[entry.toIndex]);  in extractCallGraphProfile()
290         callGraphProfile[{fromSym->isec(), toSym->isec()}] += entry.count;  in extractCallGraphProfile()
319     if (cpuType != CPU_TYPE_ANY && cpuType != target->cpuType)  in parseOrderFile()
331         objectFile = line.take_front(pos + fileEnd.size() - 1);  in parseOrderFile()
348     --highestAvailablePriority;  in parseOrderFile()
355   if (config->callGraphProfileSort) {  in buildInputSectionPriorities()
373     size_t &priority = sectionPriorities[sym->isec()];  in buildInputSectionPriorities()
380       for (Symbol *sym : file->symbols)  in buildInputSectionPriorities()