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