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
15#include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
16#include "AggressiveInstCombineInternal.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/Analysis/AliasAnalysis.h"
19#include "llvm/Analysis/AssumptionCache.h"
20#include "llvm/Analysis/BasicAliasAnalysis.h"
21#include "llvm/Analysis/ConstantFolding.h"
22#include "llvm/Analysis/DomTreeUpdater.h"
23#include "llvm/Analysis/GlobalsModRef.h"
24#include "llvm/Analysis/TargetLibraryInfo.h"
25#include "llvm/Analysis/TargetTransformInfo.h"
26#include "llvm/Analysis/ValueTracking.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"
31#include "llvm/IR/Instruction.h"
32#include "llvm/IR/IntrinsicInst.h"
33#include "llvm/IR/MDBuilder.h"
34#include "llvm/IR/PatternMatch.h"
35#include "llvm/IR/ProfDataUtils.h"
36#include "llvm/ProfileData/InstrProf.h"
37#include "llvm/Support/Casting.h"
38#include "llvm/Support/CommandLine.h"
39#include "llvm/Transforms/Utils/BasicBlockUtils.h"
40#include "llvm/Transforms/Utils/BuildLibCalls.h"
41#include "llvm/Transforms/Utils/Local.h"
42
43using namespace llvm;
44using namespace PatternMatch;
45
46#define DEBUG_TYPE "aggressive-instcombine"
47
48STATISTIC(NumAnyOrAllBitsSet, "Number of any/all-bits-set patterns folded");
49STATISTIC(NumGuardedRotates,
50 "Number of guarded rotates transformed into funnel shifts");
51STATISTIC(NumGuardedFunnelShifts,
52 "Number of guarded funnel shifts transformed into funnel shifts");
53STATISTIC(NumPopCountRecognized, "Number of popcount idioms recognized");
54STATISTIC(NumSelectCTTZFolded,
55 "Number of select-based split cttz patterns folded");
56STATISTIC(NumSelectCTLZFolded,
57 "Number of select-based split ctlz patterns folded");
58STATISTIC(NumMemSetsGuarded, "Number of memsets guarded for a zero length");
59STATISTIC(NumTableBasedLowBitsMask,
60 "Number of low-bits mask table loads folded to (1 << i) - 1");
61
62static cl::opt<unsigned> MaxInstrsToScan(
63 "aggressive-instcombine-max-scan-instrs", cl::init(Val: 64), cl::Hidden,
64 cl::desc("Max number of instructions to scan for aggressive instcombine."));
65
66static cl::opt<unsigned> StrNCmpInlineThreshold(
67 "strncmp-inline-threshold", cl::init(Val: 3), cl::Hidden,
68 cl::desc("The maximum length of a constant string for a builtin string cmp "
69 "call eligible for inlining. The default value is 3."));
70
71static cl::opt<unsigned>
72 MemChrInlineThreshold("memchr-inline-threshold", cl::init(Val: 3), cl::Hidden,
73 cl::desc("The maximum length of a constant string to "
74 "inline a memchr call."));
75
76namespace llvm {
77extern cl::opt<bool> ProfcheckDisableMetadataFixes;
78} // namespace llvm
79
80/// Try to fold a select-based split cttz pattern into a single full-width cttz.
81///
82/// %lo = trunc iN %val to i(N/2)
83/// %cmp = icmp eq i(N/2) %lo, 0
84/// %shr = lshr iN %val, N/2
85/// %hi = trunc iN %shr to i(N/2)
86/// %cttz_hi = call i(N/2) @llvm.cttz.i(N/2)(i(N/2) %hi, ...)
87/// %hi_plus = add/or_disjoint i(N/2) %cttz_hi, N/2
88/// %cttz_lo = call i(N/2) @llvm.cttz.i(N/2)(i(N/2) %lo, ...)
89/// %result = select i1 %cmp, i(N/2) %hi_plus, i(N/2) %cttz_lo
90/// -->
91/// %cttz_wide = call iN @llvm.cttz.iN(iN %val, i1 false)
92/// %result = trunc iN %cttz_wide to i(N/2)
93/// Alive proof (for i64/i32): https://alive2.llvm.org/ce/z/-s14-s
94// TrueVal/FalseVal are pre-normalized by the caller to the EQ/NE cases.
95static bool foldSelectSplitCTTZ(Instruction &I, Value *LoTrunc, Value *HiResult,
96 Value *LoResult, Type *HalfTy) {
97 unsigned HalfWidth = HalfTy->getIntegerBitWidth();
98 unsigned FullWidth = HalfWidth * 2;
99
100 // LoTrunc: trunc iN SrcVal to i(N/2)
101 Value *SrcVal;
102 if (!match(V: LoTrunc, P: m_Trunc(Op: m_Value(V&: SrcVal))))
103 return false;
104 if (!SrcVal->getType()->isIntegerTy(BitWidth: FullWidth))
105 return false;
106
107 // LoResult: cttz(trunc(SrcVal), _), must use same truncated value
108 if (!match(V: LoResult, P: m_OneUse(SubPattern: m_Cttz(Op0: m_Specific(V: LoTrunc), Op1: m_Value()))))
109 return false;
110
111 // HiResult: add/or_disjoint(cttz(trunc(lshr(SrcVal, N/2)), _), N/2)
112 Value *CttzHiCall;
113 if (!match(V: HiResult, P: m_OneUse(SubPattern: m_AddLike(L: m_Value(V&: CttzHiCall),
114 R: m_SpecificInt(V: HalfWidth)))))
115 return false;
116
117 Value *HiCttzArg;
118 if (!match(V: CttzHiCall, P: m_OneUse(SubPattern: m_Cttz(Op0: m_Value(V&: HiCttzArg), Op1: m_Value()))))
119 return false;
120
121 if (!match(V: HiCttzArg,
122 P: m_Trunc(Op: m_LShr(L: m_Specific(V: SrcVal), R: m_SpecificInt(V: HalfWidth)))))
123 return false;
124
125 // Match successful.
126 IRBuilder<> Builder(&I);
127 Value *CttzWide = Builder.CreateIntrinsic(
128 ID: Intrinsic::cttz, OverloadTypes: {SrcVal->getType()}, Args: {SrcVal, Builder.getFalse()});
129 Value *Trunc = Builder.CreateTrunc(V: CttzWide, DestTy: HalfTy);
130
131 I.replaceAllUsesWith(V: Trunc);
132 ++NumSelectCTTZFolded;
133 return true;
134}
135
136/// Same as foldSelectSplitCTTZ but for leading zeros (ctlz).
137///
138/// %shr = lshr iN %val, N/2
139/// %hi = trunc iN %shr to i(N/2)
140/// %cmp = icmp eq i(N/2) %hi, 0 (or icmp eq iN %shr, 0)
141/// %lo = trunc iN %val to i(N/2)
142/// %ctlz_lo = call i(N/2) @llvm.ctlz.i(N/2)(i(N/2) %lo, ...)
143/// %lo_plus = add/or_disjoint i(N/2) %ctlz_lo, N/2
144/// %ctlz_hi = call i(N/2) @llvm.ctlz.i(N/2)(i(N/2) %hi, ...)
145/// %result = select i1 %cmp, i(N/2) %lo_plus, i(N/2) %ctlz_hi
146/// -->
147/// %ctlz_wide = call iN @llvm.ctlz.iN(iN %val, i1 false)
148/// %result = trunc iN %ctlz_wide to i(N/2)
149///
150/// Alive proof (for i64/i32): https://alive2.llvm.org/ce/z/WfQepH
151// TrueVal/FalseVal are pre-normalized by the caller to the EQ/NE cases.
152static bool foldSelectSplitCTLZ(Instruction &I, Value *HiPart, Value *LoResult,
153 Value *HiResult, Type *HalfTy) {
154 unsigned HalfWidth = HalfTy->getIntegerBitWidth();
155 unsigned FullWidth = HalfWidth * 2;
156
157 // Extract SrcVal from HiPart: either trunc(lshr(SrcVal, N/2)) or
158 // lshr(SrcVal, N/2)
159 Value *SrcVal;
160 if (match(V: HiPart, P: m_Trunc(Op: m_Value(V&: SrcVal))))
161 HiPart = SrcVal;
162
163 if (!match(V: HiPart, P: m_LShr(L: m_Value(V&: SrcVal), R: m_SpecificInt(V: HalfWidth))))
164 return false;
165 if (!SrcVal->getType()->isIntegerTy(BitWidth: FullWidth))
166 return false;
167
168 // HiResult: ctlz(trunc(lshr(SrcVal, N/2)), _)
169 Value *HiCtlzArg;
170 if (!match(V: HiResult, P: m_OneUse(SubPattern: m_Ctlz(Op0: m_Value(V&: HiCtlzArg), Op1: m_Value()))))
171 return false;
172
173 if (!match(V: HiCtlzArg,
174 P: m_Trunc(Op: m_LShr(L: m_Specific(V: SrcVal), R: m_SpecificInt(V: HalfWidth)))))
175 return false;
176
177 // LoResult: add/or_disjoint(ctlz(trunc(SrcVal), _), N/2)
178 Value *CtlzLoCall;
179 if (!match(V: LoResult, P: m_OneUse(SubPattern: m_AddLike(L: m_Value(V&: CtlzLoCall),
180 R: m_SpecificInt(V: HalfWidth)))))
181 return false;
182
183 Value *LoCtlzArg;
184 if (!match(V: CtlzLoCall, P: m_OneUse(SubPattern: m_Ctlz(Op0: m_Value(V&: LoCtlzArg), Op1: m_Value()))))
185 return false;
186
187 if (!match(V: LoCtlzArg, P: m_Trunc(Op: m_Specific(V: SrcVal))))
188 return false;
189
190 // Match successful.
191 IRBuilder<> Builder(&I);
192 Value *CtlzWide = Builder.CreateIntrinsic(
193 ID: Intrinsic::ctlz, OverloadTypes: {SrcVal->getType()}, Args: {SrcVal, Builder.getFalse()});
194 Value *Trunc = Builder.CreateTrunc(V: CtlzWide, DestTy: HalfTy);
195
196 I.replaceAllUsesWith(V: Trunc);
197 ++NumSelectCTLZFolded;
198 return true;
199}
200
201/// Common entry point for folding select-based split cttz/ctlz patterns.
202/// Performs the initial select and type matching shared by both transforms,
203/// then delegates to foldSelectSplitCTTZ and foldSelectSplitCTLZ.
204static bool foldSelectSplitCTLZCTTZ(Instruction &I) {
205 Value *Cond, *TrueVal, *FalseVal;
206 if (!match(V: &I, P: m_Select(C: m_Value(V&: Cond), L: m_Value(V&: TrueVal), R: m_Value(V&: FalseVal))))
207 return false;
208
209 Type *Ty = I.getType();
210 if (!Ty->isIntegerTy())
211 return false;
212
213 // Bail out on very small types (i1, i2): the full-width cttz/ctlz can return
214 // values not representable in the half type (e.g., cttz.i4 can return 4,
215 // which doesn't fit in i2).
216 if (Ty->getIntegerBitWidth() <= 2)
217 return false;
218
219 CmpPredicate Pred;
220 Value *CmpOp;
221 if (!match(V: Cond, P: m_ICmp(Pred, L: m_Value(V&: CmpOp), R: m_ZeroInt())) ||
222 !ICmpInst::isEquality(P: Pred))
223 return false;
224
225 // Canonicalize select operands.
226 if (Pred == CmpInst::ICMP_NE)
227 std::swap(a&: TrueVal, b&: FalseVal);
228
229 return foldSelectSplitCTTZ(I, LoTrunc: CmpOp, HiResult: TrueVal, LoResult: FalseVal, HalfTy: Ty) ||
230 foldSelectSplitCTLZ(I, HiPart: CmpOp, LoResult: TrueVal, HiResult: FalseVal, HalfTy: Ty);
231}
232
233/// Match a pattern for a bitwise funnel/rotate operation that partially guards
234/// against undefined behavior by branching around the funnel-shift/rotation
235/// when the shift amount is 0.
236static bool foldGuardedFunnelShift(Instruction &I, const DominatorTree &DT) {
237 if (I.getOpcode() != Instruction::PHI || I.getNumOperands() != 2)
238 return false;
239
240 // As with the one-use checks below, this is not strictly necessary, but we
241 // are being cautious to avoid potential perf regressions on targets that
242 // do not actually have a funnel/rotate instruction (where the funnel shift
243 // would be expanded back into math/shift/logic ops).
244 if (!isPowerOf2_32(Value: I.getType()->getScalarSizeInBits()))
245 return false;
246
247 // Match V to funnel shift left/right and capture the source operands and
248 // shift amount.
249 auto matchFunnelShift = [](Value *V, Value *&ShVal0, Value *&ShVal1,
250 Value *&ShAmt) {
251 unsigned Width = V->getType()->getScalarSizeInBits();
252
253 // fshl(ShVal0, ShVal1, ShAmt)
254 // == (ShVal0 << ShAmt) | (ShVal1 >> (Width -ShAmt))
255 if (match(V, P: m_OneUse(SubPattern: m_c_Or(
256 L: m_Shl(L: m_Value(V&: ShVal0), R: m_Value(V&: ShAmt)),
257 R: m_LShr(L: m_Value(V&: ShVal1), R: m_Sub(L: m_SpecificInt(V: Width),
258 R: m_Deferred(V: ShAmt))))))) {
259 return Intrinsic::fshl;
260 }
261
262 // fshr(ShVal0, ShVal1, ShAmt)
263 // == (ShVal0 >> ShAmt) | (ShVal1 << (Width - ShAmt))
264 if (match(V,
265 P: m_OneUse(SubPattern: m_c_Or(L: m_Shl(L: m_Value(V&: ShVal0), R: m_Sub(L: m_SpecificInt(V: Width),
266 R: m_Value(V&: ShAmt))),
267 R: m_LShr(L: m_Value(V&: ShVal1), R: m_Deferred(V: ShAmt)))))) {
268 return Intrinsic::fshr;
269 }
270
271 return Intrinsic::not_intrinsic;
272 };
273
274 // One phi operand must be a funnel/rotate operation, and the other phi
275 // operand must be the source value of that funnel/rotate operation:
276 // phi [ rotate(RotSrc, ShAmt), FunnelBB ], [ RotSrc, GuardBB ]
277 // phi [ fshl(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal0, GuardBB ]
278 // phi [ fshr(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal1, GuardBB ]
279 PHINode &Phi = cast<PHINode>(Val&: I);
280 unsigned FunnelOp = 0, GuardOp = 1;
281 Value *P0 = Phi.getOperand(i_nocapture: 0), *P1 = Phi.getOperand(i_nocapture: 1);
282 Value *ShVal0, *ShVal1, *ShAmt;
283 Intrinsic::ID IID = matchFunnelShift(P0, ShVal0, ShVal1, ShAmt);
284 if (IID == Intrinsic::not_intrinsic ||
285 (IID == Intrinsic::fshl && ShVal0 != P1) ||
286 (IID == Intrinsic::fshr && ShVal1 != P1)) {
287 IID = matchFunnelShift(P1, ShVal0, ShVal1, ShAmt);
288 if (IID == Intrinsic::not_intrinsic ||
289 (IID == Intrinsic::fshl && ShVal0 != P0) ||
290 (IID == Intrinsic::fshr && ShVal1 != P0))
291 return false;
292 assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
293 "Pattern must match funnel shift left or right");
294 std::swap(a&: FunnelOp, b&: GuardOp);
295 }
296
297 // The incoming block with our source operand must be the "guard" block.
298 // That must contain a cmp+branch to avoid the funnel/rotate when the shift
299 // amount is equal to 0. The other incoming block is the block with the
300 // funnel/rotate.
301 BasicBlock *GuardBB = Phi.getIncomingBlock(i: GuardOp);
302 BasicBlock *FunnelBB = Phi.getIncomingBlock(i: FunnelOp);
303 Instruction *TermI = GuardBB->getTerminator();
304
305 // Ensure that the shift values dominate each block.
306 if (!DT.dominates(Def: ShVal0, User: TermI) || !DT.dominates(Def: ShVal1, User: TermI))
307 return false;
308
309 BasicBlock *PhiBB = Phi.getParent();
310 if (!match(V: TermI, P: m_Br(C: m_SpecificICmp(MatchPred: CmpInst::ICMP_EQ, L: m_Specific(V: ShAmt),
311 R: m_ZeroInt()),
312 T: m_SpecificBB(BB: PhiBB), F: m_SpecificBB(BB: FunnelBB))))
313 return false;
314
315 IRBuilder<> Builder(PhiBB->getFirstInsertionPt());
316
317 if (ShVal0 == ShVal1)
318 ++NumGuardedRotates;
319 else
320 ++NumGuardedFunnelShifts;
321
322 // If this is not a rotate then the select was blocking poison from the
323 // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
324 bool IsFshl = IID == Intrinsic::fshl;
325 if (ShVal0 != ShVal1) {
326 if (IsFshl && !llvm::isGuaranteedNotToBePoison(V: ShVal1))
327 ShVal1 = Builder.CreateFreeze(V: ShVal1);
328 else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(V: ShVal0))
329 ShVal0 = Builder.CreateFreeze(V: ShVal0);
330 }
331
332 // We matched a variation of this IR pattern:
333 // GuardBB:
334 // %cmp = icmp eq i32 %ShAmt, 0
335 // br i1 %cmp, label %PhiBB, label %FunnelBB
336 // FunnelBB:
337 // %sub = sub i32 32, %ShAmt
338 // %shr = lshr i32 %ShVal1, %sub
339 // %shl = shl i32 %ShVal0, %ShAmt
340 // %fsh = or i32 %shr, %shl
341 // br label %PhiBB
342 // PhiBB:
343 // %cond = phi i32 [ %fsh, %FunnelBB ], [ %ShVal0, %GuardBB ]
344 // -->
345 // llvm.fshl.i32(i32 %ShVal0, i32 %ShVal1, i32 %ShAmt)
346 Phi.replaceAllUsesWith(
347 V: Builder.CreateIntrinsic(ID: IID, OverloadTypes: Phi.getType(), Args: {ShVal0, ShVal1, ShAmt}));
348 return true;
349}
350
351/// This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and
352/// the bit indexes (Mask) needed by a masked compare. If we're matching a chain
353/// of 'and' ops, then we also need to capture the fact that we saw an
354/// "and X, 1", so that's an extra return value for that case.
355namespace {
356struct MaskOps {
357 Value *Root = nullptr;
358 APInt Mask;
359 bool MatchAndChain;
360 bool FoundAnd1 = false;
361
362 MaskOps(unsigned BitWidth, bool MatchAnds)
363 : Mask(APInt::getZero(numBits: BitWidth)), MatchAndChain(MatchAnds) {}
364};
365} // namespace
366
367/// This is a recursive helper for foldAnyOrAllBitsSet() that walks through a
368/// chain of 'and' or 'or' instructions looking for shift ops of a common source
369/// value. Examples:
370/// or (or (or X, (X >> 3)), (X >> 5)), (X >> 8)
371/// returns { X, 0x129 }
372/// and (and (X >> 1), 1), (X >> 4)
373/// returns { X, 0x12 }
374static bool matchAndOrChain(Value *V, MaskOps &MOps) {
375 Value *Op0, *Op1;
376 if (MOps.MatchAndChain) {
377 // Recurse through a chain of 'and' operands. This requires an extra check
378 // vs. the 'or' matcher: we must find an "and X, 1" instruction somewhere
379 // in the chain to know that all of the high bits are cleared.
380 if (match(V, P: m_And(L: m_Value(V&: Op0), R: m_One()))) {
381 MOps.FoundAnd1 = true;
382 return matchAndOrChain(V: Op0, MOps);
383 }
384 if (match(V, P: m_And(L: m_Value(V&: Op0), R: m_Value(V&: Op1))))
385 return matchAndOrChain(V: Op0, MOps) && matchAndOrChain(V: Op1, MOps);
386 } else {
387 // Recurse through a chain of 'or' operands.
388 if (match(V, P: m_Or(L: m_Value(V&: Op0), R: m_Value(V&: Op1))))
389 return matchAndOrChain(V: Op0, MOps) && matchAndOrChain(V: Op1, MOps);
390 }
391
392 // We need a shift-right or a bare value representing a compare of bit 0 of
393 // the original source operand.
394 Value *Candidate;
395 const APInt *BitIndex = nullptr;
396 if (!match(V, P: m_LShr(L: m_Value(V&: Candidate), R: m_APInt(Res&: BitIndex))))
397 Candidate = V;
398
399 // Initialize result source operand.
400 if (!MOps.Root)
401 MOps.Root = Candidate;
402
403 // The shift constant is out-of-range? This code hasn't been simplified.
404 if (BitIndex && BitIndex->uge(RHS: MOps.Mask.getBitWidth()))
405 return false;
406
407 // Fill in the mask bit derived from the shift constant.
408 MOps.Mask.setBit(BitIndex ? BitIndex->getZExtValue() : 0);
409 return MOps.Root == Candidate;
410}
411
412/// Match patterns that correspond to "any-bits-set" and "all-bits-set".
413/// These will include a chain of 'or' or 'and'-shifted bits from a
414/// common source value:
415/// and (or (lshr X, C), ...), 1 --> (X & CMask) != 0
416/// and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask
417/// Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns
418/// that differ only with a final 'not' of the result. We expect that final
419/// 'not' to be folded with the compare that we create here (invert predicate).
420static bool foldAnyOrAllBitsSet(Instruction &I) {
421 // The 'any-bits-set' ('or' chain) pattern is simpler to match because the
422 // final "and X, 1" instruction must be the final op in the sequence.
423 bool MatchAllBitsSet;
424 bool MatchTrunc;
425 Value *X;
426 if (I.getType()->isIntOrIntVectorTy(BitWidth: 1)) {
427 if (match(V: &I, P: m_Trunc(Op: m_OneUse(SubPattern: m_And(L: m_Value(), R: m_Value())))))
428 MatchAllBitsSet = true;
429 else if (match(V: &I, P: m_Trunc(Op: m_OneUse(SubPattern: m_Or(L: m_Value(), R: m_Value())))))
430 MatchAllBitsSet = false;
431 else
432 return false;
433 MatchTrunc = true;
434 X = I.getOperand(i: 0);
435 } else {
436 if (match(V: &I, P: m_c_And(L: m_OneUse(SubPattern: m_And(L: m_Value(), R: m_Value())), R: m_Value()))) {
437 X = &I;
438 MatchAllBitsSet = true;
439 } else if (match(V: &I,
440 P: m_And(L: m_OneUse(SubPattern: m_Or(L: m_Value(), R: m_Value())), R: m_One()))) {
441 X = I.getOperand(i: 0);
442 MatchAllBitsSet = false;
443 } else
444 return false;
445 MatchTrunc = false;
446 }
447 Type *Ty = X->getType();
448
449 MaskOps MOps(Ty->getScalarSizeInBits(), MatchAllBitsSet);
450 if (!matchAndOrChain(V: X, MOps) ||
451 (MatchAllBitsSet && !MatchTrunc && !MOps.FoundAnd1))
452 return false;
453
454 // The pattern was found. Create a masked compare that replaces all of the
455 // shift and logic ops.
456 IRBuilder<> Builder(&I);
457 Constant *Mask = ConstantInt::get(Ty, V: MOps.Mask);
458 Value *And = Builder.CreateAnd(LHS: MOps.Root, RHS: Mask);
459 Value *Cmp = MatchAllBitsSet ? Builder.CreateICmpEQ(LHS: And, RHS: Mask)
460 : Builder.CreateIsNotNull(Arg: And);
461 Value *Zext = MatchTrunc ? Cmp : Builder.CreateZExt(V: Cmp, DestTy: Ty);
462 I.replaceAllUsesWith(V: Zext);
463 ++NumAnyOrAllBitsSet;
464 return true;
465}
466
467/// Helper function to replace an instruction with a popcount intrinsic.
468/// This creates the ctpop intrinsic with an optional zero-extension or
469/// truncation appended at the end, and replaces all uses of the instruction.
470static void replaceWithPopCount(Instruction &I, Value *Root) {
471 LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");
472 IRBuilder<> Builder(&I);
473 Value *NewVal =
474 Builder.CreateIntrinsic(ID: Intrinsic::ctpop, OverloadTypes: Root->getType(), Args: {Root});
475 I.replaceAllUsesWith(V: Builder.CreateZExtOrTrunc(V: NewVal, DestTy: I.getType()));
476 ++NumPopCountRecognized;
477}
478
479// Matches the common innermost steps of the Hacker's Delight popcount idiom:
480// V = ((x + (x >> 4)) & 0x0F...)
481// x = (y & 0x33...) + ((y >> 2) & 0x33...) [or y - 3*((y>>2)&0x33...)]
482// y = Root - ((Root >> 1) & 0x55...)
483// This computes the popcount for each byte.
484// Returns Root on success, nullptr on failure.
485static Value *matchPopCountBytes(Value *V, unsigned Len, const DataLayout &DL) {
486 APInt Mask55 = APInt::getSplat(NewLen: Len, V: APInt(8, 0x55));
487 APInt Mask33 = APInt::getSplat(NewLen: Len, V: APInt(8, 0x33));
488 APInt Mask0F = APInt::getSplat(NewLen: Len, V: APInt(8, 0x0F));
489
490 Value *Add2;
491 // Matching "((x + (x >> 4)) & 0x0F...)".
492 if (!match(V, P: m_And(L: m_c_Add(L: m_LShr(L: m_Value(V&: Add2), R: m_SpecificInt(V: 4)),
493 R: m_Deferred(V: Add2)),
494 R: m_SpecificInt(V: Mask0F))))
495 return nullptr;
496
497 Value *Sub1;
498 APInt NegThree(Len, -3, /*isSigned=*/true);
499 // Match
500 // x = (x & 0x33333333) + ((x >> 2) & 0x33333333)"
501 // Or
502 // x = x - 3*((x >> 2) & 0x33333333)
503 if (!match(V: Add2, P: m_c_Add(L: m_And(L: m_LShr(L: m_Value(V&: Sub1), R: m_SpecificInt(V: 2)),
504 R: m_SpecificInt(V: Mask33)),
505 R: m_And(L: m_Deferred(V: Sub1), R: m_SpecificInt(V: Mask33)))) &&
506 !match(V: Add2, P: m_Add(L: m_Mul(L: m_And(L: m_LShr(L: m_Value(V&: Sub1), R: m_SpecificInt(V: 2)),
507 R: m_SpecificInt(V: Mask33)),
508 R: m_SpecificInt(V: NegThree)),
509 R: m_Deferred(V: Sub1))))
510 return nullptr;
511
512 Value *Root, *LShr;
513 const APInt *AndMask;
514 // Matching "x - ((x >> 1) & 0x55...)".
515 if (!match(V: Sub1,
516 P: m_Sub(L: m_Value(V&: Root), R: m_And(L: m_Value(V&: LShr, P: m_LShr(L: m_Deferred(V: Root),
517 R: m_SpecificInt(V: 1))),
518 R: m_APInt(Res&: AndMask)))))
519 return nullptr;
520
521 if (*AndMask != Mask55) {
522 // Accept a narrowed mask if missing bits are known zero in Root>>1.
523 if (!AndMask->isSubsetOf(RHS: Mask55))
524 return nullptr;
525 APInt NeededMask = Mask55 & ~*AndMask;
526 if (!MaskedValueIsZero(V: LShr, Mask: NeededMask, SQ: SimplifyQuery(DL)))
527 return nullptr;
528 }
529
530 return Root;
531}
532
533// Try to recognize below function as popcount intrinsic.
534// This is the "best" algorithm from
535// http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
536// Also used in TargetLowering::expandCTPOP().
537//
538// int popcount(unsigned int i) {
539// i = i - ((i >> 1) & 0x55555555);
540// i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
541// i = ((i + (i >> 4)) & 0x0F0F0F0F);
542// return (i * 0x01010101) >> 24;
543// }
544static bool tryToRecognizePopCount(Instruction &I) {
545 if (I.getOpcode() != Instruction::LShr)
546 return false;
547
548 Type *Ty = I.getType();
549 if (!Ty->isIntOrIntVectorTy())
550 return false;
551
552 unsigned Len = Ty->getScalarSizeInBits();
553 // Len==8 is handled by tryToRecognizePopCount2n3.
554 // FIXME: other irregular type lengths.
555 if (Len > 128 || Len <= 8 || Len % 8 != 0)
556 return false;
557
558 APInt Mask01 = APInt::getSplat(NewLen: Len, V: APInt(8, 0x01));
559
560 Value *Op0 = I.getOperand(i: 0);
561 Value *Op1 = I.getOperand(i: 1);
562 Value *MulOp0;
563 // Matching "(i * 0x01010101...) >> 24".
564 if (!match(V: Op0, P: m_Mul(L: m_Value(V&: MulOp0), R: m_SpecificInt(V: Mask01))) ||
565 !match(V: Op1, P: m_SpecificInt(V: Len - 8)))
566 return false;
567
568 Value *Root = matchPopCountBytes(V: MulOp0, Len, DL: I.getDataLayout());
569 if (!Root)
570 return false;
571
572 replaceWithPopCount(I, Root);
573 return true;
574}
575
576// Try to recognize below function as popcount intrinsic.
577// Ref. Hacker Delights
578// int popcount32(unsigned int i) {
579// uWord = (uWord & 0x55555555) + ((uWord>>1) & 0x55555555);
580// uWord = (uWord & 0x33333333) + ((uWord>>2) & 0x33333333);
581// uWord = (uWord & 0x0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F);
582// uWord = (uWord & 0x00FF00FF) + ((uWord>>8) & 0x00FF00FF);
583// return (uWord & 0x0000FFFF) + (uWord>>16);
584// }
585// int popcount64(unsigned long i) {
586// uWord = (uWord & 0x5555555555555555) + ((uWord>>1) & 0x5555555555555555);
587// uWord = (uWord & 0x3333333333333333) + ((uWord>>2) & 0x3333333333333333);
588// uWord = (uWord & 0x0F0F0F0F0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F0F0F0F0F);
589// uWord = (uWord & 0x00FF00FF00FF00FF) + ((uWord>>8) & 0x00FF00FF00FF00FF);
590// uWord = (uWord & 0x0000FFFF0000FFFF) + ((uWord>>16) & 0x0000FFFF0000FFFF);
591// return (uWord & 0x00000000FFFFFFFF) + (uWord>>32) & 0x00000000FFFFFFFF;
592// }
593//
594// InstCombine may narrow AND masks when it can prove the removed bits are
595// known zero (e.g. 0x0F0F0F0F -> 0x07070707). We accept such narrowed masks
596// by checking they are subsets of the expected masks and verifying the missing
597// bits are known zero via MaskedValueIsZero.
598static bool tryToRecognizePopCount1(Instruction &I) {
599 if (I.getOpcode() != Instruction::Add)
600 return false;
601
602 Type *Ty = I.getType();
603 if (!Ty->isIntOrIntVectorTy())
604 return false;
605
606 unsigned Len = Ty->getScalarSizeInBits();
607 if (Len > 64 || Len <= 8 || Len % 8 != 0)
608 return false;
609
610 // Len should be a power of 2 for the loop to work correctly
611 if (!isPowerOf2_32(Value: Len))
612 return false;
613
614 APInt Mask55 = APInt::getSplat(NewLen: Len, V: APInt(8, 0x55));
615 APInt Mask33 = APInt::getSplat(NewLen: Len, V: APInt(8, 0x33));
616
617 SimplifyQuery SQ(I.getDataLayout());
618
619 // Check if CapturedMask is a valid (possibly narrowed) version of
620 // ExpectedMask for the given Operand. Returns true if the masks match
621 // exactly, or if CapturedMask is a subset and the missing bits are
622 // known zero in the Operand.
623 auto isValidNarrowedMask = [&](const APInt &CapturedMask,
624 const APInt &ExpectedMask,
625 Value *Operand) -> bool {
626 if (CapturedMask == ExpectedMask)
627 return true;
628 if (!CapturedMask.isSubsetOf(RHS: ExpectedMask))
629 return false;
630 APInt NeededMask = ExpectedMask & ~CapturedMask;
631 return MaskedValueIsZero(V: Operand, Mask: NeededMask, SQ);
632 };
633
634 // For "(x & M) + ((x >> S) & M)" patterns, both AND masks may be narrowed.
635 // Require subsets of BaseMask and prove any implied missing bits are zero.
636 auto narrowAddPairMasksOk = [&](const APInt &BaseMask, unsigned ShiftAmt,
637 Value *Val, const APInt &AndMask1,
638 const APInt &AndMask2) -> bool {
639 if (!AndMask1.isSubsetOf(RHS: BaseMask) || !AndMask2.isSubsetOf(RHS: BaseMask))
640 return false;
641 APInt NeededShifted = (BaseMask & ~AndMask1).shl(shiftAmt: ShiftAmt);
642 APInt NeededUnshifted = BaseMask & ~AndMask2;
643 APInt AllNeeded = NeededShifted | NeededUnshifted;
644 return AllNeeded.isZero() || MaskedValueIsZero(V: Val, Mask: AllNeeded, SQ);
645 };
646
647 Value *ShiftOp;
648 Value *Start = &I;
649 for (unsigned I = Len; I >= 8; I = I / 2) {
650 APInt Mask = APInt::getSplat(NewLen: Len, V: APInt::getLowBitsSet(numBits: I, loBitsSet: I / 2));
651 const APInt *AndMask1 = nullptr, *AndMask2 = nullptr;
652
653 // Matching "(uWord & Mask) + ((uWord>>I/2) & Mask)".
654 // Both masks might have been narrowed by InstCombine.
655 if (match(V: Start,
656 P: m_c_Add(L: m_And(L: m_LShr(L: m_Value(V&: ShiftOp), R: m_SpecificInt(V: I / 2)),
657 R: m_APInt(Res&: AndMask1)),
658 R: m_And(L: m_Deferred(V: ShiftOp), R: m_APInt(Res&: AndMask2))))) {
659 if (!narrowAddPairMasksOk(Mask, I / 2, ShiftOp, *AndMask1, *AndMask2))
660 return false;
661 }
662 // Matching "(uWord & Mask) + (uWord>>I/2)".
663 // The mask might have been narrowed by InstCombine.
664 else if (match(V: Start,
665 P: m_c_Add(L: m_LShr(L: m_Value(V&: ShiftOp), R: m_SpecificInt(V: I / 2)),
666 R: m_And(L: m_Deferred(V: ShiftOp), R: m_APInt(Res&: AndMask1))))) {
667 if (!isValidNarrowedMask(*AndMask1, Mask, ShiftOp))
668 return false;
669 } else
670 return false;
671 Start = ShiftOp;
672 }
673
674 // Matching "uWord = (uWord & Mask33) + ((uWord>>2) & Mask33)".
675 const APInt *AndMask1 = nullptr, *AndMask2 = nullptr;
676 if (!match(V: Start, P: m_c_Add(L: m_And(L: m_LShr(L: m_Value(V&: ShiftOp), R: m_SpecificInt(V: 2)),
677 R: m_APInt(Res&: AndMask1)),
678 R: m_And(L: m_Deferred(V: ShiftOp), R: m_APInt(Res&: AndMask2)))))
679 return false;
680 if (!narrowAddPairMasksOk(Mask33, 2, ShiftOp, *AndMask1, *AndMask2))
681 return false;
682
683 Start = ShiftOp;
684 Value *Root;
685 // Matching "uWord = (uWord & Mask55) + ((uWord>>1) & Mask55)".
686 AndMask1 = nullptr;
687 AndMask2 = nullptr;
688 if (!match(V: Start, P: m_c_Add(L: m_And(L: m_LShr(L: m_Value(V&: Root), R: m_SpecificInt(V: 1)),
689 R: m_APInt(Res&: AndMask1)),
690 R: m_And(L: m_Deferred(V: Root), R: m_APInt(Res&: AndMask2)))))
691 return false;
692 if (!narrowAddPairMasksOk(Mask55, 1, Root, *AndMask1, *AndMask2))
693 return false;
694
695 replaceWithPopCount(I, Root);
696 return true;
697}
698
699// Try to recognize below function as popcount intrinsic.
700// Ref. Hackers Delight
701// int popcnt(unsigned x) {
702// x = x - ((x >> 1) & 0x55555555);
703// x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
704// x = (x + (x >> 4)) & 0x0F0F0F0F;
705// x = x + (x >> 8);
706// x = x + (x >> 16);
707// return x & 0x0000003F;
708// }
709
710// int popcnt(unsigned x) {
711// x = x - ((x >> 1) & 0x55555555);
712// x = x - 3*((x >> 2) & 0x33333333);
713// x = (x + (x >> 4)) & 0x0F0F0F0F;
714// x = x + (x >> 8);
715// x = x + (x >> 16);
716// return x & 0x0000003F;
717// }
718static bool tryToRecognizePopCount2n3(Instruction &I) {
719 if (I.getOpcode() != Instruction::And)
720 return false;
721
722 Type *Ty = I.getType();
723 if (!Ty->isIntOrIntVectorTy())
724 return false;
725
726 unsigned Len = Ty->getScalarSizeInBits();
727 Value *Add1;
728 if (Len == 8) {
729 // Special case for Len == 8, we only need to match the And at the end of
730 // matchPopCountBytes.
731 Add1 = &I;
732 } else {
733 const APInt *MaskRes;
734 if (!match(V: &I, P: m_And(L: m_Value(V&: Add1), R: m_APInt(Res&: MaskRes))))
735 return false;
736
737 // Since `(trunc (and x, C))` might be canonicalized into `(and (trunc x),
738 // C)` we might loose the opportunity to recognize `(trunc (popcount y))`.
739 // The following block tries to capture such truncation, update `Len`, and
740 // append the truncation at the end of the emitting popcount, if there is
741 // any.
742 Value *TruncSrc;
743 if (match(V: Add1, P: m_OneUse(SubPattern: m_Trunc(Op: m_Value(V&: TruncSrc))))) {
744 Add1 = TruncSrc;
745 Len = Add1->getType()->getScalarSizeInBits();
746 }
747
748 if (Len > 64 || Len <= 8 || Len % 8 != 0)
749 return false;
750
751 // Len should be a power of 2 for the loop to work correctly
752 if (!isPowerOf2_32(Value: Len))
753 return false;
754
755 // Number of bits needed to represent Len.
756 unsigned NumLenBits = Log2_32(Value: Len) + 1;
757 // The "mask" here really only needs to fulfill two conditions:
758 // (1) All ones for the lower NumLenBits-bits
759 // (2) Zeros from bit 8 and onward.
760 // Condition (1) is straightforward. The reason behind condition
761 // (2) is that we don't care any 8-bit chunks but the first one
762 // in the original divide-and-conquer algorithm.
763 if (MaskRes->countTrailingOnes() < NumLenBits ||
764 MaskRes->getActiveBits() > 8)
765 return false;
766
767 for (unsigned I = Len; I >= 16; I = I / 2) {
768 Value *Add2;
769 // Matching "x = x + (x >> I/2)" for I-bit.
770 if (!match(V: Add1, P: m_c_Add(L: m_LShr(L: m_Value(V&: Add2), R: m_SpecificInt(V: I / 2)),
771 R: m_Deferred(V: Add2))))
772 return false;
773 Add1 = Add2;
774 }
775 }
776
777 Value *Root = matchPopCountBytes(V: Add1, Len, DL: I.getDataLayout());
778 if (!Root)
779 return false;
780
781 replaceWithPopCount(I, Root);
782 return true;
783}
784
785/// Fold smin(smax(fptosi(x), C1), C2) to llvm.fptosi.sat(x), providing C1 and
786/// C2 saturate the value of the fp conversion. The transform is not reversable
787/// as the fptosi.sat is more defined than the input - all values produce a
788/// valid value for the fptosi.sat, where as some produce poison for original
789/// that were out of range of the integer conversion. The reversed pattern may
790/// use fmax and fmin instead. As we cannot directly reverse the transform, and
791/// it is not always profitable, we make it conditional on the cost being
792/// reported as lower by TTI.
793static bool tryToFPToSat(Instruction &I, TargetTransformInfo &TTI) {
794 // Look for min(max(fptosi, converting to fptosi_sat.
795 Value *In;
796 const APInt *MinC, *MaxC;
797 if (!match(V: &I, P: m_SMax(Op0: m_OneUse(SubPattern: m_SMin(Op0: m_OneUse(SubPattern: m_FPToSI(Op: m_Value(V&: In))),
798 Op1: m_APInt(Res&: MinC))),
799 Op1: m_APInt(Res&: MaxC))) &&
800 !match(V: &I, P: m_SMin(Op0: m_OneUse(SubPattern: m_SMax(Op0: m_OneUse(SubPattern: m_FPToSI(Op: m_Value(V&: In))),
801 Op1: m_APInt(Res&: MaxC))),
802 Op1: m_APInt(Res&: MinC))))
803 return false;
804
805 // Check that the constants clamp a saturate.
806 if (!(*MinC + 1).isPowerOf2() || -*MaxC != *MinC + 1)
807 return false;
808
809 Type *IntTy = I.getType();
810 Type *FpTy = In->getType();
811 Type *SatTy =
812 IntegerType::get(C&: IntTy->getContext(), NumBits: (*MinC + 1).exactLogBase2() + 1);
813 if (auto *VecTy = dyn_cast<VectorType>(Val: IntTy))
814 SatTy = VectorType::get(ElementType: SatTy, EC: VecTy->getElementCount());
815
816 // Get the cost of the intrinsic, and check that against the cost of
817 // fptosi+smin+smax
818 InstructionCost SatCost = TTI.getIntrinsicInstrCost(
819 ICA: IntrinsicCostAttributes(Intrinsic::fptosi_sat, SatTy, {In}, {FpTy}),
820 CostKind: TTI::TCK_RecipThroughput);
821 SatCost += TTI.getCastInstrCost(Opcode: Instruction::SExt, Dst: IntTy, Src: SatTy,
822 CCH: TTI::CastContextHint::None,
823 CostKind: TTI::TCK_RecipThroughput);
824
825 InstructionCost MinMaxCost = TTI.getCastInstrCost(
826 Opcode: Instruction::FPToSI, Dst: IntTy, Src: FpTy, CCH: TTI::CastContextHint::None,
827 CostKind: TTI::TCK_RecipThroughput);
828 MinMaxCost += TTI.getIntrinsicInstrCost(
829 ICA: IntrinsicCostAttributes(Intrinsic::smin, IntTy, {IntTy}),
830 CostKind: TTI::TCK_RecipThroughput);
831 MinMaxCost += TTI.getIntrinsicInstrCost(
832 ICA: IntrinsicCostAttributes(Intrinsic::smax, IntTy, {IntTy}),
833 CostKind: TTI::TCK_RecipThroughput);
834
835 if (SatCost >= MinMaxCost)
836 return false;
837
838 IRBuilder<> Builder(&I);
839 Value *Sat =
840 Builder.CreateIntrinsic(ID: Intrinsic::fptosi_sat, OverloadTypes: {SatTy, FpTy}, Args: In);
841 I.replaceAllUsesWith(V: Builder.CreateSExt(V: Sat, DestTy: IntTy));
842 return true;
843}
844
845/// Try to replace a mathlib call to sqrt with the LLVM intrinsic. This avoids
846/// pessimistic codegen that has to account for setting errno and can enable
847/// vectorization.
848static bool foldSqrt(CallInst *Call, LibFunc Func, TargetTransformInfo &TTI,
849 TargetLibraryInfo &TLI, AssumptionCache &AC,
850 DominatorTree &DT) {
851 // If (1) this is a sqrt libcall, (2) we can assume that NAN is not created
852 // (because NNAN or the operand arg must not be less than -0.0) and (2) we
853 // would not end up lowering to a libcall anyway (which could change the value
854 // of errno), then:
855 // (1) errno won't be set.
856 // (2) it is safe to convert this to an intrinsic call.
857 Type *Ty = Call->getType();
858 Value *Arg = Call->getArgOperand(i: 0);
859 if (TTI.haveFastSqrt(Ty) &&
860 (Call->hasNoNaNs() ||
861 cannotBeOrderedLessThanZero(
862 V: Arg, SQ: SimplifyQuery(Call->getDataLayout(), &TLI, &DT, &AC, Call)))) {
863 IRBuilder<> Builder(Call);
864 Value *NewSqrt =
865 Builder.CreateIntrinsic(ID: Intrinsic::sqrt, OverloadTypes: Ty, Args: Arg, FMFSource: Call, Name: "sqrt");
866 Call->replaceAllUsesWith(V: NewSqrt);
867
868 // Explicitly erase the old call because a call with side effects is not
869 // trivially dead.
870 Call->eraseFromParent();
871 return true;
872 }
873
874 return false;
875}
876
877// Check if this array of constants represents a cttz table.
878// Iterate over the elements from \p Table by trying to find/match all
879// the numbers from 0 to \p InputBits that should represent cttz results.
880static bool isCTTZTable(Constant *Table, const APInt &Mul, const APInt &Shift,
881 const APInt &AndMask, Type *AccessTy,
882 unsigned InputBits, const APInt &GEPIdxFactor,
883 const DataLayout &DL) {
884 for (unsigned Idx = 0; Idx < InputBits; Idx++) {
885 APInt Index =
886 (APInt::getOneBitSet(numBits: InputBits, BitNo: Idx) * Mul).lshr(ShiftAmt: Shift) & AndMask;
887 ConstantInt *C = dyn_cast_or_null<ConstantInt>(
888 Val: ConstantFoldLoadFromConst(C: Table, Ty: AccessTy, Offset: Index * GEPIdxFactor, DL));
889 if (!C || C->getValue() != Idx)
890 return false;
891 }
892
893 return true;
894}
895
896// Try to recognize table-based ctz implementation.
897// E.g., an example in C (for more cases please see the llvm/tests):
898// int f(unsigned x) {
899// static const char table[32] =
900// {0, 1, 28, 2, 29, 14, 24, 3, 30,
901// 22, 20, 15, 25, 17, 4, 8, 31, 27,
902// 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
903// return table[((unsigned)((x & -x) * 0x077CB531U)) >> 27];
904// }
905// this can be lowered to `cttz` instruction.
906// There is also a special case when the element is 0.
907//
908// The (x & -x) sets the lowest non-zero bit to 1. The multiply is a de-bruijn
909// sequence that contains each pattern of bits in it. The shift extracts
910// the top bits after the multiply, and that index into the table should
911// represent the number of trailing zeros in the original number.
912//
913// Here are some examples or LLVM IR for a 64-bit target:
914//
915// CASE 1:
916// %sub = sub i32 0, %x
917// %and = and i32 %sub, %x
918// %mul = mul i32 %and, 125613361
919// %shr = lshr i32 %mul, 27
920// %idxprom = zext i32 %shr to i64
921// %arrayidx = getelementptr inbounds [32 x i8], [32 x i8]* @ctz1.table, i64 0,
922// i64 %idxprom
923// %0 = load i8, i8* %arrayidx, align 1, !tbaa !8
924//
925// CASE 2:
926// %sub = sub i32 0, %x
927// %and = and i32 %sub, %x
928// %mul = mul i32 %and, 72416175
929// %shr = lshr i32 %mul, 26
930// %idxprom = zext i32 %shr to i64
931// %arrayidx = getelementptr inbounds [64 x i16], [64 x i16]* @ctz2.table,
932// i64 0, i64 %idxprom
933// %0 = load i16, i16* %arrayidx, align 2, !tbaa !8
934//
935// CASE 3:
936// %sub = sub i32 0, %x
937// %and = and i32 %sub, %x
938// %mul = mul i32 %and, 81224991
939// %shr = lshr i32 %mul, 27
940// %idxprom = zext i32 %shr to i64
941// %arrayidx = getelementptr inbounds [32 x i32], [32 x i32]* @ctz3.table,
942// i64 0, i64 %idxprom
943// %0 = load i32, i32* %arrayidx, align 4, !tbaa !8
944//
945// CASE 4:
946// %sub = sub i64 0, %x
947// %and = and i64 %sub, %x
948// %mul = mul i64 %and, 283881067100198605
949// %shr = lshr i64 %mul, 58
950// %arrayidx = getelementptr inbounds [64 x i8], [64 x i8]* @table, i64 0,
951// i64 %shr
952// %0 = load i8, i8* %arrayidx, align 1, !tbaa !8
953//
954// All these can be lowered to @llvm.cttz.i32/64 intrinsics.
955//
956// This shares its initial match (load from a GEP into a constant table with
957// a single variable index) with tryToRecognizeTableBasedLog2() below; see
958// tryToRecognizeTableBasedPatterns().
959static bool tryToRecognizeTableBasedCttz(LoadInst *LI, Type *AccessType,
960 GlobalVariable *GVTable, Value *GepIdx,
961 const APInt &GEPScale,
962 const DataLayout &DL) {
963 Value *X1;
964 const APInt *MulConst, *ShiftConst, *AndCst = nullptr;
965 // Check that the gep variable index is ((x & -x) * MulConst) >> ShiftConst.
966 // This might be extended to the pointer index type, and if the gep index type
967 // has been replaced with an i8 then a new And (and different ShiftConst) will
968 // be present.
969 auto MatchInner = m_LShr(
970 L: m_Mul(L: m_c_And(L: m_Neg(V: m_Value(V&: X1)), R: m_Deferred(V: X1)), R: m_APInt(Res&: MulConst)),
971 R: m_APInt(Res&: ShiftConst));
972 if (!match(V: GepIdx, P: m_CastOrSelf(Op: MatchInner)) &&
973 !match(V: GepIdx, P: m_CastOrSelf(Op: m_And(L: MatchInner, R: m_APInt(Res&: AndCst)))))
974 return false;
975
976 unsigned InputBits = X1->getType()->getScalarSizeInBits();
977 if (InputBits != 16 && InputBits != 32 && InputBits != 64 && InputBits != 128)
978 return false;
979
980 if (!GEPScale.isIntN(N: InputBits) ||
981 !isCTTZTable(Table: GVTable->getInitializer(), Mul: *MulConst, Shift: *ShiftConst,
982 AndMask: AndCst ? *AndCst : APInt::getAllOnes(numBits: InputBits), AccessTy: AccessType,
983 InputBits, GEPIdxFactor: GEPScale.zextOrTrunc(width: InputBits), DL))
984 return false;
985
986 ConstantInt *ZeroTableElem = cast<ConstantInt>(
987 Val: ConstantFoldLoadFromConst(C: GVTable->getInitializer(), Ty: AccessType, DL));
988 bool DefinedForZero = ZeroTableElem->equalsInt(V: InputBits);
989
990 IRBuilder<> B(LI);
991 ConstantInt *BoolConst = B.getInt1(V: !DefinedForZero);
992 Type *XType = X1->getType();
993 auto Cttz = B.CreateIntrinsic(ID: Intrinsic::cttz, OverloadTypes: {XType}, Args: {X1, BoolConst});
994 Value *Res = B.CreateZExtOrTrunc(V: Cttz, DestTy: AccessType);
995
996 if (!DefinedForZero) {
997 // If the value in elem 0 isn't the same as InputBits, we still want to
998 // produce the value from the table. Emit the select in AccessType with elem
999 // 0 unchanged, as the table's element type may be wider than the input
1000 // type (and directly truncating ZeroTableElem into the input type could
1001 // incorrectly drop bits).
1002 auto Cmp = B.CreateICmpEQ(LHS: X1, RHS: ConstantInt::get(Ty: XType, V: 0));
1003 Res = B.CreateSelect(C: Cmp, True: ZeroTableElem, False: Res);
1004
1005 // The true branch of select handles the cttz(0) case, which is rare.
1006 if (Instruction *SelectI = dyn_cast<Instruction>(Val: Res))
1007 SelectI->setMetadata(
1008 KindID: LLVMContext::MD_prof,
1009 Node: MDBuilder(SelectI->getContext()).createUnlikelyBranchWeights());
1010
1011 // NOTE: If the table[0] is 0, but the cttz(0) is defined by the Target
1012 // it should be handled as: `cttz(x) & (typeSize - 1)`.
1013 }
1014
1015 LI->replaceAllUsesWith(V: Res);
1016
1017 return true;
1018}
1019
1020// Recognise ctpop table lookups:
1021//
1022// %gep = getelementptr [256 x i8], ptr @ctpop.table, i32 0, i8 %x
1023// %ctpop = load i8, ptr %gep
1024// ->
1025// %ctpop = call i8 llvm.ctpop(i8 %x)
1026static bool tryToRecognizeTableBasedCtpop(LoadInst *LI, Type *AccessType,
1027 GlobalVariable *GVTable,
1028 Value *GepIdx, const APInt &GEPScale,
1029 const DataLayout &DL,
1030 const TargetTransformInfo &TTI) {
1031 Type *IdxTy = GepIdx->getType();
1032 unsigned IdxBits = IdxTy->getIntegerBitWidth();
1033 if (!LI->isSimple() || !isPowerOf2_32(Value: IdxBits) ||
1034 TTI.getPopcntSupport(IntTyWidthInBit: IdxBits) != TargetTransformInfo::PSK_FastHardware)
1035 return false;
1036
1037 uint64_t TableSize = DL.getTypeAllocSize(Ty: GVTable->getValueType());
1038 unsigned AccessSize = DL.getTypeStoreSize(Ty: AccessType);
1039 if (GEPScale != AccessSize)
1040 return false;
1041 uint64_t NumEntries = TableSize / AccessSize;
1042 for (uint64_t I = 0; I < NumEntries; I++) {
1043 auto *C = dyn_cast_or_null<ConstantInt>(Val: ConstantFoldLoadFromConst(
1044 C: GVTable->getInitializer(), Ty: AccessType, Offset: I * GEPScale, DL));
1045 if (!C || C->getValue() != popcount(Value: I))
1046 return false;
1047 }
1048
1049 replaceWithPopCount(I&: *LI, Root: GepIdx);
1050 return true;
1051}
1052
1053// Check if this array of constants represents a log2 table.
1054// Iterate over the elements from \p Table by trying to find/match all
1055// the numbers from 0 to \p InputBits that should represent log2 results.
1056static bool isLog2Table(Constant *Table, const APInt &Mul, const APInt &Shift,
1057 Type *AccessTy, unsigned InputBits,
1058 const APInt &GEPIdxFactor, const DataLayout &DL) {
1059 for (unsigned Idx = 0; Idx < InputBits; Idx++) {
1060 APInt Index = (APInt::getLowBitsSet(numBits: InputBits, loBitsSet: Idx + 1) * Mul).lshr(ShiftAmt: Shift);
1061 ConstantInt *C = dyn_cast_or_null<ConstantInt>(
1062 Val: ConstantFoldLoadFromConst(C: Table, Ty: AccessTy, Offset: Index * GEPIdxFactor, DL));
1063 if (!C || C->getValue() != Idx)
1064 return false;
1065 }
1066
1067 // Verify that an input of zero will select table index 0.
1068 APInt ZeroIndex = Mul.lshr(ShiftAmt: Shift);
1069 if (!ZeroIndex.isZero())
1070 return false;
1071
1072 return true;
1073}
1074
1075// Try to recognize table-based log2 implementation.
1076// E.g., an example in C (for more cases please the llvm/tests):
1077// int f(unsigned v) {
1078// static const char table[32] =
1079// {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
1080// 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31};
1081//
1082// v |= v >> 1; // first round down to one less than a power of 2
1083// v |= v >> 2;
1084// v |= v >> 4;
1085// v |= v >> 8;
1086// v |= v >> 16;
1087//
1088// return table[(unsigned)(v * 0x07C4ACDDU) >> 27];
1089// }
1090// this can be lowered to `ctlz` instruction.
1091// There is also a special case when the element is 0.
1092//
1093// The >> and |= sequence sets all bits below the most significant set bit. The
1094// multiply is a de-bruijn sequence that contains each pattern of bits in it.
1095// The shift extracts the top bits after the multiply, and that index into the
1096// table should represent the floor log base 2 of the original number.
1097//
1098// Here are some examples of LLVM IR for a 64-bit target.
1099//
1100// CASE 1:
1101// %shr = lshr i32 %v, 1
1102// %or = or i32 %shr, %v
1103// %shr1 = lshr i32 %or, 2
1104// %or2 = or i32 %shr1, %or
1105// %shr3 = lshr i32 %or2, 4
1106// %or4 = or i32 %shr3, %or2
1107// %shr5 = lshr i32 %or4, 8
1108// %or6 = or i32 %shr5, %or4
1109// %shr7 = lshr i32 %or6, 16
1110// %or8 = or i32 %shr7, %or6
1111// %mul = mul i32 %or8, 130329821
1112// %shr9 = lshr i32 %mul, 27
1113// %idxprom = zext nneg i32 %shr9 to i64
1114// %arrayidx = getelementptr inbounds i8, ptr @table, i64 %idxprom
1115// %0 = load i8, ptr %arrayidx, align 1
1116//
1117// CASE 2:
1118// %shr = lshr i64 %v, 1
1119// %or = or i64 %shr, %v
1120// %shr1 = lshr i64 %or, 2
1121// %or2 = or i64 %shr1, %or
1122// %shr3 = lshr i64 %or2, 4
1123// %or4 = or i64 %shr3, %or2
1124// %shr5 = lshr i64 %or4, 8
1125// %or6 = or i64 %shr5, %or4
1126// %shr7 = lshr i64 %or6, 16
1127// %or8 = or i64 %shr7, %or6
1128// %shr9 = lshr i64 %or8, 32
1129// %or10 = or i64 %shr9, %or8
1130// %mul = mul i64 %or10, 285870213051386505
1131// %shr11 = lshr i64 %mul, 58
1132// %arrayidx = getelementptr inbounds i8, ptr @table, i64 %shr11
1133// %0 = load i8, ptr %arrayidx, align 1
1134//
1135// CASE 3:
1136// A variant where the most-significant set bit of the OR-cascade result is
1137// isolated via subtraction before the multiply, i.e.
1138// table[((v - (v >> 1)) * MulConst) >> ShiftConst], analogous to how the
1139// cttz pattern isolates the least-significant set bit via `x & -x`:
1140//
1141// %shr = lshr i64 %v, 1
1142// %or = or i64 %shr, %v
1143// ... (rest of the OR-cascade, as above) ...
1144// %shr11 = lshr i64 %or10, 1
1145// %sub = sub i64 %or10, %shr11
1146// %mul = mul i64 %sub, 571347909858961602
1147// %shr12 = lshr i64 %mul, 58
1148// %arrayidx = getelementptr inbounds i8, ptr @table, i64 %shr12
1149// %0 = load i8, ptr %arrayidx, align 1
1150//
1151// All these can be lowered to @llvm.ctlz.i32/64 intrinsics and a subtract.
1152//
1153// This shares its initial match (load from a GEP into a constant table with
1154// a single variable index) with tryToRecognizeTableBasedCttz() above; see
1155// tryToRecognizeTableBasedPatterns().
1156static bool tryToRecognizeTableBasedLog2(LoadInst *LI, Type *AccessType,
1157 GlobalVariable *GVTable, Value *GepIdx,
1158 const APInt &GEPScale,
1159 const DataLayout &DL,
1160 TargetTransformInfo &TTI) {
1161 Value *X;
1162 const APInt *MulConst, *ShiftConst;
1163 // Check that the gep variable index is (x * MulConst) >> ShiftConst.
1164 auto MatchInner =
1165 m_LShr(L: m_Mul(L: m_Value(V&: X), R: m_APInt(Res&: MulConst)), R: m_APInt(Res&: ShiftConst));
1166 if (!match(V: GepIdx, P: m_CastOrSelf(Op: MatchInner)))
1167 return false;
1168
1169 // The multiplied value may instead be the OR-cascade result with its
1170 // most-significant set bit isolated first via `v - (v >> 1)`: since every
1171 // bit below the MSB of an OR-cascade result is 1, this subtraction leaves
1172 // just the MSB, mirroring how tryToRecognizeTableBasedCttz() isolates the
1173 // least-significant set bit via `x & -x`.
1174 bool IsolatedMSB = false;
1175 Value *V;
1176 if (match(V: X, P: m_Sub(L: m_Value(V), R: m_LShr(L: m_Deferred(V), R: m_SpecificInt(V: 1))))) {
1177 IsolatedMSB = true;
1178 X = V;
1179 }
1180
1181 unsigned InputBits = X->getType()->getScalarSizeInBits();
1182 if (InputBits != 16 && InputBits != 32 && InputBits != 64 && InputBits != 128)
1183 return false;
1184
1185 // Verify shift amount.
1186 // TODO: Allow other shift amounts when we have proper test coverage.
1187 if (*ShiftConst != InputBits - Log2_32(Value: InputBits))
1188 return false;
1189
1190 // Match the sequence of OR operations with right shifts by powers of 2.
1191 for (unsigned ShiftAmt = InputBits / 2; ShiftAmt != 0; ShiftAmt /= 2) {
1192 Value *Y;
1193 if (!match(V: X, P: m_c_Or(L: m_LShr(L: m_Value(V&: Y), R: m_SpecificInt(V: ShiftAmt)),
1194 R: m_Deferred(V: Y))))
1195 return false;
1196 X = Y;
1197 }
1198
1199 if (!GEPScale.isIntN(N: InputBits))
1200 return false;
1201
1202 if (IsolatedMSB) {
1203 // With the MSB isolated, the multiplicand for an input whose MSB is at bit
1204 // Idx is a single set bit rather than a run of low bits, which is exactly
1205 // what isCTTZTable() checks for (there is no additional masking here, so
1206 // pass an all-ones mask).
1207 if (!isCTTZTable(Table: GVTable->getInitializer(), Mul: *MulConst, Shift: *ShiftConst,
1208 AndMask: APInt::getAllOnes(numBits: InputBits), AccessTy: AccessType, InputBits,
1209 GEPIdxFactor: GEPScale.zextOrTrunc(width: InputBits), DL))
1210 return false;
1211 } else {
1212 if (!isLog2Table(Table: GVTable->getInitializer(), Mul: *MulConst, Shift: *ShiftConst,
1213 AccessTy: AccessType, InputBits, GEPIdxFactor: GEPScale.zextOrTrunc(width: InputBits),
1214 DL))
1215 return false;
1216 }
1217
1218 ConstantInt *ZeroTableElem = cast<ConstantInt>(
1219 Val: ConstantFoldLoadFromConst(C: GVTable->getInitializer(), Ty: AccessType, DL));
1220
1221 // Use InputBits - 1 - ctlz(X) to compute log2(X).
1222 IRBuilder<> B(LI);
1223 ConstantInt *BoolConst = B.getTrue();
1224 Type *XType = X->getType();
1225
1226 // Check the the backend has an efficient ctlz instruction.
1227 // FIXME: Teach the backend to emit the original code when ctlz isn't
1228 // supported like we do for cttz.
1229 IntrinsicCostAttributes Attrs(
1230 Intrinsic::ctlz, XType,
1231 {PoisonValue::get(T: XType), /*is_zero_poison=*/BoolConst});
1232 InstructionCost Cost =
1233 TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: TargetTransformInfo::TCK_SizeAndLatency);
1234 if (Cost > TargetTransformInfo::TCC_Basic)
1235 return false;
1236
1237 Constant *InputBitsM1 = ConstantInt::get(Ty: XType, V: InputBits - 1);
1238
1239 Value *Result;
1240 if (ZeroTableElem->getZExtValue() == InputBits - 1) {
1241 Value *Ctlz =
1242 B.CreateIntrinsic(ID: Intrinsic::ctlz, OverloadTypes: {XType}, Args: {X, B.getFalse()});
1243 Result = B.CreateAnd(LHS: B.CreateNot(V: Ctlz), RHS: InputBitsM1);
1244 } else {
1245 Value *Ctlz = B.CreateIntrinsic(ID: Intrinsic::ctlz, OverloadTypes: {XType}, Args: {X, BoolConst});
1246 Value *Sub = B.CreateSub(LHS: InputBitsM1, RHS: Ctlz);
1247
1248 // The table won't produce a sensible result for 0.
1249 Value *Cmp = B.CreateICmpEQ(LHS: X, RHS: ConstantInt::get(Ty: XType, V: 0));
1250 Value *Select =
1251 B.CreateSelect(C: Cmp, True: B.CreateZExt(V: ZeroTableElem, DestTy: XType), False: Sub);
1252
1253 // The true branch of select handles the log2(0) case, which is rare.
1254 if (Instruction *SelectI = dyn_cast<Instruction>(Val: Select))
1255 SelectI->setMetadata(
1256 KindID: LLVMContext::MD_prof,
1257 Node: MDBuilder(SelectI->getContext()).createUnlikelyBranchWeights());
1258
1259 Result = Select;
1260 }
1261
1262 Value *ZExtOrTrunc = B.CreateZExtOrTrunc(V: Result, DestTy: AccessType);
1263
1264 LI->replaceAllUsesWith(V: ZExtOrTrunc);
1265
1266 return true;
1267}
1268
1269// Recognize a load from a "low bits mask" table, tbl[j] == (1 << j) - 1:
1270//
1271// static const uintN_t tbl[K] = { 0, 1, 3, 7, ... };
1272// ... x & tbl[i] ...
1273//
1274// The loaded value equals the arithmetic mask (1 << i) - 1, so replace the load
1275// with that expression and drop the table. On X86+BMI2 a surrounding `and` then
1276// selects to a single `bzhi`; on other targets it is a shift and a decrement.
1277//
1278// Shares the load/GEP/offset match with the cttz and log2 recognizers above;
1279// see tryToRecognizeTableBasedPatterns().
1280static bool tryToRecognizeTableBasedLowBitsMask(LoadInst *LI, Type *AccessType,
1281 GlobalVariable *GVTable,
1282 Value *GepIdx,
1283 const APInt &GEPScale,
1284 const DataLayout &DL) {
1285 // The value must be exactly the table element; refuse volatile/atomic loads.
1286 if (!LI->isSimple())
1287 return false;
1288
1289 // The table must be [K x AccessType] of integers; a narrower load would read
1290 // only part of an element.
1291 auto *ArrTy = dyn_cast<ArrayType>(Val: GVTable->getValueType());
1292 if (!ArrTy || ArrTy->getElementType() != AccessType ||
1293 !AccessType->isIntegerTy())
1294 return false;
1295
1296 unsigned EltBits = AccessType->getIntegerBitWidth();
1297 uint64_t EltBytes = DL.getTypeAllocSize(Ty: AccessType).getFixedValue();
1298 uint64_t K = ArrTy->getNumElements();
1299
1300 // Only fire when the element type fits in a legal integer, so the emitted
1301 // shift is a cheap (possibly promoted) instruction rather than a runtime
1302 // libcall (e.g. __ashlti3 for i128) -- which would be worse than the load
1303 // and is unavailable in freestanding environments that do not link a
1304 // runtime library.
1305 if (!DL.fitsInLegalInteger(Width: EltBits))
1306 return false;
1307
1308 // The rewrite is only valid for indices inside the table. The nusw the
1309 // shared matcher requires keeps the address computation from wrapping but
1310 // does not keep it inside the object: a nusw-only GEP with i >= K is a
1311 // well-defined pointer past the table, and a load through it (into
1312 // whatever follows) is not (1 << i) - 1. With inbounds such a GEP is poison
1313 // and the load is UB, so every executed load has 0 <= i < K.
1314 auto *GEP = cast<GetElementPtrInst>(Val: LI->getPointerOperand());
1315 if (!GEP->isInBounds())
1316 return false;
1317
1318 // K <= EltBits then guarantees i < EltBits, so the emitted `1 << i` never
1319 // shifts by >= bitwidth (no poison). A table with EltBits + 1 entries (whose
1320 // last element is the all-ones mask, needing a shift by EltBits) is
1321 // therefore rejected.
1322 if (K == 0 || K > EltBits)
1323 return false;
1324
1325 // The index must step by exactly one element, so the runtime index value is
1326 // the shift amount; a different scale would load tbl[c * i].
1327 if (GEPScale != EltBytes)
1328 return false;
1329
1330 // Every element must be the low-bits mask for its position.
1331 for (uint64_t J = 0; J < K; ++J) {
1332 Constant *Elt = ConstantFoldLoadFromConst(
1333 C: GVTable->getInitializer(), Ty: AccessType,
1334 Offset: APInt(GEPScale.getBitWidth(), J) * GEPScale, DL);
1335 auto *CI = dyn_cast_or_null<ConstantInt>(Val: Elt);
1336 if (!CI || CI->getValue() != APInt::getLowBitsSet(numBits: EltBits, loBitsSet: J))
1337 return false;
1338 }
1339
1340 // Emit (1 << i) - 1 in the element type and replace the load. A later
1341 // InstCombine canonicalizes this to ~(-1 << i); X86 lowers both to bzhi.
1342 IRBuilder<> Builder(LI);
1343 Value *Idx = Builder.CreateZExtOrTrunc(V: GepIdx, DestTy: AccessType);
1344 Value *Mask =
1345 Builder.CreateSub(LHS: Builder.CreateShl(LHS: ConstantInt::get(Ty: AccessType, V: 1), RHS: Idx),
1346 RHS: ConstantInt::get(Ty: AccessType, V: 1));
1347 LI->replaceAllUsesWith(V: Mask);
1348 ++NumTableBasedLowBitsMask;
1349 return true;
1350}
1351
1352// Match a table-based cttz, log2, or low-bits-mask implementation. These
1353// patterns share a load from a global table that we match first; then we
1354// try the specific matches.
1355static bool tryToRecognizeTableBasedPatterns(Instruction &I,
1356 const DataLayout &DL,
1357 TargetTransformInfo &TTI) {
1358 LoadInst *LI = dyn_cast<LoadInst>(Val: &I);
1359 if (!LI)
1360 return false;
1361
1362 Type *AccessType = LI->getType();
1363 if (!AccessType->isIntegerTy())
1364 return false;
1365
1366 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: LI->getPointerOperand());
1367 if (!GEP || !GEP->hasNoUnsignedSignedWrap())
1368 return false;
1369
1370 GlobalVariable *GVTable = dyn_cast<GlobalVariable>(Val: GEP->getPointerOperand());
1371 if (!GVTable || !GVTable->isConstant() ||
1372 !GVTable->hasDefinitiveInitializer())
1373 return false;
1374
1375 unsigned BW = DL.getIndexTypeSizeInBits(Ty: GEP->getType());
1376 APInt ModOffset(BW, 0);
1377 SmallMapVector<Value *, APInt, 4> VarOffsets;
1378 if (!GEP->collectOffset(DL, BitWidth: BW, VariableOffsets&: VarOffsets, ConstantOffset&: ModOffset) ||
1379 VarOffsets.size() != 1 || ModOffset != 0)
1380 return false;
1381 auto [GepIdx, GEPScale] = VarOffsets.front();
1382
1383 if (tryToRecognizeTableBasedCttz(LI, AccessType, GVTable, GepIdx, GEPScale,
1384 DL))
1385 return true;
1386
1387 if (tryToRecognizeTableBasedCtpop(LI, AccessType, GVTable, GepIdx, GEPScale,
1388 DL, TTI))
1389 return true;
1390
1391 if (tryToRecognizeTableBasedLog2(LI, AccessType, GVTable, GepIdx, GEPScale,
1392 DL, TTI))
1393 return true;
1394
1395 return tryToRecognizeTableBasedLowBitsMask(LI, AccessType, GVTable, GepIdx,
1396 GEPScale, DL);
1397}
1398
1399/// This is used by foldLoadsRecursive() to capture a Root Load node which is
1400/// of type or(load, load) and recursively build the wide load. Also capture the
1401/// shift amount, zero extend type and loadSize.
1402struct LoadOps {
1403 LoadInst *Root = nullptr;
1404 LoadInst *RootInsert = nullptr;
1405 bool FoundRoot = false;
1406 uint64_t LoadSize = 0;
1407 uint64_t Shift = 0;
1408 Type *ZextType;
1409 AAMDNodes AATags;
1410};
1411
1412// Identify and Merge consecutive loads recursively which is of the form
1413// (ZExt(L1) << shift1) | (ZExt(L2) << shift2) -> ZExt(L3) << shift1
1414// (ZExt(L1) << shift1) | ZExt(L2) -> ZExt(L3)
1415static bool foldLoadsRecursive(Value *V, LoadOps &LOps, const DataLayout &DL,
1416 AliasAnalysis &AA, bool IsRoot = false) {
1417 uint64_t ShAmt2;
1418 Value *X;
1419 Instruction *L1, *L2;
1420
1421 // For the root instruction, allow multiple uses since the final result
1422 // may legitimately be used in multiple places. For intermediate values,
1423 // require single use to avoid creating duplicate loads.
1424 if (!IsRoot && !V->hasOneUse())
1425 return false;
1426
1427 if (!match(V, P: m_c_Or(L: m_Value(V&: X),
1428 R: m_OneUse(SubPattern: m_ShlOrSelf(L: m_OneUse(SubPattern: m_ZExt(Op: m_Instruction(I&: L2))),
1429 R&: ShAmt2)))))
1430 return false;
1431
1432 if (!foldLoadsRecursive(V: X, LOps, DL, AA, /*IsRoot=*/false) && LOps.FoundRoot)
1433 // Avoid Partial chain merge.
1434 return false;
1435
1436 // Check if the pattern has loads
1437 LoadInst *LI1 = LOps.Root;
1438 uint64_t ShAmt1 = LOps.Shift;
1439 if (LOps.FoundRoot == false &&
1440 match(V: X, P: m_OneUse(
1441 SubPattern: m_ShlOrSelf(L: m_OneUse(SubPattern: m_ZExt(Op: m_Instruction(I&: L1))), R&: ShAmt1)))) {
1442 LI1 = dyn_cast<LoadInst>(Val: L1);
1443 }
1444 LoadInst *LI2 = dyn_cast<LoadInst>(Val: L2);
1445
1446 // Check if loads are same, atomic, volatile and having same address space.
1447 if (LI1 == LI2 || !LI1 || !LI2 || !LI1->isSimple() || !LI2->isSimple() ||
1448 LI1->getPointerAddressSpace() != LI2->getPointerAddressSpace())
1449 return false;
1450
1451 // Check if Loads come from same BB.
1452 if (LI1->getParent() != LI2->getParent())
1453 return false;
1454
1455 // Find the data layout
1456 bool IsBigEndian = DL.isBigEndian();
1457
1458 // Check if loads are consecutive and same size.
1459 Value *Load1Ptr = LI1->getPointerOperand();
1460 APInt Offset1(DL.getIndexTypeSizeInBits(Ty: Load1Ptr->getType()), 0);
1461 Load1Ptr =
1462 Load1Ptr->stripAndAccumulateConstantOffsets(DL, Offset&: Offset1,
1463 /* AllowNonInbounds */ true);
1464
1465 Value *Load2Ptr = LI2->getPointerOperand();
1466 APInt Offset2(DL.getIndexTypeSizeInBits(Ty: Load2Ptr->getType()), 0);
1467 Load2Ptr =
1468 Load2Ptr->stripAndAccumulateConstantOffsets(DL, Offset&: Offset2,
1469 /* AllowNonInbounds */ true);
1470
1471 // Verify if both loads have same base pointers
1472 uint64_t LoadSize1 = LI1->getType()->getPrimitiveSizeInBits();
1473 uint64_t LoadSize2 = LI2->getType()->getPrimitiveSizeInBits();
1474 if (Load1Ptr != Load2Ptr)
1475 return false;
1476
1477 // Make sure that there are no padding bits.
1478 if (!DL.typeSizeEqualsStoreSize(Ty: LI1->getType()) ||
1479 !DL.typeSizeEqualsStoreSize(Ty: LI2->getType()))
1480 return false;
1481
1482 // Alias Analysis to check for stores b/w the loads.
1483 LoadInst *Start = LOps.FoundRoot ? LOps.RootInsert : LI1, *End = LI2;
1484 MemoryLocation Loc;
1485 if (!Start->comesBefore(Other: End)) {
1486 std::swap(a&: Start, b&: End);
1487 // If LOps.RootInsert comes after LI2, since we use LI2 as the new insert
1488 // point, we should make sure whether the memory region accessed by LOps
1489 // isn't modified.
1490 if (LOps.FoundRoot)
1491 Loc = MemoryLocation(
1492 LOps.Root->getPointerOperand(),
1493 LocationSize::precise(Value: DL.getTypeStoreSize(
1494 Ty: IntegerType::get(C&: LI1->getContext(), NumBits: LOps.LoadSize))),
1495 LOps.AATags);
1496 else
1497 Loc = MemoryLocation::get(LI: End);
1498 } else
1499 Loc = MemoryLocation::get(LI: End);
1500 unsigned NumScanned = 0;
1501 for (Instruction &Inst :
1502 make_range(x: Start->getIterator(), y: End->getIterator())) {
1503 if (Inst.mayWriteToMemory() && isModSet(MRI: AA.getModRefInfo(I: &Inst, OptLoc: Loc)))
1504 return false;
1505
1506 if (++NumScanned > MaxInstrsToScan)
1507 return false;
1508 }
1509
1510 // Make sure Load with lower Offset is at LI1
1511 bool Reverse = false;
1512 if (Offset2.slt(RHS: Offset1)) {
1513 std::swap(a&: LI1, b&: LI2);
1514 std::swap(a&: ShAmt1, b&: ShAmt2);
1515 std::swap(a&: Offset1, b&: Offset2);
1516 std::swap(a&: Load1Ptr, b&: Load2Ptr);
1517 std::swap(a&: LoadSize1, b&: LoadSize2);
1518 Reverse = true;
1519 }
1520
1521 // Big endian swap the shifts
1522 if (IsBigEndian)
1523 std::swap(a&: ShAmt1, b&: ShAmt2);
1524
1525 // First load is always LI1. This is where we put the new load.
1526 // Use the merged load size available from LI1 for forward loads.
1527 if (LOps.FoundRoot) {
1528 if (!Reverse)
1529 LoadSize1 = LOps.LoadSize;
1530 else
1531 LoadSize2 = LOps.LoadSize;
1532 }
1533
1534 // Verify if shift amount and load index aligns and verifies that loads
1535 // are consecutive.
1536 uint64_t ShiftDiff = IsBigEndian ? LoadSize2 : LoadSize1;
1537 uint64_t PrevSize =
1538 DL.getTypeStoreSize(Ty: IntegerType::get(C&: LI1->getContext(), NumBits: LoadSize1));
1539 if ((ShAmt2 - ShAmt1) != ShiftDiff || (Offset2 - Offset1) != PrevSize)
1540 return false;
1541
1542 // Reject if the combined size of the loads exceeds the target type size.
1543 // This avoids attempting to emit an invalid ZExt (from wider to narrower
1544 // type) when out-of-bounds shifts lead to matching too many loads.
1545 if (LoadSize1 + LoadSize2 > X->getType()->getScalarSizeInBits())
1546 return false;
1547
1548 // Update LOps
1549 AAMDNodes AATags1 = LOps.AATags;
1550 AAMDNodes AATags2 = LI2->getAAMetadata();
1551 if (LOps.FoundRoot == false) {
1552 LOps.FoundRoot = true;
1553 AATags1 = LI1->getAAMetadata();
1554 }
1555 LOps.LoadSize = LoadSize1 + LoadSize2;
1556 LOps.RootInsert = Start;
1557
1558 // Concatenate the AATags of the Merged Loads.
1559 LOps.AATags = AATags1.concat(Other: AATags2);
1560
1561 LOps.Root = LI1;
1562 LOps.Shift = ShAmt1;
1563 LOps.ZextType = X->getType();
1564 return true;
1565}
1566
1567// For a given BB instruction, evaluate all loads in the chain that form a
1568// pattern which suggests that the loads can be combined. The one and only use
1569// of the loads is to form a wider load.
1570static bool foldConsecutiveLoads(Instruction &I, const DataLayout &DL,
1571 TargetTransformInfo &TTI, AliasAnalysis &AA,
1572 const DominatorTree &DT) {
1573 // Only consider load chains of scalar values.
1574 if (isa<VectorType>(Val: I.getType()))
1575 return false;
1576
1577 LoadOps LOps;
1578 if (!foldLoadsRecursive(V: &I, LOps, DL, AA, /*IsRoot=*/true) || !LOps.FoundRoot)
1579 return false;
1580
1581 IRBuilder<> Builder(&I);
1582 LoadInst *NewLoad = nullptr, *LI1 = LOps.Root;
1583
1584 // Allow a power of 2 number of bytes that fit in a legal integer type.
1585 bool Allowed = LOps.LoadSize >= 16 && isPowerOf2_64(Value: LOps.LoadSize) &&
1586 DL.fitsInLegalInteger(Width: LOps.LoadSize);
1587 if (!Allowed)
1588 return false;
1589
1590 unsigned AS = LI1->getPointerAddressSpace();
1591 unsigned Fast = 0;
1592 Allowed = TTI.allowsMisalignedMemoryAccesses(Context&: I.getContext(), BitWidth: LOps.LoadSize,
1593 AddressSpace: AS, Alignment: LI1->getAlign(), Fast: &Fast);
1594 if (!Allowed || !Fast)
1595 return false;
1596
1597 // Get the Index and Ptr for the new GEP.
1598 Value *Load1Ptr = LI1->getPointerOperand();
1599 Builder.SetInsertPoint(LOps.RootInsert);
1600 if (!DT.dominates(Def: Load1Ptr, User: LOps.RootInsert)) {
1601 APInt Offset1(DL.getIndexTypeSizeInBits(Ty: Load1Ptr->getType()), 0);
1602 Load1Ptr = Load1Ptr->stripAndAccumulateConstantOffsets(
1603 DL, Offset&: Offset1, /* AllowNonInbounds */ true);
1604 Load1Ptr = Builder.CreatePtrAdd(Ptr: Load1Ptr, Offset: Builder.getInt(AI: Offset1));
1605 }
1606 // Generate wider load.
1607 IntegerType *WiderType = IntegerType::get(C&: I.getContext(), NumBits: LOps.LoadSize);
1608 NewLoad = Builder.CreateAlignedLoad(Ty: WiderType, Ptr: Load1Ptr, Align: LI1->getAlign(),
1609 isVolatile: LI1->isVolatile(), Name: "");
1610 NewLoad->takeName(V: LI1);
1611 // Set the New Load AATags Metadata.
1612 if (LOps.AATags)
1613 NewLoad->setAAMetadata(LOps.AATags);
1614
1615 Value *NewOp = NewLoad;
1616 // Zero extend if needed.
1617 NewOp = Builder.CreateZExt(V: NewOp, DestTy: LOps.ZextType);
1618
1619 // Check if shift needed. We need to shift with the amount of load1
1620 // shift if not zero.
1621 if (LOps.Shift)
1622 NewOp = Builder.CreateShl(LHS: NewOp, RHS: LOps.Shift);
1623 I.replaceAllUsesWith(V: NewOp);
1624
1625 return true;
1626}
1627
1628/// ValWidth bits starting at ValOffset of Val stored at PtrBase+PtrOffset.
1629struct PartStore {
1630 Value *PtrBase;
1631 APInt PtrOffset;
1632 Value *Val;
1633 uint64_t ValOffset;
1634 uint64_t ValWidth;
1635 StoreInst *Store;
1636
1637 bool isCompatibleWith(const PartStore &Other) const {
1638 // Offset stripping looks through addrspacecasts, so an equal PtrBase does
1639 // not imply an equal address space, and thus not an equal PtrOffset width.
1640 return PtrBase == Other.PtrBase && Val == Other.Val &&
1641 Store->getPointerAddressSpace() ==
1642 Other.Store->getPointerAddressSpace();
1643 }
1644
1645 bool operator<(const PartStore &Other) const {
1646 return PtrOffset.slt(RHS: Other.PtrOffset);
1647 }
1648};
1649
1650static std::optional<PartStore> matchPartStore(Instruction &I,
1651 const DataLayout &DL) {
1652 auto *Store = dyn_cast<StoreInst>(Val: &I);
1653 if (!Store || !Store->isSimple())
1654 return std::nullopt;
1655
1656 Value *StoredVal = Store->getValueOperand();
1657 Type *StoredTy = StoredVal->getType();
1658 if (!StoredTy->isIntegerTy() || !DL.typeSizeEqualsStoreSize(Ty: StoredTy))
1659 return std::nullopt;
1660
1661 uint64_t ValWidth = StoredTy->getPrimitiveSizeInBits();
1662 uint64_t ValOffset;
1663 Value *Val;
1664 if (!match(V: StoredVal, P: m_Trunc(Op: m_LShrOrSelf(L: m_Value(V&: Val), R&: ValOffset))))
1665 return std::nullopt;
1666
1667 Value *Ptr = Store->getPointerOperand();
1668 APInt PtrOffset(DL.getIndexTypeSizeInBits(Ty: Ptr->getType()), 0);
1669 Value *PtrBase = Ptr->stripAndAccumulateConstantOffsets(
1670 DL, Offset&: PtrOffset, /*AllowNonInbounds=*/true);
1671 return {{.PtrBase: PtrBase, .PtrOffset: PtrOffset, .Val: Val, .ValOffset: ValOffset, .ValWidth: ValWidth, .Store: Store}};
1672}
1673
1674static bool mergeConsecutivePartStores(ArrayRef<PartStore> Parts,
1675 unsigned Width, const DataLayout &DL,
1676 TargetTransformInfo &TTI) {
1677 if (Parts.size() < 2)
1678 return false;
1679
1680 // Check whether combining the stores is profitable.
1681 // FIXME: We could generate smaller stores if we can't produce a large one.
1682 const PartStore &First = Parts.front();
1683 LLVMContext &Ctx = First.Store->getContext();
1684 unsigned Fast = 0;
1685 bool Allowed =
1686 Width >= 16 && isPowerOf2_64(Value: Width) && DL.fitsInLegalInteger(Width);
1687 if (!Allowed ||
1688 !TTI.allowsMisalignedMemoryAccesses(Context&: Ctx, BitWidth: Width,
1689 AddressSpace: First.Store->getPointerAddressSpace(),
1690 Alignment: First.Store->getAlign(), Fast: &Fast) ||
1691 !Fast)
1692 return false;
1693
1694 // Generate the combined store.
1695 IRBuilder<> Builder(First.Store);
1696 Type *NewTy = Type::getIntNTy(C&: Ctx, N: Width);
1697 Value *Val = First.Val;
1698 if (First.ValOffset != 0)
1699 Val = Builder.CreateLShr(LHS: Val, RHS: First.ValOffset);
1700 Val = Builder.CreateZExtOrTrunc(V: Val, DestTy: NewTy);
1701 StoreInst *Store = Builder.CreateAlignedStore(
1702 Val, Ptr: First.Store->getPointerOperand(), Align: First.Store->getAlign());
1703
1704 // Merge various metadata onto the new store.
1705 AAMDNodes AATags = First.Store->getAAMetadata();
1706 SmallVector<Instruction *> Stores = {First.Store};
1707 Stores.reserve(N: Parts.size());
1708 SmallVector<DebugLoc> DbgLocs = {First.Store->getDebugLoc()};
1709 DbgLocs.reserve(N: Parts.size());
1710 for (const PartStore &Part : drop_begin(RangeOrContainer&: Parts)) {
1711 AATags = AATags.concat(Other: Part.Store->getAAMetadata());
1712 Stores.push_back(Elt: Part.Store);
1713 DbgLocs.push_back(Elt: Part.Store->getDebugLoc());
1714 }
1715 Store->setAAMetadata(AATags);
1716 Store->mergeDIAssignID(SourceInstructions: Stores);
1717 Store->setDebugLoc(DebugLoc::getMergedLocations(Locs: DbgLocs));
1718
1719 // Remove the old stores.
1720 for (const PartStore &Part : Parts)
1721 Part.Store->eraseFromParent();
1722
1723 return true;
1724}
1725
1726static bool mergePartStores(SmallVectorImpl<PartStore> &Parts,
1727 const DataLayout &DL, TargetTransformInfo &TTI) {
1728 if (Parts.size() < 2)
1729 return false;
1730
1731 // We now have multiple parts of the same value stored to the same pointer.
1732 // Sort the parts by pointer offset, and make sure they are consistent with
1733 // the value offsets. Also check that the value is fully covered without
1734 // overlaps.
1735 bool Changed = false;
1736 llvm::sort(C&: Parts);
1737 int64_t LastEndOffsetFromFirst = 0;
1738 const PartStore *First = &Parts[0];
1739 for (const PartStore &Part : Parts) {
1740 APInt PtrOffsetFromFirst = Part.PtrOffset - First->PtrOffset;
1741 int64_t ValOffsetFromFirst = Part.ValOffset - First->ValOffset;
1742 if (PtrOffsetFromFirst * 8 != ValOffsetFromFirst ||
1743 LastEndOffsetFromFirst != ValOffsetFromFirst) {
1744 Changed |= mergeConsecutivePartStores(Parts: ArrayRef(First, &Part),
1745 Width: LastEndOffsetFromFirst, DL, TTI);
1746 First = &Part;
1747 LastEndOffsetFromFirst = Part.ValWidth;
1748 continue;
1749 }
1750
1751 LastEndOffsetFromFirst = ValOffsetFromFirst + Part.ValWidth;
1752 }
1753
1754 Changed |= mergeConsecutivePartStores(Parts: ArrayRef(First, Parts.end()),
1755 Width: LastEndOffsetFromFirst, DL, TTI);
1756 return Changed;
1757}
1758
1759static bool foldConsecutiveStores(BasicBlock &BB, const DataLayout &DL,
1760 TargetTransformInfo &TTI, AliasAnalysis &AA) {
1761 // FIXME: Add big endian support.
1762 if (DL.isBigEndian())
1763 return false;
1764
1765 BatchAAResults BatchAA(AA);
1766 SmallVector<PartStore, 8> Parts;
1767 bool MadeChange = false;
1768 for (Instruction &I : make_early_inc_range(Range&: BB)) {
1769 if (std::optional<PartStore> Part = matchPartStore(I, DL)) {
1770 if (Parts.empty() || Part->isCompatibleWith(Other: Parts[0])) {
1771 Parts.push_back(Elt: std::move(*Part));
1772 continue;
1773 }
1774
1775 MadeChange |= mergePartStores(Parts, DL, TTI);
1776 Parts.clear();
1777 Parts.push_back(Elt: std::move(*Part));
1778 continue;
1779 }
1780
1781 if (Parts.empty())
1782 continue;
1783
1784 if (I.mayThrow() ||
1785 (I.mayReadOrWriteMemory() &&
1786 isModOrRefSet(MRI: BatchAA.getModRefInfo(
1787 I: &I, OptLoc: MemoryLocation::getBeforeOrAfter(Ptr: Parts[0].PtrBase))))) {
1788 MadeChange |= mergePartStores(Parts, DL, TTI);
1789 Parts.clear();
1790 continue;
1791 }
1792 }
1793
1794 MadeChange |= mergePartStores(Parts, DL, TTI);
1795 return MadeChange;
1796}
1797
1798/// Combine away instructions providing they are still equivalent when compared
1799/// against 0. i.e do they have any bits set.
1800static Value *optimizeShiftInOrChain(Value *V, IRBuilder<> &Builder) {
1801 auto *I = dyn_cast<Instruction>(Val: V);
1802 if (!I || I->getOpcode() != Instruction::Or || !I->hasOneUse())
1803 return nullptr;
1804
1805 Value *A;
1806
1807 // Look deeper into the chain of or's, combining away shl (so long as they are
1808 // nuw or nsw).
1809 Value *Op0 = I->getOperand(i: 0);
1810 if (match(V: Op0, P: m_CombineOr(Ps: m_NSWShl(L: m_Value(V&: A), R: m_Value()),
1811 Ps: m_NUWShl(L: m_Value(V&: A), R: m_Value()))))
1812 Op0 = A;
1813 else if (auto *NOp = optimizeShiftInOrChain(V: Op0, Builder))
1814 Op0 = NOp;
1815
1816 Value *Op1 = I->getOperand(i: 1);
1817 if (match(V: Op1, P: m_CombineOr(Ps: m_NSWShl(L: m_Value(V&: A), R: m_Value()),
1818 Ps: m_NUWShl(L: m_Value(V&: A), R: m_Value()))))
1819 Op1 = A;
1820 else if (auto *NOp = optimizeShiftInOrChain(V: Op1, Builder))
1821 Op1 = NOp;
1822
1823 if (Op0 != I->getOperand(i: 0) || Op1 != I->getOperand(i: 1))
1824 return Builder.CreateOr(LHS: Op0, RHS: Op1);
1825 return nullptr;
1826}
1827
1828static bool foldICmpOrChain(Instruction &I, const DataLayout &DL,
1829 TargetTransformInfo &TTI, AliasAnalysis &AA,
1830 const DominatorTree &DT) {
1831 CmpPredicate Pred;
1832 Value *Op0;
1833 if (!match(V: &I, P: m_ICmp(Pred, L: m_Value(V&: Op0), R: m_Zero())) ||
1834 !ICmpInst::isEquality(P: Pred))
1835 return false;
1836
1837 // If the chain or or's matches a load, combine to that before attempting to
1838 // remove shifts.
1839 if (auto OpI = dyn_cast<Instruction>(Val: Op0))
1840 if (OpI->getOpcode() == Instruction::Or)
1841 if (foldConsecutiveLoads(I&: *OpI, DL, TTI, AA, DT))
1842 return true;
1843
1844 IRBuilder<> Builder(&I);
1845 // icmp eq/ne or(shl(a), b), 0 -> icmp eq/ne or(a, b), 0
1846 if (auto *Res = optimizeShiftInOrChain(V: Op0, Builder)) {
1847 I.replaceAllUsesWith(V: Builder.CreateICmp(P: Pred, LHS: Res, RHS: I.getOperand(i: 1)));
1848 return true;
1849 }
1850
1851 return false;
1852}
1853
1854// Calculate GEP Stride and accumulated const ModOffset. Return Stride and
1855// ModOffset
1856static std::pair<APInt, APInt>
1857getStrideAndModOffsetOfGEP(Value *PtrOp, const DataLayout &DL) {
1858 unsigned BW = DL.getIndexTypeSizeInBits(Ty: PtrOp->getType());
1859 std::optional<APInt> Stride;
1860 APInt ModOffset(BW, 0);
1861 // Return a minimum gep stride, greatest common divisor of consective gep
1862 // index scales(c.f. Bézout's identity).
1863 while (auto *GEP = dyn_cast<GEPOperator>(Val: PtrOp)) {
1864 SmallMapVector<Value *, APInt, 4> VarOffsets;
1865 if (!GEP->collectOffset(DL, BitWidth: BW, VariableOffsets&: VarOffsets, ConstantOffset&: ModOffset))
1866 break;
1867
1868 for (auto [V, Scale] : VarOffsets) {
1869 // Only keep a power of two factor for non-inbounds
1870 if (!GEP->hasNoUnsignedSignedWrap())
1871 Scale = APInt::getOneBitSet(numBits: Scale.getBitWidth(), BitNo: Scale.countr_zero());
1872
1873 if (!Stride)
1874 Stride = Scale;
1875 else
1876 Stride = APIntOps::GreatestCommonDivisor(A: *Stride, B: Scale);
1877 }
1878
1879 PtrOp = GEP->getPointerOperand();
1880 }
1881
1882 // Check whether pointer arrives back at Global Variable via at least one GEP.
1883 // Even if it doesn't, we can check by alignment.
1884 if (!isa<GlobalVariable>(Val: PtrOp) || !Stride)
1885 return {APInt(BW, 1), APInt(BW, 0)};
1886
1887 // In consideration of signed GEP indices, non-negligible offset become
1888 // remainder of division by minimum GEP stride.
1889 ModOffset = ModOffset.srem(RHS: *Stride);
1890 if (ModOffset.isNegative())
1891 ModOffset += *Stride;
1892
1893 return {*Stride, ModOffset};
1894}
1895
1896/// If C is a constant patterned array and all valid loaded results for given
1897/// alignment are same to a constant, return that constant.
1898static bool foldPatternedLoads(Instruction &I, const DataLayout &DL) {
1899 auto *LI = dyn_cast<LoadInst>(Val: &I);
1900 if (!LI || LI->isVolatile())
1901 return false;
1902
1903 // We can only fold the load if it is from a constant global with definitive
1904 // initializer. Skip expensive logic if this is not the case.
1905 auto *PtrOp = LI->getPointerOperand();
1906 auto *GV = dyn_cast<GlobalVariable>(Val: getUnderlyingObject(V: PtrOp));
1907 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
1908 return false;
1909
1910 // Bail for large initializers in excess of 4K to avoid too many scans.
1911 Constant *C = GV->getInitializer();
1912 uint64_t GVSize = DL.getTypeAllocSize(Ty: C->getType());
1913 if (!GVSize || 4096 < GVSize)
1914 return false;
1915
1916 Type *LoadTy = LI->getType();
1917 unsigned BW = DL.getIndexTypeSizeInBits(Ty: PtrOp->getType());
1918 auto [Stride, ConstOffset] = getStrideAndModOffsetOfGEP(PtrOp, DL);
1919
1920 // Any possible offset could be multiple of GEP stride. And any valid
1921 // offset is multiple of load alignment, so checking only multiples of bigger
1922 // one is sufficient to say results' equality.
1923 if (auto LA = LI->getAlign();
1924 LA <= GV->getAlign().valueOrOne() && Stride.getZExtValue() < LA.value()) {
1925 ConstOffset = APInt(BW, 0);
1926 Stride = APInt(BW, LA.value());
1927 }
1928
1929 Constant *Ca = ConstantFoldLoadFromConst(C, Ty: LoadTy, Offset: ConstOffset, DL);
1930 if (!Ca)
1931 return false;
1932
1933 unsigned E = GVSize - DL.getTypeStoreSize(Ty: LoadTy);
1934 for (; ConstOffset.getZExtValue() <= E; ConstOffset += Stride)
1935 if (Ca != ConstantFoldLoadFromConst(C, Ty: LoadTy, Offset: ConstOffset, DL))
1936 return false;
1937
1938 I.replaceAllUsesWith(V: Ca);
1939
1940 return true;
1941}
1942
1943namespace {
1944class StrNCmpInliner {
1945public:
1946 StrNCmpInliner(CallInst *CI, LibFunc Func, DomTreeUpdater *DTU,
1947 const DataLayout &DL)
1948 : CI(CI), Func(Func), DTU(DTU), DL(DL) {}
1949
1950 bool optimizeStrNCmp();
1951
1952private:
1953 void inlineCompare(Value *LHS, StringRef RHS, uint64_t N, bool Swapped);
1954
1955 CallInst *CI;
1956 LibFunc Func;
1957 DomTreeUpdater *DTU;
1958 const DataLayout &DL;
1959};
1960
1961} // namespace
1962
1963/// First we normalize calls to strncmp/strcmp to the form of
1964/// compare(s1, s2, N), which means comparing first N bytes of s1 and s2
1965/// (without considering '\0').
1966///
1967/// Examples:
1968///
1969/// \code
1970/// strncmp(s, "a", 3) -> compare(s, "a", 2)
1971/// strncmp(s, "abc", 3) -> compare(s, "abc", 3)
1972/// strncmp(s, "a\0b", 3) -> compare(s, "a\0b", 2)
1973/// strcmp(s, "a") -> compare(s, "a", 2)
1974///
1975/// char s2[] = {'a'}
1976/// strncmp(s, s2, 3) -> compare(s, s2, 3)
1977///
1978/// char s2[] = {'a', 'b', 'c', 'd'}
1979/// strncmp(s, s2, 3) -> compare(s, s2, 3)
1980/// \endcode
1981///
1982/// We only handle cases where N and exactly one of s1 and s2 are constant.
1983/// Cases that s1 and s2 are both constant are already handled by the
1984/// instcombine pass.
1985///
1986/// We do not handle cases where N > StrNCmpInlineThreshold.
1987///
1988/// We also do not handles cases where N < 2, which are already
1989/// handled by the instcombine pass.
1990///
1991bool StrNCmpInliner::optimizeStrNCmp() {
1992 if (StrNCmpInlineThreshold < 2)
1993 return false;
1994
1995 if (!isOnlyUsedInZeroComparison(CtxI: CI))
1996 return false;
1997
1998 Value *Str1P = CI->getArgOperand(i: 0);
1999 Value *Str2P = CI->getArgOperand(i: 1);
2000 // Should be handled elsewhere.
2001 if (Str1P == Str2P)
2002 return false;
2003
2004 StringRef Str1, Str2;
2005 bool HasStr1 = getConstantStringInfo(V: Str1P, Str&: Str1, /*TrimAtNul=*/false);
2006 bool HasStr2 = getConstantStringInfo(V: Str2P, Str&: Str2, /*TrimAtNul=*/false);
2007 if (HasStr1 == HasStr2)
2008 return false;
2009
2010 // Note that '\0' and characters after it are not trimmed.
2011 StringRef Str = HasStr1 ? Str1 : Str2;
2012 Value *StrP = HasStr1 ? Str2P : Str1P;
2013
2014 size_t Idx = Str.find(C: '\0');
2015 uint64_t N = Idx == StringRef::npos ? UINT64_MAX : Idx + 1;
2016 if (Func == LibFunc_strncmp) {
2017 if (auto *ConstInt = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: 2)))
2018 N = std::min(a: N, b: ConstInt->getZExtValue());
2019 else
2020 return false;
2021 }
2022 // Now N means how many bytes we need to compare at most.
2023 if (N > Str.size() || N < 2 || N > StrNCmpInlineThreshold)
2024 return false;
2025
2026 // Cases where StrP has two or more dereferenceable bytes might be better
2027 // optimized elsewhere.
2028 bool CanBeNull = false;
2029 if (StrP->getPointerDereferenceableBytes(DL, CanBeNull,
2030 /*CanBeFreed=*/nullptr) > 1)
2031 return false;
2032 inlineCompare(LHS: StrP, RHS: Str, N, Swapped: HasStr1);
2033 return true;
2034}
2035
2036/// Convert
2037///
2038/// \code
2039/// ret = compare(s1, s2, N)
2040/// \endcode
2041///
2042/// into
2043///
2044/// \code
2045/// ret = (int)s1[0] - (int)s2[0]
2046/// if (ret != 0)
2047/// goto NE
2048/// ...
2049/// ret = (int)s1[N-2] - (int)s2[N-2]
2050/// if (ret != 0)
2051/// goto NE
2052/// ret = (int)s1[N-1] - (int)s2[N-1]
2053/// NE:
2054/// \endcode
2055///
2056/// CFG before and after the transformation:
2057///
2058/// (before)
2059/// BBCI
2060///
2061/// (after)
2062/// BBCI -> BBSubs[0] (sub,icmp) --NE-> BBNE -> BBTail
2063/// | ^
2064/// E |
2065/// | |
2066/// BBSubs[1] (sub,icmp) --NE-----+
2067/// ... |
2068/// BBSubs[N-1] (sub) ---------+
2069///
2070void StrNCmpInliner::inlineCompare(Value *LHS, StringRef RHS, uint64_t N,
2071 bool Swapped) {
2072 auto &Ctx = CI->getContext();
2073 IRBuilder<> B(*CI->getModule());
2074 // We want these instructions to be recognized as inlined instructions for the
2075 // compare call, but we don't have a source location for the definition of
2076 // that function, since we're generating that code now. Because the generated
2077 // code is a viable point for a memory access error, we make the pragmatic
2078 // choice here to directly use CI's location so that we have useful
2079 // attribution for the generated code.
2080 B.SetCurrentDebugLocation(CI->getDebugLoc());
2081
2082 BasicBlock *BBCI = CI->getParent();
2083 BasicBlock *BBTail =
2084 SplitBlock(Old: BBCI, SplitPt: CI, DTU, LI: nullptr, MSSAU: nullptr, BBName: BBCI->getName() + ".tail");
2085
2086 SmallVector<BasicBlock *> BBSubs;
2087 for (uint64_t I = 0; I < N; ++I)
2088 BBSubs.push_back(
2089 Elt: BasicBlock::Create(Context&: Ctx, Name: "sub_" + Twine(I), Parent: BBCI->getParent(), InsertBefore: BBTail));
2090 BasicBlock *BBNE = BasicBlock::Create(Context&: Ctx, Name: "ne", Parent: BBCI->getParent(), InsertBefore: BBTail);
2091
2092 cast<UncondBrInst>(Val: BBCI->getTerminator())->setSuccessor(BBSubs[0]);
2093
2094 B.SetInsertPoint(BBNE);
2095 PHINode *Phi = B.CreatePHI(Ty: CI->getType(), NumReservedValues: N);
2096 B.CreateBr(Dest: BBTail);
2097
2098 Value *Base = LHS;
2099 for (uint64_t i = 0; i < N; ++i) {
2100 B.SetInsertPoint(BBSubs[i]);
2101 Value *VL =
2102 B.CreateZExt(V: B.CreateLoad(Ty: B.getInt8Ty(),
2103 Ptr: B.CreateInBoundsPtrAdd(Ptr: Base, Offset: B.getInt64(C: i))),
2104 DestTy: CI->getType());
2105 Value *VR =
2106 ConstantInt::get(Ty: CI->getType(), V: static_cast<unsigned char>(RHS[i]));
2107 Value *Sub = Swapped ? B.CreateSub(LHS: VR, RHS: VL) : B.CreateSub(LHS: VL, RHS: VR);
2108 if (i < N - 1) {
2109 CondBrInst *CondBrInst = B.CreateCondBr(
2110 Cond: B.CreateICmpNE(LHS: Sub, RHS: ConstantInt::get(Ty: CI->getType(), V: 0)), True: BBNE,
2111 False: BBSubs[i + 1]);
2112
2113 Function *F = CI->getFunction();
2114 assert(F && "Instruction does not belong to a function!");
2115 std::optional<uint64_t> EC = F->getEntryCount();
2116 if (EC && *EC > 0)
2117 setExplicitlyUnknownBranchWeights(I&: *CondBrInst, DEBUG_TYPE);
2118 } else {
2119 B.CreateBr(Dest: BBNE);
2120 }
2121
2122 Phi->addIncoming(V: Sub, BB: BBSubs[i]);
2123 }
2124
2125 CI->replaceAllUsesWith(V: Phi);
2126 CI->eraseFromParent();
2127
2128 if (DTU) {
2129 SmallVector<DominatorTree::UpdateType, 8> Updates;
2130 Updates.push_back(Elt: {DominatorTree::Insert, BBCI, BBSubs[0]});
2131 for (uint64_t i = 0; i < N; ++i) {
2132 if (i < N - 1)
2133 Updates.push_back(Elt: {DominatorTree::Insert, BBSubs[i], BBSubs[i + 1]});
2134 Updates.push_back(Elt: {DominatorTree::Insert, BBSubs[i], BBNE});
2135 }
2136 Updates.push_back(Elt: {DominatorTree::Insert, BBNE, BBTail});
2137 Updates.push_back(Elt: {DominatorTree::Delete, BBCI, BBTail});
2138 DTU->applyUpdates(Updates);
2139 }
2140}
2141
2142/// Convert memchr with a small constant string into a switch
2143static bool foldMemChr(CallInst *Call, DomTreeUpdater *DTU,
2144 const DataLayout &DL) {
2145 if (isa<Constant>(Val: Call->getArgOperand(i: 1)))
2146 return false;
2147
2148 StringRef Str;
2149 Value *Base = Call->getArgOperand(i: 0);
2150 if (!getConstantStringInfo(V: Base, Str, /*TrimAtNul=*/false))
2151 return false;
2152
2153 uint64_t N = Str.size();
2154 if (auto *ConstInt = dyn_cast<ConstantInt>(Val: Call->getArgOperand(i: 2))) {
2155 uint64_t Val = ConstInt->getZExtValue();
2156 // Ignore the case that n is larger than the size of string.
2157 if (Val > N)
2158 return false;
2159 N = Val;
2160 } else
2161 return false;
2162
2163 if (N > MemChrInlineThreshold)
2164 return false;
2165
2166 BasicBlock *BB = Call->getParent();
2167 BasicBlock *BBNext = SplitBlock(Old: BB, SplitPt: Call, DTU);
2168 IRBuilder<> IRB(BB);
2169 IRB.SetCurrentDebugLocation(Call->getDebugLoc());
2170 IntegerType *ByteTy = IRB.getInt8Ty();
2171 BB->getTerminator()->eraseFromParent();
2172 SwitchInst *SI = IRB.CreateSwitch(
2173 V: IRB.CreateTrunc(V: Call->getArgOperand(i: 1), DestTy: ByteTy), Dest: BBNext, NumCases: N);
2174 // We can't know the precise weights here, as they would depend on the value
2175 // distribution of Call->getArgOperand(1). So we just mark it as "unknown".
2176 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *SI, DEBUG_TYPE);
2177 Type *IndexTy = DL.getIndexType(PtrTy: Call->getType());
2178 SmallVector<DominatorTree::UpdateType, 8> Updates;
2179
2180 BasicBlock *BBSuccess = BasicBlock::Create(
2181 Context&: Call->getContext(), Name: "memchr.success", Parent: BB->getParent(), InsertBefore: BBNext);
2182 IRB.SetInsertPoint(BBSuccess);
2183 PHINode *IndexPHI = IRB.CreatePHI(Ty: IndexTy, NumReservedValues: N, Name: "memchr.idx");
2184 Value *FirstOccursLocation = IRB.CreateInBoundsPtrAdd(Ptr: Base, Offset: IndexPHI);
2185 IRB.CreateBr(Dest: BBNext);
2186 if (DTU)
2187 Updates.push_back(Elt: {DominatorTree::Insert, BBSuccess, BBNext});
2188
2189 SmallPtrSet<ConstantInt *, 4> Cases;
2190 for (uint64_t I = 0; I < N; ++I) {
2191 ConstantInt *CaseVal =
2192 ConstantInt::get(Ty: ByteTy, V: static_cast<unsigned char>(Str[I]));
2193 if (!Cases.insert(Ptr: CaseVal).second)
2194 continue;
2195
2196 BasicBlock *BBCase = BasicBlock::Create(Context&: Call->getContext(), Name: "memchr.case",
2197 Parent: BB->getParent(), InsertBefore: BBSuccess);
2198 SI->addCase(OnVal: CaseVal, Dest: BBCase);
2199 IRB.SetInsertPoint(BBCase);
2200 IndexPHI->addIncoming(V: ConstantInt::get(Ty: IndexTy, V: I), BB: BBCase);
2201 IRB.CreateBr(Dest: BBSuccess);
2202 if (DTU) {
2203 Updates.push_back(Elt: {DominatorTree::Insert, BB, BBCase});
2204 Updates.push_back(Elt: {DominatorTree::Insert, BBCase, BBSuccess});
2205 }
2206 }
2207
2208 PHINode *PHI =
2209 PHINode::Create(Ty: Call->getType(), NumReservedValues: 2, NameStr: Call->getName(), InsertBefore: BBNext->begin());
2210 PHI->addIncoming(V: Constant::getNullValue(Ty: Call->getType()), BB);
2211 PHI->addIncoming(V: FirstOccursLocation, BB: BBSuccess);
2212
2213 Call->replaceAllUsesWith(V: PHI);
2214 Call->eraseFromParent();
2215
2216 if (DTU)
2217 DTU->applyUpdates(Updates);
2218
2219 return true;
2220}
2221
2222static bool foldLibCalls(Instruction &I, TargetTransformInfo &TTI,
2223 TargetLibraryInfo &TLI, AssumptionCache &AC,
2224 DominatorTree &DT, const DataLayout &DL,
2225 bool &MadeCFGChange) {
2226
2227 auto *CI = dyn_cast<CallInst>(Val: &I);
2228 if (!CI || CI->isNoBuiltin())
2229 return false;
2230
2231 Function *CalledFunc = CI->getCalledFunction();
2232 if (!CalledFunc)
2233 return false;
2234
2235 LibFunc LF = TLI.getLibFunc(FDecl: *CalledFunc);
2236 if (!isLibFuncEmittable(M: CI->getModule(), TLI: &TLI, TheLibFunc: LF))
2237 return false;
2238
2239 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);
2240
2241 switch (LF) {
2242 case LibFunc_sqrt:
2243 case LibFunc_sqrtf:
2244 case LibFunc_sqrtl:
2245 return foldSqrt(Call: CI, Func: LF, TTI, TLI, AC, DT);
2246 case LibFunc_strcmp:
2247 case LibFunc_strncmp:
2248 if (StrNCmpInliner(CI, LF, &DTU, DL).optimizeStrNCmp()) {
2249 MadeCFGChange = true;
2250 return true;
2251 }
2252 break;
2253 case LibFunc_memchr:
2254 if (foldMemChr(Call: CI, DTU: &DTU, DL)) {
2255 MadeCFGChange = true;
2256 return true;
2257 }
2258 break;
2259 default:;
2260 }
2261 return false;
2262}
2263
2264/// Match high part of long multiplication.
2265///
2266/// Considering a multiply made up of high and low parts, we can split the
2267/// multiply into:
2268/// x * y == (xh*T + xl) * (yh*T + yl)
2269/// where xh == x>>32 and xl == x & 0xffffffff. T = 2^32.
2270/// This expands to
2271/// xh*yh*T*T + xh*yl*T + xl*yh*T + xl*yl
2272/// which can be drawn as
2273/// [ xh*yh ]
2274/// [ xh*yl ]
2275/// [ xl*yh ]
2276/// [ xl*yl ]
2277/// We are looking for the "high" half, which is xh*yh + xh*yl>>32 + xl*yh>>32 +
2278/// some carrys. The carry makes this difficult and there are multiple ways of
2279/// representing it. The ones we attempt to support here are:
2280/// Carry: xh*yh + carry + lowsum
2281/// carry = lowsum < xh*yl ? 0x1000000 : 0
2282/// lowsum = xh*yl + xl*yh + (xl*yl>>32)
2283/// Ladder: xh*yh + c2>>32 + c3>>32
2284/// c2 = xh*yl + (xl*yl>>32); c3 = c2&0xffffffff + xl*yh
2285/// or c2 = (xl*yh&0xffffffff) + xh*yl + (xl*yl>>32); c3 = xl*yh
2286/// Carry4: xh*yh + carry + crosssum>>32 + (xl*yl + crosssum&0xffffffff) >> 32
2287/// crosssum = xh*yl + xl*yh
2288/// carry = crosssum < xh*yl ? 0x1000000 : 0
2289/// Ladder4: xh*yh + (xl*yh)>>32 + (xh*yl)>>32 + low>>32;
2290/// low = (xl*yl)>>32 + (xl*yh)&0xffffffff + (xh*yl)&0xffffffff
2291///
2292/// They all start by matching xh*yh + 2 or 3 other operands. The bottom of the
2293/// tree is xh*yh, xh*yl, xl*yh and xl*yl.
2294static bool foldMulHigh(Instruction &I) {
2295 Type *Ty = I.getType();
2296 if (!Ty->isIntOrIntVectorTy())
2297 return false;
2298
2299 unsigned BitWidth = Ty->getScalarSizeInBits();
2300 APInt LowMask = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth / 2);
2301 if (BitWidth % 2 != 0)
2302 return false;
2303
2304 auto CreateMulHigh = [&](Value *X, Value *Y) {
2305 IRBuilder<> Builder(&I);
2306 Type *NTy = Ty->getWithNewBitWidth(NewBitWidth: BitWidth * 2);
2307 Value *XExt = Builder.CreateZExt(V: X, DestTy: NTy);
2308 Value *YExt = Builder.CreateZExt(V: Y, DestTy: NTy);
2309 Value *Mul = Builder.CreateMul(LHS: XExt, RHS: YExt, Name: "", /*HasNUW=*/true);
2310 Value *High = Builder.CreateLShr(LHS: Mul, RHS: BitWidth);
2311 Value *Res = Builder.CreateTrunc(V: High, DestTy: Ty, Name: "", /*HasNUW=*/IsNUW: true);
2312 Res->takeName(V: &I);
2313 I.replaceAllUsesWith(V: Res);
2314 LLVM_DEBUG(dbgs() << "Created long multiply from parts of " << *X << " and "
2315 << *Y << "\n");
2316 return true;
2317 };
2318
2319 // Common check routines for X_lo*Y_lo and X_hi*Y_lo
2320 auto CheckLoLo = [&](Value *XlYl, Value *X, Value *Y) {
2321 return match(V: XlYl, P: m_c_Mul(L: m_And(L: m_Specific(V: X), R: m_SpecificInt(V: LowMask)),
2322 R: m_And(L: m_Specific(V: Y), R: m_SpecificInt(V: LowMask))));
2323 };
2324 auto CheckHiLo = [&](Value *XhYl, Value *X, Value *Y) {
2325 return match(V: XhYl,
2326 P: m_c_Mul(L: m_LShr(L: m_Specific(V: X), R: m_SpecificInt(V: BitWidth / 2)),
2327 R: m_And(L: m_Specific(V: Y), R: m_SpecificInt(V: LowMask))));
2328 };
2329
2330 auto FoldMulHighCarry = [&](Value *X, Value *Y, Instruction *Carry,
2331 Instruction *B) {
2332 // Looking for LowSum >> 32 and carry (select)
2333 if (Carry->getOpcode() != Instruction::Select)
2334 std::swap(a&: Carry, b&: B);
2335
2336 // Carry = LowSum < XhYl ? 0x100000000 : 0
2337 Value *LowSum, *XhYl;
2338 if (!match(V: Carry,
2339 P: m_OneUse(SubPattern: m_Select(
2340 C: m_OneUse(SubPattern: m_SpecificICmp(MatchPred: ICmpInst::ICMP_ULT, L: m_Value(V&: LowSum),
2341 R: m_Value(V&: XhYl))),
2342 L: m_SpecificInt(V: APInt::getOneBitSet(numBits: BitWidth, BitNo: BitWidth / 2)),
2343 R: m_Zero()))))
2344 return false;
2345
2346 // XhYl can be Xh*Yl or Xl*Yh
2347 if (!CheckHiLo(XhYl, X, Y)) {
2348 if (CheckHiLo(XhYl, Y, X))
2349 std::swap(a&: X, b&: Y);
2350 else
2351 return false;
2352 }
2353 if (XhYl->hasNUsesOrMore(N: 3))
2354 return false;
2355
2356 // B = LowSum >> 32
2357 if (!match(V: B, P: m_OneUse(SubPattern: m_LShr(L: m_Specific(V: LowSum),
2358 R: m_SpecificInt(V: BitWidth / 2)))) ||
2359 LowSum->hasNUsesOrMore(N: 3))
2360 return false;
2361
2362 // LowSum = XhYl + XlYh + XlYl>>32
2363 Value *XlYh, *XlYl;
2364 auto XlYlHi = m_LShr(L: m_Value(V&: XlYl), R: m_SpecificInt(V: BitWidth / 2));
2365 if (!match(V: LowSum,
2366 P: m_c_Add(L: m_Specific(V: XhYl),
2367 R: m_OneUse(SubPattern: m_c_Add(L: m_OneUse(SubPattern: m_Value(V&: XlYh)), R: XlYlHi)))) &&
2368 !match(V: LowSum, P: m_c_Add(L: m_OneUse(SubPattern: m_Value(V&: XlYh)),
2369 R: m_OneUse(SubPattern: m_c_Add(L: m_Specific(V: XhYl), R: XlYlHi)))) &&
2370 !match(V: LowSum,
2371 P: m_c_Add(L: XlYlHi, R: m_OneUse(SubPattern: m_c_Add(L: m_Specific(V: XhYl),
2372 R: m_OneUse(SubPattern: m_Value(V&: XlYh)))))))
2373 return false;
2374
2375 // Check XlYl and XlYh
2376 if (!CheckLoLo(XlYl, X, Y))
2377 return false;
2378 if (!CheckHiLo(XlYh, Y, X))
2379 return false;
2380
2381 return CreateMulHigh(X, Y);
2382 };
2383
2384 auto FoldMulHighLadder = [&](Value *X, Value *Y, Instruction *A,
2385 Instruction *B) {
2386 // xh*yh + c2>>32 + c3>>32
2387 // c2 = xh*yl + (xl*yl>>32); c3 = c2&0xffffffff + xl*yh
2388 // or c2 = (xl*yh&0xffffffff) + xh*yl + (xl*yl>>32); c3 = xh*yl
2389 Value *XlYh, *XhYl, *XlYl, *C2, *C3;
2390 // Strip off the two expected shifts.
2391 if (!match(V: A, P: m_LShr(L: m_Value(V&: C2), R: m_SpecificInt(V: BitWidth / 2))) ||
2392 !match(V: B, P: m_LShr(L: m_Value(V&: C3), R: m_SpecificInt(V: BitWidth / 2))))
2393 return false;
2394
2395 if (match(V: C3, P: m_c_Add(L: m_Add(L: m_Value(), R: m_Value()), R: m_Value())))
2396 std::swap(a&: C2, b&: C3);
2397 // Try to match c2 = (xl*yh&0xffffffff) + xh*yl + (xl*yl>>32)
2398 if (match(V: C2,
2399 P: m_c_Add(L: m_c_Add(L: m_And(L: m_Specific(V: C3), R: m_SpecificInt(V: LowMask)),
2400 R: m_Value(V&: XlYh)),
2401 R: m_LShr(L: m_Value(V&: XlYl), R: m_SpecificInt(V: BitWidth / 2)))) ||
2402 match(V: C2, P: m_c_Add(L: m_c_Add(L: m_And(L: m_Specific(V: C3), R: m_SpecificInt(V: LowMask)),
2403 R: m_LShr(L: m_Value(V&: XlYl),
2404 R: m_SpecificInt(V: BitWidth / 2))),
2405 R: m_Value(V&: XlYh))) ||
2406 match(V: C2, P: m_c_Add(L: m_c_Add(L: m_LShr(L: m_Value(V&: XlYl),
2407 R: m_SpecificInt(V: BitWidth / 2)),
2408 R: m_Value(V&: XlYh)),
2409 R: m_And(L: m_Specific(V: C3), R: m_SpecificInt(V: LowMask))))) {
2410 XhYl = C3;
2411 } else {
2412 // Match c3 = c2&0xffffffff + xl*yh
2413 if (!match(V: C3, P: m_c_Add(L: m_And(L: m_Specific(V: C2), R: m_SpecificInt(V: LowMask)),
2414 R: m_Value(V&: XlYh))))
2415 std::swap(a&: C2, b&: C3);
2416 if (!match(V: C3, P: m_c_Add(L: m_OneUse(
2417 SubPattern: m_And(L: m_Specific(V: C2), R: m_SpecificInt(V: LowMask))),
2418 R: m_Value(V&: XlYh))) ||
2419 !C3->hasOneUse() || C2->hasNUsesOrMore(N: 3))
2420 return false;
2421
2422 // Match c2 = xh*yl + (xl*yl >> 32)
2423 if (!match(V: C2, P: m_c_Add(L: m_LShr(L: m_Value(V&: XlYl), R: m_SpecificInt(V: BitWidth / 2)),
2424 R: m_Value(V&: XhYl))))
2425 return false;
2426 }
2427
2428 // Match XhYl and XlYh - they can appear either way around.
2429 if (!CheckHiLo(XlYh, Y, X))
2430 std::swap(a&: XlYh, b&: XhYl);
2431 if (!CheckHiLo(XlYh, Y, X))
2432 return false;
2433 if (!CheckHiLo(XhYl, X, Y))
2434 return false;
2435 if (!CheckLoLo(XlYl, X, Y))
2436 return false;
2437
2438 return CreateMulHigh(X, Y);
2439 };
2440
2441 auto FoldMulHighLadder4 = [&](Value *X, Value *Y, Instruction *A,
2442 Instruction *B, Instruction *C) {
2443 /// Ladder4: xh*yh + (xl*yh)>>32 + (xh+yl)>>32 + low>>32;
2444 /// low = (xl*yl)>>32 + (xl*yh)&0xffffffff + (xh*yl)&0xffffffff
2445
2446 // Find A = Low >> 32 and B/C = XhYl>>32, XlYh>>32.
2447 auto ShiftAdd =
2448 m_LShr(L: m_Add(L: m_Value(), R: m_Value()), R: m_SpecificInt(V: BitWidth / 2));
2449 if (!match(V: A, P: ShiftAdd))
2450 std::swap(a&: A, b&: B);
2451 if (!match(V: A, P: ShiftAdd))
2452 std::swap(a&: A, b&: C);
2453 Value *Low;
2454 if (!match(V: A, P: m_LShr(L: m_OneUse(SubPattern: m_Value(V&: Low)), R: m_SpecificInt(V: BitWidth / 2))))
2455 return false;
2456
2457 // Match B == XhYl>>32 and C == XlYh>>32
2458 Value *XhYl, *XlYh;
2459 if (!match(V: B, P: m_LShr(L: m_Value(V&: XhYl), R: m_SpecificInt(V: BitWidth / 2))) ||
2460 !match(V: C, P: m_LShr(L: m_Value(V&: XlYh), R: m_SpecificInt(V: BitWidth / 2))))
2461 return false;
2462 if (!CheckHiLo(XhYl, X, Y))
2463 std::swap(a&: XhYl, b&: XlYh);
2464 if (!CheckHiLo(XhYl, X, Y) || XhYl->hasNUsesOrMore(N: 3))
2465 return false;
2466 if (!CheckHiLo(XlYh, Y, X) || XlYh->hasNUsesOrMore(N: 3))
2467 return false;
2468
2469 // Match Low as XlYl>>32 + XhYl&0xffffffff + XlYh&0xffffffff
2470 Value *XlYl;
2471 if (!match(
2472 V: Low,
2473 P: m_c_Add(
2474 L: m_OneUse(SubPattern: m_c_Add(
2475 L: m_OneUse(SubPattern: m_And(L: m_Specific(V: XhYl), R: m_SpecificInt(V: LowMask))),
2476 R: m_OneUse(SubPattern: m_And(L: m_Specific(V: XlYh), R: m_SpecificInt(V: LowMask))))),
2477 R: m_OneUse(
2478 SubPattern: m_LShr(L: m_Value(V&: XlYl), R: m_SpecificInt(V: BitWidth / 2))))) &&
2479 !match(
2480 V: Low,
2481 P: m_c_Add(
2482 L: m_OneUse(SubPattern: m_c_Add(
2483 L: m_OneUse(SubPattern: m_And(L: m_Specific(V: XhYl), R: m_SpecificInt(V: LowMask))),
2484 R: m_OneUse(
2485 SubPattern: m_LShr(L: m_Value(V&: XlYl), R: m_SpecificInt(V: BitWidth / 2))))),
2486 R: m_OneUse(SubPattern: m_And(L: m_Specific(V: XlYh), R: m_SpecificInt(V: LowMask))))) &&
2487 !match(
2488 V: Low,
2489 P: m_c_Add(
2490 L: m_OneUse(SubPattern: m_c_Add(
2491 L: m_OneUse(SubPattern: m_And(L: m_Specific(V: XlYh), R: m_SpecificInt(V: LowMask))),
2492 R: m_OneUse(
2493 SubPattern: m_LShr(L: m_Value(V&: XlYl), R: m_SpecificInt(V: BitWidth / 2))))),
2494 R: m_OneUse(SubPattern: m_And(L: m_Specific(V: XhYl), R: m_SpecificInt(V: LowMask))))))
2495 return false;
2496 if (!CheckLoLo(XlYl, X, Y))
2497 return false;
2498
2499 return CreateMulHigh(X, Y);
2500 };
2501
2502 auto FoldMulHighCarry4 = [&](Value *X, Value *Y, Instruction *Carry,
2503 Instruction *B, Instruction *C) {
2504 // xh*yh + carry + crosssum>>32 + (xl*yl + crosssum&0xffffffff) >> 32
2505 // crosssum = xh*yl+xl*yh
2506 // carry = crosssum < xh*yl ? 0x1000000 : 0
2507 if (Carry->getOpcode() != Instruction::Select)
2508 std::swap(a&: Carry, b&: B);
2509 if (Carry->getOpcode() != Instruction::Select)
2510 std::swap(a&: Carry, b&: C);
2511
2512 // Carry = CrossSum < XhYl ? 0x100000000 : 0
2513 Value *CrossSum, *XhYl;
2514 if (!match(V: Carry,
2515 P: m_OneUse(SubPattern: m_Select(
2516 C: m_OneUse(SubPattern: m_SpecificICmp(MatchPred: ICmpInst::ICMP_ULT,
2517 L: m_Value(V&: CrossSum), R: m_Value(V&: XhYl))),
2518 L: m_SpecificInt(V: APInt::getOneBitSet(numBits: BitWidth, BitNo: BitWidth / 2)),
2519 R: m_Zero()))))
2520 return false;
2521
2522 if (!match(V: B, P: m_LShr(L: m_Specific(V: CrossSum), R: m_SpecificInt(V: BitWidth / 2))))
2523 std::swap(a&: B, b&: C);
2524 if (!match(V: B, P: m_LShr(L: m_Specific(V: CrossSum), R: m_SpecificInt(V: BitWidth / 2))))
2525 return false;
2526
2527 Value *XlYl, *LowAccum;
2528 if (!match(V: C, P: m_LShr(L: m_Value(V&: LowAccum), R: m_SpecificInt(V: BitWidth / 2))) ||
2529 !match(V: LowAccum, P: m_c_Add(L: m_OneUse(SubPattern: m_LShr(L: m_Value(V&: XlYl),
2530 R: m_SpecificInt(V: BitWidth / 2))),
2531 R: m_OneUse(SubPattern: m_And(L: m_Specific(V: CrossSum),
2532 R: m_SpecificInt(V: LowMask))))) ||
2533 LowAccum->hasNUsesOrMore(N: 3))
2534 return false;
2535 if (!CheckLoLo(XlYl, X, Y))
2536 return false;
2537
2538 if (!CheckHiLo(XhYl, X, Y))
2539 std::swap(a&: X, b&: Y);
2540 if (!CheckHiLo(XhYl, X, Y))
2541 return false;
2542 Value *XlYh;
2543 if (!match(V: CrossSum, P: m_c_Add(L: m_Specific(V: XhYl), R: m_OneUse(SubPattern: m_Value(V&: XlYh)))) ||
2544 !CheckHiLo(XlYh, Y, X) || CrossSum->hasNUsesOrMore(N: 4) ||
2545 XhYl->hasNUsesOrMore(N: 3))
2546 return false;
2547
2548 return CreateMulHigh(X, Y);
2549 };
2550
2551 // X and Y are the two inputs, A, B and C are other parts of the pattern
2552 // (crosssum>>32, carry, etc).
2553 Value *X, *Y;
2554 Instruction *A, *B, *C;
2555 auto HiHi = m_OneUse(SubPattern: m_Mul(L: m_LShr(L: m_Value(V&: X), R: m_SpecificInt(V: BitWidth / 2)),
2556 R: m_LShr(L: m_Value(V&: Y), R: m_SpecificInt(V: BitWidth / 2))));
2557 if ((match(V: &I, P: m_c_Add(L: HiHi, R: m_OneUse(SubPattern: m_Add(L: m_Instruction(I&: A),
2558 R: m_Instruction(I&: B))))) ||
2559 match(V: &I, P: m_c_Add(L: m_Instruction(I&: A),
2560 R: m_OneUse(SubPattern: m_c_Add(L: HiHi, R: m_Instruction(I&: B)))))) &&
2561 A->hasOneUse() && B->hasOneUse())
2562 if (FoldMulHighCarry(X, Y, A, B) || FoldMulHighLadder(X, Y, A, B))
2563 return true;
2564
2565 if ((match(V: &I, P: m_c_Add(L: HiHi, R: m_OneUse(SubPattern: m_c_Add(
2566 L: m_Instruction(I&: A),
2567 R: m_OneUse(SubPattern: m_Add(L: m_Instruction(I&: B),
2568 R: m_Instruction(I&: C))))))) ||
2569 match(V: &I, P: m_c_Add(L: m_Instruction(I&: A),
2570 R: m_OneUse(SubPattern: m_c_Add(
2571 L: HiHi, R: m_OneUse(SubPattern: m_Add(L: m_Instruction(I&: B),
2572 R: m_Instruction(I&: C))))))) ||
2573 match(V: &I, P: m_c_Add(L: m_Instruction(I&: A),
2574 R: m_OneUse(SubPattern: m_c_Add(
2575 L: m_Instruction(I&: B),
2576 R: m_OneUse(SubPattern: m_c_Add(L: HiHi, R: m_Instruction(I&: C))))))) ||
2577 match(V: &I,
2578 P: m_c_Add(L: m_OneUse(SubPattern: m_c_Add(L: HiHi, R: m_Instruction(I&: A))),
2579 R: m_OneUse(SubPattern: m_Add(L: m_Instruction(I&: B), R: m_Instruction(I&: C)))))) &&
2580 A->hasOneUse() && B->hasOneUse() && C->hasOneUse())
2581 return FoldMulHighCarry4(X, Y, A, B, C) ||
2582 FoldMulHighLadder4(X, Y, A, B, C);
2583
2584 return false;
2585}
2586
2587/// Guard a memset whose nonconstant length is known to be in [0, 1].
2588/// Inserts a conditional branch around the memset and specialises the
2589/// executed path to a one-byte store.
2590static bool foldMemSetZeroOrOneLength(Instruction &I, const DataLayout &DL,
2591 TargetLibraryInfo &TLI,
2592 AssumptionCache &AC, DominatorTree &DT,
2593 bool &MadeCFGChange) {
2594 auto *MI = dyn_cast<MemSetInst>(Val: &I);
2595 if (!MI || isa<ConstantInt>(Val: MI->getLength()))
2596 return false;
2597
2598 SimplifyQuery SQ(DL, &TLI, &DT, &AC, MI);
2599 KnownBits KnownLen = computeKnownBits(V: MI->getLength(), Q: SQ);
2600 if (!KnownLen.getMaxValue().isOne())
2601 return false;
2602
2603 uint64_t TotalCount;
2604 SmallVector<InstrProfValueData> MemsetVPMetadata = getValueProfDataFromInst(
2605 Inst: I, ValueKind: InstrProfValueKind::IPVK_MemOPSize, MaxNumValueData: 2, TotalC&: TotalCount);
2606 std::optional<uint64_t> ZeroCount = std::nullopt;
2607 std::optional<uint64_t> OneCount = std::nullopt;
2608 for (const auto [MemOpSize, SizeFrequency] : MemsetVPMetadata) {
2609 if (MemOpSize == 0)
2610 ZeroCount = SizeFrequency;
2611 else if (MemOpSize == 1)
2612 OneCount = SizeFrequency;
2613 }
2614 // If we only have one value in the profile, we assume that the other is zero.
2615 if (MemsetVPMetadata.size() == 1) {
2616 if (ZeroCount.has_value())
2617 OneCount = 0;
2618 else if (OneCount.has_value())
2619 ZeroCount = 0;
2620 }
2621
2622 BasicBlock *HeadBlock = MI->getIterator()->getParent();
2623 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
2624 IRBuilder<> B(MI);
2625 Value *IsNonZero = B.CreateIsNotNull(Arg: MI->getLength(), Name: "memset.notzero");
2626 Instruction *ThenTerm = SplitBlockAndInsertIfThen(
2627 Cond: IsNonZero, SplitBefore: MI->getIterator(), /*Unreachable=*/false,
2628 /*BranchWeights=*/nullptr, DTU: &DTU);
2629
2630 Instruction &IsNonZeroBranch = *HeadBlock->getTerminator();
2631 if (!ProfcheckDisableMetadataFixes && OneCount.has_value() &&
2632 ZeroCount.has_value() && (*OneCount + *ZeroCount > 0))
2633 setFittedBranchWeights(I&: IsNonZeroBranch, Weights: {*OneCount, *ZeroCount}, IsExpected: false);
2634 else
2635 setExplicitlyUnknownBranchWeightsIfProfiled(I&: IsNonZeroBranch, DEBUG_TYPE);
2636
2637 IRBuilder<> StoreBuilder(ThenTerm);
2638 StoreInst *Store = StoreBuilder.CreateAlignedStore(
2639 Val: MI->getValue(), Ptr: MI->getDest(), Align: MI->getDestAlign(), isVolatile: MI->isVolatile());
2640 Store->copyMetadata(SrcInst: *MI, WL: LLVMContext::MD_DIAssignID);
2641 MI->eraseFromParent();
2642 ++NumMemSetsGuarded;
2643 MadeCFGChange = true;
2644 return true;
2645}
2646
2647/// This is the entry point for folds that could be implemented in regular
2648/// InstCombine, but they are separated because they are not expected to
2649/// occur frequently and/or have more than a constant-length pattern match.
2650static bool foldUnusualPatterns(Function &F, DominatorTree &DT,
2651 TargetTransformInfo &TTI,
2652 TargetLibraryInfo &TLI, AliasAnalysis &AA,
2653 AssumptionCache &AC, bool &MadeCFGChange) {
2654 bool MadeChange = false;
2655 for (BasicBlock &BB : F) {
2656 // Ignore unreachable basic blocks.
2657 if (!DT.isReachableFromEntry(A: &BB))
2658 continue;
2659
2660 const DataLayout &DL = F.getDataLayout();
2661
2662 // Walk the block backwards for efficiency. We're matching a chain of
2663 // use->defs, so we're more likely to succeed by starting from the bottom.
2664 // Also, we want to avoid matching partial patterns.
2665 // TODO: It would be more efficient if we removed dead instructions
2666 // iteratively in this loop rather than waiting until the end.
2667 for (Instruction &I : make_early_inc_range(Range: llvm::reverse(C&: BB))) {
2668 MadeChange |= foldAnyOrAllBitsSet(I);
2669 MadeChange |= foldGuardedFunnelShift(I, DT);
2670 MadeChange |= foldSelectSplitCTLZCTTZ(I);
2671 MadeChange |= tryToRecognizePopCount(I);
2672 MadeChange |= tryToRecognizePopCount1(I);
2673 MadeChange |= tryToRecognizePopCount2n3(I);
2674 MadeChange |= tryToFPToSat(I, TTI);
2675 MadeChange |= tryToRecognizeTableBasedPatterns(I, DL, TTI);
2676 MadeChange |= foldConsecutiveLoads(I, DL, TTI, AA, DT);
2677 MadeChange |= foldPatternedLoads(I, DL);
2678 MadeChange |= foldICmpOrChain(I, DL, TTI, AA, DT);
2679 MadeChange |= foldMulHigh(I);
2680 // These folds can erase the instruction `I`, so they need to be called
2681 // at the end of this sequence.
2682 if (foldLibCalls(I, TTI, TLI, AC, DT, DL, MadeCFGChange)) {
2683 MadeChange = true;
2684 continue;
2685 }
2686 if (foldMemSetZeroOrOneLength(I, DL, TLI, AC, DT, MadeCFGChange))
2687 MadeChange = true;
2688 }
2689
2690 // Do this separately to avoid redundantly scanning stores multiple times.
2691 MadeChange |= foldConsecutiveStores(BB, DL, TTI, AA);
2692 }
2693
2694 // We're done with transforms, so remove dead instructions.
2695 if (MadeChange)
2696 for (BasicBlock &BB : F)
2697 SimplifyInstructionsInBlock(BB: &BB);
2698
2699 return MadeChange;
2700}
2701
2702/// This is the entry point for all transforms. Pass manager differences are
2703/// handled in the callers of this function.
2704static bool runImpl(Function &F, AssumptionCache &AC, TargetTransformInfo &TTI,
2705 TargetLibraryInfo &TLI, DominatorTree &DT,
2706 AliasAnalysis &AA, bool &MadeCFGChange) {
2707 bool MadeChange = false;
2708 const DataLayout &DL = F.getDataLayout();
2709 TruncInstCombine TIC(AC, TLI, DL, DT);
2710 MadeChange |= TIC.run(F);
2711 MadeChange |= foldUnusualPatterns(F, DT, TTI, TLI, AA, AC, MadeCFGChange);
2712 return MadeChange;
2713}
2714
2715PreservedAnalyses AggressiveInstCombinePass::run(Function &F,
2716 FunctionAnalysisManager &AM) {
2717 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
2718 auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F);
2719 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
2720 auto &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
2721 auto &AA = AM.getResult<AAManager>(IR&: F);
2722 bool MadeCFGChange = false;
2723 if (!runImpl(F, AC, TTI, TLI, DT, AA, MadeCFGChange)) {
2724 // No changes, all analyses are preserved.
2725 return PreservedAnalyses::all();
2726 }
2727 // Mark all the analyses that instcombine updates as preserved.
2728 PreservedAnalyses PA;
2729 if (MadeCFGChange)
2730 PA.preserve<DominatorTreeAnalysis>();
2731 else
2732 PA.preserveSet<CFGAnalyses>();
2733 return PA;
2734}
2735