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