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