LLVM 20.0.0git
AggressiveInstCombine.cpp
Go to the documentation of this file.
1//===- AggressiveInstCombine.cpp ------------------------------------------===//
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 file implements the aggressive expression pattern combiner classes.
10// Currently, it handles expression patterns for:
11// * Truncate instruction
12//
13//===----------------------------------------------------------------------===//
14
17#include "llvm/ADT/Statistic.h"
27#include "llvm/IR/DataLayout.h"
28#include "llvm/IR/Dominators.h"
29#include "llvm/IR/Function.h"
30#include "llvm/IR/IRBuilder.h"
35
36using namespace llvm;
37using namespace PatternMatch;
38
39#define DEBUG_TYPE "aggressive-instcombine"
40
41STATISTIC(NumAnyOrAllBitsSet, "Number of any/all-bits-set patterns folded");
42STATISTIC(NumGuardedRotates,
43 "Number of guarded rotates transformed into funnel shifts");
44STATISTIC(NumGuardedFunnelShifts,
45 "Number of guarded funnel shifts transformed into funnel shifts");
46STATISTIC(NumPopCountRecognized, "Number of popcount idioms recognized");
47
49 "aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden,
50 cl::desc("Max number of instructions to scan for aggressive instcombine."));
51
53 "strncmp-inline-threshold", cl::init(3), cl::Hidden,
54 cl::desc("The maximum length of a constant string for a builtin string cmp "
55 "call eligible for inlining. The default value is 3."));
56
58 MemChrInlineThreshold("memchr-inline-threshold", cl::init(3), cl::Hidden,
59 cl::desc("The maximum length of a constant string to "
60 "inline a memchr call."));
61
62/// Match a pattern for a bitwise funnel/rotate operation that partially guards
63/// against undefined behavior by branching around the funnel-shift/rotation
64/// when the shift amount is 0.
66 if (I.getOpcode() != Instruction::PHI || I.getNumOperands() != 2)
67 return false;
68
69 // As with the one-use checks below, this is not strictly necessary, but we
70 // are being cautious to avoid potential perf regressions on targets that
71 // do not actually have a funnel/rotate instruction (where the funnel shift
72 // would be expanded back into math/shift/logic ops).
73 if (!isPowerOf2_32(I.getType()->getScalarSizeInBits()))
74 return false;
75
76 // Match V to funnel shift left/right and capture the source operands and
77 // shift amount.
78 auto matchFunnelShift = [](Value *V, Value *&ShVal0, Value *&ShVal1,
79 Value *&ShAmt) {
80 unsigned Width = V->getType()->getScalarSizeInBits();
81
82 // fshl(ShVal0, ShVal1, ShAmt)
83 // == (ShVal0 << ShAmt) | (ShVal1 >> (Width -ShAmt))
84 if (match(V, m_OneUse(m_c_Or(
85 m_Shl(m_Value(ShVal0), m_Value(ShAmt)),
86 m_LShr(m_Value(ShVal1),
87 m_Sub(m_SpecificInt(Width), m_Deferred(ShAmt))))))) {
88 return Intrinsic::fshl;
89 }
90
91 // fshr(ShVal0, ShVal1, ShAmt)
92 // == (ShVal0 >> ShAmt) | (ShVal1 << (Width - ShAmt))
93 if (match(V,
95 m_Value(ShAmt))),
96 m_LShr(m_Value(ShVal1), m_Deferred(ShAmt)))))) {
97 return Intrinsic::fshr;
98 }
99
101 };
102
103 // One phi operand must be a funnel/rotate operation, and the other phi
104 // operand must be the source value of that funnel/rotate operation:
105 // phi [ rotate(RotSrc, ShAmt), FunnelBB ], [ RotSrc, GuardBB ]
106 // phi [ fshl(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal0, GuardBB ]
107 // phi [ fshr(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal1, GuardBB ]
108 PHINode &Phi = cast<PHINode>(I);
109 unsigned FunnelOp = 0, GuardOp = 1;
110 Value *P0 = Phi.getOperand(0), *P1 = Phi.getOperand(1);
111 Value *ShVal0, *ShVal1, *ShAmt;
112 Intrinsic::ID IID = matchFunnelShift(P0, ShVal0, ShVal1, ShAmt);
113 if (IID == Intrinsic::not_intrinsic ||
114 (IID == Intrinsic::fshl && ShVal0 != P1) ||
115 (IID == Intrinsic::fshr && ShVal1 != P1)) {
116 IID = matchFunnelShift(P1, ShVal0, ShVal1, ShAmt);
117 if (IID == Intrinsic::not_intrinsic ||
118 (IID == Intrinsic::fshl && ShVal0 != P0) ||
119 (IID == Intrinsic::fshr && ShVal1 != P0))
120 return false;
121 assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
122 "Pattern must match funnel shift left or right");
123 std::swap(FunnelOp, GuardOp);
124 }
125
126 // The incoming block with our source operand must be the "guard" block.
127 // That must contain a cmp+branch to avoid the funnel/rotate when the shift
128 // amount is equal to 0. The other incoming block is the block with the
129 // funnel/rotate.
130 BasicBlock *GuardBB = Phi.getIncomingBlock(GuardOp);
131 BasicBlock *FunnelBB = Phi.getIncomingBlock(FunnelOp);
132 Instruction *TermI = GuardBB->getTerminator();
133
134 // Ensure that the shift values dominate each block.
135 if (!DT.dominates(ShVal0, TermI) || !DT.dominates(ShVal1, TermI))
136 return false;
137
138 BasicBlock *PhiBB = Phi.getParent();
140 m_ZeroInt()),
141 m_SpecificBB(PhiBB), m_SpecificBB(FunnelBB))))
142 return false;
143
144 IRBuilder<> Builder(PhiBB, PhiBB->getFirstInsertionPt());
145
146 if (ShVal0 == ShVal1)
147 ++NumGuardedRotates;
148 else
149 ++NumGuardedFunnelShifts;
150
151 // If this is not a rotate then the select was blocking poison from the
152 // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
153 bool IsFshl = IID == Intrinsic::fshl;
154 if (ShVal0 != ShVal1) {
155 if (IsFshl && !llvm::isGuaranteedNotToBePoison(ShVal1))
156 ShVal1 = Builder.CreateFreeze(ShVal1);
157 else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(ShVal0))
158 ShVal0 = Builder.CreateFreeze(ShVal0);
159 }
160
161 // We matched a variation of this IR pattern:
162 // GuardBB:
163 // %cmp = icmp eq i32 %ShAmt, 0
164 // br i1 %cmp, label %PhiBB, label %FunnelBB
165 // FunnelBB:
166 // %sub = sub i32 32, %ShAmt
167 // %shr = lshr i32 %ShVal1, %sub
168 // %shl = shl i32 %ShVal0, %ShAmt
169 // %fsh = or i32 %shr, %shl
170 // br label %PhiBB
171 // PhiBB:
172 // %cond = phi i32 [ %fsh, %FunnelBB ], [ %ShVal0, %GuardBB ]
173 // -->
174 // llvm.fshl.i32(i32 %ShVal0, i32 %ShVal1, i32 %ShAmt)
175 Function *F = Intrinsic::getDeclaration(Phi.getModule(), IID, Phi.getType());
176 Phi.replaceAllUsesWith(Builder.CreateCall(F, {ShVal0, ShVal1, ShAmt}));
177 return true;
178}
179
180/// This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and
181/// the bit indexes (Mask) needed by a masked compare. If we're matching a chain
182/// of 'and' ops, then we also need to capture the fact that we saw an
183/// "and X, 1", so that's an extra return value for that case.
184struct MaskOps {
185 Value *Root = nullptr;
188 bool FoundAnd1 = false;
189
190 MaskOps(unsigned BitWidth, bool MatchAnds)
191 : Mask(APInt::getZero(BitWidth)), MatchAndChain(MatchAnds) {}
192};
193
194/// This is a recursive helper for foldAnyOrAllBitsSet() that walks through a
195/// chain of 'and' or 'or' instructions looking for shift ops of a common source
196/// value. Examples:
197/// or (or (or X, (X >> 3)), (X >> 5)), (X >> 8)
198/// returns { X, 0x129 }
199/// and (and (X >> 1), 1), (X >> 4)
200/// returns { X, 0x12 }
201static bool matchAndOrChain(Value *V, MaskOps &MOps) {
202 Value *Op0, *Op1;
203 if (MOps.MatchAndChain) {
204 // Recurse through a chain of 'and' operands. This requires an extra check
205 // vs. the 'or' matcher: we must find an "and X, 1" instruction somewhere
206 // in the chain to know that all of the high bits are cleared.
207 if (match(V, m_And(m_Value(Op0), m_One()))) {
208 MOps.FoundAnd1 = true;
209 return matchAndOrChain(Op0, MOps);
210 }
211 if (match(V, m_And(m_Value(Op0), m_Value(Op1))))
212 return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
213 } else {
214 // Recurse through a chain of 'or' operands.
215 if (match(V, m_Or(m_Value(Op0), m_Value(Op1))))
216 return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);
217 }
218
219 // We need a shift-right or a bare value representing a compare of bit 0 of
220 // the original source operand.
221 Value *Candidate;
222 const APInt *BitIndex = nullptr;
223 if (!match(V, m_LShr(m_Value(Candidate), m_APInt(BitIndex))))
224 Candidate = V;
225
226 // Initialize result source operand.
227 if (!MOps.Root)
228 MOps.Root = Candidate;
229
230 // The shift constant is out-of-range? This code hasn't been simplified.
231 if (BitIndex && BitIndex->uge(MOps.Mask.getBitWidth()))
232 return false;
233
234 // Fill in the mask bit derived from the shift constant.
235 MOps.Mask.setBit(BitIndex ? BitIndex->getZExtValue() : 0);
236 return MOps.Root == Candidate;
237}
238
239/// Match patterns that correspond to "any-bits-set" and "all-bits-set".
240/// These will include a chain of 'or' or 'and'-shifted bits from a
241/// common source value:
242/// and (or (lshr X, C), ...), 1 --> (X & CMask) != 0
243/// and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask
244/// Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns
245/// that differ only with a final 'not' of the result. We expect that final
246/// 'not' to be folded with the compare that we create here (invert predicate).
248 // The 'any-bits-set' ('or' chain) pattern is simpler to match because the
249 // final "and X, 1" instruction must be the final op in the sequence.
250 bool MatchAllBitsSet;
252 MatchAllBitsSet = true;
253 else if (match(&I, m_And(m_OneUse(m_Or(m_Value(), m_Value())), m_One())))
254 MatchAllBitsSet = false;
255 else
256 return false;
257
258 MaskOps MOps(I.getType()->getScalarSizeInBits(), MatchAllBitsSet);
259 if (MatchAllBitsSet) {
260 if (!matchAndOrChain(cast<BinaryOperator>(&I), MOps) || !MOps.FoundAnd1)
261 return false;
262 } else {
263 if (!matchAndOrChain(cast<BinaryOperator>(&I)->getOperand(0), MOps))
264 return false;
265 }
266
267 // The pattern was found. Create a masked compare that replaces all of the
268 // shift and logic ops.
269 IRBuilder<> Builder(&I);
270 Constant *Mask = ConstantInt::get(I.getType(), MOps.Mask);
271 Value *And = Builder.CreateAnd(MOps.Root, Mask);
272 Value *Cmp = MatchAllBitsSet ? Builder.CreateICmpEQ(And, Mask)
273 : Builder.CreateIsNotNull(And);
274 Value *Zext = Builder.CreateZExt(Cmp, I.getType());
275 I.replaceAllUsesWith(Zext);
276 ++NumAnyOrAllBitsSet;
277 return true;
278}
279
280// Try to recognize below function as popcount intrinsic.
281// This is the "best" algorithm from
282// http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
283// Also used in TargetLowering::expandCTPOP().
284//
285// int popcount(unsigned int i) {
286// i = i - ((i >> 1) & 0x55555555);
287// i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
288// i = ((i + (i >> 4)) & 0x0F0F0F0F);
289// return (i * 0x01010101) >> 24;
290// }
292 if (I.getOpcode() != Instruction::LShr)
293 return false;
294
295 Type *Ty = I.getType();
296 if (!Ty->isIntOrIntVectorTy())
297 return false;
298
299 unsigned Len = Ty->getScalarSizeInBits();
300 // FIXME: fix Len == 8 and other irregular type lengths.
301 if (!(Len <= 128 && Len > 8 && Len % 8 == 0))
302 return false;
303
304 APInt Mask55 = APInt::getSplat(Len, APInt(8, 0x55));
305 APInt Mask33 = APInt::getSplat(Len, APInt(8, 0x33));
306 APInt Mask0F = APInt::getSplat(Len, APInt(8, 0x0F));
307 APInt Mask01 = APInt::getSplat(Len, APInt(8, 0x01));
308 APInt MaskShift = APInt(Len, Len - 8);
309
310 Value *Op0 = I.getOperand(0);
311 Value *Op1 = I.getOperand(1);
312 Value *MulOp0;
313 // Matching "(i * 0x01010101...) >> 24".
314 if ((match(Op0, m_Mul(m_Value(MulOp0), m_SpecificInt(Mask01)))) &&
316 Value *ShiftOp0;
317 // Matching "((i + (i >> 4)) & 0x0F0F0F0F...)".
318 if (match(MulOp0, m_And(m_c_Add(m_LShr(m_Value(ShiftOp0), m_SpecificInt(4)),
319 m_Deferred(ShiftOp0)),
320 m_SpecificInt(Mask0F)))) {
321 Value *AndOp0;
322 // Matching "(i & 0x33333333...) + ((i >> 2) & 0x33333333...)".
323 if (match(ShiftOp0,
324 m_c_Add(m_And(m_Value(AndOp0), m_SpecificInt(Mask33)),
326 m_SpecificInt(Mask33))))) {
327 Value *Root, *SubOp1;
328 // Matching "i - ((i >> 1) & 0x55555555...)".
329 if (match(AndOp0, m_Sub(m_Value(Root), m_Value(SubOp1))) &&
330 match(SubOp1, m_And(m_LShr(m_Specific(Root), m_SpecificInt(1)),
331 m_SpecificInt(Mask55)))) {
332 LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");
333 IRBuilder<> Builder(&I);
335 I.getModule(), Intrinsic::ctpop, I.getType());
336 I.replaceAllUsesWith(Builder.CreateCall(Func, {Root}));
337 ++NumPopCountRecognized;
338 return true;
339 }
340 }
341 }
342 }
343
344 return false;
345}
346
347/// Fold smin(smax(fptosi(x), C1), C2) to llvm.fptosi.sat(x), providing C1 and
348/// C2 saturate the value of the fp conversion. The transform is not reversable
349/// as the fptosi.sat is more defined than the input - all values produce a
350/// valid value for the fptosi.sat, where as some produce poison for original
351/// that were out of range of the integer conversion. The reversed pattern may
352/// use fmax and fmin instead. As we cannot directly reverse the transform, and
353/// it is not always profitable, we make it conditional on the cost being
354/// reported as lower by TTI.
356 // Look for min(max(fptosi, converting to fptosi_sat.
357 Value *In;
358 const APInt *MinC, *MaxC;
360 m_APInt(MinC))),
361 m_APInt(MaxC))) &&
363 m_APInt(MaxC))),
364 m_APInt(MinC))))
365 return false;
366
367 // Check that the constants clamp a saturate.
368 if (!(*MinC + 1).isPowerOf2() || -*MaxC != *MinC + 1)
369 return false;
370
371 Type *IntTy = I.getType();
372 Type *FpTy = In->getType();
373 Type *SatTy =
374 IntegerType::get(IntTy->getContext(), (*MinC + 1).exactLogBase2() + 1);
375 if (auto *VecTy = dyn_cast<VectorType>(IntTy))
376 SatTy = VectorType::get(SatTy, VecTy->getElementCount());
377
378 // Get the cost of the intrinsic, and check that against the cost of
379 // fptosi+smin+smax
381 IntrinsicCostAttributes(Intrinsic::fptosi_sat, SatTy, {In}, {FpTy}),
383 SatCost += TTI.getCastInstrCost(Instruction::SExt, IntTy, SatTy,
386
388 Instruction::FPToSI, IntTy, FpTy, TTI::CastContextHint::None,
390 MinMaxCost += TTI.getIntrinsicInstrCost(
391 IntrinsicCostAttributes(Intrinsic::smin, IntTy, {IntTy}),
393 MinMaxCost += TTI.getIntrinsicInstrCost(
394 IntrinsicCostAttributes(Intrinsic::smax, IntTy, {IntTy}),
396
397 if (SatCost >= MinMaxCost)
398 return false;
399
400 IRBuilder<> Builder(&I);
401 Function *Fn = Intrinsic::getDeclaration(I.getModule(), Intrinsic::fptosi_sat,
402 {SatTy, FpTy});
403 Value *Sat = Builder.CreateCall(Fn, In);
404 I.replaceAllUsesWith(Builder.CreateSExt(Sat, IntTy));
405 return true;
406}
407
408/// Try to replace a mathlib call to sqrt with the LLVM intrinsic. This avoids
409/// pessimistic codegen that has to account for setting errno and can enable
410/// vectorization.
413 DominatorTree &DT) {
414
415 Module *M = Call->getModule();
416
417 // If (1) this is a sqrt libcall, (2) we can assume that NAN is not created
418 // (because NNAN or the operand arg must not be less than -0.0) and (2) we
419 // would not end up lowering to a libcall anyway (which could change the value
420 // of errno), then:
421 // (1) errno won't be set.
422 // (2) it is safe to convert this to an intrinsic call.
423 Type *Ty = Call->getType();
424 Value *Arg = Call->getArgOperand(0);
425 if (TTI.haveFastSqrt(Ty) &&
426 (Call->hasNoNaNs() ||
428 Arg, 0,
429 SimplifyQuery(Call->getDataLayout(), &TLI, &DT, &AC, Call)))) {
430 IRBuilder<> Builder(Call);
432 Builder.setFastMathFlags(Call->getFastMathFlags());
433
434 Function *Sqrt = Intrinsic::getDeclaration(M, Intrinsic::sqrt, Ty);
435 Value *NewSqrt = Builder.CreateCall(Sqrt, Arg, "sqrt");
436 Call->replaceAllUsesWith(NewSqrt);
437
438 // Explicitly erase the old call because a call with side effects is not
439 // trivially dead.
440 Call->eraseFromParent();
441 return true;
442 }
443
444 return false;
445}
446
447// Check if this array of constants represents a cttz table.
448// Iterate over the elements from \p Table by trying to find/match all
449// the numbers from 0 to \p InputBits that should represent cttz results.
450static bool isCTTZTable(const ConstantDataArray &Table, uint64_t Mul,
451 uint64_t Shift, uint64_t InputBits) {
452 unsigned Length = Table.getNumElements();
453 if (Length < InputBits || Length > InputBits * 2)
454 return false;
455
456 APInt Mask = APInt::getBitsSetFrom(InputBits, Shift);
457 unsigned Matched = 0;
458
459 for (unsigned i = 0; i < Length; i++) {
460 uint64_t Element = Table.getElementAsInteger(i);
461 if (Element >= InputBits)
462 continue;
463
464 // Check if \p Element matches a concrete answer. It could fail for some
465 // elements that are never accessed, so we keep iterating over each element
466 // from the table. The number of matched elements should be equal to the
467 // number of potential right answers which is \p InputBits actually.
468 if ((((Mul << Element) & Mask.getZExtValue()) >> Shift) == i)
469 Matched++;
470 }
471
472 return Matched == InputBits;
473}
474
475// Try to recognize table-based ctz implementation.
476// E.g., an example in C (for more cases please see the llvm/tests):
477// int f(unsigned x) {
478// static const char table[32] =
479// {0, 1, 28, 2, 29, 14, 24, 3, 30,
480// 22, 20, 15, 25, 17, 4, 8, 31, 27,
481// 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
482// return table[((unsigned)((x & -x) * 0x077CB531U)) >> 27];
483// }
484// this can be lowered to `cttz` instruction.
485// There is also a special case when the element is 0.
486//
487// Here are some examples or LLVM IR for a 64-bit target:
488//
489// CASE 1:
490// %sub = sub i32 0, %x
491// %and = and i32 %sub, %x
492// %mul = mul i32 %and, 125613361
493// %shr = lshr i32 %mul, 27
494// %idxprom = zext i32 %shr to i64
495// %arrayidx = getelementptr inbounds [32 x i8], [32 x i8]* @ctz1.table, i64 0,
496// i64 %idxprom
497// %0 = load i8, i8* %arrayidx, align 1, !tbaa !8
498//
499// CASE 2:
500// %sub = sub i32 0, %x
501// %and = and i32 %sub, %x
502// %mul = mul i32 %and, 72416175
503// %shr = lshr i32 %mul, 26
504// %idxprom = zext i32 %shr to i64
505// %arrayidx = getelementptr inbounds [64 x i16], [64 x i16]* @ctz2.table,
506// i64 0, i64 %idxprom
507// %0 = load i16, i16* %arrayidx, align 2, !tbaa !8
508//
509// CASE 3:
510// %sub = sub i32 0, %x
511// %and = and i32 %sub, %x
512// %mul = mul i32 %and, 81224991
513// %shr = lshr i32 %mul, 27
514// %idxprom = zext i32 %shr to i64
515// %arrayidx = getelementptr inbounds [32 x i32], [32 x i32]* @ctz3.table,
516// i64 0, i64 %idxprom
517// %0 = load i32, i32* %arrayidx, align 4, !tbaa !8
518//
519// CASE 4:
520// %sub = sub i64 0, %x
521// %and = and i64 %sub, %x
522// %mul = mul i64 %and, 283881067100198605
523// %shr = lshr i64 %mul, 58
524// %arrayidx = getelementptr inbounds [64 x i8], [64 x i8]* @table, i64 0,
525// i64 %shr
526// %0 = load i8, i8* %arrayidx, align 1, !tbaa !8
527//
528// All this can be lowered to @llvm.cttz.i32/64 intrinsic.
530 LoadInst *LI = dyn_cast<LoadInst>(&I);
531 if (!LI)
532 return false;
533
534 Type *AccessType = LI->getType();
535 if (!AccessType->isIntegerTy())
536 return false;
537
538 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getPointerOperand());
539 if (!GEP || !GEP->isInBounds() || GEP->getNumIndices() != 2)
540 return false;
541
542 if (!GEP->getSourceElementType()->isArrayTy())
543 return false;
544
545 uint64_t ArraySize = GEP->getSourceElementType()->getArrayNumElements();
546 if (ArraySize != 32 && ArraySize != 64)
547 return false;
548
549 GlobalVariable *GVTable = dyn_cast<GlobalVariable>(GEP->getPointerOperand());
550 if (!GVTable || !GVTable->hasInitializer() || !GVTable->isConstant())
551 return false;
552
553 ConstantDataArray *ConstData =
554 dyn_cast<ConstantDataArray>(GVTable->getInitializer());
555 if (!ConstData)
556 return false;
557
558 if (!match(GEP->idx_begin()->get(), m_ZeroInt()))
559 return false;
560
561 Value *Idx2 = std::next(GEP->idx_begin())->get();
562 Value *X1;
563 uint64_t MulConst, ShiftConst;
564 // FIXME: 64-bit targets have `i64` type for the GEP index, so this match will
565 // probably fail for other (e.g. 32-bit) targets.
566 if (!match(Idx2, m_ZExtOrSelf(
568 m_ConstantInt(MulConst)),
569 m_ConstantInt(ShiftConst)))))
570 return false;
571
572 unsigned InputBits = X1->getType()->getScalarSizeInBits();
573 if (InputBits != 32 && InputBits != 64)
574 return false;
575
576 // Shift should extract top 5..7 bits.
577 if (InputBits - Log2_32(InputBits) != ShiftConst &&
578 InputBits - Log2_32(InputBits) - 1 != ShiftConst)
579 return false;
580
581 if (!isCTTZTable(*ConstData, MulConst, ShiftConst, InputBits))
582 return false;
583
584 auto ZeroTableElem = ConstData->getElementAsInteger(0);
585 bool DefinedForZero = ZeroTableElem == InputBits;
586
587 IRBuilder<> B(LI);
588 ConstantInt *BoolConst = B.getInt1(!DefinedForZero);
589 Type *XType = X1->getType();
590 auto Cttz = B.CreateIntrinsic(Intrinsic::cttz, {XType}, {X1, BoolConst});
591 Value *ZExtOrTrunc = nullptr;
592
593 if (DefinedForZero) {
594 ZExtOrTrunc = B.CreateZExtOrTrunc(Cttz, AccessType);
595 } else {
596 // If the value in elem 0 isn't the same as InputBits, we still want to
597 // produce the value from the table.
598 auto Cmp = B.CreateICmpEQ(X1, ConstantInt::get(XType, 0));
599 auto Select =
600 B.CreateSelect(Cmp, ConstantInt::get(XType, ZeroTableElem), Cttz);
601
602 // NOTE: If the table[0] is 0, but the cttz(0) is defined by the Target
603 // it should be handled as: `cttz(x) & (typeSize - 1)`.
604
605 ZExtOrTrunc = B.CreateZExtOrTrunc(Select, AccessType);
606 }
607
608 LI->replaceAllUsesWith(ZExtOrTrunc);
609
610 return true;
611}
612
613/// This is used by foldLoadsRecursive() to capture a Root Load node which is
614/// of type or(load, load) and recursively build the wide load. Also capture the
615/// shift amount, zero extend type and loadSize.
616struct LoadOps {
617 LoadInst *Root = nullptr;
619 bool FoundRoot = false;
621 const APInt *Shift = nullptr;
624};
625
626// Identify and Merge consecutive loads recursively which is of the form
627// (ZExt(L1) << shift1) | (ZExt(L2) << shift2) -> ZExt(L3) << shift1
628// (ZExt(L1) << shift1) | ZExt(L2) -> ZExt(L3)
629static bool foldLoadsRecursive(Value *V, LoadOps &LOps, const DataLayout &DL,
630 AliasAnalysis &AA) {
631 const APInt *ShAmt2 = nullptr;
632 Value *X;
633 Instruction *L1, *L2;
634
635 // Go to the last node with loads.
636 if (match(V, m_OneUse(m_c_Or(
637 m_Value(X),
639 m_APInt(ShAmt2)))))) ||
642 if (!foldLoadsRecursive(X, LOps, DL, AA) && LOps.FoundRoot)
643 // Avoid Partial chain merge.
644 return false;
645 } else
646 return false;
647
648 // Check if the pattern has loads
649 LoadInst *LI1 = LOps.Root;
650 const APInt *ShAmt1 = LOps.Shift;
651 if (LOps.FoundRoot == false &&
654 m_APInt(ShAmt1)))))) {
655 LI1 = dyn_cast<LoadInst>(L1);
656 }
657 LoadInst *LI2 = dyn_cast<LoadInst>(L2);
658
659 // Check if loads are same, atomic, volatile and having same address space.
660 if (LI1 == LI2 || !LI1 || !LI2 || !LI1->isSimple() || !LI2->isSimple() ||
662 return false;
663
664 // Check if Loads come from same BB.
665 if (LI1->getParent() != LI2->getParent())
666 return false;
667
668 // Find the data layout
669 bool IsBigEndian = DL.isBigEndian();
670
671 // Check if loads are consecutive and same size.
672 Value *Load1Ptr = LI1->getPointerOperand();
673 APInt Offset1(DL.getIndexTypeSizeInBits(Load1Ptr->getType()), 0);
674 Load1Ptr =
675 Load1Ptr->stripAndAccumulateConstantOffsets(DL, Offset1,
676 /* AllowNonInbounds */ true);
677
678 Value *Load2Ptr = LI2->getPointerOperand();
679 APInt Offset2(DL.getIndexTypeSizeInBits(Load2Ptr->getType()), 0);
680 Load2Ptr =
681 Load2Ptr->stripAndAccumulateConstantOffsets(DL, Offset2,
682 /* AllowNonInbounds */ true);
683
684 // Verify if both loads have same base pointers and load sizes are same.
685 uint64_t LoadSize1 = LI1->getType()->getPrimitiveSizeInBits();
686 uint64_t LoadSize2 = LI2->getType()->getPrimitiveSizeInBits();
687 if (Load1Ptr != Load2Ptr || LoadSize1 != LoadSize2)
688 return false;
689
690 // Support Loadsizes greater or equal to 8bits and only power of 2.
691 if (LoadSize1 < 8 || !isPowerOf2_64(LoadSize1))
692 return false;
693
694 // Alias Analysis to check for stores b/w the loads.
695 LoadInst *Start = LOps.FoundRoot ? LOps.RootInsert : LI1, *End = LI2;
696 MemoryLocation Loc;
697 if (!Start->comesBefore(End)) {
698 std::swap(Start, End);
700 if (LOps.FoundRoot)
701 Loc = Loc.getWithNewSize(LOps.LoadSize);
702 } else
704 unsigned NumScanned = 0;
705 for (Instruction &Inst :
706 make_range(Start->getIterator(), End->getIterator())) {
707 if (Inst.mayWriteToMemory() && isModSet(AA.getModRefInfo(&Inst, Loc)))
708 return false;
709
710 // Ignore debug info so that's not counted against MaxInstrsToScan.
711 // Otherwise debug info could affect codegen.
712 if (!isa<DbgInfoIntrinsic>(Inst) && ++NumScanned > MaxInstrsToScan)
713 return false;
714 }
715
716 // Make sure Load with lower Offset is at LI1
717 bool Reverse = false;
718 if (Offset2.slt(Offset1)) {
719 std::swap(LI1, LI2);
720 std::swap(ShAmt1, ShAmt2);
721 std::swap(Offset1, Offset2);
722 std::swap(Load1Ptr, Load2Ptr);
723 std::swap(LoadSize1, LoadSize2);
724 Reverse = true;
725 }
726
727 // Big endian swap the shifts
728 if (IsBigEndian)
729 std::swap(ShAmt1, ShAmt2);
730
731 // Find Shifts values.
732 uint64_t Shift1 = 0, Shift2 = 0;
733 if (ShAmt1)
734 Shift1 = ShAmt1->getZExtValue();
735 if (ShAmt2)
736 Shift2 = ShAmt2->getZExtValue();
737
738 // First load is always LI1. This is where we put the new load.
739 // Use the merged load size available from LI1 for forward loads.
740 if (LOps.FoundRoot) {
741 if (!Reverse)
742 LoadSize1 = LOps.LoadSize;
743 else
744 LoadSize2 = LOps.LoadSize;
745 }
746
747 // Verify if shift amount and load index aligns and verifies that loads
748 // are consecutive.
749 uint64_t ShiftDiff = IsBigEndian ? LoadSize2 : LoadSize1;
750 uint64_t PrevSize =
751 DL.getTypeStoreSize(IntegerType::get(LI1->getContext(), LoadSize1));
752 if ((Shift2 - Shift1) != ShiftDiff || (Offset2 - Offset1) != PrevSize)
753 return false;
754
755 // Update LOps
756 AAMDNodes AATags1 = LOps.AATags;
757 AAMDNodes AATags2 = LI2->getAAMetadata();
758 if (LOps.FoundRoot == false) {
759 LOps.FoundRoot = true;
760 AATags1 = LI1->getAAMetadata();
761 }
762 LOps.LoadSize = LoadSize1 + LoadSize2;
763 LOps.RootInsert = Start;
764
765 // Concatenate the AATags of the Merged Loads.
766 LOps.AATags = AATags1.concat(AATags2);
767
768 LOps.Root = LI1;
769 LOps.Shift = ShAmt1;
770 LOps.ZextType = X->getType();
771 return true;
772}
773
774// For a given BB instruction, evaluate all loads in the chain that form a
775// pattern which suggests that the loads can be combined. The one and only use
776// of the loads is to form a wider load.
779 const DominatorTree &DT) {
780 // Only consider load chains of scalar values.
781 if (isa<VectorType>(I.getType()))
782 return false;
783
784 LoadOps LOps;
785 if (!foldLoadsRecursive(&I, LOps, DL, AA) || !LOps.FoundRoot)
786 return false;
787
788 IRBuilder<> Builder(&I);
789 LoadInst *NewLoad = nullptr, *LI1 = LOps.Root;
790
791 IntegerType *WiderType = IntegerType::get(I.getContext(), LOps.LoadSize);
792 // TTI based checks if we want to proceed with wider load
793 bool Allowed = TTI.isTypeLegal(WiderType);
794 if (!Allowed)
795 return false;
796
797 unsigned AS = LI1->getPointerAddressSpace();
798 unsigned Fast = 0;
799 Allowed = TTI.allowsMisalignedMemoryAccesses(I.getContext(), LOps.LoadSize,
800 AS, LI1->getAlign(), &Fast);
801 if (!Allowed || !Fast)
802 return false;
803
804 // Get the Index and Ptr for the new GEP.
805 Value *Load1Ptr = LI1->getPointerOperand();
806 Builder.SetInsertPoint(LOps.RootInsert);
807 if (!DT.dominates(Load1Ptr, LOps.RootInsert)) {
808 APInt Offset1(DL.getIndexTypeSizeInBits(Load1Ptr->getType()), 0);
809 Load1Ptr = Load1Ptr->stripAndAccumulateConstantOffsets(
810 DL, Offset1, /* AllowNonInbounds */ true);
811 Load1Ptr = Builder.CreatePtrAdd(Load1Ptr,
812 Builder.getInt32(Offset1.getZExtValue()));
813 }
814 // Generate wider load.
815 NewLoad = Builder.CreateAlignedLoad(WiderType, Load1Ptr, LI1->getAlign(),
816 LI1->isVolatile(), "");
817 NewLoad->takeName(LI1);
818 // Set the New Load AATags Metadata.
819 if (LOps.AATags)
820 NewLoad->setAAMetadata(LOps.AATags);
821
822 Value *NewOp = NewLoad;
823 // Check if zero extend needed.
824 if (LOps.ZextType)
825 NewOp = Builder.CreateZExt(NewOp, LOps.ZextType);
826
827 // Check if shift needed. We need to shift with the amount of load1
828 // shift if not zero.
829 if (LOps.Shift)
830 NewOp = Builder.CreateShl(NewOp, ConstantInt::get(I.getContext(), *LOps.Shift));
831 I.replaceAllUsesWith(NewOp);
832
833 return true;
834}
835
836// Calculate GEP Stride and accumulated const ModOffset. Return Stride and
837// ModOffset
838static std::pair<APInt, APInt>
840 unsigned BW = DL.getIndexTypeSizeInBits(PtrOp->getType());
841 std::optional<APInt> Stride;
842 APInt ModOffset(BW, 0);
843 // Return a minimum gep stride, greatest common divisor of consective gep
844 // index scales(c.f. Bézout's identity).
845 while (auto *GEP = dyn_cast<GEPOperator>(PtrOp)) {
846 MapVector<Value *, APInt> VarOffsets;
847 if (!GEP->collectOffset(DL, BW, VarOffsets, ModOffset))
848 break;
849
850 for (auto [V, Scale] : VarOffsets) {
851 // Only keep a power of two factor for non-inbounds
852 if (!GEP->isInBounds())
853 Scale = APInt::getOneBitSet(Scale.getBitWidth(), Scale.countr_zero());
854
855 if (!Stride)
856 Stride = Scale;
857 else
858 Stride = APIntOps::GreatestCommonDivisor(*Stride, Scale);
859 }
860
861 PtrOp = GEP->getPointerOperand();
862 }
863
864 // Check whether pointer arrives back at Global Variable via at least one GEP.
865 // Even if it doesn't, we can check by alignment.
866 if (!isa<GlobalVariable>(PtrOp) || !Stride)
867 return {APInt(BW, 1), APInt(BW, 0)};
868
869 // In consideration of signed GEP indices, non-negligible offset become
870 // remainder of division by minimum GEP stride.
871 ModOffset = ModOffset.srem(*Stride);
872 if (ModOffset.isNegative())
873 ModOffset += *Stride;
874
875 return {*Stride, ModOffset};
876}
877
878/// If C is a constant patterned array and all valid loaded results for given
879/// alignment are same to a constant, return that constant.
881 auto *LI = dyn_cast<LoadInst>(&I);
882 if (!LI || LI->isVolatile())
883 return false;
884
885 // We can only fold the load if it is from a constant global with definitive
886 // initializer. Skip expensive logic if this is not the case.
887 auto *PtrOp = LI->getPointerOperand();
888 auto *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(PtrOp));
889 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
890 return false;
891
892 // Bail for large initializers in excess of 4K to avoid too many scans.
893 Constant *C = GV->getInitializer();
894 uint64_t GVSize = DL.getTypeAllocSize(C->getType());
895 if (!GVSize || 4096 < GVSize)
896 return false;
897
898 Type *LoadTy = LI->getType();
899 unsigned BW = DL.getIndexTypeSizeInBits(PtrOp->getType());
900 auto [Stride, ConstOffset] = getStrideAndModOffsetOfGEP(PtrOp, DL);
901
902 // Any possible offset could be multiple of GEP stride. And any valid
903 // offset is multiple of load alignment, so checking only multiples of bigger
904 // one is sufficient to say results' equality.
905 if (auto LA = LI->getAlign();
906 LA <= GV->getAlign().valueOrOne() && Stride.getZExtValue() < LA.value()) {
907 ConstOffset = APInt(BW, 0);
908 Stride = APInt(BW, LA.value());
909 }
910
911 Constant *Ca = ConstantFoldLoadFromConst(C, LoadTy, ConstOffset, DL);
912 if (!Ca)
913 return false;
914
915 unsigned E = GVSize - DL.getTypeStoreSize(LoadTy);
916 for (; ConstOffset.getZExtValue() <= E; ConstOffset += Stride)
917 if (Ca != ConstantFoldLoadFromConst(C, LoadTy, ConstOffset, DL))
918 return false;
919
920 I.replaceAllUsesWith(Ca);
921
922 return true;
923}
924
925namespace {
926class StrNCmpInliner {
927public:
928 StrNCmpInliner(CallInst *CI, LibFunc Func, DomTreeUpdater *DTU,
929 const DataLayout &DL)
930 : CI(CI), Func(Func), DTU(DTU), DL(DL) {}
931
932 bool optimizeStrNCmp();
933
934private:
935 void inlineCompare(Value *LHS, StringRef RHS, uint64_t N, bool Swapped);
936
937 CallInst *CI;
939 DomTreeUpdater *DTU;
940 const DataLayout &DL;
941};
942
943} // namespace
944
945/// First we normalize calls to strncmp/strcmp to the form of
946/// compare(s1, s2, N), which means comparing first N bytes of s1 and s2
947/// (without considering '\0').
948///
949/// Examples:
950///
951/// \code
952/// strncmp(s, "a", 3) -> compare(s, "a", 2)
953/// strncmp(s, "abc", 3) -> compare(s, "abc", 3)
954/// strncmp(s, "a\0b", 3) -> compare(s, "a\0b", 2)
955/// strcmp(s, "a") -> compare(s, "a", 2)
956///
957/// char s2[] = {'a'}
958/// strncmp(s, s2, 3) -> compare(s, s2, 3)
959///
960/// char s2[] = {'a', 'b', 'c', 'd'}
961/// strncmp(s, s2, 3) -> compare(s, s2, 3)
962/// \endcode
963///
964/// We only handle cases where N and exactly one of s1 and s2 are constant.
965/// Cases that s1 and s2 are both constant are already handled by the
966/// instcombine pass.
967///
968/// We do not handle cases where N > StrNCmpInlineThreshold.
969///
970/// We also do not handles cases where N < 2, which are already
971/// handled by the instcombine pass.
972///
973bool StrNCmpInliner::optimizeStrNCmp() {
975 return false;
976
978 return false;
979
980 Value *Str1P = CI->getArgOperand(0);
981 Value *Str2P = CI->getArgOperand(1);
982 // Should be handled elsewhere.
983 if (Str1P == Str2P)
984 return false;
985
986 StringRef Str1, Str2;
987 bool HasStr1 = getConstantStringInfo(Str1P, Str1, /*TrimAtNul=*/false);
988 bool HasStr2 = getConstantStringInfo(Str2P, Str2, /*TrimAtNul=*/false);
989 if (HasStr1 == HasStr2)
990 return false;
991
992 // Note that '\0' and characters after it are not trimmed.
993 StringRef Str = HasStr1 ? Str1 : Str2;
994 Value *StrP = HasStr1 ? Str2P : Str1P;
995
996 size_t Idx = Str.find('\0');
998 if (Func == LibFunc_strncmp) {
999 if (auto *ConstInt = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
1000 N = std::min(N, ConstInt->getZExtValue());
1001 else
1002 return false;
1003 }
1004 // Now N means how many bytes we need to compare at most.
1005 if (N > Str.size() || N < 2 || N > StrNCmpInlineThreshold)
1006 return false;
1007
1008 // Cases where StrP has two or more dereferenceable bytes might be better
1009 // optimized elsewhere.
1010 bool CanBeNull = false, CanBeFreed = false;
1011 if (StrP->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed) > 1)
1012 return false;
1013 inlineCompare(StrP, Str, N, HasStr1);
1014 return true;
1015}
1016
1017/// Convert
1018///
1019/// \code
1020/// ret = compare(s1, s2, N)
1021/// \endcode
1022///
1023/// into
1024///
1025/// \code
1026/// ret = (int)s1[0] - (int)s2[0]
1027/// if (ret != 0)
1028/// goto NE
1029/// ...
1030/// ret = (int)s1[N-2] - (int)s2[N-2]
1031/// if (ret != 0)
1032/// goto NE
1033/// ret = (int)s1[N-1] - (int)s2[N-1]
1034/// NE:
1035/// \endcode
1036///
1037/// CFG before and after the transformation:
1038///
1039/// (before)
1040/// BBCI
1041///
1042/// (after)
1043/// BBCI -> BBSubs[0] (sub,icmp) --NE-> BBNE -> BBTail
1044/// | ^
1045/// E |
1046/// | |
1047/// BBSubs[1] (sub,icmp) --NE-----+
1048/// ... |
1049/// BBSubs[N-1] (sub) ---------+
1050///
1051void StrNCmpInliner::inlineCompare(Value *LHS, StringRef RHS, uint64_t N,
1052 bool Swapped) {
1053 auto &Ctx = CI->getContext();
1054 IRBuilder<> B(Ctx);
1055
1056 BasicBlock *BBCI = CI->getParent();
1057 BasicBlock *BBTail =
1058 SplitBlock(BBCI, CI, DTU, nullptr, nullptr, BBCI->getName() + ".tail");
1059
1061 for (uint64_t I = 0; I < N; ++I)
1062 BBSubs.push_back(
1063 BasicBlock::Create(Ctx, "sub_" + Twine(I), BBCI->getParent(), BBTail));
1064 BasicBlock *BBNE = BasicBlock::Create(Ctx, "ne", BBCI->getParent(), BBTail);
1065
1066 cast<BranchInst>(BBCI->getTerminator())->setSuccessor(0, BBSubs[0]);
1067
1068 B.SetInsertPoint(BBNE);
1069 PHINode *Phi = B.CreatePHI(CI->getType(), N);
1070 B.CreateBr(BBTail);
1071
1072 Value *Base = LHS;
1073 for (uint64_t i = 0; i < N; ++i) {
1074 B.SetInsertPoint(BBSubs[i]);
1075 Value *VL =
1076 B.CreateZExt(B.CreateLoad(B.getInt8Ty(),
1077 B.CreateInBoundsPtrAdd(Base, B.getInt64(i))),
1078 CI->getType());
1079 Value *VR =
1080 ConstantInt::get(CI->getType(), static_cast<unsigned char>(RHS[i]));
1081 Value *Sub = Swapped ? B.CreateSub(VR, VL) : B.CreateSub(VL, VR);
1082 if (i < N - 1)
1083 B.CreateCondBr(B.CreateICmpNE(Sub, ConstantInt::get(CI->getType(), 0)),
1084 BBNE, BBSubs[i + 1]);
1085 else
1086 B.CreateBr(BBNE);
1087
1088 Phi->addIncoming(Sub, BBSubs[i]);
1089 }
1090
1091 CI->replaceAllUsesWith(Phi);
1092 CI->eraseFromParent();
1093
1094 if (DTU) {
1096 Updates.push_back({DominatorTree::Insert, BBCI, BBSubs[0]});
1097 for (uint64_t i = 0; i < N; ++i) {
1098 if (i < N - 1)
1099 Updates.push_back({DominatorTree::Insert, BBSubs[i], BBSubs[i + 1]});
1100 Updates.push_back({DominatorTree::Insert, BBSubs[i], BBNE});
1101 }
1102 Updates.push_back({DominatorTree::Insert, BBNE, BBTail});
1103 Updates.push_back({DominatorTree::Delete, BBCI, BBTail});
1104 DTU->applyUpdates(Updates);
1105 }
1106}
1107
1108/// Convert memchr with a small constant string into a switch
1109static bool foldMemChr(CallInst *Call, DomTreeUpdater *DTU,
1110 const DataLayout &DL) {
1111 if (isa<Constant>(Call->getArgOperand(1)))
1112 return false;
1113
1114 StringRef Str;
1115 Value *Base = Call->getArgOperand(0);
1116 if (!getConstantStringInfo(Base, Str, /*TrimAtNul=*/false))
1117 return false;
1118
1119 uint64_t N = Str.size();
1120 if (auto *ConstInt = dyn_cast<ConstantInt>(Call->getArgOperand(2))) {
1121 uint64_t Val = ConstInt->getZExtValue();
1122 // Ignore the case that n is larger than the size of string.
1123 if (Val > N)
1124 return false;
1125 N = Val;
1126 } else
1127 return false;
1128
1130 return false;
1131
1132 BasicBlock *BB = Call->getParent();
1133 BasicBlock *BBNext = SplitBlock(BB, Call, DTU);
1134 IRBuilder<> IRB(BB);
1135 IntegerType *ByteTy = IRB.getInt8Ty();
1137 SwitchInst *SI = IRB.CreateSwitch(
1138 IRB.CreateTrunc(Call->getArgOperand(1), ByteTy), BBNext, N);
1139 Type *IndexTy = DL.getIndexType(Call->getType());
1141
1142 BasicBlock *BBSuccess = BasicBlock::Create(
1143 Call->getContext(), "memchr.success", BB->getParent(), BBNext);
1144 IRB.SetInsertPoint(BBSuccess);
1145 PHINode *IndexPHI = IRB.CreatePHI(IndexTy, N, "memchr.idx");
1146 Value *FirstOccursLocation = IRB.CreateInBoundsPtrAdd(Base, IndexPHI);
1147 IRB.CreateBr(BBNext);
1148 if (DTU)
1149 Updates.push_back({DominatorTree::Insert, BBSuccess, BBNext});
1150
1152 for (uint64_t I = 0; I < N; ++I) {
1153 ConstantInt *CaseVal = ConstantInt::get(ByteTy, Str[I]);
1154 if (!Cases.insert(CaseVal).second)
1155 continue;
1156
1157 BasicBlock *BBCase = BasicBlock::Create(Call->getContext(), "memchr.case",
1158 BB->getParent(), BBSuccess);
1159 SI->addCase(CaseVal, BBCase);
1160 IRB.SetInsertPoint(BBCase);
1161 IndexPHI->addIncoming(ConstantInt::get(IndexTy, I), BBCase);
1162 IRB.CreateBr(BBSuccess);
1163 if (DTU) {
1164 Updates.push_back({DominatorTree::Insert, BB, BBCase});
1165 Updates.push_back({DominatorTree::Insert, BBCase, BBSuccess});
1166 }
1167 }
1168
1169 PHINode *PHI =
1170 PHINode::Create(Call->getType(), 2, Call->getName(), BBNext->begin());
1171 PHI->addIncoming(Constant::getNullValue(Call->getType()), BB);
1172 PHI->addIncoming(FirstOccursLocation, BBSuccess);
1173
1174 Call->replaceAllUsesWith(PHI);
1175 Call->eraseFromParent();
1176
1177 if (DTU)
1178 DTU->applyUpdates(Updates);
1179
1180 return true;
1181}
1182
1185 DominatorTree &DT, const DataLayout &DL,
1186 bool &MadeCFGChange) {
1187
1188 auto *CI = dyn_cast<CallInst>(&I);
1189 if (!CI || CI->isNoBuiltin())
1190 return false;
1191
1192 Function *CalledFunc = CI->getCalledFunction();
1193 if (!CalledFunc)
1194 return false;
1195
1196 LibFunc LF;
1197 if (!TLI.getLibFunc(*CalledFunc, LF) ||
1198 !isLibFuncEmittable(CI->getModule(), &TLI, LF))
1199 return false;
1200
1201 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);
1202
1203 switch (LF) {
1204 case LibFunc_sqrt:
1205 case LibFunc_sqrtf:
1206 case LibFunc_sqrtl:
1207 return foldSqrt(CI, LF, TTI, TLI, AC, DT);
1208 case LibFunc_strcmp:
1209 case LibFunc_strncmp:
1210 if (StrNCmpInliner(CI, LF, &DTU, DL).optimizeStrNCmp()) {
1211 MadeCFGChange = true;
1212 return true;
1213 }
1214 break;
1215 case LibFunc_memchr:
1216 if (foldMemChr(CI, &DTU, DL)) {
1217 MadeCFGChange = true;
1218 return true;
1219 }
1220 break;
1221 default:;
1222 }
1223 return false;
1224}
1225
1226/// This is the entry point for folds that could be implemented in regular
1227/// InstCombine, but they are separated because they are not expected to
1228/// occur frequently and/or have more than a constant-length pattern match.
1232 AssumptionCache &AC, bool &MadeCFGChange) {
1233 bool MadeChange = false;
1234 for (BasicBlock &BB : F) {
1235 // Ignore unreachable basic blocks.
1236 if (!DT.isReachableFromEntry(&BB))
1237 continue;
1238
1239 const DataLayout &DL = F.getDataLayout();
1240
1241 // Walk the block backwards for efficiency. We're matching a chain of
1242 // use->defs, so we're more likely to succeed by starting from the bottom.
1243 // Also, we want to avoid matching partial patterns.
1244 // TODO: It would be more efficient if we removed dead instructions
1245 // iteratively in this loop rather than waiting until the end.
1247 MadeChange |= foldAnyOrAllBitsSet(I);
1248 MadeChange |= foldGuardedFunnelShift(I, DT);
1249 MadeChange |= tryToRecognizePopCount(I);
1250 MadeChange |= tryToFPToSat(I, TTI);
1251 MadeChange |= tryToRecognizeTableBasedCttz(I);
1252 MadeChange |= foldConsecutiveLoads(I, DL, TTI, AA, DT);
1253 MadeChange |= foldPatternedLoads(I, DL);
1254 // NOTE: This function introduces erasing of the instruction `I`, so it
1255 // needs to be called at the end of this sequence, otherwise we may make
1256 // bugs.
1257 MadeChange |= foldLibCalls(I, TTI, TLI, AC, DT, DL, MadeCFGChange);
1258 }
1259 }
1260
1261 // We're done with transforms, so remove dead instructions.
1262 if (MadeChange)
1263 for (BasicBlock &BB : F)
1265
1266 return MadeChange;
1267}
1268
1269/// This is the entry point for all transforms. Pass manager differences are
1270/// handled in the callers of this function.
1273 AliasAnalysis &AA, bool &MadeCFGChange) {
1274 bool MadeChange = false;
1275 const DataLayout &DL = F.getDataLayout();
1276 TruncInstCombine TIC(AC, TLI, DL, DT);
1277 MadeChange |= TIC.run(F);
1278 MadeChange |= foldUnusualPatterns(F, DT, TTI, TLI, AA, AC, MadeCFGChange);
1279 return MadeChange;
1280}
1281
1284 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1285 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1286 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1287 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1288 auto &AA = AM.getResult<AAManager>(F);
1289 bool MadeCFGChange = false;
1290 if (!runImpl(F, AC, TTI, TLI, DT, AA, MadeCFGChange)) {
1291 // No changes, all analyses are preserved.
1292 return PreservedAnalyses::all();
1293 }
1294 // Mark all the analyses that instcombine updates as preserved.
1296 if (MadeCFGChange)
1298 else
1300 return PA;
1301}
amdgpu AMDGPU Register Bank Select
Rewrite undef for PHI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool tryToRecognizePopCount(Instruction &I)
static bool foldSqrt(CallInst *Call, LibFunc Func, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT)
Try to replace a mathlib call to sqrt with the LLVM intrinsic.
static bool foldAnyOrAllBitsSet(Instruction &I)
Match patterns that correspond to "any-bits-set" and "all-bits-set".
static cl::opt< unsigned > MemChrInlineThreshold("memchr-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string to " "inline a memchr call."))
static bool tryToFPToSat(Instruction &I, TargetTransformInfo &TTI)
Fold smin(smax(fptosi(x), C1), C2) to llvm.fptosi.sat(x), providing C1 and C2 saturate the value of t...
static cl::opt< unsigned > StrNCmpInlineThreshold("strncmp-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string for a builtin string cmp " "call eligible for inlining. The default value is 3."))
static bool matchAndOrChain(Value *V, MaskOps &MOps)
This is a recursive helper for foldAnyOrAllBitsSet() that walks through a chain of 'and' or 'or' inst...
static bool foldMemChr(CallInst *Call, DomTreeUpdater *DTU, const DataLayout &DL)
Convert memchr with a small constant string into a switch.
static bool foldConsecutiveLoads(Instruction &I, const DataLayout &DL, TargetTransformInfo &TTI, AliasAnalysis &AA, const DominatorTree &DT)
static bool runImpl(Function &F, AssumptionCache &AC, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, DominatorTree &DT, AliasAnalysis &AA, bool &MadeCFGChange)
This is the entry point for all transforms.
static bool tryToRecognizeTableBasedCttz(Instruction &I)
static bool foldGuardedFunnelShift(Instruction &I, const DominatorTree &DT)
Match a pattern for a bitwise funnel/rotate operation that partially guards against undefined behavio...
static cl::opt< unsigned > MaxInstrsToScan("aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden, cl::desc("Max number of instructions to scan for aggressive instcombine."))
static bool foldLoadsRecursive(Value *V, LoadOps &LOps, const DataLayout &DL, AliasAnalysis &AA)
static std::pair< APInt, APInt > getStrideAndModOffsetOfGEP(Value *PtrOp, const DataLayout &DL)
static bool isCTTZTable(const ConstantDataArray &Table, uint64_t Mul, uint64_t Shift, uint64_t InputBits)
static bool foldPatternedLoads(Instruction &I, const DataLayout &DL)
If C is a constant patterned array and all valid loaded results for given alignment are same to a con...
static bool foldLibCalls(Instruction &I, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, const DataLayout &DL, bool &MadeCFGChange)
static bool foldUnusualPatterns(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AliasAnalysis &AA, AssumptionCache &AC, bool &MadeCFGChange)
This is the entry point for folds that could be implemented in regular InstCombine,...
AggressiveInstCombiner - Combine expression patterns to form expressions with fewer,...
This is the interface for LLVM's primary stateless and local alias analysis.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
bool End
Definition: ELF_riscv.cpp:480
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool runImpl(Function &F, const TargetLowering &TLI)
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
static MaybeAlign getAlign(Value *Ptr)
Definition: IRBuilder.cpp:531
static Instruction * matchFunnelShift(Instruction &Or, InstCombinerImpl &IC)
Match UB-safe variants of the funnel shift intrinsic.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const MCExpr * MaskShift(const MCExpr *Val, uint32_t Mask, uint32_t Shift, MCContext &Ctx)
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:166
This pass exposes codegen information to IR-level passes.
Value * LHS
BinaryOperator * Mul
A manager for alias analyses.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Class for arbitrary precision integers.
Definition: APInt.h:77
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1497
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
Definition: APInt.h:1307
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1445
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:306
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
Definition: APInt.cpp:620
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
Definition: APInt.cpp:1706
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1107
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:263
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:216
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1198
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:448
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:416
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:212
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:219
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:239
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:72
This class represents a function call, abstracting a target machine's calling convention.
@ ICMP_EQ
equal
Definition: InstrTypes.h:778
An array constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
Definition: Constants.h:693
uint64_t getElementAsInteger(unsigned i) const
If this is a sequential container of integers (of any size), return the specified element in the low ...
Definition: Constants.cpp:3074
unsigned getNumElements() const
Return the number of elements in the array or vector.
Definition: Constants.cpp:2817
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
This is an important base class in LLVM.
Definition: Constant.h:42
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:915
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
bool hasInitializer() const
Definitions have initializers, declarations don't.
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)
Definition: IRBuilder.h:1824
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2053
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2555
Value * CreatePtrAdd(Value *Ptr, Value *Offset, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
Definition: IRBuilder.h:1996
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition: IRBuilder.h:308
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:483
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2417
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Definition: IRBuilder.h:1160
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2261
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1433
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition: IRBuilder.h:2041
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1492
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg != 0.
Definition: IRBuilder.h:2569
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Definition: IRBuilder.h:2027
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Definition: IRBuilder.h:1131
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:177
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=std::nullopt, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2432
Value * CreateInBoundsPtrAdd(Value *Ptr, Value *Offset, const Twine &Name="")
Definition: IRBuilder.h:2001
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
Definition: IRBuilder.h:513
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2686
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1727
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:92
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
Definition: Metadata.cpp:1713
Class to represent integer types.
Definition: DerivedTypes.h:40
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:266
An instruction for reading from memory.
Definition: Instructions.h:174
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:259
Value * getPointerOperand()
Definition: Instructions.h:253
bool isSimple() const
Definition: Instructions.h:245
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
Representation for a specific memory location.
MemoryLocation getWithNewSize(LocationSize NewSize) const
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:146
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:131
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:367
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:502
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
static constexpr size_t npos
Definition: StringRef.h:52
Multiway switch.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
InstructionCost getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA, TTI::TargetCostKind CostKind) const
InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src, TTI::CastContextHint CCH, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
@ TCK_RecipThroughput
Reciprocal throughput.
bool isTypeLegal(Type *Ty) const
Return true if this type is legal.
bool allowsMisalignedMemoryAccesses(LLVMContext &Context, unsigned BitWidth, unsigned AddressSpace=0, Align Alignment=Align(1), unsigned *Fast=nullptr) const
Determine if the target supports unaligned memory accesses.
bool haveFastSqrt(Type *Ty) const
Return true if the hardware has a fast square-root instruction.
@ None
The cast is not used with a load/store of any kind.
bool run(Function &F)
Perform TruncInst pattern optimization on given function.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:230
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:128
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:224
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1075
uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, bool &CanBeFreed) const
Returns the number of bytes known to be dereferenceable for the pointer value.
Definition: Value.cpp:852
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:383
const ParentTy * getParent() const
Definition: ilist_node.h:32
#define UINT64_MAX
Definition: DataTypes.h:77
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
Definition: APInt.cpp:767
@ Fast
Attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:41
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1539
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:972
match_combine_or< CastInst_match< OpTy, ZExtInst >, OpTy > m_ZExtOrSelf(const OpTy &Op)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:816
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:875
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:168
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:592
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
Definition: PatternMatch.h:893
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:599
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
specific_bbval m_SpecificBB(BasicBlock *BB)
Match a specific basic block value.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
SpecificCmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_SpecificICmp(ICmpInst::Predicate MatchPred, const LHS &L, const RHS &R)
CastInst_match< OpTy, FPToSIInst > m_FPToSI(const OpTy &Op)
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:299
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:92
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
NodeAddr< PhiNode * > Phi
Definition: RDFGraph.h:390
NodeAddr< FuncNode * > Func
Definition: RDFGraph.h:393
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Length
Definition: DWP.cpp:480
bool isOnlyUsedInZeroComparison(const Instruction *CxtI)
bool getConstantStringInfo(const Value *V, StringRef &Str, bool TrimAtNul=true)
This function computes the length of a null-terminated C string pointed to by V.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:656
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:731
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:296
bool isLibFuncEmittable(const Module *M, const TargetLibraryInfo *TLI, LibFunc TheLibFunc)
Check whether the library function is available on target and also that it in the current Module is a...
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:340
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:291
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)
Extract value of C at the given Offset reinterpreted as Ty.
@ And
Bitwise or logical AND of integers.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
bool cannotBeOrderedLessThanZero(const Value *V, unsigned Depth, const SimplifyQuery &SQ)
Return true if we can prove that the specified FP value is either NaN or never less than -0....
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N
This is used by foldLoadsRecursive() to capture a Root Load node which is of type or(load,...
const APInt * Shift
LoadInst * RootInsert
This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and the bit indexes (Mask) nee...
MaskOps(unsigned BitWidth, bool MatchAnds)
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:760
AAMDNodes concat(const AAMDNodes &Other) const
Determine the best AAMDNodes after concatenating two different locations together.