bolt/lib/Passes/IdenticalCodeFolding.cpp

   1 //===- bolt/Passes/IdenticalCodeFolding.cpp -------------------------------===//
   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 the IdenticalCodeFolding class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/IdenticalCodeFolding.h"
  14 #include "bolt/Core/HashUtilities.h"
  15 #include "bolt/Core/ParallelUtilities.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/Support/CommandLine.h"
  18 #include "llvm/Support/ThreadPool.h"
  19 #include "llvm/Support/Timer.h"
  20 #include <atomic>
  21 #include <iterator>
  22 #include <map>
  23 #include <set>
  24 #include <unordered_map>
  25
  26 #define DEBUG_TYPE "bolt-icf"
  27
  28 using namespace llvm;
  29 using namespace bolt;
  30
  31 namespace opts {
  32
  33 extern cl::OptionCategory BoltOptCategory;
  34
  35 static cl::opt<bool>
  36     ICFUseDFS("icf-dfs", cl::desc("use DFS ordering when using -icf option"),
  37               cl::ReallyHidden, cl::cat(BoltOptCategory));
  38
  39 static cl::opt<bool>
  40 TimeICF("time-icf",
  41   cl::desc("time icf steps"),
  42   cl::ReallyHidden,
  43   cl::ZeroOrMore,
  44   cl::cat(BoltOptCategory));
  45 } // namespace opts
  46
  47 /// Compare two jump tables in 2 functions. The function relies on consistent
  48 /// ordering of basic blocks in both binary functions (e.g. DFS).
  49 static bool equalJumpTables(const JumpTable &JumpTableA,
  50                             const JumpTable &JumpTableB,
  51                             const BinaryFunction &FunctionA,
  52                             const BinaryFunction &FunctionB) {
  53   if (JumpTableA.EntrySize != JumpTableB.EntrySize)
  54     return false;
  55
  56   if (JumpTableA.Type != JumpTableB.Type)
  57     return false;
  58
  59   if (JumpTableA.getSize() != JumpTableB.getSize())
  60     return false;
  61
  62   for (uint64_t Index = 0; Index < JumpTableA.Entries.size(); ++Index) {
  63     const MCSymbol *LabelA = JumpTableA.Entries[Index];
  64     const MCSymbol *LabelB = JumpTableB.Entries[Index];
  65
  66     const BinaryBasicBlock *TargetA = FunctionA.getBasicBlockForLabel(LabelA);
  67     const BinaryBasicBlock *TargetB = FunctionB.getBasicBlockForLabel(LabelB);
  68
  69     if (!TargetA || !TargetB) {
  70       assert((TargetA || LabelA == FunctionA.getFunctionEndLabel()) &&
  71              "no target basic block found");
  72       assert((TargetB || LabelB == FunctionB.getFunctionEndLabel()) &&
  73              "no target basic block found");
  74
  75       if (TargetA != TargetB)
  76         return false;
  77
  78       continue;
  79     }
  80
  81     assert(TargetA && TargetB && "cannot locate target block(s)");
  82
  83     if (TargetA->getLayoutIndex() != TargetB->getLayoutIndex())
  84       return false;
  85   }
  86
  87   return true;
  88 }
  89
  90 /// Helper function that compares an instruction of this function to the
  91 /// given instruction of the given function. The functions should have
  92 /// identical CFG.
  93 template <class Compare>
  94 static bool isInstrEquivalentWith(const MCInst &InstA,
  95                                   const BinaryBasicBlock &BBA,
  96                                   const MCInst &InstB,
  97                                   const BinaryBasicBlock &BBB, Compare Comp) {
  98   if (InstA.getOpcode() != InstB.getOpcode())
  99     return false;
 100
 101   const BinaryContext &BC = BBA.getFunction()->getBinaryContext();
 102
 103   // In this function we check for special conditions:
 104   //
 105   //    * instructions with landing pads
 106   //
 107   // Most of the common cases should be handled by MCPlus::equals()
 108   // that compares regular instruction operands.
 109   //
 110   // NB: there's no need to compare jump table indirect jump instructions
 111   //     separately as jump tables are handled by comparing corresponding
 112   //     symbols.
 113   const std::optional<MCPlus::MCLandingPad> EHInfoA = BC.MIB->getEHInfo(InstA);
 114   const std::optional<MCPlus::MCLandingPad> EHInfoB = BC.MIB->getEHInfo(InstB);
 115
 116   if (EHInfoA || EHInfoB) {
 117     if (!EHInfoA && (EHInfoB->first || EHInfoB->second))
 118       return false;
 119
 120     if (!EHInfoB && (EHInfoA->first || EHInfoA->second))
 121       return false;
 122
 123     if (EHInfoA && EHInfoB) {
 124       // Action indices should match.
 125       if (EHInfoA->second != EHInfoB->second)
 126         return false;
 127
 128       if (!EHInfoA->first != !EHInfoB->first)
 129         return false;
 130
 131       if (EHInfoA->first && EHInfoB->first) {
 132         const BinaryBasicBlock *LPA = BBA.getLandingPad(EHInfoA->first);
 133         const BinaryBasicBlock *LPB = BBB.getLandingPad(EHInfoB->first);
 134         assert(LPA && LPB && "cannot locate landing pad(s)");
 135
 136         if (LPA->getLayoutIndex() != LPB->getLayoutIndex())
 137           return false;
 138       }
 139     }
 140   }
 141
 142   return BC.MIB->equals(InstA, InstB, Comp);
 143 }
 144
 145 /// Returns true if this function has identical code and CFG with
 146 /// the given function \p BF.
 147 ///
 148 /// If \p CongruentSymbols is set to true, then symbolic operands that reference
 149 /// potentially identical but different functions are ignored during the
 150 /// comparison.
 151 static bool isIdenticalWith(const BinaryFunction &A, const BinaryFunction &B,
 152                             bool CongruentSymbols) {
 153   assert(A.hasCFG() && B.hasCFG() && "both functions should have CFG");
 154
 155   // Compare the two functions, one basic block at a time.
 156   // Currently we require two identical basic blocks to have identical
 157   // instruction sequences and the same index in their corresponding
 158   // functions. The latter is important for CFG equality.
 159
 160   if (A.getLayout().block_size() != B.getLayout().block_size())
 161     return false;
 162
 163   // Comparing multi-entry functions could be non-trivial.
 164   if (A.isMultiEntry() || B.isMultiEntry())
 165     return false;
 166
 167   if (A.hasIslandsInfo() || B.hasIslandsInfo())
 168     return false;
 169
 170   // Process both functions in either DFS or existing order.
 171   SmallVector<const BinaryBasicBlock *, 0> OrderA;
 172   SmallVector<const BinaryBasicBlock *, 0> OrderB;
 173   if (opts::ICFUseDFS) {
 174     copy(A.dfs(), std::back_inserter(OrderA));
 175     copy(B.dfs(), std::back_inserter(OrderB));
 176   } else {
 177     copy(A.getLayout().blocks(), std::back_inserter(OrderA));
 178     copy(B.getLayout().blocks(), std::back_inserter(OrderB));
 179   }
 180
 181   const BinaryContext &BC = A.getBinaryContext();
 182
 183   auto BBI = OrderB.begin();
 184   for (const BinaryBasicBlock *BB : OrderA) {
 185     const BinaryBasicBlock *OtherBB = *BBI;
 186
 187     if (BB->getLayoutIndex() != OtherBB->getLayoutIndex())
 188       return false;
 189
 190     // Compare successor basic blocks.
 191     // NOTE: the comparison for jump tables is only partially verified here.
 192     if (BB->succ_size() != OtherBB->succ_size())
 193       return false;
 194
 195     auto SuccBBI = OtherBB->succ_begin();
 196     for (const BinaryBasicBlock *SuccBB : BB->successors()) {
 197       const BinaryBasicBlock *SuccOtherBB = *SuccBBI;
 198       if (SuccBB->getLayoutIndex() != SuccOtherBB->getLayoutIndex())
 199         return false;
 200       ++SuccBBI;
 201     }
 202
 203     // Compare all instructions including pseudos.
 204     auto I = BB->begin(), E = BB->end();
 205     auto OtherI = OtherBB->begin(), OtherE = OtherBB->end();
 206     while (I != E && OtherI != OtherE) {
 207       // Compare symbols.
 208       auto AreSymbolsIdentical = [&](const MCSymbol *SymbolA,
 209                                      const MCSymbol *SymbolB) {
 210         if (SymbolA == SymbolB)
 211           return true;
 212
 213         // All local symbols are considered identical since they affect a
 214         // control flow and we check the control flow separately.
 215         // If a local symbol is escaped, then the function (potentially) has
 216         // multiple entry points and we exclude such functions from
 217         // comparison.
 218         if (SymbolA->isTemporary() && SymbolB->isTemporary())
 219           return true;
 220
 221         // Compare symbols as functions.
 222         uint64_t EntryIDA = 0;
 223         uint64_t EntryIDB = 0;
 224         const BinaryFunction *FunctionA =
 225             BC.getFunctionForSymbol(SymbolA, &EntryIDA);
 226         const BinaryFunction *FunctionB =
 227             BC.getFunctionForSymbol(SymbolB, &EntryIDB);
 228         if (FunctionA && EntryIDA)
 229           FunctionA = nullptr;
 230         if (FunctionB && EntryIDB)
 231           FunctionB = nullptr;
 232         if (FunctionA && FunctionB) {
 233           // Self-referencing functions and recursive calls.
 234           if (FunctionA == &A && FunctionB == &B)
 235             return true;
 236
 237           // Functions with different hash values can never become identical,
 238           // hence A and B are different.
 239           if (CongruentSymbols)
 240             return FunctionA->getHash() == FunctionB->getHash();
 241
 242           return FunctionA == FunctionB;
 243         }
 244
 245         // One of the symbols represents a function, the other one does not.
 246         if (FunctionA != FunctionB)
 247           return false;
 248
 249         // Check if symbols are jump tables.
 250         const BinaryData *SIA = BC.getBinaryDataByName(SymbolA->getName());
 251         if (!SIA)
 252           return false;
 253         const BinaryData *SIB = BC.getBinaryDataByName(SymbolB->getName());
 254         if (!SIB)
 255           return false;
 256
 257         assert((SIA->getAddress() != SIB->getAddress()) &&
 258                "different symbols should not have the same value");
 259
 260         const JumpTable *JumpTableA =
 261             A.getJumpTableContainingAddress(SIA->getAddress());
 262         if (!JumpTableA)
 263           return false;
 264
 265         const JumpTable *JumpTableB =
 266             B.getJumpTableContainingAddress(SIB->getAddress());
 267         if (!JumpTableB)
 268           return false;
 269
 270         if ((SIA->getAddress() - JumpTableA->getAddress()) !=
 271             (SIB->getAddress() - JumpTableB->getAddress()))
 272           return false;
 273
 274         return equalJumpTables(*JumpTableA, *JumpTableB, A, B);
 275       };
 276
 277       if (!isInstrEquivalentWith(*I, *BB, *OtherI, *OtherBB,
 278                                  AreSymbolsIdentical))
 279         return false;
 280
 281       ++I;
 282       ++OtherI;
 283     }
 284
 285     // One of the identical blocks may have a trailing unconditional jump that
 286     // is ignored for CFG purposes.
 287     const MCInst *TrailingInstr =
 288         (I != E ? &(*I) : (OtherI != OtherE ? &(*OtherI) : nullptr));
 289     if (TrailingInstr && !BC.MIB->isUnconditionalBranch(*TrailingInstr))
 290       return false;
 291
 292     ++BBI;
 293   }
 294
 295   // Compare exceptions action tables.
 296   if (A.getLSDAActionTable() != B.getLSDAActionTable() ||
 297       A.getLSDATypeTable() != B.getLSDATypeTable() ||
 298       A.getLSDATypeIndexTable() != B.getLSDATypeIndexTable())
 299     return false;
 300
 301   return true;
 302 }
 303
 304 // This hash table is used to identify identical functions. It maps
 305 // a function to a bucket of functions identical to it.
 306 struct KeyHash {
 307   size_t operator()(const BinaryFunction *F) const { return F->getHash(); }
 308 };
 309
 310 /// Identify two congruent functions. Two functions are considered congruent,
 311 /// if they are identical/equal except for some of their instruction operands
 312 /// that reference potentially identical functions, i.e. functions that could
 313 /// be folded later. Congruent functions are candidates for folding in our
 314 /// iterative ICF algorithm.
 315 ///
 316 /// Congruent functions are required to have identical hash.
 317 struct KeyCongruent {
 318   bool operator()(const BinaryFunction *A, const BinaryFunction *B) const {
 319     if (A == B)
 320       return true;
 321     return isIdenticalWith(*A, *B, /*CongruentSymbols=*/true);
 322   }
 323 };
 324
 325 struct KeyEqual {
 326   bool operator()(const BinaryFunction *A, const BinaryFunction *B) const {
 327     if (A == B)
 328       return true;
 329     return isIdenticalWith(*A, *B, /*CongruentSymbols=*/false);
 330   }
 331 };
 332
 333 typedef std::unordered_map<BinaryFunction *, std::set<BinaryFunction *>,
 334                            KeyHash, KeyCongruent>
 335     CongruentBucketsMap;
 336
 337 typedef std::unordered_map<BinaryFunction *, std::vector<BinaryFunction *>,
 338                            KeyHash, KeyEqual>
 339     IdenticalBucketsMap;
 340
 341 namespace llvm {
 342 namespace bolt {
 343
 344 Error IdenticalCodeFolding::runOnFunctions(BinaryContext &BC) {
 345   const size_t OriginalFunctionCount = BC.getBinaryFunctions().size();
 346   uint64_t NumFunctionsFolded = 0;
 347   std::atomic<uint64_t> NumJTFunctionsFolded{0};
 348   std::atomic<uint64_t> BytesSavedEstimate{0};
 349   std::atomic<uint64_t> NumCalled{0};
 350   std::atomic<uint64_t> NumFoldedLastIteration{0};
 351   CongruentBucketsMap CongruentBuckets;
 352
 353   // Hash all the functions
 354   auto hashFunctions = [&]() {
 355     NamedRegionTimer HashFunctionsTimer("hashing", "hashing", "ICF breakdown",
 356                                         "ICF breakdown", opts::TimeICF);
 357     ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
 358       // Make sure indices are in-order.
 359       if (opts::ICFUseDFS)
 360         BF.getLayout().updateLayoutIndices(BF.dfs());
 361       else
 362         BF.getLayout().updateLayoutIndices();
 363
 364       // Pre-compute hash before pushing into hashtable.
 365       // Hash instruction operands to minimize hash collisions.
 366       BF.computeHash(
 367           opts::ICFUseDFS, HashFunction::Default,
 368           [&BC](const MCOperand &Op) { return hashInstOperand(BC, Op); });
 369     };
 370
 371     ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
 372       return !shouldOptimize(BF);
 373     };
 374
 375     ParallelUtilities::runOnEachFunction(
 376         BC, ParallelUtilities::SchedulingPolicy::SP_TRIVIAL, WorkFun, SkipFunc,
 377         "hashFunctions", /*ForceSequential*/ false, 2);
 378   };
 379
 380   // Creates buckets with congruent functions - functions that potentially
 381   // could  be folded.
 382   auto createCongruentBuckets = [&]() {
 383     NamedRegionTimer CongruentBucketsTimer("congruent buckets",
 384                                            "congruent buckets", "ICF breakdown",
 385                                            "ICF breakdown", opts::TimeICF);
 386     for (auto &BFI : BC.getBinaryFunctions()) {
 387       BinaryFunction &BF = BFI.second;
 388       if (!this->shouldOptimize(BF))
 389         continue;
 390       CongruentBuckets[&BF].emplace(&BF);
 391     }
 392   };
 393
 394   // Partition each set of congruent functions into sets of identical functions
 395   // and fold them
 396   auto performFoldingPass = [&]() {
 397     NamedRegionTimer FoldingPassesTimer("folding passes", "folding passes",
 398                                         "ICF breakdown", "ICF breakdown",
 399                                         opts::TimeICF);
 400     Timer SinglePass("single fold pass", "single fold pass");
 401     LLVM_DEBUG(SinglePass.startTimer());
 402
 403     ThreadPoolInterface *ThPool;
 404     if (!opts::NoThreads)
 405       ThPool = &ParallelUtilities::getThreadPool();
 406
 407     // Fold identical functions within a single congruent bucket
 408     auto processSingleBucket = [&](std::set<BinaryFunction *> &Candidates) {
 409       Timer T("folding single congruent list", "folding single congruent list");
 410       LLVM_DEBUG(T.startTimer());
 411
 412       // Identical functions go into the same bucket.
 413       IdenticalBucketsMap IdenticalBuckets;
 414       for (BinaryFunction *BF : Candidates) {
 415         IdenticalBuckets[BF].emplace_back(BF);
 416       }
 417
 418       for (auto &IBI : IdenticalBuckets) {
 419         // Functions identified as identical.
 420         std::vector<BinaryFunction *> &Twins = IBI.second;
 421         if (Twins.size() < 2)
 422           continue;
 423
 424         // Fold functions. Keep the order consistent across invocations with
 425         // different options.
 426         llvm::stable_sort(
 427             Twins, [](const BinaryFunction *A, const BinaryFunction *B) {
 428               return A->getFunctionNumber() < B->getFunctionNumber();
 429             });
 430
 431         BinaryFunction *ParentBF = Twins[0];
 432         if (!ParentBF->hasFunctionsFoldedInto())
 433           NumCalled += ParentBF->getKnownExecutionCount();
 434         for (unsigned I = 1; I < Twins.size(); ++I) {
 435           BinaryFunction *ChildBF = Twins[I];
 436           LLVM_DEBUG(dbgs() << "BOLT-DEBUG: folding " << *ChildBF << " into "
 437                             << *ParentBF << '\n');
 438
 439           // Remove child function from the list of candidates.
 440           auto FI = Candidates.find(ChildBF);
 441           assert(FI != Candidates.end() &&
 442                  "function expected to be in the set");
 443           Candidates.erase(FI);
 444
 445           // Fold the function and remove from the list of processed functions.
 446           BytesSavedEstimate += ChildBF->getSize();
 447           if (!ChildBF->hasFunctionsFoldedInto())
 448             NumCalled += ChildBF->getKnownExecutionCount();
 449           BC.foldFunction(*ChildBF, *ParentBF);
 450
 451           ++NumFoldedLastIteration;
 452
 453           if (ParentBF->hasJumpTables())
 454             ++NumJTFunctionsFolded;
 455         }
 456       }
 457
 458       LLVM_DEBUG(T.stopTimer());
 459     };
 460
 461     // Create a task for each congruent bucket
 462     for (auto &Entry : CongruentBuckets) {
 463       std::set<BinaryFunction *> &Bucket = Entry.second;
 464       if (Bucket.size() < 2)
 465         continue;
 466
 467       if (opts::NoThreads)
 468         processSingleBucket(Bucket);
 469       else
 470         ThPool->async(processSingleBucket, std::ref(Bucket));
 471     }
 472
 473     if (!opts::NoThreads)
 474       ThPool->wait();
 475
 476     LLVM_DEBUG(SinglePass.stopTimer());
 477   };
 478
 479   hashFunctions();
 480   createCongruentBuckets();
 481
 482   unsigned Iteration = 1;
 483   // We repeat the pass until no new modifications happen.
 484   do {
 485     NumFoldedLastIteration = 0;
 486     LLVM_DEBUG(dbgs() << "BOLT-DEBUG: ICF iteration " << Iteration << "...\n");
 487
 488     performFoldingPass();
 489
 490     NumFunctionsFolded += NumFoldedLastIteration;
 491     ++Iteration;
 492
 493   } while (NumFoldedLastIteration > 0);
 494
 495   LLVM_DEBUG({
 496     // Print functions that are congruent but not identical.
 497     for (auto &CBI : CongruentBuckets) {
 498       std::set<BinaryFunction *> &Candidates = CBI.second;
 499       if (Candidates.size() < 2)
 500         continue;
 501       dbgs() << "BOLT-DEBUG: the following " << Candidates.size()
 502              << " functions (each of size " << (*Candidates.begin())->getSize()
 503              << " bytes) are congruent but not identical:\n";
 504       for (BinaryFunction *BF : Candidates) {
 505         dbgs() << "  " << *BF;
 506         if (BF->getKnownExecutionCount())
 507           dbgs() << " (executed " << BF->getKnownExecutionCount() << " times)";
 508         dbgs() << '\n';
 509       }
 510     }
 511   });
 512
 513   if (NumFunctionsFolded)
 514     BC.outs() << "BOLT-INFO: ICF folded " << NumFunctionsFolded << " out of "
 515               << OriginalFunctionCount << " functions in " << Iteration
 516               << " passes. " << NumJTFunctionsFolded
 517               << " functions had jump tables.\n"
 518               << "BOLT-INFO: Removing all identical functions will save "
 519               << format("%.2lf", (double)BytesSavedEstimate / 1024)
 520               << " KB of code space. Folded functions were called " << NumCalled
 521               << " times based on profile.\n";
 522
 523   return Error::success();
 524 }
 525
 526 } // namespace bolt
 527 } // namespace llvm