1881 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the aggressive expression pattern combiner classes.10// Currently, it handles expression patterns for:11// * Truncate instruction12//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/MDBuilder.h"33#include "llvm/IR/PatternMatch.h"34#include "llvm/IR/ProfDataUtils.h"35#include "llvm/Support/Casting.h"36#include "llvm/Support/CommandLine.h"37#include "llvm/Transforms/Utils/BasicBlockUtils.h"38#include "llvm/Transforms/Utils/BuildLibCalls.h"39#include "llvm/Transforms/Utils/Local.h"40 41using namespace llvm;42using namespace PatternMatch;43 44#define DEBUG_TYPE "aggressive-instcombine"45 46namespace llvm {47extern cl::opt<bool> ProfcheckDisableMetadataFixes;48}49 50STATISTIC(NumAnyOrAllBitsSet, "Number of any/all-bits-set patterns folded");51STATISTIC(NumGuardedRotates,52 "Number of guarded rotates transformed into funnel shifts");53STATISTIC(NumGuardedFunnelShifts,54 "Number of guarded funnel shifts transformed into funnel shifts");55STATISTIC(NumPopCountRecognized, "Number of popcount idioms recognized");56 57static cl::opt<unsigned> MaxInstrsToScan(58 "aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden,59 cl::desc("Max number of instructions to scan for aggressive instcombine."));60 61static cl::opt<unsigned> StrNCmpInlineThreshold(62 "strncmp-inline-threshold", cl::init(3), cl::Hidden,63 cl::desc("The maximum length of a constant string for a builtin string cmp "64 "call eligible for inlining. The default value is 3."));65 66static cl::opt<unsigned>67 MemChrInlineThreshold("memchr-inline-threshold", cl::init(3), cl::Hidden,68 cl::desc("The maximum length of a constant string to "69 "inline a memchr call."));70 71/// Match a pattern for a bitwise funnel/rotate operation that partially guards72/// against undefined behavior by branching around the funnel-shift/rotation73/// when the shift amount is 0.74static bool foldGuardedFunnelShift(Instruction &I, const DominatorTree &DT) {75 if (I.getOpcode() != Instruction::PHI || I.getNumOperands() != 2)76 return false;77 78 // As with the one-use checks below, this is not strictly necessary, but we79 // are being cautious to avoid potential perf regressions on targets that80 // do not actually have a funnel/rotate instruction (where the funnel shift81 // would be expanded back into math/shift/logic ops).82 if (!isPowerOf2_32(I.getType()->getScalarSizeInBits()))83 return false;84 85 // Match V to funnel shift left/right and capture the source operands and86 // shift amount.87 auto matchFunnelShift = [](Value *V, Value *&ShVal0, Value *&ShVal1,88 Value *&ShAmt) {89 unsigned Width = V->getType()->getScalarSizeInBits();90 91 // fshl(ShVal0, ShVal1, ShAmt)92 // == (ShVal0 << ShAmt) | (ShVal1 >> (Width -ShAmt))93 if (match(V, m_OneUse(m_c_Or(94 m_Shl(m_Value(ShVal0), m_Value(ShAmt)),95 m_LShr(m_Value(ShVal1), m_Sub(m_SpecificInt(Width),96 m_Deferred(ShAmt))))))) {97 return Intrinsic::fshl;98 }99 100 // fshr(ShVal0, ShVal1, ShAmt)101 // == (ShVal0 >> ShAmt) | (ShVal1 << (Width - ShAmt))102 if (match(V,103 m_OneUse(m_c_Or(m_Shl(m_Value(ShVal0), m_Sub(m_SpecificInt(Width),104 m_Value(ShAmt))),105 m_LShr(m_Value(ShVal1), m_Deferred(ShAmt)))))) {106 return Intrinsic::fshr;107 }108 109 return Intrinsic::not_intrinsic;110 };111 112 // One phi operand must be a funnel/rotate operation, and the other phi113 // operand must be the source value of that funnel/rotate operation:114 // phi [ rotate(RotSrc, ShAmt), FunnelBB ], [ RotSrc, GuardBB ]115 // phi [ fshl(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal0, GuardBB ]116 // phi [ fshr(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal1, GuardBB ]117 PHINode &Phi = cast<PHINode>(I);118 unsigned FunnelOp = 0, GuardOp = 1;119 Value *P0 = Phi.getOperand(0), *P1 = Phi.getOperand(1);120 Value *ShVal0, *ShVal1, *ShAmt;121 Intrinsic::ID IID = matchFunnelShift(P0, ShVal0, ShVal1, ShAmt);122 if (IID == Intrinsic::not_intrinsic ||123 (IID == Intrinsic::fshl && ShVal0 != P1) ||124 (IID == Intrinsic::fshr && ShVal1 != P1)) {125 IID = matchFunnelShift(P1, ShVal0, ShVal1, ShAmt);126 if (IID == Intrinsic::not_intrinsic ||127 (IID == Intrinsic::fshl && ShVal0 != P0) ||128 (IID == Intrinsic::fshr && ShVal1 != P0))129 return false;130 assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&131 "Pattern must match funnel shift left or right");132 std::swap(FunnelOp, GuardOp);133 }134 135 // The incoming block with our source operand must be the "guard" block.136 // That must contain a cmp+branch to avoid the funnel/rotate when the shift137 // amount is equal to 0. The other incoming block is the block with the138 // funnel/rotate.139 BasicBlock *GuardBB = Phi.getIncomingBlock(GuardOp);140 BasicBlock *FunnelBB = Phi.getIncomingBlock(FunnelOp);141 Instruction *TermI = GuardBB->getTerminator();142 143 // Ensure that the shift values dominate each block.144 if (!DT.dominates(ShVal0, TermI) || !DT.dominates(ShVal1, TermI))145 return false;146 147 BasicBlock *PhiBB = Phi.getParent();148 if (!match(TermI, m_Br(m_SpecificICmp(CmpInst::ICMP_EQ, m_Specific(ShAmt),149 m_ZeroInt()),150 m_SpecificBB(PhiBB), m_SpecificBB(FunnelBB))))151 return false;152 153 IRBuilder<> Builder(PhiBB, PhiBB->getFirstInsertionPt());154 155 if (ShVal0 == ShVal1)156 ++NumGuardedRotates;157 else158 ++NumGuardedFunnelShifts;159 160 // If this is not a rotate then the select was blocking poison from the161 // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.162 bool IsFshl = IID == Intrinsic::fshl;163 if (ShVal0 != ShVal1) {164 if (IsFshl && !llvm::isGuaranteedNotToBePoison(ShVal1))165 ShVal1 = Builder.CreateFreeze(ShVal1);166 else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(ShVal0))167 ShVal0 = Builder.CreateFreeze(ShVal0);168 }169 170 // We matched a variation of this IR pattern:171 // GuardBB:172 // %cmp = icmp eq i32 %ShAmt, 0173 // br i1 %cmp, label %PhiBB, label %FunnelBB174 // FunnelBB:175 // %sub = sub i32 32, %ShAmt176 // %shr = lshr i32 %ShVal1, %sub177 // %shl = shl i32 %ShVal0, %ShAmt178 // %fsh = or i32 %shr, %shl179 // br label %PhiBB180 // PhiBB:181 // %cond = phi i32 [ %fsh, %FunnelBB ], [ %ShVal0, %GuardBB ]182 // -->183 // llvm.fshl.i32(i32 %ShVal0, i32 %ShVal1, i32 %ShAmt)184 Phi.replaceAllUsesWith(185 Builder.CreateIntrinsic(IID, Phi.getType(), {ShVal0, ShVal1, ShAmt}));186 return true;187}188 189/// This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and190/// the bit indexes (Mask) needed by a masked compare. If we're matching a chain191/// of 'and' ops, then we also need to capture the fact that we saw an192/// "and X, 1", so that's an extra return value for that case.193namespace {194struct MaskOps {195 Value *Root = nullptr;196 APInt Mask;197 bool MatchAndChain;198 bool FoundAnd1 = false;199 200 MaskOps(unsigned BitWidth, bool MatchAnds)201 : Mask(APInt::getZero(BitWidth)), MatchAndChain(MatchAnds) {}202};203} // namespace204 205/// This is a recursive helper for foldAnyOrAllBitsSet() that walks through a206/// chain of 'and' or 'or' instructions looking for shift ops of a common source207/// value. Examples:208/// or (or (or X, (X >> 3)), (X >> 5)), (X >> 8)209/// returns { X, 0x129 }210/// and (and (X >> 1), 1), (X >> 4)211/// returns { X, 0x12 }212static bool matchAndOrChain(Value *V, MaskOps &MOps) {213 Value *Op0, *Op1;214 if (MOps.MatchAndChain) {215 // Recurse through a chain of 'and' operands. This requires an extra check216 // vs. the 'or' matcher: we must find an "and X, 1" instruction somewhere217 // in the chain to know that all of the high bits are cleared.218 if (match(V, m_And(m_Value(Op0), m_One()))) {219 MOps.FoundAnd1 = true;220 return matchAndOrChain(Op0, MOps);221 }222 if (match(V, m_And(m_Value(Op0), m_Value(Op1))))223 return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);224 } else {225 // Recurse through a chain of 'or' operands.226 if (match(V, m_Or(m_Value(Op0), m_Value(Op1))))227 return matchAndOrChain(Op0, MOps) && matchAndOrChain(Op1, MOps);228 }229 230 // We need a shift-right or a bare value representing a compare of bit 0 of231 // the original source operand.232 Value *Candidate;233 const APInt *BitIndex = nullptr;234 if (!match(V, m_LShr(m_Value(Candidate), m_APInt(BitIndex))))235 Candidate = V;236 237 // Initialize result source operand.238 if (!MOps.Root)239 MOps.Root = Candidate;240 241 // The shift constant is out-of-range? This code hasn't been simplified.242 if (BitIndex && BitIndex->uge(MOps.Mask.getBitWidth()))243 return false;244 245 // Fill in the mask bit derived from the shift constant.246 MOps.Mask.setBit(BitIndex ? BitIndex->getZExtValue() : 0);247 return MOps.Root == Candidate;248}249 250/// Match patterns that correspond to "any-bits-set" and "all-bits-set".251/// These will include a chain of 'or' or 'and'-shifted bits from a252/// common source value:253/// and (or (lshr X, C), ...), 1 --> (X & CMask) != 0254/// and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask255/// Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns256/// that differ only with a final 'not' of the result. We expect that final257/// 'not' to be folded with the compare that we create here (invert predicate).258static bool foldAnyOrAllBitsSet(Instruction &I) {259 // The 'any-bits-set' ('or' chain) pattern is simpler to match because the260 // final "and X, 1" instruction must be the final op in the sequence.261 bool MatchAllBitsSet;262 if (match(&I, m_c_And(m_OneUse(m_And(m_Value(), m_Value())), m_Value())))263 MatchAllBitsSet = true;264 else if (match(&I, m_And(m_OneUse(m_Or(m_Value(), m_Value())), m_One())))265 MatchAllBitsSet = false;266 else267 return false;268 269 MaskOps MOps(I.getType()->getScalarSizeInBits(), MatchAllBitsSet);270 if (MatchAllBitsSet) {271 if (!matchAndOrChain(cast<BinaryOperator>(&I), MOps) || !MOps.FoundAnd1)272 return false;273 } else {274 if (!matchAndOrChain(cast<BinaryOperator>(&I)->getOperand(0), MOps))275 return false;276 }277 278 // The pattern was found. Create a masked compare that replaces all of the279 // shift and logic ops.280 IRBuilder<> Builder(&I);281 Constant *Mask = ConstantInt::get(I.getType(), MOps.Mask);282 Value *And = Builder.CreateAnd(MOps.Root, Mask);283 Value *Cmp = MatchAllBitsSet ? Builder.CreateICmpEQ(And, Mask)284 : Builder.CreateIsNotNull(And);285 Value *Zext = Builder.CreateZExt(Cmp, I.getType());286 I.replaceAllUsesWith(Zext);287 ++NumAnyOrAllBitsSet;288 return true;289}290 291// Try to recognize below function as popcount intrinsic.292// This is the "best" algorithm from293// http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel294// Also used in TargetLowering::expandCTPOP().295//296// int popcount(unsigned int i) {297// i = i - ((i >> 1) & 0x55555555);298// i = (i & 0x33333333) + ((i >> 2) & 0x33333333);299// i = ((i + (i >> 4)) & 0x0F0F0F0F);300// return (i * 0x01010101) >> 24;301// }302static bool tryToRecognizePopCount(Instruction &I) {303 if (I.getOpcode() != Instruction::LShr)304 return false;305 306 Type *Ty = I.getType();307 if (!Ty->isIntOrIntVectorTy())308 return false;309 310 unsigned Len = Ty->getScalarSizeInBits();311 // FIXME: fix Len == 8 and other irregular type lengths.312 if (!(Len <= 128 && Len > 8 && Len % 8 == 0))313 return false;314 315 APInt Mask55 = APInt::getSplat(Len, APInt(8, 0x55));316 APInt Mask33 = APInt::getSplat(Len, APInt(8, 0x33));317 APInt Mask0F = APInt::getSplat(Len, APInt(8, 0x0F));318 APInt Mask01 = APInt::getSplat(Len, APInt(8, 0x01));319 APInt MaskShift = APInt(Len, Len - 8);320 321 Value *Op0 = I.getOperand(0);322 Value *Op1 = I.getOperand(1);323 Value *MulOp0;324 // Matching "(i * 0x01010101...) >> 24".325 if ((match(Op0, m_Mul(m_Value(MulOp0), m_SpecificInt(Mask01)))) &&326 match(Op1, m_SpecificInt(MaskShift))) {327 Value *ShiftOp0;328 // Matching "((i + (i >> 4)) & 0x0F0F0F0F...)".329 if (match(MulOp0, m_And(m_c_Add(m_LShr(m_Value(ShiftOp0), m_SpecificInt(4)),330 m_Deferred(ShiftOp0)),331 m_SpecificInt(Mask0F)))) {332 Value *AndOp0;333 // Matching "(i & 0x33333333...) + ((i >> 2) & 0x33333333...)".334 if (match(ShiftOp0,335 m_c_Add(m_And(m_Value(AndOp0), m_SpecificInt(Mask33)),336 m_And(m_LShr(m_Deferred(AndOp0), m_SpecificInt(2)),337 m_SpecificInt(Mask33))))) {338 Value *Root, *SubOp1;339 // Matching "i - ((i >> 1) & 0x55555555...)".340 const APInt *AndMask;341 if (match(AndOp0, m_Sub(m_Value(Root), m_Value(SubOp1))) &&342 match(SubOp1, m_And(m_LShr(m_Specific(Root), m_SpecificInt(1)),343 m_APInt(AndMask)))) {344 auto CheckAndMask = [&]() {345 if (*AndMask == Mask55)346 return true;347 348 // Exact match failed, see if any bits are known to be 0 where we349 // expect a 1 in the mask.350 if (!AndMask->isSubsetOf(Mask55))351 return false;352 353 APInt NeededMask = Mask55 & ~*AndMask;354 return MaskedValueIsZero(cast<Instruction>(SubOp1)->getOperand(0),355 NeededMask,356 SimplifyQuery(I.getDataLayout()));357 };358 359 if (CheckAndMask()) {360 LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");361 IRBuilder<> Builder(&I);362 I.replaceAllUsesWith(363 Builder.CreateIntrinsic(Intrinsic::ctpop, I.getType(), {Root}));364 ++NumPopCountRecognized;365 return true;366 }367 }368 }369 }370 }371 372 return false;373}374 375/// Fold smin(smax(fptosi(x), C1), C2) to llvm.fptosi.sat(x), providing C1 and376/// C2 saturate the value of the fp conversion. The transform is not reversable377/// as the fptosi.sat is more defined than the input - all values produce a378/// valid value for the fptosi.sat, where as some produce poison for original379/// that were out of range of the integer conversion. The reversed pattern may380/// use fmax and fmin instead. As we cannot directly reverse the transform, and381/// it is not always profitable, we make it conditional on the cost being382/// reported as lower by TTI.383static bool tryToFPToSat(Instruction &I, TargetTransformInfo &TTI) {384 // Look for min(max(fptosi, converting to fptosi_sat.385 Value *In;386 const APInt *MinC, *MaxC;387 if (!match(&I, m_SMax(m_OneUse(m_SMin(m_OneUse(m_FPToSI(m_Value(In))),388 m_APInt(MinC))),389 m_APInt(MaxC))) &&390 !match(&I, m_SMin(m_OneUse(m_SMax(m_OneUse(m_FPToSI(m_Value(In))),391 m_APInt(MaxC))),392 m_APInt(MinC))))393 return false;394 395 // Check that the constants clamp a saturate.396 if (!(*MinC + 1).isPowerOf2() || -*MaxC != *MinC + 1)397 return false;398 399 Type *IntTy = I.getType();400 Type *FpTy = In->getType();401 Type *SatTy =402 IntegerType::get(IntTy->getContext(), (*MinC + 1).exactLogBase2() + 1);403 if (auto *VecTy = dyn_cast<VectorType>(IntTy))404 SatTy = VectorType::get(SatTy, VecTy->getElementCount());405 406 // Get the cost of the intrinsic, and check that against the cost of407 // fptosi+smin+smax408 InstructionCost SatCost = TTI.getIntrinsicInstrCost(409 IntrinsicCostAttributes(Intrinsic::fptosi_sat, SatTy, {In}, {FpTy}),410 TTI::TCK_RecipThroughput);411 SatCost += TTI.getCastInstrCost(Instruction::SExt, IntTy, SatTy,412 TTI::CastContextHint::None,413 TTI::TCK_RecipThroughput);414 415 InstructionCost MinMaxCost = TTI.getCastInstrCost(416 Instruction::FPToSI, IntTy, FpTy, TTI::CastContextHint::None,417 TTI::TCK_RecipThroughput);418 MinMaxCost += TTI.getIntrinsicInstrCost(419 IntrinsicCostAttributes(Intrinsic::smin, IntTy, {IntTy}),420 TTI::TCK_RecipThroughput);421 MinMaxCost += TTI.getIntrinsicInstrCost(422 IntrinsicCostAttributes(Intrinsic::smax, IntTy, {IntTy}),423 TTI::TCK_RecipThroughput);424 425 if (SatCost >= MinMaxCost)426 return false;427 428 IRBuilder<> Builder(&I);429 Value *Sat =430 Builder.CreateIntrinsic(Intrinsic::fptosi_sat, {SatTy, FpTy}, In);431 I.replaceAllUsesWith(Builder.CreateSExt(Sat, IntTy));432 return true;433}434 435/// Try to replace a mathlib call to sqrt with the LLVM intrinsic. This avoids436/// pessimistic codegen that has to account for setting errno and can enable437/// vectorization.438static bool foldSqrt(CallInst *Call, LibFunc Func, TargetTransformInfo &TTI,439 TargetLibraryInfo &TLI, AssumptionCache &AC,440 DominatorTree &DT) {441 // If (1) this is a sqrt libcall, (2) we can assume that NAN is not created442 // (because NNAN or the operand arg must not be less than -0.0) and (2) we443 // would not end up lowering to a libcall anyway (which could change the value444 // of errno), then:445 // (1) errno won't be set.446 // (2) it is safe to convert this to an intrinsic call.447 Type *Ty = Call->getType();448 Value *Arg = Call->getArgOperand(0);449 if (TTI.haveFastSqrt(Ty) &&450 (Call->hasNoNaNs() ||451 cannotBeOrderedLessThanZero(452 Arg, SimplifyQuery(Call->getDataLayout(), &TLI, &DT, &AC, Call)))) {453 IRBuilder<> Builder(Call);454 Value *NewSqrt =455 Builder.CreateIntrinsic(Intrinsic::sqrt, Ty, Arg, Call, "sqrt");456 Call->replaceAllUsesWith(NewSqrt);457 458 // Explicitly erase the old call because a call with side effects is not459 // trivially dead.460 Call->eraseFromParent();461 return true;462 }463 464 return false;465}466 467// Check if this array of constants represents a cttz table.468// Iterate over the elements from \p Table by trying to find/match all469// the numbers from 0 to \p InputBits that should represent cttz results.470static bool isCTTZTable(Constant *Table, const APInt &Mul, const APInt &Shift,471 const APInt &AndMask, Type *AccessTy,472 unsigned InputBits, const APInt &GEPIdxFactor,473 const DataLayout &DL) {474 for (unsigned Idx = 0; Idx < InputBits; Idx++) {475 APInt Index = (APInt(InputBits, 1).shl(Idx) * Mul).lshr(Shift) & AndMask;476 ConstantInt *C = dyn_cast_or_null<ConstantInt>(477 ConstantFoldLoadFromConst(Table, AccessTy, Index * GEPIdxFactor, DL));478 if (!C || C->getValue() != Idx)479 return false;480 }481 482 return true;483}484 485// Try to recognize table-based ctz implementation.486// E.g., an example in C (for more cases please see the llvm/tests):487// int f(unsigned x) {488// static const char table[32] =489// {0, 1, 28, 2, 29, 14, 24, 3, 30,490// 22, 20, 15, 25, 17, 4, 8, 31, 27,491// 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};492// return table[((unsigned)((x & -x) * 0x077CB531U)) >> 27];493// }494// this can be lowered to `cttz` instruction.495// There is also a special case when the element is 0.496//497// The (x & -x) sets the lowest non-zero bit to 1. The multiply is a de-bruijn498// sequence that contains each pattern of bits in it. The shift extracts499// the top bits after the multiply, and that index into the table should500// represent the number of trailing zeros in the original number.501//502// Here are some examples or LLVM IR for a 64-bit target:503//504// CASE 1:505// %sub = sub i32 0, %x506// %and = and i32 %sub, %x507// %mul = mul i32 %and, 125613361508// %shr = lshr i32 %mul, 27509// %idxprom = zext i32 %shr to i64510// %arrayidx = getelementptr inbounds [32 x i8], [32 x i8]* @ctz1.table, i64 0,511// i64 %idxprom512// %0 = load i8, i8* %arrayidx, align 1, !tbaa !8513//514// CASE 2:515// %sub = sub i32 0, %x516// %and = and i32 %sub, %x517// %mul = mul i32 %and, 72416175518// %shr = lshr i32 %mul, 26519// %idxprom = zext i32 %shr to i64520// %arrayidx = getelementptr inbounds [64 x i16], [64 x i16]* @ctz2.table,521// i64 0, i64 %idxprom522// %0 = load i16, i16* %arrayidx, align 2, !tbaa !8523//524// CASE 3:525// %sub = sub i32 0, %x526// %and = and i32 %sub, %x527// %mul = mul i32 %and, 81224991528// %shr = lshr i32 %mul, 27529// %idxprom = zext i32 %shr to i64530// %arrayidx = getelementptr inbounds [32 x i32], [32 x i32]* @ctz3.table,531// i64 0, i64 %idxprom532// %0 = load i32, i32* %arrayidx, align 4, !tbaa !8533//534// CASE 4:535// %sub = sub i64 0, %x536// %and = and i64 %sub, %x537// %mul = mul i64 %and, 283881067100198605538// %shr = lshr i64 %mul, 58539// %arrayidx = getelementptr inbounds [64 x i8], [64 x i8]* @table, i64 0,540// i64 %shr541// %0 = load i8, i8* %arrayidx, align 1, !tbaa !8542//543// All these can be lowered to @llvm.cttz.i32/64 intrinsics.544static bool tryToRecognizeTableBasedCttz(Instruction &I, const DataLayout &DL) {545 LoadInst *LI = dyn_cast<LoadInst>(&I);546 if (!LI)547 return false;548 549 Type *AccessType = LI->getType();550 if (!AccessType->isIntegerTy())551 return false;552 553 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getPointerOperand());554 if (!GEP || !GEP->hasNoUnsignedSignedWrap())555 return false;556 557 GlobalVariable *GVTable = dyn_cast<GlobalVariable>(GEP->getPointerOperand());558 if (!GVTable || !GVTable->hasInitializer() || !GVTable->isConstant())559 return false;560 561 unsigned BW = DL.getIndexTypeSizeInBits(GEP->getType());562 APInt ModOffset(BW, 0);563 SmallMapVector<Value *, APInt, 4> VarOffsets;564 if (!GEP->collectOffset(DL, BW, VarOffsets, ModOffset) ||565 VarOffsets.size() != 1 || ModOffset != 0)566 return false;567 auto [GepIdx, GEPScale] = VarOffsets.front();568 569 Value *X1;570 const APInt *MulConst, *ShiftConst, *AndCst = nullptr;571 // Check that the gep variable index is ((x & -x) * MulConst) >> ShiftConst.572 // This might be extended to the pointer index type, and if the gep index type573 // has been replaced with an i8 then a new And (and different ShiftConst) will574 // be present.575 auto MatchInner = m_LShr(576 m_Mul(m_c_And(m_Neg(m_Value(X1)), m_Deferred(X1)), m_APInt(MulConst)),577 m_APInt(ShiftConst));578 if (!match(GepIdx, m_CastOrSelf(MatchInner)) &&579 !match(GepIdx, m_CastOrSelf(m_And(MatchInner, m_APInt(AndCst)))))580 return false;581 582 unsigned InputBits = X1->getType()->getScalarSizeInBits();583 if (InputBits != 16 && InputBits != 32 && InputBits != 64 && InputBits != 128)584 return false;585 586 if (!GEPScale.isIntN(InputBits) ||587 !isCTTZTable(GVTable->getInitializer(), *MulConst, *ShiftConst,588 AndCst ? *AndCst : APInt::getAllOnes(InputBits), AccessType,589 InputBits, GEPScale.zextOrTrunc(InputBits), DL))590 return false;591 592 ConstantInt *ZeroTableElem = cast<ConstantInt>(593 ConstantFoldLoadFromConst(GVTable->getInitializer(), AccessType, DL));594 bool DefinedForZero = ZeroTableElem->getZExtValue() == InputBits;595 596 IRBuilder<> B(LI);597 ConstantInt *BoolConst = B.getInt1(!DefinedForZero);598 Type *XType = X1->getType();599 auto Cttz = B.CreateIntrinsic(Intrinsic::cttz, {XType}, {X1, BoolConst});600 Value *ZExtOrTrunc = nullptr;601 602 if (DefinedForZero) {603 ZExtOrTrunc = B.CreateZExtOrTrunc(Cttz, AccessType);604 } else {605 // If the value in elem 0 isn't the same as InputBits, we still want to606 // produce the value from the table.607 auto Cmp = B.CreateICmpEQ(X1, ConstantInt::get(XType, 0));608 auto Select = B.CreateSelect(Cmp, B.CreateZExt(ZeroTableElem, XType), Cttz);609 610 // The true branch of select handles the cttz(0) case, which is rare.611 if (!ProfcheckDisableMetadataFixes) {612 if (Instruction *SelectI = dyn_cast<Instruction>(Select))613 SelectI->setMetadata(614 LLVMContext::MD_prof,615 MDBuilder(SelectI->getContext()).createUnlikelyBranchWeights());616 }617 618 // NOTE: If the table[0] is 0, but the cttz(0) is defined by the Target619 // it should be handled as: `cttz(x) & (typeSize - 1)`.620 621 ZExtOrTrunc = B.CreateZExtOrTrunc(Select, AccessType);622 }623 624 LI->replaceAllUsesWith(ZExtOrTrunc);625 626 return true;627}628 629/// This is used by foldLoadsRecursive() to capture a Root Load node which is630/// of type or(load, load) and recursively build the wide load. Also capture the631/// shift amount, zero extend type and loadSize.632struct LoadOps {633 LoadInst *Root = nullptr;634 LoadInst *RootInsert = nullptr;635 bool FoundRoot = false;636 uint64_t LoadSize = 0;637 uint64_t Shift = 0;638 Type *ZextType;639 AAMDNodes AATags;640};641 642// Identify and Merge consecutive loads recursively which is of the form643// (ZExt(L1) << shift1) | (ZExt(L2) << shift2) -> ZExt(L3) << shift1644// (ZExt(L1) << shift1) | ZExt(L2) -> ZExt(L3)645static bool foldLoadsRecursive(Value *V, LoadOps &LOps, const DataLayout &DL,646 AliasAnalysis &AA) {647 uint64_t ShAmt2;648 Value *X;649 Instruction *L1, *L2;650 651 // Go to the last node with loads.652 if (match(V,653 m_OneUse(m_c_Or(m_Value(X), m_OneUse(m_ShlOrSelf(654 m_OneUse(m_ZExt(m_Instruction(L2))),655 ShAmt2)))))) {656 if (!foldLoadsRecursive(X, LOps, DL, AA) && LOps.FoundRoot)657 // Avoid Partial chain merge.658 return false;659 } else660 return false;661 662 // Check if the pattern has loads663 LoadInst *LI1 = LOps.Root;664 uint64_t ShAmt1 = LOps.Shift;665 if (LOps.FoundRoot == false &&666 match(X, m_OneUse(667 m_ShlOrSelf(m_OneUse(m_ZExt(m_Instruction(L1))), ShAmt1)))) {668 LI1 = dyn_cast<LoadInst>(L1);669 }670 LoadInst *LI2 = dyn_cast<LoadInst>(L2);671 672 // Check if loads are same, atomic, volatile and having same address space.673 if (LI1 == LI2 || !LI1 || !LI2 || !LI1->isSimple() || !LI2->isSimple() ||674 LI1->getPointerAddressSpace() != LI2->getPointerAddressSpace())675 return false;676 677 // Check if Loads come from same BB.678 if (LI1->getParent() != LI2->getParent())679 return false;680 681 // Find the data layout682 bool IsBigEndian = DL.isBigEndian();683 684 // Check if loads are consecutive and same size.685 Value *Load1Ptr = LI1->getPointerOperand();686 APInt Offset1(DL.getIndexTypeSizeInBits(Load1Ptr->getType()), 0);687 Load1Ptr =688 Load1Ptr->stripAndAccumulateConstantOffsets(DL, Offset1,689 /* AllowNonInbounds */ true);690 691 Value *Load2Ptr = LI2->getPointerOperand();692 APInt Offset2(DL.getIndexTypeSizeInBits(Load2Ptr->getType()), 0);693 Load2Ptr =694 Load2Ptr->stripAndAccumulateConstantOffsets(DL, Offset2,695 /* AllowNonInbounds */ true);696 697 // Verify if both loads have same base pointers698 uint64_t LoadSize1 = LI1->getType()->getPrimitiveSizeInBits();699 uint64_t LoadSize2 = LI2->getType()->getPrimitiveSizeInBits();700 if (Load1Ptr != Load2Ptr)701 return false;702 703 // Make sure that there are no padding bits.704 if (!DL.typeSizeEqualsStoreSize(LI1->getType()) ||705 !DL.typeSizeEqualsStoreSize(LI2->getType()))706 return false;707 708 // Alias Analysis to check for stores b/w the loads.709 LoadInst *Start = LOps.FoundRoot ? LOps.RootInsert : LI1, *End = LI2;710 MemoryLocation Loc;711 if (!Start->comesBefore(End)) {712 std::swap(Start, End);713 // If LOps.RootInsert comes after LI2, since we use LI2 as the new insert714 // point, we should make sure whether the memory region accessed by LOps715 // isn't modified.716 if (LOps.FoundRoot)717 Loc = MemoryLocation(718 LOps.Root->getPointerOperand(),719 LocationSize::precise(DL.getTypeStoreSize(720 IntegerType::get(LI1->getContext(), LOps.LoadSize))),721 LOps.AATags);722 else723 Loc = MemoryLocation::get(End);724 } else725 Loc = MemoryLocation::get(End);726 unsigned NumScanned = 0;727 for (Instruction &Inst :728 make_range(Start->getIterator(), End->getIterator())) {729 if (Inst.mayWriteToMemory() && isModSet(AA.getModRefInfo(&Inst, Loc)))730 return false;731 732 if (++NumScanned > MaxInstrsToScan)733 return false;734 }735 736 // Make sure Load with lower Offset is at LI1737 bool Reverse = false;738 if (Offset2.slt(Offset1)) {739 std::swap(LI1, LI2);740 std::swap(ShAmt1, ShAmt2);741 std::swap(Offset1, Offset2);742 std::swap(Load1Ptr, Load2Ptr);743 std::swap(LoadSize1, LoadSize2);744 Reverse = true;745 }746 747 // Big endian swap the shifts748 if (IsBigEndian)749 std::swap(ShAmt1, ShAmt2);750 751 // First load is always LI1. This is where we put the new load.752 // Use the merged load size available from LI1 for forward loads.753 if (LOps.FoundRoot) {754 if (!Reverse)755 LoadSize1 = LOps.LoadSize;756 else757 LoadSize2 = LOps.LoadSize;758 }759 760 // Verify if shift amount and load index aligns and verifies that loads761 // are consecutive.762 uint64_t ShiftDiff = IsBigEndian ? LoadSize2 : LoadSize1;763 uint64_t PrevSize =764 DL.getTypeStoreSize(IntegerType::get(LI1->getContext(), LoadSize1));765 if ((ShAmt2 - ShAmt1) != ShiftDiff || (Offset2 - Offset1) != PrevSize)766 return false;767 768 // Update LOps769 AAMDNodes AATags1 = LOps.AATags;770 AAMDNodes AATags2 = LI2->getAAMetadata();771 if (LOps.FoundRoot == false) {772 LOps.FoundRoot = true;773 AATags1 = LI1->getAAMetadata();774 }775 LOps.LoadSize = LoadSize1 + LoadSize2;776 LOps.RootInsert = Start;777 778 // Concatenate the AATags of the Merged Loads.779 LOps.AATags = AATags1.concat(AATags2);780 781 LOps.Root = LI1;782 LOps.Shift = ShAmt1;783 LOps.ZextType = X->getType();784 return true;785}786 787// For a given BB instruction, evaluate all loads in the chain that form a788// pattern which suggests that the loads can be combined. The one and only use789// of the loads is to form a wider load.790static bool foldConsecutiveLoads(Instruction &I, const DataLayout &DL,791 TargetTransformInfo &TTI, AliasAnalysis &AA,792 const DominatorTree &DT) {793 // Only consider load chains of scalar values.794 if (isa<VectorType>(I.getType()))795 return false;796 797 LoadOps LOps;798 if (!foldLoadsRecursive(&I, LOps, DL, AA) || !LOps.FoundRoot)799 return false;800 801 IRBuilder<> Builder(&I);802 LoadInst *NewLoad = nullptr, *LI1 = LOps.Root;803 804 IntegerType *WiderType = IntegerType::get(I.getContext(), LOps.LoadSize);805 // TTI based checks if we want to proceed with wider load806 bool Allowed = TTI.isTypeLegal(WiderType);807 if (!Allowed)808 return false;809 810 unsigned AS = LI1->getPointerAddressSpace();811 unsigned Fast = 0;812 Allowed = TTI.allowsMisalignedMemoryAccesses(I.getContext(), LOps.LoadSize,813 AS, LI1->getAlign(), &Fast);814 if (!Allowed || !Fast)815 return false;816 817 // Get the Index and Ptr for the new GEP.818 Value *Load1Ptr = LI1->getPointerOperand();819 Builder.SetInsertPoint(LOps.RootInsert);820 if (!DT.dominates(Load1Ptr, LOps.RootInsert)) {821 APInt Offset1(DL.getIndexTypeSizeInBits(Load1Ptr->getType()), 0);822 Load1Ptr = Load1Ptr->stripAndAccumulateConstantOffsets(823 DL, Offset1, /* AllowNonInbounds */ true);824 Load1Ptr = Builder.CreatePtrAdd(Load1Ptr, Builder.getInt(Offset1));825 }826 // Generate wider load.827 NewLoad = Builder.CreateAlignedLoad(WiderType, Load1Ptr, LI1->getAlign(),828 LI1->isVolatile(), "");829 NewLoad->takeName(LI1);830 // Set the New Load AATags Metadata.831 if (LOps.AATags)832 NewLoad->setAAMetadata(LOps.AATags);833 834 Value *NewOp = NewLoad;835 // Check if zero extend needed.836 if (LOps.ZextType)837 NewOp = Builder.CreateZExt(NewOp, LOps.ZextType);838 839 // Check if shift needed. We need to shift with the amount of load1840 // shift if not zero.841 if (LOps.Shift)842 NewOp = Builder.CreateShl(NewOp, LOps.Shift);843 I.replaceAllUsesWith(NewOp);844 845 return true;846}847 848/// ValWidth bits starting at ValOffset of Val stored at PtrBase+PtrOffset.849struct PartStore {850 Value *PtrBase;851 APInt PtrOffset;852 Value *Val;853 uint64_t ValOffset;854 uint64_t ValWidth;855 StoreInst *Store;856 857 bool isCompatibleWith(const PartStore &Other) const {858 return PtrBase == Other.PtrBase && Val == Other.Val;859 }860 861 bool operator<(const PartStore &Other) const {862 return PtrOffset.slt(Other.PtrOffset);863 }864};865 866static std::optional<PartStore> matchPartStore(Instruction &I,867 const DataLayout &DL) {868 auto *Store = dyn_cast<StoreInst>(&I);869 if (!Store || !Store->isSimple())870 return std::nullopt;871 872 Value *StoredVal = Store->getValueOperand();873 Type *StoredTy = StoredVal->getType();874 if (!StoredTy->isIntegerTy() || !DL.typeSizeEqualsStoreSize(StoredTy))875 return std::nullopt;876 877 uint64_t ValWidth = StoredTy->getPrimitiveSizeInBits();878 uint64_t ValOffset;879 Value *Val;880 if (!match(StoredVal, m_Trunc(m_LShrOrSelf(m_Value(Val), ValOffset))))881 return std::nullopt;882 883 Value *Ptr = Store->getPointerOperand();884 APInt PtrOffset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);885 Value *PtrBase = Ptr->stripAndAccumulateConstantOffsets(886 DL, PtrOffset, /*AllowNonInbounds=*/true);887 return {{PtrBase, PtrOffset, Val, ValOffset, ValWidth, Store}};888}889 890static bool mergeConsecutivePartStores(ArrayRef<PartStore> Parts,891 unsigned Width, const DataLayout &DL,892 TargetTransformInfo &TTI) {893 if (Parts.size() < 2)894 return false;895 896 // Check whether combining the stores is profitable.897 // FIXME: We could generate smaller stores if we can't produce a large one.898 const PartStore &First = Parts.front();899 LLVMContext &Ctx = First.Store->getContext();900 Type *NewTy = Type::getIntNTy(Ctx, Width);901 unsigned Fast = 0;902 if (!TTI.isTypeLegal(NewTy) ||903 !TTI.allowsMisalignedMemoryAccesses(Ctx, Width,904 First.Store->getPointerAddressSpace(),905 First.Store->getAlign(), &Fast) ||906 !Fast)907 return false;908 909 // Generate the combined store.910 IRBuilder<> Builder(First.Store);911 Value *Val = First.Val;912 if (First.ValOffset != 0)913 Val = Builder.CreateLShr(Val, First.ValOffset);914 Val = Builder.CreateTrunc(Val, NewTy);915 StoreInst *Store = Builder.CreateAlignedStore(916 Val, First.Store->getPointerOperand(), First.Store->getAlign());917 918 // Merge various metadata onto the new store.919 AAMDNodes AATags = First.Store->getAAMetadata();920 SmallVector<Instruction *> Stores = {First.Store};921 Stores.reserve(Parts.size());922 SmallVector<DebugLoc> DbgLocs = {First.Store->getDebugLoc()};923 DbgLocs.reserve(Parts.size());924 for (const PartStore &Part : drop_begin(Parts)) {925 AATags = AATags.concat(Part.Store->getAAMetadata());926 Stores.push_back(Part.Store);927 DbgLocs.push_back(Part.Store->getDebugLoc());928 }929 Store->setAAMetadata(AATags);930 Store->mergeDIAssignID(Stores);931 Store->setDebugLoc(DebugLoc::getMergedLocations(DbgLocs));932 933 // Remove the old stores.934 for (const PartStore &Part : Parts)935 Part.Store->eraseFromParent();936 937 return true;938}939 940static bool mergePartStores(SmallVectorImpl<PartStore> &Parts,941 const DataLayout &DL, TargetTransformInfo &TTI) {942 if (Parts.size() < 2)943 return false;944 945 // We now have multiple parts of the same value stored to the same pointer.946 // Sort the parts by pointer offset, and make sure they are consistent with947 // the value offsets. Also check that the value is fully covered without948 // overlaps.949 bool Changed = false;950 llvm::sort(Parts);951 int64_t LastEndOffsetFromFirst = 0;952 const PartStore *First = &Parts[0];953 for (const PartStore &Part : Parts) {954 APInt PtrOffsetFromFirst = Part.PtrOffset - First->PtrOffset;955 int64_t ValOffsetFromFirst = Part.ValOffset - First->ValOffset;956 if (PtrOffsetFromFirst * 8 != ValOffsetFromFirst ||957 LastEndOffsetFromFirst != ValOffsetFromFirst) {958 Changed |= mergeConsecutivePartStores(ArrayRef(First, &Part),959 LastEndOffsetFromFirst, DL, TTI);960 First = &Part;961 LastEndOffsetFromFirst = Part.ValWidth;962 continue;963 }964 965 LastEndOffsetFromFirst = ValOffsetFromFirst + Part.ValWidth;966 }967 968 Changed |= mergeConsecutivePartStores(ArrayRef(First, Parts.end()),969 LastEndOffsetFromFirst, DL, TTI);970 return Changed;971}972 973static bool foldConsecutiveStores(BasicBlock &BB, const DataLayout &DL,974 TargetTransformInfo &TTI, AliasAnalysis &AA) {975 // FIXME: Add big endian support.976 if (DL.isBigEndian())977 return false;978 979 BatchAAResults BatchAA(AA);980 SmallVector<PartStore, 8> Parts;981 bool MadeChange = false;982 for (Instruction &I : make_early_inc_range(BB)) {983 if (std::optional<PartStore> Part = matchPartStore(I, DL)) {984 if (Parts.empty() || Part->isCompatibleWith(Parts[0])) {985 Parts.push_back(std::move(*Part));986 continue;987 }988 989 MadeChange |= mergePartStores(Parts, DL, TTI);990 Parts.clear();991 Parts.push_back(std::move(*Part));992 continue;993 }994 995 if (Parts.empty())996 continue;997 998 if (I.mayThrow() ||999 (I.mayReadOrWriteMemory() &&1000 isModOrRefSet(BatchAA.getModRefInfo(1001 &I, MemoryLocation::getBeforeOrAfter(Parts[0].PtrBase))))) {1002 MadeChange |= mergePartStores(Parts, DL, TTI);1003 Parts.clear();1004 continue;1005 }1006 }1007 1008 MadeChange |= mergePartStores(Parts, DL, TTI);1009 return MadeChange;1010}1011 1012/// Combine away instructions providing they are still equivalent when compared1013/// against 0. i.e do they have any bits set.1014static Value *optimizeShiftInOrChain(Value *V, IRBuilder<> &Builder) {1015 auto *I = dyn_cast<Instruction>(V);1016 if (!I || I->getOpcode() != Instruction::Or || !I->hasOneUse())1017 return nullptr;1018 1019 Value *A;1020 1021 // Look deeper into the chain of or's, combining away shl (so long as they are1022 // nuw or nsw).1023 Value *Op0 = I->getOperand(0);1024 if (match(Op0, m_CombineOr(m_NSWShl(m_Value(A), m_Value()),1025 m_NUWShl(m_Value(A), m_Value()))))1026 Op0 = A;1027 else if (auto *NOp = optimizeShiftInOrChain(Op0, Builder))1028 Op0 = NOp;1029 1030 Value *Op1 = I->getOperand(1);1031 if (match(Op1, m_CombineOr(m_NSWShl(m_Value(A), m_Value()),1032 m_NUWShl(m_Value(A), m_Value()))))1033 Op1 = A;1034 else if (auto *NOp = optimizeShiftInOrChain(Op1, Builder))1035 Op1 = NOp;1036 1037 if (Op0 != I->getOperand(0) || Op1 != I->getOperand(1))1038 return Builder.CreateOr(Op0, Op1);1039 return nullptr;1040}1041 1042static bool foldICmpOrChain(Instruction &I, const DataLayout &DL,1043 TargetTransformInfo &TTI, AliasAnalysis &AA,1044 const DominatorTree &DT) {1045 CmpPredicate Pred;1046 Value *Op0;1047 if (!match(&I, m_ICmp(Pred, m_Value(Op0), m_Zero())) ||1048 !ICmpInst::isEquality(Pred))1049 return false;1050 1051 // If the chain or or's matches a load, combine to that before attempting to1052 // remove shifts.1053 if (auto OpI = dyn_cast<Instruction>(Op0))1054 if (OpI->getOpcode() == Instruction::Or)1055 if (foldConsecutiveLoads(*OpI, DL, TTI, AA, DT))1056 return true;1057 1058 IRBuilder<> Builder(&I);1059 // icmp eq/ne or(shl(a), b), 0 -> icmp eq/ne or(a, b), 01060 if (auto *Res = optimizeShiftInOrChain(Op0, Builder)) {1061 I.replaceAllUsesWith(Builder.CreateICmp(Pred, Res, I.getOperand(1)));1062 return true;1063 }1064 1065 return false;1066}1067 1068// Calculate GEP Stride and accumulated const ModOffset. Return Stride and1069// ModOffset1070static std::pair<APInt, APInt>1071getStrideAndModOffsetOfGEP(Value *PtrOp, const DataLayout &DL) {1072 unsigned BW = DL.getIndexTypeSizeInBits(PtrOp->getType());1073 std::optional<APInt> Stride;1074 APInt ModOffset(BW, 0);1075 // Return a minimum gep stride, greatest common divisor of consective gep1076 // index scales(c.f. Bézout's identity).1077 while (auto *GEP = dyn_cast<GEPOperator>(PtrOp)) {1078 SmallMapVector<Value *, APInt, 4> VarOffsets;1079 if (!GEP->collectOffset(DL, BW, VarOffsets, ModOffset))1080 break;1081 1082 for (auto [V, Scale] : VarOffsets) {1083 // Only keep a power of two factor for non-inbounds1084 if (!GEP->hasNoUnsignedSignedWrap())1085 Scale = APInt::getOneBitSet(Scale.getBitWidth(), Scale.countr_zero());1086 1087 if (!Stride)1088 Stride = Scale;1089 else1090 Stride = APIntOps::GreatestCommonDivisor(*Stride, Scale);1091 }1092 1093 PtrOp = GEP->getPointerOperand();1094 }1095 1096 // Check whether pointer arrives back at Global Variable via at least one GEP.1097 // Even if it doesn't, we can check by alignment.1098 if (!isa<GlobalVariable>(PtrOp) || !Stride)1099 return {APInt(BW, 1), APInt(BW, 0)};1100 1101 // In consideration of signed GEP indices, non-negligible offset become1102 // remainder of division by minimum GEP stride.1103 ModOffset = ModOffset.srem(*Stride);1104 if (ModOffset.isNegative())1105 ModOffset += *Stride;1106 1107 return {*Stride, ModOffset};1108}1109 1110/// If C is a constant patterned array and all valid loaded results for given1111/// alignment are same to a constant, return that constant.1112static bool foldPatternedLoads(Instruction &I, const DataLayout &DL) {1113 auto *LI = dyn_cast<LoadInst>(&I);1114 if (!LI || LI->isVolatile())1115 return false;1116 1117 // We can only fold the load if it is from a constant global with definitive1118 // initializer. Skip expensive logic if this is not the case.1119 auto *PtrOp = LI->getPointerOperand();1120 auto *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(PtrOp));1121 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())1122 return false;1123 1124 // Bail for large initializers in excess of 4K to avoid too many scans.1125 Constant *C = GV->getInitializer();1126 uint64_t GVSize = DL.getTypeAllocSize(C->getType());1127 if (!GVSize || 4096 < GVSize)1128 return false;1129 1130 Type *LoadTy = LI->getType();1131 unsigned BW = DL.getIndexTypeSizeInBits(PtrOp->getType());1132 auto [Stride, ConstOffset] = getStrideAndModOffsetOfGEP(PtrOp, DL);1133 1134 // Any possible offset could be multiple of GEP stride. And any valid1135 // offset is multiple of load alignment, so checking only multiples of bigger1136 // one is sufficient to say results' equality.1137 if (auto LA = LI->getAlign();1138 LA <= GV->getAlign().valueOrOne() && Stride.getZExtValue() < LA.value()) {1139 ConstOffset = APInt(BW, 0);1140 Stride = APInt(BW, LA.value());1141 }1142 1143 Constant *Ca = ConstantFoldLoadFromConst(C, LoadTy, ConstOffset, DL);1144 if (!Ca)1145 return false;1146 1147 unsigned E = GVSize - DL.getTypeStoreSize(LoadTy);1148 for (; ConstOffset.getZExtValue() <= E; ConstOffset += Stride)1149 if (Ca != ConstantFoldLoadFromConst(C, LoadTy, ConstOffset, DL))1150 return false;1151 1152 I.replaceAllUsesWith(Ca);1153 1154 return true;1155}1156 1157namespace {1158class StrNCmpInliner {1159public:1160 StrNCmpInliner(CallInst *CI, LibFunc Func, DomTreeUpdater *DTU,1161 const DataLayout &DL)1162 : CI(CI), Func(Func), DTU(DTU), DL(DL) {}1163 1164 bool optimizeStrNCmp();1165 1166private:1167 void inlineCompare(Value *LHS, StringRef RHS, uint64_t N, bool Swapped);1168 1169 CallInst *CI;1170 LibFunc Func;1171 DomTreeUpdater *DTU;1172 const DataLayout &DL;1173};1174 1175} // namespace1176 1177/// First we normalize calls to strncmp/strcmp to the form of1178/// compare(s1, s2, N), which means comparing first N bytes of s1 and s21179/// (without considering '\0').1180///1181/// Examples:1182///1183/// \code1184/// strncmp(s, "a", 3) -> compare(s, "a", 2)1185/// strncmp(s, "abc", 3) -> compare(s, "abc", 3)1186/// strncmp(s, "a\0b", 3) -> compare(s, "a\0b", 2)1187/// strcmp(s, "a") -> compare(s, "a", 2)1188///1189/// char s2[] = {'a'}1190/// strncmp(s, s2, 3) -> compare(s, s2, 3)1191///1192/// char s2[] = {'a', 'b', 'c', 'd'}1193/// strncmp(s, s2, 3) -> compare(s, s2, 3)1194/// \endcode1195///1196/// We only handle cases where N and exactly one of s1 and s2 are constant.1197/// Cases that s1 and s2 are both constant are already handled by the1198/// instcombine pass.1199///1200/// We do not handle cases where N > StrNCmpInlineThreshold.1201///1202/// We also do not handles cases where N < 2, which are already1203/// handled by the instcombine pass.1204///1205bool StrNCmpInliner::optimizeStrNCmp() {1206 if (StrNCmpInlineThreshold < 2)1207 return false;1208 1209 if (!isOnlyUsedInZeroComparison(CI))1210 return false;1211 1212 Value *Str1P = CI->getArgOperand(0);1213 Value *Str2P = CI->getArgOperand(1);1214 // Should be handled elsewhere.1215 if (Str1P == Str2P)1216 return false;1217 1218 StringRef Str1, Str2;1219 bool HasStr1 = getConstantStringInfo(Str1P, Str1, /*TrimAtNul=*/false);1220 bool HasStr2 = getConstantStringInfo(Str2P, Str2, /*TrimAtNul=*/false);1221 if (HasStr1 == HasStr2)1222 return false;1223 1224 // Note that '\0' and characters after it are not trimmed.1225 StringRef Str = HasStr1 ? Str1 : Str2;1226 Value *StrP = HasStr1 ? Str2P : Str1P;1227 1228 size_t Idx = Str.find('\0');1229 uint64_t N = Idx == StringRef::npos ? UINT64_MAX : Idx + 1;1230 if (Func == LibFunc_strncmp) {1231 if (auto *ConstInt = dyn_cast<ConstantInt>(CI->getArgOperand(2)))1232 N = std::min(N, ConstInt->getZExtValue());1233 else1234 return false;1235 }1236 // Now N means how many bytes we need to compare at most.1237 if (N > Str.size() || N < 2 || N > StrNCmpInlineThreshold)1238 return false;1239 1240 // Cases where StrP has two or more dereferenceable bytes might be better1241 // optimized elsewhere.1242 bool CanBeNull = false, CanBeFreed = false;1243 if (StrP->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed) > 1)1244 return false;1245 inlineCompare(StrP, Str, N, HasStr1);1246 return true;1247}1248 1249/// Convert1250///1251/// \code1252/// ret = compare(s1, s2, N)1253/// \endcode1254///1255/// into1256///1257/// \code1258/// ret = (int)s1[0] - (int)s2[0]1259/// if (ret != 0)1260/// goto NE1261/// ...1262/// ret = (int)s1[N-2] - (int)s2[N-2]1263/// if (ret != 0)1264/// goto NE1265/// ret = (int)s1[N-1] - (int)s2[N-1]1266/// NE:1267/// \endcode1268///1269/// CFG before and after the transformation:1270///1271/// (before)1272/// BBCI1273///1274/// (after)1275/// BBCI -> BBSubs[0] (sub,icmp) --NE-> BBNE -> BBTail1276/// | ^1277/// E |1278/// | |1279/// BBSubs[1] (sub,icmp) --NE-----+1280/// ... |1281/// BBSubs[N-1] (sub) ---------+1282///1283void StrNCmpInliner::inlineCompare(Value *LHS, StringRef RHS, uint64_t N,1284 bool Swapped) {1285 auto &Ctx = CI->getContext();1286 IRBuilder<> B(Ctx);1287 // We want these instructions to be recognized as inlined instructions for the1288 // compare call, but we don't have a source location for the definition of1289 // that function, since we're generating that code now. Because the generated1290 // code is a viable point for a memory access error, we make the pragmatic1291 // choice here to directly use CI's location so that we have useful1292 // attribution for the generated code.1293 B.SetCurrentDebugLocation(CI->getDebugLoc());1294 1295 BasicBlock *BBCI = CI->getParent();1296 BasicBlock *BBTail =1297 SplitBlock(BBCI, CI, DTU, nullptr, nullptr, BBCI->getName() + ".tail");1298 1299 SmallVector<BasicBlock *> BBSubs;1300 for (uint64_t I = 0; I < N; ++I)1301 BBSubs.push_back(1302 BasicBlock::Create(Ctx, "sub_" + Twine(I), BBCI->getParent(), BBTail));1303 BasicBlock *BBNE = BasicBlock::Create(Ctx, "ne", BBCI->getParent(), BBTail);1304 1305 cast<BranchInst>(BBCI->getTerminator())->setSuccessor(0, BBSubs[0]);1306 1307 B.SetInsertPoint(BBNE);1308 PHINode *Phi = B.CreatePHI(CI->getType(), N);1309 B.CreateBr(BBTail);1310 1311 Value *Base = LHS;1312 for (uint64_t i = 0; i < N; ++i) {1313 B.SetInsertPoint(BBSubs[i]);1314 Value *VL =1315 B.CreateZExt(B.CreateLoad(B.getInt8Ty(),1316 B.CreateInBoundsPtrAdd(Base, B.getInt64(i))),1317 CI->getType());1318 Value *VR =1319 ConstantInt::get(CI->getType(), static_cast<unsigned char>(RHS[i]));1320 Value *Sub = Swapped ? B.CreateSub(VR, VL) : B.CreateSub(VL, VR);1321 if (i < N - 1) {1322 BranchInst *CondBrInst = B.CreateCondBr(1323 B.CreateICmpNE(Sub, ConstantInt::get(CI->getType(), 0)), BBNE,1324 BBSubs[i + 1]);1325 1326 Function *F = CI->getFunction();1327 assert(F && "Instruction does not belong to a function!");1328 std::optional<Function::ProfileCount> EC = F->getEntryCount();1329 if (EC && EC->getCount() > 0)1330 setExplicitlyUnknownBranchWeights(*CondBrInst, DEBUG_TYPE);1331 } else {1332 B.CreateBr(BBNE);1333 }1334 1335 Phi->addIncoming(Sub, BBSubs[i]);1336 }1337 1338 CI->replaceAllUsesWith(Phi);1339 CI->eraseFromParent();1340 1341 if (DTU) {1342 SmallVector<DominatorTree::UpdateType, 8> Updates;1343 Updates.push_back({DominatorTree::Insert, BBCI, BBSubs[0]});1344 for (uint64_t i = 0; i < N; ++i) {1345 if (i < N - 1)1346 Updates.push_back({DominatorTree::Insert, BBSubs[i], BBSubs[i + 1]});1347 Updates.push_back({DominatorTree::Insert, BBSubs[i], BBNE});1348 }1349 Updates.push_back({DominatorTree::Insert, BBNE, BBTail});1350 Updates.push_back({DominatorTree::Delete, BBCI, BBTail});1351 DTU->applyUpdates(Updates);1352 }1353}1354 1355/// Convert memchr with a small constant string into a switch1356static bool foldMemChr(CallInst *Call, DomTreeUpdater *DTU,1357 const DataLayout &DL) {1358 if (isa<Constant>(Call->getArgOperand(1)))1359 return false;1360 1361 StringRef Str;1362 Value *Base = Call->getArgOperand(0);1363 if (!getConstantStringInfo(Base, Str, /*TrimAtNul=*/false))1364 return false;1365 1366 uint64_t N = Str.size();1367 if (auto *ConstInt = dyn_cast<ConstantInt>(Call->getArgOperand(2))) {1368 uint64_t Val = ConstInt->getZExtValue();1369 // Ignore the case that n is larger than the size of string.1370 if (Val > N)1371 return false;1372 N = Val;1373 } else1374 return false;1375 1376 if (N > MemChrInlineThreshold)1377 return false;1378 1379 BasicBlock *BB = Call->getParent();1380 BasicBlock *BBNext = SplitBlock(BB, Call, DTU);1381 IRBuilder<> IRB(BB);1382 IRB.SetCurrentDebugLocation(Call->getDebugLoc());1383 IntegerType *ByteTy = IRB.getInt8Ty();1384 BB->getTerminator()->eraseFromParent();1385 SwitchInst *SI = IRB.CreateSwitch(1386 IRB.CreateTrunc(Call->getArgOperand(1), ByteTy), BBNext, N);1387 // We can't know the precise weights here, as they would depend on the value1388 // distribution of Call->getArgOperand(1). So we just mark it as "unknown".1389 setExplicitlyUnknownBranchWeightsIfProfiled(*SI, DEBUG_TYPE);1390 Type *IndexTy = DL.getIndexType(Call->getType());1391 SmallVector<DominatorTree::UpdateType, 8> Updates;1392 1393 BasicBlock *BBSuccess = BasicBlock::Create(1394 Call->getContext(), "memchr.success", BB->getParent(), BBNext);1395 IRB.SetInsertPoint(BBSuccess);1396 PHINode *IndexPHI = IRB.CreatePHI(IndexTy, N, "memchr.idx");1397 Value *FirstOccursLocation = IRB.CreateInBoundsPtrAdd(Base, IndexPHI);1398 IRB.CreateBr(BBNext);1399 if (DTU)1400 Updates.push_back({DominatorTree::Insert, BBSuccess, BBNext});1401 1402 SmallPtrSet<ConstantInt *, 4> Cases;1403 for (uint64_t I = 0; I < N; ++I) {1404 ConstantInt *CaseVal = ConstantInt::get(ByteTy, Str[I]);1405 if (!Cases.insert(CaseVal).second)1406 continue;1407 1408 BasicBlock *BBCase = BasicBlock::Create(Call->getContext(), "memchr.case",1409 BB->getParent(), BBSuccess);1410 SI->addCase(CaseVal, BBCase);1411 IRB.SetInsertPoint(BBCase);1412 IndexPHI->addIncoming(ConstantInt::get(IndexTy, I), BBCase);1413 IRB.CreateBr(BBSuccess);1414 if (DTU) {1415 Updates.push_back({DominatorTree::Insert, BB, BBCase});1416 Updates.push_back({DominatorTree::Insert, BBCase, BBSuccess});1417 }1418 }1419 1420 PHINode *PHI =1421 PHINode::Create(Call->getType(), 2, Call->getName(), BBNext->begin());1422 PHI->addIncoming(Constant::getNullValue(Call->getType()), BB);1423 PHI->addIncoming(FirstOccursLocation, BBSuccess);1424 1425 Call->replaceAllUsesWith(PHI);1426 Call->eraseFromParent();1427 1428 if (DTU)1429 DTU->applyUpdates(Updates);1430 1431 return true;1432}1433 1434static bool foldLibCalls(Instruction &I, TargetTransformInfo &TTI,1435 TargetLibraryInfo &TLI, AssumptionCache &AC,1436 DominatorTree &DT, const DataLayout &DL,1437 bool &MadeCFGChange) {1438 1439 auto *CI = dyn_cast<CallInst>(&I);1440 if (!CI || CI->isNoBuiltin())1441 return false;1442 1443 Function *CalledFunc = CI->getCalledFunction();1444 if (!CalledFunc)1445 return false;1446 1447 LibFunc LF;1448 if (!TLI.getLibFunc(*CalledFunc, LF) ||1449 !isLibFuncEmittable(CI->getModule(), &TLI, LF))1450 return false;1451 1452 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);1453 1454 switch (LF) {1455 case LibFunc_sqrt:1456 case LibFunc_sqrtf:1457 case LibFunc_sqrtl:1458 return foldSqrt(CI, LF, TTI, TLI, AC, DT);1459 case LibFunc_strcmp:1460 case LibFunc_strncmp:1461 if (StrNCmpInliner(CI, LF, &DTU, DL).optimizeStrNCmp()) {1462 MadeCFGChange = true;1463 return true;1464 }1465 break;1466 case LibFunc_memchr:1467 if (foldMemChr(CI, &DTU, DL)) {1468 MadeCFGChange = true;1469 return true;1470 }1471 break;1472 default:;1473 }1474 return false;1475}1476 1477/// Match high part of long multiplication.1478///1479/// Considering a multiply made up of high and low parts, we can split the1480/// multiply into:1481/// x * y == (xh*T + xl) * (yh*T + yl)1482/// where xh == x>>32 and xl == x & 0xffffffff. T = 2^32.1483/// This expands to1484/// xh*yh*T*T + xh*yl*T + xl*yh*T + xl*yl1485/// which can be drawn as1486/// [ xh*yh ]1487/// [ xh*yl ]1488/// [ xl*yh ]1489/// [ xl*yl ]1490/// We are looking for the "high" half, which is xh*yh + xh*yl>>32 + xl*yh>>32 +1491/// some carrys. The carry makes this difficult and there are multiple ways of1492/// representing it. The ones we attempt to support here are:1493/// Carry: xh*yh + carry + lowsum1494/// carry = lowsum < xh*yl ? 0x1000000 : 01495/// lowsum = xh*yl + xl*yh + (xl*yl>>32)1496/// Ladder: xh*yh + c2>>32 + c3>>321497/// c2 = xh*yl + (xl*yl>>32); c3 = c2&0xffffffff + xl*yh1498/// or c2 = (xl*yh&0xffffffff) + xh*yl + (xl*yl>>32); c3 = xl*yh1499/// Carry4: xh*yh + carry + crosssum>>32 + (xl*yl + crosssum&0xffffffff) >> 321500/// crosssum = xh*yl + xl*yh1501/// carry = crosssum < xh*yl ? 0x1000000 : 01502/// Ladder4: xh*yh + (xl*yh)>>32 + (xh*yl)>>32 + low>>32;1503/// low = (xl*yl)>>32 + (xl*yh)&0xffffffff + (xh*yl)&0xffffffff1504///1505/// They all start by matching xh*yh + 2 or 3 other operands. The bottom of the1506/// tree is xh*yh, xh*yl, xl*yh and xl*yl.1507static bool foldMulHigh(Instruction &I) {1508 Type *Ty = I.getType();1509 if (!Ty->isIntOrIntVectorTy())1510 return false;1511 1512 unsigned BitWidth = Ty->getScalarSizeInBits();1513 APInt LowMask = APInt::getLowBitsSet(BitWidth, BitWidth / 2);1514 if (BitWidth % 2 != 0)1515 return false;1516 1517 auto CreateMulHigh = [&](Value *X, Value *Y) {1518 IRBuilder<> Builder(&I);1519 Type *NTy = Ty->getWithNewBitWidth(BitWidth * 2);1520 Value *XExt = Builder.CreateZExt(X, NTy);1521 Value *YExt = Builder.CreateZExt(Y, NTy);1522 Value *Mul = Builder.CreateMul(XExt, YExt, "", /*HasNUW=*/true);1523 Value *High = Builder.CreateLShr(Mul, BitWidth);1524 Value *Res = Builder.CreateTrunc(High, Ty, "", /*HasNUW=*/true);1525 Res->takeName(&I);1526 I.replaceAllUsesWith(Res);1527 LLVM_DEBUG(dbgs() << "Created long multiply from parts of " << *X << " and "1528 << *Y << "\n");1529 return true;1530 };1531 1532 // Common check routines for X_lo*Y_lo and X_hi*Y_lo1533 auto CheckLoLo = [&](Value *XlYl, Value *X, Value *Y) {1534 return match(XlYl, m_c_Mul(m_And(m_Specific(X), m_SpecificInt(LowMask)),1535 m_And(m_Specific(Y), m_SpecificInt(LowMask))));1536 };1537 auto CheckHiLo = [&](Value *XhYl, Value *X, Value *Y) {1538 return match(XhYl,1539 m_c_Mul(m_LShr(m_Specific(X), m_SpecificInt(BitWidth / 2)),1540 m_And(m_Specific(Y), m_SpecificInt(LowMask))));1541 };1542 1543 auto FoldMulHighCarry = [&](Value *X, Value *Y, Instruction *Carry,1544 Instruction *B) {1545 // Looking for LowSum >> 32 and carry (select)1546 if (Carry->getOpcode() != Instruction::Select)1547 std::swap(Carry, B);1548 1549 // Carry = LowSum < XhYl ? 0x100000000 : 01550 Value *LowSum, *XhYl;1551 if (!match(Carry,1552 m_OneUse(m_Select(1553 m_OneUse(m_SpecificICmp(ICmpInst::ICMP_ULT, m_Value(LowSum),1554 m_Value(XhYl))),1555 m_SpecificInt(APInt::getOneBitSet(BitWidth, BitWidth / 2)),1556 m_Zero()))))1557 return false;1558 1559 // XhYl can be Xh*Yl or Xl*Yh1560 if (!CheckHiLo(XhYl, X, Y)) {1561 if (CheckHiLo(XhYl, Y, X))1562 std::swap(X, Y);1563 else1564 return false;1565 }1566 if (XhYl->hasNUsesOrMore(3))1567 return false;1568 1569 // B = LowSum >> 321570 if (!match(B, m_OneUse(m_LShr(m_Specific(LowSum),1571 m_SpecificInt(BitWidth / 2)))) ||1572 LowSum->hasNUsesOrMore(3))1573 return false;1574 1575 // LowSum = XhYl + XlYh + XlYl>>321576 Value *XlYh, *XlYl;1577 auto XlYlHi = m_LShr(m_Value(XlYl), m_SpecificInt(BitWidth / 2));1578 if (!match(LowSum,1579 m_c_Add(m_Specific(XhYl),1580 m_OneUse(m_c_Add(m_OneUse(m_Value(XlYh)), XlYlHi)))) &&1581 !match(LowSum, m_c_Add(m_OneUse(m_Value(XlYh)),1582 m_OneUse(m_c_Add(m_Specific(XhYl), XlYlHi)))) &&1583 !match(LowSum,1584 m_c_Add(XlYlHi, m_OneUse(m_c_Add(m_Specific(XhYl),1585 m_OneUse(m_Value(XlYh)))))))1586 return false;1587 1588 // Check XlYl and XlYh1589 if (!CheckLoLo(XlYl, X, Y))1590 return false;1591 if (!CheckHiLo(XlYh, Y, X))1592 return false;1593 1594 return CreateMulHigh(X, Y);1595 };1596 1597 auto FoldMulHighLadder = [&](Value *X, Value *Y, Instruction *A,1598 Instruction *B) {1599 // xh*yh + c2>>32 + c3>>321600 // c2 = xh*yl + (xl*yl>>32); c3 = c2&0xffffffff + xl*yh1601 // or c2 = (xl*yh&0xffffffff) + xh*yl + (xl*yl>>32); c3 = xh*yl1602 Value *XlYh, *XhYl, *XlYl, *C2, *C3;1603 // Strip off the two expected shifts.1604 if (!match(A, m_LShr(m_Value(C2), m_SpecificInt(BitWidth / 2))) ||1605 !match(B, m_LShr(m_Value(C3), m_SpecificInt(BitWidth / 2))))1606 return false;1607 1608 if (match(C3, m_c_Add(m_Add(m_Value(), m_Value()), m_Value())))1609 std::swap(C2, C3);1610 // Try to match c2 = (xl*yh&0xffffffff) + xh*yl + (xl*yl>>32)1611 if (match(C2,1612 m_c_Add(m_c_Add(m_And(m_Specific(C3), m_SpecificInt(LowMask)),1613 m_Value(XlYh)),1614 m_LShr(m_Value(XlYl), m_SpecificInt(BitWidth / 2)))) ||1615 match(C2, m_c_Add(m_c_Add(m_And(m_Specific(C3), m_SpecificInt(LowMask)),1616 m_LShr(m_Value(XlYl),1617 m_SpecificInt(BitWidth / 2))),1618 m_Value(XlYh))) ||1619 match(C2, m_c_Add(m_c_Add(m_LShr(m_Value(XlYl),1620 m_SpecificInt(BitWidth / 2)),1621 m_Value(XlYh)),1622 m_And(m_Specific(C3), m_SpecificInt(LowMask))))) {1623 XhYl = C3;1624 } else {1625 // Match c3 = c2&0xffffffff + xl*yh1626 if (!match(C3, m_c_Add(m_And(m_Specific(C2), m_SpecificInt(LowMask)),1627 m_Value(XlYh))))1628 std::swap(C2, C3);1629 if (!match(C3, m_c_Add(m_OneUse(1630 m_And(m_Specific(C2), m_SpecificInt(LowMask))),1631 m_Value(XlYh))) ||1632 !C3->hasOneUse() || C2->hasNUsesOrMore(3))1633 return false;1634 1635 // Match c2 = xh*yl + (xl*yl >> 32)1636 if (!match(C2, m_c_Add(m_LShr(m_Value(XlYl), m_SpecificInt(BitWidth / 2)),1637 m_Value(XhYl))))1638 return false;1639 }1640 1641 // Match XhYl and XlYh - they can appear either way around.1642 if (!CheckHiLo(XlYh, Y, X))1643 std::swap(XlYh, XhYl);1644 if (!CheckHiLo(XlYh, Y, X))1645 return false;1646 if (!CheckHiLo(XhYl, X, Y))1647 return false;1648 if (!CheckLoLo(XlYl, X, Y))1649 return false;1650 1651 return CreateMulHigh(X, Y);1652 };1653 1654 auto FoldMulHighLadder4 = [&](Value *X, Value *Y, Instruction *A,1655 Instruction *B, Instruction *C) {1656 /// Ladder4: xh*yh + (xl*yh)>>32 + (xh+yl)>>32 + low>>32;1657 /// low = (xl*yl)>>32 + (xl*yh)&0xffffffff + (xh*yl)&0xffffffff1658 1659 // Find A = Low >> 32 and B/C = XhYl>>32, XlYh>>32.1660 auto ShiftAdd =1661 m_LShr(m_Add(m_Value(), m_Value()), m_SpecificInt(BitWidth / 2));1662 if (!match(A, ShiftAdd))1663 std::swap(A, B);1664 if (!match(A, ShiftAdd))1665 std::swap(A, C);1666 Value *Low;1667 if (!match(A, m_LShr(m_OneUse(m_Value(Low)), m_SpecificInt(BitWidth / 2))))1668 return false;1669 1670 // Match B == XhYl>>32 and C == XlYh>>321671 Value *XhYl, *XlYh;1672 if (!match(B, m_LShr(m_Value(XhYl), m_SpecificInt(BitWidth / 2))) ||1673 !match(C, m_LShr(m_Value(XlYh), m_SpecificInt(BitWidth / 2))))1674 return false;1675 if (!CheckHiLo(XhYl, X, Y))1676 std::swap(XhYl, XlYh);1677 if (!CheckHiLo(XhYl, X, Y) || XhYl->hasNUsesOrMore(3))1678 return false;1679 if (!CheckHiLo(XlYh, Y, X) || XlYh->hasNUsesOrMore(3))1680 return false;1681 1682 // Match Low as XlYl>>32 + XhYl&0xffffffff + XlYh&0xffffffff1683 Value *XlYl;1684 if (!match(1685 Low,1686 m_c_Add(1687 m_OneUse(m_c_Add(1688 m_OneUse(m_And(m_Specific(XhYl), m_SpecificInt(LowMask))),1689 m_OneUse(m_And(m_Specific(XlYh), m_SpecificInt(LowMask))))),1690 m_OneUse(1691 m_LShr(m_Value(XlYl), m_SpecificInt(BitWidth / 2))))) &&1692 !match(1693 Low,1694 m_c_Add(1695 m_OneUse(m_c_Add(1696 m_OneUse(m_And(m_Specific(XhYl), m_SpecificInt(LowMask))),1697 m_OneUse(1698 m_LShr(m_Value(XlYl), m_SpecificInt(BitWidth / 2))))),1699 m_OneUse(m_And(m_Specific(XlYh), m_SpecificInt(LowMask))))) &&1700 !match(1701 Low,1702 m_c_Add(1703 m_OneUse(m_c_Add(1704 m_OneUse(m_And(m_Specific(XlYh), m_SpecificInt(LowMask))),1705 m_OneUse(1706 m_LShr(m_Value(XlYl), m_SpecificInt(BitWidth / 2))))),1707 m_OneUse(m_And(m_Specific(XhYl), m_SpecificInt(LowMask))))))1708 return false;1709 if (!CheckLoLo(XlYl, X, Y))1710 return false;1711 1712 return CreateMulHigh(X, Y);1713 };1714 1715 auto FoldMulHighCarry4 = [&](Value *X, Value *Y, Instruction *Carry,1716 Instruction *B, Instruction *C) {1717 // xh*yh + carry + crosssum>>32 + (xl*yl + crosssum&0xffffffff) >> 321718 // crosssum = xh*yl+xl*yh1719 // carry = crosssum < xh*yl ? 0x1000000 : 01720 if (Carry->getOpcode() != Instruction::Select)1721 std::swap(Carry, B);1722 if (Carry->getOpcode() != Instruction::Select)1723 std::swap(Carry, C);1724 1725 // Carry = CrossSum < XhYl ? 0x100000000 : 01726 Value *CrossSum, *XhYl;1727 if (!match(Carry,1728 m_OneUse(m_Select(1729 m_OneUse(m_SpecificICmp(ICmpInst::ICMP_ULT,1730 m_Value(CrossSum), m_Value(XhYl))),1731 m_SpecificInt(APInt::getOneBitSet(BitWidth, BitWidth / 2)),1732 m_Zero()))))1733 return false;1734 1735 if (!match(B, m_LShr(m_Specific(CrossSum), m_SpecificInt(BitWidth / 2))))1736 std::swap(B, C);1737 if (!match(B, m_LShr(m_Specific(CrossSum), m_SpecificInt(BitWidth / 2))))1738 return false;1739 1740 Value *XlYl, *LowAccum;1741 if (!match(C, m_LShr(m_Value(LowAccum), m_SpecificInt(BitWidth / 2))) ||1742 !match(LowAccum, m_c_Add(m_OneUse(m_LShr(m_Value(XlYl),1743 m_SpecificInt(BitWidth / 2))),1744 m_OneUse(m_And(m_Specific(CrossSum),1745 m_SpecificInt(LowMask))))) ||1746 LowAccum->hasNUsesOrMore(3))1747 return false;1748 if (!CheckLoLo(XlYl, X, Y))1749 return false;1750 1751 if (!CheckHiLo(XhYl, X, Y))1752 std::swap(X, Y);1753 if (!CheckHiLo(XhYl, X, Y))1754 return false;1755 Value *XlYh;1756 if (!match(CrossSum, m_c_Add(m_Specific(XhYl), m_OneUse(m_Value(XlYh)))) ||1757 !CheckHiLo(XlYh, Y, X) || CrossSum->hasNUsesOrMore(4) ||1758 XhYl->hasNUsesOrMore(3))1759 return false;1760 1761 return CreateMulHigh(X, Y);1762 };1763 1764 // X and Y are the two inputs, A, B and C are other parts of the pattern1765 // (crosssum>>32, carry, etc).1766 Value *X, *Y;1767 Instruction *A, *B, *C;1768 auto HiHi = m_OneUse(m_Mul(m_LShr(m_Value(X), m_SpecificInt(BitWidth / 2)),1769 m_LShr(m_Value(Y), m_SpecificInt(BitWidth / 2))));1770 if ((match(&I, m_c_Add(HiHi, m_OneUse(m_Add(m_Instruction(A),1771 m_Instruction(B))))) ||1772 match(&I, m_c_Add(m_Instruction(A),1773 m_OneUse(m_c_Add(HiHi, m_Instruction(B)))))) &&1774 A->hasOneUse() && B->hasOneUse())1775 if (FoldMulHighCarry(X, Y, A, B) || FoldMulHighLadder(X, Y, A, B))1776 return true;1777 1778 if ((match(&I, m_c_Add(HiHi, m_OneUse(m_c_Add(1779 m_Instruction(A),1780 m_OneUse(m_Add(m_Instruction(B),1781 m_Instruction(C))))))) ||1782 match(&I, m_c_Add(m_Instruction(A),1783 m_OneUse(m_c_Add(1784 HiHi, m_OneUse(m_Add(m_Instruction(B),1785 m_Instruction(C))))))) ||1786 match(&I, m_c_Add(m_Instruction(A),1787 m_OneUse(m_c_Add(1788 m_Instruction(B),1789 m_OneUse(m_c_Add(HiHi, m_Instruction(C))))))) ||1790 match(&I,1791 m_c_Add(m_OneUse(m_c_Add(HiHi, m_Instruction(A))),1792 m_OneUse(m_Add(m_Instruction(B), m_Instruction(C)))))) &&1793 A->hasOneUse() && B->hasOneUse() && C->hasOneUse())1794 return FoldMulHighCarry4(X, Y, A, B, C) ||1795 FoldMulHighLadder4(X, Y, A, B, C);1796 1797 return false;1798}1799 1800/// This is the entry point for folds that could be implemented in regular1801/// InstCombine, but they are separated because they are not expected to1802/// occur frequently and/or have more than a constant-length pattern match.1803static bool foldUnusualPatterns(Function &F, DominatorTree &DT,1804 TargetTransformInfo &TTI,1805 TargetLibraryInfo &TLI, AliasAnalysis &AA,1806 AssumptionCache &AC, bool &MadeCFGChange) {1807 bool MadeChange = false;1808 for (BasicBlock &BB : F) {1809 // Ignore unreachable basic blocks.1810 if (!DT.isReachableFromEntry(&BB))1811 continue;1812 1813 const DataLayout &DL = F.getDataLayout();1814 1815 // Walk the block backwards for efficiency. We're matching a chain of1816 // use->defs, so we're more likely to succeed by starting from the bottom.1817 // Also, we want to avoid matching partial patterns.1818 // TODO: It would be more efficient if we removed dead instructions1819 // iteratively in this loop rather than waiting until the end.1820 for (Instruction &I : make_early_inc_range(llvm::reverse(BB))) {1821 MadeChange |= foldAnyOrAllBitsSet(I);1822 MadeChange |= foldGuardedFunnelShift(I, DT);1823 MadeChange |= tryToRecognizePopCount(I);1824 MadeChange |= tryToFPToSat(I, TTI);1825 MadeChange |= tryToRecognizeTableBasedCttz(I, DL);1826 MadeChange |= foldConsecutiveLoads(I, DL, TTI, AA, DT);1827 MadeChange |= foldPatternedLoads(I, DL);1828 MadeChange |= foldICmpOrChain(I, DL, TTI, AA, DT);1829 MadeChange |= foldMulHigh(I);1830 // NOTE: This function introduces erasing of the instruction `I`, so it1831 // needs to be called at the end of this sequence, otherwise we may make1832 // bugs.1833 MadeChange |= foldLibCalls(I, TTI, TLI, AC, DT, DL, MadeCFGChange);1834 }1835 1836 // Do this separately to avoid redundantly scanning stores multiple times.1837 MadeChange |= foldConsecutiveStores(BB, DL, TTI, AA);1838 }1839 1840 // We're done with transforms, so remove dead instructions.1841 if (MadeChange)1842 for (BasicBlock &BB : F)1843 SimplifyInstructionsInBlock(&BB);1844 1845 return MadeChange;1846}1847 1848/// This is the entry point for all transforms. Pass manager differences are1849/// handled in the callers of this function.1850static bool runImpl(Function &F, AssumptionCache &AC, TargetTransformInfo &TTI,1851 TargetLibraryInfo &TLI, DominatorTree &DT,1852 AliasAnalysis &AA, bool &MadeCFGChange) {1853 bool MadeChange = false;1854 const DataLayout &DL = F.getDataLayout();1855 TruncInstCombine TIC(AC, TLI, DL, DT);1856 MadeChange |= TIC.run(F);1857 MadeChange |= foldUnusualPatterns(F, DT, TTI, TLI, AA, AC, MadeCFGChange);1858 return MadeChange;1859}1860 1861PreservedAnalyses AggressiveInstCombinePass::run(Function &F,1862 FunctionAnalysisManager &AM) {1863 auto &AC = AM.getResult<AssumptionAnalysis>(F);1864 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);1865 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);1866 auto &TTI = AM.getResult<TargetIRAnalysis>(F);1867 auto &AA = AM.getResult<AAManager>(F);1868 bool MadeCFGChange = false;1869 if (!runImpl(F, AC, TTI, TLI, DT, AA, MadeCFGChange)) {1870 // No changes, all analyses are preserved.1871 return PreservedAnalyses::all();1872 }1873 // Mark all the analyses that instcombine updates as preserved.1874 PreservedAnalyses PA;1875 if (MadeCFGChange)1876 PA.preserve<DominatorTreeAnalysis>();1877 else1878 PA.preserveSet<CFGAnalyses>();1879 return PA;1880}1881