1 //===- MergeICmps.cpp - Optimize chains of integer comparisons ------------===// 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 pass turns chains of integer comparisons into memcmp (the memcmp is 10 // later typically inlined as a chain of efficient hardware comparisons). This 11 // typically benefits c++ member or nonmember operator==(). 12 // 13 // The basic idea is to replace a longer chain of integer comparisons loaded 14 // from contiguous memory locations into a shorter chain of larger integer 15 // comparisons. Benefits are double: 16 // - There are less jumps, and therefore less opportunities for mispredictions 17 // and I-cache misses. 18 // - Code size is smaller, both because jumps are removed and because the 19 // encoding of a 2*n byte compare is smaller than that of two n-byte 20 // compares. 21 // 22 // Example: 23 // 24 // struct S { 25 // int a; 26 // char b; 27 // char c; 28 // uint16_t d; 29 // bool operator==(const S& o) const { 30 // return a == o.a && b == o.b && c == o.c && d == o.d; 31 // } 32 // }; 33 // 34 // Is optimized as : 35 // 36 // bool S::operator==(const S& o) const { 37 // return memcmp(this, &o, 8) == 0; 38 // } 39 // 40 // Which will later be expanded (ExpandMemCmp) as a single 8-bytes icmp. 41 // 42 //===----------------------------------------------------------------------===// 43 44 #include "llvm/Transforms/Scalar/MergeICmps.h" 45 #include "llvm/Analysis/DomTreeUpdater.h" 46 #include "llvm/Analysis/GlobalsModRef.h" 47 #include "llvm/Analysis/Loads.h" 48 #include "llvm/Analysis/TargetLibraryInfo.h" 49 #include "llvm/Analysis/TargetTransformInfo.h" 50 #include "llvm/IR/Dominators.h" 51 #include "llvm/IR/Function.h" 52 #include "llvm/IR/IRBuilder.h" 53 #include "llvm/InitializePasses.h" 54 #include "llvm/Pass.h" 55 #include "llvm/Transforms/Scalar.h" 56 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 57 #include "llvm/Transforms/Utils/BuildLibCalls.h" 58 #include <algorithm> 59 #include <numeric> 60 #include <utility> 61 #include <vector> 62 63 using namespace llvm; 64 65 namespace { 66 67 #define DEBUG_TYPE "mergeicmps" 68 69 // Returns true if the instruction is a simple load or a simple store 70 static bool isSimpleLoadOrStore(const Instruction *I) { 71 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) 72 return LI->isSimple(); 73 if (const StoreInst *SI = dyn_cast<StoreInst>(I)) 74 return SI->isSimple(); 75 return false; 76 } 77 78 // A BCE atom "Binary Compare Expression Atom" represents an integer load 79 // that is a constant offset from a base value, e.g. `a` or `o.c` in the example 80 // at the top. 81 struct BCEAtom { 82 BCEAtom() = default; 83 BCEAtom(GetElementPtrInst *GEP, LoadInst *LoadI, int BaseId, APInt Offset) 84 : GEP(GEP), LoadI(LoadI), BaseId(BaseId), Offset(Offset) {} 85 86 BCEAtom(const BCEAtom &) = delete; 87 BCEAtom &operator=(const BCEAtom &) = delete; 88 89 BCEAtom(BCEAtom &&that) = default; 90 BCEAtom &operator=(BCEAtom &&that) { 91 if (this == &that) 92 return *this; 93 GEP = that.GEP; 94 LoadI = that.LoadI; 95 BaseId = that.BaseId; 96 Offset = std::move(that.Offset); 97 return *this; 98 } 99 100 // We want to order BCEAtoms by (Base, Offset). However we cannot use 101 // the pointer values for Base because these are non-deterministic. 102 // To make sure that the sort order is stable, we first assign to each atom 103 // base value an index based on its order of appearance in the chain of 104 // comparisons. We call this index `BaseOrdering`. For example, for: 105 // b[3] == c[2] && a[1] == d[1] && b[4] == c[3] 106 // | block 1 | | block 2 | | block 3 | 107 // b gets assigned index 0 and a index 1, because b appears as LHS in block 1, 108 // which is before block 2. 109 // We then sort by (BaseOrdering[LHS.Base()], LHS.Offset), which is stable. 110 bool operator<(const BCEAtom &O) const { 111 return BaseId != O.BaseId ? BaseId < O.BaseId : Offset.slt(O.Offset); 112 } 113 114 GetElementPtrInst *GEP = nullptr; 115 LoadInst *LoadI = nullptr; 116 unsigned BaseId = 0; 117 APInt Offset; 118 }; 119 120 // A class that assigns increasing ids to values in the order in which they are 121 // seen. See comment in `BCEAtom::operator<()``. 122 class BaseIdentifier { 123 public: 124 // Returns the id for value `Base`, after assigning one if `Base` has not been 125 // seen before. 126 int getBaseId(const Value *Base) { 127 assert(Base && "invalid base"); 128 const auto Insertion = BaseToIndex.try_emplace(Base, Order); 129 if (Insertion.second) 130 ++Order; 131 return Insertion.first->second; 132 } 133 134 private: 135 unsigned Order = 1; 136 DenseMap<const Value*, int> BaseToIndex; 137 }; 138 139 // If this value is a load from a constant offset w.r.t. a base address, and 140 // there are no other users of the load or address, returns the base address and 141 // the offset. 142 BCEAtom visitICmpLoadOperand(Value *const Val, BaseIdentifier &BaseId) { 143 auto *const LoadI = dyn_cast<LoadInst>(Val); 144 if (!LoadI) 145 return {}; 146 LLVM_DEBUG(dbgs() << "load\n"); 147 if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) { 148 LLVM_DEBUG(dbgs() << "used outside of block\n"); 149 return {}; 150 } 151 // Do not optimize atomic loads to non-atomic memcmp 152 if (!LoadI->isSimple()) { 153 LLVM_DEBUG(dbgs() << "volatile or atomic\n"); 154 return {}; 155 } 156 Value *const Addr = LoadI->getOperand(0); 157 auto *const GEP = dyn_cast<GetElementPtrInst>(Addr); 158 if (!GEP) 159 return {}; 160 LLVM_DEBUG(dbgs() << "GEP\n"); 161 if (GEP->isUsedOutsideOfBlock(LoadI->getParent())) { 162 LLVM_DEBUG(dbgs() << "used outside of block\n"); 163 return {}; 164 } 165 const auto &DL = GEP->getModule()->getDataLayout(); 166 if (!isDereferenceablePointer(GEP, LoadI->getType(), DL)) { 167 LLVM_DEBUG(dbgs() << "not dereferenceable\n"); 168 // We need to make sure that we can do comparison in any order, so we 169 // require memory to be unconditionnally dereferencable. 170 return {}; 171 } 172 APInt Offset = APInt(DL.getPointerTypeSizeInBits(GEP->getType()), 0); 173 if (!GEP->accumulateConstantOffset(DL, Offset)) 174 return {}; 175 return BCEAtom(GEP, LoadI, BaseId.getBaseId(GEP->getPointerOperand()), 176 Offset); 177 } 178 179 // A basic block with a comparison between two BCE atoms, e.g. `a == o.a` in the 180 // example at the top. 181 // The block might do extra work besides the atom comparison, in which case 182 // doesOtherWork() returns true. Under some conditions, the block can be 183 // split into the atom comparison part and the "other work" part 184 // (see canSplit()). 185 // Note: the terminology is misleading: the comparison is symmetric, so there 186 // is no real {l/r}hs. What we want though is to have the same base on the 187 // left (resp. right), so that we can detect consecutive loads. To ensure this 188 // we put the smallest atom on the left. 189 class BCECmpBlock { 190 public: 191 BCECmpBlock() {} 192 193 BCECmpBlock(BCEAtom L, BCEAtom R, int SizeBits) 194 : Lhs_(std::move(L)), Rhs_(std::move(R)), SizeBits_(SizeBits) { 195 if (Rhs_ < Lhs_) std::swap(Rhs_, Lhs_); 196 } 197 198 bool IsValid() const { return Lhs_.BaseId != 0 && Rhs_.BaseId != 0; } 199 200 // Assert the block is consistent: If valid, it should also have 201 // non-null members besides Lhs_ and Rhs_. 202 void AssertConsistent() const { 203 if (IsValid()) { 204 assert(BB); 205 assert(CmpI); 206 assert(BranchI); 207 } 208 } 209 210 const BCEAtom &Lhs() const { return Lhs_; } 211 const BCEAtom &Rhs() const { return Rhs_; } 212 int SizeBits() const { return SizeBits_; } 213 214 // Returns true if the block does other works besides comparison. 215 bool doesOtherWork() const; 216 217 // Returns true if the non-BCE-cmp instructions can be separated from BCE-cmp 218 // instructions in the block. 219 bool canSplit(AliasAnalysis &AA) const; 220 221 // Return true if this all the relevant instructions in the BCE-cmp-block can 222 // be sunk below this instruction. By doing this, we know we can separate the 223 // BCE-cmp-block instructions from the non-BCE-cmp-block instructions in the 224 // block. 225 bool canSinkBCECmpInst(const Instruction *, DenseSet<Instruction *> &, 226 AliasAnalysis &AA) const; 227 228 // We can separate the BCE-cmp-block instructions and the non-BCE-cmp-block 229 // instructions. Split the old block and move all non-BCE-cmp-insts into the 230 // new parent block. 231 void split(BasicBlock *NewParent, AliasAnalysis &AA) const; 232 233 // The basic block where this comparison happens. 234 BasicBlock *BB = nullptr; 235 // The ICMP for this comparison. 236 ICmpInst *CmpI = nullptr; 237 // The terminating branch. 238 BranchInst *BranchI = nullptr; 239 // The block requires splitting. 240 bool RequireSplit = false; 241 242 private: 243 BCEAtom Lhs_; 244 BCEAtom Rhs_; 245 int SizeBits_ = 0; 246 }; 247 248 bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst, 249 DenseSet<Instruction *> &BlockInsts, 250 AliasAnalysis &AA) const { 251 // If this instruction has side effects and its in middle of the BCE cmp block 252 // instructions, then bail for now. 253 if (Inst->mayHaveSideEffects()) { 254 // Bail if this is not a simple load or store 255 if (!isSimpleLoadOrStore(Inst)) 256 return false; 257 // Disallow stores that might alias the BCE operands 258 MemoryLocation LLoc = MemoryLocation::get(Lhs_.LoadI); 259 MemoryLocation RLoc = MemoryLocation::get(Rhs_.LoadI); 260 if (isModSet(AA.getModRefInfo(Inst, LLoc)) || 261 isModSet(AA.getModRefInfo(Inst, RLoc))) 262 return false; 263 } 264 // Make sure this instruction does not use any of the BCE cmp block 265 // instructions as operand. 266 for (auto BI : BlockInsts) { 267 if (is_contained(Inst->operands(), BI)) 268 return false; 269 } 270 return true; 271 } 272 273 void BCECmpBlock::split(BasicBlock *NewParent, AliasAnalysis &AA) const { 274 DenseSet<Instruction *> BlockInsts( 275 {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI}); 276 llvm::SmallVector<Instruction *, 4> OtherInsts; 277 for (Instruction &Inst : *BB) { 278 if (BlockInsts.count(&Inst)) 279 continue; 280 assert(canSinkBCECmpInst(&Inst, BlockInsts, AA) && 281 "Split unsplittable block"); 282 // This is a non-BCE-cmp-block instruction. And it can be separated 283 // from the BCE-cmp-block instruction. 284 OtherInsts.push_back(&Inst); 285 } 286 287 // Do the actual spliting. 288 for (Instruction *Inst : reverse(OtherInsts)) { 289 Inst->moveBefore(&*NewParent->begin()); 290 } 291 } 292 293 bool BCECmpBlock::canSplit(AliasAnalysis &AA) const { 294 DenseSet<Instruction *> BlockInsts( 295 {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI}); 296 for (Instruction &Inst : *BB) { 297 if (!BlockInsts.count(&Inst)) { 298 if (!canSinkBCECmpInst(&Inst, BlockInsts, AA)) 299 return false; 300 } 301 } 302 return true; 303 } 304 305 bool BCECmpBlock::doesOtherWork() const { 306 AssertConsistent(); 307 // All the instructions we care about in the BCE cmp block. 308 DenseSet<Instruction *> BlockInsts( 309 {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI}); 310 // TODO(courbet): Can we allow some other things ? This is very conservative. 311 // We might be able to get away with anything does not have any side 312 // effects outside of the basic block. 313 // Note: The GEPs and/or loads are not necessarily in the same block. 314 for (const Instruction &Inst : *BB) { 315 if (!BlockInsts.count(&Inst)) 316 return true; 317 } 318 return false; 319 } 320 321 // Visit the given comparison. If this is a comparison between two valid 322 // BCE atoms, returns the comparison. 323 BCECmpBlock visitICmp(const ICmpInst *const CmpI, 324 const ICmpInst::Predicate ExpectedPredicate, 325 BaseIdentifier &BaseId) { 326 // The comparison can only be used once: 327 // - For intermediate blocks, as a branch condition. 328 // - For the final block, as an incoming value for the Phi. 329 // If there are any other uses of the comparison, we cannot merge it with 330 // other comparisons as we would create an orphan use of the value. 331 if (!CmpI->hasOneUse()) { 332 LLVM_DEBUG(dbgs() << "cmp has several uses\n"); 333 return {}; 334 } 335 if (CmpI->getPredicate() != ExpectedPredicate) 336 return {}; 337 LLVM_DEBUG(dbgs() << "cmp " 338 << (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne") 339 << "\n"); 340 auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0), BaseId); 341 if (!Lhs.BaseId) 342 return {}; 343 auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1), BaseId); 344 if (!Rhs.BaseId) 345 return {}; 346 const auto &DL = CmpI->getModule()->getDataLayout(); 347 return BCECmpBlock(std::move(Lhs), std::move(Rhs), 348 DL.getTypeSizeInBits(CmpI->getOperand(0)->getType())); 349 } 350 351 // Visit the given comparison block. If this is a comparison between two valid 352 // BCE atoms, returns the comparison. 353 BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block, 354 const BasicBlock *const PhiBlock, 355 BaseIdentifier &BaseId) { 356 if (Block->empty()) return {}; 357 auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator()); 358 if (!BranchI) return {}; 359 LLVM_DEBUG(dbgs() << "branch\n"); 360 if (BranchI->isUnconditional()) { 361 // In this case, we expect an incoming value which is the result of the 362 // comparison. This is the last link in the chain of comparisons (note 363 // that this does not mean that this is the last incoming value, blocks 364 // can be reordered). 365 auto *const CmpI = dyn_cast<ICmpInst>(Val); 366 if (!CmpI) return {}; 367 LLVM_DEBUG(dbgs() << "icmp\n"); 368 auto Result = visitICmp(CmpI, ICmpInst::ICMP_EQ, BaseId); 369 Result.CmpI = CmpI; 370 Result.BranchI = BranchI; 371 return Result; 372 } else { 373 // In this case, we expect a constant incoming value (the comparison is 374 // chained). 375 const auto *const Const = dyn_cast<ConstantInt>(Val); 376 LLVM_DEBUG(dbgs() << "const\n"); 377 if (!Const->isZero()) return {}; 378 LLVM_DEBUG(dbgs() << "false\n"); 379 auto *const CmpI = dyn_cast<ICmpInst>(BranchI->getCondition()); 380 if (!CmpI) return {}; 381 LLVM_DEBUG(dbgs() << "icmp\n"); 382 assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch"); 383 BasicBlock *const FalseBlock = BranchI->getSuccessor(1); 384 auto Result = visitICmp( 385 CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, 386 BaseId); 387 Result.CmpI = CmpI; 388 Result.BranchI = BranchI; 389 return Result; 390 } 391 return {}; 392 } 393 394 static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons, 395 BCECmpBlock &&Comparison) { 396 LLVM_DEBUG(dbgs() << "Block '" << Comparison.BB->getName() 397 << "': Found cmp of " << Comparison.SizeBits() 398 << " bits between " << Comparison.Lhs().BaseId << " + " 399 << Comparison.Lhs().Offset << " and " 400 << Comparison.Rhs().BaseId << " + " 401 << Comparison.Rhs().Offset << "\n"); 402 LLVM_DEBUG(dbgs() << "\n"); 403 Comparisons.push_back(std::move(Comparison)); 404 } 405 406 // A chain of comparisons. 407 class BCECmpChain { 408 public: 409 BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi, 410 AliasAnalysis &AA); 411 412 int size() const { return Comparisons_.size(); } 413 414 #ifdef MERGEICMPS_DOT_ON 415 void dump() const; 416 #endif // MERGEICMPS_DOT_ON 417 418 bool simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA, 419 DomTreeUpdater &DTU); 420 421 private: 422 static bool IsContiguous(const BCECmpBlock &First, 423 const BCECmpBlock &Second) { 424 return First.Lhs().BaseId == Second.Lhs().BaseId && 425 First.Rhs().BaseId == Second.Rhs().BaseId && 426 First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset && 427 First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset; 428 } 429 430 PHINode &Phi_; 431 std::vector<BCECmpBlock> Comparisons_; 432 // The original entry block (before sorting); 433 BasicBlock *EntryBlock_; 434 }; 435 436 BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi, 437 AliasAnalysis &AA) 438 : Phi_(Phi) { 439 assert(!Blocks.empty() && "a chain should have at least one block"); 440 // Now look inside blocks to check for BCE comparisons. 441 std::vector<BCECmpBlock> Comparisons; 442 BaseIdentifier BaseId; 443 for (size_t BlockIdx = 0; BlockIdx < Blocks.size(); ++BlockIdx) { 444 BasicBlock *const Block = Blocks[BlockIdx]; 445 assert(Block && "invalid block"); 446 BCECmpBlock Comparison = visitCmpBlock(Phi.getIncomingValueForBlock(Block), 447 Block, Phi.getParent(), BaseId); 448 Comparison.BB = Block; 449 if (!Comparison.IsValid()) { 450 LLVM_DEBUG(dbgs() << "chain with invalid BCECmpBlock, no merge.\n"); 451 return; 452 } 453 if (Comparison.doesOtherWork()) { 454 LLVM_DEBUG(dbgs() << "block '" << Comparison.BB->getName() 455 << "' does extra work besides compare\n"); 456 if (Comparisons.empty()) { 457 // This is the initial block in the chain, in case this block does other 458 // work, we can try to split the block and move the irrelevant 459 // instructions to the predecessor. 460 // 461 // If this is not the initial block in the chain, splitting it wont 462 // work. 463 // 464 // As once split, there will still be instructions before the BCE cmp 465 // instructions that do other work in program order, i.e. within the 466 // chain before sorting. Unless we can abort the chain at this point 467 // and start anew. 468 // 469 // NOTE: we only handle blocks a with single predecessor for now. 470 if (Comparison.canSplit(AA)) { 471 LLVM_DEBUG(dbgs() 472 << "Split initial block '" << Comparison.BB->getName() 473 << "' that does extra work besides compare\n"); 474 Comparison.RequireSplit = true; 475 enqueueBlock(Comparisons, std::move(Comparison)); 476 } else { 477 LLVM_DEBUG(dbgs() 478 << "ignoring initial block '" << Comparison.BB->getName() 479 << "' that does extra work besides compare\n"); 480 } 481 continue; 482 } 483 // TODO(courbet): Right now we abort the whole chain. We could be 484 // merging only the blocks that don't do other work and resume the 485 // chain from there. For example: 486 // if (a[0] == b[0]) { // bb1 487 // if (a[1] == b[1]) { // bb2 488 // some_value = 3; //bb3 489 // if (a[2] == b[2]) { //bb3 490 // do a ton of stuff //bb4 491 // } 492 // } 493 // } 494 // 495 // This is: 496 // 497 // bb1 --eq--> bb2 --eq--> bb3* -eq--> bb4 --+ 498 // \ \ \ \ 499 // ne ne ne \ 500 // \ \ \ v 501 // +------------+-----------+----------> bb_phi 502 // 503 // We can only merge the first two comparisons, because bb3* does 504 // "other work" (setting some_value to 3). 505 // We could still merge bb1 and bb2 though. 506 return; 507 } 508 enqueueBlock(Comparisons, std::move(Comparison)); 509 } 510 511 // It is possible we have no suitable comparison to merge. 512 if (Comparisons.empty()) { 513 LLVM_DEBUG(dbgs() << "chain with no BCE basic blocks, no merge\n"); 514 return; 515 } 516 EntryBlock_ = Comparisons[0].BB; 517 Comparisons_ = std::move(Comparisons); 518 #ifdef MERGEICMPS_DOT_ON 519 errs() << "BEFORE REORDERING:\n\n"; 520 dump(); 521 #endif // MERGEICMPS_DOT_ON 522 // Reorder blocks by LHS. We can do that without changing the 523 // semantics because we are only accessing dereferencable memory. 524 llvm::sort(Comparisons_, 525 [](const BCECmpBlock &LhsBlock, const BCECmpBlock &RhsBlock) { 526 return std::tie(LhsBlock.Lhs(), LhsBlock.Rhs()) < 527 std::tie(RhsBlock.Lhs(), RhsBlock.Rhs()); 528 }); 529 #ifdef MERGEICMPS_DOT_ON 530 errs() << "AFTER REORDERING:\n\n"; 531 dump(); 532 #endif // MERGEICMPS_DOT_ON 533 } 534 535 #ifdef MERGEICMPS_DOT_ON 536 void BCECmpChain::dump() const { 537 errs() << "digraph dag {\n"; 538 errs() << " graph [bgcolor=transparent];\n"; 539 errs() << " node [color=black,style=filled,fillcolor=lightyellow];\n"; 540 errs() << " edge [color=black];\n"; 541 for (size_t I = 0; I < Comparisons_.size(); ++I) { 542 const auto &Comparison = Comparisons_[I]; 543 errs() << " \"" << I << "\" [label=\"%" 544 << Comparison.Lhs().Base()->getName() << " + " 545 << Comparison.Lhs().Offset << " == %" 546 << Comparison.Rhs().Base()->getName() << " + " 547 << Comparison.Rhs().Offset << " (" << (Comparison.SizeBits() / 8) 548 << " bytes)\"];\n"; 549 const Value *const Val = Phi_.getIncomingValueForBlock(Comparison.BB); 550 if (I > 0) errs() << " \"" << (I - 1) << "\" -> \"" << I << "\";\n"; 551 errs() << " \"" << I << "\" -> \"Phi\" [label=\"" << *Val << "\"];\n"; 552 } 553 errs() << " \"Phi\" [label=\"Phi\"];\n"; 554 errs() << "}\n\n"; 555 } 556 #endif // MERGEICMPS_DOT_ON 557 558 namespace { 559 560 // A class to compute the name of a set of merged basic blocks. 561 // This is optimized for the common case of no block names. 562 class MergedBlockName { 563 // Storage for the uncommon case of several named blocks. 564 SmallString<16> Scratch; 565 566 public: 567 explicit MergedBlockName(ArrayRef<BCECmpBlock> Comparisons) 568 : Name(makeName(Comparisons)) {} 569 const StringRef Name; 570 571 private: 572 StringRef makeName(ArrayRef<BCECmpBlock> Comparisons) { 573 assert(!Comparisons.empty() && "no basic block"); 574 // Fast path: only one block, or no names at all. 575 if (Comparisons.size() == 1) 576 return Comparisons[0].BB->getName(); 577 const int size = std::accumulate(Comparisons.begin(), Comparisons.end(), 0, 578 [](int i, const BCECmpBlock &Cmp) { 579 return i + Cmp.BB->getName().size(); 580 }); 581 if (size == 0) 582 return StringRef("", 0); 583 584 // Slow path: at least two blocks, at least one block with a name. 585 Scratch.clear(); 586 // We'll have `size` bytes for name and `Comparisons.size() - 1` bytes for 587 // separators. 588 Scratch.reserve(size + Comparisons.size() - 1); 589 const auto append = [this](StringRef str) { 590 Scratch.append(str.begin(), str.end()); 591 }; 592 append(Comparisons[0].BB->getName()); 593 for (int I = 1, E = Comparisons.size(); I < E; ++I) { 594 const BasicBlock *const BB = Comparisons[I].BB; 595 if (!BB->getName().empty()) { 596 append("+"); 597 append(BB->getName()); 598 } 599 } 600 return StringRef(Scratch); 601 } 602 }; 603 } // namespace 604 605 // Merges the given contiguous comparison blocks into one memcmp block. 606 static BasicBlock *mergeComparisons(ArrayRef<BCECmpBlock> Comparisons, 607 BasicBlock *const InsertBefore, 608 BasicBlock *const NextCmpBlock, 609 PHINode &Phi, const TargetLibraryInfo &TLI, 610 AliasAnalysis &AA, DomTreeUpdater &DTU) { 611 assert(!Comparisons.empty() && "merging zero comparisons"); 612 LLVMContext &Context = NextCmpBlock->getContext(); 613 const BCECmpBlock &FirstCmp = Comparisons[0]; 614 615 // Create a new cmp block before next cmp block. 616 BasicBlock *const BB = 617 BasicBlock::Create(Context, MergedBlockName(Comparisons).Name, 618 NextCmpBlock->getParent(), InsertBefore); 619 IRBuilder<> Builder(BB); 620 // Add the GEPs from the first BCECmpBlock. 621 Value *const Lhs = Builder.Insert(FirstCmp.Lhs().GEP->clone()); 622 Value *const Rhs = Builder.Insert(FirstCmp.Rhs().GEP->clone()); 623 624 Value *IsEqual = nullptr; 625 LLVM_DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons -> " 626 << BB->getName() << "\n"); 627 if (Comparisons.size() == 1) { 628 LLVM_DEBUG(dbgs() << "Only one comparison, updating branches\n"); 629 Value *const LhsLoad = 630 Builder.CreateLoad(FirstCmp.Lhs().LoadI->getType(), Lhs); 631 Value *const RhsLoad = 632 Builder.CreateLoad(FirstCmp.Rhs().LoadI->getType(), Rhs); 633 // There are no blocks to merge, just do the comparison. 634 IsEqual = Builder.CreateICmpEQ(LhsLoad, RhsLoad); 635 } else { 636 // If there is one block that requires splitting, we do it now, i.e. 637 // just before we know we will collapse the chain. The instructions 638 // can be executed before any of the instructions in the chain. 639 const auto ToSplit = 640 std::find_if(Comparisons.begin(), Comparisons.end(), 641 [](const BCECmpBlock &B) { return B.RequireSplit; }); 642 if (ToSplit != Comparisons.end()) { 643 LLVM_DEBUG(dbgs() << "Splitting non_BCE work to header\n"); 644 ToSplit->split(BB, AA); 645 } 646 647 const unsigned TotalSizeBits = std::accumulate( 648 Comparisons.begin(), Comparisons.end(), 0u, 649 [](int Size, const BCECmpBlock &C) { return Size + C.SizeBits(); }); 650 651 // Create memcmp() == 0. 652 const auto &DL = Phi.getModule()->getDataLayout(); 653 Value *const MemCmpCall = emitMemCmp( 654 Lhs, Rhs, 655 ConstantInt::get(DL.getIntPtrType(Context), TotalSizeBits / 8), Builder, 656 DL, &TLI); 657 IsEqual = Builder.CreateICmpEQ( 658 MemCmpCall, ConstantInt::get(Type::getInt32Ty(Context), 0)); 659 } 660 661 BasicBlock *const PhiBB = Phi.getParent(); 662 // Add a branch to the next basic block in the chain. 663 if (NextCmpBlock == PhiBB) { 664 // Continue to phi, passing it the comparison result. 665 Builder.CreateBr(PhiBB); 666 Phi.addIncoming(IsEqual, BB); 667 DTU.applyUpdates({{DominatorTree::Insert, BB, PhiBB}}); 668 } else { 669 // Continue to next block if equal, exit to phi else. 670 Builder.CreateCondBr(IsEqual, NextCmpBlock, PhiBB); 671 Phi.addIncoming(ConstantInt::getFalse(Context), BB); 672 DTU.applyUpdates({{DominatorTree::Insert, BB, NextCmpBlock}, 673 {DominatorTree::Insert, BB, PhiBB}}); 674 } 675 return BB; 676 } 677 678 bool BCECmpChain::simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA, 679 DomTreeUpdater &DTU) { 680 assert(Comparisons_.size() >= 2 && "simplifying trivial BCECmpChain"); 681 // First pass to check if there is at least one merge. If not, we don't do 682 // anything and we keep analysis passes intact. 683 const auto AtLeastOneMerged = [this]() { 684 for (size_t I = 1; I < Comparisons_.size(); ++I) { 685 if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) 686 return true; 687 } 688 return false; 689 }; 690 if (!AtLeastOneMerged()) 691 return false; 692 693 LLVM_DEBUG(dbgs() << "Simplifying comparison chain starting at block " 694 << EntryBlock_->getName() << "\n"); 695 696 // Effectively merge blocks. We go in the reverse direction from the phi block 697 // so that the next block is always available to branch to. 698 const auto mergeRange = [this, &TLI, &AA, &DTU](int I, int Num, 699 BasicBlock *InsertBefore, 700 BasicBlock *Next) { 701 return mergeComparisons(makeArrayRef(Comparisons_).slice(I, Num), 702 InsertBefore, Next, Phi_, TLI, AA, DTU); 703 }; 704 int NumMerged = 1; 705 BasicBlock *NextCmpBlock = Phi_.getParent(); 706 for (int I = static_cast<int>(Comparisons_.size()) - 2; I >= 0; --I) { 707 if (IsContiguous(Comparisons_[I], Comparisons_[I + 1])) { 708 LLVM_DEBUG(dbgs() << "Merging block " << Comparisons_[I].BB->getName() 709 << " into " << Comparisons_[I + 1].BB->getName() 710 << "\n"); 711 ++NumMerged; 712 } else { 713 NextCmpBlock = mergeRange(I + 1, NumMerged, NextCmpBlock, NextCmpBlock); 714 NumMerged = 1; 715 } 716 } 717 // Insert the entry block for the new chain before the old entry block. 718 // If the old entry block was the function entry, this ensures that the new 719 // entry can become the function entry. 720 NextCmpBlock = mergeRange(0, NumMerged, EntryBlock_, NextCmpBlock); 721 722 // Replace the original cmp chain with the new cmp chain by pointing all 723 // predecessors of EntryBlock_ to NextCmpBlock instead. This makes all cmp 724 // blocks in the old chain unreachable. 725 while (!pred_empty(EntryBlock_)) { 726 BasicBlock* const Pred = *pred_begin(EntryBlock_); 727 LLVM_DEBUG(dbgs() << "Updating jump into old chain from " << Pred->getName() 728 << "\n"); 729 Pred->getTerminator()->replaceUsesOfWith(EntryBlock_, NextCmpBlock); 730 DTU.applyUpdates({{DominatorTree::Delete, Pred, EntryBlock_}, 731 {DominatorTree::Insert, Pred, NextCmpBlock}}); 732 } 733 734 // If the old cmp chain was the function entry, we need to update the function 735 // entry. 736 const bool ChainEntryIsFnEntry = 737 (EntryBlock_ == &EntryBlock_->getParent()->getEntryBlock()); 738 if (ChainEntryIsFnEntry && DTU.hasDomTree()) { 739 LLVM_DEBUG(dbgs() << "Changing function entry from " 740 << EntryBlock_->getName() << " to " 741 << NextCmpBlock->getName() << "\n"); 742 DTU.getDomTree().setNewRoot(NextCmpBlock); 743 DTU.applyUpdates({{DominatorTree::Delete, NextCmpBlock, EntryBlock_}}); 744 } 745 EntryBlock_ = nullptr; 746 747 // Delete merged blocks. This also removes incoming values in phi. 748 SmallVector<BasicBlock *, 16> DeadBlocks; 749 for (auto &Cmp : Comparisons_) { 750 LLVM_DEBUG(dbgs() << "Deleting merged block " << Cmp.BB->getName() << "\n"); 751 DeadBlocks.push_back(Cmp.BB); 752 } 753 DeleteDeadBlocks(DeadBlocks, &DTU); 754 755 Comparisons_.clear(); 756 return true; 757 } 758 759 std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi, 760 BasicBlock *const LastBlock, 761 int NumBlocks) { 762 // Walk up from the last block to find other blocks. 763 std::vector<BasicBlock *> Blocks(NumBlocks); 764 assert(LastBlock && "invalid last block"); 765 BasicBlock *CurBlock = LastBlock; 766 for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) { 767 if (CurBlock->hasAddressTaken()) { 768 // Somebody is jumping to the block through an address, all bets are 769 // off. 770 LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex 771 << " has its address taken\n"); 772 return {}; 773 } 774 Blocks[BlockIndex] = CurBlock; 775 auto *SinglePredecessor = CurBlock->getSinglePredecessor(); 776 if (!SinglePredecessor) { 777 // The block has two or more predecessors. 778 LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex 779 << " has two or more predecessors\n"); 780 return {}; 781 } 782 if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) { 783 // The block does not link back to the phi. 784 LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex 785 << " does not link back to the phi\n"); 786 return {}; 787 } 788 CurBlock = SinglePredecessor; 789 } 790 Blocks[0] = CurBlock; 791 return Blocks; 792 } 793 794 bool processPhi(PHINode &Phi, const TargetLibraryInfo &TLI, AliasAnalysis &AA, 795 DomTreeUpdater &DTU) { 796 LLVM_DEBUG(dbgs() << "processPhi()\n"); 797 if (Phi.getNumIncomingValues() <= 1) { 798 LLVM_DEBUG(dbgs() << "skip: only one incoming value in phi\n"); 799 return false; 800 } 801 // We are looking for something that has the following structure: 802 // bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+ 803 // \ \ \ \ 804 // ne ne ne \ 805 // \ \ \ v 806 // +------------+-----------+----------> bb_phi 807 // 808 // - The last basic block (bb4 here) must branch unconditionally to bb_phi. 809 // It's the only block that contributes a non-constant value to the Phi. 810 // - All other blocks (b1, b2, b3) must have exactly two successors, one of 811 // them being the phi block. 812 // - All intermediate blocks (bb2, bb3) must have only one predecessor. 813 // - Blocks cannot do other work besides the comparison, see doesOtherWork() 814 815 // The blocks are not necessarily ordered in the phi, so we start from the 816 // last block and reconstruct the order. 817 BasicBlock *LastBlock = nullptr; 818 for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) { 819 if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue; 820 if (LastBlock) { 821 // There are several non-constant values. 822 LLVM_DEBUG(dbgs() << "skip: several non-constant values\n"); 823 return false; 824 } 825 if (!isa<ICmpInst>(Phi.getIncomingValue(I)) || 826 cast<ICmpInst>(Phi.getIncomingValue(I))->getParent() != 827 Phi.getIncomingBlock(I)) { 828 // Non-constant incoming value is not from a cmp instruction or not 829 // produced by the last block. We could end up processing the value 830 // producing block more than once. 831 // 832 // This is an uncommon case, so we bail. 833 LLVM_DEBUG( 834 dbgs() 835 << "skip: non-constant value not from cmp or not from last block.\n"); 836 return false; 837 } 838 LastBlock = Phi.getIncomingBlock(I); 839 } 840 if (!LastBlock) { 841 // There is no non-constant block. 842 LLVM_DEBUG(dbgs() << "skip: no non-constant block\n"); 843 return false; 844 } 845 if (LastBlock->getSingleSuccessor() != Phi.getParent()) { 846 LLVM_DEBUG(dbgs() << "skip: last block non-phi successor\n"); 847 return false; 848 } 849 850 const auto Blocks = 851 getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues()); 852 if (Blocks.empty()) return false; 853 BCECmpChain CmpChain(Blocks, Phi, AA); 854 855 if (CmpChain.size() < 2) { 856 LLVM_DEBUG(dbgs() << "skip: only one compare block\n"); 857 return false; 858 } 859 860 return CmpChain.simplify(TLI, AA, DTU); 861 } 862 863 static bool runImpl(Function &F, const TargetLibraryInfo &TLI, 864 const TargetTransformInfo &TTI, AliasAnalysis &AA, 865 DominatorTree *DT) { 866 LLVM_DEBUG(dbgs() << "MergeICmpsLegacyPass: " << F.getName() << "\n"); 867 868 // We only try merging comparisons if the target wants to expand memcmp later. 869 // The rationale is to avoid turning small chains into memcmp calls. 870 if (!TTI.enableMemCmpExpansion(F.hasOptSize(), true)) 871 return false; 872 873 // If we don't have memcmp avaiable we can't emit calls to it. 874 if (!TLI.has(LibFunc_memcmp)) 875 return false; 876 877 DomTreeUpdater DTU(DT, /*PostDominatorTree*/ nullptr, 878 DomTreeUpdater::UpdateStrategy::Eager); 879 880 bool MadeChange = false; 881 882 for (auto BBIt = ++F.begin(); BBIt != F.end(); ++BBIt) { 883 // A Phi operation is always first in a basic block. 884 if (auto *const Phi = dyn_cast<PHINode>(&*BBIt->begin())) 885 MadeChange |= processPhi(*Phi, TLI, AA, DTU); 886 } 887 888 return MadeChange; 889 } 890 891 class MergeICmpsLegacyPass : public FunctionPass { 892 public: 893 static char ID; 894 895 MergeICmpsLegacyPass() : FunctionPass(ID) { 896 initializeMergeICmpsLegacyPassPass(*PassRegistry::getPassRegistry()); 897 } 898 899 bool runOnFunction(Function &F) override { 900 if (skipFunction(F)) return false; 901 const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 902 const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 903 // MergeICmps does not need the DominatorTree, but we update it if it's 904 // already available. 905 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 906 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); 907 return runImpl(F, TLI, TTI, AA, DTWP ? &DTWP->getDomTree() : nullptr); 908 } 909 910 private: 911 void getAnalysisUsage(AnalysisUsage &AU) const override { 912 AU.addRequired<TargetLibraryInfoWrapperPass>(); 913 AU.addRequired<TargetTransformInfoWrapperPass>(); 914 AU.addRequired<AAResultsWrapperPass>(); 915 AU.addPreserved<GlobalsAAWrapperPass>(); 916 AU.addPreserved<DominatorTreeWrapperPass>(); 917 } 918 }; 919 920 } // namespace 921 922 char MergeICmpsLegacyPass::ID = 0; 923 INITIALIZE_PASS_BEGIN(MergeICmpsLegacyPass, "mergeicmps", 924 "Merge contiguous icmps into a memcmp", false, false) 925 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 926 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 927 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 928 INITIALIZE_PASS_END(MergeICmpsLegacyPass, "mergeicmps", 929 "Merge contiguous icmps into a memcmp", false, false) 930 931 Pass *llvm::createMergeICmpsLegacyPass() { return new MergeICmpsLegacyPass(); } 932 933 PreservedAnalyses MergeICmpsPass::run(Function &F, 934 FunctionAnalysisManager &AM) { 935 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 936 auto &TTI = AM.getResult<TargetIRAnalysis>(F); 937 auto &AA = AM.getResult<AAManager>(F); 938 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F); 939 const bool MadeChanges = runImpl(F, TLI, TTI, AA, DT); 940 if (!MadeChanges) 941 return PreservedAnalyses::all(); 942 PreservedAnalyses PA; 943 PA.preserve<GlobalsAA>(); 944 PA.preserve<DominatorTreeAnalysis>(); 945 return PA; 946 } 947