1 //===- bolt/Passes/ReorderSection.cpp - Reordering of section data --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements ReorderData class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 // TODO:
14 // - make sure writeable data isn't put on same cache line unless temporally
15 // local
16 // - estimate temporal locality by looking at CFG?
17 
18 #include "bolt/Passes/ReorderData.h"
19 #include <algorithm>
20 
21 #undef  DEBUG_TYPE
22 #define DEBUG_TYPE "reorder-data"
23 
24 using namespace llvm;
25 using namespace bolt;
26 
27 namespace opts {
28 extern cl::OptionCategory BoltCategory;
29 extern cl::OptionCategory BoltOptCategory;
30 extern cl::opt<JumpTableSupportLevel> JumpTables;
31 
32 static cl::opt<bool>
33 PrintReorderedData("print-reordered-data",
34   cl::desc("print section contents after reordering"),
35   cl::ZeroOrMore,
36   cl::Hidden,
37   cl::cat(BoltCategory));
38 
39 cl::list<std::string>
40 ReorderData("reorder-data",
41   cl::CommaSeparated,
42   cl::desc("list of sections to reorder"),
43   cl::value_desc("section1,section2,section3,..."),
44   cl::cat(BoltOptCategory));
45 
46 enum ReorderAlgo : char {
47   REORDER_COUNT         = 0,
48   REORDER_FUNCS         = 1
49 };
50 
51 static cl::opt<ReorderAlgo>
52 ReorderAlgorithm("reorder-data-algo",
53   cl::desc("algorithm used to reorder data sections"),
54   cl::init(REORDER_COUNT),
55   cl::values(
56     clEnumValN(REORDER_COUNT,
57       "count",
58       "sort hot data by read counts"),
59     clEnumValN(REORDER_FUNCS,
60       "funcs",
61       "sort hot data by hot function usage and count")),
62   cl::ZeroOrMore,
63   cl::cat(BoltOptCategory));
64 
65 static cl::opt<unsigned>
66 ReorderDataMaxSymbols("reorder-data-max-symbols",
67   cl::desc("maximum number of symbols to reorder"),
68   cl::ZeroOrMore,
69   cl::init(std::numeric_limits<unsigned>::max()),
70   cl::cat(BoltOptCategory));
71 
72 static cl::opt<unsigned>
73 ReorderDataMaxBytes("reorder-data-max-bytes",
74   cl::desc("maximum number of bytes to reorder"),
75   cl::ZeroOrMore,
76   cl::init(std::numeric_limits<unsigned>::max()),
77   cl::cat(BoltOptCategory));
78 
79 static cl::list<std::string>
80 ReorderSymbols("reorder-symbols",
81   cl::CommaSeparated,
82   cl::desc("list of symbol names that can be reordered"),
83   cl::value_desc("symbol1,symbol2,symbol3,..."),
84   cl::Hidden,
85   cl::cat(BoltCategory));
86 
87 static cl::list<std::string>
88 SkipSymbols("reorder-skip-symbols",
89   cl::CommaSeparated,
90   cl::desc("list of symbol names that cannot be reordered"),
91   cl::value_desc("symbol1,symbol2,symbol3,..."),
92   cl::Hidden,
93   cl::cat(BoltCategory));
94 
95 static cl::opt<bool>
96 ReorderInplace("reorder-data-inplace",
97   cl::desc("reorder data sections in place"),
98   cl::init(false),
99   cl::ZeroOrMore,
100   cl::cat(BoltOptCategory));
101 
102 }
103 
104 namespace llvm {
105 namespace bolt {
106 
107 namespace {
108 
109 static constexpr uint16_t MinAlignment = 16;
110 
111 bool isSupported(const BinarySection &BS) { return BS.isData() && !BS.isTLS(); }
112 
113 bool filterSymbol(const BinaryData *BD) {
114   if (!BD->isAtomic() || BD->isJumpTable() || !BD->isMoveable())
115     return false;
116 
117   bool IsValid = true;
118 
119   if (!opts::ReorderSymbols.empty()) {
120     IsValid = false;
121     for (const std::string &Name : opts::ReorderSymbols) {
122       if (BD->hasName(Name)) {
123         IsValid = true;
124         break;
125       }
126     }
127   }
128 
129   if (!IsValid)
130     return false;
131 
132   if (!opts::SkipSymbols.empty()) {
133     for (const std::string &Name : opts::SkipSymbols) {
134       if (BD->hasName(Name)) {
135         IsValid = false;
136         break;
137       }
138     }
139   }
140 
141   return IsValid;
142 }
143 
144 } // namespace
145 
146 using DataOrder = ReorderData::DataOrder;
147 
148 void ReorderData::printOrder(const BinarySection &Section,
149                              DataOrder::const_iterator Begin,
150                              DataOrder::const_iterator End) const {
151   uint64_t TotalSize = 0;
152   bool PrintHeader = false;
153   while (Begin != End) {
154     const BinaryData *BD = Begin->first;
155 
156     if (!PrintHeader) {
157       outs() << "BOLT-INFO: Hot global symbols for " << Section.getName()
158              << ":\n";
159       PrintHeader = true;
160     }
161 
162     outs() << "BOLT-INFO: " << *BD << ", moveable=" << BD->isMoveable()
163            << format(", weight=%.5f\n", double(Begin->second) / BD->getSize());
164 
165     TotalSize += BD->getSize();
166     ++Begin;
167   }
168   if (TotalSize)
169     outs() << "BOLT-INFO: Total hot symbol size = " << TotalSize << "\n";
170 }
171 
172 DataOrder ReorderData::baseOrder(BinaryContext &BC,
173                                  const BinarySection &Section) const {
174   DataOrder Order;
175   for (auto &Entry : BC.getBinaryDataForSection(Section)) {
176     BinaryData *BD = Entry.second;
177     if (!BD->isAtomic()) // skip sub-symbols
178       continue;
179     auto BDCI = BinaryDataCounts.find(BD);
180     uint64_t BDCount = BDCI == BinaryDataCounts.end() ? 0 : BDCI->second;
181     Order.emplace_back(BD, BDCount);
182   }
183   return Order;
184 }
185 
186 void ReorderData::assignMemData(BinaryContext &BC) {
187   // Map of sections (or heap/stack) to count/size.
188   StringMap<uint64_t> Counts;
189   StringMap<uint64_t> JumpTableCounts;
190   uint64_t TotalCount = 0;
191   for (auto &BFI : BC.getBinaryFunctions()) {
192     const BinaryFunction &BF = BFI.second;
193     if (!BF.hasMemoryProfile())
194       continue;
195 
196     for (const BinaryBasicBlock &BB : BF) {
197       for (const MCInst &Inst : BB) {
198         auto ErrorOrMemAccesssProfile =
199             BC.MIB->tryGetAnnotationAs<MemoryAccessProfile>(
200                 Inst, "MemoryAccessProfile");
201         if (!ErrorOrMemAccesssProfile)
202           continue;
203 
204         const MemoryAccessProfile &MemAccessProfile =
205             ErrorOrMemAccesssProfile.get();
206         for (const AddressAccess &AccessInfo :
207              MemAccessProfile.AddressAccessInfo) {
208           if (BinaryData *BD = AccessInfo.MemoryObject) {
209             BinaryDataCounts[BD->getAtomicRoot()] += AccessInfo.Count;
210             Counts[BD->getSectionName()] += AccessInfo.Count;
211             if (BD->getAtomicRoot()->isJumpTable())
212               JumpTableCounts[BD->getSectionName()] += AccessInfo.Count;
213           } else {
214             Counts["Heap/stack"] += AccessInfo.Count;
215           }
216           TotalCount += AccessInfo.Count;
217         }
218       }
219     }
220   }
221 
222   if (!Counts.empty()) {
223     outs() << "BOLT-INFO: Memory stats breakdown:\n";
224     for (StringMapEntry<uint64_t> &Entry : Counts) {
225       StringRef Section = Entry.first();
226       const uint64_t Count = Entry.second;
227       outs() << "BOLT-INFO:   " << Section << " = " << Count
228              << format(" (%.1f%%)\n", 100.0 * Count / TotalCount);
229       if (JumpTableCounts.count(Section) != 0) {
230         const uint64_t JTCount = JumpTableCounts[Section];
231         outs() << "BOLT-INFO:     jump tables = " << JTCount
232                << format(" (%.1f%%)\n", 100.0 * JTCount / Count);
233       }
234     }
235     outs() << "BOLT-INFO: Total memory events: " << TotalCount << "\n";
236   }
237 }
238 
239 /// Only consider moving data that is used by the hottest functions with
240 /// valid profiles.
241 std::pair<DataOrder, unsigned>
242 ReorderData::sortedByFunc(BinaryContext &BC, const BinarySection &Section,
243                           std::map<uint64_t, BinaryFunction> &BFs) const {
244   std::map<BinaryData *, std::set<BinaryFunction *>> BDtoFunc;
245   std::map<BinaryData *, uint64_t> BDtoFuncCount;
246 
247   auto dataUses = [&BC](const BinaryFunction &BF, bool OnlyHot) {
248     std::set<BinaryData *> Uses;
249     for (const BinaryBasicBlock &BB : BF) {
250       if (OnlyHot && BB.isCold())
251         continue;
252 
253       for (const MCInst &Inst : BB) {
254         auto ErrorOrMemAccesssProfile =
255             BC.MIB->tryGetAnnotationAs<MemoryAccessProfile>(
256                 Inst, "MemoryAccessProfile");
257         if (!ErrorOrMemAccesssProfile)
258           continue;
259 
260         const MemoryAccessProfile &MemAccessProfile =
261             ErrorOrMemAccesssProfile.get();
262         for (const AddressAccess &AccessInfo :
263              MemAccessProfile.AddressAccessInfo) {
264           if (AccessInfo.MemoryObject)
265             Uses.insert(AccessInfo.MemoryObject);
266         }
267       }
268     }
269     return Uses;
270   };
271 
272   for (auto &Entry : BFs) {
273     BinaryFunction &BF = Entry.second;
274     if (BF.hasValidProfile()) {
275       for (BinaryData *BD : dataUses(BF, true)) {
276         if (!BC.getFunctionForSymbol(BD->getSymbol())) {
277           BDtoFunc[BD->getAtomicRoot()].insert(&BF);
278           BDtoFuncCount[BD->getAtomicRoot()] += BF.getKnownExecutionCount();
279         }
280       }
281     }
282   }
283 
284   DataOrder Order = baseOrder(BC, Section);
285   unsigned SplitPoint = Order.size();
286 
287   std::sort(
288       Order.begin(), Order.end(),
289       [&](const DataOrder::value_type &A, const DataOrder::value_type &B) {
290         // Total execution counts of functions referencing BD.
291         const uint64_t ACount = BDtoFuncCount[A.first];
292         const uint64_t BCount = BDtoFuncCount[B.first];
293         // Weight by number of loads/data size.
294         const double AWeight = double(A.second) / A.first->getSize();
295         const double BWeight = double(B.second) / B.first->getSize();
296         return (ACount > BCount ||
297                 (ACount == BCount &&
298                  (AWeight > BWeight ||
299                   (AWeight == BWeight &&
300                    A.first->getAddress() < B.first->getAddress()))));
301       });
302 
303   for (unsigned Idx = 0; Idx < Order.size(); ++Idx) {
304     if (!BDtoFuncCount[Order[Idx].first]) {
305       SplitPoint = Idx;
306       break;
307     }
308   }
309 
310   return std::make_pair(Order, SplitPoint);
311 }
312 
313 std::pair<DataOrder, unsigned>
314 ReorderData::sortedByCount(BinaryContext &BC,
315                            const BinarySection &Section) const {
316   DataOrder Order = baseOrder(BC, Section);
317   unsigned SplitPoint = Order.size();
318 
319   std::sort(Order.begin(), Order.end(),
320             [](const DataOrder::value_type &A, const DataOrder::value_type &B) {
321               // Weight by number of loads/data size.
322               const double AWeight = double(A.second) / A.first->getSize();
323               const double BWeight = double(B.second) / B.first->getSize();
324               return (AWeight > BWeight ||
325                       (AWeight == BWeight &&
326                        (A.first->getSize() < B.first->getSize() ||
327                         (A.first->getSize() == B.first->getSize() &&
328                          A.first->getAddress() < B.first->getAddress()))));
329             });
330 
331   for (unsigned Idx = 0; Idx < Order.size(); ++Idx) {
332     if (!Order[Idx].second) {
333       SplitPoint = Idx;
334       break;
335     }
336   }
337 
338   return std::make_pair(Order, SplitPoint);
339 }
340 
341 // TODO
342 // add option for cache-line alignment (or just use cache-line when section
343 // is writeable)?
344 void ReorderData::setSectionOrder(BinaryContext &BC,
345                                   BinarySection &OutputSection,
346                                   DataOrder::iterator Begin,
347                                   DataOrder::iterator End) {
348   std::vector<BinaryData *> NewOrder;
349   unsigned NumReordered = 0;
350   uint64_t Offset = 0;
351   uint64_t Count = 0;
352 
353   // Get the total count just for stats
354   uint64_t TotalCount = 0;
355   for (auto Itr = Begin; Itr != End; ++Itr)
356     TotalCount += Itr->second;
357 
358   LLVM_DEBUG(dbgs() << "BOLT-DEBUG: setSectionOrder for "
359                     << OutputSection.getName() << "\n");
360 
361   for (; Begin != End; ++Begin) {
362     BinaryData *BD = Begin->first;
363 
364     // We can't move certain symbols.
365     if (!filterSymbol(BD))
366       continue;
367 
368     ++NumReordered;
369     if (NumReordered > opts::ReorderDataMaxSymbols) {
370       if (!NewOrder.empty())
371         LLVM_DEBUG(dbgs() << "BOLT-DEBUG: processing ending on symbol "
372                           << *NewOrder.back() << "\n");
373       break;
374     }
375 
376     uint16_t Alignment = std::max(BD->getAlignment(), MinAlignment);
377     Offset = alignTo(Offset, Alignment);
378 
379     if ((Offset + BD->getSize()) > opts::ReorderDataMaxBytes) {
380       if (!NewOrder.empty())
381         LLVM_DEBUG(dbgs() << "BOLT-DEBUG: processing ending on symbol "
382                           << *NewOrder.back() << "\n");
383       break;
384     }
385 
386     LLVM_DEBUG(dbgs() << "BOLT-DEBUG: " << BD->getName() << " @ 0x"
387                       << Twine::utohexstr(Offset) << "\n");
388 
389     BD->setOutputLocation(OutputSection, Offset);
390 
391     // reorder sub-symbols
392     for (std::pair<const uint64_t, BinaryData *> &SubBD :
393          BC.getSubBinaryData(BD)) {
394       if (!SubBD.second->isJumpTable()) {
395         uint64_t SubOffset =
396             Offset + SubBD.second->getAddress() - BD->getAddress();
397         LLVM_DEBUG(dbgs() << "BOLT-DEBUG: SubBD " << SubBD.second->getName()
398                           << " @ " << SubOffset << "\n");
399         SubBD.second->setOutputLocation(OutputSection, SubOffset);
400       }
401     }
402 
403     Offset += BD->getSize();
404     Count += Begin->second;
405     NewOrder.push_back(BD);
406   }
407 
408   OutputSection.reorderContents(NewOrder, opts::ReorderInplace);
409 
410   outs() << "BOLT-INFO: reorder-data: " << Count << "/" << TotalCount
411          << format(" (%.1f%%)", 100.0 * Count / TotalCount) << " events, "
412          << Offset << " hot bytes\n";
413 }
414 
415 bool ReorderData::markUnmoveableSymbols(BinaryContext &BC,
416                                         BinarySection &Section) const {
417   // Private symbols currently can't be moved because data can "leak" across
418   // the boundary of one symbol to the next, e.g. a string that has a common
419   // suffix might start in one private symbol and end with the common
420   // suffix in another.
421   auto isPrivate = [&](const BinaryData *BD) {
422     auto Prefix = std::string("PG") + BC.AsmInfo->getPrivateGlobalPrefix();
423     return BD->getName().startswith(Prefix.str());
424   };
425   auto Range = BC.getBinaryDataForSection(Section);
426   bool FoundUnmoveable = false;
427   for (auto Itr = Range.begin(); Itr != Range.end(); ++Itr) {
428     if (Itr->second->getName().startswith("PG.")) {
429       BinaryData *Prev =
430           Itr != Range.begin() ? std::prev(Itr)->second : nullptr;
431       BinaryData *Next = Itr != Range.end() ? std::next(Itr)->second : nullptr;
432       bool PrevIsPrivate = Prev && isPrivate(Prev);
433       bool NextIsPrivate = Next && isPrivate(Next);
434       if (isPrivate(Itr->second) && (PrevIsPrivate || NextIsPrivate))
435         Itr->second->setIsMoveable(false);
436     } else {
437       // check for overlapping symbols.
438       BinaryData *Next = Itr != Range.end() ? std::next(Itr)->second : nullptr;
439       if (Next && Itr->second->getEndAddress() != Next->getAddress() &&
440           Next->containsAddress(Itr->second->getEndAddress())) {
441         Itr->second->setIsMoveable(false);
442         Next->setIsMoveable(false);
443       }
444     }
445     FoundUnmoveable |= !Itr->second->isMoveable();
446   }
447   return FoundUnmoveable;
448 }
449 
450 void ReorderData::runOnFunctions(BinaryContext &BC) {
451   static const char *DefaultSections[] = {".rodata", ".data", ".bss", nullptr};
452 
453   if (!BC.HasRelocations || opts::ReorderData.empty())
454     return;
455 
456   // For now
457   if (opts::JumpTables > JTS_BASIC) {
458     outs() << "BOLT-WARNING: jump table support must be basic for "
459            << "data reordering to work.\n";
460     return;
461   }
462 
463   assignMemData(BC);
464 
465   std::vector<BinarySection *> Sections;
466 
467   for (const std::string &SectionName : opts::ReorderData) {
468     if (SectionName == "default") {
469       for (unsigned I = 0; DefaultSections[I]; ++I)
470         if (ErrorOr<BinarySection &> Section =
471                 BC.getUniqueSectionByName(DefaultSections[I]))
472           Sections.push_back(&*Section);
473       continue;
474     }
475 
476     ErrorOr<BinarySection &> Section = BC.getUniqueSectionByName(SectionName);
477     if (!Section) {
478       outs() << "BOLT-WARNING: Section " << SectionName
479              << " not found, skipping.\n";
480       continue;
481     }
482 
483     if (!isSupported(*Section)) {
484       outs() << "BOLT-ERROR: Section " << SectionName << " not supported.\n";
485       exit(1);
486     }
487 
488     Sections.push_back(&*Section);
489   }
490 
491   for (BinarySection *Section : Sections) {
492     const bool FoundUnmoveable = markUnmoveableSymbols(BC, *Section);
493 
494     DataOrder Order;
495     unsigned SplitPointIdx;
496 
497     if (opts::ReorderAlgorithm == opts::ReorderAlgo::REORDER_COUNT) {
498       outs() << "BOLT-INFO: reorder-sections: ordering data by count\n";
499       std::tie(Order, SplitPointIdx) = sortedByCount(BC, *Section);
500     } else {
501       outs() << "BOLT-INFO: reorder-sections: ordering data by funcs\n";
502       std::tie(Order, SplitPointIdx) =
503           sortedByFunc(BC, *Section, BC.getBinaryFunctions());
504     }
505     auto SplitPoint = Order.begin() + SplitPointIdx;
506 
507     if (opts::PrintReorderedData)
508       printOrder(*Section, Order.begin(), SplitPoint);
509 
510     if (!opts::ReorderInplace || FoundUnmoveable) {
511       if (opts::ReorderInplace && FoundUnmoveable)
512         outs() << "BOLT-INFO: Found unmoveable symbols in "
513                << Section->getName() << " falling back to splitting "
514                << "instead of in-place reordering.\n";
515 
516       // Copy original section to <section name>.cold.
517       BinarySection &Cold = BC.registerSection(
518           std::string(Section->getName()) + ".cold", *Section);
519 
520       // Reorder contents of original section.
521       setSectionOrder(BC, *Section, Order.begin(), SplitPoint);
522 
523       // This keeps the original data from thinking it has been moved.
524       for (std::pair<const uint64_t, BinaryData *> &Entry :
525            BC.getBinaryDataForSection(*Section)) {
526         if (!Entry.second->isMoved()) {
527           Entry.second->setSection(Cold);
528           Entry.second->setOutputSection(Cold);
529         }
530       }
531     } else {
532       outs() << "BOLT-WARNING: Inplace section reordering not supported yet.\n";
533       setSectionOrder(BC, *Section, Order.begin(), Order.end());
534     }
535   }
536 }
537 
538 } // namespace bolt
539 } // namespace llvm
540