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