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