-
Notifications
You must be signed in to change notification settings - Fork 10.8k
/
MergeICmps.cpp
650 lines (590 loc) · 23.7 KB
/
MergeICmps.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
//===- MergeICmps.cpp - Optimize chains of integer comparisons ------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass turns chains of integer comparisons into memcmp (the memcmp is
// later typically inlined as a chain of efficient hardware comparisons). This
// typically benefits c++ member or nonmember operator==().
//
// The basic idea is to replace a larger chain of integer comparisons loaded
// from contiguous memory locations into a smaller chain of such integer
// comparisons. Benefits are double:
// - There are less jumps, and therefore less opportunities for mispredictions
// and I-cache misses.
// - Code size is smaller, both because jumps are removed and because the
// encoding of a 2*n byte compare is smaller than that of two n-byte
// compares.
//===----------------------------------------------------------------------===//
#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
using namespace llvm;
namespace {
#define DEBUG_TYPE "mergeicmps"
// A BCE atom.
struct BCEAtom {
BCEAtom() : GEP(nullptr), LoadI(nullptr), Offset() {}
const Value *Base() const { return GEP ? GEP->getPointerOperand() : nullptr; }
bool operator<(const BCEAtom &O) const {
assert(Base() && "invalid atom");
assert(O.Base() && "invalid atom");
// Just ordering by (Base(), Offset) is sufficient. However because this
// means that the ordering will depend on the addresses of the base
// values, which are not reproducible from run to run. To guarantee
// stability, we use the names of the values if they exist; we sort by:
// (Base.getName(), Base(), Offset).
const int NameCmp = Base()->getName().compare(O.Base()->getName());
if (NameCmp == 0) {
if (Base() == O.Base()) {
return Offset.slt(O.Offset);
}
return Base() < O.Base();
}
return NameCmp < 0;
}
GetElementPtrInst *GEP;
LoadInst *LoadI;
APInt Offset;
};
// If this value is a load from a constant offset w.r.t. a base address, and
// there are no othe rusers of the load or address, returns the base address and
// the offset.
BCEAtom visitICmpLoadOperand(Value *const Val) {
BCEAtom Result;
if (auto *const LoadI = dyn_cast<LoadInst>(Val)) {
DEBUG(dbgs() << "load\n");
if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {
DEBUG(dbgs() << "used outside of block\n");
return {};
}
if (LoadI->isVolatile()) {
DEBUG(dbgs() << "volatile\n");
return {};
}
Value *const Addr = LoadI->getOperand(0);
if (auto *const GEP = dyn_cast<GetElementPtrInst>(Addr)) {
DEBUG(dbgs() << "GEP\n");
if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {
DEBUG(dbgs() << "used outside of block\n");
return {};
}
const auto &DL = GEP->getModule()->getDataLayout();
if (!isDereferenceablePointer(GEP, DL)) {
DEBUG(dbgs() << "not dereferenceable\n");
// We need to make sure that we can do comparison in any order, so we
// require memory to be unconditionnally dereferencable.
return {};
}
Result.Offset = APInt(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
if (GEP->accumulateConstantOffset(DL, Result.Offset)) {
Result.GEP = GEP;
Result.LoadI = LoadI;
}
}
}
return Result;
}
// A basic block with a comparison between two BCE atoms.
// Note: the terminology is misleading: the comparison is symmetric, so there
// is no real {l/r}hs. What we want though is to have the same base on the
// left (resp. right), so that we can detect consecutive loads. To ensure this
// we put the smallest atom on the left.
class BCECmpBlock {
public:
BCECmpBlock() {}
BCECmpBlock(BCEAtom L, BCEAtom R, int SizeBits)
: Lhs_(L), Rhs_(R), SizeBits_(SizeBits) {
if (Rhs_ < Lhs_) std::swap(Rhs_, Lhs_);
}
bool IsValid() const {
return Lhs_.Base() != nullptr && Rhs_.Base() != nullptr;
}
// Assert the block is consistent: If valid, it should also have
// non-null members besides Lhs_ and Rhs_.
void AssertConsistent() const {
if (IsValid()) {
assert(BB);
assert(CmpI);
assert(BranchI);
}
}
const BCEAtom &Lhs() const { return Lhs_; }
const BCEAtom &Rhs() const { return Rhs_; }
int SizeBits() const { return SizeBits_; }
// Returns true if the block does other works besides comparison.
bool doesOtherWork() const;
// The basic block where this comparison happens.
BasicBlock *BB = nullptr;
// The ICMP for this comparison.
ICmpInst *CmpI = nullptr;
// The terminating branch.
BranchInst *BranchI = nullptr;
private:
BCEAtom Lhs_;
BCEAtom Rhs_;
int SizeBits_ = 0;
};
bool BCECmpBlock::doesOtherWork() const {
AssertConsistent();
// TODO(courbet): Can we allow some other things ? This is very conservative.
// We might be able to get away with anything does does not have any side
// effects outside of the basic block.
// Note: The GEPs and/or loads are not necessarily in the same block.
for (const Instruction &Inst : *BB) {
if (const auto *const GEP = dyn_cast<GetElementPtrInst>(&Inst)) {
if (!(Lhs_.GEP == GEP || Rhs_.GEP == GEP)) return true;
} else if (const auto *const L = dyn_cast<LoadInst>(&Inst)) {
if (!(Lhs_.LoadI == L || Rhs_.LoadI == L)) return true;
} else if (const auto *const C = dyn_cast<ICmpInst>(&Inst)) {
if (C != CmpI) return true;
} else if (const auto *const Br = dyn_cast<BranchInst>(&Inst)) {
if (Br != BranchI) return true;
} else {
return true;
}
}
return false;
}
// Visit the given comparison. If this is a comparison between two valid
// BCE atoms, returns the comparison.
BCECmpBlock visitICmp(const ICmpInst *const CmpI,
const ICmpInst::Predicate ExpectedPredicate) {
if (CmpI->getPredicate() == ExpectedPredicate) {
DEBUG(dbgs() << "cmp "
<< (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne")
<< "\n");
auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0));
if (!Lhs.Base()) return {};
auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1));
if (!Rhs.Base()) return {};
return BCECmpBlock(std::move(Lhs), std::move(Rhs),
CmpI->getOperand(0)->getType()->getScalarSizeInBits());
}
return {};
}
// Visit the given comparison block. If this is a comparison between two valid
// BCE atoms, returns the comparison.
BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block,
const BasicBlock *const PhiBlock) {
if (Block->empty()) return {};
auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator());
if (!BranchI) return {};
DEBUG(dbgs() << "branch\n");
if (BranchI->isUnconditional()) {
// In this case, we expect an incoming value which is the result of the
// comparison. This is the last link in the chain of comparisons (note
// that this does not mean that this is the last incoming value, blocks
// can be reordered).
auto *const CmpI = dyn_cast<ICmpInst>(Val);
if (!CmpI) return {};
DEBUG(dbgs() << "icmp\n");
auto Result = visitICmp(CmpI, ICmpInst::ICMP_EQ);
Result.CmpI = CmpI;
Result.BranchI = BranchI;
return Result;
} else {
// In this case, we expect a constant incoming value (the comparison is
// chained).
const auto *const Const = dyn_cast<ConstantInt>(Val);
DEBUG(dbgs() << "const\n");
if (!Const->isZero()) return {};
DEBUG(dbgs() << "false\n");
auto *const CmpI = dyn_cast<ICmpInst>(BranchI->getCondition());
if (!CmpI) return {};
DEBUG(dbgs() << "icmp\n");
assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch");
BasicBlock *const FalseBlock = BranchI->getSuccessor(1);
auto Result = visitICmp(
CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE);
Result.CmpI = CmpI;
Result.BranchI = BranchI;
return Result;
}
return {};
}
// A chain of comparisons.
class BCECmpChain {
public:
BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi);
int size() const { return Comparisons_.size(); }
#ifdef MERGEICMPS_DOT_ON
void dump() const;
#endif // MERGEICMPS_DOT_ON
bool simplify(const TargetLibraryInfo *const TLI);
private:
static bool IsContiguous(const BCECmpBlock &First,
const BCECmpBlock &Second) {
return First.Lhs().Base() == Second.Lhs().Base() &&
First.Rhs().Base() == Second.Rhs().Base() &&
First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset &&
First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset;
}
// Merges the given comparison blocks into one memcmp block and update
// branches. Comparisons are assumed to be continguous. If NextBBInChain is
// null, the merged block will link to the phi block.
static void mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
BasicBlock *const NextBBInChain, PHINode &Phi,
const TargetLibraryInfo *const TLI);
PHINode &Phi_;
std::vector<BCECmpBlock> Comparisons_;
// The original entry block (before sorting);
BasicBlock *EntryBlock_;
};
BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi)
: Phi_(Phi) {
// Now look inside blocks to check for BCE comparisons.
std::vector<BCECmpBlock> Comparisons;
for (BasicBlock *Block : Blocks) {
BCECmpBlock Comparison = visitCmpBlock(Phi.getIncomingValueForBlock(Block),
Block, Phi.getParent());
Comparison.BB = Block;
if (!Comparison.IsValid()) {
DEBUG(dbgs() << "skip: not a valid BCECmpBlock\n");
return;
}
if (Comparison.doesOtherWork()) {
DEBUG(dbgs() << "block does extra work besides compare\n");
if (Comparisons.empty()) { // First block.
// TODO(courbet): The first block can do other things, and we should
// split them apart in a separate block before the comparison chain.
// Right now we just discard it and make the chain shorter.
DEBUG(dbgs()
<< "ignoring first block that does extra work besides compare\n");
continue;
}
// TODO(courbet): Right now we abort the whole chain. We could be
// merging only the blocks that don't do other work and resume the
// chain from there. For example:
// if (a[0] == b[0]) { // bb1
// if (a[1] == b[1]) { // bb2
// some_value = 3; //bb3
// if (a[2] == b[2]) { //bb3
// do a ton of stuff //bb4
// }
// }
// }
//
// This is:
//
// bb1 --eq--> bb2 --eq--> bb3* -eq--> bb4 --+
// \ \ \ \
// ne ne ne \
// \ \ \ v
// +------------+-----------+----------> bb_phi
//
// We can only merge the first two comparisons, because bb3* does
// "other work" (setting some_value to 3).
// We could still merge bb1 and bb2 though.
return;
}
DEBUG(dbgs() << "*Found cmp of " << Comparison.SizeBits()
<< " bits between " << Comparison.Lhs().Base() << " + "
<< Comparison.Lhs().Offset << " and "
<< Comparison.Rhs().Base() << " + " << Comparison.Rhs().Offset
<< "\n");
DEBUG(dbgs() << "\n");
Comparisons.push_back(Comparison);
}
EntryBlock_ = Comparisons[0].BB;
Comparisons_ = std::move(Comparisons);
#ifdef MERGEICMPS_DOT_ON
errs() << "BEFORE REORDERING:\n\n";
dump();
#endif // MERGEICMPS_DOT_ON
// Reorder blocks by LHS. We can do that without changing the
// semantics because we are only accessing dereferencable memory.
std::sort(Comparisons_.begin(), Comparisons_.end(),
[](const BCECmpBlock &a, const BCECmpBlock &b) {
return a.Lhs() < b.Lhs();
});
#ifdef MERGEICMPS_DOT_ON
errs() << "AFTER REORDERING:\n\n";
dump();
#endif // MERGEICMPS_DOT_ON
}
#ifdef MERGEICMPS_DOT_ON
void BCECmpChain::dump() const {
errs() << "digraph dag {\n";
errs() << " graph [bgcolor=transparent];\n";
errs() << " node [color=black,style=filled,fillcolor=lightyellow];\n";
errs() << " edge [color=black];\n";
for (size_t I = 0; I < Comparisons_.size(); ++I) {
const auto &Comparison = Comparisons_[I];
errs() << " \"" << I << "\" [label=\"%"
<< Comparison.Lhs().Base()->getName() << " + "
<< Comparison.Lhs().Offset << " == %"
<< Comparison.Rhs().Base()->getName() << " + "
<< Comparison.Rhs().Offset << " (" << (Comparison.SizeBits() / 8)
<< " bytes)\"];\n";
const Value *const Val = Phi_.getIncomingValueForBlock(Comparison.BB);
if (I > 0) errs() << " \"" << (I - 1) << "\" -> \"" << I << "\";\n";
errs() << " \"" << I << "\" -> \"Phi\" [label=\"" << *Val << "\"];\n";
}
errs() << " \"Phi\" [label=\"Phi\"];\n";
errs() << "}\n\n";
}
#endif // MERGEICMPS_DOT_ON
bool BCECmpChain::simplify(const TargetLibraryInfo *const TLI) {
// First pass to check if there is at least one merge. If not, we don't do
// anything and we keep analysis passes intact.
{
bool AtLeastOneMerged = false;
for (size_t I = 1; I < Comparisons_.size(); ++I) {
if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) {
AtLeastOneMerged = true;
break;
}
}
if (!AtLeastOneMerged) return false;
}
// Remove phi references to comparison blocks, they will be rebuilt as we
// merge the blocks.
for (const auto &Comparison : Comparisons_) {
Phi_.removeIncomingValue(Comparison.BB, false);
}
// Point the predecessors of the chain to the first comparison block (which is
// the new entry point).
if (EntryBlock_ != Comparisons_[0].BB)
EntryBlock_->replaceAllUsesWith(Comparisons_[0].BB);
// Effectively merge blocks.
int NumMerged = 1;
for (size_t I = 1; I < Comparisons_.size(); ++I) {
if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) {
++NumMerged;
} else {
// Merge all previous comparisons and start a new merge block.
mergeComparisons(
makeArrayRef(Comparisons_).slice(I - NumMerged, NumMerged),
Comparisons_[I].BB, Phi_, TLI);
NumMerged = 1;
}
}
mergeComparisons(makeArrayRef(Comparisons_)
.slice(Comparisons_.size() - NumMerged, NumMerged),
nullptr, Phi_, TLI);
return true;
}
void BCECmpChain::mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
BasicBlock *const NextBBInChain,
PHINode &Phi,
const TargetLibraryInfo *const TLI) {
assert(!Comparisons.empty());
const auto &FirstComparison = *Comparisons.begin();
BasicBlock *const BB = FirstComparison.BB;
LLVMContext &Context = BB->getContext();
if (Comparisons.size() >= 2) {
DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons\n");
const auto TotalSize =
std::accumulate(Comparisons.begin(), Comparisons.end(), 0,
[](int Size, const BCECmpBlock &C) {
return Size + C.SizeBits();
}) /
8;
// Incoming edges do not need to be updated, and both GEPs are already
// computing the right address, we just need to:
// - replace the two loads and the icmp with the memcmp
// - update the branch
// - update the incoming values in the phi.
FirstComparison.BranchI->eraseFromParent();
FirstComparison.CmpI->eraseFromParent();
FirstComparison.Lhs().LoadI->eraseFromParent();
FirstComparison.Rhs().LoadI->eraseFromParent();
IRBuilder<> Builder(BB);
const auto &DL = Phi.getModule()->getDataLayout();
Value *const MemCmpCall = emitMemCmp(
FirstComparison.Lhs().GEP, FirstComparison.Rhs().GEP, ConstantInt::get(DL.getIntPtrType(Context), TotalSize),
Builder, DL, TLI);
Value *const MemCmpIsZero = Builder.CreateICmpEQ(
MemCmpCall, ConstantInt::get(Type::getInt32Ty(Context), 0));
// Add a branch to the next basic block in the chain.
if (NextBBInChain) {
Builder.CreateCondBr(MemCmpIsZero, NextBBInChain, Phi.getParent());
Phi.addIncoming(ConstantInt::getFalse(Context), BB);
} else {
Builder.CreateBr(Phi.getParent());
Phi.addIncoming(MemCmpIsZero, BB);
}
// Delete merged blocks.
for (size_t I = 1; I < Comparisons.size(); ++I) {
BasicBlock *CBB = Comparisons[I].BB;
CBB->replaceAllUsesWith(BB);
CBB->eraseFromParent();
}
} else {
assert(Comparisons.size() == 1);
// There are no blocks to merge, but we still need to update the branches.
DEBUG(dbgs() << "Only one comparison, updating branches\n");
if (NextBBInChain) {
if (FirstComparison.BranchI->isConditional()) {
DEBUG(dbgs() << "conditional -> conditional\n");
// Just update the "true" target, the "false" target should already be
// the phi block.
assert(FirstComparison.BranchI->getSuccessor(1) == Phi.getParent());
FirstComparison.BranchI->setSuccessor(0, NextBBInChain);
Phi.addIncoming(ConstantInt::getFalse(Context), BB);
} else {
DEBUG(dbgs() << "unconditional -> conditional\n");
// Replace the unconditional branch by a conditional one.
FirstComparison.BranchI->eraseFromParent();
IRBuilder<> Builder(BB);
Builder.CreateCondBr(FirstComparison.CmpI, NextBBInChain,
Phi.getParent());
Phi.addIncoming(FirstComparison.CmpI, BB);
}
} else {
if (FirstComparison.BranchI->isConditional()) {
DEBUG(dbgs() << "conditional -> unconditional\n");
// Replace the conditional branch by an unconditional one.
FirstComparison.BranchI->eraseFromParent();
IRBuilder<> Builder(BB);
Builder.CreateBr(Phi.getParent());
Phi.addIncoming(FirstComparison.CmpI, BB);
} else {
DEBUG(dbgs() << "unconditional -> unconditional\n");
Phi.addIncoming(FirstComparison.CmpI, BB);
}
}
}
}
std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
BasicBlock *const LastBlock,
int NumBlocks) {
// Walk up from the last block to find other blocks.
std::vector<BasicBlock *> Blocks(NumBlocks);
BasicBlock *CurBlock = LastBlock;
for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) {
if (CurBlock->hasAddressTaken()) {
// Somebody is jumping to the block through an address, all bets are
// off.
DEBUG(dbgs() << "skip: block " << BlockIndex
<< " has its address taken\n");
return {};
}
Blocks[BlockIndex] = CurBlock;
auto *SinglePredecessor = CurBlock->getSinglePredecessor();
if (!SinglePredecessor) {
// The block has two or more predecessors.
DEBUG(dbgs() << "skip: block " << BlockIndex
<< " has two or more predecessors\n");
return {};
}
if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) {
// The block does not link back to the phi.
DEBUG(dbgs() << "skip: block " << BlockIndex
<< " does not link back to the phi\n");
return {};
}
CurBlock = SinglePredecessor;
}
Blocks[0] = CurBlock;
return Blocks;
}
bool processPhi(PHINode &Phi, const TargetLibraryInfo *const TLI) {
DEBUG(dbgs() << "processPhi()\n");
if (Phi.getNumIncomingValues() <= 1) {
DEBUG(dbgs() << "skip: only one incoming value in phi\n");
return false;
}
// We are looking for something that has the following structure:
// bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+
// \ \ \ \
// ne ne ne \
// \ \ \ v
// +------------+-----------+----------> bb_phi
//
// - The last basic block (bb4 here) must branch unconditionally to bb_phi.
// It's the only block that contributes a non-constant value to the Phi.
// - All other blocks (b1, b2, b3) must have exactly two successors, one of
// them being the phi block.
// - All intermediate blocks (bb2, bb3) must have only one predecessor.
// - Blocks cannot do other work besides the comparison, see doesOtherWork()
// The blocks are not necessarily ordered in the phi, so we start from the
// last block and reconstruct the order.
BasicBlock *LastBlock = nullptr;
for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) {
if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue;
if (LastBlock) {
// There are several non-constant values.
DEBUG(dbgs() << "skip: several non-constant values\n");
return false;
}
LastBlock = Phi.getIncomingBlock(I);
}
if (!LastBlock) {
// There is no non-constant block.
DEBUG(dbgs() << "skip: no non-constant block\n");
return false;
}
if (LastBlock->getSingleSuccessor() != Phi.getParent()) {
DEBUG(dbgs() << "skip: last block non-phi successor\n");
return false;
}
const auto Blocks =
getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues());
if (Blocks.empty()) return false;
BCECmpChain CmpChain(Blocks, Phi);
if (CmpChain.size() < 2) {
DEBUG(dbgs() << "skip: only one compare block\n");
return false;
}
return CmpChain.simplify(TLI);
}
class MergeICmps : public FunctionPass {
public:
static char ID;
MergeICmps() : FunctionPass(ID) {
initializeMergeICmpsPass(*PassRegistry::getPassRegistry());
}
bool runOnFunction(Function &F) override {
if (skipFunction(F)) return false;
const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
auto PA = runImpl(F, &TLI, &TTI);
return !PA.areAllPreserved();
}
private:
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<TargetLibraryInfoWrapperPass>();
AU.addRequired<TargetTransformInfoWrapperPass>();
}
PreservedAnalyses runImpl(Function &F, const TargetLibraryInfo *TLI,
const TargetTransformInfo *TTI);
};
PreservedAnalyses MergeICmps::runImpl(Function &F, const TargetLibraryInfo *TLI,
const TargetTransformInfo *TTI) {
DEBUG(dbgs() << "MergeICmpsPass: " << F.getName() << "\n");
// We only try merging comparisons if the target wants to expand memcmp later.
// The rationale is to avoid turning small chains into memcmp calls.
if (!TTI->enableMemCmpExpansion(true)) return PreservedAnalyses::all();
bool MadeChange = false;
for (auto BBIt = ++F.begin(); BBIt != F.end(); ++BBIt) {
// A Phi operation is always first in a basic block.
if (auto *const Phi = dyn_cast<PHINode>(&*BBIt->begin()))
MadeChange |= processPhi(*Phi, TLI);
}
if (MadeChange) return PreservedAnalyses::none();
return PreservedAnalyses::all();
}
} // namespace
char MergeICmps::ID = 0;
INITIALIZE_PASS_BEGIN(MergeICmps, "mergeicmps",
"Merge contiguous icmps into a memcmp", false, false)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_END(MergeICmps, "mergeicmps",
"Merge contiguous icmps into a memcmp", false, false)
Pass *llvm::createMergeICmpsPass() { return new MergeICmps(); }