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