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